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

source code of include/c++/11/bits/ranges_base.h