[c++]deque容器详解-编程阁

求一个关注不过分吧？（看在文章这么精品的份上）

1. 概述

deque（双端队列，double-ended queue）是序列容器，支持在头尾两端高效地插入和删除元素。
元素在内存中不是连续存储（与vector不同），但依然支持随机访问（通过下标或at()）。
位于<deque>头文件，命名空间std。

cpp

#include <deque> using namespace std;

核心特点：

头尾插入/删除O(1)（摊销常数时间）。
中间插入/删除O(n)（需要移动元素）。
支持随机访问（下标[]或at()），常数时间 O(1)。
内存布局：通常由一段段连续的缓冲区组成，类似一个分块的数组。
没有reserve()/capacity()的概念（与vector不同）。
迭代器比vector复杂，但使用方式类似。

2. 声明与初始化

方式	说明	示例
`deque<T> dq;`	空 deque	`deque<int> dq;`
`deque<T> dq(n);`	包含 n 个值初始化的元素	`deque<int> dq(10);`
`deque<T> dq(n, val);`	包含 n 个值为 val 的元素	`deque<int> dq(5, 3);`// [3,3,3,3,3]
`deque<T> dq{1,2,3};`(C++11)	列表初始化	`deque<int> dq{1,2,3};`
`deque<T> dq(begin, end);`	迭代器区间构造	`deque<int> dq(v.begin(), v.end());`
`deque<T> dq(other);`	拷贝构造	`deque<int> dq2(dq1);`
`deque<T> dq(move(other));`	移动构造（C++11）	`deque<int> dq2(move(dq1));`

cpp

deque<int> d1; // 空 deque<int> d2(10); // 10个0 deque<int> d3(5, 100); // 5个100 deque<int> d4 = {1,2,3,4,5}; // 列表初始化 vector<int> v = {10,20,30}; deque<int> d5(v.begin(), v.end()); // {10,20,30}

3. 常用操作

3.1 大小与状态

函数	说明
`size()`	元素个数
`empty()`	是否为空
`max_size()`	最大可能容纳的元素个数
`resize(n, val)`	改变大小为 n，新元素用 val 填充（默认值初始化）

注意：deque没有capacity()和reserve()，因为其内存不是连续的单一数组。

3.2 插入元素

函数	说明	时间复杂度
`push_back(val)`	尾部插入	摊销 O(1)
`push_front(val)`	头部插入	摊销 O(1)
`pop_back()`	删除尾部元素	O(1)
`pop_front()`	删除头部元素	O(1)
`insert(pos, val)`	在迭代器 pos 前插入 val	O(n)
`insert(pos, n, val)`	插入 n 个 val	O(n)
`insert(pos, begin, end)`	插入区间	O(n)
`emplace_back(args...)`(C++11)	尾部原位构造	摊销 O(1)
`emplace_front(args...)`(C++11)	头部原位构造	摊销 O(1)
`emplace(pos, args...)`	在 pos 前原位构造	O(n)

cpp

deque<int> dq = {2, 3}; dq.push_front(1); // 头部插入 1 → {1,2,3} dq.push_back(4); // 尾部插入 4 → {1,2,3,4} dq.pop_front(); // 删除头部 → {2,3,4} dq.pop_back(); // 删除尾部 → {2,3} dq.insert(dq.begin() + 1, 99); // 在索引1前插入99 → {2,99,3} dq.emplace_front(0); // 头部构造0 → {0,2,99,3}

3.3 删除元素

函数	说明	时间复杂度
`erase(pos)`	删除迭代器指向的元素，返回下一个元素的迭代器	O(n)
`erase(first, last)`	删除区间，返回 last	O(n)
`clear()`	清空所有元素	O(n)

cpp

dq.erase(dq.begin()); // 删除第一个元素 dq.erase(dq.begin(), dq.begin()+2); // 删除前两个元素 dq.clear(); // 清空

3.4 元素访问

函数	说明
`operator[]`	下标访问，不检查越界
`at()`	下标访问，检查越界（抛`out_of_range`）
`front()`	返回首元素引用
`back()`	返回尾元素引用

cpp

deque<int> dq = {10,20,30,40}; cout << dq[0]; // 10 cout << dq.at(1); // 20 dq.front() = 100; // 修改首元素 dq.back() = 400; // 修改尾元素

3.5 迭代器

deque提供随机访问迭代器，支持+、-、++、--、[]等操作。

函数	说明
`begin()`/`end()`	正向迭代器
`rbegin()`/`rend()`	反向迭代器
`cbegin()`/`cend()`	常量正向迭代器

cpp

for (auto it = dq.begin(); it != dq.end(); ++it) cout << *it << " "; for (int x : dq) cout << x << " "; // 范围 for for (auto rit = dq.rbegin(); rit != dq.rend(); ++rit) // 反向遍历

3.6 其他操作

assign(n, val)：替换为 n 个 val
assign(begin, end)：替换为区间内容
swap(other)：交换两个 deque 的内容（O(1)）
比较操作符（==,!=,<,<=,>,>=）：按字典序比较元素

cpp

dq.assign(5, 10); // 5个10 dq1.swap(dq2); // 交换内容 if (dq1 == dq2) { ... }

4. deque 与 vector 的对比

特性	deque	vector
内存布局	分段连续（多个缓冲区）	单个连续数组
头部插入/删除	O(1)高效	O(n) 低效（需移动所有元素）
尾部插入/删除	O(1) 高效	均摊 O(1) 高效
中间插入/删除	O(n)	O(n)
随机访问	O(1) 支持	O(1) 支持（可能稍快）
内存重分配	无需整体重新分配	扩容时可能重新分配并移动全部元素
`reserve()`/`capacity()`	不支持	支持
迭代器失效规则	更复杂（见后文）	插入可能使全部迭代器失效
内存开销	稍高（维护分段指针）	较低（仅连续内存）

选择建议：

只需要在尾部操作 →vector（更简洁、内存更紧凑、随机访问可能更快）。
需要在头尾两端频繁操作 →deque（更高效）。
需要在头部操作且次数不多 → 两者都可，但vector的insert在头部会 O(n)，可能成为瓶颈。
对内存连续性有要求（如传给 C 风格数组） → 只能用vector（deque无法保证连续内存）。

5. 性能与内存

操作	时间复杂度	说明
头尾插入/删除	摊销 O(1)	常数时间（实际可能稍慢于 vector 的尾部操作）
中间插入/删除	O(n)	移动元素
随机访问	O(1)	常数时间，但比 vector 慢一点点（需计算块索引）
遍历	O(n)	逐元素访问

内存特点：

deque通常由若干固定大小的块（如 512 字节）组成，每次分配新块时不会导致已有元素移动。
因此没有“容量”概念，也不需要reserve()。
内存占用略高：需要维护一个中控器（map）来指向各个块。

6. 迭代器失效规则

相比vector，deque的迭代器失效规则更复杂，但总体上更稳定：

操作	迭代器失效情况
在头部或尾部插入 (`push_front`/`push_back`)	所有迭代器失效（因为可能引起中控器重新分配？实际标准：`deque`的`push_front`/`push_back`不会使任何已有元素的引用失效，但迭代器可能失效。具体：C++标准说插入操作会使所有迭代器失效，但引用仍然有效。不同实现有差异，最安全的假设是迭代器都会失效，但引用和指针不会失效，除非插入导致中控器重新分配。为安全编程，插入后应重新获取迭代器。）
在中间插入 (`insert`)	所有迭代器失效
删除元素 (`erase`、`pop_front`/`pop_back`)	被删除元素以及之后的所有迭代器失效（标准规定`erase`会使指向被删除元素及其后元素的迭代器失效）

经验法则：在修改deque结构后（插入/删除），尽量重新获取迭代器，不要依赖旧的迭代器。

7. 完整示例

cpp

#include <iostream> #include <deque> #include <algorithm> using namespace std; int main() { // 1. 初始化 deque<int> dq = {10, 20, 30, 40}; // 2. 头尾操作 dq.push_front(5); // {5,10,20,30,40} dq.push_back(50); // {5,10,20,30,40,50} dq.pop_front(); // {10,20,30,40,50} dq.pop_back(); // {10,20,30,40} // 3. 随机访问 cout << "First: " << dq.front() << ", Last: " << dq.back() << endl; cout << "Index 2: " << dq[2] << endl; // 30 cout << "Size: " << dq.size() << endl; // 4. 中间插入 auto it = dq.begin() + 2; dq.insert(it, 25); // 在索引2前插入25 → {10,20,25,30,40} // 5. 遍历 cout << "Elements: "; for (int x : dq) cout << x << " "; cout << endl; // 6. 删除指定值（使用 erase-remove 惯用法） dq.erase(remove(dq.begin(), dq.end(), 25), dq.end()); // 删除所有25 // 7. 范围遍历（反向） cout << "Reverse: "; for (auto rit = dq.rbegin(); rit != dq.rend(); ++rit) cout << *rit << " "; cout << endl; // 8. 清空 dq.clear(); cout << "After clear, empty: " << (dq.empty() ? "yes" : "no") << endl; // 9. 使用 emplace_front 构造复杂对象 deque<pair<int, string>> dqs; dqs.emplace_front(1, "one"); // 避免临时对象 dqs.emplace_back(2, "two"); for (const auto& p : dqs) cout << p.first << " -> " << p.second << endl; return 0; }

输出示例：

text

First: 10, Last: 40 Index 2: 30 Size: 4 Elements: 10 20 25 30 40 Reverse: 40 30 20 10 After clear, empty: yes 1 -> one 2 -> two

8. 常见陷阱与注意事项

deque没有reserve()：无法预分配内存，但头尾插入一般不会导致大量元素拷贝。
随机访问性能略低于vector：因为需要计算块索引和偏移，但通常差异不大。
中间插入/删除很慢：与vector一样为 O(n)，不要误以为双端队列中间操作也很快。
迭代器失效要注意：插入或删除后，尽量重新获取迭代器，避免使用旧迭代器。
内存占用：deque可能比vector多占用一些内存，尤其是元素数量较大时。
deque<bool>不存在特化：没有vector<bool>那样的位压缩问题，因此deque<bool>的行为是正常的。
与vector的互换场景：如果你当前使用vector并在头部频繁插入，考虑改用deque；如果只需要尾部操作且对内存连续性有要求（如调用 C 函数期望数组），则继续用vector。