【STL】迭代器失效问题

  |  

摘要: 本文介绍在 C++ STL 中各容器的迭代器失效问题

【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的github:FennelDumplings
我的leetcode:FennelDumplings


本文介绍 STL 中的容器迭代器失效问题。首先列举容器的种类,然后盘点一下涉及到删除的操作,最后讨论迭代器失效的情况。

$1 容器种类

  • 标准 STL 序列容器: vector, string, deque, list
  • 标准 STL 关联容器: set, multiset, map, multimap
  • 标准 STL 无序关联容器: unordered_set, unordered_multiset, unordered_map, unordered_multimap
  • 标准非 STL 容器: 数组, bitset, valarray, stack, queue, priority_queue
  • 非标准序列容器: slist, rope

$2 删除操作

1. std::unique

unique 算法有两个:std::unique, std::unique_copy

std::unique 在迭代器上工作,但是它不知道迭代器所指的容器类型(与其它 STL 算法一样),这意味着它无法改变容器结构,只能改变容器的值。因此它不是从输入序列中删除重复,而是把不重复的元素移动到序列的前部,返回指向这一段无重复子序列末端的迭代器。

2. std::remove

remove 算法有四个:std::remove, std::remove_if, std::remove_copy, std::remove_copy_if

它们都是将不匹配的元素压缩到序列前面,返回指向这个压缩后的序列末端的迭代器。

3. erase

如果想删除元素,在使用 std::remove 算法之后,还要加上 erase。因为要删除元素,最终需要调用成员函数去删除,但是 std::remove 不知道它作用在哪个容器(类似地 sed::unique 也一样)

1
2
3
sort(v.begin(), v.end());
auto it = unique(v.begin(), v.end());
v.erase(it, v.end());
1
2
auto it = std::remove(v.begin(), v.end(), val);
v.erase(it, v.end());

4. std::list::remove

list 容器比较特殊,它提供了一些特别适用于对链表处理的操作:splice, merge, sort, reverse, 以及这里关心的 remove, remove_if, unique

list 的 removeunique 是真正删除元素的,而且比正常的 std::removestd::unique 之后跟着 erase 的方式高效。

$3 迭代器失效的情况

1. 仅被删除元素的迭代器失效

1
2
3
4
5
6
7
8
9
list
set
multiset
map
multimap
unordered_set
unordered_multiset
unordered_map
unordered_multimap

插入任何元素都不会使迭代器失效。删除元素时,除了指向当前被删除元素的迭代器外,其它迭代器都不会失效。

在遍历时用 erase 删除元素的正确写法, 其中 v 是上面列出的容器的任意一种:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
auto iter = v.begin();
while(iter != v.end())
{
if(...)
{
...
iter = v.erase(iter);
...
}
else
{
...
++iter;
}
}

错误写法:

1
2
3
4
5
6
7
8
9
10
11
12
auto iter = v.begin();
while(iter != v.end())
{
if(...)
{
...
v.erase(iter);
...
}
...
++iter;
}

迭代器可以存放在数据结构中,只需要注意被调用 erase 的迭代器需要从数据结构中删掉即可。

2. vector

  • push_back 一个元素后 end() 肯定失效
  • push_back 一个元素后,如果发生扩容,即 capacity 的返回值与插入之前不一样(事实上只会变大不会变小),此时需要重新加载整个容器,[begin(), end()] 范围内的迭代器全部会失效。
    (vector 只会自动扩容,不会自动释放,其空间在 vector 析构时才会被系统回收)
  • erase, pop_back 删除元素后,指向被删元素,以及被删元素后面的元素的迭代器全部失效。

3. deque

  • 在首部尾部插入 push_front, push_back: 不会使得任何迭代器失效
  • 在首部尾部删除元素 pop_front, pop_back: 只会使得指向被删元素的迭代器失效
  • 在除了首部尾部的其它位置插入和删除 erase, insert:指向 deque 的所有迭代器都会失效

vector 和 deque 的迭代器失效情况很复杂,防不胜防。不能把这两个容器的迭代器当指针存放在数据结构中(例如 unordered_map 中),否则自寻烦恼。


Share