標準C++ライブラリに priority_queue : 優先順位キュー ゆーのんがあります。
push()メソッドで要素をぶっこむと大きい順に出てきます。
void std_priority_queue() {
priority_queue<int> pq;
for ( int i = 1; i < 10; ++i ) {
pq.push(i);
}
while ( !pq.empty() ) {
cout << pq.top() << ' ';
pq.pop();
}
cout << endl;
}
んなもんだから、"大きいものほど優先順位が高くなる"ように
要素の大小関係を決めてやりゃえぇです。
コレ使ってメッセージやコマンドの待ち行列を処理すれば
急ぎの仕事を優先的に処理できるワケですが、これにはちょいと困った性質がありまして:
// 新幹線 : 優先順位は のぞみ > ひかり > こだま の順。
struct express {
int rank;
wstring name;
express(const wstring& n) : name(n) {
wstring key = n.substr(0,3);
if ( key == L"のぞみ" ) rank = 3;
else if ( key == L"ひかり" ) rank = 2;
else if ( key == L"こだま" ) rank = 1;
else rank = 0;
}
};
struct express_less {
bool operator()(const express& x, const express& y) const {
return x.rank < y.rank;
}
};
void std_priority_queue_isnot_stable() {
priority_queue<express,vector<express>,express_less> pq;
array<wchar_t*,9> trains = {
L"のぞみ１号", L"ひかり２号", L"こだま３号",
L"のぞみ４号", L"ひかり５号", L"こだま６号",
L"のぞみ７号", L"ひかり８号", L"こだま９号",
};
// 上記の順にホームに到着
for ( auto iter = trains.begin(); iter != trains.end(); ++iter ) {
pq.push(express(*iter));
}
// 優先順位の高いものから発車ｵｰﾗｲ
while ( !pq.empty() ) {
wcout << pq.top().name << ' ';
pq.pop();
}
wcout << endl;
}
実行結果:
のぞみ１号 のぞみ７号 のぞみ４号
ひかり５号 ひかり８号 ひかり２号
こだま３号 こだま６号 こだま９号
ご覧の有様。優先順位が同じ要素に対し、push()順が維持されんのですわ。
安定な優先順位キューが欲しければてめぇでこしらえにゃならんです。
つってもさほどにややこしくはありません。list使って実装できます。
void stable_priority_queue() {
list<express> pq;
array<wchar_t*,9> trains = {
L"のぞみ１号", L"ひかり２号", L"こだま３号",
L"のぞみ４号", L"ひかり５号", L"こだま６号",
L"のぞみ７号", L"ひかり８号", L"こだま９号",
};
// 上記の順にホームに到着
for ( auto iter = trains.begin(); iter != trains.end(); ++iter ) {
express item(*iter);
// lower_boundで挿入位置を探り
auto pos = lower_bound(pq.begin(), pq.end(), item, express_less());
// ソコに割り込ませる
pq.insert(pos, item);
}
// 優先順位の高いものから発車ｵｰﾗｲ
while ( !pq.empty() ) {
wcout << pq.back().name << ' ';
pq.pop_back();
}
wcout << endl;
}
実行結果:
のぞみ１号 のぞみ４号 のぞみ７号
ひかり２号 ひかり５号 ひかり８号
こだま３号 こだま６号 こだま９号
ﾃﾞｷﾀｰ♪