std::deque
定义于头文件 <deque>
|
||
template< class T, |
(1) | |
namespace pmr { template <class T> |
(2) | (C++17 起) |
std::deque
( double-ended queue ,双端队列)是有下标顺序容器,它允许在其首尾两段快速插入及删除。另外,在 deque 任一端插入或删除不会非法化指向其余元素的指针或引用。
与 std::vector 相反, deque 的元素不是相接存储的:典型实现用单独分配的固定大小数组的序列,外加额外的登记,这表示下标访问必须进行二次指针解引用,与之相比 vector 的下标访问只进行一次。
deque 的存储按需自动扩展及收缩。扩张 deque 比扩张 std::vector 更优,因为它不涉及到复制既存元素到新内存位置。另一方面, deque 典型地拥有较大的最小内存开销;只保有一个元素的 deque 必须分配其整个内部数组(例如 64 位 libstdc++ 上为对象大小 8 倍; 64 位 libc++ 上为对象大小 16 倍或 4096 字节的较大者)。
deque 上常见操作的复杂度(效率)如下:
- 随机访问——常数 O(1)
- 在结尾或起始插入或移除元素——常数 O(1)
- 插入或移除元素——线性 O(n)
std::deque
满足容器 (Container) 、知分配器容器 (AllocatorAwareContainer) 、序列容器 (SequenceContainer) 和可逆容器 (ReversibleContainer) 的要求。
模板形参
T | - | 元素的类型。
| ||||
Allocator | - | 用于获取/释放内存及构造/析构内存中元素的分配器。类型必须满足分配器 (Allocator) 的要求。若 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 | 仅有指向被擦除元素者和尾后迭代器 |
非法化注意
- 从 deque 任一端插入时, insert 和 emplace 不会非法化引用。
- push_front 、 push_back 、 emplace_front 和 emplace_back 不会非法化任何到 deque 元素的引用。
- 从 deque 任一端擦除时, erase 、 pop_front 和 pop_back 不会非法化到未擦除元素的引用。
- 以较小的大小调用 resize 不会非法化任何到未擦除元素的引用。
- 以较大的大小调用 resize 不会非法化任何到 deque 元素的引用。
成员类型
成员类型 | 定义 | ||||
value_type
|
T | ||||
allocator_type
|
Allocator | ||||
size_type
|
无符号整数类型(通常是 std::size_t ) | ||||
difference_type
|
有符号整数类型(通常是 std::ptrdiff_t ) | ||||
reference
|
| ||||
const_reference
|
| ||||
pointer
|
| ||||
const_pointer
|
| ||||
iterator
|
遗留随机访问迭代器 (LegacyRandomAccessIterator) | ||||
const_iterator
|
常随机访问迭代器 | ||||
reverse_iterator
|
std::reverse_iterator<iterator> | ||||
const_reverse_iterator
|
std::reverse_iterator<const_iterator> |
成员函数
构造 deque (公开成员函数) | |
析构 deque (公开成员函数) | |
赋值给容器 (公开成员函数) | |
将值赋给容器 (公开成员函数) | |
返回相关的分配器 (公开成员函数) | |
元素访问 | |
访问指定的元素,同时进行越界检查 (公开成员函数) | |
访问指定的元素 (公开成员函数) | |
访问第一个元素 (公开成员函数) | |
访问最后一个元素 (公开成员函数) | |
迭代器 | |
(C++11) |
返回指向起始的迭代器 (公开成员函数) |
(C++11) |
返回指向末尾的迭代器 (公开成员函数) |
(C++11) |
返回指向起始的逆向迭代器 (公开成员函数) |
(C++11) |
返回指向末尾的逆向迭代器 (公开成员函数) |
容量 | |
检查容器是否为空 (公开成员函数) | |
返回容纳的元素数 (公开成员函数) | |
返回可容纳的最大元素数 (公开成员函数) | |
(C++11) |
通过释放未使用的内存减少内存的使用 (公开成员函数) |
修改器 | |
清除内容 (公开成员函数) | |
插入元素 (公开成员函数) | |
(C++11) |
原位构造元素 (公开成员函数) |
擦除元素 (公开成员函数) | |
将元素添加到容器末尾 (公开成员函数) | |
(C++11) |
在容器末尾就地构造元素 (公开成员函数) |
移除末元素 (公开成员函数) | |
插入元素到容器起始 (公开成员函数) | |
(C++11) |
在容器头部就地构造元素 (公开成员函数) |
移除首元素 (公开成员函数) | |
改变容器中可存储元素的个数 (公开成员函数) | |
交换内容 (公开成员函数) |
非成员函数
(C++20 中移除)(C++20 中移除)(C++20 中移除)(C++20 中移除)(C++20 中移除)(C++20) |
按照字典顺序比较 deque 中的值 (函数模板) |
特化 std::swap 算法 (函数模板) | |
擦除所有满足特定判别标准的元素 (函数模板) |
推导指引(C++17 起)
示例
#include <iostream> #include <deque> int main() { // 创建容纳整数的 deque std::deque<int> d = {7, 5, 16, 8}; // 从 deque 的首尾添加整数 d.push_front(13); d.push_back(25); // 迭代并打印 deque 的值 for(int n : d) { std::cout << n << '\n'; } }
输出:
13 7 5 16 8 25