Associative array key order

[H. S. Teoh]

On Fri, Aug 23, 2013 at 11:22:47AM -0700, Sean Kelly wrote:
> On Jul 31, 2013, at 7:55 AM, Dicebot <public at dicebot.lv> wrote:
> 
> > On Wednesday, 31 July 2013 at 14:43:21 UTC, Daniel Kozak wrote:
> >> is there a way for AA to behave same as PHP?
> > 
> > I doubt it. This snippet suggests that AA's in PHP are not simply
> > AA's and do additionally track insertion order (or use some similar
> > trick). Data in associative arrays is organized in a way that allows
> > fast key lookup and iterating in an original order requires tracking
> > extra state. Contrary to PHP, D does care about performance so I see
> > no way this can happen automatically.
> 
> This seems more likely to be a library type.  I have something like
> this that I use very frequently at work where the behavior is
> pluggable, so it can be used as a cache that automatically does
> LIFO/FIFO eviction according to an age window, number of entries, etc.
> Or none of those if all you want is a plain old hashtable.  It's not a
> tremendous amount of work to adapt an existing implementation to work
> this way.  The only annoying bit I ran into (at least with C++) is
> that the symbol lookup rules pretty much prevent overrides of existing
> functions to be mixed in via the policies.  Does alias this work
> around this problem in D?  I've never tried.

In http://d.puremagic.com/issues/show_bug.cgi?id=10733 bearophile and I
discussed code reuse between the current AA and an ordered AA
implementation. It appears that a more fundamental structure is the Set,
where the key is the value. An AA can be implemented in terms of a Set,
by making the set element a struct containing a key and value field,
with a custom toHash() and opCmp() that only hashes/compares the key
part.

By adding a pair of pointers to this customized set element, we can make
an ordered AA in terms of Set.

Plus, a Set is something that's very useful on its own as well.


T

-- 
Береги платье снову, а здоровье смолоду.