选择合适的容器对 C++ 程序的正确性和性能都至关重要。本文深入分析常用容器的内部实现、时间复杂度与适用场景。

序列容器

• vector：连续内存，尾端插入 O(1) 均摊。超过容量时需要重新分配和拷贝。默认首选。
• deque：分段连续内存，首尾插入 O(1)。适用于需要在头部操作的场景。
• list：双向链表，任意位置插入 O(1)。但每个节点有额外指针开销，缓存不友好。大多数情况下 vector 更快。

关联容器

• map/set：红黑树实现，有序遍历 O(log n)。适用于需要排序或范围查询的场景。
• unordered_map/set：哈希表实现，平均 O(1) 查找。适合纯键值查找，但内存占用更大。

选择策略

默认首选 vector。需要频繁在头部插入时用 deque。需要稳定迭代器和频繁中间插入时考虑 list。需要键值查找时：如果需要排序遍历用 map，否则用 unordered_map。

了解容器的内部实现，才能做出正确的性能权衡。