std::mapのCompareの謎



## 大文字小文字無視でstd::map<std::string, T>を検索する

大文字・小文字を無視してMapで検索を行いたくなった。

Keyを叩くときの比較のプロセスを、std::mapに`<std::string, std::string, Compare>`という風にCompareを渡すことで、指定してやれるらしい。

知らなかったぜ。

https://en.cppreference.com/w/cpp/named_req/Compare


で、このCompareの実装について調べまわっていたら、あるサイトで妙な記述を発見した。

```C++
struct Comparator {
    bool operator() (const std::string& s1, const std::string& s2) const {
        std::string str1(s1.length(),' ');
        std::string str2(s2.length(),' ');
        std::transform(s1.begin(), s1.end(), str1.begin(), tolower);
        std::transform(s2.begin(), s2.end(), str2.begin(), tolower);
        return  str1 < str2;
    }
};
```
引用元: https://www.walletfox.com/course/caseinsensitivemap.php


注目していただきたいのはここである。

```C++
return  str1 < str2;
```

なんで・・・・？

普通に文字コードの大小を比較するだけではないのか？

もしstr2の文字コードの方が大きかったらどうするんだろう。
返すのはbool型なんだし、なぜ==じゃダメなんだ？


実際、これとほとんど同じものを実装したわけだが、なぜか==や>ではうまく動かず、<だとうまく動くのだ。
うまく動かないというのは、具体的にいうと、Valueが変なのが帰ってきたり、Vectorの例外が飛んできたりする。

なにこれ〜？

## 普通に試す


というわけで検証してみる。


```C++
#include <string>
#include <iomanip>
#include <iostream>

int main()
{
	std::string	a("HURUMY");
	std::string b("hurumy");

	if (a == b)
	{
		std::cout << "true" << std::endl;
	}
	else
	{
		std::cout << "false" << std::endl;
	}

	if (a < b)
	{
		std::cout << "true" << std::endl;
	}
	else
	{
		std::cout << "false" << std::endl;
	}

	if (a > b)
	{
		std::cout << "true" << std::endl;
	}
	else
	{
		std::cout << "false" << std::endl;
	}

}
```

素直にこういうコードを書いてみた。
出力は当然、

```shell
false
true
false
```

ASCIIコード表を眺める。
小文字の方が文字コードが大きいので全部予想通りだ。

どう考えてもこうだろ。変なこと言うな！と思ってC++リファレンスを読んでみた。
本当はどう考えてもドキュメント読んだ方がいいけど。

## ドキュメントを読んでみよう

[さっきのCompareのサイト](https://en.cppreference.com/w/cpp/named_req/Compare)をもう一回読んでみると、

`equiv(a, b)`と、
`!comp(a, b) && !comp(b, a)`が同値であることが要件ね！
と書いてあった。

あとここ！
>Compare は関数オブジェクト型である。
Compare 型のオブジェクトに適用した関数呼び出しの戻り値は、 bool へ文脈依存の変換をされたとき、第一引数が第二引数より小さい場合は true を、そうでない場合は false を返す。
何らかの順序関係 (ordering relation) を前提とするアルゴリズム全般に対して Compare 型の comp を使用する。
comp は間接参照したイテレータを通して非 const な関数を適用しないものとする。

>Compare を取るアルゴリズムには全て、代わりに operator< を使うバージョンもある。
つまり、comp(*i, *j) != false はデフォルトで *i < *j != false である。
二分探索以外のアルゴリズムでは、comp は「狭義の弱順序 (strict weak ordering) 」を示さなければならない。

>ここでの用語「狭義 (strict) 」 は非反射関係 (irreflexive relation) (全ての x について !comp(x,x) である）の要求を示し、用語「弱 (weak) 」は全順序 (total ordering) ほど強くはないが半順序 (partial ordering) よりは強い要求を示す。!comp(a, b) && !comp(b, a) として equiv(a, b) を定義する場合、用語「弱」の要求は comp と equiv の両方が以下のように推移的関係 (transitive relations) となることである。

>comp(a, b) && comp(b, c) は comp(a, c) を意味する
equiv(a, b) && equiv(b, c) は equiv(a, c) を意味する

https://cpprefjp.github.io/reference/algorithm.html#strict-weak-ordering

## そもそもstd::stringの比較の話ではなさそう

つまり、[std::mapにはそもそも「弱い順序づけ」が定義されていなきゃいけなくて、](https://en.cppreference.com/w/cpp/container/map)(!)
その順序のつけ方を定義するのが`comp(a, b)`というCompareのメンバで、
`equiv(a, b)`は別に定義しなくても`comp()`を使って定義できるという話っぽい。

順序が必要ならVectorを使ったらいいのではないか・・・・？
map、おまえが順序を定義できる必要はあるのか！

今回、mapのKeyがstd::stringなので、別に大小関係は欲しくないのだが、イテレータなんかを使ってMapの検索をやっているとかなり気軽に壊れてしまうっぽい。

## 順序ってなんだと思う！

君は順序ってなんだと思う？
わたしは知っているぞ。


これをみたまえ！
https://ja.wikipedia.org/wiki/%E9%A0%86%E5%BA%8F%E9%9B%86%E5%90%88

>反射律：P の任意の元 a に対し、a ≤ a が成り立つ。
推移律：P の任意の元 a, b, c に対し、a ≤ b かつ b ≤ c ならば a ≤ c が成り立つ。
反対称律：P の任意の元 a, b に対し、a ≤ b かつ b ≤ a ならば a = b が成り立つ。
全順序律：P の任意の元 a, b に対し、a ≤ b または b ≤ a が成り立つ。

簡単にいうと、
`a<b<c`であるにも関わらず、`a>c`でもあるとかだと、
これは推移律を満たしていなくてぜんぜん順序じゃない。

わたしたちが素朴に順序と呼びたくなるものは、最低限、反射律と推移律の二つを満たしていると思う。
4つ全部満たすのは、全順序といって、たいへん厳しい順序だ。
Pの中身が全部明示的に比較可能であることを要求してる。

で、std::mapは[「弱い順序づけ」](https://en.wikipedia.org/wiki/Weak_ordering#Strict_weak_orderings)を持っていることが条件（！）であるらしいから、順序を定義するための`comp()`が壊れると内部の検索も崩壊するという仕掛けっぽい。

https://blog.cryolite.net/entry/20040529/p3

全順序、全順序律抜き、比較可能性マシで！
弱い順序づけ完成！

## 反省

だからつまり。

さっき、`comp(a, b)`の実装で、`str1 == str2`とすると全然うまく動かなかったのは、`comp()`が名前通り「比較のみ」に使われてるわけじゃなくて、むしろ順序の定義のためにこそ使われているからであるっぽい。

Compareというのは、返り値はBoolだけど、そのBoolの意味は、「同じか同じじゃないか！」ってことじゃなくて、「どっちが”デカい”か、いつも必ず同じ結果を返す！」ってことだったんだ。
大小関係を定義するために使われてる。

逆に、Keyの同値の定義も`comp()`を使って、「`a<b`でなく、`a>b`でもないこと！」と書けちゃう。

逆に逆に、`comp()`の左右を入れ替えたものがどっちもfalseだったんなら、それは比較できないから順序つけないでよ、同じ順位ってことにしよ、みたいな雰囲気・・・ってこと！？

だから、別に`equiv()`を実装しなくても、`comp()`が適切に定義されていて、順序がまろやかにきちんと決まっている限り、これは(相対的にせよ)同値だ！（そういうことにします！）と分かるわけだ。

わたしも`equiv()`実装してない。してなくても動く。

ん〜、「Header」と「header」は全然違う文字列だけど、そこに順序をつけてほしくないから、同じ順位〜！として良いように、`comp（）`を定義してやれば良い。


## で、std::mapはなぜ順序が欲しいのだ？

std::mapに順序いる？

いや、unordered_mapというのがあるのは知っている。
しかし、mapで順序が必要になる状況、まあまあヘンテコではないか？

mapとunordered_mapではなく、mapとordered_mapという風に分けたほうがよくなかったか？

なんでこうなったんだろう。
ぴちぴち生まれたての若者であるから、歴史的理由は全くわからない。
有識者求む！