C ++ STL: передача пустого контейнера в lower_bound

Question

Определено ли поведение для передачи пустого контейнера в std::lower_bound?

Я проверил cppreference.com и старую версию стандарта C ++, которую нашел в Интернете, но не смог найти определенный ответ.

В документации cppreference.com для std::deque::erase есть предложение

Итератор не должен быть разыменованным, если first==last: удаление пустогодиапазон не работает.

Я пропускаю что-то подобное для std::lower_bound и других алгоритмов.

Answer 1

std :: lower_bound отвечает на вопрос: «Где (как и непосредственно перед значением итератора) первое место, где данный элемент может быть вставлен без нарушения порядка?» Если [ first, last ) указанный диапазон пуст, единственное место для вставки чего-либо - непосредственно перед last (равно first ), так что вот что возвращает lower_bound .

Answer 2

Стандарт говорит: :

Возвращает: Самый дальний итератор i в диапазоне [first, last] такой, что для каждого итератора jв диапазоне [first, i) выполняются следующие соответствующие условия: *j < value или comp(*j, value) != false.

Сейчас:

1. Диапазон [first, last] для пустого контейнера имеетодин элемент, а именно итератор, возвращаемый его функцией-членом end().
2. i, следовательно, может быть только end().
3. Существует только один допустимый диапазон [first, i), которыйравно [end, end()).
4. Этот диапазон пуст, поскольку нет элемента, который на больше или равен , чем end() и ниже , чем end() нав то же время.

Поскольку каждого итератора нет j, я думаю, что цитируемое предложение можно переписать в:

Возвращает: Самый дальний итератор i в диапазоне [first, last].

. Это означает, что единственное i, которое может быть возвращено, это end().

Answer 3

Cppreference на возвращаемое значение std::lower_bound(first, last):

"[возвращает] Итератор, указывающий на первый элемент, который не меньше значения, или last, если такой элемент не найден .".

(выделено мной)

В пустом диапазоне, не будет элементов, удовлетворяющих критериям, поэтому будет возвращено last.

Исходя из этого, применение std::lower_bound (и аналогичных) к пустому диапазону четко определено .Он ничего не делает и возвращает last, что равно first.