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

-Dave


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk