std::deque

 

C++

编译器支持

独立和宿主

语言

标准库

标准库头文件

具名要求

特性测试宏 (C++20)

语言支持库

概念库 (C++20)

诊断库

内存管理库

元编程库 (C++11)

通用工具库

容器库

迭代器库

范围库 (C++20)

算法库

字符串库

文本处理库

数值库

日期和时间库

输入/输出库

文件系统库 (C++17)

并发支持库 (C++11)

执行控制库 (C++26)

技术规范

符号索引

外部库

 

容器库

序列

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>= (until C++20)(until C++20)(until C++20)(until C++20)(until 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 (双端队列) 是一个索引序列容器，允许在其开头和结尾进行快速插入和删除。此外，在 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 的要求。 行为是未定义的(直到 C++20)如果 Allocator::value_type 与 T 不同，则程序是非良构的(自 C++20 起)。

迭代器失效

操作	失效
所有只读操作。	从不。
swap, std::swap	past-the-end 迭代器可能会失效（实现定义）。
shrink_to_fit, clear, insert, emplace, push_front, push_back, emplace_front, emplace_back	总是。
erase	如果在 begin 处擦除 - 仅擦除的元素。 如果在 end 处擦除 - 仅擦除的元素和 past-the-end 迭代器。 否则 - 所有迭代器都失效。 past-the-end 迭代器何时失效是未指定的。(直到 C++11) past-the-end 迭代器也失效 除非擦除的元素位于容器的开头 并且最后一个元素未被擦除。 (自 C++11 起)
resize	如果新大小小于旧大小 - 仅擦除的元素和 past-the-end 迭代器。 如果新大小大于旧大小 - 所有迭代器都失效。 否则 - 没有迭代器失效。
pop_front, pop_back	对于擦除的元素。 past-the-end 迭代器可能会失效（实现定义）。(直到 C++11) past-the-end 迭代器也失效。(自 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	LegacyRandomAccessIterator 和 ConstexprIterator(自 C++26 起) 到 value_type
const_iterator	LegacyRandomAccessIterator 和 ConstexprIterator(自 C++26 起) 到 const value_type
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	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	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_containers	202502L	(C++26)	constexpr std::deque

示例

运行此代码

#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

参见

queue

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