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