map ordering

[Noah Roberts]

I just want to be sure my recollection is correct. I can't find this
in the standard but I believe maps are defined so that if I iterate
through one from begin() to end() the keys are always in order. Maps
are basically unstable sorted based on key right? Conceptually I could
consider it as an unstable sorted array of values linked to other
values?

I know that is what my implementation does and very likely, if it isn't
defined by the standard, my map is a binary tree that iterates
in-order. I would like to be sure that is defined by standard and not
an assumption based on most implementations.

 

[Victor Bazarov]

I just want to be sure my recollection is correct. I can't find this
in the standard but I believe maps are defined so that if I iterate
through one from begin() to end() the keys are always in order. Maps
are basically unstable sorted based on key right?

What's the term "unstable" supposed to mean here?

Maps are ordered. By key values. The ordering is "strict weak".

Conceptually I
could consider it as an unstable sorted array of values linked to
other values?

Sure. Whatever. But what's the meaning of "unstable"?

I know that is what my implementation does and very likely, if it
isn't defined by the standard, my map is a binary tree that iterates
in-order. I would like to be sure that is defined by standard and not
an assumption based on most implementations.

Get a copy of the Standard and study it. Why are you using the newsgroup
as your search engine?

V

 

[Noah Roberts]

Victor Bazarov wrote:
[snip]

Thanks for the answer; you can keep the attitude though.

 

[Victor Bazarov]

Victor Bazarov wrote:
[snip]

Thanks for the answer; you can keep the attitude though.

Aw, thank you. Very generous of you. It wasn't my intention
to part with it.

 

[Marcus Kwok]

What's the term "unstable" supposed to mean here?

Maybe he means "unstable" vs. "stable" as in the sense of std::sort()
and std::stable_sort() from <algorithm>. From _TC++PL:SE_, section
18.2:

sort(): Sort with good average efficiency
stable_sort(): Sort maintaining order of equal elements

So, unstable means that items that compare equal may get shifted around.
For example, suppose we are doing a case-insensitive comparison:

{'c', 'e', 'd', 'b', 'a', 'A'}

"unstable" sort could equally produce:

{'a', 'A', 'b', 'c', 'd', 'e'}
or
{'A', 'a', 'b', 'c', 'd', 'e'}

and may even switch between the two orderings when called multiple
times.

 

[Noah Roberts]

Maybe he means "unstable" vs. "stable" as in the sense of std::sort()
and std::stable_sort() from <algorithm>. From _TC++PL:SE_, section
18.2:

sort(): Sort with good average efficiency
stable_sort(): Sort maintaining order of equal elements

So, unstable means that items that compare equal may get shifted around.
For example, suppose we are doing a case-insensitive comparison:

{'c', 'e', 'd', 'b', 'a', 'A'}

"unstable" sort could equally produce:

{'a', 'A', 'b', 'c', 'd', 'e'}
or
{'A', 'a', 'b', 'c', 'd', 'e'}

and may even switch between the two orderings when called multiple
times.

Yes, in an unstable sort you can't depend on the ordering of two of the
same value; it may or may not swap them. Of course with a map<> this
event occuring is impossible, but with a multimap it is not; I believe
it is then ok to do whatever. I guess my qualification was unnecissary
since two key values cannot coexist in a map but whatever.

 

[Mark P]

I just want to be sure my recollection is correct. I can't find this
in the standard but I believe maps are defined so that if I iterate
through one from begin() to end() the keys are always in order. Maps
are basically unstable sorted based on key right? Conceptually I could
consider it as an unstable sorted array of values linked to other
values?

I know that is what my implementation does and very likely, if it isn't
defined by the standard, my map is a binary tree that iterates
in-order. I would like to be sure that is defined by standard and not
an assumption based on most implementations.

For a map no two keys may compare equal (where a equals b if neither a <
b nor b < a). Attempting to insert a key equal to an existing key will
not change the map. I don't think this falls under the conventional
meaning of unstable sort.

For a multimap, however, you're basically right-- keys which compare
equal may be in any order within the multimap.

Mark