星期一, 24 8 月, 2026
Latest:
i007.cc

i007.cc

优先队列-降维打击

05.价值资料

STL 容器迭代器失效规则

Will

核心记忆：容器底层数据结构决定迭代器 / 引用 / 指针是否失效。迭代器本质是指向容器内部元素的 “指针”；元素内存被移动、删除、重新分配，迭代器就失效。

注意：erase(it) 返回下一个有效迭代器，被 erase 的那个it直接失效，其余要看容器。

一、各个容器迭代器失效总表

表格
容器 底层结构 操作 迭代器失效情况
vector 连续数组 erase/pop_back 删除元素位置之后全部迭代器失效；前面保持有效。删除头部，中间、尾部迭代器全部失效。
deque 分段连续数组 erase 被删元素的迭代器失效；头尾之外中间 erase，全部迭代器失效；两端 pop 仅失效被删位置
list / std::forward_list 双向 / 单向链表 erase 仅被 erase 的那个迭代器失效，其余全部完好。删头部，中间、尾部迭代器完全可用
std::map/std::set(红黑树) 平衡 BST erase 只有被删除节点迭代器失效，其他迭代器、引用保持有效。删头部节点，中间、尾部迭代器不会失效
std::unordered_map/unordered_set 哈希表 erase 仅被 erase 迭代器失效；rehash 时全部迭代器失效（insert 触发扩容 rehash）
回答你的直接问题：
  1. 删除头部节点，会不会导致中间迭代器失效？
  • vector：✅会！删 begin ()，全部中间、末尾迭代器全部失效，因为元素整体向前搬移
  • map/set/list：❌不会，其他迭代器依旧有效，仅被删掉的那个 it 失效

1. std::vector（连续内存，最容易踩坑）

底层一块连续堆数组。erase 某个元素，后面所有元素内存拷贝向前移动覆盖被删位置。
cpp
运行
std::vector<int> v{10,20,30,40,50};
auto it_mid = v.begin()+2; // 指向30
v.erase(v.begin());        // 删除头部10
// ⚠ it_mid 已经失效！元素全部前移，内存发生移动，it_mid变成野迭代器

 

  • v.erase(pos)：pos 以及 pos 之后所有迭代器、指针、引用全部失效；pos 之前的迭代器有效。
  • pop_back()：仅尾后迭代器end()失效，其他迭代器有效。
  • push_back：如果触发 capacity 扩容（reallocate），全部迭代器全部失效。
vector 删除头部代价很高：O (n) 拷贝，同时毁掉全部后面迭代器，尽量避免。

2. std::map /std::set（红黑树，节点独立堆内存）

每个节点独立分配堆内存，erase 只是把树中某个节点释放；其余节点内存地址不变。
cpp
运行
std::map<int,int> m{{1,1},{2,2},{3,3},{4,4}};
auto it_mid = m.find(3);
auto it_head = m.begin();
m.erase(it_head); // 删除头部key=1节点
// ✅ it_mid 依然有效，可以正常解引用，没有失效

 

规则：
  • erase(it)：仅被传入的 it 迭代器失效，其他所有迭代器、引用、指针完全有效。
  • erase 一个 range erase(begin,end)：
[begin,end) 区间内全部迭代器失效，区间外保持有效。
这点非常重要，上一段 TTL 缓存代码用std::map<Tp, set<>>，it=m_ttl_map.erase(it)返回下一个有效迭代器，这是安全的，就是利用 map 这个特性。
⚠️注意：erase(value)按 key 删除，不是迭代器；同样仅匹配到的节点迭代器失效。

3. std::list 双向链表

每个节点独立堆内存，删除头部节点，仅仅修改前后指针，其余节点地址不变。
cpp
运行
std::list<int> l{1,2,3,4};
auto mid = std::next(l.begin(),2);
l.erase(l.begin());
// mid依然有效，可以正常*mid

 

  • erase 某个迭代器，只有该迭代器失效，其余全部有效。

4. unordered_map /unordered_set（哈希表）

  1. erase(it)：仅被 erase 的 it 失效；其余迭代器有效。
  2. insert 如果触发rehash（哈希表扩容）：全部迭代器、指针、引用直接失效。
rehash 会把全部节点搬迁到新的 bucket 数组。这是 unordered 最常见坑。

5. deque

分段内存块。
  • 在中间位置 erase：全部迭代器失效
  • 只在两端 pop_front/pop_back：只失效被删元素迭代器。

高频易错场景

场景 1：vector 错误循环 erase

cpp
运行
// ❌错误写法
for(auto it = v.begin(); it != v.end(); ++it){
    if(*it > 10){
        v.erase(it);   // erase之后it直接失效，++it是UB崩溃
    }
}

// ✅正确，利用erase返回下一个迭代器
for(auto it = v.begin(); it != v.end(); ){
    if(*it>10){
        it = v.erase(it);
    }else{
        ++it;
    }
}

 

map/list/unordered_map 同样用 it = c.erase(it)，写法通用。

场景 2：保存迭代器，解锁后继续使用（就是你上一段 TTL 缓存原始代码的坑）

cpp
运行
// map示例
std::shared_lock rlock(mtx);
auto it = m_ttl_map.begin();
rlock.unlock();   //释放锁
// 其他线程执行 m_ttl_map.erase(it);
// 重新拿锁，继续使用it；此时it可能已经被删除，野迭代器UB

 

迭代器有效性 ≠线程安全！即使容器本身不会让 it 失效，别的线程 erase 该节点，it 依然会变成野迭代器。

👉只要释放锁，就不要再复用之前保存的迭代器，必须重新 find。

场景 3：保存引用

cpp
运行
auto& ref = it->second;
c.erase(it);
// ref变成悬空引用UB

 

简短总结回答你的问题

Q：删除头部节点，会导致中间位置迭代器失效么？
  1. vector：会！删除头部，后面所有迭代器全部失效，包括中间、尾部。
  2. map /set/list：不会！删除头部节点，只有被删的那个迭代器失效，中间、尾部迭代器继续有效。
记住两个区分口诀：
  1. 连续内存容器 (vector/deque)：erase 会移动元素，一大批迭代器跟着失效；
  2. 节点式容器 (map/set/list)：erase 仅干掉被删节点本身，其他迭代器保持有效。
如果你需要，我可以举一段最小复现代码演示 vector 删头部迭代器 UB。

std::list 迭代器能不能判断是否失效？

STL 标准没有提供任何接口，可以直接判断一个迭代器是否失效。没有 is_valid()、is_invalid() 这类成员函数。
不光是 list，vector/map/unordered_map 全部都没有。迭代器失效属于 程序逻辑问题，不是运行时可查询状态。

失效之后解引用，属于 未定义行为 UB，程序可能崩溃、可能正常跑、可能乱输出，没有任何保证。

std::list 的迭代器什么时候会失效

std::list 是双向链表：
  1. erase(it)：仅被 erase 的那个迭代器失效，其余迭代器全部保持有效。
  2. pop_front / pop_back：被删除元素对应的迭代器失效，其他迭代器有效。
  3. insert：所有迭代器保持有效。
  4. splice 拼接：被移动元素的迭代器依然有效（指向新容器里的节点）。
list 迭代器失效场景很少，但依然会失效！

例如：

cpp
运行
std::list<int> l{1,2,3};
auto it = l.begin();
l.erase(it); // it现在失效
// *it; // UB，崩溃/随机值

为什么标准不提供 it.is_valid()？

list 迭代器内部本质是一个裸指针，指向链表节点 Node*。

失效之后，这个指针是野指针（dangling pointer），指向已经被 delete 释放的堆内存。

野指针本身的值不是 nullptr，只是指向一块已经归还内存管理器的内存；你无法通过指针本身区分：是合法节点，还是已经释放的野内存。
cpp
运行
// list迭代器伪实现
template<class T>
struct __list_iterator {
    __list_node<T>* _M_node; // 内部就是节点指针
};

 

节点被 erase 之后 delete _M_node，迭代器里面存的还是原来的地址，但那块内存已经释放。指针不为空，但已经无效。无法靠指针值判断有效性。

那有什么手段间接做校验？（仅调试，禁止生产使用）

方法 1：对比是否等于容器的迭代器（只能检测一部分场景）

只能判断迭代器是否属于这个 list，但不能判断节点是否已经被 erase 删除。
cpp
运行
std::list<int> lst{10,20,30};
auto it = lst.begin();
lst.erase(it);

// ❌下面这种判断毫无用处
if(it != lst.end()){
    // it已经失效，但it != end() 可能依然成立，UB
}

 

节点已经 delete，it 是野指针，拿野迭代器和容器迭代器做比较本身就是 UB。

方法 2：调试器（gdb/lldb）

调试阶段，看迭代器内部的 _M_node 指针：
  • 如果指向已经 free 的内存，调试工具可以识别；

    只能开发调试，运行时代码不能用。

方法 3：自己包装，带标记（生产可用，有开销）

如果你需要运行时检测迭代器是否有效，可以自己封装链表节点，增加一个存活标记：
cpp
运行
struct Node {
    int val;
    bool alive = true;
    Node* prev, *next;
};
// erase时设置 alive=false;

 

迭代器保存 Node*，访问前先检查 node->alive。
代价：自己手写链表，放弃 std::list。STL 本身不支持。

✅正确工程做法：不要保存迭代器

核心准则：
  1. 迭代器只在锁保护、容器不被修改的作用域内短期使用。
  2. 不要把迭代器保存下来跨函数、跨锁释放、跨异步回调使用。
  3. 如果需要再次访问，重新调用 find() 获取新迭代器，而不是复用旧迭代器。
回到你之前的 TTL 缓存代码：

原代码的错误本质就是：unlock 释放锁之后继续保留 map 迭代器 it。

即使 std::map erase 只会失效被删迭代器；但别的线程可以 erase 这个节点，it 变成野迭代器。没有办法判断 it 是否还活着，只能释放锁之后丢弃 it，下次重新 find。

补充对比各个容器

表格
容器 迭代器内部 能否运行时判断失效
std::list 节点指针 ❌不能，野指针不为 nullptr
std::map 红黑树节点指针 ❌不能
std::vector 连续内存指针 ❌不能；失效后指针仍然是地址
unordered_map 哈希桶节点指针 ❌不能，rehash 全部失效，无法检测

简短总结

  1. STL 没有 API 可以判断迭代器是否失效。没有 is_valid ()。
  2. list 迭代器内部是节点指针；节点被 delete 之后迭代器变成野指针，指针本身非空，无法识别。
  3. 不要长期存储迭代器；跨锁、跨异步一定要丢弃，需要就重新 find。
  4. 失效迭代器解引用是 UB，行为不可预测。
扩展一个小坑：很多人误以为 list 迭代器几乎不会失效，就可以存起来长期使用。多线程环境下绝对不行，别的线程 erase 该节点之后迭代器直接野掉，无法检测。

发表回复