YoYouFun 笔记

外观

Stage07｜Modern C++ Foundation ​

Lesson087｜vector、list、map、unordered_map 如何选择 ​

Tags： #C++17 #Container #DataStructure #PerformanceDifficulty： ⭐⭐⭐⭐☆

一、问题场景：理论 O(1) 为什么反而更慢 ​

有人把连续数组改成链表，理由是中间删除 O(1)，结果帧耗时上升。因为找到节点、逐个指针跳转、缓存未命中和分配成本可能远大于移动一段连续小对象。

二、本课目标 ​

  1. 从访问模式而非单个复杂度选择容器。
  2. 理解连续存储、节点存储和哈希桶。
  3. 掌握 iterator/reference 失效规则的核心。
  4. 避免 operator[] 意外插入。
  5. 建立可复现的容器基准。

三、回到 TaskSystem：任务队列的访问模式 ​

任务队列不是抽象的“装东西的容器”，它有明确访问模式：生产者尾部插入、worker 头部取出、可能按 ID 查询、可能统计状态。若只需要 FIFO，std::queue 语义比暴露 vector 更清楚；若要取消某个任务，还要考虑索引、迭代器稳定性和删除成本。

四、默认从 vector 开始 ​

std::vector<T> 连续存储：

text
优点：遍历快、局部性好、额外开销低、可随机访问
代价：扩容会搬迁；中间插删需要移动后续元素

如果不知道选什么，且数据主要遍历，vector 通常是首选。用 reserve 表达容量预期，避免多次扩容。

五、list 的真实适用面 ​

std::list<T> 每个元素独立节点，已知迭代器位置时插删稳定，但：

text
每个节点有指针开销
通常每节点分配
无法随机访问
遍历对 CPU cache 不友好

只有确实需要稳定迭代器、频繁拼接或已知位置插删，并经测量证明时才选它。

六、map 与 unordered_map ​

text
map：有序树，O(log n)，迭代顺序稳定，范围查询方便
unordered_map：哈希桶，平均 O(1)，无排序保证，受 hash 和 rehash 影响

不要用 unordered_map 的迭代顺序做序列化、网络协议或确定性逻辑。哈希键还需要正确实现等价关系和 hash 一致性。

七、失效规则 ​

vector 扩容会使指针、引用和迭代器失效；erase 后被删位置及之后通常失效。unordered_map rehash 会使迭代器失效。工程中不要长期保存容器元素地址，除非容器与操作规则明确保证稳定。

八、operator[] 的副作用 ​

cpp
std::unordered_map<std::string, int> counts;
if (counts["missing"] == 0) { /* 已经插入了键 */ }

只查询应使用 find：

cpp
auto it = counts.find("missing");
if (it != counts.end()) { /* 使用 it->second */ }

九、可编译验证：访问模式基准 ​

构造 100 万个整数，分别测试 vector 与 list 的顺序求和；再测试随机删除 1000 个已知位置。使用 std::chrono::steady_clock，Release 编译，预热后多轮测量并输出校验和，防止编译器消除循环。

cpp
template<class F>
long long measure(F&& fn) {
    auto begin = std::chrono::steady_clock::now();
    fn();
    return std::chrono::duration_cast<std::chrono::microseconds>(
        std::chrono::steady_clock::now() - begin).count();
}

预期 vector 顺序遍历通常显著占优；删除结果取决于元素大小、位置分布和是否已知迭代器。不要预设结论，记录硬件、编译器和优化级别。

十、游戏工程选型例子 ​

text
本帧可见对象列表 → vector
实体 ID 到对象 → unordered_map
按时间排序的事件 → map 或优先队列
小型固定表 → array
需要去重且无顺序 → unordered_set

十一、TaskSystem 的取舍 ​

如果任务需要按优先级取出，FIFO queue 不够；如果需要取消任意任务，优先队列删除中间元素和索引维护会增加复杂度；如果只需要按 ID 查询状态，可以让队列和状态表分离，避免一个容器承担互相冲突的访问模式。容器不是越“通用”越好，而是要让不变量和失效规则可读。

十二、诊断清单 ​

性能下降时检查元素数量、元素大小、访问是否连续、分配次数、rehash、hash 冲突和失效后地址。大 O 只描述规模趋势，不包含缓存和常数。

十三、练习与答案 ​

1. vector 删除为什么未必慢？ ​

连续内存移动可以高度优化；小型可移动元素和中小规模下，它可能比节点分配与缓存未命中更便宜。

2. 何时需要 map 而不是 unordered_map？ ​

需要有序遍历、范围查询、稳定比较语义或最坏 O(log n) 边界时。

3. reserve 和 resize 的区别？ ​

reserve 只调整容量，不创建逻辑元素；resize 改变 size，会构造或销毁元素。

十四、本课总结 ​

容器选择应回答：数据如何遍历、如何查找、是否要求顺序、引用是否需稳定、元素多大。复杂度是起点，访问模式和测量才是结论。