［C++］std::stringをキーとする（非順序）連想コンテナでHeterogeneous Overloadを有効化する

C++ std::map std::unordered_map Heterogeneous overloads C++23 C++20

この記事はC++ Advent Calendar 2021の17日目の記事です。

Heterogeneous Overload？

Heterogeneous Overloadというのは、（非順序）連想コンテナ（C<Key, ...>）の操作においてKeyと異なる型のオブジェクトをとることのできるオーバーロードのことです。

例えばstd::map::find()はC++14から次の2つのオーバーロードを持っています（constは無視します）

iterator find(const key_type& x);             // (1)

template <class K>
iterator find(const K& x);                    // (2) C++14

ここでkey_typeとはstd::map<Key, Value>のKey型であり、2つ目のオーバーロードはKeyと異なる型の任意のオブジェクトを受け取るようになっています。これがHeterogeneous Overloadであり、keyと比較可能な別の型のオブジェクトを直接用いて値を検索することができ、使いやすさが向上するだけでなく、Keyの一時オブジェクトを作る必要がないため効率的です。

ところが、Heterogeneous Overloadを使用するためにはKeyと比較可能な型の値を渡すだけではだめで、連想コンテナならば比較クラスCompareに、非順序連想コンテナならばそれに加えてハッシュクラスHashに、is_transparentメンバ型が定義されていて、Keyと異なる型との直接比較および一貫したハッシュ生成をサポートしている必要があります。。

悲しいことに、互換性のためにデフォルトの比較クラス（std::less<Key>, std::equal_to<Key>）は比較がテンプレートではないため異なる型との直接比較ができず、ハッシュクラス（std::hash<Key>）にはis_transparentメンバ型が定義されていないため、デフォルトではHeterogeneous Overloadは有効になりません。そのため、Heterogeneous Overloadを有効化するためには、自分で要件が満たされるように一工夫しなければなりません・・・

ここでは、一番需要が高くてよく出会いそうなstd::stringをキーとする（非順序）連想コンテナについて見ていきます。

std::map<std::string, T>

#include <iostream>
#include <string>
#include <unordered_map>
#include <map>

using namespace std::literals;

int main() {
  std::cout << std::boolalpha;

  std::map<std::string, int> map = { {"1", 1}, {"2", 2}, {"3", 3}};

  std::cout << (map.find("1"sv) != map.end()) << std::endl; // エラー
  std::cout << (map.find("4") != map.end()) << std::endl;   // OK、ただし一時オブジェクトが作成されている
}

std::string_viewをそのまま受け取れないのは、std::string_viewから変換するstd::stringのコンストラクタにexplicitが付加されているためです。静かなパフォーマンス低下を長文コンパイルエラーで教えてくれるのでとても親切だといえるでしょう・・・

std::unordered_map<std::string, T>

#include <iostream>
#include <string>
#include <unordered_map>
#include <map>

using namespace std::literals;

int main() {
  std::cout << std::boolalpha;

  std::map<std::string, int> map = { {"1", 1}, {"2", 2}, {"3", 3}};

  std::cout << (map.find("1"sv) != map.end()) << std::endl; // エラー
  std::cout << (map.find("4") != map.end()) << std::endl;   // OK、ただし一時オブジェクトが作成されている
}

これもエラーが起きてるのはmapと同じ理由です。

連想コンテナ

連想コンテナ（std::set, std::mapとそのmultiバージョン）の場合、問題となるのはデフォルトの比較クラスがテンプレートパラメータに指定された型の比較しかできずis_transparentを持っていないことだけです。デフォルトの比較クラスstd::less等はなぜかvoidに対する特殊化に対してのみis_transparentが定義される（比較がテンプレートになる）のでそれを使ってもいいですし、C++20からならstd::rangesにある比較クラスを使ってもいいでしょう。

#include <iostream>
#include <string>
#include <unordered_map>
#include <map>
#include <functional> // ranges::lessとかはここにある

using namespace std::literals;

int main() {
  std::cout << std::boolalpha;

  std::map<std::string, int, std::ranges::less> map = { {"1", 1}, {"2", 2}, {"3", 3} };

  std::cout << (map.find("1"sv) != map.end()) << std::endl; // OK
  std::cout << (map.find("4") != map.end()) << std::endl;   // OK
}

これだけで連想コンテナはHeterogeneous Overloadを有効化できます。当然どちらのケースでもstd::stringの一時オブジェクトは生成されておらず、直接比較されています（はずです）。std::ranges::lessの代わりにstd::less<void>を使用しても大丈夫です、お好みでどうぞ。

std::ranges::mapみたいな感じでこれを標準で用意してほしいものです。

非順序連想コンテナ

非順序連想コンテナ（std::unorderd_map, std::unorderd_setとそのmultiバージョン）の場合、比較クラスに加えてハッシュクラスも問題となります。残念ながらハッシュクラスに関しては自分で定義をするしかありません・・・

#include <iostream>
#include <string>
#include <unordered_map>
#include <map>
#include <functional>

using namespace std::literals;

struct string_hash {
  using hash_type = std::hash<std::string_view>;
  using is_transparent = void;

  std::size_t operator()(std::string_view str) const {
    return hash_type{}(str);
  }
};

int main() {
  std::cout << std::boolalpha;

  std::unordered_map<std::string, int, string_hash, std::ranges::equal_to> map = { {"1", 1}, {"2", 2}, {"3", 3} };

  std::cout << (map.find("1"sv) != map.end()) << std::endl; // OK
  std::cout << (map.find("4") != map.end()) << std::endl;   // OK
}

少し面倒ですが、std::hashをそのまま利用してやればハッシュを独自実装する必要はありません。ハッシュクラス（string_hash）のoperator()の引数型をstd::string_viewにしておけば、const char*, std::string, std::string_viewの3つを受け取ることができます。

std::string系の文字列クラスならこうすればいいのですが、他の型の場合はハッシュ共通化が難しい場合もあるかもしれません。そういう場合は自分でハッシュ実装をする必要がありそうです。

const char*, std::string, std::string_viewのハッシュ一貫性保証

ところで、上記のようにconst char*, std::stringのハッシュ値をstd::string_viewから計算することに問題はないのでしょうか？

これは保証されていて、[basic.string.hash]/1によれば

If S is one of these string types, SV is the corresponding string view type, and s is an object of type S, then hash<S>()(s) == hash<SV>()(SV(s)).

とあります。

要は、事前定義されている各種std::basic_stringのハッシュ値と、それに対応するstring_viewのハッシュ値は一致すると言っています。

また、[string.view.hash]/1にも

The hash value of a string view object is equal to the hash value of the corresponding string object ([basic.string.hash]).

と、同じことを逆方向から確認しています。const char*の文字列もstd::string/std::string_viewを経由して考えれば同じ結論となるので、各種文字列のハッシュ値はその型によらず一致することが分かります。

どうやらこれはC++17から規定されたもののようですが、この規定によって変更が必要になるとすればそれは破壊的となるはずなので、おそらく実装がそうなっていたことを規格に反映しただけで、以前から同様の保証は暗黙的に存在していたと思われます。

（非順序）連想コンテナのHeterogeneous Overload

Heterogeneous Overloadは、連想コンテナの検索系の関数（find(), count(), lower_bound(), upper_bound(), equal_range()）に対してC++14で追加され（N3657）、続いてC++20にて非順序連想コンテナの検索系関数に対しても追加されました（P0919）。

C++23ではさらに、全ての連想コンテナの削除（erase()）とノードハンドルの取り出し（extract()）に対してもHeterogeneous Overloadが追加されました（P2077）。

さらに、挿入系の操作（insert(), insert_or_assign(), try_emplace(), bucket()）についてもHeterogeneous Overloadを追加する提案が進行中で（P2363）、まだ入ってはいませんがC++23を目指しています。これが入るとKeyを指定するタイプの操作のほぼ全てでHeterogeneous Overloadを使用可能となるため、それにアダプトする方法およびstd::stringとstd::string_view使用時の問題について頭の隅にとどめておく重要性が高まるでしょう。

参考文献

この記事のMarkdownソース