STL 与迭代器

核心问题

• 常用容器底层结构和复杂度分别是什么
• vector 为什么扩容后可能导致迭代器失效
• unordered_map 的冲突处理和 rehash 机制是什么
• 红黑树为什么适合关联式容器
• 不同容器的适用场景和性能特征
• 迭代器分类和失效规则
• 算法与容器的配合使用
• 自定义类型的容器使用注意事项

建议复习顺序

1. 顺序容器（vector扩容与迭代器失效）
2. 哈希容器（unordered_map与哈希冲突）
3. 关联容器（红黑树与关联容器）
4. 常用容器对比与选型
5. 迭代器分类与失效规则
6. 算法与仿函数（综合应用）

子主题导航

• vector扩容与迭代器失效.md
• unordered_map与哈希冲突.md
• 红黑树与关联容器.md
• 常用容器对比与选型.md
• 迭代器分类与失效规则.md
• STL算法与仿函数.md

高频追问

• 为什么 vector 不适合频繁头插
• unordered_map 为什么可能退化
• set 和 unordered_set 怎么选
• 为什么插入不一定会让所有迭代器失效
• 输入迭代器、前向迭代器、随机访问迭代器有什么区别
• vector、deque、list 应该怎么选
• 为什么 STL 算法和容器是分离设计
• 不同容器的时间复杂度对比
• 如何选择合适的容器类型
• 自定义类型如何支持容器操作

易错点

• 只背复杂度，不讲底层结构
• 把引用失效和迭代器失效混成一件事
• 认为哈希表一定比树结构更快
• 只会背容器结论，不会根据访问模式做选型
• 忽略不同容器的内存布局差异
• 不理解迭代器失效的具体条件
• 在循环中修改容器导致迭代器失效

学习策略

记忆技巧

容器选择口诀：

• vector = “连续内存，随机访问快”
• list = “链表结构，插入删除快”
• map = “红黑树，有序查找”
• unordered_map = “哈希表，平均O(1)”

性能对比：

• 查找：unordered_map(平均O(1)) > map(O(log n)) > vector(O(n))
• 插入：list(O(1)) > unordered_map(平均O(1)) > map(O(log n))
• 内存：vector(紧凑) > map(指针) > unordered_map(桶+链)

关联学习

STL与迭代器与前面的知识紧密相关：

1. 模板与泛型：所有容器都是模板类
2. 移动语义：容器操作中的性能优化
3. 类型系统：自定义类型的容器支持
4. 内存管理：容器的内存分配策略

建议结合具体使用场景来理解不同容器的设计取舍。