1 // Copyright 2020 The Chromium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #ifndef BASE_RANGES_ALGORITHM_H_
6 #define BASE_RANGES_ALGORITHM_H_
7
8 #include <algorithm>
9 #include <initializer_list>
10 #include <iterator>
11 #include <type_traits>
12 #include <utility>
13
14 #include "base/check.h"
15 #include "base/functional/identity.h"
16 #include "base/functional/invoke.h"
17 #include "base/ranges/functional.h"
18 #include "base/ranges/ranges.h"
19 #include "base/template_util.h"
20
21 namespace base {
22
23 namespace internal {
24
25 // Returns a transformed version of the unary predicate `pred` applying `proj`
26 // to its argument before invoking `pred` on it.
27 // Ensures that the return type of `invoke(pred, ...)` is convertible to bool.
28 template <typename Pred, typename Proj>
ProjectedUnaryPredicate(Pred & pred,Proj & proj)29 constexpr auto ProjectedUnaryPredicate(Pred& pred, Proj& proj) noexcept {
30 return [&pred, &proj](auto&& arg) -> bool {
31 return base::invoke(pred,
32 base::invoke(proj, std::forward<decltype(arg)>(arg)));
33 };
34 }
35
36 // Returns a transformed version of the binary predicate `pred` applying `proj1`
37 // and `proj2` to its arguments before invoking `pred` on them.
38 //
39 // Provides an opt-in to considers all four permutations of projections and
40 // argument types. This is sometimes necessary to allow usage with legacy
41 // non-ranges std:: algorithms that don't support projections.
42 //
43 // These permutations are assigned different priorities to break ambiguities in
44 // case several permutations are possible, e.g. when Proj1 and Proj2 are the
45 // same type.
46 //
47 // Note that even when opting in to using all permutations of projections,
48 // calling code should still ensure that the canonical mapping of {Proj1, Proj2}
49 // to {LHS, RHS} compiles for all members of the range. This can be done by
50 // adding the following constraint:
51 //
52 // typename = indirect_result_t<Pred&,
53 // projected<iterator_t<Range1>, Proj1>,
54 // projected<iterator_t<Range2>, Proj2>>
55 //
56 // Ensures that the return type of `invoke(pred, ...)` is convertible to bool.
57 template <typename Pred, typename Proj1, typename Proj2, bool kPermute = false>
58 class BinaryPredicateProjector {
59 public:
BinaryPredicateProjector(Pred & pred,Proj1 & proj1,Proj2 & proj2)60 constexpr BinaryPredicateProjector(Pred& pred, Proj1& proj1, Proj2& proj2)
61 : pred_(pred), proj1_(proj1), proj2_(proj2) {}
62
63 private:
64 template <typename ProjT, typename ProjU, typename T, typename U>
65 using InvokeResult = invoke_result_t<Pred&,
66 invoke_result_t<ProjT&, T&&>,
67 invoke_result_t<ProjU&, U&&>>;
68
69 template <typename T, typename U, typename = InvokeResult<Proj1, Proj2, T, U>>
GetProjs(priority_tag<3>)70 constexpr std::pair<Proj1&, Proj2&> GetProjs(priority_tag<3>) const {
71 return {proj1_, proj2_};
72 }
73
74 template <typename T,
75 typename U,
76 bool LazyPermute = kPermute,
77 typename = std::enable_if_t<LazyPermute>,
78 typename = InvokeResult<Proj2, Proj1, T, U>>
GetProjs(priority_tag<2>)79 constexpr std::pair<Proj2&, Proj1&> GetProjs(priority_tag<2>) const {
80 return {proj2_, proj1_};
81 }
82
83 template <typename T,
84 typename U,
85 bool LazyPermute = kPermute,
86 typename = std::enable_if_t<LazyPermute>,
87 typename = InvokeResult<Proj1, Proj1, T, U>>
GetProjs(priority_tag<1>)88 constexpr std::pair<Proj1&, Proj1&> GetProjs(priority_tag<1>) const {
89 return {proj1_, proj1_};
90 }
91
92 template <typename T,
93 typename U,
94 bool LazyPermute = kPermute,
95 typename = std::enable_if_t<LazyPermute>,
96 typename = InvokeResult<Proj2, Proj2, T, U>>
GetProjs(priority_tag<0>)97 constexpr std::pair<Proj2&, Proj2&> GetProjs(priority_tag<0>) const {
98 return {proj2_, proj2_};
99 }
100
101 public:
102 template <typename T, typename U>
operator()103 constexpr bool operator()(T&& lhs, U&& rhs) const {
104 auto projs = GetProjs<T, U>(priority_tag<3>());
105 return base::invoke(pred_, base::invoke(projs.first, std::forward<T>(lhs)),
106 base::invoke(projs.second, std::forward<U>(rhs)));
107 }
108
109 private:
110 Pred& pred_;
111 Proj1& proj1_;
112 Proj2& proj2_;
113 };
114
115 // Small wrappers around BinaryPredicateProjector to make the calling side more
116 // readable.
117 template <typename Pred, typename Proj1, typename Proj2>
ProjectedBinaryPredicate(Pred & pred,Proj1 & proj1,Proj2 & proj2)118 constexpr auto ProjectedBinaryPredicate(Pred& pred,
119 Proj1& proj1,
120 Proj2& proj2) noexcept {
121 return BinaryPredicateProjector<Pred, Proj1, Proj2>(pred, proj1, proj2);
122 }
123
124 template <typename Pred, typename Proj1, typename Proj2>
PermutedProjectedBinaryPredicate(Pred & pred,Proj1 & proj1,Proj2 & proj2)125 constexpr auto PermutedProjectedBinaryPredicate(Pred& pred,
126 Proj1& proj1,
127 Proj2& proj2) noexcept {
128 return BinaryPredicateProjector<Pred, Proj1, Proj2, true>(pred, proj1, proj2);
129 }
130
131 // This alias is used below to restrict iterator based APIs to types for which
132 // `iterator_category` and the pre-increment and post-increment operators are
133 // defined. This is required in situations where otherwise an undesired overload
134 // would be chosen, e.g. copy_if. In spirit this is similar to C++20's
135 // std::input_or_output_iterator, a concept that each iterator should satisfy.
136 template <typename Iter,
137 typename = decltype(++std::declval<Iter&>()),
138 typename = decltype(std::declval<Iter&>()++)>
139 using iterator_category_t =
140 typename std::iterator_traits<Iter>::iterator_category;
141
142 // This alias is used below to restrict range based APIs to types for which
143 // `iterator_category_t` is defined for the underlying iterator. This is
144 // required in situations where otherwise an undesired overload would be chosen,
145 // e.g. transform. In spirit this is similar to C++20's std::ranges::range, a
146 // concept that each range should satisfy.
147 template <typename Range>
148 using range_category_t = iterator_category_t<ranges::iterator_t<Range>>;
149
150 } // namespace internal
151
152 namespace ranges {
153
154 // C++14 implementation of std::ranges::in_fun_result. Note the because C++14
155 // lacks the `no_unique_address` attribute it is commented out.
156 //
157 // Reference: https://wg21.link/algorithms.results#:~:text=in_fun_result
158 template <typename I, typename F>
159 struct in_fun_result {
160 /* [[no_unique_address]] */ I in;
161 /* [[no_unique_address]] */ F fun;
162
163 template <typename I2,
164 typename F2,
165 std::enable_if_t<std::is_convertible<const I&, I2>{} &&
166 std::is_convertible<const F&, F2>{}>>
167 constexpr operator in_fun_result<I2, F2>() const& {
168 return {in, fun};
169 }
170
171 template <typename I2,
172 typename F2,
173 std::enable_if_t<std::is_convertible<I, I2>{} &&
174 std::is_convertible<F, F2>{}>>
175 constexpr operator in_fun_result<I2, F2>() && {
176 return {std::move(in), std::move(fun)};
177 }
178 };
179
180 // TODO(crbug.com/1071094): Implement the other result types.
181
182 // [alg.nonmodifying] Non-modifying sequence operations
183 // Reference: https://wg21.link/alg.nonmodifying
184
185 // [alg.all.of] All of
186 // Reference: https://wg21.link/alg.all.of
187
188 // Let `E(i)` be `invoke(pred, invoke(proj, *i))`.
189 //
190 // Returns: `false` if `E(i)` is `false` for some iterator `i` in the range
191 // `[first, last)`, and `true` otherwise.
192 //
193 // Complexity: At most `last - first` applications of the predicate and any
194 // projection.
195 //
196 // Reference: https://wg21.link/alg.all.of#:~:text=ranges::all_of(I
197 template <typename InputIterator,
198 typename Pred,
199 typename Proj = identity,
200 typename = internal::iterator_category_t<InputIterator>>
201 constexpr bool all_of(InputIterator first,
202 InputIterator last,
203 Pred pred,
204 Proj proj = {}) {
205 for (; first != last; ++first) {
206 if (!base::invoke(pred, base::invoke(proj, *first)))
207 return false;
208 }
209
210 return true;
211 }
212
213 // Let `E(i)` be `invoke(pred, invoke(proj, *i))`.
214 //
215 // Returns: `false` if `E(i)` is `false` for some iterator `i` in `range`, and
216 // `true` otherwise.
217 //
218 // Complexity: At most `size(range)` applications of the predicate and any
219 // projection.
220 //
221 // Reference: https://wg21.link/alg.all.of#:~:text=ranges::all_of(R
222 template <typename Range,
223 typename Pred,
224 typename Proj = identity,
225 typename = internal::range_category_t<Range>>
226 constexpr bool all_of(Range&& range, Pred pred, Proj proj = {}) {
227 return ranges::all_of(ranges::begin(range), ranges::end(range),
228 std::move(pred), std::move(proj));
229 }
230
231 // [alg.any.of] Any of
232 // Reference: https://wg21.link/alg.any.of
233
234 // Let `E(i)` be `invoke(pred, invoke(proj, *i))`.
235 //
236 // Returns: `true` if `E(i)` is `true` for some iterator `i` in the range
237 // `[first, last)`, and `false` otherwise.
238 //
239 // Complexity: At most `last - first` applications of the predicate and any
240 // projection.
241 //
242 // Reference: https://wg21.link/alg.any.of#:~:text=ranges::any_of(I
243 template <typename InputIterator,
244 typename Pred,
245 typename Proj = identity,
246 typename = internal::iterator_category_t<InputIterator>>
247 constexpr bool any_of(InputIterator first,
248 InputIterator last,
249 Pred pred,
250 Proj proj = {}) {
251 for (; first != last; ++first) {
252 if (base::invoke(pred, base::invoke(proj, *first)))
253 return true;
254 }
255
256 return false;
257 }
258
259 // Let `E(i)` be `invoke(pred, invoke(proj, *i))`.
260 //
261 // Returns: `true` if `E(i)` is `true` for some iterator `i` in `range`, and
262 // `false` otherwise.
263 //
264 // Complexity: At most `size(range)` applications of the predicate and any
265 // projection.
266 //
267 // Reference: https://wg21.link/alg.any.of#:~:text=ranges::any_of(R
268 template <typename Range,
269 typename Pred,
270 typename Proj = identity,
271 typename = internal::range_category_t<Range>>
272 constexpr bool any_of(Range&& range, Pred pred, Proj proj = {}) {
273 return ranges::any_of(ranges::begin(range), ranges::end(range),
274 std::move(pred), std::move(proj));
275 }
276
277 // [alg.none.of] None of
278 // Reference: https://wg21.link/alg.none.of
279
280 // Let `E(i)` be `invoke(pred, invoke(proj, *i))`.
281 //
282 // Returns: `false` if `E(i)` is `true` for some iterator `i` in the range
283 // `[first, last)`, and `true` otherwise.
284 //
285 // Complexity: At most `last - first` applications of the predicate and any
286 // projection.
287 //
288 // Reference: https://wg21.link/alg.none.of#:~:text=ranges::none_of(I
289 template <typename InputIterator,
290 typename Pred,
291 typename Proj = identity,
292 typename = internal::iterator_category_t<InputIterator>>
293 constexpr bool none_of(InputIterator first,
294 InputIterator last,
295 Pred pred,
296 Proj proj = {}) {
297 for (; first != last; ++first) {
298 if (base::invoke(pred, base::invoke(proj, *first)))
299 return false;
300 }
301
302 return true;
303 }
304
305 // Let `E(i)` be `invoke(pred, invoke(proj, *i))`.
306 //
307 // Returns: `false` if `E(i)` is `true` for some iterator `i` in `range`, and
308 // `true` otherwise.
309 //
310 // Complexity: At most `size(range)` applications of the predicate and any
311 // projection.
312 //
313 // Reference: https://wg21.link/alg.none.of#:~:text=ranges::none_of(R
314 template <typename Range,
315 typename Pred,
316 typename Proj = identity,
317 typename = internal::range_category_t<Range>>
318 constexpr bool none_of(Range&& range, Pred pred, Proj proj = {}) {
319 return ranges::none_of(ranges::begin(range), ranges::end(range),
320 std::move(pred), std::move(proj));
321 }
322
323 // [alg.foreach] For each
324 // Reference: https://wg21.link/alg.foreach
325
326 // Reference: https://wg21.link/algorithm.syn#:~:text=for_each_result
327 template <typename I, typename F>
328 using for_each_result = in_fun_result<I, F>;
329
330 // Effects: Calls `invoke(f, invoke(proj, *i))` for every iterator `i` in the
331 // range `[first, last)`, starting from `first` and proceeding to `last - 1`.
332 //
333 // Returns: `{last, std::move(f)}`.
334 //
335 // Complexity: Applies `f` and `proj` exactly `last - first` times.
336 //
337 // Remarks: If `f` returns a result, the result is ignored.
338 //
339 // Reference: https://wg21.link/alg.foreach#:~:text=ranges::for_each(I
340 template <typename InputIterator,
341 typename Fun,
342 typename Proj = identity,
343 typename = internal::iterator_category_t<InputIterator>>
344 constexpr auto for_each(InputIterator first,
345 InputIterator last,
346 Fun f,
347 Proj proj = {}) {
348 for (; first != last; ++first)
349 base::invoke(f, base::invoke(proj, *first));
350 return for_each_result<InputIterator, Fun>{first, std::move(f)};
351 }
352
353 // Effects: Calls `invoke(f, invoke(proj, *i))` for every iterator `i` in the
354 // range `range`, starting from `begin(range)` and proceeding to `end(range) -
355 // 1`.
356 //
357 // Returns: `{last, std::move(f)}`.
358 //
359 // Complexity: Applies `f` and `proj` exactly `size(range)` times.
360 //
361 // Remarks: If `f` returns a result, the result is ignored.
362 //
363 // Reference: https://wg21.link/alg.foreach#:~:text=ranges::for_each(R
364 template <typename Range,
365 typename Fun,
366 typename Proj = identity,
367 typename = internal::range_category_t<Range>>
368 constexpr auto for_each(Range&& range, Fun f, Proj proj = {}) {
369 return ranges::for_each(ranges::begin(range), ranges::end(range),
370 std::move(f), std::move(proj));
371 }
372
373 // Reference: https://wg21.link/algorithm.syn#:~:text=for_each_n_result
374 template <typename I, typename F>
375 using for_each_n_result = in_fun_result<I, F>;
376
377 // Preconditions: `n >= 0` is `true`.
378 //
379 // Effects: Calls `invoke(f, invoke(proj, *i))` for every iterator `i` in the
380 // range `[first, first + n)` in order.
381 //
382 // Returns: `{first + n, std::move(f)}`.
383 //
384 // Remarks: If `f` returns a result, the result is ignored.
385 //
386 // Reference: https://wg21.link/alg.foreach#:~:text=ranges::for_each_n
387 template <typename InputIterator,
388 typename Size,
389 typename Fun,
390 typename Proj = identity,
391 typename = internal::iterator_category_t<InputIterator>>
392 constexpr auto for_each_n(InputIterator first, Size n, Fun f, Proj proj = {}) {
393 while (n > 0) {
394 base::invoke(f, base::invoke(proj, *first));
395 ++first;
396 --n;
397 }
398
399 return for_each_n_result<InputIterator, Fun>{first, std::move(f)};
400 }
401
402 // [alg.find] Find
403 // Reference: https://wg21.link/alg.find
404
405 // Let `E(i)` be `bool(invoke(proj, *i) == value)`.
406 //
407 // Returns: The first iterator `i` in the range `[first, last)` for which `E(i)`
408 // is `true`. Returns `last` if no such iterator is found.
409 //
410 // Complexity: At most `last - first` applications of the corresponding
411 // predicate and any projection.
412 //
413 // Reference: https://wg21.link/alg.find#:~:text=ranges::find(I
414 template <typename InputIterator,
415 typename T,
416 typename Proj = identity,
417 typename = internal::iterator_category_t<InputIterator>>
418 constexpr auto find(InputIterator first,
419 InputIterator last,
420 const T& value,
421 Proj proj = {}) {
422 // Note: In order to be able to apply `proj` to each element in [first, last)
423 // we are dispatching to std::find_if instead of std::find.
424 return std::find_if(first, last, [&proj, &value](auto&& lhs) {
425 return base::invoke(proj, std::forward<decltype(lhs)>(lhs)) == value;
426 });
427 }
428
429 // Let `E(i)` be `bool(invoke(proj, *i) == value)`.
430 //
431 // Returns: The first iterator `i` in `range` for which `E(i)` is `true`.
432 // Returns `end(range)` if no such iterator is found.
433 //
434 // Complexity: At most `size(range)` applications of the corresponding predicate
435 // and any projection.
436 //
437 // Reference: https://wg21.link/alg.find#:~:text=ranges::find(R
438 template <typename Range,
439 typename T,
440 typename Proj = identity,
441 typename = internal::range_category_t<Range>>
442 constexpr auto find(Range&& range, const T& value, Proj proj = {}) {
443 return ranges::find(ranges::begin(range), ranges::end(range), value,
444 std::move(proj));
445 }
446
447 // Let `E(i)` be `bool(invoke(pred, invoke(proj, *i)))`.
448 //
449 // Returns: The first iterator `i` in the range `[first, last)` for which `E(i)`
450 // is `true`. Returns `last` if no such iterator is found.
451 //
452 // Complexity: At most `last - first` applications of the corresponding
453 // predicate and any projection.
454 //
455 // Reference: https://wg21.link/alg.find#:~:text=ranges::find_if(I
456 template <typename InputIterator,
457 typename Pred,
458 typename Proj = identity,
459 typename = internal::iterator_category_t<InputIterator>>
460 constexpr auto find_if(InputIterator first,
461 InputIterator last,
462 Pred pred,
463 Proj proj = {}) {
464 return std::find_if(first, last,
465 internal::ProjectedUnaryPredicate(pred, proj));
466 }
467
468 // Let `E(i)` be `bool(invoke(pred, invoke(proj, *i)))`.
469 //
470 // Returns: The first iterator `i` in `range` for which `E(i)` is `true`.
471 // Returns `end(range)` if no such iterator is found.
472 //
473 // Complexity: At most `size(range)` applications of the corresponding predicate
474 // and any projection.
475 //
476 // Reference: https://wg21.link/alg.find#:~:text=ranges::find_if(R
477 template <typename Range,
478 typename Pred,
479 typename Proj = identity,
480 typename = internal::range_category_t<Range>>
481 constexpr auto find_if(Range&& range, Pred pred, Proj proj = {}) {
482 return ranges::find_if(ranges::begin(range), ranges::end(range),
483 std::move(pred), std::move(proj));
484 }
485
486 // Let `E(i)` be `bool(!invoke(pred, invoke(proj, *i)))`.
487 //
488 // Returns: The first iterator `i` in the range `[first, last)` for which `E(i)`
489 // is `true`. Returns `last` if no such iterator is found.
490 //
491 // Complexity: At most `last - first` applications of the corresponding
492 // predicate and any projection.
493 //
494 // Reference: https://wg21.link/alg.find#:~:text=ranges::find_if_not(I
495 template <typename InputIterator,
496 typename Pred,
497 typename Proj = identity,
498 typename = internal::iterator_category_t<InputIterator>>
499 constexpr auto find_if_not(InputIterator first,
500 InputIterator last,
501 Pred pred,
502 Proj proj = {}) {
503 return std::find_if_not(first, last,
504 internal::ProjectedUnaryPredicate(pred, proj));
505 }
506
507 // Let `E(i)` be `bool(!invoke(pred, invoke(proj, *i)))`.
508 //
509 // Returns: The first iterator `i` in `range` for which `E(i)` is `true`.
510 // Returns `end(range)` if no such iterator is found.
511 //
512 // Complexity: At most `size(range)` applications of the corresponding predicate
513 // and any projection.
514 //
515 // Reference: https://wg21.link/alg.find#:~:text=ranges::find_if_not(R
516 template <typename Range,
517 typename Pred,
518 typename Proj = identity,
519 typename = internal::range_category_t<Range>>
520 constexpr auto find_if_not(Range&& range, Pred pred, Proj proj = {}) {
521 return ranges::find_if_not(ranges::begin(range), ranges::end(range),
522 std::move(pred), std::move(proj));
523 }
524
525 // [alg.find.end] Find end
526 // Reference: https://wg21.link/alg.find.end
527
528 // Let:
529 // - `E(i,n)` be `invoke(pred, invoke(proj1, *(i + n)),
530 // invoke(proj2, *(first2 + n)))`
531 //
532 // - `i` be `last1` if `[first2, last2)` is empty, or if
533 // `(last2 - first2) > (last1 - first1)` is `true`, or if there is no iterator
534 // in the range `[first1, last1 - (last2 - first2))` such that for every
535 // non-negative integer `n < (last2 - first2)`, `E(i,n)` is `true`. Otherwise
536 // `i` is the last such iterator in `[first1, last1 - (last2 - first2))`.
537 //
538 // Returns: `i`
539 // Note: std::ranges::find_end(I1 first1,...) returns a range, rather than an
540 // iterator. For simplicitly we match std::find_end's return type instead.
541 //
542 // Complexity:
543 // At most `(last2 - first2) * (last1 - first1 - (last2 - first2) + 1)`
544 // applications of the corresponding predicate and any projections.
545 //
546 // Reference: https://wg21.link/alg.find.end#:~:text=ranges::find_end(I1
547 template <typename ForwardIterator1,
548 typename ForwardIterator2,
549 typename Pred = ranges::equal_to,
550 typename Proj1 = identity,
551 typename Proj2 = identity,
552 typename = internal::iterator_category_t<ForwardIterator1>,
553 typename = internal::iterator_category_t<ForwardIterator2>,
554 typename = indirect_result_t<Pred&,
555 projected<ForwardIterator1, Proj1>,
556 projected<ForwardIterator2, Proj2>>>
557 constexpr auto find_end(ForwardIterator1 first1,
558 ForwardIterator1 last1,
559 ForwardIterator2 first2,
560 ForwardIterator2 last2,
561 Pred pred = {},
562 Proj1 proj1 = {},
563 Proj2 proj2 = {}) {
564 return std::find_end(first1, last1, first2, last2,
565 internal::ProjectedBinaryPredicate(pred, proj1, proj2));
566 }
567
568 // Let:
569 // - `E(i,n)` be `invoke(pred, invoke(proj1, *(i + n)),
570 // invoke(proj2, *(first2 + n)))`
571 //
572 // - `i` be `end(range1)` if `range2` is empty, or if
573 // `size(range2) > size(range1)` is `true`, or if there is no iterator in the
574 // range `[begin(range1), end(range1) - size(range2))` such that for every
575 // non-negative integer `n < size(range2)`, `E(i,n)` is `true`. Otherwise `i`
576 // is the last such iterator in `[begin(range1), end(range1) - size(range2))`.
577 //
578 // Returns: `i`
579 // Note: std::ranges::find_end(R1&& r1,...) returns a range, rather than an
580 // iterator. For simplicitly we match std::find_end's return type instead.
581 //
582 // Complexity: At most `size(range2) * (size(range1) - size(range2) + 1)`
583 // applications of the corresponding predicate and any projections.
584 //
585 // Reference: https://wg21.link/alg.find.end#:~:text=ranges::find_end(R1
586 template <typename Range1,
587 typename Range2,
588 typename Pred = ranges::equal_to,
589 typename Proj1 = identity,
590 typename Proj2 = identity,
591 typename = internal::range_category_t<Range1>,
592 typename = internal::range_category_t<Range2>,
593 typename = indirect_result_t<Pred&,
594 projected<iterator_t<Range1>, Proj1>,
595 projected<iterator_t<Range2>, Proj2>>>
596 constexpr auto find_end(Range1&& range1,
597 Range2&& range2,
598 Pred pred = {},
599 Proj1 proj1 = {},
600 Proj2 proj2 = {}) {
601 return ranges::find_end(ranges::begin(range1), ranges::end(range1),
602 ranges::begin(range2), ranges::end(range2),
603 std::move(pred), std::move(proj1), std::move(proj2));
604 }
605
606 // [alg.find.first.of] Find first
607 // Reference: https://wg21.link/alg.find.first.of
608
609 // Let `E(i,j)` be `bool(invoke(pred, invoke(proj1, *i), invoke(proj2, *j)))`.
610 //
611 // Effects: Finds an element that matches one of a set of values.
612 //
613 // Returns: The first iterator `i` in the range `[first1, last1)` such that for
614 // some iterator `j` in the range `[first2, last2)` `E(i,j)` holds. Returns
615 // `last1` if `[first2, last2)` is empty or if no such iterator is found.
616 //
617 // Complexity: At most `(last1 - first1) * (last2 - first2)` applications of the
618 // corresponding predicate and any projections.
619 //
620 // Reference:
621 // https://wg21.link/alg.find.first.of#:~:text=ranges::find_first_of(I1
622 template <typename ForwardIterator1,
623 typename ForwardIterator2,
624 typename Pred = ranges::equal_to,
625 typename Proj1 = identity,
626 typename Proj2 = identity,
627 typename = internal::iterator_category_t<ForwardIterator1>,
628 typename = internal::iterator_category_t<ForwardIterator2>,
629 typename = indirect_result_t<Pred&,
630 projected<ForwardIterator1, Proj1>,
631 projected<ForwardIterator2, Proj2>>>
632 constexpr auto find_first_of(ForwardIterator1 first1,
633 ForwardIterator1 last1,
634 ForwardIterator2 first2,
635 ForwardIterator2 last2,
636 Pred pred = {},
637 Proj1 proj1 = {},
638 Proj2 proj2 = {}) {
639 return std::find_first_of(
640 first1, last1, first2, last2,
641 internal::ProjectedBinaryPredicate(pred, proj1, proj2));
642 }
643
644 // Let `E(i,j)` be `bool(invoke(pred, invoke(proj1, *i), invoke(proj2, *j)))`.
645 //
646 // Effects: Finds an element that matches one of a set of values.
647 //
648 // Returns: The first iterator `i` in `range1` such that for some iterator `j`
649 // in `range2` `E(i,j)` holds. Returns `end(range1)` if `range2` is empty or if
650 // no such iterator is found.
651 //
652 // Complexity: At most `size(range1) * size(range2)` applications of the
653 // corresponding predicate and any projections.
654 //
655 // Reference:
656 // https://wg21.link/alg.find.first.of#:~:text=ranges::find_first_of(R1
657 template <typename Range1,
658 typename Range2,
659 typename Pred = ranges::equal_to,
660 typename Proj1 = identity,
661 typename Proj2 = identity,
662 typename = internal::range_category_t<Range1>,
663 typename = internal::range_category_t<Range2>,
664 typename = indirect_result_t<Pred&,
665 projected<iterator_t<Range1>, Proj1>,
666 projected<iterator_t<Range2>, Proj2>>>
667 constexpr auto find_first_of(Range1&& range1,
668 Range2&& range2,
669 Pred pred = {},
670 Proj1 proj1 = {},
671 Proj2 proj2 = {}) {
672 return ranges::find_first_of(
673 ranges::begin(range1), ranges::end(range1), ranges::begin(range2),
674 ranges::end(range2), std::move(pred), std::move(proj1), std::move(proj2));
675 }
676
677 // [alg.adjacent.find] Adjacent find
678 // Reference: https://wg21.link/alg.adjacent.find
679
680 // Let `E(i)` be `bool(invoke(pred, invoke(proj, *i), invoke(proj, *(i + 1))))`.
681 //
682 // Returns: The first iterator `i` such that both `i` and `i + 1` are in the
683 // range `[first, last)` for which `E(i)` holds. Returns `last` if no such
684 // iterator is found.
685 //
686 // Complexity: Exactly `min((i - first) + 1, (last - first) - 1)` applications
687 // of the corresponding predicate, where `i` is `adjacent_find`'s return value.
688 //
689 // Reference:
690 // https://wg21.link/alg.adjacent.find#:~:text=ranges::adjacent_find(I
691 template <typename ForwardIterator,
692 typename Pred = ranges::equal_to,
693 typename Proj = identity,
694 typename = internal::iterator_category_t<ForwardIterator>>
695 constexpr auto adjacent_find(ForwardIterator first,
696 ForwardIterator last,
697 Pred pred = {},
698 Proj proj = {}) {
699 // Implementation inspired by cppreference.com:
700 // https://en.cppreference.com/w/cpp/algorithm/adjacent_find
701 //
702 // A reimplementation is required, because std::adjacent_find is not constexpr
703 // prior to C++20. Once we have C++20, we should switch to standard library
704 // implementation.
705 if (first == last)
706 return last;
707
708 for (ForwardIterator next = first; ++next != last; ++first) {
709 if (base::invoke(pred, base::invoke(proj, *first),
710 base::invoke(proj, *next))) {
711 return first;
712 }
713 }
714
715 return last;
716 }
717
718 // Let `E(i)` be `bool(invoke(pred, invoke(proj, *i), invoke(proj, *(i + 1))))`.
719 //
720 // Returns: The first iterator `i` such that both `i` and `i + 1` are in the
721 // range `range` for which `E(i)` holds. Returns `end(range)` if no such
722 // iterator is found.
723 //
724 // Complexity: Exactly `min((i - begin(range)) + 1, size(range) - 1)`
725 // applications of the corresponding predicate, where `i` is `adjacent_find`'s
726 // return value.
727 //
728 // Reference:
729 // https://wg21.link/alg.adjacent.find#:~:text=ranges::adjacent_find(R
730 template <typename Range,
731 typename Pred = ranges::equal_to,
732 typename Proj = identity,
733 typename = internal::range_category_t<Range>>
734 constexpr auto adjacent_find(Range&& range, Pred pred = {}, Proj proj = {}) {
735 return ranges::adjacent_find(ranges::begin(range), ranges::end(range),
736 std::move(pred), std::move(proj));
737 }
738
739 // [alg.count] Count
740 // Reference: https://wg21.link/alg.count
741
742 // Let `E(i)` be `invoke(proj, *i) == value`.
743 //
744 // Effects: Returns the number of iterators `i` in the range `[first, last)` for
745 // which `E(i)` holds.
746 //
747 // Complexity: Exactly `last - first` applications of the corresponding
748 // predicate and any projection.
749 //
750 // Reference: https://wg21.link/alg.count#:~:text=ranges::count(I
751 template <typename InputIterator,
752 typename T,
753 typename Proj = identity,
754 typename = internal::iterator_category_t<InputIterator>>
755 constexpr auto count(InputIterator first,
756 InputIterator last,
757 const T& value,
758 Proj proj = {}) {
759 // Note: In order to be able to apply `proj` to each element in [first, last)
760 // we are dispatching to std::count_if instead of std::count.
761 return std::count_if(first, last, [&proj, &value](auto&& lhs) {
762 return base::invoke(proj, std::forward<decltype(lhs)>(lhs)) == value;
763 });
764 }
765
766 // Let `E(i)` be `invoke(proj, *i) == value`.
767 //
768 // Effects: Returns the number of iterators `i` in `range` for which `E(i)`
769 // holds.
770 //
771 // Complexity: Exactly `size(range)` applications of the corresponding predicate
772 // and any projection.
773 //
774 // Reference: https://wg21.link/alg.count#:~:text=ranges::count(R
775 template <typename Range,
776 typename T,
777 typename Proj = identity,
778 typename = internal::range_category_t<Range>>
779 constexpr auto count(Range&& range, const T& value, Proj proj = {}) {
780 return ranges::count(ranges::begin(range), ranges::end(range), value,
781 std::move(proj));
782 }
783
784 // Let `E(i)` be `bool(invoke(pred, invoke(proj, *i)))`.
785 //
786 // Effects: Returns the number of iterators `i` in the range `[first, last)` for
787 // which `E(i)` holds.
788 //
789 // Complexity: Exactly `last - first` applications of the corresponding
790 // predicate and any projection.
791 //
792 // Reference: https://wg21.link/alg.count#:~:text=ranges::count_if(I
793 template <typename InputIterator,
794 typename Pred,
795 typename Proj = identity,
796 typename = internal::iterator_category_t<InputIterator>>
797 constexpr auto count_if(InputIterator first,
798 InputIterator last,
799 Pred pred,
800 Proj proj = {}) {
801 return std::count_if(first, last,
802 internal::ProjectedUnaryPredicate(pred, proj));
803 }
804
805 // Let `E(i)` be `bool(invoke(pred, invoke(proj, *i)))`.
806 //
807 // Effects: Returns the number of iterators `i` in `range` for which `E(i)`
808 // holds.
809 //
810 // Complexity: Exactly `size(range)` applications of the corresponding predicate
811 // and any projection.
812 //
813 // Reference: https://wg21.link/alg.count#:~:text=ranges::count_if(R
814 template <typename Range,
815 typename Pred,
816 typename Proj = identity,
817 typename = internal::range_category_t<Range>>
818 constexpr auto count_if(Range&& range, Pred pred, Proj proj = {}) {
819 return ranges::count_if(ranges::begin(range), ranges::end(range),
820 std::move(pred), std::move(proj));
821 }
822
823 // [mismatch] Mismatch
824 // Reference: https://wg21.link/mismatch
825
826 // Let `E(n)` be `!invoke(pred, invoke(proj1, *(first1 + n)),
827 // invoke(proj2, *(first2 + n)))`.
828 //
829 // Let `N` be `min(last1 - first1, last2 - first2)`.
830 //
831 // Returns: `{ first1 + n, first2 + n }`, where `n` is the smallest integer in
832 // `[0, N)` such that `E(n)` holds, or `N` if no such integer exists.
833 //
834 // Complexity: At most `N` applications of the corresponding predicate and any
835 // projections.
836 //
837 // Reference: https://wg21.link/mismatch#:~:text=ranges::mismatch(I1
838 template <typename ForwardIterator1,
839 typename ForwardIterator2,
840 typename Pred = ranges::equal_to,
841 typename Proj1 = identity,
842 typename Proj2 = identity,
843 typename = internal::iterator_category_t<ForwardIterator1>,
844 typename = internal::iterator_category_t<ForwardIterator2>,
845 typename = indirect_result_t<Pred&,
846 projected<ForwardIterator1, Proj1>,
847 projected<ForwardIterator2, Proj2>>>
848 constexpr auto mismatch(ForwardIterator1 first1,
849 ForwardIterator1 last1,
850 ForwardIterator2 first2,
851 ForwardIterator2 last2,
852 Pred pred = {},
853 Proj1 proj1 = {},
854 Proj2 proj2 = {}) {
855 return std::mismatch(first1, last1, first2, last2,
856 internal::ProjectedBinaryPredicate(pred, proj1, proj2));
857 }
858
859 // Let `E(n)` be `!invoke(pred, invoke(proj1, *(begin(range1) + n)),
860 // invoke(proj2, *(begin(range2) + n)))`.
861 //
862 // Let `N` be `min(size(range1), size(range2))`.
863 //
864 // Returns: `{ begin(range1) + n, begin(range2) + n }`, where `n` is the
865 // smallest integer in `[0, N)` such that `E(n)` holds, or `N` if no such
866 // integer exists.
867 //
868 // Complexity: At most `N` applications of the corresponding predicate and any
869 // projections.
870 //
871 // Reference: https://wg21.link/mismatch#:~:text=ranges::mismatch(R1
872 template <typename Range1,
873 typename Range2,
874 typename Pred = ranges::equal_to,
875 typename Proj1 = identity,
876 typename Proj2 = identity,
877 typename = internal::range_category_t<Range1>,
878 typename = internal::range_category_t<Range2>,
879 typename = indirect_result_t<Pred&,
880 projected<iterator_t<Range1>, Proj1>,
881 projected<iterator_t<Range2>, Proj2>>>
882 constexpr auto mismatch(Range1&& range1,
883 Range2&& range2,
884 Pred pred = {},
885 Proj1 proj1 = {},
886 Proj2 proj2 = {}) {
887 return ranges::mismatch(ranges::begin(range1), ranges::end(range1),
888 ranges::begin(range2), ranges::end(range2),
889 std::move(pred), std::move(proj1), std::move(proj2));
890 }
891
892 // [alg.equal] Equal
893 // Reference: https://wg21.link/alg.equal
894
895 // Let `E(i)` be
896 // `invoke(pred, invoke(proj1, *i), invoke(proj2, *(first2 + (i - first1))))`.
897 //
898 // Returns: If `last1 - first1 != last2 - first2`, return `false.` Otherwise
899 // return `true` if `E(i)` holds for every iterator `i` in the range `[first1,
900 // last1)`. Otherwise, returns `false`.
901 //
902 // Complexity: If the types of `first1`, `last1`, `first2`, and `last2` meet the
903 // `RandomAccessIterator` requirements and `last1 - first1 != last2 - first2`,
904 // then no applications of the corresponding predicate and each projection;
905 // otherwise, at most `min(last1 - first1, last2 - first2)` applications of the
906 // corresponding predicate and any projections.
907 //
908 // Reference: https://wg21.link/alg.equal#:~:text=ranges::equal(I1
909 template <typename ForwardIterator1,
910 typename ForwardIterator2,
911 typename Pred = ranges::equal_to,
912 typename Proj1 = identity,
913 typename Proj2 = identity,
914 typename = internal::iterator_category_t<ForwardIterator1>,
915 typename = internal::iterator_category_t<ForwardIterator2>,
916 typename = indirect_result_t<Pred&,
917 projected<ForwardIterator1, Proj1>,
918 projected<ForwardIterator2, Proj2>>>
919 constexpr bool equal(ForwardIterator1 first1,
920 ForwardIterator1 last1,
921 ForwardIterator2 first2,
922 ForwardIterator2 last2,
923 Pred pred = {},
924 Proj1 proj1 = {},
925 Proj2 proj2 = {}) {
926 return std::equal(first1, last1, first2, last2,
927 internal::ProjectedBinaryPredicate(pred, proj1, proj2));
928 }
929
930 // Let `E(i)` be
931 // `invoke(pred, invoke(proj1, *i),
932 // invoke(proj2, *(begin(range2) + (i - begin(range1)))))`.
933 //
934 // Returns: If `size(range1) != size(range2)`, return `false.` Otherwise return
935 // `true` if `E(i)` holds for every iterator `i` in `range1`. Otherwise, returns
936 // `false`.
937 //
938 // Complexity: If the types of `begin(range1)`, `end(range1)`, `begin(range2)`,
939 // and `end(range2)` meet the `RandomAccessIterator` requirements and
940 // `size(range1) != size(range2)`, then no applications of the corresponding
941 // predicate and each projection;
942 // otherwise, at most `min(size(range1), size(range2))` applications of the
943 // corresponding predicate and any projections.
944 //
945 // Reference: https://wg21.link/alg.equal#:~:text=ranges::equal(R1
946 template <typename Range1,
947 typename Range2,
948 typename Pred = ranges::equal_to,
949 typename Proj1 = identity,
950 typename Proj2 = identity,
951 typename = internal::range_category_t<Range1>,
952 typename = internal::range_category_t<Range2>,
953 typename = indirect_result_t<Pred&,
954 projected<iterator_t<Range1>, Proj1>,
955 projected<iterator_t<Range2>, Proj2>>>
956 constexpr bool equal(Range1&& range1,
957 Range2&& range2,
958 Pred pred = {},
959 Proj1 proj1 = {},
960 Proj2 proj2 = {}) {
961 return ranges::equal(ranges::begin(range1), ranges::end(range1),
962 ranges::begin(range2), ranges::end(range2),
963 std::move(pred), std::move(proj1), std::move(proj2));
964 }
965
966 // [alg.is.permutation] Is permutation
967 // Reference: https://wg21.link/alg.is.permutation
968
969 // Returns: If `last1 - first1 != last2 - first2`, return `false`. Otherwise
970 // return `true` if there exists a permutation of the elements in the range
971 // `[first2, last2)`, bounded by `[pfirst, plast)`, such that
972 // `ranges::equal(first1, last1, pfirst, plast, pred, proj, proj)` returns
973 // `true`; otherwise, returns `false`.
974 //
975 // Complexity: No applications of the corresponding predicate if
976 // ForwardIterator1 and ForwardIterator2 meet the requirements of random access
977 // iterators and `last1 - first1 != last2 - first2`. Otherwise, exactly
978 // `last1 - first1` applications of the corresponding predicate and projections
979 // if `ranges::equal(first1, last1, first2, last2, pred, proj, proj)` would
980 // return true;
981 // otherwise, at worst `O(N^2)`, where `N` has the value `last1 - first1`.
982 //
983 // Reference:
984 // https://wg21.link/alg.is.permutation#:~:text=ranges::is_permutation(I1
985 template <typename ForwardIterator1,
986 typename ForwardIterator2,
987 typename Pred = ranges::equal_to,
988 typename Proj1 = identity,
989 typename Proj2 = identity,
990 typename = internal::iterator_category_t<ForwardIterator1>,
991 typename = internal::iterator_category_t<ForwardIterator2>,
992 typename = indirect_result_t<Pred&,
993 projected<ForwardIterator1, Proj1>,
994 projected<ForwardIterator2, Proj2>>>
995 constexpr bool is_permutation(ForwardIterator1 first1,
996 ForwardIterator1 last1,
997 ForwardIterator2 first2,
998 ForwardIterator2 last2,
999 Pred pred = {},
1000 Proj1 proj1 = {},
1001 Proj2 proj2 = {}) {
1002 // Needs to opt-in to all permutations, since std::is_permutation expects
1003 // pred(proj1(lhs), proj1(rhs)) to compile.
1004 return std::is_permutation(
1005 first1, last1, first2, last2,
1006 internal::PermutedProjectedBinaryPredicate(pred, proj1, proj2));
1007 }
1008
1009 // Returns: If `size(range1) != size(range2)`, return `false`. Otherwise return
1010 // `true` if there exists a permutation of the elements in `range2`, bounded by
1011 // `[pbegin, pend)`, such that
1012 // `ranges::equal(range1, [pbegin, pend), pred, proj, proj)` returns `true`;
1013 // otherwise, returns `false`.
1014 //
1015 // Complexity: No applications of the corresponding predicate if Range1 and
1016 // Range2 meet the requirements of random access ranges and
1017 // `size(range1) != size(range2)`. Otherwise, exactly `size(range1)`
1018 // applications of the corresponding predicate and projections if
1019 // `ranges::equal(range1, range2, pred, proj, proj)` would return true;
1020 // otherwise, at worst `O(N^2)`, where `N` has the value `size(range1)`.
1021 //
1022 // Reference:
1023 // https://wg21.link/alg.is.permutation#:~:text=ranges::is_permutation(R1
1024 template <typename Range1,
1025 typename Range2,
1026 typename Pred = ranges::equal_to,
1027 typename Proj1 = identity,
1028 typename Proj2 = identity,
1029 typename = internal::range_category_t<Range1>,
1030 typename = internal::range_category_t<Range2>,
1031 typename = indirect_result_t<Pred&,
1032 projected<iterator_t<Range1>, Proj1>,
1033 projected<iterator_t<Range2>, Proj2>>>
1034 constexpr bool is_permutation(Range1&& range1,
1035 Range2&& range2,
1036 Pred pred = {},
1037 Proj1 proj1 = {},
1038 Proj2 proj2 = {}) {
1039 return ranges::is_permutation(
1040 ranges::begin(range1), ranges::end(range1), ranges::begin(range2),
1041 ranges::end(range2), std::move(pred), std::move(proj1), std::move(proj2));
1042 }
1043
1044 // [alg.search] Search
1045 // Reference: https://wg21.link/alg.search
1046
1047 // Returns: `i`, where `i` is the first iterator in the range
1048 // `[first1, last1 - (last2 - first2))` such that for every non-negative integer
1049 // `n` less than `last2 - first2` the condition
1050 // `bool(invoke(pred, invoke(proj1, *(i + n)), invoke(proj2, *(first2 + n))))`
1051 // is `true`.
1052 // Returns `last1` if no such iterator exists.
1053 // Note: std::ranges::search(I1 first1,...) returns a range, rather than an
1054 // iterator. For simplicitly we match std::search's return type instead.
1055 //
1056 // Complexity: At most `(last1 - first1) * (last2 - first2)` applications of the
1057 // corresponding predicate and projections.
1058 //
1059 // Reference: https://wg21.link/alg.search#:~:text=ranges::search(I1
1060 template <typename ForwardIterator1,
1061 typename ForwardIterator2,
1062 typename Pred = ranges::equal_to,
1063 typename Proj1 = identity,
1064 typename Proj2 = identity,
1065 typename = internal::iterator_category_t<ForwardIterator1>,
1066 typename = internal::iterator_category_t<ForwardIterator2>,
1067 typename = indirect_result_t<Pred&,
1068 projected<ForwardIterator1, Proj1>,
1069 projected<ForwardIterator2, Proj2>>>
1070 constexpr auto search(ForwardIterator1 first1,
1071 ForwardIterator1 last1,
1072 ForwardIterator2 first2,
1073 ForwardIterator2 last2,
1074 Pred pred = {},
1075 Proj1 proj1 = {},
1076 Proj2 proj2 = {}) {
1077 return std::search(first1, last1, first2, last2,
1078 internal::ProjectedBinaryPredicate(pred, proj1, proj2));
1079 }
1080
1081 // Returns: `i`, where `i` is the first iterator in the range
1082 // `[begin(range1), end(range1) - size(range2))` such that for every
1083 // non-negative integer `n` less than `size(range2)` the condition
1084 // `bool(invoke(pred, invoke(proj1, *(i + n)),
1085 // invoke(proj2, *(begin(range2) + n))))` is `true`.
1086 // Returns `end(range1)` if no such iterator exists.
1087 // Note: std::ranges::search(R1&& r1,...) returns a range, rather than an
1088 // iterator. For simplicitly we match std::search's return type instead.
1089 //
1090 // Complexity: At most `size(range1) * size(range2)` applications of the
1091 // corresponding predicate and projections.
1092 //
1093 // Reference: https://wg21.link/alg.search#:~:text=ranges::search(R1
1094 template <typename Range1,
1095 typename Range2,
1096 typename Pred = ranges::equal_to,
1097 typename Proj1 = identity,
1098 typename Proj2 = identity,
1099 typename = internal::range_category_t<Range1>,
1100 typename = internal::range_category_t<Range2>,
1101 typename = indirect_result_t<Pred&,
1102 projected<iterator_t<Range1>, Proj1>,
1103 projected<iterator_t<Range2>, Proj2>>>
1104 constexpr auto search(Range1&& range1,
1105 Range2&& range2,
1106 Pred pred = {},
1107 Proj1 proj1 = {},
1108 Proj2 proj2 = {}) {
1109 return ranges::search(ranges::begin(range1), ranges::end(range1),
1110 ranges::begin(range2), ranges::end(range2),
1111 std::move(pred), std::move(proj1), std::move(proj2));
1112 }
1113
1114 // Mandates: The type `Size` is convertible to an integral type.
1115 //
1116 // Returns: `i` where `i` is the first iterator in the range
1117 // `[first, last - count)` such that for every non-negative integer `n` less
1118 // than `count`, the following condition holds:
1119 // `invoke(pred, invoke(proj, *(i + n)), value)`.
1120 // Returns `last` if no such iterator is found.
1121 // Note: std::ranges::search_n(I1 first1,...) returns a range, rather than an
1122 // iterator. For simplicitly we match std::search_n's return type instead.
1123 //
1124 // Complexity: At most `last - first` applications of the corresponding
1125 // predicate and projection.
1126 //
1127 // Reference: https://wg21.link/alg.search#:~:text=ranges::search_n(I
1128 template <typename ForwardIterator,
1129 typename Size,
1130 typename T,
1131 typename Pred = ranges::equal_to,
1132 typename Proj = identity,
1133 typename = internal::iterator_category_t<ForwardIterator>>
1134 constexpr auto search_n(ForwardIterator first,
1135 ForwardIterator last,
1136 Size count,
1137 const T& value,
1138 Pred pred = {},
1139 Proj proj = {}) {
1140 // The second arg is guaranteed to be `value`, so we'll simply apply the
1141 // identity projection.
1142 identity value_proj;
1143 return std::search_n(
1144 first, last, count, value,
1145 internal::ProjectedBinaryPredicate(pred, proj, value_proj));
1146 }
1147
1148 // Mandates: The type `Size` is convertible to an integral type.
1149 //
1150 // Returns: `i` where `i` is the first iterator in the range
1151 // `[begin(range), end(range) - count)` such that for every non-negative integer
1152 // `n` less than `count`, the following condition holds:
1153 // `invoke(pred, invoke(proj, *(i + n)), value)`.
1154 // Returns `end(arnge)` if no such iterator is found.
1155 // Note: std::ranges::search_n(R1&& r1,...) returns a range, rather than an
1156 // iterator. For simplicitly we match std::search_n's return type instead.
1157 //
1158 // Complexity: At most `size(range)` applications of the corresponding predicate
1159 // and projection.
1160 //
1161 // Reference: https://wg21.link/alg.search#:~:text=ranges::search_n(R
1162 template <typename Range,
1163 typename Size,
1164 typename T,
1165 typename Pred = ranges::equal_to,
1166 typename Proj = identity,
1167 typename = internal::range_category_t<Range>>
1168 constexpr auto search_n(Range&& range,
1169 Size count,
1170 const T& value,
1171 Pred pred = {},
1172 Proj proj = {}) {
1173 return ranges::search_n(ranges::begin(range), ranges::end(range), count,
1174 value, std::move(pred), std::move(proj));
1175 }
1176
1177 // [alg.modifying.operations] Mutating sequence operations
1178 // Reference: https://wg21.link/alg.modifying.operations
1179
1180 // [alg.copy] Copy
1181 // Reference: https://wg21.link/alg.copy
1182
1183 // Let N be `last - first`.
1184 //
1185 // Preconditions: `result` is not in the range `[first, last)`.
1186 //
1187 // Effects: Copies elements in the range `[first, last)` into the range
1188 // `[result, result + N)` starting from `first` and proceeding to `last`. For
1189 // each non-negative integer `n < N` , performs `*(result + n) = *(first + n)`.
1190 //
1191 // Returns: `result + N`
1192 //
1193 // Complexity: Exactly `N` assignments.
1194 //
1195 // Reference: https://wg21.link/alg.copy#:~:text=ranges::copy(I
1196 template <typename InputIterator,
1197 typename OutputIterator,
1198 typename = internal::iterator_category_t<InputIterator>,
1199 typename = internal::iterator_category_t<OutputIterator>>
copy(InputIterator first,InputIterator last,OutputIterator result)1200 constexpr auto copy(InputIterator first,
1201 InputIterator last,
1202 OutputIterator result) {
1203 return std::copy(first, last, result);
1204 }
1205
1206 // Let N be `size(range)`.
1207 //
1208 // Preconditions: `result` is not in `range`.
1209 //
1210 // Effects: Copies elements in `range` into the range `[result, result + N)`
1211 // starting from `begin(range)` and proceeding to `end(range)`. For each
1212 // non-negative integer `n < N` , performs
1213 // *(result + n) = *(begin(range) + n)`.
1214 //
1215 // Returns: `result + N`
1216 //
1217 // Complexity: Exactly `N` assignments.
1218 //
1219 // Reference: https://wg21.link/alg.copy#:~:text=ranges::copy(R
1220 template <typename Range,
1221 typename OutputIterator,
1222 typename = internal::range_category_t<Range>,
1223 typename = internal::iterator_category_t<OutputIterator>>
copy(Range && range,OutputIterator result)1224 constexpr auto copy(Range&& range, OutputIterator result) {
1225 return ranges::copy(ranges::begin(range), ranges::end(range), result);
1226 }
1227
1228 // Let `N` be `max(0, n)`.
1229 //
1230 // Mandates: The type `Size` is convertible to an integral type.
1231 //
1232 // Effects: For each non-negative integer `i < N`, performs
1233 // `*(result + i) = *(first + i)`.
1234 //
1235 // Returns: `result + N`
1236 //
1237 // Complexity: Exactly `N` assignments.
1238 //
1239 // Reference: https://wg21.link/alg.copy#:~:text=ranges::copy_n
1240 template <typename InputIterator,
1241 typename Size,
1242 typename OutputIterator,
1243 typename = internal::iterator_category_t<InputIterator>,
1244 typename = internal::iterator_category_t<OutputIterator>>
copy_n(InputIterator first,Size n,OutputIterator result)1245 constexpr auto copy_n(InputIterator first, Size n, OutputIterator result) {
1246 return std::copy_n(first, n, result);
1247 }
1248
1249 // Let `E(i)` be `bool(invoke(pred, invoke(proj, *i)))`, and `N` be the number
1250 // of iterators `i` in the range `[first, last)` for which the condition `E(i)`
1251 // holds.
1252 //
1253 // Preconditions: The ranges `[first, last)` and
1254 // `[result, result + (last - first))` do not overlap.
1255 //
1256 // Effects: Copies all of the elements referred to by the iterator `i` in the
1257 // range `[first, last)` for which `E(i)` is true.
1258 //
1259 // Returns: `result + N`
1260 //
1261 // Complexity: Exactly `last - first` applications of the corresponding
1262 // predicate and any projection.
1263 //
1264 // Remarks: Stable.
1265 //
1266 // Reference: https://wg21.link/alg.copy#:~:text=ranges::copy_if(I
1267 template <typename InputIterator,
1268 typename OutputIterator,
1269 typename Pred,
1270 typename Proj = identity,
1271 typename = internal::iterator_category_t<InputIterator>,
1272 typename = internal::iterator_category_t<OutputIterator>>
1273 constexpr auto copy_if(InputIterator first,
1274 InputIterator last,
1275 OutputIterator result,
1276 Pred pred,
1277 Proj proj = {}) {
1278 return std::copy_if(first, last, result,
1279 internal::ProjectedUnaryPredicate(pred, proj));
1280 }
1281
1282 // Let `E(i)` be `bool(invoke(pred, invoke(proj, *i)))`, and `N` be the number
1283 // of iterators `i` in `range` for which the condition `E(i)` holds.
1284 //
1285 // Preconditions: `range` and `[result, result + size(range))` do not overlap.
1286 //
1287 // Effects: Copies all of the elements referred to by the iterator `i` in
1288 // `range` for which `E(i)` is true.
1289 //
1290 // Returns: `result + N`
1291 //
1292 // Complexity: Exactly `size(range)` applications of the corresponding predicate
1293 // and any projection.
1294 //
1295 // Remarks: Stable.
1296 //
1297 // Reference: https://wg21.link/alg.copy#:~:text=ranges::copy_if(R
1298 template <typename Range,
1299 typename OutputIterator,
1300 typename Pred,
1301 typename Proj = identity,
1302 typename = internal::range_category_t<Range>,
1303 typename = internal::iterator_category_t<OutputIterator>>
1304 constexpr auto copy_if(Range&& range,
1305 OutputIterator result,
1306 Pred pred,
1307 Proj proj = {}) {
1308 return ranges::copy_if(ranges::begin(range), ranges::end(range), result,
1309 std::move(pred), std::move(proj));
1310 }
1311
1312 // Let `N` be `last - first`.
1313 //
1314 // Preconditions: `result` is not in the range `(first, last]`.
1315 //
1316 // Effects: Copies elements in the range `[first, last)` into the range
1317 // `[result - N, result)` starting from `last - 1` and proceeding to `first`.
1318 // For each positive integer `n ≤ N`, performs `*(result - n) = *(last - n)`.
1319 //
1320 // Returns: `result - N`
1321 //
1322 // Complexity: Exactly `N` assignments.
1323 //
1324 // Reference: https://wg21.link/alg.copy#:~:text=ranges::copy_backward(I1
1325 template <typename BidirectionalIterator1,
1326 typename BidirectionalIterator2,
1327 typename = internal::iterator_category_t<BidirectionalIterator1>,
1328 typename = internal::iterator_category_t<BidirectionalIterator2>>
copy_backward(BidirectionalIterator1 first,BidirectionalIterator1 last,BidirectionalIterator2 result)1329 constexpr auto copy_backward(BidirectionalIterator1 first,
1330 BidirectionalIterator1 last,
1331 BidirectionalIterator2 result) {
1332 return std::copy_backward(first, last, result);
1333 }
1334
1335 // Let `N` be `size(range)`.
1336 //
1337 // Preconditions: `result` is not in the range `(begin(range), end(range)]`.
1338 //
1339 // Effects: Copies elements in `range` into the range `[result - N, result)`
1340 // starting from `end(range) - 1` and proceeding to `begin(range)`. For each
1341 // positive integer `n ≤ N`, performs `*(result - n) = *(end(range) - n)`.
1342 //
1343 // Returns: `result - N`
1344 //
1345 // Complexity: Exactly `N` assignments.
1346 //
1347 // Reference: https://wg21.link/alg.copy#:~:text=ranges::copy_backward(R
1348 template <typename Range,
1349 typename BidirectionalIterator,
1350 typename = internal::range_category_t<Range>,
1351 typename = internal::iterator_category_t<BidirectionalIterator>>
copy_backward(Range && range,BidirectionalIterator result)1352 constexpr auto copy_backward(Range&& range, BidirectionalIterator result) {
1353 return ranges::copy_backward(ranges::begin(range), ranges::end(range),
1354 result);
1355 }
1356
1357 // [alg.move] Move
1358 // Reference: https://wg21.link/alg.move
1359
1360 // Let `E(n)` be `std::move(*(first + n))`.
1361 //
1362 // Let `N` be `last - first`.
1363 //
1364 // Preconditions: `result` is not in the range `[first, last)`.
1365 //
1366 // Effects: Moves elements in the range `[first, last)` into the range `[result,
1367 // result + N)` starting from `first` and proceeding to `last`. For each
1368 // non-negative integer `n < N`, performs `*(result + n) = E(n)`.
1369 //
1370 // Returns: `result + N`
1371 //
1372 // Complexity: Exactly `N` assignments.
1373 //
1374 // Reference: https://wg21.link/alg.move#:~:text=ranges::move(I
1375 template <typename InputIterator,
1376 typename OutputIterator,
1377 typename = internal::iterator_category_t<InputIterator>,
1378 typename = internal::iterator_category_t<OutputIterator>>
move(InputIterator first,InputIterator last,OutputIterator result)1379 constexpr auto move(InputIterator first,
1380 InputIterator last,
1381 OutputIterator result) {
1382 return std::move(first, last, result);
1383 }
1384
1385 // Let `E(n)` be `std::move(*(begin(range) + n))`.
1386 //
1387 // Let `N` be `size(range)`.
1388 //
1389 // Preconditions: `result` is not in `range`.
1390 //
1391 // Effects: Moves elements in `range` into the range `[result, result + N)`
1392 // starting from `begin(range)` and proceeding to `end(range)`. For each
1393 // non-negative integer `n < N`, performs `*(result + n) = E(n)`.
1394 //
1395 // Returns: `result + N`
1396 //
1397 // Complexity: Exactly `N` assignments.
1398 //
1399 // Reference: https://wg21.link/alg.move#:~:text=ranges::move(R
1400 template <typename Range,
1401 typename OutputIterator,
1402 typename = internal::range_category_t<Range>,
1403 typename = internal::iterator_category_t<OutputIterator>>
move(Range && range,OutputIterator result)1404 constexpr auto move(Range&& range, OutputIterator result) {
1405 return ranges::move(ranges::begin(range), ranges::end(range), result);
1406 }
1407
1408 // Let `E(n)` be `std::move(*(last - n))`.
1409 //
1410 // Let `N` be `last - first`.
1411 //
1412 // Preconditions: `result` is not in the range `(first, last]`.
1413 //
1414 // Effects: Moves elements in the range `[first, last)` into the range
1415 // `[result - N, result)` starting from `last - 1` and proceeding to `first`.
1416 // For each positive integer `n ≤ N`, performs `*(result - n) = E(n)`.
1417 //
1418 // Returns: `result - N`
1419 //
1420 // Complexity: Exactly `N` assignments.
1421 //
1422 // Reference: https://wg21.link/alg.move#:~:text=ranges::move_backward(I1
1423 template <typename BidirectionalIterator1,
1424 typename BidirectionalIterator2,
1425 typename = internal::iterator_category_t<BidirectionalIterator1>,
1426 typename = internal::iterator_category_t<BidirectionalIterator2>>
move_backward(BidirectionalIterator1 first,BidirectionalIterator1 last,BidirectionalIterator2 result)1427 constexpr auto move_backward(BidirectionalIterator1 first,
1428 BidirectionalIterator1 last,
1429 BidirectionalIterator2 result) {
1430 return std::move_backward(first, last, result);
1431 }
1432
1433 // Let `E(n)` be `std::move(*(end(range) - n))`.
1434 //
1435 // Let `N` be `size(range)`.
1436 //
1437 // Preconditions: `result` is not in the range `(begin(range), end(range)]`.
1438 //
1439 // Effects: Moves elements in `range` into the range `[result - N, result)`
1440 // starting from `end(range) - 1` and proceeding to `begin(range)`. For each
1441 // positive integer `n ≤ N`, performs `*(result - n) = E(n)`.
1442 //
1443 // Returns: `result - N`
1444 //
1445 // Complexity: Exactly `N` assignments.
1446 //
1447 // Reference: https://wg21.link/alg.move#:~:text=ranges::move_backward(R
1448 template <typename Range,
1449 typename BidirectionalIterator,
1450 typename = internal::range_category_t<Range>,
1451 typename = internal::iterator_category_t<BidirectionalIterator>>
move_backward(Range && range,BidirectionalIterator result)1452 constexpr auto move_backward(Range&& range, BidirectionalIterator result) {
1453 return ranges::move_backward(ranges::begin(range), ranges::end(range),
1454 result);
1455 }
1456
1457 // [alg.swap] Swap
1458 // Reference: https://wg21.link/alg.swap
1459
1460 // Let `M` be `min(last1 - first1, last2 - first2)`.
1461 //
1462 // Preconditions: The two ranges `[first1, last1)` and `[first2, last2)` do not
1463 // overlap. `*(first1 + n)` is swappable with `*(first2 + n)`.
1464 //
1465 // Effects: For each non-negative integer `n < M` performs
1466 // `swap(*(first1 + n), *(first2 + n))`
1467 //
1468 // Returns: `first2 + M`
1469 //
1470 // Complexity: Exactly `M` swaps.
1471 //
1472 // Reference: https://wg21.link/alg.swap#:~:text=ranges::swap_ranges(I1
1473 template <typename ForwardIterator1,
1474 typename ForwardIterator2,
1475 typename = internal::iterator_category_t<ForwardIterator1>,
1476 typename = internal::iterator_category_t<ForwardIterator2>>
swap_ranges(ForwardIterator1 first1,ForwardIterator1 last1,ForwardIterator2 first2,ForwardIterator2 last2)1477 constexpr auto swap_ranges(ForwardIterator1 first1,
1478 ForwardIterator1 last1,
1479 ForwardIterator2 first2,
1480 ForwardIterator2 last2) {
1481 // std::swap_ranges does not have a `last2` overload. Thus we need to
1482 // adjust `last1` to ensure to not read past `last2`.
1483 last1 = std::next(first1, std::min(std::distance(first1, last1),
1484 std::distance(first2, last2)));
1485 return std::swap_ranges(first1, last1, first2);
1486 }
1487
1488 // Let `M` be `min(size(range1), size(range2))`.
1489 //
1490 // Preconditions: The two ranges `range1` and `range2` do not overlap.
1491 // `*(begin(range1) + n)` is swappable with `*(begin(range2) + n)`.
1492 //
1493 // Effects: For each non-negative integer `n < M` performs
1494 // `swap(*(begin(range1) + n), *(begin(range2) + n))`
1495 //
1496 // Returns: `begin(range2) + M`
1497 //
1498 // Complexity: Exactly `M` swaps.
1499 //
1500 // Reference: https://wg21.link/alg.swap#:~:text=ranges::swap_ranges(R1
1501 template <typename Range1,
1502 typename Range2,
1503 typename = internal::range_category_t<Range1>,
1504 typename = internal::range_category_t<Range2>>
swap_ranges(Range1 && range1,Range2 && range2)1505 constexpr auto swap_ranges(Range1&& range1, Range2&& range2) {
1506 return ranges::swap_ranges(ranges::begin(range1), ranges::end(range1),
1507 ranges::begin(range2), ranges::end(range2));
1508 }
1509
1510 // [alg.transform] Transform
1511 // Reference: https://wg21.link/alg.transform
1512
1513 // Let `N` be `last1 - first1`,
1514 // `E(i)` be `invoke(op, invoke(proj, *(first1 + (i - result))))`.
1515 //
1516 // Preconditions: `op` does not invalidate iterators or subranges, nor modify
1517 // elements in the ranges `[first1, first1 + N]`, and `[result, result + N]`.
1518 //
1519 // Effects: Assigns through every iterator `i` in the range
1520 // `[result, result + N)` a new corresponding value equal to `E(i)`.
1521 //
1522 // Returns: `result + N`
1523 //
1524 // Complexity: Exactly `N` applications of `op` and any projections.
1525 //
1526 // Remarks: result may be equal to `first1`.
1527 //
1528 // Reference: https://wg21.link/alg.transform#:~:text=ranges::transform(I
1529 template <typename InputIterator,
1530 typename OutputIterator,
1531 typename UnaryOperation,
1532 typename Proj = identity,
1533 typename = internal::iterator_category_t<InputIterator>,
1534 typename = internal::iterator_category_t<OutputIterator>,
1535 typename = indirect_result_t<UnaryOperation&,
1536 projected<InputIterator, Proj>>>
1537 constexpr auto transform(InputIterator first1,
1538 InputIterator last1,
1539 OutputIterator result,
1540 UnaryOperation op,
1541 Proj proj = {}) {
1542 return std::transform(first1, last1, result, [&op, &proj](auto&& arg) {
1543 return base::invoke(op,
1544 base::invoke(proj, std::forward<decltype(arg)>(arg)));
1545 });
1546 }
1547
1548 // Let `N` be `size(range)`,
1549 // `E(i)` be `invoke(op, invoke(proj, *(begin(range) + (i - result))))`.
1550 //
1551 // Preconditions: `op` does not invalidate iterators or subranges, nor modify
1552 // elements in the ranges `[begin(range), end(range)]`, and
1553 // `[result, result + N]`.
1554 //
1555 // Effects: Assigns through every iterator `i` in the range
1556 // `[result, result + N)` a new corresponding value equal to `E(i)`.
1557 //
1558 // Returns: `result + N`
1559 //
1560 // Complexity: Exactly `N` applications of `op` and any projections.
1561 //
1562 // Remarks: result may be equal to `begin(range)`.
1563 //
1564 // Reference: https://wg21.link/alg.transform#:~:text=ranges::transform(R
1565 template <typename Range,
1566 typename OutputIterator,
1567 typename UnaryOperation,
1568 typename Proj = identity,
1569 typename = internal::range_category_t<Range>,
1570 typename = internal::iterator_category_t<OutputIterator>,
1571 typename = indirect_result_t<UnaryOperation&,
1572 projected<iterator_t<Range>, Proj>>>
1573 constexpr auto transform(Range&& range,
1574 OutputIterator result,
1575 UnaryOperation op,
1576 Proj proj = {}) {
1577 return ranges::transform(ranges::begin(range), ranges::end(range), result,
1578 std::move(op), std::move(proj));
1579 }
1580
1581 // Let:
1582 // `N` be `min(last1 - first1, last2 - first2)`,
1583 // `E(i)` be `invoke(binary_op, invoke(proj1, *(first1 + (i - result))),
1584 // invoke(proj2, *(first2 + (i - result))))`.
1585 //
1586 // Preconditions: `binary_op` does not invalidate iterators or subranges, nor
1587 // modify elements in the ranges `[first1, first1 + N]`, `[first2, first2 + N]`,
1588 // and `[result, result + N]`.
1589 //
1590 // Effects: Assigns through every iterator `i` in the range
1591 // `[result, result + N)` a new corresponding value equal to `E(i)`.
1592 //
1593 // Returns: `result + N`
1594 //
1595 // Complexity: Exactly `N` applications of `binary_op`, and any projections.
1596 //
1597 // Remarks: `result` may be equal to `first1` or `first2`.
1598 //
1599 // Reference: https://wg21.link/alg.transform#:~:text=ranges::transform(I1
1600 template <typename ForwardIterator1,
1601 typename ForwardIterator2,
1602 typename OutputIterator,
1603 typename BinaryOperation,
1604 typename Proj1 = identity,
1605 typename Proj2 = identity,
1606 typename = internal::iterator_category_t<ForwardIterator1>,
1607 typename = internal::iterator_category_t<ForwardIterator2>,
1608 typename = internal::iterator_category_t<OutputIterator>,
1609 typename = indirect_result_t<BinaryOperation&,
1610 projected<ForwardIterator1, Proj1>,
1611 projected<ForwardIterator2, Proj2>>>
1612 constexpr auto transform(ForwardIterator1 first1,
1613 ForwardIterator1 last1,
1614 ForwardIterator2 first2,
1615 ForwardIterator2 last2,
1616 OutputIterator result,
1617 BinaryOperation binary_op,
1618 Proj1 proj1 = {},
1619 Proj2 proj2 = {}) {
1620 // std::transform does not have a `last2` overload. Thus we need to adjust
1621 // `last1` to ensure to not read past `last2`.
1622 last1 = std::next(first1, std::min(std::distance(first1, last1),
1623 std::distance(first2, last2)));
1624 return std::transform(
1625 first1, last1, first2, result,
1626 [&binary_op, &proj1, &proj2](auto&& lhs, auto&& rhs) {
1627 return base::invoke(
1628 binary_op, base::invoke(proj1, std::forward<decltype(lhs)>(lhs)),
1629 base::invoke(proj2, std::forward<decltype(rhs)>(rhs)));
1630 });
1631 }
1632
1633 // Let:
1634 // `N` be `min(size(range1), size(range2)`,
1635 // `E(i)` be `invoke(binary_op, invoke(proj1, *(begin(range1) + (i - result))),
1636 // invoke(proj2, *(begin(range2) + (i - result))))`
1637 //
1638 // Preconditions: `binary_op` does not invalidate iterators or subranges, nor
1639 // modify elements in the ranges `[begin(range1), end(range1)]`,
1640 // `[begin(range2), end(range2)]`, and `[result, result + N]`.
1641 //
1642 // Effects: Assigns through every iterator `i` in the range
1643 // `[result, result + N)` a new corresponding value equal to `E(i)`.
1644 //
1645 // Returns: `result + N`
1646 //
1647 // Complexity: Exactly `N` applications of `binary_op`, and any projections.
1648 //
1649 // Remarks: `result` may be equal to `begin(range1)` or `begin(range2)`.
1650 //
1651 // Reference: https://wg21.link/alg.transform#:~:text=ranges::transform(R1
1652 template <typename Range1,
1653 typename Range2,
1654 typename OutputIterator,
1655 typename BinaryOperation,
1656 typename Proj1 = identity,
1657 typename Proj2 = identity,
1658 typename = internal::range_category_t<Range1>,
1659 typename = internal::range_category_t<Range2>,
1660 typename = internal::iterator_category_t<OutputIterator>,
1661 typename = indirect_result_t<BinaryOperation&,
1662 projected<iterator_t<Range1>, Proj1>,
1663 projected<iterator_t<Range2>, Proj2>>>
1664 constexpr auto transform(Range1&& range1,
1665 Range2&& range2,
1666 OutputIterator result,
1667 BinaryOperation binary_op,
1668 Proj1 proj1 = {},
1669 Proj2 proj2 = {}) {
1670 return ranges::transform(ranges::begin(range1), ranges::end(range1),
1671 ranges::begin(range2), ranges::end(range2), result,
1672 std::move(binary_op), std::move(proj1),
1673 std::move(proj2));
1674 }
1675
1676 // [alg.replace] Replace
1677 // Reference: https://wg21.link/alg.replace
1678
1679 // Let `E(i)` be `bool(invoke(proj, *i) == old_value)`.
1680 //
1681 // Mandates: `new_value` is writable to `first`.
1682 //
1683 // Effects: Substitutes elements referred by the iterator `i` in the range
1684 // `[first, last)` with `new_value`, when `E(i)` is true.
1685 //
1686 // Returns: `last`
1687 //
1688 // Complexity: Exactly `last - first` applications of the corresponding
1689 // predicate and any projection.
1690 //
1691 // Reference: https://wg21.link/alg.replace#:~:text=ranges::replace(I
1692 template <typename ForwardIterator,
1693 typename T,
1694 typename Proj = identity,
1695 typename = internal::iterator_category_t<ForwardIterator>>
1696 constexpr auto replace(ForwardIterator first,
1697 ForwardIterator last,
1698 const T& old_value,
1699 const T& new_value,
1700 Proj proj = {}) {
1701 // Note: In order to be able to apply `proj` to each element in [first, last)
1702 // we are dispatching to std::replace_if instead of std::replace.
1703 std::replace_if(
1704 first, last,
1705 [&proj, &old_value](auto&& lhs) {
1706 return base::invoke(proj, std::forward<decltype(lhs)>(lhs)) ==
1707 old_value;
1708 },
1709 new_value);
1710 return last;
1711 }
1712
1713 // Let `E(i)` be `bool(invoke(proj, *i) == old_value)`.
1714 //
1715 // Mandates: `new_value` is writable to `begin(range)`.
1716 //
1717 // Effects: Substitutes elements referred by the iterator `i` in `range` with
1718 // `new_value`, when `E(i)` is true.
1719 //
1720 // Returns: `end(range)`
1721 //
1722 // Complexity: Exactly `size(range)` applications of the corresponding predicate
1723 // and any projection.
1724 //
1725 // Reference: https://wg21.link/alg.replace#:~:text=ranges::replace(R
1726 template <typename Range,
1727 typename T,
1728 typename Proj = identity,
1729 typename = internal::range_category_t<Range>>
1730 constexpr auto replace(Range&& range,
1731 const T& old_value,
1732 const T& new_value,
1733 Proj proj = {}) {
1734 return ranges::replace(ranges::begin(range), ranges::end(range), old_value,
1735 new_value, std::move(proj));
1736 }
1737
1738 // Let `E(i)` be `bool(invoke(pred, invoke(proj, *i)))`.
1739 //
1740 // Mandates: `new_value` is writable to `first`.
1741 //
1742 // Effects: Substitutes elements referred by the iterator `i` in the range
1743 // `[first, last)` with `new_value`, when `E(i)` is true.
1744 //
1745 // Returns: `last`
1746 //
1747 // Complexity: Exactly `last - first` applications of the corresponding
1748 // predicate and any projection.
1749 //
1750 // Reference: https://wg21.link/alg.replace#:~:text=ranges::replace_if(I
1751 template <typename ForwardIterator,
1752 typename Predicate,
1753 typename T,
1754 typename Proj = identity,
1755 typename = internal::iterator_category_t<ForwardIterator>>
1756 constexpr auto replace_if(ForwardIterator first,
1757 ForwardIterator last,
1758 Predicate pred,
1759 const T& new_value,
1760 Proj proj = {}) {
1761 std::replace_if(first, last, internal::ProjectedUnaryPredicate(pred, proj),
1762 new_value);
1763 return last;
1764 }
1765
1766 // Let `E(i)` be `bool(invoke(pred, invoke(proj, *i)))`.
1767 //
1768 // Mandates: `new_value` is writable to `begin(range)`.
1769 //
1770 // Effects: Substitutes elements referred by the iterator `i` in `range` with
1771 // `new_value`, when `E(i)` is true.
1772 //
1773 // Returns: `end(range)`
1774 //
1775 // Complexity: Exactly `size(range)` applications of the corresponding predicate
1776 // and any projection.
1777 //
1778 // Reference: https://wg21.link/alg.replace#:~:text=ranges::replace_if(R
1779 template <typename Range,
1780 typename Predicate,
1781 typename T,
1782 typename Proj = identity,
1783 typename = internal::range_category_t<Range>>
1784 constexpr auto replace_if(Range&& range,
1785 Predicate pred,
1786 const T& new_value,
1787 Proj proj = {}) {
1788 return ranges::replace_if(ranges::begin(range), ranges::end(range),
1789 std::move(pred), new_value, std::move(proj));
1790 }
1791
1792 // Let `E(i)` be `bool(invoke(proj, *(first + (i - result))) == old_value)`.
1793 //
1794 // Mandates: The results of the expressions `*first` and `new_value` are
1795 // writable to `result`.
1796 //
1797 // Preconditions: The ranges `[first, last)` and `[result, result + (last -
1798 // first))` do not overlap.
1799 //
1800 // Effects: Assigns through every iterator `i` in the range `[result, result +
1801 // (last - first))` a new corresponding value, `new_value` if `E(i)` is true, or
1802 // `*(first + (i - result))` otherwise.
1803 //
1804 // Returns: `result + (last - first)`.
1805 //
1806 // Complexity: Exactly `last - first` applications of the corresponding
1807 // predicate and any projection.
1808 //
1809 // Reference: https://wg21.link/alg.replace#:~:text=ranges::replace_copy(I
1810 template <typename InputIterator,
1811 typename OutputIterator,
1812 typename T,
1813 typename Proj = identity,
1814 typename = internal::iterator_category_t<InputIterator>,
1815 typename = internal::iterator_category_t<OutputIterator>>
1816 constexpr auto replace_copy(InputIterator first,
1817 InputIterator last,
1818 OutputIterator result,
1819 const T& old_value,
1820 const T& new_value,
1821 Proj proj = {}) {
1822 // Note: In order to be able to apply `proj` to each element in [first, last)
1823 // we are dispatching to std::replace_copy_if instead of std::replace_copy.
1824 std::replace_copy_if(
1825 first, last, result,
1826 [&proj, &old_value](auto&& lhs) {
1827 return base::invoke(proj, std::forward<decltype(lhs)>(lhs)) ==
1828 old_value;
1829 },
1830 new_value);
1831 return last;
1832 }
1833
1834 // Let `E(i)` be
1835 // `bool(invoke(proj, *(begin(range) + (i - result))) == old_value)`.
1836 //
1837 // Mandates: The results of the expressions `*begin(range)` and `new_value` are
1838 // writable to `result`.
1839 //
1840 // Preconditions: The ranges `range` and `[result, result + size(range))` do not
1841 // overlap.
1842 //
1843 // Effects: Assigns through every iterator `i` in the range `[result, result +
1844 // size(range))` a new corresponding value, `new_value` if `E(i)` is true, or
1845 // `*(begin(range) + (i - result))` otherwise.
1846 //
1847 // Returns: `result + size(range)`.
1848 //
1849 // Complexity: Exactly `size(range)` applications of the corresponding
1850 // predicate and any projection.
1851 //
1852 // Reference: https://wg21.link/alg.replace#:~:text=ranges::replace_copy(R
1853 template <typename Range,
1854 typename OutputIterator,
1855 typename T,
1856 typename Proj = identity,
1857 typename = internal::range_category_t<Range>,
1858 typename = internal::iterator_category_t<OutputIterator>>
1859 constexpr auto replace_copy(Range&& range,
1860 OutputIterator result,
1861 const T& old_value,
1862 const T& new_value,
1863 Proj proj = {}) {
1864 return ranges::replace_copy(ranges::begin(range), ranges::end(range), result,
1865 old_value, new_value, std::move(proj));
1866 }
1867
1868 // Let `E(i)` be `bool(invoke(pred, invoke(proj, *(first + (i - result)))))`.
1869 //
1870 // Mandates: The results of the expressions `*first` and `new_value` are
1871 // writable to `result`.
1872 //
1873 // Preconditions: The ranges `[first, last)` and `[result, result + (last -
1874 // first))` do not overlap.
1875 //
1876 // Effects: Assigns through every iterator `i` in the range `[result, result +
1877 // (last - first))` a new corresponding value, `new_value` if `E(i)` is true, or
1878 // `*(first + (i - result))` otherwise.
1879 //
1880 // Returns: `result + (last - first)`.
1881 //
1882 // Complexity: Exactly `last - first` applications of the corresponding
1883 // predicate and any projection.
1884 //
1885 // Reference: https://wg21.link/alg.replace#:~:text=ranges::replace_copy_if(I
1886 template <typename InputIterator,
1887 typename OutputIterator,
1888 typename Predicate,
1889 typename T,
1890 typename Proj = identity,
1891 typename = internal::iterator_category_t<InputIterator>,
1892 typename = internal::iterator_category_t<OutputIterator>>
1893 constexpr auto replace_copy_if(InputIterator first,
1894 InputIterator last,
1895 OutputIterator result,
1896 Predicate pred,
1897 const T& new_value,
1898 Proj proj = {}) {
1899 return std::replace_copy_if(first, last, result,
1900 internal::ProjectedUnaryPredicate(pred, proj),
1901 new_value);
1902 }
1903
1904 // Let `E(i)` be
1905 // `bool(invoke(pred, invoke(proj, *(begin(range) + (i - result)))))`.
1906 //
1907 // Mandates: The results of the expressions `*begin(range)` and `new_value` are
1908 // writable to `result`.
1909 //
1910 // Preconditions: The ranges `range` and `[result, result + size(range))` do not
1911 // overlap.
1912 //
1913 // Effects: Assigns through every iterator `i` in the range `[result, result +
1914 // size(range))` a new corresponding value, `new_value` if `E(i)` is true, or
1915 // `*(begin(range) + (i - result))` otherwise.
1916 //
1917 // Returns: `result + size(range)`.
1918 //
1919 // Complexity: Exactly `size(range)` applications of the corresponding
1920 // predicate and any projection.
1921 //
1922 // Reference: https://wg21.link/alg.replace#:~:text=ranges::replace_copy_if(R
1923 template <typename Range,
1924 typename OutputIterator,
1925 typename Predicate,
1926 typename T,
1927 typename Proj = identity,
1928 typename = internal::range_category_t<Range>,
1929 typename = internal::iterator_category_t<OutputIterator>>
1930 constexpr auto replace_copy_if(Range&& range,
1931 OutputIterator result,
1932 Predicate pred,
1933 const T& new_value,
1934 Proj proj = {}) {
1935 return ranges::replace_copy_if(ranges::begin(range), ranges::end(range),
1936 result, pred, new_value, std::move(proj));
1937 }
1938
1939 // [alg.fill] Fill
1940 // Reference: https://wg21.link/alg.fill
1941
1942 // Let `N` be `last - first`.
1943 //
1944 // Mandates: The expression `value` is writable to the output iterator.
1945 //
1946 // Effects: Assigns `value` through all the iterators in the range
1947 // `[first, last)`.
1948 //
1949 // Returns: `last`.
1950 //
1951 // Complexity: Exactly `N` assignments.
1952 //
1953 // Reference: https://wg21.link/alg.fill#:~:text=ranges::fill(O
1954 template <typename OutputIterator,
1955 typename T,
1956 typename = internal::iterator_category_t<OutputIterator>>
fill(OutputIterator first,OutputIterator last,const T & value)1957 constexpr auto fill(OutputIterator first, OutputIterator last, const T& value) {
1958 std::fill(first, last, value);
1959 return last;
1960 }
1961
1962 // Let `N` be `size(range)`.
1963 //
1964 // Mandates: The expression `value` is writable to the output iterator.
1965 //
1966 // Effects: Assigns `value` through all the iterators in `range`.
1967 //
1968 // Returns: `end(range)`.
1969 //
1970 // Complexity: Exactly `N` assignments.
1971 //
1972 // Reference: https://wg21.link/alg.fill#:~:text=ranges::fill(R
1973 template <typename Range,
1974 typename T,
1975 typename = internal::range_category_t<Range>>
fill(Range && range,const T & value)1976 constexpr auto fill(Range&& range, const T& value) {
1977 return ranges::fill(ranges::begin(range), ranges::end(range), value);
1978 }
1979
1980 // Let `N` be `max(0, n)`.
1981 //
1982 // Mandates: The expression `value` is writable to the output iterator.
1983 // The type `Size` is convertible to an integral type.
1984 //
1985 // Effects: Assigns `value` through all the iterators in `[first, first + N)`.
1986 //
1987 // Returns: `first + N`.
1988 //
1989 // Complexity: Exactly `N` assignments.
1990 //
1991 // Reference: https://wg21.link/alg.fill#:~:text=ranges::fill_n(O
1992 template <typename OutputIterator,
1993 typename Size,
1994 typename T,
1995 typename = internal::iterator_category_t<OutputIterator>>
fill_n(OutputIterator first,Size n,const T & value)1996 constexpr auto fill_n(OutputIterator first, Size n, const T& value) {
1997 return std::fill_n(first, n, value);
1998 }
1999
2000 // [alg.generate] Generate
2001 // Reference: https://wg21.link/alg.generate
2002
2003 // Let `N` be `last - first`.
2004 //
2005 // Effects: Assigns the result of successive evaluations of gen() through each
2006 // iterator in the range `[first, last)`.
2007 //
2008 // Returns: `last`.
2009 //
2010 // Complexity: Exactly `N` evaluations of `gen()` and assignments.
2011 //
2012 // Reference: https://wg21.link/alg.generate#:~:text=ranges::generate(O
2013 template <typename OutputIterator,
2014 typename Generator,
2015 typename = internal::iterator_category_t<OutputIterator>>
generate(OutputIterator first,OutputIterator last,Generator gen)2016 constexpr auto generate(OutputIterator first,
2017 OutputIterator last,
2018 Generator gen) {
2019 std::generate(first, last, std::move(gen));
2020 return last;
2021 }
2022
2023 // Let `N` be `size(range)`.
2024 //
2025 // Effects: Assigns the result of successive evaluations of gen() through each
2026 // iterator in `range`.
2027 //
2028 // Returns: `end(range)`.
2029 //
2030 // Complexity: Exactly `N` evaluations of `gen()` and assignments.
2031 //
2032 // Reference: https://wg21.link/alg.generate#:~:text=ranges::generate(R
2033 template <typename Range,
2034 typename Generator,
2035 typename = internal::range_category_t<Range>>
generate(Range && range,Generator gen)2036 constexpr auto generate(Range&& range, Generator gen) {
2037 return ranges::generate(ranges::begin(range), ranges::end(range),
2038 std::move(gen));
2039 }
2040
2041 // Let `N` be `max(0, n)`.
2042 //
2043 // Mandates: `Size` is convertible to an integral type.
2044 //
2045 // Effects: Assigns the result of successive evaluations of gen() through each
2046 // iterator in the range `[first, first + N)`.
2047 //
2048 // Returns: `first + N`.
2049 //
2050 // Complexity: Exactly `N` evaluations of `gen()` and assignments.
2051 //
2052 // Reference: https://wg21.link/alg.generate#:~:text=ranges::generate_n(O
2053 template <typename OutputIterator,
2054 typename Size,
2055 typename Generator,
2056 typename = internal::iterator_category_t<OutputIterator>>
generate_n(OutputIterator first,Size n,Generator gen)2057 constexpr auto generate_n(OutputIterator first, Size n, Generator gen) {
2058 return std::generate_n(first, n, std::move(gen));
2059 }
2060
2061 // [alg.remove] Remove
2062 // Reference: https://wg21.link/alg.remove
2063
2064 // Let `E(i)` be `bool(invoke(proj, *i) == value)`.
2065 //
2066 // Effects: Eliminates all the elements referred to by iterator `i` in the range
2067 // `[first, last)` for which `E(i)` holds.
2068 //
2069 // Returns: The end of the resulting range.
2070 //
2071 // Remarks: Stable.
2072 //
2073 // Complexity: Exactly `last - first` applications of the corresponding
2074 // predicate and any projection.
2075 //
2076 // Reference: https://wg21.link/alg.remove#:~:text=ranges::remove(I
2077 template <typename ForwardIterator,
2078 typename T,
2079 typename Proj = identity,
2080 typename = internal::iterator_category_t<ForwardIterator>>
2081 constexpr auto remove(ForwardIterator first,
2082 ForwardIterator last,
2083 const T& value,
2084 Proj proj = {}) {
2085 // Note: In order to be able to apply `proj` to each element in [first, last)
2086 // we are dispatching to std::remove_if instead of std::remove.
2087 return std::remove_if(first, last, [&proj, &value](auto&& lhs) {
2088 return base::invoke(proj, std::forward<decltype(lhs)>(lhs)) == value;
2089 });
2090 }
2091
2092 // Let `E(i)` be `bool(invoke(proj, *i) == value)`.
2093 //
2094 // Effects: Eliminates all the elements referred to by iterator `i` in `range`
2095 // for which `E(i)` holds.
2096 //
2097 // Returns: The end of the resulting range.
2098 //
2099 // Remarks: Stable.
2100 //
2101 // Complexity: Exactly `size(range)` applications of the corresponding predicate
2102 // and any projection.
2103 //
2104 // Reference: https://wg21.link/alg.remove#:~:text=ranges::remove(R
2105 template <typename Range,
2106 typename T,
2107 typename Proj = identity,
2108 typename = internal::range_category_t<Range>>
2109 constexpr auto remove(Range&& range, const T& value, Proj proj = {}) {
2110 return ranges::remove(ranges::begin(range), ranges::end(range), value,
2111 std::move(proj));
2112 }
2113
2114 // Let `E(i)` be `bool(invoke(pred, invoke(proj, *i)))`.
2115 //
2116 // Effects: Eliminates all the elements referred to by iterator `i` in the range
2117 // `[first, last)` for which `E(i)` holds.
2118 //
2119 // Returns: The end of the resulting range.
2120 //
2121 // Remarks: Stable.
2122 //
2123 // Complexity: Exactly `last - first` applications of the corresponding
2124 // predicate and any projection.
2125 //
2126 // Reference: https://wg21.link/alg.remove#:~:text=ranges::remove_if(I
2127 template <typename ForwardIterator,
2128 typename Predicate,
2129 typename Proj = identity,
2130 typename = internal::iterator_category_t<ForwardIterator>>
2131 constexpr auto remove_if(ForwardIterator first,
2132 ForwardIterator last,
2133 Predicate pred,
2134 Proj proj = {}) {
2135 return std::remove_if(first, last,
2136 internal::ProjectedUnaryPredicate(pred, proj));
2137 }
2138
2139 // Let `E(i)` be `bool(invoke(pred, invoke(proj, *i)))`.
2140 //
2141 // Effects: Eliminates all the elements referred to by iterator `i` in `range`.
2142 //
2143 // Returns: The end of the resulting range.
2144 //
2145 // Remarks: Stable.
2146 //
2147 // Complexity: Exactly `size(range)` applications of the corresponding predicate
2148 // and any projection.
2149 //
2150 // Reference: https://wg21.link/alg.remove#:~:text=ranges::remove_if(R
2151 template <typename Range,
2152 typename Predicate,
2153 typename Proj = identity,
2154 typename = internal::range_category_t<Range>>
2155 constexpr auto remove_if(Range&& range, Predicate pred, Proj proj = {}) {
2156 return ranges::remove_if(ranges::begin(range), ranges::end(range),
2157 std::move(pred), std::move(proj));
2158 }
2159
2160 // Let `E(i)` be `bool(invoke(proj, *i) == value)`.
2161 //
2162 // Let `N` be the number of elements in `[first, last)` for which `E(i)` is
2163 // false.
2164 //
2165 // Mandates: `*first` is writable to `result`.
2166 //
2167 // Preconditions: The ranges `[first, last)` and `[result, result + (last -
2168 // first))` do not overlap.
2169 //
2170 // Effects: Copies all the elements referred to by the iterator `i` in the range
2171 // `[first, last)` for which `E(i)` is false.
2172 //
2173 // Returns: `result + N`.
2174 //
2175 // Complexity: Exactly `last - first` applications of the corresponding
2176 // predicate and any projection.
2177 //
2178 // Remarks: Stable.
2179 //
2180 // Reference: https://wg21.link/alg.remove#:~:text=ranges::remove_copy(I
2181 template <typename InputIterator,
2182 typename OutputIterator,
2183 typename T,
2184 typename Proj = identity,
2185 typename = internal::iterator_category_t<InputIterator>,
2186 typename = internal::iterator_category_t<OutputIterator>>
2187 constexpr auto remove_copy(InputIterator first,
2188 InputIterator last,
2189 OutputIterator result,
2190 const T& value,
2191 Proj proj = {}) {
2192 // Note: In order to be able to apply `proj` to each element in [first, last)
2193 // we are dispatching to std::remove_copy_if instead of std::remove_copy.
2194 return std::remove_copy_if(first, last, result, [&proj, &value](auto&& lhs) {
2195 return base::invoke(proj, std::forward<decltype(lhs)>(lhs)) == value;
2196 });
2197 }
2198
2199 // Let `E(i)` be `bool(invoke(proj, *i) == value)`.
2200 //
2201 // Let `N` be the number of elements in `range` for which `E(i)` is false.
2202 //
2203 // Mandates: `*begin(range)` is writable to `result`.
2204 //
2205 // Preconditions: The ranges `range` and `[result, result + size(range))` do not
2206 // overlap.
2207 //
2208 // Effects: Copies all the elements referred to by the iterator `i` in `range`
2209 // for which `E(i)` is false.
2210 //
2211 // Returns: `result + N`.
2212 //
2213 // Complexity: Exactly `size(range)` applications of the corresponding
2214 // predicate and any projection.
2215 //
2216 // Remarks: Stable.
2217 //
2218 // Reference: https://wg21.link/alg.remove#:~:text=ranges::remove_copy(R
2219 template <typename Range,
2220 typename OutputIterator,
2221 typename T,
2222 typename Proj = identity,
2223 typename = internal::range_category_t<Range>,
2224 typename = internal::iterator_category_t<OutputIterator>>
2225 constexpr auto remove_copy(Range&& range,
2226 OutputIterator result,
2227 const T& value,
2228 Proj proj = {}) {
2229 return ranges::remove_copy(ranges::begin(range), ranges::end(range), result,
2230 value, std::move(proj));
2231 }
2232
2233 // Let `E(i)` be `bool(invoke(pred, invoke(proj, *i)))`.
2234 //
2235 // Let `N` be the number of elements in `[first, last)` for which `E(i)` is
2236 // false.
2237 //
2238 // Mandates: `*first` is writable to `result`.
2239 //
2240 // Preconditions: The ranges `[first, last)` and `[result, result + (last -
2241 // first))` do not overlap.
2242 //
2243 // Effects: Copies all the elements referred to by the iterator `i` in the range
2244 // `[first, last)` for which `E(i)` is false.
2245 //
2246 // Returns: `result + N`.
2247 //
2248 // Complexity: Exactly `last - first` applications of the corresponding
2249 // predicate and any projection.
2250 //
2251 // Remarks: Stable.
2252 //
2253 // Reference: https://wg21.link/alg.remove#:~:text=ranges::remove_copy_if(I
2254 template <typename InputIterator,
2255 typename OutputIterator,
2256 typename Pred,
2257 typename Proj = identity,
2258 typename = internal::iterator_category_t<InputIterator>,
2259 typename = internal::iterator_category_t<OutputIterator>>
2260 constexpr auto remove_copy_if(InputIterator first,
2261 InputIterator last,
2262 OutputIterator result,
2263 Pred pred,
2264 Proj proj = {}) {
2265 return std::remove_copy_if(first, last, result,
2266 internal::ProjectedUnaryPredicate(pred, proj));
2267 }
2268
2269 // Let `E(i)` be `bool(invoke(pred, invoke(proj, *i)))`.
2270 //
2271 // Let `N` be the number of elements in `range` for which `E(i)` is false.
2272 //
2273 // Mandates: `*begin(range)` is writable to `result`.
2274 //
2275 // Preconditions: The ranges `range` and `[result, result + size(range))` do not
2276 // overlap.
2277 //
2278 // Effects: Copies all the elements referred to by the iterator `i` in `range`
2279 // for which `E(i)` is false.
2280 //
2281 // Returns: `result + N`.
2282 //
2283 // Complexity: Exactly `size(range)` applications of the corresponding
2284 // predicate and any projection.
2285 //
2286 // Remarks: Stable.
2287 //
2288 // Reference: https://wg21.link/alg.remove#:~:text=ranges::remove_copy(R
2289 template <typename Range,
2290 typename OutputIterator,
2291 typename Pred,
2292 typename Proj = identity,
2293 typename = internal::range_category_t<Range>,
2294 typename = internal::iterator_category_t<OutputIterator>>
2295 constexpr auto remove_copy_if(Range&& range,
2296 OutputIterator result,
2297 Pred pred,
2298 Proj proj = {}) {
2299 return ranges::remove_copy_if(ranges::begin(range), ranges::end(range),
2300 result, std::move(pred), std::move(proj));
2301 }
2302
2303 // [alg.unique] Unique
2304 // Reference: https://wg21.link/alg.unique
2305
2306 // Let `E(i)` be `bool(invoke(comp, invoke(proj, *(i - 1)), invoke(proj, *i)))`.
2307 //
2308 // Effects: For a nonempty range, eliminates all but the first element from
2309 // every consecutive group of equivalent elements referred to by the iterator
2310 // `i` in the range `[first + 1, last)` for which `E(i)` is true.
2311 //
2312 // Returns: The end of the resulting range.
2313 //
2314 // Complexity: For nonempty ranges, exactly `(last - first) - 1` applications of
2315 // the corresponding predicate and no more than twice as many applications of
2316 // any projection.
2317 //
2318 // Reference: https://wg21.link/alg.unique#:~:text=ranges::unique(I
2319 template <typename ForwardIterator,
2320 typename Comp = ranges::equal_to,
2321 typename Proj = identity,
2322 typename = internal::iterator_category_t<ForwardIterator>,
2323 typename = indirect_result_t<Comp&,
2324 projected<ForwardIterator, Proj>,
2325 projected<ForwardIterator, Proj>>>
2326 constexpr auto unique(ForwardIterator first,
2327 ForwardIterator last,
2328 Comp comp = {},
2329 Proj proj = {}) {
2330 return std::unique(first, last,
2331 internal::ProjectedBinaryPredicate(comp, proj, proj));
2332 }
2333
2334 // Let `E(i)` be `bool(invoke(comp, invoke(proj, *(i - 1)), invoke(proj, *i)))`.
2335 //
2336 // Effects: For a nonempty range, eliminates all but the first element from
2337 // every consecutive group of equivalent elements referred to by the iterator
2338 // `i` in the range `[begin(range) + 1, end(range))` for which `E(i)` is true.
2339 //
2340 // Returns: The end of the resulting range.
2341 //
2342 // Complexity: For nonempty ranges, exactly `size(range) - 1` applications of
2343 // the corresponding predicate and no more than twice as many applications of
2344 // any projection.
2345 //
2346 // Reference: https://wg21.link/alg.unique#:~:text=ranges::unique(R
2347 template <typename Range,
2348 typename Comp = ranges::equal_to,
2349 typename Proj = identity,
2350 typename = internal::range_category_t<Range>,
2351 typename = indirect_result_t<Comp&,
2352 projected<iterator_t<Range>, Proj>,
2353 projected<iterator_t<Range>, Proj>>>
2354 constexpr auto unique(Range&& range, Comp comp = {}, Proj proj = {}) {
2355 return ranges::unique(ranges::begin(range), ranges::end(range),
2356 std::move(comp), std::move(proj));
2357 }
2358
2359 // Let `E(i)` be `bool(invoke(comp, invoke(proj, *i), invoke(proj, *(i - 1))))`.
2360 //
2361 // Mandates: `*first` is writable to `result`.
2362 //
2363 // Preconditions: The ranges `[first, last)` and
2364 // `[result, result + (last - first))` do not overlap.
2365 //
2366 // Effects: Copies only the first element from every consecutive group of equal
2367 // elements referred to by the iterator `i` in the range `[first, last)` for
2368 // which `E(i)` holds.
2369 //
2370 // Returns: `result + N`.
2371 //
2372 // Complexity: Exactly `last - first - 1` applications of the corresponding
2373 // predicate and no more than twice as many applications of any projection.
2374 //
2375 // Reference: https://wg21.link/alg.unique#:~:text=ranges::unique_copy(I
2376 template <typename ForwardIterator,
2377 typename OutputIterator,
2378 typename Comp = ranges::equal_to,
2379 typename Proj = identity,
2380 typename = internal::iterator_category_t<ForwardIterator>,
2381 typename = internal::iterator_category_t<OutputIterator>>
2382 constexpr auto unique_copy(ForwardIterator first,
2383 ForwardIterator last,
2384 OutputIterator result,
2385 Comp comp = {},
2386 Proj proj = {}) {
2387 return std::unique_copy(first, last, result,
2388 internal::ProjectedBinaryPredicate(comp, proj, proj));
2389 }
2390
2391 // Let `E(i)` be `bool(invoke(comp, invoke(proj, *i), invoke(proj, *(i - 1))))`.
2392 //
2393 // Mandates: `*begin(range)` is writable to `result`.
2394 //
2395 // Preconditions: The ranges `range` and `[result, result + size(range))` do not
2396 // overlap.
2397 //
2398 // Effects: Copies only the first element from every consecutive group of equal
2399 // elements referred to by the iterator `i` in `range` for which `E(i)` holds.
2400 //
2401 // Returns: `result + N`.
2402 //
2403 // Complexity: Exactly `size(range) - 1` applications of the corresponding
2404 // predicate and no more than twice as many applications of any projection.
2405 //
2406 // Reference: https://wg21.link/alg.unique#:~:text=ranges::unique_copy(R
2407 template <typename Range,
2408 typename OutputIterator,
2409 typename Comp = ranges::equal_to,
2410 typename Proj = identity,
2411 typename = internal::range_category_t<Range>,
2412 typename = internal::iterator_category_t<OutputIterator>>
2413 constexpr auto unique_copy(Range&& range,
2414 OutputIterator result,
2415 Comp comp = {},
2416 Proj proj = {}) {
2417 return ranges::unique_copy(ranges::begin(range), ranges::end(range), result,
2418 std::move(comp), std::move(proj));
2419 }
2420
2421 // [alg.reverse] Reverse
2422 // Reference: https://wg21.link/alg.reverse
2423
2424 // Effects: For each non-negative integer `i < (last - first) / 2`, applies
2425 // `std::iter_swap` to all pairs of iterators `first + i, (last - i) - 1`.
2426 //
2427 // Returns: `last`.
2428 //
2429 // Complexity: Exactly `(last - first)/2` swaps.
2430 //
2431 // Reference: https://wg21.link/alg.reverse#:~:text=ranges::reverse(I
2432 template <typename BidirectionalIterator,
2433 typename = internal::iterator_category_t<BidirectionalIterator>>
reverse(BidirectionalIterator first,BidirectionalIterator last)2434 constexpr auto reverse(BidirectionalIterator first,
2435 BidirectionalIterator last) {
2436 std::reverse(first, last);
2437 return last;
2438 }
2439
2440 // Effects: For each non-negative integer `i < size(range) / 2`, applies
2441 // `std::iter_swap` to all pairs of iterators
2442 // `begin(range) + i, (end(range) - i) - 1`.
2443 //
2444 // Returns: `end(range)`.
2445 //
2446 // Complexity: Exactly `size(range)/2` swaps.
2447 //
2448 // Reference: https://wg21.link/alg.reverse#:~:text=ranges::reverse(R
2449 template <typename Range, typename = internal::range_category_t<Range>>
reverse(Range && range)2450 constexpr auto reverse(Range&& range) {
2451 return ranges::reverse(ranges::begin(range), ranges::end(range));
2452 }
2453
2454 // Let `N` be `last - first`.
2455 //
2456 // Preconditions: The ranges `[first, last)` and `[result, result + N)` do not
2457 // overlap.
2458 //
2459 // Effects: Copies the range `[first, last)` to the range `[result, result + N)`
2460 // such that for every non-negative integer `i < N` the following assignment
2461 // takes place: `*(result + N - 1 - i) = *(first + i)`.
2462 //
2463 // Returns: `result + N`.
2464 //
2465 // Complexity: Exactly `N` assignments.
2466 //
2467 // Reference: https://wg21.link/alg.reverse#:~:text=ranges::reverse_copy(I
2468 template <typename BidirectionalIterator,
2469 typename OutputIterator,
2470 typename = internal::iterator_category_t<BidirectionalIterator>,
2471 typename = internal::iterator_category_t<OutputIterator>>
reverse_copy(BidirectionalIterator first,BidirectionalIterator last,OutputIterator result)2472 constexpr auto reverse_copy(BidirectionalIterator first,
2473 BidirectionalIterator last,
2474 OutputIterator result) {
2475 return std::reverse_copy(first, last, result);
2476 }
2477
2478 // Let `N` be `size(range)`.
2479 //
2480 // Preconditions: The ranges `range` and `[result, result + N)` do not
2481 // overlap.
2482 //
2483 // Effects: Copies `range` to the range `[result, result + N)` such that for
2484 // every non-negative integer `i < N` the following assignment takes place:
2485 // `*(result + N - 1 - i) = *(begin(range) + i)`.
2486 //
2487 // Returns: `result + N`.
2488 //
2489 // Complexity: Exactly `N` assignments.
2490 //
2491 // Reference: https://wg21.link/alg.reverse#:~:text=ranges::reverse_copy(R
2492 template <typename Range,
2493 typename OutputIterator,
2494 typename = internal::range_category_t<Range>,
2495 typename = internal::iterator_category_t<OutputIterator>>
reverse_copy(Range && range,OutputIterator result)2496 constexpr auto reverse_copy(Range&& range, OutputIterator result) {
2497 return ranges::reverse_copy(ranges::begin(range), ranges::end(range), result);
2498 }
2499
2500 // [alg.rotate] Rotate
2501 // Reference: https://wg21.link/alg.rotate
2502
2503 // Preconditions: `[first, middle)` and `[middle, last)` are valid ranges.
2504 //
2505 // Effects: For each non-negative integer `i < (last - first)`, places the
2506 // element from the position `first + i` into position
2507 // `first + (i + (last - middle)) % (last - first)`.
2508 //
2509 // Returns: `first + (last - middle)`.
2510 //
2511 // Complexity: At most `last - first` swaps.
2512 //
2513 // Reference: https://wg21.link/alg.rotate#:~:text=ranges::rotate(I
2514 template <typename ForwardIterator,
2515 typename = internal::iterator_category_t<ForwardIterator>>
rotate(ForwardIterator first,ForwardIterator middle,ForwardIterator last)2516 constexpr auto rotate(ForwardIterator first,
2517 ForwardIterator middle,
2518 ForwardIterator last) {
2519 return std::rotate(first, middle, last);
2520 }
2521
2522 // Preconditions: `[begin(range), middle)` and `[middle, end(range))` are valid
2523 // ranges.
2524 //
2525 // Effects: For each non-negative integer `i < size(range)`, places the element
2526 // from the position `begin(range) + i` into position
2527 // `begin(range) + (i + (end(range) - middle)) % size(range)`.
2528 //
2529 // Returns: `begin(range) + (end(range) - middle)`.
2530 //
2531 // Complexity: At most `size(range)` swaps.
2532 //
2533 // Reference: https://wg21.link/alg.rotate#:~:text=ranges::rotate(R
2534 template <typename Range, typename = internal::range_category_t<Range>>
rotate(Range && range,iterator_t<Range> middle)2535 constexpr auto rotate(Range&& range, iterator_t<Range> middle) {
2536 return ranges::rotate(ranges::begin(range), middle, ranges::end(range));
2537 }
2538
2539 // Let `N` be `last - first`.
2540 //
2541 // Preconditions: `[first, middle)` and `[middle, last)` are valid ranges. The
2542 // ranges `[first, last)` and `[result, result + N)` do not overlap.
2543 //
2544 // Effects: Copies the range `[first, last)` to the range `[result, result + N)`
2545 // such that for each non-negative integer `i < N` the following assignment
2546 // takes place: `*(result + i) = *(first + (i + (middle - first)) % N)`.
2547 //
2548 // Returns: `result + N`.
2549 //
2550 // Complexity: Exactly `N` assignments.
2551 //
2552 // Reference: https://wg21.link/alg.rotate#:~:text=ranges::rotate_copy(I
2553 template <typename ForwardIterator,
2554 typename OutputIterator,
2555 typename = internal::iterator_category_t<ForwardIterator>,
2556 typename = internal::iterator_category_t<OutputIterator>>
rotate_copy(ForwardIterator first,ForwardIterator middle,ForwardIterator last,OutputIterator result)2557 constexpr auto rotate_copy(ForwardIterator first,
2558 ForwardIterator middle,
2559 ForwardIterator last,
2560 OutputIterator result) {
2561 return std::rotate_copy(first, middle, last, result);
2562 }
2563
2564 // Let `N` be `size(range)`.
2565 //
2566 // Preconditions: `[begin(range), middle)` and `[middle, end(range))` are valid
2567 // ranges. The ranges `range` and `[result, result + N)` do not overlap.
2568 //
2569 // Effects: Copies `range` to the range `[result, result + N)` such that for
2570 // each non-negative integer `i < N` the following assignment takes place:
2571 // `*(result + i) = *(begin(range) + (i + (middle - begin(range))) % N)`.
2572 //
2573 // Returns: `result + N`.
2574 //
2575 // Complexity: Exactly `N` assignments.
2576 //
2577 // Reference: https://wg21.link/alg.rotate#:~:text=ranges::rotate_copy(R
2578 template <typename Range,
2579 typename OutputIterator,
2580 typename = internal::range_category_t<Range>,
2581 typename = internal::iterator_category_t<OutputIterator>>
rotate_copy(Range && range,iterator_t<Range> middle,OutputIterator result)2582 constexpr auto rotate_copy(Range&& range,
2583 iterator_t<Range> middle,
2584 OutputIterator result) {
2585 return ranges::rotate_copy(ranges::begin(range), middle, ranges::end(range),
2586 result);
2587 }
2588
2589 // [alg.random.sample] Sample
2590 // Reference: https://wg21.link/alg.random.sample
2591
2592 // Currently not implemented due to lack of std::sample in C++14.
2593 // TODO(crbug.com/1071094): Consider implementing a hand-rolled version.
2594
2595 // [alg.random.shuffle] Shuffle
2596 // Reference: https://wg21.link/alg.random.shuffle
2597
2598 // Preconditions: The type `std::remove_reference_t<UniformRandomBitGenerator>`
2599 // meets the uniform random bit generator requirements.
2600 //
2601 // Effects: Permutes the elements in the range `[first, last)` such that each
2602 // possible permutation of those elements has equal probability of appearance.
2603 //
2604 // Returns: `last`.
2605 //
2606 // Complexity: Exactly `(last - first) - 1` swaps.
2607 //
2608 // Remarks: To the extent that the implementation of this function makes use of
2609 // random numbers, the object referenced by g shall serve as the
2610 // implementation's source of randomness.
2611 //
2612 // Reference: https://wg21.link/alg.random.shuffle#:~:text=ranges::shuffle(I
2613 template <typename RandomAccessIterator,
2614 typename UniformRandomBitGenerator,
2615 typename = internal::iterator_category_t<RandomAccessIterator>>
shuffle(RandomAccessIterator first,RandomAccessIterator last,UniformRandomBitGenerator && g)2616 constexpr auto shuffle(RandomAccessIterator first,
2617 RandomAccessIterator last,
2618 UniformRandomBitGenerator&& g) {
2619 std::shuffle(first, last, std::forward<UniformRandomBitGenerator>(g));
2620 return last;
2621 }
2622
2623 // Preconditions: The type `std::remove_reference_t<UniformRandomBitGenerator>`
2624 // meets the uniform random bit generator requirements.
2625 //
2626 // Effects: Permutes the elements in `range` such that each possible permutation
2627 // of those elements has equal probability of appearance.
2628 //
2629 // Returns: `end(range)`.
2630 //
2631 // Complexity: Exactly `size(range) - 1` swaps.
2632 //
2633 // Remarks: To the extent that the implementation of this function makes use of
2634 // random numbers, the object referenced by g shall serve as the
2635 // implementation's source of randomness.
2636 //
2637 // Reference: https://wg21.link/alg.random.shuffle#:~:text=ranges::shuffle(R
2638 template <typename Range,
2639 typename UniformRandomBitGenerator,
2640 typename = internal::range_category_t<Range>>
shuffle(Range && range,UniformRandomBitGenerator && g)2641 constexpr auto shuffle(Range&& range, UniformRandomBitGenerator&& g) {
2642 return ranges::shuffle(ranges::begin(range), ranges::end(range),
2643 std::forward<UniformRandomBitGenerator>(g));
2644 }
2645
2646 // [alg.nonmodifying] Sorting and related operations
2647 // Reference: https://wg21.link/alg.sorting
2648
2649 // [alg.sort] Sorting
2650 // Reference: https://wg21.link/alg.sort
2651
2652 // [sort] sort
2653 // Reference: https://wg21.link/sort
2654
2655 // Effects: Sorts the elements in the range `[first, last)` with respect to
2656 // `comp` and `proj`.
2657 //
2658 // Returns: `last`.
2659 //
2660 // Complexity: Let `N` be `last - first`. `O(N log N)` comparisons and
2661 // projections.
2662 //
2663 // Reference: https://wg21.link/sort#:~:text=ranges::sort(I
2664 template <typename RandomAccessIterator,
2665 typename Comp = ranges::less,
2666 typename Proj = identity,
2667 typename = internal::iterator_category_t<RandomAccessIterator>,
2668 typename = indirect_result_t<Comp&,
2669 projected<RandomAccessIterator, Proj>,
2670 projected<RandomAccessIterator, Proj>>>
2671 constexpr auto sort(RandomAccessIterator first,
2672 RandomAccessIterator last,
2673 Comp comp = {},
2674 Proj proj = {}) {
2675 std::sort(first, last, internal::ProjectedBinaryPredicate(comp, proj, proj));
2676 return last;
2677 }
2678
2679 // Effects: Sorts the elements in `range` with respect to `comp` and `proj`.
2680 //
2681 // Returns: `end(range)`.
2682 //
2683 // Complexity: Let `N` be `size(range)`. `O(N log N)` comparisons and
2684 // projections.
2685 //
2686 // Reference: https://wg21.link/sort#:~:text=ranges::sort(R
2687 template <typename Range,
2688 typename Comp = ranges::less,
2689 typename Proj = identity,
2690 typename = internal::range_category_t<Range>,
2691 typename = indirect_result_t<Comp&,
2692 projected<iterator_t<Range>, Proj>,
2693 projected<iterator_t<Range>, Proj>>>
2694 constexpr auto sort(Range&& range, Comp comp = {}, Proj proj = {}) {
2695 return ranges::sort(ranges::begin(range), ranges::end(range), std::move(comp),
2696 std::move(proj));
2697 }
2698
2699 // [stable.sort] stable_sort
2700 // Reference: https://wg21.link/stable.sort
2701
2702 // Effects: Sorts the elements in the range `[first, last)` with respect to
2703 // `comp` and `proj`.
2704 //
2705 // Returns: `last`.
2706 //
2707 // Complexity: Let `N` be `last - first`. If enough extra memory is available,
2708 // `N log (N)` comparisons. Otherwise, at most `N log^2 (N)` comparisons. In
2709 // either case, twice as many projections as the number of comparisons.
2710 //
2711 // Remarks: Stable.
2712 //
2713 // Reference: https://wg21.link/stable.sort#:~:text=ranges::stable_sort(I
2714 template <typename RandomAccessIterator,
2715 typename Comp = ranges::less,
2716 typename Proj = identity,
2717 typename = internal::iterator_category_t<RandomAccessIterator>,
2718 typename = indirect_result_t<Comp&,
2719 projected<RandomAccessIterator, Proj>,
2720 projected<RandomAccessIterator, Proj>>>
2721 constexpr auto stable_sort(RandomAccessIterator first,
2722 RandomAccessIterator last,
2723 Comp comp = {},
2724 Proj proj = {}) {
2725 std::stable_sort(first, last,
2726 internal::ProjectedBinaryPredicate(comp, proj, proj));
2727 return last;
2728 }
2729
2730 // Effects: Sorts the elements in `range` with respect to `comp` and `proj`.
2731 //
2732 // Returns: `end(rang)`.
2733 //
2734 // Complexity: Let `N` be `size(range)`. If enough extra memory is available,
2735 // `N log (N)` comparisons. Otherwise, at most `N log^2 (N)` comparisons. In
2736 // either case, twice as many projections as the number of comparisons.
2737 //
2738 // Remarks: Stable.
2739 //
2740 // Reference: https://wg21.link/stable.sort#:~:text=ranges::stable_sort(R
2741 template <typename Range,
2742 typename Comp = ranges::less,
2743 typename Proj = identity,
2744 typename = internal::range_category_t<Range>,
2745 typename = indirect_result_t<Comp&,
2746 projected<iterator_t<Range>, Proj>,
2747 projected<iterator_t<Range>, Proj>>>
2748 constexpr auto stable_sort(Range&& range, Comp comp = {}, Proj proj = {}) {
2749 return ranges::stable_sort(ranges::begin(range), ranges::end(range),
2750 std::move(comp), std::move(proj));
2751 }
2752
2753 // [partial.sort] partial_sort
2754 // Reference: https://wg21.link/partial.sort
2755
2756 // Preconditions: `[first, middle)` and `[middle, last)` are valid ranges.
2757 //
2758 // Effects: Places the first `middle - first` elements from the range
2759 // `[first, last)` as sorted with respect to `comp` and `proj` into the range
2760 // `[first, middle)`. The rest of the elements in the range `[middle, last)` are
2761 // placed in an unspecified order.
2762 //
2763 // Returns: `last`.
2764 //
2765 // Complexity: Approximately `(last - first) * log(middle - first)` comparisons,
2766 // and twice as many projections.
2767 //
2768 // Reference: https://wg21.link/partial.sort#:~:text=ranges::partial_sort(I
2769 template <typename RandomAccessIterator,
2770 typename Comp = ranges::less,
2771 typename Proj = identity,
2772 typename = internal::iterator_category_t<RandomAccessIterator>,
2773 typename = indirect_result_t<Comp&,
2774 projected<RandomAccessIterator, Proj>,
2775 projected<RandomAccessIterator, Proj>>>
2776 constexpr auto partial_sort(RandomAccessIterator first,
2777 RandomAccessIterator middle,
2778 RandomAccessIterator last,
2779 Comp comp = {},
2780 Proj proj = {}) {
2781 std::partial_sort(first, middle, last,
2782 internal::ProjectedBinaryPredicate(comp, proj, proj));
2783 return last;
2784 }
2785
2786 // Preconditions: `[begin(range), middle)` and `[middle, end(range))` are valid
2787 // ranges.
2788 //
2789 // Effects: Places the first `middle - begin(range)` elements from `range` as
2790 // sorted with respect to `comp` and `proj` into the range
2791 // `[begin(range), middle)`. The rest of the elements in the range
2792 // `[middle, end(range))` are placed in an unspecified order.
2793 //
2794 // Returns: `end(range)`.
2795 //
2796 // Complexity: Approximately `size(range) * log(middle - begin(range))`
2797 // comparisons, and twice as many projections.
2798 //
2799 // Reference: https://wg21.link/partial.sort#:~:text=ranges::partial_sort(R
2800 template <typename Range,
2801 typename Comp = ranges::less,
2802 typename Proj = identity,
2803 typename = internal::range_category_t<Range>,
2804 typename = indirect_result_t<Comp&,
2805 projected<iterator_t<Range>, Proj>,
2806 projected<iterator_t<Range>, Proj>>>
2807 constexpr auto partial_sort(Range&& range,
2808 iterator_t<Range> middle,
2809 Comp comp = {},
2810 Proj proj = {}) {
2811 return ranges::partial_sort(ranges::begin(range), middle, ranges::end(range),
2812 std::move(comp), std::move(proj));
2813 }
2814
2815 // [partial.sort.copy] partial_sort_copy
2816 // Reference: https://wg21.link/partial.sort.copy
2817
2818 // Let `N` be `min(last - first, result_last - result_first)`.
2819 //
2820 // Preconditions: For iterators `a1` and `b1` in `[first, last)`, and iterators
2821 // `x2` and `y2` in `[result_first, result_last)`, after evaluating the
2822 // assignment `*y2 = *b1`, let `E` be the value of `bool(invoke(comp,
2823 // invoke(proj1, *a1), invoke(proj2, *y2)))`. Then, after evaluating the
2824 // assignment `*x2 = *a1`, `E` is equal to `bool(invoke(comp, invoke(proj2,
2825 // *x2), invoke(proj2, *y2)))`.
2826 //
2827 // Effects: Places the first `N` elements as sorted with respect to `comp` and
2828 // `proj2` into the range `[result_first, result_first + N)`.
2829 //
2830 // Returns: `result_first + N`.
2831 //
2832 // Complexity: Approximately `(last - first) * log N` comparisons, and twice as
2833 // many projections.
2834 //
2835 // Reference:
2836 // https://wg21.link/partial.sort.copy#:~:text=ranges::partial_sort_copy(I1
2837 template <typename InputIterator,
2838 typename RandomAccessIterator,
2839 typename Comp = ranges::less,
2840 typename Proj1 = identity,
2841 typename Proj2 = identity,
2842 typename = internal::iterator_category_t<InputIterator>,
2843 typename = internal::iterator_category_t<RandomAccessIterator>,
2844 typename = indirect_result_t<Comp&,
2845 projected<InputIterator, Proj1>,
2846 projected<RandomAccessIterator, Proj2>>,
2847 typename = indirect_result_t<Comp&,
2848 projected<RandomAccessIterator, Proj2>,
2849 projected<InputIterator, Proj1>>>
2850 constexpr auto partial_sort_copy(InputIterator first,
2851 InputIterator last,
2852 RandomAccessIterator result_first,
2853 RandomAccessIterator result_last,
2854 Comp comp = {},
2855 Proj1 proj1 = {},
2856 Proj2 proj2 = {}) {
2857 // Needs to opt-in to all permutations, since std::partial_sort_copy expects
2858 // comp(proj2(lhs), proj1(rhs)) to compile.
2859 return std::partial_sort_copy(
2860 first, last, result_first, result_last,
2861 internal::PermutedProjectedBinaryPredicate(comp, proj1, proj2));
2862 }
2863
2864 // Let `N` be `min(size(range), size(result_range))`.
2865 //
2866 // Preconditions: For iterators `a1` and `b1` in `range`, and iterators
2867 // `x2` and `y2` in `result_range`, after evaluating the assignment
2868 // `*y2 = *b1`, let `E` be the value of
2869 // `bool(invoke(comp, invoke(proj1, *a1), invoke(proj2, *y2)))`. Then, after
2870 // evaluating the assignment `*x2 = *a1`, `E` is equal to
2871 // `bool(invoke(comp, invoke(proj2, *x2), invoke(proj2, *y2)))`.
2872 //
2873 // Effects: Places the first `N` elements as sorted with respect to `comp` and
2874 // `proj2` into the range `[begin(result_range), begin(result_range) + N)`.
2875 //
2876 // Returns: `begin(result_range) + N`.
2877 //
2878 // Complexity: Approximately `size(range) * log N` comparisons, and twice as
2879 // many projections.
2880 //
2881 // Reference:
2882 // https://wg21.link/partial.sort.copy#:~:text=ranges::partial_sort_copy(R1
2883 template <typename Range1,
2884 typename Range2,
2885 typename Comp = ranges::less,
2886 typename Proj1 = identity,
2887 typename Proj2 = identity,
2888 typename = internal::range_category_t<Range1>,
2889 typename = internal::range_category_t<Range2>,
2890 typename = indirect_result_t<Comp&,
2891 projected<iterator_t<Range1>, Proj1>,
2892 projected<iterator_t<Range2>, Proj2>>,
2893 typename = indirect_result_t<Comp&,
2894 projected<iterator_t<Range2>, Proj2>,
2895 projected<iterator_t<Range1>, Proj1>>>
2896 constexpr auto partial_sort_copy(Range1&& range,
2897 Range2&& result_range,
2898 Comp comp = {},
2899 Proj1 proj1 = {},
2900 Proj2 proj2 = {}) {
2901 return ranges::partial_sort_copy(ranges::begin(range), ranges::end(range),
2902 ranges::begin(result_range),
2903 ranges::end(result_range), std::move(comp),
2904 std::move(proj1), std::move(proj2));
2905 }
2906
2907 // [is.sorted] is_sorted
2908 // Reference: https://wg21.link/is.sorted
2909
2910 // Returns: The last iterator `i` in `[first, last]` for which the range
2911 // `[first, i)` is sorted with respect to `comp` and `proj`.
2912 //
2913 // Complexity: Linear.
2914 //
2915 // Reference: https://wg21.link/is.sorted#:~:text=ranges::is_sorted_until(I
2916 template <typename ForwardIterator,
2917 typename Comp = ranges::less,
2918 typename Proj = identity,
2919 typename = internal::iterator_category_t<ForwardIterator>,
2920 typename = indirect_result_t<Comp&,
2921 projected<ForwardIterator, Proj>,
2922 projected<ForwardIterator, Proj>>>
2923 constexpr auto is_sorted_until(ForwardIterator first,
2924 ForwardIterator last,
2925 Comp comp = {},
2926 Proj proj = {}) {
2927 // Implementation inspired by cppreference.com:
2928 // https://en.cppreference.com/w/cpp/algorithm/is_sorted_until
2929 //
2930 // A reimplementation is required, because std::is_sorted_until is not
2931 // constexpr prior to C++20. Once we have C++20, we should switch to standard
2932 // library implementation.
2933 if (first == last)
2934 return last;
2935
2936 for (ForwardIterator next = first; ++next != last; ++first) {
2937 if (base::invoke(comp, base::invoke(proj, *next),
2938 base::invoke(proj, *first))) {
2939 return next;
2940 }
2941 }
2942
2943 return last;
2944 }
2945
2946 // Returns: The last iterator `i` in `[begin(range), end(range)]` for which the
2947 // range `[begin(range), i)` is sorted with respect to `comp` and `proj`.
2948 //
2949 // Complexity: Linear.
2950 //
2951 // Reference: https://wg21.link/is.sorted#:~:text=ranges::is_sorted_until(R
2952 template <typename Range,
2953 typename Comp = ranges::less,
2954 typename Proj = identity,
2955 typename = internal::range_category_t<Range>,
2956 typename = indirect_result_t<Comp&,
2957 projected<iterator_t<Range>, Proj>,
2958 projected<iterator_t<Range>, Proj>>>
2959 constexpr auto is_sorted_until(Range&& range, Comp comp = {}, Proj proj = {}) {
2960 return ranges::is_sorted_until(ranges::begin(range), ranges::end(range),
2961 std::move(comp), std::move(proj));
2962 }
2963
2964 // Returns: Whether the range `[first, last)` is sorted with respect to `comp`
2965 // and `proj`.
2966 //
2967 // Complexity: Linear.
2968 //
2969 // Reference: https://wg21.link/is.sorted#:~:text=ranges::is_sorted(I
2970 template <typename ForwardIterator,
2971 typename Comp = ranges::less,
2972 typename Proj = identity,
2973 typename = internal::iterator_category_t<ForwardIterator>,
2974 typename = indirect_result_t<Comp&,
2975 projected<ForwardIterator, Proj>,
2976 projected<ForwardIterator, Proj>>>
2977 constexpr auto is_sorted(ForwardIterator first,
2978 ForwardIterator last,
2979 Comp comp = {},
2980 Proj proj = {}) {
2981 return ranges::is_sorted_until(first, last, std::move(comp),
2982 std::move(proj)) == last;
2983 }
2984
2985 // Returns: Whether `range` is sorted with respect to `comp` and `proj`.
2986 //
2987 // Complexity: Linear.
2988 //
2989 // Reference: https://wg21.link/is.sorted#:~:text=ranges::is_sorted(R
2990 template <typename Range,
2991 typename Comp = ranges::less,
2992 typename Proj = identity,
2993 typename = internal::range_category_t<Range>,
2994 typename = indirect_result_t<Comp&,
2995 projected<iterator_t<Range>, Proj>,
2996 projected<iterator_t<Range>, Proj>>>
2997 constexpr auto is_sorted(Range&& range, Comp comp = {}, Proj proj = {}) {
2998 return ranges::is_sorted(ranges::begin(range), ranges::end(range),
2999 std::move(comp), std::move(proj));
3000 }
3001
3002 // [alg.nth.element] Nth element
3003 // Reference: https://wg21.link/alg.nth.element
3004
3005 // Preconditions: `[first, nth)` and `[nth, last)` are valid ranges.
3006 //
3007 // Effects: After `nth_element` the element in the position pointed to by `nth`
3008 // is the element that would be in that position if the whole range were sorted
3009 // with respect to `comp` and `proj`, unless `nth == last`. Also for every
3010 // iterator `i` in the range `[first, nth)` and every iterator `j` in the range
3011 // `[nth, last)` it holds that:
3012 // `bool(invoke(comp, invoke(proj, *j), invoke(proj, *i)))` is false.
3013 //
3014 // Returns: `last`.
3015 //
3016 // Complexity: Linear on average.
3017 //
3018 // Reference: https://wg21.link/alg.nth.element#:~:text=ranges::nth_element(I
3019 template <typename RandomAccessIterator,
3020 typename Comp = ranges::less,
3021 typename Proj = identity,
3022 typename = internal::iterator_category_t<RandomAccessIterator>,
3023 typename = indirect_result_t<Comp&,
3024 projected<RandomAccessIterator, Proj>,
3025 projected<RandomAccessIterator, Proj>>>
3026 constexpr auto nth_element(RandomAccessIterator first,
3027 RandomAccessIterator nth,
3028 RandomAccessIterator last,
3029 Comp comp = {},
3030 Proj proj = {}) {
3031 std::nth_element(first, nth, last,
3032 internal::ProjectedBinaryPredicate(comp, proj, proj));
3033 return last;
3034 }
3035
3036 // Preconditions: `[begin(range), nth)` and `[nth, end(range))` are valid
3037 // ranges.
3038 //
3039 // Effects: After `nth_element` the element in the position pointed to by `nth`
3040 // is the element that would be in that position if the whole range were sorted
3041 // with respect to `comp` and `proj`, unless `nth == end(range)`. Also for every
3042 // iterator `i` in the range `[begin(range), nth)` and every iterator `j` in the
3043 // range `[nth, end(range))` it holds that:
3044 // `bool(invoke(comp, invoke(proj, *j), invoke(proj, *i)))` is false.
3045 //
3046 // Returns: `end(range)`.
3047 //
3048 // Complexity: Linear on average.
3049 //
3050 // Reference: https://wg21.link/alg.nth.element#:~:text=ranges::nth_element(R
3051 template <typename Range,
3052 typename Comp = ranges::less,
3053 typename Proj = identity,
3054 typename = internal::range_category_t<Range>,
3055 typename = indirect_result_t<Comp&,
3056 projected<iterator_t<Range>, Proj>,
3057 projected<iterator_t<Range>, Proj>>>
3058 constexpr auto nth_element(Range&& range,
3059 iterator_t<Range> nth,
3060 Comp comp = {},
3061 Proj proj = {}) {
3062 return ranges::nth_element(ranges::begin(range), nth, ranges::end(range),
3063 std::move(comp), std::move(proj));
3064 }
3065
3066 // [alg.binary.search] Binary search
3067 // Reference: https://wg21.link/alg.binary.search
3068
3069 // [lower.bound] lower_bound
3070 // Reference: https://wg21.link/lower.bound
3071
3072 // Preconditions: The elements `e` of `[first, last)` are partitioned with
3073 // respect to the expression `bool(invoke(comp, invoke(proj, e), value))`.
3074 //
3075 // Returns: The furthermost iterator `i` in the range `[first, last]` such that
3076 // for every iterator `j` in the range `[first, i)`,
3077 // `bool(invoke(comp, invoke(proj, *j), value))` is true.
3078 //
3079 // Complexity: At most `log_2(last - first) + O(1)` comparisons and projections.
3080 //
3081 // Reference: https://wg21.link/lower.bound#:~:text=ranges::lower_bound(I
3082 template <typename ForwardIterator,
3083 typename T,
3084 typename Comp = ranges::less,
3085 typename Proj = identity,
3086 typename = internal::iterator_category_t<ForwardIterator>>
3087 constexpr auto lower_bound(ForwardIterator first,
3088 ForwardIterator last,
3089 const T& value,
3090 Comp comp = {},
3091 Proj proj = {}) {
3092 // The second arg is guaranteed to be `value`, so we'll simply apply the
3093 // identity projection.
3094 identity value_proj;
3095 return std::lower_bound(
3096 first, last, value,
3097 internal::ProjectedBinaryPredicate(comp, proj, value_proj));
3098 }
3099
3100 // Preconditions: The elements `e` of `range` are partitioned with respect to
3101 // the expression `bool(invoke(comp, invoke(proj, e), value))`.
3102 //
3103 // Returns: The furthermost iterator `i` in the range
3104 // `[begin(range), end(range)]` such that for every iterator `j` in the range
3105 // `[begin(range), i)`, `bool(invoke(comp, invoke(proj, *j), value))` is true.
3106 //
3107 // Complexity: At most `log_2(size(range)) + O(1)` comparisons and projections.
3108 //
3109 // Reference: https://wg21.link/lower.bound#:~:text=ranges::lower_bound(R
3110 template <typename Range,
3111 typename T,
3112 typename Comp = ranges::less,
3113 typename Proj = identity,
3114 typename = internal::range_category_t<Range>>
3115 constexpr auto lower_bound(Range&& range,
3116 const T& value,
3117 Comp comp = {},
3118 Proj proj = {}) {
3119 return ranges::lower_bound(ranges::begin(range), ranges::end(range), value,
3120 std::move(comp), std::move(proj));
3121 }
3122
3123 // [upper.bound] upper_bound
3124 // Reference: https://wg21.link/upper.bound
3125
3126 // Preconditions: The elements `e` of `[first, last)` are partitioned with
3127 // respect to the expression `!bool(invoke(comp, value, invoke(proj, e)))`.
3128 //
3129 // Returns: The furthermost iterator `i` in the range `[first, last]` such that
3130 // for every iterator `j` in the range `[first, i)`,
3131 // `!bool(invoke(comp, value, invoke(proj, *j)))` is true.
3132 //
3133 // Complexity: At most `log_2(last - first) + O(1)` comparisons and projections.
3134 //
3135 // Reference: https://wg21.link/upper.bound#:~:text=ranges::upper_bound(I
3136 template <typename ForwardIterator,
3137 typename T,
3138 typename Comp = ranges::less,
3139 typename Proj = identity,
3140 typename = internal::iterator_category_t<ForwardIterator>>
3141 constexpr auto upper_bound(ForwardIterator first,
3142 ForwardIterator last,
3143 const T& value,
3144 Comp comp = {},
3145 Proj proj = {}) {
3146 // The first arg is guaranteed to be `value`, so we'll simply apply the
3147 // identity projection.
3148 identity value_proj;
3149 return std::upper_bound(
3150 first, last, value,
3151 internal::ProjectedBinaryPredicate(comp, value_proj, proj));
3152 }
3153
3154 // Preconditions: The elements `e` of `range` are partitioned with
3155 // respect to the expression `!bool(invoke(comp, value, invoke(proj, e)))`.
3156 //
3157 // Returns: The furthermost iterator `i` in the range
3158 // `[begin(range), end(range)]` such that for every iterator `j` in the range
3159 // `[begin(range), i)`, `!bool(invoke(comp, value, invoke(proj, *j)))` is true.
3160 //
3161 // Complexity: At most `log_2(size(range)) + O(1)` comparisons and projections.
3162 //
3163 // Reference: https://wg21.link/upper.bound#:~:text=ranges::upper_bound(R
3164 template <typename Range,
3165 typename T,
3166 typename Comp = ranges::less,
3167 typename Proj = identity,
3168 typename = internal::range_category_t<Range>>
3169 constexpr auto upper_bound(Range&& range,
3170 const T& value,
3171 Comp comp = {},
3172 Proj proj = {}) {
3173 return ranges::upper_bound(ranges::begin(range), ranges::end(range), value,
3174 std::move(comp), std::move(proj));
3175 }
3176
3177 // [equal.range] equal_range
3178 // Reference: https://wg21.link/equal.range
3179
3180 // Preconditions: The elements `e` of `[first, last)` are partitioned with
3181 // respect to the expressions `bool(invoke(comp, invoke(proj, e), value))` and
3182 // `!bool(invoke(comp, value, invoke(proj, e)))`.
3183 //
3184 // Returns: `{ranges::lower_bound(first, last, value, comp, proj),
3185 // ranges::upper_bound(first, last, value, comp, proj)}`.
3186 //
3187 // Complexity: At most 2 ∗ log_2(last - first) + O(1) comparisons and
3188 // projections.
3189 //
3190 // Reference: https://wg21.link/equal.range#:~:text=ranges::equal_range(I
3191 template <typename ForwardIterator,
3192 typename T,
3193 typename Comp = ranges::less,
3194 typename Proj = identity,
3195 typename = internal::iterator_category_t<ForwardIterator>>
3196 constexpr auto equal_range(ForwardIterator first,
3197 ForwardIterator last,
3198 const T& value,
3199 Comp comp = {},
3200 Proj proj = {}) {
3201 // Note: This does not dispatch to std::equal_range, as otherwise it would not
3202 // be possible to prevent applying `proj` to `value`, which can result in
3203 // unintended behavior.
3204 return std::make_pair(ranges::lower_bound(first, last, value, comp, proj),
3205 ranges::upper_bound(first, last, value, comp, proj));
3206 }
3207
3208 // Preconditions: The elements `e` of `range` are partitioned with
3209 // respect to the expressions `bool(invoke(comp, invoke(proj, e), value))` and
3210 // `!bool(invoke(comp, value, invoke(proj, e)))`.
3211 //
3212 // Returns: `{ranges::lower_bound(range, value, comp, proj),
3213 // ranges::upper_bound(range, value, comp, proj)}`.
3214 //
3215 // Complexity: At most 2 ∗ log_2(size(range)) + O(1) comparisons and
3216 // projections.
3217 //
3218 // Reference: https://wg21.link/equal.range#:~:text=ranges::equal_range(R
3219 template <typename Range,
3220 typename T,
3221 typename Comp = ranges::less,
3222 typename Proj = identity,
3223 typename = internal::range_category_t<Range>>
3224 constexpr auto equal_range(Range&& range,
3225 const T& value,
3226 Comp comp = {},
3227 Proj proj = {}) {
3228 return ranges::equal_range(ranges::begin(range), ranges::end(range), value,
3229 std::move(comp), std::move(proj));
3230 }
3231
3232 // [binary.search] binary_search
3233 // Reference: https://wg21.link/binary.search
3234
3235 // Preconditions: The elements `e` of `[first, last)` are partitioned with
3236 // respect to the expressions `bool(invoke(comp, invoke(proj, e), value))` and
3237 // `!bool(invoke(comp, value, invoke(proj, e)))`.
3238 //
3239 // Returns: `true` if and only if for some iterator `i` in the range
3240 // `[first, last)`, `!bool(invoke(comp, invoke(proj, *i), value)) &&
3241 // !bool(invoke(comp, value, invoke(proj, *i)))` is true.
3242 //
3243 // Complexity: At most `log_2(last - first) + O(1)` comparisons and projections.
3244 //
3245 // Reference: https://wg21.link/binary.search#:~:text=ranges::binary_search(I
3246 template <typename ForwardIterator,
3247 typename T,
3248 typename Comp = ranges::less,
3249 typename Proj = identity,
3250 typename = internal::iterator_category_t<ForwardIterator>>
3251 constexpr auto binary_search(ForwardIterator first,
3252 ForwardIterator last,
3253 const T& value,
3254 Comp comp = {},
3255 Proj proj = {}) {
3256 first = ranges::lower_bound(first, last, value, comp, proj);
3257 return first != last &&
3258 !base::invoke(comp, value, base::invoke(proj, *first));
3259 }
3260
3261 // Preconditions: The elements `e` of `range` are partitioned with
3262 // respect to the expressions `bool(invoke(comp, invoke(proj, e), value))` and
3263 // `!bool(invoke(comp, value, invoke(proj, e)))`.
3264 //
3265 // Returns: `true` if and only if for some iterator `i` in `range`
3266 // `!bool(invoke(comp, invoke(proj, *i), value)) &&
3267 // !bool(invoke(comp, value, invoke(proj, *i)))` is true.
3268 //
3269 // Complexity: At most `log_2(size(range)) + O(1)` comparisons and projections.
3270 //
3271 // Reference: https://wg21.link/binary.search#:~:text=ranges::binary_search(R
3272 template <typename Range,
3273 typename T,
3274 typename Comp = ranges::less,
3275 typename Proj = identity,
3276 typename = internal::range_category_t<Range>>
3277 constexpr auto binary_search(Range&& range,
3278 const T& value,
3279 Comp comp = {},
3280 Proj proj = {}) {
3281 return ranges::binary_search(ranges::begin(range), ranges::end(range), value,
3282 std::move(comp), std::move(proj));
3283 }
3284
3285 // [alg.partitions] Partitions
3286 // Reference: https://wg21.link/alg.partitions
3287
3288 // Returns: `true` if and only if the elements `e` of `[first, last)` are
3289 // partitioned with respect to the expression
3290 // `bool(invoke(pred, invoke(proj, e)))`.
3291 //
3292 // Complexity: Linear. At most `last - first` applications of `pred` and `proj`.
3293 //
3294 // Reference: https://wg21.link/alg.partitions#:~:text=ranges::is_partitioned(I
3295 template <typename ForwardIterator,
3296 typename Pred,
3297 typename Proj = identity,
3298 typename = internal::iterator_category_t<ForwardIterator>>
3299 constexpr auto is_partitioned(ForwardIterator first,
3300 ForwardIterator last,
3301 Pred pred,
3302 Proj proj = {}) {
3303 return std::is_partitioned(first, last,
3304 internal::ProjectedUnaryPredicate(pred, proj));
3305 }
3306
3307 // Returns: `true` if and only if the elements `e` of `range` are partitioned
3308 // with respect to the expression `bool(invoke(pred, invoke(proj, e)))`.
3309 //
3310 // Complexity: Linear. At most `size(range)` applications of `pred` and `proj`.
3311 //
3312 // Reference: https://wg21.link/alg.partitions#:~:text=ranges::is_partitioned(R
3313 template <typename Range,
3314 typename Pred,
3315 typename Proj = identity,
3316 typename = internal::range_category_t<Range>>
3317 constexpr auto is_partitioned(Range&& range, Pred pred, Proj proj = {}) {
3318 return ranges::is_partitioned(ranges::begin(range), ranges::end(range),
3319 std::move(pred), std::move(proj));
3320 }
3321
3322 // Let `E(x)` be `bool(invoke(pred, invoke(proj, x)))`.
3323 //
3324 // Effects: Places all the elements `e` in `[first, last)` that satisfy `E(e)`
3325 // before all the elements that do not.
3326 //
3327 // Returns: Let `i` be an iterator such that `E(*j)` is `true` for every
3328 // iterator `j` in `[first, i)` and `false` for every iterator `j` in
3329 // `[i, last)`. Returns: i.
3330 //
3331 // Complexity: Let `N = last - first`:
3332 // Exactly `N` applications of the predicate and projection. At most `N / 2`
3333 // swaps if the type of `first` models `bidirectional_iterator`, and at most `N`
3334 // swaps otherwise.
3335 //
3336 // Reference: https://wg21.link/alg.partitions#:~:text=ranges::partition(I
3337 template <typename ForwardIterator,
3338 typename Pred,
3339 typename Proj = identity,
3340 typename = internal::iterator_category_t<ForwardIterator>>
3341 constexpr auto partition(ForwardIterator first,
3342 ForwardIterator last,
3343 Pred pred,
3344 Proj proj = {}) {
3345 return std::partition(first, last,
3346 internal::ProjectedUnaryPredicate(pred, proj));
3347 }
3348
3349 // Let `E(x)` be `bool(invoke(pred, invoke(proj, x)))`.
3350 //
3351 // Effects: Places all the elements `e` in `range` that satisfy `E(e)` before
3352 // all the elements that do not.
3353 //
3354 // Returns: Let `i` be an iterator such that `E(*j)` is `true` for every
3355 // iterator `j` in `[begin(range), i)` and `false` for every iterator `j` in
3356 // `[i, last)`. Returns: i.
3357 //
3358 // Complexity: Let `N = size(range)`:
3359 // Exactly `N` applications of the predicate and projection. At most `N / 2`
3360 // swaps if the type of `first` models `bidirectional_iterator`, and at most `N`
3361 // swaps otherwise.
3362 //
3363 // Reference: https://wg21.link/alg.partitions#:~:text=ranges::partition(R
3364 template <typename Range,
3365 typename Pred,
3366 typename Proj = identity,
3367 typename = internal::range_category_t<Range>>
3368 constexpr auto partition(Range&& range, Pred pred, Proj proj = {}) {
3369 return ranges::partition(ranges::begin(range), ranges::end(range),
3370 std::move(pred), std::move(proj));
3371 }
3372
3373 // Let `E(x)` be `bool(invoke(pred, invoke(proj, x)))`.
3374 //
3375 // Effects: Places all the elements `e` in `[first, last)` that satisfy `E(e)`
3376 // before all the elements that do not. The relative order of the elements in
3377 // both groups is preserved.
3378 //
3379 // Returns: Let `i` be an iterator such that for every iterator `j` in
3380 // `[first, i)`, `E(*j)` is `true`, and for every iterator `j` in the range
3381 // `[i, last)`, `E(*j)` is `false`. Returns: `i`.
3382 //
3383 // Complexity: Let `N = last - first`:
3384 // At most `N log N` swaps, but only `O(N)` swaps if there is enough extra
3385 // memory. Exactly `N` applications of the predicate and projection.
3386 //
3387 // Reference:
3388 // https://wg21.link/alg.partitions#:~:text=ranges::stable_partition(I
3389 template <typename BidirectionalIterator,
3390 typename Pred,
3391 typename Proj = identity,
3392 typename = internal::iterator_category_t<BidirectionalIterator>>
3393 constexpr auto stable_partition(BidirectionalIterator first,
3394 BidirectionalIterator last,
3395 Pred pred,
3396 Proj proj = {}) {
3397 return std::stable_partition(first, last,
3398 internal::ProjectedUnaryPredicate(pred, proj));
3399 }
3400
3401 // Let `E(x)` be `bool(invoke(pred, invoke(proj, x)))`.
3402 //
3403 // Effects: Places all the elements `e` in `range` that satisfy `E(e)` before
3404 // all the elements that do not. The relative order of the elements in both
3405 // groups is preserved.
3406 //
3407 // Returns: Let `i` be an iterator such that for every iterator `j` in
3408 // `[begin(range), i)`, `E(*j)` is `true`, and for every iterator `j` in the
3409 // range `[i, end(range))`, `E(*j)` is `false`. Returns: `i`.
3410 //
3411 // Complexity: Let `N = size(range)`:
3412 // At most `N log N` swaps, but only `O(N)` swaps if there is enough extra
3413 // memory. Exactly `N` applications of the predicate and projection.
3414 //
3415 // Reference:
3416 // https://wg21.link/alg.partitions#:~:text=ranges::stable_partition(R
3417 template <typename Range,
3418 typename Pred,
3419 typename Proj = identity,
3420 typename = internal::range_category_t<Range>>
3421 constexpr auto stable_partition(Range&& range, Pred pred, Proj proj = {}) {
3422 return ranges::stable_partition(ranges::begin(range), ranges::end(range),
3423 std::move(pred), std::move(proj));
3424 }
3425
3426 // Let `E(x)` be `bool(invoke(pred, invoke(proj, x)))`.
3427 //
3428 // Mandates: The expression `*first` is writable to `out_true` and `out_false`.
3429 //
3430 // Preconditions: The input range and output ranges do not overlap.
3431 //
3432 // Effects: For each iterator `i` in `[first, last)`, copies `*i` to the output
3433 // range beginning with `out_true` if `E(*i)` is `true`, or to the output range
3434 // beginning with `out_false` otherwise.
3435 //
3436 // Returns: Let `o1` be the end of the output range beginning at `out_true`, and
3437 // `o2` the end of the output range beginning at `out_false`.
3438 // Returns `{o1, o2}`.
3439 //
3440 // Complexity: Exactly `last - first` applications of `pred` and `proj`.
3441 //
3442 // Reference: https://wg21.link/alg.partitions#:~:text=ranges::partition_copy(I
3443 template <typename InputIterator,
3444 typename OutputIterator1,
3445 typename OutputIterator2,
3446 typename Pred,
3447 typename Proj = identity,
3448 typename = internal::iterator_category_t<InputIterator>,
3449 typename = internal::iterator_category_t<OutputIterator1>,
3450 typename = internal::iterator_category_t<OutputIterator2>>
3451 constexpr auto partition_copy(InputIterator first,
3452 InputIterator last,
3453 OutputIterator1 out_true,
3454 OutputIterator2 out_false,
3455 Pred pred,
3456 Proj proj = {}) {
3457 return std::partition_copy(first, last, out_true, out_false,
3458 internal::ProjectedUnaryPredicate(pred, proj));
3459 }
3460
3461 // Let `E(x)` be `bool(invoke(pred, invoke(proj, x)))`.
3462 //
3463 // Mandates: The expression `*begin(range)` is writable to `out_true` and
3464 // `out_false`.
3465 //
3466 // Preconditions: The input range and output ranges do not overlap.
3467 //
3468 // Effects: For each iterator `i` in `range`, copies `*i` to the output range
3469 // beginning with `out_true` if `E(*i)` is `true`, or to the output range
3470 // beginning with `out_false` otherwise.
3471 //
3472 // Returns: Let `o1` be the end of the output range beginning at `out_true`, and
3473 // `o2` the end of the output range beginning at `out_false`.
3474 // Returns `{o1, o2}`.
3475 //
3476 // Complexity: Exactly `size(range)` applications of `pred` and `proj`.
3477 //
3478 // Reference: https://wg21.link/alg.partitions#:~:text=ranges::partition_copy(R
3479 template <typename Range,
3480 typename OutputIterator1,
3481 typename OutputIterator2,
3482 typename Pred,
3483 typename Proj = identity,
3484 typename = internal::range_category_t<Range>,
3485 typename = internal::iterator_category_t<OutputIterator1>,
3486 typename = internal::iterator_category_t<OutputIterator2>>
3487 constexpr auto partition_copy(Range&& range,
3488 OutputIterator1 out_true,
3489 OutputIterator2 out_false,
3490 Pred pred,
3491 Proj proj = {}) {
3492 return ranges::partition_copy(ranges::begin(range), ranges::end(range),
3493 out_true, out_false, std::move(pred),
3494 std::move(proj));
3495 }
3496
3497 // let `E(x)` be `bool(invoke(pred, invoke(proj, x)))`.
3498 //
3499 // Preconditions: The elements `e` of `[first, last)` are partitioned with
3500 // respect to `E(e)`.
3501 //
3502 // Returns: An iterator `mid` such that `E(*i)` is `true` for all iterators `i`
3503 // in `[first, mid)`, and `false` for all iterators `i` in `[mid, last)`.
3504 //
3505 // Complexity: `O(log(last - first))` applications of `pred` and `proj`.
3506 //
3507 // Reference: https://wg21.link/alg.partitions#:~:text=ranges::partition_point(I
3508 template <typename ForwardIterator,
3509 typename Pred,
3510 typename Proj = identity,
3511 typename = internal::iterator_category_t<ForwardIterator>>
3512 constexpr auto partition_point(ForwardIterator first,
3513 ForwardIterator last,
3514 Pred pred,
3515 Proj proj = {}) {
3516 return std::partition_point(first, last,
3517 internal::ProjectedUnaryPredicate(pred, proj));
3518 }
3519
3520 // let `E(x)` be `bool(invoke(pred, invoke(proj, x)))`.
3521 //
3522 // Preconditions: The elements `e` of `range` are partitioned with respect to
3523 // `E(e)`.
3524 //
3525 // Returns: An iterator `mid` such that `E(*i)` is `true` for all iterators `i`
3526 // in `[begin(range), mid)`, and `false` for all iterators `i` in
3527 // `[mid, end(range))`.
3528 //
3529 // Complexity: `O(log(size(range)))` applications of `pred` and `proj`.
3530 //
3531 // Reference: https://wg21.link/alg.partitions#:~:text=ranges::partition_point(R
3532 template <typename Range,
3533 typename Pred,
3534 typename Proj = identity,
3535 typename = internal::range_category_t<Range>>
3536 constexpr auto partition_point(Range&& range, Pred pred, Proj proj = {}) {
3537 return ranges::partition_point(ranges::begin(range), ranges::end(range),
3538 std::move(pred), std::move(proj));
3539 }
3540
3541 // [alg.merge] Merge
3542 // Reference: https://wg21.link/alg.merge
3543
3544 // Let `N` be `(last1 - first1) + (last2 - first2)`.
3545 //
3546 // Preconditions: The ranges `[first1, last1)` and `[first2, last2)` are sorted
3547 // with respect to `comp` and `proj1` or `proj2`, respectively. The resulting
3548 // range does not overlap with either of the original ranges.
3549 //
3550 // Effects: Copies all the elements of the two ranges `[first1, last1)` and
3551 // `[first2, last2)` into the range `[result, result_last)`, where `result_last`
3552 // is `result + N`. If an element `a` precedes `b` in an input range, `a` is
3553 // copied into the output range before `b`. If `e1` is an element of
3554 // `[first1, last1)` and `e2` of `[first2, last2)`, `e2` is copied into the
3555 // output range before `e1` if and only if
3556 // `bool(invoke(comp, invoke(proj2, e2), invoke(proj1, e1)))` is `true`.
3557 //
3558 // Returns: `result_last`.
3559 //
3560 // Complexity: At most `N - 1` comparisons and applications of each projection.
3561 //
3562 // Remarks: Stable.
3563 //
3564 // Reference: https://wg21.link/alg.merge#:~:text=ranges::merge(I1
3565 template <typename InputIterator1,
3566 typename InputIterator2,
3567 typename OutputIterator,
3568 typename Comp = ranges::less,
3569 typename Proj1 = identity,
3570 typename Proj2 = identity,
3571 typename = internal::iterator_category_t<InputIterator1>,
3572 typename = internal::iterator_category_t<InputIterator2>,
3573 typename = internal::iterator_category_t<OutputIterator>,
3574 typename = indirect_result_t<Comp&,
3575 projected<InputIterator1, Proj1>,
3576 projected<InputIterator2, Proj2>>,
3577 typename = indirect_result_t<Comp&,
3578 projected<InputIterator2, Proj2>,
3579 projected<InputIterator1, Proj1>>>
3580 constexpr auto merge(InputIterator1 first1,
3581 InputIterator1 last1,
3582 InputIterator2 first2,
3583 InputIterator2 last2,
3584 OutputIterator result,
3585 Comp comp = {},
3586 Proj1 proj1 = {},
3587 Proj2 proj2 = {}) {
3588 // Needs to opt-in to all permutations, since std::merge expects
3589 // comp(proj2(lhs), proj1(rhs)) to compile.
3590 return std::merge(
3591 first1, last1, first2, last2, result,
3592 internal::PermutedProjectedBinaryPredicate(comp, proj1, proj2));
3593 }
3594
3595 // Let `N` be `size(range1) + size(range2)`.
3596 //
3597 // Preconditions: The ranges `range1` and `range2` are sorted with respect to
3598 // `comp` and `proj1` or `proj2`, respectively. The resulting range does not
3599 // overlap with either of the original ranges.
3600 //
3601 // Effects: Copies all the elements of the two ranges `range1` and `range2` into
3602 // the range `[result, result_last)`, where `result_last` is `result + N`. If an
3603 // element `a` precedes `b` in an input range, `a` is copied into the output
3604 // range before `b`. If `e1` is an element of `range1` and `e2` of `range2`,
3605 // `e2` is copied into the output range before `e1` if and only if
3606 // `bool(invoke(comp, invoke(proj2, e2), invoke(proj1, e1)))` is `true`.
3607 //
3608 // Returns: `result_last`.
3609 //
3610 // Complexity: At most `N - 1` comparisons and applications of each projection.
3611 //
3612 // Remarks: Stable.
3613 //
3614 // Reference: https://wg21.link/alg.merge#:~:text=ranges::merge(R1
3615 template <typename Range1,
3616 typename Range2,
3617 typename OutputIterator,
3618 typename Comp = ranges::less,
3619 typename Proj1 = identity,
3620 typename Proj2 = identity,
3621 typename = internal::range_category_t<Range1>,
3622 typename = internal::range_category_t<Range2>,
3623 typename = internal::iterator_category_t<OutputIterator>,
3624 typename = indirect_result_t<Comp&,
3625 projected<iterator_t<Range1>, Proj1>,
3626 projected<iterator_t<Range2>, Proj2>>,
3627 typename = indirect_result_t<Comp&,
3628 projected<iterator_t<Range2>, Proj2>,
3629 projected<iterator_t<Range1>, Proj1>>>
3630 constexpr auto merge(Range1&& range1,
3631 Range2&& range2,
3632 OutputIterator result,
3633 Comp comp = {},
3634 Proj1 proj1 = {},
3635 Proj2 proj2 = {}) {
3636 return ranges::merge(ranges::begin(range1), ranges::end(range1),
3637 ranges::begin(range2), ranges::end(range2), result,
3638 std::move(comp), std::move(proj1), std::move(proj2));
3639 }
3640
3641 // Preconditions: `[first, middle)` and `[middle, last)` are valid ranges sorted
3642 // with respect to `comp` and `proj`.
3643 //
3644 // Effects: Merges two sorted consecutive ranges `[first, middle)` and
3645 // `[middle, last)`, putting the result of the merge into the range
3646 // `[first, last)`. The resulting range is sorted with respect to `comp` and
3647 // `proj`.
3648 //
3649 // Returns: `last`.
3650 //
3651 // Complexity: Let `N = last - first`: If enough additional memory is available,
3652 // exactly `N - 1` comparisons. Otherwise, `O(N log N)` comparisons. In either
3653 // case, twice as many projections as comparisons.
3654 //
3655 // Remarks: Stable.
3656 //
3657 // Reference: https://wg21.link/alg.merge#:~:text=ranges::inplace_merge(I
3658 template <typename BidirectionalIterator,
3659 typename Comp = ranges::less,
3660 typename Proj = identity,
3661 typename = internal::iterator_category_t<BidirectionalIterator>>
3662 constexpr auto inplace_merge(BidirectionalIterator first,
3663 BidirectionalIterator middle,
3664 BidirectionalIterator last,
3665 Comp comp = {},
3666 Proj proj = {}) {
3667 std::inplace_merge(first, middle, last,
3668 internal::ProjectedBinaryPredicate(comp, proj, proj));
3669 return last;
3670 }
3671
3672 // Preconditions: `[begin(range), middle)` and `[middle, end(range))` are valid
3673 // ranges sorted with respect to `comp` and `proj`.
3674 //
3675 // Effects: Merges two sorted consecutive ranges `[begin(range), middle)` and
3676 // `[middle, end(range))`, putting the result of the merge into `range`. The
3677 // resulting range is sorted with respect to `comp` and `proj`.
3678 //
3679 // Returns: `end(range)`.
3680 //
3681 // Complexity: Let `N = size(range)`: If enough additional memory is available,
3682 // exactly `N - 1` comparisons. Otherwise, `O(N log N)` comparisons. In either
3683 // case, twice as many projections as comparisons.
3684 //
3685 // Remarks: Stable.
3686 //
3687 // Reference: https://wg21.link/alg.merge#:~:text=ranges::inplace_merge(R
3688 template <typename Range,
3689 typename Comp = ranges::less,
3690 typename Proj = identity,
3691 typename = internal::range_category_t<Range>>
3692 constexpr auto inplace_merge(Range&& range,
3693 iterator_t<Range> middle,
3694 Comp comp = {},
3695 Proj proj = {}) {
3696 return ranges::inplace_merge(ranges::begin(range), middle, ranges::end(range),
3697 std::move(comp), std::move(proj));
3698 }
3699
3700 // [alg.set.operations] Set operations on sorted structures
3701 // Reference: https://wg21.link/alg.set.operations
3702
3703 // [includes] includes
3704 // Reference: https://wg21.link/includes
3705
3706 // Preconditions: The ranges `[first1, last1)` and `[first2, last2)` are sorted
3707 // with respect to `comp` and `proj1` or `proj2`, respectively.
3708 //
3709 // Returns: `true` if and only if `[first2, last2)` is a subsequence of
3710 // `[first1, last1)`.
3711 //
3712 // Complexity: At most `2 * ((last1 - first1) + (last2 - first2)) - 1`
3713 // comparisons and applications of each projection.
3714 //
3715 // Reference: https://wg21.link/includes#:~:text=ranges::includes(I1
3716 template <typename InputIterator1,
3717 typename InputIterator2,
3718 typename Comp = ranges::less,
3719 typename Proj1 = identity,
3720 typename Proj2 = identity,
3721 typename = internal::iterator_category_t<InputIterator1>,
3722 typename = internal::iterator_category_t<InputIterator2>,
3723 typename = indirect_result_t<Comp&,
3724 projected<InputIterator1, Proj1>,
3725 projected<InputIterator2, Proj2>>,
3726 typename = indirect_result_t<Comp&,
3727 projected<InputIterator2, Proj2>,
3728 projected<InputIterator1, Proj1>>>
3729 constexpr auto includes(InputIterator1 first1,
3730 InputIterator1 last1,
3731 InputIterator2 first2,
3732 InputIterator2 last2,
3733 Comp comp = {},
3734 Proj1 proj1 = {},
3735 Proj2 proj2 = {}) {
3736 DCHECK(ranges::is_sorted(first1, last1, comp, proj1));
3737 DCHECK(ranges::is_sorted(first2, last2, comp, proj2));
3738 // Needs to opt-in to all permutations, since std::includes expects
3739 // comp(proj1(lhs), proj2(rhs)) and comp(proj2(lhs), proj1(rhs)) to compile.
3740 return std::includes(
3741 first1, last1, first2, last2,
3742 internal::PermutedProjectedBinaryPredicate(comp, proj1, proj2));
3743 }
3744
3745 // Preconditions: The ranges `range1` and `range2` are sorted with respect to
3746 // `comp` and `proj1` or `proj2`, respectively.
3747 //
3748 // Returns: `true` if and only if `range2` is a subsequence of `range1`.
3749 //
3750 // Complexity: At most `2 * (size(range1) + size(range2)) - 1` comparisons and
3751 // applications of each projection.
3752 //
3753 // Reference: https://wg21.link/includes#:~:text=ranges::includes(R1
3754 template <typename Range1,
3755 typename Range2,
3756 typename Comp = ranges::less,
3757 typename Proj1 = identity,
3758 typename Proj2 = identity,
3759 typename = internal::range_category_t<Range1>,
3760 typename = internal::range_category_t<Range2>,
3761 typename = indirect_result_t<Comp&,
3762 projected<iterator_t<Range1>, Proj1>,
3763 projected<iterator_t<Range2>, Proj2>>,
3764 typename = indirect_result_t<Comp&,
3765 projected<iterator_t<Range2>, Proj2>,
3766 projected<iterator_t<Range1>, Proj1>>>
3767 constexpr auto includes(Range1&& range1,
3768 Range2&& range2,
3769 Comp comp = {},
3770 Proj1 proj1 = {},
3771 Proj2 proj2 = {}) {
3772 return ranges::includes(ranges::begin(range1), ranges::end(range1),
3773 ranges::begin(range2), ranges::end(range2),
3774 std::move(comp), std::move(proj1), std::move(proj2));
3775 }
3776
3777 // [set.union] set_union
3778 // Reference: https://wg21.link/set.union
3779
3780 // Preconditions: The ranges `[first1, last1)` and `[first2, last2)` are sorted
3781 // with respect to `comp` and `proj1` or `proj2`, respectively. The resulting
3782 // range does not overlap with either of the original ranges.
3783 //
3784 // Effects: Constructs a sorted union of the elements from the two ranges; that
3785 // is, the set of elements that are present in one or both of the ranges.
3786 //
3787 // Returns: The end of the constructed range.
3788 //
3789 // Complexity: At most `2 * ((last1 - first1) + (last2 - first2)) - 1`
3790 // comparisons and applications of each projection.
3791 //
3792 // Remarks: Stable. If `[first1, last1)` contains `m` elements that are
3793 // equivalent to each other and `[first2, last2)` contains `n` elements that are
3794 // equivalent to them, then all `m` elements from the first range are copied to
3795 // the output range, in order, and then the final `max(n - m , 0)` elements from
3796 // the second range are copied to the output range, in order.
3797 //
3798 // Reference: https://wg21.link/set.union#:~:text=ranges::set_union(I1
3799 template <typename InputIterator1,
3800 typename InputIterator2,
3801 typename OutputIterator,
3802 typename Comp = ranges::less,
3803 typename Proj1 = identity,
3804 typename Proj2 = identity,
3805 typename = internal::iterator_category_t<InputIterator1>,
3806 typename = internal::iterator_category_t<InputIterator2>,
3807 typename = internal::iterator_category_t<OutputIterator>,
3808 typename = indirect_result_t<Comp&,
3809 projected<InputIterator1, Proj1>,
3810 projected<InputIterator2, Proj2>>,
3811 typename = indirect_result_t<Comp&,
3812 projected<InputIterator2, Proj2>,
3813 projected<InputIterator1, Proj1>>>
3814 constexpr auto set_union(InputIterator1 first1,
3815 InputIterator1 last1,
3816 InputIterator2 first2,
3817 InputIterator2 last2,
3818 OutputIterator result,
3819 Comp comp = {},
3820 Proj1 proj1 = {},
3821 Proj2 proj2 = {}) {
3822 // Needs to opt-in to all permutations, since std::set_union expects
3823 // comp(proj1(lhs), proj2(rhs)) and comp(proj2(lhs), proj1(rhs)) to compile.
3824 return std::set_union(
3825 first1, last1, first2, last2, result,
3826 internal::PermutedProjectedBinaryPredicate(comp, proj1, proj2));
3827 }
3828
3829 // Preconditions: The ranges `range1` and `range2` are sorted with respect to
3830 // `comp` and `proj1` or `proj2`, respectively. The resulting range does not
3831 // overlap with either of the original ranges.
3832 //
3833 // Effects: Constructs a sorted union of the elements from the two ranges; that
3834 // is, the set of elements that are present in one or both of the ranges.
3835 //
3836 // Returns: The end of the constructed range.
3837 //
3838 // Complexity: At most `2 * (size(range1) + size(range2)) - 1` comparisons and
3839 // applications of each projection.
3840 //
3841 // Remarks: Stable. If `range1` contains `m` elements that are equivalent to
3842 // each other and `range2` contains `n` elements that are equivalent to them,
3843 // then all `m` elements from the first range are copied to the output range, in
3844 // order, and then the final `max(n - m , 0)` elements from the second range are
3845 // copied to the output range, in order.
3846 //
3847 // Reference: https://wg21.link/set.union#:~:text=ranges::set_union(R1
3848 template <typename Range1,
3849 typename Range2,
3850 typename OutputIterator,
3851 typename Comp = ranges::less,
3852 typename Proj1 = identity,
3853 typename Proj2 = identity,
3854 typename = internal::range_category_t<Range1>,
3855 typename = internal::range_category_t<Range2>,
3856 typename = internal::iterator_category_t<OutputIterator>,
3857 typename = indirect_result_t<Comp&,
3858 projected<iterator_t<Range1>, Proj1>,
3859 projected<iterator_t<Range2>, Proj2>>,
3860 typename = indirect_result_t<Comp&,
3861 projected<iterator_t<Range2>, Proj2>,
3862 projected<iterator_t<Range1>, Proj1>>>
3863 constexpr auto set_union(Range1&& range1,
3864 Range2&& range2,
3865 OutputIterator result,
3866 Comp comp = {},
3867 Proj1 proj1 = {},
3868 Proj2 proj2 = {}) {
3869 return ranges::set_union(ranges::begin(range1), ranges::end(range1),
3870 ranges::begin(range2), ranges::end(range2), result,
3871 std::move(comp), std::move(proj1), std::move(proj2));
3872 }
3873
3874 // [set.intersection] set_intersection
3875 // Reference: https://wg21.link/set.intersection
3876
3877 // Preconditions: The ranges `[first1, last1)` and `[first2, last2)` are sorted
3878 // with respect to `comp` and `proj1` or `proj2`, respectively. The resulting
3879 // range does not overlap with either of the original ranges.
3880 //
3881 // Effects: Constructs a sorted intersection of the elements from the two
3882 // ranges; that is, the set of elements that are present in both of the ranges.
3883 //
3884 // Returns: The end of the constructed range.
3885 //
3886 // Complexity: At most `2 * ((last1 - first1) + (last2 - first2)) - 1`
3887 // comparisons and applications of each projection.
3888 //
3889 // Remarks: Stable. If `[first1, last1)` contains `m` elements that are
3890 // equivalent to each other and `[first2, last2)` contains `n` elements that are
3891 // equivalent to them, the first `min(m, n)` elements are copied from the first
3892 // range to the output range, in order.
3893 //
3894 // Reference:
3895 // https://wg21.link/set.intersection#:~:text=ranges::set_intersection(I1
3896 template <typename InputIterator1,
3897 typename InputIterator2,
3898 typename OutputIterator,
3899 typename Comp = ranges::less,
3900 typename Proj1 = identity,
3901 typename Proj2 = identity,
3902 typename = internal::iterator_category_t<InputIterator1>,
3903 typename = internal::iterator_category_t<InputIterator2>,
3904 typename = internal::iterator_category_t<OutputIterator>,
3905 typename = indirect_result_t<Comp&,
3906 projected<InputIterator1, Proj1>,
3907 projected<InputIterator2, Proj2>>,
3908 typename = indirect_result_t<Comp&,
3909 projected<InputIterator2, Proj2>,
3910 projected<InputIterator1, Proj1>>>
3911 constexpr auto set_intersection(InputIterator1 first1,
3912 InputIterator1 last1,
3913 InputIterator2 first2,
3914 InputIterator2 last2,
3915 OutputIterator result,
3916 Comp comp = {},
3917 Proj1 proj1 = {},
3918 Proj2 proj2 = {}) {
3919 // Needs to opt-in to all permutations, since std::set_intersection expects
3920 // comp(proj1(lhs), proj2(rhs)) and comp(proj2(lhs), proj1(rhs)) to compile.
3921 return std::set_intersection(
3922 first1, last1, first2, last2, result,
3923 internal::PermutedProjectedBinaryPredicate(comp, proj1, proj2));
3924 }
3925
3926 // Preconditions: The ranges `range1` and `range2` are sorted with respect to
3927 // `comp` and `proj1` or `proj2`, respectively. The resulting range does not
3928 // overlap with either of the original ranges.
3929 //
3930 // Effects: Constructs a sorted intersection of the elements from the two
3931 // ranges; that is, the set of elements that are present in both of the ranges.
3932 //
3933 // Returns: The end of the constructed range.
3934 //
3935 // Complexity: At most `2 * (size(range1) + size(range2)) - 1` comparisons and
3936 // applications of each projection.
3937 //
3938 // Remarks: Stable. If `range1` contains `m` elements that are equivalent to
3939 // each other and `range2` contains `n` elements that are equivalent to them,
3940 // the first `min(m, n)` elements are copied from the first range to the output
3941 // range, in order.
3942 //
3943 // Reference:
3944 // https://wg21.link/set.intersection#:~:text=ranges::set_intersection(R1
3945 template <typename Range1,
3946 typename Range2,
3947 typename OutputIterator,
3948 typename Comp = ranges::less,
3949 typename Proj1 = identity,
3950 typename Proj2 = identity,
3951 typename = internal::range_category_t<Range1>,
3952 typename = internal::range_category_t<Range2>,
3953 typename = internal::iterator_category_t<OutputIterator>,
3954 typename = indirect_result_t<Comp&,
3955 projected<iterator_t<Range1>, Proj1>,
3956 projected<iterator_t<Range2>, Proj2>>,
3957 typename = indirect_result_t<Comp&,
3958 projected<iterator_t<Range2>, Proj2>,
3959 projected<iterator_t<Range1>, Proj1>>>
3960 constexpr auto set_intersection(Range1&& range1,
3961 Range2&& range2,
3962 OutputIterator result,
3963 Comp comp = {},
3964 Proj1 proj1 = {},
3965 Proj2 proj2 = {}) {
3966 return ranges::set_intersection(ranges::begin(range1), ranges::end(range1),
3967 ranges::begin(range2), ranges::end(range2),
3968 result, std::move(comp), std::move(proj1),
3969 std::move(proj2));
3970 }
3971
3972 // [set.difference] set_difference
3973 // Reference: https://wg21.link/set.difference
3974
3975 // Preconditions: The ranges `[first1, last1)` and `[first2, last2)` are sorted
3976 // with respect to `comp` and `proj1` or `proj2`, respectively. The resulting
3977 // range does not overlap with either of the original ranges.
3978 //
3979 // Effects: Copies the elements of the range `[first1, last1)` which are not
3980 // present in the range `[first2, last2)` to the range beginning at `result`.
3981 // The elements in the constructed range are sorted.
3982 //
3983 // Returns: The end of the constructed range.
3984 //
3985 // Complexity: At most `2 * ((last1 - first1) + (last2 - first2)) - 1`
3986 // comparisons and applications of each projection.
3987 //
3988 // Remarks: If `[first1, last1)` contains `m` elements that are equivalent to
3989 // each other and `[first2, last2)` contains `n` elements that are equivalent to
3990 // them, the last `max(m - n, 0)` elements from `[first1, last1)` are copied to
3991 // the output range, in order.
3992 //
3993 // Reference:
3994 // https://wg21.link/set.difference#:~:text=ranges::set_difference(I1
3995 template <typename InputIterator1,
3996 typename InputIterator2,
3997 typename OutputIterator,
3998 typename Comp = ranges::less,
3999 typename Proj1 = identity,
4000 typename Proj2 = identity,
4001 typename = internal::iterator_category_t<InputIterator1>,
4002 typename = internal::iterator_category_t<InputIterator2>,
4003 typename = internal::iterator_category_t<OutputIterator>,
4004 typename = indirect_result_t<Comp&,
4005 projected<InputIterator1, Proj1>,
4006 projected<InputIterator2, Proj2>>,
4007 typename = indirect_result_t<Comp&,
4008 projected<InputIterator2, Proj2>,
4009 projected<InputIterator1, Proj1>>>
4010 constexpr auto set_difference(InputIterator1 first1,
4011 InputIterator1 last1,
4012 InputIterator2 first2,
4013 InputIterator2 last2,
4014 OutputIterator result,
4015 Comp comp = {},
4016 Proj1 proj1 = {},
4017 Proj2 proj2 = {}) {
4018 // Needs to opt-in to all permutations, since std::set_difference expects
4019 // comp(proj1(lhs), proj2(rhs)) and comp(proj2(lhs), proj1(rhs)) to compile.
4020 return std::set_difference(
4021 first1, last1, first2, last2, result,
4022 internal::PermutedProjectedBinaryPredicate(comp, proj1, proj2));
4023 }
4024
4025 // Preconditions: The ranges `range1` and `range2` are sorted with respect to
4026 // `comp` and `proj1` or `proj2`, respectively. The resulting range does not
4027 // overlap with either of the original ranges.
4028 //
4029 // Effects: Copies the elements of `range1` which are not present in `range2`
4030 // to the range beginning at `result`. The elements in the constructed range are
4031 // sorted.
4032 //
4033 // Returns: The end of the constructed range.
4034 //
4035 // Complexity: At most `2 * (size(range1) + size(range2)) - 1` comparisons and
4036 // applications of each projection.
4037 //
4038 // Remarks: Stable. If `range1` contains `m` elements that are equivalent to
4039 // each other and `range2` contains `n` elements that are equivalent to them,
4040 // the last `max(m - n, 0)` elements from `range1` are copied to the output
4041 // range, in order.
4042 //
4043 // Reference:
4044 // https://wg21.link/set.difference#:~:text=ranges::set_difference(R1
4045 template <typename Range1,
4046 typename Range2,
4047 typename OutputIterator,
4048 typename Comp = ranges::less,
4049 typename Proj1 = identity,
4050 typename Proj2 = identity,
4051 typename = internal::range_category_t<Range1>,
4052 typename = internal::range_category_t<Range2>,
4053 typename = internal::iterator_category_t<OutputIterator>,
4054 typename = indirect_result_t<Comp&,
4055 projected<iterator_t<Range1>, Proj1>,
4056 projected<iterator_t<Range2>, Proj2>>,
4057 typename = indirect_result_t<Comp&,
4058 projected<iterator_t<Range2>, Proj2>,
4059 projected<iterator_t<Range1>, Proj1>>>
4060 constexpr auto set_difference(Range1&& range1,
4061 Range2&& range2,
4062 OutputIterator result,
4063 Comp comp = {},
4064 Proj1 proj1 = {},
4065 Proj2 proj2 = {}) {
4066 return ranges::set_difference(ranges::begin(range1), ranges::end(range1),
4067 ranges::begin(range2), ranges::end(range2),
4068 result, std::move(comp), std::move(proj1),
4069 std::move(proj2));
4070 }
4071
4072 // [set.symmetric.difference] set_symmetric_difference
4073 // Reference: https://wg21.link/set.symmetric.difference
4074
4075 // Preconditions: The ranges `[first1, last1)` and `[first2, last2)` are sorted
4076 // with respect to `comp` and `proj1` or `proj2`, respectively. The resulting
4077 // range does not overlap with either of the original ranges.
4078 //
4079 // Effects: Copies the elements of the range `[first1, last1)` that are not
4080 // present in the range `[first2, last2)`, and the elements of the range
4081 // `[first2, last2)` that are not present in the range `[first1, last1)` to the
4082 // range beginning at `result`. The elements in the constructed range are
4083 // sorted.
4084 //
4085 // Returns: The end of the constructed range.
4086 //
4087 // Complexity: At most `2 * ((last1 - first1) + (last2 - first2)) - 1`
4088 // comparisons and applications of each projection.
4089 //
4090 // Remarks: Stable. If `[first1, last1)` contains `m` elements that are
4091 // equivalent to each other and `[first2, last2)` contains `n` elements that are
4092 // equivalent to them, then `|m - n|` of those elements shall be copied to the
4093 // output range: the last `m - n` of these elements from `[first1, last1)` if
4094 // `m > n`, and the last `n - m` of these elements from `[first2, last2)` if
4095 // `m < n`. In either case, the elements are copied in order.
4096 //
4097 // Reference:
4098 // https://wg21.link/set.symmetric.difference#:~:text=set_symmetric_difference(I1
4099 template <typename InputIterator1,
4100 typename InputIterator2,
4101 typename OutputIterator,
4102 typename Comp = ranges::less,
4103 typename Proj1 = identity,
4104 typename Proj2 = identity,
4105 typename = internal::iterator_category_t<InputIterator1>,
4106 typename = internal::iterator_category_t<InputIterator2>,
4107 typename = internal::iterator_category_t<OutputIterator>,
4108 typename = indirect_result_t<Comp&,
4109 projected<InputIterator1, Proj1>,
4110 projected<InputIterator2, Proj2>>,
4111 typename = indirect_result_t<Comp&,
4112 projected<InputIterator2, Proj2>,
4113 projected<InputIterator1, Proj1>>>
4114 constexpr auto set_symmetric_difference(InputIterator1 first1,
4115 InputIterator1 last1,
4116 InputIterator2 first2,
4117 InputIterator2 last2,
4118 OutputIterator result,
4119 Comp comp = {},
4120 Proj1 proj1 = {},
4121 Proj2 proj2 = {}) {
4122 // Needs to opt-in to all permutations, since std::set_symmetric_difference
4123 // expects comp(proj1(lhs), proj2(rhs)) and comp(proj2(lhs), proj1(rhs)) to
4124 // compile.
4125 return std::set_symmetric_difference(
4126 first1, last1, first2, last2, result,
4127 internal::PermutedProjectedBinaryPredicate(comp, proj1, proj2));
4128 }
4129
4130 // Preconditions: The ranges `range1` and `range2` are sorted with respect to
4131 // `comp` and `proj1` or `proj2`, respectively. The resulting range does not
4132 // overlap with either of the original ranges.
4133 //
4134 // Effects: Copies the elements of `range1` that are not present in `range2`,
4135 // and the elements of `range2` that are not present in `range1` to the range
4136 // beginning at `result`. The elements in the constructed range are sorted.
4137 //
4138 // Returns: The end of the constructed range.
4139 //
4140 // Complexity: At most `2 * (size(range1) + size(range2)) - 1` comparisons and
4141 // applications of each projection.
4142 //
4143 // Remarks: Stable. If `range1` contains `m` elements that are equivalent to
4144 // each other and `range2` contains `n` elements that are equivalent to them,
4145 // then `|m - n|` of those elements shall be copied to the output range: the
4146 // last `m - n` of these elements from `range1` if `m > n`, and the last `n - m`
4147 // of these elements from `range2` if `m < n`. In either case, the elements are
4148 // copied in order.
4149 //
4150 // Reference:
4151 // https://wg21.link/set.symmetric.difference#:~:text=set_symmetric_difference(R1
4152 template <typename Range1,
4153 typename Range2,
4154 typename OutputIterator,
4155 typename Comp = ranges::less,
4156 typename Proj1 = identity,
4157 typename Proj2 = identity,
4158 typename = internal::range_category_t<Range1>,
4159 typename = internal::range_category_t<Range2>,
4160 typename = internal::iterator_category_t<OutputIterator>,
4161 typename = indirect_result_t<Comp&,
4162 projected<iterator_t<Range1>, Proj1>,
4163 projected<iterator_t<Range2>, Proj2>>,
4164 typename = indirect_result_t<Comp&,
4165 projected<iterator_t<Range2>, Proj2>,
4166 projected<iterator_t<Range1>, Proj1>>>
4167 constexpr auto set_symmetric_difference(Range1&& range1,
4168 Range2&& range2,
4169 OutputIterator result,
4170 Comp comp = {},
4171 Proj1 proj1 = {},
4172 Proj2 proj2 = {}) {
4173 return ranges::set_symmetric_difference(
4174 ranges::begin(range1), ranges::end(range1), ranges::begin(range2),
4175 ranges::end(range2), result, std::move(comp), std::move(proj1),
4176 std::move(proj2));
4177 }
4178
4179 // [alg.heap.operations] Heap operations
4180 // Reference: https://wg21.link/alg.heap.operations
4181
4182 // [push.heap] push_heap
4183 // Reference: https://wg21.link/push.heap
4184
4185 // Preconditions: The range `[first, last - 1)` is a valid heap with respect to
4186 // `comp` and `proj`.
4187 //
4188 // Effects: Places the value in the location `last - 1` into the resulting heap
4189 // `[first, last)`.
4190 //
4191 // Returns: `last`.
4192 //
4193 // Complexity: At most `log(last - first)` comparisons and twice as many
4194 // projections.
4195 //
4196 // Reference: https://wg21.link/push.heap#:~:text=ranges::push_heap(I
4197 template <typename RandomAccessIterator,
4198 typename Comp = ranges::less,
4199 typename Proj = identity,
4200 typename = internal::iterator_category_t<RandomAccessIterator>,
4201 typename = indirect_result_t<Comp&,
4202 projected<RandomAccessIterator, Proj>,
4203 projected<RandomAccessIterator, Proj>>>
4204 constexpr auto push_heap(RandomAccessIterator first,
4205 RandomAccessIterator last,
4206 Comp comp = {},
4207 Proj proj = {}) {
4208 std::push_heap(first, last,
4209 internal::ProjectedBinaryPredicate(comp, proj, proj));
4210 return last;
4211 }
4212
4213 // Preconditions: The range `[begin(range), end(range) - 1)` is a valid heap
4214 // with respect to `comp` and `proj`.
4215 //
4216 // Effects: Places the value in the location `end(range) - 1` into the resulting
4217 // heap `range`.
4218 //
4219 // Returns: `end(range)`.
4220 //
4221 // Complexity: At most `log(size(range))` comparisons and twice as many
4222 // projections.
4223 //
4224 // Reference: https://wg21.link/push.heap#:~:text=ranges::push_heap(R
4225 template <typename Range,
4226 typename Comp = ranges::less,
4227 typename Proj = identity,
4228 typename = internal::range_category_t<Range>,
4229 typename = indirect_result_t<Comp&,
4230 projected<iterator_t<Range>, Proj>,
4231 projected<iterator_t<Range>, Proj>>>
4232 constexpr auto push_heap(Range&& range, Comp comp = {}, Proj proj = {}) {
4233 return ranges::push_heap(ranges::begin(range), ranges::end(range),
4234 std::move(comp), std::move(proj));
4235 }
4236
4237 // [pop.heap] pop_heap
4238 // Reference: https://wg21.link/pop.heap
4239
4240 // Preconditions: The range `[first, last)` is a valid non-empty heap with
4241 // respect to `comp` and `proj`.
4242 //
4243 // Effects: Swaps the value in the location `first` with the value in the
4244 // location `last - 1` and makes `[first, last - 1)` into a heap with respect to
4245 // `comp` and `proj`.
4246 //
4247 // Returns: `last`.
4248 //
4249 // Complexity: At most `2 log(last - first)` comparisons and twice as many
4250 // projections.
4251 //
4252 // Reference: https://wg21.link/pop.heap#:~:text=ranges::pop_heap(I
4253 template <typename RandomAccessIterator,
4254 typename Comp = ranges::less,
4255 typename Proj = identity,
4256 typename = internal::iterator_category_t<RandomAccessIterator>,
4257 typename = indirect_result_t<Comp&,
4258 projected<RandomAccessIterator, Proj>,
4259 projected<RandomAccessIterator, Proj>>>
4260 constexpr auto pop_heap(RandomAccessIterator first,
4261 RandomAccessIterator last,
4262 Comp comp = {},
4263 Proj proj = {}) {
4264 std::pop_heap(first, last,
4265 internal::ProjectedBinaryPredicate(comp, proj, proj));
4266 return last;
4267 }
4268
4269 // Preconditions: `range` is a valid non-empty heap with respect to `comp` and
4270 // `proj`.
4271 //
4272 // Effects: Swaps the value in the location `begin(range)` with the value in the
4273 // location `end(range) - 1` and makes `[begin(range), end(range) - 1)` into a
4274 // heap with respect to `comp` and `proj`.
4275 //
4276 // Returns: `end(range)`.
4277 //
4278 // Complexity: At most `2 log(size(range))` comparisons and twice as many
4279 // projections.
4280 //
4281 // Reference: https://wg21.link/pop.heap#:~:text=ranges::pop_heap(R
4282 template <typename Range,
4283 typename Comp = ranges::less,
4284 typename Proj = identity,
4285 typename = internal::range_category_t<Range>,
4286 typename = indirect_result_t<Comp&,
4287 projected<iterator_t<Range>, Proj>,
4288 projected<iterator_t<Range>, Proj>>>
4289 constexpr auto pop_heap(Range&& range, Comp comp = {}, Proj proj = {}) {
4290 return ranges::pop_heap(ranges::begin(range), ranges::end(range),
4291 std::move(comp), std::move(proj));
4292 }
4293
4294 // [make.heap] make_heap
4295 // Reference: https://wg21.link/make.heap
4296
4297 // Effects: Constructs a heap with respect to `comp` and `proj` out of the range
4298 // `[first, last)`.
4299 //
4300 // Returns: `last`.
4301 //
4302 // Complexity: At most `3 log(last - first)` comparisons and twice as many
4303 // projections.
4304 //
4305 // Reference: https://wg21.link/make.heap#:~:text=ranges::make_heap(I
4306 template <typename RandomAccessIterator,
4307 typename Comp = ranges::less,
4308 typename Proj = identity,
4309 typename = internal::iterator_category_t<RandomAccessIterator>,
4310 typename = indirect_result_t<Comp&,
4311 projected<RandomAccessIterator, Proj>,
4312 projected<RandomAccessIterator, Proj>>>
4313 constexpr auto make_heap(RandomAccessIterator first,
4314 RandomAccessIterator last,
4315 Comp comp = {},
4316 Proj proj = {}) {
4317 std::make_heap(first, last,
4318 internal::ProjectedBinaryPredicate(comp, proj, proj));
4319 return last;
4320 }
4321
4322 // Effects: Constructs a heap with respect to `comp` and `proj` out of `range`.
4323 //
4324 // Returns: `end(range)`.
4325 //
4326 // Complexity: At most `3 log(size(range))` comparisons and twice as many
4327 // projections.
4328 //
4329 // Reference: https://wg21.link/make.heap#:~:text=ranges::make_heap(R
4330 template <typename Range,
4331 typename Comp = ranges::less,
4332 typename Proj = identity,
4333 typename = internal::range_category_t<Range>,
4334 typename = indirect_result_t<Comp&,
4335 projected<iterator_t<Range>, Proj>,
4336 projected<iterator_t<Range>, Proj>>>
4337 constexpr auto make_heap(Range&& range, Comp comp = {}, Proj proj = {}) {
4338 return ranges::make_heap(ranges::begin(range), ranges::end(range),
4339 std::move(comp), std::move(proj));
4340 }
4341
4342 // [sort.heap] sort_heap
4343 // Reference: https://wg21.link/sort.heap
4344
4345 // Preconditions: The range `[first, last)` is a valid heap with respect to
4346 // `comp` and `proj`.
4347 //
4348 // Effects: Sorts elements in the heap `[first, last)` with respect to `comp`
4349 // and `proj`.
4350 //
4351 // Returns: `last`.
4352 //
4353 // Complexity: At most `2 N log N` comparisons, where `N = last - first`, and
4354 // twice as many projections.
4355 //
4356 // Reference: https://wg21.link/sort.heap#:~:text=ranges::sort_heap(I
4357 template <typename RandomAccessIterator,
4358 typename Comp = ranges::less,
4359 typename Proj = identity,
4360 typename = internal::iterator_category_t<RandomAccessIterator>,
4361 typename = indirect_result_t<Comp&,
4362 projected<RandomAccessIterator, Proj>,
4363 projected<RandomAccessIterator, Proj>>>
4364 constexpr auto sort_heap(RandomAccessIterator first,
4365 RandomAccessIterator last,
4366 Comp comp = {},
4367 Proj proj = {}) {
4368 std::sort_heap(first, last,
4369 internal::ProjectedBinaryPredicate(comp, proj, proj));
4370 return last;
4371 }
4372
4373 // Preconditions: `range` is a valid heap with respect to `comp` and `proj`.
4374 //
4375 // Effects: Sorts elements in the heap `range` with respect to `comp` and
4376 // `proj`.
4377 //
4378 // Returns: `end(range)`.
4379 //
4380 // Complexity: At most `2 N log N` comparisons, where `N = size(range)`, and
4381 // twice as many projections.
4382 //
4383 // Reference: https://wg21.link/sort.heap#:~:text=ranges::sort_heap(R
4384 template <typename Range,
4385 typename Comp = ranges::less,
4386 typename Proj = identity,
4387 typename = internal::range_category_t<Range>,
4388 typename = indirect_result_t<Comp&,
4389 projected<iterator_t<Range>, Proj>,
4390 projected<iterator_t<Range>, Proj>>>
4391 constexpr auto sort_heap(Range&& range, Comp comp = {}, Proj proj = {}) {
4392 return ranges::sort_heap(ranges::begin(range), ranges::end(range),
4393 std::move(comp), std::move(proj));
4394 }
4395
4396 // [is.heap] is_heap
4397 // Reference: https://wg21.link/is.heap
4398
4399 // Returns: Whether the range `[first, last)` is a heap with respect to `comp`
4400 // and `proj`.
4401 //
4402 // Complexity: Linear.
4403 //
4404 // Reference: https://wg21.link/is.heap#:~:text=ranges::is_heap(I
4405 template <typename RandomAccessIterator,
4406 typename Comp = ranges::less,
4407 typename Proj = identity,
4408 typename = internal::iterator_category_t<RandomAccessIterator>,
4409 typename = indirect_result_t<Comp&,
4410 projected<RandomAccessIterator, Proj>,
4411 projected<RandomAccessIterator, Proj>>>
4412 constexpr auto is_heap(RandomAccessIterator first,
4413 RandomAccessIterator last,
4414 Comp comp = {},
4415 Proj proj = {}) {
4416 return std::is_heap(first, last,
4417 internal::ProjectedBinaryPredicate(comp, proj, proj));
4418 }
4419
4420 // Returns: Whether `range` is a heap with respect to `comp` and `proj`.
4421 //
4422 // Complexity: Linear.
4423 //
4424 // Reference: https://wg21.link/is.heap#:~:text=ranges::is_heap(R
4425 template <typename Range,
4426 typename Comp = ranges::less,
4427 typename Proj = identity,
4428 typename = internal::range_category_t<Range>,
4429 typename = indirect_result_t<Comp&,
4430 projected<iterator_t<Range>, Proj>,
4431 projected<iterator_t<Range>, Proj>>>
4432 constexpr auto is_heap(Range&& range, Comp comp = {}, Proj proj = {}) {
4433 return ranges::is_heap(ranges::begin(range), ranges::end(range),
4434 std::move(comp), std::move(proj));
4435 }
4436
4437 // Returns: The last iterator `i` in `[first, last]` for which the range
4438 // `[first, i)` is a heap with respect to `comp` and `proj`.
4439 //
4440 // Complexity: Linear.
4441 //
4442 // Reference: https://wg21.link/is.heap#:~:text=ranges::is_heap_until(I
4443 template <typename RandomAccessIterator,
4444 typename Comp = ranges::less,
4445 typename Proj = identity,
4446 typename = internal::iterator_category_t<RandomAccessIterator>,
4447 typename = indirect_result_t<Comp&,
4448 projected<RandomAccessIterator, Proj>,
4449 projected<RandomAccessIterator, Proj>>>
4450 constexpr auto is_heap_until(RandomAccessIterator first,
4451 RandomAccessIterator last,
4452 Comp comp = {},
4453 Proj proj = {}) {
4454 return std::is_heap_until(
4455 first, last, internal::ProjectedBinaryPredicate(comp, proj, proj));
4456 }
4457
4458 // Returns: The last iterator `i` in `[begin(range), end(range)]` for which the
4459 // range `[begin(range), i)` is a heap with respect to `comp` and `proj`.
4460 //
4461 // Complexity: Linear.
4462 //
4463 // Reference: https://wg21.link/is.heap#:~:text=ranges::is_heap_until(R
4464 template <typename Range,
4465 typename Comp = ranges::less,
4466 typename Proj = identity,
4467 typename = internal::range_category_t<Range>,
4468 typename = indirect_result_t<Comp&,
4469 projected<iterator_t<Range>, Proj>,
4470 projected<iterator_t<Range>, Proj>>>
4471 constexpr auto is_heap_until(Range&& range, Comp comp = {}, Proj proj = {}) {
4472 return ranges::is_heap_until(ranges::begin(range), ranges::end(range),
4473 std::move(comp), std::move(proj));
4474 }
4475
4476 // [alg.min.max] Minimum and maximum
4477 // Reference: https://wg21.link/alg.min.max
4478
4479 // Returns: The smaller value. Returns the first argument when the arguments are
4480 // equivalent.
4481 //
4482 // Complexity: Exactly one comparison and two applications of the projection, if
4483 // any.
4484 //
4485 // Reference: https://wg21.link/alg.min.max#:~:text=ranges::min
4486 template <typename T, typename Comp = ranges::less, typename Proj = identity>
4487 constexpr const T& min(const T& a, const T& b, Comp comp = {}, Proj proj = {}) {
4488 return base::invoke(comp, base::invoke(proj, b), base::invoke(proj, a)) ? b
4489 : a;
4490 }
4491
4492 // Preconditions: `!empty(ilist)`.
4493 //
4494 // Returns: The smallest value in the input range. Returns a copy of the
4495 // leftmost element when several elements are equivalent to the smallest.
4496 //
4497 // Complexity: Exactly `size(ilist) - 1` comparisons and twice as many
4498 // applications of the projection, if any.
4499 //
4500 // Reference: https://wg21.link/alg.min.max#:~:text=ranges::min(initializer_list
4501 template <typename T, typename Comp = ranges::less, typename Proj = identity>
4502 constexpr T min(std::initializer_list<T> ilist,
4503 Comp comp = {},
4504 Proj proj = {}) {
4505 return *std::min_element(
4506 ilist.begin(), ilist.end(),
4507 internal::ProjectedBinaryPredicate(comp, proj, proj));
4508 }
4509
4510 // Preconditions: `!empty(range)`.
4511 //
4512 // Returns: The smallest value in the input range. Returns a copy of the
4513 // leftmost element when several elements are equivalent to the smallest.
4514 //
4515 // Complexity: Exactly `size(range) - 1` comparisons and twice as many
4516 // applications of the projection, if any.
4517 //
4518 // Reference: https://wg21.link/alg.min.max#:~:text=ranges::min(R
4519 template <typename Range,
4520 typename Comp = ranges::less,
4521 typename Proj = identity,
4522 typename = internal::range_category_t<Range>>
4523 constexpr auto min(Range&& range, Comp comp = {}, Proj proj = {}) {
4524 return *std::min_element(
4525 ranges::begin(range), ranges::end(range),
4526 internal::ProjectedBinaryPredicate(comp, proj, proj));
4527 }
4528
4529 // Returns: The larger value. Returns the first argument when the arguments are
4530 // equivalent.
4531 //
4532 // Complexity: Exactly one comparison and two applications of the projection, if
4533 // any.
4534 //
4535 // Reference: https://wg21.link/alg.min.max#:~:text=ranges::max
4536 template <typename T, typename Comp = ranges::less, typename Proj = identity>
4537 constexpr const T& max(const T& a, const T& b, Comp comp = {}, Proj proj = {}) {
4538 return base::invoke(comp, base::invoke(proj, a), base::invoke(proj, b)) ? b
4539 : a;
4540 }
4541
4542 // Preconditions: `!empty(ilist)`.
4543 //
4544 // Returns: The largest value in the input range. Returns a copy of the leftmost
4545 // element when several elements are equivalent to the largest.
4546 //
4547 // Complexity: Exactly `size(ilist) - 1` comparisons and twice as many
4548 // applications of the projection, if any.
4549 //
4550 // Reference: https://wg21.link/alg.min.max#:~:text=ranges::max(initializer_list
4551 template <typename T, typename Comp = ranges::less, typename Proj = identity>
4552 constexpr T max(std::initializer_list<T> ilist,
4553 Comp comp = {},
4554 Proj proj = {}) {
4555 return *std::max_element(
4556 ilist.begin(), ilist.end(),
4557 internal::ProjectedBinaryPredicate(comp, proj, proj));
4558 }
4559
4560 // Preconditions: `!empty(range)`.
4561 //
4562 // Returns: The largest value in the input range. Returns a copy of the leftmost
4563 // element when several elements are equivalent to the smallest.
4564 //
4565 // Complexity: Exactly `size(range) - 1` comparisons and twice as many
4566 // applications of the projection, if any.
4567 //
4568 // Reference: https://wg21.link/alg.min.max#:~:text=ranges::max(R
4569 template <typename Range,
4570 typename Comp = ranges::less,
4571 typename Proj = identity,
4572 typename = internal::range_category_t<Range>>
4573 constexpr auto max(Range&& range, Comp comp = {}, Proj proj = {}) {
4574 return *std::max_element(
4575 ranges::begin(range), ranges::end(range),
4576 internal::ProjectedBinaryPredicate(comp, proj, proj));
4577 }
4578
4579 // Returns: `{b, a}` if `b` is smaller than `a`, and `{a, b}` otherwise.
4580 //
4581 // Complexity: Exactly one comparison and two applications of the projection, if
4582 // any.
4583 //
4584 // Reference: https://wg21.link/alg.min.max#:~:text=ranges::minmax
4585 template <typename T, typename Comp = ranges::less, typename Proj = identity>
4586 constexpr auto minmax(const T& a, const T& b, Comp comp = {}, Proj proj = {}) {
4587 return std::minmax(a, b,
4588 internal::ProjectedBinaryPredicate(comp, proj, proj));
4589 }
4590
4591 // Preconditions: `!empty(ilist)`.
4592 //
4593 // Returns: Let `X` be the return type. Returns `X{x, y}`, where `x` is a copy
4594 // of the leftmost element with the smallest value and `y` a copy of the
4595 // rightmost element with the largest value in the input range.
4596 //
4597 // Complexity: At most `(3/2) size(ilist)` applications of the corresponding
4598 // predicate and twice as many applications of the projection, if any.
4599 //
4600 // Reference:
4601 // https://wg21.link/alg.min.max#:~:text=ranges::minmax(initializer_list
4602 template <typename T, typename Comp = ranges::less, typename Proj = identity>
4603 constexpr auto minmax(std::initializer_list<T> ilist,
4604 Comp comp = {},
4605 Proj proj = {}) {
4606 auto it =
4607 std::minmax_element(ranges::begin(ilist), ranges::end(ilist),
4608 internal::ProjectedBinaryPredicate(comp, proj, proj));
4609 return std::pair<T, T>{*it.first, *it.second};
4610 }
4611
4612 // Preconditions: `!empty(range)`.
4613 //
4614 // Returns: Let `X` be the return type. Returns `X{x, y}`, where `x` is a copy
4615 // of the leftmost element with the smallest value and `y` a copy of the
4616 // rightmost element with the largest value in the input range.
4617 //
4618 // Complexity: At most `(3/2) size(range)` applications of the corresponding
4619 // predicate and twice as many applications of the projection, if any.
4620 //
4621 // Reference: https://wg21.link/alg.min.max#:~:text=ranges::minmax(R
4622 template <typename Range,
4623 typename Comp = ranges::less,
4624 typename Proj = identity,
4625 typename = internal::range_category_t<Range>>
4626 constexpr auto minmax(Range&& range, Comp comp = {}, Proj proj = {}) {
4627 using T = range_value_t<Range>;
4628 auto it =
4629 std::minmax_element(ranges::begin(range), ranges::end(range),
4630 internal::ProjectedBinaryPredicate(comp, proj, proj));
4631 return std::pair<T, T>{*it.first, *it.second};
4632 }
4633
4634 // Returns: The first iterator i in the range `[first, last)` such that for
4635 // every iterator `j` in the range `[first, last)`,
4636 // `bool(invoke(comp, invoke(proj, *j), invoke(proj, *i)))` is `false`. Returns
4637 // `last` if `first == last`.
4638 //
4639 // Complexity: Exactly `max(last - first - 1, 0)` comparisons and twice as
4640 // many projections.
4641 //
4642 // Reference: https://wg21.link/alg.min.max#:~:text=ranges::min_element(I
4643 template <typename ForwardIterator,
4644 typename Comp = ranges::less,
4645 typename Proj = identity,
4646 typename = internal::iterator_category_t<ForwardIterator>,
4647 typename = indirect_result_t<Comp&,
4648 projected<ForwardIterator, Proj>,
4649 projected<ForwardIterator, Proj>>>
4650 constexpr auto min_element(ForwardIterator first,
4651 ForwardIterator last,
4652 Comp comp = {},
4653 Proj proj = {}) {
4654 return std::min_element(first, last,
4655 internal::ProjectedBinaryPredicate(comp, proj, proj));
4656 }
4657
4658 // Returns: The first iterator i in `range` such that for every iterator `j` in
4659 // `range`, `bool(invoke(comp, invoke(proj, *j), invoke(proj, *i)))` is `false`.
4660 // Returns `end(range)` if `empty(range)`.
4661 //
4662 // Complexity: Exactly `max(size(range) - 1, 0)` comparisons and twice as many
4663 // projections.
4664 //
4665 // Reference: https://wg21.link/alg.min.max#:~:text=ranges::min_element(R
4666 template <typename Range,
4667 typename Comp = ranges::less,
4668 typename Proj = identity,
4669 typename = internal::range_category_t<Range>,
4670 typename = indirect_result_t<Comp&,
4671 projected<iterator_t<Range>, Proj>,
4672 projected<iterator_t<Range>, Proj>>>
4673 constexpr auto min_element(Range&& range, Comp comp = {}, Proj proj = {}) {
4674 return ranges::min_element(ranges::begin(range), ranges::end(range),
4675 std::move(comp), std::move(proj));
4676 }
4677
4678 // Returns: The first iterator i in the range `[first, last)` such that for
4679 // every iterator `j` in the range `[first, last)`,
4680 // `bool(invoke(comp, invoke(proj, *i), invoke(proj, *j)))` is `false`.
4681 // Returns `last` if `first == last`.
4682 //
4683 // Complexity: Exactly `max(last - first - 1, 0)` comparisons and twice as
4684 // many projections.
4685 //
4686 // Reference: https://wg21.link/alg.min.max#:~:text=ranges::max_element(I
4687 template <typename ForwardIterator,
4688 typename Comp = ranges::less,
4689 typename Proj = identity,
4690 typename = internal::iterator_category_t<ForwardIterator>,
4691 typename = indirect_result_t<Comp&,
4692 projected<ForwardIterator, Proj>,
4693 projected<ForwardIterator, Proj>>>
4694 constexpr auto max_element(ForwardIterator first,
4695 ForwardIterator last,
4696 Comp comp = {},
4697 Proj proj = {}) {
4698 return std::max_element(first, last,
4699 internal::ProjectedBinaryPredicate(comp, proj, proj));
4700 }
4701
4702 // Returns: The first iterator i in `range` such that for every iterator `j`
4703 // in `range`, `bool(invoke(comp, invoke(proj, *j), invoke(proj, *j)))` is
4704 // `false`. Returns `end(range)` if `empty(range)`.
4705 //
4706 // Complexity: Exactly `max(size(range) - 1, 0)` comparisons and twice as many
4707 // projections.
4708 //
4709 // Reference: https://wg21.link/alg.min.max#:~:text=ranges::max_element(R
4710 template <typename Range,
4711 typename Comp = ranges::less,
4712 typename Proj = identity,
4713 typename = internal::range_category_t<Range>,
4714 typename = indirect_result_t<Comp&,
4715 projected<iterator_t<Range>, Proj>,
4716 projected<iterator_t<Range>, Proj>>>
4717 constexpr auto max_element(Range&& range, Comp comp = {}, Proj proj = {}) {
4718 return ranges::max_element(ranges::begin(range), ranges::end(range),
4719 std::move(comp), std::move(proj));
4720 }
4721
4722 // Returns: `{first, first}` if `[first, last)` is empty, otherwise `{m, M}`,
4723 // where `m` is the first iterator in `[first, last)` such that no iterator in
4724 // the range refers to a smaller element, and where `M` is the last iterator
4725 // in
4726 // `[first, last)` such that no iterator in the range refers to a larger
4727 // element.
4728 //
4729 // Complexity: Let `N` be `last - first`. At most `max(3/2 (N − 1), 0)`
4730 // comparisons and twice as many applications of the projection, if any.
4731 //
4732 // Reference: https://wg21.link/alg.min.max#:~:text=ranges::minmax_element(I
4733 template <typename ForwardIterator,
4734 typename Comp = ranges::less,
4735 typename Proj = identity,
4736 typename = internal::iterator_category_t<ForwardIterator>,
4737 typename = indirect_result_t<Comp&,
4738 projected<ForwardIterator, Proj>,
4739 projected<ForwardIterator, Proj>>>
4740 constexpr auto minmax_element(ForwardIterator first,
4741 ForwardIterator last,
4742 Comp comp = {},
4743 Proj proj = {}) {
4744 return std::minmax_element(
4745 first, last, internal::ProjectedBinaryPredicate(comp, proj, proj));
4746 }
4747
4748 // Returns: `{begin(range), begin(range)}` if `range` is empty, otherwise
4749 // `{m, M}`, where `m` is the first iterator in `range` such that no iterator
4750 // in the range refers to a smaller element, and where `M` is the last
4751 // iterator in `range` such that no iterator in the range refers to a larger
4752 // element.
4753 //
4754 // Complexity: Let `N` be `size(range)`. At most `max(3/2 (N − 1), 0)`
4755 // comparisons and twice as many applications of the projection, if any.
4756 //
4757 // Reference: https://wg21.link/alg.min.max#:~:text=ranges::minmax_element(R
4758 template <typename Range,
4759 typename Comp = ranges::less,
4760 typename Proj = identity,
4761 typename = internal::range_category_t<Range>,
4762 typename = indirect_result_t<Comp&,
4763 projected<iterator_t<Range>, Proj>,
4764 projected<iterator_t<Range>, Proj>>>
4765 constexpr auto minmax_element(Range&& range, Comp comp = {}, Proj proj = {}) {
4766 return ranges::minmax_element(ranges::begin(range), ranges::end(range),
4767 std::move(comp), std::move(proj));
4768 }
4769
4770 // [alg.clamp] Bounded value
4771 // Reference: https://wg21.link/alg.clamp
4772
4773 // Preconditions: `bool(invoke(comp, invoke(proj, hi), invoke(proj, lo)))` is
4774 // `false`.
4775 //
4776 // Returns: `lo` if `bool(invoke(comp, invoke(proj, v), invoke(proj, lo)))` is
4777 // `true`, `hi` if `bool(invoke(comp, invoke(proj, hi), invoke(proj, v)))` is
4778 // `true`, otherwise `v`.
4779 //
4780 // Complexity: At most two comparisons and three applications of the
4781 // projection.
4782 //
4783 // Reference: https://wg21.link/alg.clamp#:~:text=ranges::clamp
4784 template <typename T, typename Comp = ranges::less, typename Proj = identity>
4785 constexpr const T& clamp(const T& v,
4786 const T& lo,
4787 const T& hi,
4788 Comp comp = {},
4789 Proj proj = {}) {
4790 auto&& projected_v = base::invoke(proj, v);
4791 if (base::invoke(comp, projected_v, base::invoke(proj, lo)))
4792 return lo;
4793
4794 return base::invoke(comp, base::invoke(proj, hi), projected_v) ? hi : v;
4795 }
4796
4797 // [alg.lex.comparison] Lexicographical comparison
4798 // Reference: https://wg21.link/alg.lex.comparison
4799
4800 // Returns: `true` if and only if the sequence of elements defined by the range
4801 // `[first1, last1)` is lexicographically less than the sequence of elements
4802 // defined by the range `[first2, last2)`.
4803 //
4804 // Complexity: At most `2 min(last1 - first1, last2 - first2)` applications of
4805 // the corresponding comparison and each projection, if any.
4806 //
4807 // Remarks: If two sequences have the same number of elements and their
4808 // corresponding elements (if any) are equivalent, then neither sequence is
4809 // lexicographically less than the other. If one sequence is a proper prefix of
4810 // the other, then the shorter sequence is lexicographically less than the
4811 // longer sequence. Otherwise, the lexicographical comparison of the sequences
4812 // yields the same result as the comparison of the first corresponding pair of
4813 // elements that are not equivalent.
4814 //
4815 // Reference:
4816 // https://wg21.link/alg.lex.comparison#:~:text=lexicographical_compare(I1
4817 template <typename ForwardIterator1,
4818 typename ForwardIterator2,
4819 typename Comp = ranges::less,
4820 typename Proj1 = identity,
4821 typename Proj2 = identity,
4822 typename = internal::iterator_category_t<ForwardIterator1>,
4823 typename = internal::iterator_category_t<ForwardIterator2>,
4824 typename = indirect_result_t<Comp&,
4825 projected<ForwardIterator1, Proj1>,
4826 projected<ForwardIterator2, Proj2>>,
4827 typename = indirect_result_t<Comp&,
4828 projected<ForwardIterator2, Proj2>,
4829 projected<ForwardIterator1, Proj1>>>
4830 constexpr bool lexicographical_compare(ForwardIterator1 first1,
4831 ForwardIterator1 last1,
4832 ForwardIterator2 first2,
4833 ForwardIterator2 last2,
4834 Comp comp = {},
4835 Proj1 proj1 = {},
4836 Proj2 proj2 = {}) {
4837 for (; first1 != last1 && first2 != last2; ++first1, ++first2) {
4838 auto&& projected_first1 = base::invoke(proj1, *first1);
4839 auto&& projected_first2 = base::invoke(proj2, *first2);
4840 if (base::invoke(comp, projected_first1, projected_first2))
4841 return true;
4842 if (base::invoke(comp, projected_first2, projected_first1))
4843 return false;
4844 }
4845
4846 // `first2 != last2` is equivalent to `first1 == last1 && first2 != last2`
4847 // here, since we broke out of the loop above.
4848 return first2 != last2;
4849 }
4850
4851 // Returns: `true` if and only if the sequence of elements defined by `range1`
4852 // is lexicographically less than the sequence of elements defined by `range2`.
4853 //
4854 // Complexity: At most `2 min(size(range1), size(range2))` applications of the
4855 // corresponding comparison and each projection, if any.
4856 //
4857 // Remarks: If two sequences have the same number of elements and their
4858 // corresponding elements (if any) are equivalent, then neither sequence is
4859 // lexicographically less than the other. If one sequence is a proper prefix of
4860 // the other, then the shorter sequence is lexicographically less than the
4861 // longer sequence. Otherwise, the lexicographical comparison of the sequences
4862 // yields the same result as the comparison of the first corresponding pair of
4863 // elements that are not equivalent.
4864 //
4865 // Reference:
4866 // https://wg21.link/alg.lex.comparison#:~:text=lexicographical_compare(R1
4867 template <typename Range1,
4868 typename Range2,
4869 typename Comp = ranges::less,
4870 typename Proj1 = identity,
4871 typename Proj2 = identity,
4872 typename = internal::range_category_t<Range1>,
4873 typename = internal::range_category_t<Range2>,
4874 typename = indirect_result_t<Comp&,
4875 projected<iterator_t<Range1>, Proj1>,
4876 projected<iterator_t<Range2>, Proj2>>,
4877 typename = indirect_result_t<Comp&,
4878 projected<iterator_t<Range2>, Proj2>,
4879 projected<iterator_t<Range1>, Proj1>>>
4880 constexpr bool lexicographical_compare(Range1&& range1,
4881 Range2&& range2,
4882 Comp comp = {},
4883 Proj1 proj1 = {},
4884 Proj2 proj2 = {}) {
4885 return ranges::lexicographical_compare(
4886 ranges::begin(range1), ranges::end(range1), ranges::begin(range2),
4887 ranges::end(range2), std::move(comp), std::move(proj1), std::move(proj2));
4888 }
4889
4890 // [alg.permutation.generators] Permutation generators
4891 // Reference: https://wg21.link/alg.permutation.generators
4892
4893 // Effects: Takes a sequence defined by the range `[first, last)` and transforms
4894 // it into the next permutation. The next permutation is found by assuming that
4895 // the set of all permutations is lexicographically sorted with respect to
4896 // `comp` and `proj`. If no such permutation exists, transforms the sequence
4897 // into the first permutation; that is, the ascendingly-sorted one.
4898 //
4899 // Returns: `true` if a next permutation was found and otherwise `false`.
4900 //
4901 // Complexity: At most `(last - first) / 2` swaps.
4902 //
4903 // Reference:
4904 // https://wg21.link/alg.permutation.generators#:~:text=next_permutation(I
4905 template <typename BidirectionalIterator,
4906 typename Comp = ranges::less,
4907 typename Proj = identity,
4908 typename = internal::iterator_category_t<BidirectionalIterator>,
4909 typename = indirect_result_t<Comp&,
4910 projected<BidirectionalIterator, Proj>,
4911 projected<BidirectionalIterator, Proj>>>
4912 constexpr auto next_permutation(BidirectionalIterator first,
4913 BidirectionalIterator last,
4914 Comp comp = {},
4915 Proj proj = {}) {
4916 return std::next_permutation(
4917 first, last, internal::ProjectedBinaryPredicate(comp, proj, proj));
4918 }
4919
4920 // Effects: Takes a sequence defined by `range` and transforms it into the next
4921 // permutation. The next permutation is found by assuming that the set of all
4922 // permutations is lexicographically sorted with respect to `comp` and `proj`.
4923 // If no such permutation exists, transforms the sequence into the first
4924 // permutation; that is, the ascendingly-sorted one.
4925 //
4926 // Returns: `true` if a next permutation was found and otherwise `false`.
4927 //
4928 // Complexity: At most `size(range) / 2` swaps.
4929 //
4930 // Reference:
4931 // https://wg21.link/alg.permutation.generators#:~:text=next_permutation(R
4932 template <typename Range,
4933 typename Comp = ranges::less,
4934 typename Proj = identity,
4935 typename = internal::range_category_t<Range>,
4936 typename = indirect_result_t<Comp&,
4937 projected<iterator_t<Range>, Proj>,
4938 projected<iterator_t<Range>, Proj>>>
4939 constexpr auto next_permutation(Range&& range, Comp comp = {}, Proj proj = {}) {
4940 return ranges::next_permutation(ranges::begin(range), ranges::end(range),
4941 std::move(comp), std::move(proj));
4942 }
4943
4944 // Effects: Takes a sequence defined by the range `[first, last)` and transforms
4945 // it into the previous permutation. The previous permutation is found by
4946 // assuming that the set of all permutations is lexicographically sorted with
4947 // respect to `comp` and `proj`. If no such permutation exists, transforms the
4948 // sequence into the last permutation; that is, the decreasingly-sorted one.
4949 //
4950 // Returns: `true` if a next permutation was found and otherwise `false`.
4951 //
4952 // Complexity: At most `(last - first) / 2` swaps.
4953 //
4954 // Reference:
4955 // https://wg21.link/alg.permutation.generators#:~:text=prev_permutation(I
4956 template <typename BidirectionalIterator,
4957 typename Comp = ranges::less,
4958 typename Proj = identity,
4959 typename = internal::iterator_category_t<BidirectionalIterator>,
4960 typename = indirect_result_t<Comp&,
4961 projected<BidirectionalIterator, Proj>,
4962 projected<BidirectionalIterator, Proj>>>
4963 constexpr auto prev_permutation(BidirectionalIterator first,
4964 BidirectionalIterator last,
4965 Comp comp = {},
4966 Proj proj = {}) {
4967 return std::prev_permutation(
4968 first, last, internal::ProjectedBinaryPredicate(comp, proj, proj));
4969 }
4970
4971 // Effects: Takes a sequence defined by `range` and transforms it into the
4972 // previous permutation. The previous permutation is found by assuming that the
4973 // set of all permutations is lexicographically sorted with respect to `comp`
4974 // and `proj`. If no such permutation exists, transforms the sequence into the
4975 // last permutation; that is, the decreasingly-sorted one.
4976 //
4977 // Returns: `true` if a previous permutation was found and otherwise `false`.
4978 //
4979 // Complexity: At most `size(range) / 2` swaps.
4980 //
4981 // Reference:
4982 // https://wg21.link/alg.permutation.generators#:~:text=prev_permutation(R
4983 template <typename Range,
4984 typename Comp = ranges::less,
4985 typename Proj = identity,
4986 typename = internal::range_category_t<Range>,
4987 typename = indirect_result_t<Comp&,
4988 projected<iterator_t<Range>, Proj>,
4989 projected<iterator_t<Range>, Proj>>>
4990 constexpr auto prev_permutation(Range&& range, Comp comp = {}, Proj proj = {}) {
4991 return ranges::prev_permutation(ranges::begin(range), ranges::end(range),
4992 std::move(comp), std::move(proj));
4993 }
4994
4995 } // namespace ranges
4996
4997 } // namespace base
4998
4999 #endif // BASE_RANGES_ALGORITHM_H_
5000