C++/STL/Iterator

iterator 是w:C++標準程式庫中的一個w:头文件，定义了C++ STL标准中的一些w:迭代器模板类 ，这些类都是以std::iterator为基类派生出来的。

迭代器模拟了C++中的指针，可以有++运算，用*（解引用算符，deference）或->算符来访问容器中的元素。容器中元素如果改变了所用内存，也不影响绑定的迭代器指向正确的位置。因此，迭代器实际上更像是句柄（handler）。

STL的迭代器实现了设计模式中的“w:迭代器模式”。即顺序访问一个聚合中的元素，又不暴露聚合的实现细节。

迭代器支持以不同方法遍历聚合类型。例如，对一颗树数据类型，可以有前序、中序、后序遍历的迭代器。同一个聚合类型的对象上，可以同时有多个迭代器，各自保持不同的遍历状态。在不同的聚合类型上实现的迭代器具有标准的对外接口，这给STL中的算法使用迭代器提供了可能。熟练掌握这些迭代器的构造、用法，是基于STL的模板元编程的基础。

迭代器的分类与接口

所有迭代器都应该实现自增算符：iter++、++iter

• Input迭代器：
  • *iter 解引用后只能用作右值
  • iter->member 解引用访问当前对象的成员数据
  • iter=iter1 迭代器赋给另一个迭代器
  • iter==iter1 迭代器相等比较
  • iter!=iter1 迭代器不等比较
• Output迭代器：
  • *iter 解引用后只能用作左值
  • iter=iter1 迭代器赋给另一个迭代器
• Forward迭代器：具有输入迭代器、输出迭代器的所有功能，且可以反复遍历操作。支持对同一个元素的多次读写。可复制前向迭代器来记录序列中的一个位置，以便将来返回此处。
• Bidirectional迭代器：是在前向迭代器的基础上，多了单步向后遍历的能力
  • --iter
  • iter--
• Random Access迭代器：在双向迭代器基础上，具有直接访问各数据元素的能力。随机迭代器增加了“迭代器算术运算”：
  • iter+=i 迭代器递增i位
  • iter-=i 迭代器递减i位
  • iter+i 加i位后的迭代器
  • iter-i 减i位后的迭代器
  • iter[i] 加i位后的迭代器的解引用
  • iter<iter1 如果迭代器iter的位置在iter1前，返回true，否则返回false
  • iter<=iter1 如果iter的位置在iter1的前面或同一位置时返回true，否则返回false
  • iter>iter1 如果迭代器iter的位置在iter1后，返回true，否则返回false
  • iter>=iter1 如果iter的位置在iter1的后面或同一位置时返回true，否则返回false

在STL定义的容器中，string，vector与deque提供了随机访问迭代器，list、set、multiset、map、multimap提供了双向迭代器。

<iterator>中定义的类

iterator_traits

iterator_traits是一个类模板，用于定义一批成员数据类型，使得STL的算法可以用一致的界面来使用各种迭代器。下述类型定义中的Iterator是类模板参数：

• difference_type Iterator::difference_type
• value_type Iterator::value_type
• pointer Iterator::pointer
• reference Iterator::reference
• iterator_category Iterator::iterator_category

5个作为iterator tag的空类

input_iterator_tag, output_iterator_tag, forward_iterator_tag, bidirectional_iterator_tag, random_access_iterator_tag均为空类。用于函数（模板）重载时的参数，以便STL算法据此判明迭代器所属类别做进一步优化。

iterator模板类

在iterator模板类中，定义了5个成员类别：value_type,difference_type pointer，reference, iterator_category，用作所有其它迭代器的基类。

iterator adapters

• reverse_iterator模板类，用来逆序遍历聚合，是STL各容器类的rbegin、rend成员函数返回的类型。其构造函数用正向迭代器作为参数，构造得到的迭代器指向参数迭代器所指位置的逆序的下一个元素。如果逆序迭代器r是用正序迭代器i构造得到，则&*r == &*(i-1)为真。逆序迭代器的成员函数base()，返回指向当前定位的正序迭代器。
• move_iterator模板类，是一种输入迭代器。但与普通的迭代器不同，解引用（deference）操作得到的是右值，并按移动(move)赋值语义处理。
• make_move_iterator模板函数，用于方便地由一个容器构造出move_iterator。
• back_insert_iterator模板类，是一种输出迭代器，用于在容器对象的尾部追加新的元素。该迭代器被赋值时，调用了容器对象的push_back()成员函数。该迭代器的自增操作实际上为空操作。
• back_inserter模板函数，用于方便地由一个容器构造出back_insert_iterator
• front_insert_iterator模板类，是一种输出迭代器，用于在容器对象的头部插入新的元素。该迭代器被赋值时，调用了容器对象的push_front()成员函数。该迭代器的自增操作实际上为空操作。
• front_inserter模板函数，用于方便地由一个容器构造出front_insert_iterator
• insert_iterator模板类，是一种输出迭代器，用于在容器对象的指定位置插入新的元素。该迭代器被赋值时，调用了容器对象的insert()成员函数。该迭代器的自增操作实际上为空操作。
• insert_inserter模板函数，用于方便地由一个容器构造出insert_iterator

流迭代器

任何已定义输入操作符(>>)的类型都可以定义istream_iterator。任何已定义输出操作符(<<)的类型也可定义ostream_iterator。在创建流迭代器时，必须指定迭代器所读写的对象类型。

• istream_iterator模板类，是一种单次遍历（single-pass）的输入迭代器。把一个std::basic_istream包装为一个输入流迭代器。从输入流迭代器通过自增操作来读取数据，实际上是调用了输入流的>>算符。输入流迭代器的默认构造函数返回一个指向流结束（end-of-stream）的迭代器。
• ostream_iterator模板类，是一种单次遍历（single-pass）的输出迭代器。把一个std::basic_ostream包装为一个输出流迭代器。对输出流迭代器赋值数据，实际上是调用了输出流的<<算符。对输出流迭代器自增，实际上是空操作。输出流迭代器的解引用操作返回该迭代器自身。
• istreambuf_iterator模板类，是一种单次遍历（single-pass）的输入迭代器。把一个std::basic_istreambuf包装为一个输入流迭代器。操作类似于istream_iterator，但效率更高。
• ostreambuf_iterator模板类，是一种单次遍历（single-pass）的输出迭代器。把一个std::basic_ostreambuf包装为一个输出流迭代器。操作类似于ostream_iterator，但效率更高。

迭代器操作函数

• advance：把迭代器增量指定的步数。步数可以是负值。不检查迭代器是否超过序列尾部位置end()
• distance：返回两个迭代器的距离值。两个迭代器必须指向同一个容器。如果不是随机迭代器，则第二个迭代器的位置必须与第一个迭代器的位置相同或在其后。
• iter_swap：交换两个迭代器所指的容器对象的元素值。迭代器类型可以不同，但其所指的值对象必须可以相互赋值。
• next：增量一个正向迭代器增量指定步数。此函数不适用reverse_iterator
• prev：把一个双向迭代器减量指定步数。

迭代器范围函数

包括begin, cbegin, end, cend,rbegin,crbegin,rend, crend等函数。返回聚合容器的开始位置、结束位置。

成员函数base()把逆向迭代器转化为对应的正向迭代器。

正向迭代器转化为逆向迭代器，只需要类型转化。

例子程序

 
#include <iostream>
#include <sstream>
#include <iterator>
#include <numeric>
 
int main()
{
    std::istringstream str("0.1 0.2 0.3 0.4");
    std::partial_sum(std::istream_iterator<double>(str),
                     std::istream_iterator<double>(),
                     std::ostream_iterator<double>(std::cout, " "));
}

运行后，输出结果：

0.1 0.3 0.6 1