为什么没有std::is_transparent等价于无序容器?

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 ...;
    }
};

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

最近的论文P0919r2提出了以下例子:

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

虽然-1L和-1.0比较相等，但某些不符合所选相等比较逻辑的异构哈希函数可能产生不同的值。本文增加了支持异构查找的函数模板——find, count, equal_range和contains——但是在满足以下要求时使它们可用[无序.req]/p17:

如果限定id Hash::transparent_key_equal是有效的，并且表示一个类型([temp. deduction])，那么程序是病态的，如果:
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.扣除])。

在这种情况下，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<>都是透明比较器，可以作为string_hash的transparent_key_equal。

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

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

如果你看了CppCon的烧烤委员会视频，他们解释了为什么会发生这样的事情:没有人为它而战。

c++是由委员会标准化的，但该委员会需要社区的输入。有人要写论文、回应批评、参加会议等等……然后可以对该特性进行投票。委员会不只是坐在那里发明语言和库的特性。它只对提交给它的提案进行讨论和投票。

下面的例子(来自于被接受的答案)在Apple clang 13.1.6版本上编译。请注意，我必须将is_transparent放在NodeHash和NodeEq中。

#include <unordered_set>
struct Node {
    int id;
    int count;
};
struct NodeEq {
    using is_transparent = void;
    bool operator() (Node const& a, Node const& b) const { return a.id == b.id; };
    bool operator() (Node const& n, int const i)   const { return n.id == i; };
    bool operator() (int const i,   Node const& n) const { return n.id == i; };
};
struct NodeHash {
    using is_transparent = void;
    using transparent_key_equal = NodeEq;
    std::size_t operator() (Node const& n) const noexcept { return n.id; };
    std::size_t operator() (int n)         const noexcept { return n;    };
};
using nodes_t = std::unordered_set< Node, NodeHash, NodeHash::transparent_key_equal >;
int main() {
    nodes_t nodes;
    nodes.find(1);
}

相关内容

最新更新

热门标签：