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