CODEWITHSUNDEEP
javac++
John
John

Reputation: 193

Equivalent of java `TreeMap.lowerEntry` and `TreeMap.higherEntry` in C++ map?

I think C++ std::map.lower_bound equals to java's TreeMap.higherEntry. What is the equivalent of java's TreeMap.lowerEntry in C++ std::map?

Upvotes: 2

Views: 1760

Answers (1)

JSQuareD
JSQuareD

Reputation: 4776

The return value of both C++ functions is a bidirectional iterator. So, you can do this:

lowerEntry = --mymap.lower_bound(mykey);

Of course, you can only do this if mymap.lower_bound(mykey) != mymap.begin().

Note that it is crucial that you use lower_bound and not upper_bound. If you use upper_bound, you may or may not end up with a pair that has key equal to mykey.

Wrapped in a function:

template < typename Key, typename Value, typename Compare, typename Alloc >
auto lowerEntry(std::map<Key, Value, Compare, Alloc>& map, Key key) -> decltype(map.begin()) {
    auto iter = map.lower_bound(key); // find the first element to go at or after key
    if(iter == map.begin()) // all elements go after key
        return map.end(); // signals that no lowerEntry could be found
    return --iter; // pre-decrement to return an iterator to the element before iter
}

Don't mind all the template stuff - it's rather awkward.

The trailing return type (-> decltype(...)) is just to make the function signature a little more readable. If you don't have access to C++11, then you can use this as the signature instead:

typename std::map<Key, Value, Compare, Alloc>::iterator lowerEntry(std::map<Key, Value, Compare, Alloc>& map, Key key) {

Here's a link to a code snippet on Wandbox (which allows you to run it in several compilers): http://melpon.org/wandbox/permlink/slFyTXHgFzWiZEIL

Upvotes: 2

Related Questions