[C++] vector对比list & deque的引出

list与vector的对比

vector与list都是STL中非常重要的序列式容器，由于两个容器的底层结构不同，导致其特性以及 应用场景不同，其主要不同如下：

[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支持高效的随机访问，这是因为它可以通过块表和块内偏移快速定位元素。

如何计算位置

对于一个给定的索引，首先需要计算它所在的块，然后计算块内的偏移量。具体计算公式如下：

1. 计算块索引：block_index = (start + index) / block_size
2. 计算块内偏移：offset = (start + index) % block_size

迭代器设计

deque的迭代器较为复杂，因为它需要封装块表、块和块内元素的位置信息。deque的迭代器通常包含以下信息：

1. 当前块指针：指向当前元素所在的块。
2. 块内指针：指向当前块中的具体位置。
3. 块表指针：指向块表中的位置。

通过这些信息，迭代器可以支持前向、后向的遍历和随机访问。当进行迭代操作时，迭代器需要处理跨块的情况，这增加了迭代器的复杂性。

总结

• deque的底层是一个分段的、动态的二维数组结构，它提供了高效的两端插入和删除操作（中间删除操作效率和**vector**一样，需要移动数据 O(N)），同时保留了随机访问的能力（下标随机访问略逊与vector）。
• 这种分段结构使得deque在需要频繁修改两端的数据的场景下，具有比vector更高的性能和灵活性。
• 迭代器的设计相对复杂，需要维护跨块的信息，但也因此提供了强大的功能。