AA insertion order iteration

spir denis.spir at gmail.com
Mon Feb 14 03:31:25 PST 2011


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.

Other ideas?

Thank you,
Denis
-- 
_________________
vita es estrany
spir.wikidot.com



More information about the Digitalmars-d-learn mailing list