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) {
//                                    ^^^^^  ^^^^^^
  ...
}

Answer 2

The comparison function you use should be strictly less-than, not less-than-or-equal. The algorithm might fail otherwise.

For efficiency's sake you should use the member function upper_bound built into the map, rather than the one in algorithm.

If you need to account for a miss due to floating point mismatches, do it as a step after.

map<double,string>::iterator it;
it = myMap.upper_bound(15.0);
if (it != myMap.begin())
{
    map<double,string>::iterator it2 = it;
    --it2;
    if (it2->first > 15.0 - 0.001)
        it = it2;
}

Answer 3

The gte should be

bool gte (const double y, pair<double,string> x) {
    return (y-x.first)<.001;
}

because you need to switch the arguments around. This gives you the results that you want, yet it is not ideal, because the comparison function is not symmetric. Anyone reading this code would need to pay a lot of attention to what's goes on what side of the comparison to make sense of what you are doing.

Your program would be more readable if you use member functions lower_bound and upper_bound from your std::map, as opposed to range-based std::lower_bound and std::upper_bound:

firstAbove_1 = myMap.lower_bound(15.0);
firstAbove_2 = myMap.upper_bound(15.0);

Here are the results of running this:

0.23 => E
10.01 => A
14.62 => B
16.33 => C
45.23 => D
first greater than 15 is C
first greater than 15 is C

Here is a demo on ideone.

Answer 4

Your function gte is wrong. it has to be

bool gte (const double y, pair<double,string> x) {
  return (x.first-y)>.001;
}

Answer 5

First of all it's better to use map::lower_bound and map::upper_bound because they will work in O(log n) operations. Not only O(log n) comparsions.

Anyway I would use lower/upper_bound without predicate but using value (15. + .001)

Answer 6

/usr/lib/gcc/i686-pc-cygwin/3.4.4/include/c++/bits/stl_algo.h: In function `_ForwardIterator std::upper_bound(_ForwardIterator, _ForwardIterator, const _Tp&, _Compare) [with _ForwardIterator = std::_Rb_tree_iterator<std::pair<const double, std::string> >, _Tp = double, _Compare = bool (*)(std::pair<double, std::string>, double)]':
a.cpp:32:   instantiated from here
/usr/lib/gcc/i686-pc-cygwin/3.4.4/include/c++/bits/stl_algo.h:2784: error: conversion from `const double' to non-scalar type `std::pair<double, std::string>' requested

stl is a stinky hairy monster of a mess when it comes to figuring out problems.

Your problem stems from the fact that a comparator typically compares two elements of the same type, but here you are trying to use it to compare a pair<double,string> and a double. Thanks to the wonderfully magical obscurity of templates in c++, the compiler doesn't see the fact that your comparator uses two different types as a problem.

The implementation of lower_bound always passes the map element in as the first parameter and the comparison value as the right parameter, so you get away with your oddly typed comparator there. But upper_bound swaps the parameter order around, so you get this type error. It's trying to stick a double in where a pair is supposed to go.

Also, you're passing the wrong kind of comparator to upper_bound. Generally, you should be passing the same "<" comparator to both functions.

Like others said, using map::upper_bound(keytype&) is a better idea.