Re: Indexed Map container

From: jbandela_at_[hidden]
Date: 2001-06-03 20:05:15

Actually it does not. For example, say you have the following map
(0,"a")
(1,"c")
(2,"d")

etc.

To insert "b" after a, you will have to change (1,"c") to (2,"c"), 
(2, "d") to (3,"d") etc, which takes linear time. Only after doing 
that can you add (1, "b").

If this data structure is what I think it is, it allows the insertion 
of "b" into position 1 in log n time.

--- In boost_at_y..., "David Abrahams" <abrahams_at_m...> wrote:
> ...but map<index, value> already has those properties. Doesn't 
it????
> 
> -Dave
> ----- Original Message -----
> From: <jbandela_at_u...>
> To: <boost_at_y...>
> 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