std：：unordered_map：：clear（） 会比 std：：map：：clear（） 慢吗，因为前者“进行”了 clear 操作？

Will std::unordered_map::clear() be slower than std::map::clear() because clear operations are "carried on" in the former?

提问人：MangoPizza 提问时间：5/17/2022 最后编辑：MangoPizza 更新时间：5/17/2022 访问量：418

问：

我正在阅读这篇文章，从我能得到的是，实际上元素数量+桶的数量是线性的。unordered_map

所以，比方说，我有代码，它

  1. 将任意数量的元素添加到std::unordered_map

  2. 然后clear()std::unordered_map

  3. 重复多次。

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

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

谢谢

C++ 字典 std 无序映射

评论

0赞 simre 5/17/2022
两者的大小都是线性的。查看复杂性：en.cppreference.com/w/cpp/container/unordered_map/clear 和 en.cppreference.com/w/cpp/container/map/clear
0赞 Nathan Pierson 5/17/2022
我不确定我是否遵循这个前提。你相信如果在任何时候你在地图中有大量的元素，那么所有未来的调用都会很慢吗？就算你，只加几个元素，再加一遍呢？我不确定链接的问题是否支持该前提。clearclearclear
0赞 MangoPizza 5/17/2022
@NathanPierson “你相信，如果在任何时候你在地图上有大量的元素，那么未来的所有调用都会很慢”。是的，我就是这么想的......要放入大量元素，必须保留内存以创建新存储桶。请参阅给定的答案“因此，您的程序的 1000 次迭代将使用这样的实现执行至少 2,000,069,000 次操作”。因此，调用了 times，并且每次它都必须将指针归入 null。clearunordered_mapclear()1000clear()memsetint(2e6) + 69
1赞 BoP 5/17/2022
std::map没有任何桶，它是一个树状结构。树不见了之后。clear()
1赞 Nathan Pierson 5/17/2022
啊，我明白了。然后继续。

答：

1赞 eerorika 5/17/2022 #1

std：：map：：clear（） 什么时候会比 std：：unordered_map：：clear（） 更快？

两者都具有线性渐近复杂度。您可以使用两者来计时代码，以查看其中任何一个是否明显更快。

请注意，如果元素的析构函数是非平凡的，则所有容器都具有线性复杂度。如果析构函数是微不足道的，则唯一复杂度小于 和 的标准容器是 和 。clearclearstd::vectorstd::basic_string

关于以下情况：

  • 将容器扩大到大
  • 清楚
  • 插入几个
  • 清楚

后者的成本显然很高，适用于不是一个重现的问题。std::unordered_mapstd::map

评论

0赞 MangoPizza 5/17/2022
你好，看来我没有正确解释这个问题。我已经编辑了它以更好地反映我的问题。谢谢
0赞 MangoPizza 5/17/2022
“后者的成本显然很高，适用于不是一个复制的问题。”这正是我所需要的。谢谢std::unordered_mapstd::map
0赞 MangoPizza 5/17/2022
事实上，当我为代码计时时。 在 中工作并在 中工作。有很大的不同！map78msunordered_map1500ms

上一个：无法从地图值中获取配对

下一个：是否有可能通过 std：：upper_bound 对 std：：map 进行有效的部分搜索？