大文字小文字無視でstd::mapを検索する
大文字・小文字を無視してMapで検索を行いたくなった。
Keyを叩くときの比較のプロセスを、std::mapに<std::string, std::string, Compare>という風にCompareを渡すことで、指定してやれるらしい。
知らなかったぜ。
で、このCompareの実装について調べまわっていたら、あるサイトで妙な記述を発見した。
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
注目していただきたいのはここである。
return str1 < str2;
なんで・・・・？
普通に文字コードの大小を比較するだけではないのか？
もしstr2の文字コードの方が大きかったらどうするんだろう。
返すのはbool型なんだし、なぜ==じゃダメなんだ？
実際、これとほとんど同じものを実装したわけだが、なぜか==や>ではうまく動かず、<だとうまく動くのだ。
うまく動かないというのは、具体的にいうと、Valueが変なのが帰ってきたり、Vectorの例外が飛んできたりする。
なにこれ〜？
普通に試す
というわけで検証してみる。
#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;
}
}
素直にこういうコードを書いてみた。
出力は当然、
false
true
false
ASCIIコード表を眺める。
小文字の方が文字コードが大きいので全部予想通りだ。
どう考えてもこうだろ。変なこと言うな！と思ってC++リファレンスを読んでみた。
本当はどう考えてもドキュメント読んだ方がいいけど。
ドキュメントを読んでみよう
さっきの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) を意味する
そもそもstd::stringの比較の話ではなさそう
つまり、std::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は「弱い順序づけ」を持っていることが条件（！）であるらしいから、順序を定義するためのcomp()が壊れると内部の検索も崩壊するという仕掛けっぽい。
全順序、全順序律抜き、比較可能性マシで！
弱い順序づけ完成！
反省
だからつまり。
さっき、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という風に分けたほうがよくなかったか？
なんでこうなったんだろう。
ぴちぴち生まれたての若者であるから、歴史的理由は全くわからない。
有識者求む！