Re: [boost] Re: Proposal: Sorted Vector Container

From: Carl Daniel (cpdaniel_at_[hidden])
Date: 2002-01-08 18:51:06

From: "corwinjoy" <cjoy_at_[hidden]>
> --- In boost_at_y..., Carl Daniel <cpdaniel_at_p...> wrote:
> > I find it disturbing that the memory occupied by vec_multiset can
> grow without bound, even if the size() of the
> > container remains bounded.
>
> 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:
>

Actually, in a long-running application, ANY turnover will eventually be a problem, even if it's only 0.01% of the
operations on the vec_multiset.

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

I was envisioning another approach.  If vec_multiset kept track of the "active history" (through some cooperation with
the iterator classes, of course), the history could be kept trimmed so it's never larger than necessary (perhaps then
storing it in a std::deque instead of std::vector).  This approach would eliminate the need to choose a "certain size",
would have better worst-case performance, and poorer average-case performance (I suspect).

>
> 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).

Not sure I do either.  If iterators are to remain valid after insert/erase, that guarantee shouldn't have a time limit.

-cd