STL Iterator的里里外外（一）？

1. Iterator是什么？

　　Iterator是指针的概括物(泛型指针)，是可以通过一组通用的接口类似于普通指针那样遍历区间中的所有元素的对象。Iterator是完全抽象的概念：任何行为类似于Iterator的东西就是一个Iterator(例如：指针是数组的迭代器)。

　　Iterator是算法和数据结构(容器)之间的接口，被实现为一个智能指针，提供对operator*和operaor->等进行重载。但是不同的Iterator具有不同的能力，这就牵扯到了Iteratorde的分类。

2. Iterator分类

　　Iterator具有5种分类，是5个concept的集合。

　　　　　　　　Iterator Categories

　　Input Iterator 　　　　OutputIterator

　　　　　　　　Forward Iterator

　　　　　　　Bidirectional Iterator

　　　　　　Random Access Iterator

　　这5中分类决定了5种Iterator, 其中普通指针是Random access Iterator这个concept的一个modal。

　　STL给了这5种Iterator一个tag用于标识这五种

　　namespace std {

　　　　//只有一种output

　　　　struct output_iterator_tag {
　　　　};

　　　　//下面的所有都是一种input, 注意继承关系

　　　　struct input_iterator_tag {
　　　　}

　　　　struct forward_iterator_tag  : public input_iterator_tag {
　　　　}

　　　　sturct bidirectional _iterator_tag : public forward_iterator_tag {
　　　　}

　　　　struct random_access_iterator_tag : public bidirctional_iterator_tag {
　　　　}

　　}

3. 各种Iterator的能力

3.1 Output iteator

　　具有只写性质，适用于单回（single-pass）算法，如：copy。

　　Input iterator的需求条件：

　　（1）可以复制和赋值： Type(iter), copy constructor

　　 (2) 可以写值： *iter = val，但是不能读：val = *iter，val = iter->member;

　　 (3) 可以累加：++iter, iter++。

　　注意：不支持 ==， ！=, 唯一不支持的iterator。

　　类似Input iterator，同一时间不能有两个不同的Output iterator指向同一个区间内的不同地点。移动中的指针进行写入，一旦写完遍继续移动。

　　下面以copy算法来讲述：

　　template <typename InputIterator, typename OutputIterator>

　　OutputIterator copy(InputIterator first, InputIterator last, OutputIterator result)

　　{

　　　　for (  ; first != last; ++result, ++first) {

　　　　　　*result = *first;
　　　　}

　　　　return result;
　　}

　　copy输入区间需要只读性质，输出区间需要只写性质，是与输入输出都有关的单回算法。

　　Output Iterator 所形成的区间都是以单独一个Iterator再加上一个计量值来决定的。如copy: 输出区间以result开头，再以[first, last）的元素个数作为

区间的长度。

　　Output iterator :有 insert_iterator, front_insert_iterator, back_insert_iterator和 ostream_iterator。

　　ostream_iterator iter; *iter = val会使val格式化输出到ostream身上。

　　template <class T>

　　class ostrem_iterator {

　　private:

　　　　ostream *os;

　　　　const char *string;

　　public:

　　　　ostrem_iterator(ostream &s, const char *c = 0) : os(&s), string(c) {}

　　　　ostream_iterator(const ostream_iterator &i) : os(i.os), string(i.string) {}

　　　　ostream_iterator& operator=(const ostream_iterator &i)

　　　　{

　　　　　　os = i.os;

　　　　　　string = i.string;

　　　　　　return *this;
　　　　}

　　　　ostream_iterator<T>& operator=(const T &value)　　

　　　　{

　　　　　　*os << value;

　　　　　　if (string)  {

　　　　　　　　*os << string;
　　　　　　}

　　　　　　return *this;
　　　　}

　　　　//实现os << value; 替换为 *iter = val;使用proxy class, 而且是其自身*this,也可以使用其它class但是没理由这么做。

　　　　ostream_iterator<T>& operator*() { return *this; }

　　　　ostream_iterator<T>& operator++() { return *this; }

　　　　ostream_iterator<T>& operator++(int) { return *this; }
　　};

3.2 Input Iterator

　　具有只读性质，适用于单回（single-pass）算法，如：copy。

　　限制条件：

　　（1）Input iterator用来指向某对象，但不需要提供任何更改该对象的方法, 就是只读的。

　　你可以*或->，但是不能对结果赋值，即：*iter; iter->member可以，*iter = val（要求写）不一定可以。

　　（2）Input iterator可以累加，但是不可以递减。

　　可以++iter; iter++, 这是Input iterator唯一需要的运算形式。 不可以--iter; iter--。

　　（3）Input iterator支持有限的比较形式，可以测试iter1 = iter2； iter1 ！= iter2； 但是不可以比较谁在谁前面。

　　（4）Input iterator 是 single pass的，你有且只能遍历range(beg, end)一次。不能重复遍历。

　　（5）Input iterator可以copy,支持copy constructor: TYPE（iter）。

　　特点：

　　Input iterator 只能读元素一次，如果使用iterator的副本和原始迭代器共同读，可能读取不同的值。典型的情况是从键盘读取输入，你不能读取两次。

　　Input iterator 就像从终端机或网络连线读取数据一样的读取输入值：你可以要求下一个值，但一旦如此，前一个值就消失无踪了。使用Input iterator class

istream_iterator,可以简单的从input stream读取数据。

　　使用Input iterator的算法：

　　此算法必须是single pass（单回）的算法，只需要遍历区间一次读取值，不需要更改值的。常见有：

find, find_if, equal, partial_sum, random_sample, set_intersection等等。

3.3.  Forward Iterators

　　缘起：

　　（1） input iterator具只读性， output iterator 具只写性。意味着： 需要读取并更改的某一区间的算法，无法单就这些concept来运作。

可以利用input iterator写出某种查找算法，但是无法写出查找并置换的算法。

　　（2） 运用input iterator和output iterator的算法，只能是single pass算法，使得算法的复杂度O(N)。

　　(3)任何时刻，区间内只能有一个有效的input iterator或output iterator。使得算法在同一时刻只能对单一元素做动作。对于行为取决于两个或多个不同元素

之间的关系的算法无能为力。

　　而采用Fordward iterator就不会有上述限制。一个Forward iterator model必须是input iterator model和output iterator model。

因此，可以写出一种算法在同一区间内做读取动作和更新动作。

　　例如：replace()

　　template <class ForwardIterator, class T>

　　void replace(ForwardIterator first, ForwardIterator last,

　　　　　　　　  const T &old_value, const T &new_value)

　　{

　　　　for ( ; first != last; ++first) {

　　　　　　if (*first == old_value) {

　　　　　　　　*first = new_valude;
　　　　　　}
　　　　}
　　}

　　replace 是single pass算法，一次只作用一个元素，由于需要在同一个iterator上进行读取和更改，所以用Forward_iterato。

　　Forward iterator也适用于在同一区间使用一个以上的iterator，是multipass的。

　　//查找连续两个元素具有相同值

　　template <class ForwardIterator>

　　ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last)

　　{

　　　　if (first == last) {

　　　　　　return last;
　　　　}

　　　　ForwardIterator next = first;

　　　　while (++next != last) {

　　　　　　if (*first == *next) {

　　　　　　　　return first;
　　　　　　}

　　　　　　first = next;
　　　　}

　　　　return last;
　　｝　　

　　*first = *next;使用了两个Iterator所以用Forward_iterator。

　　所以相比于Input iterator和Output iterator， forward_iterator提供了iter1 = iter2,因为它可以使用不同的Iteator。

　　相关容器： forward_list<>, unordered containes。

3.4. Bidrectional Iterator

　　类似于Forward Iterator,Bidirection iterator允许multipass，也可以是const或mutable。

　　支持双向移动，因此相对于Forward_iterator支持--iter和iter--，如遍历单项链表用Forward Iterator，遍历双向链表用Bidirectiorn iterator。

　　通常是由于需要反向移动而选择Bidirectional iterator, 即指定某元素之后需要寻找先前的元素。

　　如：

　　template <class BidrectionalIteartaor, class OutputIterator>

　　OutputIterator reverse_copy(BidirctionalIterator first, Bidirctional last, OutputIterator result)

　　{

　　　　while (first ！= last) {

　　　　　　--last;

　　　　　　*result = *last;

　　　　　　++result;
　　　　}

　　　　return result;

　　}

　　需要--last;

　　相关容器： class list<>, association containers。

3.5 Random Access Iterators

　　提供了算术运算能力：iter + n, iter -n, iter[n], iter - iter2, iter < iter2，这些都是特有的。

　　排序算法需要用到这个iterator,需要对比并交换相隔甚远的元素，而非只是相邻元素。

　　考虑到Random Access Iterator主要是考虑到复杂度：

　　例如：advance(), Forward Iterator是O(N), 而随机Iterator为O(1);

　　所以：Random Access iterator正真独特的性质为：在固定时间随机访问任意元素。

　　相关容器： array, vector, deque, string, wstring, C-style arrays(pointers)。