libstdc++
ranges_util.h
Go to the documentation of this file.
1// Utilities for representing and manipulating ranges -*- C++ -*-
2
3// Copyright (C) 2019-2023 Free Software Foundation, Inc.
4//
5// This file is part of the GNU ISO C++ Library. This library is free
6// software; you can redistribute it and/or modify it under the
7// terms of the GNU General Public License as published by the
8// Free Software Foundation; either version 3, or (at your option)
9// any later version.
10
11// This library is distributed in the hope that it will be useful,
12// but WITHOUT ANY WARRANTY; without even the implied warranty of
13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14// GNU General Public License for more details.
15
16// Under Section 7 of GPL version 3, you are granted additional
17// permissions described in the GCC Runtime Library Exception, version
18// 3.1, as published by the Free Software Foundation.
19
20// You should have received a copy of the GNU General Public License and
21// a copy of the GCC Runtime Library Exception along with this program;
22// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23// <http://www.gnu.org/licenses/>.
24
25/** @file bits/ranges_util.h
26 * This is an internal header file, included by other library headers.
27 * Do not attempt to use it directly. @headername{ranges}
28 */
29
30#ifndef _RANGES_UTIL_H
31#define _RANGES_UTIL_H 1
32
33#if __cplusplus > 201703L
34# include <bits/ranges_base.h>
35# include <bits/utility.h>
36
37#ifdef __cpp_lib_ranges
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 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>>
65 {
66 private:
67 constexpr _Derived& _M_derived() noexcept
68 {
70 static_assert(view<_Derived>);
71 return static_cast<_Derived&>(*this);
72 }
73
74 constexpr const _Derived& _M_derived() const noexcept
75 {
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())))
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())))
113 { return _S_empty(_M_derived()); }
114
115 constexpr bool
116 empty() const
117 noexcept(noexcept(ranges::size(_M_derived()) == 0))
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())))
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())))
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()
172 {
173 __glibcxx_assert(!empty());
174 return *ranges::prev(ranges::end(_M_derived()));
175 }
176
177 constexpr decltype(auto)
178 back() const
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
197 namespace __detail
198 {
199 template<typename _From, typename _To>
200 concept __uses_nonqualification_pointer_conversion
201 = is_pointer_v<_From> && is_pointer_v<_To>
204
205 template<typename _From, typename _To>
206 concept __convertible_to_non_slicing = convertible_to<_From, _To>
207 && !__uses_nonqualification_pointer_conversion<decay_t<_From>,
209
210 template<typename _Tp>
211 concept __pair_like
212 = !is_reference_v<_Tp> && requires(_Tp __t)
213 {
214 typename tuple_size<_Tp>::type;
216 typename tuple_element_t<0, remove_const_t<_Tp>>;
217 typename tuple_element_t<1, remove_const_t<_Tp>>;
219 { get<1>(__t) } -> convertible_to<const tuple_element_t<1, _Tp>&>;
220 };
221
222 template<typename _Tp, typename _Up, typename _Vp>
223 concept __pair_like_convertible_from
224 = !range<_Tp> && __pair_like<_Tp>
225 && constructible_from<_Tp, _Up, _Vp>
226 && __convertible_to_non_slicing<_Up, tuple_element_t<0, _Tp>>
227 && convertible_to<_Vp, tuple_element_t<1, _Tp>>;
228
229 } // namespace __detail
230
231 namespace views { struct _Drop; } // defined in <ranges>
232
233 enum class subrange_kind : bool { unsized, sized };
234
235 /// The ranges::subrange class template
236 template<input_or_output_iterator _It, sentinel_for<_It> _Sent = _It,
237 subrange_kind _Kind = sized_sentinel_for<_Sent, _It>
238 ? subrange_kind::sized : subrange_kind::unsized>
239 requires (_Kind == subrange_kind::sized || !sized_sentinel_for<_Sent, _It>)
241 {
242 private:
243 static constexpr bool _S_store_size
244 = _Kind == subrange_kind::sized && !sized_sentinel_for<_Sent, _It>;
245
246 friend struct views::_Drop; // Needs to inspect _S_store_size.
247
248 _It _M_begin = _It();
249 [[no_unique_address]] _Sent _M_end = _Sent();
250
251 using __size_type
252 = __detail::__make_unsigned_like_t<iter_difference_t<_It>>;
253
254 template<typename, bool = _S_store_size>
255 struct _Size
256 { };
257
258 template<typename _Tp>
259 struct _Size<_Tp, true>
260 { _Tp _M_size; };
261
262 [[no_unique_address]] _Size<__size_type> _M_size = {};
263
264 public:
265 subrange() requires default_initializable<_It> = default;
266
267 constexpr
268 subrange(__detail::__convertible_to_non_slicing<_It> auto __i, _Sent __s)
269 noexcept(is_nothrow_constructible_v<_It, decltype(__i)>
270 && is_nothrow_constructible_v<_Sent, _Sent&>)
271 requires (!_S_store_size)
272 : _M_begin(std::move(__i)), _M_end(__s)
273 { }
274
275 constexpr
276 subrange(__detail::__convertible_to_non_slicing<_It> auto __i, _Sent __s,
277 __size_type __n)
278 noexcept(is_nothrow_constructible_v<_It, decltype(__i)>
279 && is_nothrow_constructible_v<_Sent, _Sent&>)
280 requires (_Kind == subrange_kind::sized)
281 : _M_begin(std::move(__i)), _M_end(__s)
282 {
283 if constexpr (_S_store_size)
284 _M_size._M_size = __n;
285 }
286
287 template<__detail::__different_from<subrange> _Rng>
288 requires borrowed_range<_Rng>
289 && __detail::__convertible_to_non_slicing<iterator_t<_Rng>, _It>
291 constexpr
292 subrange(_Rng&& __r)
293 noexcept(noexcept(subrange(__r, ranges::size(__r))))
294 requires _S_store_size && sized_range<_Rng>
295 : subrange(__r, ranges::size(__r))
296 { }
297
298 template<__detail::__different_from<subrange> _Rng>
299 requires borrowed_range<_Rng>
300 && __detail::__convertible_to_non_slicing<iterator_t<_Rng>, _It>
302 constexpr
303 subrange(_Rng&& __r)
304 noexcept(noexcept(subrange(ranges::begin(__r), ranges::end(__r))))
305 requires (!_S_store_size)
306 : subrange(ranges::begin(__r), ranges::end(__r))
307 { }
308
309 template<borrowed_range _Rng>
310 requires __detail::__convertible_to_non_slicing<iterator_t<_Rng>, _It>
312 constexpr
313 subrange(_Rng&& __r, __size_type __n)
314 noexcept(noexcept(subrange(ranges::begin(__r), ranges::end(__r), __n)))
315 requires (_Kind == subrange_kind::sized)
316 : subrange{ranges::begin(__r), ranges::end(__r), __n}
317 { }
318
319 template<__detail::__different_from<subrange> _PairLike>
320 requires __detail::__pair_like_convertible_from<_PairLike, const _It&,
321 const _Sent&>
322 constexpr
323 operator _PairLike() const
324 { return _PairLike(_M_begin, _M_end); }
325
326 constexpr _It
327 begin() const requires copyable<_It>
328 { return _M_begin; }
329
330 [[nodiscard]] constexpr _It
331 begin() requires (!copyable<_It>)
332 { return std::move(_M_begin); }
333
334 constexpr _Sent end() const { return _M_end; }
335
336 constexpr bool empty() const { return _M_begin == _M_end; }
337
338 constexpr __size_type
339 size() const requires (_Kind == subrange_kind::sized)
340 {
341 if constexpr (_S_store_size)
342 return _M_size._M_size;
343 else
344 return __detail::__to_unsigned_like(_M_end - _M_begin);
345 }
346
347 [[nodiscard]] constexpr subrange
348 next(iter_difference_t<_It> __n = 1) const &
349 requires forward_iterator<_It>
350 {
351 auto __tmp = *this;
352 __tmp.advance(__n);
353 return __tmp;
354 }
355
356 [[nodiscard]] constexpr subrange
357 next(iter_difference_t<_It> __n = 1) &&
358 {
359 advance(__n);
360 return std::move(*this);
361 }
362
363 [[nodiscard]] constexpr subrange
364 prev(iter_difference_t<_It> __n = 1) const
365 requires bidirectional_iterator<_It>
366 {
367 auto __tmp = *this;
368 __tmp.advance(-__n);
369 return __tmp;
370 }
371
372 constexpr subrange&
373 advance(iter_difference_t<_It> __n)
374 {
375 // _GLIBCXX_RESOLVE_LIB_DEFECTS
376 // 3433. subrange::advance(n) has UB when n < 0
377 if constexpr (bidirectional_iterator<_It>)
378 if (__n < 0)
379 {
380 ranges::advance(_M_begin, __n);
381 if constexpr (_S_store_size)
382 _M_size._M_size += __detail::__to_unsigned_like(-__n);
383 return *this;
384 }
385
386 __glibcxx_assert(__n >= 0);
387 auto __d = __n - ranges::advance(_M_begin, __n, _M_end);
388 if constexpr (_S_store_size)
389 _M_size._M_size -= __detail::__to_unsigned_like(__d);
390 return *this;
391 }
392 };
393
394 template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
395 subrange(_It, _Sent) -> subrange<_It, _Sent>;
396
397 template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
398 subrange(_It, _Sent,
399 __detail::__make_unsigned_like_t<iter_difference_t<_It>>)
401
402 template<borrowed_range _Rng>
403 subrange(_Rng&&)
404 -> subrange<iterator_t<_Rng>, sentinel_t<_Rng>,
406 || sized_sentinel_for<sentinel_t<_Rng>, iterator_t<_Rng>>)
407 ? subrange_kind::sized : subrange_kind::unsized>;
408
409 template<borrowed_range _Rng>
410 subrange(_Rng&&,
411 __detail::__make_unsigned_like_t<range_difference_t<_Rng>>)
412 -> subrange<iterator_t<_Rng>, sentinel_t<_Rng>, subrange_kind::sized>;
413
414 template<size_t _Num, class _It, class _Sent, subrange_kind _Kind>
415 requires (_Num < 2)
416 constexpr auto
417 get(const subrange<_It, _Sent, _Kind>& __r)
418 {
419 if constexpr (_Num == 0)
420 return __r.begin();
421 else
422 return __r.end();
423 }
424
425 template<size_t _Num, class _It, class _Sent, subrange_kind _Kind>
426 requires (_Num < 2)
427 constexpr auto
428 get(subrange<_It, _Sent, _Kind>&& __r)
429 {
430 if constexpr (_Num == 0)
431 return __r.begin();
432 else
433 return __r.end();
434 }
435
436 template<typename _It, typename _Sent, subrange_kind _Kind>
437 inline constexpr bool
438 enable_borrowed_range<subrange<_It, _Sent, _Kind>> = true;
439
440 template<range _Range>
441 using borrowed_subrange_t = __conditional_t<borrowed_range<_Range>,
442 subrange<iterator_t<_Range>>,
443 dangling>;
444} // namespace ranges
445
446// The following ranges algorithms are used by <ranges>, and are defined here
447// so that <ranges> can avoid including all of <bits/ranges_algo.h>.
448namespace ranges
449{
450 struct __find_fn
451 {
452 template<input_iterator _Iter, sentinel_for<_Iter> _Sent, typename _Tp,
453 typename _Proj = identity>
454 requires indirect_binary_predicate<ranges::equal_to,
455 projected<_Iter, _Proj>, const _Tp*>
456 constexpr _Iter
457 operator()(_Iter __first, _Sent __last,
458 const _Tp& __value, _Proj __proj = {}) const
459 {
460 while (__first != __last
461 && !(std::__invoke(__proj, *__first) == __value))
462 ++__first;
463 return __first;
464 }
465
466 template<input_range _Range, typename _Tp, typename _Proj = identity>
467 requires indirect_binary_predicate<ranges::equal_to,
468 projected<iterator_t<_Range>, _Proj>,
469 const _Tp*>
470 constexpr borrowed_iterator_t<_Range>
471 operator()(_Range&& __r, const _Tp& __value, _Proj __proj = {}) const
472 {
473 return (*this)(ranges::begin(__r), ranges::end(__r),
474 __value, std::move(__proj));
475 }
476 };
477
478 inline constexpr __find_fn find{};
479
480 struct __find_if_fn
481 {
482 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
483 typename _Proj = identity,
484 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
485 constexpr _Iter
486 operator()(_Iter __first, _Sent __last,
487 _Pred __pred, _Proj __proj = {}) const
488 {
489 while (__first != __last
490 && !(bool)std::__invoke(__pred, std::__invoke(__proj, *__first)))
491 ++__first;
492 return __first;
493 }
494
495 template<input_range _Range, typename _Proj = identity,
496 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
497 _Pred>
498 constexpr borrowed_iterator_t<_Range>
499 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const
500 {
501 return (*this)(ranges::begin(__r), ranges::end(__r),
502 std::move(__pred), std::move(__proj));
503 }
504 };
505
506 inline constexpr __find_if_fn find_if{};
507
508 struct __find_if_not_fn
509 {
510 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
511 typename _Proj = identity,
512 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
513 constexpr _Iter
514 operator()(_Iter __first, _Sent __last,
515 _Pred __pred, _Proj __proj = {}) const
516 {
517 while (__first != __last
518 && (bool)std::__invoke(__pred, std::__invoke(__proj, *__first)))
519 ++__first;
520 return __first;
521 }
522
523 template<input_range _Range, typename _Proj = identity,
524 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
525 _Pred>
526 constexpr borrowed_iterator_t<_Range>
527 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const
528 {
529 return (*this)(ranges::begin(__r), ranges::end(__r),
530 std::move(__pred), std::move(__proj));
531 }
532 };
533
534 inline constexpr __find_if_not_fn find_if_not{};
535
536 template<typename _Iter1, typename _Iter2>
537 struct in_in_result
538 {
539 [[no_unique_address]] _Iter1 in1;
540 [[no_unique_address]] _Iter2 in2;
541
542 template<typename _IIter1, typename _IIter2>
543 requires convertible_to<const _Iter1&, _IIter1>
544 && convertible_to<const _Iter2&, _IIter2>
545 constexpr
546 operator in_in_result<_IIter1, _IIter2>() const &
547 { return {in1, in2}; }
548
549 template<typename _IIter1, typename _IIter2>
550 requires convertible_to<_Iter1, _IIter1>
551 && convertible_to<_Iter2, _IIter2>
552 constexpr
553 operator in_in_result<_IIter1, _IIter2>() &&
554 { return {std::move(in1), std::move(in2)}; }
555 };
556
557 template<typename _Iter1, typename _Iter2>
558 using mismatch_result = in_in_result<_Iter1, _Iter2>;
559
560 struct __mismatch_fn
561 {
562 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
563 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
564 typename _Pred = ranges::equal_to,
565 typename _Proj1 = identity, typename _Proj2 = identity>
566 requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2>
567 constexpr mismatch_result<_Iter1, _Iter2>
568 operator()(_Iter1 __first1, _Sent1 __last1,
569 _Iter2 __first2, _Sent2 __last2, _Pred __pred = {},
570 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
571 {
572 while (__first1 != __last1 && __first2 != __last2
573 && (bool)std::__invoke(__pred,
574 std::__invoke(__proj1, *__first1),
575 std::__invoke(__proj2, *__first2)))
576 {
577 ++__first1;
578 ++__first2;
579 }
580 return { std::move(__first1), std::move(__first2) };
581 }
582
583 template<input_range _Range1, input_range _Range2,
584 typename _Pred = ranges::equal_to,
585 typename _Proj1 = identity, typename _Proj2 = identity>
586 requires indirectly_comparable<iterator_t<_Range1>, iterator_t<_Range2>,
587 _Pred, _Proj1, _Proj2>
588 constexpr mismatch_result<iterator_t<_Range1>, iterator_t<_Range2>>
589 operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {},
590 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
591 {
592 return (*this)(ranges::begin(__r1), ranges::end(__r1),
593 ranges::begin(__r2), ranges::end(__r2),
594 std::move(__pred),
595 std::move(__proj1), std::move(__proj2));
596 }
597 };
598
599 inline constexpr __mismatch_fn mismatch{};
600
601 struct __search_fn
602 {
603 template<forward_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
604 forward_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
605 typename _Pred = ranges::equal_to,
606 typename _Proj1 = identity, typename _Proj2 = identity>
607 requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2>
608 constexpr subrange<_Iter1>
609 operator()(_Iter1 __first1, _Sent1 __last1,
610 _Iter2 __first2, _Sent2 __last2, _Pred __pred = {},
611 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
612 {
613 if (__first1 == __last1 || __first2 == __last2)
614 return {__first1, __first1};
615
616 for (;;)
617 {
618 for (;;)
619 {
620 if (__first1 == __last1)
621 return {__first1, __first1};
622 if (std::__invoke(__pred,
623 std::__invoke(__proj1, *__first1),
624 std::__invoke(__proj2, *__first2)))
625 break;
626 ++__first1;
627 }
628 auto __cur1 = __first1;
629 auto __cur2 = __first2;
630 for (;;)
631 {
632 if (++__cur2 == __last2)
633 return {__first1, ++__cur1};
634 if (++__cur1 == __last1)
635 return {__cur1, __cur1};
636 if (!(bool)std::__invoke(__pred,
637 std::__invoke(__proj1, *__cur1),
638 std::__invoke(__proj2, *__cur2)))
639 {
640 ++__first1;
641 break;
642 }
643 }
644 }
645 }
646
647 template<forward_range _Range1, forward_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 borrowed_subrange_t<_Range1>
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 __search_fn search{};
664
665 struct __min_fn
666 {
667 template<typename _Tp, typename _Proj = identity,
668 indirect_strict_weak_order<projected<const _Tp*, _Proj>>
669 _Comp = ranges::less>
670 constexpr const _Tp&
671 operator()(const _Tp& __a, const _Tp& __b,
672 _Comp __comp = {}, _Proj __proj = {}) const
673 {
674 if (std::__invoke(__comp,
675 std::__invoke(__proj, __b),
676 std::__invoke(__proj, __a)))
677 return __b;
678 else
679 return __a;
680 }
681
682 template<input_range _Range, typename _Proj = identity,
683 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
684 _Comp = ranges::less>
685 requires indirectly_copyable_storable<iterator_t<_Range>,
686 range_value_t<_Range>*>
687 constexpr range_value_t<_Range>
688 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
689 {
690 auto __first = ranges::begin(__r);
691 auto __last = ranges::end(__r);
692 __glibcxx_assert(__first != __last);
693 auto __result = *__first;
694 while (++__first != __last)
695 {
696 auto __tmp = *__first;
697 if (std::__invoke(__comp,
698 std::__invoke(__proj, __tmp),
699 std::__invoke(__proj, __result)))
700 __result = std::move(__tmp);
701 }
702 return __result;
703 }
704
705 template<copyable _Tp, typename _Proj = identity,
706 indirect_strict_weak_order<projected<const _Tp*, _Proj>>
707 _Comp = ranges::less>
708 constexpr _Tp
709 operator()(initializer_list<_Tp> __r,
710 _Comp __comp = {}, _Proj __proj = {}) const
711 {
712 return (*this)(ranges::subrange(__r),
713 std::move(__comp), std::move(__proj));
714 }
715 };
716
717 inline constexpr __min_fn min{};
718
719 struct __adjacent_find_fn
720 {
721 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
722 typename _Proj = identity,
723 indirect_binary_predicate<projected<_Iter, _Proj>,
724 projected<_Iter, _Proj>> _Pred
725 = ranges::equal_to>
726 constexpr _Iter
727 operator()(_Iter __first, _Sent __last,
728 _Pred __pred = {}, _Proj __proj = {}) const
729 {
730 if (__first == __last)
731 return __first;
732 auto __next = __first;
733 for (; ++__next != __last; __first = __next)
734 {
735 if (std::__invoke(__pred,
736 std::__invoke(__proj, *__first),
737 std::__invoke(__proj, *__next)))
738 return __first;
739 }
740 return __next;
741 }
742
743 template<forward_range _Range, typename _Proj = identity,
744 indirect_binary_predicate<
745 projected<iterator_t<_Range>, _Proj>,
746 projected<iterator_t<_Range>, _Proj>> _Pred = ranges::equal_to>
747 constexpr borrowed_iterator_t<_Range>
748 operator()(_Range&& __r, _Pred __pred = {}, _Proj __proj = {}) const
749 {
750 return (*this)(ranges::begin(__r), ranges::end(__r),
751 std::move(__pred), std::move(__proj));
752 }
753 };
754
755 inline constexpr __adjacent_find_fn adjacent_find{};
756
757} // namespace ranges
758
759 using ranges::get;
760
761 template<typename _Iter, typename _Sent, ranges::subrange_kind _Kind>
762 struct tuple_size<ranges::subrange<_Iter, _Sent, _Kind>>
763 : integral_constant<size_t, 2>
764 { };
765
766 template<typename _Iter, typename _Sent, ranges::subrange_kind _Kind>
767 struct tuple_element<0, ranges::subrange<_Iter, _Sent, _Kind>>
768 { using type = _Iter; };
769
770 template<typename _Iter, typename _Sent, ranges::subrange_kind _Kind>
771 struct tuple_element<1, ranges::subrange<_Iter, _Sent, _Kind>>
772 { using type = _Sent; };
773
774 template<typename _Iter, typename _Sent, ranges::subrange_kind _Kind>
775 struct tuple_element<0, const ranges::subrange<_Iter, _Sent, _Kind>>
776 { using type = _Iter; };
777
778 template<typename _Iter, typename _Sent, ranges::subrange_kind _Kind>
779 struct tuple_element<1, const ranges::subrange<_Iter, _Sent, _Kind>>
780 { using type = _Sent; };
781
782_GLIBCXX_END_NAMESPACE_VERSION
783} // namespace std
784#endif // library concepts
785#endif // C++20
786#endif // _RANGES_UTIL_H
constexpr _Tp * to_address(_Tp *__ptr) noexcept
Obtain address referenced by a pointer to an object.
Definition: ptr_traits.h:247
typename remove_pointer< _Tp >::type remove_pointer_t
Alias template for remove_pointer.
Definition: type_traits:2065
typename decay< _Tp >::type decay_t
Alias template for decay.
Definition: type_traits:2606
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
Definition: move.h:104
constexpr __invoke_result< _Callable, _Args... >::type __invoke(_Callable &&__fn, _Args &&... __args) noexcept(__is_nothrow_invocable< _Callable, _Args... >::value)
Invoke a callable object.
Definition: invoke.h:90
_Tp * end(valarray< _Tp > &__va) noexcept
Return an iterator pointing to one past the last element of the valarray.
Definition: valarray:1241
_Tp * begin(valarray< _Tp > &__va) noexcept
Return an iterator pointing to the first element of the valarray.
Definition: valarray:1219
ISO C++ entities toplevel namespace is std.
constexpr auto empty(const _Container &__cont) noexcept(noexcept(__cont.empty())) -> decltype(__cont.empty())
Return whether a container is empty.
Definition: range_access.h:284
constexpr auto size(const _Container &__cont) noexcept(noexcept(__cont.size())) -> decltype(__cont.size())
Return the size of a container.
Definition: range_access.h:264
integral_constant
Definition: type_traits:63
The ranges::view_interface class template.
Definition: ranges_util.h:65
The ranges::subrange class template.
Definition: ranges_util.h:241
Finds the size of a given tuple type.
Definition: utility.h:49
[concept.derived], concept derived_from
Definition: concepts:67
[concept.convertible], concept convertible_to
Definition: concepts:72
[concept.defaultinitializable], concept default_initializable
Definition: concepts:157
[range.range] The range concept.
Definition: ranges_base.h:584
[range.range] The borrowed_range concept.
Definition: ranges_base.h:593
[range.sized] The sized_range concept.
Definition: ranges_base.h:616
[range.view] The ranges::view concept.
Definition: ranges_base.h:651
A range for which ranges::begin returns a forward iterator.
Definition: ranges_base.h:667
A range for which ranges::begin returns a bidirectional iterator.
Definition: ranges_base.h:672
A range for which ranges::begin and ranges::end return the same type.
Definition: ranges_base.h:691