一、迭代器失效
向容器添加或者删除元素可能会导致指向容器的指针、引用或者迭代器失效。使用已经失效的指针、引用或者迭代器将会导致程序出现异常，编码过程中一定要时刻注意迭代器失效的场景。
例如，以vector为例：
|
1 2 3 4 5 6 7 8 9 10 |
int main() { vector<int> v{1, 2}; vector<int>::iterator it; for (it = v.begin(); it != v.end(); it++) { v.push_back(*it); } return 0; } |
执行以上代码会导致段错误：
原因：在循环中新增了元素，并且重新分配了内存空间，导致迭代器失效。使用已经失效的迭代器会导致程序出现段错误。
迭代器失效，主要有两个层面的意思：
- 无法通过迭代器++或--操作遍历整个stl容器，记作第一层失效。
- 无法通过迭代器存取迭代器所指向的内存，记作第二层失效。
二、失效场景
vector和string
如果增加或删除元素导致内存空间重新分配了，那么指向容器的迭代器都会失效（第二层失效）。如果存储空间未重新分配，指向删除元素之前的所有迭代器还有效（第一层失效），但是删除元素之后的所有迭代器都无效了（第二层失效）。
deque
插入到除首尾元素之外任何位置都会导致迭代器失效（第二层失效）。如果插入到首尾元素，迭代器会失效，但是指向已存在元素的指针和引用不失效（第一层失效）。
删除除首尾元素之外的元素，所有迭代器失效（第二层失效）。如果删除的是首尾元素，首前和尾后迭代器失效，其他元素的引用、指针和迭代器不会失效。
map和set
删除和添加元素会导致内部结构调整，迭代器失效，但是引用和指针任然有效（第一层失效）。
list
添加元素不会导致迭代器失效，但是删除元素会导致删除元素后面的所有迭代器失效（第一层失效）。list删除元素永远都会导致尾后迭代器失效（第二层失效）。
三、避免迭代器失效
避免迭代器失效的几种方法：
- 减小迭代器的使用范围，不保存迭代器的值。
- 避免在遍历迭代器的过程中修改容器。
- 不要保存首前和尾后指针。
vector避免删除失效
在遍历vector的过程中删除元素，会导致后面的迭代器失效。如果希望删除后还能继续使用迭代器，要使用erase方法，并接收返回值作为下一个迭代器使用。
正确的使用方式：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
int main() { vector<int> v{1, 2, 3, 4, 5}; vector<int>::iterator it; for (it = v.begin(); it != v.end();) { if (*it == 2 || *it == 4) { // 接收返回值作为下一个迭代器 it = v.erase(it); continue; } cout << *it << endl; it++; } } |
set/map避免迭代器失效
set和map也和vector一样：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
int main() { set<int> s{1, 2, 3, 4, 5}; set<int>::iterator it; for (it = s.begin(); it != s.end();) { if (*it == 2 || *it == 4) { it = s.erase(it); continue; } cout << *it << endl; it++; } return 0; } |
评论