Unusual behavior with auto while traversing a dynamic vector

Question

I am traversing a vector with auto ( code attached ). While traversing, I am also appending some elements at the back. I was not expecting the output that I got.

#include <iostream>
#include <vector>
using namespace std;

vector <int> dynamic_vector;

void access( )
{
    for ( auto i : dynamic_vector ) {
        if ( i == 3 ) {
            dynamic_vector.push_back( 4 );
            dynamic_vector.push_back( 5 );
        }
        cout << i << endl;
    }
}

int main() {
    dynamic_vector.push_back( 1 );
    dynamic_vector.push_back( 2 );
    dynamic_vector.push_back( 3 );
    access( );
    return 0;
}

Output:

1
2
3

I was expecting all numbers from 1 to 5 will get printed. I am not able to understand how traversing with auto works?

Re *I was expecting all numbers from 1 to 5 will get printed* -- I would expect nasal demons, myself. This is undefined behavior, and nasal demons are the canonical result from invoking undefined behavior. — David Hammen, Oct 11 '15 at 14:13

songyuanyao · Answer 1 · 2015-10-11T16:15:54.743

5

This is called Range-based for loop.

6.5.4$1 The range-based for statement [stmt.ranged]:

In each case, a range-based for statement is equivalent to

{
  auto && __range = range-init;
  for ( auto __begin = begin-expr,
             __end = end-expr;
        __begin != __end;
        ++__begin ) {
    for-range-declaration = *__begin;
    statement
  }
}

Note the equivalent pseudocode, __end (and __begin) will be set only once at the start of the loop. In your case, after the push_back at the last time of loop, the iterators might be invalid. If yes, the increment and comparsion on them will be implementation dependent. That means, as one of the possibilities, __end and __begin will remain the same, and loop count won't change.

edited Oct 11 '15 at 16:15

answered Oct 11 '15 at 12:47

songyuanyao

169,198
16
310
405

1

The result depends on particular implementation of the iterators. For example, the iterator may store the reference to vector object and the index of the element rather than storing just a pointer. The end iterator may be a special end_of_vector iterator. – Andrey Nasonov Oct 11 '15 at 15:12
@AndreyNasonov Yes, basically this is an implementation dependence issue. – songyuanyao Oct 11 '15 at 16:17
@songyuanyao Is it implementation-defined or undefined behavior? My reading of the standard would be that it is UB, but I am not sure because I could not find a good definition of invalid iterator. The best I found was that an invalid iterator may be a singular iterator, and that supports basically assignments. – Jens Oct 11 '15 at 18:25
@Jens The standard seems doesn't contain the explicit expression about the comparsion and increment on invalid iterator. So as Andrey said, it depends on the implementation of `vector` and its iterator. And if the iterator is implemented as pointer (as most implementations do for `vector`), according this [answer](http://stackoverflow.com/a/30694084/3309790), comparsion on invalid pointer is an implementation-defined behavior. – songyuanyao Oct 12 '15 at 01:39
@songyuanyao §24.2.1.11 states that it may be a singular iterator. In this case, dereferencing it is undefined behavior. I think that you cannot assume that it is implementation-defined behavior in general. – Jens Oct 12 '15 at 07:57
@Jens I agree that dereferencing is UB. But in OP's case, `push_back` happened at the last time of loop, after that the iterator will not be dereferenced, only increment and comparsion. For this specified case, it's hard to say it's UB. – songyuanyao Oct 12 '15 at 08:03
@songyuanyao I think this is an interesting question for itself. I have opened a new question (http://stackoverflow.com/questions/33076032/which-operations-are-defined-for-invalid-iterators) to see if anybody could give some better reference. – Jens Oct 12 '15 at 08:03

Jens · Answer 2 · 2015-10-11T14:05:36.957

In addition to the problem pointed out by songyuanyao's answer, the code you present is undefined behavior. First, it is possible that the vector needs to reallocate because of a push_back, and then all iterator are invalidated and thus incrementing the loop variable is undefined behavior.

Looking at the documentation for push_back:

If the new size() is greater than capacity() then all iterators and references (including the past-the-end iterator) are invalidated. Otherwise only the past-the-end iterator is invalidated.

, I would say that appending to the vector in a range-based for statement is undefined behavior in any case, because the end iterator is always invalidated. The range-based for stores a copy of the initial end()-iterator, and this iterator is invalidated after the first push_back. This matches to your output, because it still points to the original end of the three-element vector. However, you should not rely on this behavior.

Unfortuantely, I could not find a rigid definition of "invalid iterator" semantics in the standard. §24.2.1.11 says that invalid iterators may be singular, but only states that dereferencing them may be undefined behavior. There is no semantics for comparing them, but given the fact that one implementation for vectors is to use the next memory address following the internal storage, and that address changes when the vector reallocates, I would say that the loop is undefined behavior.

Unusual behavior with auto while traversing a dynamic vector

2 Answers2

Linked