2026-08-30
leaderboard.cpp
#include <algorithm>
#include <print>
#include <string>
#include <vector>
struct Player {
std::string name;
int score;
};
int main() {
std::vector<Player> v{{"kim", 70}, {"amy", 90}, {"zoe", 90}, {"bob", 70}};
std::ranges::stable_sort(v, std::greater{}, &Player::score);
std::ranges::sort(v, {}, &Player::name);
for (const auto& p : v)
std::print("{} ", p.name);
std::println();
}
参加者を点数の高い順に並べ、同点の参加者は名前の辞書順に並べて、名前を空白区切りで表示するつもりのコードです。main の4人なら本来は amy zoe bob kim と表示されるはずが、いまは amy bob kim zoe と、名前の順に並んだだけの列が表示されます。
Answer
Wrong
std::ranges::stable_sort(v, std::greater{}, &Player::score);
std::ranges::sort(v, {}, &Player::name);
1行目で点数の降順 amy zoe kim bob に並びますが、2行目の sort は名前だけを比べて列全体を並べ直します。4人の名前はすべて違うので、名前の順で前後が決まらない組は1つも無く、1行目が作った順序はどこにも残りません。結果は名前の順の amy bob kim zoe です。
sort は安定ではないので、つい stable_sort に変えたくなりますが、それでは直りません。安定なソートが元の順序を残すのは、比べるキーが等しい要素どうしだけで、この列では名前が等しい組が無いからです。並べ替えを重ねたとき主のキーになるのは、最後に並べたほうのキーです。
Right
std::ranges::sort(v, {}, &Player::name);
std::ranges::stable_sort(v, std::greater{}, &Player::score);
先に同点を決める名前で並べ、最後に主のキーである点数で並べます。点数の stable_sort は、同点の amy と zoe、bob と kim の前後を、直前に名前で並べた順のまま残すので、amy zoe bob kim になります。
安定である必要があるのは、この後のソートだけです。先のソートが自由に決められるのは名前が同じ要素どうしの順序だけで、そこをどう並べても、表示する点数と名前の並びは変わりません。そのため、先の名前のソートは sort のままでかまいません。1
- 重要度の低いキーから順に安定なソートを重ねるやり方は、数を下の桁から1桁ずつ並べ替える基数ソート(radix sort)と同じ考え方です。1回で済ませるなら、
std::ranges::sort(v, [](const Player& a, const Player& b) { return std::tie(b.score, a.name) < std::tie(a.score, b.name); })のように、2つのキーをまとめて比べる比較関数を渡します。