66 #ifdef __GXX_EXPERIMENTAL_CXX0X__
73 namespace std _GLIBCXX_VISIBILITY(default)
75 _GLIBCXX_BEGIN_NAMESPACE_VERSION
78 template<
typename _Iterator>
83 __glibcxx_function_requires(_LessThanComparableConcept<
84 typename iterator_traits<_Iterator>::value_type>)
102 template<
typename _Iterator,
typename _Compare>
108 __glibcxx_function_requires(_BinaryFunctionConcept<_Compare,
bool,
109 typename iterator_traits<_Iterator>::value_type,
110 typename iterator_traits<_Iterator>::value_type>)
112 if (__comp(*__a, *__b))
114 if (__comp(*__b, *__c))
116 else if (__comp(*__a, *__c))
119 else if (__comp(*__a, *__c))
121 else if (__comp(*__b, *__c))
130 template<
typename _InputIterator,
typename _Tp>
131 inline _InputIterator
132 __find(_InputIterator __first, _InputIterator __last,
135 while (__first != __last && !(*__first == __val))
141 template<
typename _InputIterator,
typename _Predicate>
142 inline _InputIterator
143 __find_if(_InputIterator __first, _InputIterator __last,
146 while (__first != __last && !
bool(__pred(*__first)))
152 template<
typename _RandomAccessIterator,
typename _Tp>
153 _RandomAccessIterator
154 __find(_RandomAccessIterator __first, _RandomAccessIterator __last,
157 typename iterator_traits<_RandomAccessIterator>::difference_type
158 __trip_count = (__last - __first) >> 2;
160 for (; __trip_count > 0; --__trip_count)
162 if (*__first == __val)
166 if (*__first == __val)
170 if (*__first == __val)
174 if (*__first == __val)
179 switch (__last - __first)
182 if (*__first == __val)
186 if (*__first == __val)
190 if (*__first == __val)
200 template<
typename _RandomAccessIterator,
typename _Predicate>
201 _RandomAccessIterator
202 __find_if(_RandomAccessIterator __first, _RandomAccessIterator __last,
205 typename iterator_traits<_RandomAccessIterator>::difference_type
206 __trip_count = (__last - __first) >> 2;
208 for (; __trip_count > 0; --__trip_count)
210 if (__pred(*__first))
214 if (__pred(*__first))
218 if (__pred(*__first))
222 if (__pred(*__first))
227 switch (__last - __first)
230 if (__pred(*__first))
234 if (__pred(*__first))
238 if (__pred(*__first))
248 template<
typename _InputIterator,
typename _Predicate>
249 inline _InputIterator
253 while (__first != __last &&
bool(__pred(*__first)))
259 template<
typename _RandomAccessIterator,
typename _Predicate>
260 _RandomAccessIterator
264 typename iterator_traits<_RandomAccessIterator>::difference_type
265 __trip_count = (__last - __first) >> 2;
267 for (; __trip_count > 0; --__trip_count)
269 if (!
bool(__pred(*__first)))
273 if (!
bool(__pred(*__first)))
277 if (!
bool(__pred(*__first)))
281 if (!
bool(__pred(*__first)))
286 switch (__last - __first)
289 if (!
bool(__pred(*__first)))
293 if (!
bool(__pred(*__first)))
297 if (!
bool(__pred(*__first)))
307 template<
typename _InputIterator,
typename _Predicate>
308 inline _InputIterator
319 template<
typename _InputIterator,
typename _Predicate,
typename _Distance>
323 for (; __len; --__len, ++__first)
324 if (!
bool(__pred(*__first)))
347 template<
typename _ForwardIterator,
typename _Integer,
typename _Tp>
349 __search_n(_ForwardIterator __first, _ForwardIterator __last,
350 _Integer __count,
const _Tp& __val,
353 __first = _GLIBCXX_STD_A::find(__first, __last, __val);
354 while (__first != __last)
356 typename iterator_traits<_ForwardIterator>::difference_type
358 _ForwardIterator __i = __first;
360 while (__i != __last && __n != 1 && *__i == __val)
369 __first = _GLIBCXX_STD_A::find(++__i, __last, __val);
379 template<
typename _RandomAccessIter,
typename _Integer,
typename _Tp>
381 __search_n(_RandomAccessIter __first, _RandomAccessIter __last,
382 _Integer __count,
const _Tp& __val,
386 typedef typename std::iterator_traits<_RandomAccessIter>::difference_type
389 _DistanceType __tailSize = __last - __first;
390 const _DistanceType __pattSize = __count;
392 if (__tailSize < __pattSize)
395 const _DistanceType __skipOffset = __pattSize - 1;
396 _RandomAccessIter __lookAhead = __first + __skipOffset;
397 __tailSize -= __pattSize;
403 while (!(*__lookAhead == __val))
405 if (__tailSize < __pattSize)
407 __lookAhead += __pattSize;
408 __tailSize -= __pattSize;
410 _DistanceType __remainder = __skipOffset;
411 for (_RandomAccessIter __backTrack = __lookAhead - 1;
412 *__backTrack == __val; --__backTrack)
414 if (--__remainder == 0)
415 return (__lookAhead - __skipOffset);
417 if (__remainder > __tailSize)
419 __lookAhead += __remainder;
420 __tailSize -= __remainder;
432 template<
typename _ForwardIterator,
typename _Integer,
typename _Tp,
433 typename _BinaryPredicate>
435 __search_n(_ForwardIterator __first, _ForwardIterator __last,
436 _Integer __count,
const _Tp& __val,
439 while (__first != __last && !
bool(__binary_pred(*__first, __val)))
442 while (__first != __last)
444 typename iterator_traits<_ForwardIterator>::difference_type
446 _ForwardIterator __i = __first;
448 while (__i != __last && __n != 1 &&
bool(__binary_pred(*__i, __val)))
458 while (__first != __last
459 && !
bool(__binary_pred(*__first, __val)))
471 template<
typename _RandomAccessIter,
typename _Integer,
typename _Tp,
472 typename _BinaryPredicate>
474 __search_n(_RandomAccessIter __first, _RandomAccessIter __last,
475 _Integer __count,
const _Tp& __val,
479 typedef typename std::iterator_traits<_RandomAccessIter>::difference_type
482 _DistanceType __tailSize = __last - __first;
483 const _DistanceType __pattSize = __count;
485 if (__tailSize < __pattSize)
488 const _DistanceType __skipOffset = __pattSize - 1;
489 _RandomAccessIter __lookAhead = __first + __skipOffset;
490 __tailSize -= __pattSize;
496 while (!
bool(__binary_pred(*__lookAhead, __val)))
498 if (__tailSize < __pattSize)
500 __lookAhead += __pattSize;
501 __tailSize -= __pattSize;
503 _DistanceType __remainder = __skipOffset;
504 for (_RandomAccessIter __backTrack = __lookAhead - 1;
505 __binary_pred(*__backTrack, __val); --__backTrack)
507 if (--__remainder == 0)
508 return (__lookAhead - __skipOffset);
510 if (__remainder > __tailSize)
512 __lookAhead += __remainder;
513 __tailSize -= __remainder;
518 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
520 __find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
521 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
522 forward_iterator_tag, forward_iterator_tag)
524 if (__first2 == __last2)
528 _ForwardIterator1 __result = __last1;
531 _ForwardIterator1 __new_result
532 = _GLIBCXX_STD_A::search(__first1, __last1, __first2, __last2);
533 if (__new_result == __last1)
537 __result = __new_result;
538 __first1 = __new_result;
545 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
546 typename _BinaryPredicate>
548 __find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
549 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
550 forward_iterator_tag, forward_iterator_tag,
551 _BinaryPredicate __comp)
553 if (__first2 == __last2)
557 _ForwardIterator1 __result = __last1;
560 _ForwardIterator1 __new_result
561 = _GLIBCXX_STD_A::search(__first1, __last1, __first2,
563 if (__new_result == __last1)
567 __result = __new_result;
568 __first1 = __new_result;
576 template<
typename _B
idirectionalIterator1,
typename _B
idirectionalIterator2>
577 _BidirectionalIterator1
578 __find_end(_BidirectionalIterator1 __first1,
579 _BidirectionalIterator1 __last1,
580 _BidirectionalIterator2 __first2,
581 _BidirectionalIterator2 __last2,
582 bidirectional_iterator_tag, bidirectional_iterator_tag)
585 __glibcxx_function_requires(_BidirectionalIteratorConcept<
586 _BidirectionalIterator1>)
587 __glibcxx_function_requires(_BidirectionalIteratorConcept<
588 _BidirectionalIterator2>)
590 typedef reverse_iterator<_BidirectionalIterator1> _RevIterator1;
591 typedef reverse_iterator<_BidirectionalIterator2> _RevIterator2;
593 _RevIterator1 __rlast1(__first1);
594 _RevIterator2 __rlast2(__first2);
595 _RevIterator1 __rresult = _GLIBCXX_STD_A::search(_RevIterator1(__last1),
597 _RevIterator2(__last2),
600 if (__rresult == __rlast1)
604 _BidirectionalIterator1 __result = __rresult.base();
610 template<
typename _BidirectionalIterator1,
typename _BidirectionalIterator2,
611 typename _BinaryPredicate>
612 _BidirectionalIterator1
613 __find_end(_BidirectionalIterator1 __first1,
614 _BidirectionalIterator1 __last1,
615 _BidirectionalIterator2 __first2,
616 _BidirectionalIterator2 __last2,
617 bidirectional_iterator_tag, bidirectional_iterator_tag,
618 _BinaryPredicate __comp)
621 __glibcxx_function_requires(_BidirectionalIteratorConcept<
622 _BidirectionalIterator1>)
623 __glibcxx_function_requires(_BidirectionalIteratorConcept<
624 _BidirectionalIterator2>)
626 typedef reverse_iterator<_BidirectionalIterator1> _RevIterator1;
627 typedef reverse_iterator<_BidirectionalIterator2> _RevIterator2;
629 _RevIterator1 __rlast1(__first1);
630 _RevIterator2 __rlast2(__first2);
631 _RevIterator1 __rresult = std::search(_RevIterator1(__last1), __rlast1,
632 _RevIterator2(__last2), __rlast2,
635 if (__rresult == __rlast1)
639 _BidirectionalIterator1 __result = __rresult.base();
671 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
672 inline _ForwardIterator1
673 find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
674 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
677 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
678 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
679 __glibcxx_function_requires(_EqualOpConcept<
680 typename iterator_traits<_ForwardIterator1>::value_type,
681 typename iterator_traits<_ForwardIterator2>::value_type>)
682 __glibcxx_requires_valid_range(__first1, __last1);
683 __glibcxx_requires_valid_range(__first2, __last2);
685 return std::__find_end(__first1, __last1, __first2, __last2,
718 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
719 typename _BinaryPredicate>
720 inline _ForwardIterator1
721 find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
722 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
723 _BinaryPredicate __comp)
726 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
727 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
728 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
729 typename iterator_traits<_ForwardIterator1>::value_type,
730 typename iterator_traits<_ForwardIterator2>::value_type>)
731 __glibcxx_requires_valid_range(__first1, __last1);
732 __glibcxx_requires_valid_range(__first2, __last2);
734 return std::__find_end(__first1, __last1, __first2, __last2,
740 #ifdef __GXX_EXPERIMENTAL_CXX0X__
753 template<
typename _InputIterator,
typename _Predicate>
755 all_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
770 template<
typename _InputIterator,
typename _Predicate>
772 none_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
773 {
return __last == _GLIBCXX_STD_A::find_if(__first, __last, __pred); }
788 template<
typename _InputIterator,
typename _Predicate>
790 any_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
803 template<
typename _InputIterator,
typename _Predicate>
804 inline _InputIterator
805 find_if_not(_InputIterator __first, _InputIterator __last,
809 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
810 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
811 typename iterator_traits<_InputIterator>::value_type>)
812 __glibcxx_requires_valid_range(__first, __last);
826 template<
typename _InputIterator,
typename _Predicate>
828 is_partitioned(_InputIterator __first, _InputIterator __last,
844 template<
typename _ForwardIterator,
typename _Predicate>
846 partition_point(_ForwardIterator __first, _ForwardIterator __last,
850 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
851 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
852 typename iterator_traits<_ForwardIterator>::value_type>)
855 __glibcxx_requires_valid_range(__first, __last);
857 typedef typename iterator_traits<_ForwardIterator>::difference_type
861 _DistanceType __half;
862 _ForwardIterator __middle;
869 if (__pred(*__middle))
873 __len = __len - __half - 1;
897 template<
typename _InputIterator,
typename _OutputIterator,
typename _Tp>
899 remove_copy(_InputIterator __first, _InputIterator __last,
900 _OutputIterator __result,
const _Tp& __value)
903 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
904 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
905 typename iterator_traits<_InputIterator>::value_type>)
906 __glibcxx_function_requires(_EqualOpConcept<
907 typename iterator_traits<_InputIterator>::value_type, _Tp>)
908 __glibcxx_requires_valid_range(__first, __last);
910 for (; __first != __last; ++__first)
911 if (!(*__first == __value))
913 *__result = *__first;
934 template<
typename _InputIterator,
typename _OutputIterator,
937 remove_copy_if(_InputIterator __first, _InputIterator __last,
938 _OutputIterator __result, _Predicate __pred)
941 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
942 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
943 typename iterator_traits<_InputIterator>::value_type>)
944 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
945 typename iterator_traits<_InputIterator>::value_type>)
946 __glibcxx_requires_valid_range(__first, __last);
948 for (; __first != __last; ++__first)
949 if (!
bool(__pred(*__first)))
951 *__result = *__first;
957 #ifdef __GXX_EXPERIMENTAL_CXX0X__
973 template<
typename _InputIterator,
typename _OutputIterator,
976 copy_if(_InputIterator __first, _InputIterator __last,
977 _OutputIterator __result, _Predicate __pred)
980 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
981 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
982 typename iterator_traits<_InputIterator>::value_type>)
983 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
984 typename iterator_traits<_InputIterator>::value_type>)
985 __glibcxx_requires_valid_range(__first, __last);
987 for (; __first != __last; ++__first)
988 if (__pred(*__first))
990 *__result = *__first;
997 template<
typename _InputIterator,
typename _Size,
typename _OutputIterator>
999 __copy_n(_InputIterator __first, _Size __n,
1000 _OutputIterator __result, input_iterator_tag)
1006 *__result = *__first;
1017 template<
typename _RandomAccessIterator,
typename _Size,
1018 typename _OutputIterator>
1019 inline _OutputIterator
1020 __copy_n(_RandomAccessIterator __first, _Size __n,
1021 _OutputIterator __result, random_access_iterator_tag)
1022 {
return std::copy(__first, __first + __n, __result); }
1037 template<
typename _InputIterator,
typename _Size,
typename _OutputIterator>
1038 inline _OutputIterator
1039 copy_n(_InputIterator __first, _Size __n, _OutputIterator __result)
1042 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1043 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1044 typename iterator_traits<_InputIterator>::value_type>)
1046 return std::__copy_n(__first, __n, __result,
1065 template<
typename _InputIterator,
typename _OutputIterator1,
1066 typename _OutputIterator2,
typename _Predicate>
1067 pair<_OutputIterator1, _OutputIterator2>
1068 partition_copy(_InputIterator __first, _InputIterator __last,
1069 _OutputIterator1 __out_true, _OutputIterator2 __out_false,
1073 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1074 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator1,
1075 typename iterator_traits<_InputIterator>::value_type>)
1076 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator2,
1077 typename iterator_traits<_InputIterator>::value_type>)
1078 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
1079 typename iterator_traits<_InputIterator>::value_type>)
1080 __glibcxx_requires_valid_range(__first, __last);
1082 for (; __first != __last; ++__first)
1083 if (__pred(*__first))
1085 *__out_true = *__first;
1090 *__out_false = *__first;
1115 template<
typename _ForwardIterator,
typename _Tp>
1117 remove(_ForwardIterator __first, _ForwardIterator __last,
1121 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1123 __glibcxx_function_requires(_EqualOpConcept<
1124 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
1125 __glibcxx_requires_valid_range(__first, __last);
1127 __first = _GLIBCXX_STD_A::find(__first, __last, __value);
1128 if(__first == __last)
1130 _ForwardIterator __result = __first;
1132 for(; __first != __last; ++__first)
1133 if(!(*__first == __value))
1135 *__result = _GLIBCXX_MOVE(*__first);
1158 template<
typename _ForwardIterator,
typename _Predicate>
1160 remove_if(_ForwardIterator __first, _ForwardIterator __last,
1164 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1166 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
1167 typename iterator_traits<_ForwardIterator>::value_type>)
1168 __glibcxx_requires_valid_range(__first, __last);
1170 __first = _GLIBCXX_STD_A::find_if(__first, __last, __pred);
1171 if(__first == __last)
1173 _ForwardIterator __result = __first;
1175 for(; __first != __last; ++__first)
1176 if(!
bool(__pred(*__first)))
1178 *__result = _GLIBCXX_MOVE(*__first);
1198 template<
typename _ForwardIterator>
1200 unique(_ForwardIterator __first, _ForwardIterator __last)
1203 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1205 __glibcxx_function_requires(_EqualityComparableConcept<
1206 typename iterator_traits<_ForwardIterator>::value_type>)
1207 __glibcxx_requires_valid_range(__first, __last);
1210 __first = _GLIBCXX_STD_A::adjacent_find(__first, __last);
1211 if (__first == __last)
1215 _ForwardIterator __dest = __first;
1217 while (++__first != __last)
1218 if (!(*__dest == *__first))
1219 *++__dest = _GLIBCXX_MOVE(*__first);
1238 template<
typename _ForwardIterator,
typename _BinaryPredicate>
1240 unique(_ForwardIterator __first, _ForwardIterator __last,
1241 _BinaryPredicate __binary_pred)
1244 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1246 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1247 typename iterator_traits<_ForwardIterator>::value_type,
1248 typename iterator_traits<_ForwardIterator>::value_type>)
1249 __glibcxx_requires_valid_range(__first, __last);
1252 __first = _GLIBCXX_STD_A::adjacent_find(__first, __last, __binary_pred);
1253 if (__first == __last)
1257 _ForwardIterator __dest = __first;
1259 while (++__first != __last)
1260 if (!
bool(__binary_pred(*__dest, *__first)))
1261 *++__dest = _GLIBCXX_MOVE(*__first);
1270 template<
typename _ForwardIterator,
typename _OutputIterator>
1273 _OutputIterator __result,
1277 _ForwardIterator __next = __first;
1278 *__result = *__first;
1279 while (++__next != __last)
1280 if (!(*__first == *__next))
1283 *++__result = *__first;
1293 template<
typename _InputIterator,
typename _OutputIterator>
1296 _OutputIterator __result,
1300 typename iterator_traits<_InputIterator>::value_type __value = *__first;
1301 *__result = __value;
1302 while (++__first != __last)
1303 if (!(__value == *__first))
1306 *++__result = __value;
1316 template<
typename _InputIterator,
typename _ForwardIterator>
1319 _ForwardIterator __result,
1323 *__result = *__first;
1324 while (++__first != __last)
1325 if (!(*__result == *__first))
1326 *++__result = *__first;
1336 template<
typename _ForwardIterator,
typename _OutputIterator,
1337 typename _BinaryPredicate>
1340 _OutputIterator __result, _BinaryPredicate __binary_pred,
1344 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1345 typename iterator_traits<_ForwardIterator>::value_type,
1346 typename iterator_traits<_ForwardIterator>::value_type>)
1348 _ForwardIterator __next = __first;
1349 *__result = *__first;
1350 while (++__next != __last)
1351 if (!
bool(__binary_pred(*__first, *__next)))
1354 *++__result = *__first;
1365 template<
typename _InputIterator,
typename _OutputIterator,
1366 typename _BinaryPredicate>
1369 _OutputIterator __result, _BinaryPredicate __binary_pred,
1373 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1374 typename iterator_traits<_InputIterator>::value_type,
1375 typename iterator_traits<_InputIterator>::value_type>)
1377 typename iterator_traits<_InputIterator>::value_type __value = *__first;
1378 *__result = __value;
1379 while (++__first != __last)
1380 if (!
bool(__binary_pred(__value, *__first)))
1383 *++__result = __value;
1394 template<
typename _InputIterator,
typename _ForwardIterator,
1395 typename _BinaryPredicate>
1398 _ForwardIterator __result, _BinaryPredicate __binary_pred,
1402 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1403 typename iterator_traits<_ForwardIterator>::value_type,
1404 typename iterator_traits<_InputIterator>::value_type>)
1406 *__result = *__first;
1407 while (++__first != __last)
1408 if (!
bool(__binary_pred(*__result, *__first)))
1409 *++__result = *__first;
1418 template<
typename _B
idirectionalIterator>
1420 __reverse(_BidirectionalIterator __first, _BidirectionalIterator __last,
1424 if (__first == __last || __first == --__last)
1438 template<
typename _RandomAccessIterator>
1440 __reverse(_RandomAccessIterator __first, _RandomAccessIterator __last,
1443 if (__first == __last)
1446 while (__first < __last)
1466 template<
typename _B
idirectionalIterator>
1468 reverse(_BidirectionalIterator __first, _BidirectionalIterator __last)
1471 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
1472 _BidirectionalIterator>)
1473 __glibcxx_requires_valid_range(__first, __last);
1493 template<
typename _B
idirectionalIterator,
typename _OutputIterator>
1495 reverse_copy(_BidirectionalIterator __first, _BidirectionalIterator __last,
1496 _OutputIterator __result)
1499 __glibcxx_function_requires(_BidirectionalIteratorConcept<
1500 _BidirectionalIterator>)
1501 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1502 typename iterator_traits<_BidirectionalIterator>::value_type>)
1503 __glibcxx_requires_valid_range(__first, __last);
1505 while (__first != __last)
1508 *__result = *__last;
1518 template<
typename _Eucl
ideanRingElement>
1519 _EuclideanRingElement
1520 __gcd(_EuclideanRingElement __m, _EuclideanRingElement __n)
1524 _EuclideanRingElement __t = __m % __n;
1532 template<
typename _ForwardIterator>
1535 _ForwardIterator __middle,
1536 _ForwardIterator __last,
1539 if (__first == __middle || __last == __middle)
1542 _ForwardIterator __first2 = __middle;
1548 if (__first == __middle)
1549 __middle = __first2;
1551 while (__first2 != __last);
1553 __first2 = __middle;
1555 while (__first2 != __last)
1560 if (__first == __middle)
1561 __middle = __first2;
1562 else if (__first2 == __last)
1563 __first2 = __middle;
1568 template<
typename _B
idirectionalIterator>
1571 _BidirectionalIterator __middle,
1572 _BidirectionalIterator __last,
1576 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
1577 _BidirectionalIterator>)
1579 if (__first == __middle || __last == __middle)
1585 while (__first != __middle && __middle != __last)
1591 if (__first == __middle)
1598 template<
typename _RandomAccessIterator>
1601 _RandomAccessIterator __middle,
1602 _RandomAccessIterator __last,
1606 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
1607 _RandomAccessIterator>)
1609 if (__first == __middle || __last == __middle)
1612 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
1614 typedef typename iterator_traits<_RandomAccessIterator>::value_type
1617 _Distance __n = __last - __first;
1618 _Distance __k = __middle - __first;
1620 if (__k == __n - __k)
1626 _RandomAccessIterator __p = __first;
1630 if (__k < __n - __k)
1632 if (__is_pod(_ValueType) && __k == 1)
1634 _ValueType __t = _GLIBCXX_MOVE(*__p);
1635 _GLIBCXX_MOVE3(__p + 1, __p + __n, __p);
1636 *(__p + __n - 1) = _GLIBCXX_MOVE(__t);
1639 _RandomAccessIterator __q = __p + __k;
1640 for (_Distance __i = 0; __i < __n - __k; ++ __i)
1649 std::swap(__n, __k);
1655 if (__is_pod(_ValueType) && __k == 1)
1657 _ValueType __t = _GLIBCXX_MOVE(*(__p + __n - 1));
1658 _GLIBCXX_MOVE_BACKWARD3(__p, __p + __n - 1, __p + __n);
1659 *__p = _GLIBCXX_MOVE(__t);
1662 _RandomAccessIterator __q = __p + __n;
1664 for (_Distance __i = 0; __i < __n - __k; ++ __i)
1673 std::swap(__n, __k);
1699 template<
typename _ForwardIterator>
1701 rotate(_ForwardIterator __first, _ForwardIterator __middle,
1702 _ForwardIterator __last)
1705 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1707 __glibcxx_requires_valid_range(__first, __middle);
1708 __glibcxx_requires_valid_range(__middle, __last);
1710 typedef typename iterator_traits<_ForwardIterator>::iterator_category
1735 template<
typename _ForwardIterator,
typename _OutputIterator>
1737 rotate_copy(_ForwardIterator __first, _ForwardIterator __middle,
1738 _ForwardIterator __last, _OutputIterator __result)
1741 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
1742 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1743 typename iterator_traits<_ForwardIterator>::value_type>)
1744 __glibcxx_requires_valid_range(__first, __middle);
1745 __glibcxx_requires_valid_range(__middle, __last);
1747 return std::copy(__first, __middle,
1748 std::copy(__middle, __last, __result));
1752 template<
typename _ForwardIterator,
typename _Predicate>
1757 if (__first == __last)
1760 while (__pred(*__first))
1761 if (++__first == __last)
1764 _ForwardIterator __next = __first;
1766 while (++__next != __last)
1767 if (__pred(*__next))
1777 template<
typename _B
idirectionalIterator,
typename _Predicate>
1778 _BidirectionalIterator
1779 __partition(_BidirectionalIterator __first, _BidirectionalIterator __last,
1785 if (__first == __last)
1787 else if (__pred(*__first))
1793 if (__first == __last)
1795 else if (!
bool(__pred(*__last)))
1809 template<
typename _ForwardIterator,
typename _Predicate,
typename _Distance>
1812 _Predicate __pred, _Distance __len)
1816 _ForwardIterator __middle = __first;
1818 _ForwardIterator __left_split =
1822 _Distance __right_len = __len - __len / 2;
1823 _ForwardIterator __right_split =
1829 std::rotate(__left_split, __middle, __right_split);
1831 return __left_split;
1840 template<
typename _ForwardIterator,
typename _Pointer,
typename _Predicate,
1844 _ForwardIterator __last,
1845 _Predicate __pred, _Distance __len,
1847 _Distance __buffer_size)
1849 if (__len <= __buffer_size)
1851 _ForwardIterator __result1 = __first;
1852 _Pointer __result2 = __buffer;
1856 *__result2 = _GLIBCXX_MOVE(*__first);
1859 for (; __first != __last; ++__first)
1860 if (__pred(*__first))
1862 *__result1 = _GLIBCXX_MOVE(*__first);
1867 *__result2 = _GLIBCXX_MOVE(*__first);
1870 _GLIBCXX_MOVE3(__buffer, __result2, __result1);
1875 _ForwardIterator __middle = __first;
1877 _ForwardIterator __left_split =
1879 __len / 2, __buffer,
1883 _Distance __right_len = __len - __len / 2;
1884 _ForwardIterator __right_split =
1890 __buffer, __buffer_size);
1891 std::rotate(__left_split, __middle, __right_split);
1893 return __left_split;
1914 template<
typename _ForwardIterator,
typename _Predicate>
1916 stable_partition(_ForwardIterator __first, _ForwardIterator __last,
1920 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1922 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
1923 typename iterator_traits<_ForwardIterator>::value_type>)
1924 __glibcxx_requires_valid_range(__first, __last);
1928 if (__first == __last)
1932 typedef typename iterator_traits<_ForwardIterator>::value_type
1934 typedef typename iterator_traits<_ForwardIterator>::difference_type
1939 if (__buf.
size() > 0)
1944 _DistanceType(__buf.
size()));
1953 template<
typename _RandomAccessIterator>
1956 _RandomAccessIterator __middle,
1957 _RandomAccessIterator __last)
1960 for (_RandomAccessIterator __i = __middle; __i < __last; ++__i)
1961 if (*__i < *__first)
1962 std::__pop_heap(__first, __middle, __i);
1966 template<
typename _RandomAccessIterator,
typename _Compare>
1969 _RandomAccessIterator __middle,
1970 _RandomAccessIterator __last, _Compare __comp)
1973 for (_RandomAccessIterator __i = __middle; __i < __last; ++__i)
1974 if (__comp(*__i, *__first))
1975 std::__pop_heap(__first, __middle, __i, __comp);
1998 template<
typename _InputIterator,
typename _RandomAccessIterator>
1999 _RandomAccessIterator
2000 partial_sort_copy(_InputIterator __first, _InputIterator __last,
2001 _RandomAccessIterator __result_first,
2002 _RandomAccessIterator __result_last)
2004 typedef typename iterator_traits<_InputIterator>::value_type
2006 typedef typename iterator_traits<_RandomAccessIterator>::value_type
2008 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
2012 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
2013 __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
2015 __glibcxx_function_requires(_LessThanOpConcept<_InputValueType,
2017 __glibcxx_function_requires(_LessThanComparableConcept<_OutputValueType>)
2018 __glibcxx_requires_valid_range(__first, __last);
2019 __glibcxx_requires_valid_range(__result_first, __result_last);
2021 if (__result_first == __result_last)
2022 return __result_last;
2023 _RandomAccessIterator __result_real_last = __result_first;
2024 while(__first != __last && __result_real_last != __result_last)
2026 *__result_real_last = *__first;
2027 ++__result_real_last;
2031 while (__first != __last)
2033 if (*__first < *__result_first)
2034 std::__adjust_heap(__result_first, _DistanceType(0),
2035 _DistanceType(__result_real_last
2037 _InputValueType(*__first));
2041 return __result_real_last;
2064 template<
typename _InputIterator,
typename _RandomAccessIterator,
typename _Compare>
2065 _RandomAccessIterator
2066 partial_sort_copy(_InputIterator __first, _InputIterator __last,
2067 _RandomAccessIterator __result_first,
2068 _RandomAccessIterator __result_last,
2071 typedef typename iterator_traits<_InputIterator>::value_type
2073 typedef typename iterator_traits<_RandomAccessIterator>::value_type
2075 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
2079 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
2080 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
2081 _RandomAccessIterator>)
2082 __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
2084 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2085 _InputValueType, _OutputValueType>)
2086 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2087 _OutputValueType, _OutputValueType>)
2088 __glibcxx_requires_valid_range(__first, __last);
2089 __glibcxx_requires_valid_range(__result_first, __result_last);
2091 if (__result_first == __result_last)
2092 return __result_last;
2093 _RandomAccessIterator __result_real_last = __result_first;
2094 while(__first != __last && __result_real_last != __result_last)
2096 *__result_real_last = *__first;
2097 ++__result_real_last;
2101 while (__first != __last)
2103 if (__comp(*__first, *__result_first))
2104 std::__adjust_heap(__result_first, _DistanceType(0),
2105 _DistanceType(__result_real_last
2107 _InputValueType(*__first),
2112 return __result_real_last;
2116 template<
typename _RandomAccessIterator>
2120 typename iterator_traits<_RandomAccessIterator>::value_type
2121 __val = _GLIBCXX_MOVE(*__last);
2122 _RandomAccessIterator __next = __last;
2124 while (__val < *__next)
2126 *__last = _GLIBCXX_MOVE(*__next);
2130 *__last = _GLIBCXX_MOVE(__val);
2134 template<
typename _RandomAccessIterator,
typename _Compare>
2139 typename iterator_traits<_RandomAccessIterator>::value_type
2140 __val = _GLIBCXX_MOVE(*__last);
2141 _RandomAccessIterator __next = __last;
2143 while (__comp(__val, *__next))
2145 *__last = _GLIBCXX_MOVE(*__next);
2149 *__last = _GLIBCXX_MOVE(__val);
2153 template<
typename _RandomAccessIterator>
2156 _RandomAccessIterator __last)
2158 if (__first == __last)
2161 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
2163 if (*__i < *__first)
2165 typename iterator_traits<_RandomAccessIterator>::value_type
2166 __val = _GLIBCXX_MOVE(*__i);
2167 _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1);
2168 *__first = _GLIBCXX_MOVE(__val);
2176 template<
typename _RandomAccessIterator,
typename _Compare>
2179 _RandomAccessIterator __last, _Compare __comp)
2181 if (__first == __last)
return;
2183 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
2185 if (__comp(*__i, *__first))
2187 typename iterator_traits<_RandomAccessIterator>::value_type
2188 __val = _GLIBCXX_MOVE(*__i);
2189 _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1);
2190 *__first = _GLIBCXX_MOVE(__val);
2198 template<
typename _RandomAccessIterator>
2201 _RandomAccessIterator __last)
2203 typedef typename iterator_traits<_RandomAccessIterator>::value_type
2206 for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
2211 template<
typename _RandomAccessIterator,
typename _Compare>
2214 _RandomAccessIterator __last, _Compare __comp)
2216 typedef typename iterator_traits<_RandomAccessIterator>::value_type
2219 for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
2227 enum { _S_threshold = 16 };
2230 template<
typename _RandomAccessIterator>
2233 _RandomAccessIterator __last)
2235 if (__last - __first >
int(_S_threshold))
2245 template<
typename _RandomAccessIterator,
typename _Compare>
2248 _RandomAccessIterator __last, _Compare __comp)
2250 if (__last - __first >
int(_S_threshold))
2261 template<
typename _RandomAccessIterator,
typename _Tp>
2262 _RandomAccessIterator
2264 _RandomAccessIterator __last,
const _Tp& __pivot)
2268 while (*__first < __pivot)
2271 while (__pivot < *__last)
2273 if (!(__first < __last))
2281 template<
typename _RandomAccessIterator,
typename _Tp,
typename _Compare>
2282 _RandomAccessIterator
2284 _RandomAccessIterator __last,
2285 const _Tp& __pivot, _Compare __comp)
2289 while (__comp(*__first, __pivot))
2292 while (__comp(__pivot, *__last))
2294 if (!(__first < __last))
2302 template<
typename _RandomAccessIterator>
2303 inline _RandomAccessIterator
2305 _RandomAccessIterator __last)
2307 _RandomAccessIterator __mid = __first + (__last - __first) / 2;
2314 template<
typename _RandomAccessIterator,
typename _Compare>
2315 inline _RandomAccessIterator
2317 _RandomAccessIterator __last, _Compare __comp)
2319 _RandomAccessIterator __mid = __first + (__last - __first) / 2;
2325 template<
typename _RandomAccessIterator,
typename _Size>
2328 _RandomAccessIterator __last,
2329 _Size __depth_limit)
2331 while (__last - __first >
int(_S_threshold))
2333 if (__depth_limit == 0)
2335 _GLIBCXX_STD_A::partial_sort(__first, __last, __last);
2339 _RandomAccessIterator __cut =
2347 template<
typename _RandomAccessIterator,
typename _Size,
typename _Compare>
2350 _RandomAccessIterator __last,
2351 _Size __depth_limit, _Compare __comp)
2353 while (__last - __first >
int(_S_threshold))
2355 if (__depth_limit == 0)
2357 _GLIBCXX_STD_A::partial_sort(__first, __last, __last, __comp);
2361 _RandomAccessIterator __cut =
2370 template<
typename _RandomAccessIterator,
typename _Size>
2372 __introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth,
2373 _RandomAccessIterator __last, _Size __depth_limit)
2375 typedef typename iterator_traits<_RandomAccessIterator>::value_type
2378 while (__last - __first > 3)
2380 if (__depth_limit == 0)
2385 std::iter_swap(__first, __nth);
2389 _RandomAccessIterator __cut =
2399 template<
typename _RandomAccessIterator,
typename _Size,
typename _Compare>
2401 __introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth,
2402 _RandomAccessIterator __last, _Size __depth_limit,
2405 typedef typename iterator_traits<_RandomAccessIterator>::value_type
2408 while (__last - __first > 3)
2410 if (__depth_limit == 0)
2418 _RandomAccessIterator __cut =
2448 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2450 lower_bound(_ForwardIterator __first, _ForwardIterator __last,
2451 const _Tp& __val, _Compare __comp)
2453 typedef typename iterator_traits<_ForwardIterator>::value_type
2455 typedef typename iterator_traits<_ForwardIterator>::difference_type
2459 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2460 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2462 __glibcxx_requires_partitioned_lower_pred(__first, __last,
2469 _DistanceType __half = __len >> 1;
2470 _ForwardIterator __middle = __first;
2472 if (__comp(*__middle, __val))
2476 __len = __len - __half - 1;
2495 template<
typename _ForwardIterator,
typename _Tp>
2497 upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2500 typedef typename iterator_traits<_ForwardIterator>::value_type
2502 typedef typename iterator_traits<_ForwardIterator>::difference_type
2506 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2507 __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>)
2508 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2514 _DistanceType __half = __len >> 1;
2515 _ForwardIterator __middle = __first;
2517 if (__val < *__middle)
2523 __len = __len - __half - 1;
2544 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2546 upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2547 const _Tp& __val, _Compare __comp)
2549 typedef typename iterator_traits<_ForwardIterator>::value_type
2551 typedef typename iterator_traits<_ForwardIterator>::difference_type
2555 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2556 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2558 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2565 _DistanceType __half = __len >> 1;
2566 _ForwardIterator __middle = __first;
2568 if (__comp(__val, *__middle))
2574 __len = __len - __half - 1;
2597 template<
typename _ForwardIterator,
typename _Tp>
2598 pair<_ForwardIterator, _ForwardIterator>
2599 equal_range(_ForwardIterator __first, _ForwardIterator __last,
2602 typedef typename iterator_traits<_ForwardIterator>::value_type
2604 typedef typename iterator_traits<_ForwardIterator>::difference_type
2608 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2609 __glibcxx_function_requires(_LessThanOpConcept<_ValueType, _Tp>)
2610 __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>)
2611 __glibcxx_requires_partitioned_lower(__first, __last, __val);
2612 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2618 _DistanceType __half = __len >> 1;
2619 _ForwardIterator __middle = __first;
2621 if (*__middle < __val)
2625 __len = __len - __half - 1;
2627 else if (__val < *__middle)
2659 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2660 pair<_ForwardIterator, _ForwardIterator>
2661 equal_range(_ForwardIterator __first, _ForwardIterator __last,
2662 const _Tp& __val, _Compare __comp)
2664 typedef typename iterator_traits<_ForwardIterator>::value_type
2666 typedef typename iterator_traits<_ForwardIterator>::difference_type
2670 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2671 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2673 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2675 __glibcxx_requires_partitioned_lower_pred(__first, __last,
2677 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2684 _DistanceType __half = __len >> 1;
2685 _ForwardIterator __middle = __first;
2687 if (__comp(*__middle, __val))
2691 __len = __len - __half - 1;
2693 else if (__comp(__val, *__middle))
2720 template<
typename _ForwardIterator,
typename _Tp>
2722 binary_search(_ForwardIterator __first, _ForwardIterator __last,
2725 typedef typename iterator_traits<_ForwardIterator>::value_type
2729 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2730 __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>)
2731 __glibcxx_requires_partitioned_lower(__first, __last, __val);
2732 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2735 return __i != __last && !(__val < *__i);
2753 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2755 binary_search(_ForwardIterator __first, _ForwardIterator __last,
2756 const _Tp& __val, _Compare __comp)
2758 typedef typename iterator_traits<_ForwardIterator>::value_type
2762 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2763 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2765 __glibcxx_requires_partitioned_lower_pred(__first, __last,
2767 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2771 return __i != __last && !bool(__comp(__val, *__i));
2777 template<
typename _InputIterator1,
typename _InputIterator2,
2778 typename _OutputIterator>
2781 _InputIterator2 __first2, _InputIterator2 __last2,
2782 _OutputIterator __result)
2784 while (__first1 != __last1 && __first2 != __last2)
2786 if (*__first2 < *__first1)
2788 *__result = _GLIBCXX_MOVE(*__first2);
2793 *__result = _GLIBCXX_MOVE(*__first1);
2798 if (__first1 != __last1)
2799 _GLIBCXX_MOVE3(__first1, __last1, __result);
2803 template<
typename _InputIterator1,
typename _InputIterator2,
2804 typename _OutputIterator,
typename _Compare>
2807 _InputIterator2 __first2, _InputIterator2 __last2,
2808 _OutputIterator __result, _Compare __comp)
2810 while (__first1 != __last1 && __first2 != __last2)
2812 if (__comp(*__first2, *__first1))
2814 *__result = _GLIBCXX_MOVE(*__first2);
2819 *__result = _GLIBCXX_MOVE(*__first1);
2824 if (__first1 != __last1)
2825 _GLIBCXX_MOVE3(__first1, __last1, __result);
2829 template<
typename _BidirectionalIterator1,
typename _BidirectionalIterator2,
2830 typename _BidirectionalIterator3>
2833 _BidirectionalIterator1 __last1,
2834 _BidirectionalIterator2 __first2,
2835 _BidirectionalIterator2 __last2,
2836 _BidirectionalIterator3 __result)
2838 if (__first1 == __last1)
2840 _GLIBCXX_MOVE_BACKWARD3(__first2, __last2, __result);
2843 else if (__first2 == __last2)
2850 if (*__last2 < *__last1)
2852 *--__result = _GLIBCXX_MOVE(*__last1);
2853 if (__first1 == __last1)
2855 _GLIBCXX_MOVE_BACKWARD3(__first2, ++__last2, __result);
2862 *--__result = _GLIBCXX_MOVE(*__last2);
2863 if (__first2 == __last2)
2871 template<
typename _BidirectionalIterator1,
typename _BidirectionalIterator2,
2872 typename _BidirectionalIterator3,
typename _Compare>
2875 _BidirectionalIterator1 __last1,
2876 _BidirectionalIterator2 __first2,
2877 _BidirectionalIterator2 __last2,
2878 _BidirectionalIterator3 __result,
2881 if (__first1 == __last1)
2883 _GLIBCXX_MOVE_BACKWARD3(__first2, __last2, __result);
2886 else if (__first2 == __last2)
2893 if (__comp(*__last2, *__last1))
2895 *--__result = _GLIBCXX_MOVE(*__last1);
2896 if (__first1 == __last1)
2898 _GLIBCXX_MOVE_BACKWARD3(__first2, ++__last2, __result);
2905 *--__result = _GLIBCXX_MOVE(*__last2);
2906 if (__first2 == __last2)
2914 template<
typename _BidirectionalIterator1,
typename _BidirectionalIterator2,
2916 _BidirectionalIterator1
2918 _BidirectionalIterator1 __middle,
2919 _BidirectionalIterator1 __last,
2920 _Distance __len1, _Distance __len2,
2921 _BidirectionalIterator2 __buffer,
2922 _Distance __buffer_size)
2924 _BidirectionalIterator2 __buffer_end;
2925 if (__len1 > __len2 && __len2 <= __buffer_size)
2929 __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
2930 _GLIBCXX_MOVE_BACKWARD3(__first, __middle, __last);
2931 return _GLIBCXX_MOVE3(__buffer, __buffer_end, __first);
2936 else if (__len1 <= __buffer_size)
2940 __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
2941 _GLIBCXX_MOVE3(__middle, __last, __first);
2942 return _GLIBCXX_MOVE_BACKWARD3(__buffer, __buffer_end, __last);
2956 template<
typename _BidirectionalIterator,
typename _Distance,
2960 _BidirectionalIterator __middle,
2961 _BidirectionalIterator __last,
2962 _Distance __len1, _Distance __len2,
2963 _Pointer __buffer, _Distance __buffer_size)
2965 if (__len1 <= __len2 && __len1 <= __buffer_size)
2967 _Pointer __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
2971 else if (__len2 <= __buffer_size)
2973 _Pointer __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
2975 __buffer_end, __last);
2979 _BidirectionalIterator __first_cut = __first;
2980 _BidirectionalIterator __second_cut = __middle;
2981 _Distance __len11 = 0;
2982 _Distance __len22 = 0;
2983 if (__len1 > __len2)
2985 __len11 = __len1 / 2;
2993 __len22 = __len2 / 2;
2999 _BidirectionalIterator __new_middle =
3001 __len1 - __len11, __len22, __buffer,
3004 __len22, __buffer, __buffer_size);
3007 __len2 - __len22, __buffer, __buffer_size);
3012 template<
typename _BidirectionalIterator,
typename _Distance,
3013 typename _Pointer,
typename _Compare>
3016 _BidirectionalIterator __middle,
3017 _BidirectionalIterator __last,
3018 _Distance __len1, _Distance __len2,
3019 _Pointer __buffer, _Distance __buffer_size,
3022 if (__len1 <= __len2 && __len1 <= __buffer_size)
3024 _Pointer __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
3028 else if (__len2 <= __buffer_size)
3030 _Pointer __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
3032 __buffer_end, __last, __comp);
3036 _BidirectionalIterator __first_cut = __first;
3037 _BidirectionalIterator __second_cut = __middle;
3038 _Distance __len11 = 0;
3039 _Distance __len22 = 0;
3040 if (__len1 > __len2)
3042 __len11 = __len1 / 2;
3050 __len22 = __len2 / 2;
3056 _BidirectionalIterator __new_middle =
3058 __len1 - __len11, __len22, __buffer,
3061 __len22, __buffer, __buffer_size, __comp);
3064 __len2 - __len22, __buffer,
3065 __buffer_size, __comp);
3070 template<
typename _B
idirectionalIterator,
typename _Distance>
3073 _BidirectionalIterator __middle,
3074 _BidirectionalIterator __last,
3075 _Distance __len1, _Distance __len2)
3077 if (__len1 == 0 || __len2 == 0)
3079 if (__len1 + __len2 == 2)
3081 if (*__middle < *__first)
3085 _BidirectionalIterator __first_cut = __first;
3086 _BidirectionalIterator __second_cut = __middle;
3087 _Distance __len11 = 0;
3088 _Distance __len22 = 0;
3089 if (__len1 > __len2)
3091 __len11 = __len1 / 2;
3098 __len22 = __len2 / 2;
3104 _BidirectionalIterator __new_middle = __first_cut;
3109 __len1 - __len11, __len2 - __len22);
3113 template<
typename _BidirectionalIterator,
typename _Distance,
3117 _BidirectionalIterator __middle,
3118 _BidirectionalIterator __last,
3119 _Distance __len1, _Distance __len2,
3122 if (__len1 == 0 || __len2 == 0)
3124 if (__len1 + __len2 == 2)
3126 if (__comp(*__middle, *__first))
3130 _BidirectionalIterator __first_cut = __first;
3131 _BidirectionalIterator __second_cut = __middle;
3132 _Distance __len11 = 0;
3133 _Distance __len22 = 0;
3134 if (__len1 > __len2)
3136 __len11 = __len1 / 2;
3144 __len22 = __len2 / 2;
3151 _BidirectionalIterator __new_middle = __first_cut;
3154 __len11, __len22, __comp);
3156 __len1 - __len11, __len2 - __len22, __comp);
3177 template<
typename _B
idirectionalIterator>
3179 inplace_merge(_BidirectionalIterator __first,
3180 _BidirectionalIterator __middle,
3181 _BidirectionalIterator __last)
3183 typedef typename iterator_traits<_BidirectionalIterator>::value_type
3185 typedef typename iterator_traits<_BidirectionalIterator>::difference_type
3189 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
3190 _BidirectionalIterator>)
3191 __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
3192 __glibcxx_requires_sorted(__first, __middle);
3193 __glibcxx_requires_sorted(__middle, __last);
3195 if (__first == __middle || __middle == __last)
3203 if (__buf.
begin() == 0)
3207 __buf.
begin(), _DistanceType(__buf.
size()));
3232 template<
typename _B
idirectionalIterator,
typename _Compare>
3234 inplace_merge(_BidirectionalIterator __first,
3235 _BidirectionalIterator __middle,
3236 _BidirectionalIterator __last,
3239 typedef typename iterator_traits<_BidirectionalIterator>::value_type
3241 typedef typename iterator_traits<_BidirectionalIterator>::difference_type
3245 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
3246 _BidirectionalIterator>)
3247 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3248 _ValueType, _ValueType>)
3249 __glibcxx_requires_sorted_pred(__first, __middle, __comp);
3250 __glibcxx_requires_sorted_pred(__middle, __last, __comp);
3252 if (__first == __middle || __middle == __last)
3255 const _DistanceType __len1 =
std::distance(__first, __middle);
3256 const _DistanceType __len2 =
std::distance(__middle, __last);
3260 if (__buf.
begin() == 0)
3265 __buf.
begin(), _DistanceType(__buf.
size()),
3271 template<
typename _InputIterator1,
typename _InputIterator2,
3272 typename _OutputIterator>
3275 _InputIterator2 __first2, _InputIterator2 __last2,
3276 _OutputIterator __result)
3278 while (__first1 != __last1 && __first2 != __last2)
3280 if (*__first2 < *__first1)
3282 *__result = _GLIBCXX_MOVE(*__first2);
3287 *__result = _GLIBCXX_MOVE(*__first1);
3292 return _GLIBCXX_MOVE3(__first2, __last2,
3293 _GLIBCXX_MOVE3(__first1, __last1,
3298 template<
typename _InputIterator1,
typename _InputIterator2,
3299 typename _OutputIterator,
typename _Compare>
3302 _InputIterator2 __first2, _InputIterator2 __last2,
3303 _OutputIterator __result, _Compare __comp)
3305 while (__first1 != __last1 && __first2 != __last2)
3307 if (__comp(*__first2, *__first1))
3309 *__result = _GLIBCXX_MOVE(*__first2);
3314 *__result = _GLIBCXX_MOVE(*__first1);
3319 return _GLIBCXX_MOVE3(__first2, __last2,
3320 _GLIBCXX_MOVE3(__first1, __last1,
3324 template<
typename _RandomAccessIterator1,
typename _RandomAccessIterator2,
3327 __merge_sort_loop(_RandomAccessIterator1 __first,
3328 _RandomAccessIterator1 __last,
3329 _RandomAccessIterator2 __result,
3330 _Distance __step_size)
3332 const _Distance __two_step = 2 * __step_size;
3334 while (__last - __first >= __two_step)
3337 __first + __step_size,
3338 __first + __two_step, __result);
3339 __first += __two_step;
3342 __step_size =
std::min(_Distance(__last - __first), __step_size);
3344 __first + __step_size, __last, __result);
3347 template<
typename _RandomAccessIterator1,
typename _RandomAccessIterator2,
3348 typename _Distance,
typename _Compare>
3350 __merge_sort_loop(_RandomAccessIterator1 __first,
3351 _RandomAccessIterator1 __last,
3352 _RandomAccessIterator2 __result, _Distance __step_size,
3355 const _Distance __two_step = 2 * __step_size;
3357 while (__last - __first >= __two_step)
3360 __first + __step_size,
3361 __first + __two_step,
3363 __first += __two_step;
3365 __step_size =
std::min(_Distance(__last - __first), __step_size);
3368 __first + __step_size, __last, __result, __comp);
3371 template<
typename _RandomAccessIterator,
typename _Distance>
3373 __chunk_insertion_sort(_RandomAccessIterator __first,
3374 _RandomAccessIterator __last,
3375 _Distance __chunk_size)
3377 while (__last - __first >= __chunk_size)
3380 __first += __chunk_size;
3385 template<
typename _RandomAccessIterator,
typename _Distance,
3388 __chunk_insertion_sort(_RandomAccessIterator __first,
3389 _RandomAccessIterator __last,
3390 _Distance __chunk_size, _Compare __comp)
3392 while (__last - __first >= __chunk_size)
3395 __first += __chunk_size;
3400 enum { _S_chunk_size = 7 };
3402 template<
typename _RandomAccessIterator,
typename _Po
inter>
3404 __merge_sort_with_buffer(_RandomAccessIterator __first,
3405 _RandomAccessIterator __last,
3408 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
3411 const _Distance __len = __last - __first;
3412 const _Pointer __buffer_last = __buffer + __len;
3414 _Distance __step_size = _S_chunk_size;
3415 std::__chunk_insertion_sort(__first, __last, __step_size);
3417 while (__step_size < __len)
3419 std::__merge_sort_loop(__first, __last, __buffer, __step_size);
3421 std::__merge_sort_loop(__buffer, __buffer_last, __first, __step_size);
3426 template<
typename _RandomAccessIterator,
typename _Po
inter,
typename _Compare>
3428 __merge_sort_with_buffer(_RandomAccessIterator __first,
3429 _RandomAccessIterator __last,
3430 _Pointer __buffer, _Compare __comp)
3432 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
3435 const _Distance __len = __last - __first;
3436 const _Pointer __buffer_last = __buffer + __len;
3438 _Distance __step_size = _S_chunk_size;
3439 std::__chunk_insertion_sort(__first, __last, __step_size, __comp);
3441 while (__step_size < __len)
3443 std::__merge_sort_loop(__first, __last, __buffer,
3444 __step_size, __comp);
3446 std::__merge_sort_loop(__buffer, __buffer_last, __first,
3447 __step_size, __comp);
3452 template<
typename _RandomAccessIterator,
typename _Pointer,
3455 __stable_sort_adaptive(_RandomAccessIterator __first,
3456 _RandomAccessIterator __last,
3457 _Pointer __buffer, _Distance __buffer_size)
3459 const _Distance __len = (__last - __first + 1) / 2;
3460 const _RandomAccessIterator __middle = __first + __len;
3461 if (__len > __buffer_size)
3463 std::__stable_sort_adaptive(__first, __middle,
3464 __buffer, __buffer_size);
3465 std::__stable_sort_adaptive(__middle, __last,
3466 __buffer, __buffer_size);
3470 std::__merge_sort_with_buffer(__first, __middle, __buffer);
3471 std::__merge_sort_with_buffer(__middle, __last, __buffer);
3474 _Distance(__middle - __first),
3475 _Distance(__last - __middle),
3476 __buffer, __buffer_size);
3479 template<
typename _RandomAccessIterator,
typename _Pointer,
3480 typename _Distance,
typename _Compare>
3482 __stable_sort_adaptive(_RandomAccessIterator __first,
3483 _RandomAccessIterator __last,
3484 _Pointer __buffer, _Distance __buffer_size,
3487 const _Distance __len = (__last - __first + 1) / 2;
3488 const _RandomAccessIterator __middle = __first + __len;
3489 if (__len > __buffer_size)
3491 std::__stable_sort_adaptive(__first, __middle, __buffer,
3492 __buffer_size, __comp);
3493 std::__stable_sort_adaptive(__middle, __last, __buffer,
3494 __buffer_size, __comp);
3498 std::__merge_sort_with_buffer(__first, __middle, __buffer, __comp);
3499 std::__merge_sort_with_buffer(__middle, __last, __buffer, __comp);
3502 _Distance(__middle - __first),
3503 _Distance(__last - __middle),
3504 __buffer, __buffer_size,
3509 template<
typename _RandomAccessIterator>
3512 _RandomAccessIterator __last)
3514 if (__last - __first < 15)
3519 _RandomAccessIterator __middle = __first + (__last - __first) / 2;
3528 template<
typename _RandomAccessIterator,
typename _Compare>
3531 _RandomAccessIterator __last, _Compare __comp)
3533 if (__last - __first < 15)
3538 _RandomAccessIterator __middle = __first + (__last - __first) / 2;
3572 template<
typename _InputIterator1,
typename _InputIterator2>
3574 includes(_InputIterator1 __first1, _InputIterator1 __last1,
3575 _InputIterator2 __first2, _InputIterator2 __last2)
3577 typedef typename iterator_traits<_InputIterator1>::value_type
3579 typedef typename iterator_traits<_InputIterator2>::value_type
3583 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
3584 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
3585 __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
3586 __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
3587 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
3588 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
3590 while (__first1 != __last1 && __first2 != __last2)
3591 if (*__first2 < *__first1)
3593 else if(*__first1 < *__first2)
3596 ++__first1, ++__first2;
3598 return __first2 == __last2;
3622 template<
typename _InputIterator1,
typename _InputIterator2,
3625 includes(_InputIterator1 __first1, _InputIterator1 __last1,
3626 _InputIterator2 __first2, _InputIterator2 __last2,
3629 typedef typename iterator_traits<_InputIterator1>::value_type
3631 typedef typename iterator_traits<_InputIterator2>::value_type
3635 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
3636 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
3637 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3638 _ValueType1, _ValueType2>)
3639 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3640 _ValueType2, _ValueType1>)
3641 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
3642 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
3644 while (__first1 != __last1 && __first2 != __last2)
3645 if (__comp(*__first2, *__first1))
3647 else if(__comp(*__first1, *__first2))
3650 ++__first1, ++__first2;
3652 return __first2 == __last2;
3677 template<
typename _B
idirectionalIterator>
3679 next_permutation(_BidirectionalIterator __first,
3680 _BidirectionalIterator __last)
3683 __glibcxx_function_requires(_BidirectionalIteratorConcept<
3684 _BidirectionalIterator>)
3685 __glibcxx_function_requires(_LessThanComparableConcept<
3686 typename iterator_traits<_BidirectionalIterator>::value_type>)
3687 __glibcxx_requires_valid_range(__first, __last);
3689 if (__first == __last)
3691 _BidirectionalIterator __i = __first;
3700 _BidirectionalIterator __ii = __i;
3704 _BidirectionalIterator __j = __last;
3705 while (!(*__i < *--__j))
3734 template<
typename _B
idirectionalIterator,
typename _Compare>
3736 next_permutation(_BidirectionalIterator __first,
3737 _BidirectionalIterator __last, _Compare __comp)
3740 __glibcxx_function_requires(_BidirectionalIteratorConcept<
3741 _BidirectionalIterator>)
3742 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3743 typename iterator_traits<_BidirectionalIterator>::value_type,
3744 typename iterator_traits<_BidirectionalIterator>::value_type>)
3745 __glibcxx_requires_valid_range(__first, __last);
3747 if (__first == __last)
3749 _BidirectionalIterator __i = __first;
3758 _BidirectionalIterator __ii = __i;
3760 if (__comp(*__i, *__ii))
3762 _BidirectionalIterator __j = __last;
3763 while (!
bool(__comp(*__i, *--__j)))
3790 template<
typename _B
idirectionalIterator>
3792 prev_permutation(_BidirectionalIterator __first,
3793 _BidirectionalIterator __last)
3796 __glibcxx_function_requires(_BidirectionalIteratorConcept<
3797 _BidirectionalIterator>)
3798 __glibcxx_function_requires(_LessThanComparableConcept<
3799 typename iterator_traits<_BidirectionalIterator>::value_type>)
3800 __glibcxx_requires_valid_range(__first, __last);
3802 if (__first == __last)
3804 _BidirectionalIterator __i = __first;
3813 _BidirectionalIterator __ii = __i;
3817 _BidirectionalIterator __j = __last;
3818 while (!(*--__j < *__i))
3847 template<
typename _B
idirectionalIterator,
typename _Compare>
3849 prev_permutation(_BidirectionalIterator __first,
3850 _BidirectionalIterator __last, _Compare __comp)
3853 __glibcxx_function_requires(_BidirectionalIteratorConcept<
3854 _BidirectionalIterator>)
3855 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3856 typename iterator_traits<_BidirectionalIterator>::value_type,
3857 typename iterator_traits<_BidirectionalIterator>::value_type>)
3858 __glibcxx_requires_valid_range(__first, __last);
3860 if (__first == __last)
3862 _BidirectionalIterator __i = __first;
3871 _BidirectionalIterator __ii = __i;
3873 if (__comp(*__ii, *__i))
3875 _BidirectionalIterator __j = __last;
3876 while (!
bool(__comp(*--__j, *__i)))
3907 template<
typename _InputIterator,
typename _OutputIterator,
typename _Tp>
3909 replace_copy(_InputIterator __first, _InputIterator __last,
3910 _OutputIterator __result,
3911 const _Tp& __old_value,
const _Tp& __new_value)
3914 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3915 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
3916 typename iterator_traits<_InputIterator>::value_type>)
3917 __glibcxx_function_requires(_EqualOpConcept<
3918 typename iterator_traits<_InputIterator>::value_type, _Tp>)
3919 __glibcxx_requires_valid_range(__first, __last);
3921 for (; __first != __last; ++__first, ++__result)
3922 if (*__first == __old_value)
3923 *__result = __new_value;
3925 *__result = *__first;
3944 template<
typename _InputIterator,
typename _OutputIterator,
3945 typename _Predicate,
typename _Tp>
3947 replace_copy_if(_InputIterator __first, _InputIterator __last,
3948 _OutputIterator __result,
3949 _Predicate __pred,
const _Tp& __new_value)
3952 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3953 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
3954 typename iterator_traits<_InputIterator>::value_type>)
3955 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
3956 typename iterator_traits<_InputIterator>::value_type>)
3957 __glibcxx_requires_valid_range(__first, __last);
3959 for (; __first != __last; ++__first, ++__result)
3960 if (__pred(*__first))
3961 *__result = __new_value;
3963 *__result = *__first;
3967 #ifdef __GXX_EXPERIMENTAL_CXX0X__
3975 template<
typename _ForwardIterator>
3977 is_sorted(_ForwardIterator __first, _ForwardIterator __last)
3989 template<
typename _ForwardIterator,
typename _Compare>
3991 is_sorted(_ForwardIterator __first, _ForwardIterator __last,
4003 template<
typename _ForwardIterator>
4005 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last)
4008 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4009 __glibcxx_function_requires(_LessThanComparableConcept<
4010 typename iterator_traits<_ForwardIterator>::value_type>)
4011 __glibcxx_requires_valid_range(__first, __last);
4013 if (__first == __last)
4016 _ForwardIterator __next = __first;
4017 for (++__next; __next != __last; __first = __next, ++__next)
4018 if (*__next < *__first)
4032 template<
typename _ForwardIterator,
typename _Compare>
4034 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last,
4038 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4039 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4040 typename iterator_traits<_ForwardIterator>::value_type,
4041 typename iterator_traits<_ForwardIterator>::value_type>)
4042 __glibcxx_requires_valid_range(__first, __last);
4044 if (__first == __last)
4047 _ForwardIterator __next = __first;
4048 for (++__next; __next != __last; __first = __next, ++__next)
4049 if (__comp(*__next, *__first))
4062 template<
typename _Tp>
4063 inline pair<const _Tp&, const _Tp&>
4067 __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
4069 return __b < __a ? pair<const _Tp&, const _Tp&>(__b, __a)
4082 template<
typename _Tp,
typename _Compare>
4083 inline pair<const _Tp&, const _Tp&>
4084 minmax(
const _Tp& __a,
const _Tp& __b, _Compare __comp)
4101 template<
typename _ForwardIterator>
4102 pair<_ForwardIterator, _ForwardIterator>
4103 minmax_element(_ForwardIterator __first, _ForwardIterator __last)
4106 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4107 __glibcxx_function_requires(_LessThanComparableConcept<
4108 typename iterator_traits<_ForwardIterator>::value_type>)
4109 __glibcxx_requires_valid_range(__first, __last);
4111 _ForwardIterator __next = __first;
4112 if (__first == __last
4113 || ++__next == __last)
4116 _ForwardIterator __min, __max;
4117 if (*__next < *__first)
4131 while (__first != __last)
4134 if (++__next == __last)
4136 if (*__first < *__min)
4138 else if (!(*__first < *__max))
4143 if (*__next < *__first)
4145 if (*__next < *__min)
4147 if (!(*__first < *__max))
4152 if (*__first < *__min)
4154 if (!(*__next < *__max))
4177 template<
typename _ForwardIterator,
typename _Compare>
4178 pair<_ForwardIterator, _ForwardIterator>
4179 minmax_element(_ForwardIterator __first, _ForwardIterator __last,
4183 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4184 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4185 typename iterator_traits<_ForwardIterator>::value_type,
4186 typename iterator_traits<_ForwardIterator>::value_type>)
4187 __glibcxx_requires_valid_range(__first, __last);
4189 _ForwardIterator __next = __first;
4190 if (__first == __last
4191 || ++__next == __last)
4194 _ForwardIterator __min, __max;
4195 if (__comp(*__next, *__first))
4209 while (__first != __last)
4212 if (++__next == __last)
4214 if (__comp(*__first, *__min))
4216 else if (!__comp(*__first, *__max))
4221 if (__comp(*__next, *__first))
4223 if (__comp(*__next, *__min))
4225 if (!__comp(*__first, *__max))
4230 if (__comp(*__first, *__min))
4232 if (!__comp(*__next, *__max))
4244 template<
typename _Tp>
4246 min(initializer_list<_Tp> __l)
4247 {
return *std::min_element(__l.begin(), __l.end()); }
4249 template<
typename _Tp,
typename _Compare>
4251 min(initializer_list<_Tp> __l, _Compare __comp)
4254 template<
typename _Tp>
4256 max(initializer_list<_Tp> __l)
4259 template<
typename _Tp,
typename _Compare>
4261 max(initializer_list<_Tp> __l, _Compare __comp)
4264 template<
typename _Tp>
4265 inline pair<_Tp, _Tp>
4266 minmax(initializer_list<_Tp> __l)
4268 pair<const _Tp*, const _Tp*> __p =
4273 template<
typename _Tp,
typename _Compare>
4274 inline pair<_Tp, _Tp>
4275 minmax(initializer_list<_Tp> __l, _Compare __comp)
4277 pair<const _Tp*, const _Tp*> __p =
4294 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
4296 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
4297 _ForwardIterator2 __first2)
4301 for (; __first1 != __last1; ++__first1, ++__first2)
4302 if (!(*__first1 == *__first2))
4305 if (__first1 == __last1)
4310 _ForwardIterator2 __last2 = __first2;
4312 for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
4314 if (__scan != _GLIBCXX_STD_A::find(__first1, __scan, *__scan))
4317 auto __matches =
std::count(__first2, __last2, *__scan);
4319 ||
std::count(__scan, __last1, *__scan) != __matches)
4339 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
4340 typename _BinaryPredicate>
4342 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
4343 _ForwardIterator2 __first2, _BinaryPredicate __pred)
4347 for (; __first1 != __last1; ++__first1, ++__first2)
4348 if (!
bool(__pred(*__first1, *__first2)))
4351 if (__first1 == __last1)
4356 _ForwardIterator2 __last2 = __first2;
4358 for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
4360 using std::placeholders::_1;
4362 if (__scan != _GLIBCXX_STD_A::find_if(__first1, __scan,
4370 std::bind(__pred, _1, *__scan)) != __matches)
4376 #ifdef _GLIBCXX_USE_C99_STDINT_TR1
4389 template<
typename _RandomAccessIterator,
4390 typename _UniformRandomNumberGenerator>
4392 shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
4393 _UniformRandomNumberGenerator&& __g)
4396 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4397 _RandomAccessIterator>)
4398 __glibcxx_requires_valid_range(__first, __last);
4400 if (__first == __last)
4403 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
4406 typedef typename std::make_unsigned<_DistanceType>::type __ud_type;
4408 typedef typename __distr_type::param_type __p_type;
4411 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
4412 std::iter_swap(__i, __first + __d(__g, __p_type(0, __i - __first)));
4416 #endif // __GXX_EXPERIMENTAL_CXX0X__
4418 _GLIBCXX_END_NAMESPACE_VERSION
4420 _GLIBCXX_BEGIN_NAMESPACE_ALGO
4434 template<
typename _InputIterator,
typename _Function>
4436 for_each(_InputIterator __first, _InputIterator __last, _Function __f)
4439 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4440 __glibcxx_requires_valid_range(__first, __last);
4441 for (; __first != __last; ++__first)
4443 return _GLIBCXX_MOVE(__f);
4455 template<
typename _InputIterator,
typename _Tp>
4456 inline _InputIterator
4457 find(_InputIterator __first, _InputIterator __last,
4461 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4462 __glibcxx_function_requires(_EqualOpConcept<
4463 typename iterator_traits<_InputIterator>::value_type, _Tp>)
4464 __glibcxx_requires_valid_range(__first, __last);
4479 template<
typename _InputIterator,
typename _Predicate>
4480 inline _InputIterator
4481 find_if(_InputIterator __first, _InputIterator __last,
4485 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4486 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4487 typename iterator_traits<_InputIterator>::value_type>)
4488 __glibcxx_requires_valid_range(__first, __last);
4509 template<
typename _InputIterator,
typename _ForwardIterator>
4511 find_first_of(_InputIterator __first1, _InputIterator __last1,
4512 _ForwardIterator __first2, _ForwardIterator __last2)
4515 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4516 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4517 __glibcxx_function_requires(_EqualOpConcept<
4518 typename iterator_traits<_InputIterator>::value_type,
4519 typename iterator_traits<_ForwardIterator>::value_type>)
4520 __glibcxx_requires_valid_range(__first1, __last1);
4521 __glibcxx_requires_valid_range(__first2, __last2);
4523 for (; __first1 != __last1; ++__first1)
4524 for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
4525 if (*__first1 == *__iter)
4549 template<
typename _InputIterator,
typename _ForwardIterator,
4550 typename _BinaryPredicate>
4552 find_first_of(_InputIterator __first1, _InputIterator __last1,
4553 _ForwardIterator __first2, _ForwardIterator __last2,
4554 _BinaryPredicate __comp)
4557 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4558 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4559 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4560 typename iterator_traits<_InputIterator>::value_type,
4561 typename iterator_traits<_ForwardIterator>::value_type>)
4562 __glibcxx_requires_valid_range(__first1, __last1);
4563 __glibcxx_requires_valid_range(__first2, __last2);
4565 for (; __first1 != __last1; ++__first1)
4566 for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
4567 if (__comp(*__first1, *__iter))
4581 template<
typename _ForwardIterator>
4583 adjacent_find(_ForwardIterator __first, _ForwardIterator __last)
4586 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4587 __glibcxx_function_requires(_EqualityComparableConcept<
4588 typename iterator_traits<_ForwardIterator>::value_type>)
4589 __glibcxx_requires_valid_range(__first, __last);
4590 if (__first == __last)
4592 _ForwardIterator __next = __first;
4593 while(++__next != __last)
4595 if (*__first == *__next)
4613 template<
typename _ForwardIterator,
typename _BinaryPredicate>
4615 adjacent_find(_ForwardIterator __first, _ForwardIterator __last,
4616 _BinaryPredicate __binary_pred)
4619 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4620 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4621 typename iterator_traits<_ForwardIterator>::value_type,
4622 typename iterator_traits<_ForwardIterator>::value_type>)
4623 __glibcxx_requires_valid_range(__first, __last);
4624 if (__first == __last)
4626 _ForwardIterator __next = __first;
4627 while(++__next != __last)
4629 if (__binary_pred(*__first, *__next))
4645 template<
typename _InputIterator,
typename _Tp>
4646 typename iterator_traits<_InputIterator>::difference_type
4647 count(_InputIterator __first, _InputIterator __last,
const _Tp& __value)
4650 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4651 __glibcxx_function_requires(_EqualOpConcept<
4652 typename iterator_traits<_InputIterator>::value_type, _Tp>)
4653 __glibcxx_requires_valid_range(__first, __last);
4654 typename iterator_traits<_InputIterator>::difference_type __n = 0;
4655 for (; __first != __last; ++__first)
4656 if (*__first == __value)
4670 template<
typename _InputIterator,
typename _Predicate>
4671 typename iterator_traits<_InputIterator>::difference_type
4672 count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
4675 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4676 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4677 typename iterator_traits<_InputIterator>::value_type>)
4678 __glibcxx_requires_valid_range(__first, __last);
4679 typename iterator_traits<_InputIterator>::difference_type __n = 0;
4680 for (; __first != __last; ++__first)
4681 if (__pred(*__first))
4712 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
4714 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
4715 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
4718 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
4719 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
4720 __glibcxx_function_requires(_EqualOpConcept<
4721 typename iterator_traits<_ForwardIterator1>::value_type,
4722 typename iterator_traits<_ForwardIterator2>::value_type>)
4723 __glibcxx_requires_valid_range(__first1, __last1);
4724 __glibcxx_requires_valid_range(__first2, __last2);
4727 if (__first1 == __last1 || __first2 == __last2)
4731 _ForwardIterator2 __p1(__first2);
4732 if (++__p1 == __last2)
4733 return _GLIBCXX_STD_A::find(__first1, __last1, *__first2);
4736 _ForwardIterator2 __p;
4737 _ForwardIterator1 __current = __first1;
4741 __first1 = _GLIBCXX_STD_A::find(__first1, __last1, *__first2);
4742 if (__first1 == __last1)
4746 __current = __first1;
4747 if (++__current == __last1)
4750 while (*__current == *__p)
4752 if (++__p == __last2)
4754 if (++__current == __last1)
4783 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
4784 typename _BinaryPredicate>
4786 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
4787 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
4788 _BinaryPredicate __predicate)
4791 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
4792 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
4793 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4794 typename iterator_traits<_ForwardIterator1>::value_type,
4795 typename iterator_traits<_ForwardIterator2>::value_type>)
4796 __glibcxx_requires_valid_range(__first1, __last1);
4797 __glibcxx_requires_valid_range(__first2, __last2);
4800 if (__first1 == __last1 || __first2 == __last2)
4804 _ForwardIterator2 __p1(__first2);
4805 if (++__p1 == __last2)
4807 while (__first1 != __last1
4808 && !
bool(__predicate(*__first1, *__first2)))
4814 _ForwardIterator2 __p;
4815 _ForwardIterator1 __current = __first1;
4819 while (__first1 != __last1
4820 && !
bool(__predicate(*__first1, *__first2)))
4822 if (__first1 == __last1)
4826 __current = __first1;
4827 if (++__current == __last1)
4830 while (__predicate(*__current, *__p))
4832 if (++__p == __last2)
4834 if (++__current == __last1)
4858 template<
typename _ForwardIterator,
typename _Integer,
typename _Tp>
4860 search_n(_ForwardIterator __first, _ForwardIterator __last,
4861 _Integer __count,
const _Tp& __val)
4864 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4865 __glibcxx_function_requires(_EqualOpConcept<
4866 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
4867 __glibcxx_requires_valid_range(__first, __last);
4872 return _GLIBCXX_STD_A::find(__first, __last, __val);
4895 template<
typename _ForwardIterator,
typename _Integer,
typename _Tp,
4896 typename _BinaryPredicate>
4898 search_n(_ForwardIterator __first, _ForwardIterator __last,
4899 _Integer __count,
const _Tp& __val,
4900 _BinaryPredicate __binary_pred)
4903 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4904 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4905 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
4906 __glibcxx_requires_valid_range(__first, __last);
4912 while (__first != __last && !
bool(__binary_pred(*__first, __val)))
4916 return std::__search_n(__first, __last, __count, __val, __binary_pred,
4937 template<
typename _InputIterator,
typename _OutputIterator,
4938 typename _UnaryOperation>
4940 transform(_InputIterator __first, _InputIterator __last,
4941 _OutputIterator __result, _UnaryOperation __unary_op)
4944 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4945 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4947 __typeof__(__unary_op(*__first))>)
4948 __glibcxx_requires_valid_range(__first, __last);
4950 for (; __first != __last; ++__first, ++__result)
4951 *__result = __unary_op(*__first);
4974 template<
typename _InputIterator1,
typename _InputIterator2,
4975 typename _OutputIterator,
typename _BinaryOperation>
4977 transform(_InputIterator1 __first1, _InputIterator1 __last1,
4978 _InputIterator2 __first2, _OutputIterator __result,
4979 _BinaryOperation __binary_op)
4982 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4983 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4984 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4986 __typeof__(__binary_op(*__first1,*__first2))>)
4987 __glibcxx_requires_valid_range(__first1, __last1);
4989 for (; __first1 != __last1; ++__first1, ++__first2, ++__result)
4990 *__result = __binary_op(*__first1, *__first2);
5007 template<
typename _ForwardIterator,
typename _Tp>
5009 replace(_ForwardIterator __first, _ForwardIterator __last,
5010 const _Tp& __old_value,
const _Tp& __new_value)
5013 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
5015 __glibcxx_function_requires(_EqualOpConcept<
5016 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
5017 __glibcxx_function_requires(_ConvertibleConcept<_Tp,
5018 typename iterator_traits<_ForwardIterator>::value_type>)
5019 __glibcxx_requires_valid_range(__first, __last);
5021 for (; __first != __last; ++__first)
5022 if (*__first == __old_value)
5023 *__first = __new_value;
5039 template<
typename _ForwardIterator,
typename _Predicate,
typename _Tp>
5041 replace_if(_ForwardIterator __first, _ForwardIterator __last,
5042 _Predicate __pred,
const _Tp& __new_value)
5045 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
5047 __glibcxx_function_requires(_ConvertibleConcept<_Tp,
5048 typename iterator_traits<_ForwardIterator>::value_type>)
5049 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
5050 typename iterator_traits<_ForwardIterator>::value_type>)
5051 __glibcxx_requires_valid_range(__first, __last);
5053 for (; __first != __last; ++__first)
5054 if (__pred(*__first))
5055 *__first = __new_value;
5071 template<
typename _ForwardIterator,
typename _Generator>
5073 generate(_ForwardIterator __first, _ForwardIterator __last,
5077 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5078 __glibcxx_function_requires(_GeneratorConcept<_Generator,
5079 typename iterator_traits<_ForwardIterator>::value_type>)
5080 __glibcxx_requires_valid_range(__first, __last);
5082 for (; __first != __last; ++__first)
5102 template<
typename _OutputIterator,
typename _Size,
typename _Generator>
5104 generate_n(_OutputIterator __first, _Size __n, _Generator __gen)
5107 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5109 __typeof__(__gen())>)
5111 for (__decltype(__n + 0) __niter = __n;
5112 __niter > 0; --__niter, ++__first)
5139 template<
typename _InputIterator,
typename _OutputIterator>
5140 inline _OutputIterator
5141 unique_copy(_InputIterator __first, _InputIterator __last,
5142 _OutputIterator __result)
5145 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
5146 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5147 typename iterator_traits<_InputIterator>::value_type>)
5148 __glibcxx_function_requires(_EqualityComparableConcept<
5149 typename iterator_traits<_InputIterator>::value_type>)
5150 __glibcxx_requires_valid_range(__first, __last);
5152 if (__first == __last)
5178 template<
typename _InputIterator,
typename _OutputIterator,
5179 typename _BinaryPredicate>
5180 inline _OutputIterator
5181 unique_copy(_InputIterator __first, _InputIterator __last,
5182 _OutputIterator __result,
5183 _BinaryPredicate __binary_pred)
5186 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
5187 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5188 typename iterator_traits<_InputIterator>::value_type>)
5189 __glibcxx_requires_valid_range(__first, __last);
5191 if (__first == __last)
5210 template<
typename _RandomAccessIterator>
5212 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
5215 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5216 _RandomAccessIterator>)
5217 __glibcxx_requires_valid_range(__first, __last);
5219 if (__first != __last)
5220 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
5221 std::iter_swap(__i, __first + (std::rand() % ((__i - __first) + 1)));
5238 template<
typename _RandomAccessIterator,
typename _RandomNumberGenerator>
5240 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
5241 #ifdef __GXX_EXPERIMENTAL_CXX0X__
5242 _RandomNumberGenerator&& __rand)
5244 _RandomNumberGenerator& __rand)
5248 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5249 _RandomAccessIterator>)
5250 __glibcxx_requires_valid_range(__first, __last);
5252 if (__first == __last)
5254 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
5274 template<
typename _ForwardIterator,
typename _Predicate>
5275 inline _ForwardIterator
5276 partition(_ForwardIterator __first, _ForwardIterator __last,
5280 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
5282 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
5283 typename iterator_traits<_ForwardIterator>::value_type>)
5284 __glibcxx_requires_valid_range(__first, __last);
5308 template<
typename _RandomAccessIterator>
5310 partial_sort(_RandomAccessIterator __first,
5311 _RandomAccessIterator __middle,
5312 _RandomAccessIterator __last)
5314 typedef typename iterator_traits<_RandomAccessIterator>::value_type
5318 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5319 _RandomAccessIterator>)
5320 __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
5321 __glibcxx_requires_valid_range(__first, __middle);
5322 __glibcxx_requires_valid_range(__middle, __last);
5347 template<
typename _RandomAccessIterator,
typename _Compare>
5349 partial_sort(_RandomAccessIterator __first,
5350 _RandomAccessIterator __middle,
5351 _RandomAccessIterator __last,
5354 typedef typename iterator_traits<_RandomAccessIterator>::value_type
5358 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5359 _RandomAccessIterator>)
5360 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5361 _ValueType, _ValueType>)
5362 __glibcxx_requires_valid_range(__first, __middle);
5363 __glibcxx_requires_valid_range(__middle, __last);
5384 template<
typename _RandomAccessIterator>
5386 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
5387 _RandomAccessIterator __last)
5389 typedef typename iterator_traits<_RandomAccessIterator>::value_type
5393 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5394 _RandomAccessIterator>)
5395 __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
5396 __glibcxx_requires_valid_range(__first, __nth);
5397 __glibcxx_requires_valid_range(__nth, __last);
5399 if (__first == __last || __nth == __last)
5402 std::__introselect(__first, __nth, __last,
5423 template<
typename _RandomAccessIterator,
typename _Compare>
5425 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
5426 _RandomAccessIterator __last, _Compare __comp)
5428 typedef typename iterator_traits<_RandomAccessIterator>::value_type
5432 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5433 _RandomAccessIterator>)
5434 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5435 _ValueType, _ValueType>)
5436 __glibcxx_requires_valid_range(__first, __nth);
5437 __glibcxx_requires_valid_range(__nth, __last);
5439 if (__first == __last || __nth == __last)
5442 std::__introselect(__first, __nth, __last,
5443 std::__lg(__last - __first) * 2, __comp);
5461 template<
typename _RandomAccessIterator>
5463 sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
5465 typedef typename iterator_traits<_RandomAccessIterator>::value_type
5469 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5470 _RandomAccessIterator>)
5471 __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
5472 __glibcxx_requires_valid_range(__first, __last);
5474 if (__first != __last)
5497 template<
typename _RandomAccessIterator,
typename _Compare>
5499 sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
5502 typedef typename iterator_traits<_RandomAccessIterator>::value_type
5506 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5507 _RandomAccessIterator>)
5508 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, _ValueType,
5510 __glibcxx_requires_valid_range(__first, __last);
5512 if (__first != __last)
5515 std::__lg(__last - __first) * 2, __comp);
5539 template<
typename _InputIterator1,
typename _InputIterator2,
5540 typename _OutputIterator>
5542 merge(_InputIterator1 __first1, _InputIterator1 __last1,
5543 _InputIterator2 __first2, _InputIterator2 __last2,
5544 _OutputIterator __result)
5546 typedef typename iterator_traits<_InputIterator1>::value_type
5548 typedef typename iterator_traits<_InputIterator2>::value_type
5552 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5553 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5554 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5556 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5558 __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
5559 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5560 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5562 while (__first1 != __last1 && __first2 != __last2)
5564 if (*__first2 < *__first1)
5566 *__result = *__first2;
5571 *__result = *__first1;
5576 return std::copy(__first2, __last2, std::copy(__first1, __last1,
5603 template<
typename _InputIterator1,
typename _InputIterator2,
5604 typename _OutputIterator,
typename _Compare>
5606 merge(_InputIterator1 __first1, _InputIterator1 __last1,
5607 _InputIterator2 __first2, _InputIterator2 __last2,
5608 _OutputIterator __result, _Compare __comp)
5610 typedef typename iterator_traits<_InputIterator1>::value_type
5612 typedef typename iterator_traits<_InputIterator2>::value_type
5616 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5617 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5618 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5620 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5622 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5623 _ValueType2, _ValueType1>)
5624 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5625 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5627 while (__first1 != __last1 && __first2 != __last2)
5629 if (__comp(*__first2, *__first1))
5631 *__result = *__first2;
5636 *__result = *__first1;
5641 return std::copy(__first2, __last2, std::copy(__first1, __last1,
5663 template<
typename _RandomAccessIterator>
5665 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
5667 typedef typename iterator_traits<_RandomAccessIterator>::value_type
5669 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
5673 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5674 _RandomAccessIterator>)
5675 __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
5676 __glibcxx_requires_valid_range(__first, __last);
5680 if (__buf.
begin() == 0)
5683 std::__stable_sort_adaptive(__first, __last, __buf.
begin(),
5684 _DistanceType(__buf.
size()));
5705 template<
typename _RandomAccessIterator,
typename _Compare>
5707 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
5710 typedef typename iterator_traits<_RandomAccessIterator>::value_type
5712 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
5716 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5717 _RandomAccessIterator>)
5718 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5721 __glibcxx_requires_valid_range(__first, __last);
5725 if (__buf.
begin() == 0)
5728 std::__stable_sort_adaptive(__first, __last, __buf.
begin(),
5729 _DistanceType(__buf.
size()), __comp);
5751 template<
typename _InputIterator1,
typename _InputIterator2,
5752 typename _OutputIterator>
5754 set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5755 _InputIterator2 __first2, _InputIterator2 __last2,
5756 _OutputIterator __result)
5758 typedef typename iterator_traits<_InputIterator1>::value_type
5760 typedef typename iterator_traits<_InputIterator2>::value_type
5764 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5765 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5766 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5768 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5770 __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
5771 __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
5772 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5773 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5775 while (__first1 != __last1 && __first2 != __last2)
5777 if (*__first1 < *__first2)
5779 *__result = *__first1;
5782 else if (*__first2 < *__first1)
5784 *__result = *__first2;
5789 *__result = *__first1;
5795 return std::copy(__first2, __last2, std::copy(__first1, __last1,
5818 template<
typename _InputIterator1,
typename _InputIterator2,
5819 typename _OutputIterator,
typename _Compare>
5821 set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5822 _InputIterator2 __first2, _InputIterator2 __last2,
5823 _OutputIterator __result, _Compare __comp)
5825 typedef typename iterator_traits<_InputIterator1>::value_type
5827 typedef typename iterator_traits<_InputIterator2>::value_type
5831 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5832 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5833 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5835 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5837 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5838 _ValueType1, _ValueType2>)
5839 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5840 _ValueType2, _ValueType1>)
5841 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5842 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5844 while (__first1 != __last1 && __first2 != __last2)
5846 if (__comp(*__first1, *__first2))
5848 *__result = *__first1;
5851 else if (__comp(*__first2, *__first1))
5853 *__result = *__first2;
5858 *__result = *__first1;
5864 return std::copy(__first2, __last2, std::copy(__first1, __last1,
5885 template<
typename _InputIterator1,
typename _InputIterator2,
5886 typename _OutputIterator>
5888 set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5889 _InputIterator2 __first2, _InputIterator2 __last2,
5890 _OutputIterator __result)
5892 typedef typename iterator_traits<_InputIterator1>::value_type
5894 typedef typename iterator_traits<_InputIterator2>::value_type
5898 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5899 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5900 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5902 __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
5903 __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
5904 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5905 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5907 while (__first1 != __last1 && __first2 != __last2)
5908 if (*__first1 < *__first2)
5910 else if (*__first2 < *__first1)
5914 *__result = *__first1;
5942 template<
typename _InputIterator1,
typename _InputIterator2,
5943 typename _OutputIterator,
typename _Compare>
5945 set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5946 _InputIterator2 __first2, _InputIterator2 __last2,
5947 _OutputIterator __result, _Compare __comp)
5949 typedef typename iterator_traits<_InputIterator1>::value_type
5951 typedef typename iterator_traits<_InputIterator2>::value_type
5955 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5956 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5957 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5959 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5960 _ValueType1, _ValueType2>)
5961 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5962 _ValueType2, _ValueType1>)
5963 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5964 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5966 while (__first1 != __last1 && __first2 != __last2)
5967 if (__comp(*__first1, *__first2))
5969 else if (__comp(*__first2, *__first1))
5973 *__result = *__first1;
6000 template<
typename _InputIterator1,
typename _InputIterator2,
6001 typename _OutputIterator>
6003 set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
6004 _InputIterator2 __first2, _InputIterator2 __last2,
6005 _OutputIterator __result)
6007 typedef typename iterator_traits<_InputIterator1>::value_type
6009 typedef typename iterator_traits<_InputIterator2>::value_type
6013 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
6014 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
6015 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
6017 __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
6018 __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
6019 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
6020 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
6022 while (__first1 != __last1 && __first2 != __last2)
6023 if (*__first1 < *__first2)
6025 *__result = *__first1;
6029 else if (*__first2 < *__first1)
6036 return std::copy(__first1, __last1, __result);
6061 template<
typename _InputIterator1,
typename _InputIterator2,
6062 typename _OutputIterator,
typename _Compare>
6064 set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
6065 _InputIterator2 __first2, _InputIterator2 __last2,
6066 _OutputIterator __result, _Compare __comp)
6068 typedef typename iterator_traits<_InputIterator1>::value_type
6070 typedef typename iterator_traits<_InputIterator2>::value_type
6074 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
6075 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
6076 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
6078 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
6079 _ValueType1, _ValueType2>)
6080 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
6081 _ValueType2, _ValueType1>)
6082 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
6083 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
6085 while (__first1 != __last1 && __first2 != __last2)
6086 if (__comp(*__first1, *__first2))
6088 *__result = *__first1;
6092 else if (__comp(*__first2, *__first1))
6099 return std::copy(__first1, __last1, __result);
6119 template<
typename _InputIterator1,
typename _InputIterator2,
6120 typename _OutputIterator>
6122 set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
6123 _InputIterator2 __first2, _InputIterator2 __last2,
6124 _OutputIterator __result)
6126 typedef typename iterator_traits<_InputIterator1>::value_type
6128 typedef typename iterator_traits<_InputIterator2>::value_type
6132 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
6133 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
6134 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
6136 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
6138 __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
6139 __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
6140 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
6141 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
6143 while (__first1 != __last1 && __first2 != __last2)
6144 if (*__first1 < *__first2)
6146 *__result = *__first1;
6150 else if (*__first2 < *__first1)
6152 *__result = *__first2;
6161 return std::copy(__first2, __last2, std::copy(__first1,
6162 __last1, __result));
6185 template<
typename _InputIterator1,
typename _InputIterator2,
6186 typename _OutputIterator,
typename _Compare>
6188 set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
6189 _InputIterator2 __first2, _InputIterator2 __last2,
6190 _OutputIterator __result,
6193 typedef typename iterator_traits<_InputIterator1>::value_type
6195 typedef typename iterator_traits<_InputIterator2>::value_type
6199 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
6200 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
6201 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
6203 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
6205 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
6206 _ValueType1, _ValueType2>)
6207 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
6208 _ValueType2, _ValueType1>)
6209 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
6210 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
6212 while (__first1 != __last1 && __first2 != __last2)
6213 if (__comp(*__first1, *__first2))
6215 *__result = *__first1;
6219 else if (__comp(*__first2, *__first1))
6221 *__result = *__first2;
6230 return std::copy(__first2, __last2,
6231 std::copy(__first1, __last1, __result));
6242 template<
typename _ForwardIterator>
6244 min_element(_ForwardIterator __first, _ForwardIterator __last)
6247 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
6248 __glibcxx_function_requires(_LessThanComparableConcept<
6249 typename iterator_traits<_ForwardIterator>::value_type>)
6250 __glibcxx_requires_valid_range(__first, __last);
6252 if (__first == __last)
6254 _ForwardIterator __result = __first;
6255 while (++__first != __last)
6256 if (*__first < *__result)
6270 template<
typename _ForwardIterator,
typename _Compare>
6272 min_element(_ForwardIterator __first, _ForwardIterator __last,
6276 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
6277 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
6278 typename iterator_traits<_ForwardIterator>::value_type,
6279 typename iterator_traits<_ForwardIterator>::value_type>)
6280 __glibcxx_requires_valid_range(__first, __last);
6282 if (__first == __last)
6284 _ForwardIterator __result = __first;
6285 while (++__first != __last)
6286 if (__comp(*__first, *__result))
6298 template<
typename _ForwardIterator>
6300 max_element(_ForwardIterator __first, _ForwardIterator __last)
6303 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
6304 __glibcxx_function_requires(_LessThanComparableConcept<
6305 typename iterator_traits<_ForwardIterator>::value_type>)
6306 __glibcxx_requires_valid_range(__first, __last);
6308 if (__first == __last)
6310 _ForwardIterator __result = __first;
6311 while (++__first != __last)
6312 if (*__result < *__first)
6326 template<
typename _ForwardIterator,
typename _Compare>
6328 max_element(_ForwardIterator __first, _ForwardIterator __last,
6332 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
6333 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
6334 typename iterator_traits<_ForwardIterator>::value_type,
6335 typename iterator_traits<_ForwardIterator>::value_type>)
6336 __glibcxx_requires_valid_range(__first, __last);
6338 if (__first == __last)
return __first;
6339 _ForwardIterator __result = __first;
6340 while (++__first != __last)
6341 if (__comp(*__result, *__first))
6346 _GLIBCXX_END_NAMESPACE_ALGO