From Jason Turner

[alg.unique]

C++23 → Trunk 5.8 KB 71 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/tmpi37x7niv/{from.md → to.md} +54 -13
tmp/tmpi37x7niv/{from.md → to.md} RENAMED
@@ -21,10 +21,20 @@ template<permutable I, sentinel_for<I> S, class Proj = identity,
21
  template<forward_range R, class Proj = identity,
22
  indirect_equivalence_relation<projected<iterator_t<R>, Proj>> C = ranges::equal_to>
23
  requires permutable<iterator_t<R>>
24
  constexpr borrowed_subrange_t<R>
25
  ranges::unique(R&& r, C comp = {}, Proj proj = {});
 
 
 
 
 
 
 
 
 
 
26
  ```
27
 
28
  Let `pred` be `equal_to{}` for the overloads with no parameter `pred`,
29
  and let E be
30
 
@@ -86,50 +96,81 @@ template<input_range R, weakly_incrementable O, class Proj = identity,
86
  (forward_iterator<iterator_t<R>> ||
87
  (input_iterator<O> && same_as<range_value_t<R>, iter_value_t<O>>) ||
88
  indirectly_copyable_storable<iterator_t<R>, O>)
89
  constexpr ranges::unique_copy_result<borrowed_iterator_t<R>, O>
90
  ranges::unique_copy(R&& r, O result, C comp = {}, Proj proj = {});
 
 
 
 
 
 
 
 
 
 
 
 
 
 
91
  ```
92
 
93
  Let `pred` be `equal_to{}` for the overloads in namespace `std` with no
94
- parameter `pred`, and let E be
95
 
96
  - `bool(pred(*i, *(i - 1)))` for the overloads in namespace `std`;
97
  - `bool(invoke(comp, invoke(proj, *i), invoke(proj, *(i - 1))))` for the
98
  overloads in namespace `ranges`.
99
 
 
 
 
 
 
 
 
 
100
  *Mandates:* `*first` is writable [[iterator.requirements.general]] to
101
  `result`.
102
 
103
  *Preconditions:*
104
 
105
- - The ranges \[`first`, `last`) and \[`result`, `result+(last-first)`)
106
- do not overlap.
107
  - For the overloads in namespace `std`:
108
  - The comparison function is an equivalence relation.
109
  - For the overloads with no `ExecutionPolicy`, let `T` be the value
110
  type of `InputIterator`. If `InputIterator` models
111
  `forward_iterator` [[iterator.concept.forward]], then there are no
112
  additional requirements for `T`. Otherwise, if `OutputIterator`
113
  meets the *Cpp17ForwardIterator* requirements and its value type is
114
  the same as `T`, then `T` meets the *Cpp17CopyAssignable*
115
  ([[cpp17.copyassignable]]) requirements. Otherwise, `T` meets both
116
  the *Cpp17CopyConstructible* ([[cpp17.copyconstructible]]) and
117
- *Cpp17CopyAssignable* requirements. \[*Note 1*: For the overloads
118
- with an `ExecutionPolicy`, there might be a performance cost if the
119
- value type of `ForwardIterator1` does not meet both the
120
- *Cpp17CopyConstructible* and *Cpp17CopyAssignable*
121
- requirements. — *end note*]
122
 
123
- *Effects:* Copies only the first element from every consecutive group of
124
- equal elements referred to by the iterator `i` in the range \[`first`,
125
- `last`) for which E holds.
 
 
 
 
 
 
 
 
126
 
127
  *Returns:*
128
 
129
  - `result + `N for the overloads in namespace `std`.
130
- - `{last, result + `N`}` for the overloads in namespace `ranges`.
 
 
 
 
 
131
 
132
- *Complexity:* Exactly `last - first - 1` applications of the
133
  corresponding predicate and no more than twice as many applications of
134
  any projection.
135
 
 
21
  template<forward_range R, class Proj = identity,
22
  indirect_equivalence_relation<projected<iterator_t<R>, Proj>> C = ranges::equal_to>
23
  requires permutable<iterator_t<R>>
24
  constexpr borrowed_subrange_t<R>
25
  ranges::unique(R&& r, C comp = {}, Proj proj = {});
26
+
27
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
28
+ class Proj = identity,
29
+ indirect_equivalence_relation<projected<I, Proj>> C = ranges::equal_to>
30
+ requires permutable<I>
31
+ subrange<I> ranges::unique(Ep&& exec, I first, S last, C comp = {}, Proj proj = {});
32
+ template<execution-policy Ep, sized-random-access-range R, class Proj = identity,
33
+ indirect_equivalence_relation<projected<iterator_t<R>, Proj>> C = ranges::equal_to>
34
+ requires permutable<iterator_t<R>>
35
+ borrowed_subrange_t<R> ranges::unique(Ep&& exec, R&& r, C comp = {}, Proj proj = {});
36
  ```
37
 
38
  Let `pred` be `equal_to{}` for the overloads with no parameter `pred`,
39
  and let E be
40
 
 
96
  (forward_iterator<iterator_t<R>> ||
97
  (input_iterator<O> && same_as<range_value_t<R>, iter_value_t<O>>) ||
98
  indirectly_copyable_storable<iterator_t<R>, O>)
99
  constexpr ranges::unique_copy_result<borrowed_iterator_t<R>, O>
100
  ranges::unique_copy(R&& r, O result, C comp = {}, Proj proj = {});
101
+
102
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
103
+ random_access_iterator O, sized_sentinel_for<O> OutS, class Proj = identity,
104
+ indirect_equivalence_relation<projected<I, Proj>> C = ranges::equal_to>
105
+ requires indirectly_copyable<I, O>
106
+ ranges::unique_copy_result<I, O>
107
+ ranges::unique_copy(Ep&& exec, I first, S last, O result, OutS result_last,
108
+ C comp = {}, Proj proj = {});
109
+ template<execution-policy Ep, sized-random-access-range R, sized-random-access-range OutR,
110
+ class Proj = identity,
111
+ indirect_equivalence_relation<projected<iterator_t<R>, Proj>> C = ranges::equal_to>
112
+ requires indirectly_copyable<iterator_t<R>, iterator_t<OutR>>
113
+ ranges::unique_copy_result<borrowed_iterator_t<R>, borrowed_iterator_t<OutR>>
114
+ ranges::unique_copy(Ep&& exec, R&& r, OutR&& result_r, C comp = {}, Proj proj = {});
115
  ```
116
 
117
  Let `pred` be `equal_to{}` for the overloads in namespace `std` with no
118
+ parameter `pred`, and let E(`i`) be
119
 
120
  - `bool(pred(*i, *(i - 1)))` for the overloads in namespace `std`;
121
  - `bool(invoke(comp, invoke(proj, *i), invoke(proj, *(i - 1))))` for the
122
  overloads in namespace `ranges`.
123
 
124
+ Let:
125
+
126
+ - M be the number of iterators `i` in the range \[`first + 1`, `last`)
127
+ for which E(`i`) is `false`;
128
+ - `result_last` be `result + `M` + 1` for the overloads with no
129
+ parameter `result_last` or `result_r`;
130
+ - N be min(M + 1, `result_last - result`).
131
+
132
  *Mandates:* `*first` is writable [[iterator.requirements.general]] to
133
  `result`.
134
 
135
  *Preconditions:*
136
 
137
+ - The ranges \[`first`, `last`) and \[`result`, `result + `N) do not
138
+ overlap.
139
  - For the overloads in namespace `std`:
140
  - The comparison function is an equivalence relation.
141
  - For the overloads with no `ExecutionPolicy`, let `T` be the value
142
  type of `InputIterator`. If `InputIterator` models
143
  `forward_iterator` [[iterator.concept.forward]], then there are no
144
  additional requirements for `T`. Otherwise, if `OutputIterator`
145
  meets the *Cpp17ForwardIterator* requirements and its value type is
146
  the same as `T`, then `T` meets the *Cpp17CopyAssignable*
147
  ([[cpp17.copyassignable]]) requirements. Otherwise, `T` meets both
148
  the *Cpp17CopyConstructible* ([[cpp17.copyconstructible]]) and
149
+ *Cpp17CopyAssignable* requirements.
 
 
 
 
150
 
151
+ [*Note 1*: For the parallel algorithm overloads in namespace `std`,
152
+ there can be a performance cost if the value type of `ForwardIterator1`
153
+ does not meet both the *Cpp17CopyConstructible* and
154
+ *Cpp17CopyAssignable* requirements. For the parallel algorithm overloads
155
+ in namespace `ranges`, there can be a performance cost if
156
+ `iter_value_t<I>` does not model `copyable`. — *end note*]
157
+
158
+ *Effects:* Copies only the first element from N consecutive groups of
159
+ equivalent elements referred to by the iterator `i` in the range
160
+ \[`first + 1`, `last`) for which E(`i`) holds into the range \[`result`,
161
+ `result + `N).
162
 
163
  *Returns:*
164
 
165
  - `result + `N for the overloads in namespace `std`.
166
+ - `{last, result + `N`}` for the overloads in namespace `ranges`, if N
167
+ is equal to M + 1.
168
+ - Otherwise, `{j, result_last}` for the overloads in namespace `ranges`,
169
+ where `j` is the iterator in \[`first + 1`, `last`) for which E(`j`)
170
+ is `false` and there are exactly N - 1 iterators `i` in \[`first + 1`,
171
+ `j`) for which E(`i`) is `false`.
172
 
173
+ *Complexity:* At most `last - first - 1` applications of the
174
  corresponding predicate and no more than twice as many applications of
175
  any projection.
176