libstdc++
ranges_util.h
Go to the documentation of this file.
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>>
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
requires(_Kind==subrange_kind::sized||!sized_sentinel_for< _Sent, _It >) class subrange subrange(_It, _Sent) -> subrange< _It, _Sent >
The ranges::subrange class template.
constexpr _Tp * to_address(_Tp *__ptr) noexcept
Obtain address referenced by a pointer to an object.
Definition: ptr_traits.h:232
typename remove_pointer< _Tp >::type remove_pointer_t
Alias template for remove_pointer.
Definition: type_traits:2249
typename decay< _Tp >::type decay_t
Alias template for decay.
Definition: type_traits:2833
constexpr __invoke_result< _Callable, _Args... >::type __invoke(_Callable &&__fn, _Args &&... __args) noexcept(__is_nothrow_invocable< _Callable, _Args... >::value)
Invoke a callable object.
Definition: invoke.h:92
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
Definition: move.h:138
_Tp * end(valarray< _Tp > &__va) noexcept
Return an iterator pointing to one past the last element of the valarray.
Definition: valarray:1251
_Tp * begin(valarray< _Tp > &__va) noexcept
Return an iterator pointing to the first element of the valarray.
Definition: valarray:1229
constexpr const _Tp & min(const _Tp &, const _Tp &)
This does what you think it does.
Definition: stl_algobase.h:234
ISO C++ entities toplevel namespace is std.
constexpr auto cend(const _Container &__cont) noexcept(noexcept(std::end(__cont))) -> decltype(std::end(__cont))
Return an iterator pointing to one past the last element of the const container.
Definition: range_access.h:144
constexpr auto empty(const _Container &__cont) noexcept(noexcept(__cont.empty())) -> decltype(__cont.empty())
Return whether a container is empty.
Definition: range_access.h:294
constexpr auto size(const _Container &__cont) noexcept(noexcept(__cont.size())) -> decltype(__cont.size())
Return the size of a container.
Definition: range_access.h:274
constexpr void advance(_InputIterator &__i, _Distance __n)
A generalization of pointer arithmetic.
constexpr auto cbegin(const _Container &__cont) noexcept(noexcept(std::begin(__cont))) -> decltype(std::begin(__cont))
Return an iterator pointing to the first element of the const container.
Definition: range_access.h:132
ranges::equal_to function object type.
Definition: ranges_cmp.h:84
The ranges::view_interface class template.
Definition: ranges_util.h:71
Finds the size of a given tuple type.
Definition: utility.h:51