C++中的deque容器详解

1. deque概述

deque（双端队列，double-ended queue）是C++ STL中的序列容器，支持在头部和尾部高效插入和删除元素。deque通常实现为多个固定大小的数组的集合，提供类似vector的功能但具有更好的前端操作性能。

2. 基本特性

• 双端操作：可在头部和尾部高效插入/删除元素
• 随机访问：支持通过下标直接访问元素
• 动态扩容：自动管理存储空间
• 不连续存储：内存不是连续的（与vector不同）

3. 头文件与声明

#include <deque>
using namespace std;

deque<int> dq1;               // 空deque
deque<string> dq2(10);        // 包含10个默认构造的string
deque<double> dq3(5, 3.14);   // 包含5个3.14
deque<char> dq4 = {'a', 'b', 'c'};  // 初始化列表

4. 构造函数与初始化

4.1 默认构造

deque<int> dq;

4.2 填充构造

deque<int> dq(10);        // 10个默认初始化的int(0)
deque<int> dq(5, 100);    // 5个100

4.3 范围构造

int arr[] = {1, 2, 3};
deque<int> dq(arr, arr+3);

4.4 拷贝构造

deque<int> dq2(dq1);

5. 容量操作

5.1 size()

cout << dq.size();  // 返回元素数量

5.2 empty()

if(dq.empty()) {
    cout << "Deque is empty";
}

5.3 max_size()

cout << dq.max_size();  // 返回deque可容纳的最大元素数

5.4 resize()

dq.resize(10);      // 调整为10个元素，新增元素默认初始化
dq.resize(15, 5);   // 调整为15个元素，新增元素初始化为5

6. 元素访问

6.1 operator[]

dq[2] = 10;         // 修改第3个元素
int val = dq[1];    // 访问第2个元素

6.2 at()

dq.at(3) = 20;      // 修改第4个元素(边界检查)
int val = dq.at(0); // 访问第1个元素(边界检查)

6.3 front()

dq.front() = 5;     // 修改第一个元素
int first = dq.front();  // 访问第一个元素

6.4 back()

dq.back() = 8;      // 修改最后一个元素
int last = dq.back();  // 访问最后一个元素

7. 修改操作

7.1 push_back()

dq.push_back(10);   // 在尾部插入10

7.2 push_front()

dq.push_front(5);   // 在头部插入5

7.3 pop_back()

dq.pop_back();      // 删除尾部元素

7.4 pop_front()

dq.pop_front();     // 删除头部元素

7.5 insert()

auto it = dq.insert(dq.begin()+2, 15);  // 在第3个位置插入15
dq.insert(dq.end(), {1, 2, 3});         // 在尾部插入多个元素

7.6 erase()

dq.erase(dq.begin());              // 删除第一个元素
dq.erase(dq.begin(), dq.begin()+2);// 删除前2个元素

7.7 clear()

dq.clear();  // 清空所有元素

7.8 swap()

deque<int> dq2;
dq.swap(dq2);  // 交换两个deque的内容

8. 迭代器

8.1 begin() & end()

for(auto it = dq.begin(); it != dq.end(); ++it) {
    cout << *it << " ";
}

8.2 rbegin() & rend()

for(auto rit = dq.rbegin(); rit != dq.rend(); ++rit) {
    cout << *rit << " ";  // 反向遍历
}

9. 完整示例

#include <iostream>
#include <deque>
#include <algorithm>
using namespace std;

int main() {
    // 创建并初始化deque
    deque<int> dq = {2, 3, 4};
    
    // 头部和尾部操作
    dq.push_front(1);    // 头部插入1
    dq.push_back(5);     // 尾部插入5
    
    // 访问元素
    cout << "First element: " << dq.front() << endl;
    cout << "Last element: " << dq.back() << endl;
    cout << "Element at index 2: " << dq[2] << endl;
    
    // 修改元素
    dq.at(1) = 10;
    
    // 插入元素
    dq.insert(dq.begin()+2, {7, 8, 9});  // 在第3个位置插入7,8,9
    
    // 删除元素
    dq.pop_front();      // 删除头部元素
    dq.erase(dq.end()-2); // 删除倒数第2个元素
    
    // 遍历deque
    cout << "All elements: ";
    for(int num : dq) {
        cout << num << " ";
    }
    cout << endl;
    
    // 排序
    sort(dq.begin(), dq.end());
    cout << "Sorted deque: ";
    copy(dq.begin(), dq.end(), ostream_iterator<int>(cout, " "));
    cout << endl;
    
    // 容量信息
    cout << "Size: " << dq.size() << endl;
    cout << "Is empty: " << (dq.empty() ? "Yes" : "No") << endl;
    
    return 0;
}

10. 性能提示

1. 在两端插入/删除元素性能最佳($O(1)$)
2. 在中间插入/删除元素性能较差($O(n)$)
3. 随机访问性能与vector相当($O(1)$)
4. 迭代器失效情况比vector少，但插入/删除仍可能导致部分迭代器失效