473,320 Members | 1,940 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,320 software developers and data experts.

map ordering

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.

May 23 '06 #1
6 1628
Noah Roberts wrote:
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
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask
May 23 '06 #2

Victor Bazarov wrote:
[snip]

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

May 23 '06 #3
Noah Roberts wrote:
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.
May 23 '06 #4
Victor Bazarov <v.********@comacast.net> wrote:
Noah Roberts wrote:
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?


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.

--
Marcus Kwok
Replace 'invalid' with 'net' to reply
May 23 '06 #5

Marcus Kwok wrote:
Victor Bazarov <v.********@comacast.net> wrote:
Noah Roberts wrote:
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?


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.

May 23 '06 #6
Noah Roberts wrote:
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
May 23 '06 #7

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

Similar topics

2
by: Ken Fine | last post by:
(originally posted to one of macromedia's groups; no help, so hopefully someone here can help me out. I'm using VBScript ASP.) When designing administrative interfaces to websites, we often need...
2
by: masood.iqbal | last post by:
What is the standard C/C++ lexicograhic ordering of punctuation characters with respect to each other and the alphanumeric characters? --Masood
2
by: D. Dante Lorenso | last post by:
First I created a function that selected the next available pin code from a table of pre-defined pin codes: CREATE FUNCTION "public"."get_next_pin_code" () RETURNS varchar AS' DECLARE...
2
by: Ken Durden | last post by:
Is there any way to control ordering of items in intellisense via attributes? For example, I have the following enum: public enum ESeverity { Acceptable, Low, Medium,
3
by: Ryan | last post by:
My project uses the /ORDER specifier to order functions as specified in file containing the decorated names of packaged functions (COMDATs). I am in the process of upgrading from VC6 to VC.NET 2003....
1
by: Matt Roberts | last post by:
Please accept my apologies if this is answered elsewhere in the archives or docs but I have searched without luck. I've always assumed that default ordering of selects are based on a first in...
20
by: Brian Tkatch | last post by:
An ORDER BY a simple-integer inside a FUNCTION, results in SQL0440N, unless the FUNCTION expects an INTEGER as its parameter. For example: DECLARE GLOBAL TEMPORARY TABLE A(A CHAR(1)) INSERT INTO...
33
by: Benjamin M. Stocks | last post by:
Hello all, I've heard differing opinions on this and would like a definitive answer on this once and for all. If I have an array of 4 1-byte values where index 0 is the least signficant byte of a...
23
by: illegal.prime | last post by:
Hi all, is there a key value collection in .Net that maintains the ordering in which I add items. I'm finding that I'm creating a number of classes that contain a name and then some object. I...
4
ChrisWang
by: ChrisWang | last post by:
Dear all, I am reading the book "Core Python Programming". In the chapter talking about modules, it says the modules should follow this ordering: import Python Standard Library modules ...
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: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
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)...
0
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...

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.