std::unordered_map::clear() 会不会比 std::map::clear() 慢，因为前者的清除操作是 "carried on"？

Question

我正在阅读 ，据我所知，unordered_map 实际上在元素数量 + 桶数量方面呈线性关系。

那么，假设我有代码，

1. 向std::unordered_map

   添加任意数量的元素

2. 然后clear() std::unordered_map

3. 重复多次。

如果我在整个执行过程中的任何一点都有很多元素（在第 1 步中），clear 时间也会在未来继续，使代码变慢。

但是，std::map也有同样的问题吗？

谢谢

Answer 1

When will std::map::clear() going to be faster that std::unordered_map::clear()?

两者都具有线性渐近复杂度。您可以同时使用这两种方法来为您的代码计时，看看其中一种是否明显更快。

注意，如果元素的析构函数是non-trivial，那么所有容器的clear具有线性复杂度。如果析构函数是微不足道的，那么唯一具有小于 clear 线性复杂度的标准容器是 std::vector 和 std::basic_string.

---

关于以下案例：

• 将容器变大
• 清除
• 插入几个
• 清除

std::unordered_map后清除成本高，用std::map重现不是问题。