为什么 "insert" of unordered_set Undefine Behavior 在这里？

Question

对不起，我的标题模糊了。

假设有一些节点指针，我想收集具有唯一性的节点指针value。

struct node_t
{
    int value;
    node_t(int v = -1) : value(v) {}
};

例如，如果我们有4个指针：

p1 points to node(1)
p2 points to node(1)
p3 points to node(2)
p4 points to node(2)

那我要收藏{p1, p3}这里

我的代码是这样写的：

#include <iostream>
#include <unordered_set>
#include <algorithm>
using namespace std;
struct node_t
{
    int value;
    node_t(int v = -1) : value(v) {}
};
struct myequal
{
    bool operator()(const node_t *p1, const node_t *p2) const
    {
        return p1->value == p2->value;
    }
};
int main()
{
    unordered_set<node_t *, hash<node_t *>, myequal> table;
    node_t n1(0), n2(0);
    table.insert(&n1), table.insert(&n2);
    cout << (&n1) << '\n';
    cout << (&n2) << '\n';
    cout << table.size() << '\n';
    cout << *table.begin() << '\n';
}

我运行MacOS12的代码，用clang++ -std=c++17 xxx.cpp编译，但输出不确定

有时输出：

0x7ff7bad974e0
0x7ff7bad974d0
1
0x7ff7bad974e0

但有时会输出：

0x7ff7b4bdc4e0
0x7ff7b4bdc4d0
2
0x7ff7b4bdc4d0

为什么会这样？

根据unordered_set的document，

Each element is inserted only if it is not equivalent to any other element already in the container (elements in an unordered_set have unique values).

Answer 1

简而言之，您的散列和相等操作不兼容。当您插入一个元素时，首先获取哈希，然后检查该哈希的桶以查看是否存在等效元素。

假设有三个名为 A、B 和 C 的存储桶。您插入 n1，它最终位于存储桶 B 中。接下来您插入 n2.

如果 n2 被散列到存储桶 B，则在该存储桶中找到等效的 n1，因此不会插入 n2。
如果 n2 被散列到桶 A（或 C），然后检查那个桶——而且只有那个桶——看元素是否已经存在。 Bucket A 是空的，当然找不到等价的元素。所以插入n2。

为了使您的散列和相等运算兼容，相等的事物必须计算为相同的散列。这确保相同的东西将分配给同一个桶（确保 n2 在上面的例子中被散列到桶 B）。如果相等性基于 p1->value，则哈希值最好基于 p1->value.

来自 cppreference.com 的文档：

If two Keys are equal according to Pred, Hash must return the same value for both keys.

为什么 "insert" of unordered_set Undefine Behavior 在这里？

Why is "insert" of unordered_set Undefine Behavior here?

c++

stl

c++17