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

# はじめに

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

# 記述例

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

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

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

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

* 関数を定義する方式

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

* クラスを定義する方式

```cpp
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());
}
```

* ラムダ式

```cpp
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により、クラス外に比較演算子を実装する<br>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()` の定義に戻ると、比較関数として指定すべき型はテンプレート引数になっていて
正直これを見ただけでは、いまいちピンと来ない
具体的には、何で関数ポインタだったりクラスオブジェクトだったり渡せるの？ってなる

```cpp
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については、雑に書くとこんな感じで

```cpp
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/