Map with maintained insertion order

[Brad Anderson]

On Saturday, 24 March 2012 at 01:07:56 UTC, Jonathan M Davis 
wrote:
> On Friday, March 23, 2012 23:48:51 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.
>
> I can't think of any data structure that does that off the top 
> of my head,
> though there may very well be one. If you don't mind the extra 
> memory
> overhead, it wouldn't be all that hard to do it with multiple 
> maps wrapped
> in a single type. You could do something like
>
> class InsertedOrderMap
> {
>     string[string] _map;
>     RedBlackTree!(Tuple!(int, string), "a[0] < b[0]") 
> _insertionOrder;
>
>     ...
> }
>
> _map holds the normal map and _insertionOrder holds pairs of 
> the insertion
> ordered and the key to _map.
>
> You can then have your range iterate over _insertionOrder and 
> use the keys
> to return either the keys, values, or pairs of keys and values 
> from _map,
> depending on what you want to iterate over.
>
> That _does_ require having two data structures in one, and 
> there may a be a
> better way to do it, but just off the top of my head, that's 
> the best that I
> can come up with. I don't know how you could have a data 
> structure where
> it's efficient to index by both insertion order and key without 
> effectively
> having two data structures. But I really should go reread my 
> data structures
> books. It's been too long since I studied that stuff.
>
> - Jonathan M Davis

Ruby's Hash in 1.9 maintains insertion order.  It does it using a 
linked list between the nodes as they are created (so yes, 
essentially two data structures).

Regards,
Brad Anderson