Line data Source code
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
41 : namespace std _GLIBCXX_VISIBILITY(default)
42 : {
43 : _GLIBCXX_BEGIN_NAMESPACE_VERSION
44 : namespace 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 0 : operator()(_It& __it, _Sent __bound) const
715 : {
716 : if constexpr (assignable_from<_It&, _Sent>)
717 0 : __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 0 : }
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 0 : operator()(_It __x, _Sent __bound) const
842 : {
843 0 : ranges::advance(__x, __bound);
844 0 : 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
|
