Boost logo

Boost :

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;

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

Eric Niebler
Boost Consulting

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