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