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