vector和deque底层实现与性能对比
请对比std::vector和std::deque的底层数据结构、内存分配策略、迭代器特性、插入/删除/随机访问的时间复杂度及适用场景。
回答
我是大山
vector:
- 底层:连续动态数组。
- 内存:预分配capacity(通常2倍增长),所有元素连续存储。
- 随机访问:O(1),极快(连续内存、CPU缓存友好)。
- 尾部插入/删除:均摊O(1),尾部之外插入/删除:O(n)(需移动元素)。
- 迭代器:随机访问迭代器,插入/删除后所有迭代器失效(重新分配时)。
deque:
- 底层:分段连续存储(一组固定大小缓冲区,通过中央控制块/映射管理)。
- 内存:非完全连续,但每个缓冲区内部连续。
- 随机访问:O(1),但比vector慢(需两级间接:控制块->缓冲区->元素)。
- 头部/尾部插入/删除:O(1)(只需操作缓冲区边界)。中间插入/删除:O(n)。
- 迭代器:随机访问迭代器,插入/删除时只有被操作元素附近迭代器失效。
适用场景:
- vector:需要大量随机访问、主要在尾部操作、对缓存友好性要求高。
- deque:需要两端高效操作(如队列)、随机访问需求较少。
- vector在C++11支持移动语义后,性能更好。