「C/C++」C++ STL容器库 之 std::deque 双端队列容器

✨博客主页
何曾参静谧的博客
📌文章专栏
「C/C++」C/C++程序设计
📚全部专栏
「VS」Visual Studio	「C/C++」C/C++程序设计	「UG/NX」BlockUI集合
「Win」Windows程序设计	「DSA」数据结构与算法	「UG/NX」NX二次开发
「QT」QT5程序设计	「File」数据文件格式	「PK」Parasolid函数说明

std::deque 容器详解

std::deque（双端队列）是C++标准模板库（STL）中的一种序列容器，它提供了动态数组的功能，但与std::vector不同的是，std::deque允许在容器的两端高效地插入和删除元素。本文将详细介绍std::deque的使用，包括引用头文件、函数构造、对象初始化、元素访问、迭代器、容器操作、修改器以及元素比较等方面。

上图截图为黑马C++课程

1. 引用头文件

要使用std::deque，首先需要包含相应的头文件：

#include <deque>

2. 函数构造与对象初始化

std::deque提供了多种构造函数来创建和初始化容器对象。

#include <iostream>
#include <deque>int main() {// 1. 默认构造函数，创建一个空的双端队列std::deque<int> dq1;// 2. 填充构造函数，创建一个包含5个元素的双端队列，所有元素初始化为0std::deque<int> dq2(5, 0);// 3. 列表初始化构造函数，创建一个包含指定元素的双端队列std::deque<int> dq3 = {1, 2, 3, 4, 5};// 输出dq3的内容for (int n : dq3) {std::cout << n << " ";}std::cout << std::endl;return 0;
}

3. 对象初始化与元素访问

在创建std::deque对象后，可以通过多种方式访问其元素。

#include <iostream>
#include <deque>int main() {std::deque<int> dq = {10, 20, 30, 40, 50};// 1. 使用下标操作符访问元素std::cout << "Element at index 2: " << dq[2] << std::endl; // 输出30// 2. 使用at函数访问元素（带边界检查）try {std::cout << "Element at index 4: " << dq.at(4) << std::endl; // 输出50} catch (const std::out_of_range& e) {std::cerr << "Out of range error: " << e.what() << std::endl;}// 3. 使用front和back函数访问第一个和最后一个元素std::cout << "First element: " << dq.front() << std::endl; // 输出10std::cout << "Last element: " << dq.back() << std::endl;   // 输出50return 0;
}

4. 迭代器

std::deque支持双向迭代器，允许在容器中向前和向后遍历元素。

#include <iostream>
#include <deque>int main() {std::deque<int> dq = {1, 2, 3, 4, 5};// 1. 使用正向迭代器遍历双端队列for (std::deque<int>::iterator it = dq.begin(); it != dq.end(); ++it) {std::cout << *it << " ";}std::cout << std::endl;// 2. 使用反向迭代器遍历双端队列for (std::deque<int>::reverse_iterator rit = dq.rbegin(); rit != dq.rend(); ++rit) {std::cout << *rit << " ";}std::cout << std::endl;return 0;
}

5. 容器操作

std::deque提供了多种容器操作函数，如size、empty、resize、max_size和swap。

#include <iostream>
#include <deque>int main() {std::deque<int> dq = {1, 2, 3};// 1. 获取容器大小std::cout << "Size of deque: " << dq.size() << std::endl; // 输出3// 2. 检查容器是否为空std::cout << "Is deque empty? " << (dq.empty() ? "Yes" : "No") << std::endl; // 输出No// 3. 调整容器大小（如果新大小大于当前大小，则新元素初始化为0）dq.resize(5);std::cout << "Size after resize: " << dq.size() << std::endl; // 输出5// 4. 获取容器能容纳的最大元素数量std::cout << "Max size of deque: " << dq.max_size() << std::endl;// 5. 交换两个容器的内容std::deque<int> dq2 = {10, 20, 30};dq.swap(dq2);std::cout << "dq after swap: ";for (int n : dq) {std::cout << n << " ";}std::cout << std::endl; // 输出10 20 30return 0;
}

6. 修改器

std::deque提供了多种修改器函数来插入、删除和替换元素。

#include <iostream>
#include <deque>int main() {std::deque<int> dq = {1, 2, 3, 4, 5};// 1. 在末尾插入元素dq.push_back(6);// 2. 在开头插入元素dq.push_front(0);// 输出dq的内容std::cout << "Deque after push_back and push_front: ";for (int n : dq) {std::cout << n << " ";}std::cout << std::endl; // 输出0 1 2 3 4 5 6// 3. 从末尾删除元素dq.pop_back();// 4. 从开头删除元素dq.pop_front();// 输出dq的内容std::cout << "Deque after pop_back and pop_front: ";for (int n : dq) {std::cout << n << " ";}std::cout << std::endl; // 输出1 2 3 4 5// 5. 在指定位置插入元素dq.insert(dq.begin() + 2, 99);// 输出dq的内容std::cout << "Deque after insert: ";for (int n : dq) {std::cout << n << " ";}std::cout << std::endl; // 输出1 2 99 3 4 5// 6. 删除指定位置的元素dq.erase(dq.begin() + 2);// 输出dq的内容std::cout << "Deque after erase: ";for (int n : dq) {std::cout << n << " ";}std::cout << std::endl; // 输出1 2 3 4 5return 0;
}

7. 元素比较

虽然std::deque本身不直接提供元素比较的成员函数，但可以使用标准库中的算法函数（如std::equal）来比较两个std::deque对象的内容。

#include <iostream>
#include <deque>
#include <algorithm> // for std::equalint main() {std::deque<int> dq1 = {1, 2, 3, 4, 5};std::deque<int> dq2 = {1, 2, 3, 4, 5};std::deque<int> dq3 = {1, 2, 3, 6, 5};// 比较两个双端队列是否相等（按元素顺序和值）bool areEqual1 = std::equal(dq1.begin(), dq1.end(), dq2.begin());bool areEqual2 = std::equal(dq1.begin(), dq1.end(), dq3.begin());std::cout << "dq1 and dq2 are equal? " << (areEqual1 ? "Yes" : "No") << std::endl; // 输出Yesstd::cout << "dq1 and dq3 are equal? " << (areEqual2 ? "Yes" : "No") << std::endl; // 输出Noreturn 0;
}

总结

std::deque（双端队列）是C++标准模板库（STL）中一个非常灵活且功能强大的序列容器。它结合了std::vector的动态数组特性和std::list的双向链表特性，允许在容器的两端高效地插入和删除元素，同时提供了随机访问功能。

应用场景

1. 动态数组扩展：

   • 当需要一个可以动态调整大小的数组，并且需要在数组的两端频繁插入或删除元素时，std::deque是一个很好的选择。与std::vector相比，std::deque在两端插入和删除元素时的性能更优，因为它不需要像std::vector那样在内存中进行大量的数据搬移。

2. 队列和栈的实现：

   • std::deque可以很方便地用作队列（FIFO，先进先出）和栈（LIFO，后进先出）的实现。对于队列，可以使用push_back在尾部插入元素，使用pop_front在头部删除元素；对于栈，则可以使用push_front在头部插入元素，使用pop_front在头部删除元素。

3. 滑动窗口算法：

   • 在处理滑动窗口问题时，std::deque可以高效地存储当前窗口内的元素，并允许在窗口的两端进行快速的插入和删除操作。这对于解决一些数组或字符串处理中的滑动窗口问题特别有用。

4. 缓存和缓冲区：

   • std::deque可以用作缓存或缓冲区，存储临时数据。由于它允许在两端进行高效的插入和删除操作，因此非常适合用于需要频繁更新数据结构的场景。

5. 数据流的处理：

   • 在处理数据流时，std::deque可以存储最近接收到的数据，并根据需要丢弃旧数据或添加新数据。这对于实时数据处理和流处理应用特别有用。

6. 算法和数据结构中的辅助容器：

   • 在实现一些复杂的算法和数据结构时，std::deque可以作为辅助容器来存储中间结果或临时数据。它的高效性和灵活性使其成为许多算法和数据结构实现中的理想选择。

综上所述，std::deque是一个功能强大且灵活的容器，适用于多种应用场景。它的高效性和易用性使其成为C++程序员在处理动态数据结构时的有力工具。