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

Question

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;

Pampa

Just a warning about using a different comparator -- you must use the same comparator (or a logically equivalent one) to the one the range was sorted with, otherwise the binary search algorithms have undefined behavior. So if you wanted to use std::greater you'd first have to either reverse the range or use a reverse iterator over it. And you can't ever use std::greater_equal as a comparator because it is not a strict weak order. – Geographer

Answer 1

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.)

Disbranch

Thanks - I should have mentioned that this is similar to what I have already, though I used lower_bound which means I had to perform more checks. Using upper_bound does simplify this somewhat. I was hoping though that an incantation such as lower_bound(rbegin(), rend(), value, std::greater()) would do what I needed in one go – Pampa

@the_mandrill: I think that works, but it returns a reverse iterator, which you'd presumably then have to convert to a normal iterator. Personally I find such conversions more confusing than decrementing an iterator would be :-) – Geographer

Hmm, just found that this isn't quite enough because it fails in the case that you are looking for a point before the start of the array. I've added the solution to the question – Pampa

Yes, sorry, you did mention about begin(), I just wanted to make it explicit that you need to return end() in that particular case. – Pampa

@Steve: Not like that's particularly complicated - return revit == rend()? end() : revit.base();. I actually find this to be clearer, since you compare if the iterator doesn't exist (off the end) with rend(). – Abjuration

@Xeo: revit will point to element the_mandrill is interested in, but revit.base() will point to the element after, so it has to be return revit == rend()? end() : --revit.base(); – Infarction

Like I said, I find it confusing. You end up with similar-looking code to doing it the way in the answer, but it's harder to convince myself whether it's correct. – Geographer

@Steve Jessop: I agree with that. It is perfectly logical, but also perfectly confusing. One of the cases where C++ is too logical for its own good. I almost never use C++ reverse iterators in production code. – Infarction

I'm happy to use them provided that I'm only using reverse iterators -- printing out a vector backwards is no problem. I try to avoid switching back and forth between reverse and normal iterators "at the same point". When absolutely necessary you can write helper functions to distinguish between the two different kinds of "at the same point" -- "inserts at the same place" vs. "dereferences to the same element". As far as I can tell, the whole system was designed by people who enjoy debugging off-by-one errors ;-) – Geographer

Answer 2

I have test your reverse iterator solution, it is correct.

Given v is sorted by '<'

Find last element less than 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;

Find last element less than equal 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;

This is better than iter -= 1 version

Keelia

elegant solution! – Misapply

It returns reverse_iterator, and if we need a normal iterator, we need to call ::base method. It will then return what normal UB/LB would return. And then need to decrement iterator by one. – Horvath

Answer 3

Here is a wrapper function around upper_bound which returns the largest number in a container or array which is less than or equal to a given value:

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

For a better explanation of what this is doing and how to use this function, check out:

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

Leeway

return NULL really does not compile. And at the end it returns --upperb or upperb - 1. This basically means the same so why not just --upperb. – Centimeter

Answer 4

std::prev: https://en.cppreference.com/w/cpp/iterator/prev

#include <iostream>
#include <map>

int main()
{
    std::map<int, char> m{{2, 'a'}, {4, 'b'}, {6, 'c'}, {8, 'd'}, {10, 'e'}};

    int num = 3;
    auto it = m.upper_bound(num);
    auto pv = std::prev(it);

    std::cout << "upper bound of " << num << ": "
        << it->first << ", " << it->second << '\n';
    std::cout << "lower than or equal of " << num << ": "
        << pv->first << ", " << pv->second << '\n';
}

Output:

upper bound of 3: 4, b
lower than or equal than 3: 2, a

Acro