<algorithm> функция для нахождения последнего элемента меньше или равного, например lower_bound - PullRequest
Новая
       23

<algorithm> функция для нахождения последнего элемента меньше или равного, например lower_bound

38 голосов
/ 03 апреля 2012

Существует ли функция, которая использует бинарный поиск, например lower_bound, но которая возвращает последний элемент меньше или равен в соответствии с данным предикатом?

lower_bound определяется как:

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

и upper_bound:

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

В частности, у меня есть контейнер событий, упорядоченных по времени, и в течение определенного времени я хочу найти последний элемент, который был до или в этот момент. Можно ли достичь этого с помощью некоторой комбинации верхней / нижней границы, обратных итераторов и использования std::greater или std::greater_equal?

EDIT: Нужно было настроить твик для предложения пользователя 763305, если вы попросите указать точку до начала массива: 

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;

Ответы [ 3 ]

39 голосов
/ 03 апреля 2012

В отсортированном контейнере последний элемент, который меньше или эквивалентен x, является элементом перед первым элементом, который больше x.

Таким образом, вы можете вызвать std::upper_bound и уменьшить возвращаемый итератор один раз. (Перед уменьшением необходимо, конечно, убедиться, что это не начальный итератор; если это так, то нет элементов, которые меньше или эквивалентны x.)

7 голосов
/ 15 сентября 2012

Вот функция-обертка вокруг 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;
}

Для лучшего объяснения того, что это делает и как использовать эту функцию, посмотрите:

C ++ STL - Найти последнее число, меньшее или равное данному элементу в массиве или контейнере

5 голосов
/ 08 мая 2018

Я протестировал ваше решение для обратного итератора, это правильно.

Учитывая v отсортировано по '<' </p>

Найти последний элемент меньше чем x: 

auto iter = std::upper_bound(v.rbegin(), v.rend(), x, std::greater<int>());
if(iter == v.rend())
    std::cout<<"no found";
else
    std::cout<<*iter;

Найти последний элемент меньше чем равный x: 

auto iter = std::lower_bound(v.rbegin(), v.rend(), x, std::greater<int>());
if(iter == v.rend())
    std::cout<<"no found";
else
    std::cout<<*iter;

Это лучше, чем iter -= 1 версия

...