迭代器是连接容器和算法的纽带，它们为数据提供了一种抽象的观点，使写算法的人不必关心多种多样的数据结构的具体细节。

1，迭代器概述

　　迭代器是指向序列元素的指针的一种抽象。通过使用迭代器，我们可以访问序列中的某个元素、改变序列中的某个元素的值、使迭代器向前或向后行走等等。

　　依据有效执行操作的情况，迭代器可以分为五类：输入迭代器、输出迭代器、前向迭代器、双向迭代器和随机存取迭代器。STL中用五个类来代表这五种迭代器类别：

　　其中

　　· Input Iterator 所指的对象不允许外界改变

　　· Output Iterator 支持对该迭代器所指对象的写操作

　　· Forward Iterator 不仅支持Input Iterator和Output Iterator的操作，还能在序列中前向移动指向下一个元素

　　· Bidirectional Iterator 可以双向移动，既可指向序列中的下一个元素，也可以指向序列中的前一个元素

　　· Random Iterator 既可以双向移动，又可以跨越多个元素存取对象

2， 与迭代器操作相关的类型及其萃取机制

　　使用迭代器是为了获取被指向的对象和被指向的序列的信息。只要给出描述某个序列的迭代器，用户就可以通过迭代器间接去操作被指向的对象，并且可以确定序列中元素的个数。为了表述这种操作，STL必须能提供与迭代器有关的各种类型。

　　迭代器在元素操作的时候需要用到以下五种类型：

　　value_type: 代表迭代器所指对象的类型。

　　difference_type:代表两个迭代器之间的距离

　　reference_type:代表迭代器所指对象的引用类型。简言之，它是operator*()的返回类型

　　pointer_type:代表迭代器所致对象的指针类型。简言之，它是operator->()的返回类型

　　iterator_category:代表1中提出的五种迭代器的类型标识

3，迭代器的适配器

STL提供了许多基于迭代器的适配器，如back_insert_iterator, front_insert_iterator, inser_iterator, reverse_iterator, istream_iterator, ostream_iterator, istreambuf_iterator, ostreambuf_iterator等。

这些适配器大致可以分为三类：插入迭代器、反向迭代器和IO迭代器。

反向迭代器

　　　　顾名思义，反向迭代器会提供与普通迭代器相反方向的遍历功能。反向迭代器其实一个正向迭代器的适配器，它的实现都是通过调用正向迭代器的操作，为了与迭代器的概念保持一致（begin指向迭代器的第一个元素，end指向迭代器的最后一个元素的下一个位置），又与正向迭代器有一点点不同。

　　　　reverse_iterator的实现中有一个名为current的Iterator，它是模板参数，即正向迭代器。正向迭代器指向的范围是序列中的第一个元素到最后一个元素的下一个位置，为了保持迭代器概念的统一，反向迭代器的rbegin应该是序列的最后一个元素，rend应该是第一个元素前面的元素。

　　　　所以，current总是指向reverse_iterator所指元素之后的一个元素。这也意味这*返回的是值*(current-1)，++通过对current的--实现。下面贴上reverse_iterator的代码。　　

总结：迭代器将算法和数据结构有效地分离并粘合起来。实际上，STL中的很多容器都设计有自己专属的迭代器，因为只有它自己才能知道自身数据结构的布局及其遍历方法，只需要按照标准声明上面提到的五种迭代器要用到的数据类型即可。迭代器更多的是运用到算法中，有了泛型和迭代器的支持，算法可以达到很高的内聚性。

//list.h#pragmaonce#include<iostream>#include<vector>#include<list>#include<assert.h>#include"iterator.h"usingnamespacestd;template<classT>struct__ListNode{T_data;__ListNode<T>*_prev;__ListNode<T>*_next;__ListNode(constT&x=T()):_prev(NULL),_next(NULL),_data(x){}};template<classT,classRef,classPtr>struct__ListIterator{typedef__ListIterator<T,Ref,Ptr>Self;typedefBidirectionalIteratorTagIteratorCategory;typedefintDifferenceType;typedefTValueType;typedefRefReference;typedefPtrPointer;__ListNode<T>*_node;__ListIterator(){}__ListIterator(__ListNode<T>*node):_node(node){}Referenceoperator*(){return_node->_data;}//当链表中存储结构体时，需要访问结构体成员变量Ptr&operator->(){////return&(operator*());return&(_node->_data);//List<AA>::Iteratorit=l.Begin();//cout<<it->_a<<endl;//编译器优化，按理说需要两个->->}booloperator==(constSelf&s){return_node==s._node;}booloperator!=(constSelf&s){return_node!=s._node;}Self&operator++(){_node=_node->_next;return*this;}Selfoperator++(int){Selftmp(*this);_node=_noode->_next;returntmp;}Self&operator--(){_node=_node->_prev;return*this;}Selfoperator--(int){Selftmp(*this);_node=_node->_prev;returntmp;}DifferenceTypeSize(){returnDistance(Begin(),End());}Referenceoperator+=(DifferenceTypen){while(n--){++*this;}return*this;}Selfoperator+(DifferenceTypen){Selftmp(*this);tmp+=n;returntmp;}Referenceoperator-=(DifferenceTypen){while(n--){--*this;}return*this;}Selfoperator-(DifferenceTypen){Selftmp(*this);tmp-=n;returntmp;}};template<classT>classList{typedef__ListNode<T>Node;Node*_head;public:typedef__ListIterator<T,T&,T*>Iterator;typedef__ListIterator<T,constT&,constT*>ConstIterator;typedefReverseIterator<ConstIterator>ConstReverseIterator;typedefReverseIterator<Iterator>ReverseIterator;typedefTValueType;typedefT*Pointer;typedefconstT*ConstPointer;typedefValueType&Reference;typedefconstValueType&ConstReference;typedefintDifferenceType;List():_head(newNode){_head->_next=_head;_head->_prev=_head;}~List(){if(_head==NULL)return;while(1){if(_head==NULL)break;elseif(_head->_next=_head){delete_head;_head=NULL;}else{Node*del=_head;_head=_head->_next;_head->_prev=NULL;deletedel;}}}/*voidPushBack(constT&x){Node*tail=_head->_prev;Node*tmp=newNode(x);tmp->_next=_head;_head->_prev=tmp;tail->_next=tmp;tmp->_prev=tail;}*/voidPushBack(constT&x){Insert(End(),x);}voidPushFront(constT&x){Insert(Begin(),x);}voidPopBack(){Erase(--End());}voidPopFront(){Erase(Begin());}voidInsert(Iteratorpos,constT&x){Node*cur=pos._node;Node*prev=cur->_prev;Node*tmp=newNode(x);tmp->_next=cur;cur->_prev=tmp;prev->_next=tmp;tmp->_prev=prev;}IteratorErase(Iteratorpos){assert(pos!=End());Node*prev=pos._node->_prev;Node*next=pos._node->_next;Node*del=pos._node;prev->_next=next;next->_prev=prev;deletedel;returnIterator(next);}IteratorBegin(){returnIterator(_head->_next);}IteratorEnd(){return_head;//explicit//returnIterator(_head);}ReverseIteratorRBegin(){returnReverseIterator(End());}ReverseIteratorREnd(){returnReverseIterator(Begin());}ConstReverseIteratorRBegin()const{returnConstReverseIterator(End());//explicit}ConstReverseIteratorREnd()const{returnConstReverseIterator(Begin());//explicit}};voidTestSList(){List<int>l;l.PushBack(1);l.PushBack(2);l.PushBack(3);l.PushBack(4);l.PushBack(5);List<int>::Iteratoriter=l.Begin();while(iter!=l.End()){cout<<*iter<<"";++iter;}cout<<endl;iter=l.Begin();while(iter!=l.End()){List<int>::Iteratortmp=iter;++tmp;if(*iter%2==0){l.Erase(iter);}iter=tmp;/*if(*iter%2==0){iter=l.Erase(iter);}else++iter;*/}List<int>::ReverseIteratorit=l.RBegin();while(it!=l.REnd()){cout<<*it<<"";++it;}cout<<endl;cout<<Distance(l.Begin(),l.End())<<endl;}//vector.h#pragmaonce#include<iostream>#include<vector>#include<list>#include<assert.h>#include"iterator.h"usingnamespacestd;template<classT>classVector{public:typedefT*Iterator;typedefconstT*ConstIterator;typedefReverseIterator<ConstIterator>ConstReverseIterator;typedefReverseIterator<Iterator>ReverseIterator;typedefTValueType;typedefT*Pointer;typedefT&Reference;typedefintDifferenceType;protected:Iterator_start;Iterator_finish;Iterator_storage;void_CheckCapacity(){if(_finish==_storage){intcapacity=_storage-_start;intnewCapacity=capacity*2+3;T*tmp=newT[newCapacity];for(inti=0;i<capacity;++i){//operator=tmp[i]=_start[i];//不能用memcpy，涉及指针拷贝}delete[]_start;_start=tmp;_finish=_start+capacity;_storage=_start+newCapacity;}}public:Vector():_start(NULL),_finish(NULL),_storage(NULL){}Vector(size_tsize):_start(newT[size]),_finish(_start),_storage(_start+size){}~Vector(){if(_start)delete[]_start;}voidPushBack(constT&x){_CheckCapacity();*_finish=x;++_finish;}voidPopBack(){assert(_finish>_start);--_finish;}IteratorBegin(){return_start;}IteratorEnd(){return_finish;}ReverseIteratorRBegin(){returnReverseIterator(End());}ReverseIteratorREnd(){returnReverseIterator(Begin());}DifferenceTypeSize(){return_finish-_start;}DifferenceTypeCapacity(){return_storage-_start;}Referenceoperator[](intindex){assert(index<Size());return_start[index];}ValueTypeat(intindex){assert(index<Size());return_start[index];}};voidTestVector(){Vector<int>v;v.PushBack(1);v.PushBack(2);v.PushBack(3);v.PushBack(4);v.PushBack(5);Vector<int>::Iteratorit=v.Begin();while(it!=v.End()){cout<<*it<<"";it++;}cout<<endl;Vector<int>::ReverseIteratorrit=v.RBegin();while(rit!=v.REnd()){cout<<*rit<<"";++rit;}cout<<endl;cout<<Distance(v.Begin(),v.End())<<endl;}//iterator.h#pragmaonce#include<iostream>usingnamespacestd;structInputIteratorTag{};structOutputIteratorTag{};structForwardIteratorTag:publicInputIteratorTag{};structBidirectionalIteratorTag:publicForwardIteratorTag{};structRandomAccessIteratorTag:publicBidirectionalIteratorTag{};template<classIterator>structIteratorTraits{typedeftypenameIterator::IteratorCategoryIteratorCategory;typedeftypenameIterator::ValueTypeValueType;typedeftypenameIterator::DifferenceTypeDifferenceType;typedeftypenameIterator::PointerPointer;typedeftypenameIterator::ReferenceReference;};template<classT>structIteratorTraits<T*>{typedeftypenameRandomAccessIteratorTagIteratorCategory;typedeftypenameTValueType;typedeftypenameintDifferenceType;typedeftypenameT*Pointer;typedeftypenameT&Reference;};template<classT>structIteratorTraits<constT*>{typedeftypenameRandomAccessIteratorTagIteratorCategory;typedeftypenameTValueType;typedeftypenameintDifferenceType;typedeftypenameT*Pointer;typedeftypenameT&Reference;};template<classInputIterator>int__Distance(InputIteratorfirst,InputIteratorlast,InputIteratorTag){intn=0;while(first!=last){++first;++n;}returnn;}template<classRandomAccessIterator>int__Distance(RandomAccessIteratorfirst,RandomAccessIteratorlast,RandomAccessIteratorTag){returnlast-first;}template<classInputIterator>intDistance(InputIteratorfirst,InputIteratorlast){return__Distance(first,last,IteratorTraits<InputIterator>::IteratorCategory());}template<classIterator>classReverseIterator{protected:Iterator_cur;typedefReverseIterator<Iterator>Self;typedeftypenameIteratorTraits<Iterator>::IteratorCategoryIteratorCategory;typedeftypenameIteratorTraits<Iterator>::DifferenceTypeDifferenceType;typedeftypenameIteratorTraits<Iterator>::ValueTypeValueType;typedeftypenameIteratorTraits<Iterator>::PointerPointer;typedeftypenameIteratorTraits<Iterator>::ReferenceReference;public:ReverseIterator(){}explicitReverseIterator(Iteratori):_cur(i){}Referenceoperator*(){Iteratortmp=_cur;return*(--tmp);}//当链表中存储结构体时，需要访问结构体成员变量Pointer&operator->(){////return&(operator*());return_cur.operator->();//List<AA>::Iteratorit=l.Begin();//cout<<it->_a<<endl;//编译器优化，按理说需要两个->->}booloperator==(constSelf&s){return_cur==s._cur;}booloperator!=(constSelf&s){return_cur!=s._cur;}Self&operator++(){--_cur;return*this;}Selfoperator++(int){Selftmp(*this);--_cur;returntmp;}Self&operator--(){++_cur;return*this;}Selfoperator--(int){Selftmp(*this);++_cur;returntmp;}Self&operator+=(intn){_cur+=n;return*this;}Self&operator-=(intn){_cur-=n;return*this;}Selfoperator+(intn){returnSelf(*this+n);}Selfoperator-(intn){returnSelf(*this-n);}Referenceoperator[](DifferenceTypen)const{return*(*this+n);}//Iterator需实现operator+(n);};//main.cpp#include"list.h"#include"vector.h"intmain(){TestSList();TestVector();system("pause");return0;}