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