On Fri, Mar 23, 2012 at 06:07:42PM -0700, 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. [...]
Yes there is one. It's called a B-tree. And it's probably total overkill for what you need. :-) But also, B-trees have O(log n) access time, not O(1). :-( T -- Right now I'm having amnesia and deja vu at the same time. I think I've forgotten this before.