在 C++ 中使用 deque 容器

Jinku Hu 2023年1月30日 2021年1月22日
  1. 使用 std::deque 容器處理快速佇列插入/刪除操作
  2. 使用 std::push_back/std::push_front 方法在 std::deque 中插入元素
  3. 使用 push_front 方法的封裝函式實現固定大小的佇列
在 C++ 中使用 deque 容器

本文將演示關於如何在 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_backpush_front 方法,它們將給定的物件作為元素新增到 deque 的相應一側。請注意,這些函式有其相反的方法來刪除元素-pop_backpop_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_frontpop_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);
}

輸出:

[ 3, 5, 7, 9 ]
[ 11, 3, 5, 7 ]
Author: Jinku Hu
Jinku Hu avatar Jinku Hu avatar

Founder of DelftStack.com. Jinku has worked in the robotics and automotive industries for over 8 years. He sharpened his coding skills when he needed to do the automatic testing, data collection from remote servers and report creation from the endurance test. He is from an electrical/electronics engineering background but has expanded his interest to embedded electronics, embedded programming and front-/back-end programming.

LinkedIn