Re: Proposal: Sorted Vector Container

From: corwinjoy (cjoy_at_[hidden])
Date: 2002-01-09 03:59:16

--- In boost_at_y..., "David Abrahams" <david.abrahams_at_r...> wrote:
> 
> ----- Original Message -----
> From: "corwinjoy" <cjoy_at_h...>
> 
> > In the case of vec_multiset the bookkeeping that goes on behind 
the
> > scenes is primarily to make sure we maintain this 'positional
> > invariant'.  In fact, whether you are holding objects directly or
> > simply holding pointers to the underlying objects I don't see how 
one
> > can maintain the position of an iterator without using bookkeeping
> > (or an address search to find where you are) if the sorting 
container
> > is a vector (the standard containers don't have this problem as 
they
> > are using linked nodes).  Here I would be curious to understand 
how
> > the other proposed containers handle this issue.  For example in 
the
> > associative indirect vector code, I don't really see how the 
indirect
> > iterator would account for this?
> 
> The associative indirect vector offers stability of pointers and 
references.
> How does your sorted vector account for that?
> 
> I'm being facetious, of course. The answer to your question is 
simple: they
> trade iterator stability for other useful properties. However, I'm 
sure you
> already understood that, so I am wondering the purpose of your 
posting?
> 
> -Dave

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