内容来自《C++ Primer（第5版）》9.2.1 迭代器、9.2.3 begin和end成员、9.3.6 容器操作可能使迭代器失效、10.4.3 反向迭代器

1. 迭代器

1.1 迭代器范围

1.2 使用左闭合范围蕴含的编程假定

2. begin和end成员

3. 容器操作可能使迭代器失效

3.1 编写改变容器的循环程序

3.2 不要保存end返回的迭代器

4. 反向迭代器

4.1 反向迭代器需要递减运算符

4.2 反向迭代器和其他迭代器间的关系

1. 迭代器

与容器一样，迭代器有着公共的接口：如果一个迭代器提供某个操作，那么所有提供相同操作的迭代器对这个操作的实现方式都是相同的。例如，标准容器类型上的所有迭代器都允许我们访问容器中的元素，而所有迭代器都是通过解引用运算符来实现这个操作的。类似的，标准库容器的所有迭代器都定义了递增运算符，从当前元素移动到下一个元素。

表1列出了容器迭代器支持的所有操作，其中有一个例外不符合公共接口特点——forward_list迭代器不支持递减运算符（--）。表2列出了迭代器支持的算术运算，这些运算只能应用于string、vector、deque和array的迭代器。我们不能将它们用于其他任何容器类型的迭代器。

表1 迭代器的运算符
*iter	返回迭代器iter所指元素的引用
iter->mem	解引用iter并获取该元素的名为mem的成员，等价于(*iter) .mem
++iter	令iter指示容器中的下一个元素
--iter	令iter指示容器中的上一个元素
iter1 == iter2	判断两个迭代器是否相等（不相等），如果两个迭代器指示的是同一个元素或者它们是同一个容器的尾后迭代器，则相等；反之，不相等
iter1 != iter2

表2 迭代器支持的运算
iter + n	迭代器加上一个整数值仍得一个迭代器，迭代器指示的新位置与原来相比向前移动了若干个元素。结果迭代器或者指示容器内的一个元素，或者指示容器尾元素的下一位置
iter - n	迭代器减去一个整数值仍得一个迭代器，迭代器指示的新位置与原来相比向后移动了若干个元素。结果迭代器或者指示容器内的一个元素，或者指示容器尾元素的下一位置
iter1 += n	迭代器加法的复合赋值语句，将iter1加n的结果赋给iter1
iter1 -= n	迭代器减法的复合赋值语句，将iter1减n的结果赋给iter1
iter1 - iter2	两个迭代器相减的结果是它们之间的距离，也就是说，将运算符右侧的迭代器向前移动差值个元素后将得到左侧的迭代器。参与运算的两个迭代器必须指向的是同一个容器中的元素或者尾元素的下一位置
>、>=、<、<=	迭代器的关系运算符，如果某迭代器指向的容器位置在另一个迭代器所指位置之前，则说前者小于后者。参与运算的两个迭代器必须指向的是同一个容器中的元素或者尾元素的下一位置

1.1 迭代器范围

Note

迭代器范围的概念是标准库的基础。

一个迭代器范围（iterator range）由一对迭代器表示，两个迭代器分别指向同一个容器中的元素或者是尾元素之后的位置（one past the last element）。这两个迭代器通常被称为begin和end，或者是first和last（可能有些误导），它们标记了容器中元素的一个范围。

虽然第二个迭代器常常被称为last，但这种叫法有些误导，因为第二个迭代器从来都不会指向范围中的最后一个元素，而是指向尾元素之后的位置。迭代器范围中的元素包含first所表示的元素以及从first开始直至last（但不包含last）之间的所有元素。

这种元素范围被称为左闭合区间（left-inclusive interval），其标准数学描述为

[begin, end)

表示范围自begin开始，于end之前结束。迭代器begin和end必须指向相同的容器。end可以与begin指向相同的位置，但不能指向begin之前的位置。

对构成范围的迭代器的要求

如果满足如下条件，两个迭代器begin和end构成一个迭代器范围：

它们指向同一个容器中的元素，或者是容器最后一个元素之后的位置，且
我们可以通过反复递增begin来到达end。换句话说，end不在begin之前。

WARNING

编译器不会强制这些要求。确保程序符合这些约定是程序员的责任。

1.2 使用左闭合范围蕴含的编程假定

标准库使用左闭合范围是因为这种范围有三种方便的性质。假定begin和end构成一个合法的迭代器范围，则

如果begin与end相等，则范围为空
如果begin与end不等，则范围至少包含一个元素，且 begin指向该范围中的第一个元素
我们可以对begin递增若干次，使得begin==end

这些性质意味着我们可以像下面的代码一样用一个循环来处理一个元素范围，而这是安全的：

while (begin != end) {
    *begin = val;//正确：范围非空，因此begin指向一个元素
    ++begin;     //移动迭代器，获取下一个元素
}

给定构成一个合法范围的迭代器begin和end，若 begin==end，则范围为空。在此情况下，我们应该退出循环。如果范围不为空，begin指向此非空范围的一个元素。因此，在while循环体中，可以安全地解引用begin，因为begin必然指向一个元素。最后，由于每次循环对begin递增一次，我们确定循环最终会结束。

2. begin和end成员

begin和end操作生成指向容器中第一个元素和尾元素之后位置的迭代器。这两个迭代器最常见的用途是形成一个包含容器中所有元素的迭代器范围。

表3 获取迭代器操作
begin	end
rbegin	rend
cbegin	cend
crbegin	crend

如表3所示，begin和end有多个版本：带r的版本返回反向迭代器；以c开头的版本则返回const迭代器：

list<string> a = { "Milton","Shakespeare","Austen" };
auto itl = a.begin();  //list<string>::iterator
auto it2 = a.rbegin(); //list<string>::reverse_iterator
auto it3 = a.cbegin(); //list<string>::const_iterator
auto it4 = a.crbegin();//list<string>::const_reverse_iterator

不以c开头的函数都是被重载过的。也就是说，实际上有两个名为begin的成员。一个是const成员，返回容器的const_iterator类型。另一个是非常量成员，返回容器的iterator类型。rbegin、end和rend的情况类似。当我们对一个非常量对象调用这些成员时，得到的是返回iterator的版本。只有在对一个const对象调用这些函数时，才会得到一个const版本。与const指针和引用类似，可以将一个普通的iterator转换为对应的const_iterator，但反之不行。

以c开头的版本是C++新标准引入的，用以支持auto与begin和end函数结合使用。过去，没有其他选择，只能显式声明希望使用哪种类型的迭代器：

//显式指定类型
list<string>::iterator it5 = a.begin();
list<string>::const_iterator it6 = a.begin();

//是iterator还是const_iterator依赖于a的类型
auto it7 = a.begin(); //仅当a是const时，it7是const_iterator
auto it8 = a.cbegin();//it8是const_iterator

当auto与begin或end结合使用时，获得的迭代器类型依赖于容器类型，与我们想要如何使用迭代器毫不相干。但以c开头的版本还是可以获得const_iterator的，而不管容器的类型是什么。

Best Practices

当不需要写访问时，应使用cbegin和cend。

3. 容器操作可能使迭代器失效

向容器中添加元素和从容器中删除元素的操作可能会使指向容器元素的指针、引用或迭代器失效。一个失效的指针、引用或迭代器将不再表示任何元素。使用失效的指针、引用或迭代器是一种严重的程序设计错误，很可能引起与使用未初始化指针一样的问题。

在向容器添加元素后：

如果容器是vector或string，且存储空间被重新分配，则指向容器的迭代器、指针和引用都会失效。如果存储空间未重新分配，指向插入位置之前的元素的迭代器、指针和引用仍有效，但指向插入位置之后元素的迭代器、指针和引用将会失效。
对于deque，插入到除首尾位置之外的任何位置都会导致迭代器、指针和引用失效。如果在首尾位置添加元素，迭代器会失效，但指向存在的元素的引用和指针不会失效。
对于list和forward_list，指向容器的迭代器（包括尾后迭代器和首前迭代器）、指针和引用仍有效。

当我们从一个容器中删除元素后，指向被删除元素的迭代器、指针和引用会失效，这应该不会令人惊讶。毕竟，这些元素都已经被销毁了。当我们删除一个元素后：

对于list和forward_list，指向容器其他位置的迭代器（包括尾后迭代器和首前迭代器）、引用和指针仍有效。
对于deque，如果在首尾之外的任何位置删除元素，那么指向被删除元素外其他元素的迭代器、引用或指针也会失效。如果是删除deque的尾元素，则尾后迭代器也会失效，但其他迭代器、引用和指针不受影响；如果是删除首元素，这些也不会受影响。
对于vector和string，指向被删元素之前元素的迭代器、引用和指针仍有效。注意：当我们删除元素时，尾后迭代器总是会失效。

WARNING

使用失效的迭代器、指针或引用是严重的运行时错误。

建议：管理迭代器

当你使用迭代器（或指向容器元素的引用或指针）时，最小化要求迭代器必须保持有效的程序片段是一个好的方法。

由于向迭代器添加元素和从迭代器删除元素的代码可能会使迭代器失效，因此必须保证每次改变容器的操作之后都正确地重新定位迭代器。这个建议对vector、string和deque尤为重要。

3.1 编写改变容器的循环程序

添加/删除vector、string或deque元素的循环程序必须考虑迭代器、引用和指针可能失效的问题。程序必须保证每个循环步中都更新迭代器、引用或指针。如果循环中调用的是insert或erase，那么更新迭代器很容易。这些操作都返回迭代器，我们可以用来更新：

//傻瓜循环，删除偶数元素，复制每个奇数元素
vector<int> vi = { 0,1,2,3,4,5,6,7,8,9 };
auto iter = vi.begin();//调用begin而不是cbegin，因为我们要改变vi
while (iter != vi.end()) {
	if (*iter % 2) {
		iter = vi.insert(iter, *iter);//复制当前元素
		iter += 2;//向前移动迭代器，跳过当前元素以及插入到它之前的元素
	}else
		iter = vi.erase(iter);//删除偶数元素
		//不应向前移动迭代器，iter指向我们删除的元素之后的元素
}

此程序删除vector中的偶数值元素，并复制每个奇数值元素。我们在调用insert和erase后都更新迭代器，因为两者都会使迭代器失效。

在调用erase后，不必递增迭代器，因为erase返回的迭代器已经指向序列中下一个元素。调用insert后，需要递增迭代器两次。记住，insert在给定位置之前插入新元素，然后返回指向新插入元素的迭代器。因此，在调用insert后，iter指向新插入元素，位于我们正在处理的元素之前。我们将迭代器递增两次，恰好越过了新添加的元素和正在处理的元素，指向下一个未处理的元素。

3.2 不要保存end返回的迭代器

当我们添加/删除vector或string的元素后，或在deque中首元素之外任何位置添加/删除元素后，原来end返回的迭代器总是会失效。因此，添加或删除元素的循环程序必须反复调用end，而不能在循环之前保存end返回的迭代器，一直当作容器末尾使用。通常C++标准库的实现中end()操作都很快，部分就是因为这个原因。

例如，考虑这样一个循环，它处理容器中的每个元素，在其后添加一个新元素。我们希望循环能跳过新添加的元素，只处理原有元素。在每步循环之后，我们将定位迭代器，使其指向下一个原有元素。如果我们试图“优化”这个循环，在循环之前保存end()返回的迭代器，一直用作容器末尾，就会导致一场灾难：

//灾难：此循环的行为是未定义的
auto begin = v.begin(),
end = v.end();//保存尾迭代器的值是一个坏主意
while (begin != end) {
	//做一些处理
	//插入新值，对begin重新赋值，否则的话它就会失效
	++begin;//向前移动begin，因为我们想在此元素之后插入元素
	begin = v.insert(begin, 42);//插入新值
	++begin; // 向前移动begin跳过我们刚刚加入的元素
}

此代码的行为是未定义的。在很多标准库实现上，此代码会导致无限循环。问题在于我们将end操作返回的迭代器保存在一个名为end的局部变量中。在循环体中，我们向容器中添加了一个元素，这个操作使保存在end中的迭代器失效了。这个迭代器不再指向v中任何元素，或是v中尾元素之后的位置。

Tip

如果在一个循环中插入/删除deque、string或vector中的元素，不要缓存end返回的迭代器。

必须在每次插入操作后重新调用end()，而不能在循环开始前保存它返回的迭代器：

//更安全的方法：在每个循环步添加/删除元素后都重新计算end
while (begin != v.end() {
    //做一些处理
    ++begin;//向前移动begin，因为我们想在此元素之后插入元素
    begin = v.insert(begin, 42);//插入新值
    ++begin;//向前移动begin，跳过我们刚刚加入的元素
}

4. 反向迭代器

反向迭代器就是在容器中从尾元素向首元素反向移动的迭代器。对于反向迭代器，递增（以及递减）操作的含义会颠倒过来。递增一个反向迭代器（++it）会移动到前一个元素；递减一个迭代器（--it）会移动到下一个元素。

除了forward_list之外，其他容器都支持反向迭代器。我们可以通过调用rbegin、rend、crbegin和 crend成员函数来获得反向迭代器。这些成员函数返回指向容器尾元素和首元素之前一个位置的迭代器。与普通迭代器一样，反向迭代器也有const和非const版本。

下图显示了一个名为vec的假设的vector上的4种迭代器：

下面的循环是一个使用反向迭代器的例子，它按逆序打印vec中的元素：

vector<int> vec = { 0,1,2,3,4,5,6,7,8,9 };
//从尾元素到首元素的反向迭代器
for (auto r_iter = vec.crbegin();//将r_iter绑定到尾元素
		r_iter != vec.crend();   //crend指向首元素之前的位置
		++r_iter)                //实际是递减，移动到前一个元素
	cout << *r_iter << endl;     //打印9,8,7,...,0

虽然颠倒递增和递减运算符的含义可能看起来令人混淆，但这样做使我们可以用算法透明地向前或向后处理容器。例如，可以通过向sort传递一对反向迭代器来将vector整理为递减序：

sort(vec.begin(), vec.end());//按“正常序”排序vec
//按逆序排序：将最小元素放在vec的末尾
sort(vec.rbegin(), vec.rend());

4.1 反向迭代器需要递减运算符

不必惊讶，我们只能从既支持++也支持--的迭代器来定义反向迭代器。毕竟反向迭代器的目的是在序列中反向移动。除了forward_list之外，标准容器上的其他迭代器都既支持递增运算又支持递减运算。但是，流迭代器不支持递减运算，因为不可能在一个流中反向移动。因此，不可能从一个forward_list或一个流迭代器创建反向迭代器。

4.2 反向迭代器和其他迭代器间的关系

假定有一个名为line的string，保存着一个逗号分隔的单词列表，我们希望打印line中的第一个单词。使用find可以很容易地完成这一任务：

//在一个逗号分隔的列表中查找第一个元素
auto comma = find(line.cbegin(), line.cend(), ',');
cout << string(line.cbegin(), comma) << endl;

如果line中有逗号，那么comma将指向这个逗号；否则，它将等于line.cend()。当我们打印从line.cbegin()到comma之间的内容时，将打印到逗号为止的字符，或者打印整个string（如果其中不含逗号的话）。

如果希望打印最后一个单词，可以改用反向迭代器：

//在一个逗号分隔的列表中查找最后一个元素
auto rcomma = find(line.crbegin(), line.crend(), ',');

由于我们将crbegin()和crend()传递给find，find将从line的最后一个字符开始向前搜索。当find完成后，如果line中有逗号，则rcomma指向最后一个逗号——即，它指向反向搜索中找到的第一个逗号。如果line中没有逗号，则rcomma指向line.crend()。

当我们试图打印找到的单词时，最有意思的部分就来了。看起来下面的代码是显然的方法

//错误：将逆序输出单词的字符
cout << string(line.crbegin(), rcomma) << endl;

但它会生成错误的输出结果。例如，如果我们的输入是

FIRST,MIDDLE,LAST

则这条语句会打印TSAL!

下图说明了问题所在：我们使用的是反向迭代器，会反向处理string。因此，上述输出语句从 crbegin开始反向打印line中内容。而我们希望按正常顺序打印从rcomma开始到line末尾间的字符。但是，我们不能直接使用rcomma。因为它是一个反向迭代器，意味着它会反向朝着string的开始位置移动。需要做的是，将rcomma转换回一个普通迭代器，能在line中正向移动。我们通过调用reverse_iterator的base成员函数来完成这一转换，此成员函数会返回其对应的普通迭代器：

//正确：得到一个正向迭代器，从逗号开始读取字符直到line末尾
cout << string(rcomma.base(), line.cend()) << endl;

给定和之前一样的输入，这条语句会如我们的预期打印出LAST。

图中的对象显示了普通迭代器与反向迭代器之间的关系。例如，rcomma和rcomma.base()指向不同的元素，line.crbegin和line.cend()也是如此。这些不同保证了元素范围无论是正向处理还是反向处理都是相同的。

从技术上讲，普通迭代器与反向迭代器的关系反映了左闭合区间的特性。关键点在于[line.crbegin (), rcomma)和[rcomma.base(), line.cend())指向line中相同的元素范围。为了实现这一点，rcomma和rcomma.base()必须生成相邻位置而不是相同位置，crbegin()和cend()也是如此。