【3. 反向迭代器】
反向迭代器是一种反向遍历容器的迭代器。其将自增（和自减）的含义反过来了：
对于反向迭代器，++ 运算将访问前一个元素，而 -- 运算则访问下一个元素。
所有容器还定义了 rbegin 和 rend 成员，分别返回指向容器尾元素和首元素前一位置的反向迭代器。
与普通迭代器一样，反向迭代器也有常量（const）和非常量（nonconst）类型。
图 11.1 使用一个假设名为 vec 的 vector 类型对象阐明了这四种迭代器之间的关系。
假设有一个 vector 容器对象，存储 0-9 这 10 个以升序排列的数字：
vector<int> vec; for (vector<int>::size_type i = 0; i != 10; ++i) vec.push_back(i); // elements are 0,1,2,...9
下面的 for 循环将以逆序输出这些元素：
// reverse iterator of vector from back to front vector<int>::reverse_iterator r_iter; for (r_iter = vec.rbegin(); // binds r_iter to last element r_iter != vec.rend(); // rend refers 1 before 1st element ++r_iter) // decrements iterator one element cout << *r_iter << endl; // prints 9,7,...0
虽然颠倒自增和自减这两个操作符可以它让程序员可以透明地向前或向后处理容器。
例如，为了以降序排列 vector，只需向 sort 传递一对反向迭代器：
// sorts vec in "normal" order sort(vec.begin(), vec.end()); // sorts in reverse: puts smallest element at the end of vec sort(vec.rbegin(), vec.rend());
3.1 反向迭代器需要使用自减操作符
从一个既支持 -- 也支持 ++ 的迭代器就可以定义反向迭代器。
毕竟，反向迭代器的目的是移动迭代器反向遍历序列。
标准容器上的迭代器既支持自增运算，也支持自减运算。
但是，流迭代器却不然，由于不能反向遍历流，因此流迭代器不能创建反向迭代器。
3.2 反向迭代器与其他迭代器之间的关系
假设有一个名为 line 的 string 对象，存储以逗号分隔的单词列表。
我们希望输出 line 中的第一个单词。使用 find 可很简单地实现这个任务：
// find first element in a comma-separated list string::iterator comma = find(line.begin(), line.end(), ','); cout << string(line.begin(), comma) << endl;
如果在 line 中有一个逗号，则 comma 指向这个逗号；否则，comma 的值为 line.end()。
在输出 string 对象中从 line.begin() 到 comma 的内容时，从头开始输出字符直到遇到逗号为止。
如果该 string 对象中没有逗号，则输出整个 string 字符串。
如果要输出列表中最后一个单词，可使用反向迭代器：
// find last element in a comma-separated list string::reverse_iterator rcomma = find(line.rbegin(), line.rend(), ',');
因为此时传递的是 rbegin() 和 rend()，这个函数调用从 line 的最后一个字符开始往回搜索。
当 find 完成时，如果列表中有逗号，那么 rcomma 指向其最后一个逗号，即指向反向搜索找到的第一个逗号。
如果没有逗号，则 rcomma 的值为 line.rend()。
在尝试输出所找到的单词时，有趣的事情发生了：
// wrong: will generate the word in reverse order cout << string(line.rbegin(), rcomma) << endl;
例如，如果输入是：FIRST,MIDDLE,LAST
则将输出 TSAL
图 11.2 阐明了这个问题：使用反向迭代器时，以逆序从后向前处理 string 对象。
为了得到正确的输出，必须将反向迭代器 line.rbegin() 和 rcomma 转换为从前向后移动的普通迭代器。
其实没必要转换 line.rbegin()，因为我们知道转换的结果必定是 line.end()。
只需调用所有反向迭代器类型都提供的成员函数 base 转换 rcomma 即可：
// ok: get a forward iterator and read to end of line cout << string(rcomma.base(), line.end()) << endl;
假设还是前面给出的输入，该语句将如愿输出 LAST。
图 11.2 显示的对象直观地解释了普通迭代器与反向迭代器之间的关系。
例如，正如 line_rbegin() 和 line.end() 一样，rcomma 和 rcomma.base() 也指向不同的元素。
为了确保正向和反向处理元素的范围相同，这些区别是必要的。
从技术上来说，设计普通迭代器与反向迭代器之间的关系是为了适应左闭合范围这个性质的，
所以，[line.rbegin(), rcomma) 和 [rcomma.base(), line.end()) 标记的是 line 中的相同元素。
Note:反向迭代器用于表示范围，而所表示的范围是不对称的，
这个事实可推导出一个重要的结论：
使用普通的迭代器对反向迭代器进行初始化或赋值时，所得到的迭代器并不是指向原迭代器所指向的元素。
【4. const 迭代器】
当我们不希望使用这个迭代器来修改容器中的元素。就会选择 const 迭代器。
虽然有的程序也不打算改变容器内的任何元素，
但是它却使用了普通的非 const 迭代器来保存 find_first_of 的返回值。
这两种处理存在细微的差别，值得解释一下。
原因是，在第二个例子中，程序将迭代器用作 find_first_of 的实参：
find_first_of(it, roster1.end(), roster2.begin(), roster2.end())
该函数调用的输入范围由 it 和调用 roster1.end() 返回的迭代器指定。
算法要求用于指定范围的两个迭代器必须具有完全一样的类型。
roster1.end() 返回的迭代器依赖于 roster1 的类型。
如果该容器是 const 对象，则返回的迭代器是 const_iterator 类型；
否则，就是普通的 iterator 类型。
在这个程序中，roster1 不是 const 对象，因而 end 返回的只是一个普通的迭代器。
如果我们将 it 定义为 const_iterator，那么 find_first_of 的调用将无法编译。
用来指定范围的两个迭代器的类型不相同。
it 是 const_iterator 类型的对象，而 rotser1.end() 返回的则是一个 iterator 对象。
【5. 五种迭代器】
迭代器定义了常用的操作集，但有些迭代器具有比其他迭代器更强大的功能。
迭代器可根据所提供的操作集进行分类。
类似地，还可根据算法要求它的迭代器提供什么类型的操作，对算法分类。
有一些算法，例如 find，只要求迭代器提供读取所指向内容和自增的功能。
另一些算法，，比如 sort，则要求其迭代器有读、写和随机访问元素的能力。
算法要求的迭代器操作分为五个类别，分别对应表 11.3 列出的五种迭代器。
// 表 11.3. 迭代器种类 Input iterator（输入迭代器） 读，不能写；只支持自增运算 Output iterator（输出迭代器） 写，不能读；只支持自增运算 Forward iterator（前向迭代器） 读和写；只支持自增运算 Bidirectional iterator（双向迭代器） 读和写；支持自增和自减运算 Random access iterator（随机访问迭代器） 读和写；支持完整的迭代器算术运算
5.1 输入迭代器
可用于读取容器中的元素，但是不保证能支持容器的写入操作。
输入迭代器必须至少提供下列支持。
相等和不等操作符（==，!=），比较两个迭代器。
前置和后置的自增运算（++），使迭代器向前递进指向下一个元素。
用于读取元素的解引用操作符（*），此操作符只能出现在赋值运算的右操作数上。
箭头操作符（->），这是 (*it).member 的同义语，
即对迭代器进行解引用来获取其所关联的对象的成员。
输入迭代器只能顺序使用；一旦输入迭代器自增了，就无法再用它检查之前的元素。
要求在这个层次上提供支持的泛型算法包括 find 和 accumulate。
标准库 istream_iterator 类型输入迭代器。
5.2 输出迭代器
可视为与输入迭代器功能互补的迭代器；
输出迭代器可用于向容器写入元素，但是不保证能支持读取容器内容。
输出迭代器要求：
前置和后置的自增运算（++），使迭代器向前递进指向下一个元素。
解引用操作符（*），引用操作符只能出现在赋值运算的左操作数上。
给解引用的输出迭代器赋值，将对该迭代器所指向的元素做写入操作。
输出迭代器可以要求每个迭代器的值必须正好写入一次。
使用输出迭代器时，对于指定的迭代器值应该使用一次 * 运算，而且只能用一次。
输出迭代器一般用作算法的第三个实参，标记起始写入的位置。
例如，copy 算法使用一个输出迭代器作为它的第三个实参，
将输入范围内的元素复制到输出迭代器指定的目标位置。
标准库 ostream_iterator 类型输出迭代器。
5.3 前向迭代器
用于读写指定的容器。这类迭代器只会以一个方向遍历序列。
前向迭代器支持输入迭代器和输出迭代器提供的所有操作，
除此之外，还支持对同一个元素的多次读写。
可复制前向迭代器来记录序列中的一个位置，以便将来返回此处。
需要前向迭代器的泛型算法包括 replace。
5.4 双向迭代器
从两个方向读写容器。
除了提供前向迭代器的全部操作之外，双向迭代器还提供前置和后置的自减运算。
需要使用双向迭代器的泛型算法包括 reverse。
所有标准库容器提供的迭代器都至少达到双向迭代器的要求。
5.5 随机访问迭代器
提供在常量时间内访问容器任意位置的功能。
这种迭代器除了支持双向迭代器的所有功能之外，还支持下面的操作：
关系操作符 <、<=、> 和 >=，比较两个迭代器的相对位置。
迭代器与整型数值 n 之间的加法和减法操作符 +、+=、- 和 -=，结果是迭代器在容器中向前（或退回）n 个元素。
两个迭代器之间的减法操作符（--），得到两个迭代器间的距离。
下标操作符 iter[n]，这是 *(iter + n) 的同义词。
需要随机访问迭代器的泛型算法包括 sort 算法。
vector、deque 和 string 迭代器是随机访问迭代器，
用作访问内置数组元素的指针也是随机访问迭代器。
除了输出迭代器，其他类别的迭代器形成了一个层次结构：
需要低级类别迭代器的地方，可使用任意一种更高级的迭代器。
对于需要输入迭代器的算法，可传递前向、双向或随机访问迭代器调用该算法。
调用需要随机访问迭代器的算法时，必须传递随机访问迭代器。
map、set 和 list 类型提供双向迭代器，
而 string、vector 和 deque 容器上定义的迭代器都是随机访问迭代器，
用作访问内置数组元素的指针也是随机访问迭代器。
istream_iterator 是输入迭代器，而 ostream_iterator 则是输出迭代器。
关键概念：关联容器与算法
尽管 map 和 set 类型提供双向迭代器，但关联容器只能使用算法的一个子集。
问题在于：关联容器的键是 const 对象。
因此，关联容器不能使用任何写序列元素的算法。
只能使用与关联容器绑在一起的迭代器提供用于读操作的实参。
Tips:在处理算法时，最好将关联容器上的迭代器视为支持自减运算的输入迭代器。
C++ 标准为所有泛型和算术算法的每一个迭代器形参指定了范围最小的迭代器种类。
例如，find（以只读方式单步遍历容器）至少需要一个输入迭代器。
replace 函数至少需要一对前向迭代器。
replace_copy 函数的头两个迭代器必须至少是前向迭代器，
第三个参数代表输出目标，必须至少是输出迭代器。
对于每一个形参，迭代器必须保证最低功能。
将支持更少功能的迭代器传递给函数是错误的；而传递更强功能的迭代器则没问题。
Beware：编译时不一定能检测到向算法传递无效的迭代器类别所引起的错误。