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

user_3305546 0
Viewed 421

To find an element from a std::set, ofc, we should use std::set::find. However, the function std::find/std::find would work too.

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;
}

As you see, all of the the three methods work as exptected (https://godbolt.org/z/fEjzTae81).

But I don't know their difference, especially their complexity.

I just did a simple benchmark here: https://quick-bench.com/q/TjtOBZIWRw0oLg9_TywAlv45kmo

But I don't know why they have totally different complexity.

I know why std::set::find is fast. But I don't know why the two others are slow.

Does std::find totally ignore the order of std::set so that a std::set will be regarded as an sequence container like a std::vector? Or can I say that std::find doesn't know the fact that all of elements have been ordered so it does the search one by one (linear complexity)?

Why is st.begin() faster than std::begin(st)?

time-complexity stl algorithm c++
1 Answers

The reason for the time complexity difference is that std::find operates with iterators, and it, indeed, does treat std::set as a sequence container, while std::set::find uses container properties.

As for why st.begin() is faster than std::begin(st), they are actually identical. The reason why second is faster is that both of your functions are doing the same thing, and as benchmarks are run consecutively, the execution of the second function is faster because probably cache misses are lower and similar things. I changed the order of these two functions and got exactly opposite result with std::begin(st) being faster. See this modified benchmark here: https://quick-bench.com/q/iM6e3iT1XbqnW_s-v_kyrs6kqrQ

user_118813680
Related