std::map, find largest value smaller than key
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 3 of 3

Thread: std::map, find largest value smaller than key

Hybrid View

  1. #1
    Join Date
    Apr 2000
    Location
    Belgium (Europe)
    Posts
    3,782

    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.

  2. #2
    Join Date
    Jan 2006
    Location
    Singapore
    Posts
    6,250

    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?
    C + C++ Compiler: MinGW port of GCC
    Build + Version Control System: SCons + Bazaar

    Look up a C/C++ Reference and learn How To Ask Questions The Smart Way
    Kindly rate my posts if you found them useful

  3. #3
    Join Date
    Apr 2000
    Location
    Belgium (Europe)
    Posts
    3,782

    Re: std::map, find largest value smaller than key

    Quote Originally Posted by laserlight View Post
    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...

    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.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Azure Activities Information Page

Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center