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.
> I like the scheme for keeping a change log so iterators can fix up
> 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
> 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
> there are lots of iterators on it. The MacApp approach may be more
> efficient if changes happen mainly when there are few or no
> 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.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk