编程C++

【STL】迭代器失效问题

字数统计: 988字   |   阅读时长: 3分
,

摘要: 本文介绍在 C++ STL 中的 bitset

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的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 的 remove 和 unique 是真正删除元素的，而且比正常的 std::remove 或 std::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