打破迷思：为什么资深C++开发者几乎总是选择vector而非list

大家好，我是小康。
前言：打破你对容器选择的固有认知

嘿，C++小伙伴们！面对这段代码，你会怎么选？

1. // 存储用户信息，需要频繁查找、偶尔在中间插入删除
2. // 选择哪个容器实现？
3. std::vector<UserInfo> users;  // 还是
4. std::list<UserInfo> users;    // ?

复制代码

如果你刚学习C++，可能会想："数据会变动，肯定用list啊！教材上说链表插入删除快嘛！"
然后有一天，你看到一位经验丰富的同事把所有list都改成了vector，并且代码性能提升了，你一脸懵逼： "这跟我学的不一样啊！"
是的，传统教科书告诉我们：

• 数组（vector）：随机访问快，插入删除慢
  
• 链表（list）：插入删除快，随机访问慢
  

但实际工作中，大多数资深C++开发者却几乎总是使用vector。为什么会这样？是教材错了，还是大佬们有什么不可告人的秘密？
今天，我要带你进入真实的C++江湖，揭开vector和list性能的真相，帮你彻底搞懂这个看似简单却被无数程序员误解的选择题。
深入阅读后，你会发现：这个选择背后，涉及现代计算机体系结构、内存模型和真实世界的性能考量，而不仅仅是算法复杂度的简单对比。

微信搜索 【跟着小康学编程】，关注我，定期分享计算机编程硬核技术文章。

一、理论上：vector和list各是什么？

先来个直观的比喻：

• vector就像一排连续的座位：大家坐在一起，找人超快，但中间插入一个人就需要后面的人都往后挪。
  
• list就像一群手拉手的人：每个人只知道自己左右邻居是谁，找到第n个人必须从头数，但中间插入一个人只需要改变两边人的"指向"。
  

技术上讲：

• vector：连续内存，支持随机访问（可以直接访问任意位置），内存布局紧凑
  
• list：双向链表，只支持顺序访问（必须从头/尾遍历），内存布局分散
  

vector和list的内部结构对比

vector的内部结构：

1. [元素0][元素1][元素2][元素3][元素4][...]
2. ↑                               ↑
3. begin()                        end()

复制代码

vector内部其实就是一个动态扩展的数组，它有三个重要指针：

• 指向数组开始位置的指针start
  
• 指向最后一个元素后面位置的指针end
  
• 指向已分配内存末尾的指针（容量capacity）
  

当空间不够时，vector会重新分配一块更大的内存（通常是当前大小的1.5或2倍），然后把所有元素搬过去，就像搬家一样。
list的内部结构：

1.    ┌──────┐    ┌──────┐    ┌──────┐
2.    │ prev │◄───┤ prev │◄───┤ prev │
3. ┌──┤ data │    │ data │    │ data │
4. │  │ next │───►│ next │───►│ next │
5. │  └──────┘    └──────┘    └──────┘
6. │     节点0        节点1       节点2
7. ↓
8. nullptr

复制代码

list是由一个个独立的节点组成，每个节点包含三部分：

• 存储的数据
  
• 指向前一个节点的指针
  
• 指向后一个节点的指针
  

这就像一个手拉手的圆圈游戏，每个人只能看到左右两个人，要找到第五个人，必须从第一个开始数。
这两种容器结构上的差异，决定了它们在不同操作上的性能表现。vector因为内存连续，所以可以通过简单的指针算术直接跳到任意位置；而list必须一个节点一个节点地遍历才能到达指定位置。
按照传统教科书，它们的复杂度对比是这样的：
操作vectorlist随机访问O(1)O(n)头部插入/删除O(n)O(1)尾部插入/删除均摊 O(1)O(1)中间插入/删除O(n)O(1)**注意：list 的中间插入/删除是O(1)，但前提是你已经有了指向该位置的迭代器，找到这个位置通常需要O(n)时间。
看上去 list 在插入删除方面优势明显，但为什么那么多经验丰富的程序员却建议"几乎总是用vector"呢？
二、现实很残酷：理论≠实践

老铁，上面的理论分析忽略了一个超级重要的现代计算机特性：缓存友好性。
什么是缓存友好性？

想象你去图书馆看书：

• vector就像是把一整本书借出来放在你桌上（数据连续存储）
  
• list就像是每看一页就得去书架上找下一页（数据分散存储）
  

现代CPU都有缓存机制，当访问一块内存时，会把周围的数据也一并加载到缓存。对于连续存储的vector，这意味着一次加载多个元素；而对于分散存储的list，每次可能只能有效加载一个节点。
实际性能测试

我做了一个简单测试，分别用vector和list存储100万个整数，然后遍历求和：

1. // Vector遍历测试 - 使用微秒计时更精确
2. auto start = chrono::high_resolution_clock::now();
3. int sum_vec = 0;
4. for (auto& num : vec) {
5.      sum_vec += num;
6. }
7. auto end = chrono::high_resolution_clock::now();
8. auto vector_time = chrono::duration_cast<chrono::microseconds>(end - start).count();
10. // List遍历测试 - 使用微秒计时更精确
11. start = chrono::high_resolution_clock::now();
12. int sum_list = 0;
13. for (auto& num : lst) {
14.      sum_list += num;
15. }
16. end = chrono::high_resolution_clock::now();
17. auto list_time = chrono::duration_cast<chrono::microseconds>(end - start).count();
19. // 输出结果 - 微秒显示，并转换为毫秒显示
20. ....

复制代码

结果震惊了我：

这是30几倍的差距！为啥？就是因为缓存友好性！
三、list的"快速插入"真的快吗？

我们再来测试一下在容器中间位置插入元素的性能：
[code] cout

热心回复！

感谢分享，下载保存了，貌似很强大

谢谢分享，辛苦了

新版吗？好像是停更了吧。

感谢分享，下载保存了，貌似很强大

热心回复！

前排留名，哈哈哈

感谢发布原创作品，程序园因你更精彩