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;

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. — Steve Jessop, Apr 03 '12 at 08:53

Johan Råde · Accepted Answer · 2012-04-03T08:45:01.973

53

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

edited Apr 03 '12 at 08:45

answered Apr 03 '12 at 08:35

Johan Råde

20,480
21
73
110

4

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 – the_mandrill Apr 03 '12 at 08:53
2

@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 :-) – Steve Jessop Apr 03 '12 at 08:56
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 – the_mandrill Apr 03 '12 at 08:59
Yes, sorry, you did mention about begin(), I just wanted to make it explicit that you need to return end() in that particular case. – the_mandrill Apr 03 '12 at 09:18
@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()`. – Xeo Apr 03 '12 at 09:38
1

@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(); – Johan Råde Apr 03 '12 at 09:39
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. – Steve Jessop Apr 03 '12 at 09:46
@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. – Johan Råde Apr 03 '12 at 09:48
1

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 ;-) – Steve Jessop Apr 03 '12 at 09:53

jean · Answer 2 · 2018-05-08T03:24:34.540

13

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

edited May 08 '18 at 03:24

answered May 08 '18 at 03:09

jean

2,825
2
35
72

elegant solution! – cxxl Apr 18 '19 at 13:13
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. – Ajay Oct 11 '20 at 18:25

score 8 · Answer 3 · edited Jun 09 '15 at 11:46

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

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. — Richy, Mar 05 '19 at 06:26

score 2 · Answer 4 · answered Apr 28 '20 at 18:27

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

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

4 Answers4

Linked