From Jason Turner

[alg.partitions]

C++17 → C++20 13.5 KB 210 lines
Current Draft | LaTeX Source
Archived: C++17 | C++20
Markdown: C++17 | C++20
Explore in Adventure Game

Diff to HTML by rtfpessoa

Files changed (1) hide show
  1. tmp/tmpz7dvqrhu/{from.md → to.md} +132 -75
tmp/tmpz7dvqrhu/{from.md → to.md} RENAMED
@@ -1,143 +1,200 @@
1
  ### Partitions <a id="alg.partitions">[[alg.partitions]]</a>
2
 
3
  ``` cpp
4
  template<class InputIterator, class Predicate>
5
- bool is_partitioned(InputIterator first, InputIterator last, Predicate pred);
6
  template<class ExecutionPolicy, class ForwardIterator, class Predicate>
7
  bool is_partitioned(ExecutionPolicy&& exec,
8
  ForwardIterator first, ForwardIterator last, Predicate pred);
 
 
 
 
 
 
 
9
  ```
10
 
11
- *Requires:* For the overload with no `ExecutionPolicy`,
12
- `InputIterator`’s value type shall be convertible to `Predicate`’s
13
- argument type. For the overload with an `ExecutionPolicy`,
14
- `ForwardIterator`’s value type shall be convertible to `Predicate`’s
15
- argument type.
16
 
17
- *Returns:* `true` if \[`first`, `last`) is empty or if \[`first`,
18
- `last`) is partitioned by `pred`, i.e. if all elements that satisfy
19
- `pred` appear before those that do not.
20
 
21
- *Complexity:* Linear. At most `last - first` applications of `pred`.
 
22
 
23
  ``` cpp
24
  template<class ForwardIterator, class Predicate>
25
- ForwardIterator
26
  partition(ForwardIterator first, ForwardIterator last, Predicate pred);
27
  template<class ExecutionPolicy, class ForwardIterator, class Predicate>
28
  ForwardIterator
29
  partition(ExecutionPolicy&& exec,
30
  ForwardIterator first, ForwardIterator last, Predicate pred);
 
 
 
 
 
 
 
 
 
 
31
  ```
32
 
33
- *Requires:* `ForwardIterator` shall satisfy the requirements of
34
- `ValueSwappable` ([[swappable.requirements]]).
35
 
36
- *Effects:* Places all the elements in the range \[`first`, `last`) that
37
- satisfy `pred` before all the elements that do not satisfy it.
38
 
39
- *Returns:* An iterator `i` such that for every iterator `j` in the range
40
- \[`first`, `i`) `pred(*j) != false`, and for every iterator `k` in the
41
- range \[`i`, `last`), `pred(*k) == false`.
 
 
 
 
 
 
42
 
43
  *Complexity:* Let N = `last - first`:
44
 
45
  - For the overload with no `ExecutionPolicy`, exactly N applications of
46
- the predicate. At most N / 2 swaps if `ForwardIterator` meets the
47
- `BidirectionalIterator` requirements and at most N swaps otherwise.
 
 
48
  - For the overload with an `ExecutionPolicy`, 𝑂(N log N) swaps and 𝑂(N)
49
  applications of the predicate.
50
 
51
  ``` cpp
52
  template<class BidirectionalIterator, class Predicate>
53
  BidirectionalIterator
54
- stable_partition(BidirectionalIterator first, BidirectionalIterator last,
55
- Predicate pred);
56
  template<class ExecutionPolicy, class BidirectionalIterator, class Predicate>
57
  BidirectionalIterator
58
  stable_partition(ExecutionPolicy&& exec,
59
- BidirectionalIterator first, BidirectionalIterator last,
60
- Predicate pred);
 
 
 
 
 
 
 
 
61
  ```
62
 
63
- *Requires:* `BidirectionalIterator` shall satisfy the requirements of
64
- `ValueSwappable` ([[swappable.requirements]]). The type of `*first`
65
- shall satisfy the requirements of `MoveConstructible`
66
- (Table  [[tab:moveconstructible]]) and of `MoveAssignable`
67
- (Table  [[tab:moveassignable]]).
68
-
69
- *Effects:* Places all the elements in the range \[`first`, `last`) that
70
- satisfy `pred` before all the elements that do not satisfy it.
71
-
72
- *Returns:* An iterator `i` such that for every iterator `j` in the range
73
- \[`first`, `i`), `pred(*j) != false`, and for every iterator `k` in the
74
- range \[`i`, `last`), `pred(*k) == false`. The relative order of the
75
- elements in both groups is preserved.
 
 
 
 
 
 
76
 
77
  *Complexity:* Let N = `last - first`:
78
 
79
- - For the overload with no `ExecutionPolicy`, at most N log N swaps, but
80
- only 𝑂(N) swaps if there is enough extra memory. Exactly N
81
- applications of the predicate.
82
  - For the overload with an `ExecutionPolicy`, 𝑂(N log N) swaps and 𝑂(N)
83
  applications of the predicate.
84
 
85
  ``` cpp
86
  template<class InputIterator, class OutputIterator1,
87
  class OutputIterator2, class Predicate>
88
- pair<OutputIterator1, OutputIterator2>
89
  partition_copy(InputIterator first, InputIterator last,
90
- OutputIterator1 out_true, OutputIterator2 out_false,
91
- Predicate pred);
92
  template<class ExecutionPolicy, class ForwardIterator, class ForwardIterator1,
93
  class ForwardIterator2, class Predicate>
94
  pair<ForwardIterator1, ForwardIterator2>
95
  partition_copy(ExecutionPolicy&& exec,
96
  ForwardIterator first, ForwardIterator last,
97
- ForwardIterator1 out_true, ForwardIterator2 out_false,
98
- Predicate pred);
 
 
 
 
 
 
 
 
 
 
 
 
 
99
  ```
100
 
101
- *Requires:*
 
102
 
103
- - For the overload with no `ExecutionPolicy`, `InputIterator`’s value
104
- type shall be `CopyAssignable` (Table  [[tab:copyassignable]]), and
105
- shall be writable ([[iterator.requirements.general]]) to the
106
- `out_true` and `out_false` `OutputIterator`s, and shall be convertible
107
- to `Predicate`’s argument type.
108
- - For the overload with an `ExecutionPolicy`, `ForwardIterator`’s value
109
- type shall be `CopyAssignable`, and shall be writable to the
110
- `out_true` and `out_false` `ForwardIterator`s, and shall be
111
- convertible to `Predicate`’s argument type. \[*Note 1*: There may be a
112
- performance cost if `ForwardIterator`’s value type is not
113
- `CopyConstructible`. — *end note*]
114
- - For both overloads, the input range shall not overlap with either of
115
- the output ranges.
116
 
117
  *Effects:* For each iterator `i` in \[`first`, `last`), copies `*i` to
118
- the output range beginning with `out_true` if `pred(*i)` is `true`, or
119
- to the output range beginning with `out_false` otherwise.
120
 
121
- *Returns:* A pair `p` such that `p.first` is the end of the output range
122
- beginning at `out_true` and `p.second` is the end of the output range
123
- beginning at `out_false`.
124
 
125
- *Complexity:* Exactly `last - first` applications of `pred`.
 
 
 
126
 
127
  ``` cpp
128
  template<class ForwardIterator, class Predicate>
129
- ForwardIterator partition_point(ForwardIterator first,
130
- ForwardIterator last,
131
- Predicate pred);
 
 
 
 
 
 
 
132
  ```
133
 
134
- *Requires:* `ForwardIterator`’s value type shall be convertible to
135
- `Predicate`’s argument type. \[`first`, `last`) shall be partitioned by
136
- `pred`, i.e. all elements that satisfy `pred` shall appear before those
137
- that do not.
138
 
139
- *Returns:* An iterator `mid` such that `all_of(first, mid, pred)` and
140
- `none_of(mid, last, pred)` are both `true`.
141
 
142
- *Complexity:* 𝑂(log(`last - first`)) applications of `pred`.
 
 
 
 
143
 
 
1
  ### Partitions <a id="alg.partitions">[[alg.partitions]]</a>
2
 
3
  ``` cpp
4
  template<class InputIterator, class Predicate>
5
+ constexpr bool is_partitioned(InputIterator first, InputIterator last, Predicate pred);
6
  template<class ExecutionPolicy, class ForwardIterator, class Predicate>
7
  bool is_partitioned(ExecutionPolicy&& exec,
8
  ForwardIterator first, ForwardIterator last, Predicate pred);
9
+
10
+ template<input_iterator I, sentinel_for<I> S, class Proj = identity,
11
+ indirect_unary_predicate<projected<I, Proj>> Pred>
12
+ constexpr bool ranges::is_partitioned(I first, S last, Pred pred, Proj proj = {});
13
+ template<input_range R, class Proj = identity,
14
+ indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
15
+ constexpr bool ranges::is_partitioned(R&& r, Pred pred, Proj proj = {});
16
  ```
17
 
18
+ Let `proj` be `identity{}` for the overloads with no parameter named
19
+ `proj`.
 
 
 
20
 
21
+ *Returns:* `true` if and only if the elements `e` of \[`first`, `last`)
22
+ are partitioned with respect to the expression
23
+ `bool(invoke(pred, invoke(proj, e)))`.
24
 
25
+ *Complexity:* Linear. At most `last - first` applications of `pred` and
26
+ `proj`.
27
 
28
  ``` cpp
29
  template<class ForwardIterator, class Predicate>
30
+ constexpr ForwardIterator
31
  partition(ForwardIterator first, ForwardIterator last, Predicate pred);
32
  template<class ExecutionPolicy, class ForwardIterator, class Predicate>
33
  ForwardIterator
34
  partition(ExecutionPolicy&& exec,
35
  ForwardIterator first, ForwardIterator last, Predicate pred);
36
+
37
+ template<permutable I, sentinel_for<I> S, class Proj = identity,
38
+ indirect_unary_predicate<projected<I, Proj>> Pred>
39
+ constexpr subrange<I>
40
+ ranges::partition(I first, S last, Pred pred, Proj proj = {});
41
+ template<forward_range R, class Proj = identity,
42
+ indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
43
+ requires permutable<iterator_t<R>>
44
+ constexpr borrowed_subrange_t<R>
45
+ ranges::partition(R&& r, Pred pred, Proj proj = {});
46
  ```
47
 
48
+ Let `proj` be `identity{}` for the overloads with no parameter named
49
+ `proj` and let E(x) be `bool(invoke(pred, invoke(proj, `x`)))`.
50
 
51
+ *Preconditions:* For the overloads in namespace `std`, `ForwardIterator`
52
+ meets the *Cpp17ValueSwappable* requirements [[swappable.requirements]].
53
 
54
+ *Effects:* Places all the elements `e` in \[`first`, `last`) that
55
+ satisfy E(`e`) before all the elements that do not.
56
+
57
+ *Returns:* Let `i` be an iterator such that E(`*j`) is `true` for every
58
+ iterator `j` in \[`first`, `i`) and `false` for every iterator `j` in
59
+ \[`i`, `last`). Returns:
60
+
61
+ - `i` for the overloads in namespace `std`.
62
+ - `{i, last}` for the overloads in namespace `ranges`.
63
 
64
  *Complexity:* Let N = `last - first`:
65
 
66
  - For the overload with no `ExecutionPolicy`, exactly N applications of
67
+ the predicate and projection. At most N / 2 swaps if the type of
68
+ `first` meets the *Cpp17BidirectionalIterator* requirements for the
69
+ overloads in namespace `std` or models `bidirectional_iterator` for
70
+ the overloads in namespace `ranges`, and at most N swaps otherwise.
71
  - For the overload with an `ExecutionPolicy`, 𝑂(N log N) swaps and 𝑂(N)
72
  applications of the predicate.
73
 
74
  ``` cpp
75
  template<class BidirectionalIterator, class Predicate>
76
  BidirectionalIterator
77
+ stable_partition(BidirectionalIterator first, BidirectionalIterator last, Predicate pred);
 
78
  template<class ExecutionPolicy, class BidirectionalIterator, class Predicate>
79
  BidirectionalIterator
80
  stable_partition(ExecutionPolicy&& exec,
81
+ BidirectionalIterator first, BidirectionalIterator last, Predicate pred);
82
+
83
+ template<bidirectional_iterator I, sentinel_for<I> S, class Proj = identity,
84
+ indirect_unary_predicate<projected<I, Proj>> Pred>
85
+ requires permutable<I>
86
+ subrange<I> ranges::stable_partition(I first, S last, Pred pred, Proj proj = {});
87
+ template<bidirectional_range R, class Proj = identity,
88
+ indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
89
+ requires permutable<iterator_t<R>>
90
+ borrowed_subrange_t<R> ranges::stable_partition(R&& r, Pred pred, Proj proj = {});
91
  ```
92
 
93
+ Let `proj` be `identity{}` for the overloads with no parameter named
94
+ `proj` and let E(x) be `bool(invoke(pred, invoke(proj, `x`)))`.
95
+
96
+ *Preconditions:* For the overloads in namespace `std`,
97
+ `BidirectionalIterator` meets the *Cpp17ValueSwappable*
98
+ requirements [[swappable.requirements]] and the type of `*first` meets
99
+ the *Cpp17MoveConstructible* ([[cpp17.moveconstructible]]) and
100
+ *Cpp17MoveAssignable* ([[cpp17.moveassignable]]) requirements.
101
+
102
+ *Effects:* Places all the elements `e` in \[`first`, `last`) that
103
+ satisfy E(`e`) before all the elements that do not. The relative order
104
+ of the elements in both groups is preserved.
105
+
106
+ *Returns:* Let `i` be an iterator such that for every iterator `j` in
107
+ \[`first`, `i`), E(`*j`) is `true`, and for every iterator `j` in the
108
+ range \[`i`, `last`), E(`*j`) is `false`. Returns:
109
+
110
+ - `i` for the overloads in namespace `std`.
111
+ - `{i, last}` for the overloads in namespace `ranges`.
112
 
113
  *Complexity:* Let N = `last - first`:
114
 
115
+ - For the overloads with no `ExecutionPolicy`, at most N log N swaps,
116
+ but only 𝑂(N) swaps if there is enough extra memory. Exactly N
117
+ applications of the predicate and projection.
118
  - For the overload with an `ExecutionPolicy`, 𝑂(N log N) swaps and 𝑂(N)
119
  applications of the predicate.
120
 
121
  ``` cpp
122
  template<class InputIterator, class OutputIterator1,
123
  class OutputIterator2, class Predicate>
124
+ constexpr pair<OutputIterator1, OutputIterator2>
125
  partition_copy(InputIterator first, InputIterator last,
126
+ OutputIterator1 out_true, OutputIterator2 out_false, Predicate pred);
 
127
  template<class ExecutionPolicy, class ForwardIterator, class ForwardIterator1,
128
  class ForwardIterator2, class Predicate>
129
  pair<ForwardIterator1, ForwardIterator2>
130
  partition_copy(ExecutionPolicy&& exec,
131
  ForwardIterator first, ForwardIterator last,
132
+ ForwardIterator1 out_true, ForwardIterator2 out_false, Predicate pred);
133
+
134
+ template<input_iterator I, sentinel_for<I> S, weakly_incrementable O1, weakly_incrementable O2,
135
+ class Proj = identity, indirect_unary_predicate<projected<I, Proj>> Pred>
136
+ requires indirectly_copyable<I, O1> && indirectly_copyable<I, O2>
137
+ constexpr ranges::partition_copy_result<I, O1, O2>
138
+ ranges::partition_copy(I first, S last, O1 out_true, O2 out_false, Pred pred,
139
+ Proj proj = {});
140
+ template<input_range R, weakly_incrementable O1, weakly_incrementable O2,
141
+ class Proj = identity,
142
+ indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
143
+ requires indirectly_copyable<iterator_t<R>, O1> &&
144
+ indirectly_copyable<iterator_t<R>, O2>
145
+ constexpr ranges::partition_copy_result<borrowed_iterator_t<R>, O1, O2>
146
+ ranges::partition_copy(R&& r, O1 out_true, O2 out_false, Pred pred, Proj proj = {});
147
  ```
148
 
149
+ Let `proj` be `identity{}` for the overloads with no parameter named
150
+ `proj` and let E(x) be `bool(invoke(pred, invoke(proj, `x`)))`.
151
 
152
+ *Mandates:* For the overloads in namespace `std`, the expression
153
+ `*first` is writable [[iterator.requirements.general]] to `out_true` and
154
+ `out_false`.
155
+
156
+ *Preconditions:* The input range and output ranges do not overlap.
157
+
158
+ [*Note 1*: For the overload with an `ExecutionPolicy`, there may be a
159
+ performance cost if `first`’s value type does not meet the
160
+ *Cpp17CopyConstructible* requirements. — *end note*]
 
 
 
 
161
 
162
  *Effects:* For each iterator `i` in \[`first`, `last`), copies `*i` to
163
+ the output range beginning with `out_true` if E(`*i`) is `true`, or to
164
+ the output range beginning with `out_false` otherwise.
165
 
166
+ *Returns:* Let `o1` be the end of the output range beginning at
167
+ `out_true`, and `o2` the end of the output range beginning at
168
+ `out_false`. Returns
169
 
170
+ - `{o1, o2}` for the overloads in namespace `std`.
171
+ - `{last, o1, o2}` for the overloads in namespace `ranges`.
172
+
173
+ *Complexity:* Exactly `last - first` applications of `pred` and `proj`.
174
 
175
  ``` cpp
176
  template<class ForwardIterator, class Predicate>
177
+ constexpr ForwardIterator
178
+ partition_point(ForwardIterator first, ForwardIterator last, Predicate pred);
179
+
180
+ template<forward_iterator I, sentinel_for<I> S, class Proj = identity,
181
+ indirect_unary_predicate<projected<I, Proj>> Pred>
182
+ constexpr I ranges::partition_point(I first, S last, Pred pred, Proj proj = {});
183
+ template<forward_range R, class Proj = identity,
184
+ indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
185
+ constexpr borrowed_iterator_t<R>
186
+ ranges::partition_point(R&& r, Pred pred, Proj proj = {});
187
  ```
188
 
189
+ Let `proj` be `identity{}` for the overloads with no parameter named
190
+ `proj` and let E(x) be `bool(invoke(pred, invoke(proj, `x`)))`.
 
 
191
 
192
+ *Preconditions:* The elements `e` of \[`first`, `last`) are partitioned
193
+ with respect to E(`e`).
194
 
195
+ *Returns:* An iterator `mid` such that E(`*i`) is `true` for all
196
+ iterators `i` in \[`first`, `mid`), and `false` for all iterators `i` in
197
+ \[`mid`, `last`).
198
+
199
+ *Complexity:* 𝑂(log(`last - first`)) applications of `pred` and `proj`.
200