8

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.

Guillermo Mosse
  • 462
  • 2
  • 14
vincentdj
  • 265
  • 2
  • 5
  • 16
  • 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. – Sneftel Nov 26 '13 at 11:38
  • 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. – vincentdj Nov 26 '13 at 12:24

2 Answers2

4

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;
  }
}
Nemanja Boric
  • 21,627
  • 6
  • 67
  • 91
  • 1
    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). – Vegard Oct 20 '14 at 18:37
  • How about: `if (it == items.end() || it->first != value) { if (it == items.begin()) { /* not found, set empty */ } else { --it; /* found prev */ } } else { /* found exact */ }`? – Vegard Oct 20 '14 at 18:51
  • @Vegard 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! – Nemanja Boric Oct 20 '14 at 19:02
0

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().

zkoza
  • 2,644
  • 3
  • 16
  • 24
Santander
  • 1
  • 2
    Please provide additional details in your answer. As it's currently written, it's hard to understand your solution. – Community Aug 28 '21 at 16:54