Реализация lower_bound на векторных парах

Question

Реализация lower_bound на векторных парах

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

Но не в состоянии написать для этого.

Например:

Элементы вектора ={(2,4),(4,2),(5,1),(5,3)}

найти = 5

lower_bound () должен вернуть 2

код->

#define pp pair<int,int>

bool cmp(const pp &l,const pp &r) {
return l.first < r.first;
}

int main() {
vector<pp> v;
sort(v.begin(), v.end(), cmp);
int id=(int)(lower_bound(v.begin(), v.end(), ??) - v.begin());
}

4

c++lower-bound std-pair vector

Решение

Другие решения

Пары (так же, как кортежи) сравнить лексически тем не мение. Вы не нужно определять никаких специальных компараторов за это.

И так как вы используете lower_bound вы будете искать первый элемент, который не сравнивает меньше, чем val вы ищете, поэтому вы должны использовать min значение в качестве второго элемента пары. Подводить итоги, все можно сделать в «двух» строках кода :

sort(v.begin(),v.end());
auto id = distance(v.begin(), lower_bound(v.begin(),v.end(),
make_pair(5, numeric_limits<int>::min())) );

Некоторые заметки:

использование std::distance рассчитать количество элементов между двумя итераторами
Тип возврата std::distance это тип без знака. Если вам не нужна отрицательная индексация (синтаксис, подобный Python для индексов «считать с конца»), хорошей практикой является сохранение ваших индексов без знака.

3

Я думаю, что вы должны сравнить пары в соответствии с определением lower_bound
Так,

   typedef pair<int,int> pp;
//...

int id=(int)(lower_bound(v.begin(),v.end(),
pp(5,std::numeric_limits<int>::min())), //Value to compare
[](const pp& lhs, const pp& rhs)       // Lambda
{
return lhs < rhs ;                //  first argument < second
}
) - v.begin()
);

1

Источник

Accepted Answer

Так как вас не волнует второе значение ppПостроить временный pp объект с любым значением в качестве второго элемента.

int id = std::lower_bound(v.begin(), v.end(), pp(5, 0), cmp) - v.begin();

4