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
> > 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
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
> > > 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.
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.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk