so i was reading the guide on USACO Silver talking about sorted sets, and i came across this warning (s is sorted std::set of integers)
Warning!
Suppose that we replace s.upper_bound(7) with upper_bound(begin(s),end(s),7), which was the syntax that we used for vectors in the prerequisite module. This will still output the expected results, but its time complexity is linear in the size of the set s rather than logarithmic, so make sure to avoid it!
https://usaco.guide/silver/intro-sorted-sets#sorted-sets
what do they mean ?
upper_bound(s.begin(), s.end(), 7 ); // o(n) ?
s.upper_bound(7); // o(logN) ?
>Solution :
It’s because a std::set doesn’t support random access iterators. In order to get from a to a + 200 the algorithm would have to increase a 200 times.
For this reason, the std::set has member functions for finding the upper_bound and lower_bound efficiently.