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 template<range _Range>
533 using const_iterator_t = const_iterator<iterator_t<_Range>>;
534
535 template<range _Range>
536 using const_sentinel_t = const_sentinel<sentinel_t<_Range>>;
537
538 template<range _Range>
539 using range_const_reference_t = iter_const_reference_t<iterator_t<_Range>>;
540#endif
541
542 template<range _Range>
543 using range_difference_t = iter_difference_t<iterator_t<_Range>>;
544
545 template<range _Range>
546 using range_value_t = iter_value_t<iterator_t<_Range>>;
547
548 template<range _Range>
549 using range_reference_t = iter_reference_t<iterator_t<_Range>>;
550
551 template<range _Range>
552 using range_rvalue_reference_t
553 = iter_rvalue_reference_t<iterator_t<_Range>>;
554
555 // _GLIBCXX_RESOLVE_LIB_DEFECTS
556 // 3860. range_common_reference_t is missing
557 template<range _Range>
558 using range_common_reference_t
559 = iter_common_reference_t<iterator_t<_Range>>;
560
561 /// [range.sized] The sized_range concept.
562 template<typename _Tp>
563 concept sized_range = range<_Tp>
564 && requires(_Tp& __t) { ranges::size(__t); };
565
566 template<sized_range _Range>
567 using range_size_t = decltype(ranges::size(std::declval<_Range&>()));
568
569 template<typename _Derived>
570 requires is_class_v<_Derived> && same_as<_Derived, remove_cv_t<_Derived>>
571 class view_interface; // defined in <bits/ranges_util.h>
572
573 namespace __detail
574 {
575 template<typename _Tp, typename _Up>
576 requires (!same_as<_Tp, view_interface<_Up>>)
577 void __is_derived_from_view_interface_fn(const _Tp&,
578 const view_interface<_Up>&); // not defined
579
580 // Returns true iff _Tp has exactly one public base class that's a
581 // specialization of view_interface.
582 template<typename _Tp>
583 concept __is_derived_from_view_interface
584 = requires (_Tp __t) { __is_derived_from_view_interface_fn(__t, __t); };
585 } // namespace __detail
586
587 /// [range.view] The ranges::view_base type.
588 struct view_base { };
589
590 /// [range.view] The ranges::enable_view boolean.
591 template<typename _Tp>
592 inline constexpr bool enable_view = derived_from<_Tp, view_base>
593 || __detail::__is_derived_from_view_interface<_Tp>;
594
595 /// [range.view] The ranges::view concept.
596 template<typename _Tp>
597 concept view
598 = range<_Tp> && movable<_Tp> && enable_view<_Tp>;
599
600 // [range.refinements]
601
602 /// A range for which ranges::begin returns an output iterator.
603 template<typename _Range, typename _Tp>
604 concept output_range
605 = range<_Range> && output_iterator<iterator_t<_Range>, _Tp>;
606
607 /// A range for which ranges::begin returns an input iterator.
608 template<typename _Tp>
609 concept input_range = range<_Tp> && input_iterator<iterator_t<_Tp>>;
610
611 /// A range for which ranges::begin returns a forward iterator.
612 template<typename _Tp>
613 concept forward_range
614 = input_range<_Tp> && forward_iterator<iterator_t<_Tp>>;
615
616 /// A range for which ranges::begin returns a bidirectional iterator.
617 template<typename _Tp>
618 concept bidirectional_range
619 = forward_range<_Tp> && bidirectional_iterator<iterator_t<_Tp>>;
620
621 /// A range for which ranges::begin returns a random access iterator.
622 template<typename _Tp>
623 concept random_access_range
624 = bidirectional_range<_Tp> && random_access_iterator<iterator_t<_Tp>>;
625
626 /// A range for which ranges::begin returns a contiguous iterator.
627 template<typename _Tp>
628 concept contiguous_range
629 = random_access_range<_Tp> && contiguous_iterator<iterator_t<_Tp>>
630 && requires(_Tp& __t)
631 {
632 { ranges::data(__t) } -> same_as<add_pointer_t<range_reference_t<_Tp>>>;
633 };
634
635 /// A range for which ranges::begin and ranges::end return the same type.
636 template<typename _Tp>
637 concept common_range
638 = range<_Tp> && same_as<iterator_t<_Tp>, sentinel_t<_Tp>>;
639
640#if __glibcxx_ranges_as_const // >= C++23
641 template<typename _Tp>
642 concept constant_range
643 = input_range<_Tp> && std::__detail::__constant_iterator<iterator_t<_Tp>>;
644#endif
645
646 namespace __access
647 {
648#if __glibcxx_ranges_as_const // >= C++23
649 template<input_range _Range>
650 constexpr auto&
651 __possibly_const_range(_Range& __r) noexcept
652 {
653 // _GLIBCXX_RESOLVE_LIB_DEFECTS
654 // 4027. possibly-const-range should prefer returning const R&
655 if constexpr (input_range<const _Range>)
656 return const_cast<const _Range&>(__r);
657 else
658 return __r;
659 }
660#else
661 // If _To is an lvalue-reference, return const _Tp&, otherwise const _Tp&&.
662 template<typename _To, typename _Tp>
663 constexpr decltype(auto)
664 __as_const(_Tp& __t) noexcept
665 {
666 static_assert(std::is_same_v<_To&, _Tp&>);
667
668 if constexpr (is_lvalue_reference_v<_To>)
669 return const_cast<const _Tp&>(__t);
670 else
671 return static_cast<const _Tp&&>(__t);
672 }
673#endif
674
675 struct _CBegin
676 {
677#if __glibcxx_ranges_as_const // >= C++23
678 template<__maybe_borrowed_range _Tp>
679 [[nodiscard]]
680 constexpr auto
681 operator()(_Tp&& __t) const
682 noexcept(noexcept(std::make_const_iterator
683 (ranges::begin(__access::__possibly_const_range(__t)))))
684 requires requires { std::make_const_iterator
685 (ranges::begin(__access::__possibly_const_range(__t))); }
686 {
687 auto& __r = __access::__possibly_const_range(__t);
688 return const_iterator_t<decltype(__r)>(ranges::begin(__r));
689 }
690#else
691 template<typename _Tp>
692 [[nodiscard]]
693 constexpr auto
694 operator()(_Tp&& __e) const
695 noexcept(noexcept(_Begin{}(__access::__as_const<_Tp>(__e))))
696 requires requires { _Begin{}(__access::__as_const<_Tp>(__e)); }
697 {
698 return _Begin{}(__access::__as_const<_Tp>(__e));
699 }
700#endif
701 };
702
703 struct _CEnd final
704 {
705#if __glibcxx_ranges_as_const // >= C++23
706 template<__maybe_borrowed_range _Tp>
707 [[nodiscard]]
708 constexpr auto
709 operator()(_Tp&& __t) const
710 noexcept(noexcept(std::make_const_sentinel
711 (ranges::end(__access::__possibly_const_range(__t)))))
712 requires requires { std::make_const_sentinel
713 (ranges::end(__access::__possibly_const_range(__t))); }
714 {
715 auto& __r = __access::__possibly_const_range(__t);
716 return const_sentinel_t<decltype(__r)>(ranges::end(__r));
717 }
718#else
719 template<typename _Tp>
720 [[nodiscard]]
721 constexpr auto
722 operator()(_Tp&& __e) const
723 noexcept(noexcept(_End{}(__access::__as_const<_Tp>(__e))))
724 requires requires { _End{}(__access::__as_const<_Tp>(__e)); }
725 {
726 return _End{}(__access::__as_const<_Tp>(__e));
727 }
728#endif
729 };
730
731 struct _CRBegin
732 {
733#if __glibcxx_ranges_as_const // >= C++23
734 template<__maybe_borrowed_range _Tp>
735 [[nodiscard]]
736 constexpr auto
737 operator()(_Tp&& __t) const
738 noexcept(noexcept(std::make_const_iterator
739 (ranges::rbegin(__access::__possibly_const_range(__t)))))
740 requires requires { std::make_const_iterator
741 (ranges::rbegin(__access::__possibly_const_range(__t))); }
742 {
743 auto& __r = __access::__possibly_const_range(__t);
744 return const_iterator<decltype(ranges::rbegin(__r))>(ranges::rbegin(__r));
745 }
746#else
747 template<typename _Tp>
748 [[nodiscard]]
749 constexpr auto
750 operator()(_Tp&& __e) const
751 noexcept(noexcept(_RBegin{}(__access::__as_const<_Tp>(__e))))
752 requires requires { _RBegin{}(__access::__as_const<_Tp>(__e)); }
753 {
754 return _RBegin{}(__access::__as_const<_Tp>(__e));
755 }
756#endif
757 };
758
759 struct _CREnd
760 {
761#if __glibcxx_ranges_as_const // >= C++23
762 template<__maybe_borrowed_range _Tp>
763 [[nodiscard]]
764 constexpr auto
765 operator()(_Tp&& __t) const
766 noexcept(noexcept(std::make_const_sentinel
767 (ranges::rend(__access::__possibly_const_range(__t)))))
768 requires requires { std::make_const_sentinel
769 (ranges::rend(__access::__possibly_const_range(__t))); }
770 {
771 auto& __r = __access::__possibly_const_range(__t);
772 return const_sentinel<decltype(ranges::rend(__r))>(ranges::rend(__r));
773 }
774#else
775 template<typename _Tp>
776 [[nodiscard]]
777 constexpr auto
778 operator()(_Tp&& __e) const
779 noexcept(noexcept(_REnd{}(__access::__as_const<_Tp>(__e))))
780 requires requires { _REnd{}(__access::__as_const<_Tp>(__e)); }
781 {
782 return _REnd{}(__access::__as_const<_Tp>(__e));
783 }
784#endif
785 };
786
787 struct _CData
788 {
789#if __glibcxx_ranges_as_const // >= C++23
790 template<__maybe_borrowed_range _Tp>
791 [[nodiscard]]
792 constexpr const auto*
793 operator()(_Tp&& __t) const
794 noexcept(noexcept(ranges::data(__access::__possibly_const_range(__t))))
795 requires requires { ranges::data(__access::__possibly_const_range(__t)); }
796 { return ranges::data(__access::__possibly_const_range(__t)); }
797#else
798 template<typename _Tp>
799 [[nodiscard]]
800 constexpr auto
801 operator()(_Tp&& __e) const
802 noexcept(noexcept(_Data{}(__access::__as_const<_Tp>(__e))))
803 requires requires { _Data{}(__access::__as_const<_Tp>(__e)); }
804 {
805 return _Data{}(__access::__as_const<_Tp>(__e));
806 }
807#endif
808 };
809 } // namespace __access
810
811 inline namespace _Cpo
812 {
813 inline constexpr ranges::__access::_CBegin cbegin{};
814 inline constexpr ranges::__access::_CEnd cend{};
815 inline constexpr ranges::__access::_CRBegin crbegin{};
816 inline constexpr ranges::__access::_CREnd crend{};
817 inline constexpr ranges::__access::_CData cdata{};
818 }
819
820 namespace __detail
821 {
822 template<typename _Tp>
823 inline constexpr bool __is_initializer_list = false;
824
825 template<typename _Tp>
826 inline constexpr bool __is_initializer_list<initializer_list<_Tp>> = true;
827 } // namespace __detail
828
829 /// A range which can be safely converted to a view.
830 template<typename _Tp>
831 concept viewable_range = range<_Tp>
832 && ((view<remove_cvref_t<_Tp>> && constructible_from<remove_cvref_t<_Tp>, _Tp>)
833 || (!view<remove_cvref_t<_Tp>>
834 && (is_lvalue_reference_v<_Tp>
835 || (movable<remove_reference_t<_Tp>>
836 && !__detail::__is_initializer_list<remove_cvref_t<_Tp>>))));
837
838 // [range.iter.ops] range iterator operations
839
840 struct __advance_fn final
841 {
842 template<input_or_output_iterator _It>
843 constexpr void
844 operator()(_It& __it, iter_difference_t<_It> __n) const
845 {
846 if constexpr (random_access_iterator<_It>)
847 __it += __n;
848 else if constexpr (bidirectional_iterator<_It>)
849 {
850 if (__n > 0)
851 {
852 do
853 {
854 ++__it;
855 }
856 while (--__n);
857 }
858 else if (__n < 0)
859 {
860 do
861 {
862 --__it;
863 }
864 while (++__n);
865 }
866 }
867 else
868 {
869 // cannot decrement a non-bidirectional iterator
870 __glibcxx_assert(__n >= 0);
871 while (__n-- > 0)
872 ++__it;
873 }
874 }
875
876 template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
877 constexpr void
878 operator()(_It& __it, _Sent __bound) const
879 {
880 if constexpr (assignable_from<_It&, _Sent>)
881 __it = std::move(__bound);
882 else if constexpr (sized_sentinel_for<_Sent, _It>)
883 (*this)(__it, __bound - __it);
884 else
885 {
886 while (__it != __bound)
887 ++__it;
888 }
889 }
890
891 template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
892 constexpr iter_difference_t<_It>
893 operator()(_It& __it, iter_difference_t<_It> __n, _Sent __bound) const
894 {
895 if constexpr (sized_sentinel_for<_Sent, _It>)
896 {
897 const auto __diff = __bound - __it;
898
899 if (__diff == 0)
900 return __n;
901 else if (__diff > 0 ? __n >= __diff : __n <= __diff)
902 {
903 (*this)(__it, __bound);
904 return __n - __diff;
905 }
906 else if (__n != 0) [[likely]]
907 {
908 // n and bound must not lead in opposite directions:
909 __glibcxx_assert((__n < 0) == (__diff < 0));
910
911 (*this)(__it, __n);
912 return 0;
913 }
914 else
915 return 0;
916 }
917 else if (__it == __bound || __n == 0)
918 return __n;
919 else if (__n > 0)
920 {
921 iter_difference_t<_It> __m = 0;
922 do
923 {
924 ++__it;
925 ++__m;
926 }
927 while (__m != __n && __it != __bound);
928 return __n - __m;
929 }
930 else if constexpr (bidirectional_iterator<_It> && same_as<_It, _Sent>)
931 {
932 iter_difference_t<_It> __m = 0;
933 do
934 {
935 --__it;
936 --__m;
937 }
938 while (__m != __n && __it != __bound);
939 return __n - __m;
940 }
941 else
942 {
943 // cannot decrement a non-bidirectional iterator
944 __glibcxx_assert(__n >= 0);
945 return __n;
946 }
947 }
948
949 void operator&() const = delete;
950 };
951
952 inline constexpr __advance_fn advance{};
953
954 struct __distance_fn final
955 {
956 // _GLIBCXX_RESOLVE_LIB_DEFECTS
957 // 3664. LWG 3392 broke std::ranges::distance(a, a+3)
958 template<typename _It, sentinel_for<_It> _Sent>
959 requires (!sized_sentinel_for<_Sent, _It>)
960 constexpr iter_difference_t<_It>
961 operator()[[nodiscard]](_It __first, _Sent __last) const
962 {
963 iter_difference_t<_It> __n = 0;
964 while (__first != __last)
965 {
966 ++__first;
967 ++__n;
968 }
969 return __n;
970 }
971
972 template<typename _It, sized_sentinel_for<decay_t<_It>> _Sent>
973 [[nodiscard]]
974 constexpr iter_difference_t<decay_t<_It>>
975 operator()(_It&& __first, _Sent __last) const
976 { return __last - static_cast<const decay_t<_It>&>(__first); }
977
978 template<range _Range>
979 [[nodiscard]]
980 constexpr range_difference_t<_Range>
981 operator()(_Range&& __r) const
982 {
983 if constexpr (sized_range<_Range>)
984 return static_cast<range_difference_t<_Range>>(ranges::size(__r));
985 else
986 return (*this)(ranges::begin(__r), ranges::end(__r));
987 }
988
989 void operator&() const = delete;
990 };
991
992 inline constexpr __distance_fn distance{};
993
994 struct __next_fn final
995 {
996 template<input_or_output_iterator _It>
997 [[nodiscard]]
998 constexpr _It
999 operator()(_It __x) const
1000 {
1001 ++__x;
1002 return __x;
1003 }
1004
1005 template<input_or_output_iterator _It>
1006 [[nodiscard]]
1007 constexpr _It
1008 operator()(_It __x, iter_difference_t<_It> __n) const
1009 {
1010 ranges::advance(__x, __n);
1011 return __x;
1012 }
1013
1014 template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
1015 [[nodiscard]]
1016 constexpr _It
1017 operator()(_It __x, _Sent __bound) const
1018 {
1019 ranges::advance(__x, __bound);
1020 return __x;
1021 }
1022
1023 template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
1024 [[nodiscard]]
1025 constexpr _It
1026 operator()(_It __x, iter_difference_t<_It> __n, _Sent __bound) const
1027 {
1028 ranges::advance(__x, __n, __bound);
1029 return __x;
1030 }
1031
1032 void operator&() const = delete;
1033 };
1034
1035 inline constexpr __next_fn next{};
1036
1037 struct __prev_fn final
1038 {
1039 template<bidirectional_iterator _It>
1040 [[nodiscard]]
1041 constexpr _It
1042 operator()(_It __x) const
1043 {
1044 --__x;
1045 return __x;
1046 }
1047
1048 template<bidirectional_iterator _It>
1049 [[nodiscard]]
1050 constexpr _It
1051 operator()(_It __x, iter_difference_t<_It> __n) const
1052 {
1053 ranges::advance(__x, -__n);
1054 return __x;
1055 }
1056
1057 template<bidirectional_iterator _It>
1058 [[nodiscard]]
1059 constexpr _It
1060 operator()(_It __x, iter_difference_t<_It> __n, _It __bound) const
1061 {
1062 ranges::advance(__x, -__n, __bound);
1063 return __x;
1064 }
1065
1066 void operator&() const = delete;
1067 };
1068
1069 inline constexpr __prev_fn prev{};
1070
1071 /// Type returned by algorithms instead of a dangling iterator or subrange.
1072 struct dangling
1073 {
1074 constexpr dangling() noexcept = default;
1075 template<typename... _Args>
1076 constexpr dangling(_Args&&...) noexcept { }
1077 };
1078
1079 template<range _Range>
1080 using borrowed_iterator_t = __conditional_t<borrowed_range<_Range>,
1081 iterator_t<_Range>,
1082 dangling>;
1083} // namespace ranges
1084
1085#if __glibcxx_ranges_to_container // C++ >= 23
1086 struct from_range_t { explicit from_range_t() = default; };
1087 inline constexpr from_range_t from_range{};
1088#endif
1089
1090#if __glibcxx_containers_ranges // C++ >= 23
1091/// @cond undocumented
1092 template<typename _T1, typename _T2>
1093 struct pair;
1094
1095namespace __detail
1096{
1097 template<typename _Rg, typename _Tp>
1098 concept __container_compatible_range
1099 = ranges::input_range<_Rg>
1100 && convertible_to<ranges::range_reference_t<_Rg>, _Tp>;
1101
1102 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1103 // 4223. Deduction guides for maps are mishandling tuples and references
1104 template<ranges::input_range _Range>
1105 using __range_key_type
1106 = remove_const_t<tuple_element_t<0, ranges::range_value_t<_Range>>>;
1107
1108 template<ranges::input_range _Range>
1109 using __range_mapped_type
1110 = tuple_element_t<1, ranges::range_value_t<_Range>>;
1111
1112 // The allocator's value_type for map-like containers.
1113 template<ranges::input_range _Range>
1114 using __range_to_alloc_type
1115 = pair<const __range_key_type<_Range>, __range_mapped_type<_Range>>;
1116}
1117/// @endcond
1118#endif
1119
1120_GLIBCXX_END_NAMESPACE_VERSION
1121} // namespace std
1122#endif // library concepts
1123#pragma GCC diagnostic pop
1124#endif // C++20
1125#endif // _GLIBCXX_RANGES_BASE_H
1126