Блог пользователя AHMADUL

Explanation of lower_bound function.
Автор AHMADUL, история, 4 года назад, По-английски

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.

  • Проголосовать: нравится
  • -9
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    4 года назад, # ^ |
    ← Rev. 3   Проголосовать: нравится -7 Проголосовать: не нравится

    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.

    → Ответить
    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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. :)

      → Ответить
      • »
        »
        »
        »
        4 года назад, # ^ |
        ← Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

        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.

        → Ответить
»
4 года назад, # |
← Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Pointer is a kind of iterator

    → Ответить
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      → Ответить
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Maybe google can help?

→ Ответить