一、底层实现结构

vector

底层是动态连续数组，内存地址连续紧挨，在堆上开辟一整块连续空间。

list

底层是双向循环链表，每个节点独立分配内存，内存散乱不连续；每个节点除数据外，还存前驱指针、后继指针。

---

二、随机访问能力

vector

支持随机访问可以用 []、.at()、下标跳跃访问，时间复杂度 O(1)原理：连续内存，首地址 + 偏移量直接定位元素。

list

不支持随机访问只能从 begin 逐个往后遍历，不能直接跳转到第 n 个元素；访问任意元素时间复杂度 O(n)。

---

三、插入、删除效率

vector

1. 尾部插入 / 删除：极快 O (1)
2. 头部 / 中间插入 / 删除：很慢 O (n)原因：必须向后 / 向前移动大量元素，腾出位置或填补空位；若空间不足还会触发整体扩容、重新分配内存、拷贝全部元素。

list

任意位置（头、中、尾）插入、删除都很快 O (1)只需要修改相邻节点的指针指向，不用移动任何元素数据，也不需要整体扩容拷贝。

---

四、内存占用与空间特点

vector

• 内存整块连续
• 有 capacity 容量冗余，提前预留空间，会浪费闲置内存
• 缓存命中率高，CPU 读取连续数据速度快

list

• 每个节点碎片化分配
• 每个节点多占用两个指针，额外内存开销大
• 内存散乱，CPU 缓存不友好，遍历速度偏慢

---

五、扩容机制

vector

元素个数达到容量上限时：

1. 重新申请一块更大的连续内存
2. 把旧元素全部拷贝到新空间
3. 释放旧内存会产生内存重新分配、元素拷贝开销。

list

无扩容概念每次新增元素单独 new 一个节点，用多少开多少，不需要整体迁移。

---

六、迭代器失效机制（重点）

vector

非常容易失效：

1. 插入元素 → 可能触发扩容，所有迭代器全部失效
2. 删除中间元素 → 后面所有元素前移，后面迭代器全部失效

list

几乎不失效：只有被删除的那个节点迭代器失效，其他所有迭代器、指针、引用依然有效。

---

七、排序效率

vector

支持随机访问，可以用 STL 快速排序，排序效率高。

list

不支持随机访问，不能直接用 std::sort；只能用自身成员函数 list.sort()，效率低于 vector 排序。

---

八、适用场景

优先用 vector

• 频繁遍历、查询、随机访问
• 只在尾部做增删
• 要求内存紧凑、CPU 缓存效率高

优先用 list

• 在任意位置频繁插入、删除
• 不怎么需要随机访问
• 要求迭代器长期有效，不怕增删元素

---

九、总结一句话

vector 是连续动态数组，随机访问快、遍历快、中间增删慢、会扩容、迭代器易失效；list 是双向链表，不支持随机访问、任意位置增删极快、无扩容、迭代器更稳定、内存开销更大。