Is std::multimap "stable" ?

Discussion in 'C++' started by melfar@gmail.com, Apr 17, 2006.

  1. Guest

    Hello.

    [lib.associative.reqmts] 9 says:

    '' The fundamental property of iterators of associative containers is
    that they iterate through the containers in the non-descending order of
    keys where non-descending is defined by the comparison that was used to
    construct them. ''

    Does it mean that if I insert values into a multimap with equal keys, I
    am guaranteed to receive them back with find() and equal_range() in the
    same order I inserted them?

    Thanks,
    melfar
    , Apr 17, 2006
    #1
    1. Advertising

  2. In article <>,
    "" <> wrote:

    > Hello.
    >
    > [lib.associative.reqmts] 9 says:
    >
    > '' The fundamental property of iterators of associative containers is
    > that they iterate through the containers in the non-descending order of
    > keys where non-descending is defined by the comparison that was used to
    > construct them. ''
    >
    > Does it mean that if I insert values into a multimap with equal keys, I
    > am guaranteed to receive them back with find() and equal_range() in the
    > same order I inserted them?
    >
    > Thanks,
    > melfar


    No, not according to the standard. However there are several issues of
    interest.

    First, see:

    http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-active.html#371

    This LWG issue is in the working draft for C++0X (voted in just two
    weeks ago). It states that once your equal keys are in the multimap,
    they won't change order as the multimap rebalances due to further
    inserts and erases. But it doesn't guarantee that the keys are placed
    in any particular order related to the order in which they were inserted.

    However, also see:

    http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-active.html#233

    and a related paper:

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

    If N1780 is accepted as the proposed resolution to 233, then your equal
    keys will be in the order you inserted them, or as otherwise directed by
    the optional "hint" parameter. That still doesn't mean that find()
    would find the keys in that order, but it does mean that equal_range,
    lower/upper_bound would find them in the expected order.

    N1780 is still controversial on the committee, but does have support.
    N1780 also points out that all existing implementations currently
    interpret "insert without hint" as "insert at upper bound" (equal keys
    will be in the order you inserted them). So there is also a second
    answer to your original question:

    Yes, all implementations will keep your inserted equal keys in the order
    you inserted them. Use lower_bound or equal_range, not find, to find
    them in that order.

    Sorry the answer is so complicated.

    -Howard
    Howard Hinnant, Apr 17, 2006
    #2
    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:
    807
    David B. Held
    Oct 6, 2003
  2. Boogie El Aceitoso

    Python's equivalent of C++ std::multimap

    Boogie El Aceitoso, Mar 5, 2004, in forum: Python
    Replies:
    2
    Views:
    1,898
    Edward C. Jones
    Mar 5, 2004
  3. Replies:
    4
    Views:
    505
  4. reppisch
    Replies:
    6
    Views:
    967
    reppisch
    Jun 19, 2007
  5. Replies:
    0
    Views:
    413
Loading...

Share This Page