命名空间
变体
操作

std::deque

来自 cppreference.com
< cpp‎ | 容器
 
 
 
 
定义在头文件 <deque>
template<

    class T,
    class Allocator = std::allocator<T>

> class deque;
(1)
namespace pmr {

    template< class T >
    using deque = std::deque<T, std::pmr::polymorphic_allocator<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 满足 ContainerAllocatorAwareContainerSequenceContainerReversibleContainer 的要求。

内容

[编辑] 模板参数

T - 元素的类型。
T 必须满足 CopyAssignableCopyConstructible 的要求。 (直到 C++11)
对元素施加的要求取决于对容器执行的实际操作。通常,要求元素类型为完整类型并满足 Erasable 的要求,但许多成员函数会施加更严格的要求。 (自 C++11 起)

[编辑]

Allocator - 一个分配器,用于获取/释放内存以及在该内存中构造/销毁元素。该类型必须满足 Allocator 的要求。 行为未定义(until C++20)程序格式错误(since C++20) 如果 Allocator::value_typeT 不相同。[编辑]

[编辑] 迭代器失效

操作 失效
所有只读操作。 从不。
swapstd::swap 末尾迭代器可能失效(实现定义)。
shrink_to_fitclearinsertemplacepush_front,
push_backemplace_frontemplace_back
总是。
erase 如果在开头擦除 - 只有被擦除的元素。

如果在结尾擦除 - 只有被擦除的元素和末尾迭代器。
否则 - 所有迭代器都会失效。

末尾迭代器何时失效是未指定的。(until C++11)

除了在容器开头擦除元素且末尾元素未擦除的情况,尾部迭代器也会失效。
元素。
(自 C++11 起)

resize 如果新大小小于旧大小 - 仅擦除元素和
尾部迭代器。

如果新大小大于旧大小 - 所有迭代器都会失效。
否则 - 不会使任何迭代器失效。

pop_front, pop_back 到被擦除的元素。

尾部迭代器
可能失效(实现定义)(直到 C++11)
也会失效。(自 C++11 起)

[编辑] 失效说明

  • 当在双端队列的任一端插入时,引用不会被 insertemplace 使失效。
  • push_front, push_back, emplace_frontemplace_back 不会使任何对双端队列元素的引用失效。
  • 当在双端队列的任一端擦除时,对未擦除元素的引用不会被 erase, pop_frontpop_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

Allocator::pointer

(直到 C++11)

std::allocator_traits<Allocator>::pointer

(自 C++11 起)
[编辑]
const_pointer

Allocator::const_pointer

(直到 C++11)

std::allocator_traits<Allocator>::const_pointer

(自 C++11 起)
[编辑]
iterator LegacyRandomAccessIteratorvalue_type[编辑]
const_iterator LegacyRandomAccessIteratorconst value_type[编辑]
reverse_iterator std::reverse_iterator<iterator>[编辑]
const_reverse_iterator std::reverse_iterator<const_iterator>[编辑]

[编辑] 成员函数

构造 deque
(公有成员函数) [编辑]
析构 deque
(公有成员函数) [编辑]
将值赋值给容器
(公有成员函数) [编辑]
将值赋值给容器
(公有成员函数) [编辑]
将一系列值赋值给容器
(公有成员函数) [编辑]
返回关联的分配器
(公有成员函数) [编辑]
元素访问
使用边界检查访问指定元素
(公有成员函数) [编辑]
访问指定元素
(公有成员函数) [编辑]
访问第一个元素
(公有成员函数) [编辑]
访问最后一个元素
(公有成员函数) [编辑]
迭代器
返回指向开头的迭代器
(公有成员函数) [编辑]
(C++11)
返回指向结尾的迭代器
(公有成员函数) [编辑]
返回指向开头的反向迭代器
(公有成员函数) [编辑]
(C++11)
返回指向结尾的反向迭代器
(公有成员函数) [编辑]
容量
检查容器是否为空
(公有成员函数) [编辑]
返回元素数量
(公有成员函数) [编辑]
返回元素的最大可能数量
(公有成员函数) [编辑]
通过释放未使用的内存来减少内存使用量
(公有成员函数) [编辑]
修饰符
清除内容
(公有成员函数) [编辑]
插入元素
(公有成员函数) [编辑]
插入一系列元素
(公有成员函数) [编辑]
(C++11)
就地构造元素
(公有成员函数) [编辑]
擦除元素
(公有成员函数) [编辑]
在末尾添加元素
(公共成员函数) [编辑]
在末尾就地构造一个元素
(公共成员函数) [编辑]
在末尾添加一系列元素
(公共成员函数) [编辑]
删除最后一个元素
(公共成员函数) [编辑]
在开头插入一个元素
(公共成员函数) [编辑]
在开头就地构造一个元素
(公共成员函数) [编辑]
在开头添加一系列元素
(公共成员函数) [编辑]
删除第一个元素
(公共成员函数) [编辑]
更改存储的元素数量
(公共成员函数) [编辑]
交换内容
(公共成员函数) [编辑]

[编辑] 非成员函数

(在 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 数据结构)
(类模板) [编辑]