std::multimap insertion order guarantees

T

Tanguy Fautré

Hello,

does std::multimap make any guarantee about the insertion order?

for example:

int main()
{
std::multimap<int, int> Map;

Map.insert(std::make_pair(0, 1));
Map.insert(std::make_pair(0, 2));
Map.insert(std::make_pair(0, 3));
Map.insert(std::make_pair(0, 4));

std::copy(Map.begin(), Map.end(), std::eek:stream_iterator<int>(std::cout,
" "));
}


Will it always output 1 2 3 4 in that order? and will equal_range(0) always
give 1 2 3 4 too?
Or is it platform dependent and is allowed to output 2 4 3 1 for example?

Thanks for your help.
Best regards,

Tanguy
 
M

Mike Wahler

Tanguy Fautré said:
Hello,

does std::multimap make any guarantee about the insertion order?

std::map and std::multimap guarantee that the dereference
of the iterator values from 'begin()' to 'end()' - 1 yield
the elements in 'key' order. For a 'multimap', the order in which
duplicate values in this sequence are retrieved is not guaranteed.
for example:

int main()
{
std::multimap<int, int> Map;

Map.insert(std::make_pair(0, 1));
Map.insert(std::make_pair(0, 2));
Map.insert(std::make_pair(0, 3));
Map.insert(std::make_pair(0, 4));

std::copy(Map.begin(), Map.end(),
std::ostream_iterator said:
" "));
}


Will it always output 1 2 3 4 in that order?

If you fix that call to copy, yes. (multimap<int,int>::iterator
deref yields type 'std::pair said:
and will equal_range(0) always
give 1 2 3 4 too?
Yes.

Or is it platform dependent and is allowed to output 2 4 3 1 for example?

No.

-Mike
 
T

Tanguy Fautré

Mike Wahler said:
std::map and std::multimap guarantee that the dereference
of the iterator values from 'begin()' to 'end()' - 1 yield
the elements in 'key' order. For a 'multimap', the order in which
duplicate values in this sequence are retrieved is not guaranteed.



If you fix that call to copy, yes. (multimap<int,int>::iterator
example?

No.

-Mike


You got me puzzled there.

You say "For a 'multimap', the order in which duplicate values in this
sequence are retrieved is not guaranteed."
but then you say that it will always output 0 1 0 2 0 3 0 4. (if I fix the
copy ;-) to print both the key and the mapped value).

So, will the the elements with the same key keep the order they were
inserted in or not ?

Best regards,

Tanguy
 
H

Howard Hinnant

WW said:
Not as far as I know.

Correct. But some vendors may go beyond the standard and provide
additional guarantees. You may decide to depend upon those guarantees
but you must understand that your code is not portable.

For example Metrowerks CodeWarrior does guarantee that the order will be
1 2 3 4. Later insertions are always placed at the end of the equal
range in this implementation, and it is a behavior we will guarantee for
future releases.

-Howard
 
H

Howard Hinnant

WW said:
Specific implementations are off topic in this newsgroup:

http://www.slack.net/~shiva/welcome.txt

Oh, sorry about that. I'll must mosey on over to the moderated
newsgroups comp.lang.c++.moderated and comp.std.c++ where such a post
would be allowed, and amazingly enough the signal to noise ratio is
soooo much higher due to the lack of so many self appointed moderators.

-Howard
 
A

Attila Feher

Howard said:
Oh, sorry about that. I'll must mosey on over to the moderated
newsgroups comp.lang.c++.moderated and comp.std.c++ where such a post
would be allowed, and amazingly enough the signal to noise ratio is
soooo much higher due to the lack of so many self appointed
moderators.

Yes. They have no self-appointed moderator. Wait! The self-appointed
moderators _made_ clcppm... Oh well. No noise there, only D marketing for
the last weeks in every topic. BTW the reason why they can afford a wider
area to cover is because of the lower noise ratio and because people rarely
post useless (implementation specific) information... and if they do, they
get pounded upon.
 
D

David B. Held

Attila Feher said:
Howard said:
[...]
Oh, sorry about that. I'll must mosey on over to the
moderated newsgroups comp.lang.c++.moderated
and comp.std.c++ where such a post would be
allowed, and amazingly enough the signal to noise
ratio is soooo much higher due to the lack of so many
self appointed moderators.

Looks like another fan, Atilla. This is what I'm talking about.
Yes. They have no self-appointed moderator. Wait! The
self-appointed moderators _made_ clcppm... Oh well. No
noise there, only D marketing for the last weeks in every
topic.

Waaah. Comparing a language that is purportedly derived
from C++ to C++ itself seems quite topical to me, as well
as to numerous individuals who are respected members
of the C++ community. Perhaps you should send a note to
the moderators insisting that your purist sensibilities be
enforced in c.l.c++.m. Isn't it enough that you get to moderate
this group? Do you really need to moderate c.l.c++.m too??
BTW the reason why they can afford a wider area to cover
is because of the lower noise ratio and because people
rarely post useless (implementation specific) information...
and if they do, they get pounded upon.

Oh, yes. It's useless to know that I can get a compiler which
provides a certain feature above and beyond standard C++.
Which is why no vendor offers such features. Your power
trips are getting increasingly annoying. You create your
own OT threads with your zealous moderation. You are
single-handedly responsible for 50% of the noise in this
NG. Most of the OT-topic posts are one-timers, like the
dude selling books. You turn it into a big thread by
discussing at length how it is off-topic. I see more posts
about moderation than I do about C++!!

If you really want to prove your point about s/n ratios,
why don't you get together with your moderator buddies
and perform an experiment, like a real computer
scientist.

For one month, don't moderate anything. Just let people
post at will. Count the number of OT posts you find,
and save the subject lines for later inspection. Then,
another month, count the OT posts "with moderation".
Include the moderating messages in the count. Compare.
Only then will you prove that pseudo-moderation has
a provably positive effect on the NG. It would be best
if you picked the months (or weeks) at random, and
didn't say which was which until the end of the experiment.

Dave
 
A

Attila Feher

David B. Held wrote:
[PERSONAL INSULTS SNIPPED]
Why don't you get a life and get off my back?

You start to be really annoying. Having spent less than 3 month in this
newsgroup but you already know everything better than anybody else.
Killfile me if you wish or find yourself another occupation than trolling on
each post of mine.
 
T

tom_usenet

Hello,

does std::multimap make any guarantee about the insertion order?

for example:

int main()
{
std::multimap<int, int> Map;

Map.insert(std::make_pair(0, 1));
Map.insert(std::make_pair(0, 2));
Map.insert(std::make_pair(0, 3));
Map.insert(std::make_pair(0, 4));

std::copy(Map.begin(), Map.end(), std::eek:stream_iterator<int>(std::cout,
" "));
}


Will it always output 1 2 3 4 in that order? and will equal_range(0) always
give 1 2 3 4 too?
Or is it platform dependent and is allowed to output 2 4 3 1 for example?

It is platform dependent. Use std::map<int, std::vector<int> > to
control ordering.

Tom
 
G

Gary Labowitz

Attila Feher said:
David B. Held wrote:
[PERSONAL INSULTS SNIPPED]
Why don't you get a life and get off my back?

You start to be really annoying. Having spent less than 3 month in this
newsgroup but you already know everything better than anybody else.
Killfile me if you wish or find yourself another occupation than trolling on
each post of mine.

Looks like it's time for a cold shower and a vote.
I vote for keeping OT posts out of the ng. The idea of "letting them in" to
see what happens is an old one, and results in killing off the ng.
I find the C++ topics here interesting, and the answers useful -- even when
they are wrong and must be corrected.

Why anyone would object to keeping the ng focused on C++ is beyond me.
How long have you been in this business?

Keep it up Atilla, it relieves me of having to jump in when the junk begins
to flow.
 
D

David B. Held

Gary Labowitz said:
[...]
Looks like it's time for a cold shower and a vote.
I vote for keeping OT posts out of the ng. The idea of
"letting them in" to see what happens is an old one, and
results in killing off the ng.

At what point in time was it tried, and for how long, so I
can go back and count the posts myself?
I find the C++ topics here interesting, and the answers
useful -- even when they are wrong and must be corrected.

It's not the C++ topics that are the problem. It's the non-C++
ones, obviously.
Why anyone would object to keeping the ng focused on
C++ is beyond me.

I would say that of the OT posts I see that get a "moderation
response", maybe less than half are obviously, unambiguously
OT. When they are, this is usually indicated by several people
responding and redirecting the poster. The rest of the "OT"
posts are almost exclusively "moderated" by Atilla, and many
of them meet with objections from other people (besides me,
even!), which means that perhaps Atilla's OT detector
sensitivity is cranked up a bit too high. I think the fact that he
objects to the way c.l.c++.m is moderated might attest to this
fact as well. I haven't seen one other person complain about
that group. Since the marginally OT posts tend to generate
longer meta-threads, I conjecture that, in fact, no moderation
will result in fewer overall posts, and definitely less noise.
How long have you been in this business?

I admit that I usually read moderated groups or groups that
don't need to be moderated, and it is precisely because
I could see a lot of noise in the general unmoderated groups.
But I was suprised to find that most of the noise was caused
by insiders, and not outsiders.
Keep it up Atilla, it relieves me of having to jump in when
the junk begins to flow.

Like now?

Dave
 

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

Forum statistics

Threads
473,757
Messages
2,569,543
Members
45,026
Latest member
camilin05

Latest Threads

Top