std::priority_queue の使い方および優先順位の付け方の変更

# `std::priority_queue` とは?

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

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

# 一般的な利用方法

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

```C++: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>` に変更すると以下の通りになる。

```C++: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` を返却していることに注意。

```C++: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

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

```C++: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.

# 参考

* http://cpprefjp.github.io/reference/queue/priority_queue.html
* http://cpprefjp.github.io/lang/cpp11/lambda_expressions.html
* http://stackoverflow.com/questions/5807735/c-priority-queue-with-lambda-comparator-error