From Jason Turner

[alg.nonmodifying]

C++23 → Trunk 47.6 KB 532 lines
Current Draft | LaTeX Source
Archived: C++23
Markdown: C++23 | Trunk
Explore in Adventure Game

Diff to HTML by rtfpessoa

Files changed (1) hide show
  1. tmp/tmp52o991jg/{from.md → to.md} +429 -69
tmp/tmp52o991jg/{from.md → to.md} RENAMED
@@ -13,10 +13,17 @@ template<input_iterator I, sentinel_for<I> S, class Proj = identity,
13
  indirect_unary_predicate<projected<I, Proj>> Pred>
14
  constexpr bool ranges::all_of(I first, S last, Pred pred, Proj proj = {});
15
  template<input_range R, class Proj = identity,
16
  indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
17
  constexpr bool ranges::all_of(R&& r, Pred pred, Proj proj = {});
 
 
 
 
 
 
 
18
  ```
19
 
20
  Let E be:
21
 
22
  - `pred(*i)` for the overloads in namespace `std`;
@@ -42,10 +49,17 @@ template<input_iterator I, sentinel_for<I> S, class Proj = identity,
42
  indirect_unary_predicate<projected<I, Proj>> Pred>
43
  constexpr bool ranges::any_of(I first, S last, Pred pred, Proj proj = {});
44
  template<input_range R, class Proj = identity,
45
  indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
46
  constexpr bool ranges::any_of(R&& r, Pred pred, Proj proj = {});
 
 
 
 
 
 
 
47
  ```
48
 
49
  Let E be:
50
 
51
  - `pred(*i)` for the overloads in namespace `std`;
@@ -71,10 +85,17 @@ template<input_iterator I, sentinel_for<I> S, class Proj = identity,
71
  indirect_unary_predicate<projected<I, Proj>> Pred>
72
  constexpr bool ranges::none_of(I first, S last, Pred pred, Proj proj = {});
73
  template<input_range R, class Proj = identity,
74
  indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
75
  constexpr bool ranges::none_of(R&& r, Pred pred, Proj proj = {});
 
 
 
 
 
 
 
76
  ```
77
 
78
  Let E be:
79
 
80
  - `pred(*i)` for the overloads in namespace `std`;
@@ -88,20 +109,36 @@ Let E be:
88
  any projection.
89
 
90
  ### Contains <a id="alg.contains">[[alg.contains]]</a>
91
 
92
  ``` cpp
93
- template<input_iterator I, sentinel_for<I> S, class T, class Proj = identity>
 
94
  requires indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T*>
95
  constexpr bool ranges::contains(I first, S last, const T& value, Proj proj = {});
96
- template<input_range R, class T, class Proj = identity>
97
  requires indirect_binary_predicate<ranges::equal_to, projected<iterator_t<R>, Proj>, const T*>
98
  constexpr bool ranges::contains(R&& r, const T& value, Proj proj = {});
99
  ```
100
 
101
  *Returns:* `ranges::find(std::move(first), last, value, proj) != last`.
102
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
103
  ``` cpp
104
  template<forward_iterator I1, sentinel_for<I1> S1,
105
  forward_iterator I2, sentinel_for<I2> S2,
106
  class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
107
  requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
@@ -113,11 +150,36 @@ template<forward_range R1, forward_range R2,
113
  constexpr bool ranges::contains_subrange(R1&& r1, R2&& r2, Pred pred = {},
114
  Proj1 proj1 = {}, Proj2 proj2 = {});
115
  ```
116
 
117
  *Returns:*
118
- `first2 == last2 || !ranges::search(first1, last1, first2, last2, pred, proj1, proj2).empty()`.
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
119
 
120
  ### For each <a id="alg.foreach">[[alg.foreach]]</a>
121
 
122
  ``` cpp
123
  template<class InputIterator, class Function>
@@ -197,10 +259,43 @@ the range \[`first`, `last`), starting from `first` and proceeding to
197
  *Remarks:* If `f` returns a result, the result is ignored.
198
 
199
  [*Note 6*: The overloads in namespace `ranges` require `Fun` to model
200
  `copy_constructible`. — *end note*]
201
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
202
  ``` cpp
203
  template<class InputIterator, class Size, class Function>
204
  constexpr InputIterator for_each_n(InputIterator first, Size n, Function f);
205
  ```
206
 
@@ -208,17 +303,17 @@ template<class InputIterator, class Size, class Function>
208
  type [[conv.integral]], [[class.conv]].
209
 
210
  *Preconditions:* `n >= 0` is `true`. `Function` meets the
211
  *Cpp17MoveConstructible* requirements.
212
 
213
- [*Note 7*: `Function` need not meet the requirements of
214
  *Cpp17CopyConstructible*. — *end note*]
215
 
216
  *Effects:* Applies `f` to the result of dereferencing every iterator in
217
  the range \[`first`, `first + n`) in order.
218
 
219
- [*Note 8*: If the type of `first` meets the requirements of a mutable
220
  iterator, `f` can apply non-constant functions through the dereferenced
221
  iterator. — *end note*]
222
 
223
  *Returns:* `first + n`.
224
 
@@ -237,11 +332,11 @@ type [[conv.integral]], [[class.conv]].
237
  *Cpp17CopyConstructible* requirements.
238
 
239
  *Effects:* Applies `f` to the result of dereferencing every iterator in
240
  the range \[`first`, `first + n`).
241
 
242
- [*Note 9*: If the type of `first` meets the requirements of a mutable
243
  iterator, `f` can apply non-constant functions through the dereferenced
244
  iterator. — *end note*]
245
 
246
  *Returns:* `first + n`.
247
 
@@ -260,27 +355,56 @@ template<input_iterator I, class Proj = identity,
260
  *Preconditions:* `n >= 0` is `true`.
261
 
262
  *Effects:* Calls `invoke(f, invoke(proj, *i))` for every iterator `i` in
263
  the range \[`first`, `first + n`) in order.
264
 
265
- [*Note 10*: If the result of `invoke(proj, *i)` is a mutable reference,
266
  `f` can apply non-constant functions. — *end note*]
267
 
268
  *Returns:* `{first + n, std::move(f)}`.
269
 
270
  *Remarks:* If `f` returns a result, the result is ignored.
271
 
272
- [*Note 11*: The overload in namespace `ranges` requires `Fun` to model
273
  `copy_constructible`. — *end note*]
274
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
275
  ### Find <a id="alg.find">[[alg.find]]</a>
276
 
277
  ``` cpp
278
- template<class InputIterator, class T>
279
  constexpr InputIterator find(InputIterator first, InputIterator last,
280
  const T& value);
281
- template<class ExecutionPolicy, class ForwardIterator, class T>
 
282
  ForwardIterator find(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last,
283
  const T& value);
284
 
285
  template<class InputIterator, class Predicate>
286
  constexpr InputIterator find_if(InputIterator first, InputIterator last,
@@ -295,31 +419,58 @@ template<class InputIterator, class Predicate>
295
  template<class ExecutionPolicy, class ForwardIterator, class Predicate>
296
  ForwardIterator find_if_not(ExecutionPolicy&& exec,
297
  ForwardIterator first, ForwardIterator last,
298
  Predicate pred);
299
 
300
- template<input_iterator I, sentinel_for<I> S, class T, class Proj = identity>
 
301
  requires indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T*>
302
  constexpr I ranges::find(I first, S last, const T& value, Proj proj = {});
303
- template<input_range R, class T, class Proj = identity>
304
  requires indirect_binary_predicate<ranges::equal_to, projected<iterator_t<R>, Proj>, const T*>
305
  constexpr borrowed_iterator_t<R>
306
  ranges::find(R&& r, const T& value, Proj proj = {});
 
 
 
 
 
 
 
 
 
 
 
307
  template<input_iterator I, sentinel_for<I> S, class Proj = identity,
308
  indirect_unary_predicate<projected<I, Proj>> Pred>
309
  constexpr I ranges::find_if(I first, S last, Pred pred, Proj proj = {});
310
  template<input_range R, class Proj = identity,
311
  indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
312
  constexpr borrowed_iterator_t<R>
313
  ranges::find_if(R&& r, Pred pred, Proj proj = {});
 
 
 
 
 
 
 
 
314
  template<input_iterator I, sentinel_for<I> S, class Proj = identity,
315
  indirect_unary_predicate<projected<I, Proj>> Pred>
316
  constexpr I ranges::find_if_not(I first, S last, Pred pred, Proj proj = {});
317
  template<input_range R, class Proj = identity,
318
  indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
319
  constexpr borrowed_iterator_t<R>
320
  ranges::find_if_not(R&& r, Pred pred, Proj proj = {});
 
 
 
 
 
 
 
321
  ```
322
 
323
  Let E be:
324
 
325
  - `*i == value` for `find`;
@@ -336,28 +487,58 @@ which E is `true`. Returns `last` if no such iterator is found.
336
  predicate and any projection.
337
 
338
  ### Find last <a id="alg.find.last">[[alg.find.last]]</a>
339
 
340
  ``` cpp
341
- template<forward_iterator I, sentinel_for<I> S, class T, class Proj = identity>
 
342
  requires indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T*>
343
  constexpr subrange<I> ranges::find_last(I first, S last, const T& value, Proj proj = {});
344
- template<forward_range R, class T, class Proj = identity>
 
345
  requires indirect_binary_predicate<ranges::equal_to, projected<iterator_t<R>, Proj>, const T*>
346
  constexpr borrowed_subrange_t<R> ranges::find_last(R&& r, const T& value, Proj proj = {});
 
 
 
 
 
 
 
 
 
 
 
347
  template<forward_iterator I, sentinel_for<I> S, class Proj = identity,
348
  indirect_unary_predicate<projected<I, Proj>> Pred>
349
  constexpr subrange<I> ranges::find_last_if(I first, S last, Pred pred, Proj proj = {});
350
  template<forward_range R, class Proj = identity,
351
  indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
352
  constexpr borrowed_subrange_t<R> ranges::find_last_if(R&& r, Pred pred, Proj proj = {});
 
 
 
 
 
 
 
 
 
353
  template<forward_iterator I, sentinel_for<I> S, class Proj = identity,
354
  indirect_unary_predicate<projected<I, Proj>> Pred>
355
  constexpr subrange<I> ranges::find_last_if_not(I first, S last, Pred pred, Proj proj = {});
356
  template<forward_range R, class Proj = identity,
357
  indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
358
  constexpr borrowed_subrange_t<R> ranges::find_last_if_not(R&& r, Pred pred, Proj proj = {});
 
 
 
 
 
 
 
 
359
  ```
360
 
361
  Let E be:
362
 
363
  - `bool(invoke(proj, *i) == value)` for `ranges::find_last`;
@@ -409,10 +590,24 @@ template<forward_range R1, forward_range R2,
409
  class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
410
  requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2>
411
  constexpr borrowed_subrange_t<R1>
412
  ranges::find_end(R1&& r1, R2&& r2, Pred pred = {},
413
  Proj1 proj1 = {}, Proj2 proj2 = {});
 
 
 
 
 
 
 
 
 
 
 
 
 
 
414
  ```
415
 
416
  Let:
417
 
418
  - `pred` be `equal_to{}` for the overloads with no parameter `pred`;
@@ -436,11 +631,11 @@ Let:
436
 
437
  *Complexity:* At most
438
  `(last2 - first2) * (last1 - first1 - (last2 - first2) + 1)`
439
  applications of the corresponding predicate and any projections.
440
 
441
- ### Find first <a id="alg.find.first.of">[[alg.find.first.of]]</a>
442
 
443
  ``` cpp
444
  template<class InputIterator, class ForwardIterator>
445
  constexpr InputIterator
446
  find_first_of(InputIterator first1, InputIterator last1,
@@ -476,10 +671,23 @@ template<input_range R1, forward_range R2,
476
  requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2>
477
  constexpr borrowed_iterator_t<R1>
478
  ranges::find_first_of(R1&& r1, R2&& r2,
479
  Pred pred = {},
480
  Proj1 proj1 = {}, Proj2 proj2 = {});
 
 
 
 
 
 
 
 
 
 
 
 
 
481
  ```
482
 
483
  Let E be:
484
 
485
  - `*i == *j` for the overloads with no parameter `pred`;
@@ -493,12 +701,12 @@ Let E be:
493
  *Returns:* The first iterator `i` in the range \[`first1`, `last1`) such
494
  that for some iterator `j` in the range \[`first2`, `last2`) E holds.
495
  Returns `last1` if \[`first2`, `last2`) is empty or if no such iterator
496
  is found.
497
 
498
- *Complexity:* At most `(last1-first1) * (last2-first2)` applications of
499
- the corresponding predicate and any projections.
500
 
501
  ### Adjacent find <a id="alg.adjacent.find">[[alg.adjacent.find]]</a>
502
 
503
  ``` cpp
504
  template<class ForwardIterator>
@@ -525,10 +733,21 @@ template<forward_iterator I, sentinel_for<I> S, class Proj = identity,
525
  constexpr I ranges::adjacent_find(I first, S last, Pred pred = {}, Proj proj = {});
526
  template<forward_range R, class Proj = identity,
527
  indirect_binary_predicate<projected<iterator_t<R>, Proj>,
528
  projected<iterator_t<R>, Proj>> Pred = ranges::equal_to>
529
  constexpr borrowed_iterator_t<R> ranges::adjacent_find(R&& r, Pred pred = {}, Proj proj = {});
 
 
 
 
 
 
 
 
 
 
 
530
  ```
531
 
532
  Let E be:
533
 
534
  - `*i == *(i + 1)` for the overloads with no parameter `pred`;
@@ -539,25 +758,25 @@ Let E be:
539
 
540
  *Returns:* The first iterator `i` such that both `i` and `i + 1` are in
541
  the range \[`first`, `last`) for which E holds. Returns `last` if no
542
  such iterator is found.
543
 
544
- *Complexity:* For the overloads with no `ExecutionPolicy`, exactly
545
  $$\min(\texttt{(i - first) + 1}, \ \texttt{(last - first) - 1})$$
546
  applications of the corresponding predicate, where `i` is
547
- `adjacent_find`’s return value. For the overloads with an
548
- `ExecutionPolicy`, 𝑂(`last - first`) applications of the corresponding
549
- predicate, and no more than twice as many applications of any
550
- projection.
551
 
552
  ### Count <a id="alg.count">[[alg.count]]</a>
553
 
554
  ``` cpp
555
- template<class InputIterator, class T>
556
  constexpr typename iterator_traits<InputIterator>::difference_type
557
  count(InputIterator first, InputIterator last, const T& value);
558
- template<class ExecutionPolicy, class ForwardIterator, class T>
 
559
  typename iterator_traits<ForwardIterator>::difference_type
560
  count(ExecutionPolicy&& exec,
561
  ForwardIterator first, ForwardIterator last, const T& value);
562
 
563
  template<class InputIterator, class Predicate>
@@ -566,26 +785,48 @@ template<class InputIterator, class Predicate>
566
  template<class ExecutionPolicy, class ForwardIterator, class Predicate>
567
  typename iterator_traits<ForwardIterator>::difference_type
568
  count_if(ExecutionPolicy&& exec,
569
  ForwardIterator first, ForwardIterator last, Predicate pred);
570
 
571
- template<input_iterator I, sentinel_for<I> S, class T, class Proj = identity>
 
572
  requires indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T*>
573
  constexpr iter_difference_t<I>
574
  ranges::count(I first, S last, const T& value, Proj proj = {});
575
- template<input_range R, class T, class Proj = identity>
576
  requires indirect_binary_predicate<ranges::equal_to, projected<iterator_t<R>, Proj>, const T*>
577
  constexpr range_difference_t<R>
578
  ranges::count(R&& r, const T& value, Proj proj = {});
 
 
 
 
 
 
 
 
 
 
 
 
579
  template<input_iterator I, sentinel_for<I> S, class Proj = identity,
580
  indirect_unary_predicate<projected<I, Proj>> Pred>
581
  constexpr iter_difference_t<I>
582
  ranges::count_if(I first, S last, Pred pred, Proj proj = {});
583
  template<input_range R, class Proj = identity,
584
  indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
585
  constexpr range_difference_t<R>
586
  ranges::count_if(R&& r, Pred pred, Proj proj = {});
 
 
 
 
 
 
 
 
 
587
  ```
588
 
589
  Let E be:
590
 
591
  - `*i == value` for the overloads with no parameter `pred` or `proj`;
@@ -600,11 +841,11 @@ Let E be:
600
  `last`) for which E holds.
601
 
602
  *Complexity:* Exactly `last - first` applications of the corresponding
603
  predicate and any projection.
604
 
605
- ### Mismatch <a id="mismatch">[[mismatch]]</a>
606
 
607
  ``` cpp
608
  template<class InputIterator1, class InputIterator2>
609
  constexpr pair<InputIterator1, InputIterator2>
610
  mismatch(InputIterator1 first1, InputIterator1 last1,
@@ -661,14 +902,28 @@ template<input_range R1, input_range R2,
661
  class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
662
  requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2>
663
  constexpr ranges::mismatch_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>>
664
  ranges::mismatch(R1&& r1, R2&& r2, Pred pred = {},
665
  Proj1 proj1 = {}, Proj2 proj2 = {});
 
 
 
 
 
 
 
 
 
 
 
 
 
 
666
  ```
667
 
668
- Let `last2` be `first2 + (last1 - first1)` for the overloads with no
669
- parameter `last2` or `r2`.
670
 
671
  Let E be:
672
 
673
  - `!(*(first1 + n) == *(first2 + n))` for the overloads with no
674
  parameter `pred`;
@@ -735,16 +990,28 @@ template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for
735
  template<input_range R1, input_range R2, class Pred = ranges::equal_to,
736
  class Proj1 = identity, class Proj2 = identity>
737
  requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2>
738
  constexpr bool ranges::equal(R1&& r1, R2&& r2, Pred pred = {},
739
  Proj1 proj1 = {}, Proj2 proj2 = {});
 
 
 
 
 
 
 
 
 
 
 
 
740
  ```
741
 
742
  Let:
743
 
744
- - `last2` be `first2 + (last1 - first1)` for the overloads with no
745
- parameter `last2` or `r2`;
746
  - `pred` be `equal_to{}` for the overloads with no parameter `pred`;
747
  - E be:
748
  - `pred(*i, *(first2 + (i - first1)))` for the overloads with no
749
  parameter `proj1`;
750
  - `invoke(pred, invoke(proj1, *i), invoke(proj2, *(first2 + (i - first1))))`
@@ -760,24 +1027,20 @@ Otherwise return `true` if E holds for every iterator `i` in the range
760
  *Cpp17RandomAccessIterator* requirements [[random.access.iterators]]
761
  and `last1 - first1 != last2 - first2` for the overloads in namespace
762
  `std`;
763
  - the types of `first1`, `last1`, `first2`, and `last2` pairwise model
764
  `sized_sentinel_for` [[iterator.concept.sizedsentinel]] and
765
- `last1 - first1 != last2 - first2` for the first overload in namespace
766
- `ranges`,
767
  - `R1` and `R2` each model `sized_range` and
768
- `ranges::distance(r1) != ranges::distance(r2)` for the second overload
769
- in namespace `ranges`,
770
 
771
  then no applications of the corresponding predicate and each projection;
772
- otherwise,
773
-
774
- - For the overloads with no `ExecutionPolicy`, at most
775
- min(`last1 - first1`, `last2 - first2`) applications of the
776
- corresponding predicate and any projections.
777
- - For the overloads with an `ExecutionPolicy`, 𝑂(min(`last1 - first1`,
778
-  `last2 - first2`)) applications of the corresponding predicate.
779
 
780
  ### Is permutation <a id="alg.is.permutation">[[alg.is.permutation]]</a>
781
 
782
  ``` cpp
783
  template<class ForwardIterator1, class ForwardIterator2>
@@ -841,11 +1104,11 @@ Otherwise return `true` if there exists a permutation of the elements in
841
  the range \[`first2`, `last2`), bounded by \[`pfirst`, `plast`), such
842
  that `ranges::equal(first1, last1, pfirst, plast, pred, proj1, proj2)`
843
  returns `true`; otherwise, returns `false`.
844
 
845
  *Complexity:* No applications of the corresponding predicate and
846
- projections if:
847
 
848
  - for the first overload,
849
  - `S1` and `I1` model `sized_sentinel_for<S1, I1>`,
850
  - `S2` and `I2` model `sized_sentinel_for<S2, I2>`, and
851
  - `last1 - first1 != last2 - first2`;
@@ -885,12 +1148,13 @@ template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
885
  ForwardIterator2 first2, ForwardIterator2 last2,
886
  BinaryPredicate pred);
887
  ```
888
 
889
  *Returns:* The first iterator `i` in the range \[`first1`,
890
- `last1 - (last2-first2)`) such that for every non-negative integer `n`
891
- less than `last2 - first2` the following corresponding conditions hold:
 
892
  `*(i + n) == *(first2 + n), pred(*(i + n), *(first2 + n)) != false`.
893
  Returns `first1` if \[`first2`, `last2`) is empty, otherwise returns
894
  `last1` if no such iterator is found.
895
 
896
  *Complexity:* At most `(last1 - first1) * (last2 - first2)` applications
@@ -908,16 +1172,30 @@ template<forward_range R1, forward_range R2, class Pred = ranges::equal_to,
908
  class Proj1 = identity, class Proj2 = identity>
909
  requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2>
910
  constexpr borrowed_subrange_t<R1>
911
  ranges::search(R1&& r1, R2&& r2, Pred pred = {},
912
  Proj1 proj1 = {}, Proj2 proj2 = {});
 
 
 
 
 
 
 
 
 
 
 
 
 
 
913
  ```
914
 
915
  *Returns:*
916
 
917
  - `{i, i + (last2 - first2)}`, where `i` is the first iterator in the
918
- range \[`first1`, `last1 - (last2 - first2)`) such that for every
919
  non-negative integer `n` less than `last2 - first2` the condition
920
  ``` cpp
921
  bool(invoke(pred, invoke(proj1, *(i + n)), invoke(proj2, *(first2 + n))))
922
  ```
923
 
@@ -926,27 +1204,29 @@ template<forward_range R1, forward_range R2, class Pred = ranges::equal_to,
926
 
927
  *Complexity:* At most `(last1 - first1) * (last2 - first2)` applications
928
  of the corresponding predicate and projections.
929
 
930
  ``` cpp
931
- template<class ForwardIterator, class Size, class T>
932
  constexpr ForwardIterator
933
  search_n(ForwardIterator first, ForwardIterator last,
934
  Size count, const T& value);
935
- template<class ExecutionPolicy, class ForwardIterator, class Size, class T>
 
936
  ForwardIterator
937
  search_n(ExecutionPolicy&& exec,
938
  ForwardIterator first, ForwardIterator last,
939
  Size count, const T& value);
940
 
941
- template<class ForwardIterator, class Size, class T,
942
  class BinaryPredicate>
943
  constexpr ForwardIterator
944
  search_n(ForwardIterator first, ForwardIterator last,
945
  Size count, const T& value,
946
  BinaryPredicate pred);
947
- template<class ExecutionPolicy, class ForwardIterator, class Size, class T,
 
948
  class BinaryPredicate>
949
  ForwardIterator
950
  search_n(ExecutionPolicy&& exec,
951
  ForwardIterator first, ForwardIterator last,
952
  Size count, const T& value,
@@ -954,36 +1234,53 @@ template<class ExecutionPolicy, class ForwardIterator, class Size, class T,
954
  ```
955
 
956
  *Mandates:* The type `Size` is convertible to an integral
957
  type [[conv.integral]], [[class.conv]].
958
 
959
- *Returns:* The first iterator `i` in the range \[`first`, `last-count`)
960
- such that for every non-negative integer `n` less than `count` the
961
- following corresponding conditions hold:
962
- `*(i + n) == value, pred(*(i + n), value) != false`. Returns `last` if
963
- no such iterator is found.
 
 
964
 
965
  *Complexity:* At most `last - first` applications of the corresponding
966
  predicate.
967
 
968
  ``` cpp
969
- template<forward_iterator I, sentinel_for<I> S, class T,
970
- class Pred = ranges::equal_to, class Proj = identity>
 
971
  requires indirectly_comparable<I, const T*, Pred, Proj>
972
  constexpr subrange<I>
973
  ranges::search_n(I first, S last, iter_difference_t<I> count,
974
  const T& value, Pred pred = {}, Proj proj = {});
975
- template<forward_range R, class T, class Pred = ranges::equal_to,
976
- class Proj = identity>
977
  requires indirectly_comparable<iterator_t<R>, const T*, Pred, Proj>
978
  constexpr borrowed_subrange_t<R>
979
  ranges::search_n(R&& r, range_difference_t<R> count,
980
  const T& value, Pred pred = {}, Proj proj = {});
 
 
 
 
 
 
 
 
 
 
 
 
 
 
981
  ```
982
 
983
  *Returns:* `{i, i + count}` where `i` is the first iterator in the range
984
- \[`first`, `last - count`) such that for every non-negative integer `n`
985
  less than `count`, the following condition holds:
986
  `invoke(pred, invoke(proj, *(i + n)), value)`. Returns `{last, last}` if
987
  no such iterator is found.
988
 
989
  *Complexity:* At most `last - first` applications of the corresponding
@@ -1020,10 +1317,32 @@ template<input_range R1, input_range R2, class Pred = ranges::equal_to, class Pr
1020
  ``` cpp
1021
  ranges::mismatch(std::move(first1), last1, std::move(first2), last2,
1022
  pred, proj1, proj2).in2 == last2
1023
  ```
1024
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1025
  ### Ends with <a id="alg.ends.with">[[alg.ends.with]]</a>
1026
 
1027
  ``` cpp
1028
  template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2,
1029
  class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
@@ -1034,17 +1353,35 @@ template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for
1034
  Proj1 proj1 = {}, Proj2 proj2 = {});
1035
  ```
1036
 
1037
  Let `N1` be `last1 - first1` and `N2` be `last2 - first2`.
1038
 
1039
- *Returns:* `false` if `N1` < `N2`, otherwise
1040
 
1041
  ``` cpp
1042
  ranges::equal(std::move(first1) + (N1 - N2), last1, std::move(first2), last2,
1043
  pred, proj1, proj2)
1044
  ```
1045
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1046
  ``` cpp
1047
  template<input_range R1, input_range R2, class Pred = ranges::equal_to, class Proj1 = identity,
1048
  class Proj2 = identity>
1049
  requires (forward_range<R1> || sized_range<R1>) &&
1050
  (forward_range<R2> || sized_range<R2>) &&
@@ -1053,22 +1390,44 @@ template<input_range R1, input_range R2, class Pred = ranges::equal_to, class Pr
1053
  Proj1 proj1 = {}, Proj2 proj2 = {});
1054
  ```
1055
 
1056
  Let `N1` be `ranges::distance(r1)` and `N2` be `ranges::distance(r2)`.
1057
 
1058
- *Returns:* `false` if `N1` < `N2`, otherwise
1059
 
1060
  ``` cpp
1061
- ranges::equal(ranges::drop_view(ranges::ref_view(r1), N1 - N2), r2, pred, proj1, proj2)
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1062
  ```
1063
 
1064
  ### Fold <a id="alg.fold">[[alg.fold]]</a>
1065
 
1066
  ``` cpp
1067
- template<input_iterator I, sentinel_for<I> S, class T, indirectly-binary-left-foldable<T, I> F>
 
1068
  constexpr auto ranges::fold_left(I first, S last, T init, F f);
1069
- template<input_range R, class T, indirectly-binary-left-foldable<T, iterator_t<R>> F>
 
1070
  constexpr auto ranges::fold_left(R&& r, T init, F f);
1071
  ```
1072
 
1073
  *Returns:*
1074
 
@@ -1091,14 +1450,14 @@ template<input_range R, indirectly-binary-left-foldable<range_value_t<R>, iterat
1091
  ``` cpp
1092
  ranges::fold_left_first_with_iter(std::move(first), last, f).value
1093
  ```
1094
 
1095
  ``` cpp
1096
- template<bidirectional_iterator I, sentinel_for<I> S, class T,
1097
  indirectly-binary-right-foldable<T, I> F>
1098
  constexpr auto ranges::fold_right(I first, S last, T init, F f);
1099
- template<bidirectional_range R, class T,
1100
  indirectly-binary-right-foldable<T, iterator_t<R>> F>
1101
  constexpr auto ranges::fold_right(R&& r, T init, F f);
1102
  ```
1103
 
1104
  *Effects:* Equivalent to:
@@ -1137,14 +1496,15 @@ I tail = ranges::prev(ranges::next(first, std::move(last)));
1137
  return optional<U>(in_place,
1138
  ranges::fold_right(std::move(first), tail, iter_value_t<I>(*tail), std::move(f)));
1139
  ```
1140
 
1141
  ``` cpp
1142
- template<input_iterator I, sentinel_for<I> S, class T,
1143
  indirectly-binary-left-foldable<T, I> F>
1144
  constexpr see below ranges::fold_left_with_iter(I first, S last, T init, F f);
1145
- template<input_range R, class T, indirectly-binary-left-foldable<T, iterator_t<R>> F>
 
1146
  constexpr see below ranges::fold_left_with_iter(R&& r, T init, F f);
1147
  ```
1148
 
1149
  Let `U` be `decay_t<invoke_result_t<F&, T, iter_reference_t<I>>>`.
1150
 
 
13
  indirect_unary_predicate<projected<I, Proj>> Pred>
14
  constexpr bool ranges::all_of(I first, S last, Pred pred, Proj proj = {});
15
  template<input_range R, class Proj = identity,
16
  indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
17
  constexpr bool ranges::all_of(R&& r, Pred pred, Proj proj = {});
18
+
19
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
20
+ class Proj = identity, indirect_unary_predicate<projected<I, Proj>> Pred>
21
+ bool ranges::all_of(Ep&& exec, I first, S last, Pred pred, Proj proj = {});
22
+ template<execution-policy Ep, sized-random-access-range R, class Proj = identity,
23
+ indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
24
+ bool ranges::all_of(Ep&& exec, R&& r, Pred pred, Proj proj = {});
25
  ```
26
 
27
  Let E be:
28
 
29
  - `pred(*i)` for the overloads in namespace `std`;
 
49
  indirect_unary_predicate<projected<I, Proj>> Pred>
50
  constexpr bool ranges::any_of(I first, S last, Pred pred, Proj proj = {});
51
  template<input_range R, class Proj = identity,
52
  indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
53
  constexpr bool ranges::any_of(R&& r, Pred pred, Proj proj = {});
54
+
55
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
56
+ class Proj = identity, indirect_unary_predicate<projected<I, Proj>> Pred>
57
+ bool ranges::any_of(Ep&& exec, I first, S last, Pred pred, Proj proj = {});
58
+ template<execution-policy Ep, sized-random-access-range R, class Proj = identity,
59
+ indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
60
+ bool ranges::any_of(Ep&& exec, R&& r, Pred pred, Proj proj = {});
61
  ```
62
 
63
  Let E be:
64
 
65
  - `pred(*i)` for the overloads in namespace `std`;
 
85
  indirect_unary_predicate<projected<I, Proj>> Pred>
86
  constexpr bool ranges::none_of(I first, S last, Pred pred, Proj proj = {});
87
  template<input_range R, class Proj = identity,
88
  indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
89
  constexpr bool ranges::none_of(R&& r, Pred pred, Proj proj = {});
90
+
91
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
92
+ class Proj = identity, indirect_unary_predicate<projected<I, Proj>> Pred>
93
+ bool ranges::none_of(Ep&& exec, I first, S last, Pred pred, Proj proj = {});
94
+ template<execution-policy Ep, sized-random-access-range R, class Proj = identity,
95
+ indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
96
+ bool ranges::none_of(Ep&& exec, R&& r, Pred pred, Proj proj = {});
97
  ```
98
 
99
  Let E be:
100
 
101
  - `pred(*i)` for the overloads in namespace `std`;
 
109
  any projection.
110
 
111
  ### Contains <a id="alg.contains">[[alg.contains]]</a>
112
 
113
  ``` cpp
114
+ template<input_iterator I, sentinel_for<I> S, class Proj = identity,
115
+ class T = projected_value_t<I, Proj>>
116
  requires indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T*>
117
  constexpr bool ranges::contains(I first, S last, const T& value, Proj proj = {});
118
+ template<input_range R, class Proj = identity, class T = projected_value_t<iterator_t<R>, Proj>>
119
  requires indirect_binary_predicate<ranges::equal_to, projected<iterator_t<R>, Proj>, const T*>
120
  constexpr bool ranges::contains(R&& r, const T& value, Proj proj = {});
121
  ```
122
 
123
  *Returns:* `ranges::find(std::move(first), last, value, proj) != last`.
124
 
125
+ ``` cpp
126
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
127
+ class Proj = identity, class T = projected_value_t<I, Proj>>
128
+ requires indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T*>
129
+ bool ranges::contains(Ep&& exec, I first, S last, const T& value, Proj proj = {});
130
+ template<execution-policy Ep, sized-random-access-range R, class Proj = identity,
131
+ class T = projected_value_t<iterator_t<R>, Proj>>
132
+ requires
133
+ indirect_binary_predicate<ranges::equal_to, projected<iterator_t<R>, Proj>, const T*>
134
+ bool ranges::contains(Ep&& exec, R&& r, const T& value, Proj proj = {});
135
+ ```
136
+
137
+ *Returns:*
138
+ `ranges::find(std::forward<Ep>(exec), first, last, value, proj) != last`.
139
+
140
  ``` cpp
141
  template<forward_iterator I1, sentinel_for<I1> S1,
142
  forward_iterator I2, sentinel_for<I2> S2,
143
  class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
144
  requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
 
150
  constexpr bool ranges::contains_subrange(R1&& r1, R2&& r2, Pred pred = {},
151
  Proj1 proj1 = {}, Proj2 proj2 = {});
152
  ```
153
 
154
  *Returns:*
155
+
156
+ ``` cpp
157
+ first2 == last2 || !ranges::search(first1, last1, first2, last2,
158
+ pred, proj1, proj2).empty()
159
+ ```
160
+
161
+ ``` cpp
162
+ template<execution-policy Ep, random_access_iterator I1, sized_sentinel_for<I1> S1,
163
+ random_access_iterator I2, sized_sentinel_for<I2> S2,
164
+ class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
165
+ requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
166
+ bool ranges::contains_subrange(Ep&& exec, I1 first1, S1 last1, I2 first2, S2 last2,
167
+ Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
168
+ template<execution-policy Ep, sized-random-access-range R1, sized-random-access-range R2,
169
+ class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
170
+ requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2>
171
+ bool ranges::contains_subrange(Ep&& exec, R1&& r1, R2&& r2, Pred pred = {},
172
+ Proj1 proj1 = {}, Proj2 proj2 = {});
173
+ ```
174
+
175
+ *Returns:*
176
+
177
+ ``` cpp
178
+ first2 == last2 || !ranges::search(std::forward<Ep>(exec), first1, last1,
179
+ first2, last2, pred, proj1, proj2).empty()
180
+ ```
181
 
182
  ### For each <a id="alg.foreach">[[alg.foreach]]</a>
183
 
184
  ``` cpp
185
  template<class InputIterator, class Function>
 
259
  *Remarks:* If `f` returns a result, the result is ignored.
260
 
261
  [*Note 6*: The overloads in namespace `ranges` require `Fun` to model
262
  `copy_constructible`. — *end note*]
263
 
264
+ ``` cpp
265
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
266
+ class Proj = identity,
267
+ indirectly_unary_invocable<projected<I, Proj>> Fun>
268
+ I ranges::for_each(Ep&& exec, I first, S last, Fun f, Proj proj = {});
269
+ template<execution-policy Ep, sized-random-access-range R, class Proj = identity,
270
+ indirectly_unary_invocable<projected<iterator_t<R>, Proj>> Fun>
271
+ borrowed_iterator_t<R>
272
+ ranges::for_each(Ep&& exec, R&& r, Fun f, Proj proj = {});
273
+ ```
274
+
275
+ *Effects:* Calls `invoke(f, invoke(proj, *i))` for every iterator `i` in
276
+ the range \[`first`, `last`).
277
+
278
+ [*Note 7*: If the result of `invoke(proj, *i)` is a mutable reference,
279
+ `f` can apply non-constant functions. — *end note*]
280
+
281
+ *Returns:* `last`.
282
+
283
+ *Complexity:* Applies `f` and `proj` exactly `last - first` times.
284
+
285
+ *Remarks:*
286
+
287
+ - If `f` returns a result, the result is ignored.
288
+ - Implementations do not have the freedom granted under
289
+ [[algorithms.parallel.exec]] to make arbitrary copies of elements from
290
+ the input sequence.
291
+ - `f` may modify objects via its arguments [[algorithms.parallel.user]].
292
+
293
+ [*Note 8*: Does not return a copy of its `Fun` parameter, since
294
+ parallelization often does not permit efficient state
295
+ accumulation. — *end note*]
296
+
297
  ``` cpp
298
  template<class InputIterator, class Size, class Function>
299
  constexpr InputIterator for_each_n(InputIterator first, Size n, Function f);
300
  ```
301
 
 
303
  type [[conv.integral]], [[class.conv]].
304
 
305
  *Preconditions:* `n >= 0` is `true`. `Function` meets the
306
  *Cpp17MoveConstructible* requirements.
307
 
308
+ [*Note 9*: `Function` need not meet the requirements of
309
  *Cpp17CopyConstructible*. — *end note*]
310
 
311
  *Effects:* Applies `f` to the result of dereferencing every iterator in
312
  the range \[`first`, `first + n`) in order.
313
 
314
+ [*Note 10*: If the type of `first` meets the requirements of a mutable
315
  iterator, `f` can apply non-constant functions through the dereferenced
316
  iterator. — *end note*]
317
 
318
  *Returns:* `first + n`.
319
 
 
332
  *Cpp17CopyConstructible* requirements.
333
 
334
  *Effects:* Applies `f` to the result of dereferencing every iterator in
335
  the range \[`first`, `first + n`).
336
 
337
+ [*Note 11*: If the type of `first` meets the requirements of a mutable
338
  iterator, `f` can apply non-constant functions through the dereferenced
339
  iterator. — *end note*]
340
 
341
  *Returns:* `first + n`.
342
 
 
355
  *Preconditions:* `n >= 0` is `true`.
356
 
357
  *Effects:* Calls `invoke(f, invoke(proj, *i))` for every iterator `i` in
358
  the range \[`first`, `first + n`) in order.
359
 
360
+ [*Note 12*: If the result of `invoke(proj, *i)` is a mutable reference,
361
  `f` can apply non-constant functions. — *end note*]
362
 
363
  *Returns:* `{first + n, std::move(f)}`.
364
 
365
  *Remarks:* If `f` returns a result, the result is ignored.
366
 
367
+ [*Note 13*: The overload in namespace `ranges` requires `Fun` to model
368
  `copy_constructible`. — *end note*]
369
 
370
+ ``` cpp
371
+ template<execution-policy Ep, random_access_iterator I, class Proj = identity,
372
+ indirectly_unary_invocable<projected<I, Proj>> Fun>
373
+ I ranges::for_each_n(Ep&& exec, I first, iter_difference_t<I> n, Fun f, Proj proj = {});
374
+ ```
375
+
376
+ *Preconditions:* `n >= 0` is `true`.
377
+
378
+ *Effects:* Calls `invoke(f, invoke(proj, *i))` for every iterator `i` in
379
+ the range \[`first`, `first + n`).
380
+
381
+ [*Note 14*: If the result of `invoke(proj, *i)` is a mutable reference,
382
+ `f` can apply non-constant functions. — *end note*]
383
+
384
+ *Returns:* `first + n`.
385
+
386
+ *Remarks:*
387
+
388
+ - If `f` returns a result, the result is ignored.
389
+ - Implementations do not have the freedom granted under
390
+ [[algorithms.parallel.exec]] to make arbitrary copies of elements from
391
+ the input sequence.
392
+ - `f` may modify objects via its arguments [[algorithms.parallel.user]].
393
+
394
+ [*Note 15*: Does not return a copy of its `Fun` parameter, since
395
+ parallelization often does not permit efficient state
396
+ accumulation. — *end note*]
397
+
398
  ### Find <a id="alg.find">[[alg.find]]</a>
399
 
400
  ``` cpp
401
+ template<class InputIterator, class T = iterator_traits<InputIterator>::value_type>
402
  constexpr InputIterator find(InputIterator first, InputIterator last,
403
  const T& value);
404
+ template<class ExecutionPolicy, class ForwardIterator,
405
+ class T = iterator_traits<ForwardIterator>::value_type>
406
  ForwardIterator find(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last,
407
  const T& value);
408
 
409
  template<class InputIterator, class Predicate>
410
  constexpr InputIterator find_if(InputIterator first, InputIterator last,
 
419
  template<class ExecutionPolicy, class ForwardIterator, class Predicate>
420
  ForwardIterator find_if_not(ExecutionPolicy&& exec,
421
  ForwardIterator first, ForwardIterator last,
422
  Predicate pred);
423
 
424
+ template<input_iterator I, sentinel_for<I> S, class Proj = identity,
425
+ class T = projected_value_t<I, Proj>>
426
  requires indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T*>
427
  constexpr I ranges::find(I first, S last, const T& value, Proj proj = {});
428
+ template<input_range R, class Proj = identity, class T = projected_value_t<iterator_t<R>, Proj>>
429
  requires indirect_binary_predicate<ranges::equal_to, projected<iterator_t<R>, Proj>, const T*>
430
  constexpr borrowed_iterator_t<R>
431
  ranges::find(R&& r, const T& value, Proj proj = {});
432
+
433
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
434
+ class Proj = identity, class T = projected_value_t<I, Proj>>
435
+ requires indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T*>
436
+ I ranges::find(Ep&& exec, I first, S last, const T& value, Proj proj = {});
437
+ template<execution-policy Ep, sized-random-access-range R, class Proj = identity,
438
+ class T = projected_value_t<iterator_t<R>, Proj>>
439
+ requires indirect_binary_predicate<ranges::equal_to,
440
+ projected<iterator_t<R>, Proj>, const T*>
441
+ borrowed_iterator_t<R> ranges::find(Ep&& exec, R&& r, const T& value, Proj proj = {});
442
+
443
  template<input_iterator I, sentinel_for<I> S, class Proj = identity,
444
  indirect_unary_predicate<projected<I, Proj>> Pred>
445
  constexpr I ranges::find_if(I first, S last, Pred pred, Proj proj = {});
446
  template<input_range R, class Proj = identity,
447
  indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
448
  constexpr borrowed_iterator_t<R>
449
  ranges::find_if(R&& r, Pred pred, Proj proj = {});
450
+
451
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
452
+ class Proj = identity, indirect_unary_predicate<projected<I, Proj>> Pred>
453
+ I ranges::find_if(Ep&& exec, I first, S last, Pred pred, Proj proj = {});
454
+ template<execution-policy Ep, sized-random-access-range R, class Proj = identity,
455
+ indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
456
+ borrowed_iterator_t<R> ranges::find_if(Ep&& exec, R&& r, Pred pred, Proj proj = {});
457
+
458
  template<input_iterator I, sentinel_for<I> S, class Proj = identity,
459
  indirect_unary_predicate<projected<I, Proj>> Pred>
460
  constexpr I ranges::find_if_not(I first, S last, Pred pred, Proj proj = {});
461
  template<input_range R, class Proj = identity,
462
  indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
463
  constexpr borrowed_iterator_t<R>
464
  ranges::find_if_not(R&& r, Pred pred, Proj proj = {});
465
+
466
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
467
+ class Proj = identity, indirect_unary_predicate<projected<I, Proj>> Pred>
468
+ I ranges::find_if_not(Ep&& exec, I first, S last, Pred pred, Proj proj = {});
469
+ template<execution-policy Ep, sized-random-access-range R, class Proj = identity,
470
+ indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
471
+ borrowed_iterator_t<R> ranges::find_if_not(Ep&& exec, R&& r, Pred pred, Proj proj = {});
472
  ```
473
 
474
  Let E be:
475
 
476
  - `*i == value` for `find`;
 
487
  predicate and any projection.
488
 
489
  ### Find last <a id="alg.find.last">[[alg.find.last]]</a>
490
 
491
  ``` cpp
492
+ template<forward_iterator I, sentinel_for<I> S, class Proj = identity,
493
+ class T = projected_value_t<I, Proj>>
494
  requires indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T*>
495
  constexpr subrange<I> ranges::find_last(I first, S last, const T& value, Proj proj = {});
496
+ template<forward_range R, class Proj = identity,
497
+ class T = projected_value_t<iterator_t<R>, Proj>>
498
  requires indirect_binary_predicate<ranges::equal_to, projected<iterator_t<R>, Proj>, const T*>
499
  constexpr borrowed_subrange_t<R> ranges::find_last(R&& r, const T& value, Proj proj = {});
500
+
501
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
502
+ class Proj = identity, class T = projected_value_t<I, Proj>>
503
+ requires indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T*>
504
+ subrange<I> ranges::find_last(Ep&& exec, I first, S last, const T& value, Proj proj = {});
505
+ template<execution-policy Ep, sized-random-access-range R, class Proj = identity,
506
+ class T = projected_value_t<iterator_t<R>, Proj>>
507
+ requires
508
+ indirect_binary_predicate<ranges::equal_to, projected<iterator_t<R>, Proj>, const T*>
509
+ borrowed_subrange_t<R> ranges::find_last(Ep&& exec, R&& r, const T& value, Proj proj = {});
510
+
511
  template<forward_iterator I, sentinel_for<I> S, class Proj = identity,
512
  indirect_unary_predicate<projected<I, Proj>> Pred>
513
  constexpr subrange<I> ranges::find_last_if(I first, S last, Pred pred, Proj proj = {});
514
  template<forward_range R, class Proj = identity,
515
  indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
516
  constexpr borrowed_subrange_t<R> ranges::find_last_if(R&& r, Pred pred, Proj proj = {});
517
+
518
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
519
+ class Proj = identity, indirect_unary_predicate<projected<I, Proj>> Pred>
520
+ subrange<I> ranges::find_last_if(Ep&& exec, I first, S last, Pred pred, Proj proj = {});
521
+ template<execution-policy Ep, sized-random-access-range R,
522
+ class Proj = identity,
523
+ indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
524
+ borrowed_subrange_t<R> ranges::find_last_if(Ep&& exec, R&& r, Pred pred, Proj proj = {});
525
+
526
  template<forward_iterator I, sentinel_for<I> S, class Proj = identity,
527
  indirect_unary_predicate<projected<I, Proj>> Pred>
528
  constexpr subrange<I> ranges::find_last_if_not(I first, S last, Pred pred, Proj proj = {});
529
  template<forward_range R, class Proj = identity,
530
  indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
531
  constexpr borrowed_subrange_t<R> ranges::find_last_if_not(R&& r, Pred pred, Proj proj = {});
532
+
533
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
534
+ class Proj = identity,
535
+ indirect_unary_predicate<projected<I, Proj>> Pred>
536
+ subrange<I> ranges::find_last_if_not(Ep&& exec, I first, S last, Pred pred, Proj proj = {});
537
+ template<execution-policy Ep, sized-random-access-range R, class Proj = identity,
538
+ indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
539
+ borrowed_subrange_t<R> ranges::find_last_if_not(Ep&& exec, R&& r, Pred pred, Proj proj = {});
540
  ```
541
 
542
  Let E be:
543
 
544
  - `bool(invoke(proj, *i) == value)` for `ranges::find_last`;
 
590
  class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
591
  requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2>
592
  constexpr borrowed_subrange_t<R1>
593
  ranges::find_end(R1&& r1, R2&& r2, Pred pred = {},
594
  Proj1 proj1 = {}, Proj2 proj2 = {});
595
+
596
+ template<execution-policy Ep, random_access_iterator I1, sized_sentinel_for<I1> S1,
597
+ random_access_iterator I2, sized_sentinel_for<I2> S2,
598
+ class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
599
+ requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
600
+ subrange<I1>
601
+ ranges::find_end(Ep&& exec, I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = {},
602
+ Proj1 proj1 = {}, Proj2 proj2 = {});
603
+ template<execution-policy Ep, sized-random-access-range R1, sized-random-access-range R2,
604
+ class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
605
+ requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2>
606
+ borrowed_subrange_t<R1>
607
+ ranges::find_end(Ep&& exec, R1&& r1, R2&& r2, Pred pred = {},
608
+ Proj1 proj1 = {}, Proj2 proj2 = {});
609
  ```
610
 
611
  Let:
612
 
613
  - `pred` be `equal_to{}` for the overloads with no parameter `pred`;
 
631
 
632
  *Complexity:* At most
633
  `(last2 - first2) * (last1 - first1 - (last2 - first2) + 1)`
634
  applications of the corresponding predicate and any projections.
635
 
636
+ ### Find first of <a id="alg.find.first.of">[[alg.find.first.of]]</a>
637
 
638
  ``` cpp
639
  template<class InputIterator, class ForwardIterator>
640
  constexpr InputIterator
641
  find_first_of(InputIterator first1, InputIterator last1,
 
671
  requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2>
672
  constexpr borrowed_iterator_t<R1>
673
  ranges::find_first_of(R1&& r1, R2&& r2,
674
  Pred pred = {},
675
  Proj1 proj1 = {}, Proj2 proj2 = {});
676
+
677
+ template<execution-policy Ep, random_access_iterator I1, sized_sentinel_for<I1> S1,
678
+ random_access_iterator I2, sized_sentinel_for<I2> S2,
679
+ class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
680
+ requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
681
+ I1 ranges::find_first_of(Ep&& exec, I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = {},
682
+ Proj1 proj1 = {}, Proj2 proj2 = {});
683
+ template<execution-policy Ep, sized-random-access-range R1, sized-random-access-range R2,
684
+ class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
685
+ requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2>
686
+ borrowed_iterator_t<R1>
687
+ ranges::find_first_of(Ep&& exec, R1&& r1, R2&& r2, Pred pred = {},
688
+ Proj1 proj1 = {}, Proj2 proj2 = {});
689
  ```
690
 
691
  Let E be:
692
 
693
  - `*i == *j` for the overloads with no parameter `pred`;
 
701
  *Returns:* The first iterator `i` in the range \[`first1`, `last1`) such
702
  that for some iterator `j` in the range \[`first2`, `last2`) E holds.
703
  Returns `last1` if \[`first2`, `last2`) is empty or if no such iterator
704
  is found.
705
 
706
+ *Complexity:* At most `(last1 - first1) * (last2 - first2)` applications
707
+ of the corresponding predicate and any projections.
708
 
709
  ### Adjacent find <a id="alg.adjacent.find">[[alg.adjacent.find]]</a>
710
 
711
  ``` cpp
712
  template<class ForwardIterator>
 
733
  constexpr I ranges::adjacent_find(I first, S last, Pred pred = {}, Proj proj = {});
734
  template<forward_range R, class Proj = identity,
735
  indirect_binary_predicate<projected<iterator_t<R>, Proj>,
736
  projected<iterator_t<R>, Proj>> Pred = ranges::equal_to>
737
  constexpr borrowed_iterator_t<R> ranges::adjacent_find(R&& r, Pred pred = {}, Proj proj = {});
738
+
739
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
740
+ class Proj = identity,
741
+ indirect_binary_predicate<projected<I, Proj>,
742
+ projected<I, Proj>> Pred = ranges::equal_to>
743
+ I ranges::adjacent_find(Ep&& exec, I first, S last, Pred pred = {}, Proj proj = {});
744
+ template<execution-policy Ep, sized-random-access-range R, class Proj = identity,
745
+ indirect_binary_predicate<projected<iterator_t<R>, Proj>,
746
+ projected<iterator_t<R>, Proj>> Pred = ranges::equal_to>
747
+ borrowed_iterator_t<R>
748
+ ranges::adjacent_find(Ep&& exec, R&& r, Pred pred = {}, Proj proj = {});
749
  ```
750
 
751
  Let E be:
752
 
753
  - `*i == *(i + 1)` for the overloads with no parameter `pred`;
 
758
 
759
  *Returns:* The first iterator `i` such that both `i` and `i + 1` are in
760
  the range \[`first`, `last`) for which E holds. Returns `last` if no
761
  such iterator is found.
762
 
763
+ *Complexity:* For the non-parallel algorithm overloads, exactly
764
  $$\min(\texttt{(i - first) + 1}, \ \texttt{(last - first) - 1})$$
765
  applications of the corresponding predicate, where `i` is
766
+ `adjacent_find`’s return value. For the parallel algorithm overloads,
767
+ 𝑂(`last - first`) applications of the corresponding predicate. No more
768
+ than twice as many applications of any projection.
 
769
 
770
  ### Count <a id="alg.count">[[alg.count]]</a>
771
 
772
  ``` cpp
773
+ template<class InputIterator, class T = iterator_traits<InputIterator>::value_type>
774
  constexpr typename iterator_traits<InputIterator>::difference_type
775
  count(InputIterator first, InputIterator last, const T& value);
776
+ template<class ExecutionPolicy, class ForwardIterator,
777
+ class T = iterator_traits<ForwardIterator>::value_type>
778
  typename iterator_traits<ForwardIterator>::difference_type
779
  count(ExecutionPolicy&& exec,
780
  ForwardIterator first, ForwardIterator last, const T& value);
781
 
782
  template<class InputIterator, class Predicate>
 
785
  template<class ExecutionPolicy, class ForwardIterator, class Predicate>
786
  typename iterator_traits<ForwardIterator>::difference_type
787
  count_if(ExecutionPolicy&& exec,
788
  ForwardIterator first, ForwardIterator last, Predicate pred);
789
 
790
+ template<input_iterator I, sentinel_for<I> S, class Proj = identity,
791
+ class T = projected_value_t<I, Proj>>
792
  requires indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T*>
793
  constexpr iter_difference_t<I>
794
  ranges::count(I first, S last, const T& value, Proj proj = {});
795
+ template<input_range R, class Proj = identity, class T = projected_value_t<iterator_t<R>, Proj>>
796
  requires indirect_binary_predicate<ranges::equal_to, projected<iterator_t<R>, Proj>, const T*>
797
  constexpr range_difference_t<R>
798
  ranges::count(R&& r, const T& value, Proj proj = {});
799
+
800
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
801
+ class Proj = identity, class T = projected_value_t<I, Proj>>
802
+ requires indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T*>
803
+ iter_difference_t<I>
804
+ ranges::count(Ep&& exec, I first, S last, const T& value, Proj proj = {});
805
+ template<execution-policy Ep, sized-random-access-range R, class Proj = identity,
806
+ class T = projected_value_t<iterator_t<R>, Proj>>
807
+ requires indirect_binary_predicate<ranges::equal_to,
808
+ projected<iterator_t<R>, Proj>, const T*>
809
+ range_difference_t<R> ranges::count(Ep&& exec, R&& r, const T& value, Proj proj = {});
810
+
811
  template<input_iterator I, sentinel_for<I> S, class Proj = identity,
812
  indirect_unary_predicate<projected<I, Proj>> Pred>
813
  constexpr iter_difference_t<I>
814
  ranges::count_if(I first, S last, Pred pred, Proj proj = {});
815
  template<input_range R, class Proj = identity,
816
  indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
817
  constexpr range_difference_t<R>
818
  ranges::count_if(R&& r, Pred pred, Proj proj = {});
819
+
820
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
821
+ class Proj = identity, indirect_unary_predicate<projected<I, Proj>> Pred>
822
+ iter_difference_t<I>
823
+ ranges::count_if(Ep&& exec, I first, S last, Pred pred, Proj proj = {});
824
+ template<execution-policy Ep, sized-random-access-range R, class Proj = identity,
825
+ indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
826
+ range_difference_t<R>
827
+ ranges::count_if(Ep&& exec, R&& r, Pred pred, Proj proj = {});
828
  ```
829
 
830
  Let E be:
831
 
832
  - `*i == value` for the overloads with no parameter `pred` or `proj`;
 
841
  `last`) for which E holds.
842
 
843
  *Complexity:* Exactly `last - first` applications of the corresponding
844
  predicate and any projection.
845
 
846
+ ### Mismatch <a id="alg.mismatch">[[alg.mismatch]]</a>
847
 
848
  ``` cpp
849
  template<class InputIterator1, class InputIterator2>
850
  constexpr pair<InputIterator1, InputIterator2>
851
  mismatch(InputIterator1 first1, InputIterator1 last1,
 
902
  class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
903
  requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2>
904
  constexpr ranges::mismatch_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>>
905
  ranges::mismatch(R1&& r1, R2&& r2, Pred pred = {},
906
  Proj1 proj1 = {}, Proj2 proj2 = {});
907
+
908
+ template<execution-policy Ep, random_access_iterator I1, sized_sentinel_for<I1> S1,
909
+ random_access_iterator I2, sized_sentinel_for<I2> S2,
910
+ class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
911
+ requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
912
+ ranges::mismatch_result<I1, I2>
913
+ ranges::mismatch(Ep&& exec, I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = {},
914
+ Proj1 proj1 = {}, Proj2 proj2 = {});
915
+ template<execution-policy Ep, sized-random-access-range R1, sized-random-access-range R2,
916
+ class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
917
+ requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2>
918
+ ranges::mismatch_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>>
919
+ ranges::mismatch(Ep&& exec, R1&& r1, R2&& r2, Pred pred = {},
920
+ Proj1 proj1 = {}, Proj2 proj2 = {});
921
  ```
922
 
923
+ Let `last2` be `first2 + (last1 - first1)` for the overloads in
924
+ namespace `std` with no parameter `last2`.
925
 
926
  Let E be:
927
 
928
  - `!(*(first1 + n) == *(first2 + n))` for the overloads with no
929
  parameter `pred`;
 
990
  template<input_range R1, input_range R2, class Pred = ranges::equal_to,
991
  class Proj1 = identity, class Proj2 = identity>
992
  requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2>
993
  constexpr bool ranges::equal(R1&& r1, R2&& r2, Pred pred = {},
994
  Proj1 proj1 = {}, Proj2 proj2 = {});
995
+
996
+ template<execution-policy Ep, random_access_iterator I1, sized_sentinel_for<I1> S1,
997
+ random_access_iterator I2, sized_sentinel_for<I2> S2,
998
+ class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
999
+ requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
1000
+ bool ranges::equal(Ep&& exec, I1 first1, S1 last1, I2 first2, S2 last2,
1001
+ Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
1002
+ template<execution-policy Ep, sized-random-access-range R1, sized-random-access-range R2,
1003
+ class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
1004
+ requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2>
1005
+ bool ranges::equal(Ep&& exec, R1&& r1, R2&& r2,
1006
+ Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
1007
  ```
1008
 
1009
  Let:
1010
 
1011
+ - `last2` be `first2 + (last1 - first1)` for the overloads in namespace
1012
+ `std` with no parameter `last2`;
1013
  - `pred` be `equal_to{}` for the overloads with no parameter `pred`;
1014
  - E be:
1015
  - `pred(*i, *(first2 + (i - first1)))` for the overloads with no
1016
  parameter `proj1`;
1017
  - `invoke(pred, invoke(proj1, *i), invoke(proj2, *(first2 + (i - first1))))`
 
1027
  *Cpp17RandomAccessIterator* requirements [[random.access.iterators]]
1028
  and `last1 - first1 != last2 - first2` for the overloads in namespace
1029
  `std`;
1030
  - the types of `first1`, `last1`, `first2`, and `last2` pairwise model
1031
  `sized_sentinel_for` [[iterator.concept.sizedsentinel]] and
1032
+ `last1 - first1 != last2 - first2` for the first and third overloads
1033
+ in namespace `ranges`, or
1034
  - `R1` and `R2` each model `sized_range` and
1035
+ `ranges::distance(r1) != ranges::distance(r2)` for the second and
1036
+ fourth overloads in namespace `ranges`,
1037
 
1038
  then no applications of the corresponding predicate and each projection;
1039
+ otherwise, at most
1040
+ $$\min(\texttt{last1 - first1}, \ \texttt{last2 - first2})$$
1041
+ applications of the corresponding predicate and any projections.
 
 
 
 
1042
 
1043
  ### Is permutation <a id="alg.is.permutation">[[alg.is.permutation]]</a>
1044
 
1045
  ``` cpp
1046
  template<class ForwardIterator1, class ForwardIterator2>
 
1104
  the range \[`first2`, `last2`), bounded by \[`pfirst`, `plast`), such
1105
  that `ranges::equal(first1, last1, pfirst, plast, pred, proj1, proj2)`
1106
  returns `true`; otherwise, returns `false`.
1107
 
1108
  *Complexity:* No applications of the corresponding predicate and
1109
+ projections if
1110
 
1111
  - for the first overload,
1112
  - `S1` and `I1` model `sized_sentinel_for<S1, I1>`,
1113
  - `S2` and `I2` model `sized_sentinel_for<S2, I2>`, and
1114
  - `last1 - first1 != last2 - first2`;
 
1148
  ForwardIterator2 first2, ForwardIterator2 last2,
1149
  BinaryPredicate pred);
1150
  ```
1151
 
1152
  *Returns:* The first iterator `i` in the range \[`first1`,
1153
+ `last1 - (last2 - first2)`\] such that for every non-negative integer
1154
+ `n` less than `last2 - first2` the following corresponding conditions
1155
+ hold:
1156
  `*(i + n) == *(first2 + n), pred(*(i + n), *(first2 + n)) != false`.
1157
  Returns `first1` if \[`first2`, `last2`) is empty, otherwise returns
1158
  `last1` if no such iterator is found.
1159
 
1160
  *Complexity:* At most `(last1 - first1) * (last2 - first2)` applications
 
1172
  class Proj1 = identity, class Proj2 = identity>
1173
  requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2>
1174
  constexpr borrowed_subrange_t<R1>
1175
  ranges::search(R1&& r1, R2&& r2, Pred pred = {},
1176
  Proj1 proj1 = {}, Proj2 proj2 = {});
1177
+
1178
+ template<execution-policy Ep, random_access_iterator I1, sized_sentinel_for<I1> S1,
1179
+ random_access_iterator I2, sized_sentinel_for<I2> S2,
1180
+ class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
1181
+ requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
1182
+ subrange<I1>
1183
+ ranges::search(Ep&& exec, I1 first1, S1 last1, I2 first2, S2 last2,
1184
+ Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
1185
+ template<execution-policy Ep, sized-random-access-range R1, sized-random-access-range R2,
1186
+ class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
1187
+ requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2>
1188
+ borrowed_subrange_t<R1>
1189
+ ranges::search(Ep&& exec, R1&& r1, R2&& r2,
1190
+ Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
1191
  ```
1192
 
1193
  *Returns:*
1194
 
1195
  - `{i, i + (last2 - first2)}`, where `i` is the first iterator in the
1196
+ range \[`first1`, `last1 - (last2 - first2)`\] such that for every
1197
  non-negative integer `n` less than `last2 - first2` the condition
1198
  ``` cpp
1199
  bool(invoke(pred, invoke(proj1, *(i + n)), invoke(proj2, *(first2 + n))))
1200
  ```
1201
 
 
1204
 
1205
  *Complexity:* At most `(last1 - first1) * (last2 - first2)` applications
1206
  of the corresponding predicate and projections.
1207
 
1208
  ``` cpp
1209
+ template<class ForwardIterator, class Size, class T = iterator_traits<ForwardIterator>::value_type>
1210
  constexpr ForwardIterator
1211
  search_n(ForwardIterator first, ForwardIterator last,
1212
  Size count, const T& value);
1213
+ template<class ExecutionPolicy, class ForwardIterator, class Size,
1214
+ class T = iterator_traits<ForwardIterator>::value_type>
1215
  ForwardIterator
1216
  search_n(ExecutionPolicy&& exec,
1217
  ForwardIterator first, ForwardIterator last,
1218
  Size count, const T& value);
1219
 
1220
+ template<class ForwardIterator, class Size, class T = iterator_traits<ForwardIterator>::value_type,
1221
  class BinaryPredicate>
1222
  constexpr ForwardIterator
1223
  search_n(ForwardIterator first, ForwardIterator last,
1224
  Size count, const T& value,
1225
  BinaryPredicate pred);
1226
+ template<class ExecutionPolicy, class ForwardIterator, class Size,
1227
+ class T = iterator_traits<ForwardIterator>::value_type,
1228
  class BinaryPredicate>
1229
  ForwardIterator
1230
  search_n(ExecutionPolicy&& exec,
1231
  ForwardIterator first, ForwardIterator last,
1232
  Size count, const T& value,
 
1234
  ```
1235
 
1236
  *Mandates:* The type `Size` is convertible to an integral
1237
  type [[conv.integral]], [[class.conv]].
1238
 
1239
+ Let E be `pred(*(i + n), value) != false` for the overloads with a
1240
+ parameter `pred`, and `*(i + n) == value` otherwise.
1241
+
1242
+ *Returns:* The first iterator `i` in the range \[`first`,
1243
+ `last - count`\] such that for every non-negative integer `n` less than
1244
+ `count` the condition E is `true`. Returns `last` if no such iterator is
1245
+ found.
1246
 
1247
  *Complexity:* At most `last - first` applications of the corresponding
1248
  predicate.
1249
 
1250
  ``` cpp
1251
+ template<forward_iterator I, sentinel_for<I> S,
1252
+ class Pred = ranges::equal_to, class Proj = identity,
1253
+ class T = projected_value_t<I, Proj>>
1254
  requires indirectly_comparable<I, const T*, Pred, Proj>
1255
  constexpr subrange<I>
1256
  ranges::search_n(I first, S last, iter_difference_t<I> count,
1257
  const T& value, Pred pred = {}, Proj proj = {});
1258
+ template<forward_range R, class Pred = ranges::equal_to,
1259
+ class Proj = identity, class T = projected_value_t<iterator_t<R>, Proj>>
1260
  requires indirectly_comparable<iterator_t<R>, const T*, Pred, Proj>
1261
  constexpr borrowed_subrange_t<R>
1262
  ranges::search_n(R&& r, range_difference_t<R> count,
1263
  const T& value, Pred pred = {}, Proj proj = {});
1264
+
1265
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
1266
+ class Pred = ranges::equal_to, class Proj = identity,
1267
+ class T = projected_value_t<I, Proj>>
1268
+ requires indirectly_comparable<I, const T*, Pred, Proj>
1269
+ subrange<I>
1270
+ ranges::search_n(Ep&& exec, I first, S last, iter_difference_t<I> count,
1271
+ const T& value, Pred pred = {}, Proj proj = {});
1272
+ template<execution-policy Ep, sized-random-access-range R, class Pred = ranges::equal_to,
1273
+ class Proj = identity, class T = projected_value_t<iterator_t<R>, Proj>>
1274
+ requires indirectly_comparable<iterator_t<R>, const T*, Pred, Proj>
1275
+ borrowed_subrange_t<R>
1276
+ ranges::search_n(Ep&& exec, R&& r, range_difference_t<R> count,
1277
+ const T& value, Pred pred = {}, Proj proj = {});
1278
  ```
1279
 
1280
  *Returns:* `{i, i + count}` where `i` is the first iterator in the range
1281
+ \[`first`, `last - count`\] such that for every non-negative integer `n`
1282
  less than `count`, the following condition holds:
1283
  `invoke(pred, invoke(proj, *(i + n)), value)`. Returns `{last, last}` if
1284
  no such iterator is found.
1285
 
1286
  *Complexity:* At most `last - first` applications of the corresponding
 
1317
  ``` cpp
1318
  ranges::mismatch(std::move(first1), last1, std::move(first2), last2,
1319
  pred, proj1, proj2).in2 == last2
1320
  ```
1321
 
1322
+ ``` cpp
1323
+ template<execution-policy Ep, random_access_iterator I1, sized_sentinel_for<I1> S1,
1324
+ random_access_iterator I2, sized_sentinel_for<I2> S2,
1325
+ class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
1326
+ requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
1327
+ bool ranges::starts_with(Ep&& exec, I1 first1, S1 last1, I2 first2, S2 last2,
1328
+ Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
1329
+ template<execution-policy Ep, sized-random-access-range R1,
1330
+ sized-random-access-range R2, class Pred = ranges::equal_to,
1331
+ class Proj1 = identity, class Proj2 = identity>
1332
+ requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2>
1333
+ bool ranges::starts_with(Ep&& exec, R1&& r1, R2&& r2,
1334
+ Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
1335
+ ```
1336
+
1337
+ *Returns:*
1338
+
1339
+ ``` cpp
1340
+ ranges::mismatch(std::forward<Ep>(exec), std::move(first1), last1, std::move(first2),
1341
+ last2, pred, proj1, proj2).in2 == last2
1342
+ ```
1343
+
1344
  ### Ends with <a id="alg.ends.with">[[alg.ends.with]]</a>
1345
 
1346
  ``` cpp
1347
  template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2,
1348
  class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
 
1353
  Proj1 proj1 = {}, Proj2 proj2 = {});
1354
  ```
1355
 
1356
  Let `N1` be `last1 - first1` and `N2` be `last2 - first2`.
1357
 
1358
+ *Returns:* `false` if `N1` < `N2`, otherwise:
1359
 
1360
  ``` cpp
1361
  ranges::equal(std::move(first1) + (N1 - N2), last1, std::move(first2), last2,
1362
  pred, proj1, proj2)
1363
  ```
1364
 
1365
+ ``` cpp
1366
+ template<execution-policy Ep, random_access_iterator I1, sized_sentinel_for<I1> S1,
1367
+ random_access_iterator I2, sized_sentinel_for<I2> S2,
1368
+ class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
1369
+ requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
1370
+ bool ranges::ends_with(Ep&& exec, I1 first1, S1 last1, I2 first2, S2 last2,
1371
+ Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
1372
+ ```
1373
+
1374
+ Let `N1` be `last1 - first1` and `N2` be `last2 - first2`.
1375
+
1376
+ *Returns:* `false` if `N1` < `N2`, otherwise:
1377
+
1378
+ ``` cpp
1379
+ ranges::equal(std::forward<Ep>(exec), std::move(first1) + (N1 - N2), last1,
1380
+ std::move(first2), last2, pred, proj1, proj2)
1381
+ ```
1382
+
1383
  ``` cpp
1384
  template<input_range R1, input_range R2, class Pred = ranges::equal_to, class Proj1 = identity,
1385
  class Proj2 = identity>
1386
  requires (forward_range<R1> || sized_range<R1>) &&
1387
  (forward_range<R2> || sized_range<R2>) &&
 
1390
  Proj1 proj1 = {}, Proj2 proj2 = {});
1391
  ```
1392
 
1393
  Let `N1` be `ranges::distance(r1)` and `N2` be `ranges::distance(r2)`.
1394
 
1395
+ *Returns:* `false` if `N1` < `N2`, otherwise:
1396
 
1397
  ``` cpp
1398
+ ranges::equal(views::drop(ranges::ref_view(r1), N1 - static_cast<decltype(N1)>(N2)),
1399
+ r2, pred, proj1, proj2)
1400
+ ```
1401
+
1402
+ ``` cpp
1403
+ template<execution-policy Ep, sized-random-access-range R1,
1404
+ sized-random-access-range R2, class Pred = ranges::equal_to,
1405
+ class Proj1 = identity, class Proj2 = identity>
1406
+ requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2>
1407
+ bool ranges::ends_with(Ep&& exec, R1&& r1, R2&& r2,
1408
+ Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
1409
+ ```
1410
+
1411
+ Let `N1` be `ranges::distance(r1)` and `N2` be `ranges::distance(r2)`.
1412
+
1413
+ *Returns:* `false` if `N1` < `N2`, otherwise:
1414
+
1415
+ ``` cpp
1416
+ ranges::equal(std::forward<Ep>(exec),
1417
+ views::drop(ranges::ref_view(r1), N1 - static_cast<decltype(N1)>(N2)),
1418
+ r2, pred, proj1, proj2)
1419
  ```
1420
 
1421
  ### Fold <a id="alg.fold">[[alg.fold]]</a>
1422
 
1423
  ``` cpp
1424
+ template<input_iterator I, sentinel_for<I> S, class T = iter_value_t<I>,
1425
+ indirectly-binary-left-foldable<T, I> F>
1426
  constexpr auto ranges::fold_left(I first, S last, T init, F f);
1427
+ template<input_range R, class T = range_value_t<R>,
1428
+ indirectly-binary-left-foldable<T, iterator_t<R>> F>
1429
  constexpr auto ranges::fold_left(R&& r, T init, F f);
1430
  ```
1431
 
1432
  *Returns:*
1433
 
 
1450
  ``` cpp
1451
  ranges::fold_left_first_with_iter(std::move(first), last, f).value
1452
  ```
1453
 
1454
  ``` cpp
1455
+ template<bidirectional_iterator I, sentinel_for<I> S, class T = iter_value_t<I>,
1456
  indirectly-binary-right-foldable<T, I> F>
1457
  constexpr auto ranges::fold_right(I first, S last, T init, F f);
1458
+ template<bidirectional_range R, class T = range_value_t<R>,
1459
  indirectly-binary-right-foldable<T, iterator_t<R>> F>
1460
  constexpr auto ranges::fold_right(R&& r, T init, F f);
1461
  ```
1462
 
1463
  *Effects:* Equivalent to:
 
1496
  return optional<U>(in_place,
1497
  ranges::fold_right(std::move(first), tail, iter_value_t<I>(*tail), std::move(f)));
1498
  ```
1499
 
1500
  ``` cpp
1501
+ template<input_iterator I, sentinel_for<I> S, class T = iter_value_t<I>,
1502
  indirectly-binary-left-foldable<T, I> F>
1503
  constexpr see below ranges::fold_left_with_iter(I first, S last, T init, F f);
1504
+ template<input_range R, class T = range_value_t<R>,
1505
+ indirectly-binary-left-foldable<T, iterator_t<R>> F>
1506
  constexpr see below ranges::fold_left_with_iter(R&& r, T init, F f);
1507
  ```
1508
 
1509
  Let `U` be `decay_t<invoke_result_t<F&, T, iter_reference_t<I>>>`.
1510