C++之vector/list/map完整对比与解读

一、底层数据结构

1. vector（动态数组） 底层：连续内存数组，一块完整的堆内存，遇到容量不够时会自动扩容。
2. list（双向链表） 底层：双向不连续链表，每个节点既存数据又带前后指针，内存是分散的。
3. map（有序红黑树） 底层：红黑平衡二叉树，按键 key 自动升序排序，键唯一不可重复。

二、核心性能对比（时间复杂度）

表格里汇总了最常用的操作复杂度，一目了然，咱们直接看数据：

三、基础代码示例

1. vector 动态数组（优先日常容器）

什么时候用？频繁随机读写、尾部增删的场景，中间插入很少出现。看一段最基础的使用：

#include 
#include 
using namespace std;

int main() {
    vector vec;
    vec.push_back(10);  // 尾部添加
    vec.push_back(20);
    vec.insert(vec.begin(), 5); // 头部插入，效率低
    cout << vec[1]; // 随机访问 O(1)

    // 遍历
    for (int x : vec) cout << x;
    return 0;
}

2. list 双向链表

适用场景：频繁在头部或中间增删，而且几乎不需要随机读取。直接上代码：

#include 
int main() {
    list lst;
    lst.push_back(1);
    lst.push_front(0); // 头部插入很快
    // 无 lst[0] 这种随机访问，只能迭代器遍历
    for (auto it = lst.begin(); it != lst.end(); ++it) {}
    return 0;
}

3. map 有序键值对

适用场景：需要 key 自动排序、按键快速查找，而且键不能重复。看个例子：

#include 

四、优缺点总结

vector

✅ 优点：随机访问超快、缓存友好、内存紧凑、遍历速度最快。

❌ 缺点：头部/中间插入删除大量元素移位，扩容时会拷贝数据。

场景：数组、缓存、数据批量存储，绝大多数业务场景的首选。

list

✅ 优点：任意位置插入删除仅修改指针，没有内存拷贝。

❌ 缺点：不支持随机访问，遍历慢、内存碎片多、缓存不命中。

场景：频繁中间增删、队列节点管理、极少需要按下标查询的场景。

map

✅ 优点：key 有序，按键二分查找，插入删除稳定 logn 复杂度。

❌ 缺点：不能按下标随机遍历 value，树结构内存开销大。

场景：字典、有序映射、需要按 key 快速检索的配对数据。

五、选型快速口诀

1. 要下标随机取数据 → vector
2. 频繁在中间/头部删改，不用下标 → list
3. 存 key-value、需要自动排序、按键查找 → map