CODEWITHSUNDEEP
c++dictionarystl
mvxxx
mvxxx

Reputation: 188

std::map::upper_bound vs std::upper_bound performance

In some CP contest (it is important) I have used 2 versions of upper_bound to find upper bound in my std::map:

Algorithm upper bound (1):

auto itr = std::upper_bound(s.begin(),s.end(), somenumber);

if(itr == s.end() || *itr > somenumber2)
{
//dosth
} else
//dosth2
}

std::map::upper_bound (2):

auto itr = s.upper_bound(somenumber);

if(itr == s.end() || *itr > somenumber2)
{
//dosth
} else
//dosth2
}

Both versions works if I put small input by hand. But when comes to ~500.000 input (1) exceeded the time limit (4 seconds) but (2) do the job in 0.5/4.0 second.
I checked at docs algorithm/upper_bound and map/upper_bound and both have O(c log(n)) complexity (I think that in both cases c should be similar.
So the question is - what caused that difference?

Upvotes: 3

Views: 1897

Answers (1)

walnut
walnut

Reputation: 22152

The cppreference page for std::upper_bound says that the number of comparisons done is logarithmic, but it also continues:

However, for non-LegacyRandomAccessIterators, the number of iterator increments is linear.

std::map does not have random access iterators and therefore std::upper_bound will be allowed to have linear time complexity in the iterator distance due to increments, while std::map::upper_bound is required to have logarithmic time complexity in the size of the container.

Upvotes: 3

Related Questions