www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - foreach for string[string]AA

reply Anton Pastukhov <pastuhov85 gmail.com> writes:
I can't see the logic in AA foreach order. Consider this code:

```
void main() {
     string[string] test = [
         "one": "1",
         "two": "2",
         "three": "3",
         "four": "4"
     ];

     import std.stdio:writeln;

     foreach(k, v; test) {
         writeln(k);
     }
}

Output:
three
two
one
four

I was sure output should be
one
two
three
four
Feb 28 2017
next sibling parent reply ikod <geller.garry gmail.com> writes:
On Tuesday, 28 February 2017 at 15:15:00 UTC, Anton Pastukhov 
wrote:

 I can't see the logic in AA foreach order. Consider this code:

 ```
 void main() {
     string[string] test = [
         "one": "1",
         "two": "2",
         "three": "3",
         "four": "4"
     ];

     import std.stdio:writeln;

     foreach(k, v; test) {
         writeln(k);
     }
 }

 Output:
 three
 two
 one
 four

 I was sure output should be
 one
 two
 three
 four


AA implemented as hash table, so it doesn't preserve insertion 
order. You have to sort keys when you need:

import std.algorithm;
import std.stdio;
void main() {
	auto aa = ["one":1,
			   "two":2
			   ];
	foreach(k; sort(aa.keys)) {
		writeln(k);
	}
}
Feb 28 2017
parent reply bachmeier <no spam.net> writes:
On Tuesday, 28 February 2017 at 15:33:46 UTC, ikod wrote:


 AA implemented as hash table, so it doesn't preserve insertion 
 order. You have to sort keys when you need:

 import std.algorithm;
 import std.stdio;
 void main() {
 	auto aa = ["one":1,
 			   "two":2
 			   ];
 	foreach(k; sort(aa.keys)) {
 		writeln(k);
 	}
 }


That will only work if sorting recovers the insertion order. An 
easy way to save the insertion order would be to use an array of 
structs. If an associate array is really needed, you can create a 
struct that contains the associative array and a string[] holding 
the keys.
Feb 28 2017
parent Anton Pastukhov <pastuhov85 gmail.com> writes:
On Tuesday, 28 February 2017 at 15:44:46 UTC, bachmeier wrote:

 On Tuesday, 28 February 2017 at 15:33:46 UTC, ikod wrote:


 AA implemented as hash table, so it doesn't preserve insertion 
 order. You have to sort keys when you need:

 import std.algorithm;
 import std.stdio;
 void main() {
 	auto aa = ["one":1,
 			   "two":2
 			   ];
 	foreach(k; sort(aa.keys)) {
 		writeln(k);
 	}
 }


 That will only work if sorting recovers the insertion order. An 
 easy way to save the insertion order would be to use an array 
 of structs. If an associate array is really needed, you can 
 create a struct that contains the associative array and a 
 string[] holding the keys.


Thank you for quick replies. I'm used to arrays in PHP that are 
actually ordered maps, so I was expected the same from D's AAs. 
For now I'm fine with array of structs.
Feb 28 2017
prev sibling parent reply Daniel =?UTF-8?B?S296w6Fr?= via Digitalmars-d-learn writes:
V Tue, 28 Feb 2017 15:15:00 +0000
Anton Pastukhov via Digitalmars-d-learn
<digitalmars-d-learn puremagic.com> napsáno:


 I can't see the logic in AA foreach order. Consider this code:
 ...
 Output:
 three
 two
 one
 four
 
 I was sure output should be
 one
 two
 three
 four


https://forum.dlang.org/post/xbanhtkvrizyqjcibsck forum.dlang.org
Feb 28 2017
parent reply Anton Pastukhov <pastuhov85 gmail.com> writes:
On Tuesday, 28 February 2017 at 17:16:43 UTC, Daniel Kozák wrote:

 V Tue, 28 Feb 2017 15:15:00 +0000
 Anton Pastukhov via Digitalmars-d-learn
 <digitalmars-d-learn puremagic.com> napsáno:


 I can't see the logic in AA foreach order. Consider this code:
 ...
 Output:
 three
 two
 one
 four
 
 I was sure output should be
 one
 two
 three
 four


 https://forum.dlang.org/post/xbanhtkvrizyqjcibsck forum.dlang.org


Thank you for the link, it was informative reading. It's a pity 
that still there is no ordered AA at least as a library type.
Feb 28 2017
next sibling parent Minty Fresh <minty fresh.com> writes:
On Tuesday, 28 February 2017 at 18:16:45 UTC, Anton Pastukhov 
wrote:

 On Tuesday, 28 February 2017 at 17:16:43 UTC, Daniel Kozák 
 wrote:

 V Tue, 28 Feb 2017 15:15:00 +0000
 Anton Pastukhov via Digitalmars-d-learn
 <digitalmars-d-learn puremagic.com> napsáno:


 I can't see the logic in AA foreach order. Consider this code:
 ...
 Output:
 three
 two
 one
 four
 
 I was sure output should be
 one
 two
 three
 four


 https://forum.dlang.org/post/xbanhtkvrizyqjcibsck forum.dlang.org


 Thank you for the link, it was informative reading. It's a pity 
 that still there is no ordered AA at least as a library type.


Ordered AA isn't that common a use case, and it's not without 
overhead. You essentially need to store an array of keys that 
define iteration order, which requires extra memory allocations 
(and, depending on implementation, may slow down iteration as 
well).

I come from a Ruby background, so I have found key order useful 
in the past, but in most cases I probably could've gotten by just 
fine with an array or set of element pairs.

Introduction of a more convenient tuple type into D might make 
something like this easier.
Mar 01 2017
prev sibling parent reply Mike Wey <mike-wey example.com> writes:
On 02/28/2017 07:16 PM, Anton Pastukhov wrote:

 On Tuesday, 28 February 2017 at 17:16:43 UTC, Daniel Kozák wrote:

 V Tue, 28 Feb 2017 15:15:00 +0000
 Anton Pastukhov via Digitalmars-d-learn
 <digitalmars-d-learn puremagic.com> napsáno:


 I can't see the logic in AA foreach order. Consider this code:
 ...
 Output:
 three
 two
 one
 four

 I was sure output should be
 one
 two
 three
 four


 https://forum.dlang.org/post/xbanhtkvrizyqjcibsck forum.dlang.org


 Thank you for the link, it was informative reading. It's a pity that
 still there is no ordered AA at least as a library type.


I had the same use case in the generator for GtkD, i needed fast lookup 
while iteration needed to preserve the insertion order. I opted for 
storing nodes of a linked list in the build in AA.

The implementation[1] is currently LGPL to match the rest of the 
library, but if anyone would find it useful it can be changed to 
something else.

[1] 
https://github.com/gtkd-developers/GtkD/blob/master/wrap/utils/LinkedHasMap.d

-- 
Mike Wey
Mar 01 2017
parent reply Anton Pastukhov <pastuhov85 gmail.com> writes:
On Wednesday, 1 March 2017 at 19:26:23 UTC, Mike Wey wrote:

 On 02/28/2017 07:16 PM, Anton Pastukhov wrote:

 On Tuesday, 28 February 2017 at 17:16:43 UTC, Daniel Kozák 
 wrote:

 [...]


 Thank you for the link, it was informative reading. It's a 
 pity that
 still there is no ordered AA at least as a library type.


 I had the same use case in the generator for GtkD, i needed 
 fast lookup while iteration needed to preserve the insertion 
 order. I opted for storing nodes of a linked list in the build 
 in AA.

 The implementation[1] is currently LGPL to match the rest of 
 the library, but if anyone would find it useful it can be 
 changed to something else.

 [1] 
 https://github.com/gtkd-developers/GtkD/blob/master/wrap/utils/LinkedHasMap.d


Interesting.
How this approach is compared to array of tuples performance-wise?
Mar 02 2017
parent Mike Wey <mike-wey example.com> writes:
On 03/02/2017 09:09 AM, Anton Pastukhov wrote:

 On Wednesday, 1 March 2017 at 19:26:23 UTC, Mike Wey wrote:

 On 02/28/2017 07:16 PM, Anton Pastukhov wrote:

 On Tuesday, 28 February 2017 at 17:16:43 UTC, Daniel Kozák wrote:

 [...]


 Thank you for the link, it was informative reading. It's a pity that
 still there is no ordered AA at least as a library type.


 I had the same use case in the generator for GtkD, i needed fast
 lookup while iteration needed to preserve the insertion order. I opted
 for storing nodes of a linked list in the build in AA.

 The implementation[1] is currently LGPL to match the rest of the
 library, but if anyone would find it useful it can be changed to
 something else.

 [1]
 https://github.com/gtkd-developers/GtkD/blob/master/wrap/utils/LinkedHasMap.d


 Interesting.
 How this approach is compared to array of tuples performance-wise?


The biggest difference would be that you don't have to iterate the array 
to find a specific key. If you don't need to index by key i suspect a 
array of tuples is slightly faster to iterate.

-- 
Mike Wey
Mar 02 2017