og_prakash's blog

Lower Bound in Map C++
By og_prakash, history, 11 months ago, In English

Whats the difference between these 2

map.lower_bound(val) vs lower_bound(map.begin(),map.end(),val)

i was getting tle on https://mirror.codeforces.com/contest/1902/submission/239546603

correct on https://mirror.codeforces.com/contest/1902/submission/239546733

with just 1 line change

TLE -> auto it = lb(mp2[(p4.fi+n)][p4.se].begin(), mp2[(p4.fi+n)][p4.se].end(), l-1);
CORRECT -> auto it=mp2[(p4.fi+n)][p4.se].lb(l-1);

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

»
11 months ago, # |
  Vote: I like it +4 Vote: I do not like it

A similar answer for std::set is here.

→ Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

see this

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

Short answer -> If you are using a data structure like a set or map always use their own implementation of lower_bound() they are faster, probably because of some internal implementation.

For arrays and vectors you can use the normal lower bound. My guess is that it has something to do with the accessing time of the elements while performing the operations.

→ Reply