обоснование для std :: lower_bound и std :: upper_bound?

std::lower_bound

Возвращает итератор, указывающий на первый элемент в диапазоне [first, last), который не меньше чем (т.е. больше или равно) значение.

std::upper_bound

Возвращает итератор, указывающий на первый элемент в диапазоне [first, last), который большая чем значение.

Таким образом, смешивая нижнюю и верхнюю границы, вы можете точно описать, где начинается ваш диапазон и где он заканчивается.

Есть ли в этом смысл??

Да.

Пример:

представьте себе вектор

std::vector<int> data = { 1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6 };

auto lower = std::lower_bound(data.begin(), data.end(), 4);

1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6
// ^ lower

auto upper = std::upper_bound(data.begin(), data.end(), 4);

1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6
// ^ upper

std::copy(lower, upper, std::ostream_iterator<int>(std::cout, " "));

принты: 4 4 4

http://en.cppreference.com/w/cpp/algorithm/lower_bound

http://en.cppreference.com/w/cpp/algorithm/upper_bound

В этом случае, я думаю, картина стоит тысячи слов. Давайте предположим, что мы используем их для поиска 2 в следующих коллекциях. Стрелки показывают, какие итераторы вернутся:

Итак, если у вас есть более одного объекта с этим значением, уже присутствующим в коллекции, lower_bound даст вам итератор, который ссылается на первый из них, и upper_bound даст итератор, который ссылается на объект сразу после последнего из них.

Это (среди прочего) делает возвращаемые итераторы пригодными для использования в качестве hint параметр для insert,

Поэтому, если вы используете их в качестве подсказки, вставляемый элемент станет новым первым элементом с этим значением (если вы использовали lower_bound) или последний элемент с этим значением (если вы использовали upper_bound). Если в коллекции ранее не было элемента с этим значением, вы все равно получите итератор, который можно использовать как hint вставить его в правильное положение в коллекции.

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

Рассмотрим последовательность

1 2 3 4 5 6 6 6 7 8 9

нижняя граница для 6 — позиция первых 6.

верхняя граница для 6 — это позиция 7.

эти позиции служат общей (начало, конец) парой, обозначающей последовательность 6 значений.

Пример:

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

auto main()
-> int
{
vector<int> v = {1, 2, 3, 4, 5, 6, 6, 6, 7, 8, 9};
auto const pos1 = lower_bound( v.begin(), v.end(), 6 );
auto const pos2 = upper_bound( v.begin(), v.end(), 6 );
for( auto it = pos1; it != pos2; ++it )
{
cout << *it;
}
cout << endl;
}

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

Думайте о возвращенном итераторе как о указывающем не на элемент * iter, а просто до этот элемент, т.е. между этот элемент и предыдущий элемент в списке, если таковой имеется. Думая об этом таким образом, контракты двух функций становятся симметричными: lower_bound находит позицию перехода из <val to> = val, и upper_bound находит позицию перехода из <= val to> val. Или, другими словами, lower_bound — это начало диапазона элементов, которые сравниваются равными val (т. Е. Диапазон, который возвращает std :: equal_range), а upper_bound — их конец.

Я хотел бы, чтобы они говорили об этом (или любой другой хороший ответ) в документах; это сделало бы это намного менее таинственным!

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

Если вы пытаетесь найти что-то в последовательности, используйте lower_bound — он будет указывать непосредственно на элемент, если он найден.

Если вы вставляете в последовательность, используйте upper_bound — сохраняет первоначальный порядок дубликатов.

Уже есть хорошие ответы о том, что std::lower_bound а также std::upper_boundявляется.

Я хотел бы ответить на ваш вопрос как их запомнить?

Это легко понять / запомнить, если мы проведем аналогию с STL begin() а также end() методы любого контейнера. begin() возвращает начальный итератор в контейнер end() возвращает итератор, который находится за пределами контейнера, и мы все знаем, насколько они полезны при итерации.

Теперь на отсортированном контейнере и заданном значении, lower_boundа также upper_bound вернет диапазон итераторов для этого значения, которое легко перебирать (как начало и конец)

Практическое использование ::

Помимо вышеупомянутого использования в отсортированном списке для доступа к диапазону для данного значения, одно из лучших применений upper_bound — это доступ к данным, имеющим отношение «многие к одному» на карте.

Например, рассмотрим следующие отношения:
1 -> a, 2 -> a, 3 -> a, 4 -> b, 5 -> c, 6 -> c, 7 -> c, 8 -> c, 9 -> c, 10 -> c

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

numeric_limits<T>::lowest() : UND
1 : a
4 : b
5 : c
11 : UND

Доступ к значениям можно получить по выражению (--map.upper_bound(val))->second,

Для значений T в диапазоне от минимального до 0 выражение будет возвращать UND,
Для значений T в диапазоне от 1 до 3 он возвращает «a» и т. Д.

Теперь представьте, что у нас есть сотни отображений данных на одно значение и сотни таких отображений.
Такой подход уменьшает размер карты и тем самым делает ее эффективной.

Для массива или вектора:

станд :: lower_bound:
Возвращает итератор, указывающий на первый элемент в диапазоне

• меньше или равно значению. (для массива или вектора в порядке убывания)
• больше или равно значению. (для массива или вектора в порядке возрастания)

станд :: upper_bound:
Возвращает итератор, указывающий на первый элемент в диапазоне

• меньше значения. (для массива или вектора в порядке убывания)

• больше значения. (для массива или вектора в порядке возрастания)