本文共 7383 字，大约阅读时间需要 24 分钟。
前言
迭代器作为一个抽象概念，在程序设计中并没有直接对应于这个概念的实物。在设计模式中，iterator模式定义为：提供一种方法，能使之依序巡防某个容器所含元素，而无须暴露该容器的内部表达方式。
3.1 迭代器设计思维–STL关键所在
STL的核心思想：将容器和算法分离，彼此独立设计，然后用迭代器将两者撮合。
3.2 迭代器是一种智能指针
指针最常见的行为是内容提领(derefence)和成员访问(member acess),因此迭代器编程的工作就是要对operator*和operator->进行重载。
3.3 迭代器所指的类型
如果在算法中要声明一个变量，其类型为迭代器所指的类型，应该如果做呢？
利用fuction template的参数推导机制
template void func_impl(I iter, T t){ T tmp; //T就是迭代器所指之物 //...这里做func()应该做的事情 }template inline void func(I iter){ func_impl(iter, *iter); //func的全部工作迁移到func_impl}int main(){ int i; func(&i);}
我们以func()为对外接口，实际操作放在func_impl中，由于其为一个function template,一旦被调用，编译器会自动进行参数推导，于是知道了类型T,解决问题。
Traits编程技法–STL源代码门钥
迭代器所指对象的类型称为迭代器的value type, 如果用于函数的返回值，上述方法不能使用。
声明内嵌类型
template class MyIter{public: typedef T value_type; T *ptr; MyIter(T *p = 0):ptr(p){} T& operator*()const{ return *ptr;}};
利用typedef T value_type把模版中的类型T暴露出来，我们可以通过以下的方法让函数的返回值为T的类型.
template typename I::value_type func(I iter){ return *iter; }
其中模版I必须提高value_type变量的自定义迭代器，编译器在编译阶段，会通过MyIter的实际模板值推导出func函数的返回值类型应该是什么，这样func函数的返回值就可以随着我们自定义迭代器传入的模板参数的改变而改变。
整体实现代码为：
#include using namespace std;template class MyIter{public: typedef T value_type; T *ptr; MyIter(T *p = NULL) : ptr(p){} T& operator*() const { return *ptr; }};template typename I::value_type func(I iter){ return *iter;}int main(){ MyIter myIter(new int(1)); cout << func(myIter) << endl; //1 return 0}
看起来很不错，但是不是所有的迭代器都是class type,是对于原生指针就会有问题，因为原生指针是没有内嵌类型的。
利用模板的特化的特性，在中间增加一层Traits类，让我们设计的func函数既支持自定义的迭代器又支持通用指针。
模版偏特化：如果一个class template拥有一个以上的template参数，我们可以针对其中某个(或数个，并非全部)的template参数进行特化工作。
/*1、模版的特化对于一个模版，对其中的所有模版参数指定确定的类型。2、偏特化对于一个模版，部分的模版参数指定确定的类型3、在进行模版实例化的时候，编译器会对特定的类型找到最合适，最匹配的实现。*/#include using namespace std;//模版template class Test{public: Test (T1 i, T2 j): a(i),b(j) { cout << "使用原模版:" << a << " " << b << endl; }private: T1 a; T2 b;};//全特化template<>class Test {public: Test(int i, char j) : a(i), b(j) { cout << "使用全特化:" << a << " " << b << endl; }private: int a; char b;};//偏特化template class Test {public: Test(T1 i, char j) : a(i), b(j) { cout << "使用偏特化:" << a << " " << b << endl; }private: T1 a; char b;};int main(){ Test t1(2.22, 3); Test t2(2.22, 'c'); Test t3(3, 'b'); return 0;}/*使用原模版:2.22 3使用偏特化:2.22 c使用全特化:3 b*/
明白了偏特化的意义，我们可以针对“迭代器之template参数为指针”者设计特化版的迭代器。
(1) 首先设计一个class template专门来萃取迭代器的特性
template struct iterator_traits{ typedef typename I::value_type value_type;};
这个traits的意义是，如果I定义有自己的value_type，那么通过这个traits的作用，萃取出来的value_type就是I::value_type。
(2) 然后使用偏特化解决原生指针和指向常数对象的原生指针
template struct iterator_traits { typedef T value_type;};template struct iterator_traits { typedef T value_type;};
整体的代码如下：
#include using namespace std;//自定义迭代器template struct MyIter{ typedef T value_type; T *ptr; MyIter(T* p = NULL):ptr(p) { } T& operator*() const { return *ptr; }};//Traits编程技法//支持自定义迭代器template class Traits{public: typedef typename T::value_type value_type;};//特化，支持传统通用指针template class Traits {public: typedef T value_type;};//特化，支持传统的const指针template class Traits {public: typedef T value_type;};//模版函数template typename Traits ::value_type func(I iter){ return *iter;}//测试int main(int argc, char** argv){ MyIter p(new int(1)); const char* ptr = "abc"; int *a = new int(9); cout << func(p) << endl; cout << func(a) << endl; cout << func(ptr) << endl; return 0;}
那么现在我们拥有三种版本：
1. 泛型版本
2. 原生指针
3. pointer-to-const
这样无论是迭代器 Iter 还是 原生指针 int* 还是 const int * 我们都可以通过traits取出正确的value_type。
最常用的迭代器类型有五种
1. value_type：迭代器所指对象的类型
2. difference_type：两个迭代器之间的距离。也可以用来表示一个容器的最大容量。如果泛型算法提供计数功能，就必须使用迭代器的这个型别做返回值。针对原生指针，使用ptrdiff_t作为其diffrence_type类型
3. reference_type： 引用类型。从迭代器所指的内容是否允许改变来看，可以将迭代器分为两种：不允许改变所指之物的内容，称为constant iterator；可以改变所指之物的内容，称为 mutable iterator。他们对应的例子分别是
cosnt int *和
int *。当我们对
mutable iterator (int *) 进行解引用操作时，获得的不应该是一个右值(rvalue)，应该是一个左值(lvalue)，因为右值不允许赋值操作(assignment)，左值才允许.
4. pointer_type：指针类型
5. iterator_category：迭代器类型， 以下具体讨论。
迭代器被分为以下五类：
只读，只写，前向，双向，随机存取。
* Input Iterator：这种迭代器所指的对象，不允许外界改变；只读(Read Only)
* Output Iterator：这种迭代器所指的对象，只可以写入；唯写(Write Only)
* Forward Iterator：允许“写入型”算法在此种迭代器形成的区间上读写操作。
* Bidirectional Iterator：可双向移动。
* Random Access Iterator：涵盖了所有的算数能力，比如p+n,p-n,p[n],p1-p2,p1
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{ }; 这里的 struct 只作为标记使用，所以不需要任何成员。
然后设计__advance()函数:
template inline void __advance(InputIterator& i, Distance n, input_iterator_tag) { while (n--) ++i;}template inline void __advance(BidirectionalIterator& i, Distance n, bidirectional_iterator_tag) { if (n >= 0) while (n--) ++i; else while (n++) --i;}template inline void __advance(RandomAccessIterator& i, Distance n, random_access_iterator_tag) { i += n;}
这里第三个参数只作为标记使用，函数内并没有使用它们。
然后接下来是 advance 函数：
template inline void advance(InputIterator& i, Distance n) { __advance(i, n, iterator_category(i));}
源码阅读：
//迭代器traitstemplate struct iterator_traits { typedef typename Iterator::iterator_category iterator_category; typedef typename Iterator::value_type value_type; typedef typename Iterator::difference_type difference_type; typedef typename Iterator::pointer pointer; typedef typename Iterator::reference reference;};//针对原生指针设计的偏特化版本template struct iterator_traits { typedef random_access_iterator_tag iterator_category; typedef T value_type; typedef ptrdiff_t difference_type; typedef T* pointer; typedef T& reference;};template struct iterator_traits { typedef random_access_iterator_tag iterator_category; typedef T value_type; typedef ptrdiff_t difference_type; typedef const T* pointer; typedef const T& reference;};//返回迭代器的类型template inline typename iterator_traits ::iterator_categoryiterator_category(const Iterator&) { typedef typename iterator_traits ::iterator_category category; return category();}//返回迭代器的distance_typetemplate inline typename iterator_traits ::difference_type*distance_type(const Iterator&) { return static_cast ::difference_type*>(0);}//返回迭代器的value typetemplate inline typename iterator_traits ::value_type*value_type(const Iterator&) { return static_cast ::value_type*>(0);}
__type_traits
Iterator_traits负责萃取迭代器的特性，__type_traits则负责萃取型别的特性。对于型别的特性，我们关注的点可能在于对该型别是否需要复杂处理。如果答案是否定的，我们在对这些型别进行构造、析构、拷贝赋值等操作时，就可以采取最有效率的措施，比如不使用析构函数，直接free等。
__type_traits提供了一种机制，允许针对不同的型别属性，在编译时期完成函数派送决定。这对于撰写template很有帮助。例如当我们对一个型别未知的数组进行copy时，如果我们事先知道该元素型别的构造函数是否是不重要的，我们可能可以使用memcpy或是memmove等函数快速处理
转载地址：http://wqmxb.baihongyu.com/