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
don'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)
?
CodePudding user response:
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