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