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

如何计算位置

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

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更高的性能和灵活性。
• 迭代器的设计相对复杂，需要维护跨块的信息，但也因此提供了强大的功能。