std::find 如何与 std::set 一起使用

Question

要从 a , ofc 中查找元素std::set，我们应该使用std::set::find. 然而，函数std::find/std::find也可以工作。

std::set<int> st;
for (int i = 0; i < 999999; i++) {
    st.insert(i);
}

// method 1
if (st.find(999990) != st.end()) {
    std::cout << "111" << std::endl;
}

// method 2
auto itor = std::find(std::begin(st), std::end(st), 999990);
if (itor != std::end(st)) {
  std::cout << "aaa" << std::endl;
}

// method 3
auto itor2 = std::find(st.begin(), st.end(), 999990);
if (itor2 != st.end()) {
  std::cout << "bbb" << std::endl;
}

如您所见，这三种方法都按预期工作（https://godbolt.org/z/fEjzTae81）。

但我不知道它们的区别，尤其是它们的复杂性。

我刚刚在这里做了一个简单的基准测试：https://quick-bench.com/q/TjtOBZIWRw0oLg9_TywAlv45kmo

但我不知道为什么它们具有完全不同的复杂性。

我知道为什么std::set::find快了。但我不知道为什么另外两个慢。

是否std::find完全忽略a 的顺序std::set，从而std::set将 a 视为像 a 一样的序列容器std::vector？或者我可以说它std::find不知道所有元素都已排序这一事实，因此它会逐一进行搜索（线性复杂度）？

为什么st.begin()比 快std::begin(st)？

Answer 1

时间复杂度差异的原因是它std::find使用迭代器进行操作，并且它确实将其视为std::set序列容器，同时std::set::find使用容器属性。

至于为什么st.begin()比 快std::begin(st)，其实是一样的。第二个函数更快的原因是两个函数都在做同样的事情，并且随着基准测试连续运行，第二个函数的执行速度更快，因为缓存未命中率可能较低且类似。我改变了这两个函数的顺序，得到了完全相反的结果，而且std::begin(st)速度更快。请在此处查看此修改后的基准：https://quick-bench.com/q/iM6e3iT1XbqnW_s-v_kyrs6kqrQ