容器选型：别让选择成为性能的绊脚石

STL 容器，说白了就是 C++ 给咱们准备好的「数据结构工具箱」。我见过太多项目，明明业务逻辑写得挺好，就因为容器选错了，性能直接崩盘。今天咱们就聊聊这几个核心容器——vector、list、map、unordered_map，怎么选、怎么用、怎么避开那些坑。

vector：最常用的「万能选手」

我个人习惯，能上 vector 就上 vector。为什么？因为它内存连续，缓存友好。你想想看，CPU 从内存读数据是按缓存行来的，vector 的元素挨着放，遍历起来那叫一个丝滑。

// 日常用法
std::vector<int> vec;
vec.push_back(42);   // 尾部插入，O(1) 均摊
vec[0];              // 随机访问，O(1)

但 vector 有个致命弱点——中间插入和删除。我在项目中遇到过，有人用 vector 做队列，频繁在头部插入，结果性能惨不忍睹。每次头部插入，后面所有元素都得往后挪，O(n) 的复杂度，数据量一上来就完蛋。

list：双向链表的「双刃剑」

list 的优势在于插入删除快，只要找到位置，O(1) 搞定。但代价是什么？内存不连续，遍历慢，而且每个节点都有额外的指针开销。

std::list<int> lst;
lst.push_back(1);
lst.push_front(2);   // 头部插入也是 O(1)

说实话，我很少用 list。除非你真的需要频繁在中间插入删除，而且不关心随机访问。否则，vector 或者 deque 往往更合适。

map vs unordered_map：有序与无序的抉择

这两个容器，我经常被问到「到底该用哪个？」。其实答案很简单：

• 需要有序遍历 → 用 map（红黑树，O(log n)）
• 只关心查找速度 → 用 unordered_map（哈希表，O(1) 均摊）

// map：有序，但慢一点
std::map<std::string, int> m;
m["apple"] = 5;
// 遍历时按键排序

// unordered_map：无序，但快
std::unordered_map<std::string, int> um;
um["apple"] = 5;
// 遍历时顺序不确定

我在项目中遇到过，有人用 map 存了 10 万条配置项，每次查找都 O(log n)，其实完全可以用 unordered_map 把查找降到 O(1)。但反过来，如果你需要范围查询（比如找出所有 key 在 "a" 到 "c" 之间的元素），map 就比 unordered_map 强太多了。

迭代器失效：一个让人头疼的问题

嗯，这里要注意。迭代器失效是 STL 里最容易踩的坑之一。说白了，就是你在遍历容器的时候，容器内部结构变了，之前的迭代器就「废了」。

容器	插入操作	删除操作
vector	可能导致所有迭代器失效（扩容时）	被删元素及之后的所有迭代器失效
list	不影响其他迭代器	只影响被删元素的迭代器
map/unordered_map	不影响其他迭代器	只影响被删元素的迭代器

我曾经在代码里写过这样的 bug：

// 错误示例：迭代器失效
std::vector<int> vec = {1, 2, 3, 4, 5};
for (auto it = vec.begin(); it != vec.end(); ++it) {
    if (*it == 3) {
        vec.erase(it);  // 这里 it 已经失效了！
    }
}

正确的做法是：

// 正确示例
for (auto it = vec.begin(); it != vec.end(); ) {
    if (*it == 3) {
        it = vec.erase(it);  // erase 返回下一个有效迭代器
    } else {
        ++it;
    }
}

算法复杂度分析：别被「平均情况」骗了

很多人只看平均复杂度，忽略了最坏情况。我见过一个系统，用 unordered_map 存了上百万条数据，结果哈希冲突严重，查找从 O(1) 退化到 O(n)，整个系统直接卡死。

这里我给大家一个简单的选型指南：

操作	vector	list	map	unordered_map
随机访问	O(1)	O(n)	O(log n)	O(1) 均摊
尾部插入	O(1) 均摊	O(1)	O(log n)	O(1) 均摊
中间插入	O(n)	O(1)	O(log n)	O(1) 均摊
查找	O(n)	O(n)	O(log n)	O(1) 均摊

知识体系总览

下面这张图，是我总结的容器选型决策流程。你跟着走一遍，基本不会选错。

这张图的核心逻辑很简单：先看你的主要操作是什么，再根据数据量和性能要求做选择。别一上来就 map，很多时候 vector 加线性查找就够用了。

好了，容器选型这块就聊到这儿。记住，没有银弹，只有最适合你场景的选择。下次写代码前，先想想你的数据长什么样、操作频率如何，再下手选容器。

---