C++ std::sort等で指定する比較関数についてのメモ

はじめに

C++で多数の構造体やクラスの要素を並べ替えを行う場合、std::sortを利用するのが基本楽なのだが
単純な値型でない限り、何らかの方法で比較方法を定義or指定してやる必要がある
この方法が多岐に渡り、なんとなく実装で動いてしまうことも多いため
実装の詳細というか理屈について触れられることも少ないと感じ、自分用に簡単なメモとしてまとめた

記述例

sort関数のI/Fについて、今回注目するものは下記のようになっている
引用 : https://en.cppreference.com/w/cpp/algorithm/sort

template< class RandomIt, class Compare >
void sort( RandomIt first, RandomIt last, Compare comp );

任意の型の並べ替えを行い、比較方法については引数compで指定するというメジャーな方式である
（余談だが、C#のライブラリも似たようなI/Fになっている）

compを指定する方式として、よく見かけるものを以下に記載する

• 関数を定義する方式

std::vector<int> values;  /* set values as you like */

bool fcomp(const int& a, const int& b) { return a < b; }

void main()
{
  std::sort(values.begin(), values.end(), fcomp);
}

• クラスを定義する方式

std::vector<int> values;  /* set values as you like */

class CComp
{
public:
  bool operator()(const int&a, const int& b) { return a < b; }
};

void main()
{
  std::sort(values.begin(), values.end(), CComp());
}

• ラムダ式

std::vector<int> values;  /* set values as you like */

void main()
{
  std::sort(values.begin(), values.end(), [](const int& a, const int& b) { return a < b; });
}

• その他
• 自作クラスの場合、クラス内に比較演算子を実装すればソート可能
• オペレータのoverloadにより、クラス外に比較演算子を実装する
  https://en.cppreference.com/w/cpp/language/operators

等の手法も存在するが、個人的にかなり使い勝手が悪いと思っているので割愛

qsort（Cライブラリ）との差異

std::sort()を使うたび混乱していたのはコイツの影響も大きい
std::sort()で求められる比較関数の要件は、cライブラリ（qsort()など）のそれとは異なる

qsort : https://en.cppreference.com/w/c/algorithm/qsort

上記ページの説明を抜粋する
C++とは大きく異なるため、これは一旦忘れなければならない

• 引数は、2個の比較対象を指すポインタ void* とする
• 戻り値はint型とする
• 引数1の方が小さい場合、負の値を返す
• 引数2の方が小さい場合、正の値を返す
• 引数が等しい場合、0を返す

comp引数の要件

std::sort() の定義に戻ると、比較関数として指定すべき型はテンプレート引数になっていて
正直これを見ただけでは、いまいちピンと来ない
具体的には、何で関数ポインタだったりクラスオブジェクトだったり渡せるの？ってなる

template< class RandomIt, class Compare >
void sort( RandomIt first, RandomIt last, Compare comp );

その回答が下記ページに記載されており、Compare は function object type であること、と定義されている
https://en.cppreference.com/w/cpp/named_req/Compare

function object type というのはC++の仕様で定義される概念で
要するに関数として呼び出し可能になってるものは大体function object typeってことらしい
https://en.cppreference.com/w/cpp/utility/functional

細かいことは良く分からないが、以下のものは function object type として扱えるらしい

• ラムダ式
• ファンクタ ---- operator() 演算子が定義されたクラスインスタンスのこと
• 関数ポインタ
• std::function
• std::bind

参考 : https://marycore.jp/prog/cpp/function-object/

比較関数の要件

これも先のページからの引用

1. 戻り値は、暗黙的にboolに変換可能な型であること
   従って、戻り値が表すものは False (0) or True (!0)だけを表すことになる
   Cライブラリのqsort()のように、3種類の値を返す必要は無い

2. comp(a, a) == false を満たすこと
   演算子として greater than は指定可能だが、greater or equal は指定不可能である
   例えばstd::sort()の比較関数に greater or equal を指定し
   かつvectorに重複要素が含まれる場合、並べ替えが完了せずにエラーが発生する
   Exception: invalid comparator

3. comp(a, b) == true である場合、comp(b, a) == false となること
   つまり、右辺と左辺を入れ替えても比較結果が破綻しないことを意味する
   なお条件2により、両方falseとなることは有り得る

4. comp(a, b) == true, comp(b, c) == true である場合、comp(a, c) == true であること
   つまり、序列が一意に決められるものでなければならない（ジャンケンの強弱などはダメ）

I/Fについては、雑に書くとこんな感じで

template<class T>
bool fcomp(T a, T b);

戻り値はboolに暗黙変換可能であれば何でも良い
引数a, bは値渡し、もしくは参照渡しが可能らしいので、多くの例に倣ってconst参照渡しとするのが良さげ
非constの参照渡しとして定義した場合、比較関数内で値を書き換えることも可能

比較関数の戻り値

対応する関数のマニュアルを参照
例えば std::sort の場合
https://en.cppreference.com/w/cpp/algorithm/sort

comparison function object (i.e. an object that satisfies the requirements of Compare)
which returns ​true if the first argument is less than (i.e. is ordered before) the second. 

と書いてある
意訳すると「順番が正しいならtrue、そうでなければfalseを返せ」という事だが
上で述べた比較関数の要件に従う必要があるため、同じ値に対してはfalseを返さなければならない
同じ値であれば並べ替えの必要がないため、順番が正しいという意味を込めて
ついついtrueを返してしまう（つまづきポイント）

参考サイト

• いつもお世話になっておりますcppreference.com様
  https://en.cppreference.com/

• 関数オブジェクトについて、いい感じにまとめてくれてたMaryCore様
  https://marycore.jp/prog/cpp/function-object/