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