Vampire_Questt's blog

set.upper_bound(element) is much faster than upper_bound(set.begin() , set.end() , element)

By Vampire_Questt, history, 3 years ago, In English

Today while giving AtCoder Beginner Contest 217, I noticed that set.upper_bound(element) is faster than upper_bound(set.begin() , set.end() , element). During the contest I used upper_bound(set.begin() , set.end() , element) and got TLE. But after the contest I resubmitted my code with set.upper_bound(element) and got AC.

contest link : https://atcoder.jp/contests/abc217/tasks

Problem link : https://atcoder.jp/contests/abc217/tasks/abc217_d

TLE solution link : https://atcoder.jp/contests/abc217/submissions/25614807

AC solution link : https://atcoder.jp/contests/abc217/submissions/25614873

  • Vote: I like it
  • -5
  • Vote: I do not like it

»
3 years ago, # |
← Rev. 2   Vote: I like it +10 Vote: I do not like it

The number of comparisons performed is logarithmic in the distance between first and last (At most log2(last — first) + O(1) comparisons). However, for non-LegacyRandomAccessIterators, the number of iterator increments is linear. Notably, std::set and std::multiset iterators are not random access, and so their member functions std::set::upper_bound (resp. std::multiset::upper_bound) should be preferred.

(from cppreference)

→ Reply