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