ISuckAtLife's blog

By ISuckAtLife, history, 4 years ago, In English

So, Just few hours back I learned that complexity of lower_bound(st.begin(),st.end(),val) is much much higher than st.lower_bound(val). where st is normal stl set in c++

As you can see the only difference between 81895138 and this 81894342 is the one mentioned above.

I thought I should share it with the community as me myself and my few friends didn't know about this.

I don't know the reasons for this, it would be really helpful if someone could give the reasons and actual complexity of lower_bound(st.begin(),st.end(),val).

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

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

Best to check cppreference first. http://www.cplusplus.com/reference/algorithm/lower_bound/

On average, logarithmic in the distance between first and last: Performs approximately log2(N)+1 element comparisons (where N is this distance). On non-random-access iterators, the iterator advances produce themselves an additional linear complexity in N on average.