65#if __cplusplus >= 201103L
71namespace std _GLIBCXX_VISIBILITY(default)
73_GLIBCXX_BEGIN_NAMESPACE_VERSION
76 template<
typename _Iterator,
typename _Compare>
79 _Iterator __c, _Compare __comp)
85 else if (__comp(__a, __c))
90 else if (__comp(__a, __c))
92 else if (__comp(__b, __c))
99 template<
typename _InputIterator,
typename _Predicate>
100 inline _InputIterator
104 while (__first != __last && !
__pred(__first))
110 template<
typename _RandomAccessIterator,
typename _Predicate>
111 _RandomAccessIterator
115 typename iterator_traits<_RandomAccessIterator>::difference_type
137 switch (__last - __first)
157 template<
typename _Iterator,
typename _Predicate>
159 __find_if(_Iterator __first, _Iterator __last, _Predicate __pred)
161 return __find_if(__first, __last, __pred,
166 template<
typename _InputIterator,
typename _Predicate>
167 inline _InputIterator
172 __gnu_cxx::__ops::__negate(
__pred),
179 template<
typename _InputIterator,
typename _Predicate,
typename _Distance>
202 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
203 typename _BinaryPredicate>
205 __search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
206 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
207 _BinaryPredicate __predicate)
210 if (__first1 == __last1 || __first2 == __last2)
214 _ForwardIterator2 __p1(__first2);
215 if (++__p1 == __last2)
217 __gnu_cxx::__ops::__iter_comp_iter(__predicate, __first2));
220 _ForwardIterator2 __p;
221 _ForwardIterator1 __current = __first1;
227 __gnu_cxx::__ops::__iter_comp_iter(__predicate, __first2));
229 if (__first1 == __last1)
233 __current = __first1;
234 if (++__current == __last1)
237 while (__predicate(__current, __p))
239 if (++__p == __last2)
241 if (++__current == __last1)
254 template<
typename _ForwardIterator,
typename _Integer,
255 typename _UnaryPredicate>
262 while (__first != __last)
264 typename iterator_traits<_ForwardIterator>::difference_type
286 template<
typename _RandomAccessIter,
typename _Integer,
287 typename _UnaryPredicate>
293 typedef typename std::iterator_traits<_RandomAccessIter>::difference_type
309 return (__first - __count);
316 template<
typename _ForwardIterator,
typename _Integer,
317 typename _UnaryPredicate>
319 __search_n(_ForwardIterator __first, _ForwardIterator __last,
321 _UnaryPredicate __unary_pred)
334 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
335 typename _BinaryPredicate>
337 __find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
338 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
339 forward_iterator_tag, forward_iterator_tag,
340 _BinaryPredicate __comp)
342 if (__first2 == __last2)
345 _ForwardIterator1 __result = __last1;
348 _ForwardIterator1 __new_result
349 = std::__search(__first1, __last1, __first2, __last2, __comp);
350 if (__new_result == __last1)
354 __result = __new_result;
355 __first1 = __new_result;
362 template<
typename _BidirectionalIterator1,
typename _BidirectionalIterator2,
363 typename _BinaryPredicate>
364 _BidirectionalIterator1
365 __find_end(_BidirectionalIterator1 __first1,
366 _BidirectionalIterator1 __last1,
367 _BidirectionalIterator2 __first2,
368 _BidirectionalIterator2 __last2,
369 bidirectional_iterator_tag, bidirectional_iterator_tag,
370 _BinaryPredicate __comp)
373 __glibcxx_function_requires(_BidirectionalIteratorConcept<
374 _BidirectionalIterator1>)
375 __glibcxx_function_requires(_BidirectionalIteratorConcept<
376 _BidirectionalIterator2>)
378 typedef reverse_iterator<_BidirectionalIterator1> _RevIterator1;
379 typedef reverse_iterator<_BidirectionalIterator2> _RevIterator2;
381 _RevIterator1 __rlast1(__first1);
382 _RevIterator2 __rlast2(__first2);
383 _RevIterator1 __rresult =
std::__search(_RevIterator1(__last1), __rlast1,
384 _RevIterator2(__last2), __rlast2,
387 if (__rresult == __rlast1)
391 _BidirectionalIterator1 __result = __rresult.base();
423 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
424 inline _ForwardIterator1
431 __glibcxx_function_requires(_EqualOpConcept<
432 typename iterator_traits<_ForwardIterator1>::value_type,
433 typename iterator_traits<_ForwardIterator2>::value_type>)
440 __gnu_cxx::__ops::__iter_equal_to_iter());
471 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
472 typename _BinaryPredicate>
473 inline _ForwardIterator1
482 typename iterator_traits<_ForwardIterator1>::value_type,
483 typename iterator_traits<_ForwardIterator2>::value_type>)
490 __gnu_cxx::__ops::__iter_comp_iter(__comp));
493#if __cplusplus >= 201103L
506 template<
typename _InputIterator,
typename _Predicate>
509 {
return __last == std::find_if_not(__first, __last,
__pred); }
523 template<
typename _InputIterator,
typename _Predicate>
526 {
return __last == _GLIBCXX_STD_A::find_if(__first, __last,
__pred); }
541 template<
typename _InputIterator,
typename _Predicate>
544 {
return !std::none_of(__first, __last,
__pred); }
556 template<
typename _InputIterator,
typename _Predicate>
557 inline _InputIterator
563 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
564 typename iterator_traits<_InputIterator>::value_type>)
565 __glibcxx_requires_valid_range(__first, __last);
567 __gnu_cxx::__ops::__pred_iter(
__pred));
580 template<
typename _InputIterator,
typename _Predicate>
585 __first = std::find_if_not(__first, __last,
__pred);
586 return std::none_of(__first, __last,
__pred);
598 template<
typename _ForwardIterator,
typename _Predicate>
605 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
606 typename iterator_traits<_ForwardIterator>::value_type>)
609 __glibcxx_requires_valid_range(__first, __last);
611 typedef typename iterator_traits<_ForwardIterator>::difference_type
636 template<
typename _InputIterator,
typename _OutputIterator,
639 __remove_copy_if(_InputIterator __first, _InputIterator __last,
640 _OutputIterator __result, _Predicate __pred)
642 for (; __first != __last; ++__first)
643 if (!__pred(__first))
645 *__result = *__first;
665 template<
typename _InputIterator,
typename _OutputIterator,
typename _Tp>
666 inline _OutputIterator
668 _OutputIterator
__result,
const _Tp& __value)
672 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
673 typename iterator_traits<_InputIterator>::value_type>)
674 __glibcxx_function_requires(_EqualOpConcept<
675 typename iterator_traits<_InputIterator>::value_type, _Tp>)
676 __glibcxx_requires_valid_range(__first, __last);
678 return std::__remove_copy_if(__first, __last,
__result,
679 __gnu_cxx::__ops::__iter_equals_val(__value));
697 template<
typename _InputIterator,
typename _OutputIterator,
699 inline _OutputIterator
705 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
706 typename iterator_traits<_InputIterator>::value_type>)
707 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
708 typename iterator_traits<_InputIterator>::value_type>)
709 __glibcxx_requires_valid_range(__first, __last);
711 return std::__remove_copy_if(__first, __last,
__result,
712 __gnu_cxx::__ops::__pred_iter(
__pred));
715#if __cplusplus >= 201103L
731 template<
typename _InputIterator,
typename _OutputIterator,
739 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
740 typename iterator_traits<_InputIterator>::value_type>)
741 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
742 typename iterator_traits<_InputIterator>::value_type>)
743 __glibcxx_requires_valid_range(__first, __last);
745 for (; __first != __last; ++__first)
754 template<
typename _InputIterator,
typename _Size,
typename _OutputIterator>
756 __copy_n(_InputIterator __first, _Size __n,
757 _OutputIterator __result, input_iterator_tag)
763 *__result = *__first;
774 template<
typename _RandomAccessIterator,
typename _Size,
775 typename _OutputIterator>
776 inline _OutputIterator
777 __copy_n(_RandomAccessIterator __first, _Size __n,
778 _OutputIterator __result, random_access_iterator_tag)
779 {
return std::copy(__first, __first + __n, __result); }
794 template<
typename _InputIterator,
typename _Size,
typename _OutputIterator>
795 inline _OutputIterator
800 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
801 typename iterator_traits<_InputIterator>::value_type>)
803 return std::__copy_n(__first, __n,
__result,
822 template<
typename _InputIterator,
typename _OutputIterator1,
823 typename _OutputIterator2,
typename _Predicate>
824 pair<_OutputIterator1, _OutputIterator2>
832 typename iterator_traits<_InputIterator>::value_type>)
834 typename iterator_traits<_InputIterator>::value_type>)
835 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
836 typename iterator_traits<_InputIterator>::value_type>)
837 __glibcxx_requires_valid_range(__first, __last);
839 for (; __first != __last; ++__first)
855 template<
typename _ForwardIterator,
typename _Predicate>
857 __remove_if(_ForwardIterator __first, _ForwardIterator __last,
861 if (__first == __last)
863 _ForwardIterator __result = __first;
865 for (; __first != __last; ++__first)
866 if (!__pred(__first))
868 *__result = _GLIBCXX_MOVE(*__first);
891 template<
typename _ForwardIterator,
typename _Tp>
892 inline _ForwardIterator
897 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
899 __glibcxx_function_requires(_EqualOpConcept<
900 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
901 __glibcxx_requires_valid_range(__first, __last);
903 return std::__remove_if(__first, __last,
904 __gnu_cxx::__ops::__iter_equals_val(__value));
924 template<
typename _ForwardIterator,
typename _Predicate>
925 inline _ForwardIterator
930 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
932 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
933 typename iterator_traits<_ForwardIterator>::value_type>)
934 __glibcxx_requires_valid_range(__first, __last);
936 return std::__remove_if(__first, __last,
937 __gnu_cxx::__ops::__pred_iter(
__pred));
940 template<
typename _ForwardIterator,
typename _BinaryPredicate>
942 __adjacent_find(_ForwardIterator __first, _ForwardIterator __last,
943 _BinaryPredicate __binary_pred)
945 if (__first == __last)
947 _ForwardIterator __next = __first;
948 while (++__next != __last)
950 if (__binary_pred(__first, __next))
957 template<
typename _ForwardIterator,
typename _BinaryPredicate>
959 __unique(_ForwardIterator __first, _ForwardIterator __last,
960 _BinaryPredicate __binary_pred)
963 __first = std::__adjacent_find(__first, __last, __binary_pred);
964 if (__first == __last)
968 _ForwardIterator __dest = __first;
970 while (++__first != __last)
971 if (!__binary_pred(__dest, __first))
972 *++__dest = _GLIBCXX_MOVE(*__first);
990 template<
typename _ForwardIterator>
991 inline _ForwardIterator
995 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
997 __glibcxx_function_requires(_EqualityComparableConcept<
998 typename iterator_traits<_ForwardIterator>::value_type>)
999 __glibcxx_requires_valid_range(__first, __last);
1001 return std::__unique(__first, __last,
1002 __gnu_cxx::__ops::__iter_equal_to_iter());
1020 template<
typename _ForwardIterator,
typename _BinaryPredicate>
1021 inline _ForwardIterator
1026 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1029 typename iterator_traits<_ForwardIterator>::value_type,
1030 typename iterator_traits<_ForwardIterator>::value_type>)
1031 __glibcxx_requires_valid_range(__first, __last);
1033 return std::__unique(__first, __last,
1043 template<
typename _ForwardIterator,
typename _OutputIterator,
1044 typename _BinaryPredicate>
1052 typename iterator_traits<_ForwardIterator>::value_type,
1053 typename iterator_traits<_ForwardIterator>::value_type>)
1057 while (++__next != __last)
1072 template<
typename _InputIterator,
typename _OutputIterator,
1073 typename _BinaryPredicate>
1081 typename iterator_traits<_InputIterator>::value_type,
1082 typename iterator_traits<_InputIterator>::value_type>)
1084 typename iterator_traits<_InputIterator>::value_type __value = *__first;
1089 while (++__first != __last)
1104 template<
typename _InputIterator,
typename _ForwardIterator,
1105 typename _BinaryPredicate>
1113 typename iterator_traits<_ForwardIterator>::value_type,
1114 typename iterator_traits<_InputIterator>::value_type>)
1116 while (++__first != __last)
1127 template<
typename _B
idirectionalIterator>
1133 if (__first == __last || __first == --__last)
1137 std::iter_swap(__first, __last);
1147 template<
typename _RandomAccessIterator>
1152 if (__first == __last)
1155 while (__first < __last)
1157 std::iter_swap(__first, __last);
1175 template<
typename _B
idirectionalIterator>
1180 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
1182 __glibcxx_requires_valid_range(__first, __last);
1202 template<
typename _B
idirectionalIterator,
typename _OutputIterator>
1208 __glibcxx_function_requires(_BidirectionalIteratorConcept<
1210 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1211 typename iterator_traits<_BidirectionalIterator>::value_type>)
1212 __glibcxx_requires_valid_range(__first, __last);
1214 while (__first != __last)
1227 template<
typename _Eucl
ideanRingElement>
1228 _EuclideanRingElement
1240 inline namespace _V2
1244 template<
typename _ForwardIterator>
1251 if (__first == __middle)
1253 else if (__last == __middle)
1262 if (__first == __middle)
1276 if (__first == __middle)
1285 template<
typename _B
idirectionalIterator>
1293 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
1296 if (__first == __middle)
1298 else if (__last == __middle)
1304 while (__first != __middle && __middle != __last)
1306 std::iter_swap(__first, --__last);
1310 if (__first == __middle)
1323 template<
typename _RandomAccessIterator>
1331 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
1334 if (__first == __middle)
1336 else if (__last == __middle)
1339 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
1341 typedef typename iterator_traits<_RandomAccessIterator>::value_type
1349 std::swap_ranges(__first, __middle, __middle);
1362 _ValueType __t = _GLIBCXX_MOVE(*__p);
1363 _GLIBCXX_MOVE3(__p + 1, __p + __n, __p);
1364 *(__p + __n - 1) = _GLIBCXX_MOVE(__t);
1370 std::iter_swap(__p, __q);
1377 std::swap(__n,
__k);
1385 _ValueType __t = _GLIBCXX_MOVE(*(__p + __n - 1));
1386 _GLIBCXX_MOVE_BACKWARD3(__p, __p + __n - 1, __p + __n);
1387 *__p = _GLIBCXX_MOVE(__t);
1396 std::iter_swap(__p, __q);
1401 std::swap(__n,
__k);
1429 template<
typename _ForwardIterator>
1435 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1437 __glibcxx_requires_valid_range(__first, __middle);
1438 __glibcxx_requires_valid_range(__middle, __last);
1466 template<
typename _ForwardIterator,
typename _OutputIterator>
1467 inline _OutputIterator
1473 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1474 typename iterator_traits<_ForwardIterator>::value_type>)
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>
1488 if (__first == __last)
1492 if (++__first == __last)
1497 while (++__next != __last)
1500 std::iter_swap(__first, __next);
1508 template<
typename _B
idirectionalIterator,
typename _Predicate>
1509 _BidirectionalIterator
1516 if (__first == __last)
1518 else if (
__pred(*__first))
1524 if (__first == __last)
1526 else if (!
bool(
__pred(*__last)))
1530 std::iter_swap(__first, __last);
1543 template<
typename _ForwardIterator,
typename _Pointer,
typename _Predicate,
1566 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> __buf(__first, __last);
1624 _DistanceType(__buf.requested_size()),
1626 _DistanceType(__buf.size()));
1646 template<
typename _ForwardIterator,
typename _Predicate>
1647 inline _ForwardIterator
1652 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1654 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
1655 typename iterator_traits<_ForwardIterator>::value_type>)
1656 __glibcxx_requires_valid_range(__first, __last);
1658 return std::__stable_partition(__first, __last,
1659 __gnu_cxx::__ops::__pred_iter(
__pred));
1663 template<
typename _RandomAccessIterator,
typename _Compare>
1669 std::__make_heap(__first, __middle, __comp);
1671 if (__comp(__i, __first))
1672 std::__pop_heap(__first, __middle, __i, __comp);
1677 template<
typename _InputIterator,
typename _RandomAccessIterator,
1679 _RandomAccessIterator
1680 __partial_sort_copy(_InputIterator __first, _InputIterator __last,
1681 _RandomAccessIterator __result_first,
1682 _RandomAccessIterator __result_last,
1685 typedef typename iterator_traits<_InputIterator>::value_type
1687 typedef iterator_traits<_RandomAccessIterator> _RItTraits;
1688 typedef typename _RItTraits::difference_type _DistanceType;
1690 if (__result_first == __result_last)
1691 return __result_last;
1692 _RandomAccessIterator __result_real_last = __result_first;
1693 while (__first != __last && __result_real_last != __result_last)
1695 *__result_real_last = *__first;
1696 ++__result_real_last;
1700 std::__make_heap(__result_first, __result_real_last, __comp);
1701 while (__first != __last)
1703 if (__comp(__first, __result_first))
1704 std::__adjust_heap(__result_first, _DistanceType(0),
1705 _DistanceType(__result_real_last
1707 _InputValueType(*__first), __comp);
1710 std::__sort_heap(__result_first, __result_real_last, __comp);
1711 return __result_real_last;
1732 template<
typename _InputIterator,
typename _RandomAccessIterator>
1733 inline _RandomAccessIterator
1738#ifdef _GLIBCXX_CONCEPT_CHECKS
1739 typedef typename iterator_traits<_InputIterator>::value_type
1741 typedef typename iterator_traits<_RandomAccessIterator>::value_type
1752 __glibcxx_requires_valid_range(__first, __last);
1753 __glibcxx_requires_irreflexive(__first, __last);
1756 return std::__partial_sort_copy(__first, __last,
1758 __gnu_cxx::__ops::__iter_less_iter());
1781 template<
typename _InputIterator,
typename _RandomAccessIterator,
1783 inline _RandomAccessIterator
1789#ifdef _GLIBCXX_CONCEPT_CHECKS
1790 typedef typename iterator_traits<_InputIterator>::value_type
1792 typedef typename iterator_traits<_RandomAccessIterator>::value_type
1798 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
1802 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
1804 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
1806 __glibcxx_requires_valid_range(__first, __last);
1807 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
1810 return std::__partial_sort_copy(__first, __last,
1812 __gnu_cxx::__ops::__iter_comp_iter(__comp));
1816 template<
typename _RandomAccessIterator,
typename _Compare>
1821 typename iterator_traits<_RandomAccessIterator>::value_type
1822 __val = _GLIBCXX_MOVE(*__last);
1825 while (__comp(__val, __next))
1827 *__last = _GLIBCXX_MOVE(*__next);
1831 *__last = _GLIBCXX_MOVE(__val);
1835 template<
typename _RandomAccessIterator,
typename _Compare>
1840 if (__first == __last)
return;
1844 if (__comp(__i, __first))
1846 typename iterator_traits<_RandomAccessIterator>::value_type
1847 __val = _GLIBCXX_MOVE(*__i);
1848 _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1);
1849 *__first = _GLIBCXX_MOVE(__val);
1853 __gnu_cxx::__ops::__val_comp_iter(__comp));
1858 template<
typename _RandomAccessIterator,
typename _Compare>
1865 __gnu_cxx::__ops::__val_comp_iter(__comp));
1872 enum { _S_threshold = 16 };
1875 template<
typename _RandomAccessIterator,
typename _Compare>
1880 if (__last - __first >
int(_S_threshold))
1891 template<
typename _RandomAccessIterator,
typename _Compare>
1892 _RandomAccessIterator
1899 while (__comp(__first,
__pivot))
1902 while (__comp(
__pivot, __last))
1904 if (!(__first < __last))
1906 std::iter_swap(__first, __last);
1912 template<
typename _RandomAccessIterator,
typename _Compare>
1913 inline _RandomAccessIterator
1923 template<
typename _RandomAccessIterator,
typename _Compare>
1925 __partial_sort(_RandomAccessIterator __first,
1926 _RandomAccessIterator __middle,
1927 _RandomAccessIterator __last,
1931 std::__sort_heap(__first, __middle, __comp);
1935 template<
typename _RandomAccessIterator,
typename _Size,
typename _Compare>
1941 while (__last - __first >
int(_S_threshold))
1945 std::__partial_sort(__first, __last, __last, __comp);
1958 template<
typename _RandomAccessIterator,
typename _Compare>
1960 __sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
1963 if (__first != __last)
1972 template<
typename _RandomAccessIterator,
typename _Size,
typename _Compare>
1974 __introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth,
1975 _RandomAccessIterator __last, _Size __depth_limit,
1978 while (__last - __first > 3)
1980 if (__depth_limit == 0)
1984 std::iter_swap(__first, __nth);
1988 _RandomAccessIterator __cut =
2018 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2019 inline _ForwardIterator
2021 const _Tp& __val, _Compare __comp)
2025 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2026 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
2027 __glibcxx_requires_partitioned_lower_pred(__first, __last,
2030 return std::__lower_bound(__first, __last, __val,
2031 __gnu_cxx::__ops::__iter_comp_val(__comp));
2034 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2036 __upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2037 const _Tp& __val, _Compare __comp)
2039 typedef typename iterator_traits<_ForwardIterator>::difference_type
2046 _DistanceType __half = __len >> 1;
2047 _ForwardIterator __middle = __first;
2049 if (__comp(__val, __middle))
2055 __len = __len - __half - 1;
2072 template<
typename _ForwardIterator,
typename _Tp>
2073 inline _ForwardIterator
2079 __glibcxx_function_requires(_LessThanOpConcept<
2080 _Tp,
typename iterator_traits<_ForwardIterator>::value_type>)
2081 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2083 return std::__upper_bound(__first, __last, __val,
2084 __gnu_cxx::__ops::__val_less_iter());
2102 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2103 inline _ForwardIterator
2105 const _Tp& __val, _Compare __comp)
2109 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2110 _Tp,
typename iterator_traits<_ForwardIterator>::value_type>)
2111 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2114 return std::__upper_bound(__first, __last, __val,
2115 __gnu_cxx::__ops::__val_comp_iter(__comp));
2118 template<
typename _ForwardIterator,
typename _Tp,
2119 typename _CompareItTp,
typename _CompareTpIt>
2120 pair<_ForwardIterator, _ForwardIterator>
2121 __equal_range(_ForwardIterator __first, _ForwardIterator __last,
2123 _CompareItTp __comp_it_val, _CompareTpIt __comp_val_it)
2125 typedef typename iterator_traits<_ForwardIterator>::difference_type
2132 _DistanceType __half = __len >> 1;
2133 _ForwardIterator __middle = __first;
2135 if (__comp_it_val(__middle, __val))
2139 __len = __len - __half - 1;
2141 else if (__comp_val_it(__val, __middle))
2145 _ForwardIterator __left
2146 = std::__lower_bound(__first, __middle, __val, __comp_it_val);
2148 _ForwardIterator __right
2149 = std::__upper_bound(++__middle, __first, __val, __comp_val_it);
2150 return pair<_ForwardIterator, _ForwardIterator>(__left, __right);
2153 return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
2173 template<
typename _ForwardIterator,
typename _Tp>
2174 inline pair<_ForwardIterator, _ForwardIterator>
2180 __glibcxx_function_requires(_LessThanOpConcept<
2181 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
2182 __glibcxx_function_requires(_LessThanOpConcept<
2183 _Tp,
typename iterator_traits<_ForwardIterator>::value_type>)
2184 __glibcxx_requires_partitioned_lower(__first, __last, __val);
2185 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2187 return std::__equal_range(__first, __last, __val,
2188 __gnu_cxx::__ops::__iter_less_val(),
2189 __gnu_cxx::__ops::__val_less_iter());
2209 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2210 inline pair<_ForwardIterator, _ForwardIterator>
2212 const _Tp& __val, _Compare __comp)
2216 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2217 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
2218 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2219 _Tp,
typename iterator_traits<_ForwardIterator>::value_type>)
2220 __glibcxx_requires_partitioned_lower_pred(__first, __last,
2222 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2225 return std::__equal_range(__first, __last, __val,
2226 __gnu_cxx::__ops::__iter_comp_val(__comp),
2227 __gnu_cxx::__ops::__val_comp_iter(__comp));
2242 template<
typename _ForwardIterator,
typename _Tp>
2249 __glibcxx_function_requires(_LessThanOpConcept<
2250 _Tp,
typename iterator_traits<_ForwardIterator>::value_type>)
2251 __glibcxx_requires_partitioned_lower(__first, __last, __val);
2252 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2255 = std::__lower_bound(__first, __last, __val,
2256 __gnu_cxx::__ops::__iter_less_val());
2257 return __i != __last && !(__val < *__i);
2275 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2278 const _Tp& __val, _Compare __comp)
2282 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2283 _Tp,
typename iterator_traits<_ForwardIterator>::value_type>)
2284 __glibcxx_requires_partitioned_lower_pred(__first, __last,
2286 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2290 = std::__lower_bound(__first, __last, __val,
2291 __gnu_cxx::__ops::__iter_comp_val(__comp));
2292 return __i != __last && !bool(__comp(__val, *__i));
2298 template<
typename _InputIterator1,
typename _InputIterator2,
2299 typename _OutputIterator,
typename _Compare>
2303 _OutputIterator
__result, _Compare __comp)
2324 template<
typename _BidirectionalIterator1,
typename _BidirectionalIterator2,
2325 typename _BidirectionalIterator3,
typename _Compare>
2367 template<
typename _BidirectionalIterator1,
typename _BidirectionalIterator2,
2369 _BidirectionalIterator1
2383 _GLIBCXX_MOVE_BACKWARD3(__first, __middle, __last);
2394 _GLIBCXX_MOVE3(__middle, __last, __first);
2402 std::rotate(__first, __middle, __last);
2409 template<
typename _BidirectionalIterator,
typename _Distance,
2410 typename _Pointer,
typename _Compare>
2442 = std::__lower_bound(__middle, __last, *
__first_cut,
2443 __gnu_cxx::__ops::__iter_comp_val(__comp));
2452 __gnu_cxx::__ops::__val_comp_iter(__comp));
2470 template<
typename _BidirectionalIterator,
typename _Distance,
2484 if (__comp(__middle, __first))
2485 std::iter_swap(__first, __middle);
2498 = std::__lower_bound(__middle, __last, *
__first_cut,
2499 __gnu_cxx::__ops::__iter_comp_val(__comp));
2508 __gnu_cxx::__ops::__val_comp_iter(__comp));
2521 template<
typename _B
idirectionalIterator,
typename _Compare>
2523 __inplace_merge(_BidirectionalIterator __first,
2524 _BidirectionalIterator __middle,
2525 _BidirectionalIterator __last,
2528 typedef typename iterator_traits<_BidirectionalIterator>::value_type
2530 typedef typename iterator_traits<_BidirectionalIterator>::difference_type
2533 if (__first == __middle || __middle == __last)
2536 const _DistanceType __len1 =
std::distance(__first, __middle);
2537 const _DistanceType __len2 =
std::distance(__middle, __last);
2539 typedef _Temporary_buffer<_BidirectionalIterator, _ValueType> _TmpBuf;
2540 _TmpBuf __buf(__first, __last);
2542 if (__buf.begin() == 0)
2544 (__first, __middle, __last, __len1, __len2, __comp);
2547 (__first, __middle, __last, __len1, __len2, __buf.begin(),
2548 _DistanceType(__buf.size()), __comp);
2569 template<
typename _B
idirectionalIterator>
2576 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
2578 __glibcxx_function_requires(_LessThanComparableConcept<
2579 typename iterator_traits<_BidirectionalIterator>::value_type>)
2580 __glibcxx_requires_sorted(__first, __middle);
2581 __glibcxx_requires_sorted(__middle, __last);
2582 __glibcxx_requires_irreflexive(__first, __last);
2584 std::__inplace_merge(__first, __middle, __last,
2585 __gnu_cxx::__ops::__iter_less_iter());
2610 template<
typename _B
idirectionalIterator,
typename _Compare>
2618 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
2620 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2621 typename iterator_traits<_BidirectionalIterator>::value_type,
2622 typename iterator_traits<_BidirectionalIterator>::value_type>)
2623 __glibcxx_requires_sorted_pred(__first, __middle, __comp);
2624 __glibcxx_requires_sorted_pred(__middle, __last, __comp);
2625 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
2627 std::__inplace_merge(__first, __middle, __last,
2628 __gnu_cxx::__ops::__iter_comp_iter(__comp));
2633 template<
typename _InputIterator,
typename _OutputIterator,
2638 _OutputIterator
__result, _Compare __comp)
2659 template<
typename _RandomAccessIterator1,
typename _RandomAccessIterator2,
2660 typename _Distance,
typename _Compare>
2662 __merge_sort_loop(_RandomAccessIterator1 __first,
2663 _RandomAccessIterator1 __last,
2664 _RandomAccessIterator2 __result, _Distance __step_size,
2667 const _Distance __two_step = 2 * __step_size;
2669 while (__last - __first >= __two_step)
2672 __first + __step_size,
2673 __first + __two_step,
2675 __first += __two_step;
2677 __step_size =
std::min(_Distance(__last - __first), __step_size);
2680 __first + __step_size, __last, __result, __comp);
2683 template<
typename _RandomAccessIterator,
typename _Distance,
2686 __chunk_insertion_sort(_RandomAccessIterator __first,
2687 _RandomAccessIterator __last,
2688 _Distance __chunk_size, _Compare __comp)
2690 while (__last - __first >= __chunk_size)
2693 __first += __chunk_size;
2698 enum { _S_chunk_size = 7 };
2700 template<
typename _RandomAccessIterator,
typename _Po
inter,
typename _Compare>
2702 __merge_sort_with_buffer(_RandomAccessIterator __first,
2703 _RandomAccessIterator __last,
2704 _Pointer __buffer, _Compare __comp)
2706 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
2709 const _Distance __len = __last - __first;
2710 const _Pointer __buffer_last = __buffer + __len;
2712 _Distance __step_size = _S_chunk_size;
2713 std::__chunk_insertion_sort(__first, __last, __step_size, __comp);
2715 while (__step_size < __len)
2717 std::__merge_sort_loop(__first, __last, __buffer,
2718 __step_size, __comp);
2720 std::__merge_sort_loop(__buffer, __buffer_last, __first,
2721 __step_size, __comp);
2726 template<
typename _RandomAccessIterator,
typename _Pointer,
2727 typename _Distance,
typename _Compare>
2729 __stable_sort_adaptive(_RandomAccessIterator __first,
2730 _RandomAccessIterator __last,
2731 _Pointer __buffer, _Distance __buffer_size,
2734 const _Distance __len = (__last - __first + 1) / 2;
2735 const _RandomAccessIterator __middle = __first + __len;
2736 if (__len > __buffer_size)
2738 std::__stable_sort_adaptive(__first, __middle, __buffer,
2739 __buffer_size, __comp);
2740 std::__stable_sort_adaptive(__middle, __last, __buffer,
2741 __buffer_size, __comp);
2745 std::__merge_sort_with_buffer(__first, __middle, __buffer, __comp);
2746 std::__merge_sort_with_buffer(__middle, __last, __buffer, __comp);
2749 _Distance(__middle - __first),
2750 _Distance(__last - __middle),
2751 __buffer, __buffer_size,
2756 template<
typename _RandomAccessIterator,
typename _Compare>
2761 if (__last - __first < 15)
2782 template<
typename _InputIterator1,
typename _InputIterator2,
2785 __includes(_InputIterator1 __first1, _InputIterator1 __last1,
2786 _InputIterator2 __first2, _InputIterator2 __last2,
2789 while (__first1 != __last1 && __first2 != __last2)
2790 if (__comp(__first2, __first1))
2792 else if (__comp(__first1, __first2))
2800 return __first2 == __last2;
2821 template<
typename _InputIterator1,
typename _InputIterator2>
2829 __glibcxx_function_requires(_LessThanOpConcept<
2830 typename iterator_traits<_InputIterator1>::value_type,
2831 typename iterator_traits<_InputIterator2>::value_type>)
2832 __glibcxx_function_requires(_LessThanOpConcept<
2833 typename iterator_traits<_InputIterator2>::value_type,
2834 typename iterator_traits<_InputIterator1>::value_type>)
2841 __gnu_cxx::__ops::__iter_less_iter());
2865 template<
typename _InputIterator1,
typename _InputIterator2,
2875 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2876 typename iterator_traits<_InputIterator1>::value_type,
2877 typename iterator_traits<_InputIterator2>::value_type>)
2878 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2879 typename iterator_traits<_InputIterator2>::value_type,
2880 typename iterator_traits<_InputIterator1>::value_type>)
2887 __gnu_cxx::__ops::__iter_comp_iter(__comp));
2900 template<
typename _B
idirectionalIterator,
typename _Compare>
2902 __next_permutation(_BidirectionalIterator __first,
2903 _BidirectionalIterator __last, _Compare __comp)
2905 if (__first == __last)
2907 _BidirectionalIterator __i = __first;
2916 _BidirectionalIterator __ii = __i;
2918 if (__comp(__i, __ii))
2920 _BidirectionalIterator __j = __last;
2921 while (!__comp(__i, --__j))
2923 std::iter_swap(__i, __j);
2949 template<
typename _B
idirectionalIterator>
2955 __glibcxx_function_requires(_BidirectionalIteratorConcept<
2957 __glibcxx_function_requires(_LessThanComparableConcept<
2958 typename iterator_traits<_BidirectionalIterator>::value_type>)
2959 __glibcxx_requires_valid_range(__first, __last);
2960 __glibcxx_requires_irreflexive(__first, __last);
2962 return std::__next_permutation
2963 (__first, __last, __gnu_cxx::__ops::__iter_less_iter());
2981 template<
typename _B
idirectionalIterator,
typename _Compare>
2987 __glibcxx_function_requires(_BidirectionalIteratorConcept<
2989 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2990 typename iterator_traits<_BidirectionalIterator>::value_type,
2991 typename iterator_traits<_BidirectionalIterator>::value_type>)
2992 __glibcxx_requires_valid_range(__first, __last);
2993 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
2995 return std::__next_permutation
2996 (__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
2999 template<
typename _B
idirectionalIterator,
typename _Compare>
3001 __prev_permutation(_BidirectionalIterator __first,
3002 _BidirectionalIterator __last, _Compare __comp)
3004 if (__first == __last)
3006 _BidirectionalIterator __i = __first;
3015 _BidirectionalIterator __ii = __i;
3017 if (__comp(__ii, __i))
3019 _BidirectionalIterator __j = __last;
3020 while (!__comp(--__j, __i))
3022 std::iter_swap(__i, __j);
3049 template<
typename _B
idirectionalIterator>
3055 __glibcxx_function_requires(_BidirectionalIteratorConcept<
3057 __glibcxx_function_requires(_LessThanComparableConcept<
3058 typename iterator_traits<_BidirectionalIterator>::value_type>)
3059 __glibcxx_requires_valid_range(__first, __last);
3060 __glibcxx_requires_irreflexive(__first, __last);
3062 return std::__prev_permutation(__first, __last,
3063 __gnu_cxx::__ops::__iter_less_iter());
3081 template<
typename _B
idirectionalIterator,
typename _Compare>
3087 __glibcxx_function_requires(_BidirectionalIteratorConcept<
3089 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3090 typename iterator_traits<_BidirectionalIterator>::value_type,
3091 typename iterator_traits<_BidirectionalIterator>::value_type>)
3092 __glibcxx_requires_valid_range(__first, __last);
3093 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
3095 return std::__prev_permutation(__first, __last,
3096 __gnu_cxx::__ops::__iter_comp_iter(__comp));
3102 template<
typename _InputIterator,
typename _OutputIterator,
3103 typename _Predicate,
typename _Tp>
3105 __replace_copy_if(_InputIterator __first, _InputIterator __last,
3106 _OutputIterator __result,
3107 _Predicate __pred,
const _Tp& __new_value)
3109 for (; __first != __last; ++__first, (void)++__result)
3110 if (__pred(__first))
3111 *__result = __new_value;
3113 *__result = *__first;
3131 template<
typename _InputIterator,
typename _OutputIterator,
typename _Tp>
3132 inline _OutputIterator
3139 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
3140 typename iterator_traits<_InputIterator>::value_type>)
3141 __glibcxx_function_requires(_EqualOpConcept<
3142 typename iterator_traits<_InputIterator>::value_type, _Tp>)
3143 __glibcxx_requires_valid_range(__first, __last);
3145 return std::__replace_copy_if(__first, __last,
__result,
3165 template<
typename _InputIterator,
typename _OutputIterator,
3166 typename _Predicate,
typename _Tp>
3167 inline _OutputIterator
3174 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
3175 typename iterator_traits<_InputIterator>::value_type>)
3176 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
3177 typename iterator_traits<_InputIterator>::value_type>)
3178 __glibcxx_requires_valid_range(__first, __last);
3180 return std::__replace_copy_if(__first, __last,
__result,
3181 __gnu_cxx::__ops::__pred_iter(
__pred),
3185 template<
typename _InputIterator,
typename _Predicate>
3186 typename iterator_traits<_InputIterator>::difference_type
3187 __count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
3189 typename iterator_traits<_InputIterator>::difference_type __n = 0;
3190 for (; __first != __last; ++__first)
3191 if (__pred(__first))
3196#if __cplusplus >= 201103L
3204 template<
typename _ForwardIterator>
3207 {
return std::is_sorted_until(__first, __last) == __last; }
3218 template<
typename _ForwardIterator,
typename _Compare>
3222 {
return std::is_sorted_until(__first, __last, __comp) == __last; }
3224 template<
typename _ForwardIterator,
typename _Compare>
3226 __is_sorted_until(_ForwardIterator __first, _ForwardIterator __last,
3229 if (__first == __last)
3232 _ForwardIterator __next = __first;
3233 for (++__next; __next != __last; __first = __next, (void)++__next)
3234 if (__comp(__next, __first))
3247 template<
typename _ForwardIterator>
3248 inline _ForwardIterator
3253 __glibcxx_function_requires(_LessThanComparableConcept<
3254 typename iterator_traits<_ForwardIterator>::value_type>)
3255 __glibcxx_requires_valid_range(__first, __last);
3256 __glibcxx_requires_irreflexive(__first, __last);
3258 return std::__is_sorted_until(__first, __last,
3259 __gnu_cxx::__ops::__iter_less_iter());
3271 template<
typename _ForwardIterator,
typename _Compare>
3272 inline _ForwardIterator
3278 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3279 typename iterator_traits<_ForwardIterator>::value_type,
3280 typename iterator_traits<_ForwardIterator>::value_type>)
3281 __glibcxx_requires_valid_range(__first, __last);
3282 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
3284 return std::__is_sorted_until(__first, __last,
3285 __gnu_cxx::__ops::__iter_comp_iter(__comp));
3296 template<
typename _Tp>
3297 _GLIBCXX14_CONSTEXPR
3298 inline pair<const _Tp&, const _Tp&>
3317 template<
typename _Tp,
typename _Compare>
3318 _GLIBCXX14_CONSTEXPR
3319 inline pair<const _Tp&, const _Tp&>
3320 minmax(
const _Tp& __a,
const _Tp& __b, _Compare __comp)
3326 template<
typename _ForwardIterator,
typename _Compare>
3327 _GLIBCXX14_CONSTEXPR
3328 pair<_ForwardIterator, _ForwardIterator>
3329 __minmax_element(_ForwardIterator __first, _ForwardIterator __last,
3332 _ForwardIterator __next = __first;
3333 if (__first == __last
3334 || ++__next == __last)
3337 _ForwardIterator __min{}, __max{};
3338 if (__comp(__next, __first))
3352 while (__first != __last)
3355 if (++__next == __last)
3357 if (__comp(__first, __min))
3359 else if (!__comp(__first, __max))
3364 if (__comp(__next, __first))
3366 if (__comp(__next, __min))
3368 if (!__comp(__first, __max))
3373 if (__comp(__first, __min))
3375 if (!__comp(__next, __max))
3397 template<
typename _ForwardIterator>
3398 _GLIBCXX14_CONSTEXPR
3399 inline pair<_ForwardIterator, _ForwardIterator>
3404 __glibcxx_function_requires(_LessThanComparableConcept<
3405 typename iterator_traits<_ForwardIterator>::value_type>)
3406 __glibcxx_requires_valid_range(__first, __last);
3407 __glibcxx_requires_irreflexive(__first, __last);
3409 return std::__minmax_element(__first, __last,
3410 __gnu_cxx::__ops::__iter_less_iter());
3425 template<
typename _ForwardIterator,
typename _Compare>
3426 _GLIBCXX14_CONSTEXPR
3427 inline pair<_ForwardIterator, _ForwardIterator>
3433 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3434 typename iterator_traits<_ForwardIterator>::value_type,
3435 typename iterator_traits<_ForwardIterator>::value_type>)
3436 __glibcxx_requires_valid_range(__first, __last);
3437 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
3439 return std::__minmax_element(__first, __last,
3440 __gnu_cxx::__ops::__iter_comp_iter(__comp));
3444 template<
typename _Tp>
3445 _GLIBCXX14_CONSTEXPR
3447 min(initializer_list<_Tp> __l)
3448 {
return *std::min_element(__l.begin(), __l.end()); }
3450 template<
typename _Tp,
typename _Compare>
3451 _GLIBCXX14_CONSTEXPR
3453 min(initializer_list<_Tp> __l, _Compare __comp)
3454 {
return *std::min_element(__l.begin(), __l.end(), __comp); }
3456 template<
typename _Tp>
3457 _GLIBCXX14_CONSTEXPR
3459 max(initializer_list<_Tp> __l)
3460 {
return *std::max_element(__l.begin(), __l.end()); }
3462 template<
typename _Tp,
typename _Compare>
3463 _GLIBCXX14_CONSTEXPR
3465 max(initializer_list<_Tp> __l, _Compare __comp)
3466 {
return *std::max_element(__l.begin(), __l.end(), __comp); }
3468 template<
typename _Tp>
3469 _GLIBCXX14_CONSTEXPR
3470 inline pair<_Tp, _Tp>
3471 minmax(initializer_list<_Tp> __l)
3473 pair<const _Tp*, const _Tp*> __p =
3474 std::minmax_element(__l.begin(), __l.end());
3478 template<
typename _Tp,
typename _Compare>
3479 _GLIBCXX14_CONSTEXPR
3480 inline pair<_Tp, _Tp>
3481 minmax(initializer_list<_Tp> __l, _Compare __comp)
3483 pair<const _Tp*, const _Tp*> __p =
3484 std::minmax_element(__l.begin(), __l.end(), __comp);
3488 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
3489 typename _BinaryPredicate>
3491 __is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3492 _ForwardIterator2 __first2, _BinaryPredicate __pred)
3496 for (; __first1 != __last1; ++__first1, (void)++__first2)
3497 if (!__pred(__first1, __first2))
3500 if (__first1 == __last1)
3505 _ForwardIterator2 __last2 = __first2;
3507 for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
3510 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)))
3514 = std::__count_if(__first2, __last2,
3515 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan));
3516 if (0 == __matches ||
3517 std::__count_if(__scan, __last1,
3518 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan))
3537 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
3545 __glibcxx_function_requires(_EqualOpConcept<
3546 typename iterator_traits<_ForwardIterator1>::value_type,
3547 typename iterator_traits<_ForwardIterator2>::value_type>)
3551 __gnu_cxx::__ops::__iter_equal_to_iter());
3568 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
3569 typename _BinaryPredicate>
3578 typename iterator_traits<_ForwardIterator1>::value_type,
3579 typename iterator_traits<_ForwardIterator2>::value_type>)
3583 __gnu_cxx::__ops::__iter_comp_iter(
__pred));
3586#if __cplusplus > 201103L
3587 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
3588 typename _BinaryPredicate>
3590 __is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3591 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
3592 _BinaryPredicate __pred)
3595 =
typename iterator_traits<_ForwardIterator1>::iterator_category;
3597 =
typename iterator_traits<_ForwardIterator2>::iterator_category;
3598 using _It1_is_RA = is_same<_Cat1, random_access_iterator_tag>;
3599 using _It2_is_RA = is_same<_Cat2, random_access_iterator_tag>;
3600 constexpr bool __ra_iters = _It1_is_RA() && _It2_is_RA();
3611 for (; __first1 != __last1 && __first2 != __last2;
3612 ++__first1, (void)++__first2)
3613 if (!__pred(__first1, __first2))
3618 if (__first1 == __last1)
3625 if (__d1 == 0 && __d2 == 0)
3631 for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
3634 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)))
3637 auto __matches = std::__count_if(__first2, __last2,
3638 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan));
3640 || std::__count_if(__scan, __last1,
3641 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan))
3661 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
3671 __gnu_cxx::__ops::__iter_equal_to_iter());
3688 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
3689 typename _BinaryPredicate>
3699 __gnu_cxx::__ops::__iter_comp_iter(
__pred));
3703#ifdef _GLIBCXX_USE_C99_STDINT_TR1
3716 template<
typename _RandomAccessIterator,
3717 typename _UniformRandomNumberGenerator>
3723 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
3725 __glibcxx_requires_valid_range(__first, __last);
3727 if (__first == __last)
3730 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
3733 typedef typename std::make_unsigned<_DistanceType>::type
__ud_type;
3735 typedef typename __distr_type::param_type
__p_type;
3739 std::iter_swap(__i, __first + __d(
__g,
__p_type(0, __i - __first)));
3745_GLIBCXX_END_NAMESPACE_VERSION
3747_GLIBCXX_BEGIN_NAMESPACE_ALGO
3761 template<
typename _InputIterator,
typename _Function>
3767 __glibcxx_requires_valid_range(__first, __last);
3768 for (; __first != __last; ++__first)
3770 return _GLIBCXX_MOVE(__f);
3782 template<
typename _InputIterator,
typename _Tp>
3783 inline _InputIterator
3789 __glibcxx_function_requires(_EqualOpConcept<
3790 typename iterator_traits<_InputIterator>::value_type, _Tp>)
3791 __glibcxx_requires_valid_range(__first, __last);
3793 __gnu_cxx::__ops::__iter_equals_val(__val));
3806 template<
typename _InputIterator,
typename _Predicate>
3807 inline _InputIterator
3813 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
3814 typename iterator_traits<_InputIterator>::value_type>)
3815 __glibcxx_requires_valid_range(__first, __last);
3818 __gnu_cxx::__ops::__pred_iter(
__pred));
3837 template<
typename _InputIterator,
typename _ForwardIterator>
3845 __glibcxx_function_requires(_EqualOpConcept<
3846 typename iterator_traits<_InputIterator>::value_type,
3847 typename iterator_traits<_ForwardIterator>::value_type>)
3877 template<
typename _InputIterator,
typename _ForwardIterator,
3878 typename _BinaryPredicate>
3888 typename iterator_traits<_InputIterator>::value_type,
3889 typename iterator_traits<_ForwardIterator>::value_type>)
3909 template<
typename _ForwardIterator>
3910 inline _ForwardIterator
3915 __glibcxx_function_requires(_EqualityComparableConcept<
3916 typename iterator_traits<_ForwardIterator>::value_type>)
3917 __glibcxx_requires_valid_range(__first, __last);
3919 return std::__adjacent_find(__first, __last,
3920 __gnu_cxx::__ops::__iter_equal_to_iter());
3934 template<
typename _ForwardIterator,
typename _BinaryPredicate>
3935 inline _ForwardIterator
3942 typename iterator_traits<_ForwardIterator>::value_type,
3943 typename iterator_traits<_ForwardIterator>::value_type>)
3944 __glibcxx_requires_valid_range(__first, __last);
3946 return std::__adjacent_find(__first, __last,
3959 template<
typename _InputIterator,
typename _Tp>
3960 inline typename iterator_traits<_InputIterator>::difference_type
3965 __glibcxx_function_requires(_EqualOpConcept<
3966 typename iterator_traits<_InputIterator>::value_type, _Tp>)
3967 __glibcxx_requires_valid_range(__first, __last);
3969 return std::__count_if(__first, __last,
3970 __gnu_cxx::__ops::__iter_equals_val(__value));
3982 template<
typename _InputIterator,
typename _Predicate>
3983 inline typename iterator_traits<_InputIterator>::difference_type
3988 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
3989 typename iterator_traits<_InputIterator>::value_type>)
3990 __glibcxx_requires_valid_range(__first, __last);
3992 return std::__count_if(__first, __last,
3993 __gnu_cxx::__ops::__pred_iter(
__pred));
4022 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
4023 inline _ForwardIterator1
4030 __glibcxx_function_requires(_EqualOpConcept<
4031 typename iterator_traits<_ForwardIterator1>::value_type,
4032 typename iterator_traits<_ForwardIterator2>::value_type>)
4037 __gnu_cxx::__ops::__iter_equal_to_iter());
4061 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
4062 typename _BinaryPredicate>
4063 inline _ForwardIterator1
4072 typename iterator_traits<_ForwardIterator1>::value_type,
4073 typename iterator_traits<_ForwardIterator2>::value_type>)
4096 template<
typename _ForwardIterator,
typename _Integer,
typename _Tp>
4097 inline _ForwardIterator
4099 _Integer __count,
const _Tp& __val)
4103 __glibcxx_function_requires(_EqualOpConcept<
4104 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
4105 __glibcxx_requires_valid_range(__first, __last);
4107 return std::__search_n(__first, __last, __count,
4108 __gnu_cxx::__ops::__iter_equals_val(__val));
4129 template<
typename _ForwardIterator,
typename _Integer,
typename _Tp,
4130 typename _BinaryPredicate>
4131 inline _ForwardIterator
4133 _Integer __count,
const _Tp& __val,
4139 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
4140 __glibcxx_requires_valid_range(__first, __last);
4142 return std::__search_n(__first, __last, __count,
4163 template<
typename _InputIterator,
typename _OutputIterator,
4164 typename _UnaryOperation>
4171 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4174 __glibcxx_requires_valid_range(__first, __last);
4200 template<
typename _InputIterator1,
typename _InputIterator2,
4201 typename _OutputIterator,
typename _BinaryOperation>
4210 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4233 template<
typename _ForwardIterator,
typename _Tp>
4239 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4241 __glibcxx_function_requires(_EqualOpConcept<
4242 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
4243 __glibcxx_function_requires(_ConvertibleConcept<_Tp,
4244 typename iterator_traits<_ForwardIterator>::value_type>)
4245 __glibcxx_requires_valid_range(__first, __last);
4247 for (; __first != __last; ++__first)
4265 template<
typename _ForwardIterator,
typename _Predicate,
typename _Tp>
4271 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4273 __glibcxx_function_requires(_ConvertibleConcept<_Tp,
4274 typename iterator_traits<_ForwardIterator>::value_type>)
4275 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4276 typename iterator_traits<_ForwardIterator>::value_type>)
4277 __glibcxx_requires_valid_range(__first, __last);
4279 for (; __first != __last; ++__first)
4297 template<
typename _ForwardIterator,
typename _Generator>
4304 __glibcxx_function_requires(_GeneratorConcept<
_Generator,
4305 typename iterator_traits<_ForwardIterator>::value_type>)
4306 __glibcxx_requires_valid_range(__first, __last);
4308 for (; __first != __last; ++__first)
4328 template<
typename _OutputIterator,
typename _Size,
typename _Generator>
4333 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4335 __typeof__(
__gen())>)
4364 template<
typename _InputIterator,
typename _OutputIterator>
4365 inline _OutputIterator
4371 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4372 typename iterator_traits<_InputIterator>::value_type>)
4373 __glibcxx_function_requires(_EqualityComparableConcept<
4374 typename iterator_traits<_InputIterator>::value_type>)
4375 __glibcxx_requires_valid_range(__first, __last);
4377 if (__first == __last)
4380 __gnu_cxx::__ops::__iter_equal_to_iter(),
4404 template<
typename _InputIterator,
typename _OutputIterator,
4405 typename _BinaryPredicate>
4406 inline _OutputIterator
4413 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4414 typename iterator_traits<_InputIterator>::value_type>)
4415 __glibcxx_requires_valid_range(__first, __last);
4417 if (__first == __last)
4437 template<
typename _RandomAccessIterator>
4439 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
4442 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4443 _RandomAccessIterator>)
4444 __glibcxx_requires_valid_range(__first, __last);
4446 if (__first != __last)
4447 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
4450 _RandomAccessIterator __j = __first
4453 std::iter_swap(__i, __j);
4472 template<
typename _RandomAccessIterator,
typename _RandomNumberGenerator>
4482 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4484 __glibcxx_requires_valid_range(__first, __last);
4486 if (__first == __last)
4492 std::iter_swap(__i, __j);
4512 template<
typename _ForwardIterator,
typename _Predicate>
4513 inline _ForwardIterator
4518 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4520 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4521 typename iterator_traits<_ForwardIterator>::value_type>)
4522 __glibcxx_requires_valid_range(__first, __last);
4545 template<
typename _RandomAccessIterator>
4552 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4554 __glibcxx_function_requires(_LessThanComparableConcept<
4555 typename iterator_traits<_RandomAccessIterator>::value_type>)
4556 __glibcxx_requires_valid_range(__first, __middle);
4557 __glibcxx_requires_valid_range(__middle, __last);
4558 __glibcxx_requires_irreflexive(__first, __last);
4560 std::__partial_sort(__first, __middle, __last,
4561 __gnu_cxx::__ops::__iter_less_iter());
4583 template<
typename _RandomAccessIterator,
typename _Compare>
4591 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4593 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4594 typename iterator_traits<_RandomAccessIterator>::value_type,
4595 typename iterator_traits<_RandomAccessIterator>::value_type>)
4596 __glibcxx_requires_valid_range(__first, __middle);
4597 __glibcxx_requires_valid_range(__middle, __last);
4598 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
4600 std::__partial_sort(__first, __middle, __last,
4601 __gnu_cxx::__ops::__iter_comp_iter(__comp));
4619 template<
typename _RandomAccessIterator>
4625 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4627 __glibcxx_function_requires(_LessThanComparableConcept<
4628 typename iterator_traits<_RandomAccessIterator>::value_type>)
4629 __glibcxx_requires_valid_range(__first,
__nth);
4630 __glibcxx_requires_valid_range(
__nth, __last);
4631 __glibcxx_requires_irreflexive(__first, __last);
4633 if (__first == __last ||
__nth == __last)
4636 std::__introselect(__first,
__nth, __last,
4638 __gnu_cxx::__ops::__iter_less_iter());
4658 template<
typename _RandomAccessIterator,
typename _Compare>
4664 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4666 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4667 typename iterator_traits<_RandomAccessIterator>::value_type,
4668 typename iterator_traits<_RandomAccessIterator>::value_type>)
4669 __glibcxx_requires_valid_range(__first,
__nth);
4670 __glibcxx_requires_valid_range(
__nth, __last);
4671 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
4673 if (__first == __last ||
__nth == __last)
4676 std::__introselect(__first,
__nth, __last,
4678 __gnu_cxx::__ops::__iter_comp_iter(__comp));
4695 template<
typename _RandomAccessIterator>
4700 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4702 __glibcxx_function_requires(_LessThanComparableConcept<
4703 typename iterator_traits<_RandomAccessIterator>::value_type>)
4704 __glibcxx_requires_valid_range(__first, __last);
4705 __glibcxx_requires_irreflexive(__first, __last);
4707 std::__sort(__first, __last, __gnu_cxx::__ops::__iter_less_iter());
4725 template<
typename _RandomAccessIterator,
typename _Compare>
4731 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4733 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4734 typename iterator_traits<_RandomAccessIterator>::value_type,
4735 typename iterator_traits<_RandomAccessIterator>::value_type>)
4736 __glibcxx_requires_valid_range(__first, __last);
4737 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
4739 std::__sort(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
4742 template<
typename _InputIterator1,
typename _InputIterator2,
4743 typename _OutputIterator,
typename _Compare>
4745 __merge(_InputIterator1 __first1, _InputIterator1 __last1,
4746 _InputIterator2 __first2, _InputIterator2 __last2,
4747 _OutputIterator __result, _Compare __comp)
4749 while (__first1 != __last1 && __first2 != __last2)
4751 if (__comp(__first2, __first1))
4753 *__result = *__first2;
4758 *__result = *__first1;
4763 return std::copy(__first2, __last2,
4764 std::copy(__first1, __last1, __result));
4786 template<
typename _InputIterator1,
typename _InputIterator2,
4787 typename _OutputIterator>
4788 inline _OutputIterator
4796 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4797 typename iterator_traits<_InputIterator1>::value_type>)
4798 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4799 typename iterator_traits<_InputIterator2>::value_type>)
4800 __glibcxx_function_requires(_LessThanOpConcept<
4801 typename iterator_traits<_InputIterator2>::value_type,
4802 typename iterator_traits<_InputIterator1>::value_type>)
4810 __gnu_cxx::__ops::__iter_less_iter());
4836 template<
typename _InputIterator1,
typename _InputIterator2,
4837 typename _OutputIterator,
typename _Compare>
4838 inline _OutputIterator
4841 _OutputIterator
__result, _Compare __comp)
4846 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4847 typename iterator_traits<_InputIterator1>::value_type>)
4848 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4849 typename iterator_traits<_InputIterator2>::value_type>)
4850 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4851 typename iterator_traits<_InputIterator2>::value_type,
4852 typename iterator_traits<_InputIterator1>::value_type>)
4860 __gnu_cxx::__ops::__iter_comp_iter(__comp));
4863 template<
typename _RandomAccessIterator,
typename _Compare>
4865 __stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
4868 typedef typename iterator_traits<_RandomAccessIterator>::value_type
4870 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
4873 typedef _Temporary_buffer<_RandomAccessIterator, _ValueType> _TmpBuf;
4874 _TmpBuf __buf(__first, __last);
4876 if (__buf.begin() == 0)
4879 std::__stable_sort_adaptive(__first, __last, __buf.begin(),
4880 _DistanceType(__buf.size()), __comp);
4900 template<
typename _RandomAccessIterator>
4905 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4907 __glibcxx_function_requires(_LessThanComparableConcept<
4908 typename iterator_traits<_RandomAccessIterator>::value_type>)
4909 __glibcxx_requires_valid_range(__first, __last);
4910 __glibcxx_requires_irreflexive(__first, __last);
4912 _GLIBCXX_STD_A::__stable_sort(__first, __last,
4913 __gnu_cxx::__ops::__iter_less_iter());
4934 template<
typename _RandomAccessIterator,
typename _Compare>
4940 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4942 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4943 typename iterator_traits<_RandomAccessIterator>::value_type,
4944 typename iterator_traits<_RandomAccessIterator>::value_type>)
4945 __glibcxx_requires_valid_range(__first, __last);
4946 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
4948 _GLIBCXX_STD_A::__stable_sort(__first, __last,
4949 __gnu_cxx::__ops::__iter_comp_iter(__comp));
4952 template<
typename _InputIterator1,
typename _InputIterator2,
4953 typename _OutputIterator,
4956 __set_union(_InputIterator1 __first1, _InputIterator1 __last1,
4957 _InputIterator2 __first2, _InputIterator2 __last2,
4958 _OutputIterator __result, _Compare __comp)
4960 while (__first1 != __last1 && __first2 != __last2)
4962 if (__comp(__first1, __first2))
4964 *__result = *__first1;
4967 else if (__comp(__first2, __first1))
4969 *__result = *__first2;
4974 *__result = *__first1;
4980 return std::copy(__first2, __last2,
4981 std::copy(__first1, __last1, __result));
5002 template<
typename _InputIterator1,
typename _InputIterator2,
5003 typename _OutputIterator>
5004 inline _OutputIterator
5012 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5013 typename iterator_traits<_InputIterator1>::value_type>)
5014 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5015 typename iterator_traits<_InputIterator2>::value_type>)
5016 __glibcxx_function_requires(_LessThanOpConcept<
5017 typename iterator_traits<_InputIterator1>::value_type,
5018 typename iterator_traits<_InputIterator2>::value_type>)
5019 __glibcxx_function_requires(_LessThanOpConcept<
5020 typename iterator_traits<_InputIterator2>::value_type,
5021 typename iterator_traits<_InputIterator1>::value_type>)
5029 __gnu_cxx::__ops::__iter_less_iter());
5051 template<
typename _InputIterator1,
typename _InputIterator2,
5052 typename _OutputIterator,
typename _Compare>
5053 inline _OutputIterator
5056 _OutputIterator
__result, _Compare __comp)
5061 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5062 typename iterator_traits<_InputIterator1>::value_type>)
5063 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5064 typename iterator_traits<_InputIterator2>::value_type>)
5065 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5066 typename iterator_traits<_InputIterator1>::value_type,
5067 typename iterator_traits<_InputIterator2>::value_type>)
5068 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5069 typename iterator_traits<_InputIterator2>::value_type,
5070 typename iterator_traits<_InputIterator1>::value_type>)
5078 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5081 template<
typename _InputIterator1,
typename _InputIterator2,
5082 typename _OutputIterator,
5085 __set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5086 _InputIterator2 __first2, _InputIterator2 __last2,
5087 _OutputIterator __result, _Compare __comp)
5089 while (__first1 != __last1 && __first2 != __last2)
5090 if (__comp(__first1, __first2))
5092 else if (__comp(__first2, __first1))
5096 *__result = *__first1;
5121 template<
typename _InputIterator1,
typename _InputIterator2,
5122 typename _OutputIterator>
5123 inline _OutputIterator
5131 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5132 typename iterator_traits<_InputIterator1>::value_type>)
5133 __glibcxx_function_requires(_LessThanOpConcept<
5134 typename iterator_traits<_InputIterator1>::value_type,
5135 typename iterator_traits<_InputIterator2>::value_type>)
5136 __glibcxx_function_requires(_LessThanOpConcept<
5137 typename iterator_traits<_InputIterator2>::value_type,
5138 typename iterator_traits<_InputIterator1>::value_type>)
5146 __gnu_cxx::__ops::__iter_less_iter());
5169 template<
typename _InputIterator1,
typename _InputIterator2,
5170 typename _OutputIterator,
typename _Compare>
5171 inline _OutputIterator
5174 _OutputIterator
__result, _Compare __comp)
5179 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5180 typename iterator_traits<_InputIterator1>::value_type>)
5181 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5182 typename iterator_traits<_InputIterator1>::value_type,
5183 typename iterator_traits<_InputIterator2>::value_type>)
5184 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5185 typename iterator_traits<_InputIterator2>::value_type,
5186 typename iterator_traits<_InputIterator1>::value_type>)
5194 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5197 template<
typename _InputIterator1,
typename _InputIterator2,
5198 typename _OutputIterator,
5201 __set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5202 _InputIterator2 __first2, _InputIterator2 __last2,
5203 _OutputIterator __result, _Compare __comp)
5205 while (__first1 != __last1 && __first2 != __last2)
5206 if (__comp(__first1, __first2))
5208 *__result = *__first1;
5212 else if (__comp(__first2, __first1))
5219 return std::copy(__first1, __last1, __result);
5241 template<
typename _InputIterator1,
typename _InputIterator2,
5242 typename _OutputIterator>
5243 inline _OutputIterator
5251 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5252 typename iterator_traits<_InputIterator1>::value_type>)
5253 __glibcxx_function_requires(_LessThanOpConcept<
5254 typename iterator_traits<_InputIterator1>::value_type,
5255 typename iterator_traits<_InputIterator2>::value_type>)
5256 __glibcxx_function_requires(_LessThanOpConcept<
5257 typename iterator_traits<_InputIterator2>::value_type,
5258 typename iterator_traits<_InputIterator1>::value_type>)
5266 __gnu_cxx::__ops::__iter_less_iter());
5291 template<
typename _InputIterator1,
typename _InputIterator2,
5292 typename _OutputIterator,
typename _Compare>
5293 inline _OutputIterator
5296 _OutputIterator
__result, _Compare __comp)
5301 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5302 typename iterator_traits<_InputIterator1>::value_type>)
5303 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5304 typename iterator_traits<_InputIterator1>::value_type,
5305 typename iterator_traits<_InputIterator2>::value_type>)
5306 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5307 typename iterator_traits<_InputIterator2>::value_type,
5308 typename iterator_traits<_InputIterator1>::value_type>)
5316 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5319 template<
typename _InputIterator1,
typename _InputIterator2,
5320 typename _OutputIterator,
5323 __set_symmetric_difference(_InputIterator1 __first1,
5324 _InputIterator1 __last1,
5325 _InputIterator2 __first2,
5326 _InputIterator2 __last2,
5327 _OutputIterator __result,
5330 while (__first1 != __last1 && __first2 != __last2)
5331 if (__comp(__first1, __first2))
5333 *__result = *__first1;
5337 else if (__comp(__first2, __first1))
5339 *__result = *__first2;
5348 return std::copy(__first2, __last2,
5349 std::copy(__first1, __last1, __result));
5369 template<
typename _InputIterator1,
typename _InputIterator2,
5370 typename _OutputIterator>
5371 inline _OutputIterator
5379 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5380 typename iterator_traits<_InputIterator1>::value_type>)
5381 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5382 typename iterator_traits<_InputIterator2>::value_type>)
5383 __glibcxx_function_requires(_LessThanOpConcept<
5384 typename iterator_traits<_InputIterator1>::value_type,
5385 typename iterator_traits<_InputIterator2>::value_type>)
5386 __glibcxx_function_requires(_LessThanOpConcept<
5387 typename iterator_traits<_InputIterator2>::value_type,
5388 typename iterator_traits<_InputIterator1>::value_type>)
5396 __gnu_cxx::__ops::__iter_less_iter());
5419 template<
typename _InputIterator1,
typename _InputIterator2,
5420 typename _OutputIterator,
typename _Compare>
5421 inline _OutputIterator
5430 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5431 typename iterator_traits<_InputIterator1>::value_type>)
5432 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5433 typename iterator_traits<_InputIterator2>::value_type>)
5434 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5435 typename iterator_traits<_InputIterator1>::value_type,
5436 typename iterator_traits<_InputIterator2>::value_type>)
5437 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5438 typename iterator_traits<_InputIterator2>::value_type,
5439 typename iterator_traits<_InputIterator1>::value_type>)
5447 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5450 template<
typename _ForwardIterator,
typename _Compare>
5451 _GLIBCXX14_CONSTEXPR
5453 __min_element(_ForwardIterator __first, _ForwardIterator __last,
5456 if (__first == __last)
5458 _ForwardIterator __result = __first;
5459 while (++__first != __last)
5460 if (__comp(__first, __result))
5472 template<
typename _ForwardIterator>
5473 _GLIBCXX14_CONSTEXPR
5479 __glibcxx_function_requires(_LessThanComparableConcept<
5480 typename iterator_traits<_ForwardIterator>::value_type>)
5481 __glibcxx_requires_valid_range(__first, __last);
5482 __glibcxx_requires_irreflexive(__first, __last);
5484 return _GLIBCXX_STD_A::__min_element(__first, __last,
5485 __gnu_cxx::__ops::__iter_less_iter());
5497 template<
typename _ForwardIterator,
typename _Compare>
5498 _GLIBCXX14_CONSTEXPR
5499 inline _ForwardIterator
5505 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5506 typename iterator_traits<_ForwardIterator>::value_type,
5507 typename iterator_traits<_ForwardIterator>::value_type>)
5508 __glibcxx_requires_valid_range(__first, __last);
5509 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
5511 return _GLIBCXX_STD_A::__min_element(__first, __last,
5512 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5515 template<
typename _ForwardIterator,
typename _Compare>
5516 _GLIBCXX14_CONSTEXPR
5518 __max_element(_ForwardIterator __first, _ForwardIterator __last,
5521 if (__first == __last)
return __first;
5522 _ForwardIterator __result = __first;
5523 while (++__first != __last)
5524 if (__comp(__result, __first))
5536 template<
typename _ForwardIterator>
5537 _GLIBCXX14_CONSTEXPR
5538 inline _ForwardIterator
5543 __glibcxx_function_requires(_LessThanComparableConcept<
5544 typename iterator_traits<_ForwardIterator>::value_type>)
5545 __glibcxx_requires_valid_range(__first, __last);
5546 __glibcxx_requires_irreflexive(__first, __last);
5548 return _GLIBCXX_STD_A::__max_element(__first, __last,
5549 __gnu_cxx::__ops::__iter_less_iter());
5561 template<
typename _ForwardIterator,
typename _Compare>
5562 _GLIBCXX14_CONSTEXPR
5563 inline _ForwardIterator
5569 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5570 typename iterator_traits<_ForwardIterator>::value_type,
5571 typename iterator_traits<_ForwardIterator>::value_type>)
5572 __glibcxx_requires_valid_range(__first, __last);
5573 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
5575 return _GLIBCXX_STD_A::__max_element(__first, __last,
5576 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5579_GLIBCXX_END_NAMESPACE_ALGO
constexpr pair< typename __decay_and_strip< _T1 >::__type, typename __decay_and_strip< _T2 >::__type > make_pair(_T1 &&__x, _T2 &&__y)
A convenience wrapper for creating a pair from two objects.
_GLIBCXX14_CONSTEXPR pair< const _Tp &, const _Tp & > minmax(const _Tp &, const _Tp &)
Determines min and max at once as an ordered pair.
_GLIBCXX14_CONSTEXPR const _Tp & max(const _Tp &, const _Tp &)
This does what you think it does.
_GLIBCXX14_CONSTEXPR const _Tp & min(const _Tp &, const _Tp &)
This does what you think it does.
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.
_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.
_RandomAccessIterator __unguarded_partition(_RandomAccessIterator __first, _RandomAccessIterator __last, _RandomAccessIterator __pivot, _Compare __comp)
This is a helper function...
void __introsort_loop(_RandomAccessIterator __first, _RandomAccessIterator __last, _Size __depth_limit, _Compare __comp)
This is a helper function for the sort routine.
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.
void advance(_InputIterator &__i, _Distance __n)
A generalization of pointer arithmetic.
_ForwardIterator __partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, forward_iterator_tag)
This is a helper function...
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.
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.
void __reverse(_BidirectionalIterator __first, _BidirectionalIterator __last, bidirectional_iterator_tag)
_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...
_RandomAccessIterator __unguarded_partition_pivot(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
This is a helper function...
_EuclideanRingElement __gcd(_EuclideanRingElement __m, _EuclideanRingElement __n)
_OutputIterator __unique_copy(_ForwardIterator __first, _ForwardIterator __last, _OutputIterator __result, _BinaryPredicate __binary_pred, forward_iterator_tag, output_iterator_tag)
void __inplace_stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
This is a helper function for the stable sorting routines.
iterator_traits< _Iter >::iterator_category __iterator_category(const _Iter &)
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 int __lg(int __n)
This is a helper function for the sort routines and for random.tcc.
_ForwardIterator __rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last, forward_iterator_tag)
This is a helper function for the rotate algorithm.
void __insertion_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
This is a helper function for the sort routine.
iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
_ForwardIterator __search_n_aux(_ForwardIterator __first, _ForwardIterator __last, _Integer __count, _UnaryPredicate __unary_pred, std::forward_iterator_tag)
void __unguarded_linear_insert(_RandomAccessIterator __last, _Compare __comp)
This is a helper function for the sort routine.
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.
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(__...
void __unguarded_insertion_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
This is a helper function for the sort routine.
_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.
_InputIterator __find_if_not(_InputIterator __first, _InputIterator __last, _Predicate __pred)
Provided for stable_partition to use.
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.