Associative array key order

[Ary Borenszweig]

On 7/31/13 12:56 PM, H. S. Teoh wrote:
> 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
>

Sorry, I meant doubly-linked list. But yeah, two pointers seem now too 
much overhead.