Parvej's blog

upper_bound(multiset.begin(),multiset.end(),x) vs multiset.upper_bound(x) in C++
By Parvej, history, 4 years ago, In English

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?

  • Vote: I like it
  • +14
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +13 Vote: I do not like it

upper_bound(set) is O(n)

but

set.upper_bound() is O(log n)

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it -11 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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);
      → Reply
»
4 years ago, # |
  Vote: I like it -7 Vote: I do not like it

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.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    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)$$$.

    → Reply
»
4 years ago, # |
  Vote: I like it +11 Vote: I do not like it

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.

→ Reply