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