root8950's blog

Difference in these two ways of using lower_bound [C++]
By root8950, history, 9 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

»
9 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).

→ Reply
»
9 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.

→ Reply
»
5 years ago, # |
  Vote: I like it -12 Vote: I do not like it

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

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

    One way is to simply use set<int, greater<int>>, then lower_bound does 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 x in the set s. If s.lower_bound(x) == s.begin(), there is no answer; otherwise the iterator is prev(s.lower_bound(x)).

    By the way I think it would be better to make a new blog instead of commenting on a mostly-irrelevant old blog.

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

      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

      → Reply