Compare function

#1

how does the compare function work here?
in the final code that is compiled at last, it says
lb=lower_bound(coins,coins+n,compare)-coins-1.
if we put our money=100, then lower bound is equal to 6. so finally, lb=6-0-1=5 coins [5]=50. how does compare get called and what happens exactly that the output returned is still correct i.e 100 instead of 50??. please reply at the earliest and do explain the function call procedure

#2

Hello @akash27,

To understand the requirement of this comparator you need to understand the lower_bound() function.

It returns an iterator pointing to the first element in the range [first,last) which does not compare less than val i.e. just smaller than the passed value.

But, in this question we want a coin that is either equal to the amount or just smaller(the closet) to it.

Thus, to consider this equal to, sir has written an external comparator.

Hope, this would help.
Give a like if you are satisfied.

#3

i understanding that sir but please tell me this. how exactly did our problem get resolved. I am asking how does the comparator function ? I am aware of the lower bound and its usage. all I am asking is how does comparator function in this case? could you please dry run it and explain it in the same way I’ve explained my problem?

#4

i feel that in lb=lower_bound-coins-1; the -1 at the end is extra because our inbuilt comparator does the work and returns the address of a number less than or equal to ‘money’. if we still use the -1 then we’re just going one address backward for no reason. don’t you think so?

#5

Hello @akash27,

  1. for money=100, lower_bound(coins,coins+n,money,compare) function will give 7 as output because it is present at 7th position.
    so finally, lb=7-0-1=6 coins [6]=100.
    Suggestion:
    Try to print lower_bound(coins,coins+n,100,compare)-coins.

  2. Usually, the inbuilt comparator of lower_bound check for the condition of x<y.
    Thus, returning an iterator to the value less than money.
    Here, you are checking for equality also.
    It is operating the same way binary search works.
    It takes two parameters, one of which is money=100(in your example) and compares other elements(at current mid) with 100, in the way binary search work.

Hope, this would help.

#6

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.