C / C++ / 系统课时

删除元素后哪些迭代器会失效

删除元素后哪些迭代器会失效

erase 之后继续使用旧迭代器,是 STL 中最隐蔽的未定义行为来源之一。不同容器的失效范围并不相同:vector 会搬移元素,deque 取决于删除位置,list 和关联容器通常只让被删元素失效。本节给出可直接用于代码审查的判断规则。

学习目标

  • 能比较 vector、deque、list 与关联容器执行 erase 后的迭代器失效范围
  • 会使用 erase 的返回值安全地继续遍历
  • 能识别“旧迭代器看起来还能用,但实际上已经失效”的代码

先看四类容器的规则

erase 的核心区别来自底层组织方式。连续存储容器删除元素后需要搬移后续对象;链式容器只断开节点;树和哈希表删除一个节点时通常也无需移动其他节点。

容器 删除一个元素后的主要规则 实战记忆
vector 被删位置及其后的迭代器、指针和引用都失效 删除点之后全部重取
deque 删除中间元素时全部迭代器和引用失效;从首尾删除时范围更小 中间删除按“全失效”处理
list 只有指向被删元素的迭代器和引用失效 其他节点保持有效
set、map 等有序关联容器 只有被删元素失效 其他元素保持有效
unordered_set、unordered_map 等无序关联容器 erase 本身只让被删元素失效 另行发生 rehash 时迭代器规则不同

erase 后迭代器失效范围对比

这张规则表适合做第一判断,但 deque 需要额外记住端点差异;同时,无论哪种容器,都不要再解引用指向已删除元素的迭代器。

vector 为什么从删除点开始失效

vector 的元素连续存储。删除中间元素后,后面的元素会向前移动来填补空洞,因此原先指向删除位置及其后的迭代器、指针和引用都不能继续使用。删除位置之前的迭代器仍然有效。

最安全的模式是接住 erase 的返回值。它指向被删除元素之后的新位置;如果删除的是最后一个元素,则返回新的 end()。

cpp
#include <iostream>
#include <vector>

int main() {
    std::vector<int> values{10, 20, 30, 40, 50};

    auto it = values.begin();
    while (it != values.end()) {
        if (*it % 20 == 0) {
            it = values.erase(it);
        } else {
            ++it;
        }
    }

    for (int value : values) {
        std::cout << value << ' ';
    }
    std::cout << '\n';
}

预期输出:

text
10 30 50 

如果写成 values.erase(it); ++it;,那么 it 在 erase 之后已经失效,再递增它属于未定义行为。即使程序在某次运行中“看起来正常”,也不能认为代码正确。

deque 要根据删除位置判断

deque 不是单块连续数组,删除规则也比 vector 更细。删除既不包含首元素也不包含尾元素的中间区间时,所有迭代器和引用都会失效;这是最需要警惕的情况。

如果只从首端删除,并且没有同时删到末元素,只有被删元素对应的迭代器和引用失效。若从尾端删除,除了被删元素外,旧的过去末尾迭代器也会失效。因此,涉及 deque 的修改代码不应长期缓存 end();完成删除后重新获取边界迭代器更稳妥。

list 与关联容器为什么更稳定

std::list 的每个元素位于独立节点中,删除一个节点不会移动其他节点,所以只有指向被删节点的迭代器和引用失效。std::set、std::map、std::multiset、std::multimap 也有类似性质:erase 只使被删除元素对应的迭代器和引用失效。

无序关联容器的 erase 同样只使被删元素失效。需要单独区分的是 rehash:当哈希桶重建时,迭代器会失效,但对未删除元素的引用和指针仍保持有效。不要把 erase 和 rehash 的规则混为一谈。

下面的示例展示 list 中保留下来的迭代器仍可继续使用:

cpp
#include <iostream>
#include <iterator>
#include <list>

int main() {
    std::list<int> values{10, 20, 30, 40};

    auto keep = std::next(values.begin());
    auto erased = std::next(values.begin(), 2);

    values.erase(erased);

    std::cout << *keep << '\n';
}

预期输出:

text
20

这里 keep 指向的节点没有被删除,因此仍然有效;erased 指向的节点已经销毁,之后绝不能再解引用或递增它。

写删除循环时按返回值推进

容器提供 erase 返回值,就是为了让“边遍历边删除”能安全继续。对支持 erase(iterator) 的常见顺序容器和关联容器,优先写成 it = c.erase(it),而不是先保存旧迭代器再猜测下一位置是否仍有效。

代码审查时可以按一个简单顺序判断:先看容器类型,再看删除位置,最后检查删除之后是否还使用了旧迭代器、旧引用、旧指针或缓存的 end()。只要其中一个对象落在失效范围内,就应该改为重新获取或使用 erase 的返回值。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

删除元素后哪些迭代器会失效

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通