Map with maintained insertion order

[H. S. Teoh]

On Fri, Mar 23, 2012 at 06:33:54PM -0700, H. S. Teoh wrote:
> 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). :-(
[...]

Actually, nevermind that. B-trees are probably not what you're looking
for at all, and they aren't really suited to the task anyway (you want
to sort by insertion order, not key order).

What you *could* do is implement a hash augmented with next/prev
pointers in each slot, IOW, a linked list. The hash itself stores a
pointer to the head and tail of the list. When a new slot is created,
the tail of the list is updated to link to it. When a slot is deleted,
its neighbours are updated. This will maintain O(1) performance of the
hash.

In fact, you could use the current AA implementation if you wrap your
data in a struct that contains the extra pointers, and wrap around the
AA operations to update these pointers as needed.


T

-- 
Valentine's Day: an occasion for florists to reach into the wallets of nominal lovers in dire need of being reminded to profess their hypothetical love for their long-forgotten.