AHMADUL's blog

Explanation of lower_bound function.
By AHMADUL, history, 4 years ago, In English

I was trying to solve problem B1 of Helvetic Coding Contest 2019 online mirror (teams allowed, unrated). I got WA and TLE for a several time.Then I went to standings and found a line from a submission: int f=lower_bound(dg,dg+b,make_pair(a[i],10000000))-dg;
But,I couldn't understand it,,why I have to subtract dg at last??? Now, I am badly in need of help.Someone please explain the above statement.

  • Vote: I like it
  • -9
  • Vote: I do not like it

Comments Comments (11)
| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

lower bound returns first iterator of the value greater then or equal you are searching for. And by seeing your code it can be assumed it is used for finding the position of the value of make_pair(a[i], 10000000) in a container named dg. If you subtract dg from the returned iterator of lower_bound function then you will get the position. because dg is similar to dg.begin() here. both of them points first value of the container. [ extra tip: subtracting two iterator or pointer gives how many chunks of memory address are there between(not depends on your datatype) ]. you can know more about lower bound in here

btw, next time please attach the code where you have taken a part from it. Cause now I don't know whether the dg container is sorted or not. or which container is it. Thanks, have a good day. :D

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 3   Vote: I like it -7 Vote: I do not like it

    dg is an array(not std::array but std::pair<int,int> dg[10]) but not a container. array shall not support begin() method, anyway it's not an obeject at all. and a container's name is also not equal to its begin() method. But since c++11 you can use std::begin() and std::end() whether arr is an array or a container.

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

      coyorkdow i didn't know without a container we can store pairs. It would be nice of you if you give some reference about this. Thanks. :)

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

        In c++ containers library is a generic collection of class templates and algorithms that allow programmers to easily implement common data structures like vector, queues, lists and stacks. reference from https://en.cppreference.com/w/cpp/container. So std::pair<int,int> is not a container but std::vector<std::pair<int,int>> is a container that stores std::pair<int,int>. Meanwhile std::pair<int,int>[100] and new std::pair<int,int>[100] can also stores pairs but neither are container. When memory are allocated, each object will call its default constructor.

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

lower_bound returns an iterator(or an pointer if parameters are not iterators) pointing to the first element in the range [first, last) that is not less than value you gived. So if you want to get the index of an element then you should transform it into an integer. Both random iterator and or pointer support subtract operation and will return the numbers of differences of elements between two interators or pointers(i.e. an iterator pointing to a[5] subtract to an interator pointing to a[2] will returns 3). Since dg is an array, array name points to the first element of the array. So after you do the subtract you get the index of the first element in the range from dg[0] to dg[b] which is not less then make_pair(a[i],10000000).

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

    Pointer is a kind of iterator

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

    make_pair(a[i],10000000)--->What kind of argument is it???Why I have to write it in the third slot of the funtion???

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

      It is the "value you gived". std::make_pair() will return a pair which contains two parameters. If a[i] is an int value then you will get a std::pair<int,int> object. You find the first element that is not less than this pair.

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

What if you learn your programming language a bit before solving problems?

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

    More like "learn to look up how unfamiliar features work" instead of spamming questions.

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

Maybe google can help?

→ Reply