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

R

reppisch

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
 
V

Victor Bazarov

reppisch said:
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
 
J

James Kanze

reppisch wrote:
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).

[...]
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?
 
V

Victor Bazarov

James said:
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).
[...]
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
 
H

Howard Hinnant

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
 
J

James Kanze

I am not sure. I'll try, though. I could be high on something, of
course.
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.
 
R

reppisch

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
 

Ask a Question

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

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,743
Messages
2,569,478
Members
44,898
Latest member
BlairH7607

Latest Threads

Top