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

upper_bound(multiset.begin(),multiset.end(),x) vs multiset.upper_bound(x) in C++
Автор Parvej, история, 5 лет назад, По-английски

In this problem 1008C - Reorder the Array

I used upper_bound(multiset.begin(),multiset.end(),x) and got TLE.

TLE Sub: 77006832

But when I used multiset.upper_bound(x), I got accepted!

AC Sub:77081261

Can anyone explain to me why inbuilt upper_bound() is slower than the member upper_bound() function of std::multiset?

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

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

upper_bound(set) is O(n)

but

set.upper_bound() is O(log n)

→ Ответить
  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится -11 Проголосовать: не нравится

    Upper_bound() uses binary search. So, it should be log(n) also.

    I used upper_bound() in vector or arrays. But never got TlE.

    Look at this question 706B - Interesting drink

    My sub: 65595364

    → Ответить
    • »
      »
      »
      5 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      set is unlike vector or array, you should be aware of things you use.

      Like this is danger

      • (idx) is (int) type which is signed variable

      • (vec.size()) is (size_t) type which is unsigned variable

      • This can cause loops infinity

      for (int idx = vec.size() - 1; idx >= 0; --idx)
{
    do_something(vec, idx);
}

      Or that your example

      • The complexity is not O(log n) for this case

      • This has been asked once Click me ^^

      lower_bound(all(set), key);
lower_bound(rall(set), key);
upper_bound(all(set), key);
upper_bound(rall(set), key);
      → Ответить
»
5 лет назад, # |
  Проголосовать: нравится -7 Проголосовать: не нравится

When you use upper_bound(multiset.begin(),multiset.end(),x), it creates a copy of the multiset to pass as an object to the function which takes o(n) time and then the search takes o(logn) time.so total time taken is o(n+logn). Whereas thats not the case when you call the function on the object itself.it just requires o(logn) time for the search.

→ Ответить
  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Oh! But when I do it on a vector or array why doesn't it make a copy of the vector or array!

    → Ответить
  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +21 Проголосовать: не нравится

    It doesn't create a copy of the multiset. The reason why upper_bound(multiset.begin(),multiset.end(),x) is slower than $$$O(log$$$ $$$n)$$$ is because you can't get the $$$i$$$-th element in a multiset in $$$O(1)$$$, unlike a vector or an array. multiset.upper_bound(x) works in a different way which allows it to work in $$$O(log$$$ $$$n)$$$.

    → Ответить
»
5 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

Read about the complexity here.
It says, On non-random-access iterators, the iterator advances produce themselves an additional linear complexity in N on average.
Since $$$array$$$ and $$$vector$$$ support random access, using lower_bound() or upper_bound() on them doesn't cause that additional linear time complexity. It only happens while using lower_bound() or upper_bound() on non-random access elements like $$$set$$$ or $$$multiset$$$. So for $$$set$$$ or $$$multiset$$$, you should use lower_bound() or upper_bound() function defined in their own class for efficiency.

→ Ответить