Re: Proposal: Sorted Vector Container

From: corwinjoy (cjoy_at_[hidden])
Date: 2002-01-08 18:44:08

--- In boost_at_y..., Carl Daniel <cpdaniel_at_p...> wrote:
> From: "corwinjoy" <cjoy_at_h...>
> 
> > The goal of the vec_multiset was to develop a vector based
> > implementation of a multimap that could be used as a substitute 
for
> > situations where multimap was employed but which would run faster 
and
> > use less memory.
> >
> > Here is a link to the docs on this submission:
> >
> > 
http://groups.yahoo.com/group/boost/files/vec_multiset/vec_multiset.ht
m
> 
> I find it disturbing that the memory occupied by vec_multiset can 
grow without bound, even if the size() of the
> container remains bounded.  One can certainly imagine a server 
application where lookup vastly outweighs inserts/erases,
> but the number of inserts/erases is nonetheless unbounded.  It'd be 
a pitty if vec_multiset (or similar) was unusable in
> such an application for this reason alone.
> 

This is true, the current implementation keeps a "change log" which 
tracks changes after the first sort so that iterators can maintain 
their invariants.  The assumption with this is that most of the data 
is applied during the construction phase with relatively few changes 
after that.  If you have a container that has a large "turnover", 
i.e. many insertions/deletions after the initial setup, likely a 
sorted vector will not be as fast as a set anyway because of the 
linear cost of insertions after the first sort.  Anyway, solutions to 
bound the size of the change log could include:

1. When it reaches a certain size, update all active iterators to the 
latest change and flush the log.

2. Only keep a change log up to a certain size, iterators with a 
version older than the size of the log could simply be invalidated. 
(Not so sure I like this option that much).