Re: [boost] Re: Indexed Map container

From: David Abrahams (abrahams_at_[hidden])
Date: 2001-06-02 18:12:04

...but map<index, value> already has those properties. Doesn't it????

-Dave
----- Original Message -----
From: <jbandela_at_[hidden]>
To: <boost_at_[hidden]>
Sent: Saturday, June 02, 2001 8:43 AM
Subject: [boost] Re: Indexed Map container

> 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
>
>
> To unsubscribe, send email to: <mailto:boost-unsubscribe_at_[hidden]>
>
>
> Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
>
>