C++

参考

<deque>

deque

类模板
<deque>

std::deque

template < class T, class Alloc = allocator<T> > class deque;
双端队列
deque（通常读作 "deck"）是 double-ended queue 的非正式缩写。双端队列是具有动态大小的序列容器，可以在两端（前端或后端）进行扩展或收缩。

具体的库可能会以不同的方式实现 deque，通常是以某种形式的动态数组。但无论如何，它们都允许通过随机访问迭代器直接访问序列中的各个元素，并且存储由容器根据需要自动处理，进行扩展和收缩。

因此，它们提供了与 vector 类似的功能，但可以在序列的开头高效地插入和删除元素，而不仅仅是在末尾。但是，与 vector 不同，deque 不保证将其所有元素存储在连续的存储位置：通过偏移指向另一个元素的指针来访问 deque 中的元素会导致 未定义行为。

向量 (vector) 和双端队列 (deque) 都提供非常相似的接口，并且可以用于相似的目的，但内部工作方式却大不相同：虽然向量使用一个需要偶尔重新分配以进行增长的单个数组，但双端队列的元素可以分散在不同的存储块中，容器内部保留必要的信息，以恒定时间直接访问其任何元素，并提供统一的顺序接口（通过迭代器）。因此，双端队列的内部比向量 (vector) 复杂一些，但这允许它们在某些情况下更有效地增长，特别是对于非常长的序列，在这些序列中重新分配的成本更高。

对于涉及在开头或末尾以外的位置频繁插入或删除元素的 O(n) 操作，双端队列 (deque) 的性能较差，并且与列表 (list) 和前向列表 (forward list) 相比，其迭代器和引用的一致性也较差。

容器属性

序列
序列容器中的元素以严格的线性序列排序。单个元素通过其在此序列中的位置进行访问。
动态数组
通常实现为动态数组，它允许直接访问序列中的任何元素，并提供在序列开头或末尾相对快速的添加/删除元素的功能。
感知分配器
容器使用分配器对象来动态处理其存储需求。

模板参数

T
元素的类型。
别名为成员类型deque::value_type.
Alloc
用于定义存储分配模型的分配器对象类型。默认情况下，使用 allocator 类模板，它定义了最简单的内存分配模型并且与值无关。
别名为成员类型deque::allocator_type.

成员类型

成员类型定义说明
value_type第一个模板参数 (T)
allocator_type第二个模板参数 (Alloc)默认为allocator<value_type>
引用allocator_type::reference对于默认的 allocatorvalue_type&
const_referenceallocator_type::const_reference对于默认的 allocatorconst value_type&
指针allocator_type::pointer对于默认的 allocatorvalue_type*
const_pointerallocator_type::const_pointer对于默认的 allocatorconst value_type*
iterator一个指向value_type的 随机访问迭代器，可转换为const_iterator
const_iterator一个指向const value_type
reverse_iteratorreverse_iterator<iterator>
const_reverse_iteratorreverse_iterator<const_iterator>
difference_type一个有符号整数类型，与iterator_traits<iterator>::difference_type相同，通常与 ptrdiff_t 一样
size_type一个可以表示任何非负值的difference_type的无符号整数类型，通常与 size_t 一样
成员类型定义说明
value_type第一个模板参数 (T)
allocator_type第二个模板参数 (Alloc)默认为allocator<value_type>
引用value_type&
const_referenceconst value_type&
指针allocator_traits<allocator_type>::pointer对于默认的 allocatorvalue_type*
const_pointerallocator_traits<allocator_type>::const_pointer对于默认的 allocatorconst value_type*
iterator一个指向value_type的 随机访问迭代器，可转换为const_iterator
const_iterator一个指向const value_type
reverse_iteratorreverse_iterator<iterator>
const_reverse_iteratorreverse_iterator<const_iterator>
difference_type一个有符号整数类型，与
iterator_traits<iterator>::difference_type		相同，通常与 ptrdiff_t 一样
size_type一个可以表示任何非负值的difference_type的无符号整数类型，通常与 size_t 一样

成员函数

（构造函数）
构造 deque 容器 (public member function)
(析构函数)
Deque 析构函数 (public member function)
operator=
赋新值 (公开成员函数)

迭代器:
begin
返回指向起始位置的迭代器 (公开成员函数)
end
返回指向末尾的迭代器 (公开成员函数)
rbegin
返回指向反向起始位置的反向迭代器 (公开成员函数)
rend
返回指向反向末尾的反向迭代器 (公开成员函数)
cbegin
返回指向起始位置的 const_iterator (公开成员函数)
cend
返回指向末尾的 const_iterator (公开成员函数)
crbegin
返回指向反向起始位置的 const_reverse_iterator (公开成员函数)
crend
返回指向反向末尾的 const_reverse_iterator (公开成员函数)

容量:
size
返回大小 (公开成员函数)
max_size
返回最大大小 (公开成员函数)
resize
改变大小 (公开成员函数)
empty
测试容器是否为空 (公开成员函数)
shrink_to_fit
缩小到适合 (公共成员函数)

元素访问:
operator[]
访问元素 (公开成员函数)
at
访问元素 (公开成员函数)
front
访问第一个元素 (公开成员函数)
back
访问最后一个元素 (公开成员函数)

修改器:
assign
赋值容器内容 (public member function)
push_back
在末尾添加元素 (公开成员函数)
push_front
在起始位置插入元素 (公开成员函数)
pop_back
删除最后一个元素 (公开成员函数)
pop_front
删除第一个元素 (公开成员函数)
insert
插入元素 (公开成员函数)
erase
擦除元素 (公开成员函数)
swap
交换内容 (公开成员函数)
clear
清除内容 (公开成员函数)
emplace
构造并插入元素 (公开成员函数)
emplace_front
在起始位置构造并插入元素 (公开成员函数)
emplace_back
在末尾构造并插入元素 (公开成员函数)

分配器:
get_allocator
获取分配器 (公开成员函数)

非成员函数重载

关系运算符
deque 的关系运算符 (function)
swap
交换两个 deque 容器的内容 (function template)