c++ - 关于 C++ 中 STL 容器的问题

Question

1. std::multimap 和 std::unordered_multimap 多久洗一次条目？我问是因为我的代码传递引用以区分具有相同哈希的条目，并且我想知道何时在它们上运行引用重定向功能。

2. 如果我这样做会发生什么：

   std::multimap atable; //Type specification stuff left out
   //Code that pus in two entries with the same key, call that key foo
   int bar = atable[foo];
   

3. 如果它是 unordered_multimap，结果会有所不同吗？

4. 回到传递引用以区分具有相同哈希的条目。有没有更安全的方法来做到这一点？

5. 如果我删除其中一个条目，条目是否会移动（这是阅读 std::vector 文档所建议的）？

Answer 1

不，在任何操作过程中都不会损坏任何元素。

正如这个著名的 Q&A中所解释的，对于关联容器，在插入/擦除时没有迭代器失效（当然，被擦除的元素除外）。对于无序的关联容器，在rehashing期间存在迭代器失效，标准说（强调我的）

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

9 无序关联容器的元素被组织成桶。具有相同哈希码的键出现在同一个桶中。当元素被添加到无序关联容器时，桶的数量会自动增加，因此每个桶的平均元素数保持在一个界限以下。重新散列使迭代器无效，更改元素之间的顺序，并更改元素出现在哪些桶中，但不会使指针或对元素的引用无效。对于 unordered_multiset 和 unordered_multimap，重新散列保留了等效元素的相对顺序。

同样，这并不需要重新排列实际存储的元素（Key和Value中的类型unordered_map<Key, Value>），因为无序映射具有以链表形式组织的存储桶，并且存储元素（键值对）的迭代器同时具有元素指针和桶指针。重新散列对存储桶进行洗牌，这会使迭代器无效（因为它们的存储桶指针无效），但不会使指针或对元素本身的引用。这在另一个问答中有详细解释

Answer 2

std::multimap 和 std::unordered_multimap 多久洗一次条目？

绝不。指向任何关联容器（包括集合、映射及其无序或“多”版本）的元素的迭代器永远不会失效（除非它们指向的特定元素被删除）。换句话说，实际的元素永远不会“乱来”。这些都需要实现为链接结构（例如，链接树），这意味着只需更改一些指针即可重新构建它们，而无需物理移动任何元素。

编辑：显然（参见 TemplateRex 的评论），无序容器并非如此。在这种情况下，迭代器可能会失效，但元素本身不会移动。这些要求意味着一个没有反向指针的间接容器，我认为这是一个合理的选择，但不是我所期望的。

如果我这样做会发生什么：...（获取[]多图）...

operator[]没有为std::multimap（或无序版本）定义。那么，会发生什么？会发生编译器错误。

如果它是 unordered_multimap，结果会有所不同吗？

不，它是一样的，operator[]不存在。

回到传递引用以区分具有相同哈希的条目。有没有更安全的方法来做到这一点？

是的，推荐的做法是使用迭代器而不是引用来引用地图/集合/任何内容的元素。元素的迭代器保证保持有效，并且它们是可复制的并且对它们具有正确的 const-ness 保护，这使它们成为“引用条目”的完美对象。

编辑：根据相同的评论，如果处理散列容器（无序容器），我将不得不建议使用指向元素的指针，因为不保证迭代器（按标准）保持有效。

Answer 3

C++ 标准库中的所有关联容器都是基于节点的，即它们的元素保持不变。但是，没有指定哈希是在复制对象后计算对象还是在传递给容器的临时对象上计算的。我猜想，通常哈希是在对象被复制/移动之前计算的。

要区分具有相同散列的元素，无论如何您都需要一个相等函数：如果对象的位置导致它不同，则意味着所有对象都不同，您根本无法查找它们。您需要对定义键等价的无序容器中的元素具有相等功能。对于有序关联，等价类基于严格的弱排序，即，基于这样的表达式（使用<而不是二元谓词以提高可读性；任何定义严格弱序的二元谓词也可以工作）：

bool equivalent = !(a < b) && !(b < a);