首页 > 代码库 > STL之迭代器（iterator）
STL之迭代器（iterator）
STL的中心思想在于：将数据容器和算法分开，彼此独立设计，最后再用一帖粘着剂将它们撮合在一起。没错，这个粘着剂正是迭代器（iterator）。迭代器的主要目的是通过遍历来对容器中元素进行相关操作。算法主要通过迭代器来访问容器，也就是说迭代器是容器和算法之间的桥梁。来段代码如例：
template <class T, class Allocator = allocator<int> >Class vector {….};template <class InputIterator, class T>InputIterator find(InputIterator first, InputIterator last, const T& value){ While (first != last && *first != value)
++first; return first;}
那么可能我们会想假如算法中我们需要用到容器中对象的类型时，我们该如何获得？利用函数模板的参数推导机制吧。那万一对象类型必须用于函数的传回值时，该怎么办？毕竟模板参数推导机制推出的只是参数，而无法推导函数的返回值类型。好吧，Traits编程技巧该上场了。
traits嘛（萃取），就是说如果你有定义一些类型，便把它萃取出来，比如：
template <class T>struct iterator_traits { typedef typename T:: value_type value_type; // typename加在T::value_type前告诉编译器这是一个类型};template <class I>typename iterator_traits<I>::value_type func(I iter){ Return *iter;}
这样便可以将它的类型（返回值类型）萃取出来。
最常用到的迭代器相应类型有5种，分别为value type(迭代器所指对象的类型), difference type（两个迭代器之间的距离）, pointer, reference, iterator catagoly（迭代器的种类）。如果你希望你开发的容器可以与STL相融合，那么一定要为你的容器的迭代器定义这5种类型，相应代码如下：
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;};
当然如果类型并非对象，而是原型指针，那么就更好办了，我们设计了2种traits偏特化版本，如下：
template <class T>struct iterator_traits<T*> { typedef T value_type;};template <class T>struct iterator_traits<const T*> { typedef T value_type;};
现在，我们来谈谈iterator_category：
迭代器被分为5类，分别为：
Input Iterator: 这种迭代器所指的对象，不允许被外界改变，只读。
Output Iterator: 只写。
Forword Iterator: 单向迭代器。
Bidirectional Iterator: 双向迭代器。
Random Access Iterator: 可跳转迭代器。（如p+n, p - n）
不同的迭代器类型对算法的效率影响非常大，主要影响于时间复杂度。这里就不讲了，之后单独讲讲。还有对于迭代器适配器也打算放在适配器里讲，这里只是为了大概了解了解迭代器的工作。当然迭代器使用起来是非常方便的，来个例子：
vector<int> vec; vector<int> :: iterator iter;
for(iter = vec.begin(); iter != vec.end(); iter++) { // … }
C++11的auto用起来也非常方便的。
vector<int> vec;
for(auto iter = vec.begin(); iter != vec.end(); iter++) { // … }
STL之迭代器（iterator）