Associative array key order

H. S. Teoh hsteoh at quickfur.ath.cx
Wed Jul 31 08:56:54 PDT 2013


On Wed, Jul 31, 2013 at 12:51:25PM -0300, Ary Borenszweig wrote:
> On 7/31/13 12:05 PM, bearophile wrote:
> >Daniel Kozak:
> >
> >> is there a way for AA to behave same as PHP?
> >
> >D associative arrays are based on hashing, so they do not keep the
> >order of the items. This is true in Python too. The Python standard
> >library has a hash-based ordered dict that keeps the insertion order
> >of the keys. There is no such data structure in Phobos.
> 
> However in Ruby 1.9 they are ordered.
> 
> You only need to store in each bucket entry a pointer to the next
> bucket. Then traversing the hash is super fast (just follow the
> links) while preserving insertion order. Accessing by key still uses
> the buckets and entries (if that's how AAs are implemented in D).
> 
> I don't think adding a pointer to each bucket entry hurts
> performance that much, and having traversal by insertion order is
> pretty common (in my opinion).
[...]

It does. What do you do when you delete entries?


T

-- 
Windows 95 was a joke, and Windows 98 was the punchline.


More information about the Digitalmars-d-learn mailing list