the_mandrill the_mandrill - 29 days ago 12
C++ Question

<algorithm> function for finding last item less-than-or-equal to, like lower_bound

Is there a function in that uses binary search, like

lower_bound
but that returns the last item less-than-or-equal-to according to a given predicate?

lower_bound
is defined to:


Finds the position of the first element in an ordered range that has a value greater than or equivalent to a specified value, where the ordering criterion may be specified by a binary predicate.


and
upper_bound
:


Finds the position of the first element in an ordered range that has a value that is greater than a specified value, where the ordering criterion may be specified by a binary predicate.


Specifically, I have a container of time ordered events and for a given time I want to find the last item that came before or at that point. Can I achieve this with some combination of upper/lower bound, reverse iterators and using
std::greater
or
std::greater_equal
?

EDIT:
A tweak was needed to user763305's suggestion to cope with if you ask for a point before the start of the array:

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

In a sorted container, the last element that is less than or equivalent to x, is the element before the first element that is greater than x.

Thus you can call std::upper_bound, and decrement the returned iterator once. (Before decrementing, you must of course check that it is not the begin iterator; if it is, then there are no elements that are less than or equivalent to x.)