一、迭代器作用

       在设计模式中有一种模式叫迭代器模式，简单来说就是提供一种方法，在不需要暴露某个容器的内部表现形式情况下，使之能依次访问该容器中的各个元素，这种设计思维在STL中得到了广泛的应用，是STL的关键所在，通过迭代器，容器和算法可以有机的粘合在一起，只要对算法给予不同的迭代器，就可以对不同容器进行相同的操作。在这里提到了一个叫迭代器的东西，说得简单一点，就是一种指针，学习C和C++的同学肯定不会对指针感到陌生，这确实是个让我们又爱又恨的东西。不曾忘记，因为指针操作引起的内存泄露、段错误而彻夜难眠；也不曾忘记，因为指针的灵活和强大，让我们自由地游刃在内存之中。以下以算法find为例，展示了容器、算法和迭代器如何合作：

template<typename InputIterator, typename T>
InputIterator find(InputIterator first, InputIterator last, const T &value)
{while (first != last && *frist != value)++first;return first;
}

        从以上代码可以看到，算法通过传入的迭代器，顺序访问容器中的元素，寻找并返回符合条件的元素。通过向算法传入指向不同容器的迭代器，实现了算法以相同的逻辑对不同容器的访问。

二、 迭代器的重要特性

2.1 迭代器是一种智能指针

        与其说迭代器是一种指针，不如说迭代器是一种智能指针，它将指针进行了一层封装，既包含了原生指针的灵活和强大，也加上很多重要的特性，使其能发挥更大的作用以及能更好的使用。迭代器对指针的一些基本操作如*、->、++、==、!=、=进行了重载，使其具有了遍历复杂数据结构的能力，其遍历机制取决于所遍历的数据结构。下面上一段代码，了解一下迭代器的“智能”：

template<typename T>
class Iterator
{
public:Iterator& operator++();//...private: T *m_ptr;
};

       对于不同的数据容器，以上Iterator类中的成员函数operator++的实现会各不相同，例如，对于数组的可能实现如下：

//对于数组的实现
template<typename T>
Iterator& operator++()
{ ++m_ptr; retrun *this;
}

       对于链表，它会有一个类似于next的成员函数用于获取下一个结点，其可能实现如下：

//对于链表的实现
template<typename T>
Iterator& operator++()
{m_ptr = m_ptr->next();//next()用于获取链表的下一个节点 return *this;
}

        从上面三段代码可以看到，迭代器的operator++操作对于不同数据结构，就会有不同的实现，这是C++原生所做不到的，也是迭代器为什么是一种智能指针的原因之一。看到这里，可能会有疑问，前面说迭代器针对不同的数据结构会有不同的实现，那意思是不是指迭代器一定要在数据结构内实现呢？答案是否定的，迭代器只要了解数据结构的实现，是可以在数据结构外定义，但是却有一定的代价。

2.2 不同的容器都有专属的迭代器

       下面尝试实现一个自己的迭代器，由于迭代器的作用对象是容器，因此需要首先实现一个容器，下面代码展示了一个单向链表的实现：

template<typename T>
class ListItem
{
public:ListItem() { m_pNext = 0;}ListItem(T v, ListItem *p = 0) { m_value = v; m_pNext = p;}T Value() const { return m_value;}ListItem* Next() const { return m_pNext;}private:T m_value;	//存储的数据ListItem* m_pNext;	//指向下一个ListItem的指针
};template<typename T>
class List
{
public://从链表尾部插入元素void Push(T value){m_pTail = new ListItem<T>(value);m_pTail = m_pTail->Next();}//打印链表元素void Print(std::ostream &os = std::cout) const{	for (ListItem<T> *ptr = m_pHead; ptr; ptr = ptr->Next())os<<ptr->Value<<" ";os<<endl;}//返回链表头部指针ListItem<T>* Begin() const { return m_pHead;}//返回链表尾部指针ListItem<T>* End() const { return 0;}//其它成员函数private：ListItem<T> *m_pHead;    //指向链表头部的指针ListItem<T> *m_pTail;    //指向链表尾部的指针long m_nSize;    //链表长度
};

       下面代码展示了操作以上List容器的一个迭代器的简单实现：

template<typename T>
class ListIter
{
public:ListIter(T *p = 0) : m_ptr(p){}//解引用，即dereferenceT& operator*() const { return *m_ptr;}//成员访问，即member accessT* operator->() const { return m_ptr;}//前置++操作ListIter& operator++() { m_ptr = m_ptr->Next(); //暴露了ListItem的东西return *this;}//后置++操作ListIter operator++(int){ListIter temp = *this;++*this;return temp;}//判断两个ListIter是否指向相同的地址bool opeartor==(const ListIter &arg) const { return arg.m_ptr == m_ptr;}//判断两个ListIter是否指向不同的地址bool operator!=(const ListIter &arg) const { return arg.m_ptr != m_ptr;}private:T *m_ptr;
};

       以下为相应的测试代码：

int main(int argc, const char *argv[])
{List<int> mylist;for (int i = 0; i < 5; ++i){mylist.push(i);}mylist.Print();	//0 1 2 3 4//暴露了ListItemListIter<ListItem<int> > begin(mylist.Begin());ListIter<ListItem<int> > end(mylist.End());ListIter<ListItem<int> > iter;iter = find(begin, end, 3);//从链表中查找3if (iter != end)cout<<"found"<<endl;elsecout<<"not found"<<endl;
}

       上面使用迭代器的测试代码给人的第一感觉就是好麻烦，首先需要声明和定义了begin和end两个ListIter<ListItem<int> >类型的迭代器，分别用来标识所操作容器List的头部和尾部，这时候暴露了ListItem；在ListIter的实现中，为了实现operator++的功能，我们又暴露了ListItem的函数Next()。另外，细心的你可能发现，算法find是通过*first != value用来判断元素是否符合要求，而上面测试代码中，first的类型为ListItem<int>，而value的类型为int，两者之间并没有可用的operator!=函数，因此，需要另外声明一个全局的operator!=重载函数，代码如下：

template<typename T>
bool operator!=(const ListItem<T> &item, T n)
{return item.Value() != n;
}

       为了实现迭代器ListIter，我们在很多地方暴露了容器List的内部实现ListItem，这违背一开始说的迭代器模式中不暴露某个容器的内部表现形式情况下，使之能依次访问该容器中的各个元素的定义。为了解决这种问题，STL将迭代器的实现交给了容器，每种容器都会以嵌套的方式在内部定义专属的迭代器。各种迭代器的接口相同，内部实现却不相同，这也直接体现了泛型编程的概念。

三、迭代器的分类

     在STL中，原生指针也是一种迭代器，除了原生指针以外，迭代器被分为五类：

• Input Iterator

          此迭代器不允许修改所指的对象，即是只读的。支持==、!=、++、*、->等操作。

• Output Iterator

          允许算法在这种迭代器所形成的区间上进行只写操作。支持++、*等操作。

• Forward Iterator

          允许算法在这种迭代器所形成的区间上进行读写操作，但只能单向移动，每次只能移动一步。支持Input Iterator和Output Iterator的所有操作。

• Bidirectional Iterator

          允许算法在这种迭代器所形成的区间上进行读写操作，可双向移动，每次只能移动一步。支持Forward Iterator的所有操作，并另外支持--操作。

• Random Access Iterator

          包含指针的所有操作，可进行随机访问，随意移动指定的步数。支持前面四种Iterator的所有操作，并另外支持it + n、it - n、it += n、 it -= n、it1 - it2和it[n]等操作。

     迭代器的分类和继承体系可用下面的图表示：

       为什么要将迭代器分为这五类，而且为什么要将它们设计为这种继承体系呢？在学习C++继承的时候，我们知道，位置继承体系越后的类，功能越强大，但是考虑的东西也会越多，体型也会越臃肿。为了提供最大化的执行效率，STL在设计算法时，会尽量提供一个最明确最合适的迭代器，在完成任务的同时，也尽量提高算法的效率。假设有个算法可接受Forward Iterator，此时，你可以传入一个Random Access Iterator，因为RandomAccess Iterator也是一种Forward Iterator，但是可用并不代表最合适，我们只需要Forward Iterator的功能，却传入了更多属于Random Access Iterator的在这里没有用到的功能，一定程度上会降低了算法的效率。       
       以函数advance为例，说明这种迭代器分类和继承体系的好处，此函数有两个参数，分别是迭代器i和数值n，主要作用是将i前进n距离，下面会有advance函数的三份定义，一份是针对Input Iterator，一份针对Bidirectional Iterator，另一份针对Random Access Iterator，而针对Forward Iterator的实现和针对Input Iterator的实现是一样的，因此没有单独列出，代码如下：

template<typename InputIterator, typename Distance>
void advance_II(InputIterator &i, Distance n)
{//单向逐一前进while (n--) ++i;
}template<typename BidirectionalIterator, typename Distance>
void advance_BI(BidirectionalIterator &i, Distance n)
{//双向逐一前进if (n >= 0)while (n--) ++i;elsewhile (n++) --i;
}template<typename RandomAccessIterator, typename Distance>
void advance_RAI(RandomAccessIterator &i, Distance n)
{//双向跳跃前进i += n;
}

       对于Random Access Iterator来说，当程序调用advance_RAI函数时，只需O(1)的时间复杂度；当程序调用advance_II()函数时，操作非常缺乏效率，原本只需O(1)时间复杂度的操作竟然变成为O(N)。因此，为了最大限度提高效率，STL将迭代器进行了明确的分类，同时将其设计为一种继承关系，以提高算法的可用性，如果某个迭代器没有相应版本的算法，通过类型转换，可以使用父类版本的算法，尽管效率不一定最优，但至少可用。

四、迭代器的使用实例

       前面说了这么多，下面简单展示一下迭代器的使用：

#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
using namespace std;int main(int argc, const char *argv[])
{int arr[5] = { 1, 2, 3, 4, 5};vector<int> iVec(arr, arr + 5);//定义容器vectorlist<int iList(arr, arr + 5);//定义容器list//在容器iVec的头部和尾部之间寻找整形数3vector<int>::iterator iter1 = find(iVec.begin(), iVec.end(), 3);if (iter1 == iVec.end())cout<<"3 not found"<<endl;elsecout<<"3 found"<<endl;//在容器iList的头部和尾部之间寻找整形数4list<int>::iterator iter2 = find(iList.begin(), iList.end(), 4);if (iter2 == iList.end())cout<<"4 not found"<<endl;elsecout<<"4 found"<<endl;return 0;
}

       从上面迭代器的使用中可以看到，迭代器依附于具体的容器，即不同的容器有不同的迭代器实现，同时，我们也看到，对于算法find来说，只要给它传入不同的迭代器，即可对不同的容器进行查找操作。通过迭代器的穿针引线，有效地实现了算法对不同容器的访问，这也是迭代器的设计目的。