//迭代器是一种smart pointertemplate<typename T>class ListItem{public:    T value()const    {        return _value;    }    ListItem *next()const    {        return _next;    }private:    T _value;    ListItem *_next;};template<class T>class List{public:    void insert_front(T value);    void insert_end(T value);    void display(ostream&os = cout)const;private:    ListItem<T>*_end;    ListItem<T>*_front;    long _size;};//为链表设计一个迭代器,要设计迭代器，必须要对容器有足够的了解//所以list和对应的迭代器的设计都由list的设计者实现，从而封装实现细节template<class Item>struct ListIter{    Item *ptr;//保持与容器之间的一个联系,ptr是list结点指针    ListIter(Item *p = 0) :ptr(p){}    //迭代器行为类似指针，其中最常见的操作是内容提领和成员访问    //所以要对operator*和operator->进行重载,可参考auto_ptr的实现    Item& operator*()const    {        return *ptr;    }    //重构->,返回值必须为一个指针或可以应用 -> 操作的类型    Item* operator->()const    {        return ptr;    }    //前增量，返回引用(迭代器对象)    ListIter& operator++()    {        ptr = ptr->next();        return *this;    }    //后增量，返回值    ListIter operator++(int)    {        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;    }};

//如何获取迭代器所指类型template<class T>struct MyIter{    typedef T value_type;//迭代器所指对象类型    T *ptr;    //....};template<class I>//函数func接受一个迭代器参数，返回值是迭代器所指对象类型//typename告诉编译器I是一个类型，使得能够通过编译typename I::value_type func(I ite){    return *ite;}//类模板用于萃取迭代器特性,I为迭代器类型template<class I>struct iterator_traits{    typedef typename I::value_type value_type;//针对class};//原生指针不是class，无法定义内嵌型别//traits可以拥有特化版本,T *为原生指针int *,则T也就是value_type为inttemplate<class T>struct iterator_traits<T*>{    typedef T value_type;//针对原生指针};//萃取机完整版本（最常用到的迭代器五种类型）//若使容器能与STL兼容，必须要为容器的迭代器定义以下五种相应型别template <class I>struct iterator_traits{    typedef typename I::iterator_category iterator_category;//迭代器类型    typedef typename I::value_type value_type;//迭代器所指对象的类型    typedef typename I::difference_type difference_type;//两个迭代器之间的距离    typedef typename I::pointer pointer;//迭代器所指对象的指针    typedef typename I::reference reference;//迭代器所指对象的引用};/*迭代器有五种类型，Input Iterator,output Iterator,Forward Iterator只支持++，Biderectional Iterator支持++、--,Random Access Iterator支持所有运算，效率最高*/struct input_iterator_tag{};struct output_iterator_tag{};struct forward_iterator_tag :public input_iterator_tag{};struct bidirectional_iterator_tag :public forward_iterator_tag{};struct random_access_iterator_tag :public bidirectional_iterator_tag{};//第三参数，使如下函数形成重载template <class InputIterator,class Distance>inline void _advance(InputIterator& i, Distance n, input_iterator_tag){    while (n--)        i++;}//下面四个函数类似，不再详述//对外开放的接口, iterator_traits<InputIterator>::iterator_category()将产生一个暂时对象，编译器根据对象//类型决定调用哪一个_advance重载函数//STL一个命名规则：以算法所能接受的最低阶迭代器类型来为其迭代器类型参数命名template<class InputIterator,class Distance>inline void advance(InputIterator& i, Distance n){    _advance(i, n, iterator_traits<InputIterator>::iterator_category());}

//ptrdiff_t为c++内建类型，定义于<cstddef>template <class Category,class T,class Distance=ptrdiff_t,class Pointer=T*,class Reference=T&>struct iterator{    typedef Category iterator_category;    typedef T value_type;    typedef Distance difference_type;    typedef Pointer pointer;    typedef Reference reference;};