Re: Re: Proposal: Sorted Vector Container

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

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?

Regards,

   Tom