罗罗编程学习记录
本页内容 展开查看

04.9.2 STL 容器与迭代器失效

所属:全栈开发面试题库 / 04 后端语言与运行时 / 04.9 C 与 C++

覆盖范围

  • sequence 容器:vector、list、deque 的底层与时间复杂度
  • associative 容器:map、set、multimap、multiset 的红黑树实现
  • unordered 容器:unordered_map、unordered_set 的哈希表实现
  • 迭代器失效规则:哪些操作会使哪些迭代器失效
  • 容器选型:时间复杂度、空间开销、cache 友好度

高频题速览

编号 题目 难度 频率
04.9.2-001 vector 的底层实现 基础 ★★★★★
04.9.2-002 vector 扩容时迭代器为什么失效 进阶 ★★★★★
04.9.2-003 list 和 vector 怎么选 基础 ★★★★★
04.9.2-004 map 底层为什么用红黑树 进阶 ★★★★☆
04.9.2-005 map vs unordered_map 选型 进阶 ★★★★★
04.9.2-006 deque 的底层实现 进阶 ★★★★☆
04.9.2-007 迭代器失效的完整规则 高级 ★★★★★
04.9.2-008 erase 时正确删除元素的写法 进阶 ★★★★★

04.9.2-001 vector 的底层实现是什么?为什么用连续数组?

频率 ★★★★★ | 难度 基础

一句话结论

vector 底层是动态分配的连续数组,支持随机访问 O(1),尾部插入摊销 O(1),扩容时按 capacity 倍增(通常 1.5 或 2 倍)重新分配并拷贝/移动全部元素。

概念解释

  • vector 内部维护三个指针:start、finish(当前大小 end)、end_of_storage(容量 end)。
  • size() = finish - start,capacity() = end_of_storage - start。
  • 连续数组意味着 cache 友好,遍历速度极快。
  • 扩容时重新申请一块更大的内存,把旧元素拷贝/移动过去,再释放旧内存。

原理流程

  1. push_back 时先检查 size < capacity,如果是直接在 finish 位置构造元素。
  2. 如果 size == capacity,按当前 capacity 的倍数(GCC 通常 2 倍,MSVC 通常 1.5 倍)申请新内存。
  3. 把旧数组的所有元素移动(或拷贝)到新数组,释放旧数组。
  4. 扩容是 O(n) 操作,但因为是摊销到多次 push_back,所以单次 push_back 摊销 O(1)。

代码 / 示例

#include <vector>

int main() {
    std::vector<int> v;
    v.reserve(100); // 预分配 100 个空间,避免多次扩容
    for (int i = 0; i < 100; i++) {
        v.push_back(i); // 不触发扩容
    }
    // size() = 100, capacity() = 100

    v.push_back(100); // 触发扩容,capacity 变成 150 或 200
    return 0;
}

常见误区

  • 误区:vector 扩容是每次加一个元素的大小?正解:按倍数扩容,1.5 或 2 倍,这样摊销复杂度才是 O(1)。
  • 误区:vector 中间插入很快?正解:中间插入需要移动后面所有元素,O(n),不推荐频繁中间插入。

追问 / 延伸

  • 为什么 vector 的 size 和 capacity 不一样?答:capacity 是已分配的总空间,size 是实际用了多少,多余的空间是为了下次 push_back 不用立刻扩容。
  • shrink_to_fit 是什么?答:请求把 capacity 缩小到和 size 一样,释放多余内存。

04.9.2-002 vector 扩容时为什么迭代器会失效?

频率 ★★★★★ | 难度 进阶

一句话结论

vector 扩容时会重新分配一块新的连续内存,把旧元素移动过去,然后释放旧内存——所有指向旧内存的迭代器、指针、引用全部失效,因为它们指向的内存已经还给操作系统了。

概念解释

  • vector 的迭代器本质上就是 T* 指针。
  • 扩容 = 新分配一块更大的数组 + 把旧元素搬过去 + 释放旧数组。
  • 旧数组的地址变了,所有指向旧数组的指针自然都失效了。

原理流程

  1. 迭代器 it = v.begin() 指向旧数组的第一个元素。
  2. push_back 触发扩容,v 内部数组搬到了新地址。
  3. 原来的 it 还指向旧地址,那块内存已经被释放。
  4. 继续解引用 it 就是访问已释放内存,未定义行为。

代码 / 示例

std::vector<int> v = {1, 2, 3};
auto it = v.begin();
v.push_back(4); // 如果 capacity == 3,触发扩容

// it 现在是悬空的!
// *it = 10; // 未定义行为

// 正确做法:扩容后重新获取迭代器
v.push_back(4);
it = v.begin(); // 重新获取

常见误区

  • 误区:vector 扩容后迭代器只是"可能"失效?正解:只要触发了扩容(重新分配),所有迭代器全部失效,没有例外。
  • 误区:reserve 之后就永远不会失效?正解:reserve 只是让 capacity 变大,只要不超过 capacity 就不会扩容;一旦超过,还是会全部失效。

追问 / 延伸

  • 除了扩容,还有什么操作会让 vector 的迭代器失效?答:insert/erase 中间位置会让插入点/删除点之后的迭代器全部失效(因为元素移动了);push_back 不触发扩容时只有尾后迭代器 end() 会失效。
  • list 的迭代器会失效吗?答:list 是链表,erase 某个元素时只有被删的那个迭代器失效,其他迭代器不受影响。

04.9.2-003 list 和 vector 怎么选?

频率 ★★★★★ | 难度 基础

一句话结论

绝大多数场景选 vector:连续内存 cache 友好、随机访问 O(1)、内存开销小;list 只在需要频繁在中间插入/删除且不关心遍历性能时才考虑,实际开发中很少用。

概念解释

  • vector:连续数组,随机访问 O(1),尾部插入摊销 O(1),中间插入 O(n)。
  • list:双向链表,随机访问 O(n),已知节点位置插入/删除 O(1)。
  • vector 的内存开销:每个元素就是一个 T,没有额外指针。
  • list 的内存开销:每个节点除了存 T,还要存 prev 和 next 两个指针(64 位下多 16 字节)。

原理流程

  1. 遍历场景:vector 连续内存,cache line 一次加载多个元素,速度极快;list 每个节点在堆上随机分布,cache miss 严重。
  2. 中间插入:vector 需要移动后面所有元素 O(n);list 已知节点位置时只改指针 O(1)。
  3. 但 list 要"知道节点位置"本身就需要遍历找到它,定位成本 O(n)。
  4. 综合下来,只有当插入/删除的位置已经通过其他方式拿到(比如遍历过程中记住了节点指针),list 才有优势。

代码 / 示例

#include <vector>
#include <list>
#include <chrono>

int main() {
    // 遍历性能对比:vector 远快于 list
    std::vector<int> v(1000000);
    std::list<int> l(1000000);

    auto t1 = std::chrono::steady_clock::now();
    long long sum1 = 0;
    for (int x : v) sum1 += x; // vector 遍历快很多
    auto t2 = std::chrono::steady_clock::now();

    long long sum2 = 0;
    for (int x : l) sum2 += x; // list 遍历慢很多
    auto t3 = std::chrono::steady_clock::now();

    return 0;
}

常见误区

  • 误区:list 插入删除总是 O(1)?正解:O(1) 的前提是已经知道节点位置;找到节点本身就是 O(n)。
  • 误区:vector 比 list 慢因为 vector 要扩容?正解:reserve 预分配后 vector 插入尾部很快,且遍历性能远好于 list。

追问 / 延伸

  • deque 是什么?答:分段连续数组,头尾插入都是 O(1),但中间操作慢,cache 不友好。
  • 什么场景用 list?答:需要频繁在已知节点位置插入删除,且很少遍历,比如 LRU 缓存的链表部分。

04.9.2-004 map 底层为什么用红黑树?

频率 ★★★★☆ | 难度 进阶

一句话结论

map 需要保持 key 有序,红黑树是一种平衡二叉搜索树,插入/删除/查找都是 O(log n),且通过颜色约束保证树不会退化成链表,平衡成本比 AVL 低。

概念解释

  • 红黑树性质:节点是红或黑;根是黑;叶子(NIL)是黑;红节点的子节点是黑;任意节点到叶子的所有路径包含相同数量的黑节点。
  • 这些性质保证了从根到最远叶子的路径不超过最短路径的两倍,树高 O(log n)。
  • AVL 树是严格平衡,每次插入删除可能需要多次旋转;红黑树是近似平衡,旋转次数更少。

原理流程

  1. map 插入时按 key 大小搜索插入位置,像二叉搜索树一样插入。
  2. 插入后检查是否违反红黑树性质,如果违反就做旋转和变色修复。
  3. 查找时从根开始,比当前节点小走左子树,大走右子树,O(log n)。
  4. 遍历 map 得到的是 key 有序的序列(中序遍历)。

代码 / 示例

#include <map>
#include <iostream>

int main() {
    std::map<int, const char*> m;
    m[3] = "three";
    m[1] = "one";
    m[2] = "two";

    // 遍历是按 key 从小到大:1, 2, 3
    for (auto& [k, v] : m) {
        std::cout << k << " => " << v << std::endl;
    }

    auto it = m.find(2); // O(log n)
    if (it != m.end()) {
        std::cout << it->second << std::endl; // "two"
    }
    return 0;
}

常见误区

  • 误区:map 查找是 O(1)?正解:map 是红黑树,查找 O(log n);unordered_map 才是哈希表,平均 O(1)。
  • 误区:红黑树和 AVL 一样严格平衡?正解:红黑树是近似平衡,高度可能比 AVL 高一点,但插入删除旋转更少,综合性能更好。

追问 / 延伸

  • 为什么 map 插入时迭代器不会失效?答:红黑树是节点在堆上独立分配的,插入新节点不会移动已有节点,所以所有已有迭代器都有效。
  • multimap 和 map 的区别?答:multimap 允许 key 重复,operator[] 被删除,因为有多个值不确定取哪个。

04.9.2-005 map 和 unordered_map 怎么选?

频率 ★★★★★ | 难度 进阶

一句话结论

需要 key 有序或需要范围查询(lower_bound/upper_bound)时用 map;只需要按键查找、不关心顺序时用 unordered_map,平均 O(1) 查找更快,但最坏 O(n) 且有哈希碰撞。

概念解释

  • map:红黑树,O(log n) 查找,key 有序,内存开销大(每个节点有左右指针和颜色)。
  • unordered_map:哈希表(桶数组 + 链表/红黑树解决冲突),平均 O(1) 查找,key 无序,内存开销小但有负载因子和 rehash 开销。

原理流程

  1. unordered_map 内部维护一个桶数组,每个 key 通过哈希函数算出桶编号。
  2. 同一个桶里的元素用链表(或长到一定程度后转红黑树)串起来。
  3. 查找时先算哈希找到桶,再在桶里逐个比较。
  4. 当元素数量超过桶数 * 负载因子时,触发 rehash:桶数翻倍,所有元素重新分配到新桶。

代码 / 示例

#include <unordered_map>
#include <map>

// 场景一:需要按 key 顺序遍历
std::map<int, std::string> ordered;
for (auto& [k, v] : ordered) {
    // k 是从小到大的
}

// 场景二:只需要按键查找
std::unordered_map<int, std::string> hash_map;
hash_map[1] = "one";
auto it = hash_map.find(1); // 平均 O(1)

// 注意:unordered_map 的 key 需要哈希函数
// 自定义类型作为 key 需要写 std::hash 特化
struct Point { int x; int y; };
struct PointHash {
    size_t operator()(const Point& p) const {
        return std::hash<int>()(p.x) ^ (std::hash<int>()(p.y) << 1);
    }
};
std::unordered_map<Point, std::string, PointHash> point_map;

常见误区

  • 误区:unordered_map 一定比 map 快?正解:小数据量下 map 可能更快,因为红黑树常数小、没有哈希计算开销;大数据量且查找密集时 unordered_map 优势明显。
  • 误区:unordered_map 遍历时顺序稳定?正解:顺序由哈希值和桶数决定,rehash 后顺序会变,不能依赖。

追问 / 延伸

  • 什么是哈希碰撞?答:两个不同的 key 算出同一个桶编号,需要用链表或红黑树在桶里区分。
  • unordered_map 的 load_factor 是什么?答:平均每个桶里的元素个数,默认 1.0,超过就 rehash。

04.9.2-006 deque 的底层实现是什么?和 vector/list 有什么区别?

频率 ★★★★☆ | 难度 进阶

一句话结论

deque(double-ended queue)底层是一段段连续的小块内存(通过 map 数组串联),头尾插入删除都是 O(1),支持随机访问,但随机访问需要两次跳转(先找块,再找块内位置),cache 不友好。

概念解释

  • deque 不是完全连续的,而是由多个固定大小的连续块组成。
  • 内部有一个 map(不是 std::map),是一个指针数组,每个元素指向一块连续内存。
  • 头尾插入时:如果当前块还有空间,直接在块里放;如果满了,在 map 前面/后面再加一块。
  • 随机访问:先算在第几个块,再算块内偏移,O(1) 但常数比 vector 大。

原理流程

  1. deque 中间是一个中控数组(map),数组里每个元素指向一块连续内存块。
  2. 头部插入:如果头部块还有空位,直接放;否则在中控数组前面加一个新块。
  3. 尾部插入:同理,尾部块有空间就直接放,没有就加新块。
  4. 中间插入/删除:需要移动元素,成本 O(n),比 vector 还慢。

代码 / 示例

#include <deque>

int main() {
    std::deque<int> dq;
    dq.push_back(1);   // 尾部
    dq.push_front(0);  // 头部,O(1)
    dq.push_back(2);

    // dq = [0, 1, 2]
    std::cout << dq[1] << std::endl; // 1,随机访问 O(1) 但常数大

    dq.pop_front(); // O(1)
    dq.pop_back();  // O(1)
    return 0;
}

常见误区

  • 误区:deque 是连续的?正解:deque 是分段连续的,不是整块连续,所以 cache 不友好。
  • 误区:deque 中间插入快?正解:中间插入需要移动元素,O(n),比 vector 还慢,因为块结构更复杂。

追问 / 延伸

  • STL 中 queue 和 stack 默认用什么实现?答:默认是 deque,因为头尾操作都 O(1)。
  • 什么时候用 deque?答:需要频繁在头尾插入删除,且不怎么中间操作,也不怎么遍历的时候。

04.9.2-007 迭代器失效的完整规则是什么?

频率 ★★★★★ | 难度 高级

一句话结论

不同容器的迭代器失效规则不同:vector 扩容时全部失效,插入/删除中间位置时该位置之后全部失效;list 只有被删的元素迭代器失效;map/set 只有被删的元素迭代器失效;deque 头尾操作可能让全部迭代器失效。

概念解释

  • vector:
    • push_back 不触发扩容:只有 end() 失效。
    • push_back 触发扩容:所有迭代器、指针、引用全部失效。
    • insert/erase 中间位置:插入/删除点之后的所有迭代器失效。
  • list:
    • erase 某个元素:只有被删元素的迭代器失效,其他都有效。
    • insert:所有迭代器都有效。
  • map/set/multimap/multiset:
    • erase 某个元素:只有被删元素的迭代器失效,其他都有效。
    • insert:所有迭代器都有效。
  • deque:
    • 头尾插入/删除:所有迭代器可能失效,但指针和引用不一定。
    • 中间插入/删除:所有迭代器失效。

原理流程

  1. 迭代器失效的本质是:容器底层结构变了,迭代器指向的内存要么被释放了,要么元素位置移动了。
  2. vector 是连续数组,插入/删除中间元素会移动后面所有元素,所以后面的迭代器都失效。
  3. list/map 是节点式结构,每个节点在堆上独立分配,删除一个节点不会移动其他节点,所以其他节点的迭代器不受影响。

代码 / 示例

// vector erase 正确写法
std::vector<int> v = {1, 2, 3, 4, 5};
for (auto it = v.begin(); it != v.end(); ) {
    if (*it % 2 == 0) {
        it = v.erase(it); // erase 返回下一个有效迭代器
    } else {
        ++it;
    }
}

// list erase 正确写法
std::list<int> l = {1, 2, 3, 4, 5};
for (auto it = l.begin(); it != l.end(); ) {
    if (*it % 2 == 0) {
        it = l.erase(it); // list 的 erase 也返回下一个迭代器
    } else {
        ++it;
    }
}

// map erase 正确写法
std::map<int, int> m = {{1,1}, {2,2}, {3,3}};
for (auto it = m.begin(); it != m.end(); ) {
    if (it->first % 2 == 0) {
        it = m.erase(it); // C++11 起 erase 返回下一个迭代器
    } else {
        ++it;
    }
}

常见误区

  • 误区:erase 之后迭代器自动变成下一个?正解:C++11 之前 STL 容器的 erase 返回 void,需要自己写 it = container.erase(it);C++11 起所有容器的 erase 都返回下一个迭代器。
  • 误区:只要不扩容 vector 的迭代器就不会失效?正解:中间 insert/erase 也会让后面的迭代器失效,因为元素移动了。

追问 / 延伸

  • 为什么 vector 的 erase 要返回下一个迭代器?答:因为 erase 之后当前位置已经被删了,而且后面的元素都往前移了,原来的 it 已经指向了下一个元素,直接返回 it 就可以继续遍历。
  • 怎么记住这些规则?答:看底层结构——连续数组的插入删除会移动元素,所以后面的迭代器失效;节点式的插入删除不移动其他节点,所以其他迭代器有效。

04.9.2-008 遍历容器并删除元素的正确写法是什么?

频率 ★★★★★ | 难度 进阶

一句话结论

遍历时删除元素必须用 it = container.erase(it) 的写法,不能在 erase 之后直接 ++it,因为 erase 已经让当前迭代器失效了;C++20 有 erase_if 算法更简洁。

概念解释

  • 错误写法:for(it = begin; it != end; ++it) { if(cond) erase(it); } — erase 之后 it 已经失效,再 ++it 是未定义行为。
  • 正确写法:erase 会返回被删元素的下一个有效迭代器,直接用这个返回值继续循环。
  • C++20 提供了 erase_if(container, pred) 算法,一行搞定。

原理流程

  1. 进入循环,it 指向某个元素。
  2. 如果满足删除条件,调用 erase(it),it 指向的元素被删除。
  3. erase 返回下一个元素的迭代器,把它赋给 it。
  4. 如果不满足条件,才 ++it 走到下一个元素。

代码 / 示例

#include <vector>
#include <list>
#include <map>

int main() {
    // vector 正确写法
    std::vector<int> v = {1, 2, 3, 4, 5, 6};
    for (auto it = v.begin(); it != v.end(); ) {
        if (*it % 2 == 0) {
            it = v.erase(it); // erase 返回下一个迭代器
        } else {
            ++it;
        }
    }
    // v = {1, 3, 5}

    // C++20 更简洁
    std::erase_if(v, [](int x) { return x % 2 == 0; });

    // map 正确写法
    std::map<int, int> m = {{1,1}, {2,2}, {3,3}, {4,4}};
    for (auto it = m.begin(); it != m.end(); ) {
        if (it->first % 2 == 0) {
            it = m.erase(it);
        } else {
            ++it;
        }
    }
    // m = {{1,1}, {3,3}}

    return 0;
}

常见误区

  • 误区:erase 之后 it 自动指向下一个?正解:C++11 之前不是,C++11 起是;但为了可移植性,永远写 it = erase(it)。
  • 误区:用 range-based for 可以边遍历边删除?正解:不行,range-based for 底层用迭代器,删除后迭代器失效,行为未定义。

追问 / 延伸

  • list 的 remove_if 是什么?答:list 自带的成员函数,直接删除满足条件的元素,O(n),比通用算法更快(因为不用移动元素)。
  • erase_if 和 remove + erase 有什么区别?答:remove + erase 是两步,先把要删的元素移到末尾,再 erase;erase_if 一步到位,语义更清晰。

待整理清单

  • [ ] 各容器时间复杂度对比表完整版
  • [ ] 自定义类型作为 unordered_map key 的哈希函数写法
  • [ ] 红黑树插入删除旋转详解
  • [ ] 短路迭代器与 vector 的坑