c++ - std::unordered_set::find 和 std::find 之间奇怪的性能差异

Question

我尝试比较 std::unordered_set::find 的性能和 std::find .与我的期望和规则相反https://clang.llvm.org/extra/clang-tidy/checks/performance-inefficient-algorithm.html std::find明显更快
quick-bench with unordered_set
unorder_set包含 int所以散列应该不是问题。 std::set::find按预期运行并且比 std::find 快.
quick-bench with set
任何人都可以解释这种行为吗？
谢谢

Answer 1

其中一些还取决于硬件和实现。但是为了更清楚地了解正在发生的事情，将不同尺寸的时间绘制成图表会很有用。

对于这个测试，我使用了微软的编译器，所以与 clang/llvm 的一些差异并不特别令人惊讶。只是为了咧嘴笑，我投入了额外的测试 std::lower_bound (当然是在对数组进行排序之后)除了 find , set , 和 unordered_set .
我还做了一些不同的测试，生成随机数来填充容器，并在容器中搜索一组 1000 个随机值。这(可能)是 std:find 右端低于线性增长的原因. Microsoft 的随机数生成器只有 15 位范围，因此对于 100,000 个元素，我们将在生成 100,000 个值之前命中它可以生成的每个值，因此在上次测试中，搜索受到范围的限制我们可以生成的值而不是数组的大小。
我想如果我雄心勃勃，我会使用更大范围的更好的随机数生成器重写它，但我认为这足以确定趋势，并很好地了解该修改的预期结果。
编辑:更正了粘贴到电子表格中的数据的错位。