stl multimap, insert with duplicate keys, is ordering stable?

Discussion in 'C++' started by reppisch, Jun 18, 2007.

  1. reppisch

    reppisch Guest

    Hi Ng,

    I have a multiset for keeping elements sorted in a container but key
    values may also be equal.

    Is there any guaranteed traversal order within the duplicate keys of a
    multimap?
    When inserting duplicate keys to the multiset i need output order to be
    in insert order.

    Sample:
    std::multimap<int,char,std::greater<int> > m;
    m.insert(pair<int,char>(1,'a'));
    m.insert(pair<int,char>(2,'B'));
    m.insert(pair<int,char>(2,'b'));
    m.insert(pair<int,char>(2,'p'));
    m.insert(pair<int,char>(3,'c'));
    std::multimap<int,char,std::greater<int> >::iterator i = m.begin();
    while (i != m.end()) {
    cout << i->first << " " << i->second << endl;
    ++i;
    };

    - Is it guaranteed that the iteraton will allways print
    3 c
    2 B
    2 b
    2 p
    1 a

    - Can it be made deterministic by providing an insert hint like
    m.insert(m.end(),pair<int,char>(2,'b'));

    I did'nt find any information about this reading the sgi-specs.

    Regards,

    Michael
    reppisch, Jun 18, 2007
    #1
    1. Advertising

  2. reppisch wrote:
    > Hi Ng,
    >
    > I have a multiset for keeping elements sorted in a container but key
    > values may also be equal.
    >
    > Is there any guaranteed traversal order within the duplicate keys of a
    > multimap?
    > When inserting duplicate keys to the multiset i need output order to
    > be in insert order.


    That's NOT how the multiset is defined in the Standard, but I believe you
    can infer from the fact that the keys are ordered in non-descending order,
    that the order of insertion of objects with the same value is preserved.

    > Sample:
    > std::multimap<int,char,std::greater<int> > m;
    > m.insert(pair<int,char>(1,'a'));
    > m.insert(pair<int,char>(2,'B'));
    > m.insert(pair<int,char>(2,'b'));
    > m.insert(pair<int,char>(2,'p'));
    > m.insert(pair<int,char>(3,'c'));
    > std::multimap<int,char,std::greater<int> >::iterator i = m.begin();
    > while (i != m.end()) {
    > cout << i->first << " " << i->second << endl;
    > ++i;
    > };
    >
    > - Is it guaranteed that the iteraton will allways print
    > 3 c
    > 2 B
    > 2 b
    > 2 p
    > 1 a


    Not directly.

    > - Can it be made deterministic by providing an insert hint like
    > m.insert(m.end(),pair<int,char>(2,'b'));
    >
    > I did'nt find any information about this reading the sgi-specs.


    Neither did I, but I think it can be inferred from the requirements
    for the comparison object.

    V
    --
    Please remove capital 'A's when replying by e-mail
    I do not respond to top-posted replies, please don't ask
    Victor Bazarov, Jun 18, 2007
    #2
    1. Advertising

  3. reppisch

    James Kanze Guest

    Re: stl multimap, insert with duplicate keys, is ordering stable?

    On Jun 18, 3:09 pm, "Victor Bazarov" <> wrote:
    > reppisch wrote:


    > > I have a multiset for keeping elements sorted in a container but key
    > > values may also be equal.


    > > Is there any guaranteed traversal order within the duplicate keys of a
    > > multimap?
    > > When inserting duplicate keys to the multiset i need output order to
    > > be in insert order.


    > That's NOT how the multiset is defined in the Standard, but I believe you
    > can infer from the fact that the keys are ordered in non-descending order,
    > that the order of insertion of objects with the same value is preserved.


    Could you explain? I don't see any relationship (but I've not
    given the matter a lot of thought).

    [...]
    > > I did'nt find any information about this reading the sgi-specs.


    > Neither did I, but I think it can be inferred from the requirements
    > for the comparison object.


    How? Two entries are considered equal if !(a<b) && !(b<a). How
    does that affect the order between a and b if the expression is
    true?

    --
    James Kanze (Gabi Software) email:
    Conseils en informatique orientée objet/
    Beratung in objektorientierter Datenverarbeitung
    9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
    James Kanze, Jun 18, 2007
    #3
  4. Re: stl multimap, insert with duplicate keys, is ordering stable?

    James Kanze wrote:
    > On Jun 18, 3:09 pm, "Victor Bazarov" <> wrote:
    >> reppisch wrote:

    >
    >>> I have a multiset for keeping elements sorted in a container but key
    >>> values may also be equal.

    >
    >>> Is there any guaranteed traversal order within the duplicate keys
    >>> of a multimap?
    >>> When inserting duplicate keys to the multiset i need output order to
    >>> be in insert order.

    >
    >> That's NOT how the multiset is defined in the Standard, but I
    >> believe you can infer from the fact that the keys are ordered in
    >> non-descending order, that the order of insertion of objects with
    >> the same value is preserved.

    >
    > Could you explain?


    I am not sure. I'll try, though. I could be high on something, of
    course.

    > I don't see any relationship (but I've not
    > given the matter a lot of thought).


    I was thinking of the procedure required to insert a new element in
    a 'multiset'.
    With a 'multiset', how do you decide where the binary tree grows?
    You compare the value to be inserted with the value already in the
    tree, right? So, if it's less than [current value], you insert into
    the left subtree, otherwise - into the right. Iteration over those
    values first reports the elements with the same value inserted first
    (they live before in the traversal order).

    > [...]
    >>> I did'nt find any information about this reading the sgi-specs.

    >
    >> Neither did I, but I think it can be inferred from the requirements
    >> for the comparison object.

    >
    > How? Two entries are considered equal if !(a<b) && !(b<a). How
    > does that affect the order between a and b if the expression is
    > true?


    It's all in the process of insertion and how those things are stored.
    if 'a' was already there when 'b' comes it, there is an order that
    can be identified. Once they have been inserted, of course, the only
    way to preserve the order is to never change it (and there can be no
    reason to change it, can there?)

    V
    --
    Please remove capital 'A's when replying by e-mail
    I do not respond to top-posted replies, please don't ask
    Victor Bazarov, Jun 18, 2007
    #4
  5. In article <f55gii$5mu$>, reppisch <> wrote:

    > Hi Ng,
    >
    > I have a multiset for keeping elements sorted in a container but key
    > values may also be equal.
    >
    > Is there any guaranteed traversal order within the duplicate keys of a
    > multimap?
    > When inserting duplicate keys to the multiset i need output order to be
    > in insert order.
    >
    > Sample:
    > std::multimap<int,char,std::greater<int> > m;
    > m.insert(pair<int,char>(1,'a'));
    > m.insert(pair<int,char>(2,'B'));
    > m.insert(pair<int,char>(2,'b'));
    > m.insert(pair<int,char>(2,'p'));
    > m.insert(pair<int,char>(3,'c'));
    > std::multimap<int,char,std::greater<int> >::iterator i = m.begin();
    > while (i != m.end()) {
    > cout << i->first << " " << i->second << endl;
    > ++i;
    > };
    >
    > - Is it guaranteed that the iteraton will allways print
    > 3 c
    > 2 B
    > 2 b
    > 2 p
    > 1 a
    >
    > - Can it be made deterministic by providing an insert hint like
    > m.insert(m.end(),pair<int,char>(2,'b'));
    >
    > I did'nt find any information about this reading the sgi-specs.


    It is not guaranteed by the C++03 spec. However this guarantee has been
    added to the working draft of C++0X:

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

    Furthermore the associated paper:

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

    did a survey of the ordering of "insert without hint" and found:

    > That is, all existing implementations implement "insert without hint" as
    > "insert at upper bound."


    So for now you should be good to go from a practical standpoint. And
    for the future your needs will be officially recognized by the standard.

    -Howard
    Howard Hinnant, Jun 18, 2007
    #5
  6. reppisch

    James Kanze Guest

    Re: stl multimap, insert with duplicate keys, is ordering stable?

    On Jun 18, 11:13 pm, "Victor Bazarov" <> wrote:
    > James Kanze wrote:
    > > On Jun 18, 3:09 pm, "Victor Bazarov" <> wrote:
    > >> reppisch wrote:


    > >>> I have a multiset for keeping elements sorted in a container but key
    > >>> values may also be equal.


    > >>> Is there any guaranteed traversal order within the duplicate keys
    > >>> of a multimap?
    > >>> When inserting duplicate keys to the multiset i need output order to
    > >>> be in insert order.


    > >> That's NOT how the multiset is defined in the Standard, but I
    > >> believe you can infer from the fact that the keys are ordered in
    > >> non-descending order, that the order of insertion of objects with
    > >> the same value is preserved.


    > > Could you explain?


    > I am not sure. I'll try, though. I could be high on something, of
    > course.


    > > I don't see any relationship (but I've not
    > > given the matter a lot of thought).


    > I was thinking of the procedure required to insert a new element in
    > a 'multiset'.
    > With a 'multiset', how do you decide where the binary tree grows?
    > You compare the value to be inserted with the value already in the
    > tree, right? So, if it's less than [current value], you insert into
    > the left subtree, otherwise - into the right. Iteration over those
    > values first reports the elements with the same value inserted first
    > (they live before in the traversal order).


    Thanks for the explination. It sounds reasonabble, although I'm
    not sure if it is a valid argument that the current standard
    requires it, or only that you can in fact count on it because it
    is the only "reasonable" implementation. . On the other hand,
    Howard (the absolute expert in such questions) has come forward
    with the information that all implementations do in fact do it
    this way, and so the requirement is being made explicit.

    --
    James Kanze (GABI Software, from CAI) email:
    Conseils en informatique orientée objet/
    Beratung in objektorientierter Datenverarbeitung
    9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
    James Kanze, Jun 19, 2007
    #6
  7. reppisch

    reppisch Guest

    Re: stl multimap, insert with duplicate keys, is ordering stable?Tnx!

    Thank's a lot to all contributors. I think whith this statement it's clear.

    > for the future your needs will be officially recognized by the standard.



    Perfect :) That's what i wanted to hear.

    Regards,

    Michael
    reppisch, Jun 19, 2007
    #7
    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. Przemek
    Replies:
    3
    Views:
    748
    Mike Wahler
    Jan 31, 2005
  2. Replies:
    4
    Views:
    506
  3. Replies:
    1
    Views:
    331
    Howard Hinnant
    Apr 17, 2006
  4. nbigaouette

    Z-Ordering (Morton ordering) question

    nbigaouette, Nov 5, 2009, in forum: C Programming
    Replies:
    2
    Views:
    2,084
  5. Howard Hinnant
    Replies:
    1
    Views:
    361
    Howard Hinnant
    Aug 28, 2012
Loading...

Share This Page