c++ - 为什么无序容器没有 std::is_transparent 等价物？

Question

C++14 引入了 Compare::is_transparent 等效 find关联容器中的操作。

template< class K > iterator       find( const K& x );
template< class K > const_iterator find( const K& x ) const;

Finds an element with key that compares equivalent to the value x. This overload only participates in overload resolution if the qualified-id Compare::is_transparent is valid and denotes a type. It allows calling this function without constructing an instance of Key

由于不再构造 Key 的临时实例，这些可以更有效。

似乎没有无序容器的等效项。

为什么没有Compare::key_equal/Compare::hash_equal？

我想允许有效地查找，例如，无序容器中的字符串文字会相对简单？

template<>
struct hash<string>
{
    std::size_t operator()(const string& s) const 
    {
        return ...;
    }
    // hash_equal=true allows hashing string literals
    std::size_t operator()(const char* s) const
    {
        return ...;
    }
};

Answer 1

比较相等的键应该产生相同的哈希值。解耦散列函数和谓词，和同时使一个或两个异构，可能太容易出错。

最近的论文，P0919r2 ，举出下面的例子:

std::hash<long>{}(-1L) == 18446744073709551615ULL
std::hash<double>{}(-1.0) == 11078049357879903929ULL

虽然-1L和 -1.0比较相等，一些异构的哈希函数，不符合选择的相等比较逻辑，可能会产生不同的值。论文添加了支持异构查找的功能模板—— find , count , equal_­range , 和 contains -- 但在满足以下要求时使它们可用[unord.req]/p17 :

If the qualified-id Hash::transparent_­key_­equal is valid and denotes a type ([temp.deduct]), then the program is ill-formed if either:

• qualified-id Hash::transparent_­key_­equal::is_­transparent is not valid or does not denote a type, or
• Pred is a different type than equal_­to<Key> or Hash::transparent_­key_­equal.

The member function templates find, count, equal_­range, and contains shall not participate in overload resolution unless the qualified-id Hash::transparent_­key_equal is valid and denotes a type ([temp.deduct]).

在这种情况下，Hash::transparent_­key_­equal覆盖默认谓词 ( std::equal_to<Key> ) 并与 Hash 一起用于(透明)相等检查本身用于(透明)散列。

在这些条件下，可以使用以下透明函数对象来启用异构查找:

struct string_equal
{
    using is_transparent = void;

    bool operator()(const std::string& l, const std::string& r) const
    {
        return l.compare(r) == 0; 
    }

    bool operator()(const std::string& l, const char* r) const 
    {
        return l.compare(r) == 0; 
    }

    bool operator()(const char* l, const std::string& r) const
    {
        return r.compare(l) == 0; 
    }
};

struct string_hash
{
    using transparent_key_equal = string_equal; // or std::equal_to<>

    std::size_t operator()(const std::string& s) const
    {
        return s.size();
    }

    std::size_t operator()(const char* s) const
    {
        return std::strlen(s);
    }
};

两者——string_equal和 std::equal_to<> -- 是透明的比较器，可以用作transparent_key_equal对于 string_hash .

在散列函数类定义中具有此类型别名(或类型定义本身)清楚地表明它是一个有效的谓词，可以很好地与特定的散列逻辑一起工作，而两者不能发散。这样一个无序集可以声明为:

std::unordered_set<std::string, string_hash> u;

或:

std::unordered_set<std::string, string_hash, string_hash::transparent_key_equal> u;

两者都将使用 string_hash和 string_equal .