logo标签列表

在unordered_map中引用值是否安全？

c++
3

例如：

#include <unordered_map>

class A{};
std::unordered_map<unsigned int, A> map {{0,{}},{1, {}},{2, {}}};

int main() {
  A& a1 = map[1];
  // some insert and remove operations ( key 1 never removed)
  // ....
}

在进行大量插入操作后，仍然使用a1引用键为"1"的值，这样做是否安全？

换句话说：由于std::vector在容量更改时会移动元素，因此其元素的引用不能保证有效。这个事实是否也适用于unordered_map？

即使std::vector中的元素位置发生变化，对其进行引用仍然是安全的吗？ - 김선달
1
我猜它类似于迭代器失效规则。 - user10957435
不是这样的。显然我对此有误解。请参考Sam的回答。 - user10957435
@ravenisadesk 哦，我打错字了。我的意思是它的元素。 - 김선달
@김선달，你可以尝试一下，当容量改变后，你对元素的引用将会无效。C++没有像Java那样的功能，可以重定向指针（在C ++术语中称为引用）。 - user2269707
显示剩余3条评论
3个回答
8

是的，它是安全的。来自标准：

22.2.7 无序关联容器 [unord.req]

插入和emplace成员不会影响对容器元素的引用的有效性，但可能使容器的所有迭代器失效。擦除成员只会使被删除元素的迭代器和引用失效，并保留未被擦除元素的相对顺序。

引用是安全的，但迭代器不安全！

1
嗨，山姆，我很好奇：实现如何确保这一点？如果我是一个哈希表并且需要扩展，我可能需要将所有基础数组重新定位到不同的内存位置。有什么想法吗？ - Aviv Cohn
无序容器通常是指指针的哈希表，因此容器中的值不受重新映射的影响。 - Sam Varshavchik
那么当我执行some_unordered_map.insert(some_key, some_value)时，some_value会被复制到某个名为X的数组中 - 而且该数组将始终停留在第一次分配它的位置。并在不同的数组Y中设置指向该位置的指针，该数组可能随时间而调整大小和重定位。而当我执行some_unordered_map.find(some_key)时，查找是在数组Y上执行的，并且将始终返回指向数组X中相同位置的指针。这就是为什么保持此指针（或引用）有效的原因。我的理解大致正确吗？ - Aviv Cohn
没有必要将some_value复制到一个array中。在哈希容器的常见实现中，容器中的值被保留在单独的链表中，数组桶作为哈希桶；类似于std::vector<std::list<T>>。无论如何，unordered_map是一个模板。这意味着您可以在头文件中找到特定C++编译器的unordered_map实现的100％代码。如果您有兴趣了解它的工作原理，可以直接从编译器的头文件中阅读。 - Sam Varshavchik
2
2
很多次插入操作之后？
如果你指的是insert或者emplace，那么没问题。
（强调是我的）
如果插入导致重新哈希，所有迭代器都会失效。否则，迭代器不受影响。 引用不会失效。重新哈希仅在新元素数量大于max_load_factor()*bucket_count()时发生。如果插入成功，则在保持节点句柄中的元素的同时获取的指针和引用将无效，并且在提取该元素之前获得的指针和引用将变为有效。（自C++17起）
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接