AA insertion order iteration
Steven Schveighoffer
schveiguy at yahoo.com
Mon Feb 14 06:27:51 PST 2011
On Mon, 14 Feb 2011 06:31:25 -0500, spir <denis.spir at gmail.com> wrote:
> Hello,
>
> How would you wrap an AA to allow memorising insertion order, and be
> able to use it
> for iteration?
>
> * Indeed, one could store keys in a // (ordered) array. But this means
> iteration requires a series of lookups by key.
> * A slightly better method would be to store hash values, which anyway
> are
> computed at insertion time, and pass them to whatever internal routine
> is used to
> fetch an item.
> * Even better, store an array of pointers to the items.
>
> Typically, items in hash tables are kinds of cells in the "bucket"
> storing
> pairs which "modulo-ed" hash values are equal. If I know the internal
> representation of such cells, then I can get (key,value) pairs. I've
> read once
> such buckets are now linked lists, which can only make things simpler.
> The issue for last 2 solutions is I need to catch some info at insertion
> time. The second one even requires calling an internal routine.
> Any chance? In any case, a pointer to current implementation of D AAs is
> welcome.
Here is the main struct which calls the implementation functions:
https://github.com/D-Programming-Language/druntime/blob/master/src/object_.d#L2461
Hopefully the functions that it calls are clues as to where to find the
implementations (all in druntime). I warn you, they are based fully on
runtime information, so they are going to be ugly.
-Steve
More information about the Digitalmars-d-learn
mailing list