unordered_map 在 erase() 上重排

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)。什么操作可以花费线性时间完成并且不会以使迭代器无效的方式修改容器？

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

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

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

Answer 1

如果您有非常糟糕的散列或病态数据，则所有元素最终都可以放在一个桶中，从而使其成为 locate/remove 元素的 O(n) 遍历。

使用元素的（单）链表实现 std::unordered_map 是完全合法的：we can see that its iterator type is only required to fulfil the ForwardIterator concept。这使得需要线性遍历来删除桶中的元素，即使在传递迭代器时也是如此。

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