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