c++ - upper - Función<algorithm> para encontrar el último elemento menor que o igual que, lower_bound

set lower bound

Question

¿Hay alguna función que utilice la búsqueda binaria, como lower_bound pero que devuelva el último elemento menor o igual a un determinado predicado?

lower_bound se define a:

Busca la posición del primer elemento en un rango ordenado que tiene un valor mayor o equivalente a un valor especificado, donde el criterio de ordenación puede ser especificado por un predicado binario.

y upper_bound :

Busca la posición del primer elemento en un rango ordenado que tiene un valor que es mayor que un valor especificado, donde el criterio de ordenación puede ser especificado por un predicado binario.

Específicamente, tengo un contenedor de eventos ordenados por tiempo y durante un tiempo determinado quiero encontrar el último elemento que vino antes o en ese momento. ¿Puedo lograr esto con alguna combinación de límite superior / inferior, iteradores inversos y usar std::greater o std::greater_equal ?

EDITAR: Se necesitaba un ajuste a la sugerencia del usuario763305 para hacer frente si se solicita un punto antes del inicio de la matriz:

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;

Answer 1

Aquí hay una función de envoltura alrededor de upper_bound que devuelve el número más grande en un contenedor o matriz que es menor o igual a un valor dado:

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;
}

Para una mejor explicación de lo que está haciendo y cómo usar esta función, revisa:

C ++ STL: encuentra el último número menor o igual que un elemento dado en una matriz o contenedor

Answer 2

En un contenedor ordenado, el último elemento que es menor o equivalente a x , es el elemento anterior al primer elemento que es mayor que x .

Por lo tanto, puede llamar a std::upper_bound y disminuir el iterador devuelto una vez. (Antes de disminuir, debe verificar que no sea el iterador de inicio; si lo es, entonces no hay elementos que sean menores o equivalentes a x ).

Answer 3

He probado su solución de iterador inverso, es correcto.

Given v está ordenada por ''<''

Encuentra el último elemento menos que 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;

Encuentra el último elemento menos que igual a 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;

Esto es mejor que iter -= 1 versión