Блог пользователя Vampire_Questt

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

Автор Vampire_Questt, история, 3 года назад, По-английски

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

  • Проголосовать: нравится
  • -5
  • Проголосовать: не нравится

»
3 года назад, # |
← Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

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)

→ Ответить