《STL源码剖析》迭代器

1.迭代器的定义

迭代器是一种抽象的设计概念，迭代器是一种数据结构，提供统一方法（如遍历，获取元素）对容器内部的元素进行操作，而又无需暴露容器元素的内部表达方式。

举个例子，指针可以看做是数组的迭代器（尽管不太符合STL规范），但是指针有很多种，我们可以提供一个封装来解决这个问题

template<tyname PtrType>
class Proxy {
    PtrType* ProxyPtr;
    //……
}

通过模板，我们用Proxy这个类统一了指针 Proxy<int>就是int指针Proxy<string>就是string指针.

它提供了统一的操作（取地址，随机访问）不管什么类型数组，反正都是用Proxy<PtrType>取地址，地址上的值就是数组内对应的元素，指针p+n对应的就是数组第n个元素，不管p是什么类型指针。

也就是说，迭代器是一类对象（不管Proxy特化为什么类型指针，都是Proxy类，都是针对数组这个容器），有着统一的方法与针对不同容器特定的行为，对容器进行操作，而不论容器类型，使得通用算法通过迭代器对不同容器起同样的效果。不同容器有专有的迭代器，但是这些迭代器都有统一的接口（方法），区别只是这些方法的内部实现不一样。

2.为什么要有迭代器

迭代器是GP泛型编程的重要组件，是容器与算法重要的胶合剂，多种容器对应多种专有迭代器，但是这些迭代器是外在统一的方法，内在不同的实现。可以对应同一个算法正常运作。没有迭代器，通用算法就没法实现通用。

3.工作原理

迭代器的工作原理与指针类型，因为迭代器是对象，通过对操作符*，->的重载，完成对容器内被指向的元素的获取，通过++，--，operator[]操作符重载，完成迭代器指向下一个元素，上一个元素，随机访问容器内元素。

例如:find算法

template<typename T>
Iterator find(Iterator begin, Iteratorend,const T& value) {
    While(begin!=end&& *begin != value)
    ++begin;
    Return begin;
}

对于STL，内置的迭代器相应的可以划分为这么几个类型：

• Input Iterator
  这种迭代器所指对象是只读的，迭代器取出所指的值，可以访问下一个元素，判断是否到达最后元素，支持操作 *p(返回值不允许修改),++p,p++,p!=q,p==q

• Output Iterator
  和Input Iterator迭代器类型，不过返回值允许修改，支持*p,++p,p++,p!=q,p==q的操作

• Forward Iterator
  前向迭代器，和Output Iterator支持操作一致

• Bidirectional Iterator
  双向迭代器，Forward Iterato支持的操作都支持，还支持--p,p--.

• Random Access Iterator
  随机访问迭代器，Bidirectional
  Iterator支持的操作都支持，另外还支持 operator[ ] 随机访问容器内元素