Map with maintained insertion order

[Michael Rynn]

On Fri, 23 Mar 2012 23:48:51 +0100, Andrej Mitrovic wrote:

> Does someone have a map implementation that maintains the insertion
> order of the keys?
> 
> E.g.:
> 
> string[string] map;
> map["foo"] = "x";
> map["bar"] = "y";
> 
> When iterating over map keys I want to visit "foo" first, then "bar",
> and so on.

http://bazaar.launchpad.net/~michael-rynn-500/d2-xml/trunk/view/head:/alt/
arraymap.d

I took and adapted the idea from Ultimate++ library code. Ultimate++ is 
worth a try, even if it is C++.

arraymap.d implements a hashmap, that will maintain insertion order, but 
only if no deletions are made.

Each added key-value pair is appended into a separate key and values 
array.

Also maintained is an array of hash_t.

Also maintained is an array of index integers. Matching hash keys are 
related by the linked list method (no pointers).

So starting with an empty map, each insertion appends the key and value 
array storage.   But a key removal will create a hole, and the hole is 
added to the free links list.  The hash_t array points to one of the 
linked list entries which indexes the key/value array.

arraymap.d would appear to have the property, that the hash values cannot 
be mistaken as aliased pointers by the GC, because they can be stored in 
a non-scanned array.

In the same module is a template version copycat implementation of 
druntime AA, aahash.d  with some customizations that I have played around 
with, like being able to use char[] for lookups to string keys (but not 
for op_put). aahash module requires hashutil.d and blockheap.  arraymap 
requires hashutil.d


In performance tests the arraymap.d was slower than the D runtime look 
alike, but acceptable.  I think it has scope for improvement in coding 
and performance.