【STL】迭代器

STL的中心思想是：将数据容器和算法分隔开，彼此独立设计，最后再用黏合剂将它们撮合在一起。容器和算法的泛型化，可以用 C++ 的 class template 和 function template 来实现，而迭代器（Iterator）就是二者的黏合剂了。

1 迭代器的实现

迭代器是一种智能指针，它将指针进行了一层封装，既包含了原生指针的灵活和强大，也加上很多重要的特性，使其能发挥更大的作用以及能更好的使用。指针最常见也最为重要的行为就是内容提领 (dereference) 和成员访问 (member access)，迭代器对指针的一些基本操作如*、->、++、==、!=、=进行了重载，使其具有了遍历复杂数据结构的能力，其遍历机制取决于所遍历的数据结构。

迭代器的“智能”体现在，针对不同的数据容器能够使用统一的方法、函数进行操作，以达到相同的目的。比如：

template<typename T>  
class Iterator  
{  
public:  
    Iterator& operator++();  

    ...  

private:   
    T *m_ptr;  
};

对于不同的数据容器，以上 Iterator 类中的成员函数 operator++ 的实现会各不相同，例如，对于数组的可能实现如下：

//对于数组的实现  
template<typename T>  
Iterator& operator++()  
{   
   ++m_ptr;   
   retrun *this;  
}

对于链表，它会有一个类似于 next 的成员函数用于获取下一个结点，其可能实现如下：

template<typename T>  
Iterator& operator++()  
{  
   m_ptr = m_ptr->next();//next()用于获取链表的下一个节点   
   return *this;  
}

iterator 的实现首先要对其所指向的对象的实现细节有非常丰富的了解，所以 iterator 为了不暴露所指向对象的信息，干脆就将 iterator 的实现由各个容器的设计者来实现好了。STL 将迭代器的实现交给了容器，每种容器都会以嵌套的方式在内部定义专属的迭代器。各种迭代器的接口相同，内部实现却不相同，这也直接体现了泛型编程的概念。

2 迭代器的类别

不同容器的迭代器，其功能强弱有所不同。容器的迭代器的功能强弱，决定了该容器是否支持 STL 中的某种算法。例如，排序算法需要通过随机访问迭代器来访问容器中的元素，因此有的容器就不支持排序算法。

常用的迭代器按功能强弱分为：

输入迭代器：只读
输出迭代器：只写
正向迭代器：正向遍历迭代器，假设 p 是一个正向迭代器，则 p 支持以下操作：++p，p++，*p。此外，两个正向迭代器可以互相赋值，还可以用==和!=运算符进行比较。
双向迭代器：双向迭代器具有正向迭代器的全部功能。除此之外，若 p 是一个双向迭代器，则--p和p-- 都是有定义的。--p使得 p 朝和++p相反的方向移动。
随机访问迭代器：随机访问迭代器具有双向迭代器的全部功能。若 p 是一个随机访问迭代器，i 是一个整型变量或常量，则 p 还支持以下操作：
- p+=i：使得 p 往后移动 i 个元素。
- p-=i：使得 p 往前移动 i 个元素。
- p+i：返回 p 后面第 i 个元素的迭代器。
- p-i：返回 p 前面第 i 个元素的迭代器。
- p[i]：返回 p 后面第 i 个元素的引用。

此外，两个随机访问迭代器 p1、p2 还可以用 <、>、<=、>= 运算符进行比较。p1<p2的含义是：p1 经过若干次（至少一次）++操作后，就会等于 p2。其他比较方式的含义与此类似。

对于两个随机访问迭代器 p1、p2，表达式p2-p1也是有定义的，其返回值是 p2 所指向元素和 p1 所指向元素的序号之差（也可以说是 p2 和 p1 之间的元素个数减一）。

下表是不同容器的迭代器功能类型：

容器	迭代器功能
vector	随机访问
deque	随机访问
list	双向
set / multiset	双向
map / multimap	双向
stack	不支持迭代器
queue	不支持迭代器
priority_queue	不支持迭代器

在以上功能的基础上，迭代器根据定义方式还分为：

正向迭代器：容器类名::iterator
常量正向迭代器：容器类名::const_iterator
反向迭代器：容器类名::reverse_iterator
常量反向迭代器：容器类名::const_reverse_iterator

反向迭代器和正向迭代器的区别在于：对正向迭代器进行++操作时，迭代器会指向容器中的后一个元素；而对反向迭代器进行++操作时，迭代器会指向容器中的前一个元素。

3 迭代器辅助函数

STL 中有用于操作迭代器的三个函数模板，它们是：

advance(p, n)：使迭代器 p 向前或向后移动 n 个元素。
distance(p, q)：计算两个迭代器之间的距离，即迭代器 p 经过多少次 ++ 操作后和迭代器 q 相等。如果调用时 p 已经指向 q 的后面，则这个函数会陷入死循环。
iter_swap(p, q)：用于交换两个迭代器 p、q 指向的值。

要使用上述模板，需要包含头文件 <algorithm>。