libstdc++
ranges_base.h
Go to the documentation of this file.
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#pragma GCC diagnostic push
45#pragma GCC diagnostic ignored "-Wpedantic" // __int128
46
47#if __glibcxx_algorithm_default_value_type // C++ >= 26
48# define _GLIBCXX26_RANGE_ALGO_DEF_VAL_T(_I, _P) = projected_value_t<_I, _P>
49#else
50# define _GLIBCXX26_RANGE_ALGO_DEF_VAL_T(_I, _P)
51#endif
52
53#ifdef __cpp_lib_concepts
54namespace std _GLIBCXX_VISIBILITY(default)
55{
56_GLIBCXX_BEGIN_NAMESPACE_VERSION
57namespace ranges
58{
59 template<typename>
60 inline constexpr bool disable_sized_range = false;
61
62 template<typename _Tp>
63 inline constexpr bool enable_borrowed_range = false;
64
65 namespace __detail
66 {
67 constexpr __max_size_type
68 __to_unsigned_like(__max_size_type __t) noexcept
69 { return __t; }
70
71 constexpr __max_size_type
72 __to_unsigned_like(__max_diff_type __t) noexcept
73 { return __max_size_type(__t); }
74
75 template<integral _Tp>
76 constexpr auto
77 __to_unsigned_like(_Tp __t) noexcept
78 { return static_cast<make_unsigned_t<_Tp>>(__t); }
79
80#if defined __STRICT_ANSI__ && defined __SIZEOF_INT128__
81 constexpr unsigned __int128
82 __to_unsigned_like(__int128 __t) noexcept
83 { return __t; }
84
85 constexpr unsigned __int128
86 __to_unsigned_like(unsigned __int128 __t) noexcept
87 { return __t; }
88#endif
89
90 template<typename _Tp>
91 using __make_unsigned_like_t
92 = decltype(__detail::__to_unsigned_like(std::declval<_Tp>()));
93
94 // Part of the constraints of ranges::borrowed_range
95 template<typename _Tp>
96 concept __maybe_borrowed_range
97 = is_lvalue_reference_v<_Tp>
98 || enable_borrowed_range<remove_cvref_t<_Tp>>;
99
100 } // namespace __detail
101
102 // Namespace for helpers for the <ranges> customization points.
103 namespace __access
104 {
105 using std::ranges::__detail::__maybe_borrowed_range;
106 using std::__detail::__range_iter_t;
107
108 struct _Begin
109 {
110 private:
111 template<typename _Tp>
112 static constexpr bool
113 _S_noexcept()
114 {
115 if constexpr (is_array_v<remove_reference_t<_Tp>>)
116 return true;
117 else if constexpr (__member_begin<_Tp>)
118 return noexcept(__decay_copy(std::declval<_Tp&>().begin()));
119 else
120 return noexcept(__decay_copy(begin(std::declval<_Tp&>())));
121 }
122
123 public:
124 template<__maybe_borrowed_range _Tp>
125 requires is_array_v<remove_reference_t<_Tp>> || __member_begin<_Tp>
126 || __adl_begin<_Tp>
127 constexpr auto
128 operator()[[nodiscard]](_Tp&& __t) const noexcept(_S_noexcept<_Tp&>())
129 {
130 if constexpr (is_array_v<remove_reference_t<_Tp>>)
131 {
132 static_assert(is_lvalue_reference_v<_Tp>);
133 return __t + 0;
134 }
135 else if constexpr (__member_begin<_Tp>)
136 return __t.begin();
137 else
138 return begin(__t);
139 }
140 };
141
142 template<typename _Tp>
143 concept __member_end = requires(_Tp& __t)
144 {
145 { __decay_copy(__t.end()) } -> sentinel_for<__range_iter_t<_Tp>>;
146 };
147
148 // Poison pill so that unqualified lookup doesn't find std::end.
149 void end() = delete;
150
151 template<typename _Tp>
152 concept __adl_end = __class_or_enum<remove_reference_t<_Tp>>
153 && requires(_Tp& __t)
154 {
155 { __decay_copy(end(__t)) } -> sentinel_for<__range_iter_t<_Tp>>;
156 };
157
158 struct _End
159 {
160 private:
161 template<typename _Tp>
162 static constexpr bool
163 _S_noexcept()
164 {
165 if constexpr (is_bounded_array_v<remove_reference_t<_Tp>>)
166 return true;
167 else if constexpr (__member_end<_Tp>)
168 return noexcept(__decay_copy(std::declval<_Tp&>().end()));
169 else
170 return noexcept(__decay_copy(end(std::declval<_Tp&>())));
171 }
172
173 public:
174 template<__maybe_borrowed_range _Tp>
175 requires is_bounded_array_v<remove_reference_t<_Tp>>
176 || __member_end<_Tp> || __adl_end<_Tp>
177 constexpr auto
178 operator()[[nodiscard]](_Tp&& __t) const noexcept(_S_noexcept<_Tp&>())
179 {
180 if constexpr (is_bounded_array_v<remove_reference_t<_Tp>>)
181 {
182 static_assert(is_lvalue_reference_v<_Tp>);
183 return __t + extent_v<remove_reference_t<_Tp>>;
184 }
185 else if constexpr (__member_end<_Tp>)
186 return __t.end();
187 else
188 return end(__t);
189 }
190 };
191
192 template<typename _Tp>
193 concept __member_rbegin = requires(_Tp& __t)
194 {
195 { __decay_copy(__t.rbegin()) } -> input_or_output_iterator;
196 };
197
198 void rbegin() = delete;
199
200 template<typename _Tp>
201 concept __adl_rbegin = __class_or_enum<remove_reference_t<_Tp>>
202 && requires(_Tp& __t)
203 {
204 { __decay_copy(rbegin(__t)) } -> input_or_output_iterator;
205 };
206
207 template<typename _Tp>
208 concept __reversable = requires(_Tp& __t)
209 {
210 { _Begin{}(__t) } -> bidirectional_iterator;
211 { _End{}(__t) } -> same_as<decltype(_Begin{}(__t))>;
212 };
213
214 struct _RBegin
215 {
216 private:
217 template<typename _Tp>
218 static constexpr bool
219 _S_noexcept()
220 {
221 if constexpr (__member_rbegin<_Tp>)
222 return noexcept(__decay_copy(std::declval<_Tp&>().rbegin()));
223 else if constexpr (__adl_rbegin<_Tp>)
224 return noexcept(__decay_copy(rbegin(std::declval<_Tp&>())));
225 else
226 {
227 if constexpr (noexcept(_End{}(std::declval<_Tp&>())))
228 {
229 using _It = decltype(_End{}(std::declval<_Tp&>()));
230 // std::reverse_iterator copy-initializes its member.
231 return is_nothrow_copy_constructible_v<_It>;
232 }
233 else
234 return false;
235 }
236 }
237
238 public:
239 template<__maybe_borrowed_range _Tp>
240 requires __member_rbegin<_Tp> || __adl_rbegin<_Tp> || __reversable<_Tp>
241 constexpr auto
242 operator()[[nodiscard]](_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 { __decay_copy(__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 { __decay_copy(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 constexpr bool
276 _S_noexcept()
277 {
278 if constexpr (__member_rend<_Tp>)
279 return noexcept(__decay_copy(std::declval<_Tp&>().rend()));
280 else if constexpr (__adl_rend<_Tp>)
281 return noexcept(__decay_copy(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 constexpr auto
299 operator()[[nodiscard]](_Tp&& __t) const
300 noexcept(_S_noexcept<_Tp&>())
301 {
302 if constexpr (__member_rend<_Tp>)
303 return __t.rend();
304 else if constexpr (__adl_rend<_Tp>)
305 return rend(__t);
306 else
307 return std::make_reverse_iterator(_Begin{}(__t));
308 }
309 };
310
311 template<typename _Tp>
312 concept __member_size = !disable_sized_range<remove_cvref_t<_Tp>>
313 && requires(_Tp& __t)
314 {
315 { __decay_copy(__t.size()) } -> __detail::__is_integer_like;
316 };
317
318 void size() = delete;
319
320 template<typename _Tp>
321 concept __adl_size = __class_or_enum<remove_reference_t<_Tp>>
322 && !disable_sized_range<remove_cvref_t<_Tp>>
323 && requires(_Tp& __t)
324 {
325 { __decay_copy(size(__t)) } -> __detail::__is_integer_like;
326 };
327
328 template<typename _Tp>
329 concept __sentinel_size = requires(_Tp& __t)
330 {
331 requires (!is_unbounded_array_v<remove_reference_t<_Tp>>);
332
333 { _Begin{}(__t) } -> forward_iterator;
334
335 { _End{}(__t) } -> sized_sentinel_for<decltype(_Begin{}(__t))>;
336
337 __detail::__to_unsigned_like(_End{}(__t) - _Begin{}(__t));
338 };
339
340 struct _Size
341 {
342 private:
343 template<typename _Tp>
344 static constexpr bool
345 _S_noexcept()
346 {
347 if constexpr (is_bounded_array_v<remove_reference_t<_Tp>>)
348 return true;
349 else if constexpr (__member_size<_Tp>)
350 return noexcept(__decay_copy(std::declval<_Tp&>().size()));
351 else if constexpr (__adl_size<_Tp>)
352 return noexcept(__decay_copy(size(std::declval<_Tp&>())));
353 else if constexpr (__sentinel_size<_Tp>)
354 return noexcept(_End{}(std::declval<_Tp&>())
355 - _Begin{}(std::declval<_Tp&>()));
356 }
357
358 public:
359 template<typename _Tp>
360 requires is_bounded_array_v<remove_reference_t<_Tp>>
361 || __member_size<_Tp> || __adl_size<_Tp> || __sentinel_size<_Tp>
362 constexpr auto
363 operator()[[nodiscard]](_Tp&& __t) const noexcept(_S_noexcept<_Tp&>())
364 {
365 if constexpr (is_bounded_array_v<remove_reference_t<_Tp>>)
366 return extent_v<remove_reference_t<_Tp>>;
367 else if constexpr (__member_size<_Tp>)
368 return __t.size();
369 else if constexpr (__adl_size<_Tp>)
370 return size(__t);
371 else if constexpr (__sentinel_size<_Tp>)
372 return __detail::__to_unsigned_like(_End{}(__t) - _Begin{}(__t));
373 }
374 };
375
376 struct _SSize
377 {
378 // _GLIBCXX_RESOLVE_LIB_DEFECTS
379 // 3403. Domain of ranges::ssize(E) doesn't match ranges::size(E)
380 template<typename _Tp>
381 requires requires (_Tp& __t) { _Size{}(__t); }
382 constexpr auto
383 operator()[[nodiscard]](_Tp&& __t) const noexcept(noexcept(_Size{}(__t)))
384 {
385 auto __size = _Size{}(__t);
386 using __size_type = decltype(__size);
387 // Return the wider of ptrdiff_t and make-signed-like-t<__size_type>.
388 if constexpr (integral<__size_type>)
389 {
391 if constexpr (__int_traits<__size_type>::__digits
392 < __int_traits<ptrdiff_t>::__digits)
393 return static_cast<ptrdiff_t>(__size);
394 else
395 return static_cast<make_signed_t<__size_type>>(__size);
396 }
397#if defined __STRICT_ANSI__ && defined __SIZEOF_INT128__
398 // For strict-ansi modes integral<__int128> is false
399 else if constexpr (__detail::__is_int128<__size_type>)
400 return static_cast<__int128>(__size);
401#endif
402 else // Must be one of __max_diff_type or __max_size_type.
403 return __detail::__max_diff_type(__size);
404 }
405 };
406
407 template<typename _Tp>
408 concept __member_empty = requires(_Tp& __t) { bool(__t.empty()); };
409
410 template<typename _Tp>
411 concept __size0_empty = requires(_Tp& __t) { _Size{}(__t) == 0; };
412
413 template<typename _Tp>
414 concept __eq_iter_empty = requires(_Tp& __t)
415 {
416 requires (!is_unbounded_array_v<remove_reference_t<_Tp>>);
417
418 { _Begin{}(__t) } -> forward_iterator;
419
420 bool(_Begin{}(__t) == _End{}(__t));
421 };
422
423 struct _Empty
424 {
425 private:
426 template<typename _Tp>
427 static constexpr bool
428 _S_noexcept()
429 {
430 if constexpr (__member_empty<_Tp>)
431 return noexcept(bool(std::declval<_Tp&>().empty()));
432 else if constexpr (__size0_empty<_Tp>)
433 return noexcept(_Size{}(std::declval<_Tp&>()) == 0);
434 else
435 return noexcept(bool(_Begin{}(std::declval<_Tp&>())
436 == _End{}(std::declval<_Tp&>())));
437 }
438
439 public:
440 template<typename _Tp>
441 requires __member_empty<_Tp> || __size0_empty<_Tp>
442 || __eq_iter_empty<_Tp>
443 constexpr bool
444 operator()[[nodiscard]](_Tp&& __t) const noexcept(_S_noexcept<_Tp&>())
445 {
446 if constexpr (__member_empty<_Tp>)
447 return bool(__t.empty());
448 else if constexpr (__size0_empty<_Tp>)
449 return _Size{}(__t) == 0;
450 else
451 return bool(_Begin{}(__t) == _End{}(__t));
452 }
453 };
454
455 template<typename _Tp>
456 concept __pointer_to_object = is_pointer_v<_Tp>
457 && is_object_v<remove_pointer_t<_Tp>>;
458
459 template<typename _Tp>
460 concept __member_data = requires(_Tp& __t)
461 {
462 { __decay_copy(__t.data()) } -> __pointer_to_object;
463 };
464
465 template<typename _Tp>
466 concept __begin_data = contiguous_iterator<__range_iter_t<_Tp>>;
467
468 struct _Data
469 {
470 private:
471 template<typename _Tp>
472 static constexpr bool
473 _S_noexcept()
474 {
475 if constexpr (__member_data<_Tp>)
476 return noexcept(__decay_copy(std::declval<_Tp&>().data()));
477 else
478 return noexcept(_Begin{}(std::declval<_Tp&>()));
479 }
480
481 public:
482 template<__maybe_borrowed_range _Tp>
483 requires __member_data<_Tp> || __begin_data<_Tp>
484 constexpr auto
485 operator()[[nodiscard]](_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 template<range _Range>
529 using const_iterator_t = const_iterator<iterator_t<_Range>>;
530
531 template<range _Range>
532 using const_sentinel_t = const_sentinel<sentinel_t<_Range>>;
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_t<decltype(__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_t<decltype(__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 namespace __detail
817 {
818 template<typename _Tp>
819 inline constexpr bool __is_initializer_list = false;
820
821 template<typename _Tp>
822 inline constexpr bool __is_initializer_list<initializer_list<_Tp>> = true;
823 } // namespace __detail
824
825 /// A range which can be safely converted to a view.
826 template<typename _Tp>
827 concept viewable_range = range<_Tp>
828 && ((view<remove_cvref_t<_Tp>> && constructible_from<remove_cvref_t<_Tp>, _Tp>)
829 || (!view<remove_cvref_t<_Tp>>
830 && (is_lvalue_reference_v<_Tp>
831 || (movable<remove_reference_t<_Tp>>
832 && !__detail::__is_initializer_list<remove_cvref_t<_Tp>>))));
833
834 // [range.iter.ops] range iterator operations
835
836 struct __advance_fn final
837 {
838 template<input_or_output_iterator _It>
839 constexpr void
840 operator()(_It& __it, iter_difference_t<_It> __n) const
841 {
842 if constexpr (random_access_iterator<_It>)
843 __it += __n;
844 else if constexpr (bidirectional_iterator<_It>)
845 {
846 if (__n > 0)
847 {
848 do
849 {
850 ++__it;
851 }
852 while (--__n);
853 }
854 else if (__n < 0)
855 {
856 do
857 {
858 --__it;
859 }
860 while (++__n);
861 }
862 }
863 else
864 {
865 // cannot decrement a non-bidirectional iterator
866 __glibcxx_assert(__n >= 0);
867 while (__n-- > 0)
868 ++__it;
869 }
870 }
871
872 template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
873 constexpr void
874 operator()(_It& __it, _Sent __bound) const
875 {
876 if constexpr (assignable_from<_It&, _Sent>)
877 __it = std::move(__bound);
878 else if constexpr (sized_sentinel_for<_Sent, _It>)
879 (*this)(__it, __bound - __it);
880 else
881 {
882 while (__it != __bound)
883 ++__it;
884 }
885 }
886
887 template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
888 constexpr iter_difference_t<_It>
889 operator()(_It& __it, iter_difference_t<_It> __n, _Sent __bound) const
890 {
891 if constexpr (sized_sentinel_for<_Sent, _It>)
892 {
893 const auto __diff = __bound - __it;
894
895 if (__diff == 0)
896 return __n;
897 else if (__diff > 0 ? __n >= __diff : __n <= __diff)
898 {
899 (*this)(__it, __bound);
900 return __n - __diff;
901 }
902 else if (__n != 0) [[likely]]
903 {
904 // n and bound must not lead in opposite directions:
905 __glibcxx_assert((__n < 0) == (__diff < 0));
906
907 (*this)(__it, __n);
908 return 0;
909 }
910 else
911 return 0;
912 }
913 else if (__it == __bound || __n == 0)
914 return __n;
915 else if (__n > 0)
916 {
917 iter_difference_t<_It> __m = 0;
918 do
919 {
920 ++__it;
921 ++__m;
922 }
923 while (__m != __n && __it != __bound);
924 return __n - __m;
925 }
926 else if constexpr (bidirectional_iterator<_It> && same_as<_It, _Sent>)
927 {
928 iter_difference_t<_It> __m = 0;
929 do
930 {
931 --__it;
932 --__m;
933 }
934 while (__m != __n && __it != __bound);
935 return __n - __m;
936 }
937 else
938 {
939 // cannot decrement a non-bidirectional iterator
940 __glibcxx_assert(__n >= 0);
941 return __n;
942 }
943 }
944
945 void operator&() const = delete;
946 };
947
948 inline constexpr __advance_fn advance{};
949
950 struct __distance_fn final
951 {
952 // _GLIBCXX_RESOLVE_LIB_DEFECTS
953 // 3664. LWG 3392 broke std::ranges::distance(a, a+3)
954 template<typename _It, sentinel_for<_It> _Sent>
955 requires (!sized_sentinel_for<_Sent, _It>)
956 constexpr iter_difference_t<_It>
957 operator()[[nodiscard]](_It __first, _Sent __last) const
958 {
959 iter_difference_t<_It> __n = 0;
960 while (__first != __last)
961 {
962 ++__first;
963 ++__n;
964 }
965 return __n;
966 }
967
968 template<typename _It, sized_sentinel_for<decay_t<_It>> _Sent>
969 [[nodiscard]]
970 constexpr iter_difference_t<decay_t<_It>>
971 operator()(_It&& __first, _Sent __last) const
972 { return __last - static_cast<const decay_t<_It>&>(__first); }
973
974 template<range _Range>
975 [[nodiscard]]
976 constexpr range_difference_t<_Range>
977 operator()(_Range&& __r) const
978 {
979 if constexpr (sized_range<_Range>)
980 return static_cast<range_difference_t<_Range>>(ranges::size(__r));
981 else
982 return (*this)(ranges::begin(__r), ranges::end(__r));
983 }
984
985 void operator&() const = delete;
986 };
987
988 inline constexpr __distance_fn distance{};
989
990 struct __next_fn final
991 {
992 template<input_or_output_iterator _It>
993 [[nodiscard]]
994 constexpr _It
995 operator()(_It __x) const
996 {
997 ++__x;
998 return __x;
999 }
1000
1001 template<input_or_output_iterator _It>
1002 [[nodiscard]]
1003 constexpr _It
1004 operator()(_It __x, iter_difference_t<_It> __n) const
1005 {
1006 ranges::advance(__x, __n);
1007 return __x;
1008 }
1009
1010 template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
1011 [[nodiscard]]
1012 constexpr _It
1013 operator()(_It __x, _Sent __bound) const
1014 {
1015 ranges::advance(__x, __bound);
1016 return __x;
1017 }
1018
1019 template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
1020 [[nodiscard]]
1021 constexpr _It
1022 operator()(_It __x, iter_difference_t<_It> __n, _Sent __bound) const
1023 {
1024 ranges::advance(__x, __n, __bound);
1025 return __x;
1026 }
1027
1028 void operator&() const = delete;
1029 };
1030
1031 inline constexpr __next_fn next{};
1032
1033 struct __prev_fn final
1034 {
1035 template<bidirectional_iterator _It>
1036 [[nodiscard]]
1037 constexpr _It
1038 operator()(_It __x) const
1039 {
1040 --__x;
1041 return __x;
1042 }
1043
1044 template<bidirectional_iterator _It>
1045 [[nodiscard]]
1046 constexpr _It
1047 operator()(_It __x, iter_difference_t<_It> __n) const
1048 {
1049 ranges::advance(__x, -__n);
1050 return __x;
1051 }
1052
1053 template<bidirectional_iterator _It>
1054 [[nodiscard]]
1055 constexpr _It
1056 operator()(_It __x, iter_difference_t<_It> __n, _It __bound) const
1057 {
1058 ranges::advance(__x, -__n, __bound);
1059 return __x;
1060 }
1061
1062 void operator&() const = delete;
1063 };
1064
1065 inline constexpr __prev_fn prev{};
1066
1067 /// Type returned by algorithms instead of a dangling iterator or subrange.
1068 struct dangling
1069 {
1070 constexpr dangling() noexcept = default;
1071 template<typename... _Args>
1072 constexpr dangling(_Args&&...) noexcept { }
1073 };
1074
1075 template<range _Range>
1076 using borrowed_iterator_t = __conditional_t<borrowed_range<_Range>,
1077 iterator_t<_Range>,
1078 dangling>;
1079} // namespace ranges
1080
1081#if __glibcxx_ranges_to_container // C++ >= 23
1082 struct from_range_t { explicit from_range_t() = default; };
1083 inline constexpr from_range_t from_range{};
1084
1085/// @cond undocumented
1086namespace __detail
1087{
1088 template<typename _Rg, typename _Tp>
1089 concept __container_compatible_range
1090 = ranges::input_range<_Rg>
1091 && convertible_to<ranges::range_reference_t<_Rg>, _Tp>;
1092
1093 template<ranges::input_range _Range>
1094 using __range_key_type
1095 = remove_const_t<typename ranges::range_value_t<_Range>::first_type>;
1096
1097 template<ranges::input_range _Range>
1098 using __range_mapped_type
1099 = typename ranges::range_value_t<_Range>::second_type;
1100}
1101/// @endcond
1102#endif
1103
1104_GLIBCXX_END_NAMESPACE_VERSION
1105} // namespace std
1106#endif // library concepts
1107#pragma GCC diagnostic pop
1108#endif // C++20
1109#endif // _GLIBCXX_RANGES_BASE_H
constexpr _Tp * to_address(_Tp *__ptr) noexcept
Obtain address referenced by a pointer to an object.
Definition ptr_traits.h:232
typename make_unsigned< _Tp >::type make_unsigned_t
Alias template for make_unsigned.
Definition type_traits:2141
auto declval() noexcept -> decltype(__declval< _Tp >(0))
Definition type_traits:2609
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
Definition move.h:138
constexpr _Tp && forward(typename std::remove_reference< _Tp >::type &__t) noexcept
Forward an lvalue.
Definition move.h:72
_Tp * end(valarray< _Tp > &__va) noexcept
Return an iterator pointing to one past the last element of the valarray.
Definition valarray:1251
_Tp * begin(valarray< _Tp > &__va) noexcept
Return an iterator pointing to the first element of the valarray.
Definition valarray:1229
constexpr reverse_iterator< _Iterator > make_reverse_iterator(_Iterator __i)
Generator function for reverse_iterator.
ISO C++ entities toplevel namespace is std.
constexpr auto rbegin(_Container &__cont) noexcept(noexcept(__cont.rbegin())) -> decltype(__cont.rbegin())
Return a reverse iterator pointing to the last element of the container.
constexpr iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
constexpr auto cend(const _Container &__cont) noexcept(noexcept(std::end(__cont))) -> decltype(std::end(__cont))
Return an iterator pointing to one past the last element of the const container.
constexpr auto empty(const _Container &__cont) noexcept(noexcept(__cont.empty())) -> decltype(__cont.empty())
Return whether a container is empty.
constexpr auto crbegin(const _Container &__cont) noexcept(noexcept(std::rbegin(__cont))) -> decltype(std::rbegin(__cont))
Return a reverse iterator pointing to the last element of the const container.
constexpr auto size(const _Container &__cont) noexcept(noexcept(__cont.size())) -> decltype(__cont.size())
Return the size of a container.
constexpr void advance(_InputIterator &__i, _Distance __n)
A generalization of pointer arithmetic.
constexpr auto data(_Container &__cont) noexcept(noexcept(__cont.data())) -> decltype(__cont.data())
Return the data pointer of a container.
constexpr auto cbegin(const _Container &__cont) noexcept(noexcept(std::begin(__cont))) -> decltype(std::begin(__cont))
Return an iterator pointing to the first element of the const container.
constexpr auto rend(_Container &__cont) noexcept(noexcept(__cont.rend())) -> decltype(__cont.rend())
Return a reverse iterator pointing one past the first element of the container.
constexpr bitset< _Nb > operator&(const bitset< _Nb > &__x, const bitset< _Nb > &__y) noexcept
Global bitwise operations on bitsets.
Definition bitset:1562
constexpr auto crend(const _Container &__cont) noexcept(noexcept(std::rend(__cont))) -> decltype(std::rend(__cont))
Return a reverse iterator pointing one past the first element of the const container.
Implementation details not part of the namespace std interface.
__numeric_traits_integer< _Tp > __int_traits
Convenience alias for __numeric_traits<integer-type>.
The ranges::view_interface class template.
Definition ranges_util.h:65