std::sort は便利

先日の ABC128_B はいい感じに入れ子のソートをしたいという問題で、自分のコードは vector, multimap, set でそれぞれ別の情報をもってがんばってしまったが、解説を読んだら pair を入れ子にすればそれを sort するだけでよしなにやってくれるということを初めて知った。

具体的には

vector<pair<pair<string, int>, int>> v;
sort(v.begin(), v.end());

このように書けば first.first, first.second, second の順に比較して昇順にしてくれる。（参考: pair で書き直したコード）

これができるなら tuple でもいいじゃんと思ったらやはり通る。（参考: tuple で書き直したコード）

そもそもなぜこういうことができるかというと、 std::sort() はソート対象のオブジェクトに operator< が定義されていればなんでもソートでき、 pair や tuple の operator< は入れ子になっていてもちゃんとソートできる頭のいい定義になっているため。（リファレンス: std::sort, std::pair の operator<, std::tuple の operator<）

pair の operator< の返り値は

x.first < y.first || (!(y.first < x.first) && x.second < y.second)

なので、まず first で比較して、x.first = y.first なら second を比較した結果が返る。 first や second に pair が入れ子になって入っていても再帰的に比較されるのでちゃんとソートができるし、 first に等しい値が入っていたらその集合の中では second でソートされる。tuple の operator< も同様。

さらに、std::sort は比較条件を自分で指定できる。今回の例で言えば、たとえばレストラン番号、レストラン所在地、レストラン点数の順で tuple に格納したとしても、所在地、点数の順で比較するように指定できる。

typedef tuple<int, string, int> T;
bool comp(const T &a, const T &b){
  return get<1>(a) < get<1>(b) || !(get<1>(b) < get<1>(a)) && get<2>(b) < get<2>(a);
}

今回の問題では点数に関しては降順だったので、最後の比較だけ a, b の大小を逆にした。こうすることで、レストランの点数を負にして格納しておく必要がなくなる。（参考: 上記比較関数を std::sort に指定した場合のコード）

全然関係ないが、最近 Rust をやりはじめた。このへん を読むと、どうやら Rust でも今回のような感覚は近そうに感じられる。とかくこういった言語知識は息をするように出し入れできるようになりたいもので、昔は高度な知識は language lawyer に聞けばよかったのかもしれないが、リファレンスが気軽に読めてコンパイラやインタプリタが親切になった現在では個々人に相応の言語知識が求められるようになっているんじゃないかと思う。（この記事は全然高度ではないが…）