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 corresponding to the key if it is 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;

then 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 found 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 key items[0]=0 for default, but I know that itlow--; is not good programming. What can I do?

Hypochondriasis

Nothing wrong with decrementing the iterator (although predecrement might be microscopically faster on certain older compilers, and it would be better to check itlow->first rather than doing items.count()). Just make sure you don't decrement past the front. – Nodarse

Ok, thanks. I was not sure that item-- could do. I'm sure that the item don't decrement beyond the fist item, because I don't allow to insert a value less then 1. – Hypochondriasis

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;
  }
}

Kenosis

This doesn't seem to work if items is empty and you look for 0. Then it will seem like find() actually found an element in the map (and return 0). – Waine

How about: if (it == items.end() || it->first != value) { if (it == items.begin()) { /* not found, set empty */ } else { --it; /* found prev */ } } else { /* found exact */ }? – Waine

@Waine thank you for your comment, it's very likely that I've missed corner cases! I'll check your proposal as soon as I get home. Cheers! – Kenosis

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, and OP explained that the map is not empty and key is not less than the first element in the map. If there is a possibility that these two conditions may not be satisfied, one should handle the cases separately where map.empty() or map.upper_bound(key) == map.begin()(the latter is also true when the map is empty because map.begin() == map.end() in that case).

Gavra

Please provide additional details in your answer. As it's currently written, it's hard to understand your solution. – Grayish

+1. This gives the iterator pointing to the first element that is less than or equal to key. The exceptional case would be when the key is less than the first element, or, the map is empty. But in the OP's case, this should work, as long as the OP's original solution works. The added contents (edited by @zkoza) nicely describe this. – Allowed