C++ vector与list区别详解

vector基于连续内存的动态数组，list为双向链表；2. vector随机访问O(1)，list为O(n)；3. list中间插入删除O(1)，vector平均O(n)；4. vector内存紧凑缓存友好，list开销大；5. vector迭代器易失效，list较稳定；6. 多数场景优先vector，频繁中间修改选list。

在C++中，vector和list是两种常用的序列容器，它们都属于STL（标准模板库）的一部分，但设计目标和底层实现不同，导致在性能和使用场景上有明显差异。

底层数据结构不同

vector基于动态数组实现，元素在内存中连续存储。这意味着可以通过指针算术快速访问任意位置的元素，也利于CPU缓存命中。

list是双向链表，每个元素包含前驱和后继指针，节点在堆上分散分配，不保证内存连续性。

随机访问性能对比

vector支持O(1)时间复杂度的随机访问，例如vec[i]或*(vec.begin() + n)非常高效。

list只支持双向遍历，访问第n个元素需要O(n)时间，不推荐频繁随机访问。

• 需要下标访问时优先选vector
• 仅顺序遍历时list也可接受

插入与删除效率差异

在中间位置插入或删除元素时，list表现更优：

• list在已知位置插入/删除为O(1)，只需修改指针
• vector在中间操作平均为O(n)，因为要移动后续所有元素
• 但在尾部插入，vector通常为O(1)（摊还），且实际速度更快

频繁在非尾部修改数据时list更有优势。

内存使用与缓存友好性

vector内存开销小，仅需额外空间用于容量增长；list每个节点额外占用两个指针空间，内存碎片多，缓存命中率低。

相同数量元素下，list通常占用更多内存，且遍历速度不如vector。

迭代器失效规则

vector在插入可能导致扩容时，所有迭代器、指针、引用都会失效；删除仅使当前位置及之后的失效。

list的迭代器几乎不会失效（删除对应元素除外），适合边遍历边修改的场景。

适用场景总结

选择依据应结合具体需求：

• 多数情况优先用vector：访问频繁、尾部增删、对性能敏感
• list适用于频繁在中间插入/删除、需要稳定迭代器的场景
• 若需高速插入+较好访问，可考虑deque或forward_list作为替代

基本上就这些。vector更通用高效，list特定场景有用，理解底层机制才能合理选择。