Indexed Map container

From: David B. Held (dheld_at_[hidden])
Date: 2001-06-02 01:52:08

Hi, I modified STLport's std::map implementation to create
an indexed map container that has an at() method that works
basically like std::vector's.  This gives std::imap (which is
what I have called it for now) O(log n) indexed lookup by 
adding two fields to each tree node: an index and a size.  
Updating these fields does not change the complexity cost 
of insert or delete, but may reduce their performance by up 
to a factor of 2 (this may be alleviated with some code 
optimization).

I have notified the STLport maintainers that they can include
this code with their library if they wish, but I thought that
perhaps people who don't use STLport might like to have
such a container.  It would probably be a bit of work to
make the code independent of STLport (and someone would
probably have to help me do that), but if there is some 
interest, I would be willing to put some work into it.

Dave