1.何为iterator?
2.为什么用iterator?
3.怎么用iterator?
4.深入iterator.
1.何为iterator?
iterator翻译为迭代器，主要作用是提供对容器数据进行遍历，修改的一层抽象。举个例子，链表和数组是不同的数据容器，我们知道如果需要访问它们当中的某个数据的下个元素，因为数据元素在数组和链表中的存储方式不一样，所以需要针对数组和链表各写两种方法来实现。但是当我们使用了iterator之后，这些针对不同数据容器的数据访问和修改等基本操作就都被抽象了出来。比如无论是数组还是链表，我们要访问他们当中的下一个元素，只要使用这种数据提供的iterator，执行iterator++操作就可以了。各个数据容器都会提供自己的iterator，并让iterator提供本身容器所能支持的基本数据操作。iterator所支持的标准数据操和一个指针所支持的所有操作类似，r++,r--,*r,r+=n,r-=n,r->,<,>,=,!=，赋值。
1.1 iterator的操作与层次结构
iterator类似一个指针，它利用各种操作符重载让自己被操作起来就好像操作一个指针。然后这其中根据各个数据容器的差异性也有诸多的限制。设想一下下面这个情况：一个数组容器的iterator可以提供++，--等操作，因为当数组的特性是只要修改下标的值就可以访问相应下表对因的元素，那么数组iterator的--,++操作就很容易的实现，但是一个单项链表容器呢，iterator的++操作可以很好的支持，但是iterator的--操作似乎就很麻烦了，就算可以实现我们也应该尽可能的不要使用，一是因为这不符合单向链表的特性，二是因为效率低下。如果需要--操作何不一开始就使用双向链表容器呢？
举上面这个例子只是为了说明各个数据容器因为自身的数据结构的特点并不是支持所有的iterator的操作，它们只能根据自身数据结构的特点，选择性的支持iterator的操作。但是这就会带来一个很大的问题，各个容器的iterator支持的操作都不一样那么使用起来肯定很麻烦，设计出来的东西也增加了对数据容器的耦合性。对于这个问题的解决方法就是将iterator细化开来，这种细化其实是一种实践之后得出的结果(为什么这么细化后面再分析)，具体的细化层次如 InputIterator < ForwardIterator < BidirectionalIterator < RandomAccessIterator. 和一个OutPutIterator. "<"符号表示前者所支持的操作的范围包含在后者之中，可以看作是一种继承关系。而前四种iterator都可以支持OutPutIterator的操作，只要它们支持了OutPutIterator那么它们就都算做是mutable的iterator，反之则是我们常说的const_iterator。各种iterator支持的操作请参阅这里http://en.cppreference.com/w/cpp/iterator。
1.2 iterator类与概念(concept)
上述我们说的5中细化的iterator它们并不是一个具体的类或任何其他东西(这里要强调一点其实iterator也不一定就是类)，而是一种比类更抽象的存在，concept。可以用对象和类的关系来比喻类和concept的关系。InputIterator是一种concetpt，ForwardIterator也是一种concept，既然它们都不是类，那么我们也不应该在用类的继承关系来形容它们之间的关系。取而代之的是Refinement，ForwardIterator支持了所有inputIterator支持的操作那么ForwardIterator称作inputerator的Refinement。下面是关于concept与类更为确切的解释：
concept可以看作是一组条件，只要满足了这组条件的type就是这个concept的model,char*是InputIterator这个concept的model，istream_iterator这个类也是它的model。所以说iterator不一定是类，而应该是一种type。从逻辑角度来说如果某个iterator是某个concept的Refinement concept的model，那么它也一定是这个concept的model,事实也的确如此。既然上述几种concept既不是类也不是任何具体的东西，那么在某些有不有什么办法可以判断某个type属于某个型别呢，其实是有的，并且利用这个特点STL的算法还进行针对不同iterator的各种优化。在第四节会讲到。
2.为什么使用iterator?
为什么使用iterator？如果从一个数据容器的角度出发那么你也许会想，我使用容器提供的iterator的++操作符和容器本身就提供的next()方法来访问下个元素没有任何缺别，或者更可以说使用iterator还不如next()方法来得方便。不得不说确实是这样。但是如果有一万个容器来说呢？如果这一万个容器都提供一个统一的访问方法那么使用起来你就或多或少的会感觉到iterator的方便之处了。为什么不让这些容器都提供统一的方法接口而是要他们都提供一个iterator来供外界访问呢？试想一下如果一个容器提供了一个next()方法，并在容器内部定义了一个变量index用来指向这个容器目前指向的数据对象的索引，那么如果在多个地方我都调用这个容器对象的next()方法，调用容器对象的next()方法所得到的值就不一定是你上次所访问的元素的下一个值了，而且取决于在你这调用next()方法之前，next()方法在其他地方被调用了几次。那么next()方法也就失去了它的意义。举这个例子只是为了说明容器内部不应该保留数据访问的状态，这样会影响到诸如访问下个元素等操作的正确性。那么这个时候iterator就出现了替代了在容器对象内部存储数据的访问状态，转而给每一个访问者一个iterator对象用来存储访问者对这个容器对象的数据的访问状态。
另外一个使用iterator的原因还是离不开iterator对数据容器的基本操作的抽象特性。STL中另外一个非常重要的部分就是算法，而算法的作用对象就是容器。设想一下这么一个算法，要求给这个算法输入一个值value和一个容器对象container，算法的目的是在这个容器搜寻这个值并返回容器中这个值的引用。假如在没有iterator，那么没有其他办法我们只有为每一个容器提供一个这个容器对应的算法了（不要假想所有的容器提供一个统一的方法接口这种方法，这种方法不可行的原因上面已经说明了）。但是有了iterator之后这个算法就可以写的很简单了,其定义类似与下面这种
template< class InputIt, class T > InputIt find( InputIt first, InputIt last, const T& value )
{
while(first!=last)
{
if(*first==value)
break;
first++;
}
return first;
}
从上面这个例子大概也就能看出iterator作为STL算法与数据容器之间桥梁的重要性了。但是还有一个额外的问题，其实就是各个算发所需要用到的iterator操作各不相同，有的算法如find，它只需要*,++,!=这几个操作就够了，所以只需要支持这几个操作的iterator的都可以使用find算法。而sort算法就需要randomIterator。总的来说各个算法所需要的iterator操作数都可以用上面细化的几种iterator来代表，而这几种细化的iterator个人觉得其实也是在对容器和算法的设计过程中经验的总结归纳吧，当然这也只是我个人的猜测而已。使用iterator容器之后从软件设计的角度来说降低了对数据容器的耦合性，可以很轻易在几种数据容器之中切换开来只要他们的iterator支持的操作满足我们程序的要求即可。而且在有了各种STL算法的支持之后使得很多不必要的劳动得到了节省，并且各种算法的效率也是非常有保障的。
3.如何使用iterator？
3.1.iterator适配器 其实这里说道适配器，什么是适配器，就是“把一种接口转化为另外一种接口的组建”。打个比方你写了一个list，它只有一些不符合标准的方法，你又写了一个class包装了这个list并提供了一些符合STL标准的接口，那么你这个class就可以算作是adaptor，它将list原有接口转化为了另外一组接口而list根本就不知道它的存在。 在STL中iterator的适配器，它们只是将STL的组件进行适配提另外一些不同的接口。比如下面这个例子：
typedef vector<int>::iterator pointer;
typedef vector<int>::const_iterator cpointer;
vector<int> ve;
ve.reserve(10);
for(int i=0;i<10;i++)
{
ve.push_back(i);
}
//reverse_iterator的构造参数至少需要支持biddirectioniterator的操作
//用reverse_iterator适配vector的randomiterator
reverse_iterator<pointer> rbegin(ve.end());
reverse_iterator<pointer> rend(ve.begin());
while(rbegin!=rend)
{
cout<<*rbegin++<<", ";
}
我们将vector<int>的iterator用reverse_iterator进行适配了，改变了它的++，*等接口的实现，让它能够倒序遍历。但是要小心reverse_iterator的*行为，它总是会取当前引用的上一个值，所以reverse_iterator的起始点是end(),而止行点是first。 上面这个例子只是将iterator作为参数进行了适配，而STL其它的iterator adaptor则会将容器作为参数进行适配。但是要注意这类适配器也有一定的前提条件比如：
vector<int> firstvector, secondvector;
for (int i=1; i<=5; i++)
{ firstvector.push_back(i); secondvector.push_back(i*10); }
//对vector容器进行了适配，产生出的iterator对象的*赋值操作将被改写成push_back操作，而++等其他操作将不会有任何实际意义。
back_insert_iterator< vector<int> > back_it (firstvector);
copy (secondvector.begin(),secondvector.end(),back_it);
vector<int>::iterator it;
for ( it = firstvector.begin(); it!= firstvector.end(); ++it )
cout << *it << " ";
cout << endl;
其中我们使用了back_insert_iterator对vector<int>容器进行了适配，back_insert_iterator的参数要求这个容器必须提供push_back接口。 STL还为我们提供了6，7中iterator，包括back(front)_insert_iterator,insert_iterator(改写了赋值操作为容器的insert操作)，i(o)stream_iterator(对iostream进行了封装)，reverse_iterator（改变了iterator的++操作为--操作，*解引操作实现也略微改变）。
3.2.iterator误区
如何使用iterator？其实最简便的认识你可以把各种iterator当作一个只支持部分功能的指针来使用即可，小心的参阅文档不使用文档中没有提及的操作比如对forwarditerator那么我们就不要使用--操作，对于BidirectionalIterator我们不使用+n操作。按照iterator的继承结构来说子类的iterator可以向上“转型”当作父类来用，但是父类的iterator不要当作之类来用。当你定义一个需要传入iterator的方法时，尽量使用更上层的iterator来指定传入参数，这样就可以支持更多的数据容器的iterator作为传入参数。上面只是一些使用的建议，下面是一些我们使用iterator是经常会遇到的误区：
1.const vector<type>::iterator 和vector<type>::const_iterator的区别。const vector<type>::iterator只是限定iterator不可改变，而iterator所指向的值却没有保证,即++，--等操作不可以执行，但是*赋值可以。const_iterator保证的是const_iterator的容器对象的值是不可改变的，而const_iterator本身是可以改变的++，--可以，*赋值不可以。v
2.iterator的比较操作符==，!=,>,<,-,+是用来操作iterator自身的值（指针的地址），而不是所指向的容器的数据的值。
3.iterator的失效。iterator本质上来说就是一个跟容器相关的经过了包装了的指针，当我们解引取值时还是调用的指针的*符号，而当容器内的数据发生移动，删除等操作时很可能导致iterator所指向的地址的值已经发生改变或是已经删除。这个时候就是所谓的iterator失效。当然也并不是所有的操作都会带来iterator失效，而且这也与容器的类型有关。只要记住一点任何可能导致iterator所指向地址失效的操作就会导致iterator失效，这个时候在继续使用iterator会带来一些不能预料的后果。这里是Peter Lsensee的一篇http://www.tantalon.com/pete/embracingstl.ppt PPT，里面详细阐述了何时iterator会失效。你需要小心使用那些使用数组存储，会自动重新分配内存的数据结构。并且当你在循环里调用了删除，插入等操作之后，记得利用这些操作的返回值及时更新你的iterator以免失效。而对于关联容器来说插入操作通常不会让你的指针失效。下面是一个例子：
typedef vector<int>::iterator pointer;
typedef vector<int>::const_iterator cpointer;
vector<int> ve;
ve.reserve(3);//这里预留了3的容量
pointer p=ve.begin();
for(int i=0;i<6;i++)
{
//这里在不停插入之后导致vector不得不重新分配一块更大的连续内存来存储数据
ve.insert(p,i);
}
这个例子因为vector数组的重分配，导致指向原来内存的iterator失效，在原先内存上的操作将导致不可预料的行为，当然最常见的就是段错误了。只要将p=ve.insert(p,i)替换掉原来的插入语句即可，这行语句表示每次插入之后都更新iterator以免失效。
4.不要用iterator和NULL来比较来判断容器方法的返回值。因为当一个容器的方法如find(const type& value)没有找到元素时它会返回一个指向最后一个元素之后的iterator来表明没有找到指定元素，这时你应该先比较返回的iterator和最后一个元素之后的iterator的值是否相等来判断是否得到你想要的东西。一般这个值的表示vector.end(),map.end()等方法的返回值。调用iterator的==操作符和NULL比较，你会发现iterator在大多数情况下根本没有声明这个方法。
4.深入iterator.
暂时留到下篇文章。将会探讨：
1.如何在一个模板方法内得到一个iterator的型别(type),即这个iterator指向的值类型。
2.STL算法是如何判断一个iterator属于哪个concept以及一个算法如何针对不同的iterator做相应的优化。