deque的原理与实现（了解即可）

目录

一、deque的基本概念

主要特点：

二、deque的底层实现原理

1、底层结构

2、内存布局示例

3、扩容机制

三、deque的迭代器设计

四、deque的优缺点分析

优点（相比其他容器）：

缺点：

五、deque的应用场景

为什么不是vector或list？

六、deque 的基本操作

1、创建和初始化 deque

2、元素访问

3、修改 deque

4、容量操作

七、deque 的迭代器

八、deque 的性能分析

九、示例：使用 deque 实现滑动窗口最大值

十、总结

---

一、deque的基本概念

        deque（双端队列，全称 double-ended queue）是一种双开口的"连续"空间数据结构，是 C++ STL 中的一个独立容器，而不是容器适配器。它允许在队列的前端和后端高效地进行插入和删除操作，时间复杂度为O(1)。

        与 vector 相比，deque 在头部插入和删除元素时性能更好；与 list 相比，deque 支持随机访问，但在中间位置插入和删除元素效率较低。

主要特点：

• 双端操作：支持push_front、push_back、pop_front、pop_back，可以在头部和尾部高效地插入和删除元素

• 假象的连续空间：实际由多个分段连续的小空间组成

• 动态扩展：不需要像vector那样搬移大量元素，可以根据需要自动扩展和收缩

• 较高空间利用率：相比list不需要存储额外指针字段

• 随机访问：支持通过下标直接访问元素

• 不连续存储：元素并非存储在连续的内存块中（与 vector 不同）

• 迭代器支持：提供随机访问迭代器

---

二、deque的底层实现原理

        deque 通常实现为一系列固定大小的数组（称为块或缓冲区），这些数组的指针被存储在一个中央控制结构中（通常是数组）。这种实现方式使得：

• 在两端扩展和收缩都很高效

• 随机访问需要先计算元素所在的块，然后再计算块内的偏移

• 内存使用比 vector 更分散，但比 list 更紧凑

1、底层结构

        deque并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，deque的底层实现类似于一个动态的二维数组，但更为复杂。它由以下几个关键部分组成：

1. map（中控器）：一个指针数组，每个元素指向一块连续的内存块（称为缓冲区或节点）

2. 缓冲区（node）：实际存储数据的连续内存块

3. 迭代器：包含四个指针：

   • cur：当前元素指针

   • first：当前缓冲区的起始位置

   • last：当前缓冲区的结束位置

   • node：指向map中对应的指针

     

2、内存布局示例

当执行以下操作时：

deque<int> deq;
deq.push_back(0);
deq.push_back(1);
deq.push_back(2);

内存可能布局为：

3、扩容机制

当map使用率满载时，会执行reallocate_map()：

1. 找一块更大的空间

2. 将原有指针复制到新map的中间位置

3. 释放旧map

这种策略保持了deque两端的高效扩展能力。

---

三、deque的迭代器设计

deque的迭代器比普通迭代器复杂，因为它需要维护"假象连续"的特性：

• 当迭代器到达当前缓冲区边界时，需要跳转到下一个/上一个缓冲区

• 迭代器需要知道当前缓冲区的位置和边界

---

四、deque的优缺点分析

优点（相比其他容器）：

• vs vector：

  • 头部操作高效（O(1) vs O(n)）

  • 扩容时不需要搬移大量元素

• vs list：

  • 更高的空间利用率（不需要存储指针）

  • 更好的缓存局部性（数据局部连续）

缺点：

• 随机访问性能不如vector（需要计算缓冲区位置）

• 遍历效率低（频繁检查边界）

• 中间插入/删除效率低（需要移动元素）

---

五、deque的应用场景

虽然deque本身应用不多，但它是STL中stack和queue的理想底层容器，因为：

1. stack和queue不需要遍历：避开了deque遍历效率低的缺陷

2. 高效的双端操作：正好满足stack和queue的操作需求，需要频繁在两端添加或删除元素

3. 内存效率高：比list更适合作为基础容器

4. 扩展高效：比vector在频繁push/pop时性能更好

5. 需要随机访问，但不需要频繁在中间插入/删除

6. 实现队列或双端队列数据结构

7. 作为优先级队列的底层容器（std::priority_queue 默认使用 vector，但也可以指定 deque）

为什么不是vector或list？

• vector：头部操作效率低，扩容成本高

• list：空间利用率低，缓存不友好

---

六、deque 的基本操作

1、创建和初始化 deque

#include <deque>
#include <iostream>int main() {// 空 dequestd::deque<int> d1;// 包含 5 个元素，每个初始化为 0std::deque<int> d2(5);// 包含 5 个元素，每个初始化为 10std::deque<int> d3(5, 10);// 通过初始化列表std::deque<int> d4 = {1, 2, 3, 4, 5};// 通过迭代器范围int arr[] = {6, 7, 8, 9, 10};std::deque<int> d5(arr, arr + 5);// 拷贝构造函数std::deque<int> d6(d5);return 0;
}

2、元素访问

std::deque<int> d = {1, 2, 3, 4, 5};// 使用下标运算符（不检查边界）
int a = d[2];  // 3// 使用 at 方法（检查边界，越界抛出 std::out_of_range 异常）
int b = d.at(3);  // 4// 访问第一个和最后一个元素
int front = d.front();  // 1
int back = d.back();    // 5

3、修改 deque

std::deque<int> d = {1, 2, 3};// 在尾部添加元素
d.push_back(4);  // {1, 2, 3, 4}// 在头部添加元素
d.push_front(0);  // {0, 1, 2, 3, 4}// 删除尾部元素
d.pop_back();  // {0, 1, 2, 3}// 删除头部元素
d.pop_front();  // {1, 2, 3}// 在指定位置插入元素
auto it = d.begin() + 1;
d.insert(it, 10);  // {1, 10, 2, 3}// 删除指定位置的元素
it = d.begin() + 2;
d.erase(it);  // {1, 10, 3}// 清空 deque
d.clear();  // {}

4、容量操作

std::deque<int> d = {1, 2, 3};// 获取元素数量
size_t size = d.size();  // 3// 检查是否为空
bool empty = d.empty();  // false// 改变大小
d.resize(5);      // {1, 2, 3, 0, 0}
d.resize(2);      // {1, 2}
d.resize(4, 10);  // {1, 2, 10, 10}

---

七、deque 的迭代器

deque 提供随机访问迭代器，支持所有随机访问迭代器操作：

std::deque<int> d = {1, 2, 3, 4, 5};// 使用迭代器遍历
for (auto it = d.begin(); it != d.end(); ++it) {std::cout << *it << " ";
}
std::cout << std::endl;// 使用反向迭代器
for (auto rit = d.rbegin(); rit != d.rend(); ++rit) {std::cout << *rit << " ";
}
std::cout << std::endl;// 随机访问
auto it = d.begin() + 3;
std::cout << *it << std::endl;  // 4

---

八、deque 的性能分析

操作	时间复杂度
随机访问	O(1)
在头部或尾部插入/删除	O(1)
在中间位置插入/删除	O(n)
查找元素	O(n)

---

九、示例：使用 deque 实现滑动窗口最大值

#include <deque>
#include <vector>
#include <iostream>std::vector<int> maxSlidingWindow(const std::vector<int>& nums, int k) {std::vector<int> result;std::deque<int> dq;  // 存储索引for (int i = 0; i < nums.size(); ++i) {// 移除超出窗口范围的元素if (!dq.empty() && dq.front() == i - k) {dq.pop_front();}// 移除所有小于当前元素的元素while (!dq.empty() && nums[dq.back()] < nums[i]) {dq.pop_back();}// 添加当前元素dq.push_back(i);// 当窗口形成时，记录最大值if (i >= k - 1) {result.push_back(nums[dq.front()]);}}return result;
}int main() {std::vector<int> nums = {1, 3, -1, -3, 5, 3, 6, 7};int k = 3;auto result = maxSlidingWindow(nums, k);for (int num : result) {std::cout << num << " ";}// 输出: 3 3 5 5 6 7return 0;
}

---

十、总结

deque是一种折衷设计的数据结构，它：

• 结合了vector和list的部分优点

• 通过复杂迭代器维护"假象连续"的特性

• 特别适合作为只需要双端操作的容器的底层实现

• 在实际应用中，除非特定需求，通常优先考虑vector或list