www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - sorted associative array

reply Kay <Kay_member pathlink.com> writes:
Hi,

The D spec says: "If it(aggregation expression) is an associative array, the
order of the elements is undefined."
How can I sort an associative array so that the elements in a foreach loop are
ordered then?

-Kay
Feb 02 2005
next sibling parent reply "Regan Heath" <regan netwin.co.nz> writes:
On Thu, 3 Feb 2005 03:10:56 +0000 (UTC), Kay <Kay_member pathlink.com>  
wrote:
 The D spec says: "If it(aggregation expression) is an associative array,  
 the
 order of the elements is undefined."
 How can I sort an associative array so that the elements in a foreach  
 loop are
 ordered then?

This might do what you want: # import std.stdio; # # int main(char[][] args) { # int[char[]] AA; # char[][] tmp; # # AA["d"] = 3; # AA["f"] = 5; # AA["a"] = 0; # AA["c"] = 2; # AA["b"] = 1; # AA["e"] = 4; # # foreach(char[] key; AA.keys) # tmp ~= key; # tmp.sort; # # foreach(char[] key; tmp) # writefln(key," = ",AA[key]); # # return 0; # } Regan
Feb 02 2005
parent reply "Charles" <no email.com> writes:
I think you can skip the tmp step right, and just do

foreach (char [] key;AA.keys.sort )
{}

?

Charlie
"Regan Heath" <regan netwin.co.nz> wrote in message
news:opsllqsqna23k2f5 ally...
 On Thu, 3 Feb 2005 03:10:56 +0000 (UTC), Kay <Kay_member pathlink.com>
 wrote:
 The D spec says: "If it(aggregation expression) is an associative array,
 the
 order of the elements is undefined."
 How can I sort an associative array so that the elements in a foreach
 loop are
 ordered then?

This might do what you want: # import std.stdio; # # int main(char[][] args) { # int[char[]] AA; # char[][] tmp; # # AA["d"] = 3; # AA["f"] = 5; # AA["a"] = 0; # AA["c"] = 2; # AA["b"] = 1; # AA["e"] = 4; # # foreach(char[] key; AA.keys) # tmp ~= key; # tmp.sort; # # foreach(char[] key; tmp) # writefln(key," = ",AA[key]); # # return 0; # } Regan

Feb 02 2005
parent reply "Regan Heath" <regan netwin.co.nz> writes:
On Wed, 2 Feb 2005 22:18:23 -0600, Charles <no email.com> wrote:
 I think you can skip the tmp step right, and just do

 foreach (char [] key;AA.keys.sort )
 {}

Godd idea, you're probably right. I assume .sort returns a copy of the array?
 Charlie
 "Regan Heath" <regan netwin.co.nz> wrote in message
 news:opsllqsqna23k2f5 ally...
 On Thu, 3 Feb 2005 03:10:56 +0000 (UTC), Kay <Kay_member pathlink.com>
 wrote:
 The D spec says: "If it(aggregation expression) is an associative  

 the
 order of the elements is undefined."
 How can I sort an associative array so that the elements in a foreach
 loop are
 ordered then?

This might do what you want: # import std.stdio; # # int main(char[][] args) { # int[char[]] AA; # char[][] tmp; # # AA["d"] = 3; # AA["f"] = 5; # AA["a"] = 0; # AA["c"] = 2; # AA["b"] = 1; # AA["e"] = 4; # # foreach(char[] key; AA.keys) # tmp ~= key; # tmp.sort; # # foreach(char[] key; tmp) # writefln(key," = ",AA[key]); # # return 0; # } Regan


Feb 03 2005
parent Russ Lewis <spamhole-2001-07-16 deming-os.org> writes:
Regan Heath wrote:
 On Wed, 2 Feb 2005 22:18:23 -0600, Charles <no email.com> wrote:
 
 I think you can skip the tmp step right, and just do

 foreach (char [] key;AA.keys.sort )
 {}

Godd idea, you're probably right. I assume .sort returns a copy of the array?

No, it sorts it in place. So my preferred way of doing things is this: foreach(char[] key; AA.keys.dup.sort) { ... }
Feb 08 2005
prev sibling next sibling parent reply "Miguel Ferreira Simões" <Kobold netcabo.pt> writes:
If you want to sort the array you should follow Regean suggestion.
But if you want to preserve the insertion order, you should give a look at 
Ben Hinkle MinTL: LinkedAA container.

Miguel Ferreira Simões 
Feb 02 2005
parent "Miguel Ferreira Simões" <Kobold netcabo.pt> writes:
Give a look at MinTL there is also a SortedAA container.

Miguel 
Feb 02 2005
prev sibling next sibling parent Ben Hinkle <Ben_member pathlink.com> writes:
In article <cts4nv$1l7u$1 digitaldaemon.com>, Kay says...
Hi,

The D spec says: "If it(aggregation expression) is an associative array, the
order of the elements is undefined."
How can I sort an associative array so that the elements in a foreach loop are
ordered then?

-Kay

There is an implementation of an associative array that stores its elements in a sorted order (determined either by the natural key comparison or by a user supplied comparison or by insertion order) in the MinTL library http://home.comcast.net/~benhinkle/mintl/. In particular see the doc for SortedAA and LinkedAA: http://home.comcast.net/~benhinkle/mintl/#sortedaa and http://home.comcast.net/~benhinkle/mintl/#linkedaa. The SortedAA class uses red-black trees which is the same as most C++ implementations of a "map". I can't tell if you want to sort the items after you insert them or maintain the array in sorted order from the beginning. The MinTL arrays require you to know the order you want before you start inserting anything. good luck, -Ben
Feb 02 2005
prev sibling parent Manfred Nowak <svv1999 hotmail.com> writes:
Kay wrote: 

[...]
 How can I sort an associative array so that the elements in a
 foreach loop are ordered then?

Do you have an order at all? -manfred
Feb 06 2005