更改了现有的 unordered_set 元素，这里的机制是什么？

Question

我自己创建了一个 unordered_set class A

struct A {
    int v;
};

struct A_eq
{
    bool operator()(A* lhs, A* rhs) const {
        return lhs->v == rhs->v;
    }
};

struct A_hash
{
    std::size_t operator()(A* obj) const {
        return std::hash<int>{}(obj->v);
    }
};

int main(int , char* []) {
    A* a7 = new A(); A* a5 = new A(); A* a7_ = new A(); A* a5_ = new A();
    a7->v = 7; a5->v = 5; a7_->v = 7; a5_->v = 5;

    std::unordered_set<A*, A_hash, A_eq> s;
    s.insert(a7); s.insert(a5); s.insert(a7_);

    printf("dump s:");
    for (auto& obj : s) {
        printf("%d,", obj->v);
    }
}

程序打印

dump s:5,7,

符合预期。

虽然a7和a7_是不同的指针，但是它们不能同时插入集合s，因为A_eq和A_hash是处理取消引用的指针而不是指针本身。

然后我通过 find 选取存储在 s 中的指针，使用 found->v = 7 更改其解引用值，以便该集合包含两个“相同”元素。但是集合坚持认为它包含两个不同的元素。

    auto iter = s.find(a5_);
    A* found = *iter;
    printf("%d\n", found->v);
    found->v = 7;

    printf("dump s:");
    for (auto& obj : s) {
        printf("%d,", obj->v);
    }
    printf("\n");

    s.erase(a7_);
    s.erase(a7);
    s.rehash(0);

    printf("dump s:");
    for (auto& obj : s) {
        printf("%d,", obj->v);
    }
    printf("\n");

    iter = s.find(a7_);
    printf(iter==s.end()?"no 7":"has 7");

这些代码输出

5
dump s:7,7,
dump s:7,
no 7

谁能告诉我发生了什么事？为什么剩下的元素不被集合视为A({.v=7})？

Answer 1

[unord.req]/5 ... For any two keys k1 and k2 in the same container, calling pred(k1, k2) shall always return the same value. For any key k in a container, calling hash(k) shall always return the same value.

您的程序因违反此要求而表现出未定义的行为。它以更改其散列的方式修改密钥，并使两个密钥在之前比较不相等的地方比较相等。

Answer 2

来自 cppreference.com 的 unordered_set 的文档：

Container elements may not be modified (even by non const iterators) since modification could change an element's hash and corrupt the container.

更准确的说，不只是直接在容器中的数据是不允许修改的，任何影响那些元素相等比较的数据都是不允许修改的。虽然您没有修改容器内的位，但您确实通过将容器的元素从不等于更改为相等来从逻辑上修改了它们。因此，您更改了元素的散列并损坏了容器。随之而来的是垃圾。

Answer 3

好的，这里的几个用户已经完全正确地批评了你的 hacky 方案。

但在这里给您留下进一步的提示：

如果您想将自定义 classes 与标准容器一起使用，请尝试使用您的 classes 作为容器的直接类型（否 pointers/wrappers），如果您愿意提供引用您的实际 class 内容的自定义 comparison/hash 函数，或者至少确保底层存储的数据是常量！

也许这里有一些理论上的少数例外情况，但一般来说，自定义 comparators/hash 方法应该始终引用它们包含的 'decayed' class 类型，至少对于它们的输入参数通过。否则，你至少打破了单一责任原则（标准容器已经关心可能的原始指针元素使用（或者你的 class 应该有自己的指针类型），你的 class 不应该在这里干涉再次）。

更改了现有的 unordered_set 元素，这里的机制是什么？

Changed existing unordered_set element, what's the mechanism here?

c++

stl

unordered-set