Использование компаратора в upper_bound STL - PullRequest
Новая
       16

Использование компаратора в upper_bound STL

0 голосов
/ 26 апреля 2020

Я пытаюсь создать программу, которая дает последний элемент, который меньше или равен нашему заданному значению.

Согласно определению lower_bound, он дает первый элемент, который больше или равен заданному значению ключа. Я создал функцию компаратора 

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

Это было передано в моей функции нижней границы: 

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

При выполнении это дало мне последний элемент, который был меньше, чем мой m (ключевое значение). Разве это не противоположно тому, как работает lower_bound? Предполагается, что нижняя граница даст мне первое значение для моего сравнения, или компаратор действительно изменит это?

Ответы [ 2 ]

0 голосов
/ 26 апреля 2020

Если вы хотите превратить «первый» в «последний», у вас есть два варианта. Сначала вы можете использовать std::upper_bound, а затем взять предыдущий элемент (см. Ниже). Во-вторых, вы можете использовать обратные итераторы : 

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

, где compare равно 

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

С этим компаратором std::lower_bound() возвращает итератор, указывающий на первый элемент, который не больше (= меньше или равен), чем m. В обратном диапазоне это эквивалентно возвращению итератора, указывающего на последний элемент, удовлетворяющий этому критерию в исходном диапазоне.

Простой пример: 

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

Как мне изменить это критерий поиска (изменить <= на другое)?

std::lower_bound находит первый элемент в диапазоне (разделенный компаратором на true, ..., true, false, ... false), для которого компаратор возвращает false. Если ваш критерий можно перефразировать на этом языке, вы можете использовать std::lower_bound.

Предположим, у нас есть диапазон 1 3 3 5, и мы заменим < на <= (ваша версия compare). Тогда мы имеем: 

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

Для m = 3 и m = 4, std::lower_bound вернет итератор в 5, то есть после последнего 3. Другими словами, std::lower_bound с заменой по умолчанию < на <= - это именно то, чем является std::upper_bound со значением по умолчанию <. Вы можете продвинуть полученный итератор на -1, чтобы получить последний элемент (но будьте осторожны с угловыми случаями, такими как m = 0 в этом примере).

Как изменить, хочу ли я первый или последний элемент

Всегда возвращает первый элемент, для которого компаратор возвращает false. Вы можете либо изменить диапазон, либо найти первый элемент, следующий за тем, который хотите найти.

0 голосов
/ 26 апреля 2020

Компаратор не должен проверять равенство, использовать меньше.

Также данные уже должны быть отсортированы или должны быть хотя бы разделены в соответствии с компаратором.

ср. https://www.cplusplus.com/reference/algorithm/lower_bound/

...