Boost logo

Boost :

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
> > situations where multimap was employed but which would run faster
> > use less memory.
> >
> > Here is a link to the docs on this submission:
> >
> >
> 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).

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