更多 C++语法知识在 C++语言学记专栏
往期 STL 容器看点：
这篇文章是关于 C++所有数据结构概览中的单独专题

顺序容器	vector	array	list	deque	forward_list
关联容器	set&multiset	map&multimap	无序关联容器	Unordered set&multiset	Unordered map&multimap
容器适配器	stack	queue	priority_queue	其他容器	string

我们来详细介绍 C++ STL 中的 std::deque (双端队列)。

首先，请确保包含了头文件：

#include <deque>

std::deque (Double-Ended Queue) 是一种非常灵活的顺序容器。它巧妙地结合了 std::vector 和 std::list 的优点：既支持快速的随机访问（像 vector），也能在序列的头部和尾部高效地添加或删除元素（像 list）。

它的底层实现通常是一个分块的连续内存（或称为“块映射”）。deque 内部维护一个指向各个内存块的指针数组（映射），每个内存块中存储着实际的元素。这使得它可以在两端轻松地分配或释放新的内存块，而无需移动整个数据结构。

---

1. 构造函数 (Constructors)

用于创建和初始化一个 deque，其构造函数与 vector 和 list 基本相同。

• deque()

  • 功能：默认构造函数，创建一个空的 deque。

  • 示例：std::deque<int> d1;

• deque(size_type count, const T& value)

  • 功能：创建包含 count 个元素的 deque，每个元素都被初始化为 value。

  • 示例：std::deque<int> d2(5, 10); // 创建包含 5 个 int 的 deque，每个都是 10

• deque(size_type count) (C++11 起)

  • 功能：创建包含 count 个元素的 deque，并对每个元素进行值初始化。

  • 示例：std::deque<int> d3(5); // 创建包含 5 个 int 的 deque，每个都是 0

• deque(InputIt first, InputIt last)

  • 功能：使用迭代器范围 [first, last) 内的元素来构造 deque。

  • 示例：int arr[] = {1, 2, 3, 4, 5}; std::deque<int> d4(arr, arr + 5);

• deque(const deque& other)

  • 功能：拷贝构造函数，创建一个与 other 内容相同的 deque。

  • 示例：std::deque<int> d5(d4);

• deque(deque&& other) (C++11)

  • 功能：移动构造函数，接管 other 的资源。

  • 示例：std::deque<int> d6(std::move(d5));

• deque(std::initializer_list<T> init) (C++11)

  • 功能：使用初始化列表来构造 deque。

  • 示例：std::deque<int> d7 = {1, 2, 3, 4, 5};

---

2. 迭代器 (Iterators)

用于遍历 deque 中的元素。

• begin() / cbegin(), end() / cend()

• rbegin() / crbegin(), rend() / crend()

  • 功能：与 vector 完全相同，分别提供正向和反向遍历的迭代器。

重要提示：deque 的迭代器是随机访问迭代器 (Random Access Iterator)，与 vector 一样。这意味着你可以对它进行 ++、--、it + n、it - n 以及比较等所有操作。这是它相较于 list 的巨大优势。不过，由于其分块存储的特性，deque 迭代器的内部实现比 vector 的普通指针要复杂，因此在性能上可能会有微小的开销。

示例：

std::deque<int> d = {10, 20, 30, 40, 50};
auto it = d.begin() + 3; // 随机访问，it 指向 40
std::cout << *it << std::endl; // 输出: 40

---

3. 容量 (Capacity)

管理 deque 的存储。

• size()

  • 功能：返回 deque 中实际元素的数量。

• empty()

  • 功能：检查 deque 是否为空。

• resize(size_type count, ...)

  • 功能：改变 deque 的大小，与 vector 行为类似。

• shrink_to_fit() (C++11)

  • 功能：请求释放未使用的内存块。

重要提示：deque 没有 capacity() 和 reserve() 方法。这是因为它不需要像 vector 那样一次性分配大块连续内存。当空间不足时，它只需在头部或尾部挂上一个新的内存块即可，这个过程不会导致所有元素的整体迁移，因此预留空间没有意义。

---

4. 元素访问 (Element Access)

获取 deque 中的单个元素。

• operator[](size_type pos)

  • 功能：访问指定位置 pos 的元素。不进行边界检查。O(1)。

• at(size_type pos)

  • 功能：访问指定位置 pos 的元素。进行边界检查。O(1)。

• front()

  • 功能：返回对第一个元素的引用。

• back()

  • 功能：返回对最后一个元素的引用。

重要提示：deque 没有 .data() 方法。因为它的内存不是完全连续的，所以无法提供一个指向整个数据序列的裸指针。这是使用 deque 时的一个关键限制，特别是在与 C 风格的 API 交互时。

示例：

std::deque<int> d = {10, 20, 30, 40};
int val = d[2];       // val = 30
d.at(1) = 25;       // d 变为 {10, 25, 30, 40}

---

5. 修改器 (Modifiers)

改变 deque 的内容，这是 deque 设计的核心。

• assign(): 功能同 vector。

• push_back(const T& value) / emplace_back(...)

  • 功能：在 deque 的末尾添加一个元素。均摊 O(1)。

• pop_back()

  • 功能：移除 deque 的最后一个元素。O(1)。

• push_front(const T& value) / emplace_front(...)

  • 功能：在 deque 的头部添加一个元素。这是 deque 相对于 vector 的核心优势。均摊 O(1)。

• pop_front()

  • 功能：移除 deque 的第一个元素。O(1)。

• insert(const_iterator pos, ...)

  • 功能：在迭代器 pos 指向的位置之前插入元素。

• erase(const_iterator pos) / erase(const_iterator first, const_iterator last)

  • 功能：移除指定位置或范围的元素。

重要提示：deque 的中间插入和删除 (insert, erase) 是其弱点。这些操作是 O(n) 的，并且通常比 vector 的等效操作要慢，因为可能需要移动多个内存块中的元素。如果你需要频繁地在序列中间操作，list 是更好的选择。

• swap(deque& other): 功能同 vector，O(1)。

• clear(): 功能同 vector。

示例：

std::deque<int> d;
d.push_back(20);    // d: {20}
d.push_front(10);   // d: {10, 20}
d.push_back(30);    // d: {10, 20, 30}
d.push_front(5);    // d: {5, 10, 20, 30}

d.pop_front();      // d: {10, 20, 30}
d.pop_back();       // d: {10, 20}

---

6. 非成员函数 (Non-member functions)

• 比较运算符 (==, !=, <, >, <=, >=)

  • 功能：以字典序比较两个 deque 的内容。

• std::swap(deque& a, deque& b)

  • 功能：与成员函数 swap 等效。

• std::erase(deque<T>& c, const U& value) (C++20)

• std::erase_if(deque<T>& c, UnaryPredicate p) (C++20)

  • 功能：提供了一种简洁的方式来移除元素，与 vector 和 list 的 C++20 版本接口保持一致。

总结：何时使用 std::deque？

当你需要一个同时满足以下大部分条件的容器时，deque 是最佳选择：

1. 需要频繁地在容器的两端进行添加和删除操作。

2. 需要像数组一样快速地随机访问元素。

3. 不需要频繁地在容器中间插入或删除元素。

4. 不需要将容器的全部数据以单个连续内存块的形式提供给其他API（即不需要 .data() 方法）。

std::stack 和 std::queue 的默认底层容器都是 std::deque，这正是因为它能高效地支持两端（或至少一端）的操作。