<algorithm> función para encontrar último elemento menos-que-o-igual, como límite distinto

Question

¿Hay una función en la que utiliza la búsqueda binaria, como lower_bound pero que devuelve el elemento últimamenos-que-o-igual-a según un predicado dado?

lower_bound se define a:

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

y upper_bound:

encuentra la posición de la primera 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 por un tiempo dado quiero encontrar el último elemento que venía antes o en ese momento. ¿Puedo lograrlo con alguna combinación de límite superior/inferior, iteradores inversos y usando std::greater o std::greater_equal?

EDIT: un pellizco se necesitaba para la sugerencia de user763305 para hacer frente a si pide un punto antes del comienzo 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

En un recipiente ordenada, el último elemento que es menor o equivalente a x, es el elemento antes del primer elemento que es mayor que x.

Así puede llamar al std::upper_bound, y disminuir el iterador devuelto una vez. (Antes de decremento, debe, por supuesto, y comprueba que no está el iterador comenzar, y si lo es, entonces no hay elementos que son inferiores o equivalentes a x.)

Answer 2

Aquí es una función de envoltura alrededor de límite superior que devuelve el mayor número en un recipiente o una 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 esto está haciendo y cómo utilizar esta función, echa un vistazo a:

C++ STL — Find last number less than or equal to a given element in an array or container