www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Map with maintained insertion order

reply Andrej Mitrovic <andrej.mitrovich gmail.com> writes:
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.
Mar 23 2012
next sibling parent Michael Rynn <michaelrynn optusnet.com.au> writes:
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.
Mar 25 2012
prev sibling parent "Richard Webb" <webby beardmouse.org.uk> writes:
I've done that in C++ before using Boost.MultiIndex, and i saw a 
post about a D port of that recently (I don't have the link to 
hand though).
Mar 26 2012