64#if __cplusplus >= 201103L
70# if (__cplusplus <= 201103L || _GLIBCXX_USE_DEPRECATED)
77namespace std _GLIBCXX_VISIBILITY(default)
79_GLIBCXX_BEGIN_NAMESPACE_VERSION
82 template<
typename _Iterator,
typename _Compare>
86 _Iterator __c, _Compare __comp)
91 std::iter_swap(__result, __b);
92 else if (__comp(__a, __c))
93 std::iter_swap(__result, __c);
95 std::iter_swap(__result, __a);
97 else if (__comp(__a, __c))
98 std::iter_swap(__result, __a);
99 else if (__comp(__b, __c))
100 std::iter_swap(__result, __c);
102 std::iter_swap(__result, __b);
106 template<
typename _InputIterator,
typename _Predicate>
108 inline _InputIterator
113 __gnu_cxx::__ops::__negate(
__pred),
120 template<
typename _InputIterator,
typename _Predicate,
typename _Distance>
144 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
145 typename _BinaryPredicate>
148 __search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
149 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
150 _BinaryPredicate __predicate)
153 if (__first1 == __last1 || __first2 == __last2)
157 _ForwardIterator2 __p1(__first2);
158 if (++__p1 == __last2)
160 __gnu_cxx::__ops::__iter_comp_iter(__predicate, __first2));
163 _ForwardIterator1 __current = __first1;
169 __gnu_cxx::__ops::__iter_comp_iter(__predicate, __first2));
171 if (__first1 == __last1)
174 _ForwardIterator2 __p = __p1;
175 __current = __first1;
176 if (++__current == __last1)
179 while (__predicate(__current, __p))
181 if (++__p == __last2)
183 if (++__current == __last1)
196 template<
typename _ForwardIterator,
typename _Integer,
197 typename _UnaryPredicate>
205 while (__first != __last)
229 template<
typename _RandomAccessIter,
typename _Integer,
230 typename _UnaryPredicate>
253 return (__first - __count);
260 template<
typename _ForwardIterator,
typename _Integer,
261 typename _UnaryPredicate>
264 __search_n(_ForwardIterator __first, _ForwardIterator __last,
266 _UnaryPredicate __unary_pred)
279 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
280 typename _BinaryPredicate>
283 __find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
284 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
285 forward_iterator_tag, forward_iterator_tag,
286 _BinaryPredicate __comp)
288 if (__first2 == __last2)
291 _ForwardIterator1 __result = __last1;
294 _ForwardIterator1 __new_result
295 = std::__search(__first1, __last1, __first2, __last2, __comp);
296 if (__new_result == __last1)
300 __result = __new_result;
301 __first1 = __new_result;
308 template<
typename _BidirectionalIterator1,
typename _BidirectionalIterator2,
309 typename _BinaryPredicate>
311 _BidirectionalIterator1
312 __find_end(_BidirectionalIterator1 __first1,
313 _BidirectionalIterator1 __last1,
314 _BidirectionalIterator2 __first2,
315 _BidirectionalIterator2 __last2,
316 bidirectional_iterator_tag, bidirectional_iterator_tag,
317 _BinaryPredicate __comp)
320 __glibcxx_function_requires(_BidirectionalIteratorConcept<
321 _BidirectionalIterator1>)
322 __glibcxx_function_requires(_BidirectionalIteratorConcept<
323 _BidirectionalIterator2>)
325 typedef reverse_iterator<_BidirectionalIterator1> _RevIterator1;
326 typedef reverse_iterator<_BidirectionalIterator2> _RevIterator2;
328 _RevIterator1 __rlast1(__first1);
329 _RevIterator2 __rlast2(__first2);
330 _RevIterator1 __rresult =
std::__search(_RevIterator1(__last1), __rlast1,
331 _RevIterator2(__last2), __rlast2,
334 if (__rresult == __rlast1)
338 _BidirectionalIterator1 __result = __rresult.base();
370 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
372 inline _ForwardIterator1
379 __glibcxx_function_requires(_EqualOpConcept<
388 __gnu_cxx::__ops::__iter_equal_to_iter());
419 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
420 typename _BinaryPredicate>
422 inline _ForwardIterator1
439 __gnu_cxx::__ops::__iter_comp_iter(__comp));
442#if __cplusplus >= 201103L
455 template<
typename _InputIterator,
typename _Predicate>
459 {
return __last == std::find_if_not(__first, __last,
__pred); }
473 template<
typename _InputIterator,
typename _Predicate>
477 {
return __last == _GLIBCXX_STD_A::find_if(__first, __last,
__pred); }
492 template<
typename _InputIterator,
typename _Predicate>
496 {
return !std::none_of(__first, __last,
__pred); }
508 template<
typename _InputIterator,
typename _Predicate>
510 inline _InputIterator
516 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
518 __glibcxx_requires_valid_range(__first, __last);
520 __gnu_cxx::__ops::__pred_iter(
__pred));
533 template<
typename _InputIterator,
typename _Predicate>
539 __first = std::find_if_not(__first, __last,
__pred);
540 if (__first == __last)
543 return std::none_of(__first, __last,
__pred);
555 template<
typename _ForwardIterator,
typename _Predicate>
563 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
567 __glibcxx_requires_valid_range(__first, __last);
592 template<
typename _InputIterator,
typename _OutputIterator,
596 __remove_copy_if(_InputIterator __first, _InputIterator __last,
597 _OutputIterator __result, _Predicate __pred)
599 for (; __first != __last; ++__first)
600 if (!__pred(__first))
602 *__result = *__first;
622 template<
typename _InputIterator,
typename _OutputIterator,
typename _Tp>
624 inline _OutputIterator
626 _OutputIterator __result,
const _Tp& __value)
630 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
632 __glibcxx_function_requires(_EqualOpConcept<
634 __glibcxx_requires_valid_range(__first, __last);
636 return std::__remove_copy_if(__first, __last, __result,
637 __gnu_cxx::__ops::__iter_equals_val(__value));
655 template<
typename _InputIterator,
typename _OutputIterator,
658 inline _OutputIterator
660 _OutputIterator __result, _Predicate
__pred)
664 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
666 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
668 __glibcxx_requires_valid_range(__first, __last);
670 return std::__remove_copy_if(__first, __last, __result,
671 __gnu_cxx::__ops::__pred_iter(
__pred));
674#if __cplusplus >= 201103L
690 template<
typename _InputIterator,
typename _OutputIterator,
695 _OutputIterator __result, _Predicate
__pred)
699 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
701 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
703 __glibcxx_requires_valid_range(__first, __last);
705 for (; __first != __last; ++__first)
708 *__result = *__first;
714 template<
typename _InputIterator,
typename _Size,
typename _OutputIterator>
717 __copy_n(_InputIterator __first, _Size __n,
718 _OutputIterator __result, input_iterator_tag)
720 return std::__niter_wrap(__result,
721 __copy_n_a(__first, __n,
722 std::__niter_base(__result),
true));
725 template<
typename _RandomAccessIterator,
typename _Size,
726 typename _OutputIterator>
728 inline _OutputIterator
729 __copy_n(_RandomAccessIterator __first, _Size __n,
730 _OutputIterator __result, random_access_iterator_tag)
731 {
return std::copy(__first, __first + __n, __result); }
746 template<
typename _InputIterator,
typename _Size,
typename _OutputIterator>
748 inline _OutputIterator
753 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
756 const auto __n2 = std::__size_to_integer(__n);
760 __glibcxx_requires_can_increment(__first,
__n2);
761 __glibcxx_requires_can_increment(__result,
__n2);
763 return std::__copy_n(__first,
__n2, __result,
782 template<
typename _InputIterator,
typename _OutputIterator1,
783 typename _OutputIterator2,
typename _Predicate>
785 pair<_OutputIterator1, _OutputIterator2>
796 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
798 __glibcxx_requires_valid_range(__first, __last);
800 for (; __first != __last; ++__first)
833 template<
typename _ForwardIterator,
typename _Tp>
835 inline _ForwardIterator
840 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
842 __glibcxx_function_requires(_EqualOpConcept<
844 __glibcxx_requires_valid_range(__first, __last);
846 return std::__remove_if(__first, __last,
847 __gnu_cxx::__ops::__iter_equals_val(__value));
867 template<
typename _ForwardIterator,
typename _Predicate>
869 inline _ForwardIterator
874 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
876 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
878 __glibcxx_requires_valid_range(__first, __last);
880 return std::__remove_if(__first, __last,
881 __gnu_cxx::__ops::__pred_iter(
__pred));
884 template<
typename _ForwardIterator,
typename _BinaryPredicate>
887 __adjacent_find(_ForwardIterator __first, _ForwardIterator __last,
888 _BinaryPredicate __binary_pred)
890 if (__first == __last)
892 _ForwardIterator __next = __first;
893 while (++__next != __last)
895 if (__binary_pred(__first, __next))
902 template<
typename _ForwardIterator,
typename _BinaryPredicate>
905 __unique(_ForwardIterator __first, _ForwardIterator __last,
906 _BinaryPredicate __binary_pred)
909 __first = std::__adjacent_find(__first, __last, __binary_pred);
910 if (__first == __last)
914 _ForwardIterator __dest = __first;
916 while (++__first != __last)
917 if (!__binary_pred(__dest, __first))
918 *++__dest = _GLIBCXX_MOVE(*__first);
936 template<
typename _ForwardIterator>
938 inline _ForwardIterator
942 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
944 __glibcxx_function_requires(_EqualityComparableConcept<
946 __glibcxx_requires_valid_range(__first, __last);
948 return std::__unique(__first, __last,
949 __gnu_cxx::__ops::__iter_equal_to_iter());
967 template<
typename _ForwardIterator,
typename _BinaryPredicate>
969 inline _ForwardIterator
974 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
979 __glibcxx_requires_valid_range(__first, __last);
981 return std::__unique(__first, __last,
991 template<
typename _ForwardIterator,
typename _OutputIterator,
992 typename _BinaryPredicate>
1005 *__result = *__first;
1006 while (++__next != __last)
1010 *++__result = *__first;
1021 template<
typename _InputIterator,
typename _OutputIterator,
1022 typename _BinaryPredicate>
1023 _GLIBCXX20_CONSTEXPR
1038 *__result = __value;
1039 while (++__first != __last)
1043 *++__result = __value;
1054 template<
typename _InputIterator,
typename _ForwardIterator,
1055 typename _BinaryPredicate>
1056 _GLIBCXX20_CONSTEXPR
1066 *__result = *__first;
1067 while (++__first != __last)
1069 *++__result = *__first;
1078 template<
typename _B
idirectionalIterator>
1079 _GLIBCXX20_CONSTEXPR
1085 if (__first == __last || __first == --__last)
1089 std::iter_swap(__first, __last);
1099 template<
typename _RandomAccessIterator>
1100 _GLIBCXX20_CONSTEXPR
1105 if (__first == __last)
1108 while (__first < __last)
1110 std::iter_swap(__first, __last);
1128 template<
typename _B
idirectionalIterator>
1129 _GLIBCXX20_CONSTEXPR
1134 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
1136 __glibcxx_requires_valid_range(__first, __last);
1156 template<
typename _B
idirectionalIterator,
typename _OutputIterator>
1157 _GLIBCXX20_CONSTEXPR
1160 _OutputIterator __result)
1163 __glibcxx_function_requires(_BidirectionalIteratorConcept<
1165 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1167 __glibcxx_requires_valid_range(__first, __last);
1169 while (__first != __last)
1172 *__result = *__last;
1182 template<
typename _Eucl
ideanRingElement>
1183 _GLIBCXX20_CONSTEXPR
1184 _EuclideanRingElement
1196_GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2)
1199 template<
typename _ForwardIterator>
1200 _GLIBCXX20_CONSTEXPR
1207 if (__first == __middle)
1209 else if (__last == __middle)
1218 if (__first == __middle)
1232 if (__first == __middle)
1241 template<
typename _B
idirectionalIterator>
1242 _GLIBCXX20_CONSTEXPR
1243 _BidirectionalIterator
1250 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
1253 if (__first == __middle)
1255 else if (__last == __middle)
1261 while (__first != __middle && __middle != __last)
1263 std::iter_swap(__first, --__last);
1267 if (__first == __middle)
1280 template<
typename _RandomAccessIterator>
1281 _GLIBCXX20_CONSTEXPR
1282 _RandomAccessIterator
1289 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
1292 if (__first == __middle)
1294 else if (__last == __middle)
1307 std::swap_ranges(__first, __middle, __middle);
1320 _ValueType __t = _GLIBCXX_MOVE(*__p);
1321 _GLIBCXX_MOVE3(__p + 1, __p + __n, __p);
1322 *(__p + __n - 1) = _GLIBCXX_MOVE(__t);
1328 std::iter_swap(__p, __q);
1335 std::swap(__n,
__k);
1343 _ValueType __t = _GLIBCXX_MOVE(*(__p + __n - 1));
1344 _GLIBCXX_MOVE_BACKWARD3(__p, __p + __n - 1, __p + __n);
1345 *__p = _GLIBCXX_MOVE(__t);
1354 std::iter_swap(__p, __q);
1359 std::swap(__n,
__k);
1387 template<
typename _ForwardIterator>
1388 _GLIBCXX20_CONSTEXPR
1389 inline _ForwardIterator
1394 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1396 __glibcxx_requires_valid_range(__first, __middle);
1397 __glibcxx_requires_valid_range(__middle, __last);
1403_GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)
1425 template<
typename _ForwardIterator,
typename _OutputIterator>
1426 _GLIBCXX20_CONSTEXPR
1427 inline _OutputIterator
1433 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1435 __glibcxx_requires_valid_range(__first, __middle);
1436 __glibcxx_requires_valid_range(__middle, __last);
1438 return std::copy(__first, __middle,
1439 std::copy(__middle, __last, __result));
1443 template<
typename _ForwardIterator,
typename _Predicate>
1444 _GLIBCXX20_CONSTEXPR
1449 if (__first == __last)
1453 if (++__first == __last)
1458 while (++__next != __last)
1461 std::iter_swap(__first, __next);
1469 template<
typename _B
idirectionalIterator,
typename _Predicate>
1470 _GLIBCXX20_CONSTEXPR
1471 _BidirectionalIterator
1478 if (__first == __last)
1480 else if (
__pred(*__first))
1486 if (__first == __last)
1488 else if (!
bool(
__pred(*__last)))
1492 std::iter_swap(__first, __last);
1506 template<
typename _ForwardIterator,
typename _Pointer,
typename _Predicate,
1529 for (; __first != __last; ++__first)
1567 template<
typename _ForwardIterator,
typename _Predicate>
1569 __stable_partition(_ForwardIterator __first, _ForwardIterator __last,
1574 if (__first == __last)
1577 typedef typename iterator_traits<_ForwardIterator>::value_type
1579 typedef typename iterator_traits<_ForwardIterator>::difference_type
1582 _Temporary_buffer<_ForwardIterator, _ValueType>
1586 _DistanceType(__buf.requested_size()),
1588 _DistanceType(__buf.size()));
1608 template<
typename _ForwardIterator,
typename _Predicate>
1609 inline _ForwardIterator
1614 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1616 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
1618 __glibcxx_requires_valid_range(__first, __last);
1620 return std::__stable_partition(__first, __last,
1621 __gnu_cxx::__ops::__pred_iter(
__pred));
1628 template<
typename _RandomAccessIterator,
typename _Compare>
1629 _GLIBCXX20_CONSTEXPR
1631 __heap_select(_RandomAccessIterator __first,
1632 _RandomAccessIterator __middle,
1633 _RandomAccessIterator __last, _Compare __comp)
1635 std::__make_heap(__first, __middle, __comp);
1636 for (_RandomAccessIterator __i = __middle; __i < __last; ++__i)
1637 if (__comp(__i, __first))
1638 std::__pop_heap(__first, __middle, __i, __comp);
1643 template<
typename _InputIterator,
typename _RandomAccessIterator,
1645 _GLIBCXX20_CONSTEXPR
1646 _RandomAccessIterator
1647 __partial_sort_copy(_InputIterator __first, _InputIterator __last,
1648 _RandomAccessIterator __result_first,
1649 _RandomAccessIterator __result_last,
1652 typedef typename iterator_traits<_InputIterator>::value_type
1654 typedef iterator_traits<_RandomAccessIterator> _RItTraits;
1655 typedef typename _RItTraits::difference_type _DistanceType;
1657 if (__result_first == __result_last)
1658 return __result_last;
1659 _RandomAccessIterator __result_real_last = __result_first;
1660 while (__first != __last && __result_real_last != __result_last)
1662 *__result_real_last = *__first;
1663 ++__result_real_last;
1667 std::__make_heap(__result_first, __result_real_last, __comp);
1668 while (__first != __last)
1670 if (__comp(__first, __result_first))
1671 std::__adjust_heap(__result_first, _DistanceType(0),
1672 _DistanceType(__result_real_last
1674 _InputValueType(*__first), __comp);
1677 std::__sort_heap(__result_first, __result_real_last, __comp);
1678 return __result_real_last;
1701 template<
typename _InputIterator,
typename _RandomAccessIterator>
1702 _GLIBCXX20_CONSTEXPR
1703 inline _RandomAccessIterator
1708#ifdef _GLIBCXX_CONCEPT_CHECKS
1722 __glibcxx_requires_valid_range(__first, __last);
1723 __glibcxx_requires_irreflexive(__first, __last);
1728 __gnu_cxx::__ops::__iter_less_iter());
1751 template<
typename _InputIterator,
typename _RandomAccessIterator,
1753 _GLIBCXX20_CONSTEXPR
1754 inline _RandomAccessIterator
1760#ifdef _GLIBCXX_CONCEPT_CHECKS
1769 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
1773 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
1775 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
1777 __glibcxx_requires_valid_range(__first, __last);
1778 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
1783 __gnu_cxx::__ops::__iter_comp_iter(__comp));
1789 template<
typename _RandomAccessIterator,
typename _Compare>
1790 _GLIBCXX20_CONSTEXPR
1792 __unguarded_linear_insert(_RandomAccessIterator __last,
1795 typename iterator_traits<_RandomAccessIterator>::value_type
1796 __val = _GLIBCXX_MOVE(*__last);
1797 _RandomAccessIterator __next = __last;
1799 while (__comp(__val, __next))
1801 *__last = _GLIBCXX_MOVE(*__next);
1805 *__last = _GLIBCXX_MOVE(__val);
1809 template<
typename _RandomAccessIterator,
typename _Compare>
1810 _GLIBCXX20_CONSTEXPR
1812 __insertion_sort(_RandomAccessIterator __first,
1813 _RandomAccessIterator __last, _Compare __comp)
1815 if (__first == __last)
return;
1817 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
1819 if (__comp(__i, __first))
1821 typename iterator_traits<_RandomAccessIterator>::value_type
1822 __val = _GLIBCXX_MOVE(*__i);
1823 _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1);
1824 *__first = _GLIBCXX_MOVE(__val);
1828 __gnu_cxx::__ops::__val_comp_iter(__comp));
1833 template<
typename _RandomAccessIterator,
typename _Compare>
1834 _GLIBCXX20_CONSTEXPR
1836 __unguarded_insertion_sort(_RandomAccessIterator __first,
1837 _RandomAccessIterator __last, _Compare __comp)
1839 for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
1841 __gnu_cxx::__ops::__val_comp_iter(__comp));
1848 enum { _S_threshold = 16 };
1851 template<
typename _RandomAccessIterator,
typename _Compare>
1852 _GLIBCXX20_CONSTEXPR
1854 __final_insertion_sort(_RandomAccessIterator __first,
1855 _RandomAccessIterator __last, _Compare __comp)
1857 if (__last - __first >
int(_S_threshold))
1868 template<
typename _RandomAccessIterator,
typename _Compare>
1869 _GLIBCXX20_CONSTEXPR
1870 _RandomAccessIterator
1871 __unguarded_partition(_RandomAccessIterator __first,
1872 _RandomAccessIterator __last,
1873 _RandomAccessIterator __pivot, _Compare __comp)
1877 while (__comp(__first, __pivot))
1880 while (__comp(__pivot, __last))
1882 if (!(__first < __last))
1884 std::iter_swap(__first, __last);
1890 template<
typename _RandomAccessIterator,
typename _Compare>
1891 _GLIBCXX20_CONSTEXPR
1892 inline _RandomAccessIterator
1893 __unguarded_partition_pivot(_RandomAccessIterator __first,
1894 _RandomAccessIterator __last, _Compare __comp)
1896 _RandomAccessIterator __mid = __first + (__last - __first) / 2;
1902 template<
typename _RandomAccessIterator,
typename _Compare>
1903 _GLIBCXX20_CONSTEXPR
1905 __partial_sort(_RandomAccessIterator __first,
1906 _RandomAccessIterator __middle,
1907 _RandomAccessIterator __last,
1911 std::__sort_heap(__first, __middle, __comp);
1915 template<
typename _RandomAccessIterator,
typename _Size,
typename _Compare>
1916 _GLIBCXX20_CONSTEXPR
1918 __introsort_loop(_RandomAccessIterator __first,
1919 _RandomAccessIterator __last,
1920 _Size __depth_limit, _Compare __comp)
1922 while (__last - __first >
int(_S_threshold))
1924 if (__depth_limit == 0)
1930 _RandomAccessIterator __cut =
1939 template<
typename _RandomAccessIterator,
typename _Compare>
1940 _GLIBCXX20_CONSTEXPR
1942 __sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
1945 if (__first != __last)
1954 template<
typename _RandomAccessIterator,
typename _Size,
typename _Compare>
1955 _GLIBCXX20_CONSTEXPR
1957 __introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth,
1958 _RandomAccessIterator __last, _Size __depth_limit,
1961 while (__last - __first > 3)
1963 if (__depth_limit == 0)
1967 std::iter_swap(__first, __nth);
1971 _RandomAccessIterator __cut =
2002 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2003 _GLIBCXX20_CONSTEXPR
2004 inline _ForwardIterator
2006 const _Tp& __val, _Compare __comp)
2010 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2012 __glibcxx_requires_partitioned_lower_pred(__first, __last,
2015 return std::__lower_bound(__first, __last, __val,
2016 __gnu_cxx::__ops::__iter_comp_val(__comp));
2019 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2020 _GLIBCXX20_CONSTEXPR
2022 __upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2023 const _Tp& __val, _Compare __comp)
2025 typedef typename iterator_traits<_ForwardIterator>::difference_type
2032 _DistanceType __half = __len >> 1;
2033 _ForwardIterator __middle = __first;
2035 if (__comp(__val, __middle))
2041 __len = __len - __half - 1;
2058 template<
typename _ForwardIterator,
typename _Tp>
2059 _GLIBCXX20_CONSTEXPR
2060 inline _ForwardIterator
2066 __glibcxx_function_requires(_LessThanOpConcept<
2068 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2070 return std::__upper_bound(__first, __last, __val,
2071 __gnu_cxx::__ops::__val_less_iter());
2089 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2090 _GLIBCXX20_CONSTEXPR
2091 inline _ForwardIterator
2093 const _Tp& __val, _Compare __comp)
2097 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2099 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2102 return std::__upper_bound(__first, __last, __val,
2103 __gnu_cxx::__ops::__val_comp_iter(__comp));
2106 template<
typename _ForwardIterator,
typename _Tp,
2107 typename _CompareItTp,
typename _CompareTpIt>
2108 _GLIBCXX20_CONSTEXPR
2109 pair<_ForwardIterator, _ForwardIterator>
2110 __equal_range(_ForwardIterator __first, _ForwardIterator __last,
2112 _CompareItTp __comp_it_val, _CompareTpIt __comp_val_it)
2114 typedef typename iterator_traits<_ForwardIterator>::difference_type
2121 _DistanceType __half = __len >> 1;
2122 _ForwardIterator __middle = __first;
2124 if (__comp_it_val(__middle, __val))
2128 __len = __len - __half - 1;
2130 else if (__comp_val_it(__val, __middle))
2134 _ForwardIterator __left
2135 = std::__lower_bound(__first, __middle, __val, __comp_it_val);
2137 _ForwardIterator __right
2138 = std::__upper_bound(++__middle, __first, __val, __comp_val_it);
2139 return pair<_ForwardIterator, _ForwardIterator>(__left, __right);
2142 return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
2162 template<
typename _ForwardIterator,
typename _Tp>
2163 _GLIBCXX20_CONSTEXPR
2164 inline pair<_ForwardIterator, _ForwardIterator>
2170 __glibcxx_function_requires(_LessThanOpConcept<
2172 __glibcxx_function_requires(_LessThanOpConcept<
2174 __glibcxx_requires_partitioned_lower(__first, __last, __val);
2175 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2177 return std::__equal_range(__first, __last, __val,
2178 __gnu_cxx::__ops::__iter_less_val(),
2179 __gnu_cxx::__ops::__val_less_iter());
2199 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2200 _GLIBCXX20_CONSTEXPR
2201 inline pair<_ForwardIterator, _ForwardIterator>
2203 const _Tp& __val, _Compare __comp)
2207 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2209 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2211 __glibcxx_requires_partitioned_lower_pred(__first, __last,
2213 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2216 return std::__equal_range(__first, __last, __val,
2217 __gnu_cxx::__ops::__iter_comp_val(__comp),
2218 __gnu_cxx::__ops::__val_comp_iter(__comp));
2233 template<
typename _ForwardIterator,
typename _Tp>
2234 _GLIBCXX20_CONSTEXPR
2241 __glibcxx_function_requires(_LessThanOpConcept<
2243 __glibcxx_requires_partitioned_lower(__first, __last, __val);
2244 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2247 = std::__lower_bound(__first, __last, __val,
2248 __gnu_cxx::__ops::__iter_less_val());
2249 return __i != __last && !(__val < *__i);
2267 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2268 _GLIBCXX20_CONSTEXPR
2271 const _Tp& __val, _Compare __comp)
2275 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2277 __glibcxx_requires_partitioned_lower_pred(__first, __last,
2279 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2283 = std::__lower_bound(__first, __last, __val,
2284 __gnu_cxx::__ops::__iter_comp_val(__comp));
2285 return __i != __last && !bool(__comp(__val, *__i));
2291 template<
typename _InputIterator1,
typename _InputIterator2,
2292 typename _OutputIterator,
typename _Compare>
2296 _OutputIterator __result, _Compare __comp)
2302 *__result = _GLIBCXX_MOVE(*
__first2);
2307 *__result = _GLIBCXX_MOVE(*
__first1);
2317 template<
typename _BidirectionalIterator1,
typename _BidirectionalIterator2,
2318 typename _BidirectionalIterator3,
typename _Compare>
2341 *--__result = _GLIBCXX_MOVE(*
__last1);
2351 *--__result = _GLIBCXX_MOVE(*
__last2);
2360 template<
typename _BidirectionalIterator1,
typename _BidirectionalIterator2,
2362 _BidirectionalIterator1
2376 _GLIBCXX_MOVE_BACKWARD3(__first, __middle, __last);
2387 _GLIBCXX_MOVE3(__middle, __last, __first);
2394 return std::rotate(__first, __middle, __last);
2398 template<
typename _BidirectionalIterator,
typename _Distance,
2399 typename _Pointer,
typename _Compare>
2405 _Pointer
__buffer, _Compare __comp)
2421 template<
typename _BidirectionalIterator,
typename _Distance,
2422 typename _Pointer,
typename _Compare>
2424 __merge_adaptive_resize(_BidirectionalIterator __first,
2425 _BidirectionalIterator __middle,
2426 _BidirectionalIterator __last,
2427 _Distance __len1, _Distance __len2,
2428 _Pointer __buffer, _Distance __buffer_size,
2431 if (__len1 <= __buffer_size || __len2 <= __buffer_size)
2433 __len1, __len2, __buffer, __comp);
2436 _BidirectionalIterator __first_cut = __first;
2437 _BidirectionalIterator __second_cut = __middle;
2438 _Distance __len11 = 0;
2439 _Distance __len22 = 0;
2440 if (__len1 > __len2)
2442 __len11 = __len1 / 2;
2445 = std::__lower_bound(__middle, __last, *__first_cut,
2446 __gnu_cxx::__ops::__iter_comp_val(__comp));
2451 __len22 = __len2 / 2;
2454 = std::__upper_bound(__first, __middle, *__second_cut,
2455 __gnu_cxx::__ops::__val_comp_iter(__comp));
2459 _BidirectionalIterator __new_middle
2461 _Distance(__len1 - __len11), __len22,
2462 __buffer, __buffer_size);
2463 std::__merge_adaptive_resize(__first, __first_cut, __new_middle,
2465 __buffer, __buffer_size, __comp);
2466 std::__merge_adaptive_resize(__new_middle, __second_cut, __last,
2467 _Distance(__len1 - __len11),
2468 _Distance(__len2 - __len22),
2469 __buffer, __buffer_size, __comp);
2474 template<
typename _BidirectionalIterator,
typename _Distance,
2488 if (__comp(__middle, __first))
2489 std::iter_swap(__first, __middle);
2502 = std::__lower_bound(__middle, __last, *
__first_cut,
2503 __gnu_cxx::__ops::__iter_comp_val(__comp));
2512 __gnu_cxx::__ops::__val_comp_iter(__comp));
2524 template<
typename _B
idirectionalIterator,
typename _Compare>
2526 __inplace_merge(_BidirectionalIterator __first,
2527 _BidirectionalIterator __middle,
2528 _BidirectionalIterator __last,
2531 typedef typename iterator_traits<_BidirectionalIterator>::value_type
2533 typedef typename iterator_traits<_BidirectionalIterator>::difference_type
2536 if (__first == __middle || __middle == __last)
2539 const _DistanceType __len1 =
std::distance(__first, __middle);
2540 const _DistanceType __len2 =
std::distance(__middle, __last);
2543 typedef _Temporary_buffer<_BidirectionalIterator, _ValueType> _TmpBuf;
2546 _TmpBuf __buf(__first,
std::min(__len1, __len2));
2548 if (__builtin_expect(__buf.size() == __buf.requested_size(),
true))
2550 (__first, __middle, __last, __len1, __len2, __buf.begin(), __comp);
2551 else if (__builtin_expect(__buf.begin() == 0,
false))
2553 (__first, __middle, __last, __len1, __len2, __comp);
2555 std::__merge_adaptive_resize
2556 (__first, __middle, __last, __len1, __len2, __buf.begin(),
2557 _DistanceType(__buf.size()), __comp);
2560 (__first, __middle, __last, __len1, __len2, __comp);
2582 template<
typename _B
idirectionalIterator>
2589 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
2591 __glibcxx_function_requires(_LessThanComparableConcept<
2593 __glibcxx_requires_sorted(__first, __middle);
2594 __glibcxx_requires_sorted(__middle, __last);
2595 __glibcxx_requires_irreflexive(__first, __last);
2597 std::__inplace_merge(__first, __middle, __last,
2598 __gnu_cxx::__ops::__iter_less_iter());
2623 template<
typename _B
idirectionalIterator,
typename _Compare>
2631 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
2633 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2636 __glibcxx_requires_sorted_pred(__first, __middle, __comp);
2637 __glibcxx_requires_sorted_pred(__middle, __last, __comp);
2638 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
2640 std::__inplace_merge(__first, __middle, __last,
2641 __gnu_cxx::__ops::__iter_comp_iter(__comp));
2646 template<
typename _InputIterator,
typename _OutputIterator,
2651 _OutputIterator __result, _Compare __comp)
2657 *__result = _GLIBCXX_MOVE(*
__first2);
2662 *__result = _GLIBCXX_MOVE(*
__first1);
2672 template<
typename _RandomAccessIterator1,
typename _RandomAccessIterator2,
2673 typename _Distance,
typename _Compare>
2675 __merge_sort_loop(_RandomAccessIterator1 __first,
2676 _RandomAccessIterator1 __last,
2677 _RandomAccessIterator2 __result, _Distance __step_size,
2680 const _Distance __two_step = 2 * __step_size;
2682 while (__last - __first >= __two_step)
2685 __first + __step_size,
2686 __first + __two_step,
2688 __first += __two_step;
2690 __step_size =
std::min(_Distance(__last - __first), __step_size);
2693 __first + __step_size, __last, __result, __comp);
2696 template<
typename _RandomAccessIterator,
typename _Distance,
2698 _GLIBCXX20_CONSTEXPR
2700 __chunk_insertion_sort(_RandomAccessIterator __first,
2701 _RandomAccessIterator __last,
2702 _Distance __chunk_size, _Compare __comp)
2704 while (__last - __first >= __chunk_size)
2707 __first += __chunk_size;
2712 enum { _S_chunk_size = 7 };
2714 template<
typename _RandomAccessIterator,
typename _Po
inter,
typename _Compare>
2716 __merge_sort_with_buffer(_RandomAccessIterator __first,
2717 _RandomAccessIterator __last,
2718 _Pointer __buffer, _Compare __comp)
2720 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
2723 const _Distance __len = __last - __first;
2724 const _Pointer __buffer_last = __buffer + __len;
2726 _Distance __step_size = _S_chunk_size;
2727 std::__chunk_insertion_sort(__first, __last, __step_size, __comp);
2729 while (__step_size < __len)
2731 std::__merge_sort_loop(__first, __last, __buffer,
2732 __step_size, __comp);
2734 std::__merge_sort_loop(__buffer, __buffer_last, __first,
2735 __step_size, __comp);
2740 template<
typename _RandomAccessIterator,
typename _Po
inter,
typename _Compare>
2742 __stable_sort_adaptive(_RandomAccessIterator __first,
2743 _RandomAccessIterator __middle,
2744 _RandomAccessIterator __last,
2745 _Pointer __buffer, _Compare __comp)
2747 std::__merge_sort_with_buffer(__first, __middle, __buffer, __comp);
2748 std::__merge_sort_with_buffer(__middle, __last, __buffer, __comp);
2751 __middle - __first, __last - __middle,
2755 template<
typename _RandomAccessIterator,
typename _Pointer,
2756 typename _Distance,
typename _Compare>
2758 __stable_sort_adaptive_resize(_RandomAccessIterator __first,
2759 _RandomAccessIterator __last,
2760 _Pointer __buffer, _Distance __buffer_size,
2763 const _Distance __len = (__last - __first + 1) / 2;
2764 const _RandomAccessIterator __middle = __first + __len;
2765 if (__len > __buffer_size)
2767 std::__stable_sort_adaptive_resize(__first, __middle, __buffer,
2768 __buffer_size, __comp);
2769 std::__stable_sort_adaptive_resize(__middle, __last, __buffer,
2770 __buffer_size, __comp);
2771 std::__merge_adaptive_resize(__first, __middle, __last,
2772 _Distance(__middle - __first),
2773 _Distance(__last - __middle),
2774 __buffer, __buffer_size,
2778 std::__stable_sort_adaptive(__first, __middle, __last,
2783 template<
typename _RandomAccessIterator,
typename _Compare>
2788 if (__last - __first < 15)
2809 template<
typename _InputIterator1,
typename _InputIterator2,
2811 _GLIBCXX20_CONSTEXPR
2813 __includes(_InputIterator1 __first1, _InputIterator1 __last1,
2814 _InputIterator2 __first2, _InputIterator2 __last2,
2817 while (__first1 != __last1 && __first2 != __last2)
2819 if (__comp(__first2, __first1))
2821 if (!__comp(__first1, __first2))
2826 return __first2 == __last2;
2847 template<
typename _InputIterator1,
typename _InputIterator2>
2848 _GLIBCXX20_CONSTEXPR
2856 __glibcxx_function_requires(_LessThanOpConcept<
2859 __glibcxx_function_requires(_LessThanOpConcept<
2868 __gnu_cxx::__ops::__iter_less_iter());
2892 template<
typename _InputIterator1,
typename _InputIterator2,
2894 _GLIBCXX20_CONSTEXPR
2903 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2906 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2915 __gnu_cxx::__ops::__iter_comp_iter(__comp));
2928 template<
typename _B
idirectionalIterator,
typename _Compare>
2929 _GLIBCXX20_CONSTEXPR
2931 __next_permutation(_BidirectionalIterator __first,
2932 _BidirectionalIterator __last, _Compare __comp)
2934 if (__first == __last)
2936 _BidirectionalIterator __i = __first;
2945 _BidirectionalIterator __ii = __i;
2947 if (__comp(__i, __ii))
2949 _BidirectionalIterator __j = __last;
2950 while (!__comp(__i, --__j))
2952 std::iter_swap(__i, __j);
2978 template<
typename _B
idirectionalIterator>
2979 _GLIBCXX20_CONSTEXPR
2985 __glibcxx_function_requires(_BidirectionalIteratorConcept<
2987 __glibcxx_function_requires(_LessThanComparableConcept<
2989 __glibcxx_requires_valid_range(__first, __last);
2990 __glibcxx_requires_irreflexive(__first, __last);
2992 return std::__next_permutation
2993 (__first, __last, __gnu_cxx::__ops::__iter_less_iter());
3011 template<
typename _B
idirectionalIterator,
typename _Compare>
3012 _GLIBCXX20_CONSTEXPR
3018 __glibcxx_function_requires(_BidirectionalIteratorConcept<
3020 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3023 __glibcxx_requires_valid_range(__first, __last);
3024 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
3026 return std::__next_permutation
3027 (__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
3030 template<
typename _B
idirectionalIterator,
typename _Compare>
3031 _GLIBCXX20_CONSTEXPR
3033 __prev_permutation(_BidirectionalIterator __first,
3034 _BidirectionalIterator __last, _Compare __comp)
3036 if (__first == __last)
3038 _BidirectionalIterator __i = __first;
3047 _BidirectionalIterator __ii = __i;
3049 if (__comp(__ii, __i))
3051 _BidirectionalIterator __j = __last;
3052 while (!__comp(--__j, __i))
3054 std::iter_swap(__i, __j);
3081 template<
typename _B
idirectionalIterator>
3082 _GLIBCXX20_CONSTEXPR
3088 __glibcxx_function_requires(_BidirectionalIteratorConcept<
3090 __glibcxx_function_requires(_LessThanComparableConcept<
3092 __glibcxx_requires_valid_range(__first, __last);
3093 __glibcxx_requires_irreflexive(__first, __last);
3095 return std::__prev_permutation(__first, __last,
3096 __gnu_cxx::__ops::__iter_less_iter());
3114 template<
typename _B
idirectionalIterator,
typename _Compare>
3115 _GLIBCXX20_CONSTEXPR
3121 __glibcxx_function_requires(_BidirectionalIteratorConcept<
3123 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3126 __glibcxx_requires_valid_range(__first, __last);
3127 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
3129 return std::__prev_permutation(__first, __last,
3130 __gnu_cxx::__ops::__iter_comp_iter(__comp));
3136 template<
typename _InputIterator,
typename _OutputIterator,
3137 typename _Predicate,
typename _Tp>
3138 _GLIBCXX20_CONSTEXPR
3140 __replace_copy_if(_InputIterator __first, _InputIterator __last,
3141 _OutputIterator __result,
3142 _Predicate __pred,
const _Tp& __new_value)
3144 for (; __first != __last; ++__first, (void)++__result)
3145 if (__pred(__first))
3146 *__result = __new_value;
3148 *__result = *__first;
3166 template<
typename _InputIterator,
typename _OutputIterator,
typename _Tp>
3167 _GLIBCXX20_CONSTEXPR
3168 inline _OutputIterator
3170 _OutputIterator __result,
3175 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
3177 __glibcxx_function_requires(_EqualOpConcept<
3179 __glibcxx_requires_valid_range(__first, __last);
3181 return std::__replace_copy_if(__first, __last, __result,
3201 template<
typename _InputIterator,
typename _OutputIterator,
3202 typename _Predicate,
typename _Tp>
3203 _GLIBCXX20_CONSTEXPR
3204 inline _OutputIterator
3206 _OutputIterator __result,
3211 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
3213 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
3215 __glibcxx_requires_valid_range(__first, __last);
3217 return std::__replace_copy_if(__first, __last, __result,
3218 __gnu_cxx::__ops::__pred_iter(
__pred),
3222#if __cplusplus >= 201103L
3230 template<
typename _ForwardIterator>
3231 _GLIBCXX20_CONSTEXPR
3234 {
return std::is_sorted_until(__first, __last) == __last; }
3245 template<
typename _ForwardIterator,
typename _Compare>
3246 _GLIBCXX20_CONSTEXPR
3250 {
return std::is_sorted_until(__first, __last, __comp) == __last; }
3252 template<
typename _ForwardIterator,
typename _Compare>
3253 _GLIBCXX20_CONSTEXPR
3255 __is_sorted_until(_ForwardIterator __first, _ForwardIterator __last,
3258 if (__first == __last)
3261 _ForwardIterator __next = __first;
3262 for (++__next; __next != __last; __first = __next, (void)++__next)
3263 if (__comp(__next, __first))
3276 template<
typename _ForwardIterator>
3277 _GLIBCXX20_CONSTEXPR
3278 inline _ForwardIterator
3283 __glibcxx_function_requires(_LessThanComparableConcept<
3285 __glibcxx_requires_valid_range(__first, __last);
3286 __glibcxx_requires_irreflexive(__first, __last);
3288 return std::__is_sorted_until(__first, __last,
3289 __gnu_cxx::__ops::__iter_less_iter());
3301 template<
typename _ForwardIterator,
typename _Compare>
3302 _GLIBCXX20_CONSTEXPR
3303 inline _ForwardIterator
3309 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3312 __glibcxx_requires_valid_range(__first, __last);
3313 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
3315 return std::__is_sorted_until(__first, __last,
3316 __gnu_cxx::__ops::__iter_comp_iter(__comp));
3327 template<
typename _Tp>
3328 _GLIBCXX14_CONSTEXPR
3329 inline pair<const _Tp&, const _Tp&>
3348 template<
typename _Tp,
typename _Compare>
3349 _GLIBCXX14_CONSTEXPR
3350 inline pair<const _Tp&, const _Tp&>
3351 minmax(
const _Tp& __a,
const _Tp& __b, _Compare __comp)
3357 template<
typename _ForwardIterator,
typename _Compare>
3358 _GLIBCXX14_CONSTEXPR
3359 pair<_ForwardIterator, _ForwardIterator>
3360 __minmax_element(_ForwardIterator __first, _ForwardIterator __last,
3363 _ForwardIterator __next = __first;
3364 if (__first == __last
3365 || ++__next == __last)
3366 return std::make_pair(__first, __first);
3368 _ForwardIterator __min{}, __max{};
3369 if (__comp(__next, __first))
3383 while (__first != __last)
3386 if (++__next == __last)
3388 if (__comp(__first, __min))
3390 else if (!__comp(__first, __max))
3395 if (__comp(__next, __first))
3397 if (__comp(__next, __min))
3399 if (!__comp(__first, __max))
3404 if (__comp(__first, __min))
3406 if (!__comp(__next, __max))
3414 return std::make_pair(__min, __max);
3428 template<
typename _ForwardIterator>
3429 _GLIBCXX14_CONSTEXPR
3430 inline pair<_ForwardIterator, _ForwardIterator>
3435 __glibcxx_function_requires(_LessThanComparableConcept<
3437 __glibcxx_requires_valid_range(__first, __last);
3438 __glibcxx_requires_irreflexive(__first, __last);
3440 return std::__minmax_element(__first, __last,
3441 __gnu_cxx::__ops::__iter_less_iter());
3456 template<
typename _ForwardIterator,
typename _Compare>
3457 _GLIBCXX14_CONSTEXPR
3458 inline pair<_ForwardIterator, _ForwardIterator>
3464 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3467 __glibcxx_requires_valid_range(__first, __last);
3468 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
3470 return std::__minmax_element(__first, __last,
3471 __gnu_cxx::__ops::__iter_comp_iter(__comp));
3474 template<
typename _Tp>
3475 _GLIBCXX14_CONSTEXPR
3476 inline pair<_Tp, _Tp>
3477 minmax(initializer_list<_Tp> __l)
3479 __glibcxx_requires_irreflexive(__l.begin(), __l.end());
3480 pair<const _Tp*, const _Tp*> __p =
3481 std::__minmax_element(__l.begin(), __l.end(),
3482 __gnu_cxx::__ops::__iter_less_iter());
3483 return std::make_pair(*__p.first, *__p.second);
3486 template<
typename _Tp,
typename _Compare>
3487 _GLIBCXX14_CONSTEXPR
3488 inline pair<_Tp, _Tp>
3489 minmax(initializer_list<_Tp> __l, _Compare __comp)
3491 __glibcxx_requires_irreflexive_pred(__l.begin(), __l.end(), __comp);
3492 pair<const _Tp*, const _Tp*> __p =
3493 std::__minmax_element(__l.begin(), __l.end(),
3494 __gnu_cxx::__ops::__iter_comp_iter(__comp));
3495 return std::make_pair(*__p.first, *__p.second);
3512 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
3513 typename _BinaryPredicate>
3514 _GLIBCXX20_CONSTEXPR
3528 __gnu_cxx::__ops::__iter_comp_iter(
__pred));
3531#if __cplusplus > 201103L
3532 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
3533 typename _BinaryPredicate>
3534 _GLIBCXX20_CONSTEXPR
3536 __is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3537 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
3538 _BinaryPredicate __pred)
3541 =
typename iterator_traits<_ForwardIterator1>::iterator_category;
3543 =
typename iterator_traits<_ForwardIterator2>::iterator_category;
3544 using _It1_is_RA = is_same<_Cat1, random_access_iterator_tag>;
3545 using _It2_is_RA = is_same<_Cat2, random_access_iterator_tag>;
3546 constexpr bool __ra_iters = _It1_is_RA() && _It2_is_RA();
3557 for (; __first1 != __last1 && __first2 != __last2;
3558 ++__first1, (void)++__first2)
3559 if (!__pred(__first1, __first2))
3564 if (__first1 == __last1)
3571 if (__d1 == 0 && __d2 == 0)
3577 for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
3580 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)))
3583 auto __matches = std::__count_if(__first2, __last2,
3584 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan));
3586 || std::__count_if(__scan, __last1,
3587 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan))
3607 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
3608 _GLIBCXX20_CONSTEXPR
3618 __gnu_cxx::__ops::__iter_equal_to_iter());
3635 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
3636 typename _BinaryPredicate>
3637 _GLIBCXX20_CONSTEXPR
3647 __gnu_cxx::__ops::__iter_comp_iter(
__pred));
3650#if __cplusplus >= 201703L
3652#define __cpp_lib_clamp 201603L
3665 template<
typename _Tp>
3666 constexpr const _Tp&
3685 template<
typename _Tp,
typename _Compare>
3686 constexpr const _Tp&
3689 __glibcxx_assert(!__comp(
__hi,
__lo));
3695#ifdef _GLIBCXX_USE_C99_STDINT_TR1
3717 template<
typename _IntType,
typename _UniformRandomBitGenerator>
3718 pair<_IntType, _IntType>
3724 return std::make_pair(__x /
__b1, __x %
__b1);
3739 template<
typename _RandomAccessIterator,
3740 typename _UniformRandomNumberGenerator>
3746 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
3748 __glibcxx_requires_valid_range(__first, __last);
3750 if (__first == __last)
3756 typedef typename std::make_unsigned<_DistanceType>::type
__ud_type;
3758 typedef typename __distr_type::param_type
__p_type;
3780 std::iter_swap(__i++, __first + __d(
__g));
3787 while (__i != __last)
3794 std::iter_swap(__i++, __first +
__pospos.first);
3795 std::iter_swap(__i++, __first +
__pospos.second);
3804 std::iter_swap(__i, __first + __d(
__g,
__p_type(0, __i - __first)));
3810_GLIBCXX_BEGIN_NAMESPACE_ALGO
3824 template<
typename _InputIterator,
typename _Function>
3825 _GLIBCXX20_CONSTEXPR
3831 __glibcxx_requires_valid_range(__first, __last);
3832 for (; __first != __last; ++__first)
3837#if __cplusplus >= 201703L
3850 template<
typename _InputIterator,
typename _Size,
typename _Function>
3851 _GLIBCXX20_CONSTEXPR
3855 auto __n2 = std::__size_to_integer(__n);
3861 auto __last = __first +
__n2;
3862 std::for_each(__first, __last,
std::move(__f));
3886 template<
typename _InputIterator,
typename _Tp>
3887 _GLIBCXX20_CONSTEXPR
3888 inline _InputIterator
3894 __glibcxx_function_requires(_EqualOpConcept<
3896 __glibcxx_requires_valid_range(__first, __last);
3898 __gnu_cxx::__ops::__iter_equals_val(__val));
3911 template<
typename _InputIterator,
typename _Predicate>
3912 _GLIBCXX20_CONSTEXPR
3913 inline _InputIterator
3919 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
3921 __glibcxx_requires_valid_range(__first, __last);
3924 __gnu_cxx::__ops::__pred_iter(
__pred));
3943 template<
typename _InputIterator,
typename _ForwardIterator>
3944 _GLIBCXX20_CONSTEXPR
3952 __glibcxx_function_requires(_EqualOpConcept<
3984 template<
typename _InputIterator,
typename _ForwardIterator,
3985 typename _BinaryPredicate>
3986 _GLIBCXX20_CONSTEXPR
4017 template<
typename _ForwardIterator>
4018 _GLIBCXX20_CONSTEXPR
4019 inline _ForwardIterator
4024 __glibcxx_function_requires(_EqualityComparableConcept<
4026 __glibcxx_requires_valid_range(__first, __last);
4028 return std::__adjacent_find(__first, __last,
4029 __gnu_cxx::__ops::__iter_equal_to_iter());
4043 template<
typename _ForwardIterator,
typename _BinaryPredicate>
4044 _GLIBCXX20_CONSTEXPR
4045 inline _ForwardIterator
4054 __glibcxx_requires_valid_range(__first, __last);
4056 return std::__adjacent_find(__first, __last,
4069 template<
typename _InputIterator,
typename _Tp>
4070 _GLIBCXX20_CONSTEXPR
4071 inline typename iterator_traits<_InputIterator>::difference_type
4076 __glibcxx_function_requires(_EqualOpConcept<
4078 __glibcxx_requires_valid_range(__first, __last);
4080 return std::__count_if(__first, __last,
4081 __gnu_cxx::__ops::__iter_equals_val(__value));
4093 template<
typename _InputIterator,
typename _Predicate>
4094 _GLIBCXX20_CONSTEXPR
4095 inline typename iterator_traits<_InputIterator>::difference_type
4100 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4102 __glibcxx_requires_valid_range(__first, __last);
4104 return std::__count_if(__first, __last,
4105 __gnu_cxx::__ops::__pred_iter(
__pred));
4134 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
4135 _GLIBCXX20_CONSTEXPR
4136 inline _ForwardIterator1
4143 __glibcxx_function_requires(_EqualOpConcept<
4150 __gnu_cxx::__ops::__iter_equal_to_iter());
4174 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
4175 typename _BinaryPredicate>
4176 _GLIBCXX20_CONSTEXPR
4177 inline _ForwardIterator1
4210 template<
typename _ForwardIterator,
typename _Integer,
typename _Tp>
4211 _GLIBCXX20_CONSTEXPR
4212 inline _ForwardIterator
4214 _Integer __count,
const _Tp& __val)
4218 __glibcxx_function_requires(_EqualOpConcept<
4220 __glibcxx_requires_valid_range(__first, __last);
4222 return std::__search_n(__first, __last, __count,
4223 __gnu_cxx::__ops::__iter_equals_val(__val));
4244 template<
typename _ForwardIterator,
typename _Integer,
typename _Tp,
4245 typename _BinaryPredicate>
4246 _GLIBCXX20_CONSTEXPR
4247 inline _ForwardIterator
4249 _Integer __count,
const _Tp& __val,
4256 __glibcxx_requires_valid_range(__first, __last);
4258 return std::__search_n(__first, __last, __count,
4262#if __cplusplus >= 201703L
4270 template<
typename _ForwardIterator,
typename _Searcher>
4271 _GLIBCXX20_CONSTEXPR
4272 inline _ForwardIterator
4275 {
return __searcher(__first, __last).first; }
4294 template<
typename _InputIterator,
typename _OutputIterator,
4295 typename _UnaryOperation>
4296 _GLIBCXX20_CONSTEXPR
4303 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4306 __glibcxx_requires_valid_range(__first, __last);
4308 for (; __first != __last; ++__first, (
void)++__result)
4332 template<
typename _InputIterator1,
typename _InputIterator2,
4333 typename _OutputIterator,
typename _BinaryOperation>
4334 _GLIBCXX20_CONSTEXPR
4343 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4366 template<
typename _ForwardIterator,
typename _Tp>
4367 _GLIBCXX20_CONSTEXPR
4373 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4375 __glibcxx_function_requires(_EqualOpConcept<
4377 __glibcxx_function_requires(_ConvertibleConcept<_Tp,
4379 __glibcxx_requires_valid_range(__first, __last);
4381 for (; __first != __last; ++__first)
4399 template<
typename _ForwardIterator,
typename _Predicate,
typename _Tp>
4400 _GLIBCXX20_CONSTEXPR
4406 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4408 __glibcxx_function_requires(_ConvertibleConcept<_Tp,
4410 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4412 __glibcxx_requires_valid_range(__first, __last);
4414 for (; __first != __last; ++__first)
4431 template<
typename _ForwardIterator,
typename _Generator>
4432 _GLIBCXX20_CONSTEXPR
4439 __glibcxx_function_requires(_GeneratorConcept<
_Generator,
4441 __glibcxx_requires_valid_range(__first, __last);
4443 for (; __first != __last; ++__first)
4464 template<
typename _OutputIterator,
typename _Size,
typename _Generator>
4465 _GLIBCXX20_CONSTEXPR
4470 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4472 __typeof__(
__gen())>)
4499 template<
typename _InputIterator,
typename _OutputIterator>
4500 _GLIBCXX20_CONSTEXPR
4501 inline _OutputIterator
4503 _OutputIterator __result)
4507 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4509 __glibcxx_function_requires(_EqualityComparableConcept<
4511 __glibcxx_requires_valid_range(__first, __last);
4513 if (__first == __last)
4516 __gnu_cxx::__ops::__iter_equal_to_iter(),
4539 template<
typename _InputIterator,
typename _OutputIterator,
4540 typename _BinaryPredicate>
4541 _GLIBCXX20_CONSTEXPR
4542 inline _OutputIterator
4544 _OutputIterator __result,
4549 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4551 __glibcxx_requires_valid_range(__first, __last);
4553 if (__first == __last)
4561#if __cplusplus <= 201103L || _GLIBCXX_USE_DEPRECATED
4578 template<
typename _RandomAccessIterator>
4579 _GLIBCXX14_DEPRECATED_SUGGEST(
"std::shuffle")
4584 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4586 __glibcxx_requires_valid_range(__first, __last);
4588 if (__first != __last)
4593 + std::rand() % ((__i - __first) + 1);
4595 std::iter_swap(__i, __j);
4617 template<
typename _RandomAccessIterator,
typename _RandomNumberGenerator>
4618 _GLIBCXX14_DEPRECATED_SUGGEST(
"std::shuffle")
4621#if __cplusplus >= 201103L
4628 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4630 __glibcxx_requires_valid_range(__first, __last);
4632 if (__first == __last)
4638 std::iter_swap(__i, __j);
4659 template<
typename _ForwardIterator,
typename _Predicate>
4660 _GLIBCXX20_CONSTEXPR
4661 inline _ForwardIterator
4666 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4668 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4670 __glibcxx_requires_valid_range(__first, __last);
4694 template<
typename _RandomAccessIterator>
4695 _GLIBCXX20_CONSTEXPR
4702 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4704 __glibcxx_function_requires(_LessThanComparableConcept<
4706 __glibcxx_requires_valid_range(__first, __middle);
4707 __glibcxx_requires_valid_range(__middle, __last);
4708 __glibcxx_requires_irreflexive(__first, __last);
4711 __gnu_cxx::__ops::__iter_less_iter());
4733 template<
typename _RandomAccessIterator,
typename _Compare>
4734 _GLIBCXX20_CONSTEXPR
4742 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4744 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4747 __glibcxx_requires_valid_range(__first, __middle);
4748 __glibcxx_requires_valid_range(__middle, __last);
4749 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
4752 __gnu_cxx::__ops::__iter_comp_iter(__comp));
4770 template<
typename _RandomAccessIterator>
4771 _GLIBCXX20_CONSTEXPR
4777 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4779 __glibcxx_function_requires(_LessThanComparableConcept<
4781 __glibcxx_requires_valid_range(__first,
__nth);
4782 __glibcxx_requires_valid_range(
__nth, __last);
4783 __glibcxx_requires_irreflexive(__first, __last);
4785 if (__first == __last ||
__nth == __last)
4790 __gnu_cxx::__ops::__iter_less_iter());
4810 template<
typename _RandomAccessIterator,
typename _Compare>
4811 _GLIBCXX20_CONSTEXPR
4817 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4819 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4822 __glibcxx_requires_valid_range(__first,
__nth);
4823 __glibcxx_requires_valid_range(
__nth, __last);
4824 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
4826 if (__first == __last ||
__nth == __last)
4831 __gnu_cxx::__ops::__iter_comp_iter(__comp));
4848 template<
typename _RandomAccessIterator>
4849 _GLIBCXX20_CONSTEXPR
4854 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4856 __glibcxx_function_requires(_LessThanComparableConcept<
4858 __glibcxx_requires_valid_range(__first, __last);
4859 __glibcxx_requires_irreflexive(__first, __last);
4861 std::__sort(__first, __last, __gnu_cxx::__ops::__iter_less_iter());
4879 template<
typename _RandomAccessIterator,
typename _Compare>
4880 _GLIBCXX20_CONSTEXPR
4886 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4888 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4891 __glibcxx_requires_valid_range(__first, __last);
4892 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
4894 std::__sort(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
4897 template<
typename _InputIterator1,
typename _InputIterator2,
4898 typename _OutputIterator,
typename _Compare>
4899 _GLIBCXX20_CONSTEXPR
4901 __merge(_InputIterator1 __first1, _InputIterator1 __last1,
4902 _InputIterator2 __first2, _InputIterator2 __last2,
4903 _OutputIterator __result, _Compare __comp)
4905 while (__first1 != __last1 && __first2 != __last2)
4907 if (__comp(__first2, __first1))
4909 *__result = *__first2;
4914 *__result = *__first1;
4919 return std::copy(__first2, __last2,
4920 std::copy(__first1, __last1, __result));
4942 template<
typename _InputIterator1,
typename _InputIterator2,
4943 typename _OutputIterator>
4944 _GLIBCXX20_CONSTEXPR
4945 inline _OutputIterator
4948 _OutputIterator __result)
4953 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4955 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4957 __glibcxx_function_requires(_LessThanOpConcept<
4967 __gnu_cxx::__ops::__iter_less_iter());
4993 template<
typename _InputIterator1,
typename _InputIterator2,
4994 typename _OutputIterator,
typename _Compare>
4995 _GLIBCXX20_CONSTEXPR
4996 inline _OutputIterator
4999 _OutputIterator __result, _Compare __comp)
5004 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5006 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5008 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5018 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5021 template<
typename _RandomAccessIterator,
typename _Compare>
5023 __stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
5026 typedef typename iterator_traits<_RandomAccessIterator>::value_type
5028 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
5031 if (__first == __last)
5035 typedef _Temporary_buffer<_RandomAccessIterator, _ValueType> _TmpBuf;
5038 _TmpBuf __buf(__first, (__last - __first + 1) / 2);
5040 if (__builtin_expect(__buf.requested_size() == __buf.size(),
true))
5041 std::__stable_sort_adaptive(__first,
5042 __first + _DistanceType(__buf.size()),
5043 __last, __buf.begin(), __comp);
5044 else if (__builtin_expect(__buf.begin() == 0,
false))
5047 std::__stable_sort_adaptive_resize(__first, __last, __buf.begin(),
5048 _DistanceType(__buf.size()), __comp);
5071 template<
typename _RandomAccessIterator>
5076 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5078 __glibcxx_function_requires(_LessThanComparableConcept<
5080 __glibcxx_requires_valid_range(__first, __last);
5081 __glibcxx_requires_irreflexive(__first, __last);
5083 _GLIBCXX_STD_A::__stable_sort(__first, __last,
5084 __gnu_cxx::__ops::__iter_less_iter());
5105 template<
typename _RandomAccessIterator,
typename _Compare>
5111 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5113 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5116 __glibcxx_requires_valid_range(__first, __last);
5117 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
5119 _GLIBCXX_STD_A::__stable_sort(__first, __last,
5120 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5123 template<
typename _InputIterator1,
typename _InputIterator2,
5124 typename _OutputIterator,
5126 _GLIBCXX20_CONSTEXPR
5128 __set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5129 _InputIterator2 __first2, _InputIterator2 __last2,
5130 _OutputIterator __result, _Compare __comp)
5132 while (__first1 != __last1 && __first2 != __last2)
5134 if (__comp(__first1, __first2))
5136 *__result = *__first1;
5139 else if (__comp(__first2, __first1))
5141 *__result = *__first2;
5146 *__result = *__first1;
5152 return std::copy(__first2, __last2,
5153 std::copy(__first1, __last1, __result));
5175 template<
typename _InputIterator1,
typename _InputIterator2,
5176 typename _OutputIterator>
5177 _GLIBCXX20_CONSTEXPR
5178 inline _OutputIterator
5181 _OutputIterator __result)
5186 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5188 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5190 __glibcxx_function_requires(_LessThanOpConcept<
5193 __glibcxx_function_requires(_LessThanOpConcept<
5203 __gnu_cxx::__ops::__iter_less_iter());
5226 template<
typename _InputIterator1,
typename _InputIterator2,
5227 typename _OutputIterator,
typename _Compare>
5228 _GLIBCXX20_CONSTEXPR
5229 inline _OutputIterator
5232 _OutputIterator __result, _Compare __comp)
5237 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5239 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5241 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5244 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5254 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5257 template<
typename _InputIterator1,
typename _InputIterator2,
5258 typename _OutputIterator,
5260 _GLIBCXX20_CONSTEXPR
5262 __set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5263 _InputIterator2 __first2, _InputIterator2 __last2,
5264 _OutputIterator __result, _Compare __comp)
5266 while (__first1 != __last1 && __first2 != __last2)
5267 if (__comp(__first1, __first2))
5269 else if (__comp(__first2, __first1))
5273 *__result = *__first1;
5299 template<
typename _InputIterator1,
typename _InputIterator2,
5300 typename _OutputIterator>
5301 _GLIBCXX20_CONSTEXPR
5302 inline _OutputIterator
5305 _OutputIterator __result)
5310 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5312 __glibcxx_function_requires(_LessThanOpConcept<
5315 __glibcxx_function_requires(_LessThanOpConcept<
5325 __gnu_cxx::__ops::__iter_less_iter());
5349 template<
typename _InputIterator1,
typename _InputIterator2,
5350 typename _OutputIterator,
typename _Compare>
5351 _GLIBCXX20_CONSTEXPR
5352 inline _OutputIterator
5355 _OutputIterator __result, _Compare __comp)
5360 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5362 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5365 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5375 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5378 template<
typename _InputIterator1,
typename _InputIterator2,
5379 typename _OutputIterator,
5381 _GLIBCXX20_CONSTEXPR
5383 __set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5384 _InputIterator2 __first2, _InputIterator2 __last2,
5385 _OutputIterator __result, _Compare __comp)
5387 while (__first1 != __last1 && __first2 != __last2)
5388 if (__comp(__first1, __first2))
5390 *__result = *__first1;
5394 else if (__comp(__first2, __first1))
5401 return std::copy(__first1, __last1, __result);
5424 template<
typename _InputIterator1,
typename _InputIterator2,
5425 typename _OutputIterator>
5426 _GLIBCXX20_CONSTEXPR
5427 inline _OutputIterator
5430 _OutputIterator __result)
5435 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5437 __glibcxx_function_requires(_LessThanOpConcept<
5440 __glibcxx_function_requires(_LessThanOpConcept<
5450 __gnu_cxx::__ops::__iter_less_iter());
5476 template<
typename _InputIterator1,
typename _InputIterator2,
5477 typename _OutputIterator,
typename _Compare>
5478 _GLIBCXX20_CONSTEXPR
5479 inline _OutputIterator
5482 _OutputIterator __result, _Compare __comp)
5487 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5489 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5492 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5502 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5505 template<
typename _InputIterator1,
typename _InputIterator2,
5506 typename _OutputIterator,
5508 _GLIBCXX20_CONSTEXPR
5510 __set_symmetric_difference(_InputIterator1 __first1,
5511 _InputIterator1 __last1,
5512 _InputIterator2 __first2,
5513 _InputIterator2 __last2,
5514 _OutputIterator __result,
5517 while (__first1 != __last1 && __first2 != __last2)
5518 if (__comp(__first1, __first2))
5520 *__result = *__first1;
5524 else if (__comp(__first2, __first1))
5526 *__result = *__first2;
5535 return std::copy(__first2, __last2,
5536 std::copy(__first1, __last1, __result));
5557 template<
typename _InputIterator1,
typename _InputIterator2,
5558 typename _OutputIterator>
5559 _GLIBCXX20_CONSTEXPR
5560 inline _OutputIterator
5563 _OutputIterator __result)
5568 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5570 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5572 __glibcxx_function_requires(_LessThanOpConcept<
5575 __glibcxx_function_requires(_LessThanOpConcept<
5585 __gnu_cxx::__ops::__iter_less_iter());
5609 template<
typename _InputIterator1,
typename _InputIterator2,
5610 typename _OutputIterator,
typename _Compare>
5611 _GLIBCXX20_CONSTEXPR
5612 inline _OutputIterator
5615 _OutputIterator __result,
5621 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5623 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5625 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5628 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5638 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5641 template<
typename _ForwardIterator,
typename _Compare>
5642 _GLIBCXX14_CONSTEXPR
5644 __min_element(_ForwardIterator __first, _ForwardIterator __last,
5647 if (__first == __last)
5649 _ForwardIterator __result = __first;
5650 while (++__first != __last)
5651 if (__comp(__first, __result))
5663 template<
typename _ForwardIterator>
5664 _GLIBCXX14_CONSTEXPR
5670 __glibcxx_function_requires(_LessThanComparableConcept<
5672 __glibcxx_requires_valid_range(__first, __last);
5673 __glibcxx_requires_irreflexive(__first, __last);
5675 return _GLIBCXX_STD_A::__min_element(__first, __last,
5676 __gnu_cxx::__ops::__iter_less_iter());
5688 template<
typename _ForwardIterator,
typename _Compare>
5689 _GLIBCXX14_CONSTEXPR
5690 inline _ForwardIterator
5696 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5699 __glibcxx_requires_valid_range(__first, __last);
5700 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
5702 return _GLIBCXX_STD_A::__min_element(__first, __last,
5703 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5706 template<
typename _ForwardIterator,
typename _Compare>
5707 _GLIBCXX14_CONSTEXPR
5709 __max_element(_ForwardIterator __first, _ForwardIterator __last,
5712 if (__first == __last)
return __first;
5713 _ForwardIterator __result = __first;
5714 while (++__first != __last)
5715 if (__comp(__result, __first))
5727 template<
typename _ForwardIterator>
5728 _GLIBCXX14_CONSTEXPR
5729 inline _ForwardIterator
5734 __glibcxx_function_requires(_LessThanComparableConcept<
5736 __glibcxx_requires_valid_range(__first, __last);
5737 __glibcxx_requires_irreflexive(__first, __last);
5739 return _GLIBCXX_STD_A::__max_element(__first, __last,
5740 __gnu_cxx::__ops::__iter_less_iter());
5752 template<
typename _ForwardIterator,
typename _Compare>
5753 _GLIBCXX14_CONSTEXPR
5754 inline _ForwardIterator
5760 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5763 __glibcxx_requires_valid_range(__first, __last);
5764 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
5766 return _GLIBCXX_STD_A::__max_element(__first, __last,
5767 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5770#if __cplusplus >= 201103L
5772 template<
typename _Tp>
5773 _GLIBCXX14_CONSTEXPR
5775 min(initializer_list<_Tp> __l)
5777 __glibcxx_requires_irreflexive(__l.begin(), __l.end());
5778 return *_GLIBCXX_STD_A::__min_element(__l.begin(), __l.end(),
5779 __gnu_cxx::__ops::__iter_less_iter());
5782 template<
typename _Tp,
typename _Compare>
5783 _GLIBCXX14_CONSTEXPR
5785 min(initializer_list<_Tp> __l, _Compare __comp)
5787 __glibcxx_requires_irreflexive_pred(__l.begin(), __l.end(), __comp);
5788 return *_GLIBCXX_STD_A::__min_element(__l.begin(), __l.end(),
5789 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5792 template<
typename _Tp>
5793 _GLIBCXX14_CONSTEXPR
5795 max(initializer_list<_Tp> __l)
5797 __glibcxx_requires_irreflexive(__l.begin(), __l.end());
5798 return *_GLIBCXX_STD_A::__max_element(__l.begin(), __l.end(),
5799 __gnu_cxx::__ops::__iter_less_iter());
5802 template<
typename _Tp,
typename _Compare>
5803 _GLIBCXX14_CONSTEXPR
5805 max(initializer_list<_Tp> __l, _Compare __comp)
5807 __glibcxx_requires_irreflexive_pred(__l.begin(), __l.end(), __comp);
5808 return *_GLIBCXX_STD_A::__max_element(__l.begin(), __l.end(),
5809 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5813#if __cplusplus >= 201402L
5815 template<
typename _InputIterator,
typename _RandomAccessIterator,
5816 typename _Size,
typename _UniformRandomBitGenerator>
5817 _RandomAccessIterator
5823 using __param_type =
typename __distrib_type::param_type;
5842 template<
typename _ForwardIterator,
typename _OutputIterator,
typename _Cat,
5843 typename _Size,
typename _UniformRandomBitGenerator>
5851 using __param_type =
typename __distrib_type::param_type;
5856 if (__first == __last)
5877 if (__p.first < __n)
5879 *
__out++ = *__first;
5885 if (__n == 0)
break;
5888 if (__p.second < __n)
5890 *
__out++ = *__first;
5900 for (; __n != 0; ++__first)
5903 *
__out++ = *__first;
5909#if __cplusplus > 201402L
5910#define __cpp_lib_sample 201603L
5912 template<
typename _PopulationIterator,
typename _SampleIterator,
5913 typename _Distance,
typename _UniformRandomBitGenerator>
5927 "output range must use a RandomAccessIterator when input range"
5928 " does not meet the ForwardIterator requirements");
5931 "sample size must be an integer type");
5934 return _GLIBCXX_STD_A::
5941_GLIBCXX_END_NAMESPACE_ALGO
5942_GLIBCXX_END_NAMESPACE_VERSION
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
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.
void __merge_adaptive(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last, _Distance __len1, _Distance __len2, _Pointer __buffer, _Compare __comp)
This is a helper function for the merge routines.
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 _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 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 _Tp __lg(_Tp __n)
This is a helper function for the sort routines and for random.tcc.
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...
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)
_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 _ForwardIterator __rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last, forward_iterator_tag)
This is a helper function for the rotate algorithm.
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.
_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.