Deque
686 字
3 分钟
Deque
核心概念
- 本质：双端队列，序列容器
- 头文件：
#include <deque> - 命名空间：
std:: - 特点：支持在头部和尾部高效插入删除，支持随机访问
- 复杂度：头尾插入删除 O(1)，随机访问 O(1)，中间插入删除 O(n)
- 内存结构：由多个固定大小的块组成，不是完全连续的内存
构造函数
| 接口 | 说明 |
|---|---|
deque<T> dq; | 默认构造，创建空deque |
deque<T> dq(n); | 创建大小为n的deque，默认初始化 |
deque<T> dq(n, value); | 创建大小为n的deque，每个元素为value |
deque<T> dq(begin, end); | 用迭代器范围[begin, end)初始化 |
deque<T> dq(other_deque); | 拷贝构造 |
deque<T> dq = {a, b, c}; | 列表初始化 |
大小操作
| 接口 | 说明 |
|---|---|
dq.size() | 返回元素数量 |
dq.empty() | 检查是否为空 |
dq.resize(new_size) | 改变大小 |
dq.resize(new_size, value) | 改变大小，新增元素初始化为value |
dq.max_size() | 返回最大可能大小 |
dq.shrink_to_fit() | 请求移除未使用的容量 |
元素访问
| 接口 | 说明 |
|---|---|
dq[index] | 不检查边界访问元素 |
dq.at(index) | 检查边界访问元素 |
dq.front() | 返回第一个元素的引用 |
dq.back() | 返回最后一个元素的引用 |
修改器
| 接口 | 说明 |
|---|---|
dq.push_back(value) | 在尾部插入元素 |
dq.push_front(value) | 在头部插入元素 |
dq.pop_back() | 移除尾部元素 |
dq.pop_front() | 移除头部元素 |
dq.insert(iterator_pos, value) | 在指定位置插入元素 |
dq.insert(iterator_pos, n, value) | 在指定位置插入n个value |
dq.insert(iterator_pos, begin, end) | 在指定位置插入迭代器范围 |
dq.erase(iterator_pos) | 移除指定位置元素 |
dq.erase(iterator_first, iterator_last) | 移除迭代器范围内的元素 |
dq.clear() | 清空所有元素 |
dq.assign(n, value) | 分配n个value |
dq.assign(begin, end) | 分配迭代器范围内的元素 |
dq.swap(other_deque) | 交换两个deque的内容 |
dq.emplace_back(args...) | 在尾部就地构造元素 |
dq.emplace_front(args...) | 在头部就地构造元素 |
dq.emplace(iterator_pos, args...) | 在指定位置就地构造元素 |
迭代器
| 接口 | 说明 |
|---|---|
dq.begin() / dq.end() | 正向迭代器 |
dq.rbegin() / dq.rend() | 反向迭代器 |
dq.cbegin() / dq.cend() | 常量正向迭代器 |
dq.crbegin() / dq.crend() | 常量反向迭代器 |
注意事项
- 内存结构：deque 由多个固定大小的块组成，不是完全连续的内存
- 迭代器失效： · 在头尾插入不会使迭代器失效 · 在中间插入删除可能使所有迭代器失效
- 性能特点： · 头尾操作性能优秀 · 随机访问性能接近vector · 中间操作性能较差
- 内存开销：比vector有更高的内存开销，但比list低
- 适用场景：需要频繁在头尾进行插入删除操作的场景
常见应用场景
· 需要高效头尾操作的场景 · 滑动窗口问题 · 实现队列和栈 · 作为queue和stack的默认底层容器 · 数据流处理 · 撤销操作历史
文章分享
如果这篇文章对你有帮助，欢迎分享给更多人！
相关文章智能推荐
1
Queue
STL本质：容器适配器，先进先出（FIFO）数据结构 头文件：include 命名空间：std:: 底层容器：默认使用 deque，也可指定 list 特点：只允许在队尾插入，队头删除 复杂度：所有操作的时间复杂度都是 O(1)
2
Stack
STL本质：容器适配器，后进先出（LIFO）数据结构 头文件：include 命名空间：std:: 底层容器：默认使用 deque，也可指定 vector 或 list 特点：只允许在栈顶进行插入和删除操作 复杂度：所有操作的时间复杂度都是 O…
3
List
STL本质：双向链表容器 头文件：include 命名空间：std:: 优点：任意位置插入删除高效 O(1)，不需要连续内存 缺点：不支持随机访问，访问元素需要遍历 O(n)，内存开销较大（每个节点包含前后指针） 特点：双向迭代器，插入删除不会…
4
vector
STL本质：动态数组，大小可变 内存：连续存储空间 头文件：include 命名空间：std:: 优点：随机访问快，尾部操作高效，自动内存管理 缺点：中间插入/删除慢，内存占用可能较高
5
String
STL本质：动态字符序列，封装了字符串操作 头文件：include 命名空间：std:: 优点：自动内存管理，丰富的字符串操作，支持C风格字符串转换 底层：通常包含长度信息，不以\0作为必需结尾（但支持C风格转换）
随机文章随机推荐