c++ std::map get element with highest key below X?

Question

Given a C++ map (or multimap) where the key is an integer, is it possible using STL to request the range of elements whose key is the largest number below a given number?

So if I had:

map = {{1,'x'}, {2, 'g'}, {3, 'n'}, {3, 'm'}, {4, 'z'}, {5, 'a'}}

and I want to find the element(s) just before 4, it would return:

{{3, 'n'}, {3, 'm'}}

(I'm more interested in std::map but kept the question general for std::multimap too).

Answer 1

You can use lower_bound() to find the first element after the ones you want, then decrement the iterator and use equal_range() to access all the elements matching that one:

Code

#include <iostream>
#include <map>

int main()
{
   std::multimap<int, char> const
       m{{1,'x'}, {2,'g'}, {3,'n'}, {3,'m'}, {4,'z'}, {5 'a'}};

   auto i = m.lower_bound(4);
   if (i == m.begin()) {
       std::cerr << "No elements less than 4 were found\n";
   } else {
       --i;
       auto const range = m.equal_range(i->first);
       for (auto j = range.first;  j != range.second;  ++j)
           std::cout << j->first << ", " << j->second << '\n';
   }
}

Output

3, n
3, m