std :: unordered_set允许插入重复项

Question

我不理解正确的事情.我的印象是unordered_set不允许基于哈希的重复元素.

我有一个结构,具有std :: hash的特化,它似乎允许重复,虽然我已经手动检查它

AddEdge ( const std::shared_ptr<Relation> relation, const std::shared_ptr<Concept> concept )
{
    auto edge = std::make_shared<Edge>( (Edge){ relation, concept } );
    auto res = _edges.insert ( edge );
    return res.second;
}

重载函数完全相同但反转参数

这是struct Edge的散列方式:

namespace std
{
    template<> struct hash<shared_ptr<Edge>>
    {
        size_t operator()( const shared_ptr<Edge> & ptr ) const
        {
            size_t from = 0;
            size_t to = 0;

            if ( auto node = std::dynamic_pointer_cast<Concept>( ptr->from ) )
                from = hash<shared_ptr<Concept>>()( node );

            else if ( auto node = std::dynamic_pointer_cast<Relation>( ptr->from ) )
                from = hash<shared_ptr<Relation>>()( node );

            if ( auto node = std::dynamic_pointer_cast<Concept>( ptr->to ) )
                 to = hash<shared_ptr<Concept>>()( node );

            else if ( auto node = std::dynamic_pointer_cast<Relation>( ptr->to ) )
                 to =  hash<shared_ptr<Relation>>()( node );

            return hash<size_t>()( from + to );
        }
    };
}

容器保存在:

std::unordered_set<std::shared_ptr<Edge>> _edges;

当我做:

graph2->AddEdge( sea_node, is_node );
graph2->AddEdge( is_node, blue_node );

我明白了:

Edge [sea,is] hash = 10017731961838884781
Edge [is,blue] hash = 11178184051384786808

我尝试第二次完全相同,我得到相同的哈希值,但是,当我检查边缘时,我现在有4个边缘而不是2个边缘.

我究竟做错了什么？

编辑:类Concept&Relation具有相同类型的哈希函数:

namespace std
{
    template<> struct hash<shared_ptr<Concept>>
    {
        size_t operator()( const shared_ptr<Concept> & ptr ) const
        {
            return hash<string>()( ptr->asToken()->value() ) + hash<int>()( ptr->TokenIndex() ) + hash<string>()( "Concept" );
        }
    };
}

更加有意义的是,我添加Edges时的输出会生成相同的哈希,但是会添加重复的Edge.

Answer 1

unordered_set将不允许基于哈希值的重复元素

不,unordered_set通过比较值避免重复,而不是那些值的散列^†.
每个共享指针的"值"将会有所不同,因为它们引用不同的对象.

实际上,您可以通过提供自己的函数作为KeyEqual模板参数来更改此行为unordered_set:

template<
    class Key,
    class Hash = std::hash<Key>,           // <-- you've been looking at this
    class KeyEqual = std::equal_to<Key>,   // <-- instead of this
    class Allocator = std::allocator<Key>
> class unordered_set;

_{^†如果在a unordered_set(a)中只允许一个具有给定散列的值,则无法添加任何真正导致散列冲突的值,并且(b)整个散列冲突解决机制将变得完全不必要.}