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