Add elements to a vector during range-based loop c++11

Question

I have used the new range-based for loop provided by C++11 standard and I came up with the following question: suppose that we iterate over a vector<> using the range-based for, and we add some element in the end of the vector during this iteration. Thus, when do the loop end?

For instance, see this code:

#include <iostream>
#include <vector>
using namespace std;
int main() {
    vector<unsigned> test({1,2,3});
    for(auto &num : test) {
        cout << num << " ";
        if(num % 2)
            test.push_back(num + 10);
    }
    cout << "\n";
    for(auto &num : test) 
        cout << num << " ";
    return 0;
}

I tested G++ 4.8 and Apple LLVM version 4.2 (clang++) with "-std=c++11" flag, and the output is (for both):

1 2 3
1 2 3 11 13

Note that the first loop terminates in the end of original vector, although we add other elements to it. It seems that the for-range loop evaluate the container end in beginning only. Is this, in fact, the correct behavior of range-for? Is it specified by the committee? Can we trust in this behavior?

Note that if we change the first loop by

for(vector<unsigned>::iterator it = test.begin(); it != test.end(); ++it)

with invalid the iterators and come up with a segmentation fault.

though adding isn't erasing, this is a duplicate of [Erasing an element from a container while inside a range-based for loop](http://stackoverflow.com/questions/8624686/erasing-an-element-from-a-container-while-inside-a-range-based-for-loop) because the answer there shows you what the standard says the range-for does - end is determined and saved before the loop starts, and that saved value is used on subsequent iterations. — Kate Gregory, Jun 12 '13 at 22:53
@KateGregory I would argue this is not a duplicate because removing the current element would be undefined behavior for all containers, but adding an element is only undefined behavior for `std::vector`, `std::deque`, `std::unordered_set` and `std::unorderd_map`. — David Brown, Jun 12 '13 at 23:24
I had seem that question, by the behavior is slightly different. Anyway, thanks. — an_drade, Jun 12 '13 at 23:30
@KateGregory This is not a duplicate. The answer is different - see mine below. — Paul Jurczak, Feb 17 '16 at 21:13

score 21 · Accepted Answer · answered Jun 12 '13 at 23:02

21

No you cannot rely on this behaviour. Modifying the vector inside the loop results in undefined behaviour because the iterators used by the loop are invalidated when the vector is modified.

The range based for loop

for ( range_declaration : range_expression) loop_statement

is essentially equivalent to

{
    auto && __range = range_expression ; 
    for (auto __begin = std::begin(__range),
        __end = std::end(__range); 
        __begin != __end; ++__begin) { 
            range_declaration = *__begin;
            loop_statement 
    }
}

When you modify the vector, the iterators __begin and __end are no longer valid and the dereferencing __begin results in undefined behaviour.

answered Jun 12 '13 at 23:02

David Brown

13,336
4
38
55

Thanks David. It is interesting note that my two pieces of code, although essentially equivalent, come up with very different results. – an_drade Jun 12 '13 at 23:38
2

actually, you are missing the disctinction between for(auto _begin = r.begin(); _begin != r.end(); ++begin) and for(auto _begin = r.begin(), _end = r.end(); _begin != _end; ++_begin) (the cacheing of r.end()) And *that* is why your program does the impression of working! the iterator is pointing to an old version of the vector. Put a destructor in the contained objects and hilarity will ensue... :-D – Massa Jun 15 '13 at 11:40
2

_iterators used by the loop are invalidated when the vector is modified_ Not necessarily. If vector's capacity is large enough not to require reallocation, then all iterators remain valid. – Paul Jurczak Feb 17 '16 at 20:57

score 0 · Answer 2 · edited Jun 20 '20 at 09:12

You can rely on this behavior as long as vector's capacity is large enough, so reallocation is not required. This would guarantee validity of all iterators and references other than past-the-end iterator after call to push_back(). This is fine since end() was calculated only once at the beginning of the loop (see std::vector::push_back).

In your case, you have to increase capacity of test vector to guarantee this behavior:

vector<unsigned> test({1,2,3});
test.reserve(5);

EDIT

Based on responses to Is it legal to add elements to a preallocated vector in a range-based for loop over that vector?, this is a case of undefined behavior. Release version built with gcc, clang and cl runs fine, but a debug version built with cl (Visual Studio) will throw an exception.

Add elements to a vector during range-based loop c++11

2 Answers2

Linked