`std::priority_queue` とは?

std::priority_queue は、C++で利用できるコンテナ・アダプタの1つで、優先順位付きキューを実現しているもの。
テンプレート・パラメータ Compare によって優先順位の付け方を変更できる。

queue

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

一般的な利用方法

パラメータ Compare をデフォルト std::less<TYPE> のまま使用すると以下の通りになる。

sample.1.cpp

#include <cstdio>
#include <queue>

int
main()
{
	int a[] = {5, 4, 6, 3, 7, 2, 8, 1, 9, 0};
	std::priority_queue<int> q;

	for (size_t i(0); i < sizeof(a) / sizeof(a[0]); ++i) {
		q.push(a[i]);
	}

	while (!q.empty()) {
		std::printf("%d\n", q.top());
		q.pop();
	}

	return 0;
}

> clang++ -Wall -Weffc++ -std=c++11 sample.1.cpp -o sample.exe
> ./sample.exe
9
8
7
6
5
4
3
2
1
0

また、std::greater<TYPE> に変更すると以下の通りになる。

sample.2.cpp

#include <cstdio>
#include <queue>
#include <vector>

int
main()
{
	int a[] = {5, 4, 6, 3, 7, 2, 8, 1, 9, 0};
	std::priority_queue< int, std::vector<int>, std::greater<int> > q;

	for (size_t i(0); i < sizeof(a) / sizeof(a[0]); ++i) {
		q.push(a[i]);
	}

	while (!q.empty()) {
		std::printf("%d\n", q.top());
		q.pop();
	}

	return 0;
}

> clang++ -Wall -Weffc++ -std=c++11 sample.2.cpp -o sample.exe
> ./sample.exe
0
1
2
3
4
5
6
7
8
9

std::priority_queue の要素の型が組み込み型やその延長のもの (例: std::pair や std::tuple で組み込み型を拡張した型) であれば、これら2つの方法でほとんどの利用シーンをカバーできる。

ラムダ式のパラメータ `Compare` への代入?

ところが、std::less<TYPE> や std::greater<TYPE> では対応できない場合がある。

例えば次の様な優先順位の付け方を想定する (要素の型を int とし、安定性は問わない) と、
上記2つの比較関数オブジェクトでは対応できない。

要素AとBに対して、Aが偶数でBが奇数なら、AはBより優先度が低い。
要素AとBに対して、AとBの両方が偶数なら、値が大きい方が優先度が低い。
要素AとBに対して、AとBの両方が奇数なら、値が小さい方が優先度が低い。

これをラムダ式で表現すると以下のようになる。
なおラムダ式において、引数 l が優先度の低い要素であるときに true を返却していることに注意。

sample.3.cpp

#include <cstdio>
#include <queue>
#include <vector>

int
main()
{
	int a[] = {5, 4, 6, 3, 7, 2, 8, 1, 9, 0};
	auto c = [](int l, int r) { if (l % 2 == 0) return r % 2 != 0 || l >= r; else return r % 2 != 0 && l < r; };
	std::priority_queue<int, std::vector<int>, decltype(c)> q(c);

	for (size_t i(0); i < sizeof(a) / sizeof(a[0]); ++i) {
		q.push(a[i]);
	}

	while (!q.empty()) {
		std::printf("%d\n", q.top());
		q.pop();
	}

	return 0;
}

> clang++ -Wall -Weffc++ -std=c++11 sample.3.cpp -o sample.exe
> ./sample.exe
9
7
5
3
1
0
2
4
6
8

このとき、直感的に以下のように書いてもコンパイルできない。

sample.4.cpp

#include <cstdio>
#include <queue>
#include <vector>

int
main()
{
	int a[] = {5, 4, 6, 3, 7, 2, 8, 1, 9, 0};
	auto c = [](int l, int r) { if (l % 2 == 0) return r % 2 != 0 || l >= r; else return r % 2 != 0 && l < r; };
	std::priority_queue<int, std::vector<int>, c> q;

	for (size_t i(0); i < sizeof(a) / sizeof(a[0]); ++i) {
		q.push(a[i]);
	}

	while (!q.empty()) {
		std::printf("%d\n", q.top());
		q.pop();
	}

	return 0;
}

> clang++ -Wall -Weffc++ -std=c++11 sample.4.cpp -o sample.exe
sample.4.cpp:12:45: error: template argument for template type parameter must be a type
        std::priority_queue<int, std::vector<int>, c> q;
                                                   ^
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/queue:385:17: note:
      template parameter is declared here
          class _Compare = less<typename _Container::value_type> >
                ^
1 error generated.

std::priority_queue とは?

一般的な利用方法

ラムダ式のパラメータ Compare への代入?

参考

`std::priority_queue` とは?

ラムダ式のパラメータ `Compare` への代入?