1. Главная страница » Компьютеры » Lower bound upper bound

Lower bound upper bound

Автор: | 16.12.2019

У меня есть этот простой кусок кода:

Это печатает 1 как нижнюю границу для 11 и 10 как верхнюю границу для 9.

Я не понимаю, почему 1 напечатан. Я надеялся использовать эти два метода, чтобы получить диапазон значений для данной верхней / нижней границы.

Решение

От cppreference.com на станд :: набор :: lower_bound:

Возвращаемое значение

Итератор, указывающий на первый элемент, который не является Меньше чем ключ. Если такой элемент не найден, используется итератор за окончанием (см. конец() ) возвращается.

В вашем случае, поскольку в вашем наборе нет элементов, которые не меньше (то есть больше или равны), чем 11, возвращается итератор за окончанием и назначается it_l , Тогда в вашей строке:

Вы защищаете этот последний итератор it_l : это неопределенное поведение, которое может привести к чему угодно (1 в вашем тесте, 0 или любое другое значение с другим компилятором, или программа может даже аварийно завершиться).

Ваша нижняя граница должна быть меньше или равна верхней границе, и вы не должны разыменовывать итераторы вне цикла или любой другой тестируемой среды:

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

Это UB. Ваш it_l = myset.lower_bound(11); возвращается myset.end() (так как он не может найти ничего в наборе), который вы не проверяете, и затем вы по существу выводите значение последнего итератора.

нижняя граница() возвращает итератор к первому элементу, который не менее чем ключ. Когда такой элемент не найден, возвращается end ().

Обратите внимание, что итератор, возвращенный с помощью end (), указывает на элемент, который находится в конце коллекции. Это нормальное поведение стандартных контейнеров, указывающее, что что-то пошло не так. Как правило, вы должны всегда проверять это и действовать соответственно.

Ваш фрагмент кода является примером вышеописанной ситуации, поскольку в наборе нет элементов, которые не меньше 11. «1», которое выводится, является просто значением мусора, полученным из итератора end ().

Скажите пожалуйста, что такое upper_bound и lower_bound в стандартной библиотеке С++ и как они работают.

1 ответ 1

Ну, например, у вас есть упорядоченная (важно!) последовательность

При поиске upper_bound для значения 5 это будет итератор (указатель, если концепция итератора для вас нова) на значение 6 — первое большее значение.

Соответственно, lower_bound будет указывать на первое не меньшее значение — на первое 5.

Совет 45. Различайте алгоритмы count, find, binary_search, lower_bound, upper_bound и equal_range

Предположим, вы ищете некоторый объект в контейнере или в интервале, границы которого обозначены итераторами. Как это сделать? В вашем распоряжении целый арсенал алгоритмов: count, find, binary_search, lower_bound, upper_bound и equal_range. Как же принять верное решение?

Очень просто. Основными критериями должны быть скорость и простота.

Временно предположим, что границы интервала поиска обозначены итераторами. Случай с поиском во всем контейнере будет рассмотрен ниже.

При выборе стратегии поиска многое зависит от того, определяют ли итераторы сортированный интервал. Если это условие выполнено, воспользуйтесь алгоритмами binary_search, lower_bound, upper_bound и equal_range для проведения быстрого поиска (обычно с логарифмической сложностью — см. совет 34). Если интервал не отсортирован, выбор ограничивается линейными алгоритмами count, count_if, find и find_if. В дальнейшем описании _if-версии алгоритмов count и find игнорируются, как и разновидности binary_search, lower_bound, upper_bound и equal_range, которым при вызове передается предикат. Алгоритм поиска выбирается по одним и тем же соображениям независимо от того, используете ли вы стандартный предикат или задаете свой собственный.

Итак, в несортированных интервалах выбор ограничивается алгоритмами count и find. Эти алгоритмы решают несколько отличающиеся задачи, к которым следует присмотреться повнимательнее. Алгоритм count отвечает на вопрос: «Присутствует ли заданное значение, и если присутствует — то в каком количестве экземпляров?». Для алгоритма find вопрос звучит так: «Присутствует ли заданное значение, и если присутствует — то где именно?»

Допустим, вы просто хотите проверить, присутствует ли в списке некоторое значение w класса Widget. При использовании алгоритма count решение выглядит так:

list lw;// Список объектов Widget

Widget w;// Искомое значение класса Widget

// Значение w присутствует в lw

// Значение не найдено

В приведенном фрагменте продемонстрирована стандартная идиома: применение count для проверки существования. Алгоритм count возвращает либо ноль, либо положительное число; в программе ненулевое значение интерпретируется как логическая истина, а ноль — как логическая ложь. Возможно, следующая конструкция более четко выражает суть происходящего:

Читайте также:  Philips sonicare совместимость насадок

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

Решение с алгоритмом find выглядит чуть сложнее, поскольку возвращаемое значение приходится сравнивать с конечным итератором списка:

if(find(lw.begin(), lw.end(),w) !=w.end())<

В контексте проверки существования идиоматическое использование count чуть проще кодируется. С другой стороны, оно также менее эффективно при успешном поиске, поскольку find при обнаружении искомого значения немедленно прекращает поиск, a count продолжает искать дополнительные экземпляры до конца интервала. Для большинства программистов выигрыш в эффективности компенсирует дополнительные хлопоты, связанные с программированием find.

Впрочем, простой проверки существования во многих случаях бывает недостаточно; требуется также найти в интервале первый объект с заданным значением. Например, этот объект можно вывести, вставить перед ним другой объект или удалить его (удаление в процессе перебора рассматривается в совете 9). Если требуется узнать, какой объект (или объекты) имеют заданное значение, воспользуйтесь алгоритмом find:

list ::iterator i = find(lw.begin(),lw.end(),w);

// Успешный поиск, i указывает на первый экземпляр

// Значение не найдено

При работе с сортированными интервалами существуют и другие варианты, и им определенно стоит отдать предпочтение. Алгоритмы count и find работают с линейной сложностью, тогда как алгоритмы поиска в сортированных интервалах (binary_search, lower_bound, upper_bound и equal_range) обладают логарифмической сложностью.

Переход от несортированных интервалов к сортированным влечет за собой изменение критерия сравнения двух величин. Различия между критериями подробно описаны в совете 19, поэтому я не стану повторяться и замечу, что алгоритмы count и find используют критерий равенства, а алгоритмы binary_search, lower_bound, upper_bound и equal range основаны на критерии эквивалентности.

Присутствие величины в сортированном интервале проверяется алгоритмом binary_search. В отличие от функции bsearch из стандартной библиотеки С (а значит, и стандартной библиотеки С++), алгоритм binary_search возвращает только bool. Алгоритм отвечает на вопрос: «Присутствует ли заданное значение в интервале?», и возможны только два ответа: «да» и «нет». Если вам понадобится дополнительная информация, выберите другой алгоритм.

Пример применения binary_search к сортированному вектору (преимущества сортированных векторов описаны в совете 23):

sort (vw. Begin(),vw.end());

// Создать вектор, заполнить // данными и отсортировать

Widget w:// Искомое значение

// Значение w присутствует в vw

// Значение не найдено

Если у вас имеется сортированный интервал и вы ищете ответ на вопрос: «Присутствует ли заданное значение в интервале, и если присутствует — то где именно?», следует использовать алгоритм equal_range, хотя на первый взгляд кажется, что вам нужен алгоритм lower_bound. Вскоре мы вернемся к equal_range, а пока проанализируем поиск в интервалах с применением алгоритма lower_bound.

При поиске заданной величины в интервале алгоритм lower_bound возвращает итератор, указывающий на первый экземпляр этой величины (в случае успешного поиска) или на правильную позицию вставки (в случае неудачи). Таким образом, алгоритм lower_bound отвечает на вопрос: «Присутствует ли заданное значение в интервале? Если присутствует, то где находится первый экземпляр, а если нет — где он должен находиться?». Как и в случае с алгоритмом find, результат lower_ bound необходимо дополнительно проверить и убедиться в том, что он указывает на искомое значение. Но в отличие от find, его нельзя просто сравнить с конечным итератором. Вместо этого приходится брать объект, идентифицированный алгоритмом lower_bound, и проверять, содержит ли он искомое значение.

Многие программисты используют lower_bound примерно так:

vector ::iterator =lower_bound(vw,begin().vw.end(),w):

// на объект, и этот объект имеет искомое

// Значение найдено, i указывает на первый

// экземпляр объекта с этим значением

// Значение не найдено

В большинстве случаев такая конструкция работает, но в действительности она содержит ошибку. Присмотритесь к проверяемому условию:

В этом условии проверяется равенство, тогда как lower_bound использует при поиске критерий эквивалентности. Как правило, результаты проверки по двум критериям совпадают, но, как показано в совете 19, это не всегда так. В таких ситуациях приведенный выше фрагмент не работает.

Чтобы исправить ошибку, необходимо убедиться в том, что итератор, полученный от lower__bound, указывает на объект со значением, эквивалентным искомому. Проверку можно выполнить вручную (в совете 19 показано, как это делается, а в совете 24 приведен пример ситуации, когда такое решение оправданно), однако сделать это непросто, поскольку при этом должна использоваться та же функция сравнения, как и при вызове lower_bound. В общем случае мы имеем дело с произвольной

Читайте также:  Canon eos m10 kit отзывы профессионалов

функцией (или объектом функции). При передаче lower_bound функции сравнения эта же функция должна использоваться и в «ручной» проверке эквивалентности; следовательно, при изменении функции сравнения, передаваемой lower_rbound, вам придется внести соответствующие изменения в проверку эквивалентности. В принципе, синхронизировать функции сравнения не так уж сложно, но об этом необходимо помнить, а при программировании хлопот и без этого хватает.

Существует простое решение: воспользуйтесь алгоритмом equal_range. Алгоритм возвращает пару итераторов; первый совпадает с итератором, возвращаемым lower_bound, а второй совпадает с итератором, возвращаемым upper_bound (то есть указывает в позицию за интервалом значений, эквивалентных искомому). Таким образом, алгоритм equal_range возвращает пару итераторов, обозначающих интервал значений, эквивалентных искомому. Согласитесь, имя алгоритма выбрано довольно удачно. Возможно, правильнее было бы назвать его equvalent_range, но и equal _range воспринимается неплохо.

Относительно возвращаемого значения equal_range необходимо сделать два важных замечания. Если два итератора совпадают, это говорит о том, что интервал пуст, а значение не найдено. По этому факту можно судить о том, было ли найдено совпадение. Пример:

sort (vw.begin(), v.end());

typedef vector ::iterator VWIter; // Вспомогательные

typedef pair VWIterPair: // определения типов

VWIterPar p = equal_range(vw.begin(),vw.end(),w);

// Значение найдено, p.first

// указывает на первый элемент

// интервала, а p.second —

// на позицию за последним элементом

// Значение не найдено, p.first

// и p.second указывают на точку

// вставки искомого значения

В этом фрагменте используется только критерий эквивалентности, поэтому он всегда верен.

Другая особенность возвращаемого значения equal_range заключается в том, что расстояние между двумя итераторами равно количеству объектов в интервале, то есть количеству объектов, эквивалентных искомому объекту. В результате equal_range не только выполняет функции find для сортированных интервалов, но и заменяет count. Например, поиск в vw объектов Widget, эквивалентных w, с последующим выводом их количества может выполняться следующим образом:

VWIterPair р = equal_range(vw.begin(),vw.end(),w);

cout « "There are " « distance(p.first,p.second)

« " elements in vw equivalent to w.";

До настоящего момента предполагалось, что в интервале ищется некоторое значение, но есть ситуации, в которых возникает задача поиска граничной позиции. Предположим, у нас имеется класс Timestamp и вектор объектов Timestamp, отсортированный от «старых» объектов к «новым»:

const Timestamp& rhs); // объект lhs объекту rhs по времени

vector vt;// Создать вектор, заполнить данными

// и отсортировать так, чтобы

sort(vt.begin(),vt.end()); // "старые" объекты предшествовали "новым"

Предположим, из vt требуется удалить все объекты, предшествующие некоторому пороговому объекту ageLimit. В данном случае не нужно искать в vt объект Timestamp, эквивалентный ageLimit, поскольку объекта с точно совпадающим значением может и не быть. Вместо этого в vt ищется граничная позиция, то есть первый элемент, не старший ageLimit. Задача решается элементарно, поскольку алгоритм lowebound предоставляет всю необходимую информацию:

vt.erase(vt.begin().lower_bound(vt.begin(),// Удалить из vt все объекты,

vt.end(),// предшествующие значению

Слегка изменим условия задачи. Допустим, требуется удалить все объекты, предшествующие или равные ageLmt. Для этого необходимо найти первый объект после ageLmt. Для решения задачи идеально подходит алгоритм upper_bound:

vt.erase(vt.begin(),upper_bound(vt.begin(). // Удалить из vt все объекты,

vt.end(), // предшествующие или

Алгоритм upper_bound также часто применяется при вставке в сортированные интервалы, когда объекты с эквивалентными значениями должны следовать в контейнере в порядке вставки. Рассмотрим сортированный список объектов Person, в котором объекты сортируются по имени:

bool operator()(const Person& lhs, const Person& rhs) const

lp.sort(PersonNameLess());// Отсортировать lp по критерию

Чтобы список сортировался требуемым образом (по имени, с хранением эквивалентных имен в порядке вставки), можно воспользоваться алгоритмом upper_ bound для определения позиции вставки:

lp.insert(upper_bound(lp.begin(),// Вставить newPerson за последним

Ip.end(), // объектом lр. предшествующим

newPerson, // или эквивалентным newPerson

Приведенное решение работоспособно и достаточно удобно, но не стройте иллюзий насчет того, что оно каким-то волшебным способом обеспечивает поиск точки вставки в контейнер list с логарифмической сложностью. Как объясняется в совете 34, при работе с list поиск занимает линейное время, но при этом выполняется логарифмическое количество сравнений.

До настоящего момента рассматривался только случай, когда поиск осуществляется в интервале, определяемом парой итераторов. Довольно часто работать приходится со всем контейнером вместо интервала. В этом случае необходимо различать последовательные и ассоциативные контейнеры. Для стандартных последовательных контейнеров (vector, string, deque и list) достаточно следовать рекомендациям, изложенным ранее, используя начальный и конечный итераторы контейнера для определения интервала.

Читайте также:  Dell xps 15 i7 6700hq

Со стандартными ассоциативными контейнерами (set, multiset, map, multimap) дело обстоит иначе. В них предусмотрены функции поиска, которые по своим возможностям обычно превосходят алгоритмы STL Превосходство функций контейнеров перед алгоритмами подробно рассматривается в совете 44; если говорить кратко — они быстрее работают и ведут себя более последовательно. К счастью, имена функций обычно совпадают с именами соответствующих алгоритмов, поэтому там, где речь идет об алгоритмах count, find, lower_bound, upper_bound и equal_range, при поиске в ассоциативных контейнерах вместо них достаточно выбрать одноименную функцию. К сожалению, для алгоритма binary_search парной функции не существует. Чтобы проверить наличие значения в контейнере set или map, воспользуйтесь идиоматической ролью count как условия проверки:

set s;// Создать множество, заполнить данными

Widget w:// Искомое значение

// Эквивалентное значение не существует

При проверке присутствия значений в контейнерах multiset или multimap функция find обычно превосходит count, поскольку она останавливается при обнаружении первого объекта с искомым значением, а функция count в худшем случае просматривает все элементы контейнера.

Тем не менее при подсчете объектов в ассоциативных контейнерах count надежно занимает свою нишу. В частности, вызов count предпочтительнее вызова equal_range с последующим применением distance к полученным итераторам. Во-первых, само название функции подсказывает ее смысл — слово count означает «подсчет». Во-вторых, count упрощает работу программиста, поскольку ему не приходится создавать пару и передавать ее компоненты при вызове distance. В-третьих, count работает чуть быстрее.

Попробуем подвести итог всему, о чем говорилось в настоящем совете. Информация собрана в следующей таблице.

Алгоритм Функция контейнера
Что вы хотите узнать Несортированный интервал Сортированный интервал Для set и map Для multiset и multimap
Присутствует ли заданное значение? find binary_search count find
Присутствует ли заданное значение? И если присутствует, то где находится первый объект с этим значением? find equal_range find find или lower_bound (см. ранее)
Где находится первый объект со значением, не предшествующим заданному? find_if lower_bound lower_bound lower_bound
Где находится первый объект со значением, следующим после заданного? find_if upper_bound upper_bound upper_bound
Сколько объектов имеют count equal_range count count
заданное значение?
Где находятся все equal_range equal_range equal_ Find (итеративный вызов)
объекты с заданным range
значением?

Несколько странно выгладит частое присутствие equal_range в столбце, относящемся к сортированным интервалам. Оно связано с особой ролью проверки эквивалентности при поиске. Использование lower_bound и upper_bound чревато ошибочной проверкой равенства, а при использовании equal_range более естественно выглядит проверка эквивалентности. Во второй строке предпочтение отдается equal_range еще по одной причине: equal_range работает с логарифмическим временем, а вызов find связан с линейными затратами времени.

Для контейнеров multiset и multimap в качестве возможных кандидатов для поиска первого объекта с заданным значением указаны два алгоритма, find и lower_ bound. Обычно для решения этой задачи выбирается find — возможно, вы обратили внимание, что именно этот алгоритм указан в таблице для контейнеров set и map. Однако multi -контейнеры не гарантируют, что при наличии нескольких элементов с заданным значением find найдет первый элемент в контейнере; известно лишь то, что будет найден один из этих элементов. Если вы действительно хотите найти первый объект с заданным значением, воспользуйтесь lower_bound и выполните вручную вторую часть проверки эквивалентности, описанной в совете 19 (без этой проверки можно обойтись при помощи equal _range, но вызов equal range обходится дороже, чем вызов lower_bound).

Выбрать между count, find, binary_search, lower_bound, upper_bound и equal_range несложно. Предпочтение отдается тому алгоритму или функции, которые обладают нужными возможностями, обеспечивают нужное быстродействие и требуют минимальных усилий при вызове. Следуйте этой рекомендации (или обращайтесь к таблице), и у вас никогда не будет проблем с выбором.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *