std::
deque
类模板 <deque>template < class T, class Alloc = allocator<T> > class deque;
双端队列
deque(通常发音为“deck”)是double-ended queue的不规则缩略词。 双端队列是具有动态大小的序列容器，可以在两端(前端或后端)展开或收缩。
特定的库可能以不同的方式实现deque，通常是某种形式的动态数组。 但在任何情况下，它们都允许通过随机访问迭代器直接访问单个元素，并根据需要通过扩展和收缩容器自动处理存储。
因此，它们提供了一种类似于向量的功能，但是在序列的开始(而不仅仅是在序列的结尾) 也能有效地插入和删除元素。
但是，与vector不同的是，deque并不保证将所有元素存储在连续的存储位置中: 通过偏移指向另一个元素的指针来访问deque中的元素会导致未定义的行为。
vector和deque都提供了非常相似的接口，也可以用于类似的目的， 但在内部却以不同的方式工作:vector使用一个数组需要偶尔增长重新分配, 而双端队列的元素可以分散在不同的块存储、与容器保持必要的内部信息, 以提供在常量时间和一致的接口(通过迭代器)直接访问任何元素。
因此，deque在内部比vector稍微复杂一些，但这允许它们在某些情况下更有效地增长， 特别是对于非常长的序列，在这种情况下重新分配变得更昂贵。
对于频繁插入或移除非开始或结束位置上的元素的操作，deque的性能比list和forward list差， 迭代器和引用的一致性也差。
☲ 容器特性
- 顺序排列
- 序列容器中的元素按照严格的线性顺序排列。每个元素根据它们在这个序列中的位置来访问。
- 动态数组
- 通常实现为动态数组，它允许直接访问序列中的任何元素，并在序列的开始或结束处提供相对快速的添加/删除元素。
- 动态分配
- 容器使用allocator对象来动态处理其存储需求。
☲ 模板参数
- T
-
元素的类型。
别名为成员类型deque::value_type。 - Alloc
-
用于定义存储分配模型的allocator对象的类型。 默认情况下，
使用allocator类模板，它定义了最简单的内存分配模型，并且是值独立的。
别名为成员类型deque::allocator_type.
☉ 成员类型
| C++98 | ||
| 成员类型 | 定义 | 注释 |
| value_type | 起始模板参数(T) | |
| allocator_type | 第二个模板参数(Alloc) | 默认为: allocator<value_type> |
| reference | allocator_type::reference& | 默认分配器: value_type& |
| const_reference | allocator_type::const_reference | 默认分配器: const value_type& |
| pointer | allocator_type::pointer | 默认分配器:value_type* |
| const_pointer | allocator_type::const_pointer | 默认分配器:const value_type* |
| iterator | 一个访问value_type的随机迭代器 | 转换为const_iterator |
| const_iterator | 指向const value_type的随机访问迭代器 | |
| reverse_iterator | reverse_iterator<iterator> | |
| const_reverse_iterator | reverse_iterator<const_iterator> | 常量反向迭代器 |
| difference_type | 一种有符号整型，相当于:
iterator_traits<iterator>::difference_type
|
通常与ptrdiff_t相同 |
| size_type | 无符号整型，可以表示任何difference_type的非负值 | 通常与size_t相同 |
☞ 成员函数
| (constructor) | 构建双端队列容器(公众成员函数) |
| (destructor) | 双端队列析构函数(公众成员函数) |
| operator= | 等号重载 (公众成员函数) |
迭代器:
| begin | 返回一个指向双端队列开头的迭代器 (公众成员函数) |
| end | 返回一个指向双端队列末尾元素的下一个元素的迭代器 (公众成员函数) |
| rbegin | 返回指向双端队列最后一个元素的反向迭代器 (公众成员函数) |
| rend | 返回指向双端队列开始元素之前的理论元素的反向迭代器(公众成员函数) |
| cbegin | 返回一个指向双端队列开头的常量迭代器 (公众成员函数) |
| cend | 返回一个指向双端队列末尾元素的下一个元素的常量迭代器 (公众成员函数) |
| crbegin | 返回指向双端队列最后一个元素的常量反向随机迭代器(公众成员函数) |
| crend | 返回指向双端队列开始元素前一个元素的常量反向随机迭代器 (公众成员函数) |
| size | 返回元素数量 (公众成员函数) |
| max_size | 返回最大元素个数(公众成员函数) |
| resize | 改变大小(公众成员函数) |
| empty | 测试数组是否为空 (公众成员函数) |
| shrink_to_fit | 压缩至适当尺寸(公众成员函数) |
| operator[] | 访问元素(公众成员函数) |
| at | 访问元素(公众成员函数) |
| front | 访问首元素(公众成员函数) |
| back | 访问最后一个元素(公众成员函数) |
| assign | 分配容器的内容(公众成员函数) |
| push_back | 在末尾添加元素(公众成员函数) |
| push_front | 在开头插入元素(公众成员函数) |
| pop_back | 删除最后一个元素(公众成员函数) |
| pop_front | 删除第一个元素(公众成员函数) |
| insert | 插入元素(公众成员函数) |
| erase | 删除元素(公众成员函数) |
| swap | 交换内容(公众成员函数) |
| clear | 清除内容(公众成员函数) |
| emplace | 构造和插入元素(公众成员函数) |
| emplace_front | 构造并在开头插入元素(公众成员函数) |
| emplace_back | 构造并在末尾插入元素(公众成员函数) |
| get_allocator | 获取空间配置器(公众成员函数) |
☣ 非成员函数重载
| relational operators | deque的关系运算符(函数模板) |
| swap | 交换deque内容(函数模板) |