Re: Re: Re: Proposal: Sorted Vector Container

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