为什么允许std::unordered_map::rehash()使迭代器无效？

Question

Visual Studio (2015)实现不会使任何迭代器无效(rehash()对内部std::list重新排序，保持所有迭代器有效)。

有没有其他的实现可以使迭代器失效(并获得更好的性能，即使具有相同的复杂性)？

使std::unordered_map::rehash()上的迭代器失效有时会限制开发人员(例如，我试图仅使用std::unordered_map实现LRU缓存:节点的值具有容器的迭代器)。但是，使迭代器无效的可能性可以更好地实现std::unordered_map::rehash()吗？

Answer 1

感谢@DanielLangr在上面的讨论，

我认为，这个要求来自于std::unordered_map::[const_]iterator定义为LegacyForwardIterator (而不是LegacyBidirectionalIterator)。使用内部std::forward_list或类似的(而不是VS的std::list)实现具有更好内存占用的实现，如果不使rehash()中的迭代器无效(可能，除了end())是不可能的。

• 这种更好的内存占用实现可能会在这里和那里添加一些简单的汇编指令(也可以在其他地方节省一些)，或者可能有更大的sizeof(std::unordered_map::[const_]iterator)，但按原样定义std::unordered_map要求并将所有这些考虑因素留给have绝对是正确的