techwiz911's blog

Difference between S.lower_bound(key) and lower_bound(S.begin(),S.end(),key)
By techwiz911, history, 9 years ago, In English

I was attempting the following question 310D

Here is my submission that timed-out TLE

And here is my submission that was accepted AC

As you may have observed, the only change I made from the TLE code to AC code was

  it=lower_bound(s.begin(),s.end(),mp(lo,o));

to

  it=s.lower_bound(mp(lo,o));

where "it" is a set iterator.

Just changing this, the time on Test #11 was reduced from >3000ms to 264ms. Can any one shed some light on why this happened? Thank you.

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

Comments Comments (7)
| Write comment?
»
9 years ago, # |
  Vote: I like it +10 Vote: I do not like it

I think without be sure that the first runs in 0(N), and the second in O(logN).

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

    Okay. But why the change in behaviour for the same function? I mean what goes behind the curtains?

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

See complexity of these methods 1 2

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

    Thanks a lot. Glad I got to know this now, getting TLE in a contest because of this would have hurt.

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

Actually you will find everything about C++ in this site. So, you can always check anything there.

http://www.cplusplus.com/

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

The key is, that the lower_bound in the algorithm package has no knowledge about the internal structure of set. It can do a binary search for random access containers, but not for set. For set, it has to go through all elements step by step.

On the other hand, set's lower_bound can leverage its knowledge about its internal structure, and can do it log n runtime.

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

    One minor technical detail is that the lower_bound function from algorithm actually always does a binary search.

    It's just that for forward iterators such as set::iterator that are not random access iterators advance(iterator,constant) is slow. More precisely, you need roughly k operations to advance an iterator by k, and this is what makes the total time complexity linear instead of logarithmic.

    (Hence, lower_bound on a container that only has forward iterators will usually be a bit slower than find.)

    → Reply