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