c++ - 我可以希望从映射中删除元素或通过迭代器设置元素不比对数差吗？

Question

cppreference.com¹ 和 cplusplus.com² 都声称 erase 在 set 或 map 容器上，如果将迭代器作为其参数，是“摊销常数”。

这几乎没有暗示其最糟糕的复杂性。我能希望它永远不会比对数差吗？至少有合理的实现？

---

¹ http://en.cppreference.com/w/cpp/container/map/erase#Complexity

² http://www.cplusplus.com/reference/map/map/erase/#complexity

Answer 1

是的，您可以希望 std::map::erase(map::iterator) 的最坏情况复杂度是容器大小的对数。

std::map::erase 有一个双参数版本，它删除元素范围，给定迭代器定义范围的开始和限制。它的复杂性保证(在表 101 中，在 §23.2.4 [associative.reqmts] 中引用)为 O(log S + N)，其中 S 是容器的大小，N 是要删除的元素的数量。您可以在 O(log S) 中找到后继迭代器并使用 N=1 的双参数删除成员函数，从而导致 O(log S) 时间。如果这不适用于单参数版本，那将是非同寻常的。

这不是铁定的保证，但它是合理希望的基础。