1// <ranges> -*- C++ -*- 2 3// Copyright (C) 2019-2022 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 include/ranges 26 * This is a Standard C++ Library header. 27 * @ingroup concepts 28 */ 29 30#ifndef _GLIBCXX_RANGES 31#define _GLIBCXX_RANGES 1 32 33#if __cplusplus > 201703L 34 35#pragma GCC system_header 36 37#include <concepts> 38 39#if __cpp_lib_concepts 40 41#include <compare> 42#include <initializer_list> 43#include <iterator> 44#include <optional> 45#include <span> 46#include <tuple> 47#include <bits/ranges_util.h> 48#include <bits/refwrap.h> 49 50/** 51 * @defgroup ranges Ranges 52 * 53 * Components for dealing with ranges of elements. 54 */ 55 56namespace std _GLIBCXX_VISIBILITY(default) 57{ 58_GLIBCXX_BEGIN_NAMESPACE_VERSION 59namespace ranges 60{ 61 // [range.access] customization point objects 62 // [range.req] range and view concepts 63 // [range.dangling] dangling iterator handling 64 // Defined in <bits/ranges_base.h> 65 66 // [view.interface] View interface 67 // [range.subrange] Sub-ranges 68 // Defined in <bits/ranges_util.h> 69 70 // C++20 24.6 [range.factories] Range factories 71 72 /// A view that contains no elements. 73 template<typename _Tp> requires is_object_v<_Tp> 74 class empty_view 75 : public view_interface<empty_view<_Tp>> 76 { 77 public: 78 static constexpr _Tp* begin() noexcept { return nullptr; } 79 static constexpr _Tp* end() noexcept { return nullptr; } 80 static constexpr _Tp* data() noexcept { return nullptr; } 81 static constexpr size_t size() noexcept { return 0; } 82 static constexpr bool empty() noexcept { return true; } 83 }; 84 85 template<typename _Tp> 86 inline constexpr bool enable_borrowed_range<empty_view<_Tp>> = true; 87 88 namespace __detail 89 { 90 template<typename _Tp> 91 concept __boxable = copy_constructible<_Tp> && is_object_v<_Tp>; 92 93 template<__boxable _Tp> 94 struct __box : std::optional<_Tp> 95 { 96 using std::optional<_Tp>::optional; 97 98 constexpr 99 __box() 100 noexcept(is_nothrow_default_constructible_v<_Tp>) 101 requires default_initializable<_Tp> 102 : std::optional<_Tp>{std::in_place} 103 { } 104 105 __box(const __box&) = default; 106 __box(__box&&) = default; 107 108 using std::optional<_Tp>::operator=; 109 110 // _GLIBCXX_RESOLVE_LIB_DEFECTS 111 // 3477. Simplify constraints for semiregular-box 112 // 3572. copyable-box should be fully constexpr 113 constexpr __box& 114 operator=(const __box& __that) 115 noexcept(is_nothrow_copy_constructible_v<_Tp>) 116 requires (!copyable<_Tp>) 117 { 118 if (this != std::__addressof(__that)) 119 { 120 if ((bool)__that) 121 this->emplace(*__that); 122 else 123 this->reset(); 124 } 125 return *this; 126 } 127 128 constexpr __box& 129 operator=(__box&& __that) 130 noexcept(is_nothrow_move_constructible_v<_Tp>) 131 requires (!movable<_Tp>) 132 { 133 if (this != std::__addressof(__that)) 134 { 135 if ((bool)__that) 136 this->emplace(std::move(*__that)); 137 else 138 this->reset(); 139 } 140 return *this; 141 } 142 }; 143 144 // For types which are already copyable, this specialization of the 145 // copyable wrapper stores the object directly without going through 146 // std::optional. It provides just the subset of the primary template's 147 // API that we currently use. 148 template<__boxable _Tp> 149 requires copyable<_Tp> || (is_nothrow_move_constructible_v<_Tp> 150 && is_nothrow_copy_constructible_v<_Tp>) 151 struct __box<_Tp> 152 { 153 private: 154 [[no_unique_address]] _Tp _M_value = _Tp(); 155 156 public: 157 __box() requires default_initializable<_Tp> = default; 158 159 constexpr explicit 160 __box(const _Tp& __t) 161 noexcept(is_nothrow_copy_constructible_v<_Tp>) 162 : _M_value(__t) 163 { } 164 165 constexpr explicit 166 __box(_Tp&& __t) 167 noexcept(is_nothrow_move_constructible_v<_Tp>) 168 : _M_value(std::move(__t)) 169 { } 170 171 template<typename... _Args> 172 requires constructible_from<_Tp, _Args...> 173 constexpr explicit 174 __box(in_place_t, _Args&&... __args) 175 noexcept(is_nothrow_constructible_v<_Tp, _Args...>) 176 : _M_value(std::forward<_Args>(__args)...) 177 { } 178 179 __box(const __box&) = default; 180 __box(__box&&) = default; 181 __box& operator=(const __box&) requires copyable<_Tp> = default; 182 __box& operator=(__box&&) requires copyable<_Tp> = default; 183 184 // When _Tp is nothrow_copy_constructible but not copy_assignable, 185 // copy assignment is implemented via destroy-then-copy-construct. 186 constexpr __box& 187 operator=(const __box& __that) noexcept 188 { 189 static_assert(is_nothrow_copy_constructible_v<_Tp>); 190 if (this != std::__addressof(__that)) 191 { 192 _M_value.~_Tp(); 193 std::construct_at(std::__addressof(_M_value), *__that); 194 } 195 return *this; 196 } 197 198 // Likewise for move assignment. 199 constexpr __box& 200 operator=(__box&& __that) noexcept 201 { 202 static_assert(is_nothrow_move_constructible_v<_Tp>); 203 if (this != std::__addressof(__that)) 204 { 205 _M_value.~_Tp(); 206 std::construct_at(std::__addressof(_M_value), std::move(*__that)); 207 } 208 return *this; 209 } 210 211 constexpr bool 212 has_value() const noexcept 213 { return true; }; 214 215 constexpr _Tp& 216 operator*() noexcept 217 { return _M_value; } 218 219 constexpr const _Tp& 220 operator*() const noexcept 221 { return _M_value; } 222 223 constexpr _Tp* 224 operator->() noexcept 225 { return std::__addressof(_M_value); } 226 227 constexpr const _Tp* 228 operator->() const noexcept 229 { return std::__addressof(_M_value); } 230 }; 231 } // namespace __detail 232 233 /// A view that contains exactly one element. 234 template<copy_constructible _Tp> requires is_object_v<_Tp> 235 class single_view : public view_interface<single_view<_Tp>> 236 { 237 public: 238 single_view() requires default_initializable<_Tp> = default; 239 240 constexpr explicit 241 single_view(const _Tp& __t) 242 noexcept(is_nothrow_copy_constructible_v<_Tp>) 243 : _M_value(__t) 244 { } 245 246 constexpr explicit 247 single_view(_Tp&& __t) 248 noexcept(is_nothrow_move_constructible_v<_Tp>) 249 : _M_value(std::move(__t)) 250 { } 251 252 // _GLIBCXX_RESOLVE_LIB_DEFECTS 253 // 3428. single_view's in place constructor should be explicit 254 template<typename... _Args> 255 requires constructible_from<_Tp, _Args...> 256 constexpr explicit 257 single_view(in_place_t, _Args&&... __args) 258 noexcept(is_nothrow_constructible_v<_Tp, _Args...>) 259 : _M_value{in_place, std::forward<_Args>(__args)...} 260 { } 261 262 constexpr _Tp* 263 begin() noexcept 264 { return data(); } 265 266 constexpr const _Tp* 267 begin() const noexcept 268 { return data(); } 269 270 constexpr _Tp* 271 end() noexcept 272 { return data() + 1; } 273 274 constexpr const _Tp* 275 end() const noexcept 276 { return data() + 1; } 277 278 static constexpr size_t 279 size() noexcept 280 { return 1; } 281 282 constexpr _Tp* 283 data() noexcept 284 { return _M_value.operator->(); } 285 286 constexpr const _Tp* 287 data() const noexcept 288 { return _M_value.operator->(); } 289 290 private: 291 [[no_unique_address]] __detail::__box<_Tp> _M_value; 292 }; 293 294 template<typename _Tp> 295 single_view(_Tp) -> single_view<_Tp>; 296 297 namespace __detail 298 { 299 template<typename _Wp> 300 constexpr auto __to_signed_like(_Wp __w) noexcept 301 { 302 if constexpr (!integral<_Wp>) 303 return iter_difference_t<_Wp>(); 304 else if constexpr (sizeof(iter_difference_t<_Wp>) > sizeof(_Wp)) 305 return iter_difference_t<_Wp>(__w); 306 else if constexpr (sizeof(ptrdiff_t) > sizeof(_Wp)) 307 return ptrdiff_t(__w); 308 else if constexpr (sizeof(long long) > sizeof(_Wp)) 309 return (long long)(__w); 310#ifdef __SIZEOF_INT128__ 311 else if constexpr (__SIZEOF_INT128__ > sizeof(_Wp)) 312 return __int128(__w); 313#endif 314 else 315 return __max_diff_type(__w); 316 } 317 318 template<typename _Wp> 319 using __iota_diff_t = decltype(__to_signed_like(std::declval<_Wp>())); 320 321 template<typename _It> 322 concept __decrementable = incrementable<_It> 323 && requires(_It __i) 324 { 325 { --__i } -> same_as<_It&>; 326 { __i-- } -> same_as<_It>; 327 }; 328 329 template<typename _It> 330 concept __advanceable = __decrementable<_It> && totally_ordered<_It> 331 && requires( _It __i, const _It __j, const __iota_diff_t<_It> __n) 332 { 333 { __i += __n } -> same_as<_It&>; 334 { __i -= __n } -> same_as<_It&>; 335 _It(__j + __n); 336 _It(__n + __j); 337 _It(__j - __n); 338 { __j - __j } -> convertible_to<__iota_diff_t<_It>>; 339 }; 340 341 template<typename _Winc> 342 struct __iota_view_iter_cat 343 { }; 344 345 template<incrementable _Winc> 346 struct __iota_view_iter_cat<_Winc> 347 { using iterator_category = input_iterator_tag; }; 348 } // namespace __detail 349 350 template<weakly_incrementable _Winc, 351 semiregular _Bound = unreachable_sentinel_t> 352 requires std::__detail::__weakly_eq_cmp_with<_Winc, _Bound> 353 && copyable<_Winc> 354 class iota_view : public view_interface<iota_view<_Winc, _Bound>> 355 { 356 private: 357 struct _Sentinel; 358 359 struct _Iterator : __detail::__iota_view_iter_cat<_Winc> 360 { 361 private: 362 static auto 363 _S_iter_concept() 364 { 365 using namespace __detail; 366 if constexpr (__advanceable<_Winc>) 367 return random_access_iterator_tag{}; 368 else if constexpr (__decrementable<_Winc>) 369 return bidirectional_iterator_tag{}; 370 else if constexpr (incrementable<_Winc>) 371 return forward_iterator_tag{}; 372 else 373 return input_iterator_tag{}; 374 } 375 376 public: 377 using iterator_concept = decltype(_S_iter_concept()); 378 // iterator_category defined in __iota_view_iter_cat 379 using value_type = _Winc; 380 using difference_type = __detail::__iota_diff_t<_Winc>; 381 382 _Iterator() requires default_initializable<_Winc> = default; 383 384 constexpr explicit 385 _Iterator(_Winc __value) 386 : _M_value(__value) { } 387 388 constexpr _Winc 389 operator*() const noexcept(is_nothrow_copy_constructible_v<_Winc>) 390 { return _M_value; } 391 392 constexpr _Iterator& 393 operator++() 394 { 395 ++_M_value; 396 return *this; 397 } 398 399 constexpr void 400 operator++(int) 401 { ++*this; } 402 403 constexpr _Iterator 404 operator++(int) requires incrementable<_Winc> 405 { 406 auto __tmp = *this; 407 ++*this; 408 return __tmp; 409 } 410 411 constexpr _Iterator& 412 operator--() requires __detail::__decrementable<_Winc> 413 { 414 --_M_value; 415 return *this; 416 } 417 418 constexpr _Iterator 419 operator--(int) requires __detail::__decrementable<_Winc> 420 { 421 auto __tmp = *this; 422 --*this; 423 return __tmp; 424 } 425 426 constexpr _Iterator& 427 operator+=(difference_type __n) requires __detail::__advanceable<_Winc> 428 { 429 using __detail::__is_integer_like; 430 using __detail::__is_signed_integer_like; 431 if constexpr (__is_integer_like<_Winc> 432 && !__is_signed_integer_like<_Winc>) 433 { 434 if (__n >= difference_type(0)) 435 _M_value += static_cast<_Winc>(__n); 436 else 437 _M_value -= static_cast<_Winc>(-__n); 438 } 439 else 440 _M_value += __n; 441 return *this; 442 } 443 444 constexpr _Iterator& 445 operator-=(difference_type __n) requires __detail::__advanceable<_Winc> 446 { 447 using __detail::__is_integer_like; 448 using __detail::__is_signed_integer_like; 449 if constexpr (__is_integer_like<_Winc> 450 && !__is_signed_integer_like<_Winc>) 451 { 452 if (__n >= difference_type(0)) 453 _M_value -= static_cast<_Winc>(__n); 454 else 455 _M_value += static_cast<_Winc>(-__n); 456 } 457 else 458 _M_value -= __n; 459 return *this; 460 } 461 462 constexpr _Winc 463 operator[](difference_type __n) const 464 requires __detail::__advanceable<_Winc> 465 { return _Winc(_M_value + __n); } 466 467 friend constexpr bool 468 operator==(const _Iterator& __x, const _Iterator& __y) 469 requires equality_comparable<_Winc> 470 { return __x._M_value == __y._M_value; } 471 472 friend constexpr bool 473 operator<(const _Iterator& __x, const _Iterator& __y) 474 requires totally_ordered<_Winc> 475 { return __x._M_value < __y._M_value; } 476 477 friend constexpr bool 478 operator>(const _Iterator& __x, const _Iterator& __y) 479 requires totally_ordered<_Winc> 480 { return __y < __x; } 481 482 friend constexpr bool 483 operator<=(const _Iterator& __x, const _Iterator& __y) 484 requires totally_ordered<_Winc> 485 { return !(__y < __x); } 486 487 friend constexpr bool 488 operator>=(const _Iterator& __x, const _Iterator& __y) 489 requires totally_ordered<_Winc> 490 { return !(__x < __y); } 491 492#ifdef __cpp_lib_three_way_comparison 493 friend constexpr auto 494 operator<=>(const _Iterator& __x, const _Iterator& __y) 495 requires totally_ordered<_Winc> && three_way_comparable<_Winc> 496 { return __x._M_value <=> __y._M_value; } 497#endif 498 499 friend constexpr _Iterator 500 operator+(_Iterator __i, difference_type __n) 501 requires __detail::__advanceable<_Winc> 502 { 503 __i += __n; 504 return __i; 505 } 506 507 friend constexpr _Iterator 508 operator+(difference_type __n, _Iterator __i) 509 requires __detail::__advanceable<_Winc> 510 { return __i += __n; } 511 512 friend constexpr _Iterator 513 operator-(_Iterator __i, difference_type __n) 514 requires __detail::__advanceable<_Winc> 515 { 516 __i -= __n; 517 return __i; 518 } 519 520 friend constexpr difference_type 521 operator-(const _Iterator& __x, const _Iterator& __y) 522 requires __detail::__advanceable<_Winc> 523 { 524 using __detail::__is_integer_like; 525 using __detail::__is_signed_integer_like; 526 using _Dt = difference_type; 527 if constexpr (__is_integer_like<_Winc>) 528 { 529 if constexpr (__is_signed_integer_like<_Winc>) 530 return _Dt(_Dt(__x._M_value) - _Dt(__y._M_value)); 531 else 532 return (__y._M_value > __x._M_value) 533 ? _Dt(-_Dt(__y._M_value - __x._M_value)) 534 : _Dt(__x._M_value - __y._M_value); 535 } 536 else 537 return __x._M_value - __y._M_value; 538 } 539 540 private: 541 _Winc _M_value = _Winc(); 542 543 friend iota_view; 544 friend _Sentinel; 545 }; 546 547 struct _Sentinel 548 { 549 private: 550 constexpr bool 551 _M_equal(const _Iterator& __x) const 552 { return __x._M_value == _M_bound; } 553 554 constexpr auto 555 _M_distance_from(const _Iterator& __x) const 556 { return _M_bound - __x._M_value; } 557 558 _Bound _M_bound = _Bound(); 559 560 public: 561 _Sentinel() = default; 562 563 constexpr explicit 564 _Sentinel(_Bound __bound) 565 : _M_bound(__bound) { } 566 567 friend constexpr bool 568 operator==(const _Iterator& __x, const _Sentinel& __y) 569 { return __y._M_equal(__x); } 570 571 friend constexpr iter_difference_t<_Winc> 572 operator-(const _Iterator& __x, const _Sentinel& __y) 573 requires sized_sentinel_for<_Bound, _Winc> 574 { return -__y._M_distance_from(__x); } 575 576 friend constexpr iter_difference_t<_Winc> 577 operator-(const _Sentinel& __x, const _Iterator& __y) 578 requires sized_sentinel_for<_Bound, _Winc> 579 { return __x._M_distance_from(__y); } 580 581 friend iota_view; 582 }; 583 584 _Winc _M_value = _Winc(); 585 [[no_unique_address]] _Bound _M_bound = _Bound(); 586 587 public: 588 iota_view() requires default_initializable<_Winc> = default; 589 590 constexpr explicit 591 iota_view(_Winc __value) 592 : _M_value(__value) 593 { } 594 595 constexpr 596 iota_view(type_identity_t<_Winc> __value, 597 type_identity_t<_Bound> __bound) 598 : _M_value(__value), _M_bound(__bound) 599 { 600 if constexpr (totally_ordered_with<_Winc, _Bound>) 601 __glibcxx_assert( bool(__value <= __bound) ); 602 } 603 604 constexpr 605 iota_view(_Iterator __first, _Iterator __last) 606 requires same_as<_Winc, _Bound> 607 : iota_view(__first._M_value, __last._M_value) 608 { } 609 610 constexpr 611 iota_view(_Iterator __first, unreachable_sentinel_t __last) 612 requires same_as<_Bound, unreachable_sentinel_t> 613 : iota_view(__first._M_value, __last) 614 { } 615 616 constexpr 617 iota_view(_Iterator __first, _Sentinel __last) 618 requires (!same_as<_Winc, _Bound>) && (!same_as<_Bound, unreachable_sentinel_t>) 619 : iota_view(__first._M_value, __last._M_bound) 620 { } 621 622 constexpr _Iterator 623 begin() const { return _Iterator{_M_value}; } 624 625 constexpr auto 626 end() const 627 { 628 if constexpr (same_as<_Bound, unreachable_sentinel_t>) 629 return unreachable_sentinel; 630 else 631 return _Sentinel{_M_bound}; 632 } 633 634 constexpr _Iterator 635 end() const requires same_as<_Winc, _Bound> 636 { return _Iterator{_M_bound}; } 637 638 constexpr auto 639 size() const 640 requires (same_as<_Winc, _Bound> && __detail::__advanceable<_Winc>) 641 || (integral<_Winc> && integral<_Bound>) 642 || sized_sentinel_for<_Bound, _Winc> 643 { 644 using __detail::__is_integer_like; 645 using __detail::__to_unsigned_like; 646 if constexpr (integral<_Winc> && integral<_Bound>) 647 { 648 using _Up = make_unsigned_t<decltype(_M_bound - _M_value)>; 649 return _Up(_M_bound) - _Up(_M_value); 650 } 651 else if constexpr (__is_integer_like<_Winc>) 652 return __to_unsigned_like(_M_bound) - __to_unsigned_like(_M_value); 653 else 654 return __to_unsigned_like(_M_bound - _M_value); 655 } 656 }; 657 658 template<typename _Winc, typename _Bound> 659 requires (!__detail::__is_integer_like<_Winc> 660 || !__detail::__is_integer_like<_Bound> 661 || (__detail::__is_signed_integer_like<_Winc> 662 == __detail::__is_signed_integer_like<_Bound>)) 663 iota_view(_Winc, _Bound) -> iota_view<_Winc, _Bound>; 664 665 template<typename _Winc, typename _Bound> 666 inline constexpr bool 667 enable_borrowed_range<iota_view<_Winc, _Bound>> = true; 668 669namespace views 670{ 671 template<typename _Tp> 672 inline constexpr empty_view<_Tp> empty{}; 673 674 namespace __detail 675 { 676 template<typename _Tp> 677 concept __can_single_view 678 = requires { single_view<decay_t<_Tp>>(std::declval<_Tp>()); }; 679 } // namespace __detail 680 681 struct _Single 682 { 683 template<__detail::__can_single_view _Tp> 684 constexpr auto 685 operator() [[nodiscard]] (_Tp&& __e) const 686 noexcept(noexcept(single_view<decay_t<_Tp>>(std::forward<_Tp>(__e)))) 687 { return single_view<decay_t<_Tp>>(std::forward<_Tp>(__e)); } 688 }; 689 690 inline constexpr _Single single{}; 691 692 namespace __detail 693 { 694 template<typename... _Args> 695 concept __can_iota_view = requires { iota_view(std::declval<_Args>()...); }; 696 } // namespace __detail 697 698 struct _Iota 699 { 700 template<__detail::__can_iota_view _Tp> 701 constexpr auto 702 operator() [[nodiscard]] (_Tp&& __e) const 703 { return iota_view(std::forward<_Tp>(__e)); } 704 705 template<typename _Tp, typename _Up> 706 requires __detail::__can_iota_view<_Tp, _Up> 707 constexpr auto 708 operator() [[nodiscard]] (_Tp&& __e, _Up&& __f) const 709 { return iota_view(std::forward<_Tp>(__e), std::forward<_Up>(__f)); } 710 }; 711 712 inline constexpr _Iota iota{}; 713} // namespace views 714 715 namespace __detail 716 { 717 template<typename _Val, typename _CharT, typename _Traits> 718 concept __stream_extractable 719 = requires(basic_istream<_CharT, _Traits>& is, _Val& t) { is >> t; }; 720 } // namespace __detail 721 722 template<movable _Val, typename _CharT, 723 typename _Traits = char_traits<_CharT>> 724 requires default_initializable<_Val> 725 && __detail::__stream_extractable<_Val, _CharT, _Traits> 726 class basic_istream_view 727 : public view_interface<basic_istream_view<_Val, _CharT, _Traits>> 728 { 729 public: 730 constexpr explicit 731 basic_istream_view(basic_istream<_CharT, _Traits>& __stream) 732 : _M_stream(std::__addressof(__stream)) 733 { } 734 735 constexpr auto 736 begin() 737 { 738 *_M_stream >> _M_object; 739 return _Iterator{this}; 740 } 741 742 constexpr default_sentinel_t 743 end() const noexcept 744 { return default_sentinel; } 745 746 private: 747 basic_istream<_CharT, _Traits>* _M_stream; 748 _Val _M_object = _Val(); 749 750 struct _Iterator 751 { 752 public: 753 using iterator_concept = input_iterator_tag; 754 using difference_type = ptrdiff_t; 755 using value_type = _Val; 756 757 constexpr explicit 758 _Iterator(basic_istream_view* __parent) noexcept 759 : _M_parent(__parent) 760 { } 761 762 _Iterator(const _Iterator&) = delete; 763 _Iterator(_Iterator&&) = default; 764 _Iterator& operator=(const _Iterator&) = delete; 765 _Iterator& operator=(_Iterator&&) = default; 766 767 _Iterator& 768 operator++() 769 { 770 *_M_parent->_M_stream >> _M_parent->_M_object; 771 return *this; 772 } 773 774 void 775 operator++(int) 776 { ++*this; } 777 778 _Val& 779 operator*() const 780 { return _M_parent->_M_object; } 781 782 friend bool 783 operator==(const _Iterator& __x, default_sentinel_t) 784 { return __x._M_at_end(); } 785 786 private: 787 basic_istream_view* _M_parent; 788 789 bool 790 _M_at_end() const 791 { return !*_M_parent->_M_stream; } 792 }; 793 794 friend _Iterator; 795 }; 796 797 template<typename _Val> 798 using istream_view = basic_istream_view<_Val, char>; 799 800 template<typename _Val> 801 using wistream_view = basic_istream_view<_Val, wchar_t>; 802 803namespace views 804{ 805 namespace __detail 806 { 807 template<typename _Tp, typename _Up> 808 concept __can_istream_view = requires (_Up __e) { 809 basic_istream_view<_Tp, typename _Up::char_type, typename _Up::traits_type>(__e); 810 }; 811 } // namespace __detail 812 813 template<typename _Tp> 814 struct _Istream 815 { 816 template<typename _CharT, typename _Traits> 817 constexpr auto 818 operator() [[nodiscard]] (basic_istream<_CharT, _Traits>& __e) const 819 requires __detail::__can_istream_view<_Tp, remove_reference_t<decltype(__e)>> 820 { return basic_istream_view<_Tp, _CharT, _Traits>(__e); } 821 }; 822 823 template<typename _Tp> 824 inline constexpr _Istream<_Tp> istream; 825} 826 827 // C++20 24.7 [range.adaptors] Range adaptors 828 829namespace __detail 830{ 831 struct _Empty { }; 832 833 // Alias for a type that is conditionally present 834 // (and is an empty type otherwise). 835 // Data members using this alias should use [[no_unique_address]] so that 836 // they take no space when not needed. 837 template<bool _Present, typename _Tp> 838 using __maybe_present_t = __conditional_t<_Present, _Tp, _Empty>; 839 840 // Alias for a type that is conditionally const. 841 template<bool _Const, typename _Tp> 842 using __maybe_const_t = __conditional_t<_Const, const _Tp, _Tp>; 843 844} // namespace __detail 845 846namespace views::__adaptor 847{ 848 // True if the range adaptor _Adaptor can be applied with _Args. 849 template<typename _Adaptor, typename... _Args> 850 concept __adaptor_invocable 851 = requires { std::declval<_Adaptor>()(declval<_Args>()...); }; 852 853 // True if the range adaptor non-closure _Adaptor can be partially applied 854 // with _Args. 855 template<typename _Adaptor, typename... _Args> 856 concept __adaptor_partial_app_viable = (_Adaptor::_S_arity > 1) 857 && (sizeof...(_Args) == _Adaptor::_S_arity - 1) 858 && (constructible_from<decay_t<_Args>, _Args> && ...); 859 860 template<typename _Adaptor, typename... _Args> 861 struct _Partial; 862 863 template<typename _Lhs, typename _Rhs> 864 struct _Pipe; 865 866 // The base class of every range adaptor closure. 867 // 868 // The derived class should define the optional static data member 869 // _S_has_simple_call_op to true if the behavior of this adaptor is 870 // independent of the constness/value category of the adaptor object. 871 struct _RangeAdaptorClosure 872 { 873 // range | adaptor is equivalent to adaptor(range). 874 template<typename _Self, typename _Range> 875 requires derived_from<remove_cvref_t<_Self>, _RangeAdaptorClosure> 876 && __adaptor_invocable<_Self, _Range> 877 friend constexpr auto 878 operator|(_Range&& __r, _Self&& __self) 879 { return std::forward<_Self>(__self)(std::forward<_Range>(__r)); } 880 881 // Compose the adaptors __lhs and __rhs into a pipeline, returning 882 // another range adaptor closure object. 883 template<typename _Lhs, typename _Rhs> 884 requires derived_from<_Lhs, _RangeAdaptorClosure> 885 && derived_from<_Rhs, _RangeAdaptorClosure> 886 friend constexpr auto 887 operator|(_Lhs __lhs, _Rhs __rhs) 888 { return _Pipe<_Lhs, _Rhs>{std::move(__lhs), std::move(__rhs)}; } 889 }; 890 891 // The base class of every range adaptor non-closure. 892 // 893 // The static data member _Derived::_S_arity must contain the total number of 894 // arguments that the adaptor takes, and the class _Derived must introduce 895 // _RangeAdaptor::operator() into the class scope via a using-declaration. 896 // 897 // The optional static data member _Derived::_S_has_simple_extra_args should 898 // be defined to true if the behavior of this adaptor is independent of the 899 // constness/value category of the extra arguments. This data member could 900 // also be defined as a variable template parameterized by the types of the 901 // extra arguments. 902 template<typename _Derived> 903 struct _RangeAdaptor 904 { 905 // Partially apply the arguments __args to the range adaptor _Derived, 906 // returning a range adaptor closure object. 907 template<typename... _Args> 908 requires __adaptor_partial_app_viable<_Derived, _Args...> 909 constexpr auto 910 operator()(_Args&&... __args) const 911 { 912 return _Partial<_Derived, decay_t<_Args>...>{std::forward<_Args>(__args)...}; 913 } 914 }; 915 916 // True if the range adaptor closure _Adaptor has a simple operator(), i.e. 917 // one that's not overloaded according to constness or value category of the 918 // _Adaptor object. 919 template<typename _Adaptor> 920 concept __closure_has_simple_call_op = _Adaptor::_S_has_simple_call_op; 921 922 // True if the behavior of the range adaptor non-closure _Adaptor is 923 // independent of the value category of its extra arguments _Args. 924 template<typename _Adaptor, typename... _Args> 925 concept __adaptor_has_simple_extra_args = _Adaptor::_S_has_simple_extra_args 926 || _Adaptor::template _S_has_simple_extra_args<_Args...>; 927 928 // A range adaptor closure that represents partial application of 929 // the range adaptor _Adaptor with arguments _Args. 930 template<typename _Adaptor, typename... _Args> 931 struct _Partial : _RangeAdaptorClosure 932 { 933 tuple<_Args...> _M_args; 934 935 constexpr 936 _Partial(_Args... __args) 937 : _M_args(std::move(__args)...) 938 { } 939 940 // Invoke _Adaptor with arguments __r, _M_args... according to the 941 // value category of this _Partial object. 942 template<typename _Range> 943 requires __adaptor_invocable<_Adaptor, _Range, const _Args&...> 944 constexpr auto 945 operator()(_Range&& __r) const & 946 { 947 auto __forwarder = [&__r] (const auto&... __args) { 948 return _Adaptor{}(std::forward<_Range>(__r), __args...); 949 }; 950 return std::apply(__forwarder, _M_args); 951 } 952 953 template<typename _Range> 954 requires __adaptor_invocable<_Adaptor, _Range, _Args...> 955 constexpr auto 956 operator()(_Range&& __r) && 957 { 958 auto __forwarder = [&__r] (auto&... __args) { 959 return _Adaptor{}(std::forward<_Range>(__r), std::move(__args)...); 960 }; 961 return std::apply(__forwarder, _M_args); 962 } 963 964 template<typename _Range> 965 constexpr auto 966 operator()(_Range&& __r) const && = delete; 967 }; 968 969 // A lightweight specialization of the above primary template for 970 // the common case where _Adaptor accepts a single extra argument. 971 template<typename _Adaptor, typename _Arg> 972 struct _Partial<_Adaptor, _Arg> : _RangeAdaptorClosure 973 { 974 _Arg _M_arg; 975 976 constexpr 977 _Partial(_Arg __arg) 978 : _M_arg(std::move(__arg)) 979 { } 980 981 template<typename _Range> 982 requires __adaptor_invocable<_Adaptor, _Range, const _Arg&> 983 constexpr auto 984 operator()(_Range&& __r) const & 985 { return _Adaptor{}(std::forward<_Range>(__r), _M_arg); } 986 987 template<typename _Range> 988 requires __adaptor_invocable<_Adaptor, _Range, _Arg> 989 constexpr auto 990 operator()(_Range&& __r) && 991 { return _Adaptor{}(std::forward<_Range>(__r), std::move(_M_arg)); } 992 993 template<typename _Range> 994 constexpr auto 995 operator()(_Range&& __r) const && = delete; 996 }; 997 998 // Partial specialization of the primary template for the case where the extra 999 // arguments of the adaptor can always be safely and efficiently forwarded by 1000 // const reference. This lets us get away with a single operator() overload, 1001 // which makes overload resolution failure diagnostics more concise. 1002 template<typename _Adaptor, typename... _Args> 1003 requires __adaptor_has_simple_extra_args<_Adaptor, _Args...> 1004 && (is_trivially_copyable_v<_Args> && ...) 1005 struct _Partial<_Adaptor, _Args...> : _RangeAdaptorClosure 1006 { 1007 tuple<_Args...> _M_args; 1008 1009 constexpr 1010 _Partial(_Args... __args) 1011 : _M_args(std::move(__args)...) 1012 { } 1013 1014 // Invoke _Adaptor with arguments __r, const _M_args&... regardless 1015 // of the value category of this _Partial object. 1016 template<typename _Range> 1017 requires __adaptor_invocable<_Adaptor, _Range, const _Args&...> 1018 constexpr auto 1019 operator()(_Range&& __r) const 1020 { 1021 auto __forwarder = [&__r] (const auto&... __args) { 1022 return _Adaptor{}(std::forward<_Range>(__r), __args...); 1023 }; 1024 return std::apply(__forwarder, _M_args); 1025 } 1026 1027 static constexpr bool _S_has_simple_call_op = true; 1028 }; 1029 1030 // A lightweight specialization of the above template for the common case 1031 // where _Adaptor accepts a single extra argument. 1032 template<typename _Adaptor, typename _Arg> 1033 requires __adaptor_has_simple_extra_args<_Adaptor, _Arg> 1034 && is_trivially_copyable_v<_Arg> 1035 struct _Partial<_Adaptor, _Arg> : _RangeAdaptorClosure 1036 { 1037 _Arg _M_arg; 1038 1039 constexpr 1040 _Partial(_Arg __arg) 1041 : _M_arg(std::move(__arg)) 1042 { } 1043 1044 template<typename _Range> 1045 requires __adaptor_invocable<_Adaptor, _Range, const _Arg&> 1046 constexpr auto 1047 operator()(_Range&& __r) const 1048 { return _Adaptor{}(std::forward<_Range>(__r), _M_arg); } 1049 1050 static constexpr bool _S_has_simple_call_op = true; 1051 }; 1052 1053 template<typename _Lhs, typename _Rhs, typename _Range> 1054 concept __pipe_invocable 1055 = requires { std::declval<_Rhs>()(std::declval<_Lhs>()(std::declval<_Range>())); }; 1056 1057 // A range adaptor closure that represents composition of the range 1058 // adaptor closures _Lhs and _Rhs. 1059 template<typename _Lhs, typename _Rhs> 1060 struct _Pipe : _RangeAdaptorClosure 1061 { 1062 [[no_unique_address]] _Lhs _M_lhs; 1063 [[no_unique_address]] _Rhs _M_rhs; 1064 1065 constexpr 1066 _Pipe(_Lhs __lhs, _Rhs __rhs) 1067 : _M_lhs(std::move(__lhs)), _M_rhs(std::move(__rhs)) 1068 { } 1069 1070 // Invoke _M_rhs(_M_lhs(__r)) according to the value category of this 1071 // range adaptor closure object. 1072 template<typename _Range> 1073 requires __pipe_invocable<const _Lhs&, const _Rhs&, _Range> 1074 constexpr auto 1075 operator()(_Range&& __r) const & 1076 { return _M_rhs(_M_lhs(std::forward<_Range>(__r))); } 1077 1078 template<typename _Range> 1079 requires __pipe_invocable<_Lhs, _Rhs, _Range> 1080 constexpr auto 1081 operator()(_Range&& __r) && 1082 { return std::move(_M_rhs)(std::move(_M_lhs)(std::forward<_Range>(__r))); } 1083 1084 template<typename _Range> 1085 constexpr auto 1086 operator()(_Range&& __r) const && = delete; 1087 }; 1088 1089 // A partial specialization of the above primary template for the case where 1090 // both adaptor operands have a simple operator(). This in turn lets us 1091 // implement composition using a single simple operator(), which makes 1092 // overload resolution failure diagnostics more concise. 1093 template<typename _Lhs, typename _Rhs> 1094 requires __closure_has_simple_call_op<_Lhs> 1095 && __closure_has_simple_call_op<_Rhs> 1096 struct _Pipe<_Lhs, _Rhs> : _RangeAdaptorClosure 1097 { 1098 [[no_unique_address]] _Lhs _M_lhs; 1099 [[no_unique_address]] _Rhs _M_rhs; 1100 1101 constexpr 1102 _Pipe(_Lhs __lhs, _Rhs __rhs) 1103 : _M_lhs(std::move(__lhs)), _M_rhs(std::move(__rhs)) 1104 { } 1105 1106 template<typename _Range> 1107 requires __pipe_invocable<const _Lhs&, const _Rhs&, _Range> 1108 constexpr auto 1109 operator()(_Range&& __r) const 1110 { return _M_rhs(_M_lhs(std::forward<_Range>(__r))); } 1111 1112 static constexpr bool _S_has_simple_call_op = true; 1113 }; 1114} // namespace views::__adaptor 1115 1116 template<range _Range> requires is_object_v<_Range> 1117 class ref_view : public view_interface<ref_view<_Range>> 1118 { 1119 private: 1120 _Range* _M_r; 1121 1122 static void _S_fun(_Range&); // not defined 1123 static void _S_fun(_Range&&) = delete; 1124 1125 public: 1126 template<__detail::__different_from<ref_view> _Tp> 1127 requires convertible_to<_Tp, _Range&> 1128 && requires { _S_fun(declval<_Tp>()); } 1129 constexpr 1130 ref_view(_Tp&& __t) 1131 noexcept(noexcept(static_cast<_Range&>(std::declval<_Tp>()))) 1132 : _M_r(std::__addressof(static_cast<_Range&>(std::forward<_Tp>(__t)))) 1133 { } 1134 1135 constexpr _Range& 1136 base() const 1137 { return *_M_r; } 1138 1139 constexpr iterator_t<_Range> 1140 begin() const 1141 { return ranges::begin(*_M_r); } 1142 1143 constexpr sentinel_t<_Range> 1144 end() const 1145 { return ranges::end(*_M_r); } 1146 1147 constexpr bool 1148 empty() const requires requires { ranges::empty(*_M_r); } 1149 { return ranges::empty(*_M_r); } 1150 1151 constexpr auto 1152 size() const requires sized_range<_Range> 1153 { return ranges::size(*_M_r); } 1154 1155 constexpr auto 1156 data() const requires contiguous_range<_Range> 1157 { return ranges::data(*_M_r); } 1158 }; 1159 1160 template<typename _Range> 1161 ref_view(_Range&) -> ref_view<_Range>; 1162 1163 template<typename _Tp> 1164 inline constexpr bool enable_borrowed_range<ref_view<_Tp>> = true; 1165 1166 template<range _Range> 1167 requires movable<_Range> 1168 && (!__detail::__is_initializer_list<remove_cv_t<_Range>>) 1169 class owning_view : public view_interface<owning_view<_Range>> 1170 { 1171 private: 1172 _Range _M_r = _Range(); 1173 1174 public: 1175 owning_view() requires default_initializable<_Range> = default; 1176 1177 constexpr 1178 owning_view(_Range&& __t) 1179 noexcept(is_nothrow_move_constructible_v<_Range>) 1180 : _M_r(std::move(__t)) 1181 { } 1182 1183 owning_view(owning_view&&) = default; 1184 owning_view& operator=(owning_view&&) = default; 1185 1186 constexpr _Range& 1187 base() & noexcept 1188 { return _M_r; } 1189 1190 constexpr const _Range& 1191 base() const& noexcept 1192 { return _M_r; } 1193 1194 constexpr _Range&& 1195 base() && noexcept 1196 { return std::move(_M_r); } 1197 1198 constexpr const _Range&& 1199 base() const&& noexcept 1200 { return std::move(_M_r); } 1201 1202 constexpr iterator_t<_Range> 1203 begin() 1204 { return ranges::begin(_M_r); } 1205 1206 constexpr sentinel_t<_Range> 1207 end() 1208 { return ranges::end(_M_r); } 1209 1210 constexpr auto 1211 begin() const requires range<const _Range> 1212 { return ranges::begin(_M_r); } 1213 1214 constexpr auto 1215 end() const requires range<const _Range> 1216 { return ranges::end(_M_r); } 1217 1218 constexpr bool 1219 empty() requires requires { ranges::empty(_M_r); } 1220 { return ranges::empty(_M_r); } 1221 1222 constexpr bool 1223 empty() const requires requires { ranges::empty(_M_r); } 1224 { return ranges::empty(_M_r); } 1225 1226 constexpr auto 1227 size() requires sized_range<_Range> 1228 { return ranges::size(_M_r); } 1229 1230 constexpr auto 1231 size() const requires sized_range<const _Range> 1232 { return ranges::size(_M_r); } 1233 1234 constexpr auto 1235 data() requires contiguous_range<_Range> 1236 { return ranges::data(_M_r); } 1237 1238 constexpr auto 1239 data() const requires contiguous_range<const _Range> 1240 { return ranges::data(_M_r); } 1241 }; 1242 1243 template<typename _Tp> 1244 inline constexpr bool enable_borrowed_range<owning_view<_Tp>> 1245 = enable_borrowed_range<_Tp>; 1246 1247 namespace views 1248 { 1249 namespace __detail 1250 { 1251 template<typename _Range> 1252 concept __can_ref_view = requires { ref_view{std::declval<_Range>()}; }; 1253 1254 template<typename _Range> 1255 concept __can_owning_view = requires { owning_view{std::declval<_Range>()}; }; 1256 } // namespace __detail 1257 1258 struct _All : __adaptor::_RangeAdaptorClosure 1259 { 1260 template<typename _Range> 1261 static constexpr bool 1262 _S_noexcept() 1263 { 1264 if constexpr (view<decay_t<_Range>>) 1265 return is_nothrow_constructible_v<decay_t<_Range>, _Range>; 1266 else if constexpr (__detail::__can_ref_view<_Range>) 1267 return true; 1268 else 1269 return noexcept(owning_view{std::declval<_Range>()}); 1270 } 1271 1272 template<viewable_range _Range> 1273 requires view<decay_t<_Range>> 1274 || __detail::__can_ref_view<_Range> 1275 || __detail::__can_owning_view<_Range> 1276 constexpr auto 1277 operator() [[nodiscard]] (_Range&& __r) const 1278 noexcept(_S_noexcept<_Range>()) 1279 { 1280 if constexpr (view<decay_t<_Range>>) 1281 return std::forward<_Range>(__r); 1282 else if constexpr (__detail::__can_ref_view<_Range>) 1283 return ref_view{std::forward<_Range>(__r)}; 1284 else 1285 return owning_view{std::forward<_Range>(__r)}; 1286 } 1287 1288 static constexpr bool _S_has_simple_call_op = true; 1289 }; 1290 1291 inline constexpr _All all; 1292 1293 template<viewable_range _Range> 1294 using all_t = decltype(all(std::declval<_Range>())); 1295 } // namespace views 1296 1297 namespace __detail 1298 { 1299 template<typename _Tp> 1300 struct __non_propagating_cache 1301 { 1302 // When _Tp is not an object type (e.g. is a reference type), we make 1303 // __non_propagating_cache<_Tp> empty rather than ill-formed so that 1304 // users can easily conditionally declare data members with this type 1305 // (such as join_view::_M_inner). 1306 }; 1307 1308 template<typename _Tp> 1309 requires is_object_v<_Tp> 1310 struct __non_propagating_cache<_Tp> 1311 : protected _Optional_base<_Tp> 1312 { 1313 __non_propagating_cache() = default; 1314 1315 constexpr 1316 __non_propagating_cache(const __non_propagating_cache&) noexcept 1317 { } 1318 1319 constexpr 1320 __non_propagating_cache(__non_propagating_cache&& __other) noexcept 1321 { __other._M_reset(); } 1322 1323 constexpr __non_propagating_cache& 1324 operator=(const __non_propagating_cache& __other) noexcept 1325 { 1326 if (std::__addressof(__other) != this) 1327 this->_M_reset(); 1328 return *this; 1329 } 1330 1331 constexpr __non_propagating_cache& 1332 operator=(__non_propagating_cache&& __other) noexcept 1333 { 1334 this->_M_reset(); 1335 __other._M_reset(); 1336 return *this; 1337 } 1338 1339 constexpr __non_propagating_cache& 1340 operator=(_Tp __val) 1341 { 1342 this->_M_reset(); 1343 this->_M_payload._M_construct(std::move(__val)); 1344 return *this; 1345 } 1346 1347 constexpr explicit 1348 operator bool() const noexcept 1349 { return this->_M_is_engaged(); } 1350 1351 constexpr _Tp& 1352 operator*() noexcept 1353 { return this->_M_get(); } 1354 1355 constexpr const _Tp& 1356 operator*() const noexcept 1357 { return this->_M_get(); } 1358 1359 template<typename _Iter> 1360 constexpr _Tp& 1361 _M_emplace_deref(const _Iter& __i) 1362 { 1363 this->_M_reset(); 1364 auto __f = [] (auto& __x) { return *__x; }; 1365 this->_M_payload._M_apply(_Optional_func{__f}, __i); 1366 return this->_M_get(); 1367 } 1368 }; 1369 1370 template<range _Range> 1371 struct _CachedPosition 1372 { 1373 constexpr bool 1374 _M_has_value() const 1375 { return false; } 1376 1377 constexpr iterator_t<_Range> 1378 _M_get(const _Range&) const 1379 { 1380 __glibcxx_assert(false); 1381 __builtin_unreachable(); 1382 } 1383 1384 constexpr void 1385 _M_set(const _Range&, const iterator_t<_Range>&) const 1386 { } 1387 }; 1388 1389 template<forward_range _Range> 1390 struct _CachedPosition<_Range> 1391 : protected __non_propagating_cache<iterator_t<_Range>> 1392 { 1393 constexpr bool 1394 _M_has_value() const 1395 { return this->_M_is_engaged(); } 1396 1397 constexpr iterator_t<_Range> 1398 _M_get(const _Range&) const 1399 { 1400 __glibcxx_assert(_M_has_value()); 1401 return **this; 1402 } 1403 1404 constexpr void 1405 _M_set(const _Range&, const iterator_t<_Range>& __it) 1406 { 1407 __glibcxx_assert(!_M_has_value()); 1408 std::construct_at(std::__addressof(this->_M_payload._M_payload), 1409 in_place, __it); 1410 this->_M_payload._M_engaged = true; 1411 } 1412 }; 1413 1414 template<random_access_range _Range> 1415 requires (sizeof(range_difference_t<_Range>) 1416 <= sizeof(iterator_t<_Range>)) 1417 struct _CachedPosition<_Range> 1418 { 1419 private: 1420 range_difference_t<_Range> _M_offset = -1; 1421 1422 public: 1423 _CachedPosition() = default; 1424 1425 constexpr 1426 _CachedPosition(const _CachedPosition&) = default; 1427 1428 constexpr 1429 _CachedPosition(_CachedPosition&& __other) noexcept 1430 { *this = std::move(__other); } 1431 1432 constexpr _CachedPosition& 1433 operator=(const _CachedPosition&) = default; 1434 1435 constexpr _CachedPosition& 1436 operator=(_CachedPosition&& __other) noexcept 1437 { 1438 // Propagate the cached offset, but invalidate the source. 1439 _M_offset = __other._M_offset; 1440 __other._M_offset = -1; 1441 return *this; 1442 } 1443 1444 constexpr bool 1445 _M_has_value() const 1446 { return _M_offset >= 0; } 1447 1448 constexpr iterator_t<_Range> 1449 _M_get(_Range& __r) const 1450 { 1451 __glibcxx_assert(_M_has_value()); 1452 return ranges::begin(__r) + _M_offset; 1453 } 1454 1455 constexpr void 1456 _M_set(_Range& __r, const iterator_t<_Range>& __it) 1457 { 1458 __glibcxx_assert(!_M_has_value()); 1459 _M_offset = __it - ranges::begin(__r); 1460 } 1461 }; 1462 } // namespace __detail 1463 1464 namespace __detail 1465 { 1466 template<typename _Base> 1467 struct __filter_view_iter_cat 1468 { }; 1469 1470 template<forward_range _Base> 1471 struct __filter_view_iter_cat<_Base> 1472 { 1473 private: 1474 static auto 1475 _S_iter_cat() 1476 { 1477 using _Cat = typename iterator_traits<iterator_t<_Base>>::iterator_category; 1478 if constexpr (derived_from<_Cat, bidirectional_iterator_tag>) 1479 return bidirectional_iterator_tag{}; 1480 else if constexpr (derived_from<_Cat, forward_iterator_tag>) 1481 return forward_iterator_tag{}; 1482 else 1483 return _Cat{}; 1484 } 1485 public: 1486 using iterator_category = decltype(_S_iter_cat()); 1487 }; 1488 } // namespace __detail 1489 1490 template<input_range _Vp, 1491 indirect_unary_predicate<iterator_t<_Vp>> _Pred> 1492 requires view<_Vp> && is_object_v<_Pred> 1493 class filter_view : public view_interface<filter_view<_Vp, _Pred>> 1494 { 1495 private: 1496 struct _Sentinel; 1497 1498 struct _Iterator : __detail::__filter_view_iter_cat<_Vp> 1499 { 1500 private: 1501 static constexpr auto 1502 _S_iter_concept() 1503 { 1504 if constexpr (bidirectional_range<_Vp>) 1505 return bidirectional_iterator_tag{}; 1506 else if constexpr (forward_range<_Vp>) 1507 return forward_iterator_tag{}; 1508 else 1509 return input_iterator_tag{}; 1510 } 1511 1512 friend filter_view; 1513 1514 using _Vp_iter = iterator_t<_Vp>; 1515 1516 _Vp_iter _M_current = _Vp_iter(); 1517 filter_view* _M_parent = nullptr; 1518 1519 public: 1520 using iterator_concept = decltype(_S_iter_concept()); 1521 // iterator_category defined in __filter_view_iter_cat 1522 using value_type = range_value_t<_Vp>; 1523 using difference_type = range_difference_t<_Vp>; 1524 1525 _Iterator() requires default_initializable<_Vp_iter> = default; 1526 1527 constexpr 1528 _Iterator(filter_view* __parent, _Vp_iter __current) 1529 : _M_current(std::move(__current)), 1530 _M_parent(__parent) 1531 { } 1532 1533 constexpr const _Vp_iter& 1534 base() const & noexcept 1535 { return _M_current; } 1536 1537 constexpr _Vp_iter 1538 base() && 1539 { return std::move(_M_current); } 1540 1541 constexpr range_reference_t<_Vp> 1542 operator*() const 1543 { return *_M_current; } 1544 1545 constexpr _Vp_iter 1546 operator->() const 1547 requires __detail::__has_arrow<_Vp_iter> 1548 && copyable<_Vp_iter> 1549 { return _M_current; } 1550 1551 constexpr _Iterator& 1552 operator++() 1553 { 1554 _M_current = ranges::find_if(std::move(++_M_current), 1555 ranges::end(_M_parent->_M_base), 1556 std::ref(*_M_parent->_M_pred)); 1557 return *this; 1558 } 1559 1560 constexpr void 1561 operator++(int) 1562 { ++*this; } 1563 1564 constexpr _Iterator 1565 operator++(int) requires forward_range<_Vp> 1566 { 1567 auto __tmp = *this; 1568 ++*this; 1569 return __tmp; 1570 } 1571 1572 constexpr _Iterator& 1573 operator--() requires bidirectional_range<_Vp> 1574 { 1575 do 1576 --_M_current; 1577 while (!std::__invoke(*_M_parent->_M_pred, *_M_current)); 1578 return *this; 1579 } 1580 1581 constexpr _Iterator 1582 operator--(int) requires bidirectional_range<_Vp> 1583 { 1584 auto __tmp = *this; 1585 --*this; 1586 return __tmp; 1587 } 1588 1589 friend constexpr bool 1590 operator==(const _Iterator& __x, const _Iterator& __y) 1591 requires equality_comparable<_Vp_iter> 1592 { return __x._M_current == __y._M_current; } 1593 1594 friend constexpr range_rvalue_reference_t<_Vp> 1595 iter_move(const _Iterator& __i) 1596 noexcept(noexcept(ranges::iter_move(__i._M_current))) 1597 { return ranges::iter_move(__i._M_current); } 1598 1599 friend constexpr void 1600 iter_swap(const _Iterator& __x, const _Iterator& __y) 1601 noexcept(noexcept(ranges::iter_swap(__x._M_current, __y._M_current))) 1602 requires indirectly_swappable<_Vp_iter> 1603 { ranges::iter_swap(__x._M_current, __y._M_current); } 1604 }; 1605 1606 struct _Sentinel 1607 { 1608 private: 1609 sentinel_t<_Vp> _M_end = sentinel_t<_Vp>(); 1610 1611 constexpr bool 1612 __equal(const _Iterator& __i) const 1613 { return __i._M_current == _M_end; } 1614 1615 public: 1616 _Sentinel() = default; 1617 1618 constexpr explicit 1619 _Sentinel(filter_view* __parent) 1620 : _M_end(ranges::end(__parent->_M_base)) 1621 { } 1622 1623 constexpr sentinel_t<_Vp> 1624 base() const 1625 { return _M_end; } 1626 1627 friend constexpr bool 1628 operator==(const _Iterator& __x, const _Sentinel& __y) 1629 { return __y.__equal(__x); } 1630 }; 1631 1632 _Vp _M_base = _Vp(); 1633 [[no_unique_address]] __detail::__box<_Pred> _M_pred; 1634 [[no_unique_address]] __detail::_CachedPosition<_Vp> _M_cached_begin; 1635 1636 public: 1637 filter_view() requires (default_initializable<_Vp> 1638 && default_initializable<_Pred>) 1639 = default; 1640 1641 constexpr 1642 filter_view(_Vp __base, _Pred __pred) 1643 : _M_base(std::move(__base)), _M_pred(std::move(__pred)) 1644 { } 1645 1646 constexpr _Vp 1647 base() const& requires copy_constructible<_Vp> 1648 { return _M_base; } 1649 1650 constexpr _Vp 1651 base() && 1652 { return std::move(_M_base); } 1653 1654 constexpr const _Pred& 1655 pred() const 1656 { return *_M_pred; } 1657 1658 constexpr _Iterator 1659 begin() 1660 { 1661 if (_M_cached_begin._M_has_value()) 1662 return {this, _M_cached_begin._M_get(_M_base)}; 1663 1664 __glibcxx_assert(_M_pred.has_value()); 1665 auto __it = ranges::find_if(ranges::begin(_M_base), 1666 ranges::end(_M_base), 1667 std::ref(*_M_pred)); 1668 _M_cached_begin._M_set(_M_base, __it); 1669 return {this, std::move(__it)}; 1670 } 1671 1672 constexpr auto 1673 end() 1674 { 1675 if constexpr (common_range<_Vp>) 1676 return _Iterator{this, ranges::end(_M_base)}; 1677 else 1678 return _Sentinel{this}; 1679 } 1680 }; 1681 1682 template<typename _Range, typename _Pred> 1683 filter_view(_Range&&, _Pred) -> filter_view<views::all_t<_Range>, _Pred>; 1684 1685 namespace views 1686 { 1687 namespace __detail 1688 { 1689 template<typename _Range, typename _Pred> 1690 concept __can_filter_view 1691 = requires { filter_view(std::declval<_Range>(), std::declval<_Pred>()); }; 1692 } // namespace __detail 1693 1694 struct _Filter : __adaptor::_RangeAdaptor<_Filter> 1695 { 1696 template<viewable_range _Range, typename _Pred> 1697 requires __detail::__can_filter_view<_Range, _Pred> 1698 constexpr auto 1699 operator() [[nodiscard]] (_Range&& __r, _Pred&& __p) const 1700 { 1701 return filter_view(std::forward<_Range>(__r), std::forward<_Pred>(__p)); 1702 } 1703 1704 using _RangeAdaptor<_Filter>::operator(); 1705 static constexpr int _S_arity = 2; 1706 static constexpr bool _S_has_simple_extra_args = true; 1707 }; 1708 1709 inline constexpr _Filter filter; 1710 } // namespace views 1711 1712 template<input_range _Vp, copy_constructible _Fp> 1713 requires view<_Vp> && is_object_v<_Fp> 1714 && regular_invocable<_Fp&, range_reference_t<_Vp>> 1715 && std::__detail::__can_reference<invoke_result_t<_Fp&, 1716 range_reference_t<_Vp>>> 1717 class transform_view : public view_interface<transform_view<_Vp, _Fp>> 1718 { 1719 private: 1720 template<bool _Const> 1721 using _Base = __detail::__maybe_const_t<_Const, _Vp>; 1722 1723 template<bool _Const> 1724 struct __iter_cat 1725 { }; 1726 1727 template<bool _Const> 1728 requires forward_range<_Base<_Const>> 1729 struct __iter_cat<_Const> 1730 { 1731 private: 1732 static auto 1733 _S_iter_cat() 1734 { 1735 using _Base = transform_view::_Base<_Const>; 1736 using _Res = invoke_result_t<_Fp&, range_reference_t<_Base>>; 1737 if constexpr (is_lvalue_reference_v<_Res>) 1738 { 1739 using _Cat 1740 = typename iterator_traits<iterator_t<_Base>>::iterator_category; 1741 if constexpr (derived_from<_Cat, contiguous_iterator_tag>) 1742 return random_access_iterator_tag{}; 1743 else 1744 return _Cat{}; 1745 } 1746 else 1747 return input_iterator_tag{}; 1748 } 1749 public: 1750 using iterator_category = decltype(_S_iter_cat()); 1751 }; 1752 1753 template<bool _Const> 1754 struct _Sentinel; 1755 1756 template<bool _Const> 1757 struct _Iterator : __iter_cat<_Const> 1758 { 1759 private: 1760 using _Parent = __detail::__maybe_const_t<_Const, transform_view>; 1761 using _Base = transform_view::_Base<_Const>; 1762 1763 static auto 1764 _S_iter_concept() 1765 { 1766 if constexpr (random_access_range<_Base>) 1767 return random_access_iterator_tag{}; 1768 else if constexpr (bidirectional_range<_Base>) 1769 return bidirectional_iterator_tag{}; 1770 else if constexpr (forward_range<_Base>) 1771 return forward_iterator_tag{}; 1772 else 1773 return input_iterator_tag{}; 1774 } 1775 1776 using _Base_iter = iterator_t<_Base>; 1777 1778 _Base_iter _M_current = _Base_iter(); 1779 _Parent* _M_parent = nullptr; 1780 1781 public: 1782 using iterator_concept = decltype(_S_iter_concept()); 1783 // iterator_category defined in __transform_view_iter_cat 1784 using value_type 1785 = remove_cvref_t<invoke_result_t<_Fp&, range_reference_t<_Base>>>; 1786 using difference_type = range_difference_t<_Base>; 1787 1788 _Iterator() requires default_initializable<_Base_iter> = default; 1789 1790 constexpr 1791 _Iterator(_Parent* __parent, _Base_iter __current) 1792 : _M_current(std::move(__current)), 1793 _M_parent(__parent) 1794 { } 1795 1796 constexpr 1797 _Iterator(_Iterator<!_Const> __i) 1798 requires _Const 1799 && convertible_to<iterator_t<_Vp>, _Base_iter> 1800 : _M_current(std::move(__i._M_current)), _M_parent(__i._M_parent) 1801 { } 1802 1803 constexpr const _Base_iter& 1804 base() const & noexcept 1805 { return _M_current; } 1806 1807 constexpr _Base_iter 1808 base() && 1809 { return std::move(_M_current); } 1810 1811 constexpr decltype(auto) 1812 operator*() const 1813 noexcept(noexcept(std::__invoke(*_M_parent->_M_fun, *_M_current))) 1814 { return std::__invoke(*_M_parent->_M_fun, *_M_current); } 1815 1816 constexpr _Iterator& 1817 operator++() 1818 { 1819 ++_M_current; 1820 return *this; 1821 } 1822 1823 constexpr void 1824 operator++(int) 1825 { ++_M_current; } 1826 1827 constexpr _Iterator 1828 operator++(int) requires forward_range<_Base> 1829 { 1830 auto __tmp = *this; 1831 ++*this; 1832 return __tmp; 1833 } 1834 1835 constexpr _Iterator& 1836 operator--() requires bidirectional_range<_Base> 1837 { 1838 --_M_current; 1839 return *this; 1840 } 1841 1842 constexpr _Iterator 1843 operator--(int) requires bidirectional_range<_Base> 1844 { 1845 auto __tmp = *this; 1846 --*this; 1847 return __tmp; 1848 } 1849 1850 constexpr _Iterator& 1851 operator+=(difference_type __n) requires random_access_range<_Base> 1852 { 1853 _M_current += __n; 1854 return *this; 1855 } 1856 1857 constexpr _Iterator& 1858 operator-=(difference_type __n) requires random_access_range<_Base> 1859 { 1860 _M_current -= __n; 1861 return *this; 1862 } 1863 1864 constexpr decltype(auto) 1865 operator[](difference_type __n) const 1866 requires random_access_range<_Base> 1867 { return std::__invoke(*_M_parent->_M_fun, _M_current[__n]); } 1868 1869 friend constexpr bool 1870 operator==(const _Iterator& __x, const _Iterator& __y) 1871 requires equality_comparable<_Base_iter> 1872 { return __x._M_current == __y._M_current; } 1873 1874 friend constexpr bool 1875 operator<(const _Iterator& __x, const _Iterator& __y) 1876 requires random_access_range<_Base> 1877 { return __x._M_current < __y._M_current; } 1878 1879 friend constexpr bool 1880 operator>(const _Iterator& __x, const _Iterator& __y) 1881 requires random_access_range<_Base> 1882 { return __y < __x; } 1883 1884 friend constexpr bool 1885 operator<=(const _Iterator& __x, const _Iterator& __y) 1886 requires random_access_range<_Base> 1887 { return !(__y < __x); } 1888 1889 friend constexpr bool 1890 operator>=(const _Iterator& __x, const _Iterator& __y) 1891 requires random_access_range<_Base> 1892 { return !(__x < __y); } 1893 1894#ifdef __cpp_lib_three_way_comparison 1895 friend constexpr auto 1896 operator<=>(const _Iterator& __x, const _Iterator& __y) 1897 requires random_access_range<_Base> 1898 && three_way_comparable<_Base_iter> 1899 { return __x._M_current <=> __y._M_current; } 1900#endif 1901 1902 friend constexpr _Iterator 1903 operator+(_Iterator __i, difference_type __n) 1904 requires random_access_range<_Base> 1905 { return {__i._M_parent, __i._M_current + __n}; } 1906 1907 friend constexpr _Iterator 1908 operator+(difference_type __n, _Iterator __i) 1909 requires random_access_range<_Base> 1910 { return {__i._M_parent, __i._M_current + __n}; } 1911 1912 friend constexpr _Iterator 1913 operator-(_Iterator __i, difference_type __n) 1914 requires random_access_range<_Base> 1915 { return {__i._M_parent, __i._M_current - __n}; } 1916 1917 // _GLIBCXX_RESOLVE_LIB_DEFECTS 1918 // 3483. transform_view::iterator's difference is overconstrained 1919 friend constexpr difference_type 1920 operator-(const _Iterator& __x, const _Iterator& __y) 1921 requires sized_sentinel_for<iterator_t<_Base>, iterator_t<_Base>> 1922 { return __x._M_current - __y._M_current; } 1923 1924 friend constexpr decltype(auto) 1925 iter_move(const _Iterator& __i) noexcept(noexcept(*__i)) 1926 { 1927 if constexpr (is_lvalue_reference_v<decltype(*__i)>) 1928 return std::move(*__i); 1929 else 1930 return *__i; 1931 } 1932 1933 friend _Iterator<!_Const>; 1934 template<bool> friend struct _Sentinel; 1935 }; 1936 1937 template<bool _Const> 1938 struct _Sentinel 1939 { 1940 private: 1941 using _Parent = __detail::__maybe_const_t<_Const, transform_view>; 1942 using _Base = transform_view::_Base<_Const>; 1943 1944 template<bool _Const2> 1945 constexpr auto 1946 __distance_from(const _Iterator<_Const2>& __i) const 1947 { return _M_end - __i._M_current; } 1948 1949 template<bool _Const2> 1950 constexpr bool 1951 __equal(const _Iterator<_Const2>& __i) const 1952 { return __i._M_current == _M_end; } 1953 1954 sentinel_t<_Base> _M_end = sentinel_t<_Base>(); 1955 1956 public: 1957 _Sentinel() = default; 1958 1959 constexpr explicit 1960 _Sentinel(sentinel_t<_Base> __end) 1961 : _M_end(__end) 1962 { } 1963 1964 constexpr 1965 _Sentinel(_Sentinel<!_Const> __i) 1966 requires _Const 1967 && convertible_to<sentinel_t<_Vp>, sentinel_t<_Base>> 1968 : _M_end(std::move(__i._M_end)) 1969 { } 1970 1971 constexpr sentinel_t<_Base> 1972 base() const 1973 { return _M_end; } 1974 1975 template<bool _Const2> 1976 requires sentinel_for<sentinel_t<_Base>, 1977 iterator_t<__detail::__maybe_const_t<_Const2, _Vp>>> 1978 friend constexpr bool 1979 operator==(const _Iterator<_Const2>& __x, const _Sentinel& __y) 1980 { return __y.__equal(__x); } 1981 1982 template<bool _Const2, 1983 typename _Base2 = __detail::__maybe_const_t<_Const2, _Vp>> 1984 requires sized_sentinel_for<sentinel_t<_Base>, iterator_t<_Base2>> 1985 friend constexpr range_difference_t<_Base2> 1986 operator-(const _Iterator<_Const2>& __x, const _Sentinel& __y) 1987 { return -__y.__distance_from(__x); } 1988 1989 template<bool _Const2, 1990 typename _Base2 = __detail::__maybe_const_t<_Const2, _Vp>> 1991 requires sized_sentinel_for<sentinel_t<_Base>, iterator_t<_Base2>> 1992 friend constexpr range_difference_t<_Base2> 1993 operator-(const _Sentinel& __y, const _Iterator<_Const2>& __x) 1994 { return __y.__distance_from(__x); } 1995 1996 friend _Sentinel<!_Const>; 1997 }; 1998 1999 _Vp _M_base = _Vp(); 2000 [[no_unique_address]] __detail::__box<_Fp> _M_fun; 2001 2002 public: 2003 transform_view() requires (default_initializable<_Vp> 2004 && default_initializable<_Fp>) 2005 = default; 2006 2007 constexpr 2008 transform_view(_Vp __base, _Fp __fun) 2009 : _M_base(std::move(__base)), _M_fun(std::move(__fun)) 2010 { } 2011 2012 constexpr _Vp 2013 base() const& requires copy_constructible<_Vp> 2014 { return _M_base ; } 2015 2016 constexpr _Vp 2017 base() && 2018 { return std::move(_M_base); } 2019 2020 constexpr _Iterator<false> 2021 begin() 2022 { return _Iterator<false>{this, ranges::begin(_M_base)}; } 2023 2024 constexpr _Iterator<true> 2025 begin() const 2026 requires range<const _Vp> 2027 && regular_invocable<const _Fp&, range_reference_t<const _Vp>> 2028 { return _Iterator<true>{this, ranges::begin(_M_base)}; } 2029 2030 constexpr _Sentinel<false> 2031 end() 2032 { return _Sentinel<false>{ranges::end(_M_base)}; } 2033 2034 constexpr _Iterator<false> 2035 end() requires common_range<_Vp> 2036 { return _Iterator<false>{this, ranges::end(_M_base)}; } 2037 2038 constexpr _Sentinel<true> 2039 end() const 2040 requires range<const _Vp> 2041 && regular_invocable<const _Fp&, range_reference_t<const _Vp>> 2042 { return _Sentinel<true>{ranges::end(_M_base)}; } 2043 2044 constexpr _Iterator<true> 2045 end() const 2046 requires common_range<const _Vp> 2047 && regular_invocable<const _Fp&, range_reference_t<const _Vp>> 2048 { return _Iterator<true>{this, ranges::end(_M_base)}; } 2049 2050 constexpr auto 2051 size() requires sized_range<_Vp> 2052 { return ranges::size(_M_base); } 2053 2054 constexpr auto 2055 size() const requires sized_range<const _Vp> 2056 { return ranges::size(_M_base); } 2057 }; 2058 2059 template<typename _Range, typename _Fp> 2060 transform_view(_Range&&, _Fp) -> transform_view<views::all_t<_Range>, _Fp>; 2061 2062 namespace views 2063 { 2064 namespace __detail 2065 { 2066 template<typename _Range, typename _Fp> 2067 concept __can_transform_view 2068 = requires { transform_view(std::declval<_Range>(), std::declval<_Fp>()); }; 2069 } // namespace __detail 2070 2071 struct _Transform : __adaptor::_RangeAdaptor<_Transform> 2072 { 2073 template<viewable_range _Range, typename _Fp> 2074 requires __detail::__can_transform_view<_Range, _Fp> 2075 constexpr auto 2076 operator() [[nodiscard]] (_Range&& __r, _Fp&& __f) const 2077 { 2078 return transform_view(std::forward<_Range>(__r), std::forward<_Fp>(__f)); 2079 } 2080 2081 using _RangeAdaptor<_Transform>::operator(); 2082 static constexpr int _S_arity = 2; 2083 static constexpr bool _S_has_simple_extra_args = true; 2084 }; 2085 2086 inline constexpr _Transform transform; 2087 } // namespace views 2088 2089 template<view _Vp> 2090 class take_view : public view_interface<take_view<_Vp>> 2091 { 2092 private: 2093 template<bool _Const> 2094 using _CI = counted_iterator< 2095 iterator_t<__detail::__maybe_const_t<_Const, _Vp>>>; 2096 2097 template<bool _Const> 2098 struct _Sentinel 2099 { 2100 private: 2101 using _Base = __detail::__maybe_const_t<_Const, _Vp>; 2102 sentinel_t<_Base> _M_end = sentinel_t<_Base>(); 2103 2104 public: 2105 _Sentinel() = default; 2106 2107 constexpr explicit 2108 _Sentinel(sentinel_t<_Base> __end) 2109 : _M_end(__end) 2110 { } 2111 2112 constexpr 2113 _Sentinel(_Sentinel<!_Const> __s) 2114 requires _Const && convertible_to<sentinel_t<_Vp>, sentinel_t<_Base>> 2115 : _M_end(std::move(__s._M_end)) 2116 { } 2117 2118 constexpr sentinel_t<_Base> 2119 base() const 2120 { return _M_end; } 2121 2122 friend constexpr bool 2123 operator==(const _CI<_Const>& __y, const _Sentinel& __x) 2124 { return __y.count() == 0 || __y.base() == __x._M_end; } 2125 2126 template<bool _OtherConst = !_Const, 2127 typename _Base2 = __detail::__maybe_const_t<_OtherConst, _Vp>> 2128 requires sentinel_for<sentinel_t<_Base>, iterator_t<_Base2>> 2129 friend constexpr bool 2130 operator==(const _CI<_OtherConst>& __y, const _Sentinel& __x) 2131 { return __y.count() == 0 || __y.base() == __x._M_end; } 2132 2133 friend _Sentinel<!_Const>; 2134 }; 2135 2136 _Vp _M_base = _Vp(); 2137 range_difference_t<_Vp> _M_count = 0; 2138 2139 public: 2140 take_view() requires default_initializable<_Vp> = default; 2141 2142 constexpr 2143 take_view(_Vp base, range_difference_t<_Vp> __count) 2144 : _M_base(std::move(base)), _M_count(std::move(__count)) 2145 { } 2146 2147 constexpr _Vp 2148 base() const& requires copy_constructible<_Vp> 2149 { return _M_base; } 2150 2151 constexpr _Vp 2152 base() && 2153 { return std::move(_M_base); } 2154 2155 constexpr auto 2156 begin() requires (!__detail::__simple_view<_Vp>) 2157 { 2158 if constexpr (sized_range<_Vp>) 2159 { 2160 if constexpr (random_access_range<_Vp>) 2161 return ranges::begin(_M_base); 2162 else 2163 { 2164 auto __sz = size(); 2165 return counted_iterator(ranges::begin(_M_base), __sz); 2166 } 2167 } 2168 else 2169 return counted_iterator(ranges::begin(_M_base), _M_count); 2170 } 2171 2172 constexpr auto 2173 begin() const requires range<const _Vp> 2174 { 2175 if constexpr (sized_range<const _Vp>) 2176 { 2177 if constexpr (random_access_range<const _Vp>) 2178 return ranges::begin(_M_base); 2179 else 2180 { 2181 auto __sz = size(); 2182 return counted_iterator(ranges::begin(_M_base), __sz); 2183 } 2184 } 2185 else 2186 return counted_iterator(ranges::begin(_M_base), _M_count); 2187 } 2188 2189 constexpr auto 2190 end() requires (!__detail::__simple_view<_Vp>) 2191 { 2192 if constexpr (sized_range<_Vp>) 2193 { 2194 if constexpr (random_access_range<_Vp>) 2195 return ranges::begin(_M_base) + size(); 2196 else 2197 return default_sentinel; 2198 } 2199 else 2200 return _Sentinel<false>{ranges::end(_M_base)}; 2201 } 2202 2203 constexpr auto 2204 end() const requires range<const _Vp> 2205 { 2206 if constexpr (sized_range<const _Vp>) 2207 { 2208 if constexpr (random_access_range<const _Vp>) 2209 return ranges::begin(_M_base) + size(); 2210 else 2211 return default_sentinel; 2212 } 2213 else 2214 return _Sentinel<true>{ranges::end(_M_base)}; 2215 } 2216 2217 constexpr auto 2218 size() requires sized_range<_Vp> 2219 { 2220 auto __n = ranges::size(_M_base); 2221 return std::min(__n, static_cast<decltype(__n)>(_M_count)); 2222 } 2223 2224 constexpr auto 2225 size() const requires sized_range<const _Vp> 2226 { 2227 auto __n = ranges::size(_M_base); 2228 return std::min(__n, static_cast<decltype(__n)>(_M_count)); 2229 } 2230 }; 2231 2232 // _GLIBCXX_RESOLVE_LIB_DEFECTS 2233 // 3447. Deduction guides for take_view and drop_view have different 2234 // constraints 2235 template<typename _Range> 2236 take_view(_Range&&, range_difference_t<_Range>) 2237 -> take_view<views::all_t<_Range>>; 2238 2239 template<typename _Tp> 2240 inline constexpr bool enable_borrowed_range<take_view<_Tp>> 2241 = enable_borrowed_range<_Tp>; 2242 2243 namespace views 2244 { 2245 namespace __detail 2246 { 2247 template<typename _Range> 2248 inline constexpr bool __is_empty_view = false; 2249 2250 template<typename _Tp> 2251 inline constexpr bool __is_empty_view<empty_view<_Tp>> = true; 2252 2253 template<typename _Range> 2254 inline constexpr bool __is_basic_string_view = false; 2255 2256 template<typename _CharT, typename _Traits> 2257 inline constexpr bool __is_basic_string_view<basic_string_view<_CharT, _Traits>> 2258 = true; 2259 2260 template<typename _Range> 2261 inline constexpr bool __is_subrange = false; 2262 2263 template<typename _Iter, typename _Sent, subrange_kind _Kind> 2264 inline constexpr bool __is_subrange<subrange<_Iter, _Sent, _Kind>> = true; 2265 2266 template<typename _Range> 2267 inline constexpr bool __is_iota_view = false; 2268 2269 template<typename _Winc, typename _Bound> 2270 inline constexpr bool __is_iota_view<iota_view<_Winc, _Bound>> = true; 2271 2272 template<typename _Range, typename _Dp> 2273 concept __can_take_view 2274 = requires { take_view(std::declval<_Range>(), std::declval<_Dp>()); }; 2275 } // namespace __detail 2276 2277 struct _Take : __adaptor::_RangeAdaptor<_Take> 2278 { 2279 template<viewable_range _Range, typename _Dp = range_difference_t<_Range>> 2280 requires __detail::__can_take_view<_Range, _Dp> 2281 constexpr auto 2282 operator() [[nodiscard]] (_Range&& __r, type_identity_t<_Dp> __n) const 2283 { 2284 using _Tp = remove_cvref_t<_Range>; 2285 if constexpr (__detail::__is_empty_view<_Tp>) 2286 return _Tp(); 2287 else if constexpr (random_access_range<_Tp> 2288 && sized_range<_Tp> 2289 && (std::__detail::__is_span<_Tp> 2290 || __detail::__is_basic_string_view<_Tp> 2291 || __detail::__is_subrange<_Tp> 2292 || __detail::__is_iota_view<_Tp>)) 2293 { 2294 __n = std::min<_Dp>(ranges::distance(__r), __n); 2295 auto __begin = ranges::begin(__r); 2296 auto __end = __begin + __n; 2297 if constexpr (std::__detail::__is_span<_Tp>) 2298 return span<typename _Tp::element_type>(__begin, __end); 2299 else if constexpr (__detail::__is_basic_string_view<_Tp>) 2300 return _Tp(__begin, __end); 2301 else if constexpr (__detail::__is_subrange<_Tp>) 2302 return subrange<iterator_t<_Tp>>(__begin, __end); 2303 else 2304 return iota_view(*__begin, *__end); 2305 } 2306 else 2307 return take_view(std::forward<_Range>(__r), __n); 2308 } 2309 2310 using _RangeAdaptor<_Take>::operator(); 2311 static constexpr int _S_arity = 2; 2312 // The count argument of views::take is not always simple -- it can be 2313 // e.g. a move-only class that's implicitly convertible to the difference 2314 // type. But an integer-like count argument is surely simple. 2315 template<typename _Tp> 2316 static constexpr bool _S_has_simple_extra_args 2317 = ranges::__detail::__is_integer_like<_Tp>; 2318 }; 2319 2320 inline constexpr _Take take; 2321 } // namespace views 2322 2323 template<view _Vp, typename _Pred> 2324 requires input_range<_Vp> && is_object_v<_Pred> 2325 && indirect_unary_predicate<const _Pred, iterator_t<_Vp>> 2326 class take_while_view : public view_interface<take_while_view<_Vp, _Pred>> 2327 { 2328 template<bool _Const> 2329 struct _Sentinel 2330 { 2331 private: 2332 using _Base = __detail::__maybe_const_t<_Const, _Vp>; 2333 2334 sentinel_t<_Base> _M_end = sentinel_t<_Base>(); 2335 const _Pred* _M_pred = nullptr; 2336 2337 public: 2338 _Sentinel() = default; 2339 2340 constexpr explicit 2341 _Sentinel(sentinel_t<_Base> __end, const _Pred* __pred) 2342 : _M_end(__end), _M_pred(__pred) 2343 { } 2344 2345 constexpr 2346 _Sentinel(_Sentinel<!_Const> __s) 2347 requires _Const && convertible_to<sentinel_t<_Vp>, sentinel_t<_Base>> 2348 : _M_end(__s._M_end), _M_pred(__s._M_pred) 2349 { } 2350 2351 constexpr sentinel_t<_Base> 2352 base() const { return _M_end; } 2353 2354 friend constexpr bool 2355 operator==(const iterator_t<_Base>& __x, const _Sentinel& __y) 2356 { return __y._M_end == __x || !std::__invoke(*__y._M_pred, *__x); } 2357 2358 template<bool _OtherConst = !_Const, 2359 typename _Base2 = __detail::__maybe_const_t<_OtherConst, _Vp>> 2360 requires sentinel_for<sentinel_t<_Base>, iterator_t<_Base2>> 2361 friend constexpr bool 2362 operator==(const iterator_t<_Base2>& __x, const _Sentinel& __y) 2363 { return __y._M_end == __x || !std::__invoke(*__y._M_pred, *__x); } 2364 2365 friend _Sentinel<!_Const>; 2366 }; 2367 2368 _Vp _M_base = _Vp(); 2369 [[no_unique_address]] __detail::__box<_Pred> _M_pred; 2370 2371 public: 2372 take_while_view() requires (default_initializable<_Vp> 2373 && default_initializable<_Pred>) 2374 = default; 2375 2376 constexpr 2377 take_while_view(_Vp base, _Pred __pred) 2378 : _M_base(std::move(base)), _M_pred(std::move(__pred)) 2379 { } 2380 2381 constexpr _Vp 2382 base() const& requires copy_constructible<_Vp> 2383 { return _M_base; } 2384 2385 constexpr _Vp 2386 base() && 2387 { return std::move(_M_base); } 2388 2389 constexpr const _Pred& 2390 pred() const 2391 { return *_M_pred; } 2392 2393 constexpr auto 2394 begin() requires (!__detail::__simple_view<_Vp>) 2395 { return ranges::begin(_M_base); } 2396 2397 constexpr auto 2398 begin() const requires range<const _Vp> 2399 && indirect_unary_predicate<const _Pred, iterator_t<const _Vp>> 2400 { return ranges::begin(_M_base); } 2401 2402 constexpr auto 2403 end() requires (!__detail::__simple_view<_Vp>) 2404 { return _Sentinel<false>(ranges::end(_M_base), 2405 std::__addressof(*_M_pred)); } 2406 2407 constexpr auto 2408 end() const requires range<const _Vp> 2409 && indirect_unary_predicate<const _Pred, iterator_t<const _Vp>> 2410 { return _Sentinel<true>(ranges::end(_M_base), 2411 std::__addressof(*_M_pred)); } 2412 }; 2413 2414 template<typename _Range, typename _Pred> 2415 take_while_view(_Range&&, _Pred) 2416 -> take_while_view<views::all_t<_Range>, _Pred>; 2417 2418 namespace views 2419 { 2420 namespace __detail 2421 { 2422 template<typename _Range, typename _Pred> 2423 concept __can_take_while_view 2424 = requires { take_while_view(std::declval<_Range>(), std::declval<_Pred>()); }; 2425 } // namespace __detail 2426 2427 struct _TakeWhile : __adaptor::_RangeAdaptor<_TakeWhile> 2428 { 2429 template<viewable_range _Range, typename _Pred> 2430 requires __detail::__can_take_while_view<_Range, _Pred> 2431 constexpr auto 2432 operator() [[nodiscard]] (_Range&& __r, _Pred&& __p) const 2433 { 2434 return take_while_view(std::forward<_Range>(__r), std::forward<_Pred>(__p)); 2435 } 2436 2437 using _RangeAdaptor<_TakeWhile>::operator(); 2438 static constexpr int _S_arity = 2; 2439 static constexpr bool _S_has_simple_extra_args = true; 2440 }; 2441 2442 inline constexpr _TakeWhile take_while; 2443 } // namespace views 2444 2445 template<view _Vp> 2446 class drop_view : public view_interface<drop_view<_Vp>> 2447 { 2448 private: 2449 _Vp _M_base = _Vp(); 2450 range_difference_t<_Vp> _M_count = 0; 2451 2452 // ranges::next(begin(base), count, end(base)) is O(1) if _Vp satisfies 2453 // both random_access_range and sized_range. Otherwise, cache its result. 2454 static constexpr bool _S_needs_cached_begin 2455 = !(random_access_range<const _Vp> && sized_range<const _Vp>); 2456 [[no_unique_address]] 2457 __detail::__maybe_present_t<_S_needs_cached_begin, 2458 __detail::_CachedPosition<_Vp>> 2459 _M_cached_begin; 2460 2461 public: 2462 drop_view() requires default_initializable<_Vp> = default; 2463 2464 constexpr 2465 drop_view(_Vp __base, range_difference_t<_Vp> __count) 2466 : _M_base(std::move(__base)), _M_count(__count) 2467 { __glibcxx_assert(__count >= 0); } 2468 2469 constexpr _Vp 2470 base() const& requires copy_constructible<_Vp> 2471 { return _M_base; } 2472 2473 constexpr _Vp 2474 base() && 2475 { return std::move(_M_base); } 2476 2477 // This overload is disabled for simple views with constant-time begin(). 2478 constexpr auto 2479 begin() 2480 requires (!(__detail::__simple_view<_Vp> 2481 && random_access_range<const _Vp> 2482 && sized_range<const _Vp>)) 2483 { 2484 if constexpr (_S_needs_cached_begin) 2485 if (_M_cached_begin._M_has_value()) 2486 return _M_cached_begin._M_get(_M_base); 2487 2488 auto __it = ranges::next(ranges::begin(_M_base), 2489 _M_count, ranges::end(_M_base)); 2490 if constexpr (_S_needs_cached_begin) 2491 _M_cached_begin._M_set(_M_base, __it); 2492 return __it; 2493 } 2494 2495 // _GLIBCXX_RESOLVE_LIB_DEFECTS 2496 // 3482. drop_view's const begin should additionally require sized_range 2497 constexpr auto 2498 begin() const 2499 requires random_access_range<const _Vp> && sized_range<const _Vp> 2500 { 2501 return ranges::next(ranges::begin(_M_base), _M_count, 2502 ranges::end(_M_base)); 2503 } 2504 2505 constexpr auto 2506 end() requires (!__detail::__simple_view<_Vp>) 2507 { return ranges::end(_M_base); } 2508 2509 constexpr auto 2510 end() const requires range<const _Vp> 2511 { return ranges::end(_M_base); } 2512 2513 constexpr auto 2514 size() requires sized_range<_Vp> 2515 { 2516 const auto __s = ranges::size(_M_base); 2517 const auto __c = static_cast<decltype(__s)>(_M_count); 2518 return __s < __c ? 0 : __s - __c; 2519 } 2520 2521 constexpr auto 2522 size() const requires sized_range<const _Vp> 2523 { 2524 const auto __s = ranges::size(_M_base); 2525 const auto __c = static_cast<decltype(__s)>(_M_count); 2526 return __s < __c ? 0 : __s - __c; 2527 } 2528 }; 2529 2530 template<typename _Range> 2531 drop_view(_Range&&, range_difference_t<_Range>) 2532 -> drop_view<views::all_t<_Range>>; 2533 2534 template<typename _Tp> 2535 inline constexpr bool enable_borrowed_range<drop_view<_Tp>> 2536 = enable_borrowed_range<_Tp>; 2537 2538 namespace views 2539 { 2540 namespace __detail 2541 { 2542 template<typename _Range, typename _Dp> 2543 concept __can_drop_view 2544 = requires { drop_view(std::declval<_Range>(), std::declval<_Dp>()); }; 2545 } // namespace __detail 2546 2547 struct _Drop : __adaptor::_RangeAdaptor<_Drop> 2548 { 2549 template<viewable_range _Range, typename _Dp = range_difference_t<_Range>> 2550 requires __detail::__can_drop_view<_Range, _Dp> 2551 constexpr auto 2552 operator() [[nodiscard]] (_Range&& __r, type_identity_t<_Dp> __n) const 2553 { 2554 using _Tp = remove_cvref_t<_Range>; 2555 if constexpr (__detail::__is_empty_view<_Tp>) 2556 return _Tp(); 2557 else if constexpr (random_access_range<_Tp> 2558 && sized_range<_Tp> 2559 && (std::__detail::__is_span<_Tp> 2560 || __detail::__is_basic_string_view<_Tp> 2561 || __detail::__is_iota_view<_Tp> 2562 || __detail::__is_subrange<_Tp>)) 2563 { 2564 __n = std::min<_Dp>(ranges::distance(__r), __n); 2565 auto __begin = ranges::begin(__r) + __n; 2566 auto __end = ranges::end(__r); 2567 if constexpr (std::__detail::__is_span<_Tp>) 2568 return span<typename _Tp::element_type>(__begin, __end); 2569 else if constexpr (__detail::__is_subrange<_Tp>) 2570 { 2571 if constexpr (_Tp::_S_store_size) 2572 { 2573 using ranges::__detail::__to_unsigned_like; 2574 auto __m = ranges::distance(__r) - __n; 2575 return _Tp(__begin, __end, __to_unsigned_like(__m)); 2576 } 2577 else 2578 return _Tp(__begin, __end); 2579 } 2580 else 2581 return _Tp(__begin, __end); 2582 } 2583 else 2584 return drop_view(std::forward<_Range>(__r), __n); 2585 } 2586 2587 using _RangeAdaptor<_Drop>::operator(); 2588 static constexpr int _S_arity = 2; 2589 template<typename _Tp> 2590 static constexpr bool _S_has_simple_extra_args 2591 = _Take::_S_has_simple_extra_args<_Tp>; 2592 }; 2593 2594 inline constexpr _Drop drop; 2595 } // namespace views 2596 2597 template<view _Vp, typename _Pred> 2598 requires input_range<_Vp> && is_object_v<_Pred> 2599 && indirect_unary_predicate<const _Pred, iterator_t<_Vp>> 2600 class drop_while_view : public view_interface<drop_while_view<_Vp, _Pred>> 2601 { 2602 private: 2603 _Vp _M_base = _Vp(); 2604 [[no_unique_address]] __detail::__box<_Pred> _M_pred; 2605 [[no_unique_address]] __detail::_CachedPosition<_Vp> _M_cached_begin; 2606 2607 public: 2608 drop_while_view() requires (default_initializable<_Vp> 2609 && default_initializable<_Pred>) 2610 = default; 2611 2612 constexpr 2613 drop_while_view(_Vp __base, _Pred __pred) 2614 : _M_base(std::move(__base)), _M_pred(std::move(__pred)) 2615 { } 2616 2617 constexpr _Vp 2618 base() const& requires copy_constructible<_Vp> 2619 { return _M_base; } 2620 2621 constexpr _Vp 2622 base() && 2623 { return std::move(_M_base); } 2624 2625 constexpr const _Pred& 2626 pred() const 2627 { return *_M_pred; } 2628 2629 constexpr auto 2630 begin() 2631 { 2632 if (_M_cached_begin._M_has_value()) 2633 return _M_cached_begin._M_get(_M_base); 2634 2635 __glibcxx_assert(_M_pred.has_value()); 2636 auto __it = ranges::find_if_not(ranges::begin(_M_base), 2637 ranges::end(_M_base), 2638 std::cref(*_M_pred)); 2639 _M_cached_begin._M_set(_M_base, __it); 2640 return __it; 2641 } 2642 2643 constexpr auto 2644 end() 2645 { return ranges::end(_M_base); } 2646 }; 2647 2648 template<typename _Range, typename _Pred> 2649 drop_while_view(_Range&&, _Pred) 2650 -> drop_while_view<views::all_t<_Range>, _Pred>; 2651 2652 template<typename _Tp, typename _Pred> 2653 inline constexpr bool enable_borrowed_range<drop_while_view<_Tp, _Pred>> 2654 = enable_borrowed_range<_Tp>; 2655 2656 namespace views 2657 { 2658 namespace __detail 2659 { 2660 template<typename _Range, typename _Pred> 2661 concept __can_drop_while_view 2662 = requires { drop_while_view(std::declval<_Range>(), std::declval<_Pred>()); }; 2663 } // namespace __detail 2664 2665 struct _DropWhile : __adaptor::_RangeAdaptor<_DropWhile> 2666 { 2667 template<viewable_range _Range, typename _Pred> 2668 requires __detail::__can_drop_while_view<_Range, _Pred> 2669 constexpr auto 2670 operator() [[nodiscard]] (_Range&& __r, _Pred&& __p) const 2671 { 2672 return drop_while_view(std::forward<_Range>(__r), 2673 std::forward<_Pred>(__p)); 2674 } 2675 2676 using _RangeAdaptor<_DropWhile>::operator(); 2677 static constexpr int _S_arity = 2; 2678 static constexpr bool _S_has_simple_extra_args = true; 2679 }; 2680 2681 inline constexpr _DropWhile drop_while; 2682 } // namespace views 2683 2684 template<input_range _Vp> 2685 requires view<_Vp> && input_range<range_reference_t<_Vp>> 2686 class join_view : public view_interface<join_view<_Vp>> 2687 { 2688 private: 2689 using _InnerRange = range_reference_t<_Vp>; 2690 2691 template<bool _Const> 2692 using _Base = __detail::__maybe_const_t<_Const, _Vp>; 2693 2694 template<bool _Const> 2695 using _Outer_iter = iterator_t<_Base<_Const>>; 2696 2697 template<bool _Const> 2698 using _Inner_iter = iterator_t<range_reference_t<_Base<_Const>>>; 2699 2700 template<bool _Const> 2701 static constexpr bool _S_ref_is_glvalue 2702 = is_reference_v<range_reference_t<_Base<_Const>>>; 2703 2704 template<bool _Const> 2705 struct __iter_cat 2706 { }; 2707 2708 template<bool _Const> 2709 requires _S_ref_is_glvalue<_Const> 2710 && forward_range<_Base<_Const>> 2711 && forward_range<range_reference_t<_Base<_Const>>> 2712 struct __iter_cat<_Const> 2713 { 2714 private: 2715 static constexpr auto 2716 _S_iter_cat() 2717 { 2718 using _Outer_iter = join_view::_Outer_iter<_Const>; 2719 using _Inner_iter = join_view::_Inner_iter<_Const>; 2720 using _OuterCat = typename iterator_traits<_Outer_iter>::iterator_category; 2721 using _InnerCat = typename iterator_traits<_Inner_iter>::iterator_category; 2722 if constexpr (derived_from<_OuterCat, bidirectional_iterator_tag> 2723 && derived_from<_InnerCat, bidirectional_iterator_tag> 2724 && common_range<range_reference_t<_Base<_Const>>>) 2725 return bidirectional_iterator_tag{}; 2726 else if constexpr (derived_from<_OuterCat, forward_iterator_tag> 2727 && derived_from<_InnerCat, forward_iterator_tag>) 2728 return forward_iterator_tag{}; 2729 else 2730 return input_iterator_tag{}; 2731 } 2732 public: 2733 using iterator_category = decltype(_S_iter_cat()); 2734 }; 2735 2736 template<bool _Const> 2737 struct _Sentinel; 2738 2739 template<bool _Const> 2740 struct _Iterator : __iter_cat<_Const> 2741 { 2742 private: 2743 using _Parent = __detail::__maybe_const_t<_Const, join_view>; 2744 using _Base = join_view::_Base<_Const>; 2745 2746 static constexpr bool _S_ref_is_glvalue 2747 = join_view::_S_ref_is_glvalue<_Const>; 2748 2749 constexpr void 2750 _M_satisfy() 2751 { 2752 auto __update_inner = [this] (const iterator_t<_Base>& __x) -> auto&& { 2753 if constexpr (_S_ref_is_glvalue) 2754 return *__x; 2755 else 2756 return _M_parent->_M_inner._M_emplace_deref(__x); 2757 }; 2758 2759 for (; _M_outer != ranges::end(_M_parent->_M_base); ++_M_outer) 2760 { 2761 auto&& __inner = __update_inner(_M_outer); 2762 _M_inner = ranges::begin(__inner); 2763 if (_M_inner != ranges::end(__inner)) 2764 return; 2765 } 2766 2767 if constexpr (_S_ref_is_glvalue) 2768 _M_inner = _Inner_iter(); 2769 } 2770 2771 static constexpr auto 2772 _S_iter_concept() 2773 { 2774 if constexpr (_S_ref_is_glvalue 2775 && bidirectional_range<_Base> 2776 && bidirectional_range<range_reference_t<_Base>> 2777 && common_range<range_reference_t<_Base>>) 2778 return bidirectional_iterator_tag{}; 2779 else if constexpr (_S_ref_is_glvalue 2780 && forward_range<_Base> 2781 && forward_range<range_reference_t<_Base>>) 2782 return forward_iterator_tag{}; 2783 else 2784 return input_iterator_tag{}; 2785 } 2786 2787 using _Outer_iter = join_view::_Outer_iter<_Const>; 2788 using _Inner_iter = join_view::_Inner_iter<_Const>; 2789 2790 _Outer_iter _M_outer = _Outer_iter(); 2791 _Inner_iter _M_inner = _Inner_iter(); 2792 _Parent* _M_parent = nullptr; 2793 2794 public: 2795 using iterator_concept = decltype(_S_iter_concept()); 2796 // iterator_category defined in __join_view_iter_cat 2797 using value_type = range_value_t<range_reference_t<_Base>>; 2798 using difference_type 2799 = common_type_t<range_difference_t<_Base>, 2800 range_difference_t<range_reference_t<_Base>>>; 2801 2802 _Iterator() requires (default_initializable<_Outer_iter> 2803 && default_initializable<_Inner_iter>) 2804 = default; 2805 2806 constexpr 2807 _Iterator(_Parent* __parent, _Outer_iter __outer) 2808 : _M_outer(std::move(__outer)), 2809 _M_parent(__parent) 2810 { _M_satisfy(); } 2811 2812 constexpr 2813 _Iterator(_Iterator<!_Const> __i) 2814 requires _Const 2815 && convertible_to<iterator_t<_Vp>, _Outer_iter> 2816 && convertible_to<iterator_t<_InnerRange>, _Inner_iter> 2817 : _M_outer(std::move(__i._M_outer)), _M_inner(std::move(__i._M_inner)), 2818 _M_parent(__i._M_parent) 2819 { } 2820 2821 constexpr decltype(auto) 2822 operator*() const 2823 { return *_M_inner; } 2824 2825 // _GLIBCXX_RESOLVE_LIB_DEFECTS 2826 // 3500. join_view::iterator::operator->() is bogus 2827 constexpr _Inner_iter 2828 operator->() const 2829 requires __detail::__has_arrow<_Inner_iter> 2830 && copyable<_Inner_iter> 2831 { return _M_inner; } 2832 2833 constexpr _Iterator& 2834 operator++() 2835 { 2836 auto&& __inner_range = [this] () -> auto&& { 2837 if constexpr (_S_ref_is_glvalue) 2838 return *_M_outer; 2839 else 2840 return *_M_parent->_M_inner; 2841 }(); 2842 if (++_M_inner == ranges::end(__inner_range)) 2843 { 2844 ++_M_outer; 2845 _M_satisfy(); 2846 } 2847 return *this; 2848 } 2849 2850 constexpr void 2851 operator++(int) 2852 { ++*this; } 2853 2854 constexpr _Iterator 2855 operator++(int) 2856 requires _S_ref_is_glvalue && forward_range<_Base> 2857 && forward_range<range_reference_t<_Base>> 2858 { 2859 auto __tmp = *this; 2860 ++*this; 2861 return __tmp; 2862 } 2863 2864 constexpr _Iterator& 2865 operator--() 2866 requires _S_ref_is_glvalue && bidirectional_range<_Base> 2867 && bidirectional_range<range_reference_t<_Base>> 2868 && common_range<range_reference_t<_Base>> 2869 { 2870 if (_M_outer == ranges::end(_M_parent->_M_base)) 2871 _M_inner = ranges::end(*--_M_outer); 2872 while (_M_inner == ranges::begin(*_M_outer)) 2873 _M_inner = ranges::end(*--_M_outer); 2874 --_M_inner; 2875 return *this; 2876 } 2877 2878 constexpr _Iterator 2879 operator--(int) 2880 requires _S_ref_is_glvalue && bidirectional_range<_Base> 2881 && bidirectional_range<range_reference_t<_Base>> 2882 && common_range<range_reference_t<_Base>> 2883 { 2884 auto __tmp = *this; 2885 --*this; 2886 return __tmp; 2887 } 2888 2889 friend constexpr bool 2890 operator==(const _Iterator& __x, const _Iterator& __y) 2891 requires _S_ref_is_glvalue 2892 && equality_comparable<_Outer_iter> 2893 && equality_comparable<_Inner_iter> 2894 { 2895 return (__x._M_outer == __y._M_outer 2896 && __x._M_inner == __y._M_inner); 2897 } 2898 2899 friend constexpr decltype(auto) 2900 iter_move(const _Iterator& __i) 2901 noexcept(noexcept(ranges::iter_move(__i._M_inner))) 2902 { return ranges::iter_move(__i._M_inner); } 2903 2904 friend constexpr void 2905 iter_swap(const _Iterator& __x, const _Iterator& __y) 2906 noexcept(noexcept(ranges::iter_swap(__x._M_inner, __y._M_inner))) 2907 requires indirectly_swappable<_Inner_iter> 2908 { return ranges::iter_swap(__x._M_inner, __y._M_inner); } 2909 2910 friend _Iterator<!_Const>; 2911 template<bool> friend struct _Sentinel; 2912 }; 2913 2914 template<bool _Const> 2915 struct _Sentinel 2916 { 2917 private: 2918 using _Parent = __detail::__maybe_const_t<_Const, join_view>; 2919 using _Base = join_view::_Base<_Const>; 2920 2921 template<bool _Const2> 2922 constexpr bool 2923 __equal(const _Iterator<_Const2>& __i) const 2924 { return __i._M_outer == _M_end; } 2925 2926 sentinel_t<_Base> _M_end = sentinel_t<_Base>(); 2927 2928 public: 2929 _Sentinel() = default; 2930 2931 constexpr explicit 2932 _Sentinel(_Parent* __parent) 2933 : _M_end(ranges::end(__parent->_M_base)) 2934 { } 2935 2936 constexpr 2937 _Sentinel(_Sentinel<!_Const> __s) 2938 requires _Const && convertible_to<sentinel_t<_Vp>, sentinel_t<_Base>> 2939 : _M_end(std::move(__s._M_end)) 2940 { } 2941 2942 template<bool _Const2> 2943 requires sentinel_for<sentinel_t<_Base>, 2944 iterator_t<__detail::__maybe_const_t<_Const2, _Vp>>> 2945 friend constexpr bool 2946 operator==(const _Iterator<_Const2>& __x, const _Sentinel& __y) 2947 { return __y.__equal(__x); } 2948 2949 friend _Sentinel<!_Const>; 2950 }; 2951 2952 _Vp _M_base = _Vp(); 2953 [[no_unique_address]] 2954 __detail::__non_propagating_cache<remove_cv_t<_InnerRange>> _M_inner; 2955 2956 public: 2957 join_view() requires default_initializable<_Vp> = default; 2958 2959 constexpr explicit 2960 join_view(_Vp __base) 2961 : _M_base(std::move(__base)) 2962 { } 2963 2964 constexpr _Vp 2965 base() const& requires copy_constructible<_Vp> 2966 { return _M_base; } 2967 2968 constexpr _Vp 2969 base() && 2970 { return std::move(_M_base); } 2971 2972 constexpr auto 2973 begin() 2974 { 2975 constexpr bool __use_const 2976 = (__detail::__simple_view<_Vp> 2977 && is_reference_v<range_reference_t<_Vp>>); 2978 return _Iterator<__use_const>{this, ranges::begin(_M_base)}; 2979 } 2980 2981 constexpr auto 2982 begin() const 2983 requires input_range<const _Vp> 2984 && is_reference_v<range_reference_t<const _Vp>> 2985 { 2986 return _Iterator<true>{this, ranges::begin(_M_base)}; 2987 } 2988 2989 constexpr auto 2990 end() 2991 { 2992 if constexpr (forward_range<_Vp> && is_reference_v<_InnerRange> 2993 && forward_range<_InnerRange> 2994 && common_range<_Vp> && common_range<_InnerRange>) 2995 return _Iterator<__detail::__simple_view<_Vp>>{this, 2996 ranges::end(_M_base)}; 2997 else 2998 return _Sentinel<__detail::__simple_view<_Vp>>{this}; 2999 } 3000 3001 constexpr auto 3002 end() const 3003 requires input_range<const _Vp> 3004 && is_reference_v<range_reference_t<const _Vp>> 3005 { 3006 if constexpr (forward_range<const _Vp> 3007 && is_reference_v<range_reference_t<const _Vp>> 3008 && forward_range<range_reference_t<const _Vp>> 3009 && common_range<const _Vp> 3010 && common_range<range_reference_t<const _Vp>>) 3011 return _Iterator<true>{this, ranges::end(_M_base)}; 3012 else 3013 return _Sentinel<true>{this}; 3014 } 3015 }; 3016 3017 template<typename _Range> 3018 explicit join_view(_Range&&) -> join_view<views::all_t<_Range>>; 3019 3020 namespace views 3021 { 3022 namespace __detail 3023 { 3024 template<typename _Range> 3025 concept __can_join_view 3026 = requires { join_view<all_t<_Range>>{std::declval<_Range>()}; }; 3027 } // namespace __detail 3028 3029 struct _Join : __adaptor::_RangeAdaptorClosure 3030 { 3031 template<viewable_range _Range> 3032 requires __detail::__can_join_view<_Range> 3033 constexpr auto 3034 operator() [[nodiscard]] (_Range&& __r) const 3035 { 3036 // _GLIBCXX_RESOLVE_LIB_DEFECTS 3037 // 3474. Nesting join_views is broken because of CTAD 3038 return join_view<all_t<_Range>>{std::forward<_Range>(__r)}; 3039 } 3040 3041 static constexpr bool _S_has_simple_call_op = true; 3042 }; 3043 3044 inline constexpr _Join join; 3045 } // namespace views 3046 3047 namespace __detail 3048 { 3049 template<auto> 3050 struct __require_constant; 3051 3052 template<typename _Range> 3053 concept __tiny_range = sized_range<_Range> 3054 && requires 3055 { typename __require_constant<remove_reference_t<_Range>::size()>; } 3056 && (remove_reference_t<_Range>::size() <= 1); 3057 3058 template<typename _Base> 3059 struct __lazy_split_view_outer_iter_cat 3060 { }; 3061 3062 template<forward_range _Base> 3063 struct __lazy_split_view_outer_iter_cat<_Base> 3064 { using iterator_category = input_iterator_tag; }; 3065 3066 template<typename _Base> 3067 struct __lazy_split_view_inner_iter_cat 3068 { }; 3069 3070 template<forward_range _Base> 3071 struct __lazy_split_view_inner_iter_cat<_Base> 3072 { 3073 private: 3074 static constexpr auto 3075 _S_iter_cat() 3076 { 3077 using _Cat = typename iterator_traits<iterator_t<_Base>>::iterator_category; 3078 if constexpr (derived_from<_Cat, forward_iterator_tag>) 3079 return forward_iterator_tag{}; 3080 else 3081 return _Cat{}; 3082 } 3083 public: 3084 using iterator_category = decltype(_S_iter_cat()); 3085 }; 3086 } 3087 3088 template<input_range _Vp, forward_range _Pattern> 3089 requires view<_Vp> && view<_Pattern> 3090 && indirectly_comparable<iterator_t<_Vp>, iterator_t<_Pattern>, 3091 ranges::equal_to> 3092 && (forward_range<_Vp> || __detail::__tiny_range<_Pattern>) 3093 class lazy_split_view : public view_interface<lazy_split_view<_Vp, _Pattern>> 3094 { 3095 private: 3096 template<bool _Const> 3097 using _Base = __detail::__maybe_const_t<_Const, _Vp>; 3098 3099 template<bool _Const> 3100 struct _InnerIter; 3101 3102 template<bool _Const> 3103 struct _OuterIter 3104 : __detail::__lazy_split_view_outer_iter_cat<_Base<_Const>> 3105 { 3106 private: 3107 using _Parent = __detail::__maybe_const_t<_Const, lazy_split_view>; 3108 using _Base = lazy_split_view::_Base<_Const>; 3109 3110 constexpr bool 3111 __at_end() const 3112 { return __current() == ranges::end(_M_parent->_M_base) && !_M_trailing_empty; } 3113 3114 // [range.lazy.split.outer] p1 3115 // Many of the following specifications refer to the notional member 3116 // current of outer-iterator. current is equivalent to current_ if 3117 // V models forward_range, and parent_->current_ otherwise. 3118 constexpr auto& 3119 __current() noexcept 3120 { 3121 if constexpr (forward_range<_Vp>) 3122 return _M_current; 3123 else 3124 return *_M_parent->_M_current; 3125 } 3126 3127 constexpr auto& 3128 __current() const noexcept 3129 { 3130 if constexpr (forward_range<_Vp>) 3131 return _M_current; 3132 else 3133 return *_M_parent->_M_current; 3134 } 3135 3136 _Parent* _M_parent = nullptr; 3137 3138 // XXX: _M_current is present only if "V models forward_range" 3139 [[no_unique_address]] 3140 __detail::__maybe_present_t<forward_range<_Vp>, 3141 iterator_t<_Base>> _M_current; 3142 bool _M_trailing_empty = false; 3143 3144 public: 3145 using iterator_concept = __conditional_t<forward_range<_Base>, 3146 forward_iterator_tag, 3147 input_iterator_tag>; 3148 // iterator_category defined in __lazy_split_view_outer_iter_cat 3149 using difference_type = range_difference_t<_Base>; 3150 3151 struct value_type : view_interface<value_type> 3152 { 3153 private: 3154 _OuterIter _M_i = _OuterIter(); 3155 3156 public: 3157 value_type() = default; 3158 3159 constexpr explicit 3160 value_type(_OuterIter __i) 3161 : _M_i(std::move(__i)) 3162 { } 3163 3164 constexpr _InnerIter<_Const> 3165 begin() const 3166 { return _InnerIter<_Const>{_M_i}; } 3167 3168 constexpr default_sentinel_t 3169 end() const noexcept 3170 { return default_sentinel; } 3171 }; 3172 3173 _OuterIter() = default; 3174 3175 constexpr explicit 3176 _OuterIter(_Parent* __parent) requires (!forward_range<_Base>) 3177 : _M_parent(__parent) 3178 { } 3179 3180 constexpr 3181 _OuterIter(_Parent* __parent, iterator_t<_Base> __current) 3182 requires forward_range<_Base> 3183 : _M_parent(__parent), 3184 _M_current(std::move(__current)) 3185 { } 3186 3187 constexpr 3188 _OuterIter(_OuterIter<!_Const> __i) 3189 requires _Const 3190 && convertible_to<iterator_t<_Vp>, iterator_t<_Base>> 3191 : _M_parent(__i._M_parent), _M_current(std::move(__i._M_current)), 3192 _M_trailing_empty(__i._M_trailing_empty) 3193 { } 3194 3195 constexpr value_type 3196 operator*() const 3197 { return value_type{*this}; } 3198 3199 constexpr _OuterIter& 3200 operator++() 3201 { 3202 // _GLIBCXX_RESOLVE_LIB_DEFECTS 3203 // 3505. lazy_split_view::outer-iterator::operator++ misspecified 3204 const auto __end = ranges::end(_M_parent->_M_base); 3205 if (__current() == __end) 3206 { 3207 _M_trailing_empty = false; 3208 return *this; 3209 } 3210 const auto [__pbegin, __pend] = subrange{_M_parent->_M_pattern}; 3211 if (__pbegin == __pend) 3212 ++__current(); 3213 else if constexpr (__detail::__tiny_range<_Pattern>) 3214 { 3215 __current() = ranges::find(std::move(__current()), __end, 3216 *__pbegin); 3217 if (__current() != __end) 3218 { 3219 ++__current(); 3220 if (__current() == __end) 3221 _M_trailing_empty = true; 3222 } 3223 } 3224 else 3225 do 3226 { 3227 auto [__b, __p] 3228 = ranges::mismatch(__current(), __end, __pbegin, __pend); 3229 if (__p == __pend) 3230 { 3231 __current() = __b; 3232 if (__current() == __end) 3233 _M_trailing_empty = true; 3234 break; 3235 } 3236 } while (++__current() != __end); 3237 return *this; 3238 } 3239 3240 constexpr decltype(auto) 3241 operator++(int) 3242 { 3243 if constexpr (forward_range<_Base>) 3244 { 3245 auto __tmp = *this; 3246 ++*this; 3247 return __tmp; 3248 } 3249 else 3250 ++*this; 3251 } 3252 3253 friend constexpr bool 3254 operator==(const _OuterIter& __x, const _OuterIter& __y) 3255 requires forward_range<_Base> 3256 { 3257 return __x._M_current == __y._M_current 3258 && __x._M_trailing_empty == __y._M_trailing_empty; 3259 } 3260 3261 friend constexpr bool 3262 operator==(const _OuterIter& __x, default_sentinel_t) 3263 { return __x.__at_end(); }; 3264 3265 friend _OuterIter<!_Const>; 3266 friend _InnerIter<_Const>; 3267 }; 3268 3269 template<bool _Const> 3270 struct _InnerIter 3271 : __detail::__lazy_split_view_inner_iter_cat<_Base<_Const>> 3272 { 3273 private: 3274 using _Base = lazy_split_view::_Base<_Const>; 3275 3276 constexpr bool 3277 __at_end() const 3278 { 3279 auto [__pcur, __pend] = subrange{_M_i._M_parent->_M_pattern}; 3280 auto __end = ranges::end(_M_i._M_parent->_M_base); 3281 if constexpr (__detail::__tiny_range<_Pattern>) 3282 { 3283 const auto& __cur = _M_i_current(); 3284 if (__cur == __end) 3285 return true; 3286 if (__pcur == __pend) 3287 return _M_incremented; 3288 return *__cur == *__pcur; 3289 } 3290 else 3291 { 3292 auto __cur = _M_i_current(); 3293 if (__cur == __end) 3294 return true; 3295 if (__pcur == __pend) 3296 return _M_incremented; 3297 do 3298 { 3299 if (*__cur != *__pcur) 3300 return false; 3301 if (++__pcur == __pend) 3302 return true; 3303 } while (++__cur != __end); 3304 return false; 3305 } 3306 } 3307 3308 constexpr auto& 3309 _M_i_current() noexcept 3310 { return _M_i.__current(); } 3311 3312 constexpr auto& 3313 _M_i_current() const noexcept 3314 { return _M_i.__current(); } 3315 3316 _OuterIter<_Const> _M_i = _OuterIter<_Const>(); 3317 bool _M_incremented = false; 3318 3319 public: 3320 using iterator_concept 3321 = typename _OuterIter<_Const>::iterator_concept; 3322 // iterator_category defined in __lazy_split_view_inner_iter_cat 3323 using value_type = range_value_t<_Base>; 3324 using difference_type = range_difference_t<_Base>; 3325 3326 _InnerIter() = default; 3327 3328 constexpr explicit 3329 _InnerIter(_OuterIter<_Const> __i) 3330 : _M_i(std::move(__i)) 3331 { } 3332 3333 constexpr const iterator_t<_Base>& 3334 base() const& noexcept 3335 { return _M_i_current(); } 3336 3337 constexpr iterator_t<_Base> 3338 base() && requires forward_range<_Vp> 3339 { return std::move(_M_i_current()); } 3340 3341 constexpr decltype(auto) 3342 operator*() const 3343 { return *_M_i_current(); } 3344 3345 constexpr _InnerIter& 3346 operator++() 3347 { 3348 _M_incremented = true; 3349 if constexpr (!forward_range<_Base>) 3350 if constexpr (_Pattern::size() == 0) 3351 return *this; 3352 ++_M_i_current(); 3353 return *this; 3354 } 3355 3356 constexpr decltype(auto) 3357 operator++(int) 3358 { 3359 if constexpr (forward_range<_Base>) 3360 { 3361 auto __tmp = *this; 3362 ++*this; 3363 return __tmp; 3364 } 3365 else 3366 ++*this; 3367 } 3368 3369 friend constexpr bool 3370 operator==(const _InnerIter& __x, const _InnerIter& __y) 3371 requires forward_range<_Base> 3372 { return __x._M_i == __y._M_i; } 3373 3374 friend constexpr bool 3375 operator==(const _InnerIter& __x, default_sentinel_t) 3376 { return __x.__at_end(); } 3377 3378 friend constexpr decltype(auto) 3379 iter_move(const _InnerIter& __i) 3380 noexcept(noexcept(ranges::iter_move(__i._M_i_current()))) 3381 { return ranges::iter_move(__i._M_i_current()); } 3382 3383 friend constexpr void 3384 iter_swap(const _InnerIter& __x, const _InnerIter& __y) 3385 noexcept(noexcept(ranges::iter_swap(__x._M_i_current(), 3386 __y._M_i_current()))) 3387 requires indirectly_swappable<iterator_t<_Base>> 3388 { ranges::iter_swap(__x._M_i_current(), __y._M_i_current()); } 3389 }; 3390 3391 _Vp _M_base = _Vp(); 3392 _Pattern _M_pattern = _Pattern(); 3393 // XXX: _M_current is "present only if !forward_range<V>" 3394 [[no_unique_address]] 3395 __detail::__maybe_present_t<!forward_range<_Vp>, 3396 __detail::__non_propagating_cache<iterator_t<_Vp>>> _M_current; 3397 3398 3399 public: 3400 lazy_split_view() requires (default_initializable<_Vp> 3401 && default_initializable<_Pattern>) 3402 = default; 3403 3404 constexpr 3405 lazy_split_view(_Vp __base, _Pattern __pattern) 3406 : _M_base(std::move(__base)), _M_pattern(std::move(__pattern)) 3407 { } 3408 3409 template<input_range _Range> 3410 requires constructible_from<_Vp, views::all_t<_Range>> 3411 && constructible_from<_Pattern, single_view<range_value_t<_Range>>> 3412 constexpr 3413 lazy_split_view(_Range&& __r, range_value_t<_Range> __e) 3414 : _M_base(views::all(std::forward<_Range>(__r))), 3415 _M_pattern(views::single(std::move(__e))) 3416 { } 3417 3418 constexpr _Vp 3419 base() const& requires copy_constructible<_Vp> 3420 { return _M_base; } 3421 3422 constexpr _Vp 3423 base() && 3424 { return std::move(_M_base); } 3425 3426 constexpr auto 3427 begin() 3428 { 3429 if constexpr (forward_range<_Vp>) 3430 { 3431 constexpr bool __simple 3432 = __detail::__simple_view<_Vp> && __detail::__simple_view<_Pattern>; 3433 return _OuterIter<__simple>{this, ranges::begin(_M_base)}; 3434 } 3435 else 3436 { 3437 _M_current = ranges::begin(_M_base); 3438 return _OuterIter<false>{this}; 3439 } 3440 } 3441 3442 constexpr auto 3443 begin() const requires forward_range<_Vp> && forward_range<const _Vp> 3444 { 3445 return _OuterIter<true>{this, ranges::begin(_M_base)}; 3446 } 3447 3448 constexpr auto 3449 end() requires forward_range<_Vp> && common_range<_Vp> 3450 { 3451 constexpr bool __simple 3452 = __detail::__simple_view<_Vp> && __detail::__simple_view<_Pattern>; 3453 return _OuterIter<__simple>{this, ranges::end(_M_base)}; 3454 } 3455 3456 constexpr auto 3457 end() const 3458 { 3459 if constexpr (forward_range<_Vp> 3460 && forward_range<const _Vp> 3461 && common_range<const _Vp>) 3462 return _OuterIter<true>{this, ranges::end(_M_base)}; 3463 else 3464 return default_sentinel; 3465 } 3466 }; 3467 3468 template<typename _Range, typename _Pattern> 3469 lazy_split_view(_Range&&, _Pattern&&) 3470 -> lazy_split_view<views::all_t<_Range>, views::all_t<_Pattern>>; 3471 3472 template<input_range _Range> 3473 lazy_split_view(_Range&&, range_value_t<_Range>) 3474 -> lazy_split_view<views::all_t<_Range>, single_view<range_value_t<_Range>>>; 3475 3476 namespace views 3477 { 3478 namespace __detail 3479 { 3480 template<typename _Range, typename _Pattern> 3481 concept __can_lazy_split_view 3482 = requires { lazy_split_view(std::declval<_Range>(), std::declval<_Pattern>()); }; 3483 } // namespace __detail 3484 3485 struct _LazySplit : __adaptor::_RangeAdaptor<_LazySplit> 3486 { 3487 template<viewable_range _Range, typename _Pattern> 3488 requires __detail::__can_lazy_split_view<_Range, _Pattern> 3489 constexpr auto 3490 operator() [[nodiscard]] (_Range&& __r, _Pattern&& __f) const 3491 { 3492 return lazy_split_view(std::forward<_Range>(__r), std::forward<_Pattern>(__f)); 3493 } 3494 3495 using _RangeAdaptor<_LazySplit>::operator(); 3496 static constexpr int _S_arity = 2; 3497 // The pattern argument of views::lazy_split is not always simple -- it can be 3498 // a non-view range, the value category of which affects whether the call 3499 // is well-formed. But a scalar or a view pattern argument is surely 3500 // simple. 3501 template<typename _Pattern> 3502 static constexpr bool _S_has_simple_extra_args 3503 = is_scalar_v<_Pattern> || (view<_Pattern> 3504 && copy_constructible<_Pattern>); 3505 }; 3506 3507 inline constexpr _LazySplit lazy_split; 3508 } // namespace views 3509 3510 template<forward_range _Vp, forward_range _Pattern> 3511 requires view<_Vp> && view<_Pattern> 3512 && indirectly_comparable<iterator_t<_Vp>, iterator_t<_Pattern>, 3513 ranges::equal_to> 3514 class split_view : public view_interface<split_view<_Vp, _Pattern>> 3515 { 3516 private: 3517 _Vp _M_base = _Vp(); 3518 _Pattern _M_pattern = _Pattern(); 3519 __detail::__non_propagating_cache<subrange<iterator_t<_Vp>>> _M_cached_begin; 3520 3521 struct _Iterator; 3522 struct _Sentinel; 3523 3524 public: 3525 split_view() requires (default_initializable<_Vp> 3526 && default_initializable<_Pattern>) 3527 = default; 3528 3529 constexpr 3530 split_view(_Vp __base, _Pattern __pattern) 3531 : _M_base(std::move(__base)), _M_pattern(std::move(__pattern)) 3532 { } 3533 3534 template<forward_range _Range> 3535 requires constructible_from<_Vp, views::all_t<_Range>> 3536 && constructible_from<_Pattern, single_view<range_value_t<_Range>>> 3537 constexpr 3538 split_view(_Range&& __r, range_value_t<_Range> __e) 3539 : _M_base(views::all(std::forward<_Range>(__r))), 3540 _M_pattern(views::single(std::move(__e))) 3541 { } 3542 3543 constexpr _Vp 3544 base() const& requires copy_constructible<_Vp> 3545 { return _M_base; } 3546 3547 constexpr _Vp 3548 base() && 3549 { return std::move(_M_base); } 3550 3551 constexpr _Iterator 3552 begin() 3553 { 3554 if (!_M_cached_begin) 3555 _M_cached_begin = _M_find_next(ranges::begin(_M_base)); 3556 return {this, ranges::begin(_M_base), *_M_cached_begin}; 3557 } 3558 3559 constexpr auto 3560 end() 3561 { 3562 if constexpr (common_range<_Vp>) 3563 return _Iterator{this, ranges::end(_M_base), {}}; 3564 else 3565 return _Sentinel{this}; 3566 } 3567 3568 constexpr subrange<iterator_t<_Vp>> 3569 _M_find_next(iterator_t<_Vp> __it) 3570 { 3571 auto [__b, __e] = ranges::search(subrange(__it, ranges::end(_M_base)), _M_pattern); 3572 if (__b != ranges::end(_M_base) && ranges::empty(_M_pattern)) 3573 { 3574 ++__b; 3575 ++__e; 3576 } 3577 return {__b, __e}; 3578 } 3579 3580 private: 3581 struct _Iterator 3582 { 3583 private: 3584 split_view* _M_parent = nullptr; 3585 iterator_t<_Vp> _M_cur = iterator_t<_Vp>(); 3586 subrange<iterator_t<_Vp>> _M_next = subrange<iterator_t<_Vp>>(); 3587 bool _M_trailing_empty = false; 3588 3589 friend struct _Sentinel; 3590 3591 public: 3592 using iterator_concept = forward_iterator_tag; 3593 using iterator_category = input_iterator_tag; 3594 using value_type = subrange<iterator_t<_Vp>>; 3595 using difference_type = range_difference_t<_Vp>; 3596 3597 _Iterator() = default; 3598 3599 constexpr 3600 _Iterator(split_view* __parent, 3601 iterator_t<_Vp> __current, 3602 subrange<iterator_t<_Vp>> __next) 3603 : _M_parent(__parent), 3604 _M_cur(std::move(__current)), 3605 _M_next(std::move(__next)) 3606 { } 3607 3608 constexpr iterator_t<_Vp> 3609 base() const 3610 { return _M_cur; } 3611 3612 constexpr value_type 3613 operator*() const 3614 { return {_M_cur, _M_next.begin()}; } 3615 3616 constexpr _Iterator& 3617 operator++() 3618 { 3619 _M_cur = _M_next.begin(); 3620 if (_M_cur != ranges::end(_M_parent->_M_base)) 3621 { 3622 _M_cur = _M_next.end(); 3623 if (_M_cur == ranges::end(_M_parent->_M_base)) 3624 { 3625 _M_trailing_empty = true; 3626 _M_next = {_M_cur, _M_cur}; 3627 } 3628 else 3629 _M_next = _M_parent->_M_find_next(_M_cur); 3630 } 3631 else 3632 _M_trailing_empty = false; 3633 return *this; 3634 } 3635 3636 constexpr _Iterator 3637 operator++(int) 3638 { 3639 auto __tmp = *this; 3640 ++*this; 3641 return __tmp; 3642 } 3643 3644 friend constexpr bool 3645 operator==(const _Iterator& __x, const _Iterator& __y) 3646 { 3647 return __x._M_cur == __y._M_cur 3648 && __x._M_trailing_empty == __y._M_trailing_empty; 3649 } 3650 }; 3651 3652 struct _Sentinel 3653 { 3654 private: 3655 sentinel_t<_Vp> _M_end = sentinel_t<_Vp>(); 3656 3657 constexpr bool 3658 _M_equal(const _Iterator& __x) const 3659 { return __x._M_cur == _M_end && !__x._M_trailing_empty; } 3660 3661 public: 3662 _Sentinel() = default; 3663 3664 constexpr explicit 3665 _Sentinel(split_view* __parent) 3666 : _M_end(ranges::end(__parent->_M_base)) 3667 { } 3668 3669 friend constexpr bool 3670 operator==(const _Iterator& __x, const _Sentinel& __y) 3671 { return __y._M_equal(__x); } 3672 }; 3673 }; 3674 3675 template<typename _Range, typename _Pattern> 3676 split_view(_Range&&, _Pattern&&) 3677 -> split_view<views::all_t<_Range>, views::all_t<_Pattern>>; 3678 3679 template<forward_range _Range> 3680 split_view(_Range&&, range_value_t<_Range>) 3681 -> split_view<views::all_t<_Range>, single_view<range_value_t<_Range>>>; 3682 3683 namespace views 3684 { 3685 namespace __detail 3686 { 3687 template<typename _Range, typename _Pattern> 3688 concept __can_split_view 3689 = requires { split_view(std::declval<_Range>(), std::declval<_Pattern>()); }; 3690 } // namespace __detail 3691 3692 struct _Split : __adaptor::_RangeAdaptor<_Split> 3693 { 3694 template<viewable_range _Range, typename _Pattern> 3695 requires __detail::__can_split_view<_Range, _Pattern> 3696 constexpr auto 3697 operator() [[nodiscard]] (_Range&& __r, _Pattern&& __f) const 3698 { 3699 return split_view(std::forward<_Range>(__r), std::forward<_Pattern>(__f)); 3700 } 3701 3702 using _RangeAdaptor<_Split>::operator(); 3703 static constexpr int _S_arity = 2; 3704 template<typename _Pattern> 3705 static constexpr bool _S_has_simple_extra_args 3706 = _LazySplit::_S_has_simple_extra_args<_Pattern>; 3707 }; 3708 3709 inline constexpr _Split split; 3710 } // namespace views 3711 3712 namespace views 3713 { 3714 struct _Counted 3715 { 3716 template<input_or_output_iterator _Iter> 3717 constexpr auto 3718 operator() [[nodiscard]] (_Iter __i, iter_difference_t<_Iter> __n) const 3719 { 3720 if constexpr (contiguous_iterator<_Iter>) 3721 return span(std::__to_address(__i), __n); 3722 else if constexpr (random_access_iterator<_Iter>) 3723 return subrange(__i, __i + __n); 3724 else 3725 return subrange(counted_iterator(std::move(__i), __n), 3726 default_sentinel); 3727 } 3728 }; 3729 3730 inline constexpr _Counted counted{}; 3731 } // namespace views 3732 3733 template<view _Vp> 3734 requires (!common_range<_Vp>) && copyable<iterator_t<_Vp>> 3735 class common_view : public view_interface<common_view<_Vp>> 3736 { 3737 private: 3738 _Vp _M_base = _Vp(); 3739 3740 public: 3741 common_view() requires default_initializable<_Vp> = default; 3742 3743 constexpr explicit 3744 common_view(_Vp __r) 3745 : _M_base(std::move(__r)) 3746 { } 3747 3748 /* XXX: LWG 3280 didn't remove this constructor, but I think it should? 3749 template<viewable_range _Range> 3750 requires (!common_range<_Range>) 3751 && constructible_from<_Vp, views::all_t<_Range>> 3752 constexpr explicit 3753 common_view(_Range&& __r) 3754 : _M_base(views::all(std::forward<_Range>(__r))) 3755 { } 3756 */ 3757 3758 constexpr _Vp 3759 base() const& requires copy_constructible<_Vp> 3760 { return _M_base; } 3761 3762 constexpr _Vp 3763 base() && 3764 { return std::move(_M_base); } 3765 3766 constexpr auto 3767 begin() 3768 { 3769 if constexpr (random_access_range<_Vp> && sized_range<_Vp>) 3770 return ranges::begin(_M_base); 3771 else 3772 return common_iterator<iterator_t<_Vp>, sentinel_t<_Vp>> 3773 (ranges::begin(_M_base)); 3774 } 3775 3776 constexpr auto 3777 begin() const requires range<const _Vp> 3778 { 3779 if constexpr (random_access_range<const _Vp> && sized_range<const _Vp>) 3780 return ranges::begin(_M_base); 3781 else 3782 return common_iterator<iterator_t<const _Vp>, sentinel_t<const _Vp>> 3783 (ranges::begin(_M_base)); 3784 } 3785 3786 constexpr auto 3787 end() 3788 { 3789 if constexpr (random_access_range<_Vp> && sized_range<_Vp>) 3790 return ranges::begin(_M_base) + ranges::size(_M_base); 3791 else 3792 return common_iterator<iterator_t<_Vp>, sentinel_t<_Vp>> 3793 (ranges::end(_M_base)); 3794 } 3795 3796 constexpr auto 3797 end() const requires range<const _Vp> 3798 { 3799 if constexpr (random_access_range<const _Vp> && sized_range<const _Vp>) 3800 return ranges::begin(_M_base) + ranges::size(_M_base); 3801 else 3802 return common_iterator<iterator_t<const _Vp>, sentinel_t<const _Vp>> 3803 (ranges::end(_M_base)); 3804 } 3805 3806 constexpr auto 3807 size() requires sized_range<_Vp> 3808 { return ranges::size(_M_base); } 3809 3810 constexpr auto 3811 size() const requires sized_range<const _Vp> 3812 { return ranges::size(_M_base); } 3813 }; 3814 3815 template<typename _Range> 3816 common_view(_Range&&) -> common_view<views::all_t<_Range>>; 3817 3818 template<typename _Tp> 3819 inline constexpr bool enable_borrowed_range<common_view<_Tp>> 3820 = enable_borrowed_range<_Tp>; 3821 3822 namespace views 3823 { 3824 namespace __detail 3825 { 3826 template<typename _Range> 3827 concept __already_common = common_range<_Range> 3828 && requires { views::all(std::declval<_Range>()); }; 3829 3830 template<typename _Range> 3831 concept __can_common_view 3832 = requires { common_view{std::declval<_Range>()}; }; 3833 } // namespace __detail 3834 3835 struct _Common : __adaptor::_RangeAdaptorClosure 3836 { 3837 template<viewable_range _Range> 3838 requires __detail::__already_common<_Range> 3839 || __detail::__can_common_view<_Range> 3840 constexpr auto 3841 operator() [[nodiscard]] (_Range&& __r) const 3842 { 3843 if constexpr (__detail::__already_common<_Range>) 3844 return views::all(std::forward<_Range>(__r)); 3845 else 3846 return common_view{std::forward<_Range>(__r)}; 3847 } 3848 3849 static constexpr bool _S_has_simple_call_op = true; 3850 }; 3851 3852 inline constexpr _Common common; 3853 } // namespace views 3854 3855 template<view _Vp> 3856 requires bidirectional_range<_Vp> 3857 class reverse_view : public view_interface<reverse_view<_Vp>> 3858 { 3859 private: 3860 static constexpr bool _S_needs_cached_begin 3861 = !common_range<_Vp> && !(random_access_range<_Vp> 3862 && sized_sentinel_for<sentinel_t<_Vp>, 3863 iterator_t<_Vp>>); 3864 3865 _Vp _M_base = _Vp(); 3866 [[no_unique_address]] 3867 __detail::__maybe_present_t<_S_needs_cached_begin, 3868 __detail::_CachedPosition<_Vp>> 3869 _M_cached_begin; 3870 3871 public: 3872 reverse_view() requires default_initializable<_Vp> = default; 3873 3874 constexpr explicit 3875 reverse_view(_Vp __r) 3876 : _M_base(std::move(__r)) 3877 { } 3878 3879 constexpr _Vp 3880 base() const& requires copy_constructible<_Vp> 3881 { return _M_base; } 3882 3883 constexpr _Vp 3884 base() && 3885 { return std::move(_M_base); } 3886 3887 constexpr reverse_iterator<iterator_t<_Vp>> 3888 begin() 3889 { 3890 if constexpr (_S_needs_cached_begin) 3891 if (_M_cached_begin._M_has_value()) 3892 return std::make_reverse_iterator(_M_cached_begin._M_get(_M_base)); 3893 3894 auto __it = ranges::next(ranges::begin(_M_base), ranges::end(_M_base)); 3895 if constexpr (_S_needs_cached_begin) 3896 _M_cached_begin._M_set(_M_base, __it); 3897 return std::make_reverse_iterator(std::move(__it)); 3898 } 3899 3900 constexpr auto 3901 begin() requires common_range<_Vp> 3902 { return std::make_reverse_iterator(ranges::end(_M_base)); } 3903 3904 constexpr auto 3905 begin() const requires common_range<const _Vp> 3906 { return std::make_reverse_iterator(ranges::end(_M_base)); } 3907 3908 constexpr reverse_iterator<iterator_t<_Vp>> 3909 end() 3910 { return std::make_reverse_iterator(ranges::begin(_M_base)); } 3911 3912 constexpr auto 3913 end() const requires common_range<const _Vp> 3914 { return std::make_reverse_iterator(ranges::begin(_M_base)); } 3915 3916 constexpr auto 3917 size() requires sized_range<_Vp> 3918 { return ranges::size(_M_base); } 3919 3920 constexpr auto 3921 size() const requires sized_range<const _Vp> 3922 { return ranges::size(_M_base); } 3923 }; 3924 3925 template<typename _Range> 3926 reverse_view(_Range&&) -> reverse_view<views::all_t<_Range>>; 3927 3928 template<typename _Tp> 3929 inline constexpr bool enable_borrowed_range<reverse_view<_Tp>> 3930 = enable_borrowed_range<_Tp>; 3931 3932 namespace views 3933 { 3934 namespace __detail 3935 { 3936 template<typename> 3937 inline constexpr bool __is_reversible_subrange = false; 3938 3939 template<typename _Iter, subrange_kind _Kind> 3940 inline constexpr bool 3941 __is_reversible_subrange<subrange<reverse_iterator<_Iter>, 3942 reverse_iterator<_Iter>, 3943 _Kind>> = true; 3944 3945 template<typename> 3946 inline constexpr bool __is_reverse_view = false; 3947 3948 template<typename _Vp> 3949 inline constexpr bool __is_reverse_view<reverse_view<_Vp>> = true; 3950 3951 template<typename _Range> 3952 concept __can_reverse_view 3953 = requires { reverse_view{std::declval<_Range>()}; }; 3954 } // namespace __detail 3955 3956 struct _Reverse : __adaptor::_RangeAdaptorClosure 3957 { 3958 template<viewable_range _Range> 3959 requires __detail::__is_reverse_view<remove_cvref_t<_Range>> 3960 || __detail::__is_reversible_subrange<remove_cvref_t<_Range>> 3961 || __detail::__can_reverse_view<_Range> 3962 constexpr auto 3963 operator() [[nodiscard]] (_Range&& __r) const 3964 { 3965 using _Tp = remove_cvref_t<_Range>; 3966 if constexpr (__detail::__is_reverse_view<_Tp>) 3967 return std::forward<_Range>(__r).base(); 3968 else if constexpr (__detail::__is_reversible_subrange<_Tp>) 3969 { 3970 using _Iter = decltype(ranges::begin(__r).base()); 3971 if constexpr (sized_range<_Tp>) 3972 return subrange<_Iter, _Iter, subrange_kind::sized> 3973 {__r.end().base(), __r.begin().base(), __r.size()}; 3974 else 3975 return subrange<_Iter, _Iter, subrange_kind::unsized> 3976 {__r.end().base(), __r.begin().base()}; 3977 } 3978 else 3979 return reverse_view{std::forward<_Range>(__r)}; 3980 } 3981 3982 static constexpr bool _S_has_simple_call_op = true; 3983 }; 3984 3985 inline constexpr _Reverse reverse; 3986 } // namespace views 3987 3988 namespace __detail 3989 { 3990 template<typename _Tp, size_t _Nm> 3991 concept __has_tuple_element = requires(_Tp __t) 3992 { 3993 typename tuple_size<_Tp>::type; 3994 requires _Nm < tuple_size_v<_Tp>; 3995 typename tuple_element_t<_Nm, _Tp>; 3996 { std::get<_Nm>(__t) } 3997 -> convertible_to<const tuple_element_t<_Nm, _Tp>&>; 3998 }; 3999 4000 template<typename _Tp, size_t _Nm> 4001 concept __returnable_element 4002 = is_reference_v<_Tp> || move_constructible<tuple_element_t<_Nm, _Tp>>; 4003 } 4004 4005 template<input_range _Vp, size_t _Nm> 4006 requires view<_Vp> 4007 && __detail::__has_tuple_element<range_value_t<_Vp>, _Nm> 4008 && __detail::__has_tuple_element<remove_reference_t<range_reference_t<_Vp>>, 4009 _Nm> 4010 && __detail::__returnable_element<range_reference_t<_Vp>, _Nm> 4011 class elements_view : public view_interface<elements_view<_Vp, _Nm>> 4012 { 4013 public: 4014 elements_view() requires default_initializable<_Vp> = default; 4015 4016 constexpr explicit 4017 elements_view(_Vp base) 4018 : _M_base(std::move(base)) 4019 { } 4020 4021 constexpr _Vp 4022 base() const& requires copy_constructible<_Vp> 4023 { return _M_base; } 4024 4025 constexpr _Vp 4026 base() && 4027 { return std::move(_M_base); } 4028 4029 constexpr auto 4030 begin() requires (!__detail::__simple_view<_Vp>) 4031 { return _Iterator<false>(ranges::begin(_M_base)); } 4032 4033 constexpr auto 4034 begin() const requires range<const _Vp> 4035 { return _Iterator<true>(ranges::begin(_M_base)); } 4036 4037 constexpr auto 4038 end() requires (!__detail::__simple_view<_Vp> && !common_range<_Vp>) 4039 { return _Sentinel<false>{ranges::end(_M_base)}; } 4040 4041 constexpr auto 4042 end() requires (!__detail::__simple_view<_Vp> && common_range<_Vp>) 4043 { return _Iterator<false>{ranges::end(_M_base)}; } 4044 4045 constexpr auto 4046 end() const requires range<const _Vp> 4047 { return _Sentinel<true>{ranges::end(_M_base)}; } 4048 4049 constexpr auto 4050 end() const requires common_range<const _Vp> 4051 { return _Iterator<true>{ranges::end(_M_base)}; } 4052 4053 constexpr auto 4054 size() requires sized_range<_Vp> 4055 { return ranges::size(_M_base); } 4056 4057 constexpr auto 4058 size() const requires sized_range<const _Vp> 4059 { return ranges::size(_M_base); } 4060 4061 private: 4062 template<bool _Const> 4063 using _Base = __detail::__maybe_const_t<_Const, _Vp>; 4064 4065 template<bool _Const> 4066 struct __iter_cat 4067 { }; 4068 4069 template<bool _Const> 4070 requires forward_range<_Base<_Const>> 4071 struct __iter_cat<_Const> 4072 { 4073 private: 4074 static auto _S_iter_cat() 4075 { 4076 using _Base = elements_view::_Base<_Const>; 4077 using _Cat = typename iterator_traits<iterator_t<_Base>>::iterator_category; 4078 using _Res = decltype((std::get<_Nm>(*std::declval<iterator_t<_Base>>()))); 4079 if constexpr (!is_lvalue_reference_v<_Res>) 4080 return input_iterator_tag{}; 4081 else if constexpr (derived_from<_Cat, random_access_iterator_tag>) 4082 return random_access_iterator_tag{}; 4083 else 4084 return _Cat{}; 4085 } 4086 public: 4087 using iterator_category = decltype(_S_iter_cat()); 4088 }; 4089 4090 template<bool _Const> 4091 struct _Sentinel; 4092 4093 template<bool _Const> 4094 struct _Iterator : __iter_cat<_Const> 4095 { 4096 private: 4097 using _Base = elements_view::_Base<_Const>; 4098 4099 iterator_t<_Base> _M_current = iterator_t<_Base>(); 4100 4101 static constexpr decltype(auto) 4102 _S_get_element(const iterator_t<_Base>& __i) 4103 { 4104 if constexpr (is_reference_v<range_reference_t<_Base>>) 4105 return std::get<_Nm>(*__i); 4106 else 4107 { 4108 using _Et = remove_cv_t<tuple_element_t<_Nm, range_reference_t<_Base>>>; 4109 return static_cast<_Et>(std::get<_Nm>(*__i)); 4110 } 4111 } 4112 4113 static auto 4114 _S_iter_concept() 4115 { 4116 if constexpr (random_access_range<_Base>) 4117 return random_access_iterator_tag{}; 4118 else if constexpr (bidirectional_range<_Base>) 4119 return bidirectional_iterator_tag{}; 4120 else if constexpr (forward_range<_Base>) 4121 return forward_iterator_tag{}; 4122 else 4123 return input_iterator_tag{}; 4124 } 4125 4126 friend _Iterator<!_Const>; 4127 4128 public: 4129 using iterator_concept = decltype(_S_iter_concept()); 4130 // iterator_category defined in elements_view::__iter_cat 4131 using value_type 4132 = remove_cvref_t<tuple_element_t<_Nm, range_value_t<_Base>>>; 4133 using difference_type = range_difference_t<_Base>; 4134 4135 _Iterator() requires default_initializable<iterator_t<_Base>> = default; 4136 4137 constexpr explicit 4138 _Iterator(iterator_t<_Base> current) 4139 : _M_current(std::move(current)) 4140 { } 4141 4142 constexpr 4143 _Iterator(_Iterator<!_Const> i) 4144 requires _Const && convertible_to<iterator_t<_Vp>, iterator_t<_Base>> 4145 : _M_current(std::move(i._M_current)) 4146 { } 4147 4148 constexpr const iterator_t<_Base>& 4149 base() const& noexcept 4150 { return _M_current; } 4151 4152 constexpr iterator_t<_Base> 4153 base() && 4154 { return std::move(_M_current); } 4155 4156 constexpr decltype(auto) 4157 operator*() const 4158 { return _S_get_element(_M_current); } 4159 4160 constexpr _Iterator& 4161 operator++() 4162 { 4163 ++_M_current; 4164 return *this; 4165 } 4166 4167 constexpr void 4168 operator++(int) 4169 { ++_M_current; } 4170 4171 constexpr _Iterator 4172 operator++(int) requires forward_range<_Base> 4173 { 4174 auto __tmp = *this; 4175 ++_M_current; 4176 return __tmp; 4177 } 4178 4179 constexpr _Iterator& 4180 operator--() requires bidirectional_range<_Base> 4181 { 4182 --_M_current; 4183 return *this; 4184 } 4185 4186 constexpr _Iterator 4187 operator--(int) requires bidirectional_range<_Base> 4188 { 4189 auto __tmp = *this; 4190 --_M_current; 4191 return __tmp; 4192 } 4193 4194 constexpr _Iterator& 4195 operator+=(difference_type __n) 4196 requires random_access_range<_Base> 4197 { 4198 _M_current += __n; 4199 return *this; 4200 } 4201 4202 constexpr _Iterator& 4203 operator-=(difference_type __n) 4204 requires random_access_range<_Base> 4205 { 4206 _M_current -= __n; 4207 return *this; 4208 } 4209 4210 constexpr decltype(auto) 4211 operator[](difference_type __n) const 4212 requires random_access_range<_Base> 4213 { return _S_get_element(_M_current + __n); } 4214 4215 friend constexpr bool 4216 operator==(const _Iterator& __x, const _Iterator& __y) 4217 requires equality_comparable<iterator_t<_Base>> 4218 { return __x._M_current == __y._M_current; } 4219 4220 friend constexpr bool 4221 operator<(const _Iterator& __x, const _Iterator& __y) 4222 requires random_access_range<_Base> 4223 { return __x._M_current < __y._M_current; } 4224 4225 friend constexpr bool 4226 operator>(const _Iterator& __x, const _Iterator& __y) 4227 requires random_access_range<_Base> 4228 { return __y._M_current < __x._M_current; } 4229 4230 friend constexpr bool 4231 operator<=(const _Iterator& __x, const _Iterator& __y) 4232 requires random_access_range<_Base> 4233 { return !(__y._M_current > __x._M_current); } 4234 4235 friend constexpr bool 4236 operator>=(const _Iterator& __x, const _Iterator& __y) 4237 requires random_access_range<_Base> 4238 { return !(__x._M_current > __y._M_current); } 4239 4240#ifdef __cpp_lib_three_way_comparison 4241 friend constexpr auto 4242 operator<=>(const _Iterator& __x, const _Iterator& __y) 4243 requires random_access_range<_Base> 4244 && three_way_comparable<iterator_t<_Base>> 4245 { return __x._M_current <=> __y._M_current; } 4246#endif 4247 4248 friend constexpr _Iterator 4249 operator+(const _Iterator& __x, difference_type __y) 4250 requires random_access_range<_Base> 4251 { return _Iterator{__x} += __y; } 4252 4253 friend constexpr _Iterator 4254 operator+(difference_type __x, const _Iterator& __y) 4255 requires random_access_range<_Base> 4256 { return __y + __x; } 4257 4258 friend constexpr _Iterator 4259 operator-(const _Iterator& __x, difference_type __y) 4260 requires random_access_range<_Base> 4261 { return _Iterator{__x} -= __y; } 4262 4263 // _GLIBCXX_RESOLVE_LIB_DEFECTS 4264 // 3483. transform_view::iterator's difference is overconstrained 4265 friend constexpr difference_type 4266 operator-(const _Iterator& __x, const _Iterator& __y) 4267 requires sized_sentinel_for<iterator_t<_Base>, iterator_t<_Base>> 4268 { return __x._M_current - __y._M_current; } 4269 4270 template <bool> friend struct _Sentinel; 4271 }; 4272 4273 template<bool _Const> 4274 struct _Sentinel 4275 { 4276 private: 4277 template<bool _Const2> 4278 constexpr bool 4279 _M_equal(const _Iterator<_Const2>& __x) const 4280 { return __x._M_current == _M_end; } 4281 4282 template<bool _Const2> 4283 constexpr auto 4284 _M_distance_from(const _Iterator<_Const2>& __i) const 4285 { return _M_end - __i._M_current; } 4286 4287 using _Base = elements_view::_Base<_Const>; 4288 sentinel_t<_Base> _M_end = sentinel_t<_Base>(); 4289 4290 public: 4291 _Sentinel() = default; 4292 4293 constexpr explicit 4294 _Sentinel(sentinel_t<_Base> __end) 4295 : _M_end(std::move(__end)) 4296 { } 4297 4298 constexpr 4299 _Sentinel(_Sentinel<!_Const> __other) 4300 requires _Const 4301 && convertible_to<sentinel_t<_Vp>, sentinel_t<_Base>> 4302 : _M_end(std::move(__other._M_end)) 4303 { } 4304 4305 constexpr sentinel_t<_Base> 4306 base() const 4307 { return _M_end; } 4308 4309 template<bool _Const2> 4310 requires sentinel_for<sentinel_t<_Base>, 4311 iterator_t<__detail::__maybe_const_t<_Const2, _Vp>>> 4312 friend constexpr bool 4313 operator==(const _Iterator<_Const2>& __x, const _Sentinel& __y) 4314 { return __y._M_equal(__x); } 4315 4316 template<bool _Const2, 4317 typename _Base2 = __detail::__maybe_const_t<_Const2, _Vp>> 4318 requires sized_sentinel_for<sentinel_t<_Base>, iterator_t<_Base2>> 4319 friend constexpr range_difference_t<_Base2> 4320 operator-(const _Iterator<_Const2>& __x, const _Sentinel& __y) 4321 { return -__y._M_distance_from(__x); } 4322 4323 template<bool _Const2, 4324 typename _Base2 = __detail::__maybe_const_t<_Const2, _Vp>> 4325 requires sized_sentinel_for<sentinel_t<_Base>, iterator_t<_Base2>> 4326 friend constexpr range_difference_t<_Base2> 4327 operator-(const _Sentinel& __x, const _Iterator<_Const2>& __y) 4328 { return __x._M_distance_from(__y); } 4329 4330 friend _Sentinel<!_Const>; 4331 }; 4332 4333 _Vp _M_base = _Vp(); 4334 }; 4335 4336 template<typename _Tp, size_t _Nm> 4337 inline constexpr bool enable_borrowed_range<elements_view<_Tp, _Nm>> 4338 = enable_borrowed_range<_Tp>; 4339 4340 template<typename _Range> 4341 using keys_view = elements_view<views::all_t<_Range>, 0>; 4342 4343 template<typename _Range> 4344 using values_view = elements_view<views::all_t<_Range>, 1>; 4345 4346 namespace views 4347 { 4348 namespace __detail 4349 { 4350 template<size_t _Nm, typename _Range> 4351 concept __can_elements_view 4352 = requires { elements_view<all_t<_Range>, _Nm>{std::declval<_Range>()}; }; 4353 } // namespace __detail 4354 4355 template<size_t _Nm> 4356 struct _Elements : __adaptor::_RangeAdaptorClosure 4357 { 4358 template<viewable_range _Range> 4359 requires __detail::__can_elements_view<_Nm, _Range> 4360 constexpr auto 4361 operator() [[nodiscard]] (_Range&& __r) const 4362 { 4363 return elements_view<all_t<_Range>, _Nm>{std::forward<_Range>(__r)}; 4364 } 4365 4366 static constexpr bool _S_has_simple_call_op = true; 4367 }; 4368 4369 template<size_t _Nm> 4370 inline constexpr _Elements<_Nm> elements; 4371 inline constexpr auto keys = elements<0>; 4372 inline constexpr auto values = elements<1>; 4373 } // namespace views 4374 4375} // namespace ranges 4376 4377 namespace views = ranges::views; 4378 4379_GLIBCXX_END_NAMESPACE_VERSION 4380} // namespace 4381#endif // library concepts 4382#endif // C++2a 4383#endif /* _GLIBCXX_RANGES */ 4384