在 C++ 中使用 deque 容器

C++ 9月前 47

本文将演示关于如何在 C++ 中使用 std::deque 容器的多种方法。

使用 `std::deque` 容器处理快速队列插入/删除操作

std::deque 实现了一个双端队列，在队列的两端提供恒定时间的插入和删除操作。因此，这种数据结构应该在这种操作构成大部分事务的情况下使用。缺点是，std::deque 元素不存储在连续的内存位置，它需要一些额外的操作来处理操作，导致对象大小比 std::vector 容器多。下面的例子显示了一个由 vector 对象构造的字符串 deque。请注意，建议使用 emplace_back 方法从字符串输入中添加一个新元素。

#include <iostream>#include <deque>#include <vector>using std::cout; using std::deque;
using std::endl; using std::string;
using std::vector;
template<typename T>
void printElements(deque<T> &d)
{
    cout << "[ ";
    for (const auto &item : d) {
        cout << item << ", ";
    }
    cout << "\b\b ]" << endl;
}
int main()
{
    vector<string> vec = {"plie", "flie", "blie", "clie"};;
    deque<string> deque2(vec.begin(), vec.end());
    deque2.emplace_back("hlie");
    printElements(deque2);
    exit(EXIT_SUCCESS);
}

输出：

[ plie, flie, blie, clie, hlie ]

使用 `std::push_back`/`std::push_front` 方法在 `std::deque` 中插入元素

std::deque 有多个内置函数，为元素操作提供丰富的功能。其中最常见的是 push_back 和 push_front 方法，它们将给定的对象作为元素添加到 deque 的相应一侧。请注意，这些函数有其相反的方法来删除元素-pop_back 和 pop_front。下面的例子展示了上述方法的基本用法。

#include <iostream>#include <deque>#include <vector>using std::cout; using std::deque;
using std::endl; using std::string;
using std::vector;
template<typename T>
void printElements(deque<T> &d)
{
    cout << "[ ";
    for (const auto &item : d) {
        cout << item << ", ";
    }
    cout << "\b\b ]" << endl;
}
int main()
{
    vector<string> vec = {"plie", "flie", "blie", "clie"};;
    deque<string> deque2(vec.begin(), vec.end());
    string str1("alie");
    deque2.push_back(str1);
    printElements(deque2);
    deque2.push_front(str1);
    printElements(deque2);
    deque2.pop_back();
    deque2.pop_front();
    printElements(deque2);
    exit(EXIT_SUCCESS);
}

输出：

[ plie, flie, blie, clie, alie ]
[ alie, plie, flie, blie, clie, alie ]
[ plie, flie, blie, clie ]

使用 `push_front` 方法的封装函数实现固定大小的队列

另一种利用 std::deque 容器的方法，将其作为固定大小的堆栈进行操作，存储 n 个元素，当堆栈满了之后，每插入一个新的元素，就会自动从后面删除一个元素。在这种情况下，我们通过将 push_front 和 pop_back 方法包装成一个单独的函数来实现这个功能。请注意，同样的功能也可以通过使用 std::stack 容器适配器来实现，在这个页面上有详细的描述。

#include <iostream>#include <deque>using std::cout; using std::deque;
using std::endl; using std::string;
template<typename T>
void printElements(deque<T> &d)
{
    cout << "[ ";
    for (const auto &item : d) {
        cout << item << ", ";
    }
    cout << "\b\b ]" << endl;
}
template<typename T>
void pushElement(T &elem, deque<T> &d)
{
    d.push_front(elem);
    d.pop_back();
}
int main()
{
    deque<int> deque1 = {3, 5, 7, 9};
    int i1 = 11;
    printElements(deque1);
    pushElement(i1, deque1);
    printElements(deque1);
    exit(EXIT_SUCCESS);
}