dgupta0812's blog

By dgupta0812, history, 3 years ago, In English

Hello everyone !! I am new to competetive programming and I am having trouble in searching for a value stored in the first or second value in vector of pairs. So it would be highly grateful of you to explain to me how to do this with the help of comparator function ? Can anyone show the code to search for the lower/upper bound in the first or second value of vector of pair separately ? Thanks in advance !!

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

3 years ago, # |
Rev. 3   Vote: I like it +9 Vote: I do not like it

I will try to explain.

lower_bound/upper_bound allways work on vetor/array sorted by an order determined by some comparator. A comparator is function (or something usable like a function) which returns consistent result while comparing elements. In particular it must allways be true that if a<b && b<c then a<c.

A lot of classes have a default, or call it natural comparator defined. For pair<T1,T2> that comparator compares the first element, and ties on second element.

If we use sort/lower_bound/upper_bound without giving a comparator as argument, that default comparator is used. You will get a compiler/linker error if none is defined.

So, as an example how to implement a comparator for pair<int,string> comparing second before first? I usually do as inline function objects, like:

auto myComp = [&](pair<int,string> e1, pair<int,string> e2) {
    return e1.second<e2.second;
    return e1.first<e2.first;

This myComp can now be used like a function name, ie call it or give it as an argument to other function calls. ie:

vector<pair<int,string>> data(n);
sort(data.begin(), data.end(), myComp);

After having sorted the vector we may use binary search to find entries:

auto it=lower_bound(data.begin(), data.end(), { INT_MIN, "someString" }, myComp);
  cout<<"found first string >=someString at index="<<distance(data.begin(), it)<<endl;
  cout<<"notfound >=someString"<<endl;
  • »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for the explanation.

    There are a few more things I did not understood. Firstly, what does this statement represent --> auto myComp = [&](pair<int,string> e1, pair<int,string> e2 ?

    Why do we have to put INT_MIN in the pair to be founded and what would we have placed in the second of pair if we wanted to search for some integer in the first of pair in the vector of pairs?

    What else could we have placed in place of INT_MIN ?

    Let's suppose we have vector<pair<int,int>> myHash and here I would like to search for some value in the second of pair of myHash, then will putting INT_MIN or any other value in the first of pair affect my answer ?

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

      The "auto myComp=..." is the definition of the comparator. Like if you define a simple function.

      Then, "search for some integer...". Note that it is kind of not possible to search for some integer value if the vector is sorted primarily by the string part.

      The function lower_bound() finds the position of the pair equal or greater than the pair searched for. So, if one is found in the vector it is allways true that:

      1. the string part is bigger or equal
      2. in case the string part is equal the int part is bigger or equal

      The int part of the pair is used in comparison whenever the string part is equal. So, if we use some value bigger than INT_MIN a pair with equal string and lower int would not be found.

      The myHash example: First, you would have to sort myHash in some order. Then you can use lower_bound() to search for positions, but you have to use the same comparator!

      The comparator determines how the given values are used in comparison of the elements.

      • »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Got it this time completely ;) Thanks for your help !!