はじめに

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; });
}

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

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/

比較関数の要件

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

戻り値は、暗黙的にboolに変換可能な型であること
従って、戻り値が表すものは False (0) or True (!0)だけを表すことになる
Cライブラリのqsort()のように、3種類の値を返す必要は無い
comp(a, a) == false を満たすこと
演算子として greater than は指定可能だが、greater or equal は指定不可能である
例えばstd::sort()の比較関数に greater or equal を指定し
かつvectorに重複要素が含まれる場合、並べ替えが完了せずにエラーが発生する
Exception: invalid comparator
comp(a, b) == true である場合、comp(b, a) == false となること
つまり、右辺と左辺を入れ替えても比較結果が破綻しないことを意味する
なお条件2により、両方falseとなることは有り得る
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/