C++ deque容器原理双端队列数据结构-C++-PHP中文网

deque在两端高效插入删除且支持随机访问，适用于需频繁首尾操作并索引访问的场景，其通过分块存储和指针地图实现O(1)首尾增删与O(1)随机访问，相比vector避免了前端移动开销，相比list保留了索引能力，但需注意缓存局部性差、内存开销大及中间操作导致迭代器失效等问题，最佳实践是明确需求、避免中间修改、理解失效规则并合理预热结构。

c++ deque容器原理双端队列数据结构

C++中的

std::deque

登录后复制

（双端队列）容器，其核心原理在于它不是像

std::vector

登录后复制

那样使用单一的连续内存块，而是通过管理一系列固定大小的内存块来实现数据存储。这种设计让它能在两端（前端和后端）进行高效的插入和删除操作，同时还能保持对元素的随机访问能力。它巧妙地平衡了

vector

登录后复制

的随机访问优势和

std::list

登录后复制

的链表式灵活插入删除特性。

std::deque

登录后复制

，作为C++标准库中的一个序列容器，它的内部结构设计得相当精巧。它并没有将所有元素存储在一个巨大的、连续的内存区域里，那样的话，在前端插入或删除元素时，会导致大量元素的移动，效率会很低。相反，

deque

登录后复制

采取了一种“分而治之”的策略：它将数据分散存储在多个较小的、固定大小的内存块中。这些内存块本身是连续的，但它们在整体内存空间中可能不是连续排列的。为了管理这些分散的内存块，

deque

登录后复制

内部维护了一个“地图”（map），这个“地图”本质上是一个指针数组，数组的每个元素都指向一个数据块。当我们需要在

deque

登录后复制

的两端添加或删除元素时，如果当前的数据块还有空间，操作就直接在当前块内完成；如果当前块已满或已空，

deque

登录后复制

就会在“地图”中分配或释放一个新的数据块。这种机制确保了

push_front

登录后复制

、

push_back

登录后复制

、

pop_front

登录后复制

和

pop_back

登录后复制

操作的平均时间复杂度为O(1)。同时，由于“地图”的存在，

deque

登录后复制

依然能实现O(1)的随机访问，因为它可以通过索引快速定位到对应的内存块，然后在块内进行偏移访问。

C++

deque

登录后复制

与

vector

登录后复制

、

list

登录后复制

相比，在哪些场景下更具优势？

选择

deque

登录后复制

而非

vector

登录后复制

或

list

登录后复制

，通常是基于对特定操作性能需求的权衡。在我看来，

deque

登录后复制

最闪光的时刻，是在你既需要

vector

登录后复制

那样的随机访问能力，又频繁需要在两端进行增删操作时。

首先，与

std::vector

登录后复制

相比，

deque

登录后复制

的优势在于其前端操作效率。

vector

登录后复制

在尾部添加元素（

push_back

登录后复制

）非常高效，通常是分摊O(1)，但如果在头部插入或删除元素（

insert

登录后复制

到

begin()

登录后复制

，

erase

登录后复制

从

begin()

登录后复制

），则需要移动其后所有元素，导致O(N)的性能开销。想象一下，一个庞大的

vector

登录后复制

，每次都在头部插入新数据，那简直是性能灾难。而

deque

登录后复制

的

push_front

登录后复制

和

pop_front

登录后复制

都是O(1)的，这对于实现双端队列、任务调度器等需要两端高效操作的场景来说，是决定性的优势。当然，如果你的应用只涉及尾部操作，

vector

登录后复制

由于其更好的缓存局部性，通常会比

deque

登录后复制

表现得略好。

立即学习“C++免费学习笔记（深入）”；

其次，与

std::list

登录后复制

相比，

deque

登录后复制

的优势在于其随机访问能力。

list

登录后复制

是基于双向链表实现的，它在任何位置插入或删除元素都是O(1)的，这一点非常灵活。但链表的致命弱点是它不支持随机访问，要访问第N个元素，你必须从头或尾开始遍历N次，即O(N)的时间复杂度。这对于需要通过索引快速访问元素的场景是不可接受的。

deque

登录后复制

则不同，它通过内部的“地图”结构，能够以O(1)的时间复杂度实现随机访问，尽管比

vector

登录后复制

的单次内存地址计算略复杂，但依然是常数时间。所以，当你的应用需要在两端高效操作，并且还需要根据索引快速查找或修改元素时，

deque

登录后复制

是当之无愧的赢家。比如，你可能正在实现一个需要快速响应新事件（

push_front

登录后复制

或

push_back

登录后复制

），同时又需要偶尔检查特定历史事件（随机访问）的日志系统，

deque

登录后复制

就能很好地胜任。

简而言之，如果你发现自己在使用

vector

登录后复制

时频繁地在头部进行插入/删除操作，或者在使用

list

登录后复制

时又苦于没有随机访问能力，那么，是时候考虑

deque

登录后复制

了。

deque

登录后复制

的内存管理机制是怎样的，它如何实现高效的两端操作和随机访问？

deque

登录后复制

的内存管理机制是其性能特性的基石，理解这一点对于正确使用它至关重要。它巧妙地规避了单一连续内存块的局限性，同时又保留了部分连续存储的优点。

deque

登录后复制

的内部结构，可以想象成一个“中央调度中心”（我们称之为

map

登录后复制

，实际上是一个指向指针的数组）管理着一系列“数据仓库”（实际存储元素的内存块）。

分块存储（Block-based Storage）：
```
deque
```
登录后复制
不会一次性分配一大块连续内存来存放所有元素。相反，它会分配多个固定大小的内存块。这些内存块是独立分配的，它们在物理内存中不一定是连续的。每个内存块内部的元素是连续存储的。例如，一个
```
deque
```
登录后复制
可能包含三个内存块，第一个块存放元素0-99，第二个块存放元素100-199，第三个块存放元素200-299。
“地图”（Map of Pointers）： 为了管理这些分散的内存块，
```
deque
```
登录后复制
内部有一个核心数据结构，通常是一个动态数组，这个数组的每个元素都是一个指针，指向一个实际存储数据的内存块。这个“地图”本身是连续的。当
```
deque
```
登录后复制
需要扩展时，如果某个数据块已满，它会分配一个新的数据块，并将其指针添加到“地图”中。如果“地图”本身也满了，它会像
```
vector
```
登录后复制
一样，重新分配更大的“地图”并拷贝旧的指针，但这比拷贝所有数据元素要轻量得多。
高效的两端操作（
```
O(1)
```
登录后复制
）：
- push_front()
  登录后复制
  /
  pop_front()
  登录后复制
  ：当在前端插入元素时，
```
deque
```
  登录后复制
  会检查最前面的数据块是否还有空余空间。如果有，就直接在块内插入，这只需要调整一个内部指针。如果没有，
```
deque
```
  登录后复制
  会分配一个新的数据块，并将其指针插入到“地图”的前端，然后将元素放入这个新块。这整个过程，无论是调整指针还是分配新块，通常都是常数时间操作。
```
pop_front()
```
  登录后复制
  也类似，只是反向操作。
- push_back()
  登录后复制
  /
  pop_back()
  登录后复制
  ：同样地，这些操作会在最末尾的数据块进行。如果块有空间，直接操作。如果没有，就分配新块并将其指针添加到“地图”的末尾。这些也是常数时间操作。
随机访问（
```
O(1)
```
登录后复制
）：这是
```
deque
```
登录后复制
的另一个强大之处。尽管数据不完全连续，但通过“地图”，
```
deque
```
登录后复制
依然能实现常数时间的随机访问。假设我们要访问
```
deque
```
登录后复制
中索引为
```
i
```
登录后复制
的元素：
- ```
deque
```
  登录后复制
  首先会根据
```
i
```
  登录后复制
  和每个数据块的大小（
```
block_size
```
  登录后复制
  ）计算出这个元素位于哪个数据块：
```
block_index = i / block_size
```
  登录后复制
  。
- 然后，它会计算出这个元素在该数据块中的偏移量：
```
offset_in_block = i % block_size
```
  登录后复制
  。
- 接着，
```
deque
```
  登录后复制
  通过“地图”找到
```
map[block_index]
```
  登录后复制
  ，这个指针指向了目标数据块的起始地址。
- 最后，将
```
offset_in_block
```
  登录后复制
  加到这个起始地址上，就能直接访问到目标元素。这个过程涉及几次简单的算术运算和一次指针解引用，因此是O(1)的。虽然比
```
vector
```
  登录后复制
  直接通过基地址加偏移量要多几步，但本质上都是常数时间。

这种内存管理机制，使得

deque

登录后复制

在处理需要两端动态增长和收缩，同时又不能放弃随机访问的应用场景时，显得尤为高效和灵活。

Quicktools Background Remover

Picsart推出的图片背景移除工具

查看详情

在使用

deque

登录后复制

时，开发者应该注意哪些潜在的性能陷阱和最佳实践？

deque

登录后复制

虽好，但并非没有自己的脾气和需要注意的地方。作为开发者，我们需要了解它的特性，才能扬长避短，发挥其最大价值。

首先，一个常见的性能陷阱是缓存局部性。由于

deque

登录后复制

的元素被分散存储在多个不连续的内存块中，当进行全量遍历时，CPU的缓存命中率可能不如

std::vector

登录后复制

。

vector

登录后复制

的元素是紧密排列的，CPU在读取一个元素后，很有可能将后续元素也预取到缓存中，从而加速访问。而

deque

登录后复制

在跨越内存块边界时，就可能导致缓存失效，需要重新从主内存加载数据块。这并不是说

deque

登录后复制

慢，而是说在某些对缓存敏感、且需要频繁全量遍历的场景下，

vector

登录后复制

可能会展现出更好的实际性能。

其次，迭代器失效规则是另一个需要关注的点。

deque

登录后复制

的迭代器失效规则比

vector

登录后复制

复杂一些，但比

list

登录后复制

要严格。

在
```
deque
```
登录后复制
的两端插入或删除元素（
```
push_front
```
登录后复制
,
```
push_back
```
登录后复制
,
```
pop_front
```
登录后复制
,
```
pop_back
```
登录后复制
）通常不会使现有迭代器失效，除非涉及到被删除的元素本身，或者因为扩容导致内部“地图”的重新分配（这会使所有迭代器失效，但这种情况相对较少）。
然而，如果在
```
deque
```
登录后复制
的中间插入或删除元素（
```
insert
```
登录后复制
或
```
erase
```
登录后复制
操作），则会导致所有迭代器失效。这比
```
vector
```
登录后复制
的
```
push_back
```
登录后复制
可能导致所有迭代器失效要好，但不如
```
list
```
登录后复制
，因为
```
list
```
登录后复制
只有指向被删除元素的迭代器会失效。因此，如果你在循环中对
```
deque
```
登录后复制
进行中间的修改操作，务必小心处理迭代器，通常的做法是重新获取迭代器。

再者，内存开销也是一个不容忽视的因素。

deque

登录后复制

需要维护一个额外的“地图”结构，以及多个数据块。这意味着与

vector

登录后复制

相比，它有更高的内存开销。每个数据块的内部也可能存在一些未使用的空间，导致内存碎片化。对于内存极其敏感的应用，这可能是一个需要仔细权衡的因素。

那么，在使用

deque

登录后复制

时的最佳实践又有哪些呢？

明确需求： 只有当你确实需要高效的两端插入/删除并且需要随机访问时，才考虑
```
deque
```
登录后复制
。如果只需要尾部操作，
```
vector
```
登录后复制
通常是更优选择；如果只需要中间的灵活插入/删除且不需要随机访问，
```
list
```
登录后复制
可能更合适。不要盲目跟风，匹配你的容器和你的使用模式。
避免中间操作： 尽管
```
deque
```
登录后复制
支持在中间插入和删除元素，但这些操作的效率是O(N)，而且会导致所有迭代器失效。如果你的核心需求是频繁地在容器中间进行增删，那么
```
std::list
```
登录后复制
、
```
std::map
```
登录后复制
或
```
std::set
```
登录后复制
可能更适合。
理解迭代器失效： 在对
```
deque
```
登录后复制
进行任何可能改变其内部结构的操作（特别是中间的
```
insert
```
登录后复制
或
```
erase
```
登录后复制
）之后，最安全的做法是重新获取所有必要的迭代器。这可以有效避免因使用失效迭代器而导致的未定义行为。
考虑预分配（部分）：
```
deque
```
登录后复制
没有像
```
vector
```
登录后复制
那样的
```
reserve()
```
登录后复制
方法来预分配所有数据块，因为它本质上是分块存储的。但是，你可以通过构造函数传入一个初始大小，或者通过多次
```
push_back
```
登录后复制
/
```
push_front
```
登录后复制
来“预热”其内部结构，减少后续操作中数据块分配的频率。虽然不能完全避免，但可以一定程度上优化性能。