C++ list和vector区别_C++链表与动态数组性能对比分析

list为链表，vector为动态数组：list支持O(1)中间插入删除但访问慢；vector随机访问O(1)、缓存友好但中间增删O(n)。频繁增删选list，遍历或访问多选vector。

C++ 中 list 和 vector 是两种常用的序列容器，虽然都能存储动态数量的元素，但在底层结构、内存布局和性能表现上有显著差异。理解它们的区别有助于在实际开发中做出更合适的选择。

底层实现不同：链表 vs 动态数组

std::list 是双向链表实现，每个元素包含数据和前后指针。元素在内存中不连续，通过指针连接。

std::vector 是动态数组，所有元素在内存中连续存储。当容量不足时，会重新分配更大空间并拷贝原有数据。

链表插入删除快，但访问慢；数组访问快，但插入删除可能涉及大量移动。

随机访问性能对比

vector 支持 O(1) 的随机访问。可以通过下标或指针算术直接定位元素：

• vec[1000] 或 *(vec.begin() + 1000) 都非常快

list 不支持真正的随机访问，只能从头或尾逐步遍历，访问第 n 个元素需要 O(n) 时间：

• std::advance(it, 1000) 会逐个移动迭代器

频繁按索引访问时，vector 明显优于 list。

插入与删除效率分析

在已知位置插入元素时，list 性能优势明显：

• list 在任意迭代器位置插入均为 O(1)
• vector 在中间插入是 O(n)，因为后续元素需后移
• vector 在末尾插入均摊 O(1)，但可能触发扩容重拷贝

删除同理：list 删除指定节点为 O(1)；vector 删除中间元素需前移后续项，为 O(n)。

若频繁在中间增删，尤其持有有效迭代器时，list 更高效。

内存使用与缓存友好性

vector 内存紧凑，具有优秀的缓存局部性：

• 连续存储利于 CPU 缓存预取，遍历速度快
• 每个元素额外开销小（无指针）

list 每个节点需额外存储两个指针，内存碎片多：

• 节点分散，缓存命中率低，遍历较慢
• 每元素额外占用通常为 16 字节（x64 下）

对性能敏感且以遍历为主场景，vector 通常更优。

基本上就这些。选择 list 还是 vector，关键看操作模式：大量中间插入删除选 list；频繁随机访问、遍历或空间敏感选 vector。实践中 vector 因缓存友好性，多数情况表现更好，除非有明确的频繁非尾部修改需求。