高效地删除tr1::unordered_map中的元素

Question

我正在尝试使用tr1::unordered_map，并遇到如何有效删除元素的问题。 'erase'方法提供了按键或迭代器删除的选项。我认为后者更有效，因为前者可能涉及隐式查找操作。另一方面，我在互联网上的调查发现，在调用insert()方法后，迭代器可能无效。

我对典型的现实世界情况感兴趣，在这种情况下，放入哈希表中的对象的生命周期足够长，使得在该生命周期内发生对insert()的调用。因此，我可以得出结论，在这种情况下，只能通过键进行删除吗？是否有任何其他方法可以更有效地删除对象？我完全意识到这个问题只影响经常发生删除的应用程序。我的当前项目是否会出现这种情况还有待观察，但是我宁愿在设计项目时学习这些问题，而不是当已经有大量代码存在时才解决这些问题。

- Samo Jordan

Answer 1

无序容器的整个重点在于具有最快的查找时间。担心通过键删除元素所需的时间听起来像是过早优化的经典例子。

- Mark Ransom

---

没有任何分析，这绝对是过早的优化。 - Mark B

Answer 2

如果对您非常重要，因为您出于其他原因保留了迭代器，那么C++0x在23.2.5/11中表示std::unordered_map（引用FDIS）：

插入和emplace成员如果（N + n）＜z * B，则不会影响迭代器的有效性，在这里，N是插入操作之前容器中的元素数量，n是插入的元素数量，B是容器的bucket count，z是容器的最大负载系数。

我没有检查tr1规范是否具有相同的保证，但基于预期的实现，这是相当合理的。

如果您可以使用此保证，则可以在一定程度上保护您的迭代器。正如马克所说，unordered_map中的查找应该很快。与在vector中保留索引而不是迭代器以及在map中保留等效内容相比，保留键而不是迭代器更糟糕，但更好。

- Steve Jessop

Answer 3

是的，insert() 可以使所有迭代器失效。因此，我认为没有办法避免（隐式）查找。好消息是后者很可能很便宜。

- NPE