deque内部实现原理是怎样的 块状数组结构优缺点解析

deque的内部实现采用分块数组结构，由多个固定大小的数据块通过指针数组（map）连接，形成逻辑连续的序列。1. 数据块是固定大小的数组，用于存储元素；2. map数组存储指向数据块的指针；3. 头尾指针标识当前逻辑起始和结束位置；4. 插入操作在头尾时分配新块并更新map，无需移动旧数据；5. 随机访问需两次指针解引用，时间复杂度为o(1)。相比vector，deque避免了频繁内存重分配，支持高效两端操作；相比list，具有更好的缓存局部性和随机访问性能。适用场景包括双端队列、滑动窗口等需要两端高效扩展的场合。迭代器失效规则介于vector和list之间：两端插入不轻易失效，但中间操作或map扩容可能导致部分或全部迭代器失效。

deque

（双端队列）的内部实现，通常采用的是一种“分块数组”或“多段数组”的结构。它不像

vector

那样在内存中连续分配一大块空间，而是由多个大小相对固定的小型动态数组（块）组成，这些小块通过一个指针数组（通常称为“map”或“control array”）来管理和连接，形成一个逻辑上连续的序列。这种设计巧妙地融合了数组的随机访问能力和链表的动态扩展灵活性，尤其擅长在两端进行高效的插入和删除操作。

解决方案

deque

的核心思想在于，它将数据分散存储在多个独立的内存块中。想象一下，你有一本厚厚的书，但不是一整页一整页地写，而是每写完一章就单独装订成一个小册子，然后把这些小册子按照顺序放在一个大盒子里。这个大盒子就是

deque

的“map”数组，里面装着指向各个小册子（数据块）的指针。

具体来说，

deque

的结构大致是这样的：

1. 数据块（Chunks/Blocks）: 每个数据块都是一个固定大小的数组，比如

   std::deque

   通常会使用一个2的幂次大小的块，比如512字节或4KB，以优化内存对齐和缓存利用率。当

   deque

   需要存储元素时，它会从这些块中分配空间。

2. 映射数组（Map Array）: 这是一个动态数组，它不存储实际的数据，而是存储指向各个数据块的指针。例如，

   map_array[i]

   会指向第

   i

   个数据块。

3. 头尾指针（Pointers/Indices）:

   deque

   内部会维护一些指针或索引，指示当前

   deque

   的逻辑起始位置（比如

   start_block_index

   ,

   start_element_index_in_block

   ）和逻辑结束位置（比如

   end_block_index

   ,

   end_element_index_in_block

   ）。

当你在

deque

的尾部

push_back

一个元素时，它会尝试将其放入当前最后一个数据块。如果该块已满，

deque

会分配一个新的数据块，并将其指针添加到映射数组的末尾，然后将新元素放入新块。类似地，

push_front

时，如果第一个数据块已满，它会分配一个新的数据块，并将其指针添加到映射数组的头部（这可能涉及到映射数组本身的扩展和元素移动），然后将新元素放入新块。

随机访问元素，例如

deque[i]

，涉及到两次指针解引用：首先通过索引

i

计算出对应的块在映射数组中的位置，然后通过该块指针和元素在块内的偏移量，找到实际的元素。这个过程虽然比

vector

多了一次指针跳转，但依然是O(1)时间复杂度。

这种分块设计的好处在于，当

deque

在两端扩展时，它不需要像

vector

那样进行大规模的内存重新分配和元素拷贝。它只需要分配一个新的小块，并更新映射数组即可。这使得

push_front

和

push_back

操作的平均时间复杂度都达到了O(1)。

deque

与

vector

、

list

相比，其性能特点和适用场景有何不同？

谈到容器，我们总会不自觉地把

deque

和

vector

、

list

放在一起比较，它们各有千秋，但

deque

的存在感似乎总是在两者之间摇摆。

从性能特点来看：

• vector

  : 内存连续，这是它最大的优势。这意味着极佳的缓存局部性，访问元素时CPU能高效预取数据，所以随机访问（

  []

  操作）和尾部添加（

  push_back

  ，均摊O(1)）速度飞快。但它的缺点也很明显：在中间插入或删除元素（O(N)），以及在头部插入元素（O(N)），都需要大量的数据移动。更要命的是，当容量不足时，它需要重新分配更大的内存空间，然后将所有旧元素拷贝过去，这个过程成本很高。

• list

  : 双向链表，内存不连续，每个元素独立分配，并带有前后指针。它的优点是插入和删除元素（无论在何处）都非常快，是O(1)操作，因为它只需要修改几个指针。但缺点也同样突出：随机访问元素是O(N)，你需要从头或尾遍历才能找到目标；缓存局部性差，因为元素可能分散在内存各处，导致CPU缓存命中率低。

• deque

  : 介于两者之间，它试图取长补短。它的随机访问是O(1)，但由于需要两次指针解引用（先到块指针，再到元素），通常会比

  vector

  略慢一点点，但比

  list

  快得多。两端插入和删除（

  push_front

  /

  push_back

  /

  pop_front

  /

  pop_back

  ）都是均摊O(1)的，这是它最突出的优势。它避免了

  vector

  频繁的内存重分配，同时比

  list

  有更好的缓存局部性（因为块内部是连续的）。不过，在中间插入或删除元素，依然是O(N)，因为它可能需要移动半个

  deque

  的数据块。

至于适用场景：

• vector

  : 你的首选容器，如果你的主要操作是尾部添加、遍历和随机访问，并且对中间插入/删除不敏感，或者数据量相对固定。它就是那个万金油。

• list

  : 当你频繁需要在容器的任意位置进行插入和删除操作，并且对随机访问性能要求不高时，

  list

  就是最佳选择。比如实现一些复杂的图算法中的邻接表，或者需要高效管理大量动态对象的场景。

• deque

  : 什么时候考虑

  deque

  呢？当你需要一个既能快速在两端扩展（像队列或栈那样），又需要保持相对快速的随机访问能力时。比如，实现一个双端队列、一个滑动窗口，或者作为其他数据结构（如某些树或图的遍历算法）的底层存储。我个人觉得，在处理日志流、任务队列，或者任何需要从两端高效处理数据的场景，

  deque

  都表现出色。

deque

在内存管理上是如何避免

vector

频繁重新分配的痛点？

vector

的内存管理方式，对于我这种追求效率的人来说，有时候确实是个“痛点”。它为了保证元素的连续存储和O(1)的随机访问，一旦当前容量不足，就得申请一块更大的新内存，然后把所有旧元素一股脑儿地复制过去，最后再释放旧内存。这个过程，尤其是当

vector

存储的是大对象或者元素数量庞大时，性能开销是相当可观的。

deque

则聪明地避开了这个坑。它的核心策略是“分而治之”。它不追求所有元素都在一块连续的内存上，而是把数据分散到多个固定大小的“块”里。当

deque

需要在两端扩展时（比如

push_back

或

push_front

），它并不会去寻找一块能容纳所有现有元素和新元素的更大内存区域，然后进行复制。

相反，它会：

1. 分配新的小块内存: 如果当前最末端或最前端的块已满，

   deque

   会直接分配一个新的数据块（通常是预设的固定大小，比如512字节或4KB），而不是一个翻倍大小的新

   deque

   总内存。

2. 更新映射数组: 这个新分配的块的指针会被添加到

   deque

   内部的“映射数组”（一个存储块指针的数组）的相应位置（头部或尾部）。

3. 放置新元素: 新元素直接放入这个新分配的块中。

这个过程的关键在于，旧的数据块和其中的元素根本不需要移动。它们仍然留在原来的内存位置。只有映射数组本身可能会因为需要存储更多块指针而进行扩展，但这个映射数组通常比实际数据小得多，其重新分配的开销也远小于

vector

的数据区重新分配。

所以，

deque

的这种“按需分配小块，并通过指针数组管理”的策略，从根本上避免了

vector

那种“全员大迁徙”式的内存重分配，从而保证了其两端操作的高效性，即使在处理大量数据时也能保持稳定的性能表现。这对我来说，是它在某些特定场景下比

vector

更有吸引力的原因。

为什么说

deque

的迭代器失效规则比

vector

复杂，但比

list

简单？

迭代器失效规则，这东西在C++容器里，有时候确实让人头疼，尤其是当你写一些复杂算法，涉及到迭代器操作时，搞不清楚就容易出bug。

deque

的迭代器失效规则，我觉得用“微妙”来形容可能更贴切，因为它确实介于

vector

的“粗暴”和

list

的“佛系”之间。

首先，让我们回顾一下：

• vector

  的迭代器失效：它的规则最简单也最“残酷”。任何可能导致

  vector

  内部内存重新分配的操作（比如

  push_back

  导致容量不足、

  insert

  、

  erase

  ），都会导致所有指向该

  vector

  元素的迭代器、指针和引用全部失效。因为元素可能已经被移动到新的内存地址了。简单粗暴，但很明确。

• list

  的迭代器失效：这是最“佛系”的。由于

  list

  的每个元素都是独立分配的，并由指针连接，所以除了指向被删除元素本身的迭代器会失效外，其他任何插入或删除操作都不会影响到现有元素的内存位置，因此它们的迭代器、指针和引用都不会失效。非常稳定。

那么

deque

呢？它有点像个“中间派”：

比

vector

更稳定（更简单）：

deque

在两端进行

push_front

或

push_back

操作时，通常不会导致所有迭代器失效。这是因为这些操作主要涉及分配新的数据块并更新映射数组，而不会移动已存在的数据块。所以，只要没有涉及到映射数组本身的重新分配（这种情况非常罕见，通常只发生在

deque

变得非常非常大，以至于映射数组也需要扩容时），或者没有在中间进行插入/删除，指向现有元素的迭代器是保持有效的。这一点比

vector

好太多了，你不用担心在

push_back

后，之前获取的迭代器就不能用了。

比

list

更复杂（不那么简单）：

deque

的迭代器并非完全免疫失效。

1. 中间插入/删除：如果在

   deque

   的中间进行

   insert

   或

   erase

   操作，那么从插入/删除点开始，到

   deque

   末尾的所有迭代器都可能失效。这是因为

   deque

   为了保持其逻辑上的连续性，需要移动数据块内的元素，或者甚至移动整个数据块以腾出空间或填补空缺。

2. 映射数组重分配：虽然罕见，但如果

   deque

   的元素数量庞大到需要扩展其内部的“映射数组”本身时，所有迭代器都会失效。这类似于

   vector

   的整体重分配，但发生的频率要低得多。

所以，我的理解是，

deque

的迭代器失效规则是

vector

和

list

之间的一个折衷。它在两端操作时提供了比

vector

更好的迭代器稳定性，但在中间操作时，它仍然需要你小心处理迭代器，不如

list

那样“无忧无虑”。在使用

deque

时，我通常会尽量避免在循环中对中间部分进行插入或删除，或者在操作后重新获取迭代器，以避免潜在的问题。