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

Difference between lower_bound s
Автор Aryan, история, 7 лет назад, По-английски

I really want to know whats the difference between 2 types of lower_bound? 1) lower_bound(st.begin(), st.end(), val) and 2) st.lower_bound(val). As you can see in 28778333 and 28778499 the second type is much much faster!

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

»
7 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

If you have something like std::set(no random access iterators), set.lower_bound works in o(logN) and lower_bound(st,begin(), st.end()) works in O(n), checking every element, where N is the size of set

→ Ответить