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
