473,390 Members | 1,673 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,390 software developers and data experts.

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
Jun 18 '07 #1
6 8989
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
Jun 18 '07 #2
On Jun 18, 3:09 pm, "Victor Bazarov" <v.Abaza...@comAcast.netwrote:
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: ja*********@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

Jun 18 '07 #3
James Kanze wrote:
On Jun 18, 3:09 pm, "Victor Bazarov" <v.Abaza...@comAcast.netwrote:
>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
Jun 18 '07 #4
In article <f5**********@online.de>, reppisch <sp**@reppisch.dewrote:
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
Jun 18 '07 #5
On Jun 18, 11:13 pm, "Victor Bazarov" <v.Abaza...@comAcast.netwrote:
James Kanze wrote:
On Jun 18, 3:09 pm, "Victor Bazarov" <v.Abaza...@comAcast.netwrote:
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:ja*********@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

Jun 19 '07 #6
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
Jun 19 '07 #7

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

12
by: Tanguy Fautré | last post by:
Hello, does std::multimap make any guarantee about the insertion order? for example: int main() { std::multimap<int, int> Map;
3
by: Daniel Fortin | last post by:
I was wondering if anyone had any suggestions for this problem: I would like to use a map to store separate lists. Each list can have a variable number of elements. The problem is that I would...
9
by: Dennis Jones | last post by:
Hi, Is there a way to iterate through a multimap in such a way as to encounter only the unique keys? In other words, since a multimap allows duplicate keys, I would like to iterate through the...
3
by: Przemek | last post by:
All, what is the efficient way to find all distinct keys in a multimap. I use the code template<class T1, class T2> set<T1> GetDistinctKeys(multimap<T1, T2> nMap) { T1 temp; multimap<T1,...
4
by: salem.ganzhorn | last post by:
#include <map> #include <iostream> using namespace std; int main( int argc, const char * argv ) {
1
by: placid | last post by:
Hi all, i was just wondering if i have a class class A {}; then i want to use a multimap like, multimap<string,A*> as; //can i have a pointer to a A object ? A* aa = new A();
3
by: Hai Nguyen | last post by:
Hi all I was attempting to insert multiple row by using a loop into a database.A table has 2 primary keys and one regular field (PR) (PR) ID Project Ans 1 2 a 1 ...
1
by: melfar | last post by:
Hello. 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...
1
by: ambarish.mitra | last post by:
Hi all, I have a multimap, where key is an int and the value is a class. I can insert into the multimap, but finding it difficult to retrieve the value when keys match. I can do this with...
0
by: taylorcarr | last post by:
A Canon printer is a smart device known for being advanced, efficient, and reliable. It is designed for home, office, and hybrid workspace use and can also be used for a variety of purposes. However,...
0
by: Charles Arthur | last post by:
How do i turn on java script on a villaon, callus and itel keypad mobile phone
0
by: ryjfgjl | last post by:
In our work, we often receive Excel tables with data in the same format. If we want to analyze these data, it can be difficult to analyze them because the data is spread across multiple Excel files...
0
BarryA
by: BarryA | last post by:
What are the essential steps and strategies outlined in the Data Structures and Algorithms (DSA) roadmap for aspiring data scientists? How can individuals effectively utilize this roadmap to progress...
1
by: nemocccc | last post by:
hello, everyone, I want to develop a software for my android phone for daily needs, any suggestions?
0
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However,...
0
Oralloy
by: Oralloy | last post by:
Hello folks, I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>". The problem is that using the GNU compilers,...
0
jinu1996
by: jinu1996 | last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven...
0
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.