c++双端队列std::deque

概念：

在C++中，std::deque（双端队列）是一种特别设计的数据结构，它允许高效地在容器的两端进行插入和删除操作。为了实现这一特性，std::deque采用了分段存储的方式来进行内存管理。下面我们将详细解释其内存分配方式以及为什么选择这种方式。

内存分配方式

std::deque 的底层实现通常由多个固定大小的缓冲区组成，每个缓冲区是一个连续的存储块。这些缓冲区通过一个指向前一个缓冲区和一个指向后一个缓冲区的指针链接在一起，形成了所谓的“映射”或“map数组”。这个 map 数组本质上是一个动态数组，其中每个元素都是一个指针，指向一段连续的内存空间（即缓冲区），而这些缓冲区才是 std::deque 的实际存储空间主体

当 std::deque 需要在头部或尾部增加存储空间时，它会申请一段新的连续空间，并在 map 数组的开头或结尾添加指向该空间的指针，从而将新空间串接到 deque 容器的头部或尾部。如果 map 数组本身满了，则会申请一块更大的连续空间供 map 数组使用，将原有数据（指针）拷贝到新的数组中，然后释放旧的空间

这种设计确保了即使是在非常长的序列上进行操作时，std::deque 也能以较低的成本扩容，因为每次只需要分配一个新的固定大小的缓冲区，而不是像 std::vector 那样可能需要重新分配整个容器的空间并复制所有元素

为什么在两端进行分配？

std::deque 在两端进行分配的原因主要是为了支持高效的两端插入和删除操作。与 std::vector 不同，后者虽然也可以在两端插入元素，但在头部插入元素会导致所有现有元素向后移动，这是一个 O(n) 的操作。相比之下，std::deque 的两端插入和删除操作都可以在常数时间内完成，即 O(1)，这是因为：

• 不需要搬移元素：每当在 std::deque 的一端插入新元素时，只要当前的缓冲区有可用空间，就直接在该缓冲区内插入；如果没有空间，则创建一个新的缓冲区并在适当的位置插入。因此，不会影响到其他元素的位置。

• 灵活扩展：由于 std::deque 是由多个独立的缓冲区组成的，所以在任何一端都需要额外空间时，都可以简单地添加一个新的缓冲区，而不必担心对整个容器的影响。

指针数组的作用

保存为指针数组的方式对于 std::deque 的性能至关重要。具体来说

• 简化管理和遍历：使用指针数组可以让开发者更容易管理和遍历 std::deque 中的所有缓冲区，同时也方便实现迭代器模式。例如，迭代器可以包含四个指针：cur 指向当前正在遍历的元素，first 和 last 分别指向当前缓冲区的起始和结束位置，node 则指向 map 数组中存储的指向当前缓冲区的指针。这样，迭代器就可以有效地跨越不同的缓冲区进行遍历。

• 高效处理两端操作：指针数组的存在使得在两端添加或删除缓冲区变得简单直接，不需要移动其他元素，从而提高了效率。

创建：

包含头文件#include <deque>

#include <deque>
#include <vector>

std::deque<int> myDeque; // 创建一个空的 int 类型的 deque

std::deque<int> myDeque(5, 10); // 创建一个包含5个元素的 deque，每个元素都初始化为10


std::vector<int> vec = {1, 2, 3, 4, 5};
std::deque<int> myDeque(vec.begin(), vec.end()); // 使用 vector 的内容初始化 deque

std::deque<int> originalDeque = {1, 2, 3};
std::deque<int> copiedDeque(originalDeque); // 复制 originalDeque 的内容到 copiedDeque

std::deque<int> sourceDeque = {1, 2, 3};
std::deque<int> movedDeque(std::move(sourceDeque)); // 将 sourceDeque 的内容移动到 movedDeque
// 注意：sourceDeque 在移动后将处于有效但未指定的状态

std::deque<int> myDeque = {1, 2, 3, 4, 5}; // 使用初始化列表创建 deque

元素访问：

1. 使用下标运算符 operator[]

类似于数组或std::vector，可以通过下标运算符直接访问std::deque中的元素。需要注意的是，这种方式不会进行边界检查，如果索引超出了有效范围，则可能会导致未定义行为。

#include <iostream>
#include <deque>

int main() {
    std::deque<int> d{1, 2, 3, 4, 5};
    // 访问并打印第二个元素
    std::cout << "Element at index 1: " << d[1] << '\n';
    // 修改第三个元素
    d[2] = 10;
    std::cout << "Modified element at index 2: " << d[2] << '\n';
}

2. 使用成员函数 at()

与operator[]不同的是，at()方法会执行越界检查。当试图访问一个超出容器大小的位置时，它将抛出一个std::out_of_range异常。因此，在不确定索引是否安全的情况下，推荐使用at()来避免潜在的风险。

#include <iostream>
#include <deque>
#include <stdexcept>

int main() {
    std::deque<int> d{1, 2, 3, 4, 5};
    try {
        // 安全地访问第四个元素
        std::cout << "Element at index 3 (via at()): " << d.at(3) << '\n';
        // 尝试访问不存在的元素，这将引发异常
        std::cout << "Element at index 10: " << d.at(10) << '\n';
    } catch (const std::out_of_range& e) {
        std::cerr << "Caught an out_of_range exception: " << e.what() << '\n';
    }
}

3. 使用成员函数 front() 和 back()

对于需要快速获取或修改序列的第一个或最后一个元素的情况，可以分别调用front()和back()。这两个函数返回对应位置元素的引用，允许对其进行读写操作。

#include <iostream>
#include <deque>

int main() {
    std::deque<int> d{1, 2, 3, 4, 5};
    // 获取并打印首尾元素
    std::cout << "Front element: " << d.front() << '\n';
    std::cout << "Back element: " << d.back() << '\n';
    // 修改首尾元素
    d.front() = 0;
    d.back() = 6;
    std::cout << "Modified front element: " << d.front() << '\n';
    std::cout << "Modified back element: " << d.back() << '\n';
}

4. 使用迭代器

除了上述基于索引的方法外，还可以通过迭代器遍历整个std::deque或者其中的一部分。迭代器提供了一种更通用的方式来遍历容器，并且可以在不改变容器内容的前提下访问每个元素。

#include <iostream>
#include <deque>

int main() {
    std::deque<int> d{1, 2, 3, 4, 5};
    // 使用迭代器从第二个元素开始遍历到倒数第二个元素
    auto first = d.begin() + 1;
    auto last = d.end() - 1;
    while (first != last) {
        std::cout << *first << " ";
        ++first;
    }
    std::cout << '\n';
}

此外，std::deque还支持反向迭代器，这对于那些需要逆序处理数据的应用非常有用。例如，rbegin()和rend()可以用来创建指向容器末尾和头部之前位置的迭代器

常用函数

赋值操作：可以通过operator=或assign()方法将一个deque的内容复制给另一个。

• d1 = d2; 将d2的所有元素拷贝到d1中。
• d.assign(first, last); 使用迭代器指定的范围替换当前内容

• 检查是否为空：empty()用于判断容器是否为空，若为空则返回true。
• 获取元素数量：size()返回当前存储的有效元素数目；而max_size()给出理论上可容纳的最大元素数。
• 调整容量：resize(count)可以改变容器大小，如果新的大小小于原有大小，则多余部分被截断；反之，则用默认构造填充新添加的空间。
• 优化内存使用：shrink_to_fit()请求释放多余的内部存储空间，但此操作不是强制性的，具体实现取决于编译器。

插入与删除

• 两端插入：

  • push_back(x) 在队尾添加元素x。
  • push_front(x) 在队头添加元素x。
  • emplace_back(args...) 和 emplace_front(args...) 分别在队尾和队头原地构造元素，避免了不必要的拷贝或移动。

• 任意位置插入：insert(pos, x) 在迭代器pos所指位置之前插入单个元素x；也可以一次性插入多个相同元素或者从其他容器复制一段连续的数据。

• 两端删除：

  • pop_back() 移除队尾元素。
  • pop_front() 移除队头元素。

• 任意位置删除：erase(pos) 删除由迭代器pos指向的单个元素；erase(first, last) 删除迭代器first到last之间的所有元素。

• 清空所有元素：clear()移除所有元素，使容器大小变为零。

迭代器支持

• 正向迭代：begin()返回指向首个元素的迭代器，end()返回指向末尾之后位置的迭代器。
• 反向迭代：rbegin()返回指向最后一个元素的逆向迭代器，rend()返回指向第一个元素之前的逆向迭代器。
• 常量迭代器：cbegin(), cend(), crbegin(), crend() 提供了只读版本的迭代器，确保不会意外修改容器内容。

其他功能

• 交换内容：swap(d) 与另一个同类型的deque交换其全部内容。
• 获取分配器：get_allocator() 返回用于创建deque实例时使用的分配器对象。

下面将通过具体的代码示例来展示一些常用的std::deque函数及其用法。

构造与初始化

首先，我们来看如何创建一个std::deque对象并对其进行初始化：

#include <iostream>
#include <deque>

int main() {
    // 创建一个空的 deque
    std::deque<int> d1;
    
    // 使用指定大小构造 deque，默认值为 0
    std::deque<int> d2(5);
    
    // 使用指定大小和初始值构造 deque
    std::deque<int> d3(5, 42);
    
    // 使用初始化列表构造 deque
    std::deque<int> d4{1, 2, 3, 4, 5};
    
    // 通过迭代器范围构造 deque
    std::deque<int> d5(d4.begin(), d4.end());
    
    return 0;
}

插入与删除元素

接下来是关于如何向std::deque中插入新元素以及如何从其中移除元素的例子：

#include <iostream>
#include <deque>

void printDeque(const std::deque<int>& d) {
    for (auto elem : d)
        std::cout << elem << " ";
    std::cout << "\n";
}

int main() {
    std::deque<int> d{1, 2, 3};
    
    // 在队尾添加元素
    d.push_back(4);
    printDeque(d); // 输出: 1 2 3 4
    
    // 在队头添加元素
    d.push_front(0);
    printDeque(d); // 输出: 0 1 2 3 4
    
    // 在任意位置插入单个元素
    auto it = d.begin();
    ++it; // 移动到第二个位置
    d.insert(it, 5); // 插入5在索引1处
    printDeque(d); // 输出: 0 5 1 2 3 4
    
    // 删除队尾元素
    d.pop_back();
    printDeque(d); // 输出: 0 5 1 2 3
    
    // 删除队头元素
    d.pop_front();
    printDeque(d); // 输出: 5 1 2 3
    
    // 删除任意位置的元素
    it = d.begin();
    ++it; // 移动到第二个位置
    d.erase(it); // 删除索引1处的元素
    printDeque(d); // 输出: 5 2 3
    
    return 0;
}

访问元素

这里展示了如何访问std::deque中的元素，包括随机访问、获取首尾元素等：

#include <iostream>
#include <deque>
#include <stdexcept>

int main() {
    std::deque<int> d{10, 20, 30, 40, 50};
    
    // 随机访问
    try {
        std::cout << "Element at index 2 (via at()): " << d.at(2) << "\n"; // 安全检查
        // 下标访问，不进行边界检查
        std::cout << "Element at index 2 (via operator[]): " << d[2] << "\n";
        
        // 修改元素
        d.at(2) = 60;
        std::cout << "Modified element at index 2: " << d.at(2) << "\n";
        
        // 获取首尾元素
        std::cout << "Front element: " << d.front() << "\n";
        std::cout << "Back element: " << d.back() << "\n";
        
        // 修改首尾元素
        d.front() = 5;
        d.back() = 70;
        std::cout << "Modified front element: " << d.front() << "\n";
        std::cout << "Modified back element: " << d.back() << "\n";
        
        // 尝试访问越界的元素，这将抛出异常
        std::cout << "Element at index 10: " << d.at(10) << "\n";
    } catch (const std::out_of_range& e) {
        std::cerr << "Caught an out_of_range exception: " << e.what() << "\n";
    }
    
    return 0;
}

迭代遍历

最后，我们看看如何使用迭代器遍历std::deque中的所有元素，无论是正向还是反向遍历：

#include <iostream>
#include <deque>

int main() {
    std::deque<int> d{1, 2, 3, 4, 5};
    
    // 正向遍历
    std::cout << "Forward iteration:\n";
    for (auto it = d.begin(); it != d.end(); ++it)
        std::cout << *it << " ";
    std::cout << "\n";
    
    // 反向遍历
    std::cout << "Reverse iteration:\n";
    for (auto rit = d.rbegin(); rit != d.rend(); ++rit)
        std::cout << *rit << " ";
    std::cout << "\n";
    
    return 0;
}

以上示例覆盖了std::deque的一些基本操作，包括但不限于构造、插入、删除、访问元素及迭代遍历等功能。实际应用中，根据具体需求选择合适的函数组合可以构建出更加复杂的数据处理逻辑

。此外，值得注意的是，虽然上述例子主要集中在整数类型的std::deque上，但实际上它可以存储任何类型的数据，只要该类型支持所需的构造函数和其他必要的操作