Map with maintained insertion order

[Jonathan M Davis]

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