CODEWITHSUNDEEP
c++stlcomparator
shawnin damnen
shawnin damnen

Reputation: 323

Using comparator in upper_bound STL

I'm trying to make a program that gives the last element that is less than or equal to our given value.

According to the definition of lower_bound, it gives the first element that is greater than or equal to the given key value passed. I created a comparator function 

bool compare(int a, int b) {
    return a <= b;
}

This was passed in my lower bound function:

int largest_idx = lower_bound(ic, ic + n, m, compare)

On execution, it was giving me the last element which was less than equal to my m (key value). Isn't this opposite to how lower_bound works ? Lower bound is supposed to give me the first value for my comparison or does the comparator actually change that?

Upvotes: 0

Views: 3380

Answers (2)

MrTux
MrTux

Reputation: 33993

The comparator must not check for equality, use less than.

Also the data shall already be sorted or must at least be partitioned according to the comparator.

cf. https://www.cplusplus.com/reference/algorithm/lower_bound/

Upvotes: 0

Evg
Evg

Reputation: 26282

If you want to turn "first" into "last", you have two options. First, you can use std::upper_bound and then take the previous element (see below). Second, you can use reverse iterators:

const auto pos = std::lower_bound(
    std::make_reverse_iterator(ic + n),
    std::make_reverse_iterator(ic), m, compare);

where compare is

bool compare(int a, int b) {
    return b < a;
}

With this comparator, std::lower_bound() returns the iterator pointing to the first element that is not greater (= less than or equal) than m. On the reversed range this is equivalent to returning the iterator pointing to the last element satisfying this criterion in the original range.

Simple example:

int ic[] = {1, 3, 3, 5};
// pos
// m = 1    ^ 
// m = 2    ^
// m = 3          ^

How do I modify that search criteria (change <= to something else)?

std::lower_bound finds the first element in the range (partitioned by the comparator into true, ..., true, false, ... false), for which the comparator returns false. If your criterion can be rephrased in this language, you can use std::lower_bound.

Suppose we have a range 1 3 3 5 and we replace < with <= (your version of compare). Then we have:

        1 3 3 5
m = 2   T F F F
m = 3   T T T F
m = 4   T T T F

For m = 3 and m = 4, std::lower_bound will return the iterator to 5, i.e. past the last 3. In other words, std::lower_bound with default < being replaced with <= is exactly what std::upper_bound with default < is. You can advance the resulting iterator by -1 to get the last element (but be careful about corner cases like m = 0 in this example).

How do I change whether I want the first or last element

It always returns the first element for which the comparator returns false. You can either reverse the range or find the first element that follows the one you want to find.

Upvotes: 1

Related Questions