C++ – Returning the greatest key strictly less than the given key in a C++ Map

cstl

Is there a way the C++ STL Maps support this, since lower_bound and upper_bound on maps strictly return the value greater than the passed value.

Lower key

Use case I have a map with times as keys in a sorted manner so in a MAP

time t1   = value1
time t2   = value2
time t2.5 = value3

In this case if I pass to this MAP t2.3 then it should give me value2. Does doing a lower_bound on the map and going back one element equivalent to the "returning greatest key strictly less than given key" i.e

iterator = map.upper_bound(2.3)
and then 
iterator--;

Best Answer

Yeah, lower_bound can be used for that, i've seen it before and used it like that. 

map_type::iterator it = map.lower_bound(2.3);
if(it != map.begin()) {
    --it;
    // it now points at the right element
}

Would actually return the greatest, yet smaller (if it != map.begin() was true) one. If it was at .begin, then there is no smaller key. Nice idea from the comments is to return .end if there is no element that's less and pack this stuff into a function:

template<typename Map> typename Map::const_iterator 
greatest_less(Map const& m, typename Map::key_type const& k) {
    typename Map::const_iterator it = m.lower_bound(k);
    if(it != m.begin()) {
        return --it;
    }
    return m.end();
}

template<typename Map> typename Map::iterator 
greatest_less(Map & m, typename Map::key_type const& k) {
    typename Map::iterator it = m.lower_bound(k);
    if(it != m.begin()) {
        return --it;
    }
    return m.end();
}

The template should work for std::set too.

Related Topic