std::multimap insertion order guarantees

[Tanguy Fautré]

Hello,

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

for example:

int main()
{
std::multimap<i nt, 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.b egin(), Map.end(), std::ostream_it erator<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

[WW]

Re: std::multimap insertion order guarantees

Tanguy Fautré wrote:[color=blue]
> Hello,
>
> does std::multimap make any guarantee about the insertion order?[/color]

Not as far as I know.

--
WW aka Attila

[Mike Wahler]

Re: std::multimap insertion order guarantees

"Tanguy Fautré" <tfautre@pandor a.be> wrote in message
news:ol%fb.6023 7$Kg1.2429985@p hobos.telenet-ops.be...[color=blue]
> Hello,
>
> does std::multimap make any guarantee about the insertion order?[/color]

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.
[color=blue]
>
> for example:
>
> int main()
> {
> std::multimap<i nt, 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.b egin(), Map.end(),[/color]
std::ostream_it erator<int>(std ::cout,[color=blue]
> " "));
> }
>
>
> Will it always output 1 2 3 4 in that order?[/color]

If you fix that call to copy, yes. (multimap<int,i nt>::iterator
deref yields type 'std::pair<int, int>', not 'int')
[color=blue]
>and will equal_range(0) always
> give 1 2 3 4 too?[/color]

Yes.
[color=blue]
> Or is it platform dependent and is allowed to output 2 4 3 1 for example?[/color]

No.

-Mike

[Tanguy Fautré]

Re: std::multimap insertion order guarantees


"Mike Wahler" <mkwahler@mkwah ler.net> wrote in message
news:NI%fb.3370 $gA1.3311@newsr ead3.news.pas.e arthlink.net...[color=blue]
> "Tanguy Fautré" <tfautre@pandor a.be> wrote in message
> news:ol%fb.6023 7$Kg1.2429985@p hobos.telenet-ops.be...[color=green]
> > Hello,
> >
> > does std::multimap make any guarantee about the insertion order?[/color]
>
> 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.
>[color=green]
> >
> > for example:
> >
> > int main()
> > {
> > std::multimap<i nt, 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.b egin(), Map.end(),[/color]
> std::ostream_it erator<int>(std ::cout,[color=green]
> > " "));
> > }
> >
> >
> > Will it always output 1 2 3 4 in that order?[/color]
>
> If you fix that call to copy, yes. (multimap<int,i nt>::iterator
> deref yields type 'std::pair<int, int>', not 'int')
>[color=green]
> >and will equal_range(0) always
> > give 1 2 3 4 too?[/color]
>
> Yes.
>[color=green]
> > Or is it platform dependent and is allowed to output 2 4 3 1 for[/color][/color]
example?[color=blue]
>
> No.
>
> -Mike
>
>[/color]


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

[WW]

Re: std::multimap insertion order guarantees

Tanguy Fautré wrote:[color=blue]
> So, will the the elements with the same key keep the order they were
> inserted in or not ?[/color]

Not.

--
WW aka Attila

[Howard Hinnant]

Re: std::multimap insertion order guarantees

In article <blq029$2fr$1@p hys-news1.kolumbus. fi>,
"WW" <wolof@freemail .hu> wrote:
[color=blue]
> Tanguy Fautré wrote:[color=green]
> > Hello,
> >
> > does std::multimap make any guarantee about the insertion order?[/color]
>
> Not as far as I know.[/color]

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

[WW]

Re: std::multimap insertion order guarantees

Howard Hinnant wrote:[color=blue][color=green][color=darkred]
>>> does std::multimap make any guarantee about the insertion order?[/color]
>>
>> Not as far as I know.[/color]
>
> 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[/color]

Specific implementations are off topic in this newsgroup:

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

--
WW aka Attila

[Howard Hinnant]

Re: std::multimap insertion order guarantees

In article <blq4io$hhh$1@p hys-news1.kolumbus. fi>,
"WW" <wolof@freemail .hu> wrote:
[color=blue]
> Howard Hinnant wrote:[color=green][color=darkred]
> >>> does std::multimap make any guarantee about the insertion order?
> >>
> >> Not as far as I know.[/color]
> >
> > 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[/color]
>
> Specific implementations are off topic in this newsgroup:
>
> http://www.slack.net/~shiva/welcome.txt[/color]

Oh, sorry about that. I'll must mosey on over to the moderated
newsgroups comp.lang.c++.m oderated 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

[Attila Feher]

Re: std::multimap insertion order guarantees

Howard Hinnant wrote:[color=blue][color=green]
>> Howard Hinnant wrote:[color=darkred]
>>>>> does std::multimap make any guarantee about the insertion order?
>>>>
>>>> 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[/color]
>>
>> Specific implementations are off topic in this newsgroup:
>>
>> http://www.slack.net/~shiva/welcome.txt[/color]
>
> Oh, sorry about that. I'll must mosey on over to the moderated
> newsgroups comp.lang.c++.m oderated 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.[/color]

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.

--
Attila aka WW

[David B. Held]

Re: std::multimap insertion order guarantees

"Attila Feher" <attila.feher@l mf.ericsson.se> wrote in message
news:blqsen$5tb $1@newstree.wis e.edt.ericsson. se...[color=blue]
> Howard Hinnant wrote:[color=green]
> > [...]
> > Oh, sorry about that. I'll must mosey on over to the
> > moderated newsgroups comp.lang.c++.m oderated
> > 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.[/color][/color]

Looks like another fan, Atilla. This is what I'm talking about.
[color=blue]
> 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.[/color]

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??
[color=blue]
> 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.[/color]

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



---
Outgoing mail is certified Virus Free.
Checked by AVG anti-virus system (http://www.grisoft.com).
Version: 6.0.521 / Virus Database: 319 - Release Date: 9/23/2003

[Attila Feher]

Re: std::multimap insertion order guarantees

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.

--
Attila aka WW

[Gary Labowitz]

Re: std::multimap insertion order guarantees

"Attila Feher" <attila.feher@l mf.ericsson.se> wrote in message
news:blrcj0$fue $1@newstree.wis e.edt.ericsson. se...[color=blue]
> 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[/color]
on[color=blue]
> each post of mine.[/color]

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.
--
Gary

[David B. Held]

Re: std::multimap insertion order guarantees

"Gary Labowitz" <glabowitz@comc ast.net> wrote in message
news:dNGdnd4T0O rJ8hyiU-KYvw@comcast.co m...[color=blue]
> [...]
> 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.[/color]

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

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

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.
[color=blue]
> How long have you been in this business?[/color]

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.
[color=blue]
> Keep it up Atilla, it relieves me of having to jump in when
> the junk begins to flow.[/color]

Like now?

Dave



---
Outgoing mail is certified Virus Free.
Checked by AVG anti-virus system (http://www.grisoft.com).
Version: 6.0.521 / Virus Database: 319 - Release Date: 9/23/2003