An algorithm like lower_bound(), but another

Question

There is a upper_bound(), returns an iterator to the first element that is greater than val.

There is a lower_bound(), returns an iterator to the first element that is not less than val.

Is there an algorithm that returns an iterator to the first element that is not greater than val, or I have to reinvent the wheel?

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
int main()
{
    std::vector<int> data = { 1, 1, 2, 3, 3, 3, 3, 5, 5, 6 };

    auto lower = std::lower_bound(data.begin(), data.end(), 4, [](int x, int y) {return x > y;});

    cout << *lower ;
}

Output: 1, expexted 3

Note that another predicate like std::greater<> doesn't work.

How about using a different predicate for `lower_bound`, like `std::greater<>`? — Kerrek SB, Jan 06 '16 at 13:07
@Jarod42 `upper_bound()` works with forward iterators so in some cases that may not work — NathanOliver, Jan 06 '16 at 13:10
Possible duplicate of [ function for finding last item less-than-or-equal to, like lower\_bound](http://stackoverflow.com/questions/9989731/algorithm-function-for-finding-last-item-less-than-or-equal-to-like-lower-bou) — hlscalon, Jan 06 '16 at 13:32

score 3 · Accepted Answer · answered Jan 06 '16 at 13:32

3

Just use the predicate as in your code, but traverse it in reverse order with rbegin and rend

answered Jan 06 '16 at 13:32

Leandro T. C. Melo

3,974
22
22

Marko Tunjic · Answer 2 · 2016-01-06T17:37:50.677

My two bits, you forgot to sort in descending order.

int main()
{
    vector<int> data = { 1, 1, 2, 3, 3, 3, 3, 5, 5, 6 };

    int wanted {4};
    sort(begin(data), end(data), greater<int>());
    auto bound =  upper_bound(begin(data), end(data), wanted, greater<int>());
    cout << "val with upper_bound: " << *bound << endl;


}

result:  val with upper_bound: 3

or one step below with partition_point:

template <typename T>
struct greater_than {
    T x;
    bool operator()(const T& y) { return y > x; }
};

int main() 
{
 ...
 auto p_point = partition_point(begin(data), end(data),
                               greater_than<int>{wanted});

 cout << "val with partition_point: " << *p_point << endl;
// val with partition_point: 3

An algorithm like lower_bound(), but another

2 Answers2