【C++】std::dequeの使い方について詳しく解説

2023 3/20

dequeは、双方向キューとして使うことができる非常に便利なコンテナです。

本記事では、dequeの基本的な使い方や応用的な使い方について、サンプルコードも交えて解説していきます。

dequeとは

dequeは、C++のSTL(Standard Template Library)に含まれるコンテナの一つです。

dequeはdouble-ended queueの略で、先頭と末尾の両方から要素を追加・削除することができます。

dequeは、vectorと同様にランダムアクセスが可能であり、listと同様に先頭・末尾への要素の追加・削除が高速に行えるため、vectorやlistよりも柔軟な使い方ができます。

また、dequeはメモリ効率も良く、大量のデータを扱う場合でも高速かつ安定した動作をすることができます。

dequeの宣言と初期化

宣言

dequeを使用するためには、以下のように宣言します。

#include <deque>

std::deque<データ型> deque名;

例えば、int型の要素を持つdequeを宣言する場合は以下のようになります。

#include <deque>

std::deque<int> myDeque;

初期化

dequeを宣言した後、初期化することもできます。初期化方法はいくつかありますが、代表的な方法を紹介します。

デフォルトコンストラクタ

デフォルトコンストラクタを使用して初期化する場合は、以下のように記述します。

std::deque<int> myDeque; // デフォルトコンストラクタで初期化

要素数指定

要素数を指定して初期化する場合は、以下のように記述します。

std::deque<int> myDeque(5); // 5つのint型要素で初期化

値指定

値を指定して初期化する場合は、以下のように記述します。

std::deque<int> myDeque{1, 2, 3}; // {1, 2, 3}で初期化

以上が、dequeの宣言と初期化方法です。次は、dequeの基本操作について解説します。

dequeの要素の追加と削除

dequeは、先頭と末尾の両方から要素を追加・削除することができます。

push_backとpop_back

dequeの末尾に要素を追加するには、push_back()関数を使用します。以下は、int型のdequeに値を追加する例です。

#include <iostream>
#include <deque>

using namespace std;

int main() {
    deque<int> myDeque;
    myDeque.push_back(1);
    myDeque.push_back(2);
    myDeque.push_back(3);

    for (auto i : myDeque) {
        cout << i << " ";
    }
    
    return 0;
}

1 2 3

また、末尾から要素を削除するには、pop_back()関数を使用します。以下は、上記の例から最後の要素を削除する例です。

myDeque.pop_back();
for (auto i : myDeque) {
    cout << i << " ";
}

1 2

push_frontとpop_front

dequeの先頭に要素を追加するには、push_front()関数を使用します。以下は、int型のdequeに値を追加する例です。

#include <iostream>
#include <deque>

using namespace std;

int main() {
    deque<int> myDeque;
    myDeque.push_front(1);
    myDeque.push_front(2);
    myDeque.push_front(3);

    for (auto i : myDeque) {
        cout << i << " ";
    }
    
    return 0;
}

3 2 1

また、先頭から要素を削除するには、pop_front()関数を使用します。以下は、上記の例から最初の要素を削除する例です。

myDeque.pop_front();
for (auto i : myDeque) {
    cout << i << " ";
}

1 2 3

以上がdequeで要素の追加・削除方法です。

dequeの要素のアクセス

dequeは、先頭と末尾から要素を追加・削除することができるデータ構造です。このような特徴を持つdequeに対して、要素へのアクセス方法も複数あります。

[]演算子

[]演算子は、配列やvectorなどでも使用される演算子で、指定したインデックス番号にある要素にアクセスすることができます。dequeでも同様に[]演算子を使用することができます。

#include <iostream>
#include <deque>

int main() {
    std::deque<int> d = {1, 2, 3, 4, 5};
    int val = d[1];
    d[2] = 20; //代入も可能
    std::cout << d[0] << std::endl; // 出力結果: 1
    std::cout << d[2] << std::endl; // 出力結果: 20
    std::cout << d[4] << std::endl; // 出力結果: 5

    return 0;
}

1
20
5

上記の例では、dequeのインデックス番号0,2,4にある要素にアクセスして出力しています。[]演算子は範囲外のインデックス番号を指定した場合、実行時エラーが発生します。

また、[]演算子は要素への参照を返すため、d[2] = 20;のように取得した値を変更することも可能です。

at関数

at関数は、[]演算子と同様に指定したインデックス番号にある要素にアクセスすることができます。

ただし、at関数は範囲外のインデックス番号を指定した場合、例外(std::out_of_range)が発生します。そのため、範囲外のインデックス番号を指定しないよう注意が必要です。

#include <iostream>
#include <deque>

int main() {
    std::deque<int> d = {1, 2, 3, 4, 5};

    std::cout << d.at(0) << std::endl; // 出力結果: 1
    std::cout << d.at(2) << std::endl; // 出力結果: 3
    std::cout << d.at(4) << std::endl; // 出力結果: 5
    
    try {
        int value = d.at(10); // 範囲外のインデックス番号を指定すると例外(std::out_of_range)が発生する
        std::cout << value;
    } catch (std::out_of_range& e) {
        std::cerr << "Error: " << e.what() << '\n';
    }

    return 0;
}

1
3
5
Error: invalid deque<T> subscript

上記の例では、at関数で範囲内・範囲外それぞれのインデックス番号にある要素にアクセスしています。

また、try-catch文を用いて範囲外のインデックス番号を指定した場合に発生する例外(std::out_of_range)をキャッチできるため、意図しない挙動に対応することが可能です。

front関数とback関数

front関数は先頭(最初)の要素へアクセスし、back関数は末尾(最後)の要素へアクセスします。以下はサンプルコードです：

#include <iostream>
#include <deque>

int main() {
	std :: deque<int> dq = {10,20,30};
	std :: cout<<dq.front()<<std :: endl;//出力：10
	std :: cout<<dq.back()<<std :: endl;//出力：30
	
	return 0;
}

10
30

上記コードではfront関数で先頭(最初)の値10、back関数で末尾(最後)の値30へアクセスしています。

以上がdequeで使える主な要素へアクセスする方法です。

dequeの要素の検索

dequeには、要素を検索するための関数が用意されています。以下では、その使い方について説明します。

find関数

find関数は、指定した値と等しい最初の要素を探して、そのイテレータを返します。もし見つからなかった場合は、end()イテレータを返します。

#include <iostream>
#include <deque>

int main() {
    std::deque<int> d = {1, 2, 3, 4, 5};
    auto it = std::find(d.begin(), d.end(), 3);
    if (it != d.end()) {
        std::cout << "Found: " << *it << std::endl;
    } else {
        std::cout << "Not found" << std::endl;
    }
}

Found: 3

上記の例では、dというdequeから値が3である最初の要素を探しています。

結果として、Found: 3と表示されます。

count関数

count関数は、指定した値と等しい要素の個数を返します。

#include <iostream>
#include <deque>

int main() {
    std::deque<int> d = {1, 2, 3, 4, 5};
    int count = std::count(d.begin(), d.end(), 3);
    std::cout << "Count: " << count << std::endl;
}

Count: 1

上記の例では、dというdequeから値が3である要素が1つだけ存在するため、Count: 1と表示されます。

lower_bound関数とupper_bound関数

lower_bound関数は、指定した値以上である最初の要素を探して、そのイテレータを返します。

もし見つからなかった場合は、次に大きい要素のイテレータを返します。

一方で、 upper_bound 関数は指定した値より大きい最初の要素を探してそのイテレータを返します。

これら2つの関数はソート済みコンテナに対して使用することが推奨されます。

#include <iostream>
#include <algorithm>
#include <deque>

int main() {
    std::deque<int> d = { 1, 2, 2, 4, 5 };

    // lower_bound
    auto it_lower = std::lower_bound(d.begin(), d.end(), 2);
    if (it_lower != d.end()) {
        std::cout << "2以上の数値の中での最小値: " << *it_lower << std::endl;
    }

    // upper_bound
    auto it_upper = std::upper_bound(d.begin(), d.end(), 2);
    if (it_upper != d.end()) {
        std::cout << "2超過の数値の中での最小値: " << *it_upper << std::endl;
    }
}

2以上の数値の中での最小値: 2
2超過の数値の中での最小値: 4

上記の例では、 d の中から lower_bound(2) を実行することで2以上の数値の中での最小値: 2と表示されます。

また同様に upper_bound(2) を実行することで2超過の数値の中での最小値: 4と表示されます。

注意点として、lower_boundやupper_boundは昇順にソート済みのコンテナに使用することを前程しています。

昇順にソートされていないコンテナに使用する場合は挙動が異なる可能性があります。

dequeの要素の並び替え

dequeは、sort関数やreverse関数を使って要素を並び替えることができます。

sort関数

sort関数は、dequeの要素を昇順にソートするために使用されます。以下は、sort関数を使用してdequeをソートする例です。

#include <iostream>
#include <deque>
#include <algorithm>

using namespace std;

int main() {
    deque<int> d = {5, 3, 1, 4, 2};
    
    sort(d.begin(), d.end());
    
    for (auto i : d) {
        cout << i << " ";
    }
    
    return 0;
}

このプログラムでは、sort関数を使用して、dの要素を昇順にソートしています。出力結果は以下のようになります。

1 2 3 4 5

reverse関数

reverse関数は、dequeの要素を逆順にするために使用されます。以下は、reverse関数を使用してdequeを逆順にする例です。

#include <iostream>
#include <deque>
#include <algorithm>

using namespace std;

int main() {
    deque<int> d = {5, 3, 1, 4, 2};
    
    reverse(d.begin(), d.end());
    
    for (auto i : d) {
        cout << i << " ";
    }
    
    return 0;
}

このプログラムでは、reverse関数を使用して、dの要素を逆順にします。出力結果は以下のようになります。