473,322 Members | 1,566 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,322 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 8976
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: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
1
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...

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.