www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Associative value order

reply "Patrick" <pmeade gmail.com> writes:
I know that there is no prescribed order that the .values array 
will be sorted in, however I'm curious if the order is 
deterministic based on keys.

If I have two associative arrays with strings for keys and ints 
for values and they each have an identical set of keys, would the 
.values property return the values in the same order?
Aug 06 2014
parent reply "H. S. Teoh via Digitalmars-d-learn" <digitalmars-d-learn puremagic.com> writes:
On Wed, Aug 06, 2014 at 05:54:23PM +0000, Patrick via Digitalmars-d-learn wrote:

 I know that there is no prescribed order that the .values array will
 be sorted in, however I'm curious if the order is deterministic based
 on keys.
 
 If I have two associative arrays with strings for keys and ints for
 values and they each have an identical set of keys, would the .values
 property return the values in the same order?


In the current implementation, yes. But I think it's a bad idea to rely
on that, since a future implementation might no longer do this. (E.g.,
if we use a different hash collision resolution algorithm that is
sensitive to insertion order.)

It is probably safest to make an array of keys with .keys, and sort the
array in the order you want.


T

-- 
One Word to write them all, One Access to find them, One Excel to count
them all, And thus to Windows bind them. -- Mike Champion
Aug 06 2014
parent reply Ary Borenszweig <ary esperanto.org.ar> writes:
On 8/6/14, 2:59 PM, H. S. Teoh via Digitalmars-d-learn wrote:

 On Wed, Aug 06, 2014 at 05:54:23PM +0000, Patrick via Digitalmars-d-learn
wrote:

 I know that there is no prescribed order that the .values array will
 be sorted in, however I'm curious if the order is deterministic based
 on keys.

 If I have two associative arrays with strings for keys and ints for
 values and they each have an identical set of keys, would the .values
 property return the values in the same order?


 In the current implementation, yes. But I think it's a bad idea to rely
 on that, since a future implementation might no longer do this. (E.g.,
 if we use a different hash collision resolution algorithm that is
 sensitive to insertion order.)

 It is probably safest to make an array of keys with .keys, and sort the
 array in the order you want.


 T


Why is a dictionary something built-in the language? Can't it be some 
standard library class/struct with syntax sugar for creation? All of 
these questions about associative arrays wouldn't exist if the source 
code for these operations was available.

(it's probably available, but buried in some C++ code, I guess, on in dmd?)
Aug 06 2014
next sibling parent "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm gmx.net> writes:
On Wednesday, 6 August 2014 at 18:33:16 UTC, Ary Borenszweig 
wrote:

 On 8/6/14, 2:59 PM, H. S. Teoh via Digitalmars-d-learn wrote:

 On Wed, Aug 06, 2014 at 05:54:23PM +0000, Patrick via 
 Digitalmars-d-learn wrote:

 I know that there is no prescribed order that the .values 
 array will
 be sorted in, however I'm curious if the order is 
 deterministic based
 on keys.

 If I have two associative arrays with strings for keys and 
 ints for
 values and they each have an identical set of keys, would the 
 .values
 property return the values in the same order?


 In the current implementation, yes. But I think it's a bad 
 idea to rely
 on that, since a future implementation might no longer do 
 this. (E.g.,
 if we use a different hash collision resolution algorithm that 
 is
 sensitive to insertion order.)

 It is probably safest to make an array of keys with .keys, and 
 sort the
 array in the order you want.


 T


 Why is a dictionary something built-in the language? Can't it 
 be some standard library class/struct with syntax sugar for 
 creation? All of these questions about associative arrays 
 wouldn't exist if the source code for these operations was 
 available.

 (it's probably available, but buried in some C++ code, I guess, 
 on in dmd?)


There is ongoing work to do exactly this, see for example:
https://github.com/D-Programming-Language/druntime/pull/482#issuecomment-28486561
https://github.com/D-Programming-Language/druntime/pull/676
Aug 06 2014
prev sibling parent "H. S. Teoh via Digitalmars-d-learn" <digitalmars-d-learn puremagic.com> writes:
On Wed, Aug 06, 2014 at 03:33:15PM -0300, Ary Borenszweig via
Digitalmars-d-learn wrote:
[...]

 Why is a dictionary something built-in the language?


It's actually one of the things I really liked about D when I was first
considering it.

I hated the fact that it took until C++11 to even *get* a proper hash
table into the C++ standard, and even now, it's a royal pain in the neck
to even use them (e.g., you have to define your own hash function if you
want to use a struct as key), because the language just wasn't designed
to support them in a non-verbose, non-contorted way. In D, it Just
Works(tm). (Well, excepting the numerous AA-related bugs in D, but
that's more of a quality-of-implementation issue. The idea itself is
sound, IMO.)



 Can't it be some standard library class/struct with syntax sugar for
 creation?


That's where we hope to get to eventually. But we're not quite there
yet.



 All of these questions about associative arrays wouldn't exist if the
 source code for these operations was available.
 
 (it's probably available, but buried in some C++ code, I guess, on in
 dmd?)


It's certainly available, and it's in D, not C++:

	https://github.com/D-Programming-Language/druntime/blob/master/src/rt/aaA.d

But that's beside the point. The point is that the AA interface does not
specify the ordering of keys/values, precisely because we want to have
the flexibility of changing the implementation (e.g., if we decide to
implement a superior hash collision resolution algorithm, replace the
default hash function, etc.) without affecting user code. User code that
depends on the specifics of the current implementation are, strictly
speaking, broken, because they break the encapsulation of AA's.

People simply need to learn that AA's are *unordered*. This is D, not
PHP. If they want an ordered dictionary, they really should be using
something else instead, perhaps std.container.RedBlackTree.


T

-- 
Windows: the ultimate triumph of marketing over technology. -- Adrian von Bidder
Aug 06 2014