//迭代器是一种smart pointer template<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; } };
注意operator *和operator->的实现，operator* 返回一个引用，operator->返回值必须为一个指针或可以应用 -> 操作的类型
如何获取迭代器所指对象的类型，即如何实现类型萃取？
可以定义一个类模板用于萃取迭代器特性，模板参数是迭代器类型。迭代器内部定义一个typedef表示迭代器所指对象类型，然后在萃取模板类中使用
typedef typename I::value_type value_type;
提取类型。由于原生指针不是class，无法定义value_type，可以对萃取模板类生成特化版本。
// 如何获取迭代器所指对象的类型 template<class T> struct MyIter { typedef T value_type;//迭代器所指对象类型 T *ptr; //.... }; template<class I> // 函数func接受一个迭代器参数，返回值是迭代器所指对象类型 // typename告诉编译器I::value_type是一个类型(嵌套从属名称)，使得能够通过编译 // 此处存在问题：如果I不是个class type，就无法定义value_type
// 可以封装类型萃取类，然后针对原生指针做偏特化处理
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，无法定义value_type //traits可以拥有特化版本,T *为原生指针int *,则T也就是value_type为int template<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()); }
为了符合规范，任何迭代器都应该提供五个内嵌类型，以用于traits萃取，否则可能无法与其他STL组件顺利搭配。STL提供了一个iterators class如下，可让每个新设计的迭代器都继承自它。
//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; };