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