<algorithm> funzione per la ricerca di ultimo elemento di meno-che-o-uguale, come lower_bound

Question

C'è una funzione in che utilizza la ricerca binaria, come lower_bound ma che restituisce l'elemento ultimameno-che-o-uguale-a in base a un determinato predicato?

lower_bound è definito da:

trova la posizione del primo elemento in un intervallo ordinata che ha un valore superiore o equivalente a un valore specificato, dove può essere specificato il criterio d'ordine da un predicato binario.

e upper_bound:

trova la posizione del primo elemento in un intervallo ordinata che ha un valore che è superiore un valore specificato, in cui il criterio di ordinamento può essere specificato da un predicato binario.

In particolare, ho un contenitore di eventi ordinati nel tempo e per un determinato periodo di tempo voglio trovare l'ultimo elemento che è venuto prima o in quel punto. Posso ottenere questo risultato con una combinazione di limiti superiori/inferiori, iteratori inversi e utilizzando std::greater o std::greater_equal?

EDIT: un tweak era necessario per il suggerimento di user763305 per far fronte a se chiedete un punto prima dell'inizio della matrice:

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

In un contenitore ordinato, l'ultimo elemento che è inferiore o equivalente a x, l'elemento prima del primo elemento è maggiore di x.

In tal modo è possibile chiamare std::upper_bound e decrementare l'iteratore restituito una volta. (Prima decremento, è necessario, naturalmente, controllare che non sia l'iteratore cominciare, se lo è, allora non ci sono elementi che sono inferiori o pari a x.)

Answer 2

Ecco una funzione wrapper superiore limite che restituisce il numero più grande di un contenitore o una matrice che è inferiore o uguale a un determinato valore:

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

per una migliore spiegazione di ciò che questo sta facendo e come utilizzare questa funzione, controlla:

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