1.27、介绍一下vector、list的底层实现原理和优缺点

底层实现：

• • vector底层是基于动态数组实现的。它维护一块连续的内存空间用于存储元素，并通过两个变量记录当前元素数量（size）和已分配容量（capacity）。
• • 当元素数量超过当前容量时，vector会申请一块更大的连续内存（通常扩容为原容量的1.5~2倍），将原有元素拷贝或移动到新内存，然后释放旧内存。
• • 这种连续内存结构保证了元素的随机访问时间复杂度为O(1)，且缓存友好，访问效率高。
• • 通过reserve()可以预先分配容量，减少扩容次数，提高性能。
• • 支持快速尾部插入和删除（均摊O(1)），但中间插入或删除需要移动大量元素，时间复杂度为O(n)。

优点：

• • 随机访问快，支持通过下标直接访问元素。
• • 内存连续，缓存命中率高，性能优越。
• • 动态扩容，使用灵活。
• • 支持移动语义，减少不必要拷贝。

缺点：

• • 扩容时可能导致内存重新分配和元素拷贝，开销较大。
• • 中间插入或删除效率低，需移动元素。
• • 内存使用可能有碎片，且扩容策略可能导致空间浪费。

list的底层实现原理及优缺点

底层实现：

• • list底层是基于双向链表实现的。每个元素存储在独立的节点中，节点包含元素本身及指向前后节点的指针。
• • 由于节点不连续，list不支持随机访问，访问第n个元素需要从头或尾开始遍历，时间复杂度为O(n)。
• • 插入和删除操作只需修改节点指针，时间复杂度为O(1)，且不会导致元素移动。
• • 迭代器是双向的，支持双向遍历。

优点：

• • 在任意位置插入和删除元素效率高（常数时间）。
• • 不需要连续内存，插入删除不会触发内存重新分配。
• • 适合频繁插入删除操作的场景。

缺点：

• • 不支持随机访问，访问效率低。
• • 每个节点额外存储两个指针，内存开销较大。
• • 缓存不友好，访问性能相对较差。

总结对比

本文首发于【讳疾忌医-note】公众号，未经授权，不得转载。
（加入我的知识星球，免费获取账号，解锁所有文章。）