Boost logo

Boost :

From: corwinjoy (cjoy_at_[hidden])
Date: 2002-01-09 13:32:56

--- In boost_at_y..., "David Abrahams" <david.abrahams_at_r...> wrote:
> ----- Original Message -----
> From: "corwinjoy" <cjoy_at_h...>
> > Actually, it was a genuine question, I wasn't 100% certain that
> > 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
> vectors is crucial: the price you have to pay in order to get it
> make seem like a such a good deal (btw, can your iterators be
> and advanced in amortized constant time?).

The time taken to dereference an iterator is directly proportional to
the number of inserts/erase operations applied to the container after
the iterator was constructed / last dereferenced. Essentially, what
happens is the iterator has to update it's position to the latest
version and then it can be dereferenced. Updating it position
requires advancing through the change log from the iterator's current
version to the most recent change version - and then modifying the
iterator's version to be the most recent version in the change log.
So, for example if there are no changes since the iterator was
constructed there would be nothing to do and operator * can just
return vector[position]. If there have been three changes, it has to
loop through these three changes, modify it's position and then
return vector[position]. This is a 'just in time' scheme to adjust
an iterator only if it's value is needed (or it has to be advanced).
This should be 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
> always contains everything you need to retrieve the iterator given
> pointer and the container in log(N) time if you /really/ need it.

Well, assuming that you have a unique associative container it's
easy. If your value_type is not unique you would have to do
lower_bound then search for the address which I guess is still log

> > 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
> > and 'slower' ones that do maintain stability. This bookkeeping
> > 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...

Agreed. Actually iterator stability would probably be better done as
either a policy for the container or seperate containers.

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