Heterogeneous Lookup
https://www.cppstories.com/2021/heterogeneous-access-cpp20/
C++ 14 加入了对有序容器的异质查找
用户的工作量很小，对标准库中的类型，只需要加上第三个模板参数：std::less<>（它的默认参数是 void）。std::less<void> 类中申明了 is_transparent 类型，所以可以用于异质查找。
std::map<std::string, int> intMap {
{ "Hello Super Long String", 1 },
{ "Another Longish String", 2 },
{ "This cannot fall into SSO buffer", 3 }
};
std::cout << "Lookup in intMap with by const char*:\\n";
std::cout << intMap.contains("Hello Super Long String") << '\\n';
//
std::map<std::string, int, std::less<>> trIntMap {
{ "Hello Super Long String", 1 },
{ "Another Longish String", 2 },
{"This cannot fall into SSO buffer", 3 }
};
std::cout << "Lookup in trIntMap by const char*: \\n";
std::cout << trIntMap.contains("Hello Super Long String") << '\\n';
C++ 20 加入了对无序容器的异质查找
需要提供标注 is_transparent 的 hash 算子和等于算子。等于算子一般可以直接用 std::equal_to<>，但 hash 算子常常需要我们自己提供。
struct string_hash {
using is_transparent = void;
[[nodiscard]] size_t operator()(const char *txt) const {
// 对指针的hash只考虑了地址，所以要选用string_view的hash
return std::hash<std::string_view>{}(txt);
}
[[nodiscard]] size_t operator()(std::string_view txt) const {
return std::hash<std::string_view>{}(txt);
}
[[nodiscard]] size_t operator()(const std::string &txt) const {
// string和string_view的hash方式一样
// 但用string的特化会减少一次从string到string_view的构造
return std::hash<std::string>{}(txt);
}
};
std::unordered_map<std::string, int, string_hash, std::equal_to<>>
intMapTransparent {
{ "Hello Super Long String", 1 },
{ "Another Longish String", 2 },
{"This cannot fall into SSO buffer", 3 }
};
bool found = intMapTransparent.contains("Hello Super Long String");
std::cout << "Found: " << std::boolalpha << found << '\\n';
为什么 C++ 不把异质容器的查找作为默认？
同质查找是先转换类型，再多次比较。异质查找是多次比较，每次比较时调用的算子可能会做类型转换操作。如果算子没有对异质查找优化，每次比较时都构建临时对象开销非常大。
标准库的 string / string_view / const char * 是一个很好的可以使用异质查找的例子，因为他们之间的相互比较都有良好的无需临时构造对象的操作符。