std::deque

来自cppreference.com
< cpp‎ | container
 
C++
 
容器库
 
std::deque
 
定义于头文件 <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 的元素不是相接存储的：典型实现用单独分配的固定大小数组的序列，外加额外的登记，这表示下标访问必须进行二次指针解引用，与之相比 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) 的要求。

模板形参

T - 元素的类型。
T 必须满足可复制赋值 (CopyAssignable) 和可复制构造 (CopyConstructible) 的要求。 (C++11 前)
加诸元素的要求依赖于容器上进行的实际操作。泛言之，要求元素类型是完整类型并满足可擦除 (Erasable) 的要求，但许多成员函数附带了更严格的要求。 (C++11 起)

Allocator - 用于获取/释放内存及构造/析构内存中元素的分配器。类型必须满足分配器 (Allocator) 的要求。若 Allocator::value_type 与 T 不同则行为未定义。

迭代器非法化

本节未完成

此节有仍少量不准确处，更多细节请查看涉及单独成员函数的页面

操作 被非法化
所有只读操作 决不
swap 、 std::swap 尾后迭代器可能被非法化（实现定义）
shrink_to_fit 、 clear 、 insert 、 emplace 、
push_front 、 push_back 、 emplace_front 、 emplace_back 		始终
erase 若在起始擦除——仅被擦除元素

若在末尾擦除——仅被擦除元素和尾后迭代器
否则——非法化所有迭代器（包含尾后迭代器）。

resize 若新大小小于旧者：仅被擦除元素和尾后迭代器

若新大小大于旧者：非法化所有迭代器
否则——不非法化任何迭代器。

pop_front 仅有指向被擦除元素者
pop_back 仅有指向被擦除元素者和尾后迭代器

非法化注意

  • 从 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
Allocator::reference (C++11 前)
value_type& (C++11 起)
const_reference
Allocator::const_reference (C++11 前)
const value_type& (C++11 起)
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)
const_iterator 常随机访问迭代器
reverse_iterator std::reverse_iterator<iterator>
const_reverse_iterator std::reverse_iterator<const_iterator>

成员函数

 构造 deque
(公开成员函数)
析构 deque
(公开成员函数)
赋值给容器
(公开成员函数)
将值赋给容器
(公开成员函数)
返回相关的分配器
(公开成员函数)
元素访问
访问指定的元素，同时进行越界检查
(公开成员函数)
访问指定的元素
(公开成员函数)
访问第一个元素
(公开成员函数)
访问最后一个元素
(公开成员函数)
迭代器
返回指向容器第一个元素的迭代器
(公开成员函数)
返回指向容器尾端的迭代器
(公开成员函数)
返回指向容器最后元素的逆向迭代器
(公开成员函数)
返回指向前端的逆向迭代器
(公开成员函数)
容量
检查容器是否为空
(公开成员函数)
返回容纳的元素数
(公开成员函数)
返回可容纳的最大元素数
(公开成员函数)
(C++11)
 通过释放未使用的内存减少内存的使用
(公开成员函数)
修改器
清除内容
(公开成员函数)
插入元素
(公开成员函数)
(C++11)
 原位构造元素
(公开成员函数)
擦除元素
(公开成员函数)
将元素添加到容器末尾
(公开成员函数)
(C++11)
 在容器末尾就地构造元素
(公开成员函数)
移除末元素
(公开成员函数)
插入元素到容器起始
(公开成员函数)
(C++11)
 在容器头部就地构造元素
(公开成员函数)
移除首元素
(公开成员函数)
改变容器中可存储元素的个数
(公开成员函数)
交换内容
(公开成员函数)

非成员函数

 按照字典顺序比较 deque 中的值
(函数模板)
特化 std::swap 算法
(函数模板)
(C++20)
 擦除所有满足特定判别标准的元素
(函数模板)

推导指引(C++17 起)

示例

运行此代码
#include <iostream>
#include <deque>
 
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 << '\n';
    }
}

输出： 

13
7
5
16
8
25
来自“https://zh.cppreference.com/mwiki/index.php?title=cpp/container/deque&oldid=58775”