[C++] vector对比list deque的引出
文章目录
- `list`与`vector`的对比
- 双端队列`deque`
- `deque`的特性
- `deque`的底层实现原理
- 内存结构
- 块表（Block Array）
- 块（Block）
- 插入与删除
- 两端插入
- 两端删除
- 随机访问
- 如何计算位置
- 迭代器设计
- 总结
list与vector的对比
vector与list都是STL中非常重要的序列式容器，由于两个容器的底层结构不同，导致其特性以及 应用场景不同，其主要不同如下：
| 特性 | **vector**（动态数组） | **list**（双向链表） |
|---|---|---|
| 底层结构 | 动态顺序表，一段连续空间 | 带头结点的双向循环链表 |
| 随机访问 | 支持随机访问，访问效率O(1) | 不支持随机访问，访问某个元素效率O(N) |
| 插入和删除 | 任意位置插入和删除效率低，需要搬移元素，时间复杂度为O(N)，插入时有可能需要增容，增容：开辟新空间，拷贝元素，释放旧空间，导致效率更低 | 任意位置插入和删除效率高，不需要搬移元素，时间复杂度为O(1) |
| 空间利用率 | 底层为连续空间，不容易造成内存碎片，空间利用率高，缓存利用率高 | |
| （但是扩容会二倍扩，可能造成空间浪费） | 底层节点动态开辟，小节点容易造成内存碎片，空间利用率低，缓存利用率低 | |
| （在申请空间的时候是按需申请，不会浪费空间） | ||
| 迭代器封装 | 原生态指针 | 对原生态指针(节点指针)进行封装 |
| 迭代器失效 | 在插入元素时，要给所有的迭代器重新赋值，因为插入元素有可能会导致重新扩容，致使原来迭代器失效，删除时，当前迭代器需要重新赋值否则会失效 | 插入元素不会导致迭代器失效，删除元素时，只会导致当前迭代器失效，其他迭代器不受影响 |
| 使用场景 | 需要高效存储，支持随机访问，不关心插入删除效率 | 大量插入和删除操作，不关心随机访问 |
[C++] vector入门&迭代器失效问题详解-CSDN博客
[C++] 深入浅出list容器-CSDN博客
以上是对list和vector的相关讲解。在关于list的文章中有对list容器关于将原生指针包装为迭代器的详细讲解，以及关于list和vector中关于迭代器失效等问题的详细解答。
双端队列deque
deque的特性
deque（双端队列）结合了vector和list的优缺点，提供了在两端进行高效插入和删除的能力，同时支持高效的随机访问。deque的底层实现比vector和list更复杂，它使用了一系列的小的连续数组块来管理数据，这样可以在两端插入和删除时避免频繁的内存分配和拷贝。
基于deque的如上特性，经常用来作为queue的实现所基于的容器。queue 可以基于任何类型的容器来实现，而 deque 提供了高效的队列操作所需的基本功能：从前端插入和删除元素，以及从后端插入元素。
deque提供了以下特性，使其适合作为queue的底层实现：
- 从两端快速插入和删除元素的能力。
- 动态大小调整，不需要像
vector那样进行整体的内存重新分配。
deque的底层实现原理
deque（双端队列）的底层实现可以理解为一个动态的分段数组。它结合了数组和链表的优点，通过一组固定大小的小数组（称为块或缓冲区）来管理数据。
内存结构
deque并不是像vector那样的一块连续内存，而是由多个固定大小的块组成。每个块是一个连续的小数组，这些块按顺序排列，形成一个类似环形的结构。每个块的大小是固定的，但deque可以动态增加或减少块的数量。
deque起初是在多个块的中间位置开始建立，如此可以更高效的向前或者向后延伸。
块表（Block Array）
deque内部维护了一个指向这些块的指针数组，这个数组被称为块表（block array）。块表记录了所有块的指针，通过块表可以定位到具体的块，从而找到存储的数据。
块（Block）
每个块内部是一个固定大小的数组。每个块的大小通常是一个固定的常量，这样可以在块表中通过偏移量计算快速定位到块中的元素。
插入与删除
deque支持在两端高效的插入和删除，这主要得益于其分段结构。
两端插入
- 前端插入：在前端插入元素时，若当前前端块有空间，则直接插入；否则，在块表的前端插入一个新的块，然后将数据插入新块中。
- 后端插入：后端插入的处理方式与前端类似。如果后端块已满，则在块表后端新增一个块。
两端删除
- 前端删除：从前端块删除元素，如果前端块为空，则释放该块并调整块表。
- 后端删除：与前端删除类似，删除后如果后端块为空，则释放该块。
随机访问
deque支持高效的随机访问，这是因为它可以通过块表和块内偏移快速定位元素。
如何计算位置
对于一个给定的索引，首先需要计算它所在的块，然后计算块内的偏移量。具体计算公式如下：
- 计算块索引：
block_index = (start + index) / block_size - 计算块内偏移：
offset = (start + index) % block_size
迭代器设计
deque的迭代器较为复杂，因为它需要封装块表、块和块内元素的位置信息。deque的迭代器通常包含以下信息：
- 当前块指针：指向当前元素所在的块。
- 块内指针：指向当前块中的具体位置。
- 块表指针：指向块表中的位置。
通过这些信息，迭代器可以支持前向、后向的遍历和随机访问。当进行迭代操作时，迭代器需要处理跨块的情况，这增加了迭代器的复杂性。
总结
deque的底层是一个分段的、动态的二维数组结构，它提供了高效的两端插入和删除操作（中间删除操作效率和**vector**一样，需要移动数据 O(N)），同时保留了随机访问的能力（下标随机访问略逊与vector）。- 这种分段结构使得
deque在需要频繁修改两端的数据的场景下，具有比vector更高的性能和灵活性。 - 迭代器的设计相对复杂，需要维护跨块的信息，但也因此提供了强大的功能。
