迭代器 (iterator)

迭代器是算法和容器之间的中间桥梁，迭代器必须能够有能力满足算法的提问，其实也就是规定了迭代器的属性。

STL中迭代器必须提供的五种相关属性（associated types）

iterator_category 分类，确定是哪种迭代器，
distance 表示两个迭代器之间的距离，如last - begin, middle - begin等
value_type 迭代器所指对象的类型
reference
pointer

Iterator Traits

根据上文，我们知道STL里面 algorithm 每次使用是都会询问桥梁，即对应 iterator 的五个属性。思考一下，传统意义的指针是iterator吗？传统意义的指针能被algorithm调用吗？

指针是iterator，但是传统指针没办法进行typedef, 就没法确定这几个associated type, 而迭代器是泛化的指针。
这样的话，算法是怎么调用传统指针呢？这里就是用了中间层的概念，这也是解决计算机复杂问题的“银色子弹”

一句话概括：迭代器萃取机制(iterator_traits)就是用tratis这个中间层，来区别 class iterators 和 non-class iterators
下面就iterator的value_type属性举例，其GCC 2.9中的代码部分如下：

 1 //如果是I，就进入这个
 2 template <class I>
 3 struct iterator_traits {
 4     typedef typename I::value_type value_type;
 5 };
 6 
 7 //模板特化
 8 //如果I是pointer to T, 就进入这个
 9 template <class T>
10 struct iterator_traits<T*> {
11     typedef T value_type;
12 };
13 
14 //模板特化
15 //如果I是pointer to const T, 就进入这个
16 template <class T>
17 struct iterator_traits<const T*> {
18     typedef T value_type;//注意是T而不是const T
19 };
20 
21 template<typename I, ...>
22 void algorithm(...) {
23     typename iterator_traits<I>::value_type y1;
24 }

各式各样的traits

除了iterator traits之外还有 type traits, char traits, allocator traits, pointer traits, array traits

总结

设计适当的相应型别（associate types），是迭代器的责任。
设计适当的迭代器，是容器的责任，只有容器才知道什么样的迭代器可以遍历自己，执行相应行为。
算法只需要设计以迭代器为对外接口就行，独立在容器和迭代器之外自行发展。

---------------- 生活 > 学习 >> 工作 ----------------