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对元素使用(单个)链接列表是完全合法的:我们可以看到它的迭代器类型只需要满足ForwardIterator概念.这使得即使在通过迭代器时也需要线性遍历来移除桶内的元素.

这是可能花费O(n)时间而不是重复的操作.