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,
598 template<
typename _ForwardIterator,
typename _Predicate>
600 partition_point(_ForwardIterator __first, _ForwardIterator __last,
604 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
605 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
606 typename iterator_traits<_ForwardIterator>::value_type>)
609 __glibcxx_requires_valid_range(__first, __last);
611 typedef typename iterator_traits<_ForwardIterator>::difference_type
615 _DistanceType __half;
616 _ForwardIterator __middle;
623 if (__pred(*__middle))
627 __len = __len - __half - 1;
636 template<
typename _InputIterator,
typename _OutputIterator,
639 __remove_copy_if(_InputIterator __first, _InputIterator __last,
640 _OutputIterator __result, _Predicate __pred)
642 for (; __first != __last; ++__first)
643 if (!__pred(__first))
645 *__result = *__first;
665 template<
typename _InputIterator,
typename _OutputIterator,
typename _Tp>
666 inline _OutputIterator
667 remove_copy(_InputIterator __first, _InputIterator __last,
668 _OutputIterator __result,
const _Tp& __value)
671 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
672 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
673 typename iterator_traits<_InputIterator>::value_type>)
674 __glibcxx_function_requires(_EqualOpConcept<
675 typename iterator_traits<_InputIterator>::value_type, _Tp>)
676 __glibcxx_requires_valid_range(__first, __last);
678 return std::__remove_copy_if(__first, __last, __result,
679 __gnu_cxx::__ops::__iter_equals_val(__value));
697 template<
typename _InputIterator,
typename _OutputIterator,
699 inline _OutputIterator
700 remove_copy_if(_InputIterator __first, _InputIterator __last,
701 _OutputIterator __result, _Predicate __pred)
704 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
705 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
706 typename iterator_traits<_InputIterator>::value_type>)
707 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
708 typename iterator_traits<_InputIterator>::value_type>)
709 __glibcxx_requires_valid_range(__first, __last);
711 return std::__remove_copy_if(__first, __last, __result,
712 __gnu_cxx::__ops::__pred_iter(__pred));
715 #if __cplusplus >= 201103L 731 template<
typename _InputIterator,
typename _OutputIterator,
734 copy_if(_InputIterator __first, _InputIterator __last,
735 _OutputIterator __result, _Predicate __pred)
738 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
739 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
740 typename iterator_traits<_InputIterator>::value_type>)
741 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
742 typename iterator_traits<_InputIterator>::value_type>)
743 __glibcxx_requires_valid_range(__first, __last);
745 for (; __first != __last; ++__first)
746 if (__pred(*__first))
748 *__result = *__first;
754 template<
typename _InputIterator,
typename _Size,
typename _OutputIterator>
756 __copy_n(_InputIterator __first, _Size __n,
763 *__result = *__first;
774 template<
typename _RandomAccessIterator,
typename _Size,
775 typename _OutputIterator>
776 inline _OutputIterator
777 __copy_n(_RandomAccessIterator __first, _Size __n,
779 {
return std::copy(__first, __first + __n, __result); }
794 template<
typename _InputIterator,
typename _Size,
typename _OutputIterator>
795 inline _OutputIterator
796 copy_n(_InputIterator __first, _Size __n, _OutputIterator __result)
799 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
800 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
801 typename iterator_traits<_InputIterator>::value_type>)
803 return std::__copy_n(__first, __n, __result,
822 template<
typename _InputIterator,
typename _OutputIterator1,
823 typename _OutputIterator2,
typename _Predicate>
825 partition_copy(_InputIterator __first, _InputIterator __last,
826 _OutputIterator1 __out_true, _OutputIterator2 __out_false,
830 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
831 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator1,
832 typename iterator_traits<_InputIterator>::value_type>)
833 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator2,
834 typename iterator_traits<_InputIterator>::value_type>)
835 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
836 typename iterator_traits<_InputIterator>::value_type>)
837 __glibcxx_requires_valid_range(__first, __last);
839 for (; __first != __last; ++__first)
840 if (__pred(*__first))
842 *__out_true = *__first;
847 *__out_false = *__first;
855 template<
typename _ForwardIterator,
typename _Predicate>
857 __remove_if(_ForwardIterator __first, _ForwardIterator __last,
861 if (__first == __last)
863 _ForwardIterator __result = __first;
865 for (; __first != __last; ++__first)
866 if (!__pred(__first))
868 *__result = _GLIBCXX_MOVE(*__first);
891 template<
typename _ForwardIterator,
typename _Tp>
892 inline _ForwardIterator
893 remove(_ForwardIterator __first, _ForwardIterator __last,
897 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
899 __glibcxx_function_requires(_EqualOpConcept<
900 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
901 __glibcxx_requires_valid_range(__first, __last);
903 return std::__remove_if(__first, __last,
904 __gnu_cxx::__ops::__iter_equals_val(__value));
924 template<
typename _ForwardIterator,
typename _Predicate>
925 inline _ForwardIterator
926 remove_if(_ForwardIterator __first, _ForwardIterator __last,
930 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
932 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
933 typename iterator_traits<_ForwardIterator>::value_type>)
934 __glibcxx_requires_valid_range(__first, __last);
936 return std::__remove_if(__first, __last,
937 __gnu_cxx::__ops::__pred_iter(__pred));
940 template<
typename _ForwardIterator,
typename _BinaryPredicate>
942 __adjacent_find(_ForwardIterator __first, _ForwardIterator __last,
943 _BinaryPredicate __binary_pred)
945 if (__first == __last)
947 _ForwardIterator __next = __first;
948 while (++__next != __last)
950 if (__binary_pred(__first, __next))
957 template<
typename _ForwardIterator,
typename _BinaryPredicate>
959 __unique(_ForwardIterator __first, _ForwardIterator __last,
960 _BinaryPredicate __binary_pred)
963 __first = std::__adjacent_find(__first, __last, __binary_pred);
964 if (__first == __last)
968 _ForwardIterator __dest = __first;
970 while (++__first != __last)
971 if (!__binary_pred(__dest, __first))
972 *++__dest = _GLIBCXX_MOVE(*__first);
990 template<
typename _ForwardIterator>
991 inline _ForwardIterator
992 unique(_ForwardIterator __first, _ForwardIterator __last)
995 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
997 __glibcxx_function_requires(_EqualityComparableConcept<
998 typename iterator_traits<_ForwardIterator>::value_type>)
999 __glibcxx_requires_valid_range(__first, __last);
1001 return std::__unique(__first, __last,
1002 __gnu_cxx::__ops::__iter_equal_to_iter());
1020 template<
typename _ForwardIterator,
typename _BinaryPredicate>
1021 inline _ForwardIterator
1022 unique(_ForwardIterator __first, _ForwardIterator __last,
1023 _BinaryPredicate __binary_pred)
1026 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1028 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1029 typename iterator_traits<_ForwardIterator>::value_type,
1030 typename iterator_traits<_ForwardIterator>::value_type>)
1031 __glibcxx_requires_valid_range(__first, __last);
1033 return std::__unique(__first, __last,
1034 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred));
1043 template<
typename _ForwardIterator,
typename _OutputIterator,
1044 typename _BinaryPredicate>
1047 _OutputIterator __result, _BinaryPredicate __binary_pred,
1051 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1052 typename iterator_traits<_ForwardIterator>::value_type,
1053 typename iterator_traits<_ForwardIterator>::value_type>)
1055 _ForwardIterator __next = __first;
1056 *__result = *__first;
1057 while (++__next != __last)
1058 if (!__binary_pred(__first, __next))
1061 *++__result = *__first;
1072 template<
typename _InputIterator,
typename _OutputIterator,
1073 typename _BinaryPredicate>
1076 _OutputIterator __result, _BinaryPredicate __binary_pred,
1080 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1081 typename iterator_traits<_InputIterator>::value_type,
1082 typename iterator_traits<_InputIterator>::value_type>)
1084 typename iterator_traits<_InputIterator>::value_type __value = *__first;
1085 __decltype(__gnu_cxx::__ops::__iter_comp_val(__binary_pred))
1087 = __gnu_cxx::__ops::__iter_comp_val(__binary_pred);
1088 *__result = __value;
1089 while (++__first != __last)
1090 if (!__rebound_pred(__first, __value))
1093 *++__result = __value;
1104 template<
typename _InputIterator,
typename _ForwardIterator,
1105 typename _BinaryPredicate>
1108 _ForwardIterator __result, _BinaryPredicate __binary_pred,
1112 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1113 typename iterator_traits<_ForwardIterator>::value_type,
1114 typename iterator_traits<_InputIterator>::value_type>)
1115 *__result = *__first;
1116 while (++__first != __last)
1117 if (!__binary_pred(__result, __first))
1118 *++__result = *__first;
1127 template<
typename _B
idirectionalIterator>
1129 __reverse(_BidirectionalIterator __first, _BidirectionalIterator __last,
1133 if (__first == __last || __first == --__last)
1147 template<
typename _RandomAccessIterator>
1149 __reverse(_RandomAccessIterator __first, _RandomAccessIterator __last,
1152 if (__first == __last)
1155 while (__first < __last)
1175 template<
typename _B
idirectionalIterator>
1177 reverse(_BidirectionalIterator __first, _BidirectionalIterator __last)
1180 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
1181 _BidirectionalIterator>)
1182 __glibcxx_requires_valid_range(__first, __last);
1202 template<
typename _B
idirectionalIterator,
typename _OutputIterator>
1204 reverse_copy(_BidirectionalIterator __first, _BidirectionalIterator __last,
1205 _OutputIterator __result)
1208 __glibcxx_function_requires(_BidirectionalIteratorConcept<
1209 _BidirectionalIterator>)
1210 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1211 typename iterator_traits<_BidirectionalIterator>::value_type>)
1212 __glibcxx_requires_valid_range(__first, __last);
1214 while (__first != __last)
1217 *__result = *__last;
1227 template<
typename _Eucl
ideanRingElement>
1228 _EuclideanRingElement
1229 __gcd(_EuclideanRingElement __m, _EuclideanRingElement __n)
1233 _EuclideanRingElement __t = __m % __n;
1241 template<
typename _ForwardIterator>
1244 _ForwardIterator __middle,
1245 _ForwardIterator __last,
1248 if (__first == __middle || __last == __middle)
1251 _ForwardIterator __first2 = __middle;
1257 if (__first == __middle)
1258 __middle = __first2;
1260 while (__first2 != __last);
1262 __first2 = __middle;
1264 while (__first2 != __last)
1269 if (__first == __middle)
1270 __middle = __first2;
1271 else if (__first2 == __last)
1272 __first2 = __middle;
1277 template<
typename _B
idirectionalIterator>
1280 _BidirectionalIterator __middle,
1281 _BidirectionalIterator __last,
1285 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
1286 _BidirectionalIterator>)
1288 if (__first == __middle || __last == __middle)
1294 while (__first != __middle && __middle != __last)
1300 if (__first == __middle)
1307 template<
typename _RandomAccessIterator>
1310 _RandomAccessIterator __middle,
1311 _RandomAccessIterator __last,
1315 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
1316 _RandomAccessIterator>)
1318 if (__first == __middle || __last == __middle)
1321 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
1323 typedef typename iterator_traits<_RandomAccessIterator>::value_type
1326 _Distance __n = __last - __first;
1327 _Distance __k = __middle - __first;
1329 if (__k == __n - __k)
1335 _RandomAccessIterator __p = __first;
1339 if (__k < __n - __k)
1341 if (__is_pod(_ValueType) && __k == 1)
1343 _ValueType __t = _GLIBCXX_MOVE(*__p);
1344 _GLIBCXX_MOVE3(__p + 1, __p + __n, __p);
1345 *(__p + __n - 1) = _GLIBCXX_MOVE(__t);
1348 _RandomAccessIterator __q = __p + __k;
1349 for (_Distance __i = 0; __i < __n - __k; ++ __i)
1364 if (__is_pod(_ValueType) && __k == 1)
1366 _ValueType __t = _GLIBCXX_MOVE(*(__p + __n - 1));
1367 _GLIBCXX_MOVE_BACKWARD3(__p, __p + __n - 1, __p + __n);
1368 *__p = _GLIBCXX_MOVE(__t);
1371 _RandomAccessIterator __q = __p + __n;
1373 for (_Distance __i = 0; __i < __n - __k; ++ __i)
1408 template<
typename _ForwardIterator>
1410 rotate(_ForwardIterator __first, _ForwardIterator __middle,
1411 _ForwardIterator __last)
1414 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1416 __glibcxx_requires_valid_range(__first, __middle);
1417 __glibcxx_requires_valid_range(__middle, __last);
1443 template<
typename _ForwardIterator,
typename _OutputIterator>
1444 inline _OutputIterator
1445 rotate_copy(_ForwardIterator __first, _ForwardIterator __middle,
1446 _ForwardIterator __last, _OutputIterator __result)
1449 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
1450 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1451 typename iterator_traits<_ForwardIterator>::value_type>)
1452 __glibcxx_requires_valid_range(__first, __middle);
1453 __glibcxx_requires_valid_range(__middle, __last);
1455 return std::copy(__first, __middle,
1456 std::copy(__middle, __last, __result));
1460 template<
typename _ForwardIterator,
typename _Predicate>
1465 if (__first == __last)
1468 while (__pred(*__first))
1469 if (++__first == __last)
1472 _ForwardIterator __next = __first;
1474 while (++__next != __last)
1475 if (__pred(*__next))
1485 template<
typename _B
idirectionalIterator,
typename _Predicate>
1486 _BidirectionalIterator
1487 __partition(_BidirectionalIterator __first, _BidirectionalIterator __last,
1493 if (__first == __last)
1495 else if (__pred(*__first))
1501 if (__first == __last)
1503 else if (!
bool(__pred(*__last)))
1517 template<
typename _ForwardIterator,
typename _Predicate,
typename _Distance>
1520 _Predicate __pred, _Distance __len)
1524 _ForwardIterator __middle = __first;
1526 _ForwardIterator __left_split =
1530 _Distance __right_len = __len - __len / 2;
1531 _ForwardIterator __right_split =
1537 std::rotate(__left_split, __middle, __right_split);
1539 return __left_split;
1548 template<
typename _ForwardIterator,
typename _Pointer,
typename _Predicate,
1552 _ForwardIterator __last,
1553 _Predicate __pred, _Distance __len,
1555 _Distance __buffer_size)
1557 if (__len <= __buffer_size)
1559 _ForwardIterator __result1 = __first;
1560 _Pointer __result2 = __buffer;
1564 *__result2 = _GLIBCXX_MOVE(*__first);
1567 for (; __first != __last; ++__first)
1568 if (__pred(__first))
1570 *__result1 = _GLIBCXX_MOVE(*__first);
1575 *__result2 = _GLIBCXX_MOVE(*__first);
1578 _GLIBCXX_MOVE3(__buffer, __result2, __result1);
1583 _ForwardIterator __middle = __first;
1585 _ForwardIterator __left_split =
1587 __len / 2, __buffer,
1591 _Distance __right_len = __len - __len / 2;
1592 _ForwardIterator __right_split =
1598 __buffer, __buffer_size);
1599 std::rotate(__left_split, __middle, __right_split);
1601 return __left_split;
1605 template<
typename _ForwardIterator,
typename _Predicate>
1607 __stable_partition(_ForwardIterator __first, _ForwardIterator __last,
1612 if (__first == __last)
1615 typedef typename iterator_traits<_ForwardIterator>::value_type
1617 typedef typename iterator_traits<_ForwardIterator>::difference_type
1621 if (__buf.
size() > 0)
1626 _DistanceType(__buf.
size()));
1650 template<
typename _ForwardIterator,
typename _Predicate>
1651 inline _ForwardIterator
1652 stable_partition(_ForwardIterator __first, _ForwardIterator __last,
1656 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1658 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
1659 typename iterator_traits<_ForwardIterator>::value_type>)
1660 __glibcxx_requires_valid_range(__first, __last);
1662 return std::__stable_partition(__first, __last,
1663 __gnu_cxx::__ops::__pred_iter(__pred));
1667 template<
typename _RandomAccessIterator,
typename _Compare>
1670 _RandomAccessIterator __middle,
1671 _RandomAccessIterator __last, _Compare __comp)
1673 std::__make_heap(__first, __middle, __comp);
1674 for (_RandomAccessIterator __i = __middle; __i < __last; ++__i)
1675 if (__comp(__i, __first))
1676 std::__pop_heap(__first, __middle, __i, __comp);
1681 template<
typename _InputIterator,
typename _RandomAccessIterator,
1683 _RandomAccessIterator
1684 __partial_sort_copy(_InputIterator __first, _InputIterator __last,
1685 _RandomAccessIterator __result_first,
1686 _RandomAccessIterator __result_last,
1689 typedef typename iterator_traits<_InputIterator>::value_type
1691 typedef iterator_traits<_RandomAccessIterator> _RItTraits;
1692 typedef typename _RItTraits::difference_type _DistanceType;
1694 if (__result_first == __result_last)
1695 return __result_last;
1696 _RandomAccessIterator __result_real_last = __result_first;
1697 while (__first != __last && __result_real_last != __result_last)
1699 *__result_real_last = *__first;
1700 ++__result_real_last;
1704 std::__make_heap(__result_first, __result_real_last, __comp);
1705 while (__first != __last)
1707 if (__comp(__first, __result_first))
1708 std::__adjust_heap(__result_first, _DistanceType(0),
1709 _DistanceType(__result_real_last
1711 _InputValueType(*__first), __comp);
1714 std::__sort_heap(__result_first, __result_real_last, __comp);
1715 return __result_real_last;
1736 template<
typename _InputIterator,
typename _RandomAccessIterator>
1737 inline _RandomAccessIterator
1738 partial_sort_copy(_InputIterator __first, _InputIterator __last,
1739 _RandomAccessIterator __result_first,
1740 _RandomAccessIterator __result_last)
1742 typedef typename iterator_traits<_InputIterator>::value_type
1744 typedef typename iterator_traits<_RandomAccessIterator>::value_type
1746 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
1750 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1751 __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
1753 __glibcxx_function_requires(_LessThanOpConcept<_InputValueType,
1755 __glibcxx_function_requires(_LessThanComparableConcept<_OutputValueType>)
1756 __glibcxx_requires_valid_range(__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 typedef typename iterator_traits<_InputIterator>::value_type
1794 typedef typename iterator_traits<_RandomAccessIterator>::value_type
1796 typedef typename iterator_traits<_RandomAccessIterator>::difference_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_valid_range(__result_first, __result_last);
1812 return std::__partial_sort_copy(__first, __last,
1813 __result_first, __result_last,
1814 __gnu_cxx::__ops::__iter_comp_iter(__comp));
1818 template<
typename _RandomAccessIterator,
typename _Compare>
1823 typename iterator_traits<_RandomAccessIterator>::value_type
1824 __val = _GLIBCXX_MOVE(*__last);
1825 _RandomAccessIterator __next = __last;
1827 while (__comp(__val, __next))
1829 *__last = _GLIBCXX_MOVE(*__next);
1833 *__last = _GLIBCXX_MOVE(__val);
1837 template<
typename _RandomAccessIterator,
typename _Compare>
1840 _RandomAccessIterator __last, _Compare __comp)
1842 if (__first == __last)
return;
1844 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
1846 if (__comp(__i, __first))
1848 typename iterator_traits<_RandomAccessIterator>::value_type
1849 __val = _GLIBCXX_MOVE(*__i);
1850 _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1);
1851 *__first = _GLIBCXX_MOVE(__val);
1855 __gnu_cxx::__ops::__val_comp_iter(__comp));
1860 template<
typename _RandomAccessIterator,
typename _Compare>
1863 _RandomAccessIterator __last, _Compare __comp)
1865 for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
1867 __gnu_cxx::__ops::__val_comp_iter(__comp));
1874 enum { _S_threshold = 16 };
1877 template<
typename _RandomAccessIterator,
typename _Compare>
1880 _RandomAccessIterator __last, _Compare __comp)
1882 if (__last - __first >
int(_S_threshold))
1893 template<
typename _RandomAccessIterator,
typename _Compare>
1894 _RandomAccessIterator
1896 _RandomAccessIterator __last,
1897 _RandomAccessIterator __pivot, _Compare __comp)
1901 while (__comp(__first, __pivot))
1904 while (__comp(__pivot, __last))
1906 if (!(__first < __last))
1914 template<
typename _RandomAccessIterator,
typename _Compare>
1915 inline _RandomAccessIterator
1917 _RandomAccessIterator __last, _Compare __comp)
1919 _RandomAccessIterator __mid = __first + (__last - __first) / 2;
1925 template<
typename _RandomAccessIterator,
typename _Compare>
1927 __partial_sort(_RandomAccessIterator __first,
1928 _RandomAccessIterator __middle,
1929 _RandomAccessIterator __last,
1933 std::__sort_heap(__first, __middle, __comp);
1937 template<
typename _RandomAccessIterator,
typename _Size,
typename _Compare>
1940 _RandomAccessIterator __last,
1941 _Size __depth_limit, _Compare __comp)
1943 while (__last - __first >
int(_S_threshold))
1945 if (__depth_limit == 0)
1947 std::__partial_sort(__first, __last, __last, __comp);
1951 _RandomAccessIterator __cut =
1960 template<
typename _RandomAccessIterator,
typename _Compare>
1962 __sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
1965 if (__first != __last)
1974 template<
typename _RandomAccessIterator,
typename _Size,
typename _Compare>
1976 __introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth,
1977 _RandomAccessIterator __last, _Size __depth_limit,
1980 while (__last - __first > 3)
1982 if (__depth_limit == 0)
1990 _RandomAccessIterator __cut =
2020 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2021 inline _ForwardIterator
2022 lower_bound(_ForwardIterator __first, _ForwardIterator __last,
2023 const _Tp& __val, _Compare __comp)
2025 typedef typename iterator_traits<_ForwardIterator>::value_type
2029 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2030 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2032 __glibcxx_requires_partitioned_lower_pred(__first, __last,
2035 return std::__lower_bound(__first, __last, __val,
2036 __gnu_cxx::__ops::__iter_comp_val(__comp));
2039 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2041 __upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2042 const _Tp& __val, _Compare __comp)
2044 typedef typename iterator_traits<_ForwardIterator>::difference_type
2051 _DistanceType __half = __len >> 1;
2052 _ForwardIterator __middle = __first;
2054 if (__comp(__val, __middle))
2060 __len = __len - __half - 1;
2077 template<
typename _ForwardIterator,
typename _Tp>
2078 inline _ForwardIterator
2079 upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2082 typedef typename iterator_traits<_ForwardIterator>::value_type
2086 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2087 __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>)
2088 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2090 return std::__upper_bound(__first, __last, __val,
2091 __gnu_cxx::__ops::__val_less_iter());
2109 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2110 inline _ForwardIterator
2111 upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2112 const _Tp& __val, _Compare __comp)
2114 typedef typename iterator_traits<_ForwardIterator>::value_type
2118 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2119 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2121 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2124 return std::__upper_bound(__first, __last, __val,
2125 __gnu_cxx::__ops::__val_comp_iter(__comp));
2128 template<
typename _ForwardIterator,
typename _Tp,
2129 typename _CompareItTp,
typename _CompareTpIt>
2131 __equal_range(_ForwardIterator __first, _ForwardIterator __last,
2133 _CompareItTp __comp_it_val, _CompareTpIt __comp_val_it)
2135 typedef typename iterator_traits<_ForwardIterator>::difference_type
2142 _DistanceType __half = __len >> 1;
2143 _ForwardIterator __middle = __first;
2145 if (__comp_it_val(__middle, __val))
2149 __len = __len - __half - 1;
2151 else if (__comp_val_it(__val, __middle))
2155 _ForwardIterator __left
2156 = std::__lower_bound(__first, __middle, __val, __comp_it_val);
2158 _ForwardIterator __right
2159 = std::__upper_bound(++__middle, __first, __val, __comp_val_it);
2183 template<
typename _ForwardIterator,
typename _Tp>
2185 equal_range(_ForwardIterator __first, _ForwardIterator __last,
2188 typedef typename iterator_traits<_ForwardIterator>::value_type
2192 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2193 __glibcxx_function_requires(_LessThanOpConcept<_ValueType, _Tp>)
2194 __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>)
2195 __glibcxx_requires_partitioned_lower(__first, __last, __val);
2196 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2198 return std::__equal_range(__first, __last, __val,
2199 __gnu_cxx::__ops::__iter_less_val(),
2200 __gnu_cxx::__ops::__val_less_iter());
2220 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2222 equal_range(_ForwardIterator __first, _ForwardIterator __last,
2223 const _Tp& __val, _Compare __comp)
2225 typedef typename iterator_traits<_ForwardIterator>::value_type
2229 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2230 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2232 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2234 __glibcxx_requires_partitioned_lower_pred(__first, __last,
2236 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2239 return std::__equal_range(__first, __last, __val,
2240 __gnu_cxx::__ops::__iter_comp_val(__comp),
2241 __gnu_cxx::__ops::__val_comp_iter(__comp));
2256 template<
typename _ForwardIterator,
typename _Tp>
2258 binary_search(_ForwardIterator __first, _ForwardIterator __last,
2261 typedef typename iterator_traits<_ForwardIterator>::value_type
2265 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2266 __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>)
2267 __glibcxx_requires_partitioned_lower(__first, __last, __val);
2268 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2270 _ForwardIterator __i
2271 = std::__lower_bound(__first, __last, __val,
2272 __gnu_cxx::__ops::__iter_less_val());
2273 return __i != __last && !(__val < *__i);
2291 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2293 binary_search(_ForwardIterator __first, _ForwardIterator __last,
2294 const _Tp& __val, _Compare __comp)
2296 typedef typename iterator_traits<_ForwardIterator>::value_type
2300 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2301 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2303 __glibcxx_requires_partitioned_lower_pred(__first, __last,
2305 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2308 _ForwardIterator __i
2309 = std::__lower_bound(__first, __last, __val,
2310 __gnu_cxx::__ops::__iter_comp_val(__comp));
2311 return __i != __last && !bool(__comp(__val, *__i));
2317 template<
typename _InputIterator1,
typename _InputIterator2,
2318 typename _OutputIterator,
typename _Compare>
2321 _InputIterator2 __first2, _InputIterator2 __last2,
2322 _OutputIterator __result, _Compare __comp)
2324 while (__first1 != __last1 && __first2 != __last2)
2326 if (__comp(__first2, __first1))
2328 *__result = _GLIBCXX_MOVE(*__first2);
2333 *__result = _GLIBCXX_MOVE(*__first1);
2338 if (__first1 != __last1)
2339 _GLIBCXX_MOVE3(__first1, __last1, __result);
2343 template<
typename _BidirectionalIterator1,
typename _BidirectionalIterator2,
2344 typename _BidirectionalIterator3,
typename _Compare>
2347 _BidirectionalIterator1 __last1,
2348 _BidirectionalIterator2 __first2,
2349 _BidirectionalIterator2 __last2,
2350 _BidirectionalIterator3 __result,
2353 if (__first1 == __last1)
2355 _GLIBCXX_MOVE_BACKWARD3(__first2, __last2, __result);
2358 else if (__first2 == __last2)
2365 if (__comp(__last2, __last1))
2367 *--__result = _GLIBCXX_MOVE(*__last1);
2368 if (__first1 == __last1)
2370 _GLIBCXX_MOVE_BACKWARD3(__first2, ++__last2, __result);
2377 *--__result = _GLIBCXX_MOVE(*__last2);
2378 if (__first2 == __last2)
2386 template<
typename _BidirectionalIterator1,
typename _BidirectionalIterator2,
2388 _BidirectionalIterator1
2390 _BidirectionalIterator1 __middle,
2391 _BidirectionalIterator1 __last,
2392 _Distance __len1, _Distance __len2,
2393 _BidirectionalIterator2 __buffer,
2394 _Distance __buffer_size)
2396 _BidirectionalIterator2 __buffer_end;
2397 if (__len1 > __len2 && __len2 <= __buffer_size)
2401 __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
2402 _GLIBCXX_MOVE_BACKWARD3(__first, __middle, __last);
2403 return _GLIBCXX_MOVE3(__buffer, __buffer_end, __first);
2408 else if (__len1 <= __buffer_size)
2412 __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
2413 _GLIBCXX_MOVE3(__middle, __last, __first);
2414 return _GLIBCXX_MOVE_BACKWARD3(__buffer, __buffer_end, __last);
2428 template<
typename _BidirectionalIterator,
typename _Distance,
2429 typename _Pointer,
typename _Compare>
2432 _BidirectionalIterator __middle,
2433 _BidirectionalIterator __last,
2434 _Distance __len1, _Distance __len2,
2435 _Pointer __buffer, _Distance __buffer_size,
2438 if (__len1 <= __len2 && __len1 <= __buffer_size)
2440 _Pointer __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
2444 else if (__len2 <= __buffer_size)
2446 _Pointer __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
2448 __buffer_end, __last, __comp);
2452 _BidirectionalIterator __first_cut = __first;
2453 _BidirectionalIterator __second_cut = __middle;
2454 _Distance __len11 = 0;
2455 _Distance __len22 = 0;
2456 if (__len1 > __len2)
2458 __len11 = __len1 / 2;
2461 = std::__lower_bound(__middle, __last, *__first_cut,
2462 __gnu_cxx::__ops::__iter_comp_val(__comp));
2467 __len22 = __len2 / 2;
2470 = std::__upper_bound(__first, __middle, *__second_cut,
2471 __gnu_cxx::__ops::__val_comp_iter(__comp));
2474 _BidirectionalIterator __new_middle
2476 __len1 - __len11, __len22, __buffer,
2479 __len22, __buffer, __buffer_size, __comp);
2482 __len2 - __len22, __buffer,
2483 __buffer_size, __comp);
2488 template<
typename _BidirectionalIterator,
typename _Distance,
2492 _BidirectionalIterator __middle,
2493 _BidirectionalIterator __last,
2494 _Distance __len1, _Distance __len2,
2497 if (__len1 == 0 || __len2 == 0)
2499 if (__len1 + __len2 == 2)
2501 if (__comp(__middle, __first))
2505 _BidirectionalIterator __first_cut = __first;
2506 _BidirectionalIterator __second_cut = __middle;
2507 _Distance __len11 = 0;
2508 _Distance __len22 = 0;
2509 if (__len1 > __len2)
2511 __len11 = __len1 / 2;
2514 = std::__lower_bound(__middle, __last, *__first_cut,
2515 __gnu_cxx::__ops::__iter_comp_val(__comp));
2520 __len22 = __len2 / 2;
2523 = std::__upper_bound(__first, __middle, *__second_cut,
2524 __gnu_cxx::__ops::__val_comp_iter(__comp));
2528 _BidirectionalIterator __new_middle = __first_cut;
2531 __len11, __len22, __comp);
2533 __len1 - __len11, __len2 - __len22, __comp);
2536 template<
typename _B
idirectionalIterator,
typename _Compare>
2538 __inplace_merge(_BidirectionalIterator __first,
2539 _BidirectionalIterator __middle,
2540 _BidirectionalIterator __last,
2543 typedef typename iterator_traits<_BidirectionalIterator>::value_type
2545 typedef typename iterator_traits<_BidirectionalIterator>::difference_type
2548 if (__first == __middle || __middle == __last)
2551 const _DistanceType __len1 =
std::distance(__first, __middle);
2552 const _DistanceType __len2 =
std::distance(__middle, __last);
2555 _TmpBuf __buf(__first, __last);
2557 if (__buf.begin() == 0)
2559 (__first, __middle, __last, __len1, __len2, __comp);
2562 (__first, __middle, __last, __len1, __len2, __buf.begin(),
2563 _DistanceType(__buf.size()), __comp);
2584 template<
typename _B
idirectionalIterator>
2586 inplace_merge(_BidirectionalIterator __first,
2587 _BidirectionalIterator __middle,
2588 _BidirectionalIterator __last)
2591 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
2592 _BidirectionalIterator>)
2593 __glibcxx_function_requires(_LessThanComparableConcept<
2594 typename iterator_traits<_BidirectionalIterator>::value_type>)
2595 __glibcxx_requires_sorted(__first, __middle);
2596 __glibcxx_requires_sorted(__middle, __last);
2598 std::__inplace_merge(__first, __middle, __last,
2599 __gnu_cxx::__ops::__iter_less_iter());
2624 template<
typename _B
idirectionalIterator,
typename _Compare>
2626 inplace_merge(_BidirectionalIterator __first,
2627 _BidirectionalIterator __middle,
2628 _BidirectionalIterator __last,
2632 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
2633 _BidirectionalIterator>)
2634 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2635 typename iterator_traits<_BidirectionalIterator>::value_type,
2636 typename iterator_traits<_BidirectionalIterator>::value_type>)
2637 __glibcxx_requires_sorted_pred(__first, __middle, __comp);
2638 __glibcxx_requires_sorted_pred(__middle, __last, __comp);
2640 std::__inplace_merge(__first, __middle, __last,
2641 __gnu_cxx::__ops::__iter_comp_iter(__comp));
2646 template<
typename _InputIterator,
typename _OutputIterator,
2650 _InputIterator __first2, _InputIterator __last2,
2651 _OutputIterator __result, _Compare __comp)
2653 while (__first1 != __last1 && __first2 != __last2)
2655 if (__comp(__first2, __first1))
2657 *__result = _GLIBCXX_MOVE(*__first2);
2662 *__result = _GLIBCXX_MOVE(*__first1);
2667 return _GLIBCXX_MOVE3(__first2, __last2,
2668 _GLIBCXX_MOVE3(__first1, __last1,
2672 template<
typename _RandomAccessIterator1,
typename _RandomAccessIterator2,
2673 typename _Distance,
typename _Compare>
2675 __merge_sort_loop(_RandomAccessIterator1 __first,
2676 _RandomAccessIterator1 __last,
2677 _RandomAccessIterator2 __result, _Distance __step_size,
2680 const _Distance __two_step = 2 * __step_size;
2682 while (__last - __first >= __two_step)
2685 __first + __step_size,
2686 __first + __two_step,
2688 __first += __two_step;
2690 __step_size =
std::min(_Distance(__last - __first), __step_size);
2693 __first + __step_size, __last, __result, __comp);
2696 template<
typename _RandomAccessIterator,
typename _Distance,
2699 __chunk_insertion_sort(_RandomAccessIterator __first,
2700 _RandomAccessIterator __last,
2701 _Distance __chunk_size, _Compare __comp)
2703 while (__last - __first >= __chunk_size)
2706 __first += __chunk_size;
2711 enum { _S_chunk_size = 7 };
2713 template<
typename _RandomAccessIterator,
typename _Po
inter,
typename _Compare>
2715 __merge_sort_with_buffer(_RandomAccessIterator __first,
2716 _RandomAccessIterator __last,
2717 _Pointer __buffer, _Compare __comp)
2719 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
2722 const _Distance __len = __last - __first;
2723 const _Pointer __buffer_last = __buffer + __len;
2725 _Distance __step_size = _S_chunk_size;
2726 std::__chunk_insertion_sort(__first, __last, __step_size, __comp);
2728 while (__step_size < __len)
2730 std::__merge_sort_loop(__first, __last, __buffer,
2731 __step_size, __comp);
2733 std::__merge_sort_loop(__buffer, __buffer_last, __first,
2734 __step_size, __comp);
2739 template<
typename _RandomAccessIterator,
typename _Pointer,
2740 typename _Distance,
typename _Compare>
2742 __stable_sort_adaptive(_RandomAccessIterator __first,
2743 _RandomAccessIterator __last,
2744 _Pointer __buffer, _Distance __buffer_size,
2747 const _Distance __len = (__last - __first + 1) / 2;
2748 const _RandomAccessIterator __middle = __first + __len;
2749 if (__len > __buffer_size)
2751 std::__stable_sort_adaptive(__first, __middle, __buffer,
2752 __buffer_size, __comp);
2753 std::__stable_sort_adaptive(__middle, __last, __buffer,
2754 __buffer_size, __comp);
2758 std::__merge_sort_with_buffer(__first, __middle, __buffer, __comp);
2759 std::__merge_sort_with_buffer(__middle, __last, __buffer, __comp);
2762 _Distance(__middle - __first),
2763 _Distance(__last - __middle),
2764 __buffer, __buffer_size,
2769 template<
typename _RandomAccessIterator,
typename _Compare>
2772 _RandomAccessIterator __last, _Compare __comp)
2774 if (__last - __first < 15)
2779 _RandomAccessIterator __middle = __first + (__last - __first) / 2;
2795 template<
typename _InputIterator1,
typename _InputIterator2,
2798 __includes(_InputIterator1 __first1, _InputIterator1 __last1,
2799 _InputIterator2 __first2, _InputIterator2 __last2,
2802 while (__first1 != __last1 && __first2 != __last2)
2803 if (__comp(__first2, __first1))
2805 else if (__comp(__first1, __first2))
2808 ++__first1, ++__first2;
2810 return __first2 == __last2;
2831 template<
typename _InputIterator1,
typename _InputIterator2>
2833 includes(_InputIterator1 __first1, _InputIterator1 __last1,
2834 _InputIterator2 __first2, _InputIterator2 __last2)
2837 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
2838 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
2839 __glibcxx_function_requires(_LessThanOpConcept<
2840 typename iterator_traits<_InputIterator1>::value_type,
2841 typename iterator_traits<_InputIterator2>::value_type>)
2842 __glibcxx_function_requires(_LessThanOpConcept<
2843 typename iterator_traits<_InputIterator2>::value_type,
2844 typename iterator_traits<_InputIterator1>::value_type>)
2845 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
2846 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
2848 return std::__includes(__first1, __last1, __first2, __last2,
2849 __gnu_cxx::__ops::__iter_less_iter());
2873 template<
typename _InputIterator1,
typename _InputIterator2,
2876 includes(_InputIterator1 __first1, _InputIterator1 __last1,
2877 _InputIterator2 __first2, _InputIterator2 __last2,
2881 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
2882 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
2883 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2884 typename iterator_traits<_InputIterator1>::value_type,
2885 typename iterator_traits<_InputIterator2>::value_type>)
2886 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2887 typename iterator_traits<_InputIterator2>::value_type,
2888 typename iterator_traits<_InputIterator1>::value_type>)
2889 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
2890 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
2892 return std::__includes(__first1, __last1, __first2, __last2,
2893 __gnu_cxx::__ops::__iter_comp_iter(__comp));
2906 template<
typename _B
idirectionalIterator,
typename _Compare>
2908 __next_permutation(_BidirectionalIterator __first,
2909 _BidirectionalIterator __last, _Compare __comp)
2911 if (__first == __last)
2913 _BidirectionalIterator __i = __first;
2922 _BidirectionalIterator __ii = __i;
2924 if (__comp(__i, __ii))
2926 _BidirectionalIterator __j = __last;
2927 while (!__comp(__i, --__j))
2955 template<
typename _B
idirectionalIterator>
2957 next_permutation(_BidirectionalIterator __first,
2958 _BidirectionalIterator __last)
2961 __glibcxx_function_requires(_BidirectionalIteratorConcept<
2962 _BidirectionalIterator>)
2963 __glibcxx_function_requires(_LessThanComparableConcept<
2964 typename iterator_traits<_BidirectionalIterator>::value_type>)
2965 __glibcxx_requires_valid_range(__first, __last);
2967 return std::__next_permutation
2968 (__first, __last, __gnu_cxx::__ops::__iter_less_iter());
2986 template<
typename _B
idirectionalIterator,
typename _Compare>
2988 next_permutation(_BidirectionalIterator __first,
2989 _BidirectionalIterator __last, _Compare __comp)
2992 __glibcxx_function_requires(_BidirectionalIteratorConcept<
2993 _BidirectionalIterator>)
2994 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2995 typename iterator_traits<_BidirectionalIterator>::value_type,
2996 typename iterator_traits<_BidirectionalIterator>::value_type>)
2997 __glibcxx_requires_valid_range(__first, __last);
2999 return std::__next_permutation
3000 (__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
3003 template<
typename _B
idirectionalIterator,
typename _Compare>
3005 __prev_permutation(_BidirectionalIterator __first,
3006 _BidirectionalIterator __last, _Compare __comp)
3008 if (__first == __last)
3010 _BidirectionalIterator __i = __first;
3019 _BidirectionalIterator __ii = __i;
3021 if (__comp(__ii, __i))
3023 _BidirectionalIterator __j = __last;
3024 while (!__comp(--__j, __i))
3053 template<
typename _B
idirectionalIterator>
3055 prev_permutation(_BidirectionalIterator __first,
3056 _BidirectionalIterator __last)
3059 __glibcxx_function_requires(_BidirectionalIteratorConcept<
3060 _BidirectionalIterator>)
3061 __glibcxx_function_requires(_LessThanComparableConcept<
3062 typename iterator_traits<_BidirectionalIterator>::value_type>)
3063 __glibcxx_requires_valid_range(__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);
3097 return std::__prev_permutation(__first, __last,
3098 __gnu_cxx::__ops::__iter_comp_iter(__comp));
3104 template<
typename _InputIterator,
typename _OutputIterator,
3105 typename _Predicate,
typename _Tp>
3107 __replace_copy_if(_InputIterator __first, _InputIterator __last,
3108 _OutputIterator __result,
3109 _Predicate __pred,
const _Tp& __new_value)
3111 for (; __first != __last; ++__first, ++__result)
3112 if (__pred(__first))
3113 *__result = __new_value;
3115 *__result = *__first;
3133 template<
typename _InputIterator,
typename _OutputIterator,
typename _Tp>
3134 inline _OutputIterator
3135 replace_copy(_InputIterator __first, _InputIterator __last,
3136 _OutputIterator __result,
3137 const _Tp& __old_value,
const _Tp& __new_value)
3140 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3141 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
3142 typename iterator_traits<_InputIterator>::value_type>)
3143 __glibcxx_function_requires(_EqualOpConcept<
3144 typename iterator_traits<_InputIterator>::value_type, _Tp>)
3145 __glibcxx_requires_valid_range(__first, __last);
3147 return std::__replace_copy_if(__first, __last, __result,
3148 __gnu_cxx::__ops::__iter_equals_val(__old_value),
3167 template<
typename _InputIterator,
typename _OutputIterator,
3168 typename _Predicate,
typename _Tp>
3169 inline _OutputIterator
3170 replace_copy_if(_InputIterator __first, _InputIterator __last,
3171 _OutputIterator __result,
3172 _Predicate __pred,
const _Tp& __new_value)
3175 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3176 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
3177 typename iterator_traits<_InputIterator>::value_type>)
3178 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
3179 typename iterator_traits<_InputIterator>::value_type>)
3180 __glibcxx_requires_valid_range(__first, __last);
3182 return std::__replace_copy_if(__first, __last, __result,
3183 __gnu_cxx::__ops::__pred_iter(__pred),
3187 template<
typename _InputIterator,
typename _Predicate>
3188 typename iterator_traits<_InputIterator>::difference_type
3189 __count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
3191 typename iterator_traits<_InputIterator>::difference_type __n = 0;
3192 for (; __first != __last; ++__first)
3193 if (__pred(__first))
3198 #if __cplusplus >= 201103L 3206 template<
typename _ForwardIterator>
3208 is_sorted(_ForwardIterator __first, _ForwardIterator __last)
3220 template<
typename _ForwardIterator,
typename _Compare>
3222 is_sorted(_ForwardIterator __first, _ForwardIterator __last,
3226 template<
typename _ForwardIterator,
typename _Compare>
3228 __is_sorted_until(_ForwardIterator __first, _ForwardIterator __last,
3231 if (__first == __last)
3234 _ForwardIterator __next = __first;
3235 for (++__next; __next != __last; __first = __next, ++__next)
3236 if (__comp(__next, __first))
3249 template<
typename _ForwardIterator>
3250 inline _ForwardIterator
3251 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last)
3254 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3255 __glibcxx_function_requires(_LessThanComparableConcept<
3256 typename iterator_traits<_ForwardIterator>::value_type>)
3257 __glibcxx_requires_valid_range(__first, __last);
3259 return std::__is_sorted_until(__first, __last,
3260 __gnu_cxx::__ops::__iter_less_iter());
3272 template<
typename _ForwardIterator,
typename _Compare>
3273 inline _ForwardIterator
3274 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last,
3278 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3279 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3280 typename iterator_traits<_ForwardIterator>::value_type,
3281 typename iterator_traits<_ForwardIterator>::value_type>)
3282 __glibcxx_requires_valid_range(__first, __last);
3284 return std::__is_sorted_until(__first, __last,
3285 __gnu_cxx::__ops::__iter_comp_iter(__comp));
3296 template<
typename _Tp>
3301 __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
3303 return __b < __a ? pair<const _Tp&, const _Tp&>(__b, __a)
3316 template<
typename _Tp,
typename _Compare>
3318 minmax(
const _Tp& __a,
const _Tp& __b, _Compare __comp)
3324 template<
typename _ForwardIterator,
typename _Compare>
3326 __minmax_element(_ForwardIterator __first, _ForwardIterator __last,
3329 _ForwardIterator __next = __first;
3330 if (__first == __last
3331 || ++__next == __last)
3334 _ForwardIterator __min, __max;
3335 if (__comp(__next, __first))
3349 while (__first != __last)
3352 if (++__next == __last)
3354 if (__comp(__first, __min))
3356 else if (!__comp(__first, __max))
3361 if (__comp(__next, __first))
3363 if (__comp(__next, __min))
3365 if (!__comp(__first, __max))
3370 if (__comp(__first, __min))
3372 if (!__comp(__next, __max))
3394 template<
typename _ForwardIterator>
3396 minmax_element(_ForwardIterator __first, _ForwardIterator __last)
3399 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3400 __glibcxx_function_requires(_LessThanComparableConcept<
3401 typename iterator_traits<_ForwardIterator>::value_type>)
3402 __glibcxx_requires_valid_range(__first, __last);
3404 return std::__minmax_element(__first, __last,
3405 __gnu_cxx::__ops::__iter_less_iter());
3420 template<
typename _ForwardIterator,
typename _Compare>
3422 minmax_element(_ForwardIterator __first, _ForwardIterator __last,
3426 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3427 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3428 typename iterator_traits<_ForwardIterator>::value_type,
3429 typename iterator_traits<_ForwardIterator>::value_type>)
3430 __glibcxx_requires_valid_range(__first, __last);
3432 return std::__minmax_element(__first, __last,
3433 __gnu_cxx::__ops::__iter_comp_iter(__comp));
3437 template<
typename _Tp>
3439 min(initializer_list<_Tp> __l)
3442 template<
typename _Tp,
typename _Compare>
3444 min(initializer_list<_Tp> __l, _Compare __comp)
3447 template<
typename _Tp>
3449 max(initializer_list<_Tp> __l)
3452 template<
typename _Tp,
typename _Compare>
3454 max(initializer_list<_Tp> __l, _Compare __comp)
3457 template<
typename _Tp>
3459 minmax(initializer_list<_Tp> __l)
3466 template<
typename _Tp,
typename _Compare>
3468 minmax(initializer_list<_Tp> __l, _Compare __comp)
3475 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
3476 typename _BinaryPredicate>
3478 __is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3479 _ForwardIterator2 __first2, _BinaryPredicate __pred)
3483 for (; __first1 != __last1; ++__first1, ++__first2)
3484 if (!__pred(__first1, __first2))
3487 if (__first1 == __last1)
3492 _ForwardIterator2 __last2 = __first2;
3494 for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
3497 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)))
3501 = std::__count_if(__first2, __last2,
3502 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan));
3503 if (0 == __matches ||
3504 std::__count_if(__scan, __last1,
3505 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan))
3524 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
3526 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3527 _ForwardIterator2 __first2)
3530 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
3531 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
3532 __glibcxx_function_requires(_EqualOpConcept<
3533 typename iterator_traits<_ForwardIterator1>::value_type,
3534 typename iterator_traits<_ForwardIterator2>::value_type>)
3535 __glibcxx_requires_valid_range(__first1, __last1);
3537 return std::__is_permutation(__first1, __last1, __first2,
3538 __gnu_cxx::__ops::__iter_equal_to_iter());
3555 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
3556 typename _BinaryPredicate>
3558 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3559 _ForwardIterator2 __first2, _BinaryPredicate __pred)
3562 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
3563 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
3564 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
3565 typename iterator_traits<_ForwardIterator1>::value_type,
3566 typename iterator_traits<_ForwardIterator2>::value_type>)
3567 __glibcxx_requires_valid_range(__first1, __last1);
3569 return std::__is_permutation(__first1, __last1, __first2,
3570 __gnu_cxx::__ops::__iter_comp_iter(__pred));
3573 #if __cplusplus > 201103L 3574 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
3575 typename _BinaryPredicate>
3577 __is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3578 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
3579 _BinaryPredicate __pred)
3582 =
typename iterator_traits<_ForwardIterator1>::iterator_category;
3584 =
typename iterator_traits<_ForwardIterator2>::iterator_category;
3585 using _It1_is_RA = is_same<_Cat1, random_access_iterator_tag>;
3586 using _It2_is_RA = is_same<_Cat2, random_access_iterator_tag>;
3587 constexpr
bool __ra_iters = _It1_is_RA() && _It2_is_RA();
3598 for (; __first1 != __last1 && __first2 != __last2;
3599 ++__first1, ++__first2)
3600 if (!__pred(__first1, __first2))
3605 if (__first1 == __last1)
3612 if (__d1 == 0 && __d2 == 0)
3618 for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
3621 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)))
3624 auto __matches = std::__count_if(__first2, __last2,
3625 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan));
3627 || std::__count_if(__scan, __last1,
3628 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan))
3648 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
3650 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3651 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
3653 __glibcxx_requires_valid_range(__first1, __last1);
3654 __glibcxx_requires_valid_range(__first2, __last2);
3657 std::__is_permutation(__first1, __last1, __first2, __last2,
3658 __gnu_cxx::__ops::__iter_equal_to_iter());
3675 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
3676 typename _BinaryPredicate>
3678 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3679 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
3680 _BinaryPredicate __pred)
3682 __glibcxx_requires_valid_range(__first1, __last1);
3683 __glibcxx_requires_valid_range(__first2, __last2);
3685 return std::__is_permutation(__first1, __last1, __first2, __last2,
3686 __gnu_cxx::__ops::__iter_comp_iter(__pred));
3690 #ifdef _GLIBCXX_USE_C99_STDINT_TR1 3703 template<
typename _RandomAccessIterator,
3704 typename _UniformRandomNumberGenerator>
3706 shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
3707 _UniformRandomNumberGenerator&& __g)
3710 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
3711 _RandomAccessIterator>)
3712 __glibcxx_requires_valid_range(__first, __last);
3714 if (__first == __last)
3717 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
3720 typedef typename std::make_unsigned<_DistanceType>::type __ud_type;
3722 typedef typename __distr_type::param_type __p_type;
3725 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
3726 std::iter_swap(__i, __first + __d(__g, __p_type(0, __i - __first)));
3732 _GLIBCXX_END_NAMESPACE_VERSION
3734 _GLIBCXX_BEGIN_NAMESPACE_ALGO
3748 template<
typename _InputIterator,
typename _Function>
3750 for_each(_InputIterator __first, _InputIterator __last, _Function __f)
3753 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3754 __glibcxx_requires_valid_range(__first, __last);
3755 for (; __first != __last; ++__first)
3757 return _GLIBCXX_MOVE(__f);
3769 template<
typename _InputIterator,
typename _Tp>
3770 inline _InputIterator
3771 find(_InputIterator __first, _InputIterator __last,
3775 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3776 __glibcxx_function_requires(_EqualOpConcept<
3777 typename iterator_traits<_InputIterator>::value_type, _Tp>)
3778 __glibcxx_requires_valid_range(__first, __last);
3780 __gnu_cxx::__ops::__iter_equals_val(__val));
3793 template<
typename _InputIterator,
typename _Predicate>
3794 inline _InputIterator
3795 find_if(_InputIterator __first, _InputIterator __last,
3799 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3800 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
3801 typename iterator_traits<_InputIterator>::value_type>)
3802 __glibcxx_requires_valid_range(__first, __last);
3805 __gnu_cxx::__ops::__pred_iter(__pred));
3824 template<
typename _InputIterator,
typename _ForwardIterator>
3826 find_first_of(_InputIterator __first1, _InputIterator __last1,
3827 _ForwardIterator __first2, _ForwardIterator __last2)
3830 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3831 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3832 __glibcxx_function_requires(_EqualOpConcept<
3833 typename iterator_traits<_InputIterator>::value_type,
3834 typename iterator_traits<_ForwardIterator>::value_type>)
3835 __glibcxx_requires_valid_range(__first1, __last1);
3836 __glibcxx_requires_valid_range(__first2, __last2);
3838 for (; __first1 != __last1; ++__first1)
3839 for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
3840 if (*__first1 == *__iter)
3864 template<
typename _InputIterator,
typename _ForwardIterator,
3865 typename _BinaryPredicate>
3867 find_first_of(_InputIterator __first1, _InputIterator __last1,
3868 _ForwardIterator __first2, _ForwardIterator __last2,
3869 _BinaryPredicate __comp)
3872 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3873 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3874 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
3875 typename iterator_traits<_InputIterator>::value_type,
3876 typename iterator_traits<_ForwardIterator>::value_type>)
3877 __glibcxx_requires_valid_range(__first1, __last1);
3878 __glibcxx_requires_valid_range(__first2, __last2);
3880 for (; __first1 != __last1; ++__first1)
3881 for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
3882 if (__comp(*__first1, *__iter))
3896 template<
typename _ForwardIterator>
3897 inline _ForwardIterator
3898 adjacent_find(_ForwardIterator __first, _ForwardIterator __last)
3901 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3902 __glibcxx_function_requires(_EqualityComparableConcept<
3903 typename iterator_traits<_ForwardIterator>::value_type>)
3904 __glibcxx_requires_valid_range(__first, __last);
3906 return std::__adjacent_find(__first, __last,
3907 __gnu_cxx::__ops::__iter_equal_to_iter());
3921 template<
typename _ForwardIterator,
typename _BinaryPredicate>
3922 inline _ForwardIterator
3923 adjacent_find(_ForwardIterator __first, _ForwardIterator __last,
3924 _BinaryPredicate __binary_pred)
3927 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3928 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
3929 typename iterator_traits<_ForwardIterator>::value_type,
3930 typename iterator_traits<_ForwardIterator>::value_type>)
3931 __glibcxx_requires_valid_range(__first, __last);
3933 return std::__adjacent_find(__first, __last,
3934 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred));
3946 template<
typename _InputIterator,
typename _Tp>
3947 inline typename iterator_traits<_InputIterator>::difference_type
3948 count(_InputIterator __first, _InputIterator __last,
const _Tp& __value)
3951 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3952 __glibcxx_function_requires(_EqualOpConcept<
3953 typename iterator_traits<_InputIterator>::value_type, _Tp>)
3954 __glibcxx_requires_valid_range(__first, __last);
3956 return std::__count_if(__first, __last,
3957 __gnu_cxx::__ops::__iter_equals_val(__value));
3969 template<
typename _InputIterator,
typename _Predicate>
3970 inline typename iterator_traits<_InputIterator>::difference_type
3971 count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
3974 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3975 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
3976 typename iterator_traits<_InputIterator>::value_type>)
3977 __glibcxx_requires_valid_range(__first, __last);
3979 return std::__count_if(__first, __last,
3980 __gnu_cxx::__ops::__pred_iter(__pred));
4009 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
4010 inline _ForwardIterator1
4011 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
4012 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
4015 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
4016 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
4017 __glibcxx_function_requires(_EqualOpConcept<
4018 typename iterator_traits<_ForwardIterator1>::value_type,
4019 typename iterator_traits<_ForwardIterator2>::value_type>)
4020 __glibcxx_requires_valid_range(__first1, __last1);
4021 __glibcxx_requires_valid_range(__first2, __last2);
4023 return std::__search(__first1, __last1, __first2, __last2,
4024 __gnu_cxx::__ops::__iter_equal_to_iter());
4048 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
4049 typename _BinaryPredicate>
4050 inline _ForwardIterator1
4051 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
4052 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
4053 _BinaryPredicate __predicate)
4056 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
4057 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
4058 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4059 typename iterator_traits<_ForwardIterator1>::value_type,
4060 typename iterator_traits<_ForwardIterator2>::value_type>)
4061 __glibcxx_requires_valid_range(__first1, __last1);
4062 __glibcxx_requires_valid_range(__first2, __last2);
4064 return std::__search(__first1, __last1, __first2, __last2,
4065 __gnu_cxx::__ops::__iter_comp_iter(__predicate));
4083 template<
typename _ForwardIterator,
typename _Integer,
typename _Tp>
4084 inline _ForwardIterator
4085 search_n(_ForwardIterator __first, _ForwardIterator __last,
4086 _Integer __count,
const _Tp& __val)
4089 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4090 __glibcxx_function_requires(_EqualOpConcept<
4091 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
4092 __glibcxx_requires_valid_range(__first, __last);
4094 return std::__search_n(__first, __last, __count,
4095 __gnu_cxx::__ops::__iter_equals_val(__val));
4116 template<
typename _ForwardIterator,
typename _Integer,
typename _Tp,
4117 typename _BinaryPredicate>
4118 inline _ForwardIterator
4119 search_n(_ForwardIterator __first, _ForwardIterator __last,
4120 _Integer __count,
const _Tp& __val,
4121 _BinaryPredicate __binary_pred)
4124 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4125 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4126 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
4127 __glibcxx_requires_valid_range(__first, __last);
4129 return std::__search_n(__first, __last, __count,
4130 __gnu_cxx::__ops::__iter_comp_val(__binary_pred, __val));
4150 template<
typename _InputIterator,
typename _OutputIterator,
4151 typename _UnaryOperation>
4153 transform(_InputIterator __first, _InputIterator __last,
4154 _OutputIterator __result, _UnaryOperation __unary_op)
4157 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4158 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4160 __typeof__(__unary_op(*__first))>)
4161 __glibcxx_requires_valid_range(__first, __last);
4163 for (; __first != __last; ++__first, ++__result)
4164 *__result = __unary_op(*__first);
4187 template<
typename _InputIterator1,
typename _InputIterator2,
4188 typename _OutputIterator,
typename _BinaryOperation>
4190 transform(_InputIterator1 __first1, _InputIterator1 __last1,
4191 _InputIterator2 __first2, _OutputIterator __result,
4192 _BinaryOperation __binary_op)
4195 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4196 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4197 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4199 __typeof__(__binary_op(*__first1,*__first2))>)
4200 __glibcxx_requires_valid_range(__first1, __last1);
4202 for (; __first1 != __last1; ++__first1, ++__first2, ++__result)
4203 *__result = __binary_op(*__first1, *__first2);
4220 template<
typename _ForwardIterator,
typename _Tp>
4222 replace(_ForwardIterator __first, _ForwardIterator __last,
4223 const _Tp& __old_value,
const _Tp& __new_value)
4226 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4228 __glibcxx_function_requires(_EqualOpConcept<
4229 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
4230 __glibcxx_function_requires(_ConvertibleConcept<_Tp,
4231 typename iterator_traits<_ForwardIterator>::value_type>)
4232 __glibcxx_requires_valid_range(__first, __last);
4234 for (; __first != __last; ++__first)
4235 if (*__first == __old_value)
4236 *__first = __new_value;
4252 template<
typename _ForwardIterator,
typename _Predicate,
typename _Tp>
4254 replace_if(_ForwardIterator __first, _ForwardIterator __last,
4255 _Predicate __pred,
const _Tp& __new_value)
4258 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4260 __glibcxx_function_requires(_ConvertibleConcept<_Tp,
4261 typename iterator_traits<_ForwardIterator>::value_type>)
4262 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4263 typename iterator_traits<_ForwardIterator>::value_type>)
4264 __glibcxx_requires_valid_range(__first, __last);
4266 for (; __first != __last; ++__first)
4267 if (__pred(*__first))
4268 *__first = __new_value;
4284 template<
typename _ForwardIterator,
typename _Generator>
4286 generate(_ForwardIterator __first, _ForwardIterator __last,
4290 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4291 __glibcxx_function_requires(_GeneratorConcept<_Generator,
4292 typename iterator_traits<_ForwardIterator>::value_type>)
4293 __glibcxx_requires_valid_range(__first, __last);
4295 for (; __first != __last; ++__first)
4315 template<
typename _OutputIterator,
typename _Size,
typename _Generator>
4317 generate_n(_OutputIterator __first, _Size __n, _Generator __gen)
4320 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4322 __typeof__(__gen())>)
4324 for (__decltype(__n + 0) __niter = __n;
4325 __niter > 0; --__niter, ++__first)
4351 template<
typename _InputIterator,
typename _OutputIterator>
4352 inline _OutputIterator
4353 unique_copy(_InputIterator __first, _InputIterator __last,
4354 _OutputIterator __result)
4357 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4358 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4359 typename iterator_traits<_InputIterator>::value_type>)
4360 __glibcxx_function_requires(_EqualityComparableConcept<
4361 typename iterator_traits<_InputIterator>::value_type>)
4362 __glibcxx_requires_valid_range(__first, __last);
4364 if (__first == __last)
4367 __gnu_cxx::__ops::__iter_equal_to_iter(),
4391 template<
typename _InputIterator,
typename _OutputIterator,
4392 typename _BinaryPredicate>
4393 inline _OutputIterator
4394 unique_copy(_InputIterator __first, _InputIterator __last,
4395 _OutputIterator __result,
4396 _BinaryPredicate __binary_pred)
4399 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4400 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4401 typename iterator_traits<_InputIterator>::value_type>)
4402 __glibcxx_requires_valid_range(__first, __last);
4404 if (__first == __last)
4407 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred),
4423 template<
typename _RandomAccessIterator>
4425 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
4428 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4429 _RandomAccessIterator>)
4430 __glibcxx_requires_valid_range(__first, __last);
4432 if (__first != __last)
4433 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
4435 _RandomAccessIterator __j = __first
4436 + std::rand() % ((__i - __first) + 1);
4456 template<
typename _RandomAccessIterator,
typename _RandomNumberGenerator>
4458 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
4459 #
if __cplusplus >= 201103L
4460 _RandomNumberGenerator&& __rand)
4462 _RandomNumberGenerator& __rand)
4466 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4467 _RandomAccessIterator>)
4468 __glibcxx_requires_valid_range(__first, __last);
4470 if (__first == __last)
4472 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
4474 _RandomAccessIterator __j = __first + __rand((__i - __first) + 1);
4496 template<
typename _ForwardIterator,
typename _Predicate>
4497 inline _ForwardIterator
4498 partition(_ForwardIterator __first, _ForwardIterator __last,
4502 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4504 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4505 typename iterator_traits<_ForwardIterator>::value_type>)
4506 __glibcxx_requires_valid_range(__first, __last);
4529 template<
typename _RandomAccessIterator>
4531 partial_sort(_RandomAccessIterator __first,
4532 _RandomAccessIterator __middle,
4533 _RandomAccessIterator __last)
4536 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4537 _RandomAccessIterator>)
4538 __glibcxx_function_requires(_LessThanComparableConcept<
4539 typename iterator_traits<_RandomAccessIterator>::value_type>)
4540 __glibcxx_requires_valid_range(__first, __middle);
4541 __glibcxx_requires_valid_range(__middle, __last);
4543 std::__partial_sort(__first, __middle, __last,
4544 __gnu_cxx::__ops::__iter_less_iter());
4566 template<
typename _RandomAccessIterator,
typename _Compare>
4568 partial_sort(_RandomAccessIterator __first,
4569 _RandomAccessIterator __middle,
4570 _RandomAccessIterator __last,
4574 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4575 _RandomAccessIterator>)
4576 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4577 typename iterator_traits<_RandomAccessIterator>::value_type,
4578 typename iterator_traits<_RandomAccessIterator>::value_type>)
4579 __glibcxx_requires_valid_range(__first, __middle);
4580 __glibcxx_requires_valid_range(__middle, __last);
4582 std::__partial_sort(__first, __middle, __last,
4583 __gnu_cxx::__ops::__iter_comp_iter(__comp));
4601 template<
typename _RandomAccessIterator>
4603 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
4604 _RandomAccessIterator __last)
4607 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4608 _RandomAccessIterator>)
4609 __glibcxx_function_requires(_LessThanComparableConcept<
4610 typename iterator_traits<_RandomAccessIterator>::value_type>)
4611 __glibcxx_requires_valid_range(__first, __nth);
4612 __glibcxx_requires_valid_range(__nth, __last);
4614 if (__first == __last || __nth == __last)
4617 std::__introselect(__first, __nth, __last,
4619 __gnu_cxx::__ops::__iter_less_iter());
4639 template<
typename _RandomAccessIterator,
typename _Compare>
4641 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
4642 _RandomAccessIterator __last, _Compare __comp)
4645 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4646 _RandomAccessIterator>)
4647 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4648 typename iterator_traits<_RandomAccessIterator>::value_type,
4649 typename iterator_traits<_RandomAccessIterator>::value_type>)
4650 __glibcxx_requires_valid_range(__first, __nth);
4651 __glibcxx_requires_valid_range(__nth, __last);
4653 if (__first == __last || __nth == __last)
4656 std::__introselect(__first, __nth, __last,
4658 __gnu_cxx::__ops::__iter_comp_iter(__comp));
4675 template<
typename _RandomAccessIterator>
4677 sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
4680 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4681 _RandomAccessIterator>)
4682 __glibcxx_function_requires(_LessThanComparableConcept<
4683 typename iterator_traits<_RandomAccessIterator>::value_type>)
4684 __glibcxx_requires_valid_range(__first, __last);
4686 std::__sort(__first, __last, __gnu_cxx::__ops::__iter_less_iter());
4704 template<
typename _RandomAccessIterator,
typename _Compare>
4706 sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
4710 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4711 _RandomAccessIterator>)
4712 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4713 typename iterator_traits<_RandomAccessIterator>::value_type,
4714 typename iterator_traits<_RandomAccessIterator>::value_type>)
4715 __glibcxx_requires_valid_range(__first, __last);
4717 std::__sort(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
4720 template<
typename _InputIterator1,
typename _InputIterator2,
4721 typename _OutputIterator,
typename _Compare>
4723 __merge(_InputIterator1 __first1, _InputIterator1 __last1,
4724 _InputIterator2 __first2, _InputIterator2 __last2,
4725 _OutputIterator __result, _Compare __comp)
4727 while (__first1 != __last1 && __first2 != __last2)
4729 if (__comp(__first2, __first1))
4731 *__result = *__first2;
4736 *__result = *__first1;
4741 return std::copy(__first2, __last2,
4742 std::copy(__first1, __last1, __result));
4764 template<
typename _InputIterator1,
typename _InputIterator2,
4765 typename _OutputIterator>
4766 inline _OutputIterator
4767 merge(_InputIterator1 __first1, _InputIterator1 __last1,
4768 _InputIterator2 __first2, _InputIterator2 __last2,
4769 _OutputIterator __result)
4772 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4773 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4774 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4775 typename iterator_traits<_InputIterator1>::value_type>)
4776 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4777 typename iterator_traits<_InputIterator2>::value_type>)
4778 __glibcxx_function_requires(_LessThanOpConcept<
4779 typename iterator_traits<_InputIterator2>::value_type,
4780 typename iterator_traits<_InputIterator1>::value_type>)
4781 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
4782 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
4784 return _GLIBCXX_STD_A::__merge(__first1, __last1,
4785 __first2, __last2, __result,
4786 __gnu_cxx::__ops::__iter_less_iter());
4812 template<
typename _InputIterator1,
typename _InputIterator2,
4813 typename _OutputIterator,
typename _Compare>
4814 inline _OutputIterator
4815 merge(_InputIterator1 __first1, _InputIterator1 __last1,
4816 _InputIterator2 __first2, _InputIterator2 __last2,
4817 _OutputIterator __result, _Compare __comp)
4820 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4821 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4822 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4823 typename iterator_traits<_InputIterator1>::value_type>)
4824 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4825 typename iterator_traits<_InputIterator2>::value_type>)
4826 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4827 typename iterator_traits<_InputIterator2>::value_type,
4828 typename iterator_traits<_InputIterator1>::value_type>)
4829 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
4830 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
4832 return _GLIBCXX_STD_A::__merge(__first1, __last1,
4833 __first2, __last2, __result,
4834 __gnu_cxx::__ops::__iter_comp_iter(__comp));
4837 template<
typename _RandomAccessIterator,
typename _Compare>
4839 __stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
4842 typedef typename iterator_traits<_RandomAccessIterator>::value_type
4844 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
4848 _TmpBuf __buf(__first, __last);
4850 if (__buf.begin() == 0)
4853 std::__stable_sort_adaptive(__first, __last, __buf.begin(),
4854 _DistanceType(__buf.size()), __comp);
4874 template<
typename _RandomAccessIterator>
4876 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
4879 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4880 _RandomAccessIterator>)
4881 __glibcxx_function_requires(_LessThanComparableConcept<
4882 typename iterator_traits<_RandomAccessIterator>::value_type>)
4883 __glibcxx_requires_valid_range(__first, __last);
4885 _GLIBCXX_STD_A::__stable_sort(__first, __last,
4886 __gnu_cxx::__ops::__iter_less_iter());
4907 template<
typename _RandomAccessIterator,
typename _Compare>
4909 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
4913 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4914 _RandomAccessIterator>)
4915 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4916 typename iterator_traits<_RandomAccessIterator>::value_type,
4917 typename iterator_traits<_RandomAccessIterator>::value_type>)
4918 __glibcxx_requires_valid_range(__first, __last);
4920 _GLIBCXX_STD_A::__stable_sort(__first, __last,
4921 __gnu_cxx::__ops::__iter_comp_iter(__comp));
4924 template<
typename _InputIterator1,
typename _InputIterator2,
4925 typename _OutputIterator,
4928 __set_union(_InputIterator1 __first1, _InputIterator1 __last1,
4929 _InputIterator2 __first2, _InputIterator2 __last2,
4930 _OutputIterator __result, _Compare __comp)
4932 while (__first1 != __last1 && __first2 != __last2)
4934 if (__comp(__first1, __first2))
4936 *__result = *__first1;
4939 else if (__comp(__first2, __first1))
4941 *__result = *__first2;
4946 *__result = *__first1;
4952 return std::copy(__first2, __last2,
4953 std::copy(__first1, __last1, __result));
4974 template<
typename _InputIterator1,
typename _InputIterator2,
4975 typename _OutputIterator>
4976 inline _OutputIterator
4977 set_union(_InputIterator1 __first1, _InputIterator1 __last1,
4978 _InputIterator2 __first2, _InputIterator2 __last2,
4979 _OutputIterator __result)
4982 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4983 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4984 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4985 typename iterator_traits<_InputIterator1>::value_type>)
4986 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4987 typename iterator_traits<_InputIterator2>::value_type>)
4988 __glibcxx_function_requires(_LessThanOpConcept<
4989 typename iterator_traits<_InputIterator1>::value_type,
4990 typename iterator_traits<_InputIterator2>::value_type>)
4991 __glibcxx_function_requires(_LessThanOpConcept<
4992 typename iterator_traits<_InputIterator2>::value_type,
4993 typename iterator_traits<_InputIterator1>::value_type>)
4994 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
4995 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
4997 return _GLIBCXX_STD_A::__set_union(__first1, __last1,
4998 __first2, __last2, __result,
4999 __gnu_cxx::__ops::__iter_less_iter());
5021 template<
typename _InputIterator1,
typename _InputIterator2,
5022 typename _OutputIterator,
typename _Compare>
5023 inline _OutputIterator
5024 set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5025 _InputIterator2 __first2, _InputIterator2 __last2,
5026 _OutputIterator __result, _Compare __comp)
5029 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5030 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5031 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5032 typename iterator_traits<_InputIterator1>::value_type>)
5033 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5034 typename iterator_traits<_InputIterator2>::value_type>)
5035 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5036 typename iterator_traits<_InputIterator1>::value_type,
5037 typename iterator_traits<_InputIterator2>::value_type>)
5038 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5039 typename iterator_traits<_InputIterator2>::value_type,
5040 typename iterator_traits<_InputIterator1>::value_type>)
5041 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5042 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5044 return _GLIBCXX_STD_A::__set_union(__first1, __last1,
5045 __first2, __last2, __result,
5046 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5049 template<
typename _InputIterator1,
typename _InputIterator2,
5050 typename _OutputIterator,
5053 __set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5054 _InputIterator2 __first2, _InputIterator2 __last2,
5055 _OutputIterator __result, _Compare __comp)
5057 while (__first1 != __last1 && __first2 != __last2)
5058 if (__comp(__first1, __first2))
5060 else if (__comp(__first2, __first1))
5064 *__result = *__first1;
5089 template<
typename _InputIterator1,
typename _InputIterator2,
5090 typename _OutputIterator>
5091 inline _OutputIterator
5092 set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5093 _InputIterator2 __first2, _InputIterator2 __last2,
5094 _OutputIterator __result)
5097 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5098 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5099 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5100 typename iterator_traits<_InputIterator1>::value_type>)
5101 __glibcxx_function_requires(_LessThanOpConcept<
5102 typename iterator_traits<_InputIterator1>::value_type,
5103 typename iterator_traits<_InputIterator2>::value_type>)
5104 __glibcxx_function_requires(_LessThanOpConcept<
5105 typename iterator_traits<_InputIterator2>::value_type,
5106 typename iterator_traits<_InputIterator1>::value_type>)
5107 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5108 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5110 return _GLIBCXX_STD_A::__set_intersection(__first1, __last1,
5111 __first2, __last2, __result,
5112 __gnu_cxx::__ops::__iter_less_iter());
5135 template<
typename _InputIterator1,
typename _InputIterator2,
5136 typename _OutputIterator,
typename _Compare>
5137 inline _OutputIterator
5138 set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5139 _InputIterator2 __first2, _InputIterator2 __last2,
5140 _OutputIterator __result, _Compare __comp)
5143 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5144 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5145 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5146 typename iterator_traits<_InputIterator1>::value_type>)
5147 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5148 typename iterator_traits<_InputIterator1>::value_type,
5149 typename iterator_traits<_InputIterator2>::value_type>)
5150 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5151 typename iterator_traits<_InputIterator2>::value_type,
5152 typename iterator_traits<_InputIterator1>::value_type>)
5153 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5154 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5156 return _GLIBCXX_STD_A::__set_intersection(__first1, __last1,
5157 __first2, __last2, __result,
5158 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5161 template<
typename _InputIterator1,
typename _InputIterator2,
5162 typename _OutputIterator,
5165 __set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5166 _InputIterator2 __first2, _InputIterator2 __last2,
5167 _OutputIterator __result, _Compare __comp)
5169 while (__first1 != __last1 && __first2 != __last2)
5170 if (__comp(__first1, __first2))
5172 *__result = *__first1;
5176 else if (__comp(__first2, __first1))
5183 return std::copy(__first1, __last1, __result);
5205 template<
typename _InputIterator1,
typename _InputIterator2,
5206 typename _OutputIterator>
5207 inline _OutputIterator
5208 set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5209 _InputIterator2 __first2, _InputIterator2 __last2,
5210 _OutputIterator __result)
5213 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5214 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5215 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5216 typename iterator_traits<_InputIterator1>::value_type>)
5217 __glibcxx_function_requires(_LessThanOpConcept<
5218 typename iterator_traits<_InputIterator1>::value_type,
5219 typename iterator_traits<_InputIterator2>::value_type>)
5220 __glibcxx_function_requires(_LessThanOpConcept<
5221 typename iterator_traits<_InputIterator2>::value_type,
5222 typename iterator_traits<_InputIterator1>::value_type>)
5223 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5224 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5226 return _GLIBCXX_STD_A::__set_difference(__first1, __last1,
5227 __first2, __last2, __result,
5228 __gnu_cxx::__ops::__iter_less_iter());
5253 template<
typename _InputIterator1,
typename _InputIterator2,
5254 typename _OutputIterator,
typename _Compare>
5255 inline _OutputIterator
5256 set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5257 _InputIterator2 __first2, _InputIterator2 __last2,
5258 _OutputIterator __result, _Compare __comp)
5261 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5262 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5263 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5264 typename iterator_traits<_InputIterator1>::value_type>)
5265 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5266 typename iterator_traits<_InputIterator1>::value_type,
5267 typename iterator_traits<_InputIterator2>::value_type>)
5268 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5269 typename iterator_traits<_InputIterator2>::value_type,
5270 typename iterator_traits<_InputIterator1>::value_type>)
5271 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5272 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5274 return _GLIBCXX_STD_A::__set_difference(__first1, __last1,
5275 __first2, __last2, __result,
5276 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5279 template<
typename _InputIterator1,
typename _InputIterator2,
5280 typename _OutputIterator,
5283 __set_symmetric_difference(_InputIterator1 __first1,
5284 _InputIterator1 __last1,
5285 _InputIterator2 __first2,
5286 _InputIterator2 __last2,
5287 _OutputIterator __result,
5290 while (__first1 != __last1 && __first2 != __last2)
5291 if (__comp(__first1, __first2))
5293 *__result = *__first1;
5297 else if (__comp(__first2, __first1))
5299 *__result = *__first2;
5308 return std::copy(__first2, __last2,
5309 std::copy(__first1, __last1, __result));
5329 template<
typename _InputIterator1,
typename _InputIterator2,
5330 typename _OutputIterator>
5331 inline _OutputIterator
5332 set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5333 _InputIterator2 __first2, _InputIterator2 __last2,
5334 _OutputIterator __result)
5337 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5338 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5339 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5340 typename iterator_traits<_InputIterator1>::value_type>)
5341 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5342 typename iterator_traits<_InputIterator2>::value_type>)
5343 __glibcxx_function_requires(_LessThanOpConcept<
5344 typename iterator_traits<_InputIterator1>::value_type,
5345 typename iterator_traits<_InputIterator2>::value_type>)
5346 __glibcxx_function_requires(_LessThanOpConcept<
5347 typename iterator_traits<_InputIterator2>::value_type,
5348 typename iterator_traits<_InputIterator1>::value_type>)
5349 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5350 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5352 return _GLIBCXX_STD_A::__set_symmetric_difference(__first1, __last1,
5353 __first2, __last2, __result,
5354 __gnu_cxx::__ops::__iter_less_iter());
5377 template<
typename _InputIterator1,
typename _InputIterator2,
5378 typename _OutputIterator,
typename _Compare>
5379 inline _OutputIterator
5380 set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5381 _InputIterator2 __first2, _InputIterator2 __last2,
5382 _OutputIterator __result,
5386 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5387 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5388 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5389 typename iterator_traits<_InputIterator1>::value_type>)
5390 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5391 typename iterator_traits<_InputIterator2>::value_type>)
5392 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5393 typename iterator_traits<_InputIterator1>::value_type,
5394 typename iterator_traits<_InputIterator2>::value_type>)
5395 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5396 typename iterator_traits<_InputIterator2>::value_type,
5397 typename iterator_traits<_InputIterator1>::value_type>)
5398 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5399 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5401 return _GLIBCXX_STD_A::__set_symmetric_difference(__first1, __last1,
5402 __first2, __last2, __result,
5403 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5406 template<
typename _ForwardIterator,
typename _Compare>
5408 __min_element(_ForwardIterator __first, _ForwardIterator __last,
5411 if (__first == __last)
5413 _ForwardIterator __result = __first;
5414 while (++__first != __last)
5415 if (__comp(__first, __result))
5427 template<
typename _ForwardIterator>
5429 inline min_element(_ForwardIterator __first, _ForwardIterator __last)
5432 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5433 __glibcxx_function_requires(_LessThanComparableConcept<
5434 typename iterator_traits<_ForwardIterator>::value_type>)
5435 __glibcxx_requires_valid_range(__first, __last);
5437 return _GLIBCXX_STD_A::__min_element(__first, __last,
5438 __gnu_cxx::__ops::__iter_less_iter());
5450 template<
typename _ForwardIterator,
typename _Compare>
5451 inline _ForwardIterator
5452 min_element(_ForwardIterator __first, _ForwardIterator __last,
5456 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5457 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5458 typename iterator_traits<_ForwardIterator>::value_type,
5459 typename iterator_traits<_ForwardIterator>::value_type>)
5460 __glibcxx_requires_valid_range(__first, __last);
5462 return _GLIBCXX_STD_A::__min_element(__first, __last,
5463 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5466 template<
typename _ForwardIterator,
typename _Compare>
5468 __max_element(_ForwardIterator __first, _ForwardIterator __last,
5471 if (__first == __last)
return __first;
5472 _ForwardIterator __result = __first;
5473 while (++__first != __last)
5474 if (__comp(__result, __first))
5486 template<
typename _ForwardIterator>
5487 inline _ForwardIterator
5488 max_element(_ForwardIterator __first, _ForwardIterator __last)
5491 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5492 __glibcxx_function_requires(_LessThanComparableConcept<
5493 typename iterator_traits<_ForwardIterator>::value_type>)
5494 __glibcxx_requires_valid_range(__first, __last);
5496 return _GLIBCXX_STD_A::__max_element(__first, __last,
5497 __gnu_cxx::__ops::__iter_less_iter());
5509 template<
typename _ForwardIterator,
typename _Compare>
5510 inline _ForwardIterator
5511 max_element(_ForwardIterator __first, _ForwardIterator __last,
5515 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5516 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5517 typename iterator_traits<_ForwardIterator>::value_type,
5518 typename iterator_traits<_ForwardIterator>::value_type>)
5519 __glibcxx_requires_valid_range(__first, __last);
5521 return _GLIBCXX_STD_A::__max_element(__first, __last,
5522 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5525 _GLIBCXX_END_NAMESPACE_ALGO
void __inplace_stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
This is a helper function for the stable sorting routines.
void __merge_without_buffer(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last, _Distance __len1, _Distance __len2, _Compare __comp)
This is a helper function for the merge routines.
void __final_insertion_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
This is a helper function for the sort routine.
_InputIterator __find_if_not(_InputIterator __first, _InputIterator __last, _Predicate __pred)
Provided for stable_partition to use.
const _Tp & max(const _Tp &, const _Tp &)
This does what you think it does.
_BidirectionalIterator1 __rotate_adaptive(_BidirectionalIterator1 __first, _BidirectionalIterator1 __middle, _BidirectionalIterator1 __last, _Distance __len1, _Distance __len2, _BidirectionalIterator2 __buffer, _Distance __buffer_size)
This is a helper function for the merge routines.
_InputIterator __find_if(_InputIterator __first, _InputIterator __last, _Predicate __pred, input_iterator_tag)
This is an overload used by find algos for the Input Iterator case.
Uniform discrete distribution for random numbers. A discrete random distribution on the range with e...
_ForwardIterator __inplace_stable_partition(_ForwardIterator __first, _Predicate __pred, _Distance __len)
This is a helper function... Requires __len != 0 and !__pred(*__first), same as __stable_partition_ad...
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.
_InputIterator find_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
Find the first element in a sequence for which a predicate is true.
_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.
_T2 second
first is a copy of the first object
Forward iterators support a superset of input iterator operations.
_ForwardIterator min_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
Return the minimum element in a range using comparison functor.
void iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b)
Swaps the contents of two iterators.
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.
void swap(_Tp &, _Tp &) noexcept(__and_< is_nothrow_move_constructible< _Tp >, is_nothrow_move_assignable< _Tp >>::value)
Swaps two values.
_T1 first
second_type is the second bound type
void __reverse(_BidirectionalIterator __first, _BidirectionalIterator __last, bidirectional_iterator_tag)
ISO C++ entities toplevel namespace is std.
_RandomAccessIterator __unguarded_partition(_RandomAccessIterator __first, _RandomAccessIterator __last, _RandomAccessIterator __pivot, _Compare __comp)
This is a helper function...
void __introsort_loop(_RandomAccessIterator __first, _RandomAccessIterator __last, _Size __depth_limit, _Compare __comp)
This is a helper function for the sort routine.
_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.
_RandomAccessIterator __unguarded_partition_pivot(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
This is a helper function...
_ForwardIterator __search_n_aux(_ForwardIterator __first, _ForwardIterator __last, _Integer __count, _UnaryPredicate __unary_pred, std::forward_iterator_tag)
_InputIterator __find_if_not_n(_InputIterator __first, _Distance &__len, _Predicate __pred)
Like find_if_not(), but uses and updates a count of the remaining range length instead of comparing a...
iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
void __insertion_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
This is a helper function for the sort routine.
Bidirectional iterators support a superset of forward iterator operations.
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_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.
void advance(_InputIterator &__i, _Distance __n)
A generalization of pointer arithmetic.
void __merge_adaptive(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last, _Distance __len1, _Distance __len2, _Pointer __buffer, _Distance __buffer_size, _Compare __comp)
This is a helper function for the merge routines.
void __heap_select(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last, _Compare __comp)
This is a helper function for the sort routines.
_ForwardIterator __partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, forward_iterator_tag)
This is a helper function...
void __unguarded_insertion_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
This is a helper function for the sort routine.
bool none_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
Checks that a predicate is false for all the elements of a sequence.
const _Tp & min(const _Tp &, const _Tp &)
This does what you think it does.
_ForwardIterator2 swap_ranges(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2)
Swap the elements of two sequences.
Struct holding two objects of arbitrary type.
void rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last)
Rotate the elements of a sequence.
Marking output iterators.
void __unguarded_linear_insert(_RandomAccessIterator __last, _Compare __comp)
This is a helper function for the sort routine.
_OutputIterator __unique_copy(_ForwardIterator __first, _ForwardIterator __last, _OutputIterator __result, _BinaryPredicate __binary_pred, forward_iterator_tag, output_iterator_tag)
iterator begin()
As per Table mumble.
iterator_traits< _Iter >::iterator_category __iterator_category(const _Iter &)
size_type requested_size() const
Returns the size requested by the constructor; may be >size().
constexpr int __lg(int __n)
This is a helper function for the sort routines and for random.tcc.
void __rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last, forward_iterator_tag)
This is a helper function for the rotate algorithm.
pair< const _Tp &, const _Tp & > minmax(const _Tp &, const _Tp &)
Determines min and max at once as an ordered pair.
_EuclideanRingElement __gcd(_EuclideanRingElement __m, _EuclideanRingElement __n)
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.
_ForwardIterator max_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
Return the maximum element in a range using comparison functor.
size_type size() const
As per Table mumble.
_ForwardIterator is_sorted_until(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
Determines the end of a sorted sequence using comparison functor.