libstdc++-v3/include/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     template<typename _Tp, typename _Up>
  57       concept __different_from
  58         = !same_as<remove_cvref_t<_Tp>, remove_cvref_t<_Up>>;
  59   } // namespace __detail
  60
  61   /// The ranges::view_interface class template
  62   template<typename _Derived>
  63     requires is_class_v<_Derived> && same_as<_Derived, remove_cv_t<_Derived>>
  64     class view_interface
  65     {
  66     private:
  67       constexpr _Derived& _M_derived() noexcept
  68       {
  69         static_assert(derived_from<_Derived, view_interface<_Derived>>);
  70         static_assert(view<_Derived>);
  71         return static_cast<_Derived&>(*this);
  72       }
  73
  74       constexpr const _Derived& _M_derived() const noexcept
  75       {
  76         static_assert(derived_from<_Derived, view_interface<_Derived>>);
  77         static_assert(view<_Derived>);
  78         return static_cast<const _Derived&>(*this);
  79       }
  80
  81       static constexpr bool
  82       _S_bool(bool) noexcept; // not defined
  83
  84       template<typename _Tp>
  85         static constexpr bool
  86         _S_empty(_Tp& __t)
  87         noexcept(noexcept(_S_bool(ranges::begin(__t) == ranges::end(__t))))
  88         { return ranges::begin(__t) == ranges::end(__t); }
  89
  90       template<typename _Tp>
  91         static constexpr auto
  92         _S_size(_Tp& __t)
  93         noexcept(noexcept(ranges::end(__t) - ranges::begin(__t)))
  94         { return ranges::end(__t) - ranges::begin(__t); }
  95
  96     public:
  97       constexpr bool
  98       empty()
  99       noexcept(noexcept(_S_empty(_M_derived())))
 100       requires forward_range<_Derived>
 101       { return _S_empty(_M_derived()); }
 102
 103       constexpr bool
 104       empty() const
 105       noexcept(noexcept(_S_empty(_M_derived())))
 106       requires forward_range<const _Derived>
 107       { return _S_empty(_M_derived()); }
 108
 109       constexpr explicit
 110       operator bool() noexcept(noexcept(ranges::empty(_M_derived())))
 111       requires requires { ranges::empty(_M_derived()); }
 112       { return !ranges::empty(_M_derived()); }
 113
 114       constexpr explicit
 115       operator bool() const noexcept(noexcept(ranges::empty(_M_derived())))
 116       requires requires { ranges::empty(_M_derived()); }
 117       { return !ranges::empty(_M_derived()); }
 118
 119       constexpr auto
 120       data() noexcept(noexcept(ranges::begin(_M_derived())))
 121       requires contiguous_iterator<iterator_t<_Derived>>
 122       { return std::to_address(ranges::begin(_M_derived())); }
 123
 124       constexpr auto
 125       data() const noexcept(noexcept(ranges::begin(_M_derived())))
 126       requires range<const _Derived>
 127         && contiguous_iterator<iterator_t<const _Derived>>
 128       { return std::to_address(ranges::begin(_M_derived())); }
 129
 130       constexpr auto
 131       size() noexcept(noexcept(_S_size(_M_derived())))
 132       requires forward_range<_Derived>
 133         && sized_sentinel_for<sentinel_t<_Derived>, iterator_t<_Derived>>
 134       { return _S_size(_M_derived()); }
 135
 136       constexpr auto
 137       size() const noexcept(noexcept(_S_size(_M_derived())))
 138       requires forward_range<const _Derived>
 139         && sized_sentinel_for<sentinel_t<const _Derived>,
 140                               iterator_t<const _Derived>>
 141       { return _S_size(_M_derived()); }
 142
 143       constexpr decltype(auto)
 144       front() requires forward_range<_Derived>
 145       {
 146         __glibcxx_assert(!empty());
 147         return *ranges::begin(_M_derived());
 148       }
 149
 150       constexpr decltype(auto)
 151       front() const requires forward_range<const _Derived>
 152       {
 153         __glibcxx_assert(!empty());
 154         return *ranges::begin(_M_derived());
 155       }
 156
 157       constexpr decltype(auto)
 158       back()
 159       requires bidirectional_range<_Derived> && common_range<_Derived>
 160       {
 161         __glibcxx_assert(!empty());
 162         return *ranges::prev(ranges::end(_M_derived()));
 163       }
 164
 165       constexpr decltype(auto)
 166       back() const
 167       requires bidirectional_range<const _Derived>
 168         && common_range<const _Derived>
 169       {
 170         __glibcxx_assert(!empty());
 171         return *ranges::prev(ranges::end(_M_derived()));
 172       }
 173
 174       template<random_access_range _Range = _Derived>
 175         constexpr decltype(auto)
 176         operator[](range_difference_t<_Range> __n)
 177         { return ranges::begin(_M_derived())[__n]; }
 178
 179       template<random_access_range _Range = const _Derived>
 180         constexpr decltype(auto)
 181         operator[](range_difference_t<_Range> __n) const
 182         { return ranges::begin(_M_derived())[__n]; }
 183     };
 184
 185   namespace __detail
 186   {
 187     template<typename _From, typename _To>
 188       concept __uses_nonqualification_pointer_conversion
 189         = is_pointer_v<_From> && is_pointer_v<_To>
 190           && !convertible_to<remove_pointer_t<_From>(*)[],
 191                              remove_pointer_t<_To>(*)[]>;
 192
 193     template<typename _From, typename _To>
 194       concept __convertible_to_non_slicing = convertible_to<_From, _To>
 195         && !__uses_nonqualification_pointer_conversion<decay_t<_From>,
 196                                                        decay_t<_To>>;
 197
 198     template<typename _Tp>
 199       concept __pair_like
 200         = !is_reference_v<_Tp> && requires(_Tp __t)
 201         {
 202           typename tuple_size<_Tp>::type;
 203           requires derived_from<tuple_size<_Tp>, integral_constant<size_t, 2>>;
 204           typename tuple_element_t<0, remove_const_t<_Tp>>;
 205           typename tuple_element_t<1, remove_const_t<_Tp>>;
 206           { get<0>(__t) } -> convertible_to<const tuple_element_t<0, _Tp>&>;
 207           { get<1>(__t) } -> convertible_to<const tuple_element_t<1, _Tp>&>;
 208         };
 209
 210     template<typename _Tp, typename _Up, typename _Vp>
 211       concept __pair_like_convertible_from
 212         = !range<_Tp> && __pair_like<_Tp>
 213         && constructible_from<_Tp, _Up, _Vp>
 214         && __convertible_to_non_slicing<_Up, tuple_element_t<0, _Tp>>
 215         && convertible_to<_Vp, tuple_element_t<1, _Tp>>;
 216
 217   } // namespace __detail
 218
 219   namespace views { struct _Drop; } // defined in <ranges>
 220
 221   enum class subrange_kind : bool { unsized, sized };
 222
 223   /// The ranges::subrange class template
 224   template<input_or_output_iterator _It, sentinel_for<_It> _Sent = _It,
 225            subrange_kind _Kind = sized_sentinel_for<_Sent, _It>
 226              ? subrange_kind::sized : subrange_kind::unsized>
 227     requires (_Kind == subrange_kind::sized || !sized_sentinel_for<_Sent, _It>)
 228     class subrange : public view_interface<subrange<_It, _Sent, _Kind>>
 229     {
 230     private:
 231       static constexpr bool _S_store_size
 232         = _Kind == subrange_kind::sized && !sized_sentinel_for<_Sent, _It>;
 233
 234       friend struct views::_Drop; // Needs to inspect _S_store_size.
 235
 236       _It _M_begin = _It();
 237       [[no_unique_address]] _Sent _M_end = _Sent();
 238
 239       using __size_type
 240         = __detail::__make_unsigned_like_t<iter_difference_t<_It>>;
 241
 242       template<typename, bool = _S_store_size>
 243         struct _Size
 244         { };
 245
 246       template<typename _Tp>
 247         struct _Size<_Tp, true>
 248         { _Tp _M_size; };
 249
 250       [[no_unique_address]] _Size<__size_type> _M_size = {};
 251
 252     public:
 253       subrange() requires default_initializable<_It> = default;
 254
 255       constexpr
 256       subrange(__detail::__convertible_to_non_slicing<_It> auto __i, _Sent __s)
 257       noexcept(is_nothrow_constructible_v<_It, decltype(__i)>
 258                && is_nothrow_constructible_v<_Sent, _Sent&>)
 259         requires (!_S_store_size)
 260       : _M_begin(std::move(__i)), _M_end(__s)
 261       { }
 262
 263       constexpr
 264       subrange(__detail::__convertible_to_non_slicing<_It> auto __i, _Sent __s,
 265                __size_type __n)
 266       noexcept(is_nothrow_constructible_v<_It, decltype(__i)>
 267                && is_nothrow_constructible_v<_Sent, _Sent&>)
 268         requires (_Kind == subrange_kind::sized)
 269       : _M_begin(std::move(__i)), _M_end(__s)
 270       {
 271         if constexpr (_S_store_size)
 272           _M_size._M_size = __n;
 273       }
 274
 275       template<__detail::__different_from<subrange> _Rng>
 276         requires borrowed_range<_Rng>
 277           && __detail::__convertible_to_non_slicing<iterator_t<_Rng>, _It>
 278           && convertible_to<sentinel_t<_Rng>, _Sent>
 279         constexpr
 280         subrange(_Rng&& __r)
 281         noexcept(noexcept(subrange(__r, ranges::size(__r))))
 282         requires _S_store_size && sized_range<_Rng>
 283         : subrange(__r, ranges::size(__r))
 284         { }
 285
 286       template<__detail::__different_from<subrange> _Rng>
 287         requires borrowed_range<_Rng>
 288           && __detail::__convertible_to_non_slicing<iterator_t<_Rng>, _It>
 289           && convertible_to<sentinel_t<_Rng>, _Sent>
 290         constexpr
 291         subrange(_Rng&& __r)
 292         noexcept(noexcept(subrange(ranges::begin(__r), ranges::end(__r))))
 293         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, __size_type __n)
 302         noexcept(noexcept(subrange(ranges::begin(__r), ranges::end(__r), __n)))
 303         requires (_Kind == subrange_kind::sized)
 304         : subrange{ranges::begin(__r), ranges::end(__r), __n}
 305         { }
 306
 307       template<__detail::__different_from<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 __size_type
 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<borrowed_range _Rng>
 391     subrange(_Rng&&)
 392       -> subrange<iterator_t<_Rng>, sentinel_t<_Rng>,
 393                  (sized_range<_Rng>
 394                   || sized_sentinel_for<sentinel_t<_Rng>, iterator_t<_Rng>>)
 395                  ? subrange_kind::sized : subrange_kind::unsized>;
 396
 397   template<borrowed_range _Rng>
 398     subrange(_Rng&&,
 399              __detail::__make_unsigned_like_t<range_difference_t<_Rng>>)
 400       -> subrange<iterator_t<_Rng>, sentinel_t<_Rng>, subrange_kind::sized>;
 401
 402   template<size_t _Num, class _It, class _Sent, subrange_kind _Kind>
 403     requires (_Num < 2)
 404     constexpr auto
 405     get(const subrange<_It, _Sent, _Kind>& __r)
 406     {
 407       if constexpr (_Num == 0)
 408         return __r.begin();
 409       else
 410         return __r.end();
 411     }
 412
 413   template<size_t _Num, class _It, class _Sent, subrange_kind _Kind>
 414     requires (_Num < 2)
 415     constexpr auto
 416     get(subrange<_It, _Sent, _Kind>&& __r)
 417     {
 418       if constexpr (_Num == 0)
 419         return __r.begin();
 420       else
 421         return __r.end();
 422     }
 423
 424   template<typename _It, typename _Sent, subrange_kind _Kind>
 425     inline constexpr bool
 426       enable_borrowed_range<subrange<_It, _Sent, _Kind>> = true;
 427
 428   template<range _Range>
 429     using borrowed_subrange_t = __conditional_t<borrowed_range<_Range>,
 430                                                 subrange<iterator_t<_Range>>,
 431                                                 dangling>;
 432 } // namespace ranges
 433
 434 // The following ranges algorithms are used by <ranges>, and are defined here
 435 // so that <ranges> can avoid including all of <bits/ranges_algo.h>.
 436 namespace ranges
 437 {
 438   struct __find_fn
 439   {
 440     template<input_iterator _Iter, sentinel_for<_Iter> _Sent, typename _Tp,
 441              typename _Proj = identity>
 442       requires indirect_binary_predicate<ranges::equal_to,
 443                                          projected<_Iter, _Proj>, const _Tp*>
 444       constexpr _Iter
 445       operator()(_Iter __first, _Sent __last,
 446                  const _Tp& __value, _Proj __proj = {}) const
 447       {
 448         while (__first != __last
 449             && !(std::__invoke(__proj, *__first) == __value))
 450           ++__first;
 451         return __first;
 452       }
 453
 454     template<input_range _Range, typename _Tp, typename _Proj = identity>
 455       requires indirect_binary_predicate<ranges::equal_to,
 456                                          projected<iterator_t<_Range>, _Proj>,
 457                                          const _Tp*>
 458       constexpr borrowed_iterator_t<_Range>
 459       operator()(_Range&& __r, const _Tp& __value, _Proj __proj = {}) const
 460       {
 461         return (*this)(ranges::begin(__r), ranges::end(__r),
 462                        __value, std::move(__proj));
 463       }
 464   };
 465
 466   inline constexpr __find_fn find{};
 467
 468   struct __find_if_fn
 469   {
 470     template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
 471              typename _Proj = identity,
 472              indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
 473       constexpr _Iter
 474       operator()(_Iter __first, _Sent __last,
 475                  _Pred __pred, _Proj __proj = {}) const
 476       {
 477         while (__first != __last
 478             && !(bool)std::__invoke(__pred, std::__invoke(__proj, *__first)))
 479           ++__first;
 480         return __first;
 481       }
 482
 483     template<input_range _Range, typename _Proj = identity,
 484              indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
 485                _Pred>
 486       constexpr borrowed_iterator_t<_Range>
 487       operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const
 488       {
 489         return (*this)(ranges::begin(__r), ranges::end(__r),
 490                        std::move(__pred), std::move(__proj));
 491       }
 492   };
 493
 494   inline constexpr __find_if_fn find_if{};
 495
 496   struct __find_if_not_fn
 497   {
 498     template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
 499              typename _Proj = identity,
 500              indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
 501       constexpr _Iter
 502       operator()(_Iter __first, _Sent __last,
 503                  _Pred __pred, _Proj __proj = {}) const
 504       {
 505         while (__first != __last
 506             && (bool)std::__invoke(__pred, std::__invoke(__proj, *__first)))
 507           ++__first;
 508         return __first;
 509       }
 510
 511     template<input_range _Range, typename _Proj = identity,
 512              indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
 513                _Pred>
 514       constexpr borrowed_iterator_t<_Range>
 515       operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const
 516       {
 517         return (*this)(ranges::begin(__r), ranges::end(__r),
 518                        std::move(__pred), std::move(__proj));
 519       }
 520   };
 521
 522   inline constexpr __find_if_not_fn find_if_not{};
 523
 524   template<typename _Iter1, typename _Iter2>
 525     struct in_in_result
 526     {
 527       [[no_unique_address]] _Iter1 in1;
 528       [[no_unique_address]] _Iter2 in2;
 529
 530       template<typename _IIter1, typename _IIter2>
 531         requires convertible_to<const _Iter1&, _IIter1>
 532           && convertible_to<const _Iter2&, _IIter2>
 533         constexpr
 534         operator in_in_result<_IIter1, _IIter2>() const &
 535         { return {in1, in2}; }
 536
 537       template<typename _IIter1, typename _IIter2>
 538         requires convertible_to<_Iter1, _IIter1>
 539           && convertible_to<_Iter2, _IIter2>
 540         constexpr
 541         operator in_in_result<_IIter1, _IIter2>() &&
 542         { return {std::move(in1), std::move(in2)}; }
 543     };
 544
 545   template<typename _Iter1, typename _Iter2>
 546     using mismatch_result = in_in_result<_Iter1, _Iter2>;
 547
 548   struct __mismatch_fn
 549   {
 550     template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
 551              input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
 552              typename _Pred = ranges::equal_to,
 553              typename _Proj1 = identity, typename _Proj2 = identity>
 554       requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2>
 555       constexpr mismatch_result<_Iter1, _Iter2>
 556       operator()(_Iter1 __first1, _Sent1 __last1,
 557                  _Iter2 __first2, _Sent2 __last2, _Pred __pred = {},
 558                  _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
 559       {
 560         while (__first1 != __last1 && __first2 != __last2
 561                && (bool)std::__invoke(__pred,
 562                                       std::__invoke(__proj1, *__first1),
 563                                       std::__invoke(__proj2, *__first2)))
 564         {
 565           ++__first1;
 566           ++__first2;
 567         }
 568         return { std::move(__first1), std::move(__first2) };
 569       }
 570
 571     template<input_range _Range1, input_range _Range2,
 572              typename _Pred = ranges::equal_to,
 573              typename _Proj1 = identity, typename _Proj2 = identity>
 574       requires indirectly_comparable<iterator_t<_Range1>, iterator_t<_Range2>,
 575                                      _Pred, _Proj1, _Proj2>
 576       constexpr mismatch_result<iterator_t<_Range1>, iterator_t<_Range2>>
 577       operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {},
 578                  _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
 579       {
 580         return (*this)(ranges::begin(__r1), ranges::end(__r1),
 581                        ranges::begin(__r2), ranges::end(__r2),
 582                        std::move(__pred),
 583                        std::move(__proj1), std::move(__proj2));
 584       }
 585   };
 586
 587   inline constexpr __mismatch_fn mismatch{};
 588
 589   struct __search_fn
 590   {
 591     template<forward_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
 592              forward_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
 593              typename _Pred = ranges::equal_to,
 594              typename _Proj1 = identity, typename _Proj2 = identity>
 595       requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2>
 596       constexpr subrange<_Iter1>
 597       operator()(_Iter1 __first1, _Sent1 __last1,
 598                  _Iter2 __first2, _Sent2 __last2, _Pred __pred = {},
 599                  _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
 600       {
 601         if (__first1 == __last1 || __first2 == __last2)
 602           return {__first1, __first1};
 603
 604         for (;;)
 605           {
 606             for (;;)
 607               {
 608                 if (__first1 == __last1)
 609                   return {__first1, __first1};
 610                 if (std::__invoke(__pred,
 611                                   std::__invoke(__proj1, *__first1),
 612                                   std::__invoke(__proj2, *__first2)))
 613                   break;
 614                 ++__first1;
 615               }
 616             auto __cur1 = __first1;
 617             auto __cur2 = __first2;
 618             for (;;)
 619               {
 620                 if (++__cur2 == __last2)
 621                   return {__first1, ++__cur1};
 622                 if (++__cur1 == __last1)
 623                   return {__cur1, __cur1};
 624                 if (!(bool)std::__invoke(__pred,
 625                                          std::__invoke(__proj1, *__cur1),
 626                                          std::__invoke(__proj2, *__cur2)))
 627                   {
 628                     ++__first1;
 629                     break;
 630                   }
 631               }
 632           }
 633       }
 634
 635     template<forward_range _Range1, forward_range _Range2,
 636              typename _Pred = ranges::equal_to,
 637              typename _Proj1 = identity, typename _Proj2 = identity>
 638       requires indirectly_comparable<iterator_t<_Range1>, iterator_t<_Range2>,
 639                                      _Pred, _Proj1, _Proj2>
 640       constexpr borrowed_subrange_t<_Range1>
 641       operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {},
 642                  _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
 643       {
 644         return (*this)(ranges::begin(__r1), ranges::end(__r1),
 645                        ranges::begin(__r2), ranges::end(__r2),
 646                        std::move(__pred),
 647                        std::move(__proj1), std::move(__proj2));
 648       }
 649   };
 650
 651   inline constexpr __search_fn search{};
 652
 653   struct __min_fn
 654   {
 655     template<typename _Tp, typename _Proj = identity,
 656              indirect_strict_weak_order<projected<const _Tp*, _Proj>>
 657                _Comp = ranges::less>
 658       constexpr const _Tp&
 659       operator()(const _Tp& __a, const _Tp& __b,
 660                  _Comp __comp = {}, _Proj __proj = {}) const
 661       {
 662         if (std::__invoke(__comp,
 663                           std::__invoke(__proj, __b),
 664                           std::__invoke(__proj, __a)))
 665           return __b;
 666         else
 667           return __a;
 668       }
 669
 670     template<input_range _Range, typename _Proj = identity,
 671              indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
 672                _Comp = ranges::less>
 673       requires indirectly_copyable_storable<iterator_t<_Range>,
 674                                             range_value_t<_Range>*>
 675       constexpr range_value_t<_Range>
 676       operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
 677       {
 678         auto __first = ranges::begin(__r);
 679         auto __last = ranges::end(__r);
 680         __glibcxx_assert(__first != __last);
 681         auto __result = *__first;
 682         while (++__first != __last)
 683           {
 684             auto __tmp = *__first;
 685             if (std::__invoke(__comp,
 686                               std::__invoke(__proj, __tmp),
 687                               std::__invoke(__proj, __result)))
 688               __result = std::move(__tmp);
 689           }
 690         return __result;
 691       }
 692
 693     template<copyable _Tp, typename _Proj = identity,
 694              indirect_strict_weak_order<projected<const _Tp*, _Proj>>
 695                _Comp = ranges::less>
 696       constexpr _Tp
 697       operator()(initializer_list<_Tp> __r,
 698                  _Comp __comp = {}, _Proj __proj = {}) const
 699       {
 700         return (*this)(ranges::subrange(__r),
 701                        std::move(__comp), std::move(__proj));
 702       }
 703   };
 704
 705   inline constexpr __min_fn min{};
 706
 707   struct __adjacent_find_fn
 708   {
 709     template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
 710              typename _Proj = identity,
 711              indirect_binary_predicate<projected<_Iter, _Proj>,
 712                                        projected<_Iter, _Proj>> _Pred
 713                = ranges::equal_to>
 714       constexpr _Iter
 715       operator()(_Iter __first, _Sent __last,
 716                  _Pred __pred = {}, _Proj __proj = {}) const
 717       {
 718         if (__first == __last)
 719           return __first;
 720         auto __next = __first;
 721         for (; ++__next != __last; __first = __next)
 722           {
 723             if (std::__invoke(__pred,
 724                               std::__invoke(__proj, *__first),
 725                               std::__invoke(__proj, *__next)))
 726               return __first;
 727           }
 728         return __next;
 729       }
 730
 731     template<forward_range _Range, typename _Proj = identity,
 732              indirect_binary_predicate<
 733                projected<iterator_t<_Range>, _Proj>,
 734                projected<iterator_t<_Range>, _Proj>> _Pred = ranges::equal_to>
 735       constexpr borrowed_iterator_t<_Range>
 736       operator()(_Range&& __r, _Pred __pred = {}, _Proj __proj = {}) const
 737       {
 738         return (*this)(ranges::begin(__r), ranges::end(__r),
 739                        std::move(__pred), std::move(__proj));
 740       }
 741   };
 742
 743   inline constexpr __adjacent_find_fn adjacent_find{};
 744
 745 } // namespace ranges
 746
 747   using ranges::get;
 748
 749   template<typename _Iter, typename _Sent, ranges::subrange_kind _Kind>
 750     struct tuple_size<ranges::subrange<_Iter, _Sent, _Kind>>
 751     : integral_constant<size_t, 2>
 752     { };
 753
 754   template<typename _Iter, typename _Sent, ranges::subrange_kind _Kind>
 755     struct tuple_element<0, ranges::subrange<_Iter, _Sent, _Kind>>
 756     { using type = _Iter; };
 757
 758   template<typename _Iter, typename _Sent, ranges::subrange_kind _Kind>
 759     struct tuple_element<1, ranges::subrange<_Iter, _Sent, _Kind>>
 760     { using type = _Sent; };
 761
 762   template<typename _Iter, typename _Sent, ranges::subrange_kind _Kind>
 763     struct tuple_element<0, const ranges::subrange<_Iter, _Sent, _Kind>>
 764     { using type = _Iter; };
 765
 766   template<typename _Iter, typename _Sent, ranges::subrange_kind _Kind>
 767     struct tuple_element<1, const ranges::subrange<_Iter, _Sent, _Kind>>
 768     { using type = _Sent; };
 769
 770 _GLIBCXX_END_NAMESPACE_VERSION
 771 } // namespace std
 772 #endif // library concepts
 773 #endif // C++20
 774 #endif // _RANGES_UTIL_H