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 不同则行为未定义 (C++20 前)程序非良构 (C++20 起)。

迭代器非法化

本节未完成

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

操作 被非法化
所有只读操作 决不
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)
 返回指向末尾的逆向迭代器
(公开成员函数)
容量
检查容器是否为空
(公开成员函数)
返回容纳的元素数
(公开成员函数)
返回可容纳的最大元素数
(公开成员函数)
(C++11)
 通过释放未使用的内存减少内存的使用
(公开成员函数)
修改器
清除内容
(公开成员函数)
插入元素
(公开成员函数)
(C++11)
 原位构造元素
(公开成员函数)
擦除元素
(公开成员函数)
将元素添加到容器末尾
(公开成员函数)
(C++11)
 在容器末尾就地构造元素
(公开成员函数)
移除末元素
(公开成员函数)
插入元素到容器起始
(公开成员函数)
(C++11)
 在容器头部就地构造元素
(公开成员函数)
移除首元素
(公开成员函数)
改变容器中可存储元素的个数
(公开成员函数)
交换内容
(公开成员函数)

非成员函数

(C++20 中移除)(C++20 中移除)(C++20 中移除)(C++20 中移除)(C++20 中移除)(C++20)
 按照字典顺序比较 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=66331”