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.