sidforces's blog

Working of lower_bound and upper_bound functions in set < pair < int , int > >
By sidforces, history, 5 years ago, In English

Can anyone explains me how the lower_bound and upper_bound functions work in set<pair<int,int> >. I mean to ask how they actually match any pair in the set with the given parameters step by step. Like i read somewhere that it first checks the first int and then goes for second so, what it actually does? I also refered this blog https://codeforces.net/blog/entry/17077 but the confusion still remains. Like I write this code-

set<pii> ms;

for(int i=0;i<10;i=i+2)

ms.insert(mp(i,i+1));

ms.insert(mp(2,4));

ms.insert(mp(2,2));

ms.insert(mp(4,4));

int x,y;

cin>>x>>y;

cout<<ms.lower_bound(mp(x,y))->first<<" "<<ms.lower_bound(mp(x,y))->second<<endl;

cout<<ms.upper_bound(mp(x,y))->first<<" "<<ms.upper_bound(mp(x,y))->second<<endl;

and on the input of (2,2) it is giving the output (2,2) for lowerbound and (2,3) for upperbound then why it is giving the output for upperbound as (2,3) because upperbound gives the just > value and it checks first int first then all pairs with '2' as first element should be discarded.And on the input of (7,10) output is (8,9) for both the functions. Now it is just checking the first int and ignoring the second int '10' because upperbound of 10 cannot be 9.

So, please if anybody can clear my confusions then please comment and may be I am understanding it totally wrong and asking the wrong question so please inlight me where i am wrong.

Thanks in advance.

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

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

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

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

I don't really understand your question so forgive me if this answers a different thing.

First let me explain how the pairs are sorted
Pairs are sorted first based on the leftmost values then by their rightmost values
So if their leftmost values are equal they are sorted based on their rightmost values
Let me give two examples $$$(-1, 2)$$$ is less than $$$(3, 2)$$$ and $$$(2, 2)$$$ is less than $$$(2, 3)$$$
So your set is sorted like this
$$$(0, 1)$$$ $$$<$$$ $$$(2, 2)$$$ $$$<$$$ $$$(2, 3)$$$ $$$<$$$ $$$(2, 4)$$$ $$$<$$$ $$$(4, 4)$$$ $$$<$$$ $$$(4, 5)$$$ $$$<$$$ $$$(6, 7)$$$ $$$<$$$ $$$(8, 9)$$$

LOWER BOUND is the first element greater than or equal to the given input
UPPER BOUND is the first element strictly greater than the given input

So from the definition of LOWER BOUND it should now be obvious that the LOWER BOUND for $$$(2, 2)$$$ is $$$(2, 2)$$$ since it's the first element equal to the given input and the UPPER BOUND is $$$(2, 3)$$$ since it's the first element strictly greater than $$$(2, 2)$$$.

Same goes for $$$(7, 10)$$$.

Hope this helps)

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

    thanks a lot. Your concept of considering the element in the set and then think about the upper_bound is very nice. This removes my confusion.

    → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +6 Vote: I do not like it

When no comparator function is specified while constructing the set, set invokes operator< for comparing elements.

And from cppreference operator< for pair

Compares lhs and rhs lexicographically, that is, compares the first elements and only if they are equivalent, compares the second elements.
That's why because of the lexicographic order (2, 2) is lesser than (2, 3) and (7, 10) is lesser than (8, 9).
→ Reply