Re: Proposal: Sorted Vector Container

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

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

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