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

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

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

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

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

On Jun 18, 3:09 pm, "Victor Bazarov" <v.Abaza...@comAcast.net> 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: james.kanze@gmail.com
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

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

James Kanze wrote:
> On Jun 18, 3:09 pm, "Victor Bazarov" <v.Abaza...@comAcast.net> 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

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

In article <f55gii$5mu$1@online.de>, reppisch <spam@reppisch.de> 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/wg...fects.html#233

Furthermore the associated paper:

http://www.open-std.org/jtc1/sc22/wg...005/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

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

On Jun 18, 11:13 pm, "Victor Bazarov" <v.Abaza...@comAcast.net> wrote:
> James Kanze wrote:
> > On Jun 18, 3:09 pm, "Victor Bazarov" <v.Abaza...@comAcast.net> 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:james.kanze@gmail.com
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

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