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
38namespace std _GLIBCXX_VISIBILITY(default)
39{
40_GLIBCXX_BEGIN_NAMESPACE_VERSION
41namespace 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>>
62 class view_interface
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>.
469namespace 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
808

source code of include/c++/13/bits/ranges_util.h