2.3、vector 与 list 区别

底层结构差异

vector

• • 底层实现：动态数组，内存连续分配。
• • 访问特性：支持高效随机访问，时间复杂度为 O(1)（通过下标operator[]或迭代器）。
• • 内存管理：预分配机制，capacity ≥ size；扩容时需重新申请更大连续内存，并复制原有元素。

list

• • 底层实现：双向链表，内存非连续（节点通过指针连接）。
• • 访问特性：不支持随机访问，只能顺序遍历，元素访问时间复杂度为 O(n)。
• • 操作特性：插入/删除操作只需修改指针指向，时间复杂度为 O(1)（已定位迭代器位置时）。

性能对比

适用场景

vector 更适合：

• • 需要频繁随机访问元素（如数组下标式操作）。
• • 主要操作集中在尾部插入/删除（如push_back/pop_back）。
• • 元素数量变化可预测，或可通过reserve提前分配空间。
• • 追求缓存友好性和高内存利用率（无额外指针开销）。

list 更适合：

• • 需要频繁在中间或头部插入/删除元素（如链表式增删）。
• • 对随机访问性能无要求，仅需顺序遍历。
• • 元素数量动态变化剧烈，且插入/删除操作位置不确定。

实践建议

• • 优先选用vector：尽管传统理论认为list在插入删除场景更优，但vector的连续内存布局带来的缓存优势和高效内存管理，使其在大多数场景下性能更优，且代码更简洁。
• • 仅当确实存在大量非尾部插入/删除操作（如频繁在容器中间增删元素）时，才考虑使用list。

总结

vector和list的设计体现了时间与空间的权衡：

• • vector以连续内存和预分配机制换取随机访问效率和缓存友好性；
• • list以非连续内存和指针操作换取灵活的插入/删除效率。
  选择容器时，需结合具体场景的访问模式、操作频率和内存效率需求，这是C++容器选型的核心要点。
  本文首发于【讳疾忌医-note】公众号，未经授权，不得转载。
  （加入我的知识星球，免费获取账号，解锁所有文章。）