-
April 19th, 2013, 07:58 AM
#1
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.
Last edited by OReubens; April 19th, 2013 at 08:01 AM.
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|