Верхние / нижние границы не работают, как я ожидаю, не могу понять, почему

Question

Верхние / нижние границы не работают, как я ожидаю, не могу понять, почему

Вот код В результате я получаю «4 4». Не понимаю, почему это не «2 4» (согласно определениям нижней и верхней границ).

#include <bits/stdc++.h>
using namespace std;
int main()
{
vector<int> v = {1, 2, 4, 5};
vector<int>::iterator s , f;
s = lower_bound(v.begin(), v.end(), 3);
f = upper_bound(v.begin(), v.end(), 3);
cout << (*s) << " " << (*f);
return 0;
}

2

c++lower-bound upperbound

Решение

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

Было бы легче понять / запомнить, что std::lower_bound() а также std::upper_bound() вернуться, зная, что std::equal_range() возвращает пару итераторов, где первый равен тому, что std::lower_bound() возвращается, а второй равен тому, что std::upper_bound() возвращается.

Итак, вот разные случаи, когда они вызываются с параметром 4:

1 2 3 4 4 4 4 5 E
|       |
F       S    - first points to the first element, second to the one behind last, representing range which contains 4

1 2 3 4 5 E
| |
F S  same for one element

1 2 3 4 E
| |
F S  same as before, but 4 is the last element

1 2 3 5 E
|
F==S  first == second, which means range for elements equal to 4 is empty

1 2 3 E
|
F==S same as before but there is no element greater than 4

куда E что означает container.end() возвращает — итератор за последним элементом.

4

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

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

2

Источник

Accepted Answer

От std::lower_bound:

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

Первый элемент (от начала вектора), который не меньше 3 является 4 и поэтому lower_bound возвращается 4,

От std::upper_bound:

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

Первый элемент (от начала вектора), который больше, чем 3 является 4 и поэтому upper_bound возвращается 4,

Причина этой путаницы в том, что upper_bound возвращает первый элемент, который больше заданного значения, поэтому по симметрии мы ожидаем lower_bound вернуть последний элемент (от начала вектора), который меньше заданного значения. Но увы std функция не подчиняется этой «ожидаемой» симметрии.

5