Вот код В результате я получаю «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;
}
От std::lower_bound
:
Возвращает итератор, указывающий на первый элемент в диапазоне
[первый Последний) который не сравнивает меньше чем вал.
Первый элемент (от начала вектора), который не меньше 3
является 4
и поэтому lower_bound
возвращается 4
,
От std::upper_bound
:
Возвращает итератор, указывающий на первый элемент в диапазоне [первый Последний) который сравнивает больше чем вал.
Первый элемент (от начала вектора), который больше, чем 3
является 4
и поэтому upper_bound
возвращается 4
,
Причина этой путаницы в том, что upper_bound
возвращает первый элемент, который больше заданного значения, поэтому по симметрии мы ожидаем lower_bound
вернуть последний элемент (от начала вектора), который меньше заданного значения. Но увы std
функция не подчиняется этой «ожидаемой» симметрии.
Было бы легче понять / запомнить, что 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()
возвращает — итератор за последним элементом.
Наименование lower_bound
а также upper_bound
К сожалению, это вызывает путаницу. Имена относятся к результатам при поиске в последовательности, содержащей несколько элементов, которые в точности эквивалентны тому, который вы ищете; lower_bound
возвращает итератор в начало и upper_bound
возвращает один за концом.
Когда элемент не является частью последовательности, они и то и другое верните итератор к первому элементу, большему, чем тот, который вы искали. Это может быть end
итератор, если нет больше.