Changing vector inside std::transform on the same vector

Question

I want to figure out if it is allowed to change the vector inside transform. Consider the code:

std::vector<int> v;
for (int i = 0; i < 10; i++) v.push_back(i);

for (auto &i : v) std::cout << i << " ";
std::cout << std::endl;
std::transform(v.begin(), v.end(), std::back_inserter(v),
          [](auto i) { return i;});

for (auto &i : v) std::cout << i << " ";
std::cout << std::endl;

I expect to expand vector with elements which are based on exist vector contents. Here is the output:

0 1 2 3 4 5 6 7 8 9 
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9

But if I replace begin and end with rbegin and rend correspondingly the output is following:

0 1 2 3 4 5 6 7 8 9 
0 1 2 3 4 5 6 7 8 9 9 8 7 6 5 4 3 2 0 0

I get unexpected 0 instead of 1 in a position before last. This makes me wonder if this code is a UB per se, and I should not rely on correct output with forward iterators as well.

The algorithm has undefined behavior at least because the vector can reallocate the used memory. In this case the iterators will be invalid. — Vlad from Moscow, Mar 01 '17 at 00:41
That is what I suspect. I even tried different compiler versions and with MSVS compiler I managed to get some big arbitrary numbers in last two places. Is there a way to implement this algorithm without using additional vector? I need to do several iterations with the new data and I'm a bit reluctant to move vectors back and forth. — mcsim, Mar 01 '17 at 00:46
The question I linked both explains why your code triggers undefined behaviour (invalidation of iterators when reallocating) and how to properly use a vector while adding to the end of the same vector. — chris, Mar 01 '17 at 00:49

score 0 · Accepted Answer · answered Mar 01 '17 at 00:49

There is no for_each above. Certain changes in certain situations are valid, others are not. Yours is not. Generally iterator invalidation makes iteration invalid. Adding or removing elements from a vector invalidates the end iterator (and all iterators at or after the point of insert/removal). Reallocation invalidates all iterators.

Reverse iterators follow different rules based off the validity of thier base iterator. But the forward case was UB already.

Changing vector inside std::transform on the same vector

1 Answers1