26 Algorithms library [algorithms]

26.3 Parallel algorithms [algorithms.parallel]

26.3.1 Preamble [algorithms.parallel.defns]

1
#
Subclause [algorithms.parallel] describes components that C++ programs may use to perform operations on containers and other sequences in parallel.
2
#
A parallel algorithm is a function template listed in this document with a template parameter named ExecutionPolicy or constrained by the following exposition-only concept: template<class Ep> concept execution-policy = is_execution_policy_v<remove_cvref_t<Ep>>; // exposition only
Such a template parameter is termed an execution policy template parameter.
3
#
A parallel algorithm accesses objects indirectly accessible via its arguments by invoking the following functions:
  • (3.1)
    All operations of the categories of the iterators, sentinels, or mdspan types that the algorithm is instantiated with.
  • (3.2)
    Operations on those sequence elements that are required by its specification.
  • (3.3)
    User-provided invocable objects to be applied during the execution of the algorithm, if required by the specification.
  • (3.4)
    Operations on those invocable objects required by the specification.
    [Note 1:  — end note]
These functions are herein called element access functions.
4
#
[Example 1: 
The sort function may invoke the following element access functions:
  • (4.1)
    Operations of the random-access iterator of the actual template argument (as per [random.access.iterators]), as implied by the name of the template parameter RandomAccessIterator.
  • (4.2)
    The swap function on the elements of the sequence (as per the preconditions specified in [sort]).
  • (4.3)
    The user-provided Compare function object.
— end example]
5
#
A standard library function is vectorization-unsafe if it is specified to synchronize with another function invocation, or another function invocation is specified to synchronize with it, and if it is not a memory allocation or deallocation function or lock-free atomic modify-write operation ([atomics.order]).
[Note 2: 
Implementations must ensure that internal synchronization inside standard library functions does not prevent forward progress when those functions are executed by threads of execution with weakly parallel forward progress guarantees.
— end note]
[Example 2: int x = 0; std::mutex m; void f() { int a[] = {1,2}; std::for_each(std::execution::par_unseq, std::begin(a), std::end(a), [&](int) { std::lock_guard<mutex> guard(m); // incorrect: lock_guard constructor calls m.lock() ++x; }); }
The above program may result in two consecutive calls to m.lock() on the same thread of execution (which may deadlock), because the applications of the function object are not guaranteed to run on different threads of execution.
— end example]