deque | Programming Place Plus　C++編【標準ライブラリ】　第７章

deque 🔗

deque は、STLコンテナの一種で、両端待ち行列（アルゴリズムとデータ構造【データ構造】第１１章）を提供します。これを使うには、<deque> という名前の標準ヘッダをインクルードする必要があります。

deque は、vector と同様に、内部的に動的な配列を持っています。ただし、vector のように単純な配列ではなく、たとえば、複数の配列を組み合わせて使うような複雑な形をしています（実際の実装方法は、ライブラリの実装に任されています）。

deque は、先頭と末尾に対する挿入や削除が高速に行えるという特性を持っています。途中への要素の挿入や、途中の要素の削除は、やや負荷の高い処理になります。なお、要素の直接アクセスは、vector よりわずかに遅くなる傾向があります。

deque は、次のように定義されています。

namespace std {
    template <typename T, typename Allocator = allocator<T> >
    class deque {
    };
}

deque はクラステンプレート（【言語解説】第２０章）なので、使用時にはテンプレート実引数の指定が必要です。テンプレート仮引数 T は、動的配列の要素の型です。たとえば、int型の要素を扱いたいのであれば、以下のようになります。

std::deque<int> intDeque;

もう１つのテンプレート仮引数 Allocator は、メモリ確保の方法を定義するアロケータと呼ばれるオブジェクトの指定です。テンプレート仮引数 Allocator はデフォルトテンプレート実引数を持っているので省略できます。多くの場合、省略しても list は活用できるので、本章では解説しません。アロケータについては、第３２章であらためて取り上げます。

サイズ 🔗

deque の中に実際に存在している要素数が「サイズ」です。

vector の場合、実際に確保された領域の大きさを指して「容量」という言葉があります。deque の場合も、内部に事前に領域を確保していますが、deque では「容量」を意識する必要はありません（調べることもできません）。

現在の「サイズ」を知るには、sizeメンバ関数を使います。また、「サイズ」が 0 かどうかは、emptyメンバ関数で調べられます。

「サイズ」の最大値は max_sizeメンバ関数で取得できます。戻り値の型は、std::deque::size_type型です。

使用例としては、次のようになります。

#include <iostream>
#include <deque>

int main()
{
    std::deque<int> deq;

    for (int i = 0; i < 5; ++i) {
        deq.push_back(i);
    }

    std::cout << deq.max_size() << "\n"
              << deq.size() << "\n"
              << std::boolalpha << deq.empty() << std::endl;
}

実行結果：

1073741823
5
false

resizeメンバ関数を使うと、サイズを変更できます。

現在のサイズよりも大きな値を指定すると、そのサイズになるまで要素を充填します。このとき、要素の型のデフォルトコンストラクタが使用されます。もし、第２引数を指定している場合には、その値を要素の初期化に使用します。

また、現在のサイズよりも小さい値を指定した場合は、指定したサイズになるまで、要素が末尾にあるものから順に取り除かれます。

#include <iostream>
#include <deque>

typedef std::deque<int> IntDeque;

void PrintDeque(const IntDeque& deq)
{
    const IntDeque::const_iterator itEnd = deq.end();
    for (IntDeque::const_iterator it = deq.begin(); it != itEnd; ++it) {
        std::cout << *it << "\n";
    }
    std::cout << std::endl;
}

int main()
{
    IntDeque deq;

    deq.resize(5);
    PrintDeque(deq);

    deq.resize(10, 99);
    PrintDeque(deq);

    deq.resize(1);
    PrintDeque(deq);
}

実行結果：

生成と初期化 🔗

deque には、複数のコンストラクタが定義されているので、さまざまな方法でインスタンス化できます。

int main()
{
    const int a[] = {0, 1, 2, 3, 4};

    std::deque<int> deq1;           // 空
    std::deque<int> deq2(10);       // サイズ10 (要素はデフォルトコンストラクタで生成)
    std::deque<int> deq3(10, 3);    // サイズ10 (要素はコピーコンストラクタで生成)
    std::deque<int> deq4(deq2);     // 他の deque からコピー
    std::deque<int> deq5(a, a + 5); // イテレータで指定された範囲からコピー
}

この５通りのコンストラクタは、vector のものと同じ意味合いになっています。

deq1、deq3、deq5 の方法の場合は、アロケータを渡すデフォルト実引数が隠されています。

deq2、deq3 の方法では、要素数を指定して、その個数分の要素を実際に生成しています。deq2 の場合は、デフォルトコンストラクタによる生成、deq3 の場合は、第２引数に指定した値を使って要素を生成し、コピーしています。

破棄 🔗

デストラクタでは、deque が内部で確保した領域が破棄されます。

仮想デストラクタ（【言語解説】第２７章）ではないので、deque を継承して使用することは不適切であることに注意してください。

要素のアクセス 🔗

deque には、operator[] が用意されており、配列や vector のように、[] を使った添字アクセスが可能です。

deq[3] = 10;
int a = deq[3];

添字に 0未満の数や、現在の「サイズ」以上の数を指定した場合、範囲外アクセスになってしまいます。これは普通の配列の場合と同じで、何が起こるか分からない危険な操作です。

範囲外アクセスへの備えが欲しければ、atメンバ関数を使用します。atメンバ関数は、添字を引数に取り、その位置にある要素の参照を返します。[] を使う場合と違うのは、範囲外アクセスになったときに std::out_of_range例外を送出する点です。

例外については、【言語解説】第３０章で、std::out_of_range については第２５章で解説しますが、ここでは使用例だけ挙げておきます。

#include <iostream>
#include <deque>

int main()
{
    std::deque<int> deq(10);

    try {
        deq.at(3) = 10;
        int a = deq.at(3);
        std::cout << a << std::endl;

        deq.at(50) = 10;  // 範囲外アクセス

        // 実行されない
        std::cout << "!!!!!" << std::endl;
    }
    catch (const std::out_of_range& ex) {
        std::cerr << ex.what() << std::endl;
    }
}

実行結果：

10
invalid deque<T> subscript

実行結果の２行目は、Visual Studio 2017 の場合です。この部分は、環境によって異なるはずです。

また、deque の先頭要素（の参照）を frontメンバ関数で、末尾の要素（の参照）を backメンバ関数で取得できます。これらのメンバ関数は、deque が空の場合には未定義の動作になることに注意してください。

#include <iostream>
#include <deque>

int main()
{
    std::deque<int> deq(10);

    const std::deque<int>::size_type size = deq.size();
    for (int i = 0; i < static_cast<int>(size); ++i) {
        deq[i] = i;
    }

    std::cout << deq.front() << std::endl;
    std::cout << deq.back() << std::endl;
}

実行結果：

0
9

代入 🔗

deque は、テンプレート実引数が同一であれば、代入演算子を使ってコピーできます。

また、assignメンバ関数を使うこともできます。

#include <iostream>
#include <deque>

typedef std::deque<int> IntDeque;

void PrintDeque(const IntDeque& deq)
{
    const IntDeque::const_iterator itEnd = deq.end();
    for (IntDeque::const_iterator it = deq.begin(); it != itEnd; ++it) {
        std::cout << *it << "\n";
    }
    std::cout << std::endl;
}

int main()
{
    IntDeque deq;

    deq.assign(5, 3);  // 5個の 3 を代入
    PrintDeque(deq);

    const int a[10] = { 0, 10, 20, 30, 40, 50, 60, 70, 80, 90 };
    deq.assign(a, a + 10);  // 範囲内の要素を代入
    PrintDeque(deq);
}

実行結果：

assignメンバ関数の１つ目の使い方は、第２引数に指定した要素のコピーを、第１引数に指定した個数だけ代入します。

２つ目の方は、イテレータを使って範囲を指定し、その範囲内にある要素のコピーを代入します。

追加・挿入 🔗

要素を挿入する方法はいくつかあります。

１つ目の方法として、push_backメンバ関数があります。これは、末尾に要素を追加します。

２つ目の方法は、push_frontメンバ関数です。こちらは、先頭に要素を追加します。

deque では、これらのメンバ関数を使うと、イテレータが無効化されることに注意してください。つまり、既存のイテレータは有効な要素を指さなくなっていると考える必要があります。ただし、要素への参照（やポインタ）は無効になりません。

#include <iostream>
#include <deque>

typedef std::deque<int> IntDeque;

void PrintDeque(const IntDeque& deq)
{
    const IntDeque::const_iterator itEnd = deq.end();
    for (IntDeque::const_iterator it = deq.begin(); it != itEnd; ++it) {
        std::cout << *it << "\n";
    }
    std::cout << std::endl;
}

int main()
{
    IntDeque deq;

    for (int i = 0; i < 5; ++i) {
        deq.push_back(i);
    }

    for (int i = 0; i < 5; ++i) {
        deq.push_front(i);
    }

    PrintDeque(deq);
}

実行結果：

３つ目の方法は、insertメンバ関数です。これは、イテレータを使って、任意の位置に要素を挿入します。

#include <iostream>
#include <deque>

typedef std::deque<int> IntDeque;

void PrintDeque(const IntDeque& deq)
{
    const IntDeque::const_iterator itEnd = deq.end();
    for (IntDeque::const_iterator it = deq.begin(); it != itEnd; ++it) {
        std::cout << *it << "\n";
    }
    std::cout << std::endl;
}

int main()
{
    IntDeque deq(5, 3);

    IntDeque::iterator it;

    it = deq.insert(deq.end()--, 0);   // 末尾に 0 を挿入
    PrintDeque(deq);

    deq.insert(it, 3, 99);             // 0 の手前に 99 を 3個挿入
    PrintDeque(deq);

    const int a[] = {10, 11, 12};
    deq.insert(deq.begin(), a, a + 3); // ある範囲から先頭へ挿入
    PrintDeque(deq);
}

実行結果：

使い方が３通りありますが、どれでも第１引数が挿入位置を表しています。挿入位置は、イテレータを使って指定し、そのイテレータが指している位置へ挿入されます。たとえば、beginメンバ関数で取得したイテレータを指定すれば、先頭要素になるように挿入できます。

１つ目の使い方では、第２引数に挿入する値を指定します。この形式の場合は、戻り値で、挿入された値を指すイテレータが返されます。

２つ目の使い方では、同じ値を複数個まとめて挿入できます。第２引数が個数、第３引数が挿入する値です。

３つ目の使い方では、第２第３の引数で指定した範囲内にある要素を挿入します。これは、別のコンテナや配列からコピーしたい場合に使います。

insertメンバ関数の場合は、イテレータや参照がすべて無効になることに注意してください。

削除 🔗

「削除」は、コンテナから要素を取り除くということです。格納されている要素が new で生成されたものであるのなら、取り除くだけではなく delete を行わなければなりません。「削除」はそういった処理までは面倒を見ないことに注意してください。

また、deque の場合、未使用になった領域のメモリが解放されることがあります。ただし、この挙動は実装次第なので、確実なものではありません。

まず、pop_backメンバ関数と pop_frontメンバ関数があります。前者は末尾にある要素を削除し、後者は先頭にある要素を削除します。これらのメンバ関数は、コンテナが空の状態では未定義の動作となることに注意してください。

#include <iostream>
#include <deque>

typedef std::deque<int> IntDeque;

void PrintDeque(const IntDeque& deq)
{
    const IntDeque::const_iterator itEnd = deq.end();
    for (IntDeque::const_iterator it = deq.begin(); it != itEnd; ++it) {
        std::cout << *it << "\n";
    }
    std::cout << std::endl;
}

int main()
{
    IntDeque deq;

    for (int i = 0; i < 5; ++i) {
        deq.push_back(i);
    }

    deq.pop_front();
    deq.pop_back();

    PrintDeque(deq);
}

実行結果：

1
2
3

次に、eraseメンバ関数を使う方法です。

#include <iostream>
#include <deque>

typedef std::deque<int> IntDeque;

void PrintDeque(const IntDeque& deq)
{
    const IntDeque::const_iterator itEnd = deq.end();
    for (IntDeque::const_iterator it = deq.begin(); it != itEnd; ++it) {
        std::cout << *it << "\n";
    }
    std::cout << std::endl;
}

int main()
{
    IntDeque deq;

    for (int i = 0; i < 5; ++i) {
        deq.push_back(i);
    }

    deq.erase(deq.begin());  // 先頭要素を削除
    PrintDeque(deq);

    deq.erase(deq.begin() + 1, deq.end());  // 先頭の次から末尾まで削除
    PrintDeque(deq);
}

実行結果：

eraseメンバ関数の使い方は２通りで、イテレータを１つ渡すか、２つ渡すかの違いです。前者の場合はイテレータが指す要素を削除し、後者の場合は２つのイテレータで作られる範囲内の要素が削除されます。

eraseメンバ関数は、削除された要素の次の有効な要素を指すイテレータを返します。また、イテレータや参照は無効化されます。

最後に、要素をすべて削除する場合ですが、これは clearメンバ関数を使うだけです。

#include <iostream>
#include <deque>
#include <cassert>

int main()
{
    std::deque<int> deq;

    for (int i = 0; i < 5; ++i) {
        deq.push_back(i);
    }

    deq.clear();
    assert(deq.empty());
}

実行結果：

イテレータ 🔗

イテレータに関する詳細は、第１４章であらためて取り上げますが、ここでは、deque におけるイテレータについて、簡単に紹介します。

他のコンテナと同様に、最初の要素を指すイテレータを beginメンバ関数で、最後の要素の次を指すイテレータを endメンバ関数で取得できます。また、逆方向に走査するための逆イテレータの場合に最初の要素を指すイテレータを rbeginメンバ関数で、最後の要素の次を指すイテレータを rendメンバ関数で取得できます。

#include <iostream>
#include <deque>

int main()
{
    typedef std::deque<int> IntDeque;

    IntDeque deq;

    for (int i = 0; i < 10; ++i) {
        deq.push_back(i);
    }

    IntDeque::const_iterator itEnd = deq.end();
    for (IntDeque::const_iterator it = deq.begin(); it != itEnd; ++it) {
        std::cout << *it << "\n";
    }
    std::cout << std::endl;

    IntDeque::const_reverse_iterator ritEnd = deq.rend();
    for (IntDeque::const_reverse_iterator rit = deq.rbegin(); rit != ritEnd; ++rit) {
        std::cout << *rit << "\n";
    }
    std::cout << std::endl;
}

実行結果：

beginメンバ関数や endメンバ関数で取得できるイテレータの型は、std::deque<T>::iterator型、あるいはその const版である std::deque<T>::const_iterator型です。後者の場合は、イテレータを通して要素を書き換えることができません。

また、rbeginメンバ関数、rendメンバ関数の場合は、std::deque<T>::reverse_iterator型、あるいはその const版である std::deque<T>::const_reverse_iterator型になります。これらイテレータの型は、deque内部で typedef されているものですが、その正体（typedef の元になる型) が何であるかは実装依存です。

deque のイテレータは、vector と同様に、ランダムアクセス機能を提供しています。そのため、「deq.begin() + 3」のような感じで、指す位置を一気に移動できます。もちろん、++演算子や –演算子も使えます。

練習問題 🔗

問題①　deque は vector と酷似したインターフェースを備えています。deque を使った方が良いと思われる場面と、vector を使った方が良いと思われる場面をそれぞれ考えてみてください。

解答ページはこちら。

参考リンク 🔗

Programming Place Plus　C++編　参考書籍
　– 当サイトの参考書籍一覧ページ。C++ に関する書籍を多数紹介。
Programming Place Plus　C++編　リンク集
　– 当サイトの参考Webサイト集。C++ の全般的な学習に有益なサイトを紹介。

更新履歴 🔗

’2021/9/30
- C++11 に関する記述を削除（C++11 は新C++編で対応する）

’2019/2/12　VisualStudio 2015 の対応終了。

’2018/4/5　VisualStudio 2013 の対応終了。

’2018/4/2　「VisualC++」という表現を「VisualStudio」に統一。

’2018/1/5　コンパイラの対応状況について、対応している場合は明記しない方針にした。

’2017/7/30　clang 3.7 (Xcode 7.3) を、Xcode 8.3.3 に置き換え。

≪さらに古い更新履歴≫

’2017/3/25　VisualC++ 2017 に対応。

’2016/10/15　clang の対応バージョンを 3.7 に更新。

’2015/10/12　clang の対応バージョンを 3.4 に更新。

’2015/9/5　VisualC++ 2012 の対応終了。

’2015/8/18　VisualC++ 2010 の対応終了。

’2015/8/15　VisualC++ 2015 に対応。

’2015/1/24　新規作成。

前の章へ　（第６章　list）

次の章へ　（第８章　set と multiset）

C++編のトップページへ

Programming Place Plus のトップページへ

はてなブックマークに保存	Pocket に保存	Facebook でシェア
X でポスト／フォロー	LINE で送る	noteで書く
RSS	管理者情報	プライバシーポリシー

この章の概要 🔗

deque 🔗

サイズ 🔗

生成と初期化 🔗

破棄 🔗

要素のアクセス 🔗

代入 🔗

追加・挿入 🔗

削除 🔗

イテレータ 🔗

練習問題 🔗

参考リンク 🔗

更新履歴 🔗