C++編【標準ライブラリ】 第12章 priority_queue

このエントリーをはてなブックマークに追加

この章の概要

この章の概要です。

priority_queue

priority_queue は、 コンテナアダプタの一種で、その名の通り、 優先度付きキュー(アルゴリズムとデータ構造編【データ構造】第10章)を提供します。
使用するには、queue(第11章)と同じく、 queue という名前の標準ヘッダをインクルードする必要があります(priority_queue ではありません)。

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

namespace std {
	template <typename T,
	          typename Container = vector<T>,
	          typename Compare = less<typename Container::value_type> >
	class priority_queue {
	};
}

テンプレートパラメータ T は、格納する要素の型です。

テンプレートパラメータ Container は、要素を格納するために内部で使用するコンテナを指定します。 デフォルトでは、vector(第5章)が使用されます。 Container には、deque(第7章) や list(第6章) のような他のコンテナを指定することができます。
指定できるコンテナの種類には条件があり、 push_backメンバ関数、pop_backメンバ関数、frontメンバ関数を持っている必要があります。 結果的に、標準の STLコンテナとしては、vector、list、deque のいずれかから選択することになります。

C++11 の場合、emplace_backメンバ関数も必要です。 C++11 の vector、list、deque には、このメンバ関数が追加されているので、条件は満たしています。

テンプレートパラメータ Compare は、ソートの基準を指定します。
デフォルトでは std::less(第19章)が指定されていますが、 これは、要素の大小関係の比較に <演算子を用いることを意味しています。 つまり、T型の要素2つを <演算子で比較し、どちらがより小さいかを判断し、小さい方が手前に来るように並び替えます。 したがって、デフォルトでは昇順にソートされます。 優先度が高い要素ほど、コンテナの後ろの方に来るようになっている(だから、内部のコンテナに pop_backメンバ関数が必要)ので、 直感的とは言い難いかも知れませんが、<演算子が使われると、優先度が「大きい」ものが優先されることになります。
なお、ソートは安定(アルゴリズムとデータ構造編【整列】第0章)ではないので、 同じ優先度を持った要素が複数存在する場合、どちらが優先されるかは不定です。

なお、使用しているコンテナの型は、container_type という名前で型別名が与えられています。

サイズ

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

現在の「サイズ」を知るには、sizeメンバ関数を使います。 また、「サイズ」が 0 かどうかは、emptyメンバ関数で調べられます。
空かどうかを知りたい場合は、効率面から、emptyメンバ関数を優先した方が良いです。

これらの関数は、内部で使用されているコンテナの同名関数を呼び出すように実装されます。 C++03 時点の list においては、sizeメンバ関数の効率が悪い可能性があります(第6章参照)。

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

#include <iostream>
#include <queue>

typedef std::priority_queue<int> IntPrioQueue;

int main()
{
	IntPrioQueue iPrioQueue;

	for (int i = 0; i < 5; ++i) {
		iPrioQueue.push(i);
	}

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

実行結果

5
false

ソート基準

priority_queue のソート基準は、テンプレート引数で指定するか、コンストラクタの引数で指定します。

まず、テンプレート引数で指定する方法を見ていきましょう。

#include <iostream>
#include <queue>
#include <functional>

typedef std::priority_queue<int> IntPrioQueue;
typedef std::priority_queue<int, std::vector<int>, std::greater<int> > IntReversePrioQueue;

int main()
{
	IntPrioQueue iPrioQueue1;
	IntReversePrioQueue iPrioQueue2;

	for (int i = 0; i < 5; ++i) {
		iPrioQueue1.push(i);
		iPrioQueue2.push(i);
	}

	while (!iPrioQueue1.empty()) {
		std::cout << iPrioQueue1.top() << " ";
		iPrioQueue1.pop();
	}
	std::cout << std::endl;
	while (!iPrioQueue2.empty()) {
		std::cout << iPrioQueue2.top() << " ";
		iPrioQueue2.pop();
	}
	std::cout << std::endl;
}

実行結果

4 3 2 1 0
0 1 2 3 4

typedef によって、2つの型の別名を定義しています。
IntPrioQueue の方は、ソート基準を定義していないので、デフォルト値 (std::less<>) が使用されます。 この場合、ソートには <演算子が使用されることになり、int型の要素達は昇順に並びます。
IntReversePrioQueue の方は、ソート基準として std::greater<> を使用しました。 こちらは、ソートに >演算子を使用するので、要素は降順に並びます。

std::less<> や std::greater<> は、標準の関数オブジェクトで、 functional という標準ヘッダに定義されています。 関数オブジェクトについては、第19章で取り上げます。

2つの priority_queue は、共通の要素で初期化されていますが、要素を順番に出力してみると、逆の順序に並ぶことが分かります。 topメンバ関数は、一番優先度が高い要素(キューの末尾にある要素)を返し、popメンバ関数は実際にキューから取り除きます。 そのため、IntPrioQueue の方は、大きい数の要素から順に取り除かれ、 IntReversePrioQueue の方は、小さい数の要素から順に取り除かれています。

このように、ソート基準をテンプレート引数で指定する方法では、コンテナの型自体が異なったものになります。 そのため、型の不一致がコンパイラによって検出されます。これは利点でもあるし、不便さが生まれることもあります。 実際、型が違うため、要素を出力する部分の処理は、IntPrioQueue と IntReversePrioQueue とで同じですが、 テンプレートを使わない普通の関数にまとめることができません。


次に、コンストラクタの引数で指定する方法です。

#include <iostream>
#include <queue>

template <typename T>
class MyCompare {
public:
	enum Mode {
		MODE_NORMAL,
		MODE_REVERSE,
	};

public:
	explicit MyCompare(Mode mode = MODE_NORMAL) :
		mMode(mode)
	{}

	inline bool operator()(const T& a, const T& b) const
	{
		return mMode == MODE_NORMAL ? a < b : a > b;
	}

private:
	Mode	mMode;
};

typedef std::priority_queue<int, std::vector<int>, MyCompare<int> > IntPrioQueue;

void PrintAndClearIntPrioQueue(IntPrioQueue& iPrioQueue)
{
	while (!iPrioQueue.empty()) {
		std::cout << iPrioQueue.top() << " ";
		iPrioQueue.pop();
	}
	std::cout << std::endl;
}

int main()
{
	IntPrioQueue iPrioQueue1;
	IntPrioQueue iPrioQueue2((MyCompare<int>(MyCompare<int>::MODE_REVERSE)));

	for (int i = 0; i < 5; ++i) {
		iPrioQueue1.push(i);
		iPrioQueue2.push(i);
	}

	PrintAndClearIntPrioQueue(iPrioQueue1);
	PrintAndClearIntPrioQueue(iPrioQueue2);
}

実行結果

4 3 2 1 0
0 1 2 3 4

この方法の場合は、ソート基準を表現する関数オブジェクトを独自で用意します。 ここで用意した MyCompare は、コンストラクタに渡す引数によって、ソートの方法を切り替えられるようになっています。
priority_queue の2つ目のテンプレートパラメータには、MyCompare を指定しています。 ソート基準は、コンストラクタで指定するので、priority_queue としては、1つの型で済みます。 実際、要素を出力する部分を、PrintAndClearIntPrioQueue関数にまとめることができています。

上記サンプルプログラムで、iPrioQueue2 に渡す実引数全体が ( ) で囲まれていることに注意して下さい。 これがないと、構文解析の問題で、コンパイルエラーになります。

なお、MyCompare に、デフォルトコンストラクタ(【言語解説】第13章)が無いと、 priority_queue のコンストラクタで、必ず明示的にソート基準を指定しないといけなくなります。

生成と初期化

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

#include <queue>
#include <vector>
#include <functional>

typedef std::priority_queue<int> IntPrioQueue;

int main()
{
	IntPrioQueue::container_type c;
	
	const int a[] = {4, 7, 2, 3, 5};

	IntPrioQueue iPrioQueue1;                                // 空
	IntPrioQueue iPrioQueue2((std::less<int>()));            // ソート基準を指定。要素は空
	IntPrioQueue iPrioQueue3(std::less<int>(), c);           // ソート基準を指定し、内部で使用しているコンテナと同種のコンテナからコピー
	IntPrioQueue iPrioQueue4(iPrioQueue3);                   // 他の priority_queue からコピー
	IntPrioQueue iPrioQueue5(a, a + 5);                      // ある範囲から要素を作成
	IntPrioQueue iPrioQueue6(a, a + 5, std::less<int>());    // ソート基準を指定し、ある範囲から要素を作成
	IntPrioQueue iPrioQueue7(a, a + 5, std::less<int>(), c); // ソート基準を指定し、内部で使用しているコンテナと同種のコンテナと、ある範囲から要素を作成
}

iPrioQueue2 は、ソート基準を指定しています。

iPrioQueue3 のように、第2引数で、内部で使用しているコンテナと同種のコンテナを指定でき、 この場合、指定したコンテナの要素をコピーして、新しい priority_queue を生成します。 内部で使用するコンテナの型は、std::priority_queue<>::container_type で得られます。
第1引数のところにソート基準の指定があるため、このスタイルで初期化するには、ソート基準の指定も行わないといけません。 ソート基準を変更するつもりが無いのなら、std::less<> を渡して下さい。

iPrioQueue5、iPrioQueue6、iPrioQueue7 は、2つのイテレータを使って表現される範囲内にある要素を使って初期化します。 この3種のコンストラクタに関しては、テンプレートコンストラクタ(【言語解説】第23章)になっており、 priority_queue の要素の型と、イテレータが指す先の要素の型は、完全一致していなくても、変換可能であれば受け付けられます。
iPrioQueue7 については少しわかりにくいですが、 第4引数で指定したコンテナのすべての要素と、第1,2引数で指定した範囲内の要素とを加えて初期化します。

STLコンテナの場合、コンストラクタからアロケータ(第32章)を指定できますが、コンテナアダプタにはありません。 コンテナアダプタの場合、使用するアロケータは、内部で使用しているコンテナ次第で決まります。

C++11 (生成と初期化)

C++11 で、コンストラクタ周りは強化されています。

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

IntPrioQueue::container_type c;
const int a[] = {4, 7, 2, 3, 5};

IntPrioQueue iPrioQueue8(std::less<int>(), std::move(c));        // ソート基準を指定し、内部で使用しているコンテナと同種のコンテナからムーブ
IntPrioQueue iPrioQueue9(std::move(iPrioQueue8));                // 他の priority_queue からムーブ
IntPrioQueue iPrioQueue10(a, a + 5, std::less<int>(), std::move(c)); // ソート基準を指定し、内部で使用しているコンテナと同種のコンテナと、ある範囲から要素を作成

また、アロケータを指定できるようになりました。

std::allocator<int> alloc;

IntPrioQueue iPrioQueue11(alloc);                                    // 要素は空
IntPrioQueue iPrioQueue12(std::less<int>(), alloc);                  // ソート基準を指定。要素は空
IntPrioQueue iPrioQueue13(std::less<int>(), c, alloc);               // ソート基準を指定し、内部で使用しているコンテナと同種のコンテナからコピー
IntPrioQueue iPrioQueue14(std::less<int>(), std::move(c), alloc);    // ソート基準を指定し、内部で使用しているコンテナと同種のコンテナからムーブ
IntPrioQueue iPrioQueue15(iPrioQueue14, alloc);                      // 他の priority_queue からコピー
IntPrioQueue iPrioQueue16(std::move(iPrioQueue15), alloc);           // 他の priority_queue からムーブ

いずれのパターンも、VisualC++ 2013/2015/2017、clang 3.7 は対応しています

破棄

デストラクタでは、priority_queue(が内部で使用しているコンテナ)が確保した領域が破棄されます。

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

比較

他のコンテナと違い、priority_queue 同士を ==、!=、<、<=、>、>= の各演算子で比較することはできません

代入

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

#include <iostream>
#include <queue>

typedef std::priority_queue<int> IntPrioQueue;

void PrintAndClearIntPrioQueue(IntPrioQueue& iPrioQueue)
{
	while (!iPrioQueue.empty()) {
		std::cout << iPrioQueue.top() << " ";
		iPrioQueue.pop();
	}
	std::cout << std::endl;
}

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

	IntPrioQueue iPrioQueue(a, a + 5);
	IntPrioQueue iPrioQueue2;

	iPrioQueue2 = iPrioQueue;

	PrintAndClearIntPrioQueue(iPrioQueue);
	PrintAndClearIntPrioQueue(iPrioQueue2);
}

実行結果

7 5 4 3 2
7 5 4 3 2

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

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

#include <iostream>
#include <queue>

typedef std::priority_queue<int> IntPrioQueue;

void PrintAndClearIntPrioQueue(IntPrioQueue& iPrioQueue)
{
	while (!iPrioQueue.empty()) {
		std::cout << iPrioQueue.top() << " ";
		iPrioQueue.pop();
	}
	std::cout << std::endl;
}

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

	IntPrioQueue iPrioQueue(a, a + 5);
	IntPrioQueue iPrioQueue2;

	iPrioQueue2 = std::move(iPrioQueue);

	PrintAndClearIntPrioQueue(iPrioQueue);
	PrintAndClearIntPrioQueue(iPrioQueue2);
}

実行結果


7 5 4 3 2

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

要素のアクセス

priority_queue は、格納されている要素の中で、最も優先度の高い要素にしかアクセスできません。 このためには、topメンバ関数を使用します。

#include <iostream>
#include <queue>

typedef std::priority_queue<int> IntPrioQueue;

int main()
{
	IntPrioQueue iPrioQueue;

	for (int i = 0; i < 5; ++i) {
		iPrioQueue.push(i);
	}

	std::cout << iPrioQueue.top() << std::endl;

	std::cout << iPrioQueue.size() << std::endl;
}

実行結果

4
5

topメンバ関数は最も優先度が高い要素の参照を返します。 queue の場合と違って、constメンバ関数版しかありません。 これは、要素を書き換えられてしまうと、優先度が変化してしまい、その後の挙動が不適切になる可能性があるためです。
参照で返されることから分かるように、ヌルを知ることはできませんから、 空の priority_queue に対する topメンバ関数の呼び出しは、未定義の動作になることに注意して下さい

上記のサンプルプログラムの sizeメンバ関数の結果の出力からも分かるように、 topメンバ関数は、priority_queue から要素を取り出すわけではありません。 要素を取り出したいのであれば、popメンバ関数を使う必要があります。

なお、topメンバ関数は、内部で使用しているコンテナの frontメンバ関数を呼び出す形で実装されます

追加

priority_queue への要素の追加には、pushメンバ関数を使用します。 順序は、優先度によってしか決定できないので、挿入位置を選択する余地はありません。

#include <iostream>
#include <queue>

typedef std::priority_queue<int> IntPrioQueue;

int main()
{
	IntPrioQueue iPrioQueue;

	for (int i = 0; i < 5; ++i) {
		iPrioQueue.push(i);
	}

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

実行結果

5
false

なお、pushメンバ関数は、内部で使用しているコンテナの push_backメンバ関数を呼び出す形で実装されます

C++11(移動による追加)

C++11 では、移動による要素の追加ができるようになっています。

iPrioQueue.push(std::move(value));

VisualC++ 2013/2015/2017、clang 3.7 のいずれでも使用できます

C++11(emplace)

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

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

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

emplaceメンバ関数は、内部で使用しているコンテナの emplace_backメンバ関数を呼び出す形で実装されます

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

削除

priority_queue から要素を削除するには、popメンバ関数を使用します。 必ず、優先度が一番高い要素が削除されます。
なお、priority_queue が空の場合に使用すると、未定義の動作となるので注意して下さい

#include <iostream>
#include <queue>

typedef std::priority_queue<int> IntPrioQueue;

int main()
{
	IntPrioQueue iPrioQueue;

	for (int i = 0; i < 5; ++i) {
		iPrioQueue.push(i);
	}

	while (!iPrioQueue.empty()) {
		iPrioQueue.pop();
	}

	std::cout << iPrioQueue.size() << std::endl;
}

実行結果

0

popメンバ関数の戻り値は void であり、何も返しません。 もし、要素の値を知る必要があるのなら、先に topメンバ関数を使用するようにします。

#include <iostream>
#include <queue>

typedef std::priority_queue<int> IntPrioQueue;

int main()
{
	IntPrioQueue iPrioQueue;

	for (int i = 0; i < 5; ++i) {
		iPrioQueue.push(i);
	}

	while (!iPrioQueue.empty()) {
		std::cout << iPrioQueue.top() << "を取り除きます" << std::endl;
		iPrioQueue.pop();
	}
}

実行結果

4を取り除きます
3を取り除きます
2を取り除きます
1を取り除きます
0を取り除きます

popメンバ関数が要素を返さないのは、例外安全(【言語解説】第31章)を保証するためです。 もし、popメンバ関数が戻り値を返すとすれば、それは格納されている要素の「コピー」になります(格納されている要素は削除したい訳だから)が、 これを呼び出し元が受け取るまでの課程で例外が発生すると、削除してしまった要素が完全に失われてしまいます。

なお、popメンバ関数は、内部で使用しているコンテナの pop_backメンバ関数を呼び出す形で実装されます


練習問題

問題@ 要素の型が std::string で、文字列の長さが短いものほど優先度が高い priority_queue を作成して下さい。


解答ページはこちら

参考リンク

更新履歴

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

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

'2015/10/18 新規作成。



前の章へ

次の章へ

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

Programming Place Plus のトップページへ