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

From: David Abrahams (david.abrahams_at_[hidden])
Date: 2002-01-09 05:44:19

----- Original Message -----
From: "corwinjoy" <cjoy_at_[hidden]>

> Actually, it was a genuine question, I wasn't 100% certain that the
> associative vector code might not have kind of smart trick I just
> missed in the indirect iterator that gave iterator stability (or
> perhaps there were good reasons why this was felt to be
> unnecessary).

Just the same reasons that nobody thinks iterator stability for regular
vectors is crucial: the price you have to pay in order to get it doesn't
make seem like a such a good deal (btw, can your iterators be dereferenced
and advanced in amortized constant time?).

> Anyway, my main goal was to discuss this as a property
> for sorted associated containers.  Obviously, the necessary
> bookkeeping adds overhead - maybe for many applications it is not
> needed

Right; I have never needed it. It's usually easy to replace uses of
iterators with uses of pointers in the indirect case, since the value_type
always contains everything you need to retrieve the iterator given the
pointer and the container in log(N) time if you /really/ need it.

> and/or perhaps this bookkeeping could be factored out of the
> container.  In other words, a container could expose two types of
> iterators: 'fast' ones that don't try to maintain iterator stability,
> and 'slower' ones that do maintain stability.  This bookkeeping would
> be a property that was independent of whether the containter held
> objects by value or by pointer to value.

I'd prefer to go further, and say that the bookkeeping iterators should only
be provided by a container adaptor as suggested by someone else. After all,
don't they increase the size of the container object? You need to save the
bookkeeping info somewhere...

-Dave