[algorithms.parallel.defns]

# 26 Algorithms library [[algorithms]](./#algorithms)

## 26.3 Parallel algorithms [[algorithms.parallel]](algorithms.parallel#defns)

### 26.3.1 Preamble [algorithms.parallel.defns]

[1](#1)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L287)

Subclause [[algorithms.parallel]](algorithms.parallel "26.3 Parallel algorithms") describes components that C++ programs may use
to perform operations on containers and other sequences in parallel[.](#1.sentence-1)

[2](#2)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L291)

A [*parallel algorithm*](#def:parallel_algorithm "26.3.1 Preamble [algorithms.parallel.defns]") 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*](#concept:execution-policy "26.3.1 Preamble [algorithms.parallel.defns]") = is_execution_policy_v<remove_cvref_t<Ep>>; // *exposition only*

Such a template parameter is termed an [*execution policy template parameter*](#def:template_parameter,execution_policy "26.3.1 Preamble [algorithms.parallel.defns]")[.](#2.sentence-2)

[3](#3)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L301)

A parallel algorithm accesses objects indirectly accessible via its arguments
by invoking the following functions:

- [(3.1)](#3.1)

  All operations of the categories of the iterators, sentinels, or mdspan types
 that the algorithm is instantiated with[.](#3.1.sentence-1)

- [(3.2)](#3.2)

  Operations on those sequence elements that are required by its specification[.](#3.2.sentence-1)

- [(3.3)](#3.3)

  User-provided invocable objects
 to be applied during the execution of the algorithm,
 if required by the specification[.](#3.3.sentence-1)

- [(3.4)](#3.4)

  Operations on those invocable objects required by the specification[.](#3.4.sentence-1)
  [*Note [1](#note-1)*:
  See [[algorithms.requirements]](algorithms.requirements "26.2 Algorithms requirements")[.](#3.4.sentence-2)
 â *end note*]

These functions are herein called [*element access functions*](#def:element_access_functions "26.3.1 Preamble [algorithms.parallel.defns]")[.](#3.sentence-2)

[4](#4)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L322)

[*Example [1](#example-1)*:

The sort function may invoke the following element access functions:

- [(4.1)](#4.1)

  Operations of the random-access iterator of the actual template argument
 (as per [[random.access.iterators]](random.access.iterators "24.3.5.7 Random access iterators")),
 as implied by the name of the template parameter RandomAccessIterator[.](#4.1.sentence-1)

- [(4.2)](#4.2)

  The swap function on the elements of the sequence
 (as per the preconditions specified in [[sort]](sort "26.8.2.1 sort"))[.](#4.2.sentence-1)

- [(4.3)](#4.3)

  The user-provided Compare function object[.](#4.3.sentence-1)

â *end example*]

[5](#5)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L338)

A standard library function is [*vectorization-unsafe*](#def:vectorization-unsafe "26.3.1 Preamble [algorithms.parallel.defns]") 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]](atomics.order "32.5.4 Order and consistency"))[.](#5.sentence-1)

[*Note [2](#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[.](#5.sentence-2)

â *end note*]

[*Example [2](#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[.](#5.sentence-3)

â *end example*]
