libstdc++
ranges_util.h
Go to the documentation of this file.
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>>
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
concept forward_range
A range for which ranges::begin returns a forward iterator.
Definition: ranges_base.h:595
concept input_range
A range for which ranges::begin returns an input iterator.
Definition: ranges_base.h:590
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:250
typename remove_pointer< _Tp >::type remove_pointer_t
Alias template for remove_pointer.
Definition: type_traits:2065
typename decay< _Tp >::type decay_t
Alias template for decay.
Definition: type_traits:2606
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:90
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
Definition: move.h:97
_Tp * end(valarray< _Tp > &__va) noexcept
Return an iterator pointing to one past the last element of the valarray.
Definition: valarray:1249
_Tp * begin(valarray< _Tp > &__va) noexcept
Return an iterator pointing to the first element of the valarray.
Definition: valarray:1227
constexpr const _Tp & min(const _Tp &, const _Tp &)
This does what you think it does.
Definition: stl_algobase.h:233
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:138
constexpr auto empty(const _Container &__cont) noexcept(noexcept(__cont.empty())) -> decltype(__cont.empty())
Return whether a container is empty.
Definition: range_access.h:284
constexpr auto size(const _Container &__cont) noexcept(noexcept(__cont.size())) -> decltype(__cont.size())
Return the size of a container.
Definition: range_access.h:264
constexpr void advance(_InputIterator &__i, _Distance __n)
A generalization of pointer arithmetic.
concept derived_from
[concept.derived], concept derived_from
Definition: concepts:67
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:126
typename __detail::__projected< _Iter, _Proj >::__type projected
[projected], projected
concept default_initializable
[concept.defaultinitializable], concept default_initializable
Definition: concepts:157
The ranges::view_interface class template.
Definition: ranges_util.h:63
ranges::equal_to function object type.
Definition: ranges_cmp.h:91
Finds the size of a given tuple type.
Definition: utility.h:49