From: Tom Becker (voidampersand_at_[hidden])
Date: 2002-01-10 14:27:57
On Thu, 10 Jan 2002 09:02:40 -0500, "David Abrahams"
<david.abrahams_at_[hidden]> wrote:
>----- Original Message -----
>From: "Tom Becker" <voidampersand_at_[hidden]>
>
>> 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.
>
>Wouldn't an iterator-stabilizing container adaptor be more versatile?
Okay. If the cost of providing iterator stability is very low, it
would be a no-brainer. Of course, policies provide versatility too.
The question is whether they would provide the right kind of
versatility.
I worked on a framework where containers provided iterator stability.
The implementation is reasonably efficient, and it's been used for a
long time without any problems I'm aware of. That having been said,
the containers were not as nice as those in the STL, and we've been
moving to use STL containers in the framework and encouraging
developers to do the same in their applications. One concern that we
had initially was the lack of guaranteed iterator stability. In
practice, it turned out to not be a problem at all. The most common
case where the iterator stability feature got exercised was in code
that deleted the contents of a container, using a forward loop that
supposedly advanced an iterator. Because the iterator got adjusted as
each element was deleted, it really stayed pointing at the beginning
for the whole time. This was ridiculous. Changing the code, to a
while loop that pops elements off the back, eliminated the iterator
and was also more efficient. I have yet to find any other code that
depended on iterator fixups, or to hear from a developer who had an
application that demanded it. That doesn't mean there aren't valid
needs for such a feature, just that I'm not running into them in my
area. There is a general problem in programming of when code needs to
pull the rug out from under itself. The classic example is clicking
on a window's close button. The classic solution is to use the
command pattern to close and delete the window later, as soon as it
is safe. One reason why I may not be seeing much use for iterator
stability in my area, is that developers are using commands to delay
modifications to containers they are iterating on. The command
mechanism in this framework is how undo is supported, so it gets used
a lot. This has an interesting resemblance to the change log
approach. Rather than building up a list of changes that have been
made to the container, it's building up a list of changes to be made.
The main disadvantage I see for a policy-based approach is it gives
developers yet another choice they have to make, and it adds some
complexity to the design. Also, because the policy API would be
exposed, if there are problems with it, fixing it might be more
difficult than if iterator stability were a private feature.
The main advantage of the policy-based approach is that there would
be no overhead for supporting iterator stability except in cases
where it is really needed. Since associative vector is an optimized
version of an existing container, the developer who choose to use it
are likely to be even more focused on efficiency than the usual C++
crowd. Of course, developers would be free to use an associative
vector with a guaranteed stability policy. If they don't know whether
or not they need iterator stability, they should use the class that
provides the guarantee. If they do know, they can choose the class
that is best suited for their needs.
Regards,
Tom
--
Tom Becker "Within C++, there is a much smaller and
<voidampersand_at_[hidden]> cleaner language struggling to get out."
-- Bjarne Stroustrup