Map with maintained insertion order

[Andrej Mitrovic]

On 3/24/12, Jonathan M Davis <jmdavisProg at gmx.com> wrote:
> I can't think of any data structure that does that off the top of my head

Java has it and they call it a LinkedHashMap:
http://docs.oracle.com/javase/1.4.2/docs/api/java/util/LinkedHashMap.html

> 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.

Yeah it's not efficient, but in my use-case I'm not looking so much
for efficiency but convenience. Sometimes I have to look up a key
based on a name to modify some values, and I have to keep the order of
the keys.