How can I find the first element of a map where key is greater than val

Question

I have a map<double,T> (say T==string) and I wanted to find the first element of the map such that the key was greater than a given number. I looked in <algorithm> and find upper_bound and lower_bound.

Strangely I can get the first above using lower_bound but not upper_bound, what am I doing wrong?

#include <iostream>
#include <map>
#include <algorithm>
#include <string>
using namespace std;

bool lte (pair<double,string> x, const double y) {
  return (x.first-y)<.001;
}
bool gte (pair<double,string> x, const double y) {
  return (x.first-y)>.001;
}
int main()
{
    map<double,string> myMap;
    myMap[10.01] = "A";
    myMap[14.62] = "B";
    myMap[16.33] = "C";
    myMap[45.23] = "D";
    myMap[0.23] = "E";

    map<double,string>::iterator it;
    for(it = myMap.begin(); it != myMap.end() ; it++){
        cout << it->first << " => " << it->second << endl;
    }

    map<double,string>::iterator firstAbove_1;
    firstAbove_1 = lower_bound(myMap.begin(), myMap.end(), 15., lte); //
    cout << "first greater that 15 is " << firstAbove_1->second << '\n';

    //map<double,string>::iterator firstAbove_2;
    //firstAbove_2 = upper_bound (myMap.begin(), myMap.end(), 15., gte); //         ^
    //cout << "first greater that 15 is " << firstAbove_2->second << '\n';

    return 0;
}

Answer 1

IMPORTANT: This answer explains why you are getting a compilation error. However, when available, you should always prefer the member-function versions of an algorithm to the free-function version, because they offer better complexity guarantees.

Thus, use std::map::upper_bound() and std::map::lower_bound. This said, the following explains why you are getting a compile-time error.

---

The order of the arguments of sdt::lower_bound and std::upper_bound is swapped. See Paragraphs 25.4.3.1-2 of the C++11 Standard:

25.4.3.1 lower_bound [lower.bound]

 template<class ForwardIterator, class T, class Compare>
 ForwardIterator  lower_bound(
     ForwardIterator first, 
     ForwardIterator last, 
     const T& value, 
     Compare comp
     );

1 Requires: The elements e of [first,last) shall be partitioned with respect to the expression e < value or comp(e, value).

2 Returns: The furthermost iterator i in the range [first,last] such that for any iterator j in the range [first,i) the following corresponding conditions hold: *j < value or comp(*j, value) != false.

[...]

25.4.3.2 upper_bound [upper.bound]

template<class ForwardIterator, class T>
ForwardIterator upper_bound(
    ForwardIterator first, 
    ForwardIterator last,
    const T& value);
    Compare comp
    );

1 Requires: The elements e of [first,last) shall be partitioned with respect to the expression !(value < e) or !comp(value, e).

2 Returns: The furthermost iterator i in the range [first,last] such that for any iterator j in the range [first,i) the following corresponding conditions hold: !(value < *j) or comp(value, *j) == false.

[...]

You should modify your comparator function accordingly:

bool lte (pair<double, string> x, const double y) {
  ...
}

bool gte (const double y, pair<double,string> x) {
  ...
}

Also, the value_type of an std::map<A, B> is not std::pair<A, B>, but rather std::pair<A const, B>. To avoid useless conversions and copies, I suggest using the following signatures:

bool lte (pair<double const,string> const& x, double const y) {
//                    ^^^^^         ^^^^^^
  ...
}

bool gte (double const y, pair<double const, string> const& x) {
//                                    ^^^^^  ^^^^^^
  ...
}