Peregrine_Falcon's blog

Need help about STL set in C++
By Peregrine_Falcon, history, 6 years ago, In English

In this problem I used set < pair < int , int > > st;

auto it = lower_bound( st.begin(), st.end(), make_pair( a + d + 1 , 0 ) )

But it costs me several TLE. But when I look over the tutorial solution, I saw this-

it = st.lower_bound( make_pair( a + d + 1 , 0 ) );

I used it, & got AC.

But I don't understand what's the difference? If anyone can please help. TLE Submission AC Submission Thank You O_o

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

Comments Comments (8)
| Write comment?
»
6 years ago, # |
← Rev. 2   Vote: I like it +6 Vote: I do not like it

lower_bound from <algorithm> requires random access iterators for it to be . Set does not have random access iterators.

The member function lower_bound in set is and uses a different approach that uses the properties specific to set (i.e searching the balanced binary search tree maintained by set).

→ Reply
»
6 years ago, # |
  Vote: I like it +10 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
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

lower_bound(st.begin(), st.end(), x) is efficient for random-access iterator. However, the stl set iterators aren't. Therefore, lower_bound(st.begin(), st.end(), x) is actually O(n)

In contrast, the st.lower_bound() is a built-in function for red-black tree, so it works in O(log2(n))

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

Can we lower_bound on map as well?

→ Reply