Deque

STL deque 简介

std::deque（双端队列）是 STL 提供的一种序列式容器。它是一种 允许在序列的两端（前端和后端）进行快速插入和删除操作 的数据结构。与只能在一端进行操作的 std::queue 和 std::stack 不同，deque 提供了更大的灵活性。此外，deque 还 支持随机访问，就像数组和 std::vector 一样，允许你通过索引直接访问任何位置的元素。

源文件 指出，deque 结合了 vector 和 list 的一些优点。像 vector 一样，它支持随机访问，但与 vector 在前端进行插入和删除操作性能较差不同，deque 在两端进行这些操作都非常高效。这与 list 的特性类似，因为 list（STL 中的 std::list）是使用双向链表实现的，也支持快速的两端插入和删除。

std::deque 的实现方式

一个非常关键的点是，STL 的 std::deque 并不是简单的作为双向链表来实现的。虽然概念上双向链表可以支持两端的快速插入和删除，但 STL deque 的实现更加复杂，旨在提供 常数时间复杂度的随机访问（摊销） 以及 常数时间复杂度的两端插入和删除操作。

源文件 解释说，std::deque 通常被实现为由多个连续的内存块（或者说缓冲区）组成的结构。为了管理这些不连续的内存块，deque 内部维护了一个 索引数组（或者是指针数组），该数组存储了指向每个内存块起始地址的指针。

当需要在 deque 的前端或后端插入新的元素而某个内存块已满时，deque 会分配一个新的内存块，并更新其内部的索引数组，使其指向新的内存块。当访问 deque 中的某个元素时，deque 会首先通过索引计算出该元素所在的内存块，然后再在该内存块中定位到具体的元素，从而实现随机访问。

这种分段式的实现方式使得 deque 在两端进行插入和删除操作时，只需要在相应的内存块中进行操作，并在必要时分配新的内存块和更新索引，避免了像 vector 那样可能发生的整体数据搬移。同时，通过维护索引数组，deque 也实现了高效的随机访问。

简单总结

• std::deque 是 STL 中的一个 双端队列容器，支持在 前端和后端进行高效的插入和删除操作。
• std::deque 支持随机访问，类似于数组和 std::vector。
• 在实现上，std::deque 通常不是一个简单的链表，而是由多个连续的内存块和一个索引数组构成，这使得它能够在提供两端高效操作的同时，也支持高效的随机访问。
• std::queue 默认就是基于 std::deque 实现的，但 queue 只暴露了队列的 FIFO 行为，限制了对 deque 两端操作和随机访问的直接使用 [我们的对话]。

因此，std::deque 是一种非常灵活的数据结构，适用于既需要在两端进行频繁操作，又需要能够随机访问元素的场景。

STL deque 常用成员函数

deque 演示程序

#include <iostream>
#include <algorithm>
#include <deque>

using namespace std;

int main() {
    deque<int> dq1;
    dq1.push_front(1);     // dq1 = (1)
    dq1.push_front(2);     // dq1 = (2 1)
    dq1.push_back(3);      // dq1 = (2 1 3)
    dq1.push_back(4);      // dq1 = (2 1 3 4)

    deque<int> dq2(dq1.begin() + 1, dq1.end() - 1); // dq2 = (1 3)

    dq1 = 5;           // dq1 = (2 5 3 4)
    dq1.erase(dq1.begin()); // dq1 = (5 3 4)
    dq1.insert(dq1.end() - 1, 2, 6); // dq1 = (5 3 6 6 4)
    sort(dq1.begin(), dq1.end());   // dq1 = (3 4 5 6 6)

    deque<int> dq3;
    dq3.resize(dq1.size() + dq2.size()); // dq3 = (0 0 0 0 0 0 0)
    merge(dq1.begin(), dq1.end(), dq2.begin(), dq2.end(), dq3.begin());
    // dq1 = (3 4 5 6 6) and dq2 = (1 3) ==> dq3 = (1 3 3 4 5 6 6)

    cout << "dq1 的元素: ";
    for (int val : dq1) {
        cout << val << " ";
    }
    cout << endl; // 输出: dq1 的元素: 3 4 5 6 6

    cout << "dq2 的元素: ";
    for (int val : dq2) {
        cout << val << " ";
    }
    cout << endl; // 输出: dq2 的元素: 1 3

    cout << "dq3 的元素: ";
    for (int val : dq3) {
        cout << val << " ";
    }
    cout << endl; // 输出: dq3 的元素: 1 3 3 4 5 6 6

    return 0;
}

程序说明:

• 程序首先包含了必要的头文件 <iostream>，<algorithm> 和 <deque>.
• 创建了一个 deque<int> 对象 dq1，并演示了 push_front() (在前端插入)、push_back() (在后端插入) 的使用。
• 创建了第二个 deque<int> 对象 dq2，并使用 dq1 的一部分元素进行初始化（使用迭代器指定范围）。
• 演示了使用下标运算符 [] 修改 dq1 中间位置的元素。
• 使用 erase() 移除 dq1 的第一个元素。
• 使用 insert() 在 dq1 倒数第二个位置插入两个值为 6 的元素。
• 使用 sort() 算法对 dq1 中的元素进行排序。
• 创建了第三个 deque<int> 对象 dq3，并使用 resize() 改变了其大小。
• 使用 merge() 算法将排序后的 dq1 和 dq2 的元素合并到 dq3 中（需要包含 <algorithm> 头文件）。
• 最后，程序通过循环输出了 dq1、dq2 和 dq3 中的元素，展示了上述操作的结果。

这个程序演示了 std::deque 的一些常用成员函数，包括在两端插入和删除元素、使用迭代器、随机访问以及与其他 STL 算法的配合使用。同时也印证了 deque 具有类似于 vector 的随机访问能力以及类似于 list 的两端高效插入删除能力。