Re: Proposal: Sorted Vector Container

From: corwinjoy (cjoy_at_[hidden])
Date: 2002-01-14 02:50:32

--- In boost_at_y..., Tom Becker <voidampersand_at_f...> wrote:
> Dear Boosters,
> 
> An associative vector would be valuable in boost, and I definitely 
> would use it a lot.
> 
<...snip...>
> I like the scheme for keeping a change log so iterators can fix up 
themselves.
> 
> There is another approach that has been used in MacApp's containers 
> for many years. The iterators on a container are linked into a list 
> owned by the container. When elements are inserted or deleted in 
the 
> container, it immediately fixes up all its iterators.
> 
> The change log approach looks like it would be more efficient in 
> situations where lots of changes are being made on a container 
while 
> there are lots of iterators on it. The MacApp approach may be more 
> efficient if changes happen mainly when there are few or no 
iterators 
> on the container.
> 

Interestingly, the approach of applying the changes right away was 
what we did in our first implementation of vec_multiset.  We 
eventually moved to a scheme where the iterator's position was only 
recalculated on an as-needed basis.  The idea was to avoid unecessary 
calculations for iterators that are not actually used.  As to 
efficiency, the change-log scheme should be more efficient 
computationally but will be less efficient memory wise.  However, I 
think the memory used can be reduced from what we have in the current 
scheme by adding a bit of clever usage counting in the 
constructor/destructor/update functions for the iterators.