1// Core concepts and definitions for <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_base.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 _GLIBCXX_RANGES_BASE_H
31#define _GLIBCXX_RANGES_BASE_H 1
32
33#ifdef _GLIBCXX_SYSHDR
34#pragma GCC system_header
35#endif
36
37#if __cplusplus > 201703L
38#include <initializer_list>
39#include <bits/stl_iterator.h>
40#include <ext/numeric_traits.h>
41#include <bits/max_size_type.h>
42#include <bits/version.h>
43
44#if __glibcxx_containers_ranges // C++ >= 23
45# include <bits/utility.h> // for tuple_element_t
46#endif
47
48#pragma GCC diagnostic push
49#pragma GCC diagnostic ignored "-Wpedantic" // __int128
50
51#if __glibcxx_algorithm_default_value_type // C++ >= 26
52# define _GLIBCXX26_RANGE_ALGO_DEF_VAL_T(_I, _P) = projected_value_t<_I, _P>
53#else
54# define _GLIBCXX26_RANGE_ALGO_DEF_VAL_T(_I, _P)
55#endif
56
57#ifdef __cpp_lib_concepts
58namespace std _GLIBCXX_VISIBILITY(default)
59{
60_GLIBCXX_BEGIN_NAMESPACE_VERSION
61namespace ranges
62{
63 template<typename>
64 inline constexpr bool disable_sized_range = false;
65
66 template<typename _Tp>
67 inline constexpr bool enable_borrowed_range = false;
68
69 namespace __detail
70 {
71 constexpr __max_size_type
72 __to_unsigned_like(__max_size_type __t) noexcept
73 { return __t; }
74
75 constexpr __max_size_type
76 __to_unsigned_like(__max_diff_type __t) noexcept
77 { return __max_size_type(__t); }
78
79 template<integral _Tp>
80 constexpr auto
81 __to_unsigned_like(_Tp __t) noexcept
82 { return static_cast<make_unsigned_t<_Tp>>(__t); }
83
84#if defined __STRICT_ANSI__ && defined __SIZEOF_INT128__
85 constexpr unsigned __int128
86 __to_unsigned_like(__int128 __t) noexcept
87 { return __t; }
88
89 constexpr unsigned __int128
90 __to_unsigned_like(unsigned __int128 __t) noexcept
91 { return __t; }
92#endif
93
94 template<typename _Tp>
95 using __make_unsigned_like_t
96 = decltype(__detail::__to_unsigned_like(std::declval<_Tp>()));
97
98 // Part of the constraints of ranges::borrowed_range
99 template<typename _Tp>
100 concept __maybe_borrowed_range
101 = is_lvalue_reference_v<_Tp>
102 || enable_borrowed_range<remove_cvref_t<_Tp>>;
103
104 } // namespace __detail
105
106 // Namespace for helpers for the <ranges> customization points.
107 namespace __access
108 {
109 using std::ranges::__detail::__maybe_borrowed_range;
110 using std::__detail::__range_iter_t;
111
112 struct _Begin
113 {
114 private:
115 template<typename _Tp>
116 static constexpr bool
117 _S_noexcept()
118 {
119 if constexpr (is_array_v<remove_reference_t<_Tp>>)
120 return true;
121 else if constexpr (__member_begin<_Tp>)
122 return noexcept(__decay_copy(std::declval<_Tp&>().begin()));
123 else
124 return noexcept(__decay_copy(begin(std::declval<_Tp&>())));
125 }
126
127 public:
128 template<__maybe_borrowed_range _Tp>
129 requires is_array_v<remove_reference_t<_Tp>> || __member_begin<_Tp>
130 || __adl_begin<_Tp>
131 constexpr auto
132 operator()[[nodiscard]](_Tp&& __t) const noexcept(_S_noexcept<_Tp&>())
133 {
134 if constexpr (is_array_v<remove_reference_t<_Tp>>)
135 {
136 static_assert(is_lvalue_reference_v<_Tp>);
137 return __t + 0;
138 }
139 else if constexpr (__member_begin<_Tp>)
140 return __t.begin();
141 else
142 return begin(__t);
143 }
144 };
145
146 template<typename _Tp>
147 concept __member_end = requires(_Tp& __t)
148 {
149 { __decay_copy(__t.end()) } -> sentinel_for<__range_iter_t<_Tp>>;
150 };
151
152 // Poison pill so that unqualified lookup doesn't find std::end.
153 void end() = delete;
154
155 template<typename _Tp>
156 concept __adl_end = __class_or_enum<remove_reference_t<_Tp>>
157 && requires(_Tp& __t)
158 {
159 { __decay_copy(end(__t)) } -> sentinel_for<__range_iter_t<_Tp>>;
160 };
161
162 struct _End
163 {
164 private:
165 template<typename _Tp>
166 static constexpr bool
167 _S_noexcept()
168 {
169 if constexpr (is_bounded_array_v<remove_reference_t<_Tp>>)
170 return true;
171 else if constexpr (__member_end<_Tp>)
172 return noexcept(__decay_copy(std::declval<_Tp&>().end()));
173 else
174 return noexcept(__decay_copy(end(std::declval<_Tp&>())));
175 }
176
177 public:
178 template<__maybe_borrowed_range _Tp>
179 requires is_bounded_array_v<remove_reference_t<_Tp>>
180 || __member_end<_Tp> || __adl_end<_Tp>
181 constexpr auto
182 operator()[[nodiscard]](_Tp&& __t) const noexcept(_S_noexcept<_Tp&>())
183 {
184 if constexpr (is_bounded_array_v<remove_reference_t<_Tp>>)
185 {
186 static_assert(is_lvalue_reference_v<_Tp>);
187 return __t + extent_v<remove_reference_t<_Tp>>;
188 }
189 else if constexpr (__member_end<_Tp>)
190 return __t.end();
191 else
192 return end(__t);
193 }
194 };
195
196 template<typename _Tp>
197 concept __member_rbegin = requires(_Tp& __t)
198 {
199 { __decay_copy(__t.rbegin()) } -> input_or_output_iterator;
200 };
201
202 void rbegin() = delete;
203
204 template<typename _Tp>
205 concept __adl_rbegin = __class_or_enum<remove_reference_t<_Tp>>
206 && requires(_Tp& __t)
207 {
208 { __decay_copy(rbegin(__t)) } -> input_or_output_iterator;
209 };
210
211 template<typename _Tp>
212 concept __reversable = requires(_Tp& __t)
213 {
214 { _Begin{}(__t) } -> bidirectional_iterator;
215 { _End{}(__t) } -> same_as<decltype(_Begin{}(__t))>;
216 };
217
218 struct _RBegin
219 {
220 private:
221 template<typename _Tp>
222 static constexpr bool
223 _S_noexcept()
224 {
225 if constexpr (__member_rbegin<_Tp>)
226 return noexcept(__decay_copy(std::declval<_Tp&>().rbegin()));
227 else if constexpr (__adl_rbegin<_Tp>)
228 return noexcept(__decay_copy(rbegin(std::declval<_Tp&>())));
229 else
230 {
231 if constexpr (noexcept(_End{}(std::declval<_Tp&>())))
232 {
233 using _It = decltype(_End{}(std::declval<_Tp&>()));
234 // std::reverse_iterator copy-initializes its member.
235 return is_nothrow_copy_constructible_v<_It>;
236 }
237 else
238 return false;
239 }
240 }
241
242 public:
243 template<__maybe_borrowed_range _Tp>
244 requires __member_rbegin<_Tp> || __adl_rbegin<_Tp> || __reversable<_Tp>
245 constexpr auto
246 operator()[[nodiscard]](_Tp&& __t) const
247 noexcept(_S_noexcept<_Tp&>())
248 {
249 if constexpr (__member_rbegin<_Tp>)
250 return __t.rbegin();
251 else if constexpr (__adl_rbegin<_Tp>)
252 return rbegin(__t);
253 else
254 return std::make_reverse_iterator(_End{}(__t));
255 }
256 };
257
258 template<typename _Tp>
259 concept __member_rend = requires(_Tp& __t)
260 {
261 { __decay_copy(__t.rend()) }
262 -> sentinel_for<decltype(_RBegin{}(std::forward<_Tp>(__t)))>;
263 };
264
265 void rend() = delete;
266
267 template<typename _Tp>
268 concept __adl_rend = __class_or_enum<remove_reference_t<_Tp>>
269 && requires(_Tp& __t)
270 {
271 { __decay_copy(rend(__t)) }
272 -> sentinel_for<decltype(_RBegin{}(std::forward<_Tp>(__t)))>;
273 };
274
275 struct _REnd
276 {
277 private:
278 template<typename _Tp>
279 static constexpr bool
280 _S_noexcept()
281 {
282 if constexpr (__member_rend<_Tp>)
283 return noexcept(__decay_copy(std::declval<_Tp&>().rend()));
284 else if constexpr (__adl_rend<_Tp>)
285 return noexcept(__decay_copy(rend(std::declval<_Tp&>())));
286 else
287 {
288 if constexpr (noexcept(_Begin{}(std::declval<_Tp&>())))
289 {
290 using _It = decltype(_Begin{}(std::declval<_Tp&>()));
291 // std::reverse_iterator copy-initializes its member.
292 return is_nothrow_copy_constructible_v<_It>;
293 }
294 else
295 return false;
296 }
297 }
298
299 public:
300 template<__maybe_borrowed_range _Tp>
301 requires __member_rend<_Tp> || __adl_rend<_Tp> || __reversable<_Tp>
302 constexpr auto
303 operator()[[nodiscard]](_Tp&& __t) const
304 noexcept(_S_noexcept<_Tp&>())
305 {
306 if constexpr (__member_rend<_Tp>)
307 return __t.rend();
308 else if constexpr (__adl_rend<_Tp>)
309 return rend(__t);
310 else
311 return std::make_reverse_iterator(_Begin{}(__t));
312 }
313 };
314
315 template<typename _Tp>
316 concept __member_size = !disable_sized_range<remove_cvref_t<_Tp>>
317 && requires(_Tp& __t)
318 {
319 { __decay_copy(__t.size()) } -> __detail::__is_integer_like;
320 };
321
322 void size() = delete;
323
324 template<typename _Tp>
325 concept __adl_size = __class_or_enum<remove_reference_t<_Tp>>
326 && !disable_sized_range<remove_cvref_t<_Tp>>
327 && requires(_Tp& __t)
328 {
329 { __decay_copy(size(__t)) } -> __detail::__is_integer_like;
330 };
331
332 template<typename _Tp>
333 concept __sentinel_size = requires(_Tp& __t)
334 {
335 requires (!is_unbounded_array_v<remove_reference_t<_Tp>>);
336
337 { _Begin{}(__t) } -> forward_iterator;
338
339 { _End{}(__t) } -> sized_sentinel_for<decltype(_Begin{}(__t))>;
340
341 __detail::__to_unsigned_like(_End{}(__t) - _Begin{}(__t));
342 };
343
344 struct _Size
345 {
346 private:
347 template<typename _Tp>
348 static constexpr bool
349 _S_noexcept()
350 {
351 if constexpr (is_bounded_array_v<remove_reference_t<_Tp>>)
352 return true;
353 else if constexpr (__member_size<_Tp>)
354 return noexcept(__decay_copy(std::declval<_Tp&>().size()));
355 else if constexpr (__adl_size<_Tp>)
356 return noexcept(__decay_copy(size(std::declval<_Tp&>())));
357 else if constexpr (__sentinel_size<_Tp>)
358 return noexcept(_End{}(std::declval<_Tp&>())
359 - _Begin{}(std::declval<_Tp&>()));
360 }
361
362 public:
363 template<typename _Tp>
364 requires is_bounded_array_v<remove_reference_t<_Tp>>
365 || __member_size<_Tp> || __adl_size<_Tp> || __sentinel_size<_Tp>
366 constexpr auto
367 operator()[[nodiscard]](_Tp&& __t) const noexcept(_S_noexcept<_Tp&>())
368 {
369 if constexpr (is_bounded_array_v<remove_reference_t<_Tp>>)
370 return extent_v<remove_reference_t<_Tp>>;
371 else if constexpr (__member_size<_Tp>)
372 return __t.size();
373 else if constexpr (__adl_size<_Tp>)
374 return size(__t);
375 else if constexpr (__sentinel_size<_Tp>)
376 return __detail::__to_unsigned_like(_End{}(__t) - _Begin{}(__t));
377 }
378 };
379
380 struct _SSize
381 {
382 // _GLIBCXX_RESOLVE_LIB_DEFECTS
383 // 3403. Domain of ranges::ssize(E) doesn't match ranges::size(E)
384 template<typename _Tp>
385 requires requires (_Tp& __t) { _Size{}(__t); }
386 constexpr auto
387 operator()[[nodiscard]](_Tp&& __t) const noexcept(noexcept(_Size{}(__t)))
388 {
389 auto __size = _Size{}(__t);
390 using __size_type = decltype(__size);
391 // Return the wider of ptrdiff_t and make-signed-like-t<__size_type>.
392 if constexpr (integral<__size_type>)
393 {
394 using __gnu_cxx::__int_traits;
395 if constexpr (__int_traits<__size_type>::__digits
396 < __int_traits<ptrdiff_t>::__digits)
397 return static_cast<ptrdiff_t>(__size);
398 else
399 return static_cast<make_signed_t<__size_type>>(__size);
400 }
401#if defined __STRICT_ANSI__ && defined __SIZEOF_INT128__
402 // For strict-ansi modes integral<__int128> is false
403 else if constexpr (__detail::__is_int128<__size_type>)
404 return static_cast<__int128>(__size);
405#endif
406 else // Must be one of __max_diff_type or __max_size_type.
407 return __detail::__max_diff_type(__size);
408 }
409 };
410
411 template<typename _Tp>
412 concept __member_empty = requires(_Tp& __t) { bool(__t.empty()); };
413
414 template<typename _Tp>
415 concept __size0_empty = requires(_Tp& __t) { _Size{}(__t) == 0; };
416
417 template<typename _Tp>
418 concept __eq_iter_empty = requires(_Tp& __t)
419 {
420 requires (!is_unbounded_array_v<remove_reference_t<_Tp>>);
421
422 { _Begin{}(__t) } -> forward_iterator;
423
424 bool(_Begin{}(__t) == _End{}(__t));
425 };
426
427 struct _Empty
428 {
429 private:
430 template<typename _Tp>
431 static constexpr bool
432 _S_noexcept()
433 {
434 if constexpr (__member_empty<_Tp>)
435 return noexcept(bool(std::declval<_Tp&>().empty()));
436 else if constexpr (__size0_empty<_Tp>)
437 return noexcept(_Size{}(std::declval<_Tp&>()) == 0);
438 else
439 return noexcept(bool(_Begin{}(std::declval<_Tp&>())
440 == _End{}(std::declval<_Tp&>())));
441 }
442
443 public:
444 template<typename _Tp>
445 requires __member_empty<_Tp> || __size0_empty<_Tp>
446 || __eq_iter_empty<_Tp>
447 constexpr bool
448 operator()[[nodiscard]](_Tp&& __t) const noexcept(_S_noexcept<_Tp&>())
449 {
450 if constexpr (__member_empty<_Tp>)
451 return bool(__t.empty());
452 else if constexpr (__size0_empty<_Tp>)
453 return _Size{}(__t) == 0;
454 else
455 return bool(_Begin{}(__t) == _End{}(__t));
456 }
457 };
458
459 template<typename _Tp>
460 concept __pointer_to_object = is_pointer_v<_Tp>
461 && is_object_v<remove_pointer_t<_Tp>>;
462
463 template<typename _Tp>
464 concept __member_data = requires(_Tp& __t)
465 {
466 { __decay_copy(__t.data()) } -> __pointer_to_object;
467 };
468
469 template<typename _Tp>
470 concept __begin_data = contiguous_iterator<__range_iter_t<_Tp>>;
471
472 struct _Data
473 {
474 private:
475 template<typename _Tp>
476 static constexpr bool
477 _S_noexcept()
478 {
479 if constexpr (__member_data<_Tp>)
480 return noexcept(__decay_copy(std::declval<_Tp&>().data()));
481 else
482 return noexcept(_Begin{}(std::declval<_Tp&>()));
483 }
484
485 public:
486 template<__maybe_borrowed_range _Tp>
487 requires __member_data<_Tp> || __begin_data<_Tp>
488 constexpr auto
489 operator()[[nodiscard]](_Tp&& __t) const noexcept(_S_noexcept<_Tp>())
490 {
491 if constexpr (__member_data<_Tp>)
492 return __t.data();
493 else
494 return std::to_address(_Begin{}(__t));
495 }
496 };
497
498 } // namespace __access
499
500 inline namespace _Cpo
501 {
502 inline constexpr ranges::__access::_Begin begin{};
503 inline constexpr ranges::__access::_End end{};
504 inline constexpr ranges::__access::_RBegin rbegin{};
505 inline constexpr ranges::__access::_REnd rend{};
506 inline constexpr ranges::__access::_Size size{};
507 inline constexpr ranges::__access::_SSize ssize{};
508 inline constexpr ranges::__access::_Empty empty{};
509 inline constexpr ranges::__access::_Data data{};
510 }
511
512 /// [range.range] The range concept.
513 template<typename _Tp>
514 concept range = requires(_Tp& __t)
515 {
516 ranges::begin(__t);
517 ranges::end(__t);
518 };
519
520 /// [range.range] The borrowed_range concept.
521 template<typename _Tp>
522 concept borrowed_range
523 = range<_Tp> && __detail::__maybe_borrowed_range<_Tp>;
524
525 template<typename _Tp>
526 using iterator_t = std::__detail::__range_iter_t<_Tp>;
527
528 template<range _Range>
529 using sentinel_t = decltype(ranges::end(std::declval<_Range&>()));
530
531#if __glibcxx_ranges_as_const // >= C++23
532 // const_iterator_t and const_sentinel_t defined below.
533
534 template<range _Range>
535 using range_const_reference_t = iter_const_reference_t<iterator_t<_Range>>;
536#endif
537
538 template<range _Range>
539 using range_difference_t = iter_difference_t<iterator_t<_Range>>;
540
541 template<range _Range>
542 using range_value_t = iter_value_t<iterator_t<_Range>>;
543
544 template<range _Range>
545 using range_reference_t = iter_reference_t<iterator_t<_Range>>;
546
547 template<range _Range>
548 using range_rvalue_reference_t
549 = iter_rvalue_reference_t<iterator_t<_Range>>;
550
551 // _GLIBCXX_RESOLVE_LIB_DEFECTS
552 // 3860. range_common_reference_t is missing
553 template<range _Range>
554 using range_common_reference_t
555 = iter_common_reference_t<iterator_t<_Range>>;
556
557 /// [range.sized] The sized_range concept.
558 template<typename _Tp>
559 concept sized_range = range<_Tp>
560 && requires(_Tp& __t) { ranges::size(__t); };
561
562 template<sized_range _Range>
563 using range_size_t = decltype(ranges::size(std::declval<_Range&>()));
564
565 template<typename _Derived>
566 requires is_class_v<_Derived> && same_as<_Derived, remove_cv_t<_Derived>>
567 class view_interface; // defined in <bits/ranges_util.h>
568
569 namespace __detail
570 {
571 template<typename _Tp, typename _Up>
572 requires (!same_as<_Tp, view_interface<_Up>>)
573 void __is_derived_from_view_interface_fn(const _Tp&,
574 const view_interface<_Up>&); // not defined
575
576 // Returns true iff _Tp has exactly one public base class that's a
577 // specialization of view_interface.
578 template<typename _Tp>
579 concept __is_derived_from_view_interface
580 = requires (_Tp __t) { __is_derived_from_view_interface_fn(__t, __t); };
581 } // namespace __detail
582
583 /// [range.view] The ranges::view_base type.
584 struct view_base { };
585
586 /// [range.view] The ranges::enable_view boolean.
587 template<typename _Tp>
588 inline constexpr bool enable_view = derived_from<_Tp, view_base>
589 || __detail::__is_derived_from_view_interface<_Tp>;
590
591 /// [range.view] The ranges::view concept.
592 template<typename _Tp>
593 concept view
594 = range<_Tp> && movable<_Tp> && enable_view<_Tp>;
595
596 // [range.refinements]
597
598 /// A range for which ranges::begin returns an output iterator.
599 template<typename _Range, typename _Tp>
600 concept output_range
601 = range<_Range> && output_iterator<iterator_t<_Range>, _Tp>;
602
603 /// A range for which ranges::begin returns an input iterator.
604 template<typename _Tp>
605 concept input_range = range<_Tp> && input_iterator<iterator_t<_Tp>>;
606
607 /// A range for which ranges::begin returns a forward iterator.
608 template<typename _Tp>
609 concept forward_range
610 = input_range<_Tp> && forward_iterator<iterator_t<_Tp>>;
611
612 /// A range for which ranges::begin returns a bidirectional iterator.
613 template<typename _Tp>
614 concept bidirectional_range
615 = forward_range<_Tp> && bidirectional_iterator<iterator_t<_Tp>>;
616
617 /// A range for which ranges::begin returns a random access iterator.
618 template<typename _Tp>
619 concept random_access_range
620 = bidirectional_range<_Tp> && random_access_iterator<iterator_t<_Tp>>;
621
622 /// A range for which ranges::begin returns a contiguous iterator.
623 template<typename _Tp>
624 concept contiguous_range
625 = random_access_range<_Tp> && contiguous_iterator<iterator_t<_Tp>>
626 && requires(_Tp& __t)
627 {
628 { ranges::data(__t) } -> same_as<add_pointer_t<range_reference_t<_Tp>>>;
629 };
630
631 /// A range for which ranges::begin and ranges::end return the same type.
632 template<typename _Tp>
633 concept common_range
634 = range<_Tp> && same_as<iterator_t<_Tp>, sentinel_t<_Tp>>;
635
636#if __glibcxx_ranges_as_const // >= C++23
637 template<typename _Tp>
638 concept constant_range
639 = input_range<_Tp> && std::__detail::__constant_iterator<iterator_t<_Tp>>;
640#endif
641
642 namespace __access
643 {
644#if __glibcxx_ranges_as_const // >= C++23
645 template<input_range _Range>
646 constexpr auto&
647 __possibly_const_range(_Range& __r) noexcept
648 {
649 // _GLIBCXX_RESOLVE_LIB_DEFECTS
650 // 4027. possibly-const-range should prefer returning const R&
651 if constexpr (input_range<const _Range>)
652 return const_cast<const _Range&>(__r);
653 else
654 return __r;
655 }
656#else
657 // If _To is an lvalue-reference, return const _Tp&, otherwise const _Tp&&.
658 template<typename _To, typename _Tp>
659 constexpr decltype(auto)
660 __as_const(_Tp& __t) noexcept
661 {
662 static_assert(std::is_same_v<_To&, _Tp&>);
663
664 if constexpr (is_lvalue_reference_v<_To>)
665 return const_cast<const _Tp&>(__t);
666 else
667 return static_cast<const _Tp&&>(__t);
668 }
669#endif
670
671 struct _CBegin
672 {
673#if __glibcxx_ranges_as_const // >= C++23
674 template<__maybe_borrowed_range _Tp>
675 [[nodiscard]]
676 constexpr auto
677 operator()(_Tp&& __t) const
678 noexcept(noexcept(std::make_const_iterator
679 (ranges::begin(__access::__possibly_const_range(__t)))))
680 requires requires { std::make_const_iterator
681 (ranges::begin(__access::__possibly_const_range(__t))); }
682 {
683 auto& __r = __access::__possibly_const_range(__t);
684 return const_iterator<decltype(ranges::begin(__r))>(ranges::begin(__r));
685 }
686#else
687 template<typename _Tp>
688 [[nodiscard]]
689 constexpr auto
690 operator()(_Tp&& __e) const
691 noexcept(noexcept(_Begin{}(__access::__as_const<_Tp>(__e))))
692 requires requires { _Begin{}(__access::__as_const<_Tp>(__e)); }
693 {
694 return _Begin{}(__access::__as_const<_Tp>(__e));
695 }
696#endif
697 };
698
699 struct _CEnd final
700 {
701#if __glibcxx_ranges_as_const // >= C++23
702 template<__maybe_borrowed_range _Tp>
703 [[nodiscard]]
704 constexpr auto
705 operator()(_Tp&& __t) const
706 noexcept(noexcept(std::make_const_sentinel
707 (ranges::end(__access::__possibly_const_range(__t)))))
708 requires requires { std::make_const_sentinel
709 (ranges::end(__access::__possibly_const_range(__t))); }
710 {
711 auto& __r = __access::__possibly_const_range(__t);
712 return const_sentinel<decltype(ranges::end(__r))>(ranges::end(__r));
713 }
714#else
715 template<typename _Tp>
716 [[nodiscard]]
717 constexpr auto
718 operator()(_Tp&& __e) const
719 noexcept(noexcept(_End{}(__access::__as_const<_Tp>(__e))))
720 requires requires { _End{}(__access::__as_const<_Tp>(__e)); }
721 {
722 return _End{}(__access::__as_const<_Tp>(__e));
723 }
724#endif
725 };
726
727 struct _CRBegin
728 {
729#if __glibcxx_ranges_as_const // >= C++23
730 template<__maybe_borrowed_range _Tp>
731 [[nodiscard]]
732 constexpr auto
733 operator()(_Tp&& __t) const
734 noexcept(noexcept(std::make_const_iterator
735 (ranges::rbegin(__access::__possibly_const_range(__t)))))
736 requires requires { std::make_const_iterator
737 (ranges::rbegin(__access::__possibly_const_range(__t))); }
738 {
739 auto& __r = __access::__possibly_const_range(__t);
740 return const_iterator<decltype(ranges::rbegin(__r))>(ranges::rbegin(__r));
741 }
742#else
743 template<typename _Tp>
744 [[nodiscard]]
745 constexpr auto
746 operator()(_Tp&& __e) const
747 noexcept(noexcept(_RBegin{}(__access::__as_const<_Tp>(__e))))
748 requires requires { _RBegin{}(__access::__as_const<_Tp>(__e)); }
749 {
750 return _RBegin{}(__access::__as_const<_Tp>(__e));
751 }
752#endif
753 };
754
755 struct _CREnd
756 {
757#if __glibcxx_ranges_as_const // >= C++23
758 template<__maybe_borrowed_range _Tp>
759 [[nodiscard]]
760 constexpr auto
761 operator()(_Tp&& __t) const
762 noexcept(noexcept(std::make_const_sentinel
763 (ranges::rend(__access::__possibly_const_range(__t)))))
764 requires requires { std::make_const_sentinel
765 (ranges::rend(__access::__possibly_const_range(__t))); }
766 {
767 auto& __r = __access::__possibly_const_range(__t);
768 return const_sentinel<decltype(ranges::rend(__r))>(ranges::rend(__r));
769 }
770#else
771 template<typename _Tp>
772 [[nodiscard]]
773 constexpr auto
774 operator()(_Tp&& __e) const
775 noexcept(noexcept(_REnd{}(__access::__as_const<_Tp>(__e))))
776 requires requires { _REnd{}(__access::__as_const<_Tp>(__e)); }
777 {
778 return _REnd{}(__access::__as_const<_Tp>(__e));
779 }
780#endif
781 };
782
783 struct _CData
784 {
785#if __glibcxx_ranges_as_const // >= C++23
786 template<__maybe_borrowed_range _Tp>
787 [[nodiscard]]
788 constexpr const auto*
789 operator()(_Tp&& __t) const
790 noexcept(noexcept(ranges::data(__access::__possibly_const_range(__t))))
791 requires requires { ranges::data(__access::__possibly_const_range(__t)); }
792 { return ranges::data(__access::__possibly_const_range(__t)); }
793#else
794 template<typename _Tp>
795 [[nodiscard]]
796 constexpr auto
797 operator()(_Tp&& __e) const
798 noexcept(noexcept(_Data{}(__access::__as_const<_Tp>(__e))))
799 requires requires { _Data{}(__access::__as_const<_Tp>(__e)); }
800 {
801 return _Data{}(__access::__as_const<_Tp>(__e));
802 }
803#endif
804 };
805 } // namespace __access
806
807 inline namespace _Cpo
808 {
809 inline constexpr ranges::__access::_CBegin cbegin{};
810 inline constexpr ranges::__access::_CEnd cend{};
811 inline constexpr ranges::__access::_CRBegin crbegin{};
812 inline constexpr ranges::__access::_CREnd crend{};
813 inline constexpr ranges::__access::_CData cdata{};
814 }
815
816#if __glibcxx_ranges_as_const // >= C++23
817 // _GLIBCXX_RESOLVE_LIB_DEFECTS
818 // 3946. The definition of const_iterator_t should be reworked
819 template<range _Range>
820 using const_iterator_t = decltype(ranges::cbegin(std::declval<_Range&>()));
821
822 template<range _Range>
823 using const_sentinel_t = decltype(ranges::cend(std::declval<_Range&>()));
824#endif
825
826 namespace __detail
827 {
828 template<typename _Tp>
829 inline constexpr bool __is_initializer_list = false;
830
831 template<typename _Tp>
832 inline constexpr bool __is_initializer_list<initializer_list<_Tp>> = true;
833 } // namespace __detail
834
835 /// A range which can be safely converted to a view.
836 template<typename _Tp>
837 concept viewable_range = range<_Tp>
838 && ((view<remove_cvref_t<_Tp>> && constructible_from<remove_cvref_t<_Tp>, _Tp>)
839 || (!view<remove_cvref_t<_Tp>>
840 && (is_lvalue_reference_v<_Tp>
841 || (movable<remove_reference_t<_Tp>>
842 && !__detail::__is_initializer_list<remove_cvref_t<_Tp>>))));
843
844 // [range.iter.ops] range iterator operations
845
846 struct __advance_fn final
847 {
848 template<input_or_output_iterator _It>
849 constexpr void
850 operator()(_It& __it, iter_difference_t<_It> __n) const
851 {
852 if constexpr (random_access_iterator<_It>)
853 __it += __n;
854 else if constexpr (bidirectional_iterator<_It>)
855 {
856 if (__n > 0)
857 {
858 do
859 {
860 ++__it;
861 }
862 while (--__n);
863 }
864 else if (__n < 0)
865 {
866 do
867 {
868 --__it;
869 }
870 while (++__n);
871 }
872 }
873 else
874 {
875 // cannot decrement a non-bidirectional iterator
876 __glibcxx_assert(__n >= 0);
877 while (__n-- > 0)
878 ++__it;
879 }
880 }
881
882 template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
883 constexpr void
884 operator()(_It& __it, _Sent __bound) const
885 {
886 if constexpr (assignable_from<_It&, _Sent>)
887 __it = std::move(__bound);
888 else if constexpr (sized_sentinel_for<_Sent, _It>)
889 (*this)(__it, __bound - __it);
890 else
891 {
892 while (__it != __bound)
893 ++__it;
894 }
895 }
896
897 template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
898 constexpr iter_difference_t<_It>
899 operator()(_It& __it, iter_difference_t<_It> __n, _Sent __bound) const
900 {
901 if constexpr (sized_sentinel_for<_Sent, _It>)
902 {
903 const auto __diff = __bound - __it;
904
905 if (__diff == 0)
906 return __n;
907 else if (__diff > 0 ? __n >= __diff : __n <= __diff)
908 {
909 (*this)(__it, __bound);
910 return __n - __diff;
911 }
912 else if (__n != 0) [[likely]]
913 {
914 // n and bound must not lead in opposite directions:
915 __glibcxx_assert((__n < 0) == (__diff < 0));
916
917 (*this)(__it, __n);
918 return 0;
919 }
920 else
921 return 0;
922 }
923 else if (__it == __bound || __n == 0)
924 return __n;
925 else if (__n > 0)
926 {
927 iter_difference_t<_It> __m = 0;
928 do
929 {
930 ++__it;
931 ++__m;
932 }
933 while (__m != __n && __it != __bound);
934 return __n - __m;
935 }
936 else if constexpr (bidirectional_iterator<_It> && same_as<_It, _Sent>)
937 {
938 iter_difference_t<_It> __m = 0;
939 do
940 {
941 --__it;
942 --__m;
943 }
944 while (__m != __n && __it != __bound);
945 return __n - __m;
946 }
947 else
948 {
949 // cannot decrement a non-bidirectional iterator
950 __glibcxx_assert(__n >= 0);
951 return __n;
952 }
953 }
954
955 void operator&() const = delete;
956 };
957
958 inline constexpr __advance_fn advance{};
959
960 struct __distance_fn final
961 {
962 // _GLIBCXX_RESOLVE_LIB_DEFECTS
963 // 3664. LWG 3392 broke std::ranges::distance(a, a+3)
964 template<typename _It, sentinel_for<_It> _Sent>
965 requires (!sized_sentinel_for<_Sent, _It>)
966 constexpr iter_difference_t<_It>
967 operator()[[nodiscard]](_It __first, _Sent __last) const
968 {
969 iter_difference_t<_It> __n = 0;
970 while (__first != __last)
971 {
972 ++__first;
973 ++__n;
974 }
975 return __n;
976 }
977
978 template<typename _It, sized_sentinel_for<decay_t<_It>> _Sent>
979 [[nodiscard]]
980 constexpr iter_difference_t<decay_t<_It>>
981 operator()(_It&& __first, _Sent __last) const
982 { return __last - static_cast<const decay_t<_It>&>(__first); }
983
984 template<range _Range>
985 [[nodiscard]]
986 constexpr range_difference_t<_Range>
987 operator()(_Range&& __r) const
988 {
989 if constexpr (sized_range<_Range>)
990 return static_cast<range_difference_t<_Range>>(ranges::size(__r));
991 else
992 return (*this)(ranges::begin(__r), ranges::end(__r));
993 }
994
995 void operator&() const = delete;
996 };
997
998 inline constexpr __distance_fn distance{};
999
1000 struct __next_fn final
1001 {
1002 template<input_or_output_iterator _It>
1003 [[nodiscard]]
1004 constexpr _It
1005 operator()(_It __x) const
1006 {
1007 ++__x;
1008 return __x;
1009 }
1010
1011 template<input_or_output_iterator _It>
1012 [[nodiscard]]
1013 constexpr _It
1014 operator()(_It __x, iter_difference_t<_It> __n) const
1015 {
1016 ranges::advance(__x, __n);
1017 return __x;
1018 }
1019
1020 template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
1021 [[nodiscard]]
1022 constexpr _It
1023 operator()(_It __x, _Sent __bound) const
1024 {
1025 ranges::advance(__x, __bound);
1026 return __x;
1027 }
1028
1029 template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
1030 [[nodiscard]]
1031 constexpr _It
1032 operator()(_It __x, iter_difference_t<_It> __n, _Sent __bound) const
1033 {
1034 ranges::advance(__x, __n, __bound);
1035 return __x;
1036 }
1037
1038 void operator&() const = delete;
1039 };
1040
1041 inline constexpr __next_fn next{};
1042
1043 struct __prev_fn final
1044 {
1045 template<bidirectional_iterator _It>
1046 [[nodiscard]]
1047 constexpr _It
1048 operator()(_It __x) const
1049 {
1050 --__x;
1051 return __x;
1052 }
1053
1054 template<bidirectional_iterator _It>
1055 [[nodiscard]]
1056 constexpr _It
1057 operator()(_It __x, iter_difference_t<_It> __n) const
1058 {
1059 ranges::advance(__x, -__n);
1060 return __x;
1061 }
1062
1063 template<bidirectional_iterator _It>
1064 [[nodiscard]]
1065 constexpr _It
1066 operator()(_It __x, iter_difference_t<_It> __n, _It __bound) const
1067 {
1068 ranges::advance(__x, -__n, __bound);
1069 return __x;
1070 }
1071
1072 void operator&() const = delete;
1073 };
1074
1075 inline constexpr __prev_fn prev{};
1076
1077 /// Type returned by algorithms instead of a dangling iterator or subrange.
1078 struct dangling
1079 {
1080 constexpr dangling() noexcept = default;
1081 template<typename... _Args>
1082 constexpr dangling(_Args&&...) noexcept { }
1083 };
1084
1085 template<range _Range>
1086 using borrowed_iterator_t = __conditional_t<borrowed_range<_Range>,
1087 iterator_t<_Range>,
1088 dangling>;
1089} // namespace ranges
1090
1091#if __glibcxx_ranges_to_container // C++ >= 23
1092 struct from_range_t { explicit from_range_t() = default; };
1093 inline constexpr from_range_t from_range{};
1094#endif
1095
1096#if __glibcxx_containers_ranges // C++ >= 23
1097/// @cond undocumented
1098 template<typename _T1, typename _T2>
1099 struct pair;
1100
1101namespace __detail
1102{
1103 template<typename _Rg, typename _Tp>
1104 concept __container_compatible_range
1105 = ranges::input_range<_Rg>
1106 && convertible_to<ranges::range_reference_t<_Rg>, _Tp>;
1107
1108 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1109 // 4223. Deduction guides for maps are mishandling tuples and references
1110 template<ranges::input_range _Range>
1111 using __range_key_type
1112 = remove_const_t<tuple_element_t<0, ranges::range_value_t<_Range>>>;
1113
1114 template<ranges::input_range _Range>
1115 using __range_mapped_type
1116 = tuple_element_t<1, ranges::range_value_t<_Range>>;
1117
1118 // The allocator's value_type for map-like containers.
1119 template<ranges::input_range _Range>
1120 using __range_to_alloc_type
1121 = pair<const __range_key_type<_Range>, __range_mapped_type<_Range>>;
1122}
1123/// @endcond
1124#endif
1125
1126_GLIBCXX_END_NAMESPACE_VERSION
1127} // namespace std
1128#endif // library concepts
1129#pragma GCC diagnostic pop
1130#endif // C++20
1131#endif // _GLIBCXX_RANGES_BASE_H
1132