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.
