Parallel implementations of std algorithms and side effects

Question

Going through the standard documentation for std::transform, I noticed that until C++11 the functor argument was required not to have side effects, while from C++11 onwards the requirement has been made less restrictive - "op and binary_op shall not invalidate iterators or subranges, or modify elements in the ranges". See

http://en.cppreference.com/w/cpp/algorithm/transform

and section 25.3.4 of the standard. The webpage on cppreference.com mentions as well that "The intent of these requirements is to allow parallel or out-of-order implementations of std::transform".

I do not understand then if this snippet of code is legal or not in C++11:

std::vector<int> v(/* fill it with something */), v_transformed;
int foo = 0;
std::transform(v.begin(),v.end(),std::back_inserter(v_transformed),[&foo](const int &n) -> int {
    foo += 1;
    return n*2;
});

Clearly, if std::transform is parallelised behind the scenes, we will have multiple concurrent calls to foo += 1, which is going to be UB. But the functor itself does not seem to violate the requirements outlined in the standard.

This question can be asked for other standard algorithms (except I think std::for_each, which explicitly states that the iteration is to be performed in-order).

Did I misunderstand something?

Answer 1

As far as I understand the C++11 spec, all standard library functions have to perform all their operations sequentially, if their effects are visible to the user. In particular, all "mutating sequence operations" have to be perfomed sequentially.

The relevant part of the standard is §17.6.5.9/8:

Unless otherwise specified, C++ standard library functions shall perform all operations solely within the current thread if those operations have effects that are visible (1.10) to users.

Answer 2

The way the algorithms are currently defined they have to be executed sequentially unless the implementation can prove that executing it concurrently doesn't change the semantics. I could imagine a future addition for algorithms which are explicitly allowed to be executed concurrently but they would be different algorithms.