Where Online Learning is simpler!
The C and C++ Include Header Files
/usr/include/c++/13/bits/ranges_util.h
$ cat -n /usr/include/c++/13/bits/ranges_util.h 1 // Utilities for representing and manipulating ranges -*- C++ -*- 2 3 // Copyright (C) 2019-2023 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 bits/ranges_util.h 26 * This is an internal header file, included by other library headers. 27 * Do not attempt to use it directly. @headername{ranges} 28 */ 29 30 #ifndef _RANGES_UTIL_H 31 #define _RANGES_UTIL_H 1 32 33 #if __cplusplus > 201703L 34 # include <bits/ranges_base.h> 35 # include <bits/utility.h> 36 37 #ifdef __cpp_lib_ranges 38 namespace std _GLIBCXX_VISIBILITY(default) 39 { 40 _GLIBCXX_BEGIN_NAMESPACE_VERSION 41 namespace ranges 42 { 43 // C++20 24.5 [range.utility] Range utilities 44 45 namespace __detail 46 { 47 template<typename _Range> 48 concept __simple_view = view<_Range> && range<const _Range> 49 && same_as<iterator_t<_Range>, iterator_t<const _Range>> 50 && same_as<sentinel_t<_Range>, sentinel_t<const _Range>>; 51 52 template<typename _It> 53 concept __has_arrow = input_iterator<_It> 54 && (is_pointer_v<_It> || requires(_It __it) { __it.operator->(); }); 55 56 using std::__detail::__different_from; 57 } // namespace __detail 58 59 /// The ranges::view_interface class template 60 template<typename _Derived> 61 requires is_class_v<_Derived> && same_as<_Derived, remove_cv_t<_Derived>> 62 class view_interface 63 { 64 private: 65 constexpr _Derived& _M_derived() noexcept 66 { 67 static_assert(derived_from<_Derived, view_interface<_Derived>>); 68 static_assert(view<_Derived>); 69 return static_cast<_Derived&>(*this); 70 } 71 72 constexpr const _Derived& _M_derived() const noexcept 73 { 74 static_assert(derived_from<_Derived, view_interface<_Derived>>); 75 static_assert(view<_Derived>); 76 return static_cast<const _Derived&>(*this); 77 } 78 79 static constexpr bool 80 _S_bool(bool) noexcept; // not defined 81 82 template<typename _Tp> 83 static constexpr bool 84 _S_empty(_Tp& __t) 85 noexcept(noexcept(_S_bool(ranges::begin(__t) == ranges::end(__t)))) 86 { return ranges::begin(__t) == ranges::end(__t); } 87 88 template<typename _Tp> 89 static constexpr auto 90 _S_size(_Tp& __t) 91 noexcept(noexcept(ranges::end(__t) - ranges::begin(__t))) 92 { return ranges::end(__t) - ranges::begin(__t); } 93 94 public: 95 constexpr bool 96 empty() 97 noexcept(noexcept(_S_empty(_M_derived()))) 98 requires forward_range<_Derived> && (!sized_range<_Derived>) 99 { return _S_empty(_M_derived()); } 100 101 constexpr bool 102 empty() 103 noexcept(noexcept(ranges::size(_M_derived()) == 0)) 104 requires sized_range<_Derived> 105 { return ranges::size(_M_derived()) == 0; } 106 107 constexpr bool 108 empty() const 109 noexcept(noexcept(_S_empty(_M_derived()))) 110 requires forward_range<const _Derived> && (!sized_range<const _Derived>) 111 { return _S_empty(_M_derived()); } 112 113 constexpr bool 114 empty() const 115 noexcept(noexcept(ranges::size(_M_derived()) == 0)) 116 requires sized_range<const _Derived> 117 { return ranges::size(_M_derived()) == 0; } 118 119 constexpr explicit 120 operator bool() noexcept(noexcept(ranges::empty(_M_derived()))) 121 requires requires { ranges::empty(_M_derived()); } 122 { return !ranges::empty(_M_derived()); } 123 124 constexpr explicit 125 operator bool() const noexcept(noexcept(ranges::empty(_M_derived()))) 126 requires requires { ranges::empty(_M_derived()); } 127 { return !ranges::empty(_M_derived()); } 128 129 constexpr auto 130 data() noexcept(noexcept(ranges::begin(_M_derived()))) 131 requires contiguous_iterator<iterator_t<_Derived>> 132 { return std::to_address(ranges::begin(_M_derived())); } 133 134 constexpr auto 135 data() const noexcept(noexcept(ranges::begin(_M_derived()))) 136 requires range<const _Derived> 137 && contiguous_iterator<iterator_t<const _Derived>> 138 { return std::to_address(ranges::begin(_M_derived())); } 139 140 constexpr auto 141 size() noexcept(noexcept(_S_size(_M_derived()))) 142 requires forward_range<_Derived> 143 && sized_sentinel_for<sentinel_t<_Derived>, iterator_t<_Derived>> 144 { return _S_size(_M_derived()); } 145 146 constexpr auto 147 size() const noexcept(noexcept(_S_size(_M_derived()))) 148 requires forward_range<const _Derived> 149 && sized_sentinel_for<sentinel_t<const _Derived>, 150 iterator_t<const _Derived>> 151 { return _S_size(_M_derived()); } 152 153 constexpr decltype(auto) 154 front() requires forward_range<_Derived> 155 { 156 __glibcxx_assert(!empty()); 157 return *ranges::begin(_M_derived()); 158 } 159 160 constexpr decltype(auto) 161 front() const requires forward_range<const _Derived> 162 { 163 __glibcxx_assert(!empty()); 164 return *ranges::begin(_M_derived()); 165 } 166 167 constexpr decltype(auto) 168 back() 169 requires bidirectional_range<_Derived> && common_range<_Derived> 170 { 171 __glibcxx_assert(!empty()); 172 return *ranges::prev(ranges::end(_M_derived())); 173 } 174 175 constexpr decltype(auto) 176 back() const 177 requires bidirectional_range<const _Derived> 178 && common_range<const _Derived> 179 { 180 __glibcxx_assert(!empty()); 181 return *ranges::prev(ranges::end(_M_derived())); 182 } 183 184 template<random_access_range _Range = _Derived> 185 constexpr decltype(auto) 186 operator[](range_difference_t<_Range> __n) 187 { return ranges::begin(_M_derived())[__n]; } 188 189 template<random_access_range _Range = const _Derived> 190 constexpr decltype(auto) 191 operator[](range_difference_t<_Range> __n) const 192 { return ranges::begin(_M_derived())[__n]; } 193 194 #if __cplusplus > 202002L 195 constexpr auto 196 cbegin() requires input_range<_Derived> 197 { return ranges::cbegin(_M_derived()); } 198 199 constexpr auto 200 cbegin() const requires input_range<const _Derived> 201 { return ranges::cbegin(_M_derived()); } 202 203 constexpr auto 204 cend() requires input_range<_Derived> 205 { return ranges::cend(_M_derived()); } 206 207 constexpr auto 208 cend() const requires input_range<const _Derived> 209 { return ranges::cend(_M_derived()); } 210 #endif 211 }; 212 213 namespace __detail 214 { 215 template<typename _From, typename _To> 216 concept __uses_nonqualification_pointer_conversion 217 = is_pointer_v<_From> && is_pointer_v<_To> 218 && !convertible_to<remove_pointer_t<_From>(*)[], 219 remove_pointer_t<_To>(*)[]>; 220 221 template<typename _From, typename _To> 222 concept __convertible_to_non_slicing = convertible_to<_From, _To> 223 && !__uses_nonqualification_pointer_conversion<decay_t<_From>, 224 decay_t<_To>>; 225 226 template<typename _Tp> 227 concept __pair_like 228 = !is_reference_v<_Tp> && requires(_Tp __t) 229 { 230 typename tuple_size<_Tp>::type; 231 requires derived_from<tuple_size<_Tp>, integral_constant<size_t, 2>>; 232 typename tuple_element_t<0, remove_const_t<_Tp>>; 233 typename tuple_element_t<1, remove_const_t<_Tp>>; 234 { get<0>(__t) } -> convertible_to<const tuple_element_t<0, _Tp>&>; 235 { get<1>(__t) } -> convertible_to<const tuple_element_t<1, _Tp>&>; 236 }; 237 238 template<typename _Tp, typename _Up, typename _Vp> 239 concept __pair_like_convertible_from 240 = !range<_Tp> && __pair_like<_Tp> 241 && constructible_from<_Tp, _Up, _Vp> 242 && __convertible_to_non_slicing<_Up, tuple_element_t<0, _Tp>> 243 && convertible_to<_Vp, tuple_element_t<1, _Tp>>; 244 245 } // namespace __detail 246 247 namespace views { struct _Drop; } // defined in <ranges> 248 249 enum class subrange_kind : bool { unsized, sized }; 250 251 /// The ranges::subrange class template 252 template<input_or_output_iterator _It, sentinel_for<_It> _Sent = _It, 253 subrange_kind _Kind = sized_sentinel_for<_Sent, _It> 254 ? subrange_kind::sized : subrange_kind::unsized> 255 requires (_Kind == subrange_kind::sized || !sized_sentinel_for<_Sent, _It>) 256 class subrange : public view_interface<subrange<_It, _Sent, _Kind>> 257 { 258 private: 259 static constexpr bool _S_store_size 260 = _Kind == subrange_kind::sized && !sized_sentinel_for<_Sent, _It>; 261 262 friend struct views::_Drop; // Needs to inspect _S_store_size. 263 264 _It _M_begin = _It(); 265 [[no_unique_address]] _Sent _M_end = _Sent(); 266 267 using __size_type 268 = __detail::__make_unsigned_like_t<iter_difference_t<_It>>; 269 270 template<typename _Tp, bool = _S_store_size> 271 struct _Size 272 { 273 [[__gnu__::__always_inline__]] 274 constexpr _Size(_Tp = {}) { } 275 }; 276 277 template<typename _Tp> 278 struct _Size<_Tp, true> 279 { 280 [[__gnu__::__always_inline__]] 281 constexpr _Size(_Tp __s = {}) : _M_size(__s) { } 282 283 _Tp _M_size; 284 }; 285 286 [[no_unique_address]] _Size<__size_type> _M_size = {}; 287 288 public: 289 subrange() requires default_initializable<_It> = default; 290 291 constexpr 292 subrange(__detail::__convertible_to_non_slicing<_It> auto __i, _Sent __s) 293 noexcept(is_nothrow_constructible_v<_It, decltype(__i)> 294 && is_nothrow_constructible_v<_Sent, _Sent&>) 295 requires (!_S_store_size) 296 : _M_begin(std::move(__i)), _M_end(__s) 297 { } 298 299 constexpr 300 subrange(__detail::__convertible_to_non_slicing<_It> auto __i, _Sent __s, 301 __size_type __n) 302 noexcept(is_nothrow_constructible_v<_It, decltype(__i)> 303 && is_nothrow_constructible_v<_Sent, _Sent&>) 304 requires (_Kind == subrange_kind::sized) 305 : _M_begin(std::move(__i)), _M_end(__s), _M_size(__n) 306 { } 307 308 template<__detail::__different_from<subrange> _Rng> 309 requires borrowed_range<_Rng> 310 && __detail::__convertible_to_non_slicing<iterator_t<_Rng>, _It> 311 && convertible_to<sentinel_t<_Rng>, _Sent> 312 constexpr 313 subrange(_Rng&& __r) 314 noexcept(noexcept(subrange(__r, ranges::size(__r)))) 315 requires _S_store_size && sized_range<_Rng> 316 : subrange(__r, ranges::size(__r)) 317 { } 318 319 template<__detail::__different_from<subrange> _Rng> 320 requires borrowed_range<_Rng> 321 && __detail::__convertible_to_non_slicing<iterator_t<_Rng>, _It> 322 && convertible_to<sentinel_t<_Rng>, _Sent> 323 constexpr 324 subrange(_Rng&& __r) 325 noexcept(noexcept(subrange(ranges::begin(__r), ranges::end(__r)))) 326 requires (!_S_store_size) 327 : subrange(ranges::begin(__r), ranges::end(__r)) 328 { } 329 330 template<borrowed_range _Rng> 331 requires __detail::__convertible_to_non_slicing<iterator_t<_Rng>, _It> 332 && convertible_to<sentinel_t<_Rng>, _Sent> 333 constexpr 334 subrange(_Rng&& __r, __size_type __n) 335 noexcept(noexcept(subrange(ranges::begin(__r), ranges::end(__r), __n))) 336 requires (_Kind == subrange_kind::sized) 337 : subrange{ranges::begin(__r), ranges::end(__r), __n} 338 { } 339 340 template<__detail::__different_from<subrange> _PairLike> 341 requires __detail::__pair_like_convertible_from<_PairLike, const _It&, 342 const _Sent&> 343 constexpr 344 operator _PairLike() const 345 { return _PairLike(_M_begin, _M_end); } 346 347 constexpr _It 348 begin() const requires copyable<_It> 349 { return _M_begin; } 350 351 [[nodiscard]] constexpr _It 352 begin() requires (!copyable<_It>) 353 { return std::move(_M_begin); } 354 355 constexpr _Sent end() const { return _M_end; } 356 357 constexpr bool empty() const { return _M_begin == _M_end; } 358 359 constexpr __size_type 360 size() const requires (_Kind == subrange_kind::sized) 361 { 362 if constexpr (_S_store_size) 363 return _M_size._M_size; 364 else 365 return __detail::__to_unsigned_like(_M_end - _M_begin); 366 } 367 368 [[nodiscard]] constexpr subrange 369 next(iter_difference_t<_It> __n = 1) const & 370 requires forward_iterator<_It> 371 { 372 auto __tmp = *this; 373 __tmp.advance(__n); 374 return __tmp; 375 } 376 377 [[nodiscard]] constexpr subrange 378 next(iter_difference_t<_It> __n = 1) && 379 { 380 advance(__n); 381 return std::move(*this); 382 } 383 384 [[nodiscard]] constexpr subrange 385 prev(iter_difference_t<_It> __n = 1) const 386 requires bidirectional_iterator<_It> 387 { 388 auto __tmp = *this; 389 __tmp.advance(-__n); 390 return __tmp; 391 } 392 393 constexpr subrange& 394 advance(iter_difference_t<_It> __n) 395 { 396 // _GLIBCXX_RESOLVE_LIB_DEFECTS 397 // 3433. subrange::advance(n) has UB when n < 0 398 if constexpr (bidirectional_iterator<_It>) 399 if (__n < 0) 400 { 401 ranges::advance(_M_begin, __n); 402 if constexpr (_S_store_size) 403 _M_size._M_size += __detail::__to_unsigned_like(-__n); 404 return *this; 405 } 406 407 __glibcxx_assert(__n >= 0); 408 auto __d = __n - ranges::advance(_M_begin, __n, _M_end); 409 if constexpr (_S_store_size) 410 _M_size._M_size -= __detail::__to_unsigned_like(__d); 411 return *this; 412 } 413 }; 414 415 template<input_or_output_iterator _It, sentinel_for<_It> _Sent> 416 subrange(_It, _Sent) -> subrange<_It, _Sent>; 417 418 template<input_or_output_iterator _It, sentinel_for<_It> _Sent> 419 subrange(_It, _Sent, 420 __detail::__make_unsigned_like_t<iter_difference_t<_It>>) 421 -> subrange<_It, _Sent, subrange_kind::sized>; 422 423 template<borrowed_range _Rng> 424 subrange(_Rng&&) 425 -> subrange<iterator_t<_Rng>, sentinel_t<_Rng>, 426 (sized_range<_Rng> 427 || sized_sentinel_for<sentinel_t<_Rng>, iterator_t<_Rng>>) 428 ? subrange_kind::sized : subrange_kind::unsized>; 429 430 template<borrowed_range _Rng> 431 subrange(_Rng&&, 432 __detail::__make_unsigned_like_t<range_difference_t<_Rng>>) 433 -> subrange<iterator_t<_Rng>, sentinel_t<_Rng>, subrange_kind::sized>; 434 435 template<size_t _Num, class _It, class _Sent, subrange_kind _Kind> 436 requires (_Num < 2) 437 constexpr auto 438 get(const subrange<_It, _Sent, _Kind>& __r) 439 { 440 if constexpr (_Num == 0) 441 return __r.begin(); 442 else 443 return __r.end(); 444 } 445 446 template<size_t _Num, class _It, class _Sent, subrange_kind _Kind> 447 requires (_Num < 2) 448 constexpr auto 449 get(subrange<_It, _Sent, _Kind>&& __r) 450 { 451 if constexpr (_Num == 0) 452 return __r.begin(); 453 else 454 return __r.end(); 455 } 456 457 template<typename _It, typename _Sent, subrange_kind _Kind> 458 inline constexpr bool 459 enable_borrowed_range<subrange<_It, _Sent, _Kind>> = true; 460 461 template<range _Range> 462 using borrowed_subrange_t = __conditional_t<borrowed_range<_Range>, 463 subrange<iterator_t<_Range>>, 464 dangling>; 465 } // namespace ranges 466 467 // The following ranges algorithms are used by <ranges>, and are defined here 468 // so that <ranges> can avoid including all of <bits/ranges_algo.h>. 469 namespace ranges 470 { 471 struct __find_fn 472 { 473 template<input_iterator _Iter, sentinel_for<_Iter> _Sent, typename _Tp, 474 typename _Proj = identity> 475 requires indirect_binary_predicate<ranges::equal_to, 476 projected<_Iter, _Proj>, const _Tp*> 477 constexpr _Iter 478 operator()(_Iter __first, _Sent __last, 479 const _Tp& __value, _Proj __proj = {}) const 480 { 481 while (__first != __last 482 && !(std::__invoke(__proj, *__first) == __value)) 483 ++__first; 484 return __first; 485 } 486 487 template<input_range _Range, typename _Tp, typename _Proj = identity> 488 requires indirect_binary_predicate<ranges::equal_to, 489 projected<iterator_t<_Range>, _Proj>, 490 const _Tp*> 491 constexpr borrowed_iterator_t<_Range> 492 operator()(_Range&& __r, const _Tp& __value, _Proj __proj = {}) const 493 { 494 return (*this)(ranges::begin(__r), ranges::end(__r), 495 __value, std::move(__proj)); 496 } 497 }; 498 499 inline constexpr __find_fn find{}; 500 501 struct __find_if_fn 502 { 503 template<input_iterator _Iter, sentinel_for<_Iter> _Sent, 504 typename _Proj = identity, 505 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred> 506 constexpr _Iter 507 operator()(_Iter __first, _Sent __last, 508 _Pred __pred, _Proj __proj = {}) const 509 { 510 while (__first != __last 511 && !(bool)std::__invoke(__pred, std::__invoke(__proj, *__first))) 512 ++__first; 513 return __first; 514 } 515 516 template<input_range _Range, typename _Proj = identity, 517 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> 518 _Pred> 519 constexpr borrowed_iterator_t<_Range> 520 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const 521 { 522 return (*this)(ranges::begin(__r), ranges::end(__r), 523 std::move(__pred), std::move(__proj)); 524 } 525 }; 526 527 inline constexpr __find_if_fn find_if{}; 528 529 struct __find_if_not_fn 530 { 531 template<input_iterator _Iter, sentinel_for<_Iter> _Sent, 532 typename _Proj = identity, 533 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred> 534 constexpr _Iter 535 operator()(_Iter __first, _Sent __last, 536 _Pred __pred, _Proj __proj = {}) const 537 { 538 while (__first != __last 539 && (bool)std::__invoke(__pred, std::__invoke(__proj, *__first))) 540 ++__first; 541 return __first; 542 } 543 544 template<input_range _Range, typename _Proj = identity, 545 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> 546 _Pred> 547 constexpr borrowed_iterator_t<_Range> 548 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const 549 { 550 return (*this)(ranges::begin(__r), ranges::end(__r), 551 std::move(__pred), std::move(__proj)); 552 } 553 }; 554 555 inline constexpr __find_if_not_fn find_if_not{}; 556 557 template<typename _Iter1, typename _Iter2> 558 struct in_in_result 559 { 560 [[no_unique_address]] _Iter1 in1; 561 [[no_unique_address]] _Iter2 in2; 562 563 template<typename _IIter1, typename _IIter2> 564 requires convertible_to<const _Iter1&, _IIter1> 565 && convertible_to<const _Iter2&, _IIter2> 566 constexpr 567 operator in_in_result<_IIter1, _IIter2>() const & 568 { return {in1, in2}; } 569 570 template<typename _IIter1, typename _IIter2> 571 requires convertible_to<_Iter1, _IIter1> 572 && convertible_to<_Iter2, _IIter2> 573 constexpr 574 operator in_in_result<_IIter1, _IIter2>() && 575 { return {std::move(in1), std::move(in2)}; } 576 }; 577 578 template<typename _Iter1, typename _Iter2> 579 using mismatch_result = in_in_result<_Iter1, _Iter2>; 580 581 struct __mismatch_fn 582 { 583 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1, 584 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2, 585 typename _Pred = ranges::equal_to, 586 typename _Proj1 = identity, typename _Proj2 = identity> 587 requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2> 588 constexpr mismatch_result<_Iter1, _Iter2> 589 operator()(_Iter1 __first1, _Sent1 __last1, 590 _Iter2 __first2, _Sent2 __last2, _Pred __pred = {}, 591 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const 592 { 593 while (__first1 != __last1 && __first2 != __last2 594 && (bool)std::__invoke(__pred, 595 std::__invoke(__proj1, *__first1), 596 std::__invoke(__proj2, *__first2))) 597 { 598 ++__first1; 599 ++__first2; 600 } 601 return { std::move(__first1), std::move(__first2) }; 602 } 603 604 template<input_range _Range1, input_range _Range2, 605 typename _Pred = ranges::equal_to, 606 typename _Proj1 = identity, typename _Proj2 = identity> 607 requires indirectly_comparable<iterator_t<_Range1>, iterator_t<_Range2>, 608 _Pred, _Proj1, _Proj2> 609 constexpr mismatch_result<iterator_t<_Range1>, iterator_t<_Range2>> 610 operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {}, 611 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const 612 { 613 return (*this)(ranges::begin(__r1), ranges::end(__r1), 614 ranges::begin(__r2), ranges::end(__r2), 615 std::move(__pred), 616 std::move(__proj1), std::move(__proj2)); 617 } 618 }; 619 620 inline constexpr __mismatch_fn mismatch{}; 621 622 struct __search_fn 623 { 624 template<forward_iterator _Iter1, sentinel_for<_Iter1> _Sent1, 625 forward_iterator _Iter2, sentinel_for<_Iter2> _Sent2, 626 typename _Pred = ranges::equal_to, 627 typename _Proj1 = identity, typename _Proj2 = identity> 628 requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2> 629 constexpr subrange<_Iter1> 630 operator()(_Iter1 __first1, _Sent1 __last1, 631 _Iter2 __first2, _Sent2 __last2, _Pred __pred = {}, 632 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const 633 { 634 if (__first1 == __last1 || __first2 == __last2) 635 return {__first1, __first1}; 636 637 for (;;) 638 { 639 for (;;) 640 { 641 if (__first1 == __last1) 642 return {__first1, __first1}; 643 if (std::__invoke(__pred, 644 std::__invoke(__proj1, *__first1), 645 std::__invoke(__proj2, *__first2))) 646 break; 647 ++__first1; 648 } 649 auto __cur1 = __first1; 650 auto __cur2 = __first2; 651 for (;;) 652 { 653 if (++__cur2 == __last2) 654 return {__first1, ++__cur1}; 655 if (++__cur1 == __last1) 656 return {__cur1, __cur1}; 657 if (!(bool)std::__invoke(__pred, 658 std::__invoke(__proj1, *__cur1), 659 std::__invoke(__proj2, *__cur2))) 660 { 661 ++__first1; 662 break; 663 } 664 } 665 } 666 } 667 668 template<forward_range _Range1, forward_range _Range2, 669 typename _Pred = ranges::equal_to, 670 typename _Proj1 = identity, typename _Proj2 = identity> 671 requires indirectly_comparable<iterator_t<_Range1>, iterator_t<_Range2>, 672 _Pred, _Proj1, _Proj2> 673 constexpr borrowed_subrange_t<_Range1> 674 operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {}, 675 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const 676 { 677 return (*this)(ranges::begin(__r1), ranges::end(__r1), 678 ranges::begin(__r2), ranges::end(__r2), 679 std::move(__pred), 680 std::move(__proj1), std::move(__proj2)); 681 } 682 }; 683 684 inline constexpr __search_fn search{}; 685 686 struct __min_fn 687 { 688 template<typename _Tp, typename _Proj = identity, 689 indirect_strict_weak_order<projected<const _Tp*, _Proj>> 690 _Comp = ranges::less> 691 constexpr const _Tp& 692 operator()(const _Tp& __a, const _Tp& __b, 693 _Comp __comp = {}, _Proj __proj = {}) const 694 { 695 if (std::__invoke(__comp, 696 std::__invoke(__proj, __b), 697 std::__invoke(__proj, __a))) 698 return __b; 699 else 700 return __a; 701 } 702 703 template<input_range _Range, typename _Proj = identity, 704 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>> 705 _Comp = ranges::less> 706 requires indirectly_copyable_storable<iterator_t<_Range>, 707 range_value_t<_Range>*> 708 constexpr range_value_t<_Range> 709 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const 710 { 711 auto __first = ranges::begin(__r); 712 auto __last = ranges::end(__r); 713 __glibcxx_assert(__first != __last); 714 auto __result = *__first; 715 while (++__first != __last) 716 { 717 auto __tmp = *__first; 718 if (std::__invoke(__comp, 719 std::__invoke(__proj, __tmp), 720 std::__invoke(__proj, __result))) 721 __result = std::move(__tmp); 722 } 723 return __result; 724 } 725 726 template<copyable _Tp, typename _Proj = identity, 727 indirect_strict_weak_order<projected<const _Tp*, _Proj>> 728 _Comp = ranges::less> 729 constexpr _Tp 730 operator()(initializer_list<_Tp> __r, 731 _Comp __comp = {}, _Proj __proj = {}) const 732 { 733 return (*this)(ranges::subrange(__r), 734 std::move(__comp), std::move(__proj)); 735 } 736 }; 737 738 inline constexpr __min_fn min{}; 739 740 struct __adjacent_find_fn 741 { 742 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent, 743 typename _Proj = identity, 744 indirect_binary_predicate<projected<_Iter, _Proj>, 745 projected<_Iter, _Proj>> _Pred 746 = ranges::equal_to> 747 constexpr _Iter 748 operator()(_Iter __first, _Sent __last, 749 _Pred __pred = {}, _Proj __proj = {}) const 750 { 751 if (__first == __last) 752 return __first; 753 auto __next = __first; 754 for (; ++__next != __last; __first = __next) 755 { 756 if (std::__invoke(__pred, 757 std::__invoke(__proj, *__first), 758 std::__invoke(__proj, *__next))) 759 return __first; 760 } 761 return __next; 762 } 763 764 template<forward_range _Range, typename _Proj = identity, 765 indirect_binary_predicate< 766 projected<iterator_t<_Range>, _Proj>, 767 projected<iterator_t<_Range>, _Proj>> _Pred = ranges::equal_to> 768 constexpr borrowed_iterator_t<_Range> 769 operator()(_Range&& __r, _Pred __pred = {}, _Proj __proj = {}) const 770 { 771 return (*this)(ranges::begin(__r), ranges::end(__r), 772 std::move(__pred), std::move(__proj)); 773 } 774 }; 775 776 inline constexpr __adjacent_find_fn adjacent_find{}; 777 778 } // namespace ranges 779 780 using ranges::get; 781 782 template<typename _Iter, typename _Sent, ranges::subrange_kind _Kind> 783 struct tuple_size<ranges::subrange<_Iter, _Sent, _Kind>> 784 : integral_constant<size_t, 2> 785 { }; 786 787 template<typename _Iter, typename _Sent, ranges::subrange_kind _Kind> 788 struct tuple_element<0, ranges::subrange<_Iter, _Sent, _Kind>> 789 { using type = _Iter; }; 790 791 template<typename _Iter, typename _Sent, ranges::subrange_kind _Kind> 792 struct tuple_element<1, ranges::subrange<_Iter, _Sent, _Kind>> 793 { using type = _Sent; }; 794 795 template<typename _Iter, typename _Sent, ranges::subrange_kind _Kind> 796 struct tuple_element<0, const ranges::subrange<_Iter, _Sent, _Kind>> 797 { using type = _Iter; }; 798 799 template<typename _Iter, typename _Sent, ranges::subrange_kind _Kind> 800 struct tuple_element<1, const ranges::subrange<_Iter, _Sent, _Kind>> 801 { using type = _Sent; }; 802 803 _GLIBCXX_END_NAMESPACE_VERSION 804 } // namespace std 805 #endif // library concepts 806 #endif // C++20 807 #endif // _RANGES_UTIL_H
Contact us
|
About us
|
Term of use
|
Copyright © 2000-2025 MyWebUniversity.com ™
