Re: Indexed Map container

From: jbandela_at_[hidden]
Date: 2001-06-02 07:43:15

Hi David,
I would be interested in such a container. It is a nice compromise 
between vectors(constant indexing, linear insertion) and list(linear 
indexing, constant insertion) by providing both indexing and 
insertion in logarithmic time.

John R. Bandela

--- In boost_at_y..., "David B. Held" <dheld_at_c...> wrote:
> 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