C++: Map, previous item of a key

Question

I have this map: map<int, int > items. Given a key, I want that this map returns the item corrisponding to the key if it present, otherwise the map returns the item with key immediately less than the given key. For example, if I have:

  items[0]=0;
  items[6]=10;
  items[15]=18;
  items[20]=22;

than for key=15, I want that the map returns item with value 18, otherwise for key=9, I want that map returns item with value 10.

I haven't find a function for this case. But I tried in this way:

itlow=items.lower_bound(key);
if(!items.count(key))
   itlow--;
return itlow->second;

This works as I want, entering in the map a min value items[0]=0 for default, but I know that itlow--; it's not good programming. How can I do? thanks all.

Answer 1

You just need to check if your itlow is already items.begin(). If it is, there's no such element in the map:

itlow=items.lower_bound(key);
if(itlow->first == key)
    return itlow->second;
else if(itlow != items.begin())
    itlow--;
    return itlow->second;
else
    throw some_exception();

Instead of throwing exception, you may return iterator, and then you can return items.end() if no such element is found.

#include <iostream>
#include <map>

using namespace std;


map<int, int>::const_iterator find(const map<int, int> &items, int value)
{
    auto itlow = items.lower_bound(value);

    if(itlow->first == value)
        return itlow;
    else if(itlow != items.cbegin())
        return --itlow;
    else 
        return items.cend();

}

int main()
{
  map<int, int> items;
          items[2]=0;
  items[6]=10;
  items[15]=18;
  items[20]=22;

  auto i = find(items, 0);
  if(i != items.cend())
  {
     cout << i->second << endl;
  }
  i = find(items, 15);
  if(i != items.cend())
  {
    cout << i->second << endl;
  }
  i = find(items, 9);
  if(i != items.cend())
  {
    cout << i->second << endl;
  }
}

Answer 2

Try this auto it = prev(map.upper_bound(key));

---

This works because map.upper_bound returns an iterator pointing to the first element that is greater than key or the past-the-end iterator when such element does not exist. Also, OP explained that map is not empty and key is greater than the first element in the map. If the latter conditions are not met, one should handle separately the case where upper_bound returns map.begin().