[C++ Primer]一些关于"向 vector 对象添加元素蕴含的编程假定"

作者 Shilei Tian 日期 2016-09-13
C++
[C++ Primer]一些关于"向 vector 对象添加元素蕴含的编程假定"

C++ Primer 在讲述向 vector 中添加元素的时候有一个应该注意的一点,就是

For reasons we’ll explain in 5.4.3, we cannot use a range for if the body of the loop adds elements to the vector.

Warning: The body of a range for must not change the size of the sequence over which it is iterating.

意思就是,作者说不要在通过 for 遍历 vector 的时候向它添加元素,具体的会在 5.4.3 地方讲,我去 5.4.3 里面看了一下,那一部分用 for 来对 vector 进行迭代的时候,使用的是 iterator,后面解释道,

In a range for, the value of the end() is cached. If we add elements to (or remove them from) the sequence, the value of end() might be invalidated.

这里我们来探索一下,到底是不是真的不能在遍历 vector 的时候去增加元素了,删除元素这里先不考虑。遍历 vector 可以通过下标,可以通过 iterator,还可以通过范围 for 语句,那我们就尝试从这三个方式来探索。

下标遍历

如果我们通过下标来遍历 vector 的过程中添加元素会发生什么呢?我们来看一段程序:

#include <iostream>
#include <vector>
using namespace std;
int main(int argc, char *argv[]) {
vector<int> vec(5, 1);
for (decltype(vec.size()) i = 0; i < vec.size(); ++i) {
vec[i] = i;
}
unsigned int cnt = 0;
for (decltype(vec.size()) i = 0; i < vec.size(); ++i) {
cout << vec[i] << endl;
if (cnt < 3) {
vec.push_back(vec.size());
}
++cnt;
}
return 0;
}

上面这段程序我们先定义一个容量为 5 的 vecotor,然后我们对其遍历。在遍历的时候,我们设置一个计数值 cnt,当 cnt < 3 的时候,向 vector 中添加一个元素。那这个程序的运行结果是什么呢?大家可以将代码跑一下看看。答案是,能够正确遍历。

0
1
2
3
4
5
6
7

这一点其实告诉我们,在 for 语句的判断中,那个 vec.size() 是每次都要计算一次的,只有这样这个遍历才可以正确的执行。

iterator 遍历

我们将上面的程序稍作修改,得到下面使用 iterator 的版本:

#include <iostream>
#include <vector>
using namespace std;
int main(int argc, char *argv[]) {
vector<int> vec(5, 1);
for (decltype(vec.size()) i = 0; i < vec.size(); ++i) {
vec[i] = i;
}
unsigned int cnt = 0;
for (auto itr = vec.begin(); itr != vec.end(); ++itr) {
cout << *itr << endl;
if (cnt < 3) {
vec.push_back(vec.size());
}
++cnt;
}
return 0;
}

那这个版本的遍历能否成功呢?答案是——否定的!这个版本的程序得到的结果很随机,也就是它无法正确遍历,循环执行的次数也是随机的。

范围 for 遍历

我们继续将之前的程序进行修改,得到下面这个版本:

#include <iostream>
#include <vector>
using namespace std;
int main(int argc, char *argv[]) {
vector<int> vec(5, 1);
for (decltype(vec.size()) i = 0; i < vec.size(); ++i) {
vec[i] = i;
}
unsigned int cnt = 0;
for (auto v : vec) {
cout << v << endl;
if (cnt < 3) {
vec.push_back(vec.size());
}
++cnt;
}
return 0;
}

这个版本的程序得到的结果如下:

0
1
2
3
4

从这个结果来看,在 for 开始执行之前程序就已经确定了遍历的次数,无论后期添加了多少,还是执行到之前的次数,我猜测这个遍历类似下面这样的:

decltype(vec.size()) size = vec.size();
for (decltype(vec.size()) i = 0; i < size; ++i) { // 判断部分是关键
cout << vec[i] << endl;
if (cnt < 3) {
vec.push_back(vec.size());
}
++cnt;
}

总结

通过上面的结果看,如果需要在遍历的时候添加元素,那么使用下标来遍历看起来是个不错的选择。但是,我还是觉得,在遍历的时候能不对 vector 进行添加就不添加。但凡是使用了 iterator 的循环体,都不要向 iterator 所属的容器添加元素。

下面我们来解释一下为什么使用 iterator 的循环体遍历会出错。因为我们这里的操作是使用的 push_backvector 会动态管理它的空间,如果在添加一个元素后没有重新分配空间,那么指向插入位置之前的元素的iterator、指针和引用仍有效,但指向插入位置之后元素的迭代器、指针和引用将会失效。但是,如果执行添加操作以后,空间被重新分配,那么之前所有的 iterator、指针和引用都就失效了。那么何时会重新分配空间呢?这个跟不同版本的 STL 的实现不同,因此会出现不确定的现象。

不过,删除操作就不一样了,有一种情况会导致遍历的时候缺少元素,我们以后再来谈论这个问题。