vector基于连续内存，随机访问O(1)，适合尾部增删和频繁访问；list为双向链表，插入删除O(1)，但访问O(n)，适用于频繁中间修改和迭代器稳定场景。
在C++中，vector 和 list 是两种常用的序列容器，它们都属于STL（标准模板库），但底层实现和性能特点差异明显。选择合适的一种对程序效率至关重要。
底层数据结构不同
vector 是基于动态数组实现的，元素在内存中连续存储。这意味着可以通过指针算术快速访问任意位置的元素，缓存局部性好。
list 是双向链表，每个节点包含前驱和后继指针。节点在堆上分散分配，不保证内存连续。
随机访问性能对比
vector 支持 O(1) 随机访问：通过下标 operator[] 或 at() 方法可直接定位元素。
立即学习“C++免费学习笔记（深入）”；
list 仅支持 O(n) 遍历访问：要访问第 n 个元素必须从头或尾逐步遍历，不支持下标随机访问。
例如：
- vector
v(1000); v[500] = 10; // 瞬间完成 - list
l; /* 填充1000个元素 */ - advance(l.begin(), 500); // 需要一步步移动迭代器
插入与删除操作效率
vector 在中间插入/删除为 O(n)：虽然尾部插入均摊 O(1)，但中间操作需要移动后续所有元素，并可能触发重新分配。
list 在任意位置插入/删除为 O(1)：只要已有迭代器指向位置，插入和删除只涉及指针调整，非常高效。
注意：
- vector 尾插效率高（推荐使用 emplace_back / push_back）
- list 插入不会使其他迭代器失效（除了被删元素的迭代器）
- vector 插入可能导致内存重分配，使所有迭代器、指针、引用失效
内存使用与缓存友好性
vector 内存开销小，更紧凑：只存储数据本身，无额外指针。连续布局利于CPU缓存预取，访问速度快。
list 每个节点额外消耗两个指针空间：以 int 为例，64位系统上一个节点通常占用 4（int）+ 8×2（指针）= 20 字节，有内存碎片问题。
因此，遍历 list 的实际速度通常远慢于 vector，即使两者都是 O(n)。
适用场景总结
选择依据应基于实际操作类型：
- 频繁随机访问、尾部增删 → 用 vector
- 频繁中间插入/删除、不常随机访问 → 用 list
- 元素少且操作简单 → 优先选 vector（缓存优势明显）
- 需要稳定迭代器（插入不失效）→ 考虑 list
基本上就这些。多数情况下，vector 是更优选择，除非你明确需要 list 提供的常数时间中间修改能力。不要过早优化，先用 vector，性能瓶颈再考虑替换。不复杂但容易忽略的是：现代CPU对连续内存的偏好往往压倒理论上的“链表插入更快”印象。
