std::map, find largest value smaller than key
I have a std::map<int, foo>
what's the ideal way to get an iterator to the item that has the largest key (int) smaller than a given value.
basically, the item before upper_bound(). I can use upper_bound() and then decrement, but it needs special cases for both end() and begin(), and in the case of end() I'm not sure how I get it to the last item in the map, afaik, we're not allowed to decrement end().
Code:
auto it = mymap.upper_bound(x);
if (it==mymap.begin()) // first item in the map is already too large. reject
NotFound();
else if (it==mymap.end())
{
if (mymap.empty())
NoFound();
else
it= ???; // last item in the map. what do I do here ?
}
else
--it;
// here it points to largest item smaller than x.
I can iterate over the entire map and do a compare, but then I pretty much loose the benefit of the binary search.
Re: std::map, find largest value smaller than key
Quote:
Originally Posted by OReubens
it needs special cases for both end() and begin()
I think you'll always need to consider the case where there are no keys smaller than the given one, hence you will always need to special case begin().
Quote:
Originally Posted by OReubens
in the case of end() I'm not sure how I get it to the last item in the map, afaik, we're not allowed to decrement end().
This is new to me though as I had the impression that decrementing an iterator equal to end() is allowed. Is there some part of the standard that you have in mind that could be interpreted as not allowing that?
Re: std::map, find largest value smaller than key
Quote:
Originally Posted by
laserlight
I think you'll always need to consider the case where there are no keys smaller than the given one, hence you will always need to special case begin().
Not if there was a function/algorithm that already had that baked in :)
With upper_bound() I don't need to worry about .begin() only about .end() any other return value is valid.
so I'm still curious as to whether there isn't a better way to do what I'm needing...
Quote:
This is new to me though as I had the impression that decrementing an iterator equal to end() is allowed. Is there some part of the standard that you have in mind that could be interpreted as not allowing that?
You're right. map returns a bidirectional iterator and according to the spec, for any dereferencable value, the sequence i--;i++; needs to be valid and be a nul operation for bidirectional iterators (and same with i++;i--; )
the upshot of this is that if i points to the last valid item, then i++ will be end() and decrementing again is required to give me the last valid element.
It seems it's more of a general policy over here that dates back to when we had to deal with STL implementations where decrementing end() didn't always work.
