[boost] Re: Formal Review: FOREACH macro

From: Eric Niebler (eric_at_[hidden])
Date: 2005-05-02 14:44:42

Stefan Strasser wrote:
> Eric Niebler schrieb:
> 
>>>
>>> Incidently, if it is caching then code like:
>>>
>>>     BOOST_FOREACH( int i, vec )
>>>         if (condition(i))
>>>             vec.push_back( filter(i) );
>>>
>>> will not work the same as:
>>>
> 
> vec.reserve(a lot);

Haha! OK.

> 
>>>     for (iterator i = vec.begin(); i != vec.end(); ++i)
>>>         if (condition(*i))
>>>             vec.push_back( filter(*i) );
>>>
>>
>>
>> Neither of these loops "work" -- they are both broken in the same way. 
>> They both invalidate the iterator they are using.
> 
> 
> 
> [5] A vector's iterators are invalidated when its memory is reallocated. 
> Additionally, inserting or deleting an element in the middle of a vector 
> invalidates all iterators that point to elements following the insertion 
> or deletion point. It follows that you can prevent a vector's iterators 
> from being invalidated if you use reserve() to preallocate as much 
> memory as the vector will ever use, and if all insertions and deletions 
> are at the vector's end.
> 
> 
> i is never following the insertion point.
> 

Right, *now* you have an interesting point. Disregarding the fact 
(opinion) that writing loops that add/remove elements from a sequence 
while iterating it is playing with fire, you're absolutely right that 
the second loops is guaranteed to work by the standard (for proper 
values of "a lot") whereas the first does not.

How serious an issue is this? It's a sincere question. For some sequence 
types (std::list, all the associative containers) the end iterator is 
stable even when adding/removing elements from the sequence. It 
certainly seems worth making a note about this in the FOREACH docs, but 
what should I say? An outright ban on adding/removing elements from the 
sequence during iteration seems too extreme. Perhaps something like:

"If adding/removing elements from the collection type can cause iterator 
invalidation under any circumstances, the effect of doing such from the 
body of FOREACH is undefined."

Or maybe it would be better to define FOREACH's behavior in terms of the 
equivalent for loop:

for( iterator-type begin = begin(col), end = end(col);
      begin != end; ++begin )
{
   loop-variable = *begin;
   loop-body
}

That way people can work out for themselves whether iterator 
invalidation will occur or not.

-- 
Eric Niebler
Boost Consulting
www.boost-consulting.com