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

Question

要从 std::set、ofc 中查找元素，我们应该使用 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是否完全忽略std::set的顺序，这样std::set就会像[=一样被当成一个序列容器21=]?或者我可以说 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

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

How does std::find works with std::set

c++

algorithm

stl

time-complexity