I have a set as
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) ?
Auto comment: topic has been updated by root8950 (previous revision, new revision, compare).
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
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
listlike 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
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::sethas Bidirectional Iterator and cannot provide random access to its members. So unified
std::lower_bound()works in O(N). Yet, container
setis 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.
Is there a stl for finding just immediate lower or equal value than key in map/set In lower_bound I get iterator to the key or next immediategreater value Is there any stl for getting iterator to the key or immediate smaller value than key
One way is to simply use
set<int, greater<int>>, then
lower_bounddoes what you ask for.
If you need to have both immediate greater and immediate smaller, then do the following. Suppose you want the immediate strictly lower value of
xin the set
s.lower_bound(x) == s.begin(), there is no answer; otherwise the iterator is
By the way I think it would be better to make a new blog instead of commenting on a mostly-irrelevant old blog.
I feared of getting no reply or may be I asked a stupid question...Many times I feel like to make a new post. But eventually can't for some psychological issue. In future I would try to do like you advised. Thank you