lower bound c что делает
Lower bound c что делает
Множества и мультимножества оптимизированы для поиска элементов, поэтому в этих контейнерах определены специальные функции поиска (таблица 1). Эти функции представляют собой оптимизированные версии одноименных универсальных алгоритмов. Всегда используйте оптимизированные версии функций для множеств и мультимножеств, обеспечивающие логарифмическую сложность вместо линейной сложности универсальных алгоритмов. Например, поиск в коллекции из 1000 элементов требует в среднем 10 сравнений вместо 500 (смотри 42 шаг).
| Операция | Описание |
|---|---|
| count(elem) | Возвращает количество элементов со значением elem |
| find(elem) | Возвращает позицию первого элемента со значением elem (или end() ) |
| lower_bound(elem) | Возвращает первую позицию, в которой может быть вставлен элемент elem (первый элемент >= elem ) |
| upper_bound(elem) | Возвращает последнюю позицию, в которой может быть вставлен элемент elem (первый элемент > elem ) |
| equal_range(elem) | Возвращает первую и последнюю позиции, в которых может быть вставлен элемент elem (интервал, в котором элементы == elem ) |
Результат выполнения программы выглядит так:
Рис.1. Результат работы приложения
Если вместо множества использовать мультимножество, результат останется прежним.
Алгоритм lower_bound()
template class ForwardIterator, class Type
lower_bound( ForwardIterator first,
ForwardIterator last, const Type &value );
template class ForwardIterator, class Type, class Compare
lower_bound( ForwardIterator first,
ForwardIterator last, const Type &value,
lower_bound() возвращает итератор, указывающий на первую позицию в отсортированной последовательности, ограниченной диапазоном [first,last), в которую можно вставить значение value, не нарушая упорядоченности. В этой позиции находится значение, большее либо равное value. Например, если дана такая последовательность:
то обращение к lower_bound() с аргументом value=21 возвращает итератор, указывающий на 23. Обращение с аргументом 22 возвращает тот же итератор. В первом варианте алгоритма используется оператор “меньше”, определенный для типа элементов контейнера, а во втором для упорядочения элементов применяется объект comp.
int search_value = 18;
int *ptr = lower_bound( ia, ia+12, search_value );
// Предыдущее значение равно 17
cout «Первый элемент, перед которым можно вставить «
«Предыдущее значение равно «
vector int, allocator ivec( ia, ia+12 );
sort( ivec.begin(), ivec.end(), greaterint() );
vector int, allocator ::iterator iter;
// необходимо указать, как именно
iter = lower_bound( ivec.begin(), ivec.end(),
// Предыдущее значение равно 29
cout «Первый элемент, перед которым можно вставить «
«Предыдущее значение равно «
Читайте также
8.1.1 Алгоритм
8.1.1 Алгоритм Сразу после переключения контекста ядро запускает алгоритм планирования выполнения процессов (Рисунок 8.1), выбирая на выполнение процесс с наивысшим приоритетом среди процессов, находящихся в состояниях «резервирования» и «готовности к выполнению, будучи
Совет 45. Различайте алгоритмы count, find, binary_search, lower_bound, upper_bound и equal_range
Совет 45. Различайте алгоритмы count, find, binary_search, lower_bound, upper_bound и equal_range Предположим, вы ищете некоторый объект в контейнере или в интервале, границы которого обозначены итераторами. Как это сделать? В вашем распоряжении целый арсенал алгоритмов: count, find, binary_search, lower_bound, upper_bound и
Алгоритм iter_swap()
Алгоритм iter_swap() template class ForwardIterator1, class ForwardIterator2 voiditer_swap( ForwardIterator1 a, ForwardIterator2 b );iter_swap() обменивает значения элементов, на которые указывают итераторы a и b.#include algorithm#include list#include iostream.hint main()
Алгоритм lexicographical_compare()
Алгоритм lexicographical_compare() template class InputIterator1, class InputIterator2 boollexicographical_compare(InputIterator1 first1, InputIterator1 last1,InputIterator1 first2, InputIterator2 last2 );template class InputIterator1, class InputIterator2,class Compare boollexicographical_compare(InputIterator1 first1, InputIterator1 last1,InputIterator1 first2, InputIterator2 last2,Compare comp );lexicographical_compare() сравнивает соответственные пары
Алгоритм max()
Алгоритм min()
Алгоритм merge()
Алгоритм merge() template class InputIterator1, class InputIterator2,class OutputIterator OutputIteratormerge( InputIterator1 first1, InputIterator1 last1,InputIterator2 first2, InputIterator2 last2,OutputIterator result );template class InputIterator1, class InputIterator2,class OutputIterator, class Compare OutputIteratormerge( InputIterator1 first1, InputIterator1 last1,InputIterator2 first2, InputIterator2 last2,OutputIterator result, Compare comp );merge() объединяет
Алгоритм mismatch()
Алгоритм mismatch() template class InputIterator1, class InputIterator2 pairInputIterator1, InputIterator2mismatch( InputIterator1 first,InputIterator1 last, InputIterator2 first2 );template class InputIterator1, class InputIterator2,class BinaryPredicate pairInputIterator1, InputIterator2mismatch( InputIterator1 first, InputIterator1 last,InputIterator2 first2, BinaryPredicate pred );mismatch() сравнивает две последовательности и находит
Алгоритм nth_element()
Алгоритм nth_element() template class RandomAccessIterator voidnth_element( RandomAccessIterator first,RandomAccessIterator nth,RandomAccessIterator last );template class RandomAccessIterator, class Compare voidnth_element( RandomAccessIterator first,RandomAccessIterator nth,RandomAccessIterator last, Compare comp );nth_element() переупорядочивает последовательность, ограниченную диапазоном [first,last), так что все
Алгоритм partial_sort()
Алгоритм partial_sort() template class RandomAccessIterator voidpartial_sort( RandomAccessIterator first,RandomAccessIterator middle,RandomAccessIterator last );templatepartial_sort() сортирует часть последовательности, укладывающуюся в диапазон [first,middle). Элементы в диапазоне [middle,last) остаются неотсортированными. Например, если дан массивint ia[] =
Алгоритм partial_sum()
Алгоритм partial_sum() template class InputIterator, class OutputIterator OutputIteratorpartial_sum(InputIterator first, InputIterator last,OutputIterator result );template class InputIterator, class OutputIterator,class BinaryOperation OutputIteratorpartial_sum(InputIterator first, InputIterator last,OutputIterator result, BinaryOperation op );Первый вариант partial_sum() создает из последовательности, ограниченной
Алгоритм partition()
Алгоритм partition() template class BidirectionalIterator, class UnaryPredicate BidirectionalIteratorpartition(BidirectionalIterator first,BidirectionalIterator last, UnaryPredicate pred );partition() переупорядочивает элементы в диапазоне [first,last). Все элементы, для которых предикат pred равен true, помещаются перед элементами, для которых он равен false.
Алгоритм random_shuffle()
Алгоритм random_shuffle() template class RandomAccessIterator voidrandom_shuffle( RandomAccessIterator first,RandomAccessIterator last );template class RandomAccessIterator,class RandomNumberGenerator voidrandom_shuffle( RandomAccessIterator first,RandomAccessIterator last,RandomNumberGenerator rand);random_shuffle() переставляет элементы из диапазона [first,last) в случайном порядке. Во втором варианте можно
std :: set, как работают lower_bound и upper_bound?
У меня есть этот простой кусок кода:
Это печатает 1 как нижнюю границу для 11 и 10 как верхнюю границу для 9.
Я не понимаю, почему 1 напечатан. Я надеялся использовать эти два метода, чтобы получить диапазон значений для данной верхней / нижней границы.
Решение
От cppreference.com на станд :: набор :: lower_bound:
Возвращаемое значение
Итератор, указывающий на первый элемент, который не является Меньше чем ключ. Если такой элемент не найден, используется итератор за окончанием (см. конец() ) возвращается.
Вы защищаете этот последний итератор it_l : это неопределенное поведение, которое может привести к чему угодно (1 в вашем тесте, 0 или любое другое значение с другим компилятором, или программа может даже аварийно завершиться).
Ваша нижняя граница должна быть меньше или равна верхней границе, и вы не должны разыменовывать итераторы вне цикла или любой другой тестируемой среды:
Другие решения
Это UB. Ваш it_l = myset.lower_bound(11); возвращается myset.end() (так как он не может найти ничего в наборе), который вы не проверяете, и затем вы по существу выводите значение последнего итератора.
нижняя граница() возвращает итератор к первому элементу, который не менее чем ключ. Когда такой элемент не найден, возвращается end ().
Обратите внимание, что итератор, возвращенный с помощью end (), указывает на элемент, который находится в конце коллекции. Это нормальное поведение стандартных контейнеров, указывающее, что что-то пошло не так. Как правило, вы должны всегда проверять это и действовать соответственно.
Ваш фрагмент кода является примером вышеописанной ситуации, поскольку в наборе нет элементов, которые не меньше 11. «1», которое выводится, является просто значением мусора, полученным из итератора end ().
Работа кастомного компаратора в алгоритмах lower_bound и upper_bound
Задача следующая: написать функцию, которая получала бы итераторы на начало и конец отсортированного vector и символ prefix, выдавала бы начало и конец диапазона, строки в котором начинаются с prefix. Застрял на написании лямбды, которую можно подставить в алгоритм поиска. Все ошибки на этапе компиляции, соответственно, не могу пошагово пройтись, и понять, где же именно моя ошибка. По всей видимости, я не до конца (или даже совсем) не поимаю, как работает кастомный компаратор. Код одной из реализаций (тоже с ошибкой):
Ошибка сообщает о том, что в лямбде невозможно преобразовать аргумент 1 из «const Ту» в «const std::string».
И что со всем этим делать?
3 ответа 3
Еще один простой (поиск в векторе целых чисел (куда уж проще)) пример, показывающий работу с lower_bound и upper_bownd.
Возможно имеет смысл напомнить, что при успешном поиске lower_bound возвращает позицию первого из нескольких одинаковых элементов, а upper_bound возвращает позицию сразу за последним (или можно считать, что позицию в которую можно вставить новый элемент, равный искомому и при этом упорядоченность массива сохранится). При неуспешном поиске обе функции возвращают одну и ту же позицию, ту в которую можно вставить искомый элемент.
STL алгоритмы (да и любые сторонние библиотеки) содержат правила, которым должны соответствовать самописные компараторы или функторы.
Идем на любой источник документации по С++ и ищем ограничения для компаратора std::upper_bound :
Аналогично для std::lower_bound :
Из этого делаем вывод:
std::lower_bound вернет вам итератор на начало множества, определенного условием в компараторе, итератор, возвращаемый std::upper_bound итератор будет как минимум не меньше этого итератора. Проще говоря, поиск в std::uppe_bound стоит осуществлять в диапазоне (std::lower_bound(begin, end), end)
Возможно, кому-то мой пост покажется изобретением велосипеда, возможно, кому-то мой пост поможет вникнуть в тему. Не знаю. Для меня наконец-то свершилось открытие, до которого я шел без малого 3 дня. Я наконец понял логику работы лямбда-выражения или функции-компаратора в алгоритмах lower_bound и upper_bound.
Так, например, при векторе <1, 1, 2, 3, 5, 6, 6>и внешней переменной, равной 2, и алгоритме lower_bound при компараторе, сравнивающем элемент_вектора > внешняя_переменная, найти тройку будет невозможно, так как первое значение, принятое на проверку будет 3, как середина интервала, т.к. 3 > 2, интервал поиска станет от 3 до конца вектора. Ну, а так как все числа справа больше 2, то итогом вычисления станет конец вектора. Если же сравнивать результат на меньше, то получим итератор, указывающий на двойку, что, в принципе, нас тоже не устраивает, т.к. двойка не меньше двойки, и уж тем более это не будет нижним пределом.
Обобщу вышесказанное, и добавлю несколько моментов по этим алгоритмам:
Как-то так, бугафф много, надеюсь, кому-то поможет.
C std :: lower_bound, использовать перегруженный оператор в качестве двоичного предиката comp?
Я работаю над заданием, в котором мы должны запрограммировать несколько колод карт, которые могут взаимодействовать друг с другом с помощью векторов (например, удалить одну карту из основной колоды и добавить ее в другую). Присвоение состояний означает, что мы должны использовать перегруженный оператор «меньше чем» из нашей структуры карточек, чтобы определить правильный порядок карточек, комбинируя его с функцией std :: lower_bound. Пока это то, что у меня есть:
А перегруженный оператор «меньше чем» структуры Card выглядит следующим образом. Он сравнивает ранг и масть карт на основе заранее определенного порядка в перечислении:
Любая помощь с благодарностью. Состояния присваивания мы ДОЛЖНЫ использовать перегруженный оператор. Нам не разрешено создавать собственный простой метод IsSmallerThan ().
РЕДАКТИРОВАТЬ: забыл отметить проблему. Дополнительная информация в комментариях.
Решение
должно нормально работать, дать соответствующий operator определены на типах карт.
Стоит отметить, что ваш код для operator можно упростить до
(что также исправляет небольшую ошибку в вашем коде).
Другие решения
если вы хотите действительно предоставить компаратор. Поскольку по умолчанию уже используется вышеперечисленное, вы также можете просто пропустить его:
Вы также можете упростить operator (и сделать его менее подверженным ошибкам) с помощью std::tie :