Why does std::upper_bound() have linear complexity?

Question

I was reading the guide on USACO Silver talking about sorted sets, and I came across this warning (s is a 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!

What do they mean ?

   upper_bound(s.begin(), s.end(), 7 ); // O(n) ?
   s.upper_bound(7);                    // O(log N) ?

Answer 1

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.

Answer 2

From cppreference:

for non-LegacyRandomAccessIterators, the number of iterator increments is linear. Notably, std::map, std::multimap, std::set, and std::multiset iterators are not random access