std::deque
定义在头文件 <deque> 中 |
||
template< class T, |
(1) | |
namespace pmr { template< class T > |
(2) | (自 C++17 起) |
std::deque
(双端队列)是一个索引序列容器,允许在开头和结尾快速插入和删除元素。此外,在双端队列的任一端插入和删除元素永远不会使指向其他元素的指针或引用失效。
与 std::vector 不同,双端队列的元素不是连续存储的:典型的实现使用一系列单独分配的固定大小数组,以及额外的簿记信息,这意味着双端队列的索引访问必须执行两次指针解引用,而向量的索引访问只执行一次。
双端队列的存储会根据需要自动扩展和收缩。双端队列的扩展比 std::vector 的扩展更便宜,因为它不需要将现有元素复制到新的内存位置。另一方面,双端队列通常具有较大的最小内存成本;一个只包含一个元素的双端队列必须分配其完整的内部数组(例如,在 64 位 libstdc++ 上是对象大小的 8 倍;在 64 位 libc++ 上是对象大小的 16 倍或 4096 字节,以较大者为准)。
双端队列上的常见操作的复杂度(效率)如下所示
- 随机访问 - 常数 O(1).
- 在结尾或开头插入或删除元素 - 常数 O(1).
- 插入或删除元素 - 线性 O(n).
std::deque
满足 Container、AllocatorAwareContainer、SequenceContainer 和 ReversibleContainer 的要求。
内容 |
[编辑] 模板参数
T | - | 元素的类型。
| ||||
Allocator | - | 一个分配器,用于获取/释放内存以及在该内存中构造/销毁元素。该类型必须满足 Allocator 的要求。 行为未定义(until C++20)程序格式错误(since C++20) 如果 Allocator::value_type 与 T 不相同。 |
[编辑] 迭代器失效
本节内容不完整 原因:本节中仍然存在一些不准确之处,有关更多详细信息,请参阅各个成员函数页面。 |
操作 | 失效 |
---|---|
所有只读操作。 | 从不。 |
swap、std::swap | 末尾迭代器可能失效(实现定义)。 |
shrink_to_fit、clear、insert、emplace、push_front, push_back、emplace_front、emplace_back |
总是。 |
erase | 如果在开头擦除 - 只有被擦除的元素。 如果在结尾擦除 - 只有被擦除的元素和末尾迭代器。 |
resize | 如果新大小小于旧大小 - 仅擦除元素和 尾部迭代器。 如果新大小大于旧大小 - 所有迭代器都会失效。 |
pop_front, pop_back | 到被擦除的元素。 尾部迭代器 |
[编辑] 失效说明
- 当在双端队列的任一端插入时,引用不会被 insert 和 emplace 使失效。
- push_front, push_back, emplace_front 和 emplace_back 不会使任何对双端队列元素的引用失效。
- 当在双端队列的任一端擦除时,对未擦除元素的引用不会被 erase, pop_front 和 pop_back 使失效。
- 调用 resize 并使用较小的尺寸不会使任何对未擦除元素的引用失效。
- 调用 resize 并使用较大的尺寸不会使任何对双端队列元素的引用失效。
[编辑] 成员类型
成员类型 | 定义 | ||||
value_type
|
T | ||||
allocator_type
|
Allocator | ||||
size_type
|
无符号整数类型(通常为 std::size_t) | ||||
difference_type
|
有符号整数类型(通常为 std::ptrdiff_t) | ||||
reference
|
value_type& | ||||
const_reference
|
const value_type& | ||||
pointer
|
| ||||
const_pointer
|
| ||||
iterator
|
LegacyRandomAccessIterator 到 value_type | ||||
const_iterator
|
LegacyRandomAccessIterator 到 const value_type | ||||
reverse_iterator
|
std::reverse_iterator<iterator> | ||||
const_reverse_iterator
|
std::reverse_iterator<const_iterator> |
[编辑] 成员函数
构造 deque (公有成员函数) | |
析构 deque (公有成员函数) | |
将值赋值给容器 (公有成员函数) | |
将值赋值给容器 (公有成员函数) | |
(C++23) |
将一系列值赋值给容器 (公有成员函数) |
返回关联的分配器 (公有成员函数) | |
元素访问 | |
使用边界检查访问指定元素 (公有成员函数) | |
访问指定元素 (公有成员函数) | |
访问第一个元素 (公有成员函数) | |
访问最后一个元素 (公有成员函数) | |
迭代器 | |
(C++11) |
返回指向开头的迭代器 (公有成员函数) |
(C++11) |
返回指向结尾的迭代器 (公有成员函数) |
(C++11) |
返回指向开头的反向迭代器 (公有成员函数) |
(C++11) |
返回指向结尾的反向迭代器 (公有成员函数) |
容量 | |
检查容器是否为空 (公有成员函数) | |
返回元素数量 (公有成员函数) | |
返回元素的最大可能数量 (公有成员函数) | |
(DR*) |
通过释放未使用的内存来减少内存使用量 (公有成员函数) |
修饰符 | |
清除内容 (公有成员函数) | |
插入元素 (公有成员函数) | |
(C++23) |
插入一系列元素 (公有成员函数) |
(C++11) |
就地构造元素 (公有成员函数) |
擦除元素 (公有成员函数) | |
在末尾添加元素 (公共成员函数) | |
(C++11) |
在末尾就地构造一个元素 (公共成员函数) |
(C++23) |
在末尾添加一系列元素 (公共成员函数) |
删除最后一个元素 (公共成员函数) | |
在开头插入一个元素 (公共成员函数) | |
(C++11) |
在开头就地构造一个元素 (公共成员函数) |
(C++23) |
在开头添加一系列元素 (公共成员函数) |
删除第一个元素 (公共成员函数) | |
更改存储的元素数量 (公共成员函数) | |
交换内容 (公共成员函数) |
[编辑] 非成员函数
(在 C++20 中移除)(在 C++20 中移除)(在 C++20 中移除)(在 C++20 中移除)(在 C++20 中移除)(C++20) |
按字典顺序比较两个 deque 的值(函数模板) |
专门化了 std::swap 算法 (函数模板) | |
删除满足特定条件的所有元素 (函数模板) |
推断指南 |
(自 C++17 起) |
[编辑] 注释
特性测试 宏 | 值 | Std | 特性 |
---|---|---|---|
__cpp_lib_containers_ranges |
202202L | (C++23) | 容器的范围构造和插入 |
[编辑] 示例
#include <deque> #include <iostream> int main() { // Create a deque containing integers std::deque<int> d = {7, 5, 16, 8}; // Add an integer to the beginning and end of the deque d.push_front(13); d.push_back(25); // Iterate and print values of deque for (int n : d) std::cout << n << ' '; std::cout << '\n'; }
输出
13 7 5 16 8 25
[编辑] 缺陷报告
以下更改行为的缺陷报告被追溯应用于之前发布的 C++ 标准。
DR | 应用于 | 发布的行为 | 正确行为 |
---|---|---|---|
LWG 230 | C++98 | T 不需要是 CopyConstructible(类型为 T 的元素可能无法被构造) |
T 也需要是 CopyConstructible |
[编辑] 另请参阅
适配一个容器以提供队列(FIFO 数据结构) (类模板) |