题目重点：用 vector、deque、list、map 与 unordered_map 比较访问、插入和内存。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 区分标准复杂度/失效保证与常见实现；标准不要求 map 必须使用某一种红黑树实现。
解题路线
- vector 连续存储，随机访问常数，末尾插入摊还常数；扩容可能搬移元素，容量改变时引用/指针/迭代器失效。
- deque 支持随机访问与两端增长，常见分块实现；list 节点式结构使已知位置插删常数，但寻找第 k 个仍线性。
- map 按 comparator 排序，检索/插删对数；unordered_map 平均常数，最坏可线性，需 hash 与 key equality 一致。
- 不要只看复杂度：连续访问的缓存局部性、每节点分配和元素搬移成本会改变真实表现。先选访问合同，再测规模。
手动走一遍
想存一百万条只按下标读取的数据，vector 通常比 list 更匹配；list 的 O(1) 插入不包含找到位置的成本。保存 vector 元素地址后 push_back 触发扩容，旧地址不能继续使用。reserve 可减少重新分配，但不消除所有失效。
规模与取舍
n 元素空间 O(n)，额外容量/指针/桶带来不同常数；标准上界不能替代代表性负载基准。
易错点与追问
容易失分的边界
- map 必须红黑树的绝对说法。
- deque 与 vector 失效规则完全相同。
- unordered_map 所有输入都 O(1)。
继续深挖
- 如何选择稳定地址的数据结构？
- 自定义比较器不满足严格弱序会有什么问题？
