Get the key equal (if key exists in the map) or strictly less than given input in a map

Question

I am taking numberOfItems number of keys as input and putting them in a map like this:

int numberOfItems;
int query;
scanf("%d",&numberOfItems);
int temp;
map<int,int> iimap;
for(int i=0;i<numberOfItems;i++)
{
    scanf("%d",&temp);
    iimap.insert(make_pair(temp,1));
}
printf("Enter query: ");
scanf("%d",&query);
int VstrictlyLessOrEqual = FstrictlyLessOrEqual(query);

I set the default key for each input = 1; So, the non-existent key has value =0 .

6 100 5 4 3 2 1 50

For this input (the first input 6 is numberOfItems & the last input 50 is query) FstrictlyLessOrEqual() should return value 5

Answer 1

You want to use std::map's upper_bound() or lower_bound() method :

upper_bound()

upper_bound() returns an iterator to the first key that's higher than the key searched for. So:

1. Call upper_bound().

2. If upper_bound() returned begin() this means that the searched for is lower than the lowest key in the map.

3. Otherwise decrement the iterator. It will now point to a key either equal to the key searched for, or the next smaller key.

lower_bound()

lower_bound() returns an iterator to the first key in the map that's equal or greater than the key searched for, so to accomplish your goals you will need to:

1. Call lower_bound()

2. Check if lower_bound() did not return end(), and the iterator's key is the same key you searched for. The key exists in the map.

3. Otherwise, check if lower_bound() returned the map's begin() iterator value. If so, this means that the key you searched for is lower than the first key in the map, and so such value exists.

4. Otherwise, decrement the returned iterator. The key you searched for does not exist in the map, and the decremented iterator points to a key that's the next smallest in the map.

Answer 2

If the the default ordering (std::less) of keys is not a requirement, then using std::greater as key_compare with a single lower_bound() call would do the trick.

// std::greater instead of default std::less
std::map<int, int, std::greater<int>> m = {{3, 0}, {5, 0}, {7, 0}, {9, 0}};

auto it = m.lower_bound(1);
printf("%d\n", it != m.end() ? it->first : -1); // prints -1
it = m.lower_bound(3);
printf("%d\n", it != m.end() ? it->first : -1); // prints 3
it = m.lower_bound(4);
printf("%d\n", it != m.end() ? it->first : -1); // also prints 3

Answer 3

Return an iterator to the last element whose key is < key. If no such element is found, the past-the-end iterator is returned.

template <typename C>
typename C::const_iterator
find_key_less(const C& c, const typename C::key_type& key)
{
    auto iter = c.lower_bound(key);
    if (iter == c.cbegin())
        return c.cend();
    return --iter;
}

Return an iterator to the last element whose key is <= key. If no such element is found, the past-the-end iterator is returned.

template <typename C>
typename C::const_iterator
find_key_less_equal(const C& c, const typename C::key_type& key)
{
    auto iter = c.upper_bound(key);
    if (iter == c.cbegin())
        return c.cend();
    return --iter;
}

find_key_greater_equal == lower_bound

find_key_greater == upper_bound