Boost logo

Boost :

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


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