Boost logo

Boost :

From: Tom Becker (voidampersand_at_[hidden])
Date: 2002-01-10 02:23:05

Dear Boosters,

An associative vector would be valuable in boost, and I definitely
would use it a lot.

Implementing the associative vector as a subclass of a standard
vector seems unsafe. Some of the vector API overlaps with map and
might be okay to use, but not all of it. Implementing associative
vector as an object that owns a standard vector will allow
associative vector to export only the APIs that are appropriate. It
can also provide access to the underlying vector with a single
function. This allows convenient setting up of the vector while
making it obvious that the code is going around the associative APIs
and should be checked to make sure it leaves the vector in a state
that is okay for its owner.

I don't have any problem with the idea that iterator stability may be
different with an associated vector than with a map. Iterator
stability is more a function of the container implementation than of
the API. Also, since the main purpose of an associative vector is to
support efficient lookups rather than efficient inserting and
deleting, iterators on associative vectors are less likely to be
invalidated than iterators on maps.

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.

There are many applications for associative vectors that will never
need iterator fixups. In those situations, it would be nice if the
overhead of tracking changes and adjusting iterators could be avoided

Since there seem to be multiple reasonable approaches for managing
iterator stability, I'd like to propose that the associative vector
template use a policy. The default would be a do-nothing policy. In
order to cover the possibilities, the policy should have at least
these functions:

template< typename Container, typename BaseIterator >
struct iterator_stability_policy
     typedef BaseIterator Iterator; // default for do-nothing
     // class Iterator : public BaseIterator { ... }; // for do-something

     void install(Iterator& iter);
     void remove(Iterator& iter);
     void inserted(const Container& c,
                   BaseIterator first,
                   BaseIterator last) const;
     void deleted(const Container& c,
                  BaseIterator first,
                  BaseIterator last) const;
     void adjust(const Container& c,
                 Iterator& iter) const;

This is whiteboard-quality code, and I would be surprised if it
didn't need at least some changes to get it right. I'm pretty sure it
would cover the MacApp-style iterator management, and of course
almost anything will work for the do-nothing case. Do you think it
would work okay for the change log approach? Are there other
approaches that the policy should be able to support?



Boost list run by bdawes at, gregod at, cpdaniel at, john at