为什么没有std :: is_transparent等价的无序容器？

Question

C++ 14 在关联容器中引入Compare::is_transparent了等效的查找操作.

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

查找具有键的元素,该元素与值x进行比较.如果qualified-id Compare :: is_transparent有效并且表示类型,则此重载仅参与重载解析.它允许在不构造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 和-但使它们可在下面的要求得到满足[unord.req]/P17:countequal_­rangecontains

如果qualified-id Hash::transparent_­key_­equal有效并且表示类型([temp.deduct]),那么如果以下情况之一,程序就会形成错误:

• qualified-id Hash::transparent_­key_­equal::is_­transparent无效或不表示类型,或
• Pred是一种不同于equal_­to<Key>或Hash::transparent_­key_­equal.

成员函数模板find,count,equal_­range,和contains不得参加重载除非合格-ID Hash::transparent_­key_equal是有效的,表示类型([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.

Answer 2

如果您观看CppCon 的Grill the委员会视频，他们会解释为什么发生这种情况：没有人为此奋斗。

C ++由委员会标准化，但是该委员会需要社区的投入。有人必须写论文，回应批评，参加会议等。然后才能对该功能进行投票。该委员会不只是坐在那里发明语言和图书馆功能。它仅对提出的内容进行讨论和投票。