C++のソートをもっと柔軟に行う
Published on 2020月04月11日
10 min read
In category
プログラミング
C++のソートをもっと柔軟に行う
突然ですが、C++ユーザーの競プロerのみなさまは一度はsort関数を使用したことがおありだと思いますが、sort の第3引数に渡されがちな、greater<int>()って何者なのかご存知ですか？
sortの公式ドキュメントを見ると、第1引数、第2引数にイテレータを、第3引数に"Compare"型のオブジェクトを取ることがわかる。つまり、greater<int>()は"Compare型"のオブジェクトだったのだー!!
Compare型のオブジェクトってなんだよ
僕もわかりません。一緒に公式ドキュメントを読みましょう。(本題のsortを使いこなすことのみに興味がある人は適宜飛ばし読みしてくれ)
適当に関連しそうな部分を引用する
- Compare は関数オブジェクト型である。
- Compare 型のオブジェクトに適用した関数呼び出しの戻り値は、 bool へ文脈依存の変換をされたとき、第一引数が第二引数より小さい場合は true を、そうでない場合は false を返す。
- 何らかの順序関係 (ordering relation) を前提とするアルゴリズム全般に対して Compare 型の comp を使用する。
- comp は間接参照したイテレータを通して非 const な関数を適用しないものとする。
以上の引用のなかで重要だと僕が考える点を整理する。
- Compareは関数オブジェクトであること
- (Compare型の関数オブジェクトの)第1引数と第2引数を比較してbool値を判定している
何らかの順序関係 (ordering relation) を前提とするアルゴリズム全般に対して Compare 型の comp を使用する。
ここの部分の議論(どう順序関係を組み立てればよいか)はまた別の話だと思うので割愛します。ただ、プログラミングの順序の議論を行う際に、数学の集合論の議論を援用しているので興味がある人は例えば松坂『集合・位相入門』を読むなどで補完してみても良いと思う。
他の言語でいうと、例えばジョシュア・ブロック『Effective Java 第3版』項目14「Comparebleの実装を検討する」が詳しい。
閑話休題。つまりCompare型は第1引数と第2引数を"何らかの順序関係"をもとに比較して第一引数が小さい場合はtrueを、大きい場合はfalseを取る関数であることがわかった。この時点で、sort関数が何を内部で実現しようとしているのかのベールが一枚剥がされた。イメージは配列が渡されたら一つ一つCompare型の関数の引数にぶちこんで判定結果のbool値をもとに小さい順に並べ替えているのだ。
改めてgreater<int>()の中身を見る。以下は公式ドキュメントからの引用
template <class T> struct greater {
bool operator() (const T& x, const T& y) const {return x>y;}
typedef T first_argument_type;
typedef T second_argument_type;
typedef bool result_type;
};operator()で第1引数が第2引数より大きいならtrueを、小さいならfalseを取るような処理が実装されていることがわかる。(operatorはオーバーロードされた関数である点に注意)。これによって、ソート後の配列の連続する2つの要素についてもoperatorと矛盾しないような順番に並べ替えることが可能になる(...ぽい)。C++の実装箇所はここ
柔軟にソートする
上の議論から、Compare型(の中のOperator型)の関数オブジェクトに実装された処理に従って、ソートが行われることがわかった。じゃあ、そのCompareの法則をユーザーが独自に定義して渡せちゃうんじゃね？というのがこの記事の本題。
結論からいえば渡せます。ラムダ関数という機能を使って関数オブジェクトを即席でこしらえて渡してあげればいいです。
また便利な公式リファレンス。ラムダ式の細かな説明は省きます。例も上の公式リファレンスが有能すぎるのでぜひご参照を。僕の方でもラムダ式を理解できるような一つ例を出してみます
auto greater=[](int a, int b){return a>b;};たったこれだけの記述で、int型の第1引数aがint型第2引数より真に大きければtrueを、そうでなければfalseを返す関数greaterが定義できちゃいます。
例を示すと
bool a = greater(1,2); //false
bool b = greater(2,1); //true
bool c = greater(1,1); //trueこんな感じでしょうか。この処理って "第1引数が第2引数より大きいならtrueを、小さいならfalseを取るような処理" にほかなりません。しかもラムダ式は関数オブジェクトなのでsortの第3引数に渡せちゃいます。挙動を僕のMacで確かめてみる。
#include <iostream>
#include<vector>
#include <algorithm>
int main(){
#include <iostream>
#include<vector>
#include <algorithm>
int main(){
std::vector<int> vec{7,3,5,2,9,10};
std::cout<<"ソート前出力結果:"<<" ";
for(auto v:vec){
std::cout<<v<<" ";
}
std::cout<<"\n";
auto greater_=[](int a, int b){return a > b;};
std::cout<<"ソート後出力結果:"<<" ";
sort(vec.begin(),vec.end(),greater_);
for(auto v:vec){
std::cout<<v<<" ";
}
std::cout<<"\n";
return 0;
}
}結果は
ソート前出力結果: 7 3 5 2 9 10
ソート後出力結果: 10 9 7 5 3 2 見事大成功である。こうして2つの引数をとり、返り値がbool型の関数をラムダ式で定義してあげて渡してあげると、その処理通りの処理をsortが行ってくれることがわかる。
(ぶっちゃけ僕自身有益なことを提供できそうにないので)詳細を省くが、ここでの引数の型はなんでもよいです。stuctでもdictでもmapでも。
いい感じの使い方を教えてよ
例えばvector<pair<int,int>>で、firstの部分は辞書順で、もしfirst要素が等価ならばsecondを逆辞書順でソートしたいといういささか病的な例を上げる。 この処理をラムダ式として記述すると以下のような感じになる。
auto juunannna_soto=[](pair<int,int> p1,pair<int,int> p2){
if(p1.first!=p2.first){return p1.first<p2.first}
else{return p1.second>p2.second}
}果たして要望通りソートしてくれるのか...???
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
typedef std::pair<int,int> P;
int main(){
std::vector<P> vec{{2,3},{2,2},{2,1},{1,10},{3,1},{3,2},{1,1},{3,3},{2,2}};
std::cout<<":"<<" ";
for(auto v:vec){
std::cout<<'{'<<v.first<<','<<v.second<<'}'<<" ";
}
std::cout<<"\n";
auto juunannna_soto=[](P p1,P p2){
if(p1.first!=p2.first){return p1.first<p2.first;}
else{return p1.second>p2.second;}
};
std::cout<<":"<<" ";
sort(vec.begin(),vec.end(),juunannna_soto);
for(auto v:vec){
std::cout<<'{'<<v.first<<','<<v.second<<'}'<<" ";
}
std::cout<<"\n";
return 0;
}出力結果は
ソート前出力結果: {2,3} {2,2} {2,1} {1,10} {3,1} {3,2} {1,1} {3,3} {2,2}
ソート後出力結果: {1,10} {1,1} {2,3} {2,2} {2,2} {2,1} {3,3} {3,2} {3,1} やりました😋
最後の例は構造体です。 構造体のメンバーa,b,cについて、「まずaが大きい順を考える、aが等しかったらbが小さな順を考える。もしbも等しかったらcが大きな順に並べる」というものを考えてみる。また、ラムダ式の引数は型推論できるのでautoと記述することができます。 予め処理を書くとこんな感じでしょうか。
auto struct_sort=[](auto st1,auto st2){
if(st1.a!=st2.a){return st1.a>st2.a;}
else if(st1.b!=st2.b){return st1.b<st2.b;}
else {return st1.c>st2.c;}
};実験していきましょう。
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
typedef std::pair<int,int> P;
struct my_struct{
int a;
int b;
int c;
};
int main(){
std::vector<my_struct> vec{
{1,2,3},{1,200,3},{8,100,59},{8,1,1},{8,101,9},{5,5,1},{5,5,5},{1,2,3},{190,80,4}
};
std::cout<<"ソート前出力結果:"<<" ";
for(auto v:vec){
std::cout<<'{'<<v.a<<','<<v.b<<','<<v.c<<'}'<<" ";
}
std::cout<<"\n";
auto struct_sort=[](auto st1,auto st2){
if(st1.a!=st2.a){return st1.a>st2.a;}
else if(st1.b!=st2.b){return st1.b<st2.b;}
else {return st1.c>st2.c;}
};
std::cout<<"ソート後出力結果:"<<" ";
sort(vec.begin(),vec.end(),struct_sort);
for(auto v:vec){
std::cout<<'{'<<v.a<<','<<v.b<<','<<v.c<<'}'<<" ";
}
std::cout<<"\n";
return 0;
}出力結果は以下のようになります
ソート前出力結果: {1,2,3} {1,200,3} {8,100,59} {8,1,1} {8,101,9} {5,5,1} {5,5,5} {1,2,3} {190,80,4}
ソート後出力結果: {190,80,4} {8,1,1} {8,100,59} {8,101,9} {5,5,5} {5,5,1} {1,2,3} {1,2,3} {1,200,3}この例ではうまくいきました!!(例をいくつも上げたところで法則をverifyできるわけではないので控えめな表現で...)
このようにしてソートを柔軟に使いこなして、高パフォーマンスを目指していきましょう!
落穂広いのコーナー
まず、他の競技者の人のコードを見る感じ、例えば構造体の例を用いると以下のような書きぶりになりそう。
sort(vec.begin(),vec.end(),[](auto st1,auto st2){
if(st1.a!=st2.a){return st1.a>st2.a;}
else if(st1.b!=st2.b){return st1.b<st2.b;}
else {return st1.c>=st2.c;}
});説明のためにあえてsort関数外でラムダ式を書いていましたが、第3引数に直接記述することも可能です。
次にAtCoderの例題たちです。この記事のようにsortを柔軟に使えたから解きやすかったなと記憶に残っているものを上げていきます。
・AtCoder Beginner Contest 128 B - Guidebook
https://atcoder.jp/contests/abc128/tasks/abc128_b
・AtCoder Beginner Contest 113 C - ID
https://atcoder.jp/contests/abc113/tasks/abc113_c
・AtCoder Beginner Contest 091 C - 2D Plane 2N Points
https://atcoder.jp/contests/abc091/tasks/arc092_a
・AtCoder Beginner Contest 091 C - 背の順 https://atcoder.jp/contests/abc041/tasks/abc041_c
