使用迭代器操作单链表
目录
一、引言
迭代器功能类似指针，也可以说迭代器就是一个“指针”。指针最重要的两个功能就是*和->。前者是解引用；后者是指向所指之物的成员。
二、举例说明
为了看起来更加直观，将一个源文件分割成若*分：
2.1 实现结点类
结点类包含2个私有数据成员：元素和指针。公有方法有：构造方法以及两个接口（返回元素的值、返回指针的值）。我们还知道，在其他类中是没有办法访问本类私有成员的，很明显:头插法insert_front(T value)和尾插法insert_back(T value)需要改变结点的（私有）元素和（私有）指针，故而添加有元——封装和暴露之间我们需要做一个均衡。
析构方法在这种情形下，使用默认的析构方法是可以的。因为并没有向堆申请空间！
template <typename T>
class ListItem //结点类
{
public:
ListItem(T value = 0, ListItem *next = 0):_value(value),_next(next){}
T value() const { return _value; } //返回本结点元素值
ListItem *next() const { return _next; } //返回本结点的指针值
private:
T _value;
ListItem* _next;
friend void List<T>::insert_front(T value);
friend void List<T>::insert_back(T value);
};2.2 实现单链表类
单链表的实现方式多种多样，但只要不违背单链表的定义（“结点的序列”表示线性表）就可以了。在这里，我采用不带头结点的实现方式。类中私有成员是：头指针、尾指针、记录当前结点个数的变量。公有方法有：构造、头插、尾插、返回头指针的值、头删、析构（一旦向堆区申请空间必须要实现自己的析构方法，否则会造成内存泄露）、打印输出、返回链表大小。
#include<assert.h>
#include<iostream>
using namespace std;
template<typename T>
class ListItem;
template<typename T>
class List //单链表类
{
public:
List() { _front = NULL; _end = NULL; _size = 0; } //构造函数
void insert_front(T value); //头插
void insert_back(T value); //尾插
ListItem<T>* front(); //返回头指针的值
void delete_front(); //头删
~List(); //析构
void display(std::ostream &os = std::cout) const; //打印输出
int size();
private:
ListItem<T> *_front;
ListItem<T> *_end;
long _size;
};
template<typename T>
void List<T>::insert_front(T value) //头部插入
{
ListItem<T> *p = new ListItem<T>; //申请一个结点
assert(NULL != p);
p->_value = value;
if (NULL == _front && NULL == _end) //单链表为空时，头指针和尾指针都要移动;
{
_front = _end = p;
}
else { //单链表非空时，只需移动头指针;
p->_next = _front;
_front = p;
}
_size++;
}
template<typename T>
void List<T>::insert_back(T value) //尾插法
{
ListItem<T> *p = new ListItem<T>; //申请一个结点
assert(NULL != p);
p->_value = value;
if (NULL == _front && NULL == _end) //单链表为空时，头指针和尾指针都要移动;
{
_front = _end = p;
}
else
{
_end->_next = p;
_end = p;
}
_size++;
}
template<typename T>
ListItem<T>* List<T>::front() //返回头指针的值
{
return _front;
}
template<typename T>
void List<T>::delete_front() //头删，单链表尾删不方便处理
{
int size = this->size();
if (0 == size) return; //单链表已空，无法删除
if (1 == size) //单链表中只含1个节点
{
delete _front;
_front = _end = NULL;
}
else
{
ListItem<T>*p = _front->next();
delete _front;
_front = p;
}
--_size;
}
template<typename T>
List<T>::~List() //析构
{
cout << "~List()析构函数正被调用" << endl;
while (this->size())
{
delete_front();
}
}
template<typename T>
void List<T>::display(std::ostream & os) const //打印输出链表
{
ListItem<T> *p = _front;
while (NULL != p && p != _end)
{
os << p->_value<<" ";
p = p->next();
}
os << endl;
}
template<typename T>
int List<T>::size() //返回当前链表大小
{
return _size;
}
2.3 实现迭代器
用结构体实现，默认权限为public！
迭代器是对指针的一次“封装”，指针能做到的事情，迭代器也自然需要做到（如果做不到的话为什么要使用迭代器呢？）。迭代器的成员是指针。迭代器需要做到的事有：解引用、访问数据成员、自加（前置和后置）、赋值、逻辑（不）相等······并没有列举完，只是将典型的拿出来讨论了。
在撰写这篇博客的过程当中，对自增运算符的重载遇到了比较多的问题，大家引起注意！
一部分代码段：
ListIter& operator ++() //pre-increment operator
{
_ptr = _ptr->next();
return *_this;
}
//必须先实现前置++的重载才能去实现后置++的重载，否则语句++*this;会报错，编译器会提示你没有实现前置++运算符的重载函数！
ListIter operator++(int) //post-increment operator
{
ListIter tmp = *this;
++*this;
return tmp; //返回值是迭代器自增之前的值
}完整代码段 ：
template<class Item> //迭代器适用于任何形态的结点；因为结构体中含有自增，故而该迭代器特定只为链表服务。
struct ListIter
{
Item *_ptr;
ListIter(Item *p = 0):_ptr(p){} //构造方法
Item &operator *() const { return *_ptr; }
Item *operator ->() const { return _ptr; }
//不必实现copy ctor和operator=，因为编译器提供的缺省行为已经足够
ListIter& operator ++() //pre-increment operator
{
_ptr = _ptr->next();
return *_this;
}
//必须先实现前置++的重载才能去实现后置++的重载，否则语句++*this;会报错，编译器会提示你没有实现前置++运算符的重载函数！
ListIter operator++(int) //post-increment operator
{
ListIter tmp = *this;
++*this;
return tmp; //返回值是迭代器自增之前的值
}
bool operator == (const ListIter &i) const
{
return _ptr == _i._ptr;
}
bool operator !=(const ListIter &i)const
{
return _ptr != i._ptr;
}
};2.4 实现全局查找函数
template<typename T>
bool operator != (const ListItem<T>& item, T n)
{
return item.value() != n;
}
template<class InputIterator, class T> //全局函数：功能为查找元素
InputIterator ownfind(InputIterator first, InputIterator last, const T& value)
{
while (first != last && *first != value)
++first;
return first;
}说明：为什么要重载“！=”运算符呢？ 可以想象一下，在函数ownfind使用过程中，一定是ownfind(first, last, value)，迭代器所指之物是结点本身，那么对迭代器进行解引用的话——是结点类型，结点类型如何能去与结点中元素值去比较呢？那有人有疑问了，结点不是实现了返回元素值的方法value()吗？直接把ownfind函数改造一下不就好了？就像下面的样子。我的回答是：ownfind函数在设计的时候并不知道迭代器所指对象中有无包含该方法，按照下面的写法，是对ownfind函数泛型的限制。我们可以在获取到ownfind函数，再进行处理。就像全局查找函数实现的那样去做。
培养泛型思维是很重要的！
template<class InputIterator, class T> //全局函数：功能为查找元素
InputIterator ownfind(InputIterator first, InputIterator last, const T& value)
{
while (first != last && *first.value() != value)
++first;
return first;
}三、测试用例
int main()
{
List<int> mylist;
for (int i = 0; i < 5; ++i)
{
mylist.insert_front(i);
mylist.insert_back(i + 2);
}
mylist.display();
//对于迭代器来说，参数列表中应该填写其所指之物
ListIter<ListItem<int>>begin(mylist.front());
ListIter<ListItem<int>>end; //default 0, NULL
ListIter<ListItem<int>>iter; //defaule 0, NULL
iter = ownfind(begin, end, 90);
if (iter == end)
cout << "not found!" << endl;
else
cout << "found" << endl;
system("pause");
return 0;
}四、结束语
例子虽小，但是帮助我们了解迭代器还是绰绰有余的。计算机科学是讲究实用性的，有时候实用比理论更重要。吾尝终日而思矣，不如登高之博见也。