65 #if __cplusplus >= 201103L 71 namespace 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
101 __find_if(_InputIterator __first, _InputIterator __last,
104 while (__first != __last && !__pred(__first))
110 template<
typename _RandomAccessIterator,
typename _Predicate>
111 _RandomAccessIterator
112 __find_if(_RandomAccessIterator __first, _RandomAccessIterator __last,
115 typename iterator_traits<_RandomAccessIterator>::difference_type
116 __trip_count = (__last - __first) >> 2;
118 for (; __trip_count > 0; --__trip_count)
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>
183 for (; __len; --__len, ++__first)
184 if (!__pred(__first))
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>
258 _Integer __count, _UnaryPredicate __unary_pred,
262 while (__first != __last)
264 typename iterator_traits<_ForwardIterator>::difference_type
266 _ForwardIterator __i = __first;
268 while (__i != __last && __n != 1 && __unary_pred(__i))
286 template<
typename _RandomAccessIter,
typename _Integer,
287 typename _UnaryPredicate>
290 _Integer __count, _UnaryPredicate __unary_pred,
293 typedef typename std::iterator_traits<_RandomAccessIter>::difference_type
296 _DistanceType __tailSize = __last - __first;
297 _DistanceType __remainder = __count;
299 while (__remainder <= __tailSize)
301 __first += __remainder;
302 __tailSize -= __remainder;
305 _RandomAccessIter __backTrack = __first;
306 while (__unary_pred(--__backTrack))
308 if (--__remainder == 0)
309 return (__first - __count);
311 __remainder = __count + 1 - (__first - __backTrack);
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,
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,
370 _BinaryPredicate __comp)
373 __glibcxx_function_requires(_BidirectionalIteratorConcept<
374 _BidirectionalIterator1>)
375 __glibcxx_function_requires(_BidirectionalIteratorConcept<
376 _BidirectionalIterator2>)
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
425 find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
426 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
429 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
430 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
431 __glibcxx_function_requires(_EqualOpConcept<
432 typename iterator_traits<_ForwardIterator1>::value_type,
433 typename iterator_traits<_ForwardIterator2>::value_type>)
434 __glibcxx_requires_valid_range(__first1, __last1);
435 __glibcxx_requires_valid_range(__first2, __last2);
437 return std::__find_end(__first1, __last1, __first2, __last2,
440 __gnu_cxx::__ops::__iter_equal_to_iter());
471 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
472 typename _BinaryPredicate>
473 inline _ForwardIterator1
474 find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
475 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
476 _BinaryPredicate __comp)
479 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
480 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
481 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
482 typename iterator_traits<_ForwardIterator1>::value_type,
483 typename iterator_traits<_ForwardIterator2>::value_type>)
484 __glibcxx_requires_valid_range(__first1, __last1);
485 __glibcxx_requires_valid_range(__first2, __last2);
487 return std::__find_end(__first1, __last1, __first2, __last2,
490 __gnu_cxx::__ops::__iter_comp_iter(__comp));
493 #if __cplusplus >= 201103L 506 template<
typename _InputIterator,
typename _Predicate>
508 all_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
523 template<
typename _InputIterator,
typename _Predicate>
525 none_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
541 template<
typename _InputIterator,
typename _Predicate>
543 any_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
556 template<
typename _InputIterator,
typename _Predicate>
557 inline _InputIterator
558 find_if_not(_InputIterator __first, _InputIterator __last,
562 __glibcxx_function_requires(_InputIteratorConcept<_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>
582 is_partitioned(_InputIterator __first, _InputIterator __last,
586 if (__first == __last)
601 template<
typename _ForwardIterator,
typename _Predicate>
603 partition_point(_ForwardIterator __first, _ForwardIterator __last,
607 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
608 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
609 typename iterator_traits<_ForwardIterator>::value_type>)
612 __glibcxx_requires_valid_range(__first, __last);
614 typedef typename iterator_traits<_ForwardIterator>::difference_type
618 _DistanceType __half;
619 _ForwardIterator __middle;
626 if (__pred(*__middle))
630 __len = __len - __half - 1;
639 template<
typename _InputIterator,
typename _OutputIterator,
642 __remove_copy_if(_InputIterator __first, _InputIterator __last,
643 _OutputIterator __result, _Predicate __pred)
645 for (; __first != __last; ++__first)
646 if (!__pred(__first))
648 *__result = *__first;
668 template<
typename _InputIterator,
typename _OutputIterator,
typename _Tp>
669 inline _OutputIterator
670 remove_copy(_InputIterator __first, _InputIterator __last,
671 _OutputIterator __result,
const _Tp& __value)
674 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
675 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
676 typename iterator_traits<_InputIterator>::value_type>)
677 __glibcxx_function_requires(_EqualOpConcept<
678 typename iterator_traits<_InputIterator>::value_type, _Tp>)
679 __glibcxx_requires_valid_range(__first, __last);
681 return std::__remove_copy_if(__first, __last, __result,
682 __gnu_cxx::__ops::__iter_equals_val(__value));
700 template<
typename _InputIterator,
typename _OutputIterator,
702 inline _OutputIterator
703 remove_copy_if(_InputIterator __first, _InputIterator __last,
704 _OutputIterator __result, _Predicate __pred)
707 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
708 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
709 typename iterator_traits<_InputIterator>::value_type>)
710 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
711 typename iterator_traits<_InputIterator>::value_type>)
712 __glibcxx_requires_valid_range(__first, __last);
714 return std::__remove_copy_if(__first, __last, __result,
715 __gnu_cxx::__ops::__pred_iter(__pred));
718 #if __cplusplus >= 201103L 734 template<
typename _InputIterator,
typename _OutputIterator,
737 copy_if(_InputIterator __first, _InputIterator __last,
738 _OutputIterator __result, _Predicate __pred)
741 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
742 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
743 typename iterator_traits<_InputIterator>::value_type>)
744 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
745 typename iterator_traits<_InputIterator>::value_type>)
746 __glibcxx_requires_valid_range(__first, __last);
748 for (; __first != __last; ++__first)
749 if (__pred(*__first))
751 *__result = *__first;
757 template<
typename _InputIterator,
typename _Size,
typename _OutputIterator>
759 __copy_n(_InputIterator __first, _Size __n,
766 *__result = *__first;
777 template<
typename _RandomAccessIterator,
typename _Size,
778 typename _OutputIterator>
779 inline _OutputIterator
780 __copy_n(_RandomAccessIterator __first, _Size __n,
782 {
return std::copy(__first, __first + __n, __result); }
797 template<
typename _InputIterator,
typename _Size,
typename _OutputIterator>
798 inline _OutputIterator
799 copy_n(_InputIterator __first, _Size __n, _OutputIterator __result)
802 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
803 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
804 typename iterator_traits<_InputIterator>::value_type>)
806 return std::__copy_n(__first, __n, __result,
825 template<
typename _InputIterator,
typename _OutputIterator1,
826 typename _OutputIterator2,
typename _Predicate>
828 partition_copy(_InputIterator __first, _InputIterator __last,
829 _OutputIterator1 __out_true, _OutputIterator2 __out_false,
833 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
834 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator1,
835 typename iterator_traits<_InputIterator>::value_type>)
836 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator2,
837 typename iterator_traits<_InputIterator>::value_type>)
838 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
839 typename iterator_traits<_InputIterator>::value_type>)
840 __glibcxx_requires_valid_range(__first, __last);
842 for (; __first != __last; ++__first)
843 if (__pred(*__first))
845 *__out_true = *__first;
850 *__out_false = *__first;
858 template<
typename _ForwardIterator,
typename _Predicate>
860 __remove_if(_ForwardIterator __first, _ForwardIterator __last,
864 if (__first == __last)
866 _ForwardIterator __result = __first;
868 for (; __first != __last; ++__first)
869 if (!__pred(__first))
871 *__result = _GLIBCXX_MOVE(*__first);
894 template<
typename _ForwardIterator,
typename _Tp>
895 inline _ForwardIterator
896 remove(_ForwardIterator __first, _ForwardIterator __last,
900 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
902 __glibcxx_function_requires(_EqualOpConcept<
903 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
904 __glibcxx_requires_valid_range(__first, __last);
906 return std::__remove_if(__first, __last,
907 __gnu_cxx::__ops::__iter_equals_val(__value));
927 template<
typename _ForwardIterator,
typename _Predicate>
928 inline _ForwardIterator
929 remove_if(_ForwardIterator __first, _ForwardIterator __last,
933 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
935 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
936 typename iterator_traits<_ForwardIterator>::value_type>)
937 __glibcxx_requires_valid_range(__first, __last);
939 return std::__remove_if(__first, __last,
940 __gnu_cxx::__ops::__pred_iter(__pred));
943 template<
typename _ForwardIterator,
typename _BinaryPredicate>
945 __adjacent_find(_ForwardIterator __first, _ForwardIterator __last,
946 _BinaryPredicate __binary_pred)
948 if (__first == __last)
950 _ForwardIterator __next = __first;
951 while (++__next != __last)
953 if (__binary_pred(__first, __next))
960 template<
typename _ForwardIterator,
typename _BinaryPredicate>
962 __unique(_ForwardIterator __first, _ForwardIterator __last,
963 _BinaryPredicate __binary_pred)
966 __first = std::__adjacent_find(__first, __last, __binary_pred);
967 if (__first == __last)
971 _ForwardIterator __dest = __first;
973 while (++__first != __last)
974 if (!__binary_pred(__dest, __first))
975 *++__dest = _GLIBCXX_MOVE(*__first);
993 template<
typename _ForwardIterator>
994 inline _ForwardIterator
995 unique(_ForwardIterator __first, _ForwardIterator __last)
998 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1000 __glibcxx_function_requires(_EqualityComparableConcept<
1001 typename iterator_traits<_ForwardIterator>::value_type>)
1002 __glibcxx_requires_valid_range(__first, __last);
1004 return std::__unique(__first, __last,
1005 __gnu_cxx::__ops::__iter_equal_to_iter());
1023 template<
typename _ForwardIterator,
typename _BinaryPredicate>
1024 inline _ForwardIterator
1025 unique(_ForwardIterator __first, _ForwardIterator __last,
1026 _BinaryPredicate __binary_pred)
1029 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1031 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1032 typename iterator_traits<_ForwardIterator>::value_type,
1033 typename iterator_traits<_ForwardIterator>::value_type>)
1034 __glibcxx_requires_valid_range(__first, __last);
1036 return std::__unique(__first, __last,
1037 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred));
1046 template<
typename _ForwardIterator,
typename _OutputIterator,
1047 typename _BinaryPredicate>
1050 _OutputIterator __result, _BinaryPredicate __binary_pred,
1054 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1055 typename iterator_traits<_ForwardIterator>::value_type,
1056 typename iterator_traits<_ForwardIterator>::value_type>)
1058 _ForwardIterator __next = __first;
1059 *__result = *__first;
1060 while (++__next != __last)
1061 if (!__binary_pred(__first, __next))
1064 *++__result = *__first;
1075 template<
typename _InputIterator,
typename _OutputIterator,
1076 typename _BinaryPredicate>
1079 _OutputIterator __result, _BinaryPredicate __binary_pred,
1083 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1084 typename iterator_traits<_InputIterator>::value_type,
1085 typename iterator_traits<_InputIterator>::value_type>)
1087 typename iterator_traits<_InputIterator>::value_type __value = *__first;
1088 __decltype(__gnu_cxx::__ops::__iter_comp_val(__binary_pred))
1090 = __gnu_cxx::__ops::__iter_comp_val(__binary_pred);
1091 *__result = __value;
1092 while (++__first != __last)
1093 if (!__rebound_pred(__first, __value))
1096 *++__result = __value;
1107 template<
typename _InputIterator,
typename _ForwardIterator,
1108 typename _BinaryPredicate>
1111 _ForwardIterator __result, _BinaryPredicate __binary_pred,
1115 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1116 typename iterator_traits<_ForwardIterator>::value_type,
1117 typename iterator_traits<_InputIterator>::value_type>)
1118 *__result = *__first;
1119 while (++__first != __last)
1120 if (!__binary_pred(__result, __first))
1121 *++__result = *__first;
1130 template<
typename _B
idirectionalIterator>
1132 __reverse(_BidirectionalIterator __first, _BidirectionalIterator __last,
1136 if (__first == __last || __first == --__last)
1150 template<
typename _RandomAccessIterator>
1152 __reverse(_RandomAccessIterator __first, _RandomAccessIterator __last,
1155 if (__first == __last)
1158 while (__first < __last)
1178 template<
typename _B
idirectionalIterator>
1180 reverse(_BidirectionalIterator __first, _BidirectionalIterator __last)
1183 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
1184 _BidirectionalIterator>)
1185 __glibcxx_requires_valid_range(__first, __last);
1205 template<
typename _B
idirectionalIterator,
typename _OutputIterator>
1207 reverse_copy(_BidirectionalIterator __first, _BidirectionalIterator __last,
1208 _OutputIterator __result)
1211 __glibcxx_function_requires(_BidirectionalIteratorConcept<
1212 _BidirectionalIterator>)
1213 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1214 typename iterator_traits<_BidirectionalIterator>::value_type>)
1215 __glibcxx_requires_valid_range(__first, __last);
1217 while (__first != __last)
1220 *__result = *__last;
1230 template<
typename _Eucl
ideanRingElement>
1231 _EuclideanRingElement
1232 __gcd(_EuclideanRingElement __m, _EuclideanRingElement __n)
1236 _EuclideanRingElement __t = __m % __n;
1243 inline namespace _V2
1247 template<
typename _ForwardIterator>
1250 _ForwardIterator __middle,
1251 _ForwardIterator __last,
1254 if (__first == __middle)
1256 else if (__last == __middle)
1259 _ForwardIterator __first2 = __middle;
1265 if (__first == __middle)
1266 __middle = __first2;
1268 while (__first2 != __last);
1270 _ForwardIterator __ret = __first;
1272 __first2 = __middle;
1274 while (__first2 != __last)
1279 if (__first == __middle)
1280 __middle = __first2;
1281 else if (__first2 == __last)
1282 __first2 = __middle;
1288 template<
typename _B
idirectionalIterator>
1289 _BidirectionalIterator
1291 _BidirectionalIterator __middle,
1292 _BidirectionalIterator __last,
1296 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
1297 _BidirectionalIterator>)
1299 if (__first == __middle)
1301 else if (__last == __middle)
1307 while (__first != __middle && __middle != __last)
1313 if (__first == __middle)
1326 template<
typename _RandomAccessIterator>
1327 _RandomAccessIterator
1329 _RandomAccessIterator __middle,
1330 _RandomAccessIterator __last,
1334 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
1335 _RandomAccessIterator>)
1337 if (__first == __middle)
1339 else if (__last == __middle)
1342 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
1344 typedef typename iterator_traits<_RandomAccessIterator>::value_type
1347 _Distance __n = __last - __first;
1348 _Distance __k = __middle - __first;
1350 if (__k == __n - __k)
1356 _RandomAccessIterator __p = __first;
1357 _RandomAccessIterator __ret = __first + (__last - __middle);
1361 if (__k < __n - __k)
1363 if (__is_pod(_ValueType) && __k == 1)
1365 _ValueType __t = _GLIBCXX_MOVE(*__p);
1366 _GLIBCXX_MOVE3(__p + 1, __p + __n, __p);
1367 *(__p + __n - 1) = _GLIBCXX_MOVE(__t);
1370 _RandomAccessIterator __q = __p + __k;
1371 for (_Distance __i = 0; __i < __n - __k; ++ __i)
1380 std::swap(__n, __k);
1386 if (__is_pod(_ValueType) && __k == 1)
1388 _ValueType __t = _GLIBCXX_MOVE(*(__p + __n - 1));
1389 _GLIBCXX_MOVE_BACKWARD3(__p, __p + __n - 1, __p + __n);
1390 *__p = _GLIBCXX_MOVE(__t);
1393 _RandomAccessIterator __q = __p + __n;
1395 for (_Distance __i = 0; __i < __n - __k; ++ __i)
1404 std::swap(__n, __k);
1432 template<
typename _ForwardIterator>
1433 inline _ForwardIterator
1434 rotate(_ForwardIterator __first, _ForwardIterator __middle,
1435 _ForwardIterator __last)
1438 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1440 __glibcxx_requires_valid_range(__first, __middle);
1441 __glibcxx_requires_valid_range(__middle, __last);
1443 return std::__rotate(__first, __middle, __last,
1469 template<
typename _ForwardIterator,
typename _OutputIterator>
1470 inline _OutputIterator
1471 rotate_copy(_ForwardIterator __first, _ForwardIterator __middle,
1472 _ForwardIterator __last, _OutputIterator __result)
1475 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
1476 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1477 typename iterator_traits<_ForwardIterator>::value_type>)
1478 __glibcxx_requires_valid_range(__first, __middle);
1479 __glibcxx_requires_valid_range(__middle, __last);
1481 return std::copy(__first, __middle,
1482 std::copy(__middle, __last, __result));
1486 template<
typename _ForwardIterator,
typename _Predicate>
1491 if (__first == __last)
1494 while (__pred(*__first))
1495 if (++__first == __last)
1498 _ForwardIterator __next = __first;
1500 while (++__next != __last)
1501 if (__pred(*__next))
1511 template<
typename _B
idirectionalIterator,
typename _Predicate>
1512 _BidirectionalIterator
1513 __partition(_BidirectionalIterator __first, _BidirectionalIterator __last,
1519 if (__first == __last)
1521 else if (__pred(*__first))
1527 if (__first == __last)
1529 else if (!
bool(__pred(*__last)))
1546 template<
typename _ForwardIterator,
typename _Pointer,
typename _Predicate,
1550 _ForwardIterator __last,
1551 _Predicate __pred, _Distance __len,
1553 _Distance __buffer_size)
1558 if (__len <= __buffer_size)
1560 _ForwardIterator __result1 = __first;
1561 _Pointer __result2 = __buffer;
1566 *__result2 = _GLIBCXX_MOVE(*__first);
1569 for (; __first != __last; ++__first)
1570 if (__pred(__first))
1572 *__result1 = _GLIBCXX_MOVE(*__first);
1577 *__result2 = _GLIBCXX_MOVE(*__first);
1581 _GLIBCXX_MOVE3(__buffer, __result2, __result1);
1585 _ForwardIterator __middle = __first;
1587 _ForwardIterator __left_split =
1589 __len / 2, __buffer,
1594 _Distance __right_len = __len - __len / 2;
1595 _ForwardIterator __right_split =
1602 __buffer, __buffer_size);
1604 std::rotate(__left_split, __middle, __right_split);
1606 return __left_split;
1609 template<
typename _ForwardIterator,
typename _Predicate>
1611 __stable_partition(_ForwardIterator __first, _ForwardIterator __last,
1616 if (__first == __last)
1619 typedef typename iterator_traits<_ForwardIterator>::value_type
1621 typedef typename iterator_traits<_ForwardIterator>::difference_type
1629 _DistanceType(__buf.
size()));
1649 template<
typename _ForwardIterator,
typename _Predicate>
1650 inline _ForwardIterator
1651 stable_partition(_ForwardIterator __first, _ForwardIterator __last,
1655 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1657 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
1658 typename iterator_traits<_ForwardIterator>::value_type>)
1659 __glibcxx_requires_valid_range(__first, __last);
1661 return std::__stable_partition(__first, __last,
1662 __gnu_cxx::__ops::__pred_iter(__pred));
1666 template<
typename _RandomAccessIterator,
typename _Compare>
1669 _RandomAccessIterator __middle,
1670 _RandomAccessIterator __last, _Compare __comp)
1672 std::__make_heap(__first, __middle, __comp);
1673 for (_RandomAccessIterator __i = __middle; __i < __last; ++__i)
1674 if (__comp(__i, __first))
1675 std::__pop_heap(__first, __middle, __i, __comp);
1680 template<
typename _InputIterator,
typename _RandomAccessIterator,
1682 _RandomAccessIterator
1683 __partial_sort_copy(_InputIterator __first, _InputIterator __last,
1684 _RandomAccessIterator __result_first,
1685 _RandomAccessIterator __result_last,
1688 typedef typename iterator_traits<_InputIterator>::value_type
1690 typedef iterator_traits<_RandomAccessIterator> _RItTraits;
1691 typedef typename _RItTraits::difference_type _DistanceType;
1693 if (__result_first == __result_last)
1694 return __result_last;
1695 _RandomAccessIterator __result_real_last = __result_first;
1696 while (__first != __last && __result_real_last != __result_last)
1698 *__result_real_last = *__first;
1699 ++__result_real_last;
1703 std::__make_heap(__result_first, __result_real_last, __comp);
1704 while (__first != __last)
1706 if (__comp(__first, __result_first))
1707 std::__adjust_heap(__result_first, _DistanceType(0),
1708 _DistanceType(__result_real_last
1710 _InputValueType(*__first), __comp);
1713 std::__sort_heap(__result_first, __result_real_last, __comp);
1714 return __result_real_last;
1735 template<
typename _InputIterator,
typename _RandomAccessIterator>
1736 inline _RandomAccessIterator
1737 partial_sort_copy(_InputIterator __first, _InputIterator __last,
1738 _RandomAccessIterator __result_first,
1739 _RandomAccessIterator __result_last)
1741 #ifdef _GLIBCXX_CONCEPT_CHECKS 1742 typedef typename iterator_traits<_InputIterator>::value_type
1744 typedef typename iterator_traits<_RandomAccessIterator>::value_type
1749 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1750 __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
1752 __glibcxx_function_requires(_LessThanOpConcept<_InputValueType,
1754 __glibcxx_function_requires(_LessThanComparableConcept<_OutputValueType>)
1755 __glibcxx_requires_valid_range(__first, __last);
1756 __glibcxx_requires_irreflexive(__first, __last);
1757 __glibcxx_requires_valid_range(__result_first, __result_last);
1759 return std::__partial_sort_copy(__first, __last,
1760 __result_first, __result_last,
1761 __gnu_cxx::__ops::__iter_less_iter());
1784 template<
typename _InputIterator,
typename _RandomAccessIterator,
1786 inline _RandomAccessIterator
1787 partial_sort_copy(_InputIterator __first, _InputIterator __last,
1788 _RandomAccessIterator __result_first,
1789 _RandomAccessIterator __result_last,
1792 #ifdef _GLIBCXX_CONCEPT_CHECKS 1793 typedef typename iterator_traits<_InputIterator>::value_type
1795 typedef typename iterator_traits<_RandomAccessIterator>::value_type
1800 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1801 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
1802 _RandomAccessIterator>)
1803 __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
1805 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
1806 _InputValueType, _OutputValueType>)
1807 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
1808 _OutputValueType, _OutputValueType>)
1809 __glibcxx_requires_valid_range(__first, __last);
1810 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
1811 __glibcxx_requires_valid_range(__result_first, __result_last);
1813 return std::__partial_sort_copy(__first, __last,
1814 __result_first, __result_last,
1815 __gnu_cxx::__ops::__iter_comp_iter(__comp));
1819 template<
typename _RandomAccessIterator,
typename _Compare>
1824 typename iterator_traits<_RandomAccessIterator>::value_type
1825 __val = _GLIBCXX_MOVE(*__last);
1826 _RandomAccessIterator __next = __last;
1828 while (__comp(__val, __next))
1830 *__last = _GLIBCXX_MOVE(*__next);
1834 *__last = _GLIBCXX_MOVE(__val);
1838 template<
typename _RandomAccessIterator,
typename _Compare>
1841 _RandomAccessIterator __last, _Compare __comp)
1843 if (__first == __last)
return;
1845 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
1847 if (__comp(__i, __first))
1849 typename iterator_traits<_RandomAccessIterator>::value_type
1850 __val = _GLIBCXX_MOVE(*__i);
1851 _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1);
1852 *__first = _GLIBCXX_MOVE(__val);
1856 __gnu_cxx::__ops::__val_comp_iter(__comp));
1861 template<
typename _RandomAccessIterator,
typename _Compare>
1864 _RandomAccessIterator __last, _Compare __comp)
1866 for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
1868 __gnu_cxx::__ops::__val_comp_iter(__comp));
1875 enum { _S_threshold = 16 };
1878 template<
typename _RandomAccessIterator,
typename _Compare>
1881 _RandomAccessIterator __last, _Compare __comp)
1883 if (__last - __first >
int(_S_threshold))
1894 template<
typename _RandomAccessIterator,
typename _Compare>
1895 _RandomAccessIterator
1897 _RandomAccessIterator __last,
1898 _RandomAccessIterator __pivot, _Compare __comp)
1902 while (__comp(__first, __pivot))
1905 while (__comp(__pivot, __last))
1907 if (!(__first < __last))
1915 template<
typename _RandomAccessIterator,
typename _Compare>
1916 inline _RandomAccessIterator
1918 _RandomAccessIterator __last, _Compare __comp)
1920 _RandomAccessIterator __mid = __first + (__last - __first) / 2;
1926 template<
typename _RandomAccessIterator,
typename _Compare>
1928 __partial_sort(_RandomAccessIterator __first,
1929 _RandomAccessIterator __middle,
1930 _RandomAccessIterator __last,
1934 std::__sort_heap(__first, __middle, __comp);
1938 template<
typename _RandomAccessIterator,
typename _Size,
typename _Compare>
1941 _RandomAccessIterator __last,
1942 _Size __depth_limit, _Compare __comp)
1944 while (__last - __first >
int(_S_threshold))
1946 if (__depth_limit == 0)
1948 std::__partial_sort(__first, __last, __last, __comp);
1952 _RandomAccessIterator __cut =
1961 template<
typename _RandomAccessIterator,
typename _Compare>
1963 __sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
1966 if (__first != __last)
1975 template<
typename _RandomAccessIterator,
typename _Size,
typename _Compare>
1977 __introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth,
1978 _RandomAccessIterator __last, _Size __depth_limit,
1981 while (__last - __first > 3)
1983 if (__depth_limit == 0)
1991 _RandomAccessIterator __cut =
2021 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2022 inline _ForwardIterator
2023 lower_bound(_ForwardIterator __first, _ForwardIterator __last,
2024 const _Tp& __val, _Compare __comp)
2027 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2028 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2029 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
2030 __glibcxx_requires_partitioned_lower_pred(__first, __last,
2033 return std::__lower_bound(__first, __last, __val,
2034 __gnu_cxx::__ops::__iter_comp_val(__comp));
2037 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2039 __upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2040 const _Tp& __val, _Compare __comp)
2042 typedef typename iterator_traits<_ForwardIterator>::difference_type
2049 _DistanceType __half = __len >> 1;
2050 _ForwardIterator __middle = __first;
2052 if (__comp(__val, __middle))
2058 __len = __len - __half - 1;
2075 template<
typename _ForwardIterator,
typename _Tp>
2076 inline _ForwardIterator
2077 upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2081 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2082 __glibcxx_function_requires(_LessThanOpConcept<
2083 _Tp,
typename iterator_traits<_ForwardIterator>::value_type>)
2084 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2086 return std::__upper_bound(__first, __last, __val,
2087 __gnu_cxx::__ops::__val_less_iter());
2105 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2106 inline _ForwardIterator
2107 upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2108 const _Tp& __val, _Compare __comp)
2111 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2112 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2113 _Tp,
typename iterator_traits<_ForwardIterator>::value_type>)
2114 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2117 return std::__upper_bound(__first, __last, __val,
2118 __gnu_cxx::__ops::__val_comp_iter(__comp));
2121 template<
typename _ForwardIterator,
typename _Tp,
2122 typename _CompareItTp,
typename _CompareTpIt>
2124 __equal_range(_ForwardIterator __first, _ForwardIterator __last,
2126 _CompareItTp __comp_it_val, _CompareTpIt __comp_val_it)
2128 typedef typename iterator_traits<_ForwardIterator>::difference_type
2135 _DistanceType __half = __len >> 1;
2136 _ForwardIterator __middle = __first;
2138 if (__comp_it_val(__middle, __val))
2142 __len = __len - __half - 1;
2144 else if (__comp_val_it(__val, __middle))
2148 _ForwardIterator __left
2149 = std::__lower_bound(__first, __middle, __val, __comp_it_val);
2151 _ForwardIterator __right
2152 = std::__upper_bound(++__middle, __first, __val, __comp_val_it);
2176 template<
typename _ForwardIterator,
typename _Tp>
2178 equal_range(_ForwardIterator __first, _ForwardIterator __last,
2182 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2183 __glibcxx_function_requires(_LessThanOpConcept<
2184 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
2185 __glibcxx_function_requires(_LessThanOpConcept<
2186 _Tp,
typename iterator_traits<_ForwardIterator>::value_type>)
2187 __glibcxx_requires_partitioned_lower(__first, __last, __val);
2188 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2190 return std::__equal_range(__first, __last, __val,
2191 __gnu_cxx::__ops::__iter_less_val(),
2192 __gnu_cxx::__ops::__val_less_iter());
2212 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2214 equal_range(_ForwardIterator __first, _ForwardIterator __last,
2215 const _Tp& __val, _Compare __comp)
2218 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2219 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2220 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
2221 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2222 _Tp,
typename iterator_traits<_ForwardIterator>::value_type>)
2223 __glibcxx_requires_partitioned_lower_pred(__first, __last,
2225 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2228 return std::__equal_range(__first, __last, __val,
2229 __gnu_cxx::__ops::__iter_comp_val(__comp),
2230 __gnu_cxx::__ops::__val_comp_iter(__comp));
2245 template<
typename _ForwardIterator,
typename _Tp>
2247 binary_search(_ForwardIterator __first, _ForwardIterator __last,
2251 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2252 __glibcxx_function_requires(_LessThanOpConcept<
2253 _Tp,
typename iterator_traits<_ForwardIterator>::value_type>)
2254 __glibcxx_requires_partitioned_lower(__first, __last, __val);
2255 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2257 _ForwardIterator __i
2258 = std::__lower_bound(__first, __last, __val,
2259 __gnu_cxx::__ops::__iter_less_val());
2260 return __i != __last && !(__val < *__i);
2278 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2280 binary_search(_ForwardIterator __first, _ForwardIterator __last,
2281 const _Tp& __val, _Compare __comp)
2284 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2285 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2286 _Tp,
typename iterator_traits<_ForwardIterator>::value_type>)
2287 __glibcxx_requires_partitioned_lower_pred(__first, __last,
2289 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2292 _ForwardIterator __i
2293 = std::__lower_bound(__first, __last, __val,
2294 __gnu_cxx::__ops::__iter_comp_val(__comp));
2295 return __i != __last && !bool(__comp(__val, *__i));
2301 template<
typename _InputIterator1,
typename _InputIterator2,
2302 typename _OutputIterator,
typename _Compare>
2305 _InputIterator2 __first2, _InputIterator2 __last2,
2306 _OutputIterator __result, _Compare __comp)
2308 while (__first1 != __last1 && __first2 != __last2)
2310 if (__comp(__first2, __first1))
2312 *__result = _GLIBCXX_MOVE(*__first2);
2317 *__result = _GLIBCXX_MOVE(*__first1);
2322 if (__first1 != __last1)
2323 _GLIBCXX_MOVE3(__first1, __last1, __result);
2327 template<
typename _BidirectionalIterator1,
typename _BidirectionalIterator2,
2328 typename _BidirectionalIterator3,
typename _Compare>
2331 _BidirectionalIterator1 __last1,
2332 _BidirectionalIterator2 __first2,
2333 _BidirectionalIterator2 __last2,
2334 _BidirectionalIterator3 __result,
2337 if (__first1 == __last1)
2339 _GLIBCXX_MOVE_BACKWARD3(__first2, __last2, __result);
2342 else if (__first2 == __last2)
2349 if (__comp(__last2, __last1))
2351 *--__result = _GLIBCXX_MOVE(*__last1);
2352 if (__first1 == __last1)
2354 _GLIBCXX_MOVE_BACKWARD3(__first2, ++__last2, __result);
2361 *--__result = _GLIBCXX_MOVE(*__last2);
2362 if (__first2 == __last2)
2370 template<
typename _BidirectionalIterator1,
typename _BidirectionalIterator2,
2372 _BidirectionalIterator1
2374 _BidirectionalIterator1 __middle,
2375 _BidirectionalIterator1 __last,
2376 _Distance __len1, _Distance __len2,
2377 _BidirectionalIterator2 __buffer,
2378 _Distance __buffer_size)
2380 _BidirectionalIterator2 __buffer_end;
2381 if (__len1 > __len2 && __len2 <= __buffer_size)
2385 __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
2386 _GLIBCXX_MOVE_BACKWARD3(__first, __middle, __last);
2387 return _GLIBCXX_MOVE3(__buffer, __buffer_end, __first);
2392 else if (__len1 <= __buffer_size)
2396 __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
2397 _GLIBCXX_MOVE3(__middle, __last, __first);
2398 return _GLIBCXX_MOVE_BACKWARD3(__buffer, __buffer_end, __last);
2412 template<
typename _BidirectionalIterator,
typename _Distance,
2413 typename _Pointer,
typename _Compare>
2416 _BidirectionalIterator __middle,
2417 _BidirectionalIterator __last,
2418 _Distance __len1, _Distance __len2,
2419 _Pointer __buffer, _Distance __buffer_size,
2422 if (__len1 <= __len2 && __len1 <= __buffer_size)
2424 _Pointer __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
2428 else if (__len2 <= __buffer_size)
2430 _Pointer __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
2432 __buffer_end, __last, __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 __len1 - __len11, __len22, __buffer,
2464 __len22, __buffer, __buffer_size, __comp);
2467 __len2 - __len22, __buffer,
2468 __buffer_size, __comp);
2473 template<
typename _BidirectionalIterator,
typename _Distance,
2477 _BidirectionalIterator __middle,
2478 _BidirectionalIterator __last,
2479 _Distance __len1, _Distance __len2,
2482 if (__len1 == 0 || __len2 == 0)
2485 if (__len1 + __len2 == 2)
2487 if (__comp(__middle, __first))
2492 _BidirectionalIterator __first_cut = __first;
2493 _BidirectionalIterator __second_cut = __middle;
2494 _Distance __len11 = 0;
2495 _Distance __len22 = 0;
2496 if (__len1 > __len2)
2498 __len11 = __len1 / 2;
2501 = std::__lower_bound(__middle, __last, *__first_cut,
2502 __gnu_cxx::__ops::__iter_comp_val(__comp));
2507 __len22 = __len2 / 2;
2510 = std::__upper_bound(__first, __middle, *__second_cut,
2511 __gnu_cxx::__ops::__val_comp_iter(__comp));
2516 _BidirectionalIterator __new_middle = __first_cut;
2519 __len11, __len22, __comp);
2521 __len1 - __len11, __len2 - __len22, __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 _TmpBuf __buf(__first, __last);
2545 if (__buf.begin() == 0)
2547 (__first, __middle, __last, __len1, __len2, __comp);
2550 (__first, __middle, __last, __len1, __len2, __buf.begin(),
2551 _DistanceType(__buf.size()), __comp);
2572 template<
typename _B
idirectionalIterator>
2574 inplace_merge(_BidirectionalIterator __first,
2575 _BidirectionalIterator __middle,
2576 _BidirectionalIterator __last)
2579 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
2580 _BidirectionalIterator>)
2581 __glibcxx_function_requires(_LessThanComparableConcept<
2582 typename iterator_traits<_BidirectionalIterator>::value_type>)
2583 __glibcxx_requires_sorted(__first, __middle);
2584 __glibcxx_requires_sorted(__middle, __last);
2585 __glibcxx_requires_irreflexive(__first, __last);
2587 std::__inplace_merge(__first, __middle, __last,
2588 __gnu_cxx::__ops::__iter_less_iter());
2613 template<
typename _B
idirectionalIterator,
typename _Compare>
2615 inplace_merge(_BidirectionalIterator __first,
2616 _BidirectionalIterator __middle,
2617 _BidirectionalIterator __last,
2621 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
2622 _BidirectionalIterator>)
2623 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2624 typename iterator_traits<_BidirectionalIterator>::value_type,
2625 typename iterator_traits<_BidirectionalIterator>::value_type>)
2626 __glibcxx_requires_sorted_pred(__first, __middle, __comp);
2627 __glibcxx_requires_sorted_pred(__middle, __last, __comp);
2628 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
2630 std::__inplace_merge(__first, __middle, __last,
2631 __gnu_cxx::__ops::__iter_comp_iter(__comp));
2636 template<
typename _InputIterator,
typename _OutputIterator,
2640 _InputIterator __first2, _InputIterator __last2,
2641 _OutputIterator __result, _Compare __comp)
2643 while (__first1 != __last1 && __first2 != __last2)
2645 if (__comp(__first2, __first1))
2647 *__result = _GLIBCXX_MOVE(*__first2);
2652 *__result = _GLIBCXX_MOVE(*__first1);
2657 return _GLIBCXX_MOVE3(__first2, __last2,
2658 _GLIBCXX_MOVE3(__first1, __last1,
2662 template<
typename _RandomAccessIterator1,
typename _RandomAccessIterator2,
2663 typename _Distance,
typename _Compare>
2665 __merge_sort_loop(_RandomAccessIterator1 __first,
2666 _RandomAccessIterator1 __last,
2667 _RandomAccessIterator2 __result, _Distance __step_size,
2670 const _Distance __two_step = 2 * __step_size;
2672 while (__last - __first >= __two_step)
2675 __first + __step_size,
2676 __first + __two_step,
2678 __first += __two_step;
2680 __step_size =
std::min(_Distance(__last - __first), __step_size);
2683 __first + __step_size, __last, __result, __comp);
2686 template<
typename _RandomAccessIterator,
typename _Distance,
2689 __chunk_insertion_sort(_RandomAccessIterator __first,
2690 _RandomAccessIterator __last,
2691 _Distance __chunk_size, _Compare __comp)
2693 while (__last - __first >= __chunk_size)
2696 __first += __chunk_size;
2701 enum { _S_chunk_size = 7 };
2703 template<
typename _RandomAccessIterator,
typename _Po
inter,
typename _Compare>
2705 __merge_sort_with_buffer(_RandomAccessIterator __first,
2706 _RandomAccessIterator __last,
2707 _Pointer __buffer, _Compare __comp)
2709 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
2712 const _Distance __len = __last - __first;
2713 const _Pointer __buffer_last = __buffer + __len;
2715 _Distance __step_size = _S_chunk_size;
2716 std::__chunk_insertion_sort(__first, __last, __step_size, __comp);
2718 while (__step_size < __len)
2720 std::__merge_sort_loop(__first, __last, __buffer,
2721 __step_size, __comp);
2723 std::__merge_sort_loop(__buffer, __buffer_last, __first,
2724 __step_size, __comp);
2729 template<
typename _RandomAccessIterator,
typename _Pointer,
2730 typename _Distance,
typename _Compare>
2732 __stable_sort_adaptive(_RandomAccessIterator __first,
2733 _RandomAccessIterator __last,
2734 _Pointer __buffer, _Distance __buffer_size,
2737 const _Distance __len = (__last - __first + 1) / 2;
2738 const _RandomAccessIterator __middle = __first + __len;
2739 if (__len > __buffer_size)
2741 std::__stable_sort_adaptive(__first, __middle, __buffer,
2742 __buffer_size, __comp);
2743 std::__stable_sort_adaptive(__middle, __last, __buffer,
2744 __buffer_size, __comp);
2748 std::__merge_sort_with_buffer(__first, __middle, __buffer, __comp);
2749 std::__merge_sort_with_buffer(__middle, __last, __buffer, __comp);
2752 _Distance(__middle - __first),
2753 _Distance(__last - __middle),
2754 __buffer, __buffer_size,
2759 template<
typename _RandomAccessIterator,
typename _Compare>
2762 _RandomAccessIterator __last, _Compare __comp)
2764 if (__last - __first < 15)
2769 _RandomAccessIterator __middle = __first + (__last - __first) / 2;
2785 template<
typename _InputIterator1,
typename _InputIterator2,
2788 __includes(_InputIterator1 __first1, _InputIterator1 __last1,
2789 _InputIterator2 __first2, _InputIterator2 __last2,
2792 while (__first1 != __last1 && __first2 != __last2)
2793 if (__comp(__first2, __first1))
2795 else if (__comp(__first1, __first2))
2803 return __first2 == __last2;
2824 template<
typename _InputIterator1,
typename _InputIterator2>
2826 includes(_InputIterator1 __first1, _InputIterator1 __last1,
2827 _InputIterator2 __first2, _InputIterator2 __last2)
2830 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
2831 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
2832 __glibcxx_function_requires(_LessThanOpConcept<
2833 typename iterator_traits<_InputIterator1>::value_type,
2834 typename iterator_traits<_InputIterator2>::value_type>)
2835 __glibcxx_function_requires(_LessThanOpConcept<
2836 typename iterator_traits<_InputIterator2>::value_type,
2837 typename iterator_traits<_InputIterator1>::value_type>)
2838 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
2839 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
2840 __glibcxx_requires_irreflexive2(__first1, __last1);
2841 __glibcxx_requires_irreflexive2(__first2, __last2);
2843 return std::__includes(__first1, __last1, __first2, __last2,
2844 __gnu_cxx::__ops::__iter_less_iter());
2868 template<
typename _InputIterator1,
typename _InputIterator2,
2871 includes(_InputIterator1 __first1, _InputIterator1 __last1,
2872 _InputIterator2 __first2, _InputIterator2 __last2,
2876 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
2877 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
2878 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2879 typename iterator_traits<_InputIterator1>::value_type,
2880 typename iterator_traits<_InputIterator2>::value_type>)
2881 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2882 typename iterator_traits<_InputIterator2>::value_type,
2883 typename iterator_traits<_InputIterator1>::value_type>)
2884 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
2885 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
2886 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
2887 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
2889 return std::__includes(__first1, __last1, __first2, __last2,
2890 __gnu_cxx::__ops::__iter_comp_iter(__comp));
2903 template<
typename _B
idirectionalIterator,
typename _Compare>
2905 __next_permutation(_BidirectionalIterator __first,
2906 _BidirectionalIterator __last, _Compare __comp)
2908 if (__first == __last)
2910 _BidirectionalIterator __i = __first;
2919 _BidirectionalIterator __ii = __i;
2921 if (__comp(__i, __ii))
2923 _BidirectionalIterator __j = __last;
2924 while (!__comp(__i, --__j))
2952 template<
typename _B
idirectionalIterator>
2954 next_permutation(_BidirectionalIterator __first,
2955 _BidirectionalIterator __last)
2958 __glibcxx_function_requires(_BidirectionalIteratorConcept<
2959 _BidirectionalIterator>)
2960 __glibcxx_function_requires(_LessThanComparableConcept<
2961 typename iterator_traits<_BidirectionalIterator>::value_type>)
2962 __glibcxx_requires_valid_range(__first, __last);
2963 __glibcxx_requires_irreflexive(__first, __last);
2965 return std::__next_permutation
2966 (__first, __last, __gnu_cxx::__ops::__iter_less_iter());
2984 template<
typename _B
idirectionalIterator,
typename _Compare>
2986 next_permutation(_BidirectionalIterator __first,
2987 _BidirectionalIterator __last, _Compare __comp)
2990 __glibcxx_function_requires(_BidirectionalIteratorConcept<
2991 _BidirectionalIterator>)
2992 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2993 typename iterator_traits<_BidirectionalIterator>::value_type,
2994 typename iterator_traits<_BidirectionalIterator>::value_type>)
2995 __glibcxx_requires_valid_range(__first, __last);
2996 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
2998 return std::__next_permutation
2999 (__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
3002 template<
typename _B
idirectionalIterator,
typename _Compare>
3004 __prev_permutation(_BidirectionalIterator __first,
3005 _BidirectionalIterator __last, _Compare __comp)
3007 if (__first == __last)
3009 _BidirectionalIterator __i = __first;
3018 _BidirectionalIterator __ii = __i;
3020 if (__comp(__ii, __i))
3022 _BidirectionalIterator __j = __last;
3023 while (!__comp(--__j, __i))
3052 template<
typename _B
idirectionalIterator>
3054 prev_permutation(_BidirectionalIterator __first,
3055 _BidirectionalIterator __last)
3058 __glibcxx_function_requires(_BidirectionalIteratorConcept<
3059 _BidirectionalIterator>)
3060 __glibcxx_function_requires(_LessThanComparableConcept<
3061 typename iterator_traits<_BidirectionalIterator>::value_type>)
3062 __glibcxx_requires_valid_range(__first, __last);
3063 __glibcxx_requires_irreflexive(__first, __last);
3065 return std::__prev_permutation(__first, __last,
3066 __gnu_cxx::__ops::__iter_less_iter());
3084 template<
typename _B
idirectionalIterator,
typename _Compare>
3086 prev_permutation(_BidirectionalIterator __first,
3087 _BidirectionalIterator __last, _Compare __comp)
3090 __glibcxx_function_requires(_BidirectionalIteratorConcept<
3091 _BidirectionalIterator>)
3092 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3093 typename iterator_traits<_BidirectionalIterator>::value_type,
3094 typename iterator_traits<_BidirectionalIterator>::value_type>)
3095 __glibcxx_requires_valid_range(__first, __last);
3096 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
3098 return std::__prev_permutation(__first, __last,
3099 __gnu_cxx::__ops::__iter_comp_iter(__comp));
3105 template<
typename _InputIterator,
typename _OutputIterator,
3106 typename _Predicate,
typename _Tp>
3108 __replace_copy_if(_InputIterator __first, _InputIterator __last,
3109 _OutputIterator __result,
3110 _Predicate __pred,
const _Tp& __new_value)
3112 for (; __first != __last; ++__first, (void)++__result)
3113 if (__pred(__first))
3114 *__result = __new_value;
3116 *__result = *__first;
3134 template<
typename _InputIterator,
typename _OutputIterator,
typename _Tp>
3135 inline _OutputIterator
3136 replace_copy(_InputIterator __first, _InputIterator __last,
3137 _OutputIterator __result,
3138 const _Tp& __old_value,
const _Tp& __new_value)
3141 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3142 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
3143 typename iterator_traits<_InputIterator>::value_type>)
3144 __glibcxx_function_requires(_EqualOpConcept<
3145 typename iterator_traits<_InputIterator>::value_type, _Tp>)
3146 __glibcxx_requires_valid_range(__first, __last);
3148 return std::__replace_copy_if(__first, __last, __result,
3149 __gnu_cxx::__ops::__iter_equals_val(__old_value),
3168 template<
typename _InputIterator,
typename _OutputIterator,
3169 typename _Predicate,
typename _Tp>
3170 inline _OutputIterator
3171 replace_copy_if(_InputIterator __first, _InputIterator __last,
3172 _OutputIterator __result,
3173 _Predicate __pred,
const _Tp& __new_value)
3176 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3177 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
3178 typename iterator_traits<_InputIterator>::value_type>)
3179 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
3180 typename iterator_traits<_InputIterator>::value_type>)
3181 __glibcxx_requires_valid_range(__first, __last);
3183 return std::__replace_copy_if(__first, __last, __result,
3184 __gnu_cxx::__ops::__pred_iter(__pred),
3188 template<
typename _InputIterator,
typename _Predicate>
3189 typename iterator_traits<_InputIterator>::difference_type
3190 __count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
3192 typename iterator_traits<_InputIterator>::difference_type __n = 0;
3193 for (; __first != __last; ++__first)
3194 if (__pred(__first))
3199 #if __cplusplus >= 201103L 3207 template<
typename _ForwardIterator>
3209 is_sorted(_ForwardIterator __first, _ForwardIterator __last)
3221 template<
typename _ForwardIterator,
typename _Compare>
3223 is_sorted(_ForwardIterator __first, _ForwardIterator __last,
3227 template<
typename _ForwardIterator,
typename _Compare>
3229 __is_sorted_until(_ForwardIterator __first, _ForwardIterator __last,
3232 if (__first == __last)
3235 _ForwardIterator __next = __first;
3236 for (++__next; __next != __last; __first = __next, (void)++__next)
3237 if (__comp(__next, __first))
3250 template<
typename _ForwardIterator>
3251 inline _ForwardIterator
3252 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last)
3255 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3256 __glibcxx_function_requires(_LessThanComparableConcept<
3257 typename iterator_traits<_ForwardIterator>::value_type>)
3258 __glibcxx_requires_valid_range(__first, __last);
3259 __glibcxx_requires_irreflexive(__first, __last);
3261 return std::__is_sorted_until(__first, __last,
3262 __gnu_cxx::__ops::__iter_less_iter());
3274 template<
typename _ForwardIterator,
typename _Compare>
3275 inline _ForwardIterator
3276 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last,
3280 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3281 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3282 typename iterator_traits<_ForwardIterator>::value_type,
3283 typename iterator_traits<_ForwardIterator>::value_type>)
3284 __glibcxx_requires_valid_range(__first, __last);
3285 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
3287 return std::__is_sorted_until(__first, __last,
3288 __gnu_cxx::__ops::__iter_comp_iter(__comp));
3299 template<
typename _Tp>
3300 _GLIBCXX14_CONSTEXPR
3305 __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
3307 return __b < __a ? pair<const _Tp&, const _Tp&>(__b, __a)
3320 template<
typename _Tp,
typename _Compare>
3321 _GLIBCXX14_CONSTEXPR
3323 minmax(
const _Tp& __a,
const _Tp& __b, _Compare __comp)
3329 template<
typename _ForwardIterator,
typename _Compare>
3330 _GLIBCXX14_CONSTEXPR
3332 __minmax_element(_ForwardIterator __first, _ForwardIterator __last,
3335 _ForwardIterator __next = __first;
3336 if (__first == __last
3337 || ++__next == __last)
3340 _ForwardIterator __min{}, __max{};
3341 if (__comp(__next, __first))
3355 while (__first != __last)
3358 if (++__next == __last)
3360 if (__comp(__first, __min))
3362 else if (!__comp(__first, __max))
3367 if (__comp(__next, __first))
3369 if (__comp(__next, __min))
3371 if (!__comp(__first, __max))
3376 if (__comp(__first, __min))
3378 if (!__comp(__next, __max))
3400 template<
typename _ForwardIterator>
3401 _GLIBCXX14_CONSTEXPR
3403 minmax_element(_ForwardIterator __first, _ForwardIterator __last)
3406 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3407 __glibcxx_function_requires(_LessThanComparableConcept<
3408 typename iterator_traits<_ForwardIterator>::value_type>)
3409 __glibcxx_requires_valid_range(__first, __last);
3410 __glibcxx_requires_irreflexive(__first, __last);
3412 return std::__minmax_element(__first, __last,
3413 __gnu_cxx::__ops::__iter_less_iter());
3428 template<
typename _ForwardIterator,
typename _Compare>
3429 _GLIBCXX14_CONSTEXPR
3431 minmax_element(_ForwardIterator __first, _ForwardIterator __last,
3435 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3436 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3437 typename iterator_traits<_ForwardIterator>::value_type,
3438 typename iterator_traits<_ForwardIterator>::value_type>)
3439 __glibcxx_requires_valid_range(__first, __last);
3440 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
3442 return std::__minmax_element(__first, __last,
3443 __gnu_cxx::__ops::__iter_comp_iter(__comp));
3447 template<
typename _Tp>
3448 _GLIBCXX14_CONSTEXPR
3453 template<
typename _Tp,
typename _Compare>
3454 _GLIBCXX14_CONSTEXPR
3459 template<
typename _Tp>
3460 _GLIBCXX14_CONSTEXPR
3465 template<
typename _Tp,
typename _Compare>
3466 _GLIBCXX14_CONSTEXPR
3471 template<
typename _Tp>
3472 _GLIBCXX14_CONSTEXPR
3481 template<
typename _Tp,
typename _Compare>
3482 _GLIBCXX14_CONSTEXPR
3491 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
3492 typename _BinaryPredicate>
3494 __is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3495 _ForwardIterator2 __first2, _BinaryPredicate __pred)
3499 for (; __first1 != __last1; ++__first1, (void)++__first2)
3500 if (!__pred(__first1, __first2))
3503 if (__first1 == __last1)
3508 _ForwardIterator2 __last2 = __first2;
3510 for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
3513 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)))
3517 = std::__count_if(__first2, __last2,
3518 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan));
3519 if (0 == __matches ||
3520 std::__count_if(__scan, __last1,
3521 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan))
3540 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
3542 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3543 _ForwardIterator2 __first2)
3546 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
3547 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
3548 __glibcxx_function_requires(_EqualOpConcept<
3549 typename iterator_traits<_ForwardIterator1>::value_type,
3550 typename iterator_traits<_ForwardIterator2>::value_type>)
3551 __glibcxx_requires_valid_range(__first1, __last1);
3553 return std::__is_permutation(__first1, __last1, __first2,
3554 __gnu_cxx::__ops::__iter_equal_to_iter());
3571 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
3572 typename _BinaryPredicate>
3574 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3575 _ForwardIterator2 __first2, _BinaryPredicate __pred)
3578 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
3579 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
3580 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
3581 typename iterator_traits<_ForwardIterator1>::value_type,
3582 typename iterator_traits<_ForwardIterator2>::value_type>)
3583 __glibcxx_requires_valid_range(__first1, __last1);
3585 return std::__is_permutation(__first1, __last1, __first2,
3586 __gnu_cxx::__ops::__iter_comp_iter(__pred));
3589 #if __cplusplus > 201103L 3590 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
3591 typename _BinaryPredicate>
3593 __is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3594 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
3595 _BinaryPredicate __pred)
3598 =
typename iterator_traits<_ForwardIterator1>::iterator_category;
3600 =
typename iterator_traits<_ForwardIterator2>::iterator_category;
3601 using _It1_is_RA = is_same<_Cat1, random_access_iterator_tag>;
3602 using _It2_is_RA = is_same<_Cat2, random_access_iterator_tag>;
3603 constexpr
bool __ra_iters = _It1_is_RA() && _It2_is_RA();
3614 for (; __first1 != __last1 && __first2 != __last2;
3615 ++__first1, (void)++__first2)
3616 if (!__pred(__first1, __first2))
3621 if (__first1 == __last1)
3628 if (__d1 == 0 && __d2 == 0)
3634 for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
3637 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)))
3640 auto __matches = std::__count_if(__first2, __last2,
3641 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan));
3643 || std::__count_if(__scan, __last1,
3644 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan))
3664 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
3666 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3667 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
3669 __glibcxx_requires_valid_range(__first1, __last1);
3670 __glibcxx_requires_valid_range(__first2, __last2);
3673 std::__is_permutation(__first1, __last1, __first2, __last2,
3674 __gnu_cxx::__ops::__iter_equal_to_iter());
3691 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
3692 typename _BinaryPredicate>
3694 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3695 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
3696 _BinaryPredicate __pred)
3698 __glibcxx_requires_valid_range(__first1, __last1);
3699 __glibcxx_requires_valid_range(__first2, __last2);
3701 return std::__is_permutation(__first1, __last1, __first2, __last2,
3702 __gnu_cxx::__ops::__iter_comp_iter(__pred));
3705 #if __cplusplus > 201402L 3707 #define __cpp_lib_clamp 201603 3717 template<
typename _Tp>
3718 constexpr
const _Tp&
3719 clamp(
const _Tp& __val,
const _Tp& __lo,
const _Tp& __hi)
3721 __glibcxx_assert(!(__hi < __lo));
3722 return (__val < __lo) ? __lo : (__hi < __val) ? __hi : __val;
3735 template<
typename _Tp,
typename _Compare>
3736 constexpr
const _Tp&
3737 clamp(
const _Tp& __val,
const _Tp& __lo,
const _Tp& __hi, _Compare __comp)
3739 __glibcxx_assert(!__comp(__hi, __lo));
3740 return __comp(__val, __lo) ? __lo : __comp(__hi, __val) ? __hi : __val;
3745 #ifdef _GLIBCXX_USE_C99_STDINT_TR1 3767 template<
typename _IntType,
typename _UniformRandomBitGenerator>
3770 _UniformRandomBitGenerator&& __g)
3789 template<
typename _RandomAccessIterator,
3790 typename _UniformRandomNumberGenerator>
3792 shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
3793 _UniformRandomNumberGenerator&& __g)
3796 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
3797 _RandomAccessIterator>)
3798 __glibcxx_requires_valid_range(__first, __last);
3800 if (__first == __last)
3803 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
3806 typedef typename std::make_unsigned<_DistanceType>::type __ud_type;
3808 typedef typename __distr_type::param_type __p_type;
3810 typedef typename remove_reference<_UniformRandomNumberGenerator>::type
3812 typedef typename common_type<typename _Gen::result_type, __ud_type>::type
3815 const __uc_type __urngrange = __g.
max() - __g.min();
3816 const __uc_type __urange = __uc_type(__last - __first);
3818 if (__urngrange / __urange >= __urange)
3821 _RandomAccessIterator __i = __first + 1;
3827 if ((__urange % 2) == 0)
3829 __distr_type __d{0, 1};
3837 while (__i != __last)
3839 const __uc_type __swap_range = __uc_type(__i - __first) + 1;
3853 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
3854 std::iter_swap(__i, __first + __d(__g, __p_type(0, __i - __first)));
3860 _GLIBCXX_END_NAMESPACE_VERSION
3862 _GLIBCXX_BEGIN_NAMESPACE_ALGO
3876 template<
typename _InputIterator,
typename _Function>
3878 for_each(_InputIterator __first, _InputIterator __last, _Function __f)
3881 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3882 __glibcxx_requires_valid_range(__first, __last);
3883 for (; __first != __last; ++__first)
3897 template<
typename _InputIterator,
typename _Tp>
3898 inline _InputIterator
3899 find(_InputIterator __first, _InputIterator __last,
3903 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3904 __glibcxx_function_requires(_EqualOpConcept<
3905 typename iterator_traits<_InputIterator>::value_type, _Tp>)
3906 __glibcxx_requires_valid_range(__first, __last);
3908 __gnu_cxx::__ops::__iter_equals_val(__val));
3921 template<
typename _InputIterator,
typename _Predicate>
3922 inline _InputIterator
3923 find_if(_InputIterator __first, _InputIterator __last,
3927 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3928 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
3929 typename iterator_traits<_InputIterator>::value_type>)
3930 __glibcxx_requires_valid_range(__first, __last);
3933 __gnu_cxx::__ops::__pred_iter(__pred));
3952 template<
typename _InputIterator,
typename _ForwardIterator>
3954 find_first_of(_InputIterator __first1, _InputIterator __last1,
3955 _ForwardIterator __first2, _ForwardIterator __last2)
3958 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3959 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3960 __glibcxx_function_requires(_EqualOpConcept<
3961 typename iterator_traits<_InputIterator>::value_type,
3962 typename iterator_traits<_ForwardIterator>::value_type>)
3963 __glibcxx_requires_valid_range(__first1, __last1);
3964 __glibcxx_requires_valid_range(__first2, __last2);
3966 for (; __first1 != __last1; ++__first1)
3967 for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
3968 if (*__first1 == *__iter)
3992 template<
typename _InputIterator,
typename _ForwardIterator,
3993 typename _BinaryPredicate>
3995 find_first_of(_InputIterator __first1, _InputIterator __last1,
3996 _ForwardIterator __first2, _ForwardIterator __last2,
3997 _BinaryPredicate __comp)
4000 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4001 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4002 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4003 typename iterator_traits<_InputIterator>::value_type,
4004 typename iterator_traits<_ForwardIterator>::value_type>)
4005 __glibcxx_requires_valid_range(__first1, __last1);
4006 __glibcxx_requires_valid_range(__first2, __last2);
4008 for (; __first1 != __last1; ++__first1)
4009 for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
4010 if (__comp(*__first1, *__iter))
4024 template<
typename _ForwardIterator>
4025 inline _ForwardIterator
4026 adjacent_find(_ForwardIterator __first, _ForwardIterator __last)
4029 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4030 __glibcxx_function_requires(_EqualityComparableConcept<
4031 typename iterator_traits<_ForwardIterator>::value_type>)
4032 __glibcxx_requires_valid_range(__first, __last);
4034 return std::__adjacent_find(__first, __last,
4035 __gnu_cxx::__ops::__iter_equal_to_iter());
4049 template<
typename _ForwardIterator,
typename _BinaryPredicate>
4050 inline _ForwardIterator
4051 adjacent_find(_ForwardIterator __first, _ForwardIterator __last,
4052 _BinaryPredicate __binary_pred)
4055 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4056 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4057 typename iterator_traits<_ForwardIterator>::value_type,
4058 typename iterator_traits<_ForwardIterator>::value_type>)
4059 __glibcxx_requires_valid_range(__first, __last);
4061 return std::__adjacent_find(__first, __last,
4062 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred));
4074 template<
typename _InputIterator,
typename _Tp>
4075 inline typename iterator_traits<_InputIterator>::difference_type
4076 count(_InputIterator __first, _InputIterator __last,
const _Tp& __value)
4079 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4080 __glibcxx_function_requires(_EqualOpConcept<
4081 typename iterator_traits<_InputIterator>::value_type, _Tp>)
4082 __glibcxx_requires_valid_range(__first, __last);
4084 return std::__count_if(__first, __last,
4085 __gnu_cxx::__ops::__iter_equals_val(__value));
4097 template<
typename _InputIterator,
typename _Predicate>
4098 inline typename iterator_traits<_InputIterator>::difference_type
4099 count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
4102 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4103 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4104 typename iterator_traits<_InputIterator>::value_type>)
4105 __glibcxx_requires_valid_range(__first, __last);
4107 return std::__count_if(__first, __last,
4108 __gnu_cxx::__ops::__pred_iter(__pred));
4137 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
4138 inline _ForwardIterator1
4139 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
4140 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
4143 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
4144 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
4145 __glibcxx_function_requires(_EqualOpConcept<
4146 typename iterator_traits<_ForwardIterator1>::value_type,
4147 typename iterator_traits<_ForwardIterator2>::value_type>)
4148 __glibcxx_requires_valid_range(__first1, __last1);
4149 __glibcxx_requires_valid_range(__first2, __last2);
4151 return std::__search(__first1, __last1, __first2, __last2,
4152 __gnu_cxx::__ops::__iter_equal_to_iter());
4176 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
4177 typename _BinaryPredicate>
4178 inline _ForwardIterator1
4179 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
4180 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
4181 _BinaryPredicate __predicate)
4184 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
4185 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
4186 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4187 typename iterator_traits<_ForwardIterator1>::value_type,
4188 typename iterator_traits<_ForwardIterator2>::value_type>)
4189 __glibcxx_requires_valid_range(__first1, __last1);
4190 __glibcxx_requires_valid_range(__first2, __last2);
4192 return std::__search(__first1, __last1, __first2, __last2,
4193 __gnu_cxx::__ops::__iter_comp_iter(__predicate));
4211 template<
typename _ForwardIterator,
typename _Integer,
typename _Tp>
4212 inline _ForwardIterator
4213 search_n(_ForwardIterator __first, _ForwardIterator __last,
4214 _Integer __count,
const _Tp& __val)
4217 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4218 __glibcxx_function_requires(_EqualOpConcept<
4219 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
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 inline _ForwardIterator
4247 search_n(_ForwardIterator __first, _ForwardIterator __last,
4248 _Integer __count,
const _Tp& __val,
4249 _BinaryPredicate __binary_pred)
4252 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4253 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4254 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
4255 __glibcxx_requires_valid_range(__first, __last);
4257 return std::__search_n(__first, __last, __count,
4258 __gnu_cxx::__ops::__iter_comp_val(__binary_pred, __val));
4261 #if __cplusplus > 201402L 4269 template<
typename _ForwardIterator,
typename _Searcher>
4270 inline _ForwardIterator
4271 search(_ForwardIterator __first, _ForwardIterator __last,
4272 const _Searcher& __searcher)
4273 {
return __searcher(__first, __last).first; }
4292 template<
typename _InputIterator,
typename _OutputIterator,
4293 typename _UnaryOperation>
4295 transform(_InputIterator __first, _InputIterator __last,
4296 _OutputIterator __result, _UnaryOperation __unary_op)
4299 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4300 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4302 __typeof__(__unary_op(*__first))>)
4303 __glibcxx_requires_valid_range(__first, __last);
4305 for (; __first != __last; ++__first, (void)++__result)
4306 *__result = __unary_op(*__first);
4329 template<
typename _InputIterator1,
typename _InputIterator2,
4330 typename _OutputIterator,
typename _BinaryOperation>
4332 transform(_InputIterator1 __first1, _InputIterator1 __last1,
4333 _InputIterator2 __first2, _OutputIterator __result,
4334 _BinaryOperation __binary_op)
4337 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4338 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4339 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4341 __typeof__(__binary_op(*__first1,*__first2))>)
4342 __glibcxx_requires_valid_range(__first1, __last1);
4344 for (; __first1 != __last1; ++__first1, (void)++__first2, ++__result)
4345 *__result = __binary_op(*__first1, *__first2);
4362 template<
typename _ForwardIterator,
typename _Tp>
4364 replace(_ForwardIterator __first, _ForwardIterator __last,
4365 const _Tp& __old_value,
const _Tp& __new_value)
4368 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4370 __glibcxx_function_requires(_EqualOpConcept<
4371 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
4372 __glibcxx_function_requires(_ConvertibleConcept<_Tp,
4373 typename iterator_traits<_ForwardIterator>::value_type>)
4374 __glibcxx_requires_valid_range(__first, __last);
4376 for (; __first != __last; ++__first)
4377 if (*__first == __old_value)
4378 *__first = __new_value;
4394 template<
typename _ForwardIterator,
typename _Predicate,
typename _Tp>
4396 replace_if(_ForwardIterator __first, _ForwardIterator __last,
4397 _Predicate __pred,
const _Tp& __new_value)
4400 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4402 __glibcxx_function_requires(_ConvertibleConcept<_Tp,
4403 typename iterator_traits<_ForwardIterator>::value_type>)
4404 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4405 typename iterator_traits<_ForwardIterator>::value_type>)
4406 __glibcxx_requires_valid_range(__first, __last);
4408 for (; __first != __last; ++__first)
4409 if (__pred(*__first))
4410 *__first = __new_value;
4426 template<
typename _ForwardIterator,
typename _Generator>
4428 generate(_ForwardIterator __first, _ForwardIterator __last,
4432 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4433 __glibcxx_function_requires(_GeneratorConcept<_Generator,
4434 typename iterator_traits<_ForwardIterator>::value_type>)
4435 __glibcxx_requires_valid_range(__first, __last);
4437 for (; __first != __last; ++__first)
4457 template<
typename _OutputIterator,
typename _Size,
typename _Generator>
4459 generate_n(_OutputIterator __first, _Size __n, _Generator __gen)
4462 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4464 __typeof__(__gen())>)
4466 for (__decltype(__n + 0) __niter = __n;
4467 __niter > 0; --__niter, ++__first)
4493 template<
typename _InputIterator,
typename _OutputIterator>
4494 inline _OutputIterator
4495 unique_copy(_InputIterator __first, _InputIterator __last,
4496 _OutputIterator __result)
4499 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4500 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4501 typename iterator_traits<_InputIterator>::value_type>)
4502 __glibcxx_function_requires(_EqualityComparableConcept<
4503 typename iterator_traits<_InputIterator>::value_type>)
4504 __glibcxx_requires_valid_range(__first, __last);
4506 if (__first == __last)
4509 __gnu_cxx::__ops::__iter_equal_to_iter(),
4533 template<
typename _InputIterator,
typename _OutputIterator,
4534 typename _BinaryPredicate>
4535 inline _OutputIterator
4536 unique_copy(_InputIterator __first, _InputIterator __last,
4537 _OutputIterator __result,
4538 _BinaryPredicate __binary_pred)
4541 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4542 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4543 typename iterator_traits<_InputIterator>::value_type>)
4544 __glibcxx_requires_valid_range(__first, __last);
4546 if (__first == __last)
4549 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred),
4566 template<
typename _RandomAccessIterator>
4568 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
4571 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4572 _RandomAccessIterator>)
4573 __glibcxx_requires_valid_range(__first, __last);
4575 if (__first != __last)
4576 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
4579 _RandomAccessIterator __j = __first
4580 + std::rand() % ((__i - __first) + 1);
4601 template<
typename _RandomAccessIterator,
typename _RandomNumberGenerator>
4603 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
4604 #
if __cplusplus >= 201103L
4605 _RandomNumberGenerator&& __rand)
4607 _RandomNumberGenerator& __rand)
4611 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4612 _RandomAccessIterator>)
4613 __glibcxx_requires_valid_range(__first, __last);
4615 if (__first == __last)
4617 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
4619 _RandomAccessIterator __j = __first + __rand((__i - __first) + 1);
4641 template<
typename _ForwardIterator,
typename _Predicate>
4642 inline _ForwardIterator
4643 partition(_ForwardIterator __first, _ForwardIterator __last,
4647 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4649 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4650 typename iterator_traits<_ForwardIterator>::value_type>)
4651 __glibcxx_requires_valid_range(__first, __last);
4674 template<
typename _RandomAccessIterator>
4676 partial_sort(_RandomAccessIterator __first,
4677 _RandomAccessIterator __middle,
4678 _RandomAccessIterator __last)
4681 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4682 _RandomAccessIterator>)
4683 __glibcxx_function_requires(_LessThanComparableConcept<
4684 typename iterator_traits<_RandomAccessIterator>::value_type>)
4685 __glibcxx_requires_valid_range(__first, __middle);
4686 __glibcxx_requires_valid_range(__middle, __last);
4687 __glibcxx_requires_irreflexive(__first, __last);
4689 std::__partial_sort(__first, __middle, __last,
4690 __gnu_cxx::__ops::__iter_less_iter());
4712 template<
typename _RandomAccessIterator,
typename _Compare>
4714 partial_sort(_RandomAccessIterator __first,
4715 _RandomAccessIterator __middle,
4716 _RandomAccessIterator __last,
4720 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4721 _RandomAccessIterator>)
4722 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4723 typename iterator_traits<_RandomAccessIterator>::value_type,
4724 typename iterator_traits<_RandomAccessIterator>::value_type>)
4725 __glibcxx_requires_valid_range(__first, __middle);
4726 __glibcxx_requires_valid_range(__middle, __last);
4727 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
4729 std::__partial_sort(__first, __middle, __last,
4730 __gnu_cxx::__ops::__iter_comp_iter(__comp));
4748 template<
typename _RandomAccessIterator>
4750 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
4751 _RandomAccessIterator __last)
4754 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4755 _RandomAccessIterator>)
4756 __glibcxx_function_requires(_LessThanComparableConcept<
4757 typename iterator_traits<_RandomAccessIterator>::value_type>)
4758 __glibcxx_requires_valid_range(__first, __nth);
4759 __glibcxx_requires_valid_range(__nth, __last);
4760 __glibcxx_requires_irreflexive(__first, __last);
4762 if (__first == __last || __nth == __last)
4765 std::__introselect(__first, __nth, __last,
4767 __gnu_cxx::__ops::__iter_less_iter());
4787 template<
typename _RandomAccessIterator,
typename _Compare>
4789 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
4790 _RandomAccessIterator __last, _Compare __comp)
4793 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4794 _RandomAccessIterator>)
4795 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4796 typename iterator_traits<_RandomAccessIterator>::value_type,
4797 typename iterator_traits<_RandomAccessIterator>::value_type>)
4798 __glibcxx_requires_valid_range(__first, __nth);
4799 __glibcxx_requires_valid_range(__nth, __last);
4800 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
4802 if (__first == __last || __nth == __last)
4805 std::__introselect(__first, __nth, __last,
4807 __gnu_cxx::__ops::__iter_comp_iter(__comp));
4824 template<
typename _RandomAccessIterator>
4826 sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
4829 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4830 _RandomAccessIterator>)
4831 __glibcxx_function_requires(_LessThanComparableConcept<
4832 typename iterator_traits<_RandomAccessIterator>::value_type>)
4833 __glibcxx_requires_valid_range(__first, __last);
4834 __glibcxx_requires_irreflexive(__first, __last);
4836 std::__sort(__first, __last, __gnu_cxx::__ops::__iter_less_iter());
4854 template<
typename _RandomAccessIterator,
typename _Compare>
4856 sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
4860 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4861 _RandomAccessIterator>)
4862 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4863 typename iterator_traits<_RandomAccessIterator>::value_type,
4864 typename iterator_traits<_RandomAccessIterator>::value_type>)
4865 __glibcxx_requires_valid_range(__first, __last);
4866 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
4868 std::__sort(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
4871 template<
typename _InputIterator1,
typename _InputIterator2,
4872 typename _OutputIterator,
typename _Compare>
4874 __merge(_InputIterator1 __first1, _InputIterator1 __last1,
4875 _InputIterator2 __first2, _InputIterator2 __last2,
4876 _OutputIterator __result, _Compare __comp)
4878 while (__first1 != __last1 && __first2 != __last2)
4880 if (__comp(__first2, __first1))
4882 *__result = *__first2;
4887 *__result = *__first1;
4892 return std::copy(__first2, __last2,
4893 std::copy(__first1, __last1, __result));
4915 template<
typename _InputIterator1,
typename _InputIterator2,
4916 typename _OutputIterator>
4917 inline _OutputIterator
4918 merge(_InputIterator1 __first1, _InputIterator1 __last1,
4919 _InputIterator2 __first2, _InputIterator2 __last2,
4920 _OutputIterator __result)
4923 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4924 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4925 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4926 typename iterator_traits<_InputIterator1>::value_type>)
4927 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4928 typename iterator_traits<_InputIterator2>::value_type>)
4929 __glibcxx_function_requires(_LessThanOpConcept<
4930 typename iterator_traits<_InputIterator2>::value_type,
4931 typename iterator_traits<_InputIterator1>::value_type>)
4932 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
4933 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
4934 __glibcxx_requires_irreflexive2(__first1, __last1);
4935 __glibcxx_requires_irreflexive2(__first2, __last2);
4937 return _GLIBCXX_STD_A::__merge(__first1, __last1,
4938 __first2, __last2, __result,
4939 __gnu_cxx::__ops::__iter_less_iter());
4965 template<
typename _InputIterator1,
typename _InputIterator2,
4966 typename _OutputIterator,
typename _Compare>
4967 inline _OutputIterator
4968 merge(_InputIterator1 __first1, _InputIterator1 __last1,
4969 _InputIterator2 __first2, _InputIterator2 __last2,
4970 _OutputIterator __result, _Compare __comp)
4973 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4974 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4975 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4976 typename iterator_traits<_InputIterator1>::value_type>)
4977 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4978 typename iterator_traits<_InputIterator2>::value_type>)
4979 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4980 typename iterator_traits<_InputIterator2>::value_type,
4981 typename iterator_traits<_InputIterator1>::value_type>)
4982 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
4983 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
4984 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
4985 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
4987 return _GLIBCXX_STD_A::__merge(__first1, __last1,
4988 __first2, __last2, __result,
4989 __gnu_cxx::__ops::__iter_comp_iter(__comp));
4992 template<
typename _RandomAccessIterator,
typename _Compare>
4994 __stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
4997 typedef typename iterator_traits<_RandomAccessIterator>::value_type
4999 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
5003 _TmpBuf __buf(__first, __last);
5005 if (__buf.begin() == 0)
5008 std::__stable_sort_adaptive(__first, __last, __buf.begin(),
5009 _DistanceType(__buf.size()), __comp);
5029 template<
typename _RandomAccessIterator>
5031 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
5034 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5035 _RandomAccessIterator>)
5036 __glibcxx_function_requires(_LessThanComparableConcept<
5037 typename iterator_traits<_RandomAccessIterator>::value_type>)
5038 __glibcxx_requires_valid_range(__first, __last);
5039 __glibcxx_requires_irreflexive(__first, __last);
5041 _GLIBCXX_STD_A::__stable_sort(__first, __last,
5042 __gnu_cxx::__ops::__iter_less_iter());
5063 template<
typename _RandomAccessIterator,
typename _Compare>
5065 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
5069 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5070 _RandomAccessIterator>)
5071 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5072 typename iterator_traits<_RandomAccessIterator>::value_type,
5073 typename iterator_traits<_RandomAccessIterator>::value_type>)
5074 __glibcxx_requires_valid_range(__first, __last);
5075 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
5077 _GLIBCXX_STD_A::__stable_sort(__first, __last,
5078 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5081 template<
typename _InputIterator1,
typename _InputIterator2,
5082 typename _OutputIterator,
5085 __set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5086 _InputIterator2 __first2, _InputIterator2 __last2,
5087 _OutputIterator __result, _Compare __comp)
5089 while (__first1 != __last1 && __first2 != __last2)
5091 if (__comp(__first1, __first2))
5093 *__result = *__first1;
5096 else if (__comp(__first2, __first1))
5098 *__result = *__first2;
5103 *__result = *__first1;
5109 return std::copy(__first2, __last2,
5110 std::copy(__first1, __last1, __result));
5131 template<
typename _InputIterator1,
typename _InputIterator2,
5132 typename _OutputIterator>
5133 inline _OutputIterator
5134 set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5135 _InputIterator2 __first2, _InputIterator2 __last2,
5136 _OutputIterator __result)
5139 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5140 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5141 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5142 typename iterator_traits<_InputIterator1>::value_type>)
5143 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5144 typename iterator_traits<_InputIterator2>::value_type>)
5145 __glibcxx_function_requires(_LessThanOpConcept<
5146 typename iterator_traits<_InputIterator1>::value_type,
5147 typename iterator_traits<_InputIterator2>::value_type>)
5148 __glibcxx_function_requires(_LessThanOpConcept<
5149 typename iterator_traits<_InputIterator2>::value_type,
5150 typename iterator_traits<_InputIterator1>::value_type>)
5151 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5152 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5153 __glibcxx_requires_irreflexive2(__first1, __last1);
5154 __glibcxx_requires_irreflexive2(__first2, __last2);
5156 return _GLIBCXX_STD_A::__set_union(__first1, __last1,
5157 __first2, __last2, __result,
5158 __gnu_cxx::__ops::__iter_less_iter());
5180 template<
typename _InputIterator1,
typename _InputIterator2,
5181 typename _OutputIterator,
typename _Compare>
5182 inline _OutputIterator
5183 set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5184 _InputIterator2 __first2, _InputIterator2 __last2,
5185 _OutputIterator __result, _Compare __comp)
5188 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5189 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5190 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5191 typename iterator_traits<_InputIterator1>::value_type>)
5192 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5193 typename iterator_traits<_InputIterator2>::value_type>)
5194 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5195 typename iterator_traits<_InputIterator1>::value_type,
5196 typename iterator_traits<_InputIterator2>::value_type>)
5197 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5198 typename iterator_traits<_InputIterator2>::value_type,
5199 typename iterator_traits<_InputIterator1>::value_type>)
5200 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5201 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5202 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5203 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5205 return _GLIBCXX_STD_A::__set_union(__first1, __last1,
5206 __first2, __last2, __result,
5207 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5210 template<
typename _InputIterator1,
typename _InputIterator2,
5211 typename _OutputIterator,
5214 __set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5215 _InputIterator2 __first2, _InputIterator2 __last2,
5216 _OutputIterator __result, _Compare __comp)
5218 while (__first1 != __last1 && __first2 != __last2)
5219 if (__comp(__first1, __first2))
5221 else if (__comp(__first2, __first1))
5225 *__result = *__first1;
5250 template<
typename _InputIterator1,
typename _InputIterator2,
5251 typename _OutputIterator>
5252 inline _OutputIterator
5253 set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5254 _InputIterator2 __first2, _InputIterator2 __last2,
5255 _OutputIterator __result)
5258 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5259 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5260 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5261 typename iterator_traits<_InputIterator1>::value_type>)
5262 __glibcxx_function_requires(_LessThanOpConcept<
5263 typename iterator_traits<_InputIterator1>::value_type,
5264 typename iterator_traits<_InputIterator2>::value_type>)
5265 __glibcxx_function_requires(_LessThanOpConcept<
5266 typename iterator_traits<_InputIterator2>::value_type,
5267 typename iterator_traits<_InputIterator1>::value_type>)
5268 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5269 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5270 __glibcxx_requires_irreflexive2(__first1, __last1);
5271 __glibcxx_requires_irreflexive2(__first2, __last2);
5273 return _GLIBCXX_STD_A::__set_intersection(__first1, __last1,
5274 __first2, __last2, __result,
5275 __gnu_cxx::__ops::__iter_less_iter());
5298 template<
typename _InputIterator1,
typename _InputIterator2,
5299 typename _OutputIterator,
typename _Compare>
5300 inline _OutputIterator
5301 set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5302 _InputIterator2 __first2, _InputIterator2 __last2,
5303 _OutputIterator __result, _Compare __comp)
5306 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5307 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5308 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5309 typename iterator_traits<_InputIterator1>::value_type>)
5310 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5311 typename iterator_traits<_InputIterator1>::value_type,
5312 typename iterator_traits<_InputIterator2>::value_type>)
5313 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5314 typename iterator_traits<_InputIterator2>::value_type,
5315 typename iterator_traits<_InputIterator1>::value_type>)
5316 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5317 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5318 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5319 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5321 return _GLIBCXX_STD_A::__set_intersection(__first1, __last1,
5322 __first2, __last2, __result,
5323 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5326 template<
typename _InputIterator1,
typename _InputIterator2,
5327 typename _OutputIterator,
5330 __set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5331 _InputIterator2 __first2, _InputIterator2 __last2,
5332 _OutputIterator __result, _Compare __comp)
5334 while (__first1 != __last1 && __first2 != __last2)
5335 if (__comp(__first1, __first2))
5337 *__result = *__first1;
5341 else if (__comp(__first2, __first1))
5348 return std::copy(__first1, __last1, __result);
5370 template<
typename _InputIterator1,
typename _InputIterator2,
5371 typename _OutputIterator>
5372 inline _OutputIterator
5373 set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5374 _InputIterator2 __first2, _InputIterator2 __last2,
5375 _OutputIterator __result)
5378 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5379 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5380 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5381 typename iterator_traits<_InputIterator1>::value_type>)
5382 __glibcxx_function_requires(_LessThanOpConcept<
5383 typename iterator_traits<_InputIterator1>::value_type,
5384 typename iterator_traits<_InputIterator2>::value_type>)
5385 __glibcxx_function_requires(_LessThanOpConcept<
5386 typename iterator_traits<_InputIterator2>::value_type,
5387 typename iterator_traits<_InputIterator1>::value_type>)
5388 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5389 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5390 __glibcxx_requires_irreflexive2(__first1, __last1);
5391 __glibcxx_requires_irreflexive2(__first2, __last2);
5393 return _GLIBCXX_STD_A::__set_difference(__first1, __last1,
5394 __first2, __last2, __result,
5395 __gnu_cxx::__ops::__iter_less_iter());
5420 template<
typename _InputIterator1,
typename _InputIterator2,
5421 typename _OutputIterator,
typename _Compare>
5422 inline _OutputIterator
5423 set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5424 _InputIterator2 __first2, _InputIterator2 __last2,
5425 _OutputIterator __result, _Compare __comp)
5428 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5429 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5430 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5431 typename iterator_traits<_InputIterator1>::value_type>)
5432 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5433 typename iterator_traits<_InputIterator1>::value_type,
5434 typename iterator_traits<_InputIterator2>::value_type>)
5435 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5436 typename iterator_traits<_InputIterator2>::value_type,
5437 typename iterator_traits<_InputIterator1>::value_type>)
5438 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5439 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5440 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5441 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5443 return _GLIBCXX_STD_A::__set_difference(__first1, __last1,
5444 __first2, __last2, __result,
5445 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5448 template<
typename _InputIterator1,
typename _InputIterator2,
5449 typename _OutputIterator,
5452 __set_symmetric_difference(_InputIterator1 __first1,
5453 _InputIterator1 __last1,
5454 _InputIterator2 __first2,
5455 _InputIterator2 __last2,
5456 _OutputIterator __result,
5459 while (__first1 != __last1 && __first2 != __last2)
5460 if (__comp(__first1, __first2))
5462 *__result = *__first1;
5466 else if (__comp(__first2, __first1))
5468 *__result = *__first2;
5477 return std::copy(__first2, __last2,
5478 std::copy(__first1, __last1, __result));
5498 template<
typename _InputIterator1,
typename _InputIterator2,
5499 typename _OutputIterator>
5500 inline _OutputIterator
5501 set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5502 _InputIterator2 __first2, _InputIterator2 __last2,
5503 _OutputIterator __result)
5506 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5507 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5508 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5509 typename iterator_traits<_InputIterator1>::value_type>)
5510 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5511 typename iterator_traits<_InputIterator2>::value_type>)
5512 __glibcxx_function_requires(_LessThanOpConcept<
5513 typename iterator_traits<_InputIterator1>::value_type,
5514 typename iterator_traits<_InputIterator2>::value_type>)
5515 __glibcxx_function_requires(_LessThanOpConcept<
5516 typename iterator_traits<_InputIterator2>::value_type,
5517 typename iterator_traits<_InputIterator1>::value_type>)
5518 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5519 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5520 __glibcxx_requires_irreflexive2(__first1, __last1);
5521 __glibcxx_requires_irreflexive2(__first2, __last2);
5523 return _GLIBCXX_STD_A::__set_symmetric_difference(__first1, __last1,
5524 __first2, __last2, __result,
5525 __gnu_cxx::__ops::__iter_less_iter());
5548 template<
typename _InputIterator1,
typename _InputIterator2,
5549 typename _OutputIterator,
typename _Compare>
5550 inline _OutputIterator
5551 set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5552 _InputIterator2 __first2, _InputIterator2 __last2,
5553 _OutputIterator __result,
5557 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5558 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5559 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5560 typename iterator_traits<_InputIterator1>::value_type>)
5561 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5562 typename iterator_traits<_InputIterator2>::value_type>)
5563 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5564 typename iterator_traits<_InputIterator1>::value_type,
5565 typename iterator_traits<_InputIterator2>::value_type>)
5566 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5567 typename iterator_traits<_InputIterator2>::value_type,
5568 typename iterator_traits<_InputIterator1>::value_type>)
5569 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5570 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5571 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5572 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5574 return _GLIBCXX_STD_A::__set_symmetric_difference(__first1, __last1,
5575 __first2, __last2, __result,
5576 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5579 template<
typename _ForwardIterator,
typename _Compare>
5580 _GLIBCXX14_CONSTEXPR
5582 __min_element(_ForwardIterator __first, _ForwardIterator __last,
5585 if (__first == __last)
5587 _ForwardIterator __result = __first;
5588 while (++__first != __last)
5589 if (__comp(__first, __result))
5601 template<
typename _ForwardIterator>
5602 _GLIBCXX14_CONSTEXPR
5604 inline min_element(_ForwardIterator __first, _ForwardIterator __last)
5607 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5608 __glibcxx_function_requires(_LessThanComparableConcept<
5609 typename iterator_traits<_ForwardIterator>::value_type>)
5610 __glibcxx_requires_valid_range(__first, __last);
5611 __glibcxx_requires_irreflexive(__first, __last);
5613 return _GLIBCXX_STD_A::__min_element(__first, __last,
5614 __gnu_cxx::__ops::__iter_less_iter());
5626 template<
typename _ForwardIterator,
typename _Compare>
5627 _GLIBCXX14_CONSTEXPR
5628 inline _ForwardIterator
5629 min_element(_ForwardIterator __first, _ForwardIterator __last,
5633 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5634 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5635 typename iterator_traits<_ForwardIterator>::value_type,
5636 typename iterator_traits<_ForwardIterator>::value_type>)
5637 __glibcxx_requires_valid_range(__first, __last);
5638 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
5640 return _GLIBCXX_STD_A::__min_element(__first, __last,
5641 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5644 template<
typename _ForwardIterator,
typename _Compare>
5645 _GLIBCXX14_CONSTEXPR
5647 __max_element(_ForwardIterator __first, _ForwardIterator __last,
5650 if (__first == __last)
return __first;
5651 _ForwardIterator __result = __first;
5652 while (++__first != __last)
5653 if (__comp(__result, __first))
5665 template<
typename _ForwardIterator>
5666 _GLIBCXX14_CONSTEXPR
5667 inline _ForwardIterator
5668 max_element(_ForwardIterator __first, _ForwardIterator __last)
5671 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5672 __glibcxx_function_requires(_LessThanComparableConcept<
5673 typename iterator_traits<_ForwardIterator>::value_type>)
5674 __glibcxx_requires_valid_range(__first, __last);
5675 __glibcxx_requires_irreflexive(__first, __last);
5677 return _GLIBCXX_STD_A::__max_element(__first, __last,
5678 __gnu_cxx::__ops::__iter_less_iter());
5690 template<
typename _ForwardIterator,
typename _Compare>
5691 _GLIBCXX14_CONSTEXPR
5692 inline _ForwardIterator
5693 max_element(_ForwardIterator __first, _ForwardIterator __last,
5697 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5698 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5699 typename iterator_traits<_ForwardIterator>::value_type,
5700 typename iterator_traits<_ForwardIterator>::value_type>)
5701 __glibcxx_requires_valid_range(__first, __last);
5702 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
5704 return _GLIBCXX_STD_A::__max_element(__first, __last,
5705 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5708 #if __cplusplus >= 201402L 5710 template<
typename _InputIterator,
typename _RandomAccessIterator,
5711 typename _Size,
typename _UniformRandomBitGenerator>
5712 _RandomAccessIterator
5715 _Size __n, _UniformRandomBitGenerator&& __g)
5718 using __param_type =
typename __distrib_type::param_type;
5719 __distrib_type __d{};
5720 _Size __sample_sz = 0;
5721 while (__first != __last && __sample_sz != __n)
5723 __out[__sample_sz++] = *__first;
5726 for (
auto __pop_sz = __sample_sz; __first != __last;
5727 ++__first, (void) ++__pop_sz)
5729 const auto __k = __d(__g, __param_type{0, __pop_sz});
5731 __out[__k] = *__first;
5733 return __out + __sample_sz;
5737 template<
typename _ForwardIterator,
typename _OutputIterator,
typename _Cat,
5738 typename _Size,
typename _UniformRandomBitGenerator>
5740 __sample(_ForwardIterator __first, _ForwardIterator __last,
5742 _OutputIterator __out, _Cat,
5743 _Size __n, _UniformRandomBitGenerator&& __g)
5746 using __param_type =
typename __distrib_type::param_type;
5747 using _USize = make_unsigned_t<_Size>;
5748 using _Gen = remove_reference_t<_UniformRandomBitGenerator>;
5749 using __uc_type = common_type_t<typename _Gen::result_type, _USize>;
5751 __distrib_type __d{};
5753 __n =
std::min(__n, __unsampled_sz);
5758 const __uc_type __urngrange = __g.max() - __g.min();
5759 if (__urngrange / __uc_type(__unsampled_sz) >= __uc_type(__unsampled_sz))
5763 while (__n != 0 && __unsampled_sz >= 2)
5769 if (__p.
first < __n)
5771 *__out++ = *__first;
5777 if (__n == 0)
break;
5782 *__out++ = *__first;
5792 for (; __n != 0; ++__first)
5793 if (__d(__g, __param_type{0, --__unsampled_sz}) < __n)
5795 *__out++ = *__first;
5801 #if __cplusplus > 201402L 5802 #define __cpp_lib_sample 201603 5804 template<
typename _PopulationIterator,
typename _SampleIterator,
5805 typename _Distance,
typename _UniformRandomBitGenerator>
5807 sample(_PopulationIterator __first, _PopulationIterator __last,
5808 _SampleIterator __out, _Distance __n,
5809 _UniformRandomBitGenerator&& __g)
5811 using __pop_cat =
typename 5812 std::iterator_traits<_PopulationIterator>::iterator_category;
5813 using __samp_cat =
typename 5814 std::iterator_traits<_SampleIterator>::iterator_category;
5817 __or_<is_convertible<__pop_cat, forward_iterator_tag>,
5818 is_convertible<__samp_cat, random_access_iterator_tag>>::value,
5819 "output range must use a RandomAccessIterator when input range" 5820 " does not meet the ForwardIterator requirements");
5823 "sample size must be an integer type");
5825 typename iterator_traits<_PopulationIterator>::difference_type __d = __n;
5827 __sample(__first, __last, __pop_cat{}, __out, __samp_cat{}, __d,
5828 std::forward<_UniformRandomBitGenerator>(__g));
5833 _GLIBCXX_END_NAMESPACE_ALGO
_GLIBCXX14_CONSTEXPR _ForwardIterator min_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
Return the minimum element in a range using comparison functor.
iterator_traits< _Iter >::iterator_category __iterator_category(const _Iter &)
Bidirectional iterators support a superset of forward iterator operations.
constexpr int __lg(int __n)
This is a helper function for the sort routines and for random.tcc.
void __heap_select(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last, _Compare __comp)
This is a helper function for the sort routines.
_ForwardIterator __search_n_aux(_ForwardIterator __first, _ForwardIterator __last, _Integer __count, _UnaryPredicate __unary_pred, std::forward_iterator_tag)
_GLIBCXX14_CONSTEXPR pair< const _Tp &, const _Tp & > minmax(const _Tp &, const _Tp &)
Determines min and max at once as an ordered pair.
_RandomAccessIterator __unguarded_partition(_RandomAccessIterator __first, _RandomAccessIterator __last, _RandomAccessIterator __pivot, _Compare __comp)
This is a helper function...
_InputIterator find_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
Find the first element in a sequence for which a predicate is true.
void iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b)
Swaps the contents of two iterators.
_RandomAccessIterator __sample(_InputIterator __first, _InputIterator __last, input_iterator_tag, _RandomAccessIterator __out, random_access_iterator_tag, _Size __n, _UniformRandomBitGenerator &&__g)
Reservoir sampling algorithm.
void __unguarded_linear_insert(_RandomAccessIterator __last, _Compare __comp)
This is a helper function for the sort routine.
ISO C++ entities toplevel namespace is std.
bool none_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
Checks that a predicate is false for all the elements of a sequence.
_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...
_OutputIterator __sample(_ForwardIterator __first, _ForwardIterator __last, forward_iterator_tag, _OutputIterator __out, _Cat, _Size __n, _UniformRandomBitGenerator &&__g)
Selection sampling algorithm.
_GLIBCXX14_CONSTEXPR _ForwardIterator max_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
Return the maximum element in a range using comparison functor.
_ForwardIterator __partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, forward_iterator_tag)
This is a helper function...
_GLIBCXX17_CONSTEXPR iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
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.
size_type requested_size() const
Returns the size requested by the constructor; may be >size().
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< _ForwardIterator, _ForwardIterator > minmax_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
Return a pair of iterators pointing to the minimum and maximum elements in a range.
_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.
_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.
_GLIBCXX14_CONSTEXPR const _Tp & max(const _Tp &, const _Tp &)
This does what you think it does.
iterator begin()
As per Table mumble.
_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 __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.
_EuclideanRingElement __gcd(_EuclideanRingElement __m, _EuclideanRingElement __n)
void __final_insertion_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
This is a helper function for the sort routine.
_RandomAccessIterator __unguarded_partition_pivot(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
This is a helper function...
_OutputIterator __unique_copy(_ForwardIterator __first, _ForwardIterator __last, _OutputIterator __result, _BinaryPredicate __binary_pred, forward_iterator_tag, output_iterator_tag)
void __insertion_sort(_RandomAccessIterator __first, _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 __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.
void __unguarded_insertion_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
This is a helper function for the sort routine.
_GLIBCXX17_CONSTEXPR void advance(_InputIterator &__i, _Distance __n)
A generalization of pointer arithmetic.
_ForwardIterator2 swap_ranges(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2)
Swap the elements of two sequences.
_ForwardIterator __rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last, forward_iterator_tag)
This is a helper function for the rotate algorithm.
Forward iterators support a superset of input iterator operations.
_T1 first
second_type is the second bound type
void __reverse(_BidirectionalIterator __first, _BidirectionalIterator __last, bidirectional_iterator_tag)
pair< _IntType, _IntType > __gen_two_uniform_ints(_IntType __b0, _IntType __b1, _UniformRandomBitGenerator &&__g)
Generate two uniformly distributed integers using a single distribution invocation.
Uniform discrete distribution for random numbers. A discrete random distribution on the range with e...
size_type size() const
As per Table mumble.
_InputIterator find_if_not(_InputIterator __first, _InputIterator __last, _Predicate __pred)
Find the first element in a sequence for which a predicate is false.
Random-access iterators support a superset of bidirectional iterator operations.
_T2 second
first is a copy of the first object
void __inplace_stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
This is a helper function for the stable sorting routines.
result_type max() const
Returns the inclusive upper bound of the distribution range.
_GLIBCXX14_CONSTEXPR const _Tp & min(const _Tp &, const _Tp &)
This does what you think it does.
Struct holding two objects of arbitrary type.
Marking output iterators.
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.
_ForwardIterator rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last)
Rotate the elements of a sequence.
_ForwardIterator is_sorted_until(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
Determines the end of a sorted sequence using comparison functor.
_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.
void __introsort_loop(_RandomAccessIterator __first, _RandomAccessIterator __last, _Size __depth_limit, _Compare __comp)
This is a helper function for the sort routine.