Upper_bound для pair

115

25 января 2022, 00:30

Язык: С++

Имеется упорядоченный по возрастанию массив пар p с значениями заданными от p[1] до p[2*n]. Нужно при введенном x найти мин. индекс index такой, что x < p[index].first (значения в p.second не важно) или формально upper_bound. Пытался ввести следующие команды:

                  int index = upper_bound(p + 1, p + 2 * n + 1, x);

Или же через лямбда функции

 int index = upper_bound(p + 1, p + 2*n + 1, x, [&](pair u){
                        return (u.first < x);
});

В первый раз вожусь с этой функцией, и уверен что ошибка просто в моем незнании синтаксиса. Можете помочь с проблемой, плюс разъяснить по полкам синтаксис upper_bound (по крайней мере ссылку: можно и на английском)

Ремарка: понимаю что можно просто переписать p.first значения в одномерный массив и для него делать upper_bound с первой выше написанной командой, но просто самому хотелось бы разобраться в синтаксисе на будущее.

Answer 1

Ну, нужно примерно так:

auto i = upper_bound(p,p+2*n,make_pair(x,0));

Или, если вам критично от p[1], то

auto i = upper_bound(p+1,p+2*n+1,make_pair(x,0));

Просто вы же должны сравнивать однотипные величины...

Да, вернет функция никак не индекс, а итератор на найденный элемент (или итератор за конец массива). В cлучае массива это будет указатель

pait<int,int>*

P.S. Ан, нет - насчет типа соврал. Вы можете передавать и int, вот так:

auto i = upper_bound(p,p+2*n,value,[](int x, const pair<int,int>& z){ return x < z.first; });

Но это все немножко на грани фола - потому что если только ваша функция сравнения не будет соответствовать требованию upper_bound, то результат может быть самым неверным... Но в этом конкретном случае сравнение первого поля с переданным значением для отсортированного массива удовлетворяет условию.