Boost logo

Boost :

From: David Abrahams (david.abrahams_at_[hidden])
Date: 2002-01-09 14:10:40


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

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

I'm not so sure. It sounds like it could be much worse than that in some
cases. For example, imagine a graph where nodes were elements of the vector
holding a reference-counted pointer to a vector of iterators (representing
the out-edges). Now construct the transitive closure (ouch!)

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

depending on the average number of duplicates, it could be as high as O(N)
in the multimap case.

> > > 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...
> >
>
> Agreed. Actually iterator stability would probably be better done as
> either a policy for the container or seperate containers.

It's too late to add policies to std::vector<> and std::deque<>, though, and
an adaptor that adds it to any random access container could be layered atop
many different containers, whereas "separate containers" could not.

-Dave


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