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_a(_InputIterator __first, _Size __n, _OutputIterator __result)
717 *__result = *__first;
728 template<
typename _CharT,
typename _Size>
729 __enable_if_t<__is_char<_CharT>::__value, _CharT*>
730 __copy_n_a(istreambuf_iterator<_CharT, char_traits<_CharT>>,
733 template<
typename _InputIterator,
typename _Size,
typename _OutputIterator>
736 __copy_n(_InputIterator __first, _Size __n,
737 _OutputIterator __result, input_iterator_tag)
739 return std::__niter_wrap(__result,
740 __copy_n_a(__first, __n,
741 std::__niter_base(__result)));
744 template<
typename _RandomAccessIterator,
typename _Size,
745 typename _OutputIterator>
747 inline _OutputIterator
748 __copy_n(_RandomAccessIterator __first, _Size __n,
749 _OutputIterator __result, random_access_iterator_tag)
750 {
return std::copy(__first, __first + __n, __result); }
765 template<
typename _InputIterator,
typename _Size,
typename _OutputIterator>
767 inline _OutputIterator
772 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
775 const auto __n2 = std::__size_to_integer(__n);
779 __glibcxx_requires_can_increment(__first,
__n2);
780 __glibcxx_requires_can_increment(__result,
__n2);
782 return std::__copy_n(__first,
__n2, __result,
801 template<
typename _InputIterator,
typename _OutputIterator1,
802 typename _OutputIterator2,
typename _Predicate>
804 pair<_OutputIterator1, _OutputIterator2>
815 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
817 __glibcxx_requires_valid_range(__first, __last);
819 for (; __first != __last; ++__first)
835 template<
typename _ForwardIterator,
typename _Predicate>
838 __remove_if(_ForwardIterator __first, _ForwardIterator __last,
842 if (__first == __last)
844 _ForwardIterator __result = __first;
846 for (; __first != __last; ++__first)
847 if (!__pred(__first))
849 *__result = _GLIBCXX_MOVE(*__first);
872 template<
typename _ForwardIterator,
typename _Tp>
874 inline _ForwardIterator
879 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
881 __glibcxx_function_requires(_EqualOpConcept<
883 __glibcxx_requires_valid_range(__first, __last);
885 return std::__remove_if(__first, __last,
886 __gnu_cxx::__ops::__iter_equals_val(__value));
906 template<
typename _ForwardIterator,
typename _Predicate>
908 inline _ForwardIterator
913 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
915 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
917 __glibcxx_requires_valid_range(__first, __last);
919 return std::__remove_if(__first, __last,
920 __gnu_cxx::__ops::__pred_iter(
__pred));
923 template<
typename _ForwardIterator,
typename _BinaryPredicate>
926 __adjacent_find(_ForwardIterator __first, _ForwardIterator __last,
927 _BinaryPredicate __binary_pred)
929 if (__first == __last)
931 _ForwardIterator __next = __first;
932 while (++__next != __last)
934 if (__binary_pred(__first, __next))
941 template<
typename _ForwardIterator,
typename _BinaryPredicate>
944 __unique(_ForwardIterator __first, _ForwardIterator __last,
945 _BinaryPredicate __binary_pred)
948 __first = std::__adjacent_find(__first, __last, __binary_pred);
949 if (__first == __last)
953 _ForwardIterator __dest = __first;
955 while (++__first != __last)
956 if (!__binary_pred(__dest, __first))
957 *++__dest = _GLIBCXX_MOVE(*__first);
975 template<
typename _ForwardIterator>
977 inline _ForwardIterator
981 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
983 __glibcxx_function_requires(_EqualityComparableConcept<
985 __glibcxx_requires_valid_range(__first, __last);
987 return std::__unique(__first, __last,
988 __gnu_cxx::__ops::__iter_equal_to_iter());
1006 template<
typename _ForwardIterator,
typename _BinaryPredicate>
1007 _GLIBCXX20_CONSTEXPR
1008 inline _ForwardIterator
1013 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1018 __glibcxx_requires_valid_range(__first, __last);
1020 return std::__unique(__first, __last,
1030 template<
typename _ForwardIterator,
typename _OutputIterator,
1031 typename _BinaryPredicate>
1032 _GLIBCXX20_CONSTEXPR
1044 *__result = *__first;
1045 while (++__next != __last)
1049 *++__result = *__first;
1060 template<
typename _InputIterator,
typename _OutputIterator,
1061 typename _BinaryPredicate>
1062 _GLIBCXX20_CONSTEXPR
1077 *__result = __value;
1078 while (++__first != __last)
1082 *++__result = __value;
1093 template<
typename _InputIterator,
typename _ForwardIterator,
1094 typename _BinaryPredicate>
1095 _GLIBCXX20_CONSTEXPR
1105 *__result = *__first;
1106 while (++__first != __last)
1108 *++__result = *__first;
1117 template<
typename _B
idirectionalIterator>
1118 _GLIBCXX20_CONSTEXPR
1124 if (__first == __last || __first == --__last)
1128 std::iter_swap(__first, __last);
1138 template<
typename _RandomAccessIterator>
1139 _GLIBCXX20_CONSTEXPR
1144 if (__first == __last)
1147 while (__first < __last)
1149 std::iter_swap(__first, __last);
1167 template<
typename _B
idirectionalIterator>
1168 _GLIBCXX20_CONSTEXPR
1173 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
1175 __glibcxx_requires_valid_range(__first, __last);
1195 template<
typename _B
idirectionalIterator,
typename _OutputIterator>
1196 _GLIBCXX20_CONSTEXPR
1199 _OutputIterator __result)
1202 __glibcxx_function_requires(_BidirectionalIteratorConcept<
1204 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1206 __glibcxx_requires_valid_range(__first, __last);
1208 while (__first != __last)
1211 *__result = *__last;
1221 template<
typename _Eucl
ideanRingElement>
1222 _GLIBCXX20_CONSTEXPR
1223 _EuclideanRingElement
1235 inline namespace _V2
1239 template<
typename _ForwardIterator>
1240 _GLIBCXX20_CONSTEXPR
1247 if (__first == __middle)
1249 else if (__last == __middle)
1258 if (__first == __middle)
1272 if (__first == __middle)
1281 template<
typename _B
idirectionalIterator>
1290 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
1293 if (__first == __middle)
1295 else if (__last == __middle)
1301 while (__first != __middle && __middle != __last)
1303 std::iter_swap(__first, --__last);
1307 if (__first == __middle)
1320 template<
typename _RandomAccessIterator>
1329 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
1332 if (__first == __middle)
1334 else if (__last == __middle)
1347 std::swap_ranges(__first, __middle, __middle);
1360 _ValueType __t = _GLIBCXX_MOVE(*__p);
1361 _GLIBCXX_MOVE3(__p + 1, __p + __n, __p);
1362 *(__p + __n - 1) = _GLIBCXX_MOVE(__t);
1368 std::iter_swap(__p, __q);
1375 std::swap(__n,
__k);
1383 _ValueType __t = _GLIBCXX_MOVE(*(__p + __n - 1));
1384 _GLIBCXX_MOVE_BACKWARD3(__p, __p + __n - 1, __p + __n);
1385 *__p = _GLIBCXX_MOVE(__t);
1394 std::iter_swap(__p, __q);
1399 std::swap(__n,
__k);
1427 template<
typename _ForwardIterator>
1434 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1436 __glibcxx_requires_valid_range(__first, __middle);
1437 __glibcxx_requires_valid_range(__middle, __last);
1465 template<
typename _ForwardIterator,
typename _OutputIterator>
1466 _GLIBCXX20_CONSTEXPR
1467 inline _OutputIterator
1473 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1475 __glibcxx_requires_valid_range(__first, __middle);
1476 __glibcxx_requires_valid_range(__middle, __last);
1478 return std::copy(__first, __middle,
1479 std::copy(__middle, __last, __result));
1483 template<
typename _ForwardIterator,
typename _Predicate>
1484 _GLIBCXX20_CONSTEXPR
1489 if (__first == __last)
1493 if (++__first == __last)
1498 while (++__next != __last)
1501 std::iter_swap(__first, __next);
1509 template<
typename _B
idirectionalIterator,
typename _Predicate>
1510 _GLIBCXX20_CONSTEXPR
1511 _BidirectionalIterator
1518 if (__first == __last)
1520 else if (
__pred(*__first))
1526 if (__first == __last)
1528 else if (!
bool(
__pred(*__last)))
1532 std::iter_swap(__first, __last);
1545 template<
typename _ForwardIterator,
typename _Pointer,
typename _Predicate,
1568 for (; __first != __last; ++__first)
1606 template<
typename _ForwardIterator,
typename _Predicate>
1608 __stable_partition(_ForwardIterator __first, _ForwardIterator __last,
1613 if (__first == __last)
1616 typedef typename iterator_traits<_ForwardIterator>::value_type
1618 typedef typename iterator_traits<_ForwardIterator>::difference_type
1621 _Temporary_buffer<_ForwardIterator, _ValueType>
1625 _DistanceType(__buf.requested_size()),
1627 _DistanceType(__buf.size()));
1647 template<
typename _ForwardIterator,
typename _Predicate>
1648 inline _ForwardIterator
1653 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1655 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
1657 __glibcxx_requires_valid_range(__first, __last);
1659 return std::__stable_partition(__first, __last,
1660 __gnu_cxx::__ops::__pred_iter(
__pred));
1664 template<
typename _RandomAccessIterator,
typename _Compare>
1665 _GLIBCXX20_CONSTEXPR
1671 std::__make_heap(__first, __middle, __comp);
1673 if (__comp(__i, __first))
1674 std::__pop_heap(__first, __middle, __i, __comp);
1679 template<
typename _InputIterator,
typename _RandomAccessIterator,
1681 _GLIBCXX20_CONSTEXPR
1682 _RandomAccessIterator
1683 __partial_sort_copy(_InputIterator __first, _InputIterator __last,
1684 _RandomAccessIterator __result_first,
1685 _RandomAccessIterator __result_last,
1688 typedef typename iterator_traits<_InputIterator>::value_type
1690 typedef iterator_traits<_RandomAccessIterator> _RItTraits;
1691 typedef typename _RItTraits::difference_type _DistanceType;
1693 if (__result_first == __result_last)
1694 return __result_last;
1695 _RandomAccessIterator __result_real_last = __result_first;
1696 while (__first != __last && __result_real_last != __result_last)
1698 *__result_real_last = *__first;
1699 ++__result_real_last;
1703 std::__make_heap(__result_first, __result_real_last, __comp);
1704 while (__first != __last)
1706 if (__comp(__first, __result_first))
1707 std::__adjust_heap(__result_first, _DistanceType(0),
1708 _DistanceType(__result_real_last
1710 _InputValueType(*__first), __comp);
1713 std::__sort_heap(__result_first, __result_real_last, __comp);
1714 return __result_real_last;
1735 template<
typename _InputIterator,
typename _RandomAccessIterator>
1736 _GLIBCXX20_CONSTEXPR
1737 inline _RandomAccessIterator
1742#ifdef _GLIBCXX_CONCEPT_CHECKS
1756 __glibcxx_requires_valid_range(__first, __last);
1757 __glibcxx_requires_irreflexive(__first, __last);
1760 return std::__partial_sort_copy(__first, __last,
1762 __gnu_cxx::__ops::__iter_less_iter());
1785 template<
typename _InputIterator,
typename _RandomAccessIterator,
1787 _GLIBCXX20_CONSTEXPR
1788 inline _RandomAccessIterator
1794#ifdef _GLIBCXX_CONCEPT_CHECKS
1803 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
1807 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
1809 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
1811 __glibcxx_requires_valid_range(__first, __last);
1812 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
1815 return std::__partial_sort_copy(__first, __last,
1817 __gnu_cxx::__ops::__iter_comp_iter(__comp));
1821 template<
typename _RandomAccessIterator,
typename _Compare>
1822 _GLIBCXX20_CONSTEXPR
1828 __val = _GLIBCXX_MOVE(*__last);
1831 while (__comp(__val, __next))
1833 *__last = _GLIBCXX_MOVE(*__next);
1837 *__last = _GLIBCXX_MOVE(__val);
1841 template<
typename _RandomAccessIterator,
typename _Compare>
1842 _GLIBCXX20_CONSTEXPR
1847 if (__first == __last)
return;
1851 if (__comp(__i, __first))
1854 __val = _GLIBCXX_MOVE(*__i);
1855 _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1);
1856 *__first = _GLIBCXX_MOVE(__val);
1860 __gnu_cxx::__ops::__val_comp_iter(__comp));
1865 template<
typename _RandomAccessIterator,
typename _Compare>
1866 _GLIBCXX20_CONSTEXPR
1873 __gnu_cxx::__ops::__val_comp_iter(__comp));
1880 enum { _S_threshold = 16 };
1883 template<
typename _RandomAccessIterator,
typename _Compare>
1884 _GLIBCXX20_CONSTEXPR
1889 if (__last - __first >
int(_S_threshold))
1900 template<
typename _RandomAccessIterator,
typename _Compare>
1901 _GLIBCXX20_CONSTEXPR
1902 _RandomAccessIterator
1909 while (__comp(__first,
__pivot))
1912 while (__comp(
__pivot, __last))
1914 if (!(__first < __last))
1916 std::iter_swap(__first, __last);
1922 template<
typename _RandomAccessIterator,
typename _Compare>
1923 _GLIBCXX20_CONSTEXPR
1924 inline _RandomAccessIterator
1934 template<
typename _RandomAccessIterator,
typename _Compare>
1935 _GLIBCXX20_CONSTEXPR
1937 __partial_sort(_RandomAccessIterator __first,
1938 _RandomAccessIterator __middle,
1939 _RandomAccessIterator __last,
1943 std::__sort_heap(__first, __middle, __comp);
1947 template<
typename _RandomAccessIterator,
typename _Size,
typename _Compare>
1948 _GLIBCXX20_CONSTEXPR
1954 while (__last - __first >
int(_S_threshold))
1958 std::__partial_sort(__first, __last, __last, __comp);
1971 template<
typename _RandomAccessIterator,
typename _Compare>
1972 _GLIBCXX20_CONSTEXPR
1974 __sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
1977 if (__first != __last)
1986 template<
typename _RandomAccessIterator,
typename _Size,
typename _Compare>
1987 _GLIBCXX20_CONSTEXPR
1989 __introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth,
1990 _RandomAccessIterator __last, _Size __depth_limit,
1993 while (__last - __first > 3)
1995 if (__depth_limit == 0)
1999 std::iter_swap(__first, __nth);
2003 _RandomAccessIterator __cut =
2033 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2034 _GLIBCXX20_CONSTEXPR
2035 inline _ForwardIterator
2037 const _Tp& __val, _Compare __comp)
2041 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2043 __glibcxx_requires_partitioned_lower_pred(__first, __last,
2046 return std::__lower_bound(__first, __last, __val,
2047 __gnu_cxx::__ops::__iter_comp_val(__comp));
2050 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2051 _GLIBCXX20_CONSTEXPR
2053 __upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2054 const _Tp& __val, _Compare __comp)
2056 typedef typename iterator_traits<_ForwardIterator>::difference_type
2063 _DistanceType __half = __len >> 1;
2064 _ForwardIterator __middle = __first;
2066 if (__comp(__val, __middle))
2072 __len = __len - __half - 1;
2089 template<
typename _ForwardIterator,
typename _Tp>
2090 _GLIBCXX20_CONSTEXPR
2091 inline _ForwardIterator
2097 __glibcxx_function_requires(_LessThanOpConcept<
2099 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2101 return std::__upper_bound(__first, __last, __val,
2102 __gnu_cxx::__ops::__val_less_iter());
2120 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2121 _GLIBCXX20_CONSTEXPR
2122 inline _ForwardIterator
2124 const _Tp& __val, _Compare __comp)
2128 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2130 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2133 return std::__upper_bound(__first, __last, __val,
2134 __gnu_cxx::__ops::__val_comp_iter(__comp));
2137 template<
typename _ForwardIterator,
typename _Tp,
2138 typename _CompareItTp,
typename _CompareTpIt>
2139 _GLIBCXX20_CONSTEXPR
2140 pair<_ForwardIterator, _ForwardIterator>
2141 __equal_range(_ForwardIterator __first, _ForwardIterator __last,
2143 _CompareItTp __comp_it_val, _CompareTpIt __comp_val_it)
2145 typedef typename iterator_traits<_ForwardIterator>::difference_type
2152 _DistanceType __half = __len >> 1;
2153 _ForwardIterator __middle = __first;
2155 if (__comp_it_val(__middle, __val))
2159 __len = __len - __half - 1;
2161 else if (__comp_val_it(__val, __middle))
2165 _ForwardIterator __left
2166 = std::__lower_bound(__first, __middle, __val, __comp_it_val);
2168 _ForwardIterator __right
2169 = std::__upper_bound(++__middle, __first, __val, __comp_val_it);
2170 return pair<_ForwardIterator, _ForwardIterator>(__left, __right);
2173 return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
2193 template<
typename _ForwardIterator,
typename _Tp>
2194 _GLIBCXX20_CONSTEXPR
2195 inline pair<_ForwardIterator, _ForwardIterator>
2201 __glibcxx_function_requires(_LessThanOpConcept<
2203 __glibcxx_function_requires(_LessThanOpConcept<
2205 __glibcxx_requires_partitioned_lower(__first, __last, __val);
2206 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2208 return std::__equal_range(__first, __last, __val,
2209 __gnu_cxx::__ops::__iter_less_val(),
2210 __gnu_cxx::__ops::__val_less_iter());
2230 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2231 _GLIBCXX20_CONSTEXPR
2232 inline pair<_ForwardIterator, _ForwardIterator>
2234 const _Tp& __val, _Compare __comp)
2238 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2240 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2242 __glibcxx_requires_partitioned_lower_pred(__first, __last,
2244 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2247 return std::__equal_range(__first, __last, __val,
2248 __gnu_cxx::__ops::__iter_comp_val(__comp),
2249 __gnu_cxx::__ops::__val_comp_iter(__comp));
2264 template<
typename _ForwardIterator,
typename _Tp>
2265 _GLIBCXX20_CONSTEXPR
2272 __glibcxx_function_requires(_LessThanOpConcept<
2274 __glibcxx_requires_partitioned_lower(__first, __last, __val);
2275 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2278 = std::__lower_bound(__first, __last, __val,
2279 __gnu_cxx::__ops::__iter_less_val());
2280 return __i != __last && !(__val < *__i);
2298 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2299 _GLIBCXX20_CONSTEXPR
2302 const _Tp& __val, _Compare __comp)
2306 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2308 __glibcxx_requires_partitioned_lower_pred(__first, __last,
2310 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2314 = std::__lower_bound(__first, __last, __val,
2315 __gnu_cxx::__ops::__iter_comp_val(__comp));
2316 return __i != __last && !bool(__comp(__val, *__i));
2322 template<
typename _InputIterator1,
typename _InputIterator2,
2323 typename _OutputIterator,
typename _Compare>
2327 _OutputIterator __result, _Compare __comp)
2333 *__result = _GLIBCXX_MOVE(*
__first2);
2338 *__result = _GLIBCXX_MOVE(*
__first1);
2348 template<
typename _BidirectionalIterator1,
typename _BidirectionalIterator2,
2349 typename _BidirectionalIterator3,
typename _Compare>
2372 *--__result = _GLIBCXX_MOVE(*
__last1);
2382 *--__result = _GLIBCXX_MOVE(*
__last2);
2391 template<
typename _BidirectionalIterator1,
typename _BidirectionalIterator2,
2393 _BidirectionalIterator1
2407 _GLIBCXX_MOVE_BACKWARD3(__first, __middle, __last);
2418 _GLIBCXX_MOVE3(__middle, __last, __first);
2425 return std::rotate(__first, __middle, __last);
2429 template<
typename _BidirectionalIterator,
typename _Distance,
2430 typename _Pointer,
typename _Compare>
2462 = std::__lower_bound(__middle, __last, *
__first_cut,
2463 __gnu_cxx::__ops::__iter_comp_val(__comp));
2472 __gnu_cxx::__ops::__val_comp_iter(__comp));
2490 template<
typename _BidirectionalIterator,
typename _Distance,
2504 if (__comp(__middle, __first))
2505 std::iter_swap(__first, __middle);
2518 = std::__lower_bound(__middle, __last, *
__first_cut,
2519 __gnu_cxx::__ops::__iter_comp_val(__comp));
2528 __gnu_cxx::__ops::__val_comp_iter(__comp));
2540 template<
typename _B
idirectionalIterator,
typename _Compare>
2542 __inplace_merge(_BidirectionalIterator __first,
2543 _BidirectionalIterator __middle,
2544 _BidirectionalIterator __last,
2547 typedef typename iterator_traits<_BidirectionalIterator>::value_type
2549 typedef typename iterator_traits<_BidirectionalIterator>::difference_type
2552 if (__first == __middle || __middle == __last)
2555 const _DistanceType __len1 =
std::distance(__first, __middle);
2556 const _DistanceType __len2 =
std::distance(__middle, __last);
2558 typedef _Temporary_buffer<_BidirectionalIterator, _ValueType> _TmpBuf;
2559 _TmpBuf __buf(__first, __len1 + __len2);
2561 if (__buf.begin() == 0)
2563 (__first, __middle, __last, __len1, __len2, __comp);
2566 (__first, __middle, __last, __len1, __len2, __buf.begin(),
2567 _DistanceType(__buf.size()), __comp);
2588 template<
typename _B
idirectionalIterator>
2595 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
2597 __glibcxx_function_requires(_LessThanComparableConcept<
2599 __glibcxx_requires_sorted(__first, __middle);
2600 __glibcxx_requires_sorted(__middle, __last);
2601 __glibcxx_requires_irreflexive(__first, __last);
2603 std::__inplace_merge(__first, __middle, __last,
2604 __gnu_cxx::__ops::__iter_less_iter());
2629 template<
typename _B
idirectionalIterator,
typename _Compare>
2637 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
2639 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2642 __glibcxx_requires_sorted_pred(__first, __middle, __comp);
2643 __glibcxx_requires_sorted_pred(__middle, __last, __comp);
2644 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
2646 std::__inplace_merge(__first, __middle, __last,
2647 __gnu_cxx::__ops::__iter_comp_iter(__comp));
2652 template<
typename _InputIterator,
typename _OutputIterator,
2657 _OutputIterator __result, _Compare __comp)
2663 *__result = _GLIBCXX_MOVE(*
__first2);
2668 *__result = _GLIBCXX_MOVE(*
__first1);
2678 template<
typename _RandomAccessIterator1,
typename _RandomAccessIterator2,
2679 typename _Distance,
typename _Compare>
2681 __merge_sort_loop(_RandomAccessIterator1 __first,
2682 _RandomAccessIterator1 __last,
2683 _RandomAccessIterator2 __result, _Distance __step_size,
2686 const _Distance __two_step = 2 * __step_size;
2688 while (__last - __first >= __two_step)
2691 __first + __step_size,
2692 __first + __two_step,
2694 __first += __two_step;
2696 __step_size =
std::min(_Distance(__last - __first), __step_size);
2699 __first + __step_size, __last, __result, __comp);
2702 template<
typename _RandomAccessIterator,
typename _Distance,
2704 _GLIBCXX20_CONSTEXPR
2706 __chunk_insertion_sort(_RandomAccessIterator __first,
2707 _RandomAccessIterator __last,
2708 _Distance __chunk_size, _Compare __comp)
2710 while (__last - __first >= __chunk_size)
2713 __first += __chunk_size;
2718 enum { _S_chunk_size = 7 };
2720 template<
typename _RandomAccessIterator,
typename _Po
inter,
typename _Compare>
2722 __merge_sort_with_buffer(_RandomAccessIterator __first,
2723 _RandomAccessIterator __last,
2724 _Pointer __buffer, _Compare __comp)
2726 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
2729 const _Distance __len = __last - __first;
2730 const _Pointer __buffer_last = __buffer + __len;
2732 _Distance __step_size = _S_chunk_size;
2733 std::__chunk_insertion_sort(__first, __last, __step_size, __comp);
2735 while (__step_size < __len)
2737 std::__merge_sort_loop(__first, __last, __buffer,
2738 __step_size, __comp);
2740 std::__merge_sort_loop(__buffer, __buffer_last, __first,
2741 __step_size, __comp);
2746 template<
typename _RandomAccessIterator,
typename _Pointer,
2747 typename _Distance,
typename _Compare>
2749 __stable_sort_adaptive(_RandomAccessIterator __first,
2750 _RandomAccessIterator __last,
2751 _Pointer __buffer, _Distance __buffer_size,
2754 const _Distance __len = (__last - __first + 1) / 2;
2755 const _RandomAccessIterator __middle = __first + __len;
2756 if (__len > __buffer_size)
2758 std::__stable_sort_adaptive(__first, __middle, __buffer,
2759 __buffer_size, __comp);
2760 std::__stable_sort_adaptive(__middle, __last, __buffer,
2761 __buffer_size, __comp);
2765 std::__merge_sort_with_buffer(__first, __middle, __buffer, __comp);
2766 std::__merge_sort_with_buffer(__middle, __last, __buffer, __comp);
2769 _Distance(__middle - __first),
2770 _Distance(__last - __middle),
2771 __buffer, __buffer_size,
2776 template<
typename _RandomAccessIterator,
typename _Compare>
2781 if (__last - __first < 15)
2802 template<
typename _InputIterator1,
typename _InputIterator2,
2804 _GLIBCXX20_CONSTEXPR
2806 __includes(_InputIterator1 __first1, _InputIterator1 __last1,
2807 _InputIterator2 __first2, _InputIterator2 __last2,
2810 while (__first1 != __last1 && __first2 != __last2)
2811 if (__comp(__first2, __first1))
2813 else if (__comp(__first1, __first2))
2821 return __first2 == __last2;
2842 template<
typename _InputIterator1,
typename _InputIterator2>
2843 _GLIBCXX20_CONSTEXPR
2851 __glibcxx_function_requires(_LessThanOpConcept<
2854 __glibcxx_function_requires(_LessThanOpConcept<
2863 __gnu_cxx::__ops::__iter_less_iter());
2887 template<
typename _InputIterator1,
typename _InputIterator2,
2889 _GLIBCXX20_CONSTEXPR
2898 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2901 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2910 __gnu_cxx::__ops::__iter_comp_iter(__comp));
2923 template<
typename _B
idirectionalIterator,
typename _Compare>
2924 _GLIBCXX20_CONSTEXPR
2926 __next_permutation(_BidirectionalIterator __first,
2927 _BidirectionalIterator __last, _Compare __comp)
2929 if (__first == __last)
2931 _BidirectionalIterator __i = __first;
2940 _BidirectionalIterator __ii = __i;
2942 if (__comp(__i, __ii))
2944 _BidirectionalIterator __j = __last;
2945 while (!__comp(__i, --__j))
2947 std::iter_swap(__i, __j);
2973 template<
typename _B
idirectionalIterator>
2974 _GLIBCXX20_CONSTEXPR
2980 __glibcxx_function_requires(_BidirectionalIteratorConcept<
2982 __glibcxx_function_requires(_LessThanComparableConcept<
2984 __glibcxx_requires_valid_range(__first, __last);
2985 __glibcxx_requires_irreflexive(__first, __last);
2987 return std::__next_permutation
2988 (__first, __last, __gnu_cxx::__ops::__iter_less_iter());
3006 template<
typename _B
idirectionalIterator,
typename _Compare>
3007 _GLIBCXX20_CONSTEXPR
3013 __glibcxx_function_requires(_BidirectionalIteratorConcept<
3015 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3018 __glibcxx_requires_valid_range(__first, __last);
3019 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
3021 return std::__next_permutation
3022 (__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
3025 template<
typename _B
idirectionalIterator,
typename _Compare>
3026 _GLIBCXX20_CONSTEXPR
3028 __prev_permutation(_BidirectionalIterator __first,
3029 _BidirectionalIterator __last, _Compare __comp)
3031 if (__first == __last)
3033 _BidirectionalIterator __i = __first;
3042 _BidirectionalIterator __ii = __i;
3044 if (__comp(__ii, __i))
3046 _BidirectionalIterator __j = __last;
3047 while (!__comp(--__j, __i))
3049 std::iter_swap(__i, __j);
3076 template<
typename _B
idirectionalIterator>
3077 _GLIBCXX20_CONSTEXPR
3083 __glibcxx_function_requires(_BidirectionalIteratorConcept<
3085 __glibcxx_function_requires(_LessThanComparableConcept<
3087 __glibcxx_requires_valid_range(__first, __last);
3088 __glibcxx_requires_irreflexive(__first, __last);
3090 return std::__prev_permutation(__first, __last,
3091 __gnu_cxx::__ops::__iter_less_iter());
3109 template<
typename _B
idirectionalIterator,
typename _Compare>
3110 _GLIBCXX20_CONSTEXPR
3116 __glibcxx_function_requires(_BidirectionalIteratorConcept<
3118 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3121 __glibcxx_requires_valid_range(__first, __last);
3122 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
3124 return std::__prev_permutation(__first, __last,
3125 __gnu_cxx::__ops::__iter_comp_iter(__comp));
3131 template<
typename _InputIterator,
typename _OutputIterator,
3132 typename _Predicate,
typename _Tp>
3133 _GLIBCXX20_CONSTEXPR
3135 __replace_copy_if(_InputIterator __first, _InputIterator __last,
3136 _OutputIterator __result,
3137 _Predicate __pred,
const _Tp& __new_value)
3139 for (; __first != __last; ++__first, (void)++__result)
3140 if (__pred(__first))
3141 *__result = __new_value;
3143 *__result = *__first;
3161 template<
typename _InputIterator,
typename _OutputIterator,
typename _Tp>
3162 _GLIBCXX20_CONSTEXPR
3163 inline _OutputIterator
3165 _OutputIterator __result,
3170 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
3172 __glibcxx_function_requires(_EqualOpConcept<
3174 __glibcxx_requires_valid_range(__first, __last);
3176 return std::__replace_copy_if(__first, __last, __result,
3196 template<
typename _InputIterator,
typename _OutputIterator,
3197 typename _Predicate,
typename _Tp>
3198 _GLIBCXX20_CONSTEXPR
3199 inline _OutputIterator
3201 _OutputIterator __result,
3206 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
3208 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
3210 __glibcxx_requires_valid_range(__first, __last);
3212 return std::__replace_copy_if(__first, __last, __result,
3213 __gnu_cxx::__ops::__pred_iter(
__pred),
3217#if __cplusplus >= 201103L
3225 template<
typename _ForwardIterator>
3226 _GLIBCXX20_CONSTEXPR
3229 {
return std::is_sorted_until(__first, __last) == __last; }
3240 template<
typename _ForwardIterator,
typename _Compare>
3241 _GLIBCXX20_CONSTEXPR
3245 {
return std::is_sorted_until(__first, __last, __comp) == __last; }
3247 template<
typename _ForwardIterator,
typename _Compare>
3248 _GLIBCXX20_CONSTEXPR
3250 __is_sorted_until(_ForwardIterator __first, _ForwardIterator __last,
3253 if (__first == __last)
3256 _ForwardIterator __next = __first;
3257 for (++__next; __next != __last; __first = __next, (void)++__next)
3258 if (__comp(__next, __first))
3271 template<
typename _ForwardIterator>
3272 _GLIBCXX20_CONSTEXPR
3273 inline _ForwardIterator
3278 __glibcxx_function_requires(_LessThanComparableConcept<
3280 __glibcxx_requires_valid_range(__first, __last);
3281 __glibcxx_requires_irreflexive(__first, __last);
3283 return std::__is_sorted_until(__first, __last,
3284 __gnu_cxx::__ops::__iter_less_iter());
3296 template<
typename _ForwardIterator,
typename _Compare>
3297 _GLIBCXX20_CONSTEXPR
3298 inline _ForwardIterator
3304 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3307 __glibcxx_requires_valid_range(__first, __last);
3308 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
3310 return std::__is_sorted_until(__first, __last,
3311 __gnu_cxx::__ops::__iter_comp_iter(__comp));
3322 template<
typename _Tp>
3323 _GLIBCXX14_CONSTEXPR
3324 inline pair<const _Tp&, const _Tp&>
3343 template<
typename _Tp,
typename _Compare>
3344 _GLIBCXX14_CONSTEXPR
3345 inline pair<const _Tp&, const _Tp&>
3346 minmax(
const _Tp& __a,
const _Tp& __b, _Compare __comp)
3352 template<
typename _ForwardIterator,
typename _Compare>
3353 _GLIBCXX14_CONSTEXPR
3354 pair<_ForwardIterator, _ForwardIterator>
3355 __minmax_element(_ForwardIterator __first, _ForwardIterator __last,
3358 _ForwardIterator __next = __first;
3359 if (__first == __last
3360 || ++__next == __last)
3361 return std::make_pair(__first, __first);
3363 _ForwardIterator __min{}, __max{};
3364 if (__comp(__next, __first))
3378 while (__first != __last)
3381 if (++__next == __last)
3383 if (__comp(__first, __min))
3385 else if (!__comp(__first, __max))
3390 if (__comp(__next, __first))
3392 if (__comp(__next, __min))
3394 if (!__comp(__first, __max))
3399 if (__comp(__first, __min))
3401 if (!__comp(__next, __max))
3409 return std::make_pair(__min, __max);
3423 template<
typename _ForwardIterator>
3424 _GLIBCXX14_CONSTEXPR
3425 inline pair<_ForwardIterator, _ForwardIterator>
3430 __glibcxx_function_requires(_LessThanComparableConcept<
3432 __glibcxx_requires_valid_range(__first, __last);
3433 __glibcxx_requires_irreflexive(__first, __last);
3435 return std::__minmax_element(__first, __last,
3436 __gnu_cxx::__ops::__iter_less_iter());
3451 template<
typename _ForwardIterator,
typename _Compare>
3452 _GLIBCXX14_CONSTEXPR
3453 inline pair<_ForwardIterator, _ForwardIterator>
3459 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3462 __glibcxx_requires_valid_range(__first, __last);
3463 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
3465 return std::__minmax_element(__first, __last,
3466 __gnu_cxx::__ops::__iter_comp_iter(__comp));
3470 template<
typename _Tp>
3471 _GLIBCXX14_CONSTEXPR
3473 min(initializer_list<_Tp> __l)
3474 {
return *std::min_element(__l.begin(), __l.end()); }
3476 template<
typename _Tp,
typename _Compare>
3477 _GLIBCXX14_CONSTEXPR
3479 min(initializer_list<_Tp> __l, _Compare __comp)
3480 {
return *std::min_element(__l.begin(), __l.end(), __comp); }
3482 template<
typename _Tp>
3483 _GLIBCXX14_CONSTEXPR
3485 max(initializer_list<_Tp> __l)
3486 {
return *std::max_element(__l.begin(), __l.end()); }
3488 template<
typename _Tp,
typename _Compare>
3489 _GLIBCXX14_CONSTEXPR
3491 max(initializer_list<_Tp> __l, _Compare __comp)
3492 {
return *std::max_element(__l.begin(), __l.end(), __comp); }
3494 template<
typename _Tp>
3495 _GLIBCXX14_CONSTEXPR
3496 inline pair<_Tp, _Tp>
3497 minmax(initializer_list<_Tp> __l)
3499 pair<const _Tp*, const _Tp*> __p =
3500 std::minmax_element(__l.begin(), __l.end());
3501 return std::make_pair(*__p.first, *__p.second);
3504 template<
typename _Tp,
typename _Compare>
3505 _GLIBCXX14_CONSTEXPR
3506 inline pair<_Tp, _Tp>
3507 minmax(initializer_list<_Tp> __l, _Compare __comp)
3509 pair<const _Tp*, const _Tp*> __p =
3510 std::minmax_element(__l.begin(), __l.end(), __comp);
3511 return std::make_pair(*__p.first, *__p.second);
3528 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
3529 typename _BinaryPredicate>
3530 _GLIBCXX20_CONSTEXPR
3544 __gnu_cxx::__ops::__iter_comp_iter(
__pred));
3547#if __cplusplus > 201103L
3548 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
3549 typename _BinaryPredicate>
3550 _GLIBCXX20_CONSTEXPR
3552 __is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3553 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
3554 _BinaryPredicate __pred)
3557 =
typename iterator_traits<_ForwardIterator1>::iterator_category;
3559 =
typename iterator_traits<_ForwardIterator2>::iterator_category;
3560 using _It1_is_RA = is_same<_Cat1, random_access_iterator_tag>;
3561 using _It2_is_RA = is_same<_Cat2, random_access_iterator_tag>;
3562 constexpr bool __ra_iters = _It1_is_RA() && _It2_is_RA();
3573 for (; __first1 != __last1 && __first2 != __last2;
3574 ++__first1, (void)++__first2)
3575 if (!__pred(__first1, __first2))
3580 if (__first1 == __last1)
3587 if (__d1 == 0 && __d2 == 0)
3593 for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
3596 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)))
3599 auto __matches = std::__count_if(__first2, __last2,
3600 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan));
3602 || std::__count_if(__scan, __last1,
3603 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan))
3623 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
3624 _GLIBCXX20_CONSTEXPR
3634 __gnu_cxx::__ops::__iter_equal_to_iter());
3651 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
3652 typename _BinaryPredicate>
3653 _GLIBCXX20_CONSTEXPR
3663 __gnu_cxx::__ops::__iter_comp_iter(
__pred));
3666#if __cplusplus > 201402L
3668#define __cpp_lib_clamp 201603
3678 template<
typename _Tp>
3679 constexpr const _Tp&
3680 clamp(
const _Tp& __val,
const _Tp& __lo,
const _Tp& __hi)
3682 __glibcxx_assert(!(__hi < __lo));
3683 return (__val < __lo) ? __lo : (__hi < __val) ? __hi : __val;
3696 template<
typename _Tp,
typename _Compare>
3697 constexpr const _Tp&
3698 clamp(
const _Tp& __val,
const _Tp& __lo,
const _Tp& __hi, _Compare __comp)
3700 __glibcxx_assert(!__comp(__hi, __lo));
3701 return __comp(__val, __lo) ? __lo : __comp(__hi, __val) ? __hi : __val;
3706#ifdef _GLIBCXX_USE_C99_STDINT_TR1
3728 template<
typename _IntType,
typename _UniformRandomBitGenerator>
3729 pair<_IntType, _IntType>
3735 return std::make_pair(__x /
__b1, __x %
__b1);
3750 template<
typename _RandomAccessIterator,
3751 typename _UniformRandomNumberGenerator>
3757 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
3759 __glibcxx_requires_valid_range(__first, __last);
3761 if (__first == __last)
3767 typedef typename std::make_unsigned<_DistanceType>::type
__ud_type;
3769 typedef typename __distr_type::param_type
__p_type;
3791 std::iter_swap(__i++, __first + __d(
__g));
3798 while (__i != __last)
3805 std::iter_swap(__i++, __first +
__pospos.first);
3806 std::iter_swap(__i++, __first +
__pospos.second);
3815 std::iter_swap(__i, __first + __d(
__g,
__p_type(0, __i - __first)));
3821_GLIBCXX_BEGIN_NAMESPACE_ALGO
3835 template<
typename _InputIterator,
typename _Function>
3836 _GLIBCXX20_CONSTEXPR
3842 __glibcxx_requires_valid_range(__first, __last);
3843 for (; __first != __last; ++__first)
3848#if __cplusplus >= 201703L
3861 template<
typename _InputIterator,
typename _Size,
typename _Function>
3862 _GLIBCXX20_CONSTEXPR
3864 for_each_n(_InputIterator __first, _Size __n, _Function __f)
3866 auto __n2 = std::__size_to_integer(__n);
3867 using _Cat =
typename iterator_traits<_InputIterator>::iterator_category;
3868 if constexpr (is_base_of_v<random_access_iterator_tag, _Cat>)
3872 auto __last = __first + __n2;
3873 std::for_each(__first, __last,
std::move(__f));
3897 template<
typename _InputIterator,
typename _Tp>
3898 _GLIBCXX20_CONSTEXPR
3899 inline _InputIterator
3905 __glibcxx_function_requires(_EqualOpConcept<
3907 __glibcxx_requires_valid_range(__first, __last);
3909 __gnu_cxx::__ops::__iter_equals_val(__val));
3922 template<
typename _InputIterator,
typename _Predicate>
3923 _GLIBCXX20_CONSTEXPR
3924 inline _InputIterator
3930 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
3932 __glibcxx_requires_valid_range(__first, __last);
3935 __gnu_cxx::__ops::__pred_iter(
__pred));
3954 template<
typename _InputIterator,
typename _ForwardIterator>
3955 _GLIBCXX20_CONSTEXPR
3963 __glibcxx_function_requires(_EqualOpConcept<
3995 template<
typename _InputIterator,
typename _ForwardIterator,
3996 typename _BinaryPredicate>
3997 _GLIBCXX20_CONSTEXPR
4028 template<
typename _ForwardIterator>
4029 _GLIBCXX20_CONSTEXPR
4030 inline _ForwardIterator
4035 __glibcxx_function_requires(_EqualityComparableConcept<
4037 __glibcxx_requires_valid_range(__first, __last);
4039 return std::__adjacent_find(__first, __last,
4040 __gnu_cxx::__ops::__iter_equal_to_iter());
4054 template<
typename _ForwardIterator,
typename _BinaryPredicate>
4055 _GLIBCXX20_CONSTEXPR
4056 inline _ForwardIterator
4065 __glibcxx_requires_valid_range(__first, __last);
4067 return std::__adjacent_find(__first, __last,
4080 template<
typename _InputIterator,
typename _Tp>
4081 _GLIBCXX20_CONSTEXPR
4082 inline typename iterator_traits<_InputIterator>::difference_type
4087 __glibcxx_function_requires(_EqualOpConcept<
4089 __glibcxx_requires_valid_range(__first, __last);
4091 return std::__count_if(__first, __last,
4092 __gnu_cxx::__ops::__iter_equals_val(__value));
4104 template<
typename _InputIterator,
typename _Predicate>
4105 _GLIBCXX20_CONSTEXPR
4106 inline typename iterator_traits<_InputIterator>::difference_type
4111 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4113 __glibcxx_requires_valid_range(__first, __last);
4115 return std::__count_if(__first, __last,
4116 __gnu_cxx::__ops::__pred_iter(
__pred));
4145 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
4146 _GLIBCXX20_CONSTEXPR
4147 inline _ForwardIterator1
4154 __glibcxx_function_requires(_EqualOpConcept<
4161 __gnu_cxx::__ops::__iter_equal_to_iter());
4185 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
4186 typename _BinaryPredicate>
4187 _GLIBCXX20_CONSTEXPR
4188 inline _ForwardIterator1
4221 template<
typename _ForwardIterator,
typename _Integer,
typename _Tp>
4222 _GLIBCXX20_CONSTEXPR
4223 inline _ForwardIterator
4225 _Integer __count,
const _Tp& __val)
4229 __glibcxx_function_requires(_EqualOpConcept<
4231 __glibcxx_requires_valid_range(__first, __last);
4233 return std::__search_n(__first, __last, __count,
4234 __gnu_cxx::__ops::__iter_equals_val(__val));
4255 template<
typename _ForwardIterator,
typename _Integer,
typename _Tp,
4256 typename _BinaryPredicate>
4257 _GLIBCXX20_CONSTEXPR
4258 inline _ForwardIterator
4260 _Integer __count,
const _Tp& __val,
4267 __glibcxx_requires_valid_range(__first, __last);
4269 return std::__search_n(__first, __last, __count,
4273#if __cplusplus > 201402L
4281 template<
typename _ForwardIterator,
typename _Searcher>
4282 _GLIBCXX20_CONSTEXPR
4283 inline _ForwardIterator
4284 search(_ForwardIterator __first, _ForwardIterator __last,
4285 const _Searcher& __searcher)
4286 {
return __searcher(__first, __last).first; }
4305 template<
typename _InputIterator,
typename _OutputIterator,
4306 typename _UnaryOperation>
4307 _GLIBCXX20_CONSTEXPR
4314 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4317 __glibcxx_requires_valid_range(__first, __last);
4319 for (; __first != __last; ++__first, (
void)++__result)
4343 template<
typename _InputIterator1,
typename _InputIterator2,
4344 typename _OutputIterator,
typename _BinaryOperation>
4345 _GLIBCXX20_CONSTEXPR
4354 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4377 template<
typename _ForwardIterator,
typename _Tp>
4378 _GLIBCXX20_CONSTEXPR
4384 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4386 __glibcxx_function_requires(_EqualOpConcept<
4388 __glibcxx_function_requires(_ConvertibleConcept<_Tp,
4390 __glibcxx_requires_valid_range(__first, __last);
4392 for (; __first != __last; ++__first)
4410 template<
typename _ForwardIterator,
typename _Predicate,
typename _Tp>
4411 _GLIBCXX20_CONSTEXPR
4417 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4419 __glibcxx_function_requires(_ConvertibleConcept<_Tp,
4421 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4423 __glibcxx_requires_valid_range(__first, __last);
4425 for (; __first != __last; ++__first)
4443 template<
typename _ForwardIterator,
typename _Generator>
4444 _GLIBCXX20_CONSTEXPR
4451 __glibcxx_function_requires(_GeneratorConcept<
_Generator,
4453 __glibcxx_requires_valid_range(__first, __last);
4455 for (; __first != __last; ++__first)
4477 template<
typename _OutputIterator,
typename _Size,
typename _Generator>
4478 _GLIBCXX20_CONSTEXPR
4483 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4485 __typeof__(
__gen())>)
4515 template<
typename _InputIterator,
typename _OutputIterator>
4516 _GLIBCXX20_CONSTEXPR
4517 inline _OutputIterator
4519 _OutputIterator __result)
4523 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4525 __glibcxx_function_requires(_EqualityComparableConcept<
4527 __glibcxx_requires_valid_range(__first, __last);
4529 if (__first == __last)
4532 __gnu_cxx::__ops::__iter_equal_to_iter(),
4556 template<
typename _InputIterator,
typename _OutputIterator,
4557 typename _BinaryPredicate>
4558 _GLIBCXX20_CONSTEXPR
4559 inline _OutputIterator
4561 _OutputIterator __result,
4566 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4568 __glibcxx_requires_valid_range(__first, __last);
4570 if (__first == __last)
4590 template<
typename _RandomAccessIterator>
4592 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
4595 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4596 _RandomAccessIterator>)
4597 __glibcxx_requires_valid_range(__first, __last);
4599 if (__first != __last)
4600 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
4603 _RandomAccessIterator __j = __first
4606 std::iter_swap(__i, __j);
4625 template<
typename _RandomAccessIterator,
typename _RandomNumberGenerator>
4635 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4637 __glibcxx_requires_valid_range(__first, __last);
4639 if (__first == __last)
4645 std::iter_swap(__i, __j);
4665 template<
typename _ForwardIterator,
typename _Predicate>
4666 _GLIBCXX20_CONSTEXPR
4667 inline _ForwardIterator
4672 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4674 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4676 __glibcxx_requires_valid_range(__first, __last);
4699 template<
typename _RandomAccessIterator>
4700 _GLIBCXX20_CONSTEXPR
4707 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4709 __glibcxx_function_requires(_LessThanComparableConcept<
4711 __glibcxx_requires_valid_range(__first, __middle);
4712 __glibcxx_requires_valid_range(__middle, __last);
4713 __glibcxx_requires_irreflexive(__first, __last);
4715 std::__partial_sort(__first, __middle, __last,
4716 __gnu_cxx::__ops::__iter_less_iter());
4738 template<
typename _RandomAccessIterator,
typename _Compare>
4739 _GLIBCXX20_CONSTEXPR
4747 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4749 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4752 __glibcxx_requires_valid_range(__first, __middle);
4753 __glibcxx_requires_valid_range(__middle, __last);
4754 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
4756 std::__partial_sort(__first, __middle, __last,
4757 __gnu_cxx::__ops::__iter_comp_iter(__comp));
4775 template<
typename _RandomAccessIterator>
4776 _GLIBCXX20_CONSTEXPR
4782 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4784 __glibcxx_function_requires(_LessThanComparableConcept<
4786 __glibcxx_requires_valid_range(__first,
__nth);
4787 __glibcxx_requires_valid_range(
__nth, __last);
4788 __glibcxx_requires_irreflexive(__first, __last);
4790 if (__first == __last ||
__nth == __last)
4793 std::__introselect(__first,
__nth, __last,
4795 __gnu_cxx::__ops::__iter_less_iter());
4815 template<
typename _RandomAccessIterator,
typename _Compare>
4816 _GLIBCXX20_CONSTEXPR
4822 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4824 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4827 __glibcxx_requires_valid_range(__first,
__nth);
4828 __glibcxx_requires_valid_range(
__nth, __last);
4829 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
4831 if (__first == __last ||
__nth == __last)
4834 std::__introselect(__first,
__nth, __last,
4836 __gnu_cxx::__ops::__iter_comp_iter(__comp));
4853 template<
typename _RandomAccessIterator>
4854 _GLIBCXX20_CONSTEXPR
4859 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4861 __glibcxx_function_requires(_LessThanComparableConcept<
4863 __glibcxx_requires_valid_range(__first, __last);
4864 __glibcxx_requires_irreflexive(__first, __last);
4866 std::__sort(__first, __last, __gnu_cxx::__ops::__iter_less_iter());
4884 template<
typename _RandomAccessIterator,
typename _Compare>
4885 _GLIBCXX20_CONSTEXPR
4891 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4893 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4896 __glibcxx_requires_valid_range(__first, __last);
4897 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
4899 std::__sort(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
4902 template<
typename _InputIterator1,
typename _InputIterator2,
4903 typename _OutputIterator,
typename _Compare>
4904 _GLIBCXX20_CONSTEXPR
4906 __merge(_InputIterator1 __first1, _InputIterator1 __last1,
4907 _InputIterator2 __first2, _InputIterator2 __last2,
4908 _OutputIterator __result, _Compare __comp)
4910 while (__first1 != __last1 && __first2 != __last2)
4912 if (__comp(__first2, __first1))
4914 *__result = *__first2;
4919 *__result = *__first1;
4924 return std::copy(__first2, __last2,
4925 std::copy(__first1, __last1, __result));
4947 template<
typename _InputIterator1,
typename _InputIterator2,
4948 typename _OutputIterator>
4949 _GLIBCXX20_CONSTEXPR
4950 inline _OutputIterator
4953 _OutputIterator __result)
4958 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4960 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4962 __glibcxx_function_requires(_LessThanOpConcept<
4972 __gnu_cxx::__ops::__iter_less_iter());
4998 template<
typename _InputIterator1,
typename _InputIterator2,
4999 typename _OutputIterator,
typename _Compare>
5000 _GLIBCXX20_CONSTEXPR
5001 inline _OutputIterator
5004 _OutputIterator __result, _Compare __comp)
5009 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5011 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5013 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5023 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5026 template<
typename _RandomAccessIterator,
typename _Compare>
5028 __stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
5031 typedef typename iterator_traits<_RandomAccessIterator>::value_type
5033 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
5036 typedef _Temporary_buffer<_RandomAccessIterator, _ValueType> _TmpBuf;
5039 if (__buf.begin() == 0)
5042 std::__stable_sort_adaptive(__first, __last, __buf.begin(),
5043 _DistanceType(__buf.size()), __comp);
5063 template<
typename _RandomAccessIterator>
5068 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5070 __glibcxx_function_requires(_LessThanComparableConcept<
5072 __glibcxx_requires_valid_range(__first, __last);
5073 __glibcxx_requires_irreflexive(__first, __last);
5075 _GLIBCXX_STD_A::__stable_sort(__first, __last,
5076 __gnu_cxx::__ops::__iter_less_iter());
5097 template<
typename _RandomAccessIterator,
typename _Compare>
5103 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5105 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5108 __glibcxx_requires_valid_range(__first, __last);
5109 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
5111 _GLIBCXX_STD_A::__stable_sort(__first, __last,
5112 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5115 template<
typename _InputIterator1,
typename _InputIterator2,
5116 typename _OutputIterator,
5118 _GLIBCXX20_CONSTEXPR
5120 __set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5121 _InputIterator2 __first2, _InputIterator2 __last2,
5122 _OutputIterator __result, _Compare __comp)
5124 while (__first1 != __last1 && __first2 != __last2)
5126 if (__comp(__first1, __first2))
5128 *__result = *__first1;
5131 else if (__comp(__first2, __first1))
5133 *__result = *__first2;
5138 *__result = *__first1;
5144 return std::copy(__first2, __last2,
5145 std::copy(__first1, __last1, __result));
5167 template<
typename _InputIterator1,
typename _InputIterator2,
5168 typename _OutputIterator>
5169 _GLIBCXX20_CONSTEXPR
5170 inline _OutputIterator
5173 _OutputIterator __result)
5178 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5180 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5182 __glibcxx_function_requires(_LessThanOpConcept<
5185 __glibcxx_function_requires(_LessThanOpConcept<
5195 __gnu_cxx::__ops::__iter_less_iter());
5218 template<
typename _InputIterator1,
typename _InputIterator2,
5219 typename _OutputIterator,
typename _Compare>
5220 _GLIBCXX20_CONSTEXPR
5221 inline _OutputIterator
5224 _OutputIterator __result, _Compare __comp)
5229 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5231 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5233 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5236 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5246 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5249 template<
typename _InputIterator1,
typename _InputIterator2,
5250 typename _OutputIterator,
5252 _GLIBCXX20_CONSTEXPR
5254 __set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5255 _InputIterator2 __first2, _InputIterator2 __last2,
5256 _OutputIterator __result, _Compare __comp)
5258 while (__first1 != __last1 && __first2 != __last2)
5259 if (__comp(__first1, __first2))
5261 else if (__comp(__first2, __first1))
5265 *__result = *__first1;
5291 template<
typename _InputIterator1,
typename _InputIterator2,
5292 typename _OutputIterator>
5293 _GLIBCXX20_CONSTEXPR
5294 inline _OutputIterator
5297 _OutputIterator __result)
5302 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5304 __glibcxx_function_requires(_LessThanOpConcept<
5307 __glibcxx_function_requires(_LessThanOpConcept<
5317 __gnu_cxx::__ops::__iter_less_iter());
5341 template<
typename _InputIterator1,
typename _InputIterator2,
5342 typename _OutputIterator,
typename _Compare>
5343 _GLIBCXX20_CONSTEXPR
5344 inline _OutputIterator
5347 _OutputIterator __result, _Compare __comp)
5352 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5354 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5357 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5367 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5370 template<
typename _InputIterator1,
typename _InputIterator2,
5371 typename _OutputIterator,
5373 _GLIBCXX20_CONSTEXPR
5375 __set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5376 _InputIterator2 __first2, _InputIterator2 __last2,
5377 _OutputIterator __result, _Compare __comp)
5379 while (__first1 != __last1 && __first2 != __last2)
5380 if (__comp(__first1, __first2))
5382 *__result = *__first1;
5386 else if (__comp(__first2, __first1))
5393 return std::copy(__first1, __last1, __result);
5416 template<
typename _InputIterator1,
typename _InputIterator2,
5417 typename _OutputIterator>
5418 _GLIBCXX20_CONSTEXPR
5419 inline _OutputIterator
5422 _OutputIterator __result)
5427 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5429 __glibcxx_function_requires(_LessThanOpConcept<
5432 __glibcxx_function_requires(_LessThanOpConcept<
5442 __gnu_cxx::__ops::__iter_less_iter());
5468 template<
typename _InputIterator1,
typename _InputIterator2,
5469 typename _OutputIterator,
typename _Compare>
5470 _GLIBCXX20_CONSTEXPR
5471 inline _OutputIterator
5474 _OutputIterator __result, _Compare __comp)
5479 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5481 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5484 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5494 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5497 template<
typename _InputIterator1,
typename _InputIterator2,
5498 typename _OutputIterator,
5500 _GLIBCXX20_CONSTEXPR
5502 __set_symmetric_difference(_InputIterator1 __first1,
5503 _InputIterator1 __last1,
5504 _InputIterator2 __first2,
5505 _InputIterator2 __last2,
5506 _OutputIterator __result,
5509 while (__first1 != __last1 && __first2 != __last2)
5510 if (__comp(__first1, __first2))
5512 *__result = *__first1;
5516 else if (__comp(__first2, __first1))
5518 *__result = *__first2;
5527 return std::copy(__first2, __last2,
5528 std::copy(__first1, __last1, __result));
5549 template<
typename _InputIterator1,
typename _InputIterator2,
5550 typename _OutputIterator>
5551 _GLIBCXX20_CONSTEXPR
5552 inline _OutputIterator
5555 _OutputIterator __result)
5560 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5562 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5564 __glibcxx_function_requires(_LessThanOpConcept<
5567 __glibcxx_function_requires(_LessThanOpConcept<
5577 __gnu_cxx::__ops::__iter_less_iter());
5601 template<
typename _InputIterator1,
typename _InputIterator2,
5602 typename _OutputIterator,
typename _Compare>
5603 _GLIBCXX20_CONSTEXPR
5604 inline _OutputIterator
5607 _OutputIterator __result,
5613 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5615 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5617 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5620 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5630 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5633 template<
typename _ForwardIterator,
typename _Compare>
5634 _GLIBCXX14_CONSTEXPR
5636 __min_element(_ForwardIterator __first, _ForwardIterator __last,
5639 if (__first == __last)
5641 _ForwardIterator __result = __first;
5642 while (++__first != __last)
5643 if (__comp(__first, __result))
5655 template<
typename _ForwardIterator>
5656 _GLIBCXX14_CONSTEXPR
5662 __glibcxx_function_requires(_LessThanComparableConcept<
5664 __glibcxx_requires_valid_range(__first, __last);
5665 __glibcxx_requires_irreflexive(__first, __last);
5667 return _GLIBCXX_STD_A::__min_element(__first, __last,
5668 __gnu_cxx::__ops::__iter_less_iter());
5680 template<
typename _ForwardIterator,
typename _Compare>
5681 _GLIBCXX14_CONSTEXPR
5682 inline _ForwardIterator
5688 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5691 __glibcxx_requires_valid_range(__first, __last);
5692 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
5694 return _GLIBCXX_STD_A::__min_element(__first, __last,
5695 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5698 template<
typename _ForwardIterator,
typename _Compare>
5699 _GLIBCXX14_CONSTEXPR
5701 __max_element(_ForwardIterator __first, _ForwardIterator __last,
5704 if (__first == __last)
return __first;
5705 _ForwardIterator __result = __first;
5706 while (++__first != __last)
5707 if (__comp(__result, __first))
5719 template<
typename _ForwardIterator>
5720 _GLIBCXX14_CONSTEXPR
5721 inline _ForwardIterator
5726 __glibcxx_function_requires(_LessThanComparableConcept<
5728 __glibcxx_requires_valid_range(__first, __last);
5729 __glibcxx_requires_irreflexive(__first, __last);
5731 return _GLIBCXX_STD_A::__max_element(__first, __last,
5732 __gnu_cxx::__ops::__iter_less_iter());
5744 template<
typename _ForwardIterator,
typename _Compare>
5745 _GLIBCXX14_CONSTEXPR
5746 inline _ForwardIterator
5752 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5755 __glibcxx_requires_valid_range(__first, __last);
5756 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
5758 return _GLIBCXX_STD_A::__max_element(__first, __last,
5759 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5762#if __cplusplus >= 201402L
5764 template<
typename _InputIterator,
typename _RandomAccessIterator,
5765 typename _Size,
typename _UniformRandomBitGenerator>
5766 _RandomAccessIterator
5772 using __param_type =
typename __distrib_type::param_type;
5791 template<
typename _ForwardIterator,
typename _OutputIterator,
typename _Cat,
5792 typename _Size,
typename _UniformRandomBitGenerator>
5800 using __param_type =
typename __distrib_type::param_type;
5805 if (__first == __last)
5826 if (__p.first < __n)
5828 *
__out++ = *__first;
5834 if (__n == 0)
break;
5837 if (__p.second < __n)
5839 *
__out++ = *__first;
5849 for (; __n != 0; ++__first)
5852 *
__out++ = *__first;
5858#if __cplusplus > 201402L
5859#define __cpp_lib_sample 201603
5861 template<
typename _PopulationIterator,
typename _SampleIterator,
5862 typename _Distance,
typename _UniformRandomBitGenerator>
5864 sample(_PopulationIterator __first, _PopulationIterator __last,
5865 _SampleIterator __out, _Distance __n,
5866 _UniformRandomBitGenerator&& __g)
5868 using __pop_cat =
typename
5870 using __samp_cat =
typename
5874 __or_<is_convertible<__pop_cat, forward_iterator_tag>,
5875 is_convertible<__samp_cat, random_access_iterator_tag>>::value,
5876 "output range must use a RandomAccessIterator when input range"
5877 " does not meet the ForwardIterator requirements");
5879 static_assert(is_integral<_Distance>::value,
5880 "sample size must be an integer type");
5882 typename iterator_traits<_PopulationIterator>::difference_type __d = __n;
5883 return _GLIBCXX_STD_A::
5884 __sample(__first, __last, __pop_cat{}, __out, __samp_cat{}, __d,
5890_GLIBCXX_END_NAMESPACE_ALGO
5891_GLIBCXX_END_NAMESPACE_VERSION
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
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.
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.