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