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