forked from cplusplus/draft
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathalgorithms.tex
9823 lines (8714 loc) · 380 KB
/
algorithms.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
%!TEX root = std.tex
\rSec0[algorithms]{Algorithms library}
\rSec1[algorithms.general]{General}
\pnum
This Clause describes components that \Cpp{} programs may use to perform
algorithmic operations on containers\iref{containers} and other sequences.
\pnum
The following subclauses describe components for
non-modifying sequence operations,
mutating sequence operations,
sorting and related operations,
and algorithms from the ISO C library,
as summarized in \tref{algorithms.summary}.
\begin{libsumtab}{Algorithms library summary}{algorithms.summary}
\ref{algorithms.requirements} & Algorithms requirements & \\
\ref{algorithms.parallel} & Parallel algorithms & \\ \rowsep
\ref{alg.nonmodifying} & Non-modifying sequence operations & \tcode{<algorithm>} \\
\ref{alg.modifying.operations} & Mutating sequence operations & \\
\ref{alg.sorting} & Sorting and related operations & \\ \rowsep
\ref{numeric.ops} & Generalized numeric operations & \tcode{<numeric>} \\ \rowsep
\ref{alg.c.library} & C library algorithms & \tcode{<cstdlib>} \\
\end{libsumtab}
\rSec1[algorithms.requirements]{Algorithms requirements}
\pnum
All of the algorithms
are separated from the particular implementations of data structures and
are parameterized by iterator types.
Because of this, they can work with program-defined data structures,
as long as these data structures have iterator types
satisfying the assumptions on the algorithms.
\pnum
The entities defined in the \tcode{std::ranges} namespace in this Clause
are not found by argument-dependent name lookup\iref{basic.lookup.argdep}.
When found by unqualified\iref{basic.lookup.unqual} name lookup
for the \grammarterm{postfix-expression} in a function call\iref{expr.call},
they inhibit argument-dependent name lookup.
\begin{example}
\begin{codeblock}
void foo() {
using namespace std::ranges;
std::vector<int> vec{1,2,3};
find(begin(vec), end(vec), 2); // \#1
}
\end{codeblock}
The function call expression at \tcode{\#1} invokes \tcode{std::ranges::find},
not \tcode{std::find}, despite that
(a) the iterator type returned from \tcode{begin(vec)} and \tcode{end(vec)}
may be associated with namespace \tcode{std} and
(b) \tcode{std::find} is more specialized\iref{temp.func.order} than
\tcode{std::ranges::find} since the former requires
its first two parameters to have the same type.
\end{example}
\pnum
For purposes of determining the existence of data races,
algorithms shall not modify objects referenced through an iterator argument
unless the specification requires such modification.
\pnum
Throughout this Clause, where the template parameters are not constrained,
the names of template parameters are used to express type requirements.
\begin{itemize}
\item
If an algorithm's template parameter is named
\tcode{InputIterator},
\tcode{InputIterator1}, or
\tcode{Input\-Iterator2},
the template argument shall satisfy the
\oldconcept{InputIterator} requirements\iref{input.iterators}.
\item
If an algorithm's template parameter is named
\tcode{OutputIterator},
\tcode{OutputIterator1}, or
\tcode{Output\-Iterator2},
the template argument shall satisfy the
\oldconcept{OutputIterator} requirements\iref{output.iterators}.
\item
If an algorithm's template parameter is named
\tcode{ForwardIterator},
\tcode{ForwardIterator1}, or
\tcode{Forward\-Iterator2},
the template argument shall satisfy the
\oldconcept{ForwardIterator} requirements\iref{forward.iterators}.
\item
If an algorithm's template parameter is named
\tcode{BidirectionalIterator},
\tcode{Bidirectional\-Iterator1}, or
\tcode{BidirectionalIterator2},
the template argument shall satisfy the
\oldconcept{BidirectionalIterator} requirements\iref{bidirectional.iterators}.
\item
If an algorithm's template parameter is named
\tcode{RandomAccessIterator},
\tcode{Random\-AccessIterator1}, or
\tcode{RandomAccessIterator2},
the template argument shall satisfy the
\oldconcept{RandomAccessIterator} requirements\iref{random.access.iterators}.
\end{itemize}
\pnum
If an algorithm's \effects element specifies
that a value pointed to by any iterator passed as an argument is modified,
then that algorithm has an additional type requirement:
The type of that argument shall satisfy
the requirements of a mutable iterator\iref{iterator.requirements}.
\begin{note}
This requirement does not affect arguments that are named
\tcode{OutputIterator}, \tcode{OutputIterator1}, or \tcode{OutputIterator2},
because output iterators must always be mutable, nor
does it affect arguments that are constrained,
for which mutability requirements are expressed explicitly.
\end{note}
\pnum
Both in-place and copying versions are provided for certain algorithms.%
\footnote{The decision whether to include a copying version was
usually based on complexity considerations.
When the cost of doing the operation dominates the cost of copy,
the copying version is not included.
For example, \tcode{sort_copy} is not included
because the cost of sorting is much more significant,
and users might as well do \tcode{copy} followed by \tcode{sort}.}
When such a version is provided for \textit{algorithm} it is called
\textit{algorithm\tcode{_copy}}.
Algorithms that take predicates end with the suffix \tcode{_if}
(which follows the suffix \tcode{_copy}).
\pnum
When not otherwise constrained, the \tcode{Predicate} parameter is used
whenever an algorithm expects a function object\iref{function.objects} that,
when applied to the result of dereferencing the corresponding iterator,
returns a value testable as \tcode{true}.
In other words,
if an algorithm takes \tcode{Predicate pred} as its argument and
\tcode{first} as its iterator argument with value type \tcode{T},
it should work correctly in the construct
\tcode{pred(*first)} contextually converted to \tcode{bool}\iref{conv}.
The function object \tcode{pred} shall not apply any non-constant function
through the dereferenced iterator.
Given a glvalue \tcode{u} of type (possibly \tcode{const}) \tcode{T}
that designates the same object as \tcode{*first},
\tcode{pred(u)} shall be a valid expression
that is equal to \tcode{pred(*first)}.
\pnum
When not otherwise constrained, the \tcode{BinaryPredicate} parameter is used
whenever an algorithm expects a function object that when applied
to the result of dereferencing two corresponding iterators or
to dereferencing an iterator and type \tcode{T}
when \tcode{T} is part of the signature
returns a value testable as \tcode{true}.
In other words,
if an algorithm takes \tcode{BinaryPredicate binary_pred} as its argument and
\tcode{first1} and \tcode{first2} as its iterator arguments
with respective value types \tcode{T1} and \tcode{T2},
it should work correctly in the construct
\tcode{binary_pred(*first1, *first2)} contextually converted to \tcode{bool}\iref{conv}.
Unless otherwise specified,
\tcode{BinaryPredicate} always takes the first iterator's \tcode{value_type}
as its first argument, that is, in those cases when \tcode{T value}
is part of the signature, it should work correctly in the construct
\tcode{binary_pred(*first1, value)} contextually converted to \tcode{bool}\iref{conv}.
\tcode{binary_pred} shall not apply any non-constant function
through the dereferenced iterators.
Given a glvalue \tcode{u} of type (possibly \tcode{const}) \tcode{T1}
that designates the same object as \tcode{*first1}, and
a glvalue \tcode{v} of type (possibly \tcode{const}) \tcode{T2}
that designates the same object as \tcode{*first2},
\tcode{binary_pred(u, *first2)},
\tcode{binary_pred(*first1, v)}, and
\tcode{binary_pred(u, v)}
shall each be a valid expression that is equal to
\tcode{binary_pred(*first1, *first2)}, and
\tcode{binary_pred(u, value)}
shall be a valid expression that is equal to
\tcode{binary_pred(*first1, value)}.
\pnum
The parameters
\tcode{UnaryOperation},
\tcode{BinaryOperation},
\tcode{BinaryOperation1},
and \tcode{BinaryOperation2}
are used
whenever an algorithm expects a function object\iref{function.objects}.
\pnum
\begin{note}
Unless otherwise specified, algorithms that take function objects as arguments
are permitted to copy those function objects freely.
Programmers for whom object identity is important should consider
using a wrapper class that points to a noncopied implementation object
such as \tcode{reference_wrapper<T>}\iref{refwrap}, or some equivalent solution.
\end{note}
\pnum
When the description of an algorithm gives an expression such as
\tcode{*first == value} for a condition, the expression
shall evaluate to either \tcode{true} or \tcode{false} in boolean contexts.
\pnum
In the description of the algorithms, operator \tcode{+}
is used for some of the iterator categories
for which it does not have to be defined.
In these cases the semantics of \tcode{a + n} are the same as those of
\begin{codeblock}
auto tmp = a;
for (; n < 0; ++n) --tmp;
for (; n > 0; --n) ++tmp;
return tmp;
\end{codeblock}
Similarly, operator \tcode{-} is used
for some combinations of iterators and sentinel types
for which it does not have to be defined.
If \range{a}{b} denotes a range,
the semantics of \tcode{b - a} in these cases are the same as those of
\begin{codeblock}
iter_difference_t<remove_reference_t<decltype(a)>> n = 0;
for (auto tmp = a; tmp != b; ++tmp) ++n;
return n;
\end{codeblock}
and if \range{b}{a} denotes a range, the same as those of
\begin{codeblock}
iter_difference_t<remove_reference_t<decltype(b)>> n = 0;
for (auto tmp = b; tmp != a; ++tmp) --n;
return n;
\end{codeblock}
\pnum
In the description of algorithm return values,
a sentinel value \tcode{s} denoting the end of a range \range{i}{s}
is sometimes returned where an iterator is expected.
In these cases,
the semantics are as if the sentinel is converted into an iterator using
\tcode{ranges::next(i, s)}.
\pnum
Overloads of algorithms that take \libconcept{Range} arguments\iref{range.range}
behave as if they are implemented by calling \tcode{ranges::begin} and
\tcode{ranges::end} on the \libconcept{Range}(s) and
dispatching to the overload in namespace \tcode{ranges}
that takes separate iterator and sentinel arguments.
\pnum
The number and order of deducible template parameters for algorithm declarations
are unspecified, except where explicitly stated otherwise.
\begin{note}
Consequently, the algorithms may not
be called with explicitly-specified template argument lists.
\end{note}
\pnum
The class templates
\tcode{binary_transform_result},
\tcode{for_each_result},
\tcode{minmax_result},
\tcode{mismatch_result},
\tcode{copy_result}, and
\tcode{partition_copy_result}
have the template parameters, data members, and special members specified below.
They have no base classes or members other than those specified.
\rSec1[algorithms.parallel]{Parallel algorithms}
\pnum
This subclause describes components that \Cpp{} programs may use
to perform operations on containers and other sequences in parallel.
\rSec2[algorithms.parallel.defns]{Terms and definitions}
\pnum
A \defn{parallel algorithm} is a function template listed in this document
with a template parameter named \tcode{ExecutionPolicy}.
\pnum
Parallel algorithms access objects indirectly accessible via their arguments
by invoking the following functions:
\begin{itemize}
\item
All operations of the categories of the iterators
that the algorithm is instantiated with.
\item
Operations on those sequence elements that are required by its specification.
\item
User-provided function objects
to be applied during the execution of the algorithm,
if required by the specification.
\item
Operations on those function objects required by the specification.
\begin{note}
See~\ref{algorithms.requirements}.
\end{note}
\end{itemize}
These functions are herein called \defn{element access functions}.
\begin{example}
The \tcode{sort} function may invoke the following element access functions:
\begin{itemize}
\item
Operations of the random-access iterator of the actual template argument
(as per \ref{random.access.iterators}),
as implied by the name of the template parameter \tcode{RandomAccessIterator}.
\item
The \tcode{swap} function on the elements of the sequence
(as per the preconditions specified in \ref{sort}).
\item
The user-provided \tcode{Compare} function object.
\end{itemize}
\end{example}
\pnum
A standard library function is \defn{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.
\begin{note}
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}
\begin{example}
\begin{codeblock}
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: \tcode{lock_guard} constructor calls \tcode{m.lock()}
++x;
});
}
\end{codeblock}
The above program may result in two consecutive calls to \tcode{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}
\rSec2[algorithms.parallel.user]{Requirements on user-provided function objects}
\pnum
Unless otherwise specified,
function objects passed into parallel algorithms as objects of type
\tcode{Predicate},
\tcode{BinaryPredicate},
\tcode{Compare},
\tcode{UnaryOperation},
\tcode{BinaryOperation},
\tcode{BinaryOperation1},
\tcode{BinaryOperation2}, and
the operators used by the analogous overloads to these parallel algorithms
that could be formed by the invocation
with the specified default predicate or operation (where applicable)
shall not directly or indirectly modify objects via their arguments,
nor shall they rely on the identity of the provided objects.
\rSec2[algorithms.parallel.exec]{Effect of execution policies on algorithm execution}
\pnum
Parallel algorithms have
template parameters named \tcode{ExecutionPolicy}\iref{execpol}
which describe the manner in which the execution of these algorithms may be
parallelized and the manner in which they apply the element access functions.
\pnum
If an object is modified by an element access function,
the algorithm will perform no other unsynchronized accesses to that object.
The modifying element access functions are those
which are specified as modifying the object.
\begin{note}
For example,
\tcode{swap()},
\tcode{++},
\tcode{--},
\tcode{@=}, and
assignments
modify the object.
For the assignment and \tcode{@=} operators, only the left argument is modified.
\end{note}
\pnum
Unless otherwise stated, implementations may make arbitrary copies of elements
(with type \tcode{T}) from sequences
where \tcode{is_trivially_copy_constructible_v<T>}
and \tcode{is_trivially_destructible_v<T>} are \tcode{true}.
\begin{note}
This implies that user-supplied function objects should not rely on
object identity of arguments for such input sequences.
Users for whom the object identity of the arguments to these function objects
is important should consider using a wrapping iterator
that returns a non-copied implementation object
such as \tcode{reference_wrapper<T>}\iref{refwrap}
or some equivalent solution.
\end{note}
\pnum
The invocations of element access functions in parallel algorithms invoked with
an execution policy object of type \tcode{execution::sequenced_policy} all occur
in the calling thread of execution.
\begin{note}
The invocations are not interleaved; see~\ref{intro.execution}.
\end{note}
\pnum
The invocations of element access functions in parallel algorithms invoked with
an execution policy object of type \tcode{execution::unsequenced_policy}
are permitted to execute in an unordered fashion
in the calling thread of execution,
unsequenced with respect to one another in the calling thread of execution.
\begin{note}
This means that multiple function object invocations
may be interleaved on a single thread of execution,
which overrides the usual guarantee from \ref{intro.execution}
that function executions do not overlap with one another.
\end{note}
The behavior of a program is undefined if
it invokes a vectorization-unsafe standard library function
from user code
called from a \tcode{execution::unsequenced_policy} algorithm.
\begin{note}
Because \tcode{execution::unsequenced_policy} allows
the execution of element access functions
to be interleaved on a single thread of execution,
blocking synchronization, including the use of mutexes, risks deadlock.
\end{note}
\pnum
The invocations of element access functions in parallel algorithms invoked with
an execution policy object of type \tcode{execution::parallel_policy}
are permitted to execute either
in the invoking thread of execution or
in a thread of execution implicitly created by the library
to support parallel algorithm execution.
If the threads of execution created by \tcode{thread}\iref{thread.thread.class}
provide concurrent forward progress guarantees\iref{intro.progress},
then a thread of execution implicitly created by the library will provide
parallel forward progress guarantees;
otherwise, the provided forward progress guarantee is
\impldef{forward progress guarantees for
implicit threads of parallel algorithms (if not defined for \tcode{thread})}.
Any such invocations executing in the same thread of execution
are indeterminately sequenced with respect to each other.
\begin{note}
It is the caller's responsibility to ensure
that the invocation does not introduce data races or deadlocks.
\end{note}
\begin{example}
\begin{codeblock}
int a[] = {0,1};
std::vector<int> v;
std::for_each(std::execution::par, std::begin(a), std::end(a), [&](int i) {
v.push_back(i*2+1); // incorrect: data race
});
\end{codeblock}
The program above has a data race because of the unsynchronized access to the
container \tcode{v}.
\end{example}
\begin{example}
\begin{codeblock}
std::atomic<int> x{0};
int a[] = {1,2};
std::for_each(std::execution::par, std::begin(a), std::end(a), [&](int) {
x.fetch_add(1, std::memory_order::relaxed);
// spin wait for another iteration to change the value of \tcode{x}
while (x.load(std::memory_order::relaxed) == 1) { } // incorrect: assumes execution order
});
\end{codeblock}
The above example depends on the order of execution of the iterations, and
will not terminate if both iterations are executed sequentially
on the same thread of execution.
\end{example}
\begin{example}
\begin{codeblock}
int x = 0;
std::mutex m;
int a[] = {1,2};
std::for_each(std::execution::par, std::begin(a), std::end(a), [&](int) {
std::lock_guard<mutex> guard(m);
++x;
});
\end{codeblock}
The above example synchronizes access to object \tcode{x}
ensuring that it is incremented correctly.
\end{example}
\pnum
The invocations of element access functions in parallel algorithms invoked with
an execution policy object of type \tcode{execution::parallel_unsequenced_policy} are
permitted to execute
in an unordered fashion in unspecified threads of execution, and
unsequenced with respect to one another within each thread of execution.
These threads of execution are
either the invoking thread of execution
or threads of execution implicitly created by the library;
the latter will provide weakly parallel forward progress guarantees.
\begin{note}
This means that multiple function object invocations may be interleaved
on a single thread of execution,
which overrides the usual guarantee from \ref{intro.execution}
that function executions do not overlap with one another.
\end{note}
The behavior of a program is undefined if
it invokes a vectorization-unsafe standard library function
from user code
called from a \tcode{execution::parallel_unsequenced_policy} algorithm.
\begin{note}
Because \tcode{execution::parallel_unsequenced_policy} allows
the execution of element access functions
to be interleaved on a single thread of execution,
blocking synchronization, including the use of mutexes, risks deadlock.
\end{note}
\pnum
\begin{note}
The semantics of invocation with
\tcode{execution::unsequenced_policy},
\tcode{execution::parallel_policy}, or
\tcode{execution::parallel_unsequenced_policy}
allow the implementation to fall back to sequential execution
if the system cannot parallelize an algorithm invocation,
e.g., due to lack of resources.
\end{note}
\pnum
If an invocation of a parallel algorithm uses threads of execution
implicitly created by the library,
then the invoking thread of execution will either
\begin{itemize}
\item
temporarily block
with forward progress guarantee delegation\iref{intro.progress}
on the completion of these library-managed threads of execution, or
\item
eventually execute an element access function;
\end{itemize}
the thread of execution will continue to do so until the algorithm is finished.
\begin{note}
In blocking with forward progress guarantee delegation in this context,
a thread of execution created by the library
is considered to have finished execution
as soon as it has finished the execution
of the particular element access function
that the invoking thread of execution logically depends on.
\end{note}
\pnum
The semantics of parallel algorithms invoked with an execution policy object of
\impldef{additional execution policies supported by parallel algorithms} type
are \impldef{semantics of parallel algorithms invoked with
imple\-men\-tation-defined execution policies}.
\rSec2[algorithms.parallel.exceptions]{Parallel algorithm exceptions}
\pnum
During the execution of a parallel algorithm,
if temporary memory resources are required for parallelization
and none are available, the algorithm throws a \tcode{bad_alloc} exception.
\pnum
During the execution of a parallel algorithm,
if the invocation of an element access function exits via an uncaught exception,
the behavior is determined by the \tcode{ExecutionPolicy}.
\rSec2[algorithms.parallel.overloads]{\tcode{ExecutionPolicy} algorithm overloads}
\pnum
Parallel algorithms are algorithm overloads.
Each parallel algorithm overload
has an additional template type parameter named \tcode{ExecutionPolicy},
which is the first template parameter.
Additionally, each parallel algorithm overload
has an additional function parameter of type \tcode{ExecutionPolicy\&\&},
which is the first function parameter.
\begin{note}
Not all algorithms have parallel algorithm overloads.
\end{note}
\pnum
Unless otherwise specified,
the semantics of \tcode{ExecutionPolicy} algorithm overloads
are identical to their overloads without.
\pnum
Unless otherwise specified,
the complexity requirements of \tcode{ExecutionPolicy} algorithm overloads
are relaxed from the complexity requirements of the overloads without
as follows:
when the guarantee says ``at most \placeholder{expr}'' or
``exactly \placeholder{expr}''
and does not specify the number of assignments or swaps, and
\placeholder{expr} is not already expressed with \bigoh{} notation,
the complexity of the algorithm shall be \bigoh{\placeholder{expr}}.
\pnum
Parallel algorithms shall not participate in overload resolution unless
\tcode{is_execution_policy_v<remove_cvref_t<ExecutionPolicy>>} is \tcode{true}.
\rSec1[algorithm.syn]{Header \tcode{<algorithm>} synopsis}
\indexhdr{algorithm}%
\begin{codeblock}
#include <initializer_list>
namespace std {
// \ref{alg.nonmodifying}, non-modifying sequence operations
// \ref{alg.all.of}, all of
template<class InputIterator, class Predicate>
constexpr bool all_of(InputIterator first, InputIterator last, Predicate pred);
template<class ExecutionPolicy, class ForwardIterator, class Predicate>
bool all_of(ExecutionPolicy&& exec, // see \ref{algorithms.parallel.overloads}
ForwardIterator first, ForwardIterator last, Predicate pred);
namespace ranges {
template<InputIterator I, Sentinel<I> S, class Proj = identity,
IndirectUnaryPredicate<projected<I, Proj>> Pred>
constexpr bool all_of(I first, S last, Pred pred, Proj proj = {});
template<InputRange R, class Proj = identity,
IndirectUnaryPredicate<projected<iterator_t<R>, Proj>> Pred>
constexpr bool all_of(R&& r, Pred pred, Proj proj = {});
}
// \ref{alg.any.of}, any of
template<class InputIterator, class Predicate>
constexpr bool any_of(InputIterator first, InputIterator last, Predicate pred);
template<class ExecutionPolicy, class ForwardIterator, class Predicate>
bool any_of(ExecutionPolicy&& exec, // see \ref{algorithms.parallel.overloads}
ForwardIterator first, ForwardIterator last, Predicate pred);
namespace ranges {
template<InputIterator I, Sentinel<I> S, class Proj = identity,
IndirectUnaryPredicate<projected<I, Proj>> Pred>
constexpr bool any_of(I first, S last, Pred pred, Proj proj = {});
template<InputRange R, class Proj = identity,
IndirectUnaryPredicate<projected<iterator_t<R>, Proj>> Pred>
constexpr bool any_of(R&& r, Pred pred, Proj proj = {});
}
// \ref{alg.none.of}, none of
template<class InputIterator, class Predicate>
constexpr bool none_of(InputIterator first, InputIterator last, Predicate pred);
template<class ExecutionPolicy, class ForwardIterator, class Predicate>
bool none_of(ExecutionPolicy&& exec, // see \ref{algorithms.parallel.overloads}
ForwardIterator first, ForwardIterator last, Predicate pred);
namespace ranges {
template<InputIterator I, Sentinel<I> S, class Proj = identity,
IndirectUnaryPredicate<projected<I, Proj>> Pred>
constexpr bool none_of(I first, S last, Pred pred, Proj proj = {});
template<InputRange R, class Proj = identity,
IndirectUnaryPredicate<projected<iterator_t<R>, Proj>> Pred>
constexpr bool none_of(R&& r, Pred pred, Proj proj = {});
}
// \ref{alg.foreach}, for each
template<class InputIterator, class Function>
constexpr Function for_each(InputIterator first, InputIterator last, Function f);
template<class ExecutionPolicy, class ForwardIterator, class Function>
void for_each(ExecutionPolicy&& exec, // see \ref{algorithms.parallel.overloads}
ForwardIterator first, ForwardIterator last, Function f);
namespace ranges {
template<class I, class F>
struct for_each_result {
[[no_unique_address]] I in;
[[no_unique_address]] F fun;
template<class I2, class F2>
requires ConvertibleTo<const I&, I2> && ConvertibleTo<const F&, F2>
operator for_each_result<I2, F2>() const & {
return {in, fun};
}
template<class I2, class F2>
requires ConvertibleTo<I, I2> && ConvertibleTo<F, F2>
operator for_each_result<I2, F2>() && {
return {std::move(in), std::move(fun)};
}
};
template<InputIterator I, Sentinel<I> S, class Proj = identity,
IndirectUnaryInvocable<projected<I, Proj>> Fun>
constexpr for_each_result<I, Fun>
for_each(I first, S last, Fun f, Proj proj = {});
template<InputRange R, class Proj = identity,
IndirectUnaryInvocable<projected<iterator_t<R>, Proj>> Fun>
constexpr for_each_result<safe_iterator_t<R>, Fun>
for_each(R&& r, Fun f, Proj proj = {});
}
template<class InputIterator, class Size, class Function>
constexpr InputIterator for_each_n(InputIterator first, Size n, Function f);
template<class ExecutionPolicy, class ForwardIterator, class Size, class Function>
ForwardIterator for_each_n(ExecutionPolicy&& exec, // see \ref{algorithms.parallel.overloads}
ForwardIterator first, Size n, Function f);
// \ref{alg.find}, find
template<class InputIterator, class T>
constexpr InputIterator find(InputIterator first, InputIterator last,
const T& value);
template<class ExecutionPolicy, class ForwardIterator, class T>
ForwardIterator find(ExecutionPolicy&& exec, // see \ref{algorithms.parallel.overloads}
ForwardIterator first, ForwardIterator last,
const T& value);
template<class InputIterator, class Predicate>
constexpr InputIterator find_if(InputIterator first, InputIterator last,
Predicate pred);
template<class ExecutionPolicy, class ForwardIterator, class Predicate>
ForwardIterator find_if(ExecutionPolicy&& exec, // see \ref{algorithms.parallel.overloads}
ForwardIterator first, ForwardIterator last,
Predicate pred);
template<class InputIterator, class Predicate>
constexpr InputIterator find_if_not(InputIterator first, InputIterator last,
Predicate pred);
template<class ExecutionPolicy, class ForwardIterator, class Predicate>
ForwardIterator find_if_not(ExecutionPolicy&& exec, // see \ref{algorithms.parallel.overloads}
ForwardIterator first, ForwardIterator last,
Predicate pred);
namespace ranges {
template<InputIterator I, Sentinel<I> S, class T, class Proj = identity>
requires IndirectRelation<ranges::equal_to, projected<I, Proj>, const T*>
constexpr I find(I first, S last, const T& value, Proj proj = {});
template<InputRange R, class T, class Proj = identity>
requires IndirectRelation<ranges::equal_to, projected<iterator_t<R>, Proj>, const T*>
constexpr safe_iterator_t<R>
find(R&& r, const T& value, Proj proj = {});
template<InputIterator I, Sentinel<I> S, class Proj = identity,
IndirectUnaryPredicate<projected<I, Proj>> Pred>
constexpr I find_if(I first, S last, Pred pred, Proj proj = {});
template<InputRange R, class Proj = identity,
IndirectUnaryPredicate<projected<iterator_t<R>, Proj>> Pred>
constexpr safe_iterator_t<R>
find_if(R&& r, Pred pred, Proj proj = {});
template<InputIterator I, Sentinel<I> S, class Proj = identity,
IndirectUnaryPredicate<projected<I, Proj>> Pred>
constexpr I find_if_not(I first, S last, Pred pred, Proj proj = {});
template<InputRange R, class Proj = identity,
IndirectUnaryPredicate<projected<iterator_t<R>, Proj>> Pred>
constexpr safe_iterator_t<R>
find_if_not(R&& r, Pred pred, Proj proj = {});
}
// \ref{alg.find.end}, find end
template<class ForwardIterator1, class ForwardIterator2>
constexpr ForwardIterator1
find_end(ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2);
template<class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
constexpr ForwardIterator1
find_end(ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
BinaryPredicate pred);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2>
ForwardIterator1
find_end(ExecutionPolicy&& exec, // see \ref{algorithms.parallel.overloads}
ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2);
template<class ExecutionPolicy, class ForwardIterator1,
class ForwardIterator2, class BinaryPredicate>
ForwardIterator1
find_end(ExecutionPolicy&& exec, // see \ref{algorithms.parallel.overloads}
ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
BinaryPredicate pred);
namespace ranges {
template<ForwardIterator I1, Sentinel<I1> S1, ForwardIterator I2, Sentinel<I2> S2,
class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
requires IndirectlyComparable<I1, I2, Pred, Proj1, Proj2>
constexpr subrange<I1>
find_end(I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = {},
Proj1 proj1 = {}, Proj2 proj2 = {});
template<ForwardRange R1, ForwardRange R2,
class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
requires IndirectlyComparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2>
constexpr safe_subrange_t<R1>
find_end(R1&& r1, R2&& r2, Pred pred = {},
Proj1 proj1 = {}, Proj2 proj2 = {});
}
// \ref{alg.find.first.of}, find first
template<class InputIterator, class ForwardIterator>
constexpr InputIterator
find_first_of(InputIterator first1, InputIterator last1,
ForwardIterator first2, ForwardIterator last2);
template<class InputIterator, class ForwardIterator, class BinaryPredicate>
constexpr InputIterator
find_first_of(InputIterator first1, InputIterator last1,
ForwardIterator first2, ForwardIterator last2,
BinaryPredicate pred);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2>
ForwardIterator1
find_first_of(ExecutionPolicy&& exec, // see \ref{algorithms.parallel.overloads}
ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2);
template<class ExecutionPolicy, class ForwardIterator1,
class ForwardIterator2, class BinaryPredicate>
ForwardIterator1
find_first_of(ExecutionPolicy&& exec, // see \ref{algorithms.parallel.overloads}
ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
BinaryPredicate pred);
namespace ranges {
template<InputIterator I1, Sentinel<I1> S1, ForwardIterator I2, Sentinel<I2> S2,
class Proj1 = identity, class Proj2 = identity,
IndirectRelation<projected<I1, Proj1>,
projected<I2, Proj2>> Pred = ranges::equal_to>
constexpr I1 find_first_of(I1 first1, S1 last1, I2 first2, S2 last2,
Pred pred = {},
Proj1 proj1 = {}, Proj2 proj2 = {});
template<InputRange R1, ForwardRange R2, class Proj1 = identity, class Proj2 = identity,
IndirectRelation<projected<iterator_t<R1>, Proj1>,
projected<iterator_t<R2>, Proj2>> Pred = ranges::equal_to>
constexpr safe_iterator_t<R1>
find_first_of(R1&& r1, R2&& r2,
Pred pred = {},
Proj1 proj1 = {}, Proj2 proj2 = {});
}
// \ref{alg.adjacent.find}, adjacent find
template<class ForwardIterator>
constexpr ForwardIterator
adjacent_find(ForwardIterator first, ForwardIterator last);
template<class ForwardIterator, class BinaryPredicate>
constexpr ForwardIterator
adjacent_find(ForwardIterator first, ForwardIterator last,
BinaryPredicate pred);
template<class ExecutionPolicy, class ForwardIterator>
ForwardIterator
adjacent_find(ExecutionPolicy&& exec, // see \ref{algorithms.parallel.overloads}
ForwardIterator first, ForwardIterator last);
template<class ExecutionPolicy, class ForwardIterator, class BinaryPredicate>
ForwardIterator
adjacent_find(ExecutionPolicy&& exec, // see \ref{algorithms.parallel.overloads}
ForwardIterator first, ForwardIterator last,
BinaryPredicate pred);
namespace ranges {
template<ForwardIterator I, Sentinel<I> S, class Proj = identity,
IndirectRelation<projected<I, Proj>> Pred = ranges::equal_to>
constexpr I adjacent_find(I first, S last, Pred pred = {},
Proj proj = {});
template<ForwardRange R, class Proj = identity,
IndirectRelation<projected<iterator_t<R>, Proj>> Pred = ranges::equal_to>
constexpr safe_iterator_t<R>
adjacent_find(R&& r, Pred pred = {}, Proj proj = {});
}
// \ref{alg.count}, count
template<class InputIterator, class T>
constexpr typename iterator_traits<InputIterator>::difference_type
count(InputIterator first, InputIterator last, const T& value);
template<class ExecutionPolicy, class ForwardIterator, class T>
typename iterator_traits<ForwardIterator>::difference_type
count(ExecutionPolicy&& exec, // see \ref{algorithms.parallel.overloads}
ForwardIterator first, ForwardIterator last, const T& value);
template<class InputIterator, class Predicate>
constexpr typename iterator_traits<InputIterator>::difference_type
count_if(InputIterator first, InputIterator last, Predicate pred);
template<class ExecutionPolicy, class ForwardIterator, class Predicate>
typename iterator_traits<ForwardIterator>::difference_type
count_if(ExecutionPolicy&& exec, // see \ref{algorithms.parallel.overloads}
ForwardIterator first, ForwardIterator last, Predicate pred);
namespace ranges {
template<InputIterator I, Sentinel<I> S, class T, class Proj = identity>
requires IndirectRelation<ranges::equal_to, projected<I, Proj>, const T*>
constexpr iter_difference_t<I>
count(I first, S last, const T& value, Proj proj = {});
template<InputRange R, class T, class Proj = identity>
requires IndirectRelation<ranges::equal_to, projected<iterator_t<R>, Proj>, const T*>
constexpr iter_difference_t<iterator_t<R>>
count(R&& r, const T& value, Proj proj = {});
template<InputIterator I, Sentinel<I> S, class Proj = identity,
IndirectUnaryPredicate<projected<I, Proj>> Pred>
constexpr iter_difference_t<I>
count_if(I first, S last, Pred pred, Proj proj = {});
template<InputRange R, class Proj = identity,
IndirectUnaryPredicate<projected<iterator_t<R>, Proj>> Pred>
constexpr iter_difference_t<iterator_t<R>>
count_if(R&& r, Pred pred, Proj proj = {});
}
// \ref{mismatch}, mismatch
template<class InputIterator1, class InputIterator2>
constexpr pair<InputIterator1, InputIterator2>
mismatch(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2);
template<class InputIterator1, class InputIterator2, class BinaryPredicate>
constexpr pair<InputIterator1, InputIterator2>
mismatch(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, BinaryPredicate pred);
template<class InputIterator1, class InputIterator2>
constexpr pair<InputIterator1, InputIterator2>
mismatch(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2);
template<class InputIterator1, class InputIterator2, class BinaryPredicate>
constexpr pair<InputIterator1, InputIterator2>
mismatch(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
BinaryPredicate pred);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2>
pair<ForwardIterator1, ForwardIterator2>
mismatch(ExecutionPolicy&& exec, // see \ref{algorithms.parallel.overloads}
ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
class BinaryPredicate>
pair<ForwardIterator1, ForwardIterator2>
mismatch(ExecutionPolicy&& exec, // see \ref{algorithms.parallel.overloads}
ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, BinaryPredicate pred);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2>
pair<ForwardIterator1, ForwardIterator2>
mismatch(ExecutionPolicy&& exec, // see \ref{algorithms.parallel.overloads}
ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
class BinaryPredicate>
pair<ForwardIterator1, ForwardIterator2>
mismatch(ExecutionPolicy&& exec, // see \ref{algorithms.parallel.overloads}
ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
BinaryPredicate pred);
namespace ranges {
template<class I1, class I2>
struct mismatch_result {
[[no_unique_address]] I1 in1;
[[no_unique_address]] I2 in2;
template<class II1, class II2>
requires ConvertibleTo<const I1&, II1> && ConvertibleTo<const I2&, II2>
operator mismatch_result<II1, II2>() const & {
return {in1, in2};
}
template<class II1, class II2>
requires ConvertibleTo<I1, II1> && ConvertibleTo<I2, II2>
operator mismatch_result<II1, II2>() && {
return {std::move(in1), std::move(in2)};
}
};
template<InputIterator I1, Sentinel<I1> S1, InputIterator I2, Sentinel<I2> S2,
class Proj1 = identity, class Proj2 = identity,
IndirectRelation<projected<I1, Proj1>,
projected<I2, Proj2>> Pred = ranges::equal_to>
constexpr mismatch_result<I1, I2>
mismatch(I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = {},
Proj1 proj1 = {}, Proj2 proj2 = {});
template<InputRange R1, InputRange R2,
class Proj1 = identity, class Proj2 = identity,
IndirectRelation<projected<iterator_t<R1>, Proj1>,
projected<iterator_t<R2>, Proj2>> Pred = ranges::equal_to>
constexpr mismatch_result<safe_iterator_t<R1>, safe_iterator_t<R2>>
mismatch(R1&& r1, R2&& r2, Pred pred = {},
Proj1 proj1 = {}, Proj2 proj2 = {});
}
// \ref{alg.equal}, equal
template<class InputIterator1, class InputIterator2>
constexpr bool equal(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2);
template<class InputIterator1, class InputIterator2, class BinaryPredicate>
constexpr bool equal(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, BinaryPredicate pred);
template<class InputIterator1, class InputIterator2>
constexpr bool equal(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2);
template<class InputIterator1, class InputIterator2, class BinaryPredicate>
constexpr bool equal(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
BinaryPredicate pred);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2>
bool equal(ExecutionPolicy&& exec, // see \ref{algorithms.parallel.overloads}
ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
class BinaryPredicate>
bool equal(ExecutionPolicy&& exec, // see \ref{algorithms.parallel.overloads}
ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, BinaryPredicate pred);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2>
bool equal(ExecutionPolicy&& exec, // see \ref{algorithms.parallel.overloads}
ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
class BinaryPredicate>
bool equal(ExecutionPolicy&& exec, // see \ref{algorithms.parallel.overloads}
ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
BinaryPredicate pred);