c++stdmap

Find the Key range that exists in an `enquiring range` in std::map in C++


How do I find if I have any keys within a range . I am trying below:

The goal is to get -2 and 2 as the key boundary range (that actually exists in the map) within enquiry range [-3,3]

std::map<int, char> m{ {-2,'B'}, {1, 'C'},  {2, 'A'}};

auto itCurrent = m.lower_bound(-3);
auto itNext = m.upper_bound(-3);

auto it1 = m.lower_bound(3);
auto it2 = m.upper_bound(3);

I do get value -2 for itCurrent and itNext but why am I getting end for it1 and it2 both. I was expecting m.lower_bound(3) should return 2.


Solution

  • As you can see in the std::map::lower_bound documentation:

    Return value

    Iterator pointing to the first element that is not less than key. If no such element is found, a past-the-end iterator (see end()) is returned.

    (emphasis is mine)

    You don't have a key that is not less than 3, and therfore m.lower_bound(3) returns end().

    Similarly regarding std::map::upper_bound:

    Return value

    Iterator pointing to the first element that is greater than key. If no such element is found, past-the-end (see end()) iterator is returned.

    (emphasis is mine)

    You don't have a key that is greater than 3, and so m.upper_bound(3) returns end().

    This also makes sense for your purpose of finding elements in a range:
    All of your elements are before the end of the range (and included in it) - which is what the end() return value signifies.
    For a closed range like [-3,3], all the elements from m.lower_bound(-3), up to (but not including) m.upper_bound(3) are in the range.
    If you need the ones that are the closest to the range's borders they are:
    auto it_low = m.lower_bound(-3); and
    auto it_high = m.upper_bound(3); std::advance(it_high , -1);
    (std::advance with -1 is used to get one element before the iterator that is just after the range).