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