Boost logo

Boost :

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

Boost list run by bdawes at, gregod at, cpdaniel at, john at