65#if __cplusplus >= 201103L
71namespace std _GLIBCXX_VISIBILITY(default)
73_GLIBCXX_BEGIN_NAMESPACE_VERSION
76 template<
typename _Iterator,
typename _Compare>
80 _Iterator __c, _Compare __comp)
85 std::iter_swap(__result, __b);
86 else if (__comp(__a, __c))
87 std::iter_swap(__result, __c);
89 std::iter_swap(__result, __a);
91 else if (__comp(__a, __c))
92 std::iter_swap(__result, __a);
93 else if (__comp(__b, __c))
94 std::iter_swap(__result, __c);
96 std::iter_swap(__result, __b);
100 template<
typename _InputIterator,
typename _Predicate>
102 inline _InputIterator
107 __gnu_cxx::__ops::__negate(
__pred),
114 template<
typename _InputIterator,
typename _Predicate,
typename _Distance>
138 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
139 typename _BinaryPredicate>
142 __search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
143 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
144 _BinaryPredicate __predicate)
147 if (__first1 == __last1 || __first2 == __last2)
151 _ForwardIterator2 __p1(__first2);
152 if (++__p1 == __last2)
154 __gnu_cxx::__ops::__iter_comp_iter(__predicate, __first2));
157 _ForwardIterator1 __current = __first1;
163 __gnu_cxx::__ops::__iter_comp_iter(__predicate, __first2));
165 if (__first1 == __last1)
168 _ForwardIterator2 __p = __p1;
169 __current = __first1;
170 if (++__current == __last1)
173 while (__predicate(__current, __p))
175 if (++__p == __last2)
177 if (++__current == __last1)
190 template<
typename _ForwardIterator,
typename _Integer,
191 typename _UnaryPredicate>
199 while (__first != __last)
223 template<
typename _RandomAccessIter,
typename _Integer,
224 typename _UnaryPredicate>
247 return (__first - __count);
254 template<
typename _ForwardIterator,
typename _Integer,
255 typename _UnaryPredicate>
258 __search_n(_ForwardIterator __first, _ForwardIterator __last,
260 _UnaryPredicate __unary_pred)
273 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
274 typename _BinaryPredicate>
277 __find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
278 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
279 forward_iterator_tag, forward_iterator_tag,
280 _BinaryPredicate __comp)
282 if (__first2 == __last2)
285 _ForwardIterator1 __result = __last1;
288 _ForwardIterator1 __new_result
289 = std::__search(__first1, __last1, __first2, __last2, __comp);
290 if (__new_result == __last1)
294 __result = __new_result;
295 __first1 = __new_result;
302 template<
typename _BidirectionalIterator1,
typename _BidirectionalIterator2,
303 typename _BinaryPredicate>
305 _BidirectionalIterator1
306 __find_end(_BidirectionalIterator1 __first1,
307 _BidirectionalIterator1 __last1,
308 _BidirectionalIterator2 __first2,
309 _BidirectionalIterator2 __last2,
310 bidirectional_iterator_tag, bidirectional_iterator_tag,
311 _BinaryPredicate __comp)
314 __glibcxx_function_requires(_BidirectionalIteratorConcept<
315 _BidirectionalIterator1>)
316 __glibcxx_function_requires(_BidirectionalIteratorConcept<
317 _BidirectionalIterator2>)
319 typedef reverse_iterator<_BidirectionalIterator1> _RevIterator1;
320 typedef reverse_iterator<_BidirectionalIterator2> _RevIterator2;
322 _RevIterator1 __rlast1(__first1);
323 _RevIterator2 __rlast2(__first2);
324 _RevIterator1 __rresult =
std::__search(_RevIterator1(__last1), __rlast1,
325 _RevIterator2(__last2), __rlast2,
328 if (__rresult == __rlast1)
332 _BidirectionalIterator1 __result = __rresult.base();
364 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
366 inline _ForwardIterator1
373 __glibcxx_function_requires(_EqualOpConcept<
382 __gnu_cxx::__ops::__iter_equal_to_iter());
413 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
414 typename _BinaryPredicate>
416 inline _ForwardIterator1
433 __gnu_cxx::__ops::__iter_comp_iter(__comp));
436#if __cplusplus >= 201103L
449 template<
typename _InputIterator,
typename _Predicate>
453 {
return __last == std::find_if_not(__first, __last,
__pred); }
467 template<
typename _InputIterator,
typename _Predicate>
471 {
return __last == _GLIBCXX_STD_A::find_if(__first, __last,
__pred); }
486 template<
typename _InputIterator,
typename _Predicate>
490 {
return !std::none_of(__first, __last,
__pred); }
502 template<
typename _InputIterator,
typename _Predicate>
504 inline _InputIterator
510 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
512 __glibcxx_requires_valid_range(__first, __last);
514 __gnu_cxx::__ops::__pred_iter(
__pred));
527 template<
typename _InputIterator,
typename _Predicate>
533 __first = std::find_if_not(__first, __last,
__pred);
534 if (__first == __last)
537 return std::none_of(__first, __last,
__pred);
549 template<
typename _ForwardIterator,
typename _Predicate>
557 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
561 __glibcxx_requires_valid_range(__first, __last);
586 template<
typename _InputIterator,
typename _OutputIterator,
590 __remove_copy_if(_InputIterator __first, _InputIterator __last,
591 _OutputIterator __result, _Predicate __pred)
593 for (; __first != __last; ++__first)
594 if (!__pred(__first))
596 *__result = *__first;
616 template<
typename _InputIterator,
typename _OutputIterator,
typename _Tp>
618 inline _OutputIterator
620 _OutputIterator __result,
const _Tp& __value)
624 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
626 __glibcxx_function_requires(_EqualOpConcept<
628 __glibcxx_requires_valid_range(__first, __last);
630 return std::__remove_copy_if(__first, __last, __result,
631 __gnu_cxx::__ops::__iter_equals_val(__value));
649 template<
typename _InputIterator,
typename _OutputIterator,
652 inline _OutputIterator
654 _OutputIterator __result, _Predicate
__pred)
658 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
660 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
662 __glibcxx_requires_valid_range(__first, __last);
664 return std::__remove_copy_if(__first, __last, __result,
665 __gnu_cxx::__ops::__pred_iter(
__pred));
668#if __cplusplus >= 201103L
684 template<
typename _InputIterator,
typename _OutputIterator,
689 _OutputIterator __result, _Predicate
__pred)
693 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
695 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
697 __glibcxx_requires_valid_range(__first, __last);
699 for (; __first != __last; ++__first)
702 *__result = *__first;
708 template<
typename _InputIterator,
typename _Size,
typename _OutputIterator>
711 __copy_n(_InputIterator __first, _Size __n,
712 _OutputIterator __result, input_iterator_tag)
714 return std::__niter_wrap(__result,
715 __copy_n_a(__first, __n,
716 std::__niter_base(__result),
true));
719 template<
typename _RandomAccessIterator,
typename _Size,
720 typename _OutputIterator>
722 inline _OutputIterator
723 __copy_n(_RandomAccessIterator __first, _Size __n,
724 _OutputIterator __result, random_access_iterator_tag)
725 {
return std::copy(__first, __first + __n, __result); }
740 template<
typename _InputIterator,
typename _Size,
typename _OutputIterator>
742 inline _OutputIterator
747 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
750 const auto __n2 = std::__size_to_integer(__n);
754 __glibcxx_requires_can_increment(__first,
__n2);
755 __glibcxx_requires_can_increment(__result,
__n2);
757 return std::__copy_n(__first,
__n2, __result,
776 template<
typename _InputIterator,
typename _OutputIterator1,
777 typename _OutputIterator2,
typename _Predicate>
779 pair<_OutputIterator1, _OutputIterator2>
790 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
792 __glibcxx_requires_valid_range(__first, __last);
794 for (; __first != __last; ++__first)
810 template<
typename _ForwardIterator,
typename _Predicate>
813 __remove_if(_ForwardIterator __first, _ForwardIterator __last,
817 if (__first == __last)
819 _ForwardIterator __result = __first;
821 for (; __first != __last; ++__first)
822 if (!__pred(__first))
824 *__result = _GLIBCXX_MOVE(*__first);
847 template<
typename _ForwardIterator,
typename _Tp>
849 inline _ForwardIterator
854 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
856 __glibcxx_function_requires(_EqualOpConcept<
858 __glibcxx_requires_valid_range(__first, __last);
860 return std::__remove_if(__first, __last,
861 __gnu_cxx::__ops::__iter_equals_val(__value));
881 template<
typename _ForwardIterator,
typename _Predicate>
883 inline _ForwardIterator
888 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
890 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
892 __glibcxx_requires_valid_range(__first, __last);
894 return std::__remove_if(__first, __last,
895 __gnu_cxx::__ops::__pred_iter(
__pred));
898 template<
typename _ForwardIterator,
typename _BinaryPredicate>
901 __adjacent_find(_ForwardIterator __first, _ForwardIterator __last,
902 _BinaryPredicate __binary_pred)
904 if (__first == __last)
906 _ForwardIterator __next = __first;
907 while (++__next != __last)
909 if (__binary_pred(__first, __next))
916 template<
typename _ForwardIterator,
typename _BinaryPredicate>
919 __unique(_ForwardIterator __first, _ForwardIterator __last,
920 _BinaryPredicate __binary_pred)
923 __first = std::__adjacent_find(__first, __last, __binary_pred);
924 if (__first == __last)
928 _ForwardIterator __dest = __first;
930 while (++__first != __last)
931 if (!__binary_pred(__dest, __first))
932 *++__dest = _GLIBCXX_MOVE(*__first);
950 template<
typename _ForwardIterator>
952 inline _ForwardIterator
956 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
958 __glibcxx_function_requires(_EqualityComparableConcept<
960 __glibcxx_requires_valid_range(__first, __last);
962 return std::__unique(__first, __last,
963 __gnu_cxx::__ops::__iter_equal_to_iter());
981 template<
typename _ForwardIterator,
typename _BinaryPredicate>
983 inline _ForwardIterator
988 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
993 __glibcxx_requires_valid_range(__first, __last);
995 return std::__unique(__first, __last,
1005 template<
typename _ForwardIterator,
typename _OutputIterator,
1006 typename _BinaryPredicate>
1007 _GLIBCXX20_CONSTEXPR
1019 *__result = *__first;
1020 while (++__next != __last)
1024 *++__result = *__first;
1035 template<
typename _InputIterator,
typename _OutputIterator,
1036 typename _BinaryPredicate>
1037 _GLIBCXX20_CONSTEXPR
1052 *__result = __value;
1053 while (++__first != __last)
1057 *++__result = __value;
1068 template<
typename _InputIterator,
typename _ForwardIterator,
1069 typename _BinaryPredicate>
1070 _GLIBCXX20_CONSTEXPR
1080 *__result = *__first;
1081 while (++__first != __last)
1083 *++__result = *__first;
1092 template<
typename _B
idirectionalIterator>
1093 _GLIBCXX20_CONSTEXPR
1099 if (__first == __last || __first == --__last)
1103 std::iter_swap(__first, __last);
1113 template<
typename _RandomAccessIterator>
1114 _GLIBCXX20_CONSTEXPR
1119 if (__first == __last)
1122 while (__first < __last)
1124 std::iter_swap(__first, __last);
1142 template<
typename _B
idirectionalIterator>
1143 _GLIBCXX20_CONSTEXPR
1148 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
1150 __glibcxx_requires_valid_range(__first, __last);
1170 template<
typename _B
idirectionalIterator,
typename _OutputIterator>
1171 _GLIBCXX20_CONSTEXPR
1174 _OutputIterator __result)
1177 __glibcxx_function_requires(_BidirectionalIteratorConcept<
1179 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1181 __glibcxx_requires_valid_range(__first, __last);
1183 while (__first != __last)
1186 *__result = *__last;
1196 template<
typename _Eucl
ideanRingElement>
1197 _GLIBCXX20_CONSTEXPR
1198 _EuclideanRingElement
1210 inline namespace _V2
1214 template<
typename _ForwardIterator>
1215 _GLIBCXX20_CONSTEXPR
1222 if (__first == __middle)
1224 else if (__last == __middle)
1233 if (__first == __middle)
1247 if (__first == __middle)
1256 template<
typename _B
idirectionalIterator>
1265 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
1268 if (__first == __middle)
1270 else if (__last == __middle)
1276 while (__first != __middle && __middle != __last)
1278 std::iter_swap(__first, --__last);
1282 if (__first == __middle)
1295 template<
typename _RandomAccessIterator>
1304 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
1307 if (__first == __middle)
1309 else if (__last == __middle)
1322 std::swap_ranges(__first, __middle, __middle);
1335 _ValueType __t = _GLIBCXX_MOVE(*__p);
1336 _GLIBCXX_MOVE3(__p + 1, __p + __n, __p);
1337 *(__p + __n - 1) = _GLIBCXX_MOVE(__t);
1343 std::iter_swap(__p, __q);
1358 _ValueType __t = _GLIBCXX_MOVE(*(__p + __n - 1));
1359 _GLIBCXX_MOVE_BACKWARD3(__p, __p + __n - 1, __p + __n);
1360 *__p = _GLIBCXX_MOVE(__t);
1369 std::iter_swap(__p, __q);
1402 template<
typename _ForwardIterator>
1409 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1411 __glibcxx_requires_valid_range(__first, __middle);
1412 __glibcxx_requires_valid_range(__middle, __last);
1440 template<
typename _ForwardIterator,
typename _OutputIterator>
1441 _GLIBCXX20_CONSTEXPR
1442 inline _OutputIterator
1448 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1450 __glibcxx_requires_valid_range(__first, __middle);
1451 __glibcxx_requires_valid_range(__middle, __last);
1453 return std::copy(__first, __middle,
1454 std::copy(__middle, __last, __result));
1458 template<
typename _ForwardIterator,
typename _Predicate>
1459 _GLIBCXX20_CONSTEXPR
1464 if (__first == __last)
1468 if (++__first == __last)
1473 while (++__next != __last)
1476 std::iter_swap(__first, __next);
1484 template<
typename _B
idirectionalIterator,
typename _Predicate>
1485 _GLIBCXX20_CONSTEXPR
1486 _BidirectionalIterator
1493 if (__first == __last)
1495 else if (
__pred(*__first))
1501 if (__first == __last)
1503 else if (!
bool(
__pred(*__last)))
1507 std::iter_swap(__first, __last);
1520 template<
typename _ForwardIterator,
typename _Pointer,
typename _Predicate,
1543 for (; __first != __last; ++__first)
1581 template<
typename _ForwardIterator,
typename _Predicate>
1583 __stable_partition(_ForwardIterator __first, _ForwardIterator __last,
1588 if (__first == __last)
1591 typedef typename iterator_traits<_ForwardIterator>::value_type
1593 typedef typename iterator_traits<_ForwardIterator>::difference_type
1596 _Temporary_buffer<_ForwardIterator, _ValueType>
1600 _DistanceType(__buf.requested_size()),
1602 _DistanceType(__buf.size()));
1622 template<
typename _ForwardIterator,
typename _Predicate>
1623 inline _ForwardIterator
1628 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1630 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
1632 __glibcxx_requires_valid_range(__first, __last);
1634 return std::__stable_partition(__first, __last,
1635 __gnu_cxx::__ops::__pred_iter(
__pred));
1639 template<
typename _RandomAccessIterator,
typename _Compare>
1640 _GLIBCXX20_CONSTEXPR
1646 std::__make_heap(__first, __middle, __comp);
1648 if (__comp(__i, __first))
1649 std::__pop_heap(__first, __middle, __i, __comp);
1654 template<
typename _InputIterator,
typename _RandomAccessIterator,
1656 _GLIBCXX20_CONSTEXPR
1657 _RandomAccessIterator
1658 __partial_sort_copy(_InputIterator __first, _InputIterator __last,
1659 _RandomAccessIterator __result_first,
1660 _RandomAccessIterator __result_last,
1663 typedef typename iterator_traits<_InputIterator>::value_type
1665 typedef iterator_traits<_RandomAccessIterator> _RItTraits;
1666 typedef typename _RItTraits::difference_type _DistanceType;
1668 if (__result_first == __result_last)
1669 return __result_last;
1670 _RandomAccessIterator __result_real_last = __result_first;
1671 while (__first != __last && __result_real_last != __result_last)
1673 *__result_real_last = *__first;
1674 ++__result_real_last;
1678 std::__make_heap(__result_first, __result_real_last, __comp);
1679 while (__first != __last)
1681 if (__comp(__first, __result_first))
1682 std::__adjust_heap(__result_first, _DistanceType(0),
1683 _DistanceType(__result_real_last
1685 _InputValueType(*__first), __comp);
1688 std::__sort_heap(__result_first, __result_real_last, __comp);
1689 return __result_real_last;
1710 template<
typename _InputIterator,
typename _RandomAccessIterator>
1711 _GLIBCXX20_CONSTEXPR
1712 inline _RandomAccessIterator
1717#ifdef _GLIBCXX_CONCEPT_CHECKS
1731 __glibcxx_requires_valid_range(__first, __last);
1732 __glibcxx_requires_irreflexive(__first, __last);
1735 return std::__partial_sort_copy(__first, __last,
1737 __gnu_cxx::__ops::__iter_less_iter());
1760 template<
typename _InputIterator,
typename _RandomAccessIterator,
1762 _GLIBCXX20_CONSTEXPR
1763 inline _RandomAccessIterator
1769#ifdef _GLIBCXX_CONCEPT_CHECKS
1778 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
1782 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
1784 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
1786 __glibcxx_requires_valid_range(__first, __last);
1787 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
1790 return std::__partial_sort_copy(__first, __last,
1792 __gnu_cxx::__ops::__iter_comp_iter(__comp));
1796 template<
typename _RandomAccessIterator,
typename _Compare>
1797 _GLIBCXX20_CONSTEXPR
1803 __val = _GLIBCXX_MOVE(*__last);
1806 while (__comp(__val, __next))
1808 *__last = _GLIBCXX_MOVE(*__next);
1812 *__last = _GLIBCXX_MOVE(__val);
1816 template<
typename _RandomAccessIterator,
typename _Compare>
1817 _GLIBCXX20_CONSTEXPR
1822 if (__first == __last)
return;
1826 if (__comp(__i, __first))
1829 __val = _GLIBCXX_MOVE(*__i);
1830 _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1);
1831 *__first = _GLIBCXX_MOVE(__val);
1835 __gnu_cxx::__ops::__val_comp_iter(__comp));
1840 template<
typename _RandomAccessIterator,
typename _Compare>
1841 _GLIBCXX20_CONSTEXPR
1848 __gnu_cxx::__ops::__val_comp_iter(__comp));
1855 enum { _S_threshold = 16 };
1858 template<
typename _RandomAccessIterator,
typename _Compare>
1859 _GLIBCXX20_CONSTEXPR
1864 if (__last - __first >
int(_S_threshold))
1875 template<
typename _RandomAccessIterator,
typename _Compare>
1876 _GLIBCXX20_CONSTEXPR
1877 _RandomAccessIterator
1884 while (__comp(__first,
__pivot))
1887 while (__comp(
__pivot, __last))
1889 if (!(__first < __last))
1891 std::iter_swap(__first, __last);
1897 template<
typename _RandomAccessIterator,
typename _Compare>
1898 _GLIBCXX20_CONSTEXPR
1899 inline _RandomAccessIterator
1909 template<
typename _RandomAccessIterator,
typename _Compare>
1910 _GLIBCXX20_CONSTEXPR
1912 __partial_sort(_RandomAccessIterator __first,
1913 _RandomAccessIterator __middle,
1914 _RandomAccessIterator __last,
1918 std::__sort_heap(__first, __middle, __comp);
1922 template<
typename _RandomAccessIterator,
typename _Size,
typename _Compare>
1923 _GLIBCXX20_CONSTEXPR
1929 while (__last - __first >
int(_S_threshold))
1933 std::__partial_sort(__first, __last, __last, __comp);
1946 template<
typename _RandomAccessIterator,
typename _Compare>
1947 _GLIBCXX20_CONSTEXPR
1949 __sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
1952 if (__first != __last)
1961 template<
typename _RandomAccessIterator,
typename _Size,
typename _Compare>
1962 _GLIBCXX20_CONSTEXPR
1964 __introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth,
1965 _RandomAccessIterator __last, _Size __depth_limit,
1968 while (__last - __first > 3)
1970 if (__depth_limit == 0)
1974 std::iter_swap(__first, __nth);
1978 _RandomAccessIterator __cut =
2008 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2009 _GLIBCXX20_CONSTEXPR
2010 inline _ForwardIterator
2012 const _Tp& __val, _Compare __comp)
2016 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2018 __glibcxx_requires_partitioned_lower_pred(__first, __last,
2021 return std::__lower_bound(__first, __last, __val,
2022 __gnu_cxx::__ops::__iter_comp_val(__comp));
2025 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2026 _GLIBCXX20_CONSTEXPR
2028 __upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2029 const _Tp& __val, _Compare __comp)
2031 typedef typename iterator_traits<_ForwardIterator>::difference_type
2038 _DistanceType __half = __len >> 1;
2039 _ForwardIterator __middle = __first;
2041 if (__comp(__val, __middle))
2047 __len = __len - __half - 1;
2064 template<
typename _ForwardIterator,
typename _Tp>
2065 _GLIBCXX20_CONSTEXPR
2066 inline _ForwardIterator
2072 __glibcxx_function_requires(_LessThanOpConcept<
2074 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2076 return std::__upper_bound(__first, __last, __val,
2077 __gnu_cxx::__ops::__val_less_iter());
2095 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2096 _GLIBCXX20_CONSTEXPR
2097 inline _ForwardIterator
2099 const _Tp& __val, _Compare __comp)
2103 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2105 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2108 return std::__upper_bound(__first, __last, __val,
2109 __gnu_cxx::__ops::__val_comp_iter(__comp));
2112 template<
typename _ForwardIterator,
typename _Tp,
2113 typename _CompareItTp,
typename _CompareTpIt>
2114 _GLIBCXX20_CONSTEXPR
2115 pair<_ForwardIterator, _ForwardIterator>
2116 __equal_range(_ForwardIterator __first, _ForwardIterator __last,
2118 _CompareItTp __comp_it_val, _CompareTpIt __comp_val_it)
2120 typedef typename iterator_traits<_ForwardIterator>::difference_type
2127 _DistanceType __half = __len >> 1;
2128 _ForwardIterator __middle = __first;
2130 if (__comp_it_val(__middle, __val))
2134 __len = __len - __half - 1;
2136 else if (__comp_val_it(__val, __middle))
2140 _ForwardIterator __left
2141 = std::__lower_bound(__first, __middle, __val, __comp_it_val);
2143 _ForwardIterator __right
2144 = std::__upper_bound(++__middle, __first, __val, __comp_val_it);
2145 return pair<_ForwardIterator, _ForwardIterator>(__left, __right);
2148 return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
2168 template<
typename _ForwardIterator,
typename _Tp>
2169 _GLIBCXX20_CONSTEXPR
2170 inline pair<_ForwardIterator, _ForwardIterator>
2176 __glibcxx_function_requires(_LessThanOpConcept<
2178 __glibcxx_function_requires(_LessThanOpConcept<
2180 __glibcxx_requires_partitioned_lower(__first, __last, __val);
2181 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2183 return std::__equal_range(__first, __last, __val,
2184 __gnu_cxx::__ops::__iter_less_val(),
2185 __gnu_cxx::__ops::__val_less_iter());
2205 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2206 _GLIBCXX20_CONSTEXPR
2207 inline pair<_ForwardIterator, _ForwardIterator>
2209 const _Tp& __val, _Compare __comp)
2213 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2215 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2217 __glibcxx_requires_partitioned_lower_pred(__first, __last,
2219 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2222 return std::__equal_range(__first, __last, __val,
2223 __gnu_cxx::__ops::__iter_comp_val(__comp),
2224 __gnu_cxx::__ops::__val_comp_iter(__comp));
2239 template<
typename _ForwardIterator,
typename _Tp>
2240 _GLIBCXX20_CONSTEXPR
2247 __glibcxx_function_requires(_LessThanOpConcept<
2249 __glibcxx_requires_partitioned_lower(__first, __last, __val);
2250 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2253 = std::__lower_bound(__first, __last, __val,
2254 __gnu_cxx::__ops::__iter_less_val());
2255 return __i != __last && !(__val < *__i);
2273 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2274 _GLIBCXX20_CONSTEXPR
2277 const _Tp& __val, _Compare __comp)
2281 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2283 __glibcxx_requires_partitioned_lower_pred(__first, __last,
2285 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2289 = std::__lower_bound(__first, __last, __val,
2290 __gnu_cxx::__ops::__iter_comp_val(__comp));
2291 return __i != __last && !bool(__comp(__val, *__i));
2297 template<
typename _InputIterator1,
typename _InputIterator2,
2298 typename _OutputIterator,
typename _Compare>
2302 _OutputIterator __result, _Compare __comp)
2308 *__result = _GLIBCXX_MOVE(*
__first2);
2313 *__result = _GLIBCXX_MOVE(*
__first1);
2323 template<
typename _BidirectionalIterator1,
typename _BidirectionalIterator2,
2324 typename _BidirectionalIterator3,
typename _Compare>
2347 *--__result = _GLIBCXX_MOVE(*
__last1);
2357 *--__result = _GLIBCXX_MOVE(*
__last2);
2366 template<
typename _BidirectionalIterator1,
typename _BidirectionalIterator2,
2368 _BidirectionalIterator1
2382 _GLIBCXX_MOVE_BACKWARD3(__first, __middle, __last);
2393 _GLIBCXX_MOVE3(__middle, __last, __first);
2400 return std::rotate(__first, __middle, __last);
2404 template<
typename _BidirectionalIterator,
typename _Distance,
2405 typename _Pointer,
typename _Compare>
2437 = std::__lower_bound(__middle, __last, *
__first_cut,
2438 __gnu_cxx::__ops::__iter_comp_val(__comp));
2447 __gnu_cxx::__ops::__val_comp_iter(__comp));
2465 template<
typename _BidirectionalIterator,
typename _Distance,
2479 if (__comp(__middle, __first))
2480 std::iter_swap(__first, __middle);
2493 = std::__lower_bound(__middle, __last, *
__first_cut,
2494 __gnu_cxx::__ops::__iter_comp_val(__comp));
2503 __gnu_cxx::__ops::__val_comp_iter(__comp));
2515 template<
typename _B
idirectionalIterator,
typename _Compare>
2517 __inplace_merge(_BidirectionalIterator __first,
2518 _BidirectionalIterator __middle,
2519 _BidirectionalIterator __last,
2522 typedef typename iterator_traits<_BidirectionalIterator>::value_type
2524 typedef typename iterator_traits<_BidirectionalIterator>::difference_type
2526 typedef _Temporary_buffer<_BidirectionalIterator, _ValueType> _TmpBuf;
2528 if (__first == __middle || __middle == __last)
2531 const _DistanceType __len1 =
std::distance(__first, __middle);
2532 const _DistanceType __len2 =
std::distance(__middle, __last);
2536 _TmpBuf __buf(__first,
std::min(__len1, __len2));
2538 if (__buf.begin() == 0)
2540 (__first, __middle, __last, __len1, __len2, __comp);
2543 (__first, __middle, __last, __len1, __len2, __buf.begin(),
2544 _DistanceType(__buf.size()), __comp);
2565 template<
typename _B
idirectionalIterator>
2572 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
2574 __glibcxx_function_requires(_LessThanComparableConcept<
2576 __glibcxx_requires_sorted(__first, __middle);
2577 __glibcxx_requires_sorted(__middle, __last);
2578 __glibcxx_requires_irreflexive(__first, __last);
2580 std::__inplace_merge(__first, __middle, __last,
2581 __gnu_cxx::__ops::__iter_less_iter());
2606 template<
typename _B
idirectionalIterator,
typename _Compare>
2614 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
2616 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2619 __glibcxx_requires_sorted_pred(__first, __middle, __comp);
2620 __glibcxx_requires_sorted_pred(__middle, __last, __comp);
2621 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
2623 std::__inplace_merge(__first, __middle, __last,
2624 __gnu_cxx::__ops::__iter_comp_iter(__comp));
2629 template<
typename _InputIterator,
typename _OutputIterator,
2634 _OutputIterator __result, _Compare __comp)
2640 *__result = _GLIBCXX_MOVE(*
__first2);
2645 *__result = _GLIBCXX_MOVE(*
__first1);
2655 template<
typename _RandomAccessIterator1,
typename _RandomAccessIterator2,
2656 typename _Distance,
typename _Compare>
2658 __merge_sort_loop(_RandomAccessIterator1 __first,
2659 _RandomAccessIterator1 __last,
2660 _RandomAccessIterator2 __result, _Distance __step_size,
2663 const _Distance __two_step = 2 * __step_size;
2665 while (__last - __first >= __two_step)
2668 __first + __step_size,
2669 __first + __two_step,
2671 __first += __two_step;
2673 __step_size =
std::min(_Distance(__last - __first), __step_size);
2676 __first + __step_size, __last, __result, __comp);
2679 template<
typename _RandomAccessIterator,
typename _Distance,
2681 _GLIBCXX20_CONSTEXPR
2683 __chunk_insertion_sort(_RandomAccessIterator __first,
2684 _RandomAccessIterator __last,
2685 _Distance __chunk_size, _Compare __comp)
2687 while (__last - __first >= __chunk_size)
2690 __first += __chunk_size;
2695 enum { _S_chunk_size = 7 };
2697 template<
typename _RandomAccessIterator,
typename _Po
inter,
typename _Compare>
2699 __merge_sort_with_buffer(_RandomAccessIterator __first,
2700 _RandomAccessIterator __last,
2701 _Pointer __buffer, _Compare __comp)
2703 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
2706 const _Distance __len = __last - __first;
2707 const _Pointer __buffer_last = __buffer + __len;
2709 _Distance __step_size = _S_chunk_size;
2710 std::__chunk_insertion_sort(__first, __last, __step_size, __comp);
2712 while (__step_size < __len)
2714 std::__merge_sort_loop(__first, __last, __buffer,
2715 __step_size, __comp);
2717 std::__merge_sort_loop(__buffer, __buffer_last, __first,
2718 __step_size, __comp);
2723 template<
typename _RandomAccessIterator,
typename _Pointer,
2724 typename _Distance,
typename _Compare>
2726 __stable_sort_adaptive(_RandomAccessIterator __first,
2727 _RandomAccessIterator __last,
2728 _Pointer __buffer, _Distance __buffer_size,
2731 const _Distance __len = (__last - __first + 1) / 2;
2732 const _RandomAccessIterator __middle = __first + __len;
2733 if (__len > __buffer_size)
2735 std::__stable_sort_adaptive(__first, __middle, __buffer,
2736 __buffer_size, __comp);
2737 std::__stable_sort_adaptive(__middle, __last, __buffer,
2738 __buffer_size, __comp);
2742 std::__merge_sort_with_buffer(__first, __middle, __buffer, __comp);
2743 std::__merge_sort_with_buffer(__middle, __last, __buffer, __comp);
2747 _Distance(__middle - __first),
2748 _Distance(__last - __middle),
2749 __buffer, __buffer_size,
2754 template<
typename _RandomAccessIterator,
typename _Compare>
2759 if (__last - __first < 15)
2780 template<
typename _InputIterator1,
typename _InputIterator2,
2782 _GLIBCXX20_CONSTEXPR
2784 __includes(_InputIterator1 __first1, _InputIterator1 __last1,
2785 _InputIterator2 __first2, _InputIterator2 __last2,
2788 while (__first1 != __last1 && __first2 != __last2)
2790 if (__comp(__first2, __first1))
2792 if (!__comp(__first1, __first2))
2797 return __first2 == __last2;
2818 template<
typename _InputIterator1,
typename _InputIterator2>
2819 _GLIBCXX20_CONSTEXPR
2827 __glibcxx_function_requires(_LessThanOpConcept<
2830 __glibcxx_function_requires(_LessThanOpConcept<
2839 __gnu_cxx::__ops::__iter_less_iter());
2863 template<
typename _InputIterator1,
typename _InputIterator2,
2865 _GLIBCXX20_CONSTEXPR
2874 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2877 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2886 __gnu_cxx::__ops::__iter_comp_iter(__comp));
2899 template<
typename _B
idirectionalIterator,
typename _Compare>
2900 _GLIBCXX20_CONSTEXPR
2902 __next_permutation(_BidirectionalIterator __first,
2903 _BidirectionalIterator __last, _Compare __comp)
2905 if (__first == __last)
2907 _BidirectionalIterator __i = __first;
2916 _BidirectionalIterator __ii = __i;
2918 if (__comp(__i, __ii))
2920 _BidirectionalIterator __j = __last;
2921 while (!__comp(__i, --__j))
2923 std::iter_swap(__i, __j);
2949 template<
typename _B
idirectionalIterator>
2950 _GLIBCXX20_CONSTEXPR
2956 __glibcxx_function_requires(_BidirectionalIteratorConcept<
2958 __glibcxx_function_requires(_LessThanComparableConcept<
2960 __glibcxx_requires_valid_range(__first, __last);
2961 __glibcxx_requires_irreflexive(__first, __last);
2963 return std::__next_permutation
2964 (__first, __last, __gnu_cxx::__ops::__iter_less_iter());
2982 template<
typename _B
idirectionalIterator,
typename _Compare>
2983 _GLIBCXX20_CONSTEXPR
2989 __glibcxx_function_requires(_BidirectionalIteratorConcept<
2991 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2994 __glibcxx_requires_valid_range(__first, __last);
2995 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
2997 return std::__next_permutation
2998 (__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
3001 template<
typename _B
idirectionalIterator,
typename _Compare>
3002 _GLIBCXX20_CONSTEXPR
3004 __prev_permutation(_BidirectionalIterator __first,
3005 _BidirectionalIterator __last, _Compare __comp)
3007 if (__first == __last)
3009 _BidirectionalIterator __i = __first;
3018 _BidirectionalIterator __ii = __i;
3020 if (__comp(__ii, __i))
3022 _BidirectionalIterator __j = __last;
3023 while (!__comp(--__j, __i))
3025 std::iter_swap(__i, __j);
3052 template<
typename _B
idirectionalIterator>
3053 _GLIBCXX20_CONSTEXPR
3059 __glibcxx_function_requires(_BidirectionalIteratorConcept<
3061 __glibcxx_function_requires(_LessThanComparableConcept<
3063 __glibcxx_requires_valid_range(__first, __last);
3064 __glibcxx_requires_irreflexive(__first, __last);
3066 return std::__prev_permutation(__first, __last,
3067 __gnu_cxx::__ops::__iter_less_iter());
3085 template<
typename _B
idirectionalIterator,
typename _Compare>
3086 _GLIBCXX20_CONSTEXPR
3092 __glibcxx_function_requires(_BidirectionalIteratorConcept<
3094 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3097 __glibcxx_requires_valid_range(__first, __last);
3098 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
3100 return std::__prev_permutation(__first, __last,
3101 __gnu_cxx::__ops::__iter_comp_iter(__comp));
3107 template<
typename _InputIterator,
typename _OutputIterator,
3108 typename _Predicate,
typename _Tp>
3109 _GLIBCXX20_CONSTEXPR
3111 __replace_copy_if(_InputIterator __first, _InputIterator __last,
3112 _OutputIterator __result,
3113 _Predicate __pred,
const _Tp& __new_value)
3115 for (; __first != __last; ++__first, (void)++__result)
3116 if (__pred(__first))
3117 *__result = __new_value;
3119 *__result = *__first;
3137 template<
typename _InputIterator,
typename _OutputIterator,
typename _Tp>
3138 _GLIBCXX20_CONSTEXPR
3139 inline _OutputIterator
3141 _OutputIterator __result,
3146 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
3148 __glibcxx_function_requires(_EqualOpConcept<
3150 __glibcxx_requires_valid_range(__first, __last);
3152 return std::__replace_copy_if(__first, __last, __result,
3172 template<
typename _InputIterator,
typename _OutputIterator,
3173 typename _Predicate,
typename _Tp>
3174 _GLIBCXX20_CONSTEXPR
3175 inline _OutputIterator
3177 _OutputIterator __result,
3182 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
3184 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
3186 __glibcxx_requires_valid_range(__first, __last);
3188 return std::__replace_copy_if(__first, __last, __result,
3189 __gnu_cxx::__ops::__pred_iter(
__pred),
3193#if __cplusplus >= 201103L
3201 template<
typename _ForwardIterator>
3202 _GLIBCXX20_CONSTEXPR
3205 {
return std::is_sorted_until(__first, __last) == __last; }
3216 template<
typename _ForwardIterator,
typename _Compare>
3217 _GLIBCXX20_CONSTEXPR
3221 {
return std::is_sorted_until(__first, __last, __comp) == __last; }
3223 template<
typename _ForwardIterator,
typename _Compare>
3224 _GLIBCXX20_CONSTEXPR
3226 __is_sorted_until(_ForwardIterator __first, _ForwardIterator __last,
3229 if (__first == __last)
3232 _ForwardIterator __next = __first;
3233 for (++__next; __next != __last; __first = __next, (void)++__next)
3234 if (__comp(__next, __first))
3247 template<
typename _ForwardIterator>
3248 _GLIBCXX20_CONSTEXPR
3249 inline _ForwardIterator
3254 __glibcxx_function_requires(_LessThanComparableConcept<
3256 __glibcxx_requires_valid_range(__first, __last);
3257 __glibcxx_requires_irreflexive(__first, __last);
3259 return std::__is_sorted_until(__first, __last,
3260 __gnu_cxx::__ops::__iter_less_iter());
3272 template<
typename _ForwardIterator,
typename _Compare>
3273 _GLIBCXX20_CONSTEXPR
3274 inline _ForwardIterator
3280 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3283 __glibcxx_requires_valid_range(__first, __last);
3284 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
3286 return std::__is_sorted_until(__first, __last,
3287 __gnu_cxx::__ops::__iter_comp_iter(__comp));
3298 template<
typename _Tp>
3299 _GLIBCXX14_CONSTEXPR
3300 inline pair<const _Tp&, const _Tp&>
3319 template<
typename _Tp,
typename _Compare>
3320 _GLIBCXX14_CONSTEXPR
3321 inline pair<const _Tp&, const _Tp&>
3322 minmax(
const _Tp& __a,
const _Tp& __b, _Compare __comp)
3328 template<
typename _ForwardIterator,
typename _Compare>
3329 _GLIBCXX14_CONSTEXPR
3330 pair<_ForwardIterator, _ForwardIterator>
3331 __minmax_element(_ForwardIterator __first, _ForwardIterator __last,
3334 _ForwardIterator __next = __first;
3335 if (__first == __last
3336 || ++__next == __last)
3337 return std::make_pair(__first, __first);
3339 _ForwardIterator __min{}, __max{};
3340 if (__comp(__next, __first))
3354 while (__first != __last)
3357 if (++__next == __last)
3359 if (__comp(__first, __min))
3361 else if (!__comp(__first, __max))
3366 if (__comp(__next, __first))
3368 if (__comp(__next, __min))
3370 if (!__comp(__first, __max))
3375 if (__comp(__first, __min))
3377 if (!__comp(__next, __max))
3385 return std::make_pair(__min, __max);
3399 template<
typename _ForwardIterator>
3400 _GLIBCXX14_CONSTEXPR
3401 inline pair<_ForwardIterator, _ForwardIterator>
3406 __glibcxx_function_requires(_LessThanComparableConcept<
3408 __glibcxx_requires_valid_range(__first, __last);
3409 __glibcxx_requires_irreflexive(__first, __last);
3411 return std::__minmax_element(__first, __last,
3412 __gnu_cxx::__ops::__iter_less_iter());
3427 template<
typename _ForwardIterator,
typename _Compare>
3428 _GLIBCXX14_CONSTEXPR
3429 inline pair<_ForwardIterator, _ForwardIterator>
3435 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3438 __glibcxx_requires_valid_range(__first, __last);
3439 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
3441 return std::__minmax_element(__first, __last,
3442 __gnu_cxx::__ops::__iter_comp_iter(__comp));
3446 template<
typename _Tp>
3447 _GLIBCXX14_CONSTEXPR
3449 min(initializer_list<_Tp> __l)
3450 {
return *std::min_element(__l.begin(), __l.end()); }
3452 template<
typename _Tp,
typename _Compare>
3453 _GLIBCXX14_CONSTEXPR
3455 min(initializer_list<_Tp> __l, _Compare __comp)
3456 {
return *std::min_element(__l.begin(), __l.end(), __comp); }
3458 template<
typename _Tp>
3459 _GLIBCXX14_CONSTEXPR
3461 max(initializer_list<_Tp> __l)
3462 {
return *std::max_element(__l.begin(), __l.end()); }
3464 template<
typename _Tp,
typename _Compare>
3465 _GLIBCXX14_CONSTEXPR
3467 max(initializer_list<_Tp> __l, _Compare __comp)
3468 {
return *std::max_element(__l.begin(), __l.end(), __comp); }
3470 template<
typename _Tp>
3471 _GLIBCXX14_CONSTEXPR
3472 inline pair<_Tp, _Tp>
3473 minmax(initializer_list<_Tp> __l)
3475 pair<const _Tp*, const _Tp*> __p =
3476 std::minmax_element(__l.begin(), __l.end());
3477 return std::make_pair(*__p.first, *__p.second);
3480 template<
typename _Tp,
typename _Compare>
3481 _GLIBCXX14_CONSTEXPR
3482 inline pair<_Tp, _Tp>
3483 minmax(initializer_list<_Tp> __l, _Compare __comp)
3485 pair<const _Tp*, const _Tp*> __p =
3486 std::minmax_element(__l.begin(), __l.end(), __comp);
3487 return std::make_pair(*__p.first, *__p.second);
3504 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
3505 typename _BinaryPredicate>
3506 _GLIBCXX20_CONSTEXPR
3520 __gnu_cxx::__ops::__iter_comp_iter(
__pred));
3523#if __cplusplus > 201103L
3524 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
3525 typename _BinaryPredicate>
3526 _GLIBCXX20_CONSTEXPR
3528 __is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3529 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
3530 _BinaryPredicate __pred)
3533 =
typename iterator_traits<_ForwardIterator1>::iterator_category;
3535 =
typename iterator_traits<_ForwardIterator2>::iterator_category;
3536 using _It1_is_RA = is_same<_Cat1, random_access_iterator_tag>;
3537 using _It2_is_RA = is_same<_Cat2, random_access_iterator_tag>;
3538 constexpr bool __ra_iters = _It1_is_RA() && _It2_is_RA();
3549 for (; __first1 != __last1 && __first2 != __last2;
3550 ++__first1, (void)++__first2)
3551 if (!__pred(__first1, __first2))
3556 if (__first1 == __last1)
3563 if (__d1 == 0 && __d2 == 0)
3569 for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
3572 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)))
3575 auto __matches = std::__count_if(__first2, __last2,
3576 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan));
3578 || std::__count_if(__scan, __last1,
3579 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan))
3599 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
3600 _GLIBCXX20_CONSTEXPR
3610 __gnu_cxx::__ops::__iter_equal_to_iter());
3627 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
3628 typename _BinaryPredicate>
3629 _GLIBCXX20_CONSTEXPR
3639 __gnu_cxx::__ops::__iter_comp_iter(
__pred));
3642#if __cplusplus > 201402L
3644#define __cpp_lib_clamp 201603
3654 template<
typename _Tp>
3655 constexpr const _Tp&
3672 template<
typename _Tp,
typename _Compare>
3673 constexpr const _Tp&
3676 __glibcxx_assert(!__comp(
__hi,
__lo));
3682#ifdef _GLIBCXX_USE_C99_STDINT_TR1
3704 template<
typename _IntType,
typename _UniformRandomBitGenerator>
3705 pair<_IntType, _IntType>
3711 return std::make_pair(__x /
__b1, __x %
__b1);
3726 template<
typename _RandomAccessIterator,
3727 typename _UniformRandomNumberGenerator>
3733 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
3735 __glibcxx_requires_valid_range(__first, __last);
3737 if (__first == __last)
3743 typedef typename std::make_unsigned<_DistanceType>::type
__ud_type;
3745 typedef typename __distr_type::param_type
__p_type;
3767 std::iter_swap(__i++, __first + __d(
__g));
3774 while (__i != __last)
3781 std::iter_swap(__i++, __first +
__pospos.first);
3782 std::iter_swap(__i++, __first +
__pospos.second);
3791 std::iter_swap(__i, __first + __d(
__g,
__p_type(0, __i - __first)));
3797_GLIBCXX_BEGIN_NAMESPACE_ALGO
3811 template<
typename _InputIterator,
typename _Function>
3812 _GLIBCXX20_CONSTEXPR
3818 __glibcxx_requires_valid_range(__first, __last);
3819 for (; __first != __last; ++__first)
3824#if __cplusplus >= 201703L
3837 template<
typename _InputIterator,
typename _Size,
typename _Function>
3838 _GLIBCXX20_CONSTEXPR
3842 auto __n2 = std::__size_to_integer(__n);
3848 auto __last = __first +
__n2;
3849 std::for_each(__first, __last,
std::move(__f));
3873 template<
typename _InputIterator,
typename _Tp>
3874 _GLIBCXX20_CONSTEXPR
3875 inline _InputIterator
3881 __glibcxx_function_requires(_EqualOpConcept<
3883 __glibcxx_requires_valid_range(__first, __last);
3885 __gnu_cxx::__ops::__iter_equals_val(__val));
3898 template<
typename _InputIterator,
typename _Predicate>
3899 _GLIBCXX20_CONSTEXPR
3900 inline _InputIterator
3906 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
3908 __glibcxx_requires_valid_range(__first, __last);
3911 __gnu_cxx::__ops::__pred_iter(
__pred));
3930 template<
typename _InputIterator,
typename _ForwardIterator>
3931 _GLIBCXX20_CONSTEXPR
3939 __glibcxx_function_requires(_EqualOpConcept<
3971 template<
typename _InputIterator,
typename _ForwardIterator,
3972 typename _BinaryPredicate>
3973 _GLIBCXX20_CONSTEXPR
4004 template<
typename _ForwardIterator>
4005 _GLIBCXX20_CONSTEXPR
4006 inline _ForwardIterator
4011 __glibcxx_function_requires(_EqualityComparableConcept<
4013 __glibcxx_requires_valid_range(__first, __last);
4015 return std::__adjacent_find(__first, __last,
4016 __gnu_cxx::__ops::__iter_equal_to_iter());
4030 template<
typename _ForwardIterator,
typename _BinaryPredicate>
4031 _GLIBCXX20_CONSTEXPR
4032 inline _ForwardIterator
4041 __glibcxx_requires_valid_range(__first, __last);
4043 return std::__adjacent_find(__first, __last,
4056 template<
typename _InputIterator,
typename _Tp>
4057 _GLIBCXX20_CONSTEXPR
4058 inline typename iterator_traits<_InputIterator>::difference_type
4063 __glibcxx_function_requires(_EqualOpConcept<
4065 __glibcxx_requires_valid_range(__first, __last);
4067 return std::__count_if(__first, __last,
4068 __gnu_cxx::__ops::__iter_equals_val(__value));
4080 template<
typename _InputIterator,
typename _Predicate>
4081 _GLIBCXX20_CONSTEXPR
4082 inline typename iterator_traits<_InputIterator>::difference_type
4087 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4089 __glibcxx_requires_valid_range(__first, __last);
4091 return std::__count_if(__first, __last,
4092 __gnu_cxx::__ops::__pred_iter(
__pred));
4121 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
4122 _GLIBCXX20_CONSTEXPR
4123 inline _ForwardIterator1
4130 __glibcxx_function_requires(_EqualOpConcept<
4137 __gnu_cxx::__ops::__iter_equal_to_iter());
4161 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
4162 typename _BinaryPredicate>
4163 _GLIBCXX20_CONSTEXPR
4164 inline _ForwardIterator1
4197 template<
typename _ForwardIterator,
typename _Integer,
typename _Tp>
4198 _GLIBCXX20_CONSTEXPR
4199 inline _ForwardIterator
4201 _Integer __count,
const _Tp& __val)
4205 __glibcxx_function_requires(_EqualOpConcept<
4207 __glibcxx_requires_valid_range(__first, __last);
4209 return std::__search_n(__first, __last, __count,
4210 __gnu_cxx::__ops::__iter_equals_val(__val));
4231 template<
typename _ForwardIterator,
typename _Integer,
typename _Tp,
4232 typename _BinaryPredicate>
4233 _GLIBCXX20_CONSTEXPR
4234 inline _ForwardIterator
4236 _Integer __count,
const _Tp& __val,
4243 __glibcxx_requires_valid_range(__first, __last);
4245 return std::__search_n(__first, __last, __count,
4249#if __cplusplus >= 201703L
4257 template<
typename _ForwardIterator,
typename _Searcher>
4258 _GLIBCXX20_CONSTEXPR
4259 inline _ForwardIterator
4262 {
return __searcher(__first, __last).first; }
4281 template<
typename _InputIterator,
typename _OutputIterator,
4282 typename _UnaryOperation>
4283 _GLIBCXX20_CONSTEXPR
4290 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4293 __glibcxx_requires_valid_range(__first, __last);
4295 for (; __first != __last; ++__first, (
void)++__result)
4319 template<
typename _InputIterator1,
typename _InputIterator2,
4320 typename _OutputIterator,
typename _BinaryOperation>
4321 _GLIBCXX20_CONSTEXPR
4330 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4353 template<
typename _ForwardIterator,
typename _Tp>
4354 _GLIBCXX20_CONSTEXPR
4360 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4362 __glibcxx_function_requires(_EqualOpConcept<
4364 __glibcxx_function_requires(_ConvertibleConcept<_Tp,
4366 __glibcxx_requires_valid_range(__first, __last);
4368 for (; __first != __last; ++__first)
4386 template<
typename _ForwardIterator,
typename _Predicate,
typename _Tp>
4387 _GLIBCXX20_CONSTEXPR
4393 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4395 __glibcxx_function_requires(_ConvertibleConcept<_Tp,
4397 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4399 __glibcxx_requires_valid_range(__first, __last);
4401 for (; __first != __last; ++__first)
4419 template<
typename _ForwardIterator,
typename _Generator>
4420 _GLIBCXX20_CONSTEXPR
4427 __glibcxx_function_requires(_GeneratorConcept<
_Generator,
4429 __glibcxx_requires_valid_range(__first, __last);
4431 for (; __first != __last; ++__first)
4453 template<
typename _OutputIterator,
typename _Size,
typename _Generator>
4454 _GLIBCXX20_CONSTEXPR
4459 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4461 __typeof__(
__gen())>)
4491 template<
typename _InputIterator,
typename _OutputIterator>
4492 _GLIBCXX20_CONSTEXPR
4493 inline _OutputIterator
4495 _OutputIterator __result)
4499 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4501 __glibcxx_function_requires(_EqualityComparableConcept<
4503 __glibcxx_requires_valid_range(__first, __last);
4505 if (__first == __last)
4508 __gnu_cxx::__ops::__iter_equal_to_iter(),
4532 template<
typename _InputIterator,
typename _OutputIterator,
4533 typename _BinaryPredicate>
4534 _GLIBCXX20_CONSTEXPR
4535 inline _OutputIterator
4537 _OutputIterator __result,
4542 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4544 __glibcxx_requires_valid_range(__first, __last);
4546 if (__first == __last)
4566 template<
typename _RandomAccessIterator>
4568 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
4571 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4572 _RandomAccessIterator>)
4573 __glibcxx_requires_valid_range(__first, __last);
4575 if (__first != __last)
4576 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
4579 _RandomAccessIterator __j = __first
4582 std::iter_swap(__i, __j);
4601 template<
typename _RandomAccessIterator,
typename _RandomNumberGenerator>
4611 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4613 __glibcxx_requires_valid_range(__first, __last);
4615 if (__first == __last)
4621 std::iter_swap(__i, __j);
4641 template<
typename _ForwardIterator,
typename _Predicate>
4642 _GLIBCXX20_CONSTEXPR
4643 inline _ForwardIterator
4648 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4650 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4652 __glibcxx_requires_valid_range(__first, __last);
4675 template<
typename _RandomAccessIterator>
4676 _GLIBCXX20_CONSTEXPR
4683 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4685 __glibcxx_function_requires(_LessThanComparableConcept<
4687 __glibcxx_requires_valid_range(__first, __middle);
4688 __glibcxx_requires_valid_range(__middle, __last);
4689 __glibcxx_requires_irreflexive(__first, __last);
4691 std::__partial_sort(__first, __middle, __last,
4692 __gnu_cxx::__ops::__iter_less_iter());
4714 template<
typename _RandomAccessIterator,
typename _Compare>
4715 _GLIBCXX20_CONSTEXPR
4723 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4725 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4728 __glibcxx_requires_valid_range(__first, __middle);
4729 __glibcxx_requires_valid_range(__middle, __last);
4730 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
4732 std::__partial_sort(__first, __middle, __last,
4733 __gnu_cxx::__ops::__iter_comp_iter(__comp));
4751 template<
typename _RandomAccessIterator>
4752 _GLIBCXX20_CONSTEXPR
4758 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4760 __glibcxx_function_requires(_LessThanComparableConcept<
4762 __glibcxx_requires_valid_range(__first,
__nth);
4763 __glibcxx_requires_valid_range(
__nth, __last);
4764 __glibcxx_requires_irreflexive(__first, __last);
4766 if (__first == __last ||
__nth == __last)
4769 std::__introselect(__first,
__nth, __last,
4771 __gnu_cxx::__ops::__iter_less_iter());
4791 template<
typename _RandomAccessIterator,
typename _Compare>
4792 _GLIBCXX20_CONSTEXPR
4798 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4800 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4803 __glibcxx_requires_valid_range(__first,
__nth);
4804 __glibcxx_requires_valid_range(
__nth, __last);
4805 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
4807 if (__first == __last ||
__nth == __last)
4810 std::__introselect(__first,
__nth, __last,
4812 __gnu_cxx::__ops::__iter_comp_iter(__comp));
4829 template<
typename _RandomAccessIterator>
4830 _GLIBCXX20_CONSTEXPR
4835 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4837 __glibcxx_function_requires(_LessThanComparableConcept<
4839 __glibcxx_requires_valid_range(__first, __last);
4840 __glibcxx_requires_irreflexive(__first, __last);
4842 std::__sort(__first, __last, __gnu_cxx::__ops::__iter_less_iter());
4860 template<
typename _RandomAccessIterator,
typename _Compare>
4861 _GLIBCXX20_CONSTEXPR
4867 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4869 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4872 __glibcxx_requires_valid_range(__first, __last);
4873 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
4875 std::__sort(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
4878 template<
typename _InputIterator1,
typename _InputIterator2,
4879 typename _OutputIterator,
typename _Compare>
4880 _GLIBCXX20_CONSTEXPR
4882 __merge(_InputIterator1 __first1, _InputIterator1 __last1,
4883 _InputIterator2 __first2, _InputIterator2 __last2,
4884 _OutputIterator __result, _Compare __comp)
4886 while (__first1 != __last1 && __first2 != __last2)
4888 if (__comp(__first2, __first1))
4890 *__result = *__first2;
4895 *__result = *__first1;
4900 return std::copy(__first2, __last2,
4901 std::copy(__first1, __last1, __result));
4923 template<
typename _InputIterator1,
typename _InputIterator2,
4924 typename _OutputIterator>
4925 _GLIBCXX20_CONSTEXPR
4926 inline _OutputIterator
4929 _OutputIterator __result)
4934 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4936 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4938 __glibcxx_function_requires(_LessThanOpConcept<
4948 __gnu_cxx::__ops::__iter_less_iter());
4974 template<
typename _InputIterator1,
typename _InputIterator2,
4975 typename _OutputIterator,
typename _Compare>
4976 _GLIBCXX20_CONSTEXPR
4977 inline _OutputIterator
4980 _OutputIterator __result, _Compare __comp)
4985 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4987 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4989 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4999 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5002 template<
typename _RandomAccessIterator,
typename _Compare>
5004 __stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
5007 typedef typename iterator_traits<_RandomAccessIterator>::value_type
5009 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
5011 typedef _Temporary_buffer<_RandomAccessIterator, _ValueType> _TmpBuf;
5013 if (__first == __last)
5018 _TmpBuf __buf(__first, (__last - __first + 1) / 2);
5020 if (__buf.begin() == 0)
5023 std::__stable_sort_adaptive(__first, __last, __buf.begin(),
5024 _DistanceType(__buf.size()), __comp);
5044 template<
typename _RandomAccessIterator>
5049 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5051 __glibcxx_function_requires(_LessThanComparableConcept<
5053 __glibcxx_requires_valid_range(__first, __last);
5054 __glibcxx_requires_irreflexive(__first, __last);
5056 _GLIBCXX_STD_A::__stable_sort(__first, __last,
5057 __gnu_cxx::__ops::__iter_less_iter());
5078 template<
typename _RandomAccessIterator,
typename _Compare>
5084 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5086 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5089 __glibcxx_requires_valid_range(__first, __last);
5090 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
5092 _GLIBCXX_STD_A::__stable_sort(__first, __last,
5093 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5096 template<
typename _InputIterator1,
typename _InputIterator2,
5097 typename _OutputIterator,
5099 _GLIBCXX20_CONSTEXPR
5101 __set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5102 _InputIterator2 __first2, _InputIterator2 __last2,
5103 _OutputIterator __result, _Compare __comp)
5105 while (__first1 != __last1 && __first2 != __last2)
5107 if (__comp(__first1, __first2))
5109 *__result = *__first1;
5112 else if (__comp(__first2, __first1))
5114 *__result = *__first2;
5119 *__result = *__first1;
5125 return std::copy(__first2, __last2,
5126 std::copy(__first1, __last1, __result));
5148 template<
typename _InputIterator1,
typename _InputIterator2,
5149 typename _OutputIterator>
5150 _GLIBCXX20_CONSTEXPR
5151 inline _OutputIterator
5154 _OutputIterator __result)
5159 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5161 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5163 __glibcxx_function_requires(_LessThanOpConcept<
5166 __glibcxx_function_requires(_LessThanOpConcept<
5176 __gnu_cxx::__ops::__iter_less_iter());
5199 template<
typename _InputIterator1,
typename _InputIterator2,
5200 typename _OutputIterator,
typename _Compare>
5201 _GLIBCXX20_CONSTEXPR
5202 inline _OutputIterator
5205 _OutputIterator __result, _Compare __comp)
5210 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5212 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5214 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5217 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5227 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5230 template<
typename _InputIterator1,
typename _InputIterator2,
5231 typename _OutputIterator,
5233 _GLIBCXX20_CONSTEXPR
5235 __set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5236 _InputIterator2 __first2, _InputIterator2 __last2,
5237 _OutputIterator __result, _Compare __comp)
5239 while (__first1 != __last1 && __first2 != __last2)
5240 if (__comp(__first1, __first2))
5242 else if (__comp(__first2, __first1))
5246 *__result = *__first1;
5272 template<
typename _InputIterator1,
typename _InputIterator2,
5273 typename _OutputIterator>
5274 _GLIBCXX20_CONSTEXPR
5275 inline _OutputIterator
5278 _OutputIterator __result)
5283 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5285 __glibcxx_function_requires(_LessThanOpConcept<
5288 __glibcxx_function_requires(_LessThanOpConcept<
5298 __gnu_cxx::__ops::__iter_less_iter());
5322 template<
typename _InputIterator1,
typename _InputIterator2,
5323 typename _OutputIterator,
typename _Compare>
5324 _GLIBCXX20_CONSTEXPR
5325 inline _OutputIterator
5328 _OutputIterator __result, _Compare __comp)
5333 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5335 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5338 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5348 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5351 template<
typename _InputIterator1,
typename _InputIterator2,
5352 typename _OutputIterator,
5354 _GLIBCXX20_CONSTEXPR
5356 __set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5357 _InputIterator2 __first2, _InputIterator2 __last2,
5358 _OutputIterator __result, _Compare __comp)
5360 while (__first1 != __last1 && __first2 != __last2)
5361 if (__comp(__first1, __first2))
5363 *__result = *__first1;
5367 else if (__comp(__first2, __first1))
5374 return std::copy(__first1, __last1, __result);
5397 template<
typename _InputIterator1,
typename _InputIterator2,
5398 typename _OutputIterator>
5399 _GLIBCXX20_CONSTEXPR
5400 inline _OutputIterator
5403 _OutputIterator __result)
5408 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5410 __glibcxx_function_requires(_LessThanOpConcept<
5413 __glibcxx_function_requires(_LessThanOpConcept<
5423 __gnu_cxx::__ops::__iter_less_iter());
5449 template<
typename _InputIterator1,
typename _InputIterator2,
5450 typename _OutputIterator,
typename _Compare>
5451 _GLIBCXX20_CONSTEXPR
5452 inline _OutputIterator
5455 _OutputIterator __result, _Compare __comp)
5460 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5462 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5465 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5475 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5478 template<
typename _InputIterator1,
typename _InputIterator2,
5479 typename _OutputIterator,
5481 _GLIBCXX20_CONSTEXPR
5483 __set_symmetric_difference(_InputIterator1 __first1,
5484 _InputIterator1 __last1,
5485 _InputIterator2 __first2,
5486 _InputIterator2 __last2,
5487 _OutputIterator __result,
5490 while (__first1 != __last1 && __first2 != __last2)
5491 if (__comp(__first1, __first2))
5493 *__result = *__first1;
5497 else if (__comp(__first2, __first1))
5499 *__result = *__first2;
5508 return std::copy(__first2, __last2,
5509 std::copy(__first1, __last1, __result));
5530 template<
typename _InputIterator1,
typename _InputIterator2,
5531 typename _OutputIterator>
5532 _GLIBCXX20_CONSTEXPR
5533 inline _OutputIterator
5536 _OutputIterator __result)
5541 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5543 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5545 __glibcxx_function_requires(_LessThanOpConcept<
5548 __glibcxx_function_requires(_LessThanOpConcept<
5558 __gnu_cxx::__ops::__iter_less_iter());
5582 template<
typename _InputIterator1,
typename _InputIterator2,
5583 typename _OutputIterator,
typename _Compare>
5584 _GLIBCXX20_CONSTEXPR
5585 inline _OutputIterator
5588 _OutputIterator __result,
5594 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5596 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5598 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5601 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5611 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5614 template<
typename _ForwardIterator,
typename _Compare>
5615 _GLIBCXX14_CONSTEXPR
5617 __min_element(_ForwardIterator __first, _ForwardIterator __last,
5620 if (__first == __last)
5622 _ForwardIterator __result = __first;
5623 while (++__first != __last)
5624 if (__comp(__first, __result))
5636 template<
typename _ForwardIterator>
5637 _GLIBCXX14_CONSTEXPR
5643 __glibcxx_function_requires(_LessThanComparableConcept<
5645 __glibcxx_requires_valid_range(__first, __last);
5646 __glibcxx_requires_irreflexive(__first, __last);
5648 return _GLIBCXX_STD_A::__min_element(__first, __last,
5649 __gnu_cxx::__ops::__iter_less_iter());
5661 template<
typename _ForwardIterator,
typename _Compare>
5662 _GLIBCXX14_CONSTEXPR
5663 inline _ForwardIterator
5669 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5672 __glibcxx_requires_valid_range(__first, __last);
5673 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
5675 return _GLIBCXX_STD_A::__min_element(__first, __last,
5676 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5679 template<
typename _ForwardIterator,
typename _Compare>
5680 _GLIBCXX14_CONSTEXPR
5682 __max_element(_ForwardIterator __first, _ForwardIterator __last,
5685 if (__first == __last)
return __first;
5686 _ForwardIterator __result = __first;
5687 while (++__first != __last)
5688 if (__comp(__result, __first))
5700 template<
typename _ForwardIterator>
5701 _GLIBCXX14_CONSTEXPR
5702 inline _ForwardIterator
5707 __glibcxx_function_requires(_LessThanComparableConcept<
5709 __glibcxx_requires_valid_range(__first, __last);
5710 __glibcxx_requires_irreflexive(__first, __last);
5712 return _GLIBCXX_STD_A::__max_element(__first, __last,
5713 __gnu_cxx::__ops::__iter_less_iter());
5725 template<
typename _ForwardIterator,
typename _Compare>
5726 _GLIBCXX14_CONSTEXPR
5727 inline _ForwardIterator
5733 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5736 __glibcxx_requires_valid_range(__first, __last);
5737 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
5739 return _GLIBCXX_STD_A::__max_element(__first, __last,
5740 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5743#if __cplusplus >= 201402L
5745 template<
typename _InputIterator,
typename _RandomAccessIterator,
5746 typename _Size,
typename _UniformRandomBitGenerator>
5747 _RandomAccessIterator
5753 using __param_type =
typename __distrib_type::param_type;
5772 template<
typename _ForwardIterator,
typename _OutputIterator,
typename _Cat,
5773 typename _Size,
typename _UniformRandomBitGenerator>
5781 using __param_type =
typename __distrib_type::param_type;
5786 if (__first == __last)
5807 if (__p.first < __n)
5809 *
__out++ = *__first;
5815 if (__n == 0)
break;
5818 if (__p.second < __n)
5820 *
__out++ = *__first;
5830 for (; __n != 0; ++__first)
5833 *
__out++ = *__first;
5839#if __cplusplus > 201402L
5840#define __cpp_lib_sample 201603
5842 template<
typename _PopulationIterator,
typename _SampleIterator,
5843 typename _Distance,
typename _UniformRandomBitGenerator>
5857 "output range must use a RandomAccessIterator when input range"
5858 " does not meet the ForwardIterator requirements");
5861 "sample size must be an integer type");
5864 return _GLIBCXX_STD_A::
5871_GLIBCXX_END_NAMESPACE_ALGO
5872_GLIBCXX_END_NAMESPACE_VERSION
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
void swap(any &__x, any &__y) noexcept
Exchange the states of two any objects.
constexpr _InputIterator for_each_n(_InputIterator __first, _Size __n, _Function __f)
Apply a function to every element of a sequence.
constexpr const _Tp & clamp(const _Tp &, const _Tp &, const _Tp &)
Returns the value clamped between lo and hi.
constexpr const _Tp & max(const _Tp &, const _Tp &)
This does what you think it does.
constexpr pair< const _Tp &, const _Tp & > minmax(const _Tp &, const _Tp &)
Determines min and max at once as an ordered pair.
constexpr const _Tp & min(const _Tp &, const _Tp &)
This does what you think it does.
constexpr iterator_traits< _Iter >::iterator_category __iterator_category(const _Iter &)
ISO C++ entities toplevel namespace is std.
_BidirectionalIterator1 __rotate_adaptive(_BidirectionalIterator1 __first, _BidirectionalIterator1 __middle, _BidirectionalIterator1 __last, _Distance __len1, _Distance __len2, _BidirectionalIterator2 __buffer, _Distance __buffer_size)
This is a helper function for the merge routines.
_RandomAccessIterator __sample(_InputIterator __first, _InputIterator __last, input_iterator_tag, _RandomAccessIterator __out, random_access_iterator_tag, _Size __n, _UniformRandomBitGenerator &&__g)
Reservoir sampling algorithm.
constexpr _InputIterator __find_if_not_n(_InputIterator __first, _Distance &__len, _Predicate __pred)
Like find_if_not(), but uses and updates a count of the remaining range length instead of comparing a...
constexpr void __unguarded_linear_insert(_RandomAccessIterator __last, _Compare __comp)
This is a helper function for the sort routine.
constexpr _OutputIterator __unique_copy(_ForwardIterator __first, _ForwardIterator __last, _OutputIterator __result, _BinaryPredicate __binary_pred, forward_iterator_tag, output_iterator_tag)
void __merge_without_buffer(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last, _Distance __len1, _Distance __len2, _Compare __comp)
This is a helper function for the merge routines.
pair< _IntType, _IntType > __gen_two_uniform_ints(_IntType __b0, _IntType __b1, _UniformRandomBitGenerator &&__g)
Generate two uniformly distributed integers using a single distribution invocation.
constexpr void __unguarded_insertion_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
This is a helper function for the sort routine.
constexpr void __heap_select(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last, _Compare __comp)
This is a helper function for the sort routines.
void __merge_adaptive(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last, _Distance __len1, _Distance __len2, _Pointer __buffer, _Distance __buffer_size, _Compare __comp)
This is a helper function for the merge routines.
constexpr _RandomAccessIterator __unguarded_partition_pivot(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
This is a helper function...
constexpr iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
void __inplace_stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
This is a helper function for the stable sorting routines.
constexpr _ForwardIterator __rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last, forward_iterator_tag)
This is a helper function for the rotate algorithm.
constexpr void __introsort_loop(_RandomAccessIterator __first, _RandomAccessIterator __last, _Size __depth_limit, _Compare __comp)
This is a helper function for the sort routine.
constexpr _RandomAccessIterator __unguarded_partition(_RandomAccessIterator __first, _RandomAccessIterator __last, _RandomAccessIterator __pivot, _Compare __comp)
This is a helper function...
constexpr _InputIterator __find_if(_InputIterator __first, _InputIterator __last, _Predicate __pred, input_iterator_tag)
This is an overload used by find algos for the Input Iterator case.
constexpr _EuclideanRingElement __gcd(_EuclideanRingElement __m, _EuclideanRingElement __n)
constexpr _ForwardIterator __partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, forward_iterator_tag)
This is a helper function...
constexpr void __insertion_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
This is a helper function for the sort routine.
void __move_merge_adaptive(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
This is a helper function for the __merge_adaptive routines.
constexpr void __reverse(_BidirectionalIterator __first, _BidirectionalIterator __last, bidirectional_iterator_tag)
constexpr int __lg(int __n)
This is a helper function for the sort routines and for random.tcc.
_SampleIterator sample(_PopulationIterator __first, _PopulationIterator __last, _SampleIterator __out, _Distance __n, _UniformRandomBitGenerator &&__g)
Take a random sample from a population.
constexpr void advance(_InputIterator &__i, _Distance __n)
A generalization of pointer arithmetic.
constexpr void __move_median_to_first(_Iterator __result, _Iterator __a, _Iterator __b, _Iterator __c, _Compare __comp)
Swaps the median value of *__a, *__b and *__c under __comp to *__result.
constexpr _ForwardIterator __search_n_aux(_ForwardIterator __first, _ForwardIterator __last, _Integer __count, _UnaryPredicate __unary_pred, std::forward_iterator_tag)
void __move_merge_adaptive_backward(_BidirectionalIterator1 __first1, _BidirectionalIterator1 __last1, _BidirectionalIterator2 __first2, _BidirectionalIterator2 __last2, _BidirectionalIterator3 __result, _Compare __comp)
This is a helper function for the __merge_adaptive routines.
constexpr void __final_insertion_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
This is a helper function for the sort routine.
_ForwardIterator __stable_partition_adaptive(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, _Distance __len, _Pointer __buffer, _Distance __buffer_size)
This is a helper function... Requires __first != __last and !__pred(__first) and __len == distance(__...
constexpr _InputIterator __find_if_not(_InputIterator __first, _InputIterator __last, _Predicate __pred)
Provided for stable_partition to use.
_OutputIterator __move_merge(_InputIterator __first1, _InputIterator __last1, _InputIterator __first2, _InputIterator __last2, _OutputIterator __result, _Compare __comp)
This is a helper function for the __merge_sort_loop routines.
Traits class for iterators.
Marking output iterators.
Forward iterators support a superset of input iterator operations.
Bidirectional iterators support a superset of forward iterator operations.
Random-access iterators support a superset of bidirectional iterator operations.