Date: 2001-06-02 07:43:15
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
> 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.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk