C++編【標準ライブラリ】 第7章 deque

この章の概要

この章の概要です。

deque

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

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

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

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

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

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

std::deque<int> intDeque;

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

サイズ

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メンバ関数を使うと、サイズを変更できます。
現在のサイズよりも大きな値を指定すると、そのサイズになるまで要素を充填します。 このとき、要素の型のデフォルトコンストラクタが使用されます。 もし、第2引数を指定している場合には、その値を要素の初期化に使用します。
また、現在のサイズよりも小さい値を指定した場合は、指定したサイズになるまで、 要素が末尾にあるものから順に取り除かれます。

#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);
}

実行結果

0
0
0
0
0

0
0
0
0
0
99
99
99
99
99

0

生成

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); // イテレータで指定された範囲からコピー
}

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

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

C++11 (生成)

C++11 で、コンストラクタ周りは強化されています。 まず、std::initializer_list を使用できるようになりました。

int main()
{
	std::deque<int> deq6 {0, 1, 2};       // std::initializer_list
}

また、ムーブコンストラクタが追加されています。

int main()
{
	std::deque<int> deq7(std::move(deq6));  // ムーブコンストラクタ
}

なお、ここまでに取り上げた方法のうち、v2 の形を除いたすべてで、引数の末尾でアロケータを指定できます。

std::initializer_list、ムーブコンストラクタともに、VisualC++ 2013/2015/2017、clang 3.7 のいずれも対応しています。

破棄

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

仮想デストラクタ(【言語解説】第27章)ではないので、 deque を継承して使用することは不適切であることに注意して下さい

要素のアクセス

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

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

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

範囲外アクセスへの備えが欲しければ、atメンバ関数を使用します。 atメンバ関数は、添字を引数に取り、その位置にある要素の参照を返します。 [] を使う場合と違うのは、範囲外アクセスになったときに std::out_of_range例外を送出する点です
例外については、【言語解説】第30章で、std::out_of_range については第25章で解説しますが、 ここでは使用例だけ挙げておきます。

#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

実行結果の2行目は、VisualC++ 2013/2015/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);
}

実行結果

3
3
3
3
3

0
10
20
30
40
50
60
70
80
90

assignメンバ関数の1つ目の使い方は、第2引数に指定した要素のコピーを、第1引数に指定した個数だけ代入します。
2つ目の方は、イテレータを使って範囲を指定し、その範囲内にある要素のコピーを代入します。

C++11 (代入、assign の std::initializer_list対応)

C++11 の代入演算子および assignメンバ関数では、std::initializer_list を使えるようになりました。

#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 = { 0, 1, 2 };
	PrintDeque(deq);

	deq.assign({ 0, 10, 20 });
	PrintDeque(deq);
}

実行結果

0
1
2

0
10
20

std::initializer_list は、VisualC++ 2013/2015/2017、clang 3.7 のいずれも対応しています。

C++11 (ムーブ代入演算子)

C++11 では、ムーブ代入演算子が追加されています。

#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 deq1(5, 3);
	IntDeque deq2;

	deq2 = std::move(deq1);
	PrintDeque(deq1);
	PrintDeque(deq2);
}

実行結果


3
3
3
3
3

ムーブ代入演算子は、VisualC++ 2013/2015/2017、clang 3.7 のいずれでも使用できます。

挿入

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

1つ目の方法として、push_backメンバ関数があります。 これは、末尾に要素を追加します。
2つ目の方法は、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);
}

実行結果

4
3
2
1
0
0
1
2
3
4

3つ目の方法は、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);
}

実行結果

3
3
3
3
3
0

3
3
3
3
3
99
99
99
0

10
11
12
3
3
3
3
3
99
99
99
0

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

1つ目の使い方では、第2引数に挿入する値を指定します。 この形式の場合は、戻り値で、挿入された値を指すイテレータが返されます。
2つ目の使い方では、同じ値を複数個まとめて挿入できます。 第2引数が個数、第3引数が挿入する値です。
3つ目の使い方では、第2第3の引数で指定した範囲内にある要素を挿入します。 これは、別のコンテナや配列からコピーしたい場合に使います。

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

C++11(移動による挿入)

C++11 では、移動による挿入ができるようになっています。
まず、push_backメンバ関数が対応しています。

deq.push_back(std::move(value));

同様に、push_frontメンバ関数が対応しています。

deq.push_front(std::move(value));

insertメンバ関数の場合は、挿入する要素が1つだけになる形式のみ対応します。

deq.insert(it, std::move(value));

これらのメンバ関数は、VisualC++ 2013/2015/2017、clang 3.7 のいずれでも使用できます

C++11(emplace_back、emplace_front、emplace)

push_back、push_front、insert の各メンバ関数は、deque の外で挿入するオブジェクトを作り、それをコピー(または移動)する必要があります。 これは、少なくとも一時オブジェクトを生成するコストが掛かるため(コピーの場合は、更にコピーのコスト)、 使い方によっては非効率さがあります。

C++11 では、要素のコンストラクタに渡す引数だけを指定し、メンバ関数内でオブジェクトを作らせるという方法が使えるようになりました。 push_backメンバ関数なら emplace_backメンバ関数が、 push_frontメンバ関数なら emplace_frontメンバ関数が、 insertメンバ関数なら emplaceメンバ関数が対応します。

std::deque<MyClass> deq;

deq.push_back(MyClass(10, "abc"));   // 一時オブジェクトを作ってコピー
deq.emplace_back(10, "abc");         // コンストラクタの引数だけ指定し、関数内で生成

deq.push_front(MyClass(10, "abc"));  // 一時オブジェクトを作ってコピー
deq.emplace_front(10, "abc");        // コンストラクタの引数だけ指定し、関数内で生成

deq.insert(it, MyClass(10, "abc"));  // 一時オブジェクトを作ってコピー
deq.emplace(it, 10, "abc");          // コンストラクタの引数だけ指定し、関数内で生成

insertメンバ関数はオーバーロードされていますが、emplaceメンバ関数は1つだけです。

これらのメンバ関数は、VisualC++ 2013/2015/2017、clang 3.7 のいずれでも使用できます

C++11(insert の std::initializer_list対応)

C++11 では、insertメンバ関数が std::initializer_list に対応しています。

deq.insert(it, {10, 20, 30});

VisualC++ 2013/2015/2017、clang 3.7 のいずれも対応しています。

C++11(insert のイテレータの const化)

C++03 までの insertメンバ関数は、要素の挿入位置を指定する第1引数の型が、std::deque<T>::iterator型になっていました。 そのため、この引数の意味は、挿入位置を示すことだけなので constイテレータで問題ないはずなのに、constイテレータを渡すことができません。

C++11 では、第1引数の型が std::deque<T>::const_iterator型に改められています。

VisualC++ 2013/2015/2017、clang 3.7 のそれぞれで対応されています。

削除

「削除」は、コンテナから要素を取り除くということです。 格納されている要素が 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);
}

実行結果

1
2
3
4

1

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

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());
}

実行結果





C++11(erase のイテレータの const化)

C++03 までの eraseメンバ関数は、要素の位置を指定するイテレータが、std::deque<T>::iterator型になっていました。 そのため、この引数の意味は、位置を示すことだけなので constイテレータで問題ないはずなのに、constイテレータを渡すことができません。

C++11 では、イテレータの型が std::deque<T>::const_iterator型に改められています。

VisualC++ 2013/2015/2017、clang 3.7 のそれぞれで対応されています。

イテレータ

イテレータに関する詳細は、第14章で改めて取り上げますが、 ここでは、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;
}

実行結果

0
1
2
3
4
5
6
7
8
9

9
8
7
6
5
4
3
2
1
0

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」のような感じで、指す位置を一気に移動することができます。 もちろん、++演算子や --演算子も使えます。

C++11(const版のイテレータ取得関数)

C++11 には、必ず constイテレータを返す cbegin、cend、crbegin、crend の各メンバ関数が追加されています。

元々、begin、end、rbegin、rend の各メンバ関数は、非constイテレータを返すものと constイテレータを返すものとでオーバーロードされており、 constイテレータ型の変数で受け取れば、const版を使えました。
新たにこれらのメンバ関数が追加された意義は幾つかあると思いますが、 例えば、C++11 で追加された auto(【言語解説】第2章)を使いやすくすることが考えられます。

std::deque<int> deq;
auto it = deq.begin();   // こう書くと std::deque<int>::iterator型
auto it = deq.cbegin();  // こう書くと std::deque<int>::const_iterator型

これらの追加されたメンバ関数は、VisualC++ 2013/2015/2017、clang 3.7 のいずれでも使用できます。


練習問題

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


解答ページはこちら

参考リンク

更新履歴

'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 新規作成。



前の章へ

次の章へ

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

Programming Place Plus のトップページへ