本文共 2639 字，大约阅读时间需要 8 分钟。

C++ deque 数据结构详解

deque（双端队列）是一种高效的容器，支持在队首和队尾快速插入和删除操作。它与传统的向量（vector）相比，具有显著的优势，适合需要频繁在两端操作数据的场景。本文将详细介绍deque的基本原理、使用方法、时间复杂度以及注意事项。

一、基本原理

deque是一种双向开口的连续线性空间，支持在头部和尾部进行元素插入和删除操作。其最大特点在于：

deque的核心结构由两部分组成：

• 主控块：一小块存储空间，用于存储指针，指向另一段较大的连续缓冲区。
• 缓冲区：deque的实际存储空间，包含多个连续的线性块。

二、用法

1. 初始化

创建一个deque实例，可以通过以下方式：

deque
   
     d1;             // 创建一个空队列deque
    
      d1(100, 7);    // 初始化包含100个7的队列deque
     
       d1{1, 2, 3, ...}; // 初始化包含元素1, 2, 3...的队列deque
      
        d2(d1);         // 拷贝d1到d2deque
       
         d2 = d1;        // 将d1赋值给d2
       
      
     
    
   

2. 访问元素

通过索引或迭代器访问元素：

int elem = d1[5];           // 根据索引访问元素int elem = d1.at(5);        // 根据索引访问元素（越界会抛出异常）int first = d1.front();      // 访问队首元素int last = d1.back();       // 访问队尾元素

获取迭代器：

auto iter = d1.begin();     // 队首的迭代器auto end = d1.end();        // 队尾元素的后一个位置auto riter = d1.rbegin();   // 队首元素的前一个位置auto rend = d1.rend();     // 队尾元素的迭代器auto citer = d1.cbegin();    // 常量迭代器指向队首元素auto crediter = d1.cend();  // 常量迭代器指向队尾元素的后一个位置

3. 遍历容器

使用普通for循环或范围for语句：

for (int i = 0; i < d1.size(); ++i) {    cout << d1[i] << endl;}for (deque
   
    ::iterator iter = d1.begin(); iter != d1.end(); ++iter) {    cout << *iter << endl;}for (auto it : d1) {    cout << it << endl;}
   

4. 添加与删除元素

添加元素

d1.push_front(10);       // 队首添加元素d1.emplace_front(10);    // 队首添加元素（更灵活）d1.push_back(20);        // 队尾添加元素d1.emplace_back(20);     // 队尾添加元素（更灵活）d1.insert(d1.begin(), 10); // 在队首插入元素d1.insert(d1.end(), 3, 5); // 队尾插入多个元素

删除元素

d1.pop_front();        // 队首删除元素d1.pop_back();        // 队尾删除元素d1.erase(iter);        // 删除指定迭代器指向的元素d1.erase(iter1, iter2); // 删除迭代器范围内的元素d1.clear();           // 删除所有元素

5. 替换元素

d1 = d2;              // 将d1替换为d2的元素d1.swap(d2);          // 交换d1和d2的元素d1.resize(5, 0);      // 调整大小为5，新元素初始化为0d1.assign(iter1, iter2); // 替换元素d1.assign(5, 0);       // 替换为5个0d1.assign({1, 2, 3, 4, 5}); // 替换为指定列表

6. deque的大小

int size = d1.size();    // 获取实际使用的元素数目int capacity = d1.max_size(); // 获取可存储最大元素数目d1.shrink_to_fit();       // 释放不必要的内存d1.resize(10);           // 调整大小为10d1.resize(10, -5);       // 调整大小为10，新元素初始化为-5

三、时间复杂度

四、注意事项

1. 下标越界

• d1[n]：越界时行为未定义。
• d1.at(n)：越界时抛出out_of_range异常。

2. 迭代器失效

• deque和string：插入或删除非首尾元素会使所有迭代器失效。

• deque：插入或删除尾部元素仅会使尾迭代器失效。

• list和forward_list：插入或删除元素不会使迭代器失效。

• 删除元素后：

  • deque和string：删除尾元素会使尾迭代器失效。
  • deque：删除非首尾元素会使所有迭代器失效，删除首元素则不会。

通过合理使用deque，可以充分发挥其高效操作的优势，同时注意迭代器的有效性管理。