Почему std:: set:: lower_bound (x) (эффективно) определяется как наименьшее число >= x, а не наибольшее число <= x?
Возможно, я неправильно понимаю техническое определение lower bound, но я ожидал бы, если бы у меня был набор a = { 0, 3, 4 } и вычислил a.lower_bound(2), что результатом будет 0. То есть Я ожидал бы, что std::set::lower_bound будет близок к математической концепции infimum
И все же стандартная библиотека определяет его как наибольшее число не менее (эффективно >=) x.
Каковы причины этого?
Ответы
Ответ 1
Функции "[lower|upper]_bound" предназначены для возврата места в набор, где вы можете вставить ключ, который не будет нарушать порядок набора. Поскольку итератор набора STL указывает перед следующим элементом, если lower_bound(2) возвратил итератор в 0, тогда вставка 2 нарушит порядок вашего набора, теперь он будет {2, 0, 3, 4}. Верхняя граница служит для отображения последнего места, которое вы могли бы вставить, не нарушая установленный порядок.
Это наиболее полезно, если ваш набор может содержать дубликаты ключевых записей. Рассмотрим {0, 3, 3, 4}. lower_bound(3) вернет сюда итератор: {0, *, 3, 3, 4}, а upper_bound(3) вернет его здесь: {0, 3, 3, *, 4}.
Ответ 2
Это может помочь рассмотреть поведение lower_bound и upper_bound вместе.
В STL диапазоны всегда являются закрытыми интервалами. Диапазон, разделенный двумя итераторами first и last, включает в себя все элементы между first и last, включая first и исключая last. Используя интервальную нотацию, мы будем представлять это как [first, last).
lower_bound и upper_bound определены так, что они находят диапазон элементов, которые сравниваются с указанным значением. Если вы выполняете итерацию между lower_bound(x) и upper_bound(x), вы будете перебирать все элементы, которые сравниваются с x. Если ни один элемент не равен x, то гарантируется, что lower_bound(x) == upper_bound(x).
Эта функция менее важна для std::map, которая имеет не более одного элемента для каждого ключа, но является очень полезной функцией для неспецифических ассоциативных контейнеров и для неемника std::lower_bound, который может быть использован с произвольными последовательностями отсортированные элементы.
[Обратите внимание, что если вы хотите получить как нижнюю, так и верхнюю границу, вы должны вызвать equal_range вместо этого, который возвращает оба.]
