Deque内部实现原理及块状数组结构优缺点解析

摘要：deque（双端队列）的内部实现原理主要基于块状数组结构。其优点在于可以方便地从两端进行插入和删除操作，具有较高的效率。块状数组也存在一些缺点，如内存分配和管理的复杂性较高，以及在处理大量数据时可能存在内存碎片化的问题。总体而言，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时，我通常会尽量避免在循环中对中间部分进行插入或删除，或者在操作后重新获取迭代器，以避免潜在的问题。

本文转载于：互联网 如有侵犯，请联系zhengruancom@outlook.com删除。
免责声明：正软商城发布此文仅为传递信息，不代表正软商城认同其观点或证实其描述。