std::unordered_set 是否允许插入重复的元素？

Question

我没有理解正确的地方，我的印象是unordered_set不允许插入重复的元素。我的印象是，基于哈希值，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;
}

一个重载函数做的完全一样，但参数是反过来的。

这就是结构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条。

我到底做错了什么？

EDIT: Class 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 避免重复，通过比较 价值观而不是这些值的哈希值^†. 你的每一个共享指针的 "值 "都会不同，因为它们指向不同的对象。

实际上，你可以通过提供你自己的函数来改变这种行为，将其作为 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;

_{^† 如果在一个给定的哈希值中只允许有一个值，那么在一个 unordered_set 那么(a)你将无法添加任何真正导致哈希碰撞的值，(b)整个哈希碰撞解决机制将变得完全没有必要。}