c++ - 擦除（）上的 unordered_map 重新设置

Question

我不完全清楚是否unordered_map允许在执行重新哈希时执行erase()

很明显，在insert()使所有迭代器和引用无效的过程中可能会发生重新散列：

http://en.cppreference.com/w/cpp/container/unordered_map/insert

但erase()似乎保留了所有迭代器和引用，除了那些被删除的：

http://en.cppreference.com/w/cpp/container/unordered_map/erase

但是，最后一页和标准表明erase()最差执行时间是O(size). 什么操作可以花费线性时间来完成并且不会以使迭代器无效的方式修改容器？

这篇文章表明迭代器在擦除期间无效：http: //kera.name/articles/2011/06/iterator-invalidation-rules-c0x/

我还在某处读到，未来的提案将允许重新散列erase()。真的吗？

如果确实发生了重新散列，那么旧的迭代和擦除算法是错误的，对吧？

Answer 1

如果你有一个非常糟糕的散列或病态数据，所有元素都可能最终放在一个桶中，这使得定位/删除元素需要 O(n) 遍历。

std::unordered_map为元素使用（单）链表实现 a 是完全合法的：我们可以看到它的迭代器类型只需要满足 ForwardIterator 概念。这使得删除桶中的元素需要进行线性遍历，即使在传递迭代器时也是如此。

这是可能需要 O(n) 时间的操作，而不是重新散列。