迭代器是一种抽象的设计概念，现实程序语言中并没有直接对应于这个概念的实物。
在设计模式中，迭代器模式是指：提供一种方法，使之能够依序巡防某个聚合物(容器)所含的各个元素，而又无须暴露该聚合物的内部表述方式。
迭代器是STL的关键所在：将数据容器和算法分开，彼此独立设计，最后再用桥梁将它们联系在一起，这个桥梁就是迭代器。
比如泛型算法 find 的实现
template <typename InputIterator, typename T>
InputIterator find(InputIterator first, InputIterator last, const T& value)
{
for (; first != last; ++first)
{
if (*first == value)
return first;
}
return first;
}
我们不需要关心容器的具体类型，也不需要关心T的具体实现，就能够对不同的容器进行查找操作。
迭代器榨汁机
template<typename I>
struct iterator_traits
{
typedef typename I::iterator_category
typedef typename I::value_type;
typedef typename I::difference_type;
typedef typename I::pointer;
typedef typename I::reference;
}
template<typename Category, typename T, typename Distance = ptrdiff_t,
typename Pointer = T*, typename Reference = T&>
struct iterator
{
typedef Category iterator_category;
typedef T value_type;
typedef Distance difference_type;
typedef Pointer pointer;
typedef Reference reference;
};
迭代器型别
迭代器型别之一：value_type
value_type 是指对象的型别，每一个打算与STL算法完美搭配的class，都应该定义自己的value_type内嵌型别。-
迭代器型别之二：difference_type
difference_type用来表示2个迭代器的距离，因此它可以用来表示容器的最大容量。通常用于STL中泛型算法提供的计数功能，例如STL中的count()。template <typename I, typename T> typename iterator_traits<I>::difference_type count (I first, I last, count T& value) { typename iterator_traits<I>::difference_type n = 0; for (; first != last; first++) if (*first == value) ++n; return n; } -
迭代器相应型别之三：reference_type
迭代器所指之物的内容是否允许改变， 迭代器分为2类，- 不允许改变“所指对象之内容者”称为constant iterators 例如 const int* pic。
- 允许改变“所指对象之内容者” 称为mutable iterators，例如int *pi。
-
迭代器相应型别之四：pointer type
reference_type 表示迭代器所指之物，那么pointer type则表示迭代器所指之物的地址。// 针对原生指针而设计的"偏特化版" template <typename T> struct iterator_traits<T*> { ...... typedef T* pointer; typedef T& reference; } // 针对原生的pointer-to-const而设计的"偏特化" template <typename T> struct iterator_traits<const T*> { ...... typedef T* pointer; typedef T& reference; } -
迭代器相应型别之五：Iterator_category
根据移动特性与施行操作迭代器被分为5类：- Input Iterator：这种迭代器所指的对象，不允许外界改变，只读。
- Output Iterator：只写。
- Forward Iterator：允许写入型算法在此种迭代器所形成的区间上进行读写操作。
- Bidirectional Iterator：可双向移动，某些算法需要逆向走访某个区间。
- Random Access Iterator：前4种迭代器只提供一部分指针算术能力，(前3种支持operator++，第4种支持operator--)，第5种则涵盖所有指针算术能力。
为什么需要区分这么多的迭代器种类？因为我们在设计算法时，应该针对某种强化的迭代器提供另一种定义，这样才能提供最大的效率。
任何一个迭代器，其类型应该落在 "该迭代器所隶属的各种类型中，最强化的那个"，例如，int* 既是 RandomAccess Iterator，又是 Bidirectional Iterator，同时也是 Forward Iterator，而且也是 Input Iterator，那么其类型应该归属为RandomAccess 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
{ };
比如以 advanced() 为例，它的目的是使迭代器向前移动n步。
/* 适合Input Iterator */
template <typename InputIterator, typename Distance>
void advance_II(InputIterator& i, Distance n)
{
while(n--)
++i;
}
/* 适合Bidirectional Iterator */
template <typename BidirectionalIterator, typename Distance>
void advance_BI(BidirectionalIterator& i, Distance n)
{
if (n >= 0)
while(n--)
++i;
else
while(n++)
--i;
}
/* 适合Random Access Iterator */
template <typename RandomAccessIterator, typename Distance>
void advance_RAI(RandomAccessIterator& i, Distance n)
{
i += n;
}
template <typename InputIterator, typename Distance>
void advance(InputIterator& i, Distance n)
{
if (is_random_access_iterator(i)) // 有待实现。
advanced_RAI(i, n);
else if (is_bidirectional_iterator(i)) // 有待实现。
advance_BI(i, n)
......
}
像在advanced中，通过判断不同迭代器类型来调用不同的函数以达到最大的效率。
那怎么判断出不同类型呢？
第一种方法是多态，但运行期才确定未免成本太高，同时胡乱继承多态也是把问题复杂化。
第二种就是函数重载，我们可以事先标记不同迭代器类型，并将其作为第3个参数传给advanced。
template <typename InputIterator, typename Distance>
inline void advance(InputIterator &iter, Distance n)
{
typedef typename iterator_traits<InputIterator>::iterator_category category;
__advance(iter, n, category());
}
template <typename RandomAccessIterator, typename Distance>
void __advance(RandomAccessIterator iter, Distance n, random_access_iterator_tag)
{
iter += n;
}
template <typename InputIterator, typename Distance>
void __advance(InputIterator iter, Distance n, input_iterator_tag)
{
while(n--)
iter++;
}
template <typename BidirectionalIterator, typename Distance>
void __advance(BidirectionalIterator iter, Distance n, bidirectional_iterator_tag)
{
if (n >= 0)
while(n--)
iter++;
else
while(n++)
iter--;
}
__advanced中的第三个参数仅仅是激活重载。但我们还需要一个提供上层统一的接口，在这一层中通过traits机制，将迭代器类型推导出来。
参考资料
[1]《STL源码剖析》侯捷
