注意

请注意，本文尚未完成！您可以通过编辑此文档页面来提供帮助。

概述

简化版 (C++98 起)

template< class T, /* ... */ >
class deque;

详细

常规版 (C++98 起)

template<
    class T,
    class Allocator = std::allocator<T>
>
class deque;

多态版 (C++17 起)

namespace pmr {
    template < class T >
    using deque = std::deque<T, std::pmr::polymorphic_allocator<T>>;
}

Deque（双端队列）是一种允许从头尾两端快速插入和删除的容器。

与 std::queue 或 std::priority_queue 不同，它不是容器适配器。

deque 的技术定义

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

定义于

队列

模板参数

pub	T	元素的类型。 自 C++11 起 对元素施加的要求取决于在容器上执行的实际操作。 通常，要求元素类型是完整类型并满足 Erasable 的要求，但许多成员函数施加了更严格的要求。 直到 C++11 T 必须满足 CopyAssignable 和 CopyConstructible 的要求。
pub	Allocator	用于获取/释放内存以及在该内存中构造/销毁元素的分配器。类型必须满足 Allocator 的要求。 自 C++11 起 如果 Allocator::value_type 与 T 不同，则行为未定义。 直到 C++11 如果 Allocator::value_type 与 T 不同，则程序格式错误。

类型名称

pub	value_type	T
pub	allocator_type	Allocator
pub	size_type	无符号整数类型（通常是 std::size_t）
pub	difference_type	有符号整数类型（通常是 std::ptrdiff_t）
pub	reference	value_type&
pub	const_reference	const value_type&
pub	pointer	Allocator::pointer (直到 C++11) std::allocator_traits<Allocator>::pointer (自 C++11 起)
pub	const_pointer	Allocator::const_pointer (直到 C++11) std::allocator_traits<Allocator>::const_pointer (自 C++11 起)
pub	iterator	LegacyRandomAccessIterator
pub	const_iterator	LegacyRandomAccessIterator
pub	reverse_iterator	std::reverse_iterator<iterator>
pub	const_reverse_iterator	std::reverse_iterator<const_iterator>

成员函数

pub	（构造函数）	构造一个 deque。
pub	（析构函数）	销毁 deque，如果使用了内部存储，则解除分配。
pub	operator=	将值分配给容器。
pub	assign	将值分配给容器。
pub	get_allocator	返回关联的分配器。

元素访问

pub	at	访问指定元素，带边界检查。
pub	operator[]	访问指定元素。
pub	front	返回第一个元素。
pub	末尾	返回最后一个元素。

迭代器

pub	begin cbegin (自 C++11 起)	返回指向起始元素的iterator/const_iterator。
pub	end cend (自 C++11 起)	返回指向结束元素的iterator/const_iterator。
pub	rbegin crbegin (自 C++11 起)	返回一个反向 iterator/const_iterator 指向起始位置。
pub	rend crend (自 C++11 起)	返回一个反向 iterator/const_iterator 指向结束位置。

容量

pub	empty	如果 deque 为空，返回 true，否则返回 false。
pub	size	返回元素数量。
pub	max_size	返回最大可能的元素数量。
pub	shrink_to_fit (自 C++11 起)	通过释放未使用的内存来减少内存使用。

修饰符

pub	clear	清除 deque 的内容。
pub	insert	插入元素。
pub	emplace (自 C++11 起)	就地构造新元素。
pub	erase	擦除元素。
pub	push_back	在末尾添加一个元素。
pub	emplace_back (自 C++11 起)	在末尾原地构造新元素。
pub	pop_back	删除最后一个元素。
pub	push_front	在开头添加一个新元素。
pub	emplace_front (自 C++11 起)	在开头原地构造新元素。
pub	pop_front	删除第一个元素。
pub	resize	更改存储的元素数量。
pub	swap	交换两个 deque。

非成员函数

pub	operator== operator!= (在 C++20 中移除) operator< (在 C++20 中移除) operator> (在 C++20 中移除) operator<= (在 C++20 中移除) operator>= (在 C++20 中移除) operator<=> (自 C++20 起)	按字典顺序比较 deque 中的值。
pub	std::swap (std::deque)	std::swap 算法的重载。
pub	erase (std::deque) erase_if (std::deque)	std::erase/std::erase_if 算法的重载。

辅助类

pub

std::uses_allocator (std::deque)

特化 std::uses_allocator 类型特征。

推导指南 (C++17 起)

点击展开

// (1) (since C++17)
template< class InputIt,
          class Alloc = std::allocator<
            typename std::iterator_traits<InputIt>::value_type
          >
        >
deque( InputIt, InputIt, Alloc = Alloc() )
  -> deque<typename std::iterator_traits<InputIt>::value_type, Alloc>;

(1) 允许从**迭代器范围**进行推导。

重载决议

为了使 (1) 参与重载解析，必须满足以下要求：

• InputIt 满足 LegacyInputIterator
• Alo 满足 Allocator

注意

库确定类型不满足 LegacyInputIterator 的程度是未指定的，但至少

• 整型不符合输入迭代器的条件。

同样，它确定类型不满足 Allocator 的程度是未指定的，但至少

• 成员类型 Alloc::value_type 必须存在。
• 当作为未求值操作数处理时，表达式 std::declval<Alloc&>().allocate(std::size_t{}) 必须是格式良好的。

示例

基本操作

初始化队列，添加值并打印内容

#include <iostream>
#include <deque>
 
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 << ' ';
    }
}

结果

13 7 5 16 8 25