std::deque

 

C++

编译器支持

自立实现与有宿主实现

语言

标准库

标准库标头

具名要求

功能特性测试宏(C++20)

语言支持库

概念库(C++20)

诊断库

内存管理库

元编程库(C++11)

通用工具库

容器库

迭代器库

范围库(C++20)

算法库

字符串库

文本处理库

数值库

日期和时间库

输入/输出库

文件系统库(C++17)

并发支持库(C++11)

执行控制库(C++26)

技术规范

符号索引

外部库

 

容器库

node-handle (C++17)

序列容器

array (C++11)

vector

vector<bool>

inplace_vector (C++26)

hive (C++26)

deque

forward_list (C++11)

list

关联容器

set

multiset

map

multimap

无序关联容器

unordered_set (C++11)

unordered_multiset (C++11)

unordered_map (C++11)

unordered_multimap (C++11)

容器适配器

stack

queue

priority_queue

flat_set (C++23)

flat_multiset (C++23)

flat_map (C++23)

flat_multimap (C++23)

视图

span (C++20)

mdspan (C++23)

表格

迭代器失效

成员函数表格

非成员函数表格

 

std::deque

成员类型
成员函数
deque::deque deque::~deque deque::operator= deque::assign deque::assign_range (C++23)   deque::get_allocator 元素访问 deque::at deque::operator[] deque::front deque::back 迭代器 deque::begindeque::cbegin (C++11) deque::enddeque::cend (C++11) deque::rbegindeque::crbegin (C++11) deque::renddeque::crend (C++11)	容量 deque::empty deque::size deque::max_size deque::shrink_to_fit (DR*) 修改器 deque::clear deque::insert deque::insert_range (C++23) deque::emplace deque::erase deque::push_front deque::emplace_front (C++11) deque::prepend_range (C++23) deque::pop_front deque::push_back deque::emplace_back (C++11) deque::append_range (C++23) deque::pop_back deque::resize deque::swap
非成员函数
operator==operator<=> (C++20) swap(std::deque) erase(std::deque)erase_if(std::deque) (C++20)(C++20)	operator!=operator<operator>operator<=operator>= (C++20 前)(C++20 前)(C++20 前)(C++20 前)(C++20 前)
推导指引(C++17)

 

在标头 <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（double-ended queue，双端队列）是有索引的序列容器，允许在它的首尾两端快速插入及删除。另外，在 deque 任一端的插入或删除不会使指向其余元素的指针或引用失效。

与 std::vector 相反，deque 的元素不是连续存储的：典型实现采用一系列单独分配的固定尺寸数组，外加额外的簿记数据，这表示对 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) 。

std::deque 的全部成员函数均为 constexpr：在常量表达式求值中创建并使用 std::deque 对象是可能的。 然而，std::deque 对象通常不能为 constexpr，因为任何动态分配的存储都必须在相同的常量表达式求值中释放。

(C++26 起)

模板形参

T	-	元素的类型。 T 必须满足可复制赋值(CopyAssignable) 和可复制构造(CopyConstructible) 。 (C++11 前) 对元素的要求依赖于容器上进行的实际操作。一般地，要求元素类型是完整类型并满足可擦除(Erasable) ，但许多成员函数附带了更严格的要求。 (C++11 起)
Allocator	-	用于获取/释放内存及构造/析构内存中元素的分配器。类型必须满足分配器(Allocator) 。如果 Allocator::value_type 与 T 不同，那么行为未定义(C++20 前)程序非良构(C++20 起)。

迭代器失效

操作	失效
所有只读操作	决不
swap、std::swap	尾后迭代器可能失效（由实现定义）
shrink_to_fit、clear、insert、emplace、push_front、 push_back、emplace_front、emplace_back	始终
erase	如果在起始擦除——只有被擦除元素 如果在末尾擦除——只有被擦除元素和尾后迭代器 否则——所有迭代器（包含尾后迭代器）。 未指定尾后迭代器何时失效。 (C++11 前) 尾后迭代器也会失效，除非所擦除的元素 处于容器开头且最后一个元素未被擦除。 (C++11 起)
resize	如果新尺寸小于旧尺寸——只有被擦除元素和尾后迭代器 如果新尺寸大于旧尺寸——所有迭代器均失效 否则——无迭代器失效。
pop_front、pop_back	到被擦除元素的迭代器。 尾后迭代器可能失效（实现定义）。 (C++11 前) 尾后迭代器也会失效。 (C++11 起)

失效相关注解

• 从 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	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	指向 value_type 的老式随机访问迭代器(LegacyRandomAccessIterator) 和常量表达式迭代器(ConstexprIterator) (C++26 起)
const_iterator	指向 const value_type 的老式随机访问迭代器(LegacyRandomAccessIterator) 和常量表达式迭代器(ConstexprIterator) (C++26 起)
reverse_iterator	std::reverse_iterator<iterator>
const_reverse_iterator	std::reverse_iterator<const_iterator>

成员函数

(构造函数)	构造 deque (公开成员函数)
(析构函数)	析构 deque (公开成员函数)
operator=	将值赋给容器 (公开成员函数)
assign	将值赋给容器 (公开成员函数)
assign_range (C++23)	将范围的值赋给容器 (公开成员函数)
get_allocator	返回关联的分配器 (公开成员函数)
元素访问
at	带越界检查访问指定的元素 (公开成员函数)
operator[]	访问指定的元素 (公开成员函数)
front	访问第一个元素 (公开成员函数)
back	访问最后一个元素 (公开成员函数)
迭代器
begincbegin (C++11)	返回指向起始的迭代器 (公开成员函数)
endcend (C++11)	返回指向末尾的迭代器 (公开成员函数)
rbegincrbegin (C++11)	返回指向起始的逆向迭代器 (公开成员函数)
rendcrend (C++11)	返回指向末尾的逆向迭代器 (公开成员函数)
容量
empty	检查容器是否为空 (公开成员函数)
size	返回元素数 (公开成员函数)
max_size	返回可容纳的最大元素数 (公开成员函数)
shrink_to_fit (DR*)	通过释放未使用的内存减少内存的使用 (公开成员函数)
修改器
clear	清除内容 (公开成员函数)
insert	插入元素 (公开成员函数)
insert_range (C++23)	插入元素范围 (公开成员函数)
emplace (C++11)	原位构造元素 (公开成员函数)
erase	擦除元素 (公开成员函数)
push_back	将元素添加到容器末尾 (公开成员函数)
emplace_back (C++11)	在容器末尾原位构造元素 (公开成员函数)
append_range (C++23)	添加元素的范围到末尾 (公开成员函数)
pop_back	移除末元素 (公开成员函数)
push_front	插入元素到容器起始 (公开成员函数)
emplace_front (C++11)	在容器头部原位构造元素 (公开成员函数)
prepend_range (C++23)	添加元素的范围到起始 (公开成员函数)
pop_front	移除首元素 (公开成员函数)
resize	改变存储元素的个数 (公开成员函数)
swap	交换内容 (公开成员函数)

非成员函数

operator==operator!=operator<operator<=operator>operator>=operator<=> (C++20 移除)(C++20 移除)(C++20 移除)(C++20 移除)(C++20 移除)(C++20)	按照字典顺序比较两个 deque 的值 (函数模板)
std::swap(std::deque)	特化 std::swap 算法 (函数模板)
erase(std::deque)erase_if(std::deque) (C++20)	擦除所有满足特定判别标准的元素 (函数模板)

推导指引

(C++17 起)

注解

功能特性测试宏	值	标准	功能特性
__cpp_lib_containers_ranges	202202L	(C++23)	容器的范围构造和插入
__cpp_lib_constexpr_deque	202502L	(C++26)	constexprstd::deque

示例

运行此代码

#include <deque>#include <iostream>   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 <<' ';std::cout<<'\n';}

输出：

13 7 5 16 8 25

缺陷报告

下列更改行为的缺陷报告追溯地应用于以前出版的 C++ 标准。

缺陷报告	应用于	出版时的行为	正确行为
LWG 230	C++98	T 不需要满足可复制构造(CopyConstructible) （因此不保证能构造 T 类型的元素）	T 也需要满足 可复制构造(CopyConstructible)

参阅

queue

适配一个容器以提供队列（FIFO 数据结构） (类模板)