2.5、说一说如何选择顺序容器

• • 优先选择vector或deque（支持operator[]/at等随机访问操作）：
  • • vector：底层连续内存，缓存友好性最佳，随机访问速度最快。
  • • deque：分段连续内存，支持随机访问，但效率略逊于vector（需跨块指针跳转）。

2. 插入与删除操作位置

• • 尾部操作为主+随机访问：选vector，尾部push_back/pop_back均摊O(1)效率。
• • 头尾双端操作+随机访问：选deque，头尾插入/删除均为O(1)（无需移动元素，仅修改指针）。
• • 中间频繁插入/删除+低随机访问需求：选list（双向链表），插入/删除O(1)（已定位迭代器），但访问元素需O(n)顺序遍历。

3. 已知元素数量及内存考虑

• • 空间敏感+已知元素量：优先选vector，避免链表（list/deque）的指针额外内存开销。
• • 大元素+高频插入删除+空间允许：可接受list的内存开销（每个节点含前驱/后继指针）。

4. 复杂场景的折中方案

• • 输入阶段中间插入+后续随机访问：
  先用list存储（灵活插入），输入完成后排序并复制到vector中（转为高效随机访问）。
• • 随机访问+双端插入删除：选deque，平衡vector的访问效率与list的双端操作优势。

5. 其他关键注意点

• • 避免vector中间操作：频繁中间插入/删除会导致大量元素移动，时间复杂度O(n)，性能低下。
• • deque内存管理：无固定capacity，分段动态扩展，适合元素数量不可预测的双端操作场景。
• • list迭代器稳定性：插入/删除时仅当前节点迭代器失效，其他迭代器保持有效，适合迭代过程中修改容器。

总结表：需求场景与推荐容器

本文首发于【讳疾忌医-note】公众号，未经授权，不得转载。
（加入我的知识星球，免费获取账号，解锁所有文章。）