Lower_bound == upper_bound

Ответ 1

• Нижняя граница: первый элемент, который больше или равен.

• Верхняя граница: первый элемент, который строго больше.

Пример:

+- lb(2) == ub(2)       +- lb(6)        +- lb(8)
|        == begin()     |  == ub(6)     |   +- ub(8) == end()
V                       V               V   V
+---+---+---+---+---+---+---+---+---+---+---+
| 3 | 4 | 4 | 4 | 4 | 5 | 7 | 7 | 7 | 7 | 8 |
+---+---+---+---+---+---+---+---+---+---+---+
    ^               ^                       ^
    |               |                       |
    +- lb(4)        +- ub(4)                +- lb(9) == ub(9) == end()

    |- eq-range(4) -|

Как вы можете видеть, полуоткрытый равный диапазон для n равен [lb (n), ub (n)).

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

void insert(Container & c, T const & t)
{
    auto it = std::lower_bound(c.begin(), c.end(), t);

    // if unique container:
    if (it != c.end() && *it == t) { /* error, element exists! */ return; }

    c.insert(it, t);
}

Ответ 2

Он возвращает итератор за последний элемент, который меньше запрашиваемого значения. Это полезно в качестве позиции вставки (и поэтому функция возвращает этот итератор). Также полезно, чтобы полуоткрытый диапазон first, lower_bound(first, last, value) указывал все значения меньше value.

upper_bound возвращает итератор за последний элемент [меньше или равно/не больше] запрашиваемого значения. Или строго: последний элемент, значение которого не меньше, поскольку оба алгоритма имеют дело исключительно с менее чем компараторами.

Если вам нужен итератор перед итератором, возвращаемым lower_bound, вы можете вычесть 1 (для итератора произвольного доступа), декремент (для двунаправленного итератора) или выполнить линейный поиск вместо использования lower_bound (для итератор, который не является ни одним из них).

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

Ответ 3

Так как это было открыто, я попытаюсь ответить на мой комментарий.

Имя lower_bound является математически неправильным. Лучшее имя может быть least_upper_bound, но это, вероятно, смутило бы большинство не-математически мыслящих людей. (И тогда, что вы называете upper_bound? almost_least_upper_bound? Yech!)

Мой совет: ознакомьтесь с тем, что имена lower_bound и upper_bound технически неверны. Две функции, как они определены, весьма полезны. Подумайте об этих функциях как о полезном использовании нотации.

Чтобы создать математически корректную функцию lower_bound, которая соответствует концепции итератора С++, функция должна была бы вернуть обратный итератор, а не прямой итератор. Возвращение обратного итератора не так полезно, как подход, который может быть ошибочно обозначен lower_bound и upper_bound, а концепция возврата обратного итератора исходит из того, что не все контейнеры обратимы.

Почему обратный итератор? Так же, как нет гарантии, что верхняя граница существует в контейнере, аналогично не гарантирует, что нижняя граница будет существовать. Существующие lower_bound и upper_bound возвращают end(), чтобы указать, что искомое значение неактивное. Истинная нижняя граница должна вернуть rend(), чтобы указать, что искомое значение неактивное.

Существует способ реализовать истинную нижнюю грань в виде форвардного итератора, но он стоит за цену, злоупотребляя значением end(), чтобы означать, что "нет нижней границы". Проблема с этим злоупотреблением нотацией заключается в том, что некоторый пользователь функции может сделать что-то эквивалентное true_lower_bound(off_scale_low_search_value)-1 и voila! у одного есть указатель на самый большой элемент в наборе.

Итак, вот как это сделать. Вернуть функцию нижней нижней границы end(), если контейнер пуст или если искомое значение меньше первого значения в контейнере. В противном случае верните upper_bound()-1.

Ответ 4

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

1, 2, 3, 4, 4, 4, 5, 6, 7

В этом случае при поиске значения 4, lower_bound вернет итератор, указывающий на первый из трех элементов со значением 4, upper_bound вернет итератор, указывающий на элемент со значением 5, и equal_range вернет пару, содержащую эти два итератора.

Ответ 5

Auch!

Вы изменили исходный код или это ошибка копирования-вставки там с первого дня?

float operator()(double f)
{
    SpectrumPoint* l=std::lower_bound//...
...
    SpectrumPoint* u=std::lower_bound//...
...
}

В коде, который я прочитал сегодня, вы назначаете lower_bound как "l", так и "u".

Ответ 6

После ответа Дэвида Хаммена я попытался объяснить, почему мы часто не считаем имена lower_bound/upper_bound правильными или, по крайней мере, интуитивными.

Это потому, что мы ищем элемент сразу ниже, чем запрос. Я сделал рисунок и пример использования:

Код:

template< typename T, typename U >
auto infimum(std::map<T,U> const& ctr, T query)
{
    auto it = ctr.upper_bound(query);
    return it == ctr.begin() ? ctr.cend() : --it;
}

template< typename T, typename U >
bool is_in_interval(std::map<T,U> const& ctr, T query)
{
    auto inf = infimum(ctr, query);
    return inf == ctr.end() ? false : query <= inf->second;
}

https://ideone.com/jM8pt3

В основном, чтобы получить поведение "серых стрелок", нам нужно upper_bound - 1 поэтому это странно.

Позвольте мне перефразировать это немного: от имени lower_bound мы инстинктивно ожидаем returns-first-immediately-inferior-element lower_bound returns-first-immediately-inferior-element lower_bound (например, серые стрелки). Но мы получаем returns-first-immediately-superior-element return returns-first-immediately-superior-element for для lower_bound; и first-immediately-strictly-superior-element для upper_bound. Вот что удивительно.

Удивительно, что вы работаете с редкой последовательностью, подобной моему мысленному эксперименту на картинке выше. Но это имеет прекрасный смысл, когда вы думаете об этом в терминах "границ equal_range " в плотной последовательности, населенной плато, как красиво изображенный Керрек С.Б.

Тестовый код:

#include <map>
#include <cassert>
#include <iostream>

// .. paste infimum and is_in_interval here

int main()
{
    using std::cout;
    using Map = std::map<int,int>;
    Map intervals{{2,5}, {8,9}};

    auto red = infimum(intervals, 4);
    assert(red->first == 2);
    cout << "red->first " << red->first << "\n";

    auto green = infimum(intervals, 6);
    assert(green->first == 2);
    cout << "green->first " << green->first << "\n";

    auto pink = infimum(intervals, 8);
    assert(pink->first == 8);
    cout << "pink->first " << pink->first << "\n";

    auto yellow = infimum(intervals, 1);
    assert(yellow == intervals.cend());

    auto larger_than_all = infimum(intervals, 15);
    assert(larger_than_all->first == 8);

    bool red_is = is_in_interval(intervals, 4);
    cout << "red is in " << red_is << "\n";

    bool green_is = is_in_interval(intervals, 6);
    cout << "green is in " << green_is << "\n";

    bool pink_is = is_in_interval(intervals, 8);
    cout << "pink is in " << pink_is << "\n";

    bool yellow_is = is_in_interval(intervals, 1);
    cout << "yellow is in " << yellow_is << "\n";
}

результаты в

red->first 2
green->first 2
pink->first 8
red is in 1
green is in 0
pink is in 1
yellow is in 0

кажется в порядке.

Поэтому, конечно, служебные функции не очень хороши, они должны быть разработаны с использованием API диапазона, чтобы мы могли работать с любым набором или поддиапазоном, или обратными итераторами, или отфильтрованными представлениями и так далее. Мы можем получить это, когда у нас есть С++ 20. Тем временем я только что сделал простой обучающий API для создания карт.

играть с этим:
https://ideone.com/jM8pt3

Ответ 7

Другим использованием lower_bound и upper_bound является поиск диапазона равных элементов в контейнере, например.

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);
auto upper = std::upper_bound(lower, data.end(), 4);

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