root8950's blog

By root8950, history, 4 years ago, In English,

I have a set as
set<int> s;
I used lower_bound(s.begin(),s.end(),x)
It gave me TLE.
Then i used s.lower_bound(x)
My solution passed.
Whats the difference in both? I mean why is it happening?
First one is working in O(n) time while latter in O(logn).
Weren't both supposed to be O(logn) ?

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

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

Auto comment: topic has been updated by root8950 (previous revision, new revision, compare).

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

STL was designed to be universal and flexible.

There are a bunch of containers, and all of them need to support universal operations like iterating through elements, sorting, finding element, etc. So instead of implementation multiple methods container.sort() in all of the containers, which for majority of them will be the same algorithm, STL offers one unified function std::sort(), which can be used to sort different containers. Same with function std::lower_bound().

However, due to internal model of containers not all of them use the same algorithm. For example, you cannot access elements in random order in list like you do in vector. So for that case, there are methods designed specifically for the container. So list have method list::sort() which use algorithm specific for linked list structure.

Just same story with set and lower_bound(). There is a unified function std::lower_bound(), which works in O(logN) on Random Access Iterators, and O(N) on other iterators. Container std::set has Bidirectional Iterator and cannot provide random access to its members. So unified std::lower_bound() works in O(N). Yet, container set is binary search tree and can find lower bound in O(logN) using different algorithm, specific for internal structure of std::set. It is implemented in method set::lower_bound(), which works in O(logN).

This is one of the fundamental ideas in STL, so I recommend you to read some literature about STL in general.

Hope that helps, feel free to ask/correct something.