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 {
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<input_range _Range>
635 constexpr auto&
636 __possibly_const_range(_Range& __r) noexcept
637 {
638 // _GLIBCXX_RESOLVE_LIB_DEFECTS
639 // 4027. possibly-const-range should prefer returning const R&
640 if constexpr (input_range<const _Range>)
641 return const_cast<const _Range&>(__r);
642 else
643 return __r;
644 }
645#else
646 // If _To is an lvalue-reference, return const _Tp&, otherwise const _Tp&&.
647 template<typename _To, typename _Tp>
648 constexpr decltype(auto)
649 __as_const(_Tp& __t) noexcept
650 {
651 static_assert(std::is_same_v<_To&, _Tp&>);
652
653 if constexpr (is_lvalue_reference_v<_To>)
654 return const_cast<const _Tp&>(__t);
655 else
656 return static_cast<const _Tp&&>(__t);
657 }
658#endif
659
660 struct _CBegin
661 {
662#if __glibcxx_ranges_as_const // >= C++23
663 template<__maybe_borrowed_range _Tp>
664 [[nodiscard]]
665 constexpr auto
666 operator()(_Tp&& __t) const
667 noexcept(noexcept(std::make_const_iterator
668 (ranges::begin(__access::__possibly_const_range(__t)))))
669 requires requires { std::make_const_iterator
670 (ranges::begin(__access::__possibly_const_range(__t))); }
671 {
672 auto& __r = __access::__possibly_const_range(__t);
673 return const_iterator_t<decltype(__r)>(ranges::begin(__r));
674 }
675#else
676 template<typename _Tp>
677 [[nodiscard]]
678 constexpr auto
679 operator()(_Tp&& __e) const
680 noexcept(noexcept(_Begin{}(__access::__as_const<_Tp>(__e))))
681 requires requires { _Begin{}(__access::__as_const<_Tp>(__e)); }
682 {
683 return _Begin{}(__access::__as_const<_Tp>(__e));
684 }
685#endif
686 };
687
688 struct _CEnd final
689 {
690#if __glibcxx_ranges_as_const // >= C++23
691 template<__maybe_borrowed_range _Tp>
692 [[nodiscard]]
693 constexpr auto
694 operator()(_Tp&& __t) const
695 noexcept(noexcept(std::make_const_sentinel
696 (ranges::end(__access::__possibly_const_range(__t)))))
697 requires requires { std::make_const_sentinel
698 (ranges::end(__access::__possibly_const_range(__t))); }
699 {
700 auto& __r = __access::__possibly_const_range(__t);
701 return const_sentinel_t<decltype(__r)>(ranges::end(__r));
702 }
703#else
704 template<typename _Tp>
705 [[nodiscard]]
706 constexpr auto
707 operator()(_Tp&& __e) const
708 noexcept(noexcept(_End{}(__access::__as_const<_Tp>(__e))))
709 requires requires { _End{}(__access::__as_const<_Tp>(__e)); }
710 {
711 return _End{}(__access::__as_const<_Tp>(__e));
712 }
713#endif
714 };
715
716 struct _CRBegin
717 {
718#if __glibcxx_ranges_as_const // >= C++23
719 template<__maybe_borrowed_range _Tp>
720 [[nodiscard]]
721 constexpr auto
722 operator()(_Tp&& __t) const
723 noexcept(noexcept(std::make_const_iterator
724 (ranges::rbegin(__access::__possibly_const_range(__t)))))
725 requires requires { std::make_const_iterator
726 (ranges::rbegin(__access::__possibly_const_range(__t))); }
727 {
728 auto& __r = __access::__possibly_const_range(__t);
729 return const_iterator<decltype(ranges::rbegin(__r))>(ranges::rbegin(__r));
730 }
731#else
732 template<typename _Tp>
733 [[nodiscard]]
734 constexpr auto
735 operator()(_Tp&& __e) const
736 noexcept(noexcept(_RBegin{}(__access::__as_const<_Tp>(__e))))
737 requires requires { _RBegin{}(__access::__as_const<_Tp>(__e)); }
738 {
739 return _RBegin{}(__access::__as_const<_Tp>(__e));
740 }
741#endif
742 };
743
744 struct _CREnd
745 {
746#if __glibcxx_ranges_as_const // >= C++23
747 template<__maybe_borrowed_range _Tp>
748 [[nodiscard]]
749 constexpr auto
750 operator()(_Tp&& __t) const
751 noexcept(noexcept(std::make_const_sentinel
752 (ranges::rend(__access::__possibly_const_range(__t)))))
753 requires requires { std::make_const_sentinel
754 (ranges::rend(__access::__possibly_const_range(__t))); }
755 {
756 auto& __r = __access::__possibly_const_range(__t);
757 return const_sentinel<decltype(ranges::rend(__r))>(ranges::rend(__r));
758 }
759#else
760 template<typename _Tp>
761 [[nodiscard]]
762 constexpr auto
763 operator()(_Tp&& __e) const
764 noexcept(noexcept(_REnd{}(__access::__as_const<_Tp>(__e))))
765 requires requires { _REnd{}(__access::__as_const<_Tp>(__e)); }
766 {
767 return _REnd{}(__access::__as_const<_Tp>(__e));
768 }
769#endif
770 };
771
772 struct _CData
773 {
774#if __glibcxx_ranges_as_const // >= C++23
775 template<__maybe_borrowed_range _Tp>
776 [[nodiscard]]
777 constexpr const auto*
778 operator()(_Tp&& __t) const
779 noexcept(noexcept(ranges::data(__access::__possibly_const_range(__t))))
780 requires requires { ranges::data(__access::__possibly_const_range(__t)); }
781 { return ranges::data(__access::__possibly_const_range(__t)); }
782#else
783 template<typename _Tp>
784 [[nodiscard]]
785 constexpr auto
786 operator()(_Tp&& __e) const
787 noexcept(noexcept(_Data{}(__access::__as_const<_Tp>(__e))))
788 requires requires { _Data{}(__access::__as_const<_Tp>(__e)); }
789 {
790 return _Data{}(__access::__as_const<_Tp>(__e));
791 }
792#endif
793 };
794 } // namespace __access
795
796 inline namespace _Cpo
797 {
798 inline constexpr ranges::__access::_CBegin cbegin{};
799 inline constexpr ranges::__access::_CEnd cend{};
800 inline constexpr ranges::__access::_CRBegin crbegin{};
801 inline constexpr ranges::__access::_CREnd crend{};
802 inline constexpr ranges::__access::_CData cdata{};
803 }
804
805 namespace __detail
806 {
807 template<typename _Tp>
808 inline constexpr bool __is_initializer_list = false;
809
810 template<typename _Tp>
811 inline constexpr bool __is_initializer_list<initializer_list<_Tp>> = true;
812 } // namespace __detail
813
814 /// A range which can be safely converted to a view.
815 template<typename _Tp>
816 concept viewable_range = range<_Tp>
817 && ((view<remove_cvref_t<_Tp>> && constructible_from<remove_cvref_t<_Tp>, _Tp>)
818 || (!view<remove_cvref_t<_Tp>>
819 && (is_lvalue_reference_v<_Tp>
820 || (movable<remove_reference_t<_Tp>>
821 && !__detail::__is_initializer_list<remove_cvref_t<_Tp>>))));
822
823 // [range.iter.ops] range iterator operations
824
825 struct __advance_fn final
826 {
827 template<input_or_output_iterator _It>
828 constexpr void
829 operator()(_It& __it, iter_difference_t<_It> __n) const
830 {
831 if constexpr (random_access_iterator<_It>)
832 __it += __n;
833 else if constexpr (bidirectional_iterator<_It>)
834 {
835 if (__n > 0)
836 {
837 do
838 {
839 ++__it;
840 }
841 while (--__n);
842 }
843 else if (__n < 0)
844 {
845 do
846 {
847 --__it;
848 }
849 while (++__n);
850 }
851 }
852 else
853 {
854 // cannot decrement a non-bidirectional iterator
855 __glibcxx_assert(__n >= 0);
856 while (__n-- > 0)
857 ++__it;
858 }
859 }
860
861 template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
862 constexpr void
863 operator()(_It& __it, _Sent __bound) const
864 {
865 if constexpr (assignable_from<_It&, _Sent>)
866 __it = std::move(__bound);
867 else if constexpr (sized_sentinel_for<_Sent, _It>)
868 (*this)(__it, __bound - __it);
869 else
870 {
871 while (__it != __bound)
872 ++__it;
873 }
874 }
875
876 template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
877 constexpr iter_difference_t<_It>
878 operator()(_It& __it, iter_difference_t<_It> __n, _Sent __bound) const
879 {
880 if constexpr (sized_sentinel_for<_Sent, _It>)
881 {
882 const auto __diff = __bound - __it;
883
884 if (__diff == 0)
885 return __n;
886 else if (__diff > 0 ? __n >= __diff : __n <= __diff)
887 {
888 (*this)(__it, __bound);
889 return __n - __diff;
890 }
891 else if (__n != 0) [[likely]]
892 {
893 // n and bound must not lead in opposite directions:
894 __glibcxx_assert((__n < 0) == (__diff < 0));
895
896 (*this)(__it, __n);
897 return 0;
898 }
899 else
900 return 0;
901 }
902 else if (__it == __bound || __n == 0)
903 return __n;
904 else if (__n > 0)
905 {
906 iter_difference_t<_It> __m = 0;
907 do
908 {
909 ++__it;
910 ++__m;
911 }
912 while (__m != __n && __it != __bound);
913 return __n - __m;
914 }
915 else if constexpr (bidirectional_iterator<_It> && same_as<_It, _Sent>)
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
927 {
928 // cannot decrement a non-bidirectional iterator
929 __glibcxx_assert(__n >= 0);
930 return __n;
931 }
932 }
933
934 void operator&() const = delete;
935 };
936
937 inline constexpr __advance_fn advance{};
938
939 struct __distance_fn final
940 {
941 // _GLIBCXX_RESOLVE_LIB_DEFECTS
942 // 3664. LWG 3392 broke std::ranges::distance(a, a+3)
943 template<typename _It, sentinel_for<_It> _Sent>
944 requires (!sized_sentinel_for<_Sent, _It>)
945 constexpr iter_difference_t<_It>
946 operator()[[nodiscard]](_It __first, _Sent __last) const
947 {
948 iter_difference_t<_It> __n = 0;
949 while (__first != __last)
950 {
951 ++__first;
952 ++__n;
953 }
954 return __n;
955 }
956
957 template<typename _It, sized_sentinel_for<decay_t<_It>> _Sent>
958 [[nodiscard]]
959 constexpr iter_difference_t<decay_t<_It>>
960 operator()(_It&& __first, _Sent __last) const
961 { return __last - static_cast<const decay_t<_It>&>(__first); }
962
963 template<range _Range>
964 [[nodiscard]]
965 constexpr range_difference_t<_Range>
966 operator()(_Range&& __r) const
967 {
968 if constexpr (sized_range<_Range>)
969 return static_cast<range_difference_t<_Range>>(ranges::size(__r));
970 else
971 return (*this)(ranges::begin(__r), ranges::end(__r));
972 }
973
974 void operator&() const = delete;
975 };
976
977 inline constexpr __distance_fn distance{};
978
979 struct __next_fn final
980 {
981 template<input_or_output_iterator _It>
982 [[nodiscard]]
983 constexpr _It
984 operator()(_It __x) const
985 {
986 ++__x;
987 return __x;
988 }
989
990 template<input_or_output_iterator _It>
991 [[nodiscard]]
992 constexpr _It
993 operator()(_It __x, iter_difference_t<_It> __n) const
994 {
995 ranges::advance(__x, __n);
996 return __x;
997 }
998
999 template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
1000 [[nodiscard]]
1001 constexpr _It
1002 operator()(_It __x, _Sent __bound) const
1003 {
1004 ranges::advance(__x, __bound);
1005 return __x;
1006 }
1007
1008 template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
1009 [[nodiscard]]
1010 constexpr _It
1011 operator()(_It __x, iter_difference_t<_It> __n, _Sent __bound) const
1012 {
1013 ranges::advance(__x, __n, __bound);
1014 return __x;
1015 }
1016
1017 void operator&() const = delete;
1018 };
1019
1020 inline constexpr __next_fn next{};
1021
1022 struct __prev_fn final
1023 {
1024 template<bidirectional_iterator _It>
1025 [[nodiscard]]
1026 constexpr _It
1027 operator()(_It __x) const
1028 {
1029 --__x;
1030 return __x;
1031 }
1032
1033 template<bidirectional_iterator _It>
1034 [[nodiscard]]
1035 constexpr _It
1036 operator()(_It __x, iter_difference_t<_It> __n) const
1037 {
1038 ranges::advance(__x, -__n);
1039 return __x;
1040 }
1041
1042 template<bidirectional_iterator _It>
1043 [[nodiscard]]
1044 constexpr _It
1045 operator()(_It __x, iter_difference_t<_It> __n, _It __bound) const
1046 {
1047 ranges::advance(__x, -__n, __bound);
1048 return __x;
1049 }
1050
1051 void operator&() const = delete;
1052 };
1053
1054 inline constexpr __prev_fn prev{};
1055
1056 /// Type returned by algorithms instead of a dangling iterator or subrange.
1057 struct dangling
1058 {
1059 constexpr dangling() noexcept = default;
1060 template<typename... _Args>
1061 constexpr dangling(_Args&&...) noexcept { }
1062 };
1063
1064 template<range _Range>
1065 using borrowed_iterator_t = __conditional_t<borrowed_range<_Range>,
1066 iterator_t<_Range>,
1067 dangling>;
1068} // namespace ranges
1069
1070#if __glibcxx_ranges_to_container // C++ >= 23
1071 struct from_range_t { explicit from_range_t() = default; };
1072 inline constexpr from_range_t from_range{};
1073#endif
1074
1075_GLIBCXX_END_NAMESPACE_VERSION
1076} // namespace std
1077#endif // library concepts
1078#endif // C++20
1079#endif // _GLIBCXX_RANGES_BASE_H
strong_ordering operator(const error_code &__lhs, const error_code &__rhs) noexcept
Definition system_error:316
constexpr _Tp * to_address(_Tp *__ptr) noexcept
Obtain address referenced by a pointer to an object.
Definition ptr_traits.h:241
typename make_unsigned< _Tp >::type make_unsigned_t
Alias template for make_unsigned.
Definition type_traits:2074
auto declval() noexcept -> decltype(__declval< _Tp >(0))
Definition type_traits:2483
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
Definition move.h:137
constexpr _Tp && forward(typename std::remove_reference< _Tp >::type &__t) noexcept
Forward an lvalue.
Definition move.h:71
_Tp * end(valarray< _Tp > &__va) noexcept
Return an iterator pointing to one past the last element of the valarray.
Definition valarray:1249
_Tp * begin(valarray< _Tp > &__va) noexcept
Return an iterator pointing to the first element of the valarray.
Definition valarray:1227
constexpr reverse_iterator< _Iterator > make_reverse_iterator(_Iterator __i)
Generator function for reverse_iterator.
ISO C++ entities toplevel namespace is std.
constexpr auto crend(const _Container &__cont) -> decltype(std::rend(__cont))
Return a reverse iterator pointing one past the first element of the const container.
constexpr auto rend(_Container &__cont) -> decltype(__cont.rend())
Return a reverse iterator pointing one past the first 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 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 rbegin(_Container &__cont) -> decltype(__cont.rbegin())
Return a reverse iterator pointing to the last element of the container.
constexpr auto crbegin(const _Container &__cont) -> decltype(std::rbegin(__cont))
Return a reverse iterator pointing to the last element of the const container.
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 bitset< _Nb > operator&(const bitset< _Nb > &__x, const bitset< _Nb > &__y) noexcept
Global bitwise operations on bitsets.
Definition bitset:1557
__numeric_traits_integer< _Tp > __int_traits
Convenience alias for __numeric_traits<integer-type>.