From Jason Turner

[alg.sorting]

C++23 → Trunk 63.0 KB 681 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/tmp2nwafskr/{from.md → to.md} +545 -96
tmp/tmp2nwafskr/{from.md → to.md} RENAMED
@@ -94,10 +94,19 @@ template<random_access_iterator I, sentinel_for<I> S, class Comp = ranges::less,
94
  ranges::sort(I first, S last, Comp comp = {}, Proj proj = {});
95
  template<random_access_range R, class Comp = ranges::less, class Proj = identity>
96
  requires sortable<iterator_t<R>, Comp, Proj>
97
  constexpr borrowed_iterator_t<R>
98
  ranges::sort(R&& r, Comp comp = {}, Proj proj = {});
 
 
 
 
 
 
 
 
 
99
  ```
100
 
101
  Let `comp` be `less{}` and `proj` be `identity{}` for the overloads with
102
  no parameters by those names.
103
 
@@ -117,31 +126,41 @@ projections.
117
 
118
  #### `stable_sort` <a id="stable.sort">[[stable.sort]]</a>
119
 
120
  ``` cpp
121
  template<class RandomAccessIterator>
122
- void stable_sort(RandomAccessIterator first, RandomAccessIterator last);
123
  template<class ExecutionPolicy, class RandomAccessIterator>
124
  void stable_sort(ExecutionPolicy&& exec,
125
  RandomAccessIterator first, RandomAccessIterator last);
126
 
127
  template<class RandomAccessIterator, class Compare>
128
- void stable_sort(RandomAccessIterator first, RandomAccessIterator last,
129
  Compare comp);
130
  template<class ExecutionPolicy, class RandomAccessIterator, class Compare>
131
  void stable_sort(ExecutionPolicy&& exec,
132
  RandomAccessIterator first, RandomAccessIterator last,
133
  Compare comp);
134
 
135
  template<random_access_iterator I, sentinel_for<I> S, class Comp = ranges::less,
136
  class Proj = identity>
137
  requires sortable<I, Comp, Proj>
138
- I ranges::stable_sort(I first, S last, Comp comp = {}, Proj proj = {});
139
  template<random_access_range R, class Comp = ranges::less, class Proj = identity>
140
  requires sortable<iterator_t<R>, Comp, Proj>
141
- borrowed_iterator_t<R>
142
  ranges::stable_sort(R&& r, Comp comp = {}, Proj proj = {});
 
 
 
 
 
 
 
 
 
 
143
  ```
144
 
145
  Let `comp` be `less{}` and `proj` be `identity{}` for the overloads with
146
  no parameters by those names.
147
 
@@ -191,10 +210,14 @@ template<class ExecutionPolicy, class RandomAccessIterator, class Compare>
191
  template<random_access_iterator I, sentinel_for<I> S, class Comp = ranges::less,
192
  class Proj = identity>
193
  requires sortable<I, Comp, Proj>
194
  constexpr I
195
  ranges::partial_sort(I first, I middle, S last, Comp comp = {}, Proj proj = {});
 
 
 
 
196
  ```
197
 
198
  Let `comp` be `less{}` and `proj` be `identity{}` for the overloads with
199
  no parameters by those names.
200
 
@@ -226,10 +249,26 @@ template<random_access_range R, class Comp = ranges::less, class Proj = identity
226
 
227
  ``` cpp
228
  return ranges::partial_sort(ranges::begin(r), middle, ranges::end(r), comp, proj);
229
  ```
230
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
231
  #### `partial_sort_copy` <a id="partial.sort.copy">[[partial.sort.copy]]</a>
232
 
233
  ``` cpp
234
  template<class InputIterator, class RandomAccessIterator>
235
  constexpr RandomAccessIterator
@@ -273,10 +312,29 @@ template<input_range R1, random_access_range R2, class Comp = ranges::less,
273
  indirect_strict_weak_order<Comp, projected<iterator_t<R1>, Proj1>,
274
  projected<iterator_t<R2>, Proj2>>
275
  constexpr ranges::partial_sort_copy_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>>
276
  ranges::partial_sort_copy(R1&& r, R2&& result_r, Comp comp = {},
277
  Proj1 proj1 = {}, Proj2 proj2 = {});
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
278
  ```
279
 
280
  Let N be min(`last - first`, `result_last - result_first`). Let `comp`
281
  be `less{}`, and `proj1` and `proj2` be `identity{}` for the overloads
282
  with no parameters by those names.
@@ -373,10 +431,26 @@ template<forward_range R, class Proj = identity,
373
  ```
374
 
375
  *Effects:* Equivalent to:
376
  `return ranges::is_sorted_until(first, last, comp, proj) == last;`
377
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
378
  ``` cpp
379
  template<class ForwardIterator>
380
  constexpr ForwardIterator
381
  is_sorted_until(ForwardIterator first, ForwardIterator last);
382
  template<class ExecutionPolicy, class ForwardIterator>
@@ -399,10 +473,20 @@ template<forward_iterator I, sentinel_for<I> S, class Proj = identity,
399
  constexpr I ranges::is_sorted_until(I first, S last, Comp comp = {}, Proj proj = {});
400
  template<forward_range R, class Proj = identity,
401
  indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
402
  constexpr borrowed_iterator_t<R>
403
  ranges::is_sorted_until(R&& r, Comp comp = {}, Proj proj = {});
 
 
 
 
 
 
 
 
 
 
404
  ```
405
 
406
  Let `comp` be `less{}` and `proj` be `identity{}` for the overloads with
407
  no parameters by those names.
408
 
@@ -433,10 +517,14 @@ template<class ExecutionPolicy, class RandomAccessIterator, class Compare>
433
  template<random_access_iterator I, sentinel_for<I> S, class Comp = ranges::less,
434
  class Proj = identity>
435
  requires sortable<I, Comp, Proj>
436
  constexpr I
437
  ranges::nth_element(I first, I nth, S last, Comp comp = {}, Proj proj = {});
 
 
 
 
438
  ```
439
 
440
  Let `comp` be `less{}` and `proj` be `identity{}` for the overloads with
441
  no parameters by those names.
442
 
@@ -454,13 +542,13 @@ Also for every iterator `i` in the range \[`first`, `nth`) and every
454
  iterator `j` in the range \[`nth`, `last`) it holds that:
455
  `bool(invoke(comp, invoke(proj, *j), invoke(proj, *i)))` is `false`.
456
 
457
  *Returns:* `last` for the overload in namespace `ranges`.
458
 
459
- *Complexity:* For the overloads with no `ExecutionPolicy`, linear on
460
- average. For the overloads with an `ExecutionPolicy`, 𝑂(N) applications
461
- of the predicate, and 𝑂(N log N) swaps, where N = `last - first`.
462
 
463
  ``` cpp
464
  template<random_access_range R, class Comp = ranges::less, class Proj = identity>
465
  requires sortable<iterator_t<R>, Comp, Proj>
466
  constexpr borrowed_iterator_t<R>
@@ -471,10 +559,25 @@ template<random_access_range R, class Comp = ranges::less, class Proj = identity
471
 
472
  ``` cpp
473
  return ranges::nth_element(ranges::begin(r), nth, ranges::end(r), comp, proj);
474
  ```
475
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
476
  ### Binary search <a id="alg.binary.search">[[alg.binary.search]]</a>
477
 
478
  #### General <a id="alg.binary.search.general">[[alg.binary.search.general]]</a>
479
 
480
  All of the algorithms in [[alg.binary.search]] are versions of binary
@@ -488,25 +591,28 @@ through the data structure. For non-random access iterators they execute
488
  a linear number of steps.
489
 
490
  #### `lower_bound` <a id="lower.bound">[[lower.bound]]</a>
491
 
492
  ``` cpp
493
- template<class ForwardIterator, class T>
494
  constexpr ForwardIterator
495
  lower_bound(ForwardIterator first, ForwardIterator last,
496
  const T& value);
497
 
498
- template<class ForwardIterator, class T, class Compare>
 
499
  constexpr ForwardIterator
500
  lower_bound(ForwardIterator first, ForwardIterator last,
501
  const T& value, Compare comp);
502
 
503
- template<forward_iterator I, sentinel_for<I> S, class T, class Proj = identity,
 
504
  indirect_strict_weak_order<const T*, projected<I, Proj>> Comp = ranges::less>
505
  constexpr I ranges::lower_bound(I first, S last, const T& value, Comp comp = {},
506
  Proj proj = {});
507
- template<forward_range R, class T, class Proj = identity,
 
508
  indirect_strict_weak_order<const T*, projected<iterator_t<R>, Proj>> Comp =
509
  ranges::less>
510
  constexpr borrowed_iterator_t<R>
511
  ranges::lower_bound(R&& r, const T& value, Comp comp = {}, Proj proj = {});
512
  ```
@@ -526,24 +632,27 @@ such that for every iterator `j` in the range \[`first`, `i`),
526
  projections.
527
 
528
  #### `upper_bound` <a id="upper.bound">[[upper.bound]]</a>
529
 
530
  ``` cpp
531
- template<class ForwardIterator, class T>
532
  constexpr ForwardIterator
533
  upper_bound(ForwardIterator first, ForwardIterator last,
534
  const T& value);
535
 
536
- template<class ForwardIterator, class T, class Compare>
 
537
  constexpr ForwardIterator
538
  upper_bound(ForwardIterator first, ForwardIterator last,
539
  const T& value, Compare comp);
540
 
541
- template<forward_iterator I, sentinel_for<I> S, class T, class Proj = identity,
 
542
  indirect_strict_weak_order<const T*, projected<I, Proj>> Comp = ranges::less>
543
  constexpr I ranges::upper_bound(I first, S last, const T& value, Comp comp = {}, Proj proj = {});
544
- template<forward_range R, class T, class Proj = identity,
 
545
  indirect_strict_weak_order<const T*, projected<iterator_t<R>, Proj>> Comp =
546
  ranges::less>
547
  constexpr borrowed_iterator_t<R>
548
  ranges::upper_bound(R&& r, const T& value, Comp comp = {}, Proj proj = {});
549
  ```
@@ -563,26 +672,29 @@ such that for every iterator `j` in the range \[`first`, `i`),
563
  projections.
564
 
565
  #### `equal_range` <a id="equal.range">[[equal.range]]</a>
566
 
567
  ``` cpp
568
- template<class ForwardIterator, class T>
569
  constexpr pair<ForwardIterator, ForwardIterator>
570
  equal_range(ForwardIterator first,
571
  ForwardIterator last, const T& value);
572
 
573
- template<class ForwardIterator, class T, class Compare>
 
574
  constexpr pair<ForwardIterator, ForwardIterator>
575
  equal_range(ForwardIterator first,
576
  ForwardIterator last, const T& value,
577
  Compare comp);
578
 
579
- template<forward_iterator I, sentinel_for<I> S, class T, class Proj = identity,
 
580
  indirect_strict_weak_order<const T*, projected<I, Proj>> Comp = ranges::less>
581
  constexpr subrange<I>
582
  ranges::equal_range(I first, S last, const T& value, Comp comp = {}, Proj proj = {});
583
- template<forward_range R, class T, class Proj = identity,
 
584
  indirect_strict_weak_order<const T*, projected<iterator_t<R>, Proj>> Comp =
585
  ranges::less>
586
  constexpr borrowed_subrange_t<R>
587
  ranges::equal_range(R&& r, const T& value, Comp comp = {}, Proj proj = {});
588
  ```
@@ -592,11 +704,11 @@ parameters by those names.
592
 
593
  *Preconditions:* The elements `e` of \[`first`, `last`) are partitioned
594
  with respect to the expressions
595
  `bool(invoke(comp, invoke(proj, e), value))` and
596
  `!bool(invoke(comp, value, invoke(proj, e)))`. Also, for all elements
597
- `e` of `[first, last)`, `bool(comp(e, value))` implies
598
  `!bool(comp(value, e))` for the overloads in namespace `std`.
599
 
600
  *Returns:*
601
 
602
  - For the overloads in namespace `std`:
@@ -614,25 +726,28 @@ with respect to the expressions
614
  projections.
615
 
616
  #### `binary_search` <a id="binary.search">[[binary.search]]</a>
617
 
618
  ``` cpp
619
- template<class ForwardIterator, class T>
620
  constexpr bool
621
  binary_search(ForwardIterator first, ForwardIterator last,
622
  const T& value);
623
 
624
- template<class ForwardIterator, class T, class Compare>
 
625
  constexpr bool
626
  binary_search(ForwardIterator first, ForwardIterator last,
627
  const T& value, Compare comp);
628
 
629
- template<forward_iterator I, sentinel_for<I> S, class T, class Proj = identity,
 
630
  indirect_strict_weak_order<const T*, projected<I, Proj>> Comp = ranges::less>
631
  constexpr bool ranges::binary_search(I first, S last, const T& value, Comp comp = {},
632
  Proj proj = {});
633
- template<forward_range R, class T, class Proj = identity,
 
634
  indirect_strict_weak_order<const T*, projected<iterator_t<R>, Proj>> Comp =
635
  ranges::less>
636
  constexpr bool ranges::binary_search(R&& r, const T& value, Comp comp = {},
637
  Proj proj = {});
638
  ```
@@ -642,11 +757,11 @@ parameters by those names.
642
 
643
  *Preconditions:* The elements `e` of \[`first`, `last`) are partitioned
644
  with respect to the expressions
645
  `bool(invoke(comp, invoke(proj, e), value))` and
646
  `!bool(invoke(comp, value, invoke(proj, e)))`. Also, for all elements
647
- `e` of `[first, last)`, `bool(comp(e, value))` implies
648
  `!bool(comp(value, e))` for the overloads in namespace `std`.
649
 
650
  *Returns:* `true` if and only if for some iterator `i` in the range
651
  \[`first`, `last`),
652
  `!bool(invoke(comp, invoke(proj, *i), value)) && !bool(invoke(comp, value, invoke(proj, *i)))`
@@ -668,10 +783,17 @@ template<input_iterator I, sentinel_for<I> S, class Proj = identity,
668
  indirect_unary_predicate<projected<I, Proj>> Pred>
669
  constexpr bool ranges::is_partitioned(I first, S last, Pred pred, Proj proj = {});
670
  template<input_range R, class Proj = identity,
671
  indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
672
  constexpr bool ranges::is_partitioned(R&& r, Pred pred, Proj proj = {});
 
 
 
 
 
 
 
673
  ```
674
 
675
  Let `proj` be `identity{}` for the overloads with no parameter named
676
  `proj`.
677
 
@@ -686,22 +808,29 @@ are partitioned with respect to the expression
686
  template<class ForwardIterator, class Predicate>
687
  constexpr ForwardIterator
688
  partition(ForwardIterator first, ForwardIterator last, Predicate pred);
689
  template<class ExecutionPolicy, class ForwardIterator, class Predicate>
690
  ForwardIterator
691
- partition(ExecutionPolicy&& exec,
692
- ForwardIterator first, ForwardIterator last, Predicate pred);
693
 
694
  template<permutable I, sentinel_for<I> S, class Proj = identity,
695
  indirect_unary_predicate<projected<I, Proj>> Pred>
696
  constexpr subrange<I>
697
  ranges::partition(I first, S last, Pred pred, Proj proj = {});
698
  template<forward_range R, class Proj = identity,
699
  indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
700
  requires permutable<iterator_t<R>>
701
  constexpr borrowed_subrange_t<R>
702
  ranges::partition(R&& r, Pred pred, Proj proj = {});
 
 
 
 
 
 
 
 
703
  ```
704
 
705
  Let `proj` be `identity{}` for the overloads with no parameter named
706
  `proj` and let E(x) be `bool(invoke(pred, invoke(proj, `x`)))`.
707
 
@@ -718,35 +847,47 @@ iterator `j` in \[`first`, `i`) and `false` for every iterator `j` in
718
  - `i` for the overloads in namespace `std`.
719
  - `{i, last}` for the overloads in namespace `ranges`.
720
 
721
  *Complexity:* Let N = `last - first`:
722
 
723
- - For the overload with no `ExecutionPolicy`, exactly N applications of
724
  the predicate and projection. At most N / 2 swaps if the type of
725
  `first` meets the *Cpp17BidirectionalIterator* requirements for the
726
  overloads in namespace `std` or models `bidirectional_iterator` for
727
  the overloads in namespace `ranges`, and at most N swaps otherwise.
728
- - For the overload with an `ExecutionPolicy`, 𝑂(N log N) swaps and 𝑂(N)
729
  applications of the predicate.
730
 
731
  ``` cpp
732
  template<class BidirectionalIterator, class Predicate>
733
  BidirectionalIterator
734
- stable_partition(BidirectionalIterator first, BidirectionalIterator last, Predicate pred);
 
735
  template<class ExecutionPolicy, class BidirectionalIterator, class Predicate>
736
  BidirectionalIterator
737
  stable_partition(ExecutionPolicy&& exec,
738
  BidirectionalIterator first, BidirectionalIterator last, Predicate pred);
739
 
740
  template<bidirectional_iterator I, sentinel_for<I> S, class Proj = identity,
741
  indirect_unary_predicate<projected<I, Proj>> Pred>
742
  requires permutable<I>
743
- subrange<I> ranges::stable_partition(I first, S last, Pred pred, Proj proj = {});
744
  template<bidirectional_range R, class Proj = identity,
745
  indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
746
  requires permutable<iterator_t<R>>
747
- borrowed_subrange_t<R> ranges::stable_partition(R&& r, Pred pred, Proj proj = {});
 
 
 
 
 
 
 
 
 
 
 
748
  ```
749
 
750
  Let `proj` be `identity{}` for the overloads with no parameter named
751
  `proj` and let E(x) be `bool(invoke(pred, invoke(proj, `x`)))`.
752
 
@@ -767,14 +908,14 @@ range \[`i`, `last`), E(`*j`) is `false`. Returns:
767
  - `i` for the overloads in namespace `std`.
768
  - `{i, last}` for the overloads in namespace `ranges`.
769
 
770
  *Complexity:* Let N = `last - first`:
771
 
772
- - For the overloads with no `ExecutionPolicy`, at most N log₂ N swaps,
773
- but only 𝑂(N) swaps if there is enough extra memory. Exactly N
774
  applications of the predicate and projection.
775
- - For the overload with an `ExecutionPolicy`, 𝑂(N log N) swaps and 𝑂(N)
776
  applications of the predicate.
777
 
778
  ``` cpp
779
  template<class InputIterator, class OutputIterator1, class OutputIterator2, class Predicate>
780
  constexpr pair<OutputIterator1, OutputIterator2>
@@ -798,37 +939,80 @@ template<input_range R, weakly_incrementable O1, weakly_incrementable O2,
798
  indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
799
  requires indirectly_copyable<iterator_t<R>, O1> &&
800
  indirectly_copyable<iterator_t<R>, O2>
801
  constexpr ranges::partition_copy_result<borrowed_iterator_t<R>, O1, O2>
802
  ranges::partition_copy(R&& r, O1 out_true, O2 out_false, Pred pred, Proj proj = {});
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
803
  ```
804
 
805
  Let `proj` be `identity{}` for the overloads with no parameter named
806
  `proj` and let E(x) be `bool(invoke(pred, invoke(proj, `x`)))`.
807
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
808
  *Mandates:* For the overloads in namespace `std`, the expression
809
  `*first` is writable [[iterator.requirements.general]] to `out_true` and
810
  `out_false`.
811
 
812
  *Preconditions:* The input range and output ranges do not overlap.
813
 
814
- [*Note 1*: For the overload with an `ExecutionPolicy`, there might be a
815
- performance cost if `first`’s value type does not meet the
816
- *Cpp17CopyConstructible* requirements. — *end note*]
 
 
817
 
818
- *Effects:* For each iterator `i` in \[`first`, `last`), copies `*i` to
819
- the output range beginning with `out_true` if E(`*i`) is `true`, or to
820
- the output range beginning with `out_false` otherwise.
821
 
822
- *Returns:* Let `o1` be the end of the output range beginning at
823
- `out_true`, and `o2` the end of the output range beginning at
824
- `out_false`. Returns
 
825
 
826
  - `{o1, o2}` for the overloads in namespace `std`.
827
- - `{last, o1, o2}` for the overloads in namespace `ranges`.
828
 
829
- *Complexity:* Exactly `last - first` applications of `pred` and `proj`.
830
 
831
  ``` cpp
832
  template<class ForwardIterator, class Predicate>
833
  constexpr ForwardIterator
834
  partition_point(ForwardIterator first, ForwardIterator last, Predicate pred);
@@ -896,56 +1080,87 @@ template<input_range R1, input_range R2, weakly_incrementable O, class Comp = ra
896
  class Proj1 = identity, class Proj2 = identity>
897
  requires mergeable<iterator_t<R1>, iterator_t<R2>, O, Comp, Proj1, Proj2>
898
  constexpr ranges::merge_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>, O>
899
  ranges::merge(R1&& r1, R2&& r2, O result,
900
  Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
901
  ```
902
 
903
- Let N be `(last1 - first1) + (last2 - first2)`. Let `comp` be `less{}`,
904
- `proj1` be `identity{}`, and `proj2` be `identity{}`, for the overloads
905
- with no parameters by those names.
 
 
 
 
 
 
 
 
 
 
 
 
 
 
906
 
907
  *Preconditions:* The ranges \[`first1`, `last1`) and \[`first2`,
908
  `last2`) are sorted with respect to `comp` and `proj1` or `proj2`,
909
  respectively. The resulting range does not overlap with either of the
910
  original ranges.
911
 
912
- *Effects:* Copies all the elements of the two ranges \[`first1`,
913
- `last1`) and \[`first2`, `last2`) into the range \[`result`,
914
- `result_last`), where `result_last` is `result + `N. If an element `a`
915
- precedes `b` in an input range, `a` is copied into the output range
916
- before `b`. If `e1` is an element of \[`first1`, `last1`) and `e2` of
917
- \[`first2`, `last2`), `e2` is copied into the output range before `e1`
918
- if and only if
919
- `bool(invoke(comp, invoke(proj2, e2), invoke(proj1, e1)))` is `true`.
920
 
921
  *Returns:*
922
 
923
- - `result_last` for the overloads in namespace `std`.
924
- - `{last1, last2, result_last}` for the overloads in namespace `ranges`.
 
925
 
926
  *Complexity:*
927
 
928
- - For the overloads with no `ExecutionPolicy`, at most N - 1 comparisons
929
  and applications of each projection.
930
- - For the overloads with an `ExecutionPolicy`, 𝑂(N) comparisons.
 
931
 
932
  *Remarks:* Stable [[algorithm.stable]].
933
 
934
  ``` cpp
935
  template<class BidirectionalIterator>
936
- void inplace_merge(BidirectionalIterator first,
937
  BidirectionalIterator middle,
938
  BidirectionalIterator last);
939
  template<class ExecutionPolicy, class BidirectionalIterator>
940
  void inplace_merge(ExecutionPolicy&& exec,
941
  BidirectionalIterator first,
942
  BidirectionalIterator middle,
943
  BidirectionalIterator last);
944
 
945
  template<class BidirectionalIterator, class Compare>
946
- void inplace_merge(BidirectionalIterator first,
947
  BidirectionalIterator middle,
948
  BidirectionalIterator last, Compare comp);
949
  template<class ExecutionPolicy, class BidirectionalIterator, class Compare>
950
  void inplace_merge(ExecutionPolicy&& exec,
951
  BidirectionalIterator first,
@@ -953,11 +1168,15 @@ template<class ExecutionPolicy, class BidirectionalIterator, class Compare>
953
  BidirectionalIterator last, Compare comp);
954
 
955
  template<bidirectional_iterator I, sentinel_for<I> S, class Comp = ranges::less,
956
  class Proj = identity>
957
  requires sortable<I, Comp, Proj>
958
- I ranges::inplace_merge(I first, I middle, S last, Comp comp = {}, Proj proj = {});
 
 
 
 
959
  ```
960
 
961
  Let `comp` be `less{}` and `proj` be `identity{}` for the overloads with
962
  no parameters by those names.
963
 
@@ -975,31 +1194,47 @@ and `proj`.
975
 
976
  *Returns:* `last` for the overload in namespace `ranges`.
977
 
978
  *Complexity:* Let N = `last - first`:
979
 
980
- - For the overloads with no `ExecutionPolicy`, and if enough additional
981
- memory is available, exactly N - 1 comparisons.
982
  - Otherwise, 𝑂(N log N) comparisons.
983
 
984
  In either case, twice as many projections as comparisons.
985
 
986
  *Remarks:* Stable [[algorithm.stable]].
987
 
988
  ``` cpp
989
  template<bidirectional_range R, class Comp = ranges::less, class Proj = identity>
990
  requires sortable<iterator_t<R>, Comp, Proj>
991
- borrowed_iterator_t<R>
992
  ranges::inplace_merge(R&& r, iterator_t<R> middle, Comp comp = {}, Proj proj = {});
993
  ```
994
 
995
  *Effects:* Equivalent to:
996
 
997
  ``` cpp
998
  return ranges::inplace_merge(ranges::begin(r), middle, ranges::end(r), comp, proj);
999
  ```
1000
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1001
  ### Set operations on sorted structures <a id="alg.set.operations">[[alg.set.operations]]</a>
1002
 
1003
  #### General <a id="alg.set.operations.general">[[alg.set.operations.general]]</a>
1004
 
1005
  Subclause [[alg.set.operations]] defines all the basic set operations on
@@ -1040,10 +1275,24 @@ template<input_range R1, input_range R2, class Proj1 = identity,
1040
  class Proj2 = identity,
1041
  indirect_strict_weak_order<projected<iterator_t<R1>, Proj1>,
1042
  projected<iterator_t<R2>, Proj2>> Comp = ranges::less>
1043
  constexpr bool ranges::includes(R1&& r1, R2&& r2, Comp comp = {},
1044
  Proj1 proj1 = {}, Proj2 proj2 = {});
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1045
  ```
1046
 
1047
  Let `comp` be `less{}`, `proj1` be `identity{}`, and `proj2` be
1048
  `identity{}`, for the overloads with no parameters by those names.
1049
 
@@ -1101,29 +1350,58 @@ template<input_range R1, input_range R2, weakly_incrementable O,
1101
  class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity>
1102
  requires mergeable<iterator_t<R1>, iterator_t<R2>, O, Comp, Proj1, Proj2>
1103
  constexpr ranges::set_union_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>, O>
1104
  ranges::set_union(R1&& r1, R2&& r2, O result, Comp comp = {},
1105
  Proj1 proj1 = {}, Proj2 proj2 = {});
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1106
  ```
1107
 
1108
- Let `comp` be `less{}`, and `proj1` and `proj2` be `identity{}` for the
1109
- overloads with no parameters by those names.
 
 
 
 
 
 
 
1110
 
1111
  *Preconditions:* The ranges \[`first1`, `last1`) and \[`first2`,
1112
  `last2`) are sorted with respect to `comp` and `proj1` or `proj2`,
1113
  respectively. The resulting range does not overlap with either of the
1114
  original ranges.
1115
 
1116
- *Effects:* Constructs a sorted union of the elements from the two
1117
- ranges; that is, the set of elements that are present in one or both of
1118
- the ranges.
1119
 
1120
- *Returns:* Let `result_last` be the end of the constructed range.
1121
- Returns
1122
 
1123
  - `result_last` for the overloads in namespace `std`.
1124
- - `{last1, last2, result_last}` for the overloads in namespace `ranges`.
 
 
 
 
 
1125
 
1126
  *Complexity:* At most `2 * ((last1 - first1) + (last2 - first2)) - 1`
1127
  comparisons and applications of each projection.
1128
 
1129
  *Remarks:* Stable [[algorithm.stable]]. If \[`first1`, `last1`) contains
@@ -1175,29 +1453,58 @@ template<input_range R1, input_range R2, weakly_incrementable O,
1175
  class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity>
1176
  requires mergeable<iterator_t<R1>, iterator_t<R2>, O, Comp, Proj1, Proj2>
1177
  constexpr ranges::set_intersection_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>, O>
1178
  ranges::set_intersection(R1&& r1, R2&& r2, O result,
1179
  Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1180
  ```
1181
 
1182
- Let `comp` be `less{}`, and `proj1` and `proj2` be `identity{}` for the
1183
- overloads with no parameters by those names.
 
 
 
 
 
 
 
1184
 
1185
  *Preconditions:* The ranges \[`first1`, `last1`) and \[`first2`,
1186
  `last2`) are sorted with respect to `comp` and `proj1` or `proj2`,
1187
  respectively. The resulting range does not overlap with either of the
1188
  original ranges.
1189
 
1190
- *Effects:* Constructs a sorted intersection of the elements from the two
1191
  ranges; that is, the set of elements that are present in both of the
1192
  ranges.
1193
 
1194
- *Returns:* Let `result_last` be the end of the constructed range.
1195
- Returns
1196
 
1197
  - `result_last` for the overloads in namespace `std`.
1198
- - `{last1, last2, result_last}` for the overloads in namespace `ranges`.
 
 
 
 
 
1199
 
1200
  *Complexity:* At most `2 * ((last1 - first1) + (last2 - first2)) - 1`
1201
  comparisons and applications of each projection.
1202
 
1203
  *Remarks:* Stable [[algorithm.stable]]. If \[`first1`, `last1`) contains
@@ -1247,29 +1554,56 @@ template<input_range R1, input_range R2, weakly_incrementable O,
1247
  class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity>
1248
  requires mergeable<iterator_t<R1>, iterator_t<R2>, O, Comp, Proj1, Proj2>
1249
  constexpr ranges::set_difference_result<borrowed_iterator_t<R1>, O>
1250
  ranges::set_difference(R1&& r1, R2&& r2, O result,
1251
  Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1252
  ```
1253
 
1254
- Let `comp` be `less{}`, and `proj1` and `proj2` be `identity{}` for the
1255
- overloads with no parameters by those names.
 
 
 
 
 
 
 
1256
 
1257
  *Preconditions:* The ranges \[`first1`, `last1`) and \[`first2`,
1258
  `last2`) are sorted with respect to `comp` and `proj1` or `proj2`,
1259
  respectively. The resulting range does not overlap with either of the
1260
  original ranges.
1261
 
1262
- *Effects:* Copies the elements of the range \[`first1`, `last1`) which
1263
- are not present in the range \[`first2`, `last2`) to the range beginning
1264
- at `result`. The elements in the constructed range are sorted.
1265
 
1266
- *Returns:* Let `result_last` be the end of the constructed range.
1267
- Returns
1268
 
1269
  - `result_last` for the overloads in namespace `std`.
1270
- - `{last1, result_last}` for the overloads in namespace `ranges`.
 
 
 
 
1271
 
1272
  *Complexity:* At most `2 * ((last1 - first1) + (last2 - first2)) - 1`
1273
  comparisons and applications of each projection.
1274
 
1275
  *Remarks:* If \[`first1`, `last1`) contains m elements that are
@@ -1321,31 +1655,62 @@ template<input_range R1, input_range R2, weakly_incrementable O,
1321
  requires mergeable<iterator_t<R1>, iterator_t<R2>, O, Comp, Proj1, Proj2>
1322
  constexpr ranges::set_symmetric_difference_result<borrowed_iterator_t<R1>,
1323
  borrowed_iterator_t<R2>, O>
1324
  ranges::set_symmetric_difference(R1&& r1, R2&& r2, O result, Comp comp = {},
1325
  Proj1 proj1 = {}, Proj2 proj2 = {});
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1326
  ```
1327
 
1328
- Let `comp` be `less{}`, and `proj1` and `proj2` be `identity{}` for the
1329
- overloads with no parameters by those names.
 
 
 
 
 
 
 
 
 
1330
 
1331
  *Preconditions:* The ranges \[`first1`, `last1`) and \[`first2`,
1332
  `last2`) are sorted with respect to `comp` and `proj1` or `proj2`,
1333
  respectively. The resulting range does not overlap with either of the
1334
  original ranges.
1335
 
1336
  *Effects:* Copies the elements of the range \[`first1`, `last1`) that
1337
  are not present in the range \[`first2`, `last2`), and the elements of
1338
  the range \[`first2`, `last2`) that are not present in the range
1339
- \[`first1`, `last1`) to the range beginning at `result`. The elements in
1340
- the constructed range are sorted.
1341
 
1342
- *Returns:* Let `result_last` be the end of the constructed range.
1343
- Returns
1344
 
1345
  - `result_last` for the overloads in namespace `std`.
1346
- - `{last1, last2, result_last}` for the overloads in namespace `ranges`.
 
 
 
 
 
1347
 
1348
  *Complexity:* At most `2 * ((last1 - first1) + (last2 - first2)) - 1`
1349
  comparisons and applications of each projection.
1350
 
1351
  *Remarks:* Stable [[algorithm.stable]]. If \[`first1`, `last1`) contains
@@ -1584,10 +1949,26 @@ template<random_access_range R, class Proj = identity,
1584
  ```
1585
 
1586
  *Effects:* Equivalent to:
1587
  `return ranges::is_heap_until(first, last, comp, proj) == last;`
1588
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1589
  ``` cpp
1590
  template<class RandomAccessIterator>
1591
  constexpr RandomAccessIterator
1592
  is_heap_until(RandomAccessIterator first, RandomAccessIterator last);
1593
  template<class ExecutionPolicy, class RandomAccessIterator>
@@ -1610,10 +1991,19 @@ template<random_access_iterator I, sentinel_for<I> S, class Proj = identity,
1610
  constexpr I ranges::is_heap_until(I first, S last, Comp comp = {}, Proj proj = {});
1611
  template<random_access_range R, class Proj = identity,
1612
  indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
1613
  constexpr borrowed_iterator_t<R>
1614
  ranges::is_heap_until(R&& r, Comp comp = {}, Proj proj = {});
 
 
 
 
 
 
 
 
 
1615
  ```
1616
 
1617
  Let `comp` be `less{}` and `proj` be `identity{}` for the overloads with
1618
  no parameters by those names.
1619
 
@@ -1659,10 +2049,15 @@ template<copyable T, class Proj = identity,
1659
  template<input_range R, class Proj = identity,
1660
  indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
1661
  requires indirectly_copyable_storable<iterator_t<R>, range_value_t<R>*>
1662
  constexpr range_value_t<R>
1663
  ranges::min(R&& r, Comp comp = {}, Proj proj = {});
 
 
 
 
 
1664
  ```
1665
 
1666
  *Preconditions:* `ranges::distance(r) > 0`. For the overloads in
1667
  namespace `std`, `T` meets the *Cpp17CopyConstructible* requirements.
1668
  For the first form, `T` meets the *Cpp17LessThanComparable* requirements
@@ -1712,10 +2107,15 @@ template<copyable T, class Proj = identity,
1712
  template<input_range R, class Proj = identity,
1713
  indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
1714
  requires indirectly_copyable_storable<iterator_t<R>, range_value_t<R>*>
1715
  constexpr range_value_t<R>
1716
  ranges::max(R&& r, Comp comp = {}, Proj proj = {});
 
 
 
 
 
1717
  ```
1718
 
1719
  *Preconditions:* `ranges::distance(r) > 0`. For the overloads in
1720
  namespace `std`, `T` meets the *Cpp17CopyConstructible* requirements.
1721
  For the first form, `T` meets the *Cpp17LessThanComparable* requirements
@@ -1766,10 +2166,15 @@ template<copyable T, class Proj = identity,
1766
  template<input_range R, class Proj = identity,
1767
  indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
1768
  requires indirectly_copyable_storable<iterator_t<R>, range_value_t<R>*>
1769
  constexpr ranges::minmax_result<range_value_t<R>>
1770
  ranges::minmax(R&& r, Comp comp = {}, Proj proj = {});
 
 
 
 
 
1771
  ```
1772
 
1773
  *Preconditions:* `ranges::distance(r) > 0`. For the overloads in
1774
  namespace `std`, `T` meets the *Cpp17CopyConstructible* requirements.
1775
  For the first form, type `T` meets the *Cpp17LessThanComparable*
@@ -1806,10 +2211,20 @@ template<forward_iterator I, sentinel_for<I> S, class Proj = identity,
1806
  constexpr I ranges::min_element(I first, S last, Comp comp = {}, Proj proj = {});
1807
  template<forward_range R, class Proj = identity,
1808
  indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
1809
  constexpr borrowed_iterator_t<R>
1810
  ranges::min_element(R&& r, Comp comp = {}, Proj proj = {});
 
 
 
 
 
 
 
 
 
 
1811
  ```
1812
 
1813
  Let `comp` be `less{}` and `proj` be `identity{}` for the overloads with
1814
  no parameters by those names.
1815
 
@@ -1845,10 +2260,20 @@ template<forward_iterator I, sentinel_for<I> S, class Proj = identity,
1845
  constexpr I ranges::max_element(I first, S last, Comp comp = {}, Proj proj = {});
1846
  template<forward_range R, class Proj = identity,
1847
  indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
1848
  constexpr borrowed_iterator_t<R>
1849
  ranges::max_element(R&& r, Comp comp = {}, Proj proj = {});
 
 
 
 
 
 
 
 
 
 
1850
  ```
1851
 
1852
  Let `comp` be `less{}` and `proj` be `identity{}` for the overloads with
1853
  no parameters by those names.
1854
 
@@ -1887,10 +2312,20 @@ template<forward_iterator I, sentinel_for<I> S, class Proj = identity,
1887
  ranges::minmax_element(I first, S last, Comp comp = {}, Proj proj = {});
1888
  template<forward_range R, class Proj = identity,
1889
  indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
1890
  constexpr ranges::minmax_element_result<borrowed_iterator_t<R>>
1891
  ranges::minmax_element(R&& r, Comp comp = {}, Proj proj = {});
 
 
 
 
 
 
 
 
 
 
1892
  ```
1893
 
1894
  *Returns:* `{first, first}` if \[`first`, `last`) is empty, otherwise
1895
  `{m, M}`, where `m` is the first iterator in \[`first`, `last`) such
1896
  that no iterator in the range refers to a smaller element, and where `M`
@@ -1973,10 +2408,24 @@ template<input_range R1, input_range R2, class Proj1 = identity,
1973
  indirect_strict_weak_order<projected<iterator_t<R1>, Proj1>,
1974
  projected<iterator_t<R2>, Proj2>> Comp = ranges::less>
1975
  constexpr bool
1976
  ranges::lexicographical_compare(R1&& r1, R2&& r2, Comp comp = {},
1977
  Proj1 proj1 = {}, Proj2 proj2 = {});
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1978
  ```
1979
 
1980
  *Returns:* `true` if and only if the sequence of elements defined by the
1981
  range \[`first1`, `last1`) is lexicographically less than the sequence
1982
  of elements defined by the range \[`first2`, `last2`).
 
94
  ranges::sort(I first, S last, Comp comp = {}, Proj proj = {});
95
  template<random_access_range R, class Comp = ranges::less, class Proj = identity>
96
  requires sortable<iterator_t<R>, Comp, Proj>
97
  constexpr borrowed_iterator_t<R>
98
  ranges::sort(R&& r, Comp comp = {}, Proj proj = {});
99
+
100
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
101
+ class Comp = ranges::less, class Proj = identity>
102
+ requires sortable<I, Comp, Proj>
103
+ I ranges::sort(Ep&& exec, I first, S last, Comp comp = {}, Proj proj = {});
104
+ template<execution-policy Ep, sized-random-access-range R, class Comp = ranges::less,
105
+ class Proj = identity>
106
+ requires sortable<iterator_t<R>, Comp, Proj>
107
+ borrowed_iterator_t<R> ranges::sort(Ep&& exec, R&& r, Comp comp = {}, Proj proj = {});
108
  ```
109
 
110
  Let `comp` be `less{}` and `proj` be `identity{}` for the overloads with
111
  no parameters by those names.
112
 
 
126
 
127
  #### `stable_sort` <a id="stable.sort">[[stable.sort]]</a>
128
 
129
  ``` cpp
130
  template<class RandomAccessIterator>
131
+ constexpr void stable_sort(RandomAccessIterator first, RandomAccessIterator last);
132
  template<class ExecutionPolicy, class RandomAccessIterator>
133
  void stable_sort(ExecutionPolicy&& exec,
134
  RandomAccessIterator first, RandomAccessIterator last);
135
 
136
  template<class RandomAccessIterator, class Compare>
137
+ constexpr void stable_sort(RandomAccessIterator first, RandomAccessIterator last,
138
  Compare comp);
139
  template<class ExecutionPolicy, class RandomAccessIterator, class Compare>
140
  void stable_sort(ExecutionPolicy&& exec,
141
  RandomAccessIterator first, RandomAccessIterator last,
142
  Compare comp);
143
 
144
  template<random_access_iterator I, sentinel_for<I> S, class Comp = ranges::less,
145
  class Proj = identity>
146
  requires sortable<I, Comp, Proj>
147
+ constexpr I ranges::stable_sort(I first, S last, Comp comp = {}, Proj proj = {});
148
  template<random_access_range R, class Comp = ranges::less, class Proj = identity>
149
  requires sortable<iterator_t<R>, Comp, Proj>
150
+ constexpr borrowed_iterator_t<R>
151
  ranges::stable_sort(R&& r, Comp comp = {}, Proj proj = {});
152
+
153
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
154
+ class Comp = ranges::less, class Proj = identity>
155
+ requires sortable<I, Comp, Proj>
156
+ I ranges::stable_sort(Ep&& exec, I first, S last, Comp comp = {}, Proj proj = {});
157
+ template<execution-policy Ep, sized-random-access-range R, class Comp = ranges::less,
158
+ class Proj = identity>
159
+ requires sortable<iterator_t<R>, Comp, Proj>
160
+ borrowed_iterator_t<R>
161
+ ranges::stable_sort(Ep&& exec, R&& r, Comp comp = {}, Proj proj = {});
162
  ```
163
 
164
  Let `comp` be `less{}` and `proj` be `identity{}` for the overloads with
165
  no parameters by those names.
166
 
 
210
  template<random_access_iterator I, sentinel_for<I> S, class Comp = ranges::less,
211
  class Proj = identity>
212
  requires sortable<I, Comp, Proj>
213
  constexpr I
214
  ranges::partial_sort(I first, I middle, S last, Comp comp = {}, Proj proj = {});
215
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
216
+ class Comp = ranges::less, class Proj = identity>
217
+ requires sortable<I, Comp, Proj>
218
+ I ranges::partial_sort(Ep&& exec, I first, I middle, S last, Comp comp = {}, Proj proj = {});
219
  ```
220
 
221
  Let `comp` be `less{}` and `proj` be `identity{}` for the overloads with
222
  no parameters by those names.
223
 
 
249
 
250
  ``` cpp
251
  return ranges::partial_sort(ranges::begin(r), middle, ranges::end(r), comp, proj);
252
  ```
253
 
254
+ ``` cpp
255
+ template<execution-policy Ep, sized-random-access-range R,
256
+ class Comp = ranges::less, class Proj = identity>
257
+ requires sortable<iterator_t<R>, Comp, Proj>
258
+ borrowed_iterator_t<R>
259
+ ranges::partial_sort(Ep&& exec, R&& r, iterator_t<R> middle, Comp comp = {},
260
+ Proj proj = {});
261
+ ```
262
+
263
+ *Effects:* Equivalent to:
264
+
265
+ ``` cpp
266
+ return ranges::partial_sort(std::forward<Ep>(exec), ranges::begin(r), middle,
267
+ ranges::end(r), comp, proj);
268
+ ```
269
+
270
  #### `partial_sort_copy` <a id="partial.sort.copy">[[partial.sort.copy]]</a>
271
 
272
  ``` cpp
273
  template<class InputIterator, class RandomAccessIterator>
274
  constexpr RandomAccessIterator
 
312
  indirect_strict_weak_order<Comp, projected<iterator_t<R1>, Proj1>,
313
  projected<iterator_t<R2>, Proj2>>
314
  constexpr ranges::partial_sort_copy_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>>
315
  ranges::partial_sort_copy(R1&& r, R2&& result_r, Comp comp = {},
316
  Proj1 proj1 = {}, Proj2 proj2 = {});
317
+
318
+ template<execution-policy Ep, random_access_iterator I1, sized_sentinel_for<I1> S1,
319
+ random_access_iterator I2, sized_sentinel_for<I2> S2,
320
+ class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity>
321
+ requires indirectly_copyable<I1, I2> && sortable<I2, Comp, Proj2> &&
322
+ indirect_strict_weak_order<Comp, projected<I1, Proj1>, projected<I2, Proj2>>
323
+ ranges::partial_sort_copy_result<I1, I2>
324
+ ranges::partial_sort_copy(Ep&& exec, I1 first, S1 last, I2 result_first, S2 result_last,
325
+ Comp comp = {}, Proj1 proj1 = {},
326
+ Proj2 proj2 = {});
327
+ template<execution-policy Ep, sized-random-access-range R1, sized-random-access-range R2,
328
+ class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity>
329
+ requires indirectly_copyable<iterator_t<R1>, iterator_t<R2>> &&
330
+ sortable<iterator_t<R2>, Comp, Proj2> &&
331
+ indirect_strict_weak_order<Comp, projected<iterator_t<R1>, Proj1>,
332
+ projected<iterator_t<R2>, Proj2>>
333
+ ranges::partial_sort_copy_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>>
334
+ ranges::partial_sort_copy(Ep&& exec, R1&& r, R2&& result_r, Comp comp = {},
335
+ Proj1 proj1 = {}, Proj2 proj2 = {});
336
  ```
337
 
338
  Let N be min(`last - first`, `result_last - result_first`). Let `comp`
339
  be `less{}`, and `proj1` and `proj2` be `identity{}` for the overloads
340
  with no parameters by those names.
 
431
  ```
432
 
433
  *Effects:* Equivalent to:
434
  `return ranges::is_sorted_until(first, last, comp, proj) == last;`
435
 
436
+ ``` cpp
437
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
438
+ class Proj = identity,
439
+ indirect_strict_weak_order<projected<I, Proj>> Comp = ranges::less>
440
+ bool ranges::is_sorted(Ep&& exec, I first, S last, Comp comp = {}, Proj proj = {});
441
+ template<execution-policy Ep, sized-random-access-range R, class Proj = identity,
442
+ indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
443
+ bool ranges::is_sorted(Ep&& exec, R&& r, Comp comp = {}, Proj proj = {});
444
+ ```
445
+
446
+ *Effects:* Equivalent to:
447
+
448
+ ``` cpp
449
+ return ranges::is_sorted_until(std::forward<Ep>(exec), first, last, comp, proj) == last;
450
+ ```
451
+
452
  ``` cpp
453
  template<class ForwardIterator>
454
  constexpr ForwardIterator
455
  is_sorted_until(ForwardIterator first, ForwardIterator last);
456
  template<class ExecutionPolicy, class ForwardIterator>
 
473
  constexpr I ranges::is_sorted_until(I first, S last, Comp comp = {}, Proj proj = {});
474
  template<forward_range R, class Proj = identity,
475
  indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
476
  constexpr borrowed_iterator_t<R>
477
  ranges::is_sorted_until(R&& r, Comp comp = {}, Proj proj = {});
478
+
479
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
480
+ class Proj = identity,
481
+ indirect_strict_weak_order<projected<I, Proj>> Comp = ranges::less>
482
+ I ranges::is_sorted_until(Ep&& exec, I first, S last, Comp comp = {},
483
+ Proj proj = {});
484
+ template<execution-policy Ep, sized-random-access-range R, class Proj = identity,
485
+ indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
486
+ borrowed_iterator_t<R>
487
+ ranges::is_sorted_until(Ep&& exec, R&& r, Comp comp = {}, Proj proj = {});
488
  ```
489
 
490
  Let `comp` be `less{}` and `proj` be `identity{}` for the overloads with
491
  no parameters by those names.
492
 
 
517
  template<random_access_iterator I, sentinel_for<I> S, class Comp = ranges::less,
518
  class Proj = identity>
519
  requires sortable<I, Comp, Proj>
520
  constexpr I
521
  ranges::nth_element(I first, I nth, S last, Comp comp = {}, Proj proj = {});
522
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
523
+ class Comp = ranges::less, class Proj = identity>
524
+ requires sortable<I, Comp, Proj>
525
+ I ranges::nth_element(Ep&& exec, I first, I nth, S last, Comp comp = {}, Proj proj = {});
526
  ```
527
 
528
  Let `comp` be `less{}` and `proj` be `identity{}` for the overloads with
529
  no parameters by those names.
530
 
 
542
  iterator `j` in the range \[`nth`, `last`) it holds that:
543
  `bool(invoke(comp, invoke(proj, *j), invoke(proj, *i)))` is `false`.
544
 
545
  *Returns:* `last` for the overload in namespace `ranges`.
546
 
547
+ *Complexity:* For the non-parallel algorithm overloads, linear on
548
+ average. For the parallel algorithm overloads, 𝑂(N) applications of the
549
+ predicate, and 𝑂(N log N) swaps, where N = `last - first`.
550
 
551
  ``` cpp
552
  template<random_access_range R, class Comp = ranges::less, class Proj = identity>
553
  requires sortable<iterator_t<R>, Comp, Proj>
554
  constexpr borrowed_iterator_t<R>
 
559
 
560
  ``` cpp
561
  return ranges::nth_element(ranges::begin(r), nth, ranges::end(r), comp, proj);
562
  ```
563
 
564
+ ``` cpp
565
+ template<execution-policy Ep, sized-random-access-range R, class Comp = ranges::less,
566
+ class Proj = identity>
567
+ requires sortable<iterator_t<R>, Comp, Proj>
568
+ borrowed_iterator_t<R>
569
+ ranges::nth_element(Ep&& exec, R&& r, iterator_t<R> nth, Comp comp = {}, Proj proj = {});
570
+ ```
571
+
572
+ *Effects:* Equivalent to:
573
+
574
+ ``` cpp
575
+ return ranges::nth_element(std::forward<Ep>(exec), ranges::begin(r), nth, ranges::end(r),
576
+ comp, proj);
577
+ ```
578
+
579
  ### Binary search <a id="alg.binary.search">[[alg.binary.search]]</a>
580
 
581
  #### General <a id="alg.binary.search.general">[[alg.binary.search.general]]</a>
582
 
583
  All of the algorithms in [[alg.binary.search]] are versions of binary
 
591
  a linear number of steps.
592
 
593
  #### `lower_bound` <a id="lower.bound">[[lower.bound]]</a>
594
 
595
  ``` cpp
596
+ template<class ForwardIterator, class T = iterator_traits<ForwardIterator>::value_type>
597
  constexpr ForwardIterator
598
  lower_bound(ForwardIterator first, ForwardIterator last,
599
  const T& value);
600
 
601
+ template<class ForwardIterator, class T = iterator_traits<ForwardIterator>::value_type,
602
+ class Compare>
603
  constexpr ForwardIterator
604
  lower_bound(ForwardIterator first, ForwardIterator last,
605
  const T& value, Compare comp);
606
 
607
+ template<forward_iterator I, sentinel_for<I> S, class Proj = identity,
608
+ class T = projected_value_t<I, Proj>,
609
  indirect_strict_weak_order<const T*, projected<I, Proj>> Comp = ranges::less>
610
  constexpr I ranges::lower_bound(I first, S last, const T& value, Comp comp = {},
611
  Proj proj = {});
612
+ template<forward_range R, class Proj = identity,
613
+ class T = projected_value_t<iterator_t<R>, Proj>,
614
  indirect_strict_weak_order<const T*, projected<iterator_t<R>, Proj>> Comp =
615
  ranges::less>
616
  constexpr borrowed_iterator_t<R>
617
  ranges::lower_bound(R&& r, const T& value, Comp comp = {}, Proj proj = {});
618
  ```
 
632
  projections.
633
 
634
  #### `upper_bound` <a id="upper.bound">[[upper.bound]]</a>
635
 
636
  ``` cpp
637
+ template<class ForwardIterator, class T = iterator_traits<ForwardIterator>::value_type>
638
  constexpr ForwardIterator
639
  upper_bound(ForwardIterator first, ForwardIterator last,
640
  const T& value);
641
 
642
+ template<class ForwardIterator, class T = iterator_traits<ForwardIterator>::value_type,
643
+ class Compare>
644
  constexpr ForwardIterator
645
  upper_bound(ForwardIterator first, ForwardIterator last,
646
  const T& value, Compare comp);
647
 
648
+ template<forward_iterator I, sentinel_for<I> S, class Proj = identity,
649
+ class T = projected_value_t<I, Proj>,
650
  indirect_strict_weak_order<const T*, projected<I, Proj>> Comp = ranges::less>
651
  constexpr I ranges::upper_bound(I first, S last, const T& value, Comp comp = {}, Proj proj = {});
652
+ template<forward_range R, class Proj = identity,
653
+ class T = projected_value_t<iterator_t<R>, Proj>,
654
  indirect_strict_weak_order<const T*, projected<iterator_t<R>, Proj>> Comp =
655
  ranges::less>
656
  constexpr borrowed_iterator_t<R>
657
  ranges::upper_bound(R&& r, const T& value, Comp comp = {}, Proj proj = {});
658
  ```
 
672
  projections.
673
 
674
  #### `equal_range` <a id="equal.range">[[equal.range]]</a>
675
 
676
  ``` cpp
677
+ template<class ForwardIterator, class T = iterator_traits<ForwardIterator>::value_type>
678
  constexpr pair<ForwardIterator, ForwardIterator>
679
  equal_range(ForwardIterator first,
680
  ForwardIterator last, const T& value);
681
 
682
+ template<class ForwardIterator, class T = iterator_traits<ForwardIterator>::value_type,
683
+ class Compare>
684
  constexpr pair<ForwardIterator, ForwardIterator>
685
  equal_range(ForwardIterator first,
686
  ForwardIterator last, const T& value,
687
  Compare comp);
688
 
689
+ template<forward_iterator I, sentinel_for<I> S, class Proj = identity,
690
+ class T = projected_value_t<I, Proj>,
691
  indirect_strict_weak_order<const T*, projected<I, Proj>> Comp = ranges::less>
692
  constexpr subrange<I>
693
  ranges::equal_range(I first, S last, const T& value, Comp comp = {}, Proj proj = {});
694
+ template<forward_range R, class Proj = identity,
695
+ class T = projected_value_t<iterator_t<R>, Proj>,
696
  indirect_strict_weak_order<const T*, projected<iterator_t<R>, Proj>> Comp =
697
  ranges::less>
698
  constexpr borrowed_subrange_t<R>
699
  ranges::equal_range(R&& r, const T& value, Comp comp = {}, Proj proj = {});
700
  ```
 
704
 
705
  *Preconditions:* The elements `e` of \[`first`, `last`) are partitioned
706
  with respect to the expressions
707
  `bool(invoke(comp, invoke(proj, e), value))` and
708
  `!bool(invoke(comp, value, invoke(proj, e)))`. Also, for all elements
709
+ `e` of \[`first`, `last`), `bool(comp(e, value))` implies
710
  `!bool(comp(value, e))` for the overloads in namespace `std`.
711
 
712
  *Returns:*
713
 
714
  - For the overloads in namespace `std`:
 
726
  projections.
727
 
728
  #### `binary_search` <a id="binary.search">[[binary.search]]</a>
729
 
730
  ``` cpp
731
+ template<class ForwardIterator, class T = iterator_traits<ForwardIterator>::value_type>
732
  constexpr bool
733
  binary_search(ForwardIterator first, ForwardIterator last,
734
  const T& value);
735
 
736
+ template<class ForwardIterator, class T = iterator_traits<ForwardIterator>::value_type,
737
+ class Compare>
738
  constexpr bool
739
  binary_search(ForwardIterator first, ForwardIterator last,
740
  const T& value, Compare comp);
741
 
742
+ template<forward_iterator I, sentinel_for<I> S, class Proj = identity,
743
+ class T = projected_value_t<I, Proj>,
744
  indirect_strict_weak_order<const T*, projected<I, Proj>> Comp = ranges::less>
745
  constexpr bool ranges::binary_search(I first, S last, const T& value, Comp comp = {},
746
  Proj proj = {});
747
+ template<forward_range R, class Proj = identity,
748
+ class T = projected_value_t<iterator_t<R>, Proj>,
749
  indirect_strict_weak_order<const T*, projected<iterator_t<R>, Proj>> Comp =
750
  ranges::less>
751
  constexpr bool ranges::binary_search(R&& r, const T& value, Comp comp = {},
752
  Proj proj = {});
753
  ```
 
757
 
758
  *Preconditions:* The elements `e` of \[`first`, `last`) are partitioned
759
  with respect to the expressions
760
  `bool(invoke(comp, invoke(proj, e), value))` and
761
  `!bool(invoke(comp, value, invoke(proj, e)))`. Also, for all elements
762
+ `e` of \[`first`, `last`), `bool(comp(e, value))` implies
763
  `!bool(comp(value, e))` for the overloads in namespace `std`.
764
 
765
  *Returns:* `true` if and only if for some iterator `i` in the range
766
  \[`first`, `last`),
767
  `!bool(invoke(comp, invoke(proj, *i), value)) && !bool(invoke(comp, value, invoke(proj, *i)))`
 
783
  indirect_unary_predicate<projected<I, Proj>> Pred>
784
  constexpr bool ranges::is_partitioned(I first, S last, Pred pred, Proj proj = {});
785
  template<input_range R, class Proj = identity,
786
  indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
787
  constexpr bool ranges::is_partitioned(R&& r, Pred pred, Proj proj = {});
788
+
789
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
790
+ class Proj = identity, indirect_unary_predicate<projected<I, Proj>> Pred>
791
+ bool ranges::is_partitioned(Ep&& exec, I first, S last, Pred pred, Proj proj = {});
792
+ template<execution-policy Ep, sized-random-access-range R, class Proj = identity,
793
+ indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
794
+ bool ranges::is_partitioned(Ep&& exec, R&& r, Pred pred, Proj proj = {});
795
  ```
796
 
797
  Let `proj` be `identity{}` for the overloads with no parameter named
798
  `proj`.
799
 
 
808
  template<class ForwardIterator, class Predicate>
809
  constexpr ForwardIterator
810
  partition(ForwardIterator first, ForwardIterator last, Predicate pred);
811
  template<class ExecutionPolicy, class ForwardIterator, class Predicate>
812
  ForwardIterator
813
+ partition(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last, Predicate pred);
 
814
 
815
  template<permutable I, sentinel_for<I> S, class Proj = identity,
816
  indirect_unary_predicate<projected<I, Proj>> Pred>
817
  constexpr subrange<I>
818
  ranges::partition(I first, S last, Pred pred, Proj proj = {});
819
  template<forward_range R, class Proj = identity,
820
  indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
821
  requires permutable<iterator_t<R>>
822
  constexpr borrowed_subrange_t<R>
823
  ranges::partition(R&& r, Pred pred, Proj proj = {});
824
+
825
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
826
+ class Proj = identity, indirect_unary_predicate<projected<I, Proj>> Pred>
827
+ subrange<I> ranges::partition(Ep&& exec, I first, S last, Pred pred, Proj proj = {});
828
+ template<execution-policy Ep, sized-random-access-range R, class Proj = identity,
829
+ indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
830
+ requires permutable<iterator_t<R>>
831
+ borrowed_subrange_t<R> ranges::partition(Ep&& exec, R&& r, Pred pred, Proj proj = {});
832
  ```
833
 
834
  Let `proj` be `identity{}` for the overloads with no parameter named
835
  `proj` and let E(x) be `bool(invoke(pred, invoke(proj, `x`)))`.
836
 
 
847
  - `i` for the overloads in namespace `std`.
848
  - `{i, last}` for the overloads in namespace `ranges`.
849
 
850
  *Complexity:* Let N = `last - first`:
851
 
852
+ - For the non-parallel algorithm overloads, exactly N applications of
853
  the predicate and projection. At most N / 2 swaps if the type of
854
  `first` meets the *Cpp17BidirectionalIterator* requirements for the
855
  overloads in namespace `std` or models `bidirectional_iterator` for
856
  the overloads in namespace `ranges`, and at most N swaps otherwise.
857
+ - For the parallel algorithm overloads, 𝑂(N log N) swaps and 𝑂(N)
858
  applications of the predicate.
859
 
860
  ``` cpp
861
  template<class BidirectionalIterator, class Predicate>
862
  BidirectionalIterator
863
+ constexpr stable_partition(BidirectionalIterator first, BidirectionalIterator last,
864
+ Predicate pred);
865
  template<class ExecutionPolicy, class BidirectionalIterator, class Predicate>
866
  BidirectionalIterator
867
  stable_partition(ExecutionPolicy&& exec,
868
  BidirectionalIterator first, BidirectionalIterator last, Predicate pred);
869
 
870
  template<bidirectional_iterator I, sentinel_for<I> S, class Proj = identity,
871
  indirect_unary_predicate<projected<I, Proj>> Pred>
872
  requires permutable<I>
873
+ constexpr subrange<I> ranges::stable_partition(I first, S last, Pred pred, Proj proj = {});
874
  template<bidirectional_range R, class Proj = identity,
875
  indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
876
  requires permutable<iterator_t<R>>
877
+ constexpr borrowed_subrange_t<R> ranges::stable_partition(R&& r, Pred pred, Proj proj = {});
878
+
879
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
880
+ class Proj = identity, indirect_unary_predicate<projected<I, Proj>> Pred>
881
+ requires permutable<I>
882
+ subrange<I>
883
+ ranges::stable_partition(Ep&& exec, I first, S last, Pred pred, Proj proj = {});
884
+ template<execution-policy Ep, sized-random-access-range R, class Proj = identity,
885
+ indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
886
+ requires permutable<iterator_t<R>>
887
+ borrowed_subrange_t<R>
888
+ ranges::stable_partition(Ep&& exec, R&& r, Pred pred, Proj proj = {});
889
  ```
890
 
891
  Let `proj` be `identity{}` for the overloads with no parameter named
892
  `proj` and let E(x) be `bool(invoke(pred, invoke(proj, `x`)))`.
893
 
 
908
  - `i` for the overloads in namespace `std`.
909
  - `{i, last}` for the overloads in namespace `ranges`.
910
 
911
  *Complexity:* Let N = `last - first`:
912
 
913
+ - For the non-parallel algorithm overloads, at most N log₂ N swaps, but
914
+ only 𝑂(N) swaps if there is enough extra memory. Exactly N
915
  applications of the predicate and projection.
916
+ - For the parallel algorithm overloads, 𝑂(N log N) swaps and 𝑂(N)
917
  applications of the predicate.
918
 
919
  ``` cpp
920
  template<class InputIterator, class OutputIterator1, class OutputIterator2, class Predicate>
921
  constexpr pair<OutputIterator1, OutputIterator2>
 
939
  indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
940
  requires indirectly_copyable<iterator_t<R>, O1> &&
941
  indirectly_copyable<iterator_t<R>, O2>
942
  constexpr ranges::partition_copy_result<borrowed_iterator_t<R>, O1, O2>
943
  ranges::partition_copy(R&& r, O1 out_true, O2 out_false, Pred pred, Proj proj = {});
944
+
945
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
946
+ random_access_iterator O1, sized_sentinel_for<O1> OutS1,
947
+ random_access_iterator O2, sized_sentinel_for<O2> OutS2,
948
+ class Proj = identity, indirect_unary_predicate<projected<I, Proj>> Pred>
949
+ requires indirectly_copyable<I, O1> && indirectly_copyable<I, O2>
950
+ ranges::partition_copy_result<I, O1, O2>
951
+ ranges::partition_copy(Ep&& exec, I first, S last, O1 out_true, OutS1 last_true,
952
+ O2 out_false, OutS2 last_false, Pred pred, Proj proj = {});
953
+ template<execution-policy Ep, sized-random-access-range R,
954
+ sized-random-access-range OutR1, sized-random-access-range OutR2,
955
+ class Proj = identity,
956
+ indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
957
+ requires indirectly_copyable<iterator_t<R>, iterator_t<OutR1>> &&
958
+ indirectly_copyable<iterator_t<R>, iterator_t<OutR2>>
959
+ ranges::partition_copy_result<borrowed_iterator_t<R>, borrowed_iterator_t<OutR1>,
960
+ borrowed_iterator_t<OutR2>>
961
+ ranges::partition_copy(Ep&& exec, R&& r, OutR1&& out_true_r, OutR2&& out_false_r,
962
+ Pred pred, Proj proj = {});
963
  ```
964
 
965
  Let `proj` be `identity{}` for the overloads with no parameter named
966
  `proj` and let E(x) be `bool(invoke(pred, invoke(proj, `x`)))`.
967
 
968
+ For the overloads with no parameters `last_true`, `last_false`,
969
+ `out_true_r`, or `out_false_r`, let
970
+
971
+ - M be the number of iterators `i` in \[`first`, `last`) for which
972
+ E(`*i`) is `true`, and K be `last - first - `M;
973
+ - `last_true` be `out_true + `M, and `last_false` be `out_false + `K.
974
+
975
+ For the overloads with parameters `last_true`, `last_false`,
976
+ `out_true_r`, or `out_false_r`, let M be `last_true - out_true` and K be
977
+ `last_false - out_false`.
978
+
979
+ Let:
980
+
981
+ - `i1` be the iterator in \[`first`, `last`) for which E(`*i1`) is
982
+ `true` and there are exactly M iterators `j` in \[`first`, `i1`) for
983
+ which E(`*j`) is `true`, or `last` if no such iterator exists;
984
+ - `i2` be the iterator in \[`first`, `last`) for which E(`*i2`) is
985
+ `false` and there are exactly K iterators `j` in \[`first`, `i2`) for
986
+ which E(`*j`) is `false`, or `last` if no such iterator exists;
987
+ - N be min(`i1 - first`, `i2 - first`).
988
+
989
  *Mandates:* For the overloads in namespace `std`, the expression
990
  `*first` is writable [[iterator.requirements.general]] to `out_true` and
991
  `out_false`.
992
 
993
  *Preconditions:* The input range and output ranges do not overlap.
994
 
995
+ [*Note 1*: For the parallel algorithm overload in namespace `std`,
996
+ there can be a performance cost if `first`’s value type does not meet
997
+ the *Cpp17CopyConstructible* requirements. For the parallel algorithm
998
+ overloads in namespace `ranges`, there can be a performance cost if
999
+ `first`’s value type does not model `copy_constructible`. — *end note*]
1000
 
1001
+ *Effects:* For each iterator `i` in \[`first`, `first + `N), copies `*i`
1002
+ to the output range \[`out_true`, `last_true`) if E(`*i`) is `true`, or
1003
+ to the output range \[`out_false`, `last_false`) otherwise.
1004
 
1005
+ *Returns:* Let `o1` be the iterator past the last copied element in the
1006
+ output range \[`out_true`, `last_true`), and `o2` be the iterator past
1007
+ the last copied element in the output range \[`out_false`,
1008
+ `last_false`). Returns:
1009
 
1010
  - `{o1, o2}` for the overloads in namespace `std`.
1011
+ - `{first + `N`, o1, o2}` for the overloads in namespace `ranges`.
1012
 
1013
+ *Complexity:* At most `last - first` applications of `pred` and `proj`.
1014
 
1015
  ``` cpp
1016
  template<class ForwardIterator, class Predicate>
1017
  constexpr ForwardIterator
1018
  partition_point(ForwardIterator first, ForwardIterator last, Predicate pred);
 
1080
  class Proj1 = identity, class Proj2 = identity>
1081
  requires mergeable<iterator_t<R1>, iterator_t<R2>, O, Comp, Proj1, Proj2>
1082
  constexpr ranges::merge_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>, O>
1083
  ranges::merge(R1&& r1, R2&& r2, O result,
1084
  Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
1085
+
1086
+ template<execution-policy Ep, random_access_iterator I1, sized_sentinel_for<I1> S1,
1087
+ random_access_iterator I2, sized_sentinel_for<I2> S2,
1088
+ random_access_iterator O, sized_sentinel_for<O> OutS, class Comp = ranges::less,
1089
+ class Proj1 = identity, class Proj2 = identity>
1090
+ requires mergeable<I1, I2, O, Comp, Proj1, Proj2>
1091
+ ranges::merge_result<I1, I2, O>
1092
+ ranges::merge(Ep&& exec, I1 first1, S1 last1, I2 first2, S2 last2, O result, OutS result_last,
1093
+ Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
1094
+ template<execution-policy Ep, sized-random-access-range R1, sized-random-access-range R2,
1095
+ sized-random-access-range OutR, class Comp = ranges::less,
1096
+ class Proj1 = identity, class Proj2 = identity>
1097
+ requires mergeable<iterator_t<R1>, iterator_t<R2>, iterator_t<OutR>, Comp, Proj1, Proj2>
1098
+ ranges::merge_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>, borrowed_iterator_t<OutR>>
1099
+ ranges::merge(Ep&& exec, R1&& r1, R2&& r2, OutR&& result_r,
1100
+ Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
1101
  ```
1102
 
1103
+ Let:
1104
+
1105
+ - N be:
1106
+ - `(last1 - first1) + (last2 - first2)` for the overloads with no
1107
+ parameter `result_last` or `result_r`;
1108
+ - min(`(last1 - first1) + (last2 - first2)`, `result_last - result`)
1109
+ for the overloads with parameters `result_last` or `result_r`;
1110
+ - `comp` be `less{}`, `proj1` be `identity{}`, and `proj2` be
1111
+ `identity{}`, for the overloads with no parameters by those names;
1112
+ - E(`e1`, `e1`) be
1113
+ `bool(invoke(comp, invoke(proj2, e2), invoke(proj1, e1)))`;
1114
+ - K be the smallest integer in \[`0`, `last1 - first1`) such that for
1115
+ the element `e1` in the position `first1 + `K there are at least N - K
1116
+ elements `e2` in \[`first2`, `last2`) for which E(`e1`, `e1`) holds,
1117
+ and be equal to `last1 - first1` if no such integer exists.
1118
+ \[*Note 1*: `first1 + `K points to the position past the last element
1119
+ to be copied. — *end note*]
1120
 
1121
  *Preconditions:* The ranges \[`first1`, `last1`) and \[`first2`,
1122
  `last2`) are sorted with respect to `comp` and `proj1` or `proj2`,
1123
  respectively. The resulting range does not overlap with either of the
1124
  original ranges.
1125
 
1126
+ *Effects:* Copies the first K elements of the range \[`first1`, `last1`)
1127
+ and the first N - K elements of the range \[`first2`, `last2`) into the
1128
+ range \[`result`, `result + `N). If an element `a` precedes `b` in an
1129
+ input range, `a` is copied into the output range before `b`. If `e1` is
1130
+ an element of \[`first1`, `last1`) and `e2` of \[`first2`, `last2`),
1131
+ `e2` is copied into the output range before `e1` if and only if
1132
+ E(`e1`, `e1`) is `true`.
 
1133
 
1134
  *Returns:*
1135
 
1136
+ - `result + `N for the overloads in namespace `std`.
1137
+ - `{first1 + `K`, first2 + `N` - `K`, result + `N`}` for the overloads
1138
+ in namespace `ranges`.
1139
 
1140
  *Complexity:*
1141
 
1142
+ - For the non-parallel algorithm overloads, at most N - 1 comparisons
1143
  and applications of each projection.
1144
+ - For the parallel algorithm overloads, 𝑂(N) comparisons and
1145
+ applications of each projection.
1146
 
1147
  *Remarks:* Stable [[algorithm.stable]].
1148
 
1149
  ``` cpp
1150
  template<class BidirectionalIterator>
1151
+ constexpr void inplace_merge(BidirectionalIterator first,
1152
  BidirectionalIterator middle,
1153
  BidirectionalIterator last);
1154
  template<class ExecutionPolicy, class BidirectionalIterator>
1155
  void inplace_merge(ExecutionPolicy&& exec,
1156
  BidirectionalIterator first,
1157
  BidirectionalIterator middle,
1158
  BidirectionalIterator last);
1159
 
1160
  template<class BidirectionalIterator, class Compare>
1161
+ constexpr void inplace_merge(BidirectionalIterator first,
1162
  BidirectionalIterator middle,
1163
  BidirectionalIterator last, Compare comp);
1164
  template<class ExecutionPolicy, class BidirectionalIterator, class Compare>
1165
  void inplace_merge(ExecutionPolicy&& exec,
1166
  BidirectionalIterator first,
 
1168
  BidirectionalIterator last, Compare comp);
1169
 
1170
  template<bidirectional_iterator I, sentinel_for<I> S, class Comp = ranges::less,
1171
  class Proj = identity>
1172
  requires sortable<I, Comp, Proj>
1173
+ constexpr I ranges::inplace_merge(I first, I middle, S last, Comp comp = {}, Proj proj = {});
1174
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
1175
+ class Comp = ranges::less, class Proj = identity>
1176
+ requires sortable<I, Comp, Proj>
1177
+ I ranges::inplace_merge(Ep&& exec, I first, I middle, S last, Comp comp = {}, Proj proj = {});
1178
  ```
1179
 
1180
  Let `comp` be `less{}` and `proj` be `identity{}` for the overloads with
1181
  no parameters by those names.
1182
 
 
1194
 
1195
  *Returns:* `last` for the overload in namespace `ranges`.
1196
 
1197
  *Complexity:* Let N = `last - first`:
1198
 
1199
+ - For the non-parallel algorithm overloads, and if enough additional
1200
+ memory is available, at most N - 1 comparisons.
1201
  - Otherwise, 𝑂(N log N) comparisons.
1202
 
1203
  In either case, twice as many projections as comparisons.
1204
 
1205
  *Remarks:* Stable [[algorithm.stable]].
1206
 
1207
  ``` cpp
1208
  template<bidirectional_range R, class Comp = ranges::less, class Proj = identity>
1209
  requires sortable<iterator_t<R>, Comp, Proj>
1210
+ constexpr borrowed_iterator_t<R>
1211
  ranges::inplace_merge(R&& r, iterator_t<R> middle, Comp comp = {}, Proj proj = {});
1212
  ```
1213
 
1214
  *Effects:* Equivalent to:
1215
 
1216
  ``` cpp
1217
  return ranges::inplace_merge(ranges::begin(r), middle, ranges::end(r), comp, proj);
1218
  ```
1219
 
1220
+ ``` cpp
1221
+ template<execution-policy Ep, sized-random-access-range R, class Comp = ranges::less,
1222
+ class Proj = identity>
1223
+ requires sortable<iterator_t<R>, Comp, Proj>
1224
+ borrowed_iterator_t<R>
1225
+ ranges::inplace_merge(Ep&& exec, R&& r, iterator_t<R> middle, Comp comp = {},
1226
+ Proj proj = {});
1227
+ ```
1228
+
1229
+ *Effects:* Equivalent to:
1230
+
1231
+ ``` cpp
1232
+ return ranges::inplace_merge(std::forward<Ep>(exec), ranges::begin(r), middle,
1233
+ ranges::end(r), comp, proj);
1234
+ ```
1235
+
1236
  ### Set operations on sorted structures <a id="alg.set.operations">[[alg.set.operations]]</a>
1237
 
1238
  #### General <a id="alg.set.operations.general">[[alg.set.operations.general]]</a>
1239
 
1240
  Subclause [[alg.set.operations]] defines all the basic set operations on
 
1275
  class Proj2 = identity,
1276
  indirect_strict_weak_order<projected<iterator_t<R1>, Proj1>,
1277
  projected<iterator_t<R2>, Proj2>> Comp = ranges::less>
1278
  constexpr bool ranges::includes(R1&& r1, R2&& r2, Comp comp = {},
1279
  Proj1 proj1 = {}, Proj2 proj2 = {});
1280
+
1281
+ template<execution-policy Ep, random_access_iterator I1, sized_sentinel_for<I1> S1,
1282
+ random_access_iterator I2, sized_sentinel_for<I2> S2,
1283
+ class Proj1 = identity, class Proj2 = identity,
1284
+ indirect_strict_weak_order<projected<I1, Proj1>, projected<I2, Proj2>> Comp =
1285
+ ranges::less>
1286
+ bool ranges::includes(Ep&& exec, I1 first1, S1 last1, I2 first2, S2 last2,
1287
+ Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
1288
+ template<execution-policy Ep, sized-random-access-range R1, sized-random-access-range R2,
1289
+ class Proj1 = identity, class Proj2 = identity,
1290
+ indirect_strict_weak_order<projected<iterator_t<R1>, Proj1>,
1291
+ projected<iterator_t<R2>, Proj2>> Comp = ranges::less>
1292
+ bool ranges::includes(Ep&& exec, R1&& r1, R2&& r2,
1293
+ Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
1294
  ```
1295
 
1296
  Let `comp` be `less{}`, `proj1` be `identity{}`, and `proj2` be
1297
  `identity{}`, for the overloads with no parameters by those names.
1298
 
 
1350
  class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity>
1351
  requires mergeable<iterator_t<R1>, iterator_t<R2>, O, Comp, Proj1, Proj2>
1352
  constexpr ranges::set_union_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>, O>
1353
  ranges::set_union(R1&& r1, R2&& r2, O result, Comp comp = {},
1354
  Proj1 proj1 = {}, Proj2 proj2 = {});
1355
+
1356
+ template<execution-policy Ep, random_access_iterator I1, sized_sentinel_for<I1> S1,
1357
+ random_access_iterator I2, sized_sentinel_for<I2> S2,
1358
+ random_access_iterator O, sized_sentinel_for<O> OutS, class Comp = ranges::less,
1359
+ class Proj1 = identity, class Proj2 = identity>
1360
+ requires mergeable<I1, I2, O, Comp, Proj1, Proj2>
1361
+ ranges::set_union_result<I1, I2, O>
1362
+ ranges::set_union(Ep&& exec, I1 first1, S1 last1,
1363
+ I2 first2, S2 last2, O result, OutS result_last,
1364
+ Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
1365
+ template<execution-policy Ep, sized-random-access-range R1, sized-random-access-range R2,
1366
+ sized-random-access-range OutR, class Comp = ranges::less,
1367
+ class Proj1 = identity, class Proj2 = identity>
1368
+ requires mergeable<iterator_t<R1>, iterator_t<R2>, iterator_t<OutR>, Comp, Proj1, Proj2>
1369
+ ranges::set_union_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>,
1370
+ borrowed_iterator_t<OutR>>
1371
+ ranges::set_union(Ep&& exec, R1&& r1, R2&& r2, OutR&& result_r, Comp comp = {},
1372
+ Proj1 proj1 = {}, Proj2 proj2 = {});
1373
  ```
1374
 
1375
+ Let:
1376
+
1377
+ - `comp` be `less{}`, and `proj1` and `proj2` be `identity{}` for the
1378
+ overloads with no parameters by those names;
1379
+ - M be `last1 - first1` plus the number of elements in \[`first2`,
1380
+ `last2`) that are not present in \[`first1`, `last1`);
1381
+ - `result_last` be `result + `M for the overloads with no parameter
1382
+ `result_last` or `result_r`;
1383
+ - N be min(M, `result_last - result`).
1384
 
1385
  *Preconditions:* The ranges \[`first1`, `last1`) and \[`first2`,
1386
  `last2`) are sorted with respect to `comp` and `proj1` or `proj2`,
1387
  respectively. The resulting range does not overlap with either of the
1388
  original ranges.
1389
 
1390
+ *Effects:* Constructs a sorted union of N elements from the two ranges;
1391
+ that is, the set of elements that are present in one or both of the
1392
+ ranges.
1393
 
1394
+ *Returns:*
 
1395
 
1396
  - `result_last` for the overloads in namespace `std`.
1397
+ - `{last1, last2, result + `N`}` for the overloads in namespace
1398
+ `ranges`, if N is equal to M.
1399
+ - Otherwise, `{j1, j2, result_last}` for the overloads in namespace
1400
+ `ranges`, where the iterators `j1` and `j2` point to positions past
1401
+ the last copied or skipped elements in \[`first1`, `last1`) and
1402
+ \[`first2`, `last2`), respectively.
1403
 
1404
  *Complexity:* At most `2 * ((last1 - first1) + (last2 - first2)) - 1`
1405
  comparisons and applications of each projection.
1406
 
1407
  *Remarks:* Stable [[algorithm.stable]]. If \[`first1`, `last1`) contains
 
1453
  class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity>
1454
  requires mergeable<iterator_t<R1>, iterator_t<R2>, O, Comp, Proj1, Proj2>
1455
  constexpr ranges::set_intersection_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>, O>
1456
  ranges::set_intersection(R1&& r1, R2&& r2, O result,
1457
  Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
1458
+
1459
+ template<execution-policy Ep, random_access_iterator I1, sized_sentinel_for<I1> S1,
1460
+ random_access_iterator I2, sized_sentinel_for<I2> S2,
1461
+ random_access_iterator O, sized_sentinel_for<O> OutS, class Comp = ranges::less,
1462
+ class Proj1 = identity, class Proj2 = identity>
1463
+ requires mergeable<I1, I2, O, Comp, Proj1, Proj2>
1464
+ ranges::set_intersection_result<I1, I2, O>
1465
+ ranges::set_intersection(Ep&& exec, I1 first1, S1 last1,
1466
+ I2 first2, S2 last2, O result, OutS result_last,
1467
+ Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
1468
+ template<execution-policy Ep, sized-random-access-range R1, sized-random-access-range R2,
1469
+ sized-random-access-range OutR, class Comp = ranges::less,
1470
+ class Proj1 = identity, class Proj2 = identity>
1471
+ requires mergeable<iterator_t<R1>, iterator_t<R2>, iterator_t<OutR>, Comp, Proj1, Proj2>
1472
+ ranges::set_intersection_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>,
1473
+ borrowed_iterator_t<OutR>>
1474
+ ranges::set_intersection(Ep&& exec, R1&& r1, R2&& r2, OutR&& result_r, Comp comp = {},
1475
+ Proj1 proj1 = {}, Proj2 proj2 = {});
1476
  ```
1477
 
1478
+ Let:
1479
+
1480
+ - `comp` be `less{}`, and `proj1` and `proj2` be `identity{}` for the
1481
+ overloads with no parameters by those names;
1482
+ - M be the number of elements in \[`first1`, `last1`) that are present
1483
+ in \[`first2`, `last2`);
1484
+ - `result_last` be `result + `M for the overloads with no parameter
1485
+ `result_last` or `result_r`;
1486
+ - N be min(M, `result_last - result`).
1487
 
1488
  *Preconditions:* The ranges \[`first1`, `last1`) and \[`first2`,
1489
  `last2`) are sorted with respect to `comp` and `proj1` or `proj2`,
1490
  respectively. The resulting range does not overlap with either of the
1491
  original ranges.
1492
 
1493
+ *Effects:* Constructs a sorted intersection of N elements from the two
1494
  ranges; that is, the set of elements that are present in both of the
1495
  ranges.
1496
 
1497
+ *Returns:*
 
1498
 
1499
  - `result_last` for the overloads in namespace `std`.
1500
+ - `{last1, last2, result + `N`}` for the overloads in namespace
1501
+ `ranges`, if N is equal to M.
1502
+ - Otherwise, `{j1, j2, result_last}` for the overloads in namespace
1503
+ `ranges`, where the iterators `j1` and `j2` point to positions past
1504
+ the last copied or skipped elements in \[`first1`, `last1`) and
1505
+ \[`first2`, `last2`), respectively.
1506
 
1507
  *Complexity:* At most `2 * ((last1 - first1) + (last2 - first2)) - 1`
1508
  comparisons and applications of each projection.
1509
 
1510
  *Remarks:* Stable [[algorithm.stable]]. If \[`first1`, `last1`) contains
 
1554
  class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity>
1555
  requires mergeable<iterator_t<R1>, iterator_t<R2>, O, Comp, Proj1, Proj2>
1556
  constexpr ranges::set_difference_result<borrowed_iterator_t<R1>, O>
1557
  ranges::set_difference(R1&& r1, R2&& r2, O result,
1558
  Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
1559
+
1560
+ template<execution-policy Ep, random_access_iterator I1, sized_sentinel_for<I1> S1,
1561
+ random_access_iterator I2, sized_sentinel_for<I2> S2,
1562
+ random_access_iterator O, sized_sentinel_for<O> OutS, class Comp = ranges::less,
1563
+ class Proj1 = identity, class Proj2 = identity>
1564
+ requires mergeable<I1, I2, O, Comp, Proj1, Proj2>
1565
+ ranges::set_difference_result<I1, O>
1566
+ ranges::set_difference(Ep&& exec, I1 first1, S1 last1,
1567
+ I2 first2, S2 last2, O result, OutS result_last,
1568
+ Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
1569
+ template<execution-policy Ep, sized-random-access-range R1, sized-random-access-range R2,
1570
+ sized-random-access-range OutR, class Comp = ranges::less,
1571
+ class Proj1 = identity, class Proj2 = identity>
1572
+ requires mergeable<iterator_t<R1>, iterator_t<R2>, iterator_t<OutR>, Comp, Proj1, Proj2>
1573
+ ranges::set_difference_result<borrowed_iterator_t<R1>, borrowed_iterator_t<OutR>>
1574
+ ranges::set_difference(Ep&& exec, R1&& r1, R2&& r2, OutR&& result_r, Comp comp = {},
1575
+ Proj1 proj1 = {}, Proj2 proj2 = {});
1576
  ```
1577
 
1578
+ Let:
1579
+
1580
+ - `comp` be `less{}`, and `proj1` and `proj2` be `identity{}` for the
1581
+ overloads with no parameters by those names;
1582
+ - M be the number of elements in \[`first1`, `last1`) that are not
1583
+ present in \[`first2`, `last2`);
1584
+ - `result_last` be `result + `M for the overloads with no parameter
1585
+ `result_last` or `result_r`;
1586
+ - N be min(M, `result_last - result`).
1587
 
1588
  *Preconditions:* The ranges \[`first1`, `last1`) and \[`first2`,
1589
  `last2`) are sorted with respect to `comp` and `proj1` or `proj2`,
1590
  respectively. The resulting range does not overlap with either of the
1591
  original ranges.
1592
 
1593
+ *Effects:* Copies N elements of the range \[`first1`, `last1`) which are
1594
+ not present in the range \[`first2`, `last2`) to the range \[`result`,
1595
+ `result + `N). The elements in the constructed range are sorted.
1596
 
1597
+ *Returns:*
 
1598
 
1599
  - `result_last` for the overloads in namespace `std`.
1600
+ - `{last1, result + `N`}` for the overloads in namespace `ranges`, if N
1601
+ is equal to M.
1602
+ - Otherwise, `{j1, result_last}` for the overloads in namespace
1603
+ `ranges`, where the iterator `j1` points to the position past the last
1604
+ copied or skipped element in \[`first1`, `last1`).
1605
 
1606
  *Complexity:* At most `2 * ((last1 - first1) + (last2 - first2)) - 1`
1607
  comparisons and applications of each projection.
1608
 
1609
  *Remarks:* If \[`first1`, `last1`) contains m elements that are
 
1655
  requires mergeable<iterator_t<R1>, iterator_t<R2>, O, Comp, Proj1, Proj2>
1656
  constexpr ranges::set_symmetric_difference_result<borrowed_iterator_t<R1>,
1657
  borrowed_iterator_t<R2>, O>
1658
  ranges::set_symmetric_difference(R1&& r1, R2&& r2, O result, Comp comp = {},
1659
  Proj1 proj1 = {}, Proj2 proj2 = {});
1660
+
1661
+ template<execution-policy Ep, random_access_iterator I1, sized_sentinel_for<I1> S1,
1662
+ random_access_iterator I2, sized_sentinel_for<I2> S2,
1663
+ random_access_iterator O, sized_sentinel_for<O> OutS, class Comp = ranges::less,
1664
+ class Proj1 = identity, class Proj2 = identity>
1665
+ requires mergeable<I1, I2, O, Comp, Proj1, Proj2>
1666
+ ranges::set_symmetric_difference_result<I1, I2, O>
1667
+ ranges::set_symmetric_difference(Ep&& exec, I1 first1, S1 last1,
1668
+ I2 first2, S2 last2, O result, OutS result_last,
1669
+ Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
1670
+ template<execution-policy Ep, sized-random-access-range R1, sized-random-access-range R2,
1671
+ sized-random-access-range OutR, class Comp = ranges::less,
1672
+ class Proj1 = identity, class Proj2 = identity>
1673
+ requires mergeable<iterator_t<R1>, iterator_t<R2>, iterator_t<OutR>, Comp, Proj1, Proj2>
1674
+ ranges::set_symmetric_difference_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>,
1675
+ borrowed_iterator_t<OutR>>
1676
+ ranges::set_symmetric_difference(Ep&& exec, R1&& r1, R2&& r2, OutR&& result_r,
1677
+ Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
1678
  ```
1679
 
1680
+ Let:
1681
+
1682
+ - `comp` be `less{}`, and `proj1` and `proj2` be `identity{}` for the
1683
+ overloads with no parameters by those names;
1684
+ - K be the number of elements in \[`first1`, `last1`) that are not
1685
+ present in \[`first2`, `last2`).
1686
+ - M be the number of elements in \[`first2`, `last2`) that are not
1687
+ present in \[`first1`, `last1`).
1688
+ - `result_last` be `result + `M` + `K for the overloads with no
1689
+ parameter `result_last` or `result_r`;
1690
+ - N be min(K + M, `result_last - result`).
1691
 
1692
  *Preconditions:* The ranges \[`first1`, `last1`) and \[`first2`,
1693
  `last2`) are sorted with respect to `comp` and `proj1` or `proj2`,
1694
  respectively. The resulting range does not overlap with either of the
1695
  original ranges.
1696
 
1697
  *Effects:* Copies the elements of the range \[`first1`, `last1`) that
1698
  are not present in the range \[`first2`, `last2`), and the elements of
1699
  the range \[`first2`, `last2`) that are not present in the range
1700
+ \[`first1`, `last1`) to the range \[`result`, `result + `N). The
1701
+ elements in the constructed range are sorted.
1702
 
1703
+ *Returns:*
 
1704
 
1705
  - `result_last` for the overloads in namespace `std`.
1706
+ - `{last1, last2, result + `N`}` for the overloads in namespace
1707
+ `ranges`, if N is equal to M + K.
1708
+ - Otherwise, `{j1, j2, result_last}` for the overloads in namespace
1709
+ `ranges`, where the iterators `j1` and `j2` point to positions past
1710
+ the last copied or skipped elements in \[`first1`, `last1`) and
1711
+ \[`first2`, `last2`), respectively.
1712
 
1713
  *Complexity:* At most `2 * ((last1 - first1) + (last2 - first2)) - 1`
1714
  comparisons and applications of each projection.
1715
 
1716
  *Remarks:* Stable [[algorithm.stable]]. If \[`first1`, `last1`) contains
 
1949
  ```
1950
 
1951
  *Effects:* Equivalent to:
1952
  `return ranges::is_heap_until(first, last, comp, proj) == last;`
1953
 
1954
+ ``` cpp
1955
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
1956
+ class Proj = identity,
1957
+ indirect_strict_weak_order<projected<I, Proj>> Comp = ranges::less>
1958
+ bool ranges::is_heap(Ep&& exec, I first, S last, Comp comp = {}, Proj proj = {});
1959
+ template<execution-policy Ep, sized-random-access-range R, class Proj = identity,
1960
+ indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
1961
+ bool ranges::is_heap(Ep&& exec, R&& r, Comp comp = {}, Proj proj = {});
1962
+ ```
1963
+
1964
+ *Effects:* Equivalent to:
1965
+
1966
+ ``` cpp
1967
+ return ranges::is_heap_until(std::forward<Ep>(exec), first, last, comp, proj) == last;
1968
+ ```
1969
+
1970
  ``` cpp
1971
  template<class RandomAccessIterator>
1972
  constexpr RandomAccessIterator
1973
  is_heap_until(RandomAccessIterator first, RandomAccessIterator last);
1974
  template<class ExecutionPolicy, class RandomAccessIterator>
 
1991
  constexpr I ranges::is_heap_until(I first, S last, Comp comp = {}, Proj proj = {});
1992
  template<random_access_range R, class Proj = identity,
1993
  indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
1994
  constexpr borrowed_iterator_t<R>
1995
  ranges::is_heap_until(R&& r, Comp comp = {}, Proj proj = {});
1996
+
1997
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
1998
+ class Proj = identity,
1999
+ indirect_strict_weak_order<projected<I, Proj>> Comp = ranges::less>
2000
+ I ranges::is_heap_until(Ep&& exec, I first, S last, Comp comp = {}, Proj proj = {});
2001
+ template<execution-policy Ep, sized-random-access-range R, class Proj = identity,
2002
+ indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
2003
+ borrowed_iterator_t<R>
2004
+ ranges::is_heap_until(Ep&& exec, R&& r, Comp comp = {}, Proj proj = {});
2005
  ```
2006
 
2007
  Let `comp` be `less{}` and `proj` be `identity{}` for the overloads with
2008
  no parameters by those names.
2009
 
 
2049
  template<input_range R, class Proj = identity,
2050
  indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
2051
  requires indirectly_copyable_storable<iterator_t<R>, range_value_t<R>*>
2052
  constexpr range_value_t<R>
2053
  ranges::min(R&& r, Comp comp = {}, Proj proj = {});
2054
+ template<execution-policy Ep, sized-random-access-range R, class Proj = identity,
2055
+ indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
2056
+ requires indirectly_copyable_storable<iterator_t<R>, range_value_t<R>*>
2057
+ range_value_t<R>
2058
+ ranges::min(Ep&& exec, R&& r, Comp comp = {}, Proj proj = {});
2059
  ```
2060
 
2061
  *Preconditions:* `ranges::distance(r) > 0`. For the overloads in
2062
  namespace `std`, `T` meets the *Cpp17CopyConstructible* requirements.
2063
  For the first form, `T` meets the *Cpp17LessThanComparable* requirements
 
2107
  template<input_range R, class Proj = identity,
2108
  indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
2109
  requires indirectly_copyable_storable<iterator_t<R>, range_value_t<R>*>
2110
  constexpr range_value_t<R>
2111
  ranges::max(R&& r, Comp comp = {}, Proj proj = {});
2112
+ template<execution-policy Ep, sized-random-access-range R, class Proj = identity,
2113
+ indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
2114
+ requires indirectly_copyable_storable<iterator_t<R>, range_value_t<R>*>
2115
+ range_value_t<R>
2116
+ ranges::max(Ep&& exec, R&& r, Comp comp = {}, Proj proj = {});
2117
  ```
2118
 
2119
  *Preconditions:* `ranges::distance(r) > 0`. For the overloads in
2120
  namespace `std`, `T` meets the *Cpp17CopyConstructible* requirements.
2121
  For the first form, `T` meets the *Cpp17LessThanComparable* requirements
 
2166
  template<input_range R, class Proj = identity,
2167
  indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
2168
  requires indirectly_copyable_storable<iterator_t<R>, range_value_t<R>*>
2169
  constexpr ranges::minmax_result<range_value_t<R>>
2170
  ranges::minmax(R&& r, Comp comp = {}, Proj proj = {});
2171
+ template<execution-policy Ep, sized-random-access-range R, class Proj = identity,
2172
+ indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
2173
+ requires indirectly_copyable_storable<iterator_t<R>, range_value_t<R>*>
2174
+ ranges::minmax_result<range_value_t<R>>
2175
+ ranges::minmax(Ep&& exec, R&& r, Comp comp = {}, Proj proj = {});
2176
  ```
2177
 
2178
  *Preconditions:* `ranges::distance(r) > 0`. For the overloads in
2179
  namespace `std`, `T` meets the *Cpp17CopyConstructible* requirements.
2180
  For the first form, type `T` meets the *Cpp17LessThanComparable*
 
2211
  constexpr I ranges::min_element(I first, S last, Comp comp = {}, Proj proj = {});
2212
  template<forward_range R, class Proj = identity,
2213
  indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
2214
  constexpr borrowed_iterator_t<R>
2215
  ranges::min_element(R&& r, Comp comp = {}, Proj proj = {});
2216
+
2217
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
2218
+ class Proj = identity,
2219
+ indirect_strict_weak_order<projected<I, Proj>> Comp = ranges::less>
2220
+ I ranges::min_element(Ep&& exec, I first, S last, Comp comp = {}, Proj proj = {});
2221
+ template<execution-policy Ep, sized-random-access-range R,
2222
+ class Proj = identity,
2223
+ indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
2224
+ borrowed_iterator_t<R>
2225
+ ranges::min_element(Ep&& exec, R&& r, Comp comp = {}, Proj proj = {});
2226
  ```
2227
 
2228
  Let `comp` be `less{}` and `proj` be `identity{}` for the overloads with
2229
  no parameters by those names.
2230
 
 
2260
  constexpr I ranges::max_element(I first, S last, Comp comp = {}, Proj proj = {});
2261
  template<forward_range R, class Proj = identity,
2262
  indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
2263
  constexpr borrowed_iterator_t<R>
2264
  ranges::max_element(R&& r, Comp comp = {}, Proj proj = {});
2265
+
2266
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
2267
+ class Proj = identity,
2268
+ indirect_strict_weak_order<projected<I, Proj>> Comp = ranges::less>
2269
+ I ranges::max_element(Ep&& exec, I first, S last, Comp comp = {}, Proj proj = {});
2270
+ template<execution-policy Ep, sized-random-access-range R,
2271
+ class Proj = identity,
2272
+ indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
2273
+ borrowed_iterator_t<R>
2274
+ ranges::max_element(Ep&& exec, R&& r, Comp comp = {}, Proj proj = {});
2275
  ```
2276
 
2277
  Let `comp` be `less{}` and `proj` be `identity{}` for the overloads with
2278
  no parameters by those names.
2279
 
 
2312
  ranges::minmax_element(I first, S last, Comp comp = {}, Proj proj = {});
2313
  template<forward_range R, class Proj = identity,
2314
  indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
2315
  constexpr ranges::minmax_element_result<borrowed_iterator_t<R>>
2316
  ranges::minmax_element(R&& r, Comp comp = {}, Proj proj = {});
2317
+
2318
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
2319
+ class Proj = identity,
2320
+ indirect_strict_weak_order<projected<I, Proj>> Comp = ranges::less>
2321
+ ranges::minmax_element_result<I>
2322
+ ranges::minmax_element(Ep&& exec, I first, S last, Comp comp = {}, Proj proj = {});
2323
+ template<execution-policy Ep, sized-random-access-range R, class Proj = identity,
2324
+ indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
2325
+ ranges::minmax_element_result<borrowed_iterator_t<R>>
2326
+ ranges::minmax_element(Ep&& exec, R&& r, Comp comp = {}, Proj proj = {});
2327
  ```
2328
 
2329
  *Returns:* `{first, first}` if \[`first`, `last`) is empty, otherwise
2330
  `{m, M}`, where `m` is the first iterator in \[`first`, `last`) such
2331
  that no iterator in the range refers to a smaller element, and where `M`
 
2408
  indirect_strict_weak_order<projected<iterator_t<R1>, Proj1>,
2409
  projected<iterator_t<R2>, Proj2>> Comp = ranges::less>
2410
  constexpr bool
2411
  ranges::lexicographical_compare(R1&& r1, R2&& r2, Comp comp = {},
2412
  Proj1 proj1 = {}, Proj2 proj2 = {});
2413
+
2414
+ template<execution-policy Ep, random_access_iterator I1, sized_sentinel_for<I1> S1,
2415
+ random_access_iterator I2, sized_sentinel_for<I2> S2,
2416
+ class Proj1 = identity, class Proj2 = identity,
2417
+ indirect_strict_weak_order<projected<I1, Proj1>,
2418
+ projected<I2, Proj2>> Comp = ranges::less>
2419
+ bool ranges::lexicographical_compare(Ep&& exec, I1 first1, S1 last1, I2 first2, S2 last2,
2420
+ Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
2421
+ template<execution-policy Ep, sized-random-access-range R1, sized-random-access-range R2,
2422
+ class Proj1 = identity, class Proj2 = identity,
2423
+ indirect_strict_weak_order<projected<iterator_t<R1>, Proj1>,
2424
+ projected<iterator_t<R2>, Proj2>> Comp = ranges::less>
2425
+ bool ranges::lexicographical_compare(Ep&& exec, R1&& r1, R2&& r2, Comp comp = {},
2426
+ Proj1 proj1 = {}, Proj2 proj2 = {});
2427
  ```
2428
 
2429
  *Returns:* `true` if and only if the sequence of elements defined by the
2430
  range \[`first1`, `last1`) is lexicographically less than the sequence
2431
  of elements defined by the range \[`first2`, `last2`).