std::vector和std::list的迭代器何时失效问题

c++

vector 和 list 迭代器失效条件

做 cmu15445 的过程中遇到好多迭代器操作，深感对 STL 掌握之不扎实，尤其是对迭代器使用方面，特此记录一下。

在看别人的实现时发现这样的用法：

1
2
3
4
5
6
7
8
9
10
std::list<int> cache;

cache.push_front(i);
auto it = cache.begin();

# 多次 push_front 操作...
cache.push_front(...);

# 使用 it 访问元素
...

第一反应是这样 it 迭代器不会失效吗？查了查 c++ primer，对于 std::vector 和 std::list，迭代器失效的条件是不一样的。

  • 插入操作
    • vector 和 string：如果插入导致存储空间重新分配，则指向容器的迭代器、指针、引用都失效，否则，指向插入位置之前的迭代器、指针、引用有效，之后的都无效。
    • list 和 forward_list：指向容器的迭代器、指针、引用都有效。
    • deque：插入除首尾位置之外的位置会导致迭代器、指针、引用失效，插入首尾会使迭代器失效，指针和引用有效。
  • 删除操作
    • vector 和 string：指向被删除位置之前的迭代器、指针、引用有效。
    • list 和 forward_list：指向容器其他位置的迭代器、指针、引用都有效。
    • deque：在除首尾之外的其他位置删除元素，指向其他位置的迭代器、指针、引用都失效，如果删除尾元素，则尾后迭代器失效。

验证一下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
list<int> l;
// 10 9 8 7 6 5 4 3 2 1 
for(int i = 1; i <= 10; i++)
    l.push_front(i);
// *it = 10, *it2 = 9
auto it = l.begin();
auto it2 = std::next(it);
l.insert(it2, 100);

for(int i: l)
    cout << i << " ";
cout << endl << endl;

cout << (*it) << " " << (*it2) << endl;

输出：

1
2
10 100 9 8 7 6 5 4 3 2 1 
10 9

可见对于 list ，插入点前后迭代器都有效。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<int> v;
// 10 9 8 7 6 5 4 3 2 1 
for(int i = 1; i <= 10; i++)
    v.insert(v.begin(), i);
// *it = 10, *it2 = 9
auto it = v.begin();
auto it2 = std::next(it);
cout << (*it) << " " << (*it2) << endl;

v.insert(it2, 100);

for(int i: v)
    cout << i << " ";
cout << endl;
cout << (*it) << " " << (*it2) << endl;

输出

1
2
3
10 9
10 100 9 8 7 6 5 4 3 2 1 
10 100

可见插入点后的迭代器已经不再指向原来的元素了，这大概是因为 vector 是连续内存，插入时要把插入点及之后的元素后移一个内存单位，指向原先内存地址的迭代器就失效了。

关于 insert() 和 erase() 的返回值

inert() 的返回值是指向新插入元素的迭代器，erase() 的返回值是指向被删除元素下一个元素的迭代器，这两个函数返回值常用来在循环操作中更新迭代器的值，如果忘记用返回值更新迭代器，可能会产生不可预知的 bug。c++ primer 上有个有意思的例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 删除偶数元素，复制奇数元素
vector<int> v = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
auto it = v.begin();
while(it != v.end()) {
    if((*it) & 1) {
        it = v.insert(it, *it);
        // 迭代器前移2，跳过当前正在处理的元素和新插入的元素
        advance(it, 2);
    }
    else {
        it = v.erase(it);
    }
}
for(int i: v)
    cout << i << " ";
cout << endl << endl;

输出

1
1 1 3 3 5 5 7 7 9 9

如果将第 6 行 it = v.insert(it, *it) 写成 v.insert(it, *it)，在这个例子下也能输出正确结果，这是因为 vector 插入会使插入点后迭代器失效，歪打正着地指向了新插入的元素，产生了正确的效果，但这样写是错误的，如果把 vector 变成 list，就会产生有意思的 bug:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
list<int> l = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
auto it = l.begin();
while(it != l.end()) {
    if((*it) & 1) {
        l.insert(it, *it);
        advance(it, 2);
    }
    else {
        it = l.erase(it);
    }
}
for(int i: l)
    cout << i << " ";
cout << endl << endl;

输出

1
1 1 1 3 3 3 5 5 5 7 7 7 9 9 9

每个奇数元素都被复制了 2 次，这是因为 insert() 后没有更新迭代器，导致 advance(it, 2)跳过了下一个应该处理的元素，在执行到末尾的时候也跳过了 l.end()，而 list 是循环链表，迭代器回到了开头又迭代了一次。

注意在执行完it = v.erase(it)后不需要再递增迭代器了，否则会跳过下一个元素。