libstdc++
ranges_util.h
Go to the documentation of this file.
1// Utilities for representing and manipulating ranges -*- C++ -*-
2
3// Copyright (C) 2019-2023 Free Software Foundation, Inc.
4//
5// This file is part of the GNU ISO C++ Library. This library is free
6// software; you can redistribute it and/or modify it under the
7// terms of the GNU General Public License as published by the
8// Free Software Foundation; either version 3, or (at your option)
9// any later version.
10
11// This library is distributed in the hope that it will be useful,
12// but WITHOUT ANY WARRANTY; without even the implied warranty of
13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14// GNU General Public License for more details.
15
16// Under Section 7 of GPL version 3, you are granted additional
17// permissions described in the GCC Runtime Library Exception, version
18// 3.1, as published by the Free Software Foundation.
19
20// You should have received a copy of the GNU General Public License and
21// a copy of the GCC Runtime Library Exception along with this program;
22// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23// <http://www.gnu.org/licenses/>.
24
25/** @file bits/ranges_util.h
26 * This is an internal header file, included by other library headers.
27 * Do not attempt to use it directly. @headername{ranges}
28 */
29
30#ifndef _RANGES_UTIL_H
31#define _RANGES_UTIL_H 1
32
33#if __cplusplus > 201703L
34# include <bits/ranges_base.h>
35# include <bits/utility.h>
36
37#ifdef __cpp_lib_ranges
38namespace std _GLIBCXX_VISIBILITY(default)
39{
40_GLIBCXX_BEGIN_NAMESPACE_VERSION
41namespace ranges
42{
43 // C++20 24.5 [range.utility] Range utilities
44
45 namespace __detail
46 {
47 template<typename _Range>
48 concept __simple_view = view<_Range> && range<const _Range>
49 && same_as<iterator_t<_Range>, iterator_t<const _Range>>
50 && same_as<sentinel_t<_Range>, sentinel_t<const _Range>>;
51
52 template<typename _It>
53 concept __has_arrow = input_iterator<_It>
54 && (is_pointer_v<_It> || requires(_It __it) { __it.operator->(); });
55
56 using std::__detail::__different_from;
57 } // namespace __detail
58
59 /// The ranges::view_interface class template
60 template<typename _Derived>
61 requires is_class_v<_Derived> && same_as<_Derived, remove_cv_t<_Derived>>
63 {
64 private:
65 constexpr _Derived& _M_derived() noexcept
66 {
68 static_assert(view<_Derived>);
69 return static_cast<_Derived&>(*this);
70 }
71
72 constexpr const _Derived& _M_derived() const noexcept
73 {
75 static_assert(view<_Derived>);
76 return static_cast<const _Derived&>(*this);
77 }
78
79 static constexpr bool
80 _S_bool(bool) noexcept; // not defined
81
82 template<typename _Tp>
83 static constexpr bool
84 _S_empty(_Tp& __t)
85 noexcept(noexcept(_S_bool(ranges::begin(__t) == ranges::end(__t))))
86 { return ranges::begin(__t) == ranges::end(__t); }
87
88 template<typename _Tp>
89 static constexpr auto
90 _S_size(_Tp& __t)
91 noexcept(noexcept(ranges::end(__t) - ranges::begin(__t)))
92 { return ranges::end(__t) - ranges::begin(__t); }
93
94 public:
95 constexpr bool
96 empty()
97 noexcept(noexcept(_S_empty(_M_derived())))
99 { return _S_empty(_M_derived()); }
100
101 constexpr bool
102 empty()
103 noexcept(noexcept(ranges::size(_M_derived()) == 0))
104 requires sized_range<_Derived>
105 { return ranges::size(_M_derived()) == 0; }
106
107 constexpr bool
108 empty() const
109 noexcept(noexcept(_S_empty(_M_derived())))
111 { return _S_empty(_M_derived()); }
112
113 constexpr bool
114 empty() const
115 noexcept(noexcept(ranges::size(_M_derived()) == 0))
117 { return ranges::size(_M_derived()) == 0; }
118
119 constexpr explicit
120 operator bool() noexcept(noexcept(ranges::empty(_M_derived())))
121 requires requires { ranges::empty(_M_derived()); }
122 { return !ranges::empty(_M_derived()); }
123
124 constexpr explicit
125 operator bool() const noexcept(noexcept(ranges::empty(_M_derived())))
126 requires requires { ranges::empty(_M_derived()); }
127 { return !ranges::empty(_M_derived()); }
128
129 constexpr auto
130 data() noexcept(noexcept(ranges::begin(_M_derived())))
131 requires contiguous_iterator<iterator_t<_Derived>>
132 { return std::to_address(ranges::begin(_M_derived())); }
133
134 constexpr auto
135 data() const noexcept(noexcept(ranges::begin(_M_derived())))
136 requires range<const _Derived>
137 && contiguous_iterator<iterator_t<const _Derived>>
138 { return std::to_address(ranges::begin(_M_derived())); }
139
140 constexpr auto
141 size() noexcept(noexcept(_S_size(_M_derived())))
143 && sized_sentinel_for<sentinel_t<_Derived>, iterator_t<_Derived>>
144 { return _S_size(_M_derived()); }
145
146 constexpr auto
147 size() const noexcept(noexcept(_S_size(_M_derived())))
149 && sized_sentinel_for<sentinel_t<const _Derived>,
150 iterator_t<const _Derived>>
151 { return _S_size(_M_derived()); }
152
153 constexpr decltype(auto)
154 front() requires forward_range<_Derived>
155 {
156 __glibcxx_assert(!empty());
157 return *ranges::begin(_M_derived());
158 }
159
160 constexpr decltype(auto)
161 front() const requires forward_range<const _Derived>
162 {
163 __glibcxx_assert(!empty());
164 return *ranges::begin(_M_derived());
165 }
166
167 constexpr decltype(auto)
168 back()
170 {
171 __glibcxx_assert(!empty());
172 return *ranges::prev(ranges::end(_M_derived()));
173 }
174
175 constexpr decltype(auto)
176 back() const
179 {
180 __glibcxx_assert(!empty());
181 return *ranges::prev(ranges::end(_M_derived()));
182 }
183
184 template<random_access_range _Range = _Derived>
185 constexpr decltype(auto)
186 operator[](range_difference_t<_Range> __n)
187 { return ranges::begin(_M_derived())[__n]; }
188
189 template<random_access_range _Range = const _Derived>
190 constexpr decltype(auto)
191 operator[](range_difference_t<_Range> __n) const
192 { return ranges::begin(_M_derived())[__n]; }
193
194#if __cplusplus > 202002L
195 constexpr auto
197 { return ranges::cbegin(_M_derived()); }
198
199 constexpr auto
200 cbegin() const requires input_range<const _Derived>
201 { return ranges::cbegin(_M_derived()); }
202
203 constexpr auto
204 cend() requires input_range<_Derived>
205 { return ranges::cend(_M_derived()); }
206
207 constexpr auto
208 cend() const requires input_range<const _Derived>
209 { return ranges::cend(_M_derived()); }
210#endif
211 };
212
213 namespace __detail
214 {
215 template<typename _From, typename _To>
216 concept __uses_nonqualification_pointer_conversion
217 = is_pointer_v<_From> && is_pointer_v<_To>
220
221 template<typename _From, typename _To>
222 concept __convertible_to_non_slicing = convertible_to<_From, _To>
223 && !__uses_nonqualification_pointer_conversion<decay_t<_From>,
225
226 template<typename _Tp>
227 concept __pair_like
228 = !is_reference_v<_Tp> && requires(_Tp __t)
229 {
230 typename tuple_size<_Tp>::type;
232 typename tuple_element_t<0, remove_const_t<_Tp>>;
233 typename tuple_element_t<1, remove_const_t<_Tp>>;
235 { get<1>(__t) } -> convertible_to<const tuple_element_t<1, _Tp>&>;
236 };
237
238 template<typename _Tp, typename _Up, typename _Vp>
239 concept __pair_like_convertible_from
240 = !range<_Tp> && __pair_like<_Tp>
241 && constructible_from<_Tp, _Up, _Vp>
242 && __convertible_to_non_slicing<_Up, tuple_element_t<0, _Tp>>
243 && convertible_to<_Vp, tuple_element_t<1, _Tp>>;
244
245 } // namespace __detail
246
247 namespace views { struct _Drop; } // defined in <ranges>
248
249 enum class subrange_kind : bool { unsized, sized };
250
251 /// The ranges::subrange class template
252 template<input_or_output_iterator _It, sentinel_for<_It> _Sent = _It,
253 subrange_kind _Kind = sized_sentinel_for<_Sent, _It>
254 ? subrange_kind::sized : subrange_kind::unsized>
255 requires (_Kind == subrange_kind::sized || !sized_sentinel_for<_Sent, _It>)
257 {
258 private:
259 static constexpr bool _S_store_size
260 = _Kind == subrange_kind::sized && !sized_sentinel_for<_Sent, _It>;
261
262 friend struct views::_Drop; // Needs to inspect _S_store_size.
263
264 _It _M_begin = _It();
265 [[no_unique_address]] _Sent _M_end = _Sent();
266
267 using __size_type
268 = __detail::__make_unsigned_like_t<iter_difference_t<_It>>;
269
270 template<typename _Tp, bool = _S_store_size>
271 struct _Size
272 {
273 [[__gnu__::__always_inline__]]
274 constexpr _Size(_Tp = {}) { }
275 };
276
277 template<typename _Tp>
278 struct _Size<_Tp, true>
279 {
280 [[__gnu__::__always_inline__]]
281 constexpr _Size(_Tp __s = {}) : _M_size(__s) { }
282
283 _Tp _M_size;
284 };
285
286 [[no_unique_address]] _Size<__size_type> _M_size = {};
287
288 public:
289 subrange() requires default_initializable<_It> = default;
290
291 constexpr
292 subrange(__detail::__convertible_to_non_slicing<_It> auto __i, _Sent __s)
293 noexcept(is_nothrow_constructible_v<_It, decltype(__i)>
294 && is_nothrow_constructible_v<_Sent, _Sent&>)
295 requires (!_S_store_size)
296 : _M_begin(std::move(__i)), _M_end(__s)
297 { }
298
299 constexpr
300 subrange(__detail::__convertible_to_non_slicing<_It> auto __i, _Sent __s,
301 __size_type __n)
302 noexcept(is_nothrow_constructible_v<_It, decltype(__i)>
303 && is_nothrow_constructible_v<_Sent, _Sent&>)
304 requires (_Kind == subrange_kind::sized)
305 : _M_begin(std::move(__i)), _M_end(__s), _M_size(__n)
306 { }
307
308 template<__detail::__different_from<subrange> _Rng>
309 requires borrowed_range<_Rng>
310 && __detail::__convertible_to_non_slicing<iterator_t<_Rng>, _It>
312 constexpr
313 subrange(_Rng&& __r)
314 noexcept(noexcept(subrange(__r, ranges::size(__r))))
315 requires _S_store_size && sized_range<_Rng>
316 : subrange(__r, ranges::size(__r))
317 { }
318
319 template<__detail::__different_from<subrange> _Rng>
320 requires borrowed_range<_Rng>
321 && __detail::__convertible_to_non_slicing<iterator_t<_Rng>, _It>
323 constexpr
324 subrange(_Rng&& __r)
325 noexcept(noexcept(subrange(ranges::begin(__r), ranges::end(__r))))
326 requires (!_S_store_size)
327 : subrange(ranges::begin(__r), ranges::end(__r))
328 { }
329
330 template<borrowed_range _Rng>
331 requires __detail::__convertible_to_non_slicing<iterator_t<_Rng>, _It>
333 constexpr
334 subrange(_Rng&& __r, __size_type __n)
335 noexcept(noexcept(subrange(ranges::begin(__r), ranges::end(__r), __n)))
336 requires (_Kind == subrange_kind::sized)
337 : subrange{ranges::begin(__r), ranges::end(__r), __n}
338 { }
339
340 template<__detail::__different_from<subrange> _PairLike>
341 requires __detail::__pair_like_convertible_from<_PairLike, const _It&,
342 const _Sent&>
343 constexpr
344 operator _PairLike() const
345 { return _PairLike(_M_begin, _M_end); }
346
347 constexpr _It
348 begin() const requires copyable<_It>
349 { return _M_begin; }
350
351 [[nodiscard]] constexpr _It
352 begin() requires (!copyable<_It>)
353 { return std::move(_M_begin); }
354
355 constexpr _Sent end() const { return _M_end; }
356
357 constexpr bool empty() const { return _M_begin == _M_end; }
358
359 constexpr __size_type
360 size() const requires (_Kind == subrange_kind::sized)
361 {
362 if constexpr (_S_store_size)
363 return _M_size._M_size;
364 else
365 return __detail::__to_unsigned_like(_M_end - _M_begin);
366 }
367
368 [[nodiscard]] constexpr subrange
369 next(iter_difference_t<_It> __n = 1) const &
370 requires forward_iterator<_It>
371 {
372 auto __tmp = *this;
373 __tmp.advance(__n);
374 return __tmp;
375 }
376
377 [[nodiscard]] constexpr subrange
378 next(iter_difference_t<_It> __n = 1) &&
379 {
380 advance(__n);
381 return std::move(*this);
382 }
383
384 [[nodiscard]] constexpr subrange
385 prev(iter_difference_t<_It> __n = 1) const
386 requires bidirectional_iterator<_It>
387 {
388 auto __tmp = *this;
389 __tmp.advance(-__n);
390 return __tmp;
391 }
392
393 constexpr subrange&
394 advance(iter_difference_t<_It> __n)
395 {
396 // _GLIBCXX_RESOLVE_LIB_DEFECTS
397 // 3433. subrange::advance(n) has UB when n < 0
398 if constexpr (bidirectional_iterator<_It>)
399 if (__n < 0)
400 {
401 ranges::advance(_M_begin, __n);
402 if constexpr (_S_store_size)
403 _M_size._M_size += __detail::__to_unsigned_like(-__n);
404 return *this;
405 }
406
407 __glibcxx_assert(__n >= 0);
408 auto __d = __n - ranges::advance(_M_begin, __n, _M_end);
409 if constexpr (_S_store_size)
410 _M_size._M_size -= __detail::__to_unsigned_like(__d);
411 return *this;
412 }
413 };
414
415 template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
416 subrange(_It, _Sent) -> subrange<_It, _Sent>;
417
418 template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
419 subrange(_It, _Sent,
420 __detail::__make_unsigned_like_t<iter_difference_t<_It>>)
422
423 template<borrowed_range _Rng>
424 subrange(_Rng&&)
425 -> subrange<iterator_t<_Rng>, sentinel_t<_Rng>,
427 || sized_sentinel_for<sentinel_t<_Rng>, iterator_t<_Rng>>)
428 ? subrange_kind::sized : subrange_kind::unsized>;
429
430 template<borrowed_range _Rng>
431 subrange(_Rng&&,
432 __detail::__make_unsigned_like_t<range_difference_t<_Rng>>)
433 -> subrange<iterator_t<_Rng>, sentinel_t<_Rng>, subrange_kind::sized>;
434
435 // _GLIBCXX_RESOLVE_LIB_DEFECTS
436 // 3589. The const lvalue reference overload of get for subrange does not
437 // constrain I to be copyable when N == 0
438 template<size_t _Num, class _It, class _Sent, subrange_kind _Kind>
439 requires ((_Num == 0 && copyable<_It>) || _Num == 1)
440 constexpr auto
441 get(const subrange<_It, _Sent, _Kind>& __r)
442 {
443 if constexpr (_Num == 0)
444 return __r.begin();
445 else
446 return __r.end();
447 }
448
449 template<size_t _Num, class _It, class _Sent, subrange_kind _Kind>
450 requires (_Num < 2)
451 constexpr auto
452 get(subrange<_It, _Sent, _Kind>&& __r)
453 {
454 if constexpr (_Num == 0)
455 return __r.begin();
456 else
457 return __r.end();
458 }
459
460 template<typename _It, typename _Sent, subrange_kind _Kind>
461 inline constexpr bool
462 enable_borrowed_range<subrange<_It, _Sent, _Kind>> = true;
463
464 template<range _Range>
465 using borrowed_subrange_t = __conditional_t<borrowed_range<_Range>,
466 subrange<iterator_t<_Range>>,
467 dangling>;
468} // namespace ranges
469
470// The following ranges algorithms are used by <ranges>, and are defined here
471// so that <ranges> can avoid including all of <bits/ranges_algo.h>.
472namespace ranges
473{
474 struct __find_fn
475 {
476 template<input_iterator _Iter, sentinel_for<_Iter> _Sent, typename _Tp,
477 typename _Proj = identity>
478 requires indirect_binary_predicate<ranges::equal_to,
479 projected<_Iter, _Proj>, const _Tp*>
480 constexpr _Iter
481 operator()(_Iter __first, _Sent __last,
482 const _Tp& __value, _Proj __proj = {}) const
483 {
484 while (__first != __last
485 && !(std::__invoke(__proj, *__first) == __value))
486 ++__first;
487 return __first;
488 }
489
490 template<input_range _Range, typename _Tp, typename _Proj = identity>
491 requires indirect_binary_predicate<ranges::equal_to,
492 projected<iterator_t<_Range>, _Proj>,
493 const _Tp*>
494 constexpr borrowed_iterator_t<_Range>
495 operator()(_Range&& __r, const _Tp& __value, _Proj __proj = {}) const
496 {
497 return (*this)(ranges::begin(__r), ranges::end(__r),
498 __value, std::move(__proj));
499 }
500 };
501
502 inline constexpr __find_fn find{};
503
504 struct __find_if_fn
505 {
506 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
507 typename _Proj = identity,
508 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
509 constexpr _Iter
510 operator()(_Iter __first, _Sent __last,
511 _Pred __pred, _Proj __proj = {}) const
512 {
513 while (__first != __last
514 && !(bool)std::__invoke(__pred, std::__invoke(__proj, *__first)))
515 ++__first;
516 return __first;
517 }
518
519 template<input_range _Range, typename _Proj = identity,
520 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
521 _Pred>
522 constexpr borrowed_iterator_t<_Range>
523 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const
524 {
525 return (*this)(ranges::begin(__r), ranges::end(__r),
526 std::move(__pred), std::move(__proj));
527 }
528 };
529
530 inline constexpr __find_if_fn find_if{};
531
532 struct __find_if_not_fn
533 {
534 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
535 typename _Proj = identity,
536 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
537 constexpr _Iter
538 operator()(_Iter __first, _Sent __last,
539 _Pred __pred, _Proj __proj = {}) const
540 {
541 while (__first != __last
542 && (bool)std::__invoke(__pred, std::__invoke(__proj, *__first)))
543 ++__first;
544 return __first;
545 }
546
547 template<input_range _Range, typename _Proj = identity,
548 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
549 _Pred>
550 constexpr borrowed_iterator_t<_Range>
551 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const
552 {
553 return (*this)(ranges::begin(__r), ranges::end(__r),
554 std::move(__pred), std::move(__proj));
555 }
556 };
557
558 inline constexpr __find_if_not_fn find_if_not{};
559
560 template<typename _Iter1, typename _Iter2>
561 struct in_in_result
562 {
563 [[no_unique_address]] _Iter1 in1;
564 [[no_unique_address]] _Iter2 in2;
565
566 template<typename _IIter1, typename _IIter2>
567 requires convertible_to<const _Iter1&, _IIter1>
568 && convertible_to<const _Iter2&, _IIter2>
569 constexpr
570 operator in_in_result<_IIter1, _IIter2>() const &
571 { return {in1, in2}; }
572
573 template<typename _IIter1, typename _IIter2>
574 requires convertible_to<_Iter1, _IIter1>
575 && convertible_to<_Iter2, _IIter2>
576 constexpr
577 operator in_in_result<_IIter1, _IIter2>() &&
578 { return {std::move(in1), std::move(in2)}; }
579 };
580
581 template<typename _Iter1, typename _Iter2>
582 using mismatch_result = in_in_result<_Iter1, _Iter2>;
583
584 struct __mismatch_fn
585 {
586 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
587 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
588 typename _Pred = ranges::equal_to,
589 typename _Proj1 = identity, typename _Proj2 = identity>
590 requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2>
591 constexpr mismatch_result<_Iter1, _Iter2>
592 operator()(_Iter1 __first1, _Sent1 __last1,
593 _Iter2 __first2, _Sent2 __last2, _Pred __pred = {},
594 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
595 {
596 while (__first1 != __last1 && __first2 != __last2
597 && (bool)std::__invoke(__pred,
598 std::__invoke(__proj1, *__first1),
599 std::__invoke(__proj2, *__first2)))
600 {
601 ++__first1;
602 ++__first2;
603 }
604 return { std::move(__first1), std::move(__first2) };
605 }
606
607 template<input_range _Range1, input_range _Range2,
608 typename _Pred = ranges::equal_to,
609 typename _Proj1 = identity, typename _Proj2 = identity>
610 requires indirectly_comparable<iterator_t<_Range1>, iterator_t<_Range2>,
611 _Pred, _Proj1, _Proj2>
612 constexpr mismatch_result<iterator_t<_Range1>, iterator_t<_Range2>>
613 operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {},
614 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
615 {
616 return (*this)(ranges::begin(__r1), ranges::end(__r1),
617 ranges::begin(__r2), ranges::end(__r2),
618 std::move(__pred),
619 std::move(__proj1), std::move(__proj2));
620 }
621 };
622
623 inline constexpr __mismatch_fn mismatch{};
624
625 struct __search_fn
626 {
627 template<forward_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
628 forward_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
629 typename _Pred = ranges::equal_to,
630 typename _Proj1 = identity, typename _Proj2 = identity>
631 requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2>
632 constexpr subrange<_Iter1>
633 operator()(_Iter1 __first1, _Sent1 __last1,
634 _Iter2 __first2, _Sent2 __last2, _Pred __pred = {},
635 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
636 {
637 if (__first1 == __last1 || __first2 == __last2)
638 return {__first1, __first1};
639
640 for (;;)
641 {
642 for (;;)
643 {
644 if (__first1 == __last1)
645 return {__first1, __first1};
646 if (std::__invoke(__pred,
647 std::__invoke(__proj1, *__first1),
648 std::__invoke(__proj2, *__first2)))
649 break;
650 ++__first1;
651 }
652 auto __cur1 = __first1;
653 auto __cur2 = __first2;
654 for (;;)
655 {
656 if (++__cur2 == __last2)
657 return {__first1, ++__cur1};
658 if (++__cur1 == __last1)
659 return {__cur1, __cur1};
660 if (!(bool)std::__invoke(__pred,
661 std::__invoke(__proj1, *__cur1),
662 std::__invoke(__proj2, *__cur2)))
663 {
664 ++__first1;
665 break;
666 }
667 }
668 }
669 }
670
671 template<forward_range _Range1, forward_range _Range2,
672 typename _Pred = ranges::equal_to,
673 typename _Proj1 = identity, typename _Proj2 = identity>
674 requires indirectly_comparable<iterator_t<_Range1>, iterator_t<_Range2>,
675 _Pred, _Proj1, _Proj2>
676 constexpr borrowed_subrange_t<_Range1>
677 operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {},
678 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
679 {
680 return (*this)(ranges::begin(__r1), ranges::end(__r1),
681 ranges::begin(__r2), ranges::end(__r2),
682 std::move(__pred),
683 std::move(__proj1), std::move(__proj2));
684 }
685 };
686
687 inline constexpr __search_fn search{};
688
689 struct __min_fn
690 {
691 template<typename _Tp, typename _Proj = identity,
692 indirect_strict_weak_order<projected<const _Tp*, _Proj>>
693 _Comp = ranges::less>
694 constexpr const _Tp&
695 operator()(const _Tp& __a, const _Tp& __b,
696 _Comp __comp = {}, _Proj __proj = {}) const
697 {
698 if (std::__invoke(__comp,
699 std::__invoke(__proj, __b),
700 std::__invoke(__proj, __a)))
701 return __b;
702 else
703 return __a;
704 }
705
706 template<input_range _Range, typename _Proj = identity,
707 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
708 _Comp = ranges::less>
709 requires indirectly_copyable_storable<iterator_t<_Range>,
710 range_value_t<_Range>*>
711 constexpr range_value_t<_Range>
712 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
713 {
714 auto __first = ranges::begin(__r);
715 auto __last = ranges::end(__r);
716 __glibcxx_assert(__first != __last);
717 auto __result = *__first;
718 while (++__first != __last)
719 {
720 auto __tmp = *__first;
721 if (std::__invoke(__comp,
722 std::__invoke(__proj, __tmp),
723 std::__invoke(__proj, __result)))
724 __result = std::move(__tmp);
725 }
726 return __result;
727 }
728
729 template<copyable _Tp, typename _Proj = identity,
730 indirect_strict_weak_order<projected<const _Tp*, _Proj>>
731 _Comp = ranges::less>
732 constexpr _Tp
733 operator()(initializer_list<_Tp> __r,
734 _Comp __comp = {}, _Proj __proj = {}) const
735 {
736 return (*this)(ranges::subrange(__r),
737 std::move(__comp), std::move(__proj));
738 }
739 };
740
741 inline constexpr __min_fn min{};
742
743 struct __adjacent_find_fn
744 {
745 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
746 typename _Proj = identity,
747 indirect_binary_predicate<projected<_Iter, _Proj>,
748 projected<_Iter, _Proj>> _Pred
749 = ranges::equal_to>
750 constexpr _Iter
751 operator()(_Iter __first, _Sent __last,
752 _Pred __pred = {}, _Proj __proj = {}) const
753 {
754 if (__first == __last)
755 return __first;
756 auto __next = __first;
757 for (; ++__next != __last; __first = __next)
758 {
759 if (std::__invoke(__pred,
760 std::__invoke(__proj, *__first),
761 std::__invoke(__proj, *__next)))
762 return __first;
763 }
764 return __next;
765 }
766
767 template<forward_range _Range, typename _Proj = identity,
768 indirect_binary_predicate<
769 projected<iterator_t<_Range>, _Proj>,
770 projected<iterator_t<_Range>, _Proj>> _Pred = ranges::equal_to>
771 constexpr borrowed_iterator_t<_Range>
772 operator()(_Range&& __r, _Pred __pred = {}, _Proj __proj = {}) const
773 {
774 return (*this)(ranges::begin(__r), ranges::end(__r),
775 std::move(__pred), std::move(__proj));
776 }
777 };
778
779 inline constexpr __adjacent_find_fn adjacent_find{};
780
781} // namespace ranges
782
783 using ranges::get;
784
785 template<typename _Iter, typename _Sent, ranges::subrange_kind _Kind>
786 struct tuple_size<ranges::subrange<_Iter, _Sent, _Kind>>
787 : integral_constant<size_t, 2>
788 { };
789
790 template<typename _Iter, typename _Sent, ranges::subrange_kind _Kind>
791 struct tuple_element<0, ranges::subrange<_Iter, _Sent, _Kind>>
792 { using type = _Iter; };
793
794 template<typename _Iter, typename _Sent, ranges::subrange_kind _Kind>
795 struct tuple_element<1, ranges::subrange<_Iter, _Sent, _Kind>>
796 { using type = _Sent; };
797
798 template<typename _Iter, typename _Sent, ranges::subrange_kind _Kind>
799 struct tuple_element<0, const ranges::subrange<_Iter, _Sent, _Kind>>
800 { using type = _Iter; };
801
802 template<typename _Iter, typename _Sent, ranges::subrange_kind _Kind>
803 struct tuple_element<1, const ranges::subrange<_Iter, _Sent, _Kind>>
804 { using type = _Sent; };
805
806_GLIBCXX_END_NAMESPACE_VERSION
807} // namespace std
808#endif // library concepts
809#endif // C++20
810#endif // _RANGES_UTIL_H
constexpr _Tp * to_address(_Tp *__ptr) noexcept
Obtain address referenced by a pointer to an object.
Definition: ptr_traits.h:250
typename remove_pointer< _Tp >::type remove_pointer_t
Alias template for remove_pointer.
Definition: type_traits:2065
typename decay< _Tp >::type decay_t
Alias template for decay.
Definition: type_traits:2610
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
Definition: move.h:97
constexpr __invoke_result< _Callable, _Args... >::type __invoke(_Callable &&__fn, _Args &&... __args) noexcept(__is_nothrow_invocable< _Callable, _Args... >::value)
Invoke a callable object.
Definition: invoke.h:90
_Tp * end(valarray< _Tp > &__va) noexcept
Return an iterator pointing to one past the last element of the valarray.
Definition: valarray:1249
_Tp * begin(valarray< _Tp > &__va) noexcept
Return an iterator pointing to the first element of the valarray.
Definition: valarray:1227
constexpr const _Tp & min(const _Tp &, const _Tp &)
This does what you think it does.
Definition: stl_algobase.h:233
ISO C++ entities toplevel namespace is std.
constexpr auto cend(const _Container &__cont) noexcept(noexcept(std::end(__cont))) -> decltype(std::end(__cont))
Return an iterator pointing to one past the last element of the const container.
Definition: range_access.h:138
constexpr auto empty(const _Container &__cont) noexcept(noexcept(__cont.empty())) -> decltype(__cont.empty())
Return whether a container is empty.
Definition: range_access.h:284
constexpr auto size(const _Container &__cont) noexcept(noexcept(__cont.size())) -> decltype(__cont.size())
Return the size of a container.
Definition: range_access.h:264
constexpr void advance(_InputIterator &__i, _Distance __n)
A generalization of pointer arithmetic.
constexpr auto cbegin(const _Container &__cont) noexcept(noexcept(std::begin(__cont))) -> decltype(std::begin(__cont))
Return an iterator pointing to the first element of the const container.
Definition: range_access.h:126
The ranges::view_interface class template.
Definition: ranges_util.h:63
The ranges::subrange class template.
Definition: ranges_util.h:257
Finds the size of a given tuple type.
Definition: utility.h:49
[concept.derived], concept derived_from
Definition: concepts:67
[concept.convertible], concept convertible_to
Definition: concepts:72
[concept.defaultinitializable], concept default_initializable
Definition: concepts:157
[range.range] The range concept.
Definition: ranges_base.h:501
[range.range] The borrowed_range concept.
Definition: ranges_base.h:510
[range.sized] The sized_range concept.
Definition: ranges_base.h:544
[range.view] The ranges::view concept.
Definition: ranges_base.h:579
A range for which ranges::begin returns an input iterator.
Definition: ranges_base.h:590
A range for which ranges::begin returns a forward iterator.
Definition: ranges_base.h:595
A range for which ranges::begin returns a bidirectional iterator.
Definition: ranges_base.h:600
A range for which ranges::begin and ranges::end return the same type.
Definition: ranges_base.h:619