C++ 标准库 deque
关键要点
<deque>是 C++ STL 中的双端队列，支持高效的头尾插入和删除操作，同时提供随机访问功能。- 研究表明，它适合需要频繁头尾操作且需要随机访问的场景，与
std::vector和std::list各有优劣。 - 证据显示，其元素存储在非连续内存中，动态调整大小，无需预先指定容量。
简介
<deque>（双端队列）是 C++ 标准库中的一个容器，允许在队列的两端高效地插入和删除元素，同时支持像数组一样的随机访问。以下是其主要特点和使用方法的详细讲解，适合初学者和进阶者参考。
主要特点
- 双端操作：可以在头部和尾部快速插入或删除元素，时间复杂度为 O(1)。
- 随机访问：支持通过索引或迭代器快速访问任意位置的元素，时间复杂度为 O(1)。
- 动态大小：可以根据需要自动扩展或收缩，无需预先指定容量。
- 非连续存储：元素存储在分段的连续空间中，不保证内存连续性，因此不能使用指针偏移访问。
使用方法
要使用 <deque>，需要包含头文件 <deque>。以下是常见操作：
- 创建：
std::deque<int> d;（创建空队列）或std::deque<int> d(10, 5);（创建 10 个值为 5 的元素）。 - 插入和删除：
push_back和push_front用于尾部和头部插入，pop_back和pop_front用于删除。 - 访问：使用
front()获取第一个元素，back()获取最后一个元素，或通过索引d[i]访问。 - 遍历：可以使用迭代器（如
begin()和end()）或范围 for 循环遍历。
适用场景
<deque> 适合需要频繁在头尾操作且需要随机访问的场景，例如某些算法实现或队列管理。
详细报告
引言
C++ 标准库中的 <deque> 是双端队列（double-ended queue）的实现，它是 C++ STL（标准模板库）的一部分。<deque> 支持在队列的两端（头部和尾部）高效地进行插入和删除操作，同时也支持随机访问。以下是对 <deque> 的详细讲解，包括其主要特点、使用方法以及与其他容器的比较，旨在为用户提供全面的中文讲解。
背景与定义
<deque> 是 C++ 标准库中的序列容器，其模板定义在头文件 <deque> 中。它基于分段的连续空间实现，允许在逻辑上表现为连续的线性结构，但实际内存中各段空间可能不连续。<deque> 的全称是 double-ended queue，翻译过来是双端队列，也有人称之为双向队列，这两个名称都可以表示该数据结构。
主要特点
以下是 <deque> 的核心特点，总结自多个权威资源：
- 结构：由一段一段的固定大小的连续空间构成，整体逻辑上表现为连续，但内存中不保证连续性。
- 双端操作高效：在头部和尾部插入或删除元素的时间复杂度为 O(1)，如
push_front、push_back、pop_front、pop_back。 - 随机访问支持：支持通过索引或迭代器快速访问任意位置的元素，时间复杂度为 O(1)，类似于数组。
- 动态大小：可以根据需要动态调整大小，无需预先指定容量，自动扩展或收缩。
- 内存管理：相比
std::vector，扩展时不需要移动已有元素，因此在某些场景下更高效；但不像std::vector那样保证连续存储。 - 迭代器和引用稳定性：在头部或尾部插入或删除元素时，迭代器和引用的有效性保持不变；但在中间位置的操作（如
insert、erase）可能会使迭代器和引用失效。
以下表格总结了 <deque> 的主要特性对比：
| 特性 | 描述 |
|---|---|
| 内存使用 | 非连续存储，分段管理，扩展时无需移动元素 |
| 头尾操作效率 | O(1)，高效 |
| 随机访问效率 | O(1)，支持索引访问 |
| 中间操作效率 | 插入/删除效率较低，需移动元素 |
| 迭代器稳定性 | 头尾操作不影响迭代器，中部操作可能失效 |
使用方法
<deque> 的使用方法包括创建实例和调用各种成员函数。以下是常见创建方式：
- 空队列：
std::deque<int> d; - 包含 N 个默认值元素：
std::deque<int> d(10);// 10 个元素，默认值为 0（对于 int 类型） - 包含 N 个指定值元素：
std::deque<int> d(10, 5);// 10 个元素，每个值为 5 - 拷贝构造：
std::deque<int> d2(d1);// 从现有 deque 拷贝 - 从数组创建：
int a[] = {1,2,3,4,5}; std::deque<int> d(a, a+5);// 从数组范围初始化
关键成员函数
<deque> 提供了多种成员函数，涵盖元素访问、修改和算法支持。以下是部分重要函数的说明：
| 函数名 | 描述 |
|---|---|
front() | 返回第一个元素的引用 |
back() | 返回最后一个元素的引用 |
push_front() | 在列表开头添加元素 |
push_back() | 在列表尾部添加元素 |
pop_front() | 移除第一个元素 |
pop_back() | 移除最后一个元素 |
insert() | 在指定位置插入元素 |
erase() | 删除指定位置的元素 |
empty() | 检查队列是否为空，返回布尔值 |
size() | 返回当前元素数量 |
clear() | 清空队列 |
at() | 通过索引访问元素，支持越界检查 |
operator[] | 通过索引访问元素，无越界检查 |
例如，使用 push_front 和 push_back 可以分别在头部和尾部添加元素：
- 示例：
d.push_front(0); d.push_back(2);// 结果为 {0, …, 2}
insert 用于在指定位置插入元素，例如：
- 示例：
d.insert(d.begin() + 1, 1);// 在第二个位置插入 1
遍历方法
<deque> 支持多种遍历方式：
- 迭代器：使用
begin()和end()遍历整个队列。- 示例：
for (auto it = d.begin(); it != d.end(); ++it) { /* 操作 */ }
- 示例：
- 索引：使用
operator[]或at()通过索引访问。- 示例：
for (size_t i = 0; i < d.size(); ++i) { /* 操作 */ }
- 示例：
- 范围 for 循环：C++11 及以上支持。
- 示例：
for (const auto& elem : d) { /* 操作 */ }
- 示例：
示例代码
以下是一个简单的示例，展示了 <deque> 的基本操作：
#include <deque>
#include <iostream>
int main() {
std::deque<int> d;
// 插入元素
d.push_back(1);
d.push_front(0);
d.push_back(2);
// 访问元素
std::cout << "Front: " << d.front() << std::endl;
std::cout << "Back: " << d.back() << std::endl;
// 遍历元素
for (const auto& elem : d) {
std::cout << elem << " ";
}
std::cout << std::endl;
// 删除元素
d.pop_front();
d.pop_back();
// 检查大小
std::cout << "Size: " << d.size() << std::endl;
return 0;
}
与其他容器的比较
<deque> 与其他容器（如 std::vector 和 std::list）有显著差异：
- 与
std::vector：- 相似之处：都支持随机访问和动态大小。
- 区别：
std::vector的元素在连续内存中，适合需要连续存储或频繁中间操作的场景；<deque>支持高效的头部操作，但不保证连续存储。 - 选择：如果需要频繁在头部和尾部操作，
<deque>更合适；否则，std::vector通常更高效。
- 与
std::list：<deque>支持随机访问，但中间插入和删除效率较低（需要移动元素）。std::list不支持随机访问，但中间插入和删除更高效（双向链表）。- 选择：如果需要频繁中间操作，
std::list更合适；如果需要随机访问，<deque>更合适。
研究表明，当需要频繁头尾操作且需要随机访问时，<deque> 是更优的选择，尤其在内存敏感的场景下。
适用场景
<deque> 适合以下场景：
- 需要频繁在队列两端插入或删除元素，例如某些算法实现或队列管理。
- 需要快速访问任意位置元素，同时又需要头尾操作的高效性。
- 对比
std::vector，当连续内存不是必须时，<deque>的分块存储可能更适合。
例如，在实现一个需要快速头尾操作的队列时，<deque> 可能比 vector 或 deque 更合适，但如果需要按索引访问元素，则应选择其他容器。
结论
<deque> 是 C++ STL 中一个功能强大的容器，特别适合需要频繁头尾操作且需要随机访问的场景。尽管它不支持像 std::vector 那样的连续存储，但其设计目标是提供高效的双端操作和随机访问，广泛应用于算法实现和其他需要线性遍历的场景。
参考资料
本报告基于以下资源整理，供进一步阅读：