Map with maintained insertion order

[H. S. Teoh]

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.