is STL multimap "find" order stable?

Discussion in 'C++' started by salem.ganzhorn@gmail.com, Jun 24, 2005.

  1. Guest

    #include <map>
    #include <iostream>

    using namespace std;

    int main(
    int argc,
    const char * argv[]
    )
    {
    if( 4 != argc ) {
    cerr << "usage: " << endl
    << argv[0] << " index value1 value2" << endl;
    exit(1);
    }
    int index = atoi(argv[1]);
    int value1 = atoi(argv[2]);
    int value2 = atoi(argv[3]);
    multimap<int,int> mm;
    mm.insert( pair<int,int>(index,value1) );
    mm.insert( pair<int,int>(index,value2) );
    cout << "Am I guaranteed that " << mm.find(index)->second << " == "
    << value1 << "?" << endl;
    return 0;
    }

    I have read the STL docs and I did not see this explicitly stated.
     
    , Jun 24, 2005
    #1
    1. Advertising

  2. There's no guarantee about the order of identical keys in a multimap.
     
    James Daughtry, Jun 24, 2005
    #2
    1. Advertising

  3. Guest

    Arg... that is very unfortunate. I might actually have to write some
    code :(
    Thanks for the info.
     
    , Jun 24, 2005
    #3
  4. In article <>,
    wrote:

    > Arg... that is very unfortunate. I might actually have to write some
    > code :(
    > Thanks for the info.


    Fwiw, I'm trying to change this, at least partly:

    http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1780.html

    If accepted, you would have to use lower_bound instead of find, but
    otherwise you would be good to go. But as James said, as it stands
    today you're just out of luck as far as the standard goes.

    However the above paper contains a survey of several libraries (actually
    all of them (current versions) that I'm aware of), and they all
    implement "insert without hint" as if they were told to "insert at
    upper_bound". So from a practical standpoint you might get away with
    use of lower_bound instead of find today.

    -Howard
     
    Howard Hinnant, Jun 24, 2005
    #4
  5. Guest

    Howard, thanks so much!
    This paper does all the hard work. It is sufficient for me to know that
    current implementations are stable when inserting without hints. I will
    just add additional unit tests to be sure it doesn't bite me when
    someone changes the implementation.
    Best wishes,
    Salem
     
    , Jun 25, 2005
    #5
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Tanguy Fautré

    std::multimap insertion order guarantees

    Tanguy Fautré, Oct 5, 2003, in forum: C++
    Replies:
    13
    Views:
    834
    David B. Held
    Oct 6, 2003
  2. Pete Becker

    Re: Insertion order of multimap

    Pete Becker, Apr 3, 2004, in forum: C++
    Replies:
    0
    Views:
    411
    Pete Becker
    Apr 3, 2004
  3. John Mills
    Replies:
    7
    Views:
    4,540
    John Harrison
    Jun 23, 2004
  4. Replies:
    1
    Views:
    354
    Howard Hinnant
    Apr 17, 2006
  5. reppisch
    Replies:
    6
    Views:
    999
    reppisch
    Jun 19, 2007
Loading...

Share This Page