<algorithm> функция поиска последнего элемента меньше или равна, например lower_bound
Есть ли функция, в которой используется двоичный поиск, например lower_bound
, но который возвращает последний элемент меньше или равный-в соответствии с заданным предикатом?
lower_bound
определяется как:
Определяет позицию первого элемента в упорядоченном диапазоне, который имеет значение, большее или эквивалентное заданному значению, где критерий упорядочения может быть задан двоичным предикатом.
и upper_bound
:
Определяет позицию первого элемента в упорядоченном диапазоне, значение которого больше заданного значения, где критерий упорядочения может быть задан двоичным предикатом.
В частности, у меня есть контейнер событий, упорядоченных по времени, и в течение определенного времени я хочу найти последний элемент, который был до или в этот момент. Могу ли я достичь этого с помощью комбинации верхних/нижних границ, обратных итераторов и используя std::greater
или std::greater_equal
?
EDIT:
Для решения user763305 необходимо было выполнить настройку, если вы попросите точку до начала массива:
iterator it=upper_bound(begin(), end(), val, LessThanFunction());
if (it!=begin()) {
it--; // not at end of array so rewind to previous item
} else {
it=end(); // no items before this point, so return end()
}
return it;
Ответы
Ответ 1
В отсортированном контейнере последний элемент, который меньше или эквивалентен x
, является элементом перед первым элементом, который больше, чем x
.
Таким образом, вы можете вызывать std::upper_bound
и декретировать возвращенный итератор один раз.
(Перед декрементацией вы должны, конечно, проверить, что это не итератор начала, а если нет, то нет элементов, которые меньше или эквивалентны x
.)
Ответ 2
Вот функция-оболочка вокруг upper_bound, которая возвращает наибольшее число в контейнере или массиве, которое меньше или равно заданному значению:
template <class ForwardIterator, class T>
ForwardIterator largest_less_than_or_equal_to ( ForwardIterator first,
ForwardIterator last,
const T& value)
{
ForwardIterator upperb = upper_bound(first, last, value);
// First element is >, so none are <=
if(upperb == first)
return NULL;
// All elements are <=, so return the largest.
if(upperb == last)
return --upperb;
return upperb - 1;
}
Для лучшего объяснения того, что это делает и как использовать эту функцию, проверьте:
С++ STL - найти последнее число, меньшее или равное заданному элементу в массиве или контейнере