69 _GLIBCXX_BEGIN_NAMESPACE(std)
83 template<typename _Tp>
85 __median(const _Tp& __a, const _Tp& __b, const _Tp& __c)
88 __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
117 template<
typename _Tp,
typename _Compare>
119 __median(
const _Tp& __a,
const _Tp& __b,
const _Tp& __c, _Compare __comp)
122 __glibcxx_function_requires(_BinaryFunctionConcept<_Compare,
bool,
124 if (__comp(__a, __b))
125 if (__comp(__b, __c))
127 else if (__comp(__a, __c))
131 else if (__comp(__a, __c))
133 else if (__comp(__b, __c))
142 template<
typename _InputIterator,
typename _Tp>
143 inline _InputIterator
144 __find(_InputIterator __first, _InputIterator __last,
147 while (__first != __last && !(*__first == __val))
153 template<
typename _InputIterator,
typename _Predicate>
154 inline _InputIterator
155 __find_if(_InputIterator __first, _InputIterator __last,
158 while (__first != __last && !
bool(__pred(*__first)))
164 template<
typename _RandomAccessIterator,
typename _Tp>
165 _RandomAccessIterator
166 __find(_RandomAccessIterator __first, _RandomAccessIterator __last,
169 typename iterator_traits<_RandomAccessIterator>::difference_type
170 __trip_count = (__last - __first) >> 2;
172 for (; __trip_count > 0; --__trip_count)
174 if (*__first == __val)
178 if (*__first == __val)
182 if (*__first == __val)
186 if (*__first == __val)
191 switch (__last - __first)
194 if (*__first == __val)
198 if (*__first == __val)
202 if (*__first == __val)
212 template<
typename _RandomAccessIterator,
typename _Predicate>
213 _RandomAccessIterator
214 __find_if(_RandomAccessIterator __first, _RandomAccessIterator __last,
217 typename iterator_traits<_RandomAccessIterator>::difference_type
218 __trip_count = (__last - __first) >> 2;
220 for (; __trip_count > 0; --__trip_count)
222 if (__pred(*__first))
226 if (__pred(*__first))
230 if (__pred(*__first))
234 if (__pred(*__first))
239 switch (__last - __first)
242 if (__pred(*__first))
246 if (__pred(*__first))
250 if (__pred(*__first))
259 #ifdef __GXX_EXPERIMENTAL_CXX0X__
261 template<
typename _InputIterator,
typename _Predicate>
262 inline _InputIterator
266 while (__first != __last &&
bool(__pred(*__first)))
272 template<
typename _RandomAccessIterator,
typename _Predicate>
273 _RandomAccessIterator
277 typename iterator_traits<_RandomAccessIterator>::difference_type
278 __trip_count = (__last - __first) >> 2;
280 for (; __trip_count > 0; --__trip_count)
282 if (!
bool(__pred(*__first)))
286 if (!
bool(__pred(*__first)))
290 if (!
bool(__pred(*__first)))
294 if (!
bool(__pred(*__first)))
299 switch (__last - __first)
302 if (!
bool(__pred(*__first)))
306 if (!
bool(__pred(*__first)))
310 if (!
bool(__pred(*__first)))
338 template<
typename _ForwardIterator,
typename _Integer,
typename _Tp>
340 __search_n(_ForwardIterator __first, _ForwardIterator __last,
341 _Integer __count,
const _Tp& __val,
345 while (__first != __last)
347 typename iterator_traits<_ForwardIterator>::difference_type
349 _ForwardIterator __i = __first;
351 while (__i != __last && __n != 1 && *__i == __val)
370 template<
typename _RandomAccessIter,
typename _Integer,
typename _Tp>
372 __search_n(_RandomAccessIter __first, _RandomAccessIter __last,
373 _Integer __count,
const _Tp& __val,
377 typedef typename std::iterator_traits<_RandomAccessIter>::difference_type
380 _DistanceType __tailSize = __last - __first;
381 const _DistanceType __pattSize = __count;
383 if (__tailSize < __pattSize)
386 const _DistanceType __skipOffset = __pattSize - 1;
387 _RandomAccessIter __lookAhead = __first + __skipOffset;
388 __tailSize -= __pattSize;
394 while (!(*__lookAhead == __val))
396 if (__tailSize < __pattSize)
398 __lookAhead += __pattSize;
399 __tailSize -= __pattSize;
401 _DistanceType __remainder = __skipOffset;
402 for (_RandomAccessIter __backTrack = __lookAhead - 1;
403 *__backTrack == __val; --__backTrack)
405 if (--__remainder == 0)
406 return (__lookAhead - __skipOffset);
408 if (__remainder > __tailSize)
410 __lookAhead += __remainder;
411 __tailSize -= __remainder;
423 template<
typename _ForwardIterator,
typename _Integer,
typename _Tp,
424 typename _BinaryPredicate>
426 __search_n(_ForwardIterator __first, _ForwardIterator __last,
427 _Integer __count,
const _Tp& __val,
430 while (__first != __last && !
bool(__binary_pred(*__first, __val)))
433 while (__first != __last)
435 typename iterator_traits<_ForwardIterator>::difference_type
437 _ForwardIterator __i = __first;
439 while (__i != __last && __n != 1 &&
bool(__binary_pred(*__i, __val)))
449 while (__first != __last
450 && !
bool(__binary_pred(*__first, __val)))
462 template<
typename _RandomAccessIter,
typename _Integer,
typename _Tp,
463 typename _BinaryPredicate>
465 __search_n(_RandomAccessIter __first, _RandomAccessIter __last,
466 _Integer __count,
const _Tp& __val,
470 typedef typename std::iterator_traits<_RandomAccessIter>::difference_type
473 _DistanceType __tailSize = __last - __first;
474 const _DistanceType __pattSize = __count;
476 if (__tailSize < __pattSize)
479 const _DistanceType __skipOffset = __pattSize - 1;
480 _RandomAccessIter __lookAhead = __first + __skipOffset;
481 __tailSize -= __pattSize;
487 while (!
bool(__binary_pred(*__lookAhead, __val)))
489 if (__tailSize < __pattSize)
491 __lookAhead += __pattSize;
492 __tailSize -= __pattSize;
494 _DistanceType __remainder = __skipOffset;
495 for (_RandomAccessIter __backTrack = __lookAhead - 1;
496 __binary_pred(*__backTrack, __val); --__backTrack)
498 if (--__remainder == 0)
499 return (__lookAhead - __skipOffset);
501 if (__remainder > __tailSize)
503 __lookAhead += __remainder;
504 __tailSize -= __remainder;
509 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
511 __find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
512 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
513 forward_iterator_tag, forward_iterator_tag)
515 if (__first2 == __last2)
519 _ForwardIterator1 __result = __last1;
522 _ForwardIterator1 __new_result
524 if (__new_result == __last1)
528 __result = __new_result;
529 __first1 = __new_result;
536 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
537 typename _BinaryPredicate>
539 __find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
540 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
541 forward_iterator_tag, forward_iterator_tag,
542 _BinaryPredicate __comp)
544 if (__first2 == __last2)
548 _ForwardIterator1 __result = __last1;
551 _ForwardIterator1 __new_result
554 if (__new_result == __last1)
558 __result = __new_result;
559 __first1 = __new_result;
567 template<
typename _B
idirectionalIterator1,
typename _B
idirectionalIterator2>
568 _BidirectionalIterator1
569 __find_end(_BidirectionalIterator1 __first1,
570 _BidirectionalIterator1 __last1,
571 _BidirectionalIterator2 __first2,
572 _BidirectionalIterator2 __last2,
573 bidirectional_iterator_tag, bidirectional_iterator_tag)
576 __glibcxx_function_requires(_BidirectionalIteratorConcept<
577 _BidirectionalIterator1>)
578 __glibcxx_function_requires(_BidirectionalIteratorConcept<
579 _BidirectionalIterator2>)
581 typedef reverse_iterator<_BidirectionalIterator1> _RevIterator1;
582 typedef reverse_iterator<_BidirectionalIterator2> _RevIterator2;
584 _RevIterator1 __rlast1(__first1);
585 _RevIterator2 __rlast2(__first2);
586 _RevIterator1 __rresult = _GLIBCXX_STD_P::
search(_RevIterator1(__last1),
588 _RevIterator2(__last2),
591 if (__rresult == __rlast1)
595 _BidirectionalIterator1 __result = __rresult.base();
601 template<
typename _BidirectionalIterator1,
typename _BidirectionalIterator2,
602 typename _BinaryPredicate>
603 _BidirectionalIterator1
604 __find_end(_BidirectionalIterator1 __first1,
605 _BidirectionalIterator1 __last1,
606 _BidirectionalIterator2 __first2,
607 _BidirectionalIterator2 __last2,
608 bidirectional_iterator_tag, bidirectional_iterator_tag,
609 _BinaryPredicate __comp)
612 __glibcxx_function_requires(_BidirectionalIteratorConcept<
613 _BidirectionalIterator1>)
614 __glibcxx_function_requires(_BidirectionalIteratorConcept<
615 _BidirectionalIterator2>)
617 typedef reverse_iterator<_BidirectionalIterator1> _RevIterator1;
618 typedef reverse_iterator<_BidirectionalIterator2> _RevIterator2;
620 _RevIterator1 __rlast1(__first1);
621 _RevIterator2 __rlast2(__first2);
622 _RevIterator1 __rresult = std::
search(_RevIterator1(__last1), __rlast1,
623 _RevIterator2(__last2), __rlast2,
626 if (__rresult == __rlast1)
630 _BidirectionalIterator1 __result = __rresult.base();
661 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
662 inline _ForwardIterator1
663 find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
664 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
667 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
668 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
669 __glibcxx_function_requires(_EqualOpConcept<
670 typename iterator_traits<_ForwardIterator1>::value_type,
671 typename iterator_traits<_ForwardIterator2>::value_type>)
672 __glibcxx_requires_valid_range(__first1, __last1);
673 __glibcxx_requires_valid_range(__first2, __last2);
675 return std::__find_end(__first1, __last1, __first2, __last2,
707 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
708 typename _BinaryPredicate>
709 inline _ForwardIterator1
710 find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
711 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
712 _BinaryPredicate __comp)
715 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
716 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
717 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
718 typename iterator_traits<_ForwardIterator1>::value_type,
719 typename iterator_traits<_ForwardIterator2>::value_type>)
720 __glibcxx_requires_valid_range(__first1, __last1);
721 __glibcxx_requires_valid_range(__first2, __last2);
723 return std::__find_end(__first1, __last1, __first2, __last2,
729 #ifdef __GXX_EXPERIMENTAL_CXX0X__
742 template<
typename _InputIterator,
typename _Predicate>
744 all_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
759 template<
typename _InputIterator,
typename _Predicate>
761 none_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
776 template<
typename _InputIterator,
typename _Predicate>
778 any_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
791 template<
typename _InputIterator,
typename _Predicate>
792 inline _InputIterator
797 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
798 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
799 typename iterator_traits<_InputIterator>::value_type>)
800 __glibcxx_requires_valid_range(__first, __last);
815 template<
typename _InputIterator,
typename _Predicate>
833 template<
typename _ForwardIterator,
typename _Predicate>
839 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
840 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
841 typename iterator_traits<_ForwardIterator>::value_type>)
844 __glibcxx_requires_valid_range(__first, __last);
846 typedef typename iterator_traits<_ForwardIterator>::difference_type
850 _DistanceType __half;
851 _ForwardIterator __middle;
858 if (__pred(*__middle))
862 __len = __len - __half - 1;
886 template<
typename _InputIterator,
typename _OutputIterator,
typename _Tp>
889 _OutputIterator __result,
const _Tp& __value)
892 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
893 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
894 typename iterator_traits<_InputIterator>::value_type>)
895 __glibcxx_function_requires(_EqualOpConcept<
896 typename iterator_traits<_InputIterator>::value_type, _Tp>)
897 __glibcxx_requires_valid_range(__first, __last);
899 for (; __first != __last; ++__first)
900 if (!(*__first == __value))
902 *__result = *__first;
923 template<
typename _InputIterator,
typename _OutputIterator,
927 _OutputIterator __result, _Predicate __pred)
930 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
931 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
932 typename iterator_traits<_InputIterator>::value_type>)
933 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
934 typename iterator_traits<_InputIterator>::value_type>)
935 __glibcxx_requires_valid_range(__first, __last);
937 for (; __first != __last; ++__first)
938 if (!
bool(__pred(*__first)))
940 *__result = *__first;
946 #ifdef __GXX_EXPERIMENTAL_CXX0X__
962 template<
typename _InputIterator,
typename _OutputIterator,
965 copy_if(_InputIterator __first, _InputIterator __last,
966 _OutputIterator __result, _Predicate __pred)
969 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
970 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
971 typename iterator_traits<_InputIterator>::value_type>)
972 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
973 typename iterator_traits<_InputIterator>::value_type>)
974 __glibcxx_requires_valid_range(__first, __last);
976 for (; __first != __last; ++__first)
977 if (__pred(*__first))
979 *__result = *__first;
986 template<
typename _InputIterator,
typename _Size,
typename _OutputIterator>
988 __copy_n(_InputIterator __first, _Size __n,
989 _OutputIterator __result, input_iterator_tag)
991 for (; __n > 0; --__n)
993 *__result = *__first;
1000 template<
typename _RandomAccessIterator,
typename _Size,
1001 typename _OutputIterator>
1002 inline _OutputIterator
1003 __copy_n(_RandomAccessIterator __first, _Size __n,
1004 _OutputIterator __result, random_access_iterator_tag)
1005 {
return std::copy(__first, __first + __n, __result); }
1020 template<
typename _InputIterator,
typename _Size,
typename _OutputIterator>
1021 inline _OutputIterator
1022 copy_n(_InputIterator __first, _Size __n, _OutputIterator __result)
1025 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1026 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1027 typename iterator_traits<_InputIterator>::value_type>)
1029 return std::__copy_n(__first, __n, __result,
1048 template<
typename _InputIterator,
typename _OutputIterator1,
1049 typename _OutputIterator2,
typename _Predicate>
1050 pair<_OutputIterator1, _OutputIterator2>
1052 _OutputIterator1 __out_true, _OutputIterator2 __out_false,
1056 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1057 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator1,
1058 typename iterator_traits<_InputIterator>::value_type>)
1059 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator2,
1060 typename iterator_traits<_InputIterator>::value_type>)
1061 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
1062 typename iterator_traits<_InputIterator>::value_type>)
1063 __glibcxx_requires_valid_range(__first, __last);
1065 for (; __first != __last; ++__first)
1066 if (__pred(*__first))
1068 *__out_true = *__first;
1073 *__out_false = *__first;
1098 template<
typename _ForwardIterator,
typename _Tp>
1100 remove(_ForwardIterator __first, _ForwardIterator __last,
1104 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1106 __glibcxx_function_requires(_EqualOpConcept<
1107 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
1108 __glibcxx_requires_valid_range(__first, __last);
1111 if(__first == __last)
1113 _ForwardIterator __result = __first;
1115 for(; __first != __last; ++__first)
1116 if(!(*__first == __value))
1118 *__result = _GLIBCXX_MOVE(*__first);
1141 template<
typename _ForwardIterator,
typename _Predicate>
1143 remove_if(_ForwardIterator __first, _ForwardIterator __last,
1147 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1149 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
1150 typename iterator_traits<_ForwardIterator>::value_type>)
1151 __glibcxx_requires_valid_range(__first, __last);
1154 if(__first == __last)
1156 _ForwardIterator __result = __first;
1158 for(; __first != __last; ++__first)
1159 if(!
bool(__pred(*__first)))
1161 *__result = _GLIBCXX_MOVE(*__first);
1181 template<
typename _ForwardIterator>
1183 unique(_ForwardIterator __first, _ForwardIterator __last)
1186 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1188 __glibcxx_function_requires(_EqualityComparableConcept<
1189 typename iterator_traits<_ForwardIterator>::value_type>)
1190 __glibcxx_requires_valid_range(__first, __last);
1194 if (__first == __last)
1198 _ForwardIterator __dest = __first;
1200 while (++__first != __last)
1201 if (!(*__dest == *__first))
1202 *++__dest = _GLIBCXX_MOVE(*__first);
1221 template<
typename _ForwardIterator,
typename _BinaryPredicate>
1223 unique(_ForwardIterator __first, _ForwardIterator __last,
1224 _BinaryPredicate __binary_pred)
1227 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1229 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1230 typename iterator_traits<_ForwardIterator>::value_type,
1231 typename iterator_traits<_ForwardIterator>::value_type>)
1232 __glibcxx_requires_valid_range(__first, __last);
1236 if (__first == __last)
1240 _ForwardIterator __dest = __first;
1242 while (++__first != __last)
1243 if (!
bool(__binary_pred(*__dest, *__first)))
1244 *++__dest = _GLIBCXX_MOVE(*__first);
1253 template<
typename _ForwardIterator,
typename _OutputIterator>
1256 _OutputIterator __result,
1260 _ForwardIterator __next = __first;
1261 *__result = *__first;
1262 while (++__next != __last)
1263 if (!(*__first == *__next))
1266 *++__result = *__first;
1276 template<
typename _InputIterator,
typename _OutputIterator>
1279 _OutputIterator __result,
1283 typename iterator_traits<_InputIterator>::value_type __value = *__first;
1284 *__result = __value;
1285 while (++__first != __last)
1286 if (!(__value == *__first))
1289 *++__result = __value;
1299 template<
typename _InputIterator,
typename _ForwardIterator>
1302 _ForwardIterator __result,
1306 *__result = *__first;
1307 while (++__first != __last)
1308 if (!(*__result == *__first))
1309 *++__result = *__first;
1319 template<
typename _ForwardIterator,
typename _OutputIterator,
1320 typename _BinaryPredicate>
1323 _OutputIterator __result, _BinaryPredicate __binary_pred,
1327 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1328 typename iterator_traits<_ForwardIterator>::value_type,
1329 typename iterator_traits<_ForwardIterator>::value_type>)
1331 _ForwardIterator __next = __first;
1332 *__result = *__first;
1333 while (++__next != __last)
1334 if (!
bool(__binary_pred(*__first, *__next)))
1337 *++__result = *__first;
1348 template<
typename _InputIterator,
typename _OutputIterator,
1349 typename _BinaryPredicate>
1352 _OutputIterator __result, _BinaryPredicate __binary_pred,
1356 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1357 typename iterator_traits<_InputIterator>::value_type,
1358 typename iterator_traits<_InputIterator>::value_type>)
1360 typename iterator_traits<_InputIterator>::value_type __value = *__first;
1361 *__result = __value;
1362 while (++__first != __last)
1363 if (!
bool(__binary_pred(__value, *__first)))
1366 *++__result = __value;
1377 template<
typename _InputIterator,
typename _ForwardIterator,
1378 typename _BinaryPredicate>
1381 _ForwardIterator __result, _BinaryPredicate __binary_pred,
1385 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1386 typename iterator_traits<_ForwardIterator>::value_type,
1387 typename iterator_traits<_InputIterator>::value_type>)
1389 *__result = *__first;
1390 while (++__first != __last)
1391 if (!
bool(__binary_pred(*__result, *__first)))
1392 *++__result = *__first;
1401 template<
typename _B
idirectionalIterator>
1403 __reverse(_BidirectionalIterator __first, _BidirectionalIterator __last,
1407 if (__first == __last || __first == --__last)
1421 template<
typename _RandomAccessIterator>
1423 __reverse(_RandomAccessIterator __first, _RandomAccessIterator __last,
1426 if (__first == __last)
1429 while (__first < __last)
1449 template<
typename _B
idirectionalIterator>
1451 reverse(_BidirectionalIterator __first, _BidirectionalIterator __last)
1454 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
1455 _BidirectionalIterator>)
1456 __glibcxx_requires_valid_range(__first, __last);
1476 template<
typename _B
idirectionalIterator,
typename _OutputIterator>
1478 reverse_copy(_BidirectionalIterator __first, _BidirectionalIterator __last,
1479 _OutputIterator __result)
1482 __glibcxx_function_requires(_BidirectionalIteratorConcept<
1483 _BidirectionalIterator>)
1484 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1485 typename iterator_traits<_BidirectionalIterator>::value_type>)
1486 __glibcxx_requires_valid_range(__first, __last);
1488 while (__first != __last)
1491 *__result = *__last;
1501 template<
typename _Eucl
ideanRingElement>
1502 _EuclideanRingElement
1503 __gcd(_EuclideanRingElement __m, _EuclideanRingElement __n)
1507 _EuclideanRingElement __t = __m % __n;
1515 template<
typename _ForwardIterator>
1518 _ForwardIterator __middle,
1519 _ForwardIterator __last,
1522 if (__first == __middle || __last == __middle)
1525 _ForwardIterator __first2 = __middle;
1531 if (__first == __middle)
1532 __middle = __first2;
1534 while (__first2 != __last);
1536 __first2 = __middle;
1538 while (__first2 != __last)
1543 if (__first == __middle)
1544 __middle = __first2;
1545 else if (__first2 == __last)
1546 __first2 = __middle;
1551 template<
typename _B
idirectionalIterator>
1554 _BidirectionalIterator __middle,
1555 _BidirectionalIterator __last,
1559 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
1560 _BidirectionalIterator>)
1562 if (__first == __middle || __last == __middle)
1568 while (__first != __middle && __middle != __last)
1574 if (__first == __middle)
1581 template<
typename _RandomAccessIterator>
1584 _RandomAccessIterator __middle,
1585 _RandomAccessIterator __last,
1589 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
1590 _RandomAccessIterator>)
1592 if (__first == __middle || __last == __middle)
1595 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
1597 typedef typename iterator_traits<_RandomAccessIterator>::value_type
1600 const _Distance __n = __last - __first;
1601 const _Distance __k = __middle - __first;
1602 const _Distance __l = __n - __k;
1612 for (_Distance __i = 0; __i < __d; __i++)
1614 _ValueType __tmp = _GLIBCXX_MOVE(*__first);
1615 _RandomAccessIterator __p = __first;
1619 for (_Distance __j = 0; __j < __l / __d; __j++)
1621 if (__p > __first + __l)
1623 *__p = _GLIBCXX_MOVE(*(__p - __l));
1627 *__p = _GLIBCXX_MOVE(*(__p + __k));
1633 for (_Distance __j = 0; __j < __k / __d - 1; __j ++)
1635 if (__p < __last - __k)
1637 *__p = _GLIBCXX_MOVE(*(__p + __k));
1640 *__p = _GLIBCXX_MOVE(*(__p - __l));
1645 *__p = _GLIBCXX_MOVE(__tmp);
1669 template<
typename _ForwardIterator>
1671 rotate(_ForwardIterator __first, _ForwardIterator __middle,
1672 _ForwardIterator __last)
1675 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1677 __glibcxx_requires_valid_range(__first, __middle);
1678 __glibcxx_requires_valid_range(__middle, __last);
1680 typedef typename iterator_traits<_ForwardIterator>::iterator_category
1703 template<
typename _ForwardIterator,
typename _OutputIterator>
1706 _ForwardIterator __last, _OutputIterator __result)
1709 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
1710 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1711 typename iterator_traits<_ForwardIterator>::value_type>)
1712 __glibcxx_requires_valid_range(__first, __middle);
1713 __glibcxx_requires_valid_range(__middle, __last);
1715 return std::copy(__first, __middle,
1716 std::copy(__middle, __last, __result));
1720 template<
typename _ForwardIterator,
typename _Predicate>
1725 if (__first == __last)
1728 while (__pred(*__first))
1729 if (++__first == __last)
1732 _ForwardIterator __next = __first;
1734 while (++__next != __last)
1735 if (__pred(*__next))
1745 template<
typename _B
idirectionalIterator,
typename _Predicate>
1746 _BidirectionalIterator
1747 __partition(_BidirectionalIterator __first, _BidirectionalIterator __last,
1753 if (__first == __last)
1755 else if (__pred(*__first))
1761 if (__first == __last)
1763 else if (!
bool(__pred(*__last)))
1775 template<
typename _ForwardIterator,
typename _Predicate,
typename _Distance>
1778 _ForwardIterator __last,
1779 _Predicate __pred, _Distance __len)
1782 return __pred(*__first) ? __last : __first;
1783 _ForwardIterator __middle = __first;
1799 template<
typename _ForwardIterator,
typename _Pointer,
typename _Predicate,
1803 _ForwardIterator __last,
1804 _Predicate __pred, _Distance __len,
1806 _Distance __buffer_size)
1808 if (__len <= __buffer_size)
1810 _ForwardIterator __result1 = __first;
1811 _Pointer __result2 = __buffer;
1812 for (; __first != __last; ++__first)
1813 if (__pred(*__first))
1815 *__result1 = *__first;
1820 *__result2 = *__first;
1823 std::copy(__buffer, __result2, __result1);
1828 _ForwardIterator __middle = __first;
1830 _ForwardIterator __begin =
1832 __len / 2, __buffer,
1834 _ForwardIterator __end =
1837 __buffer, __buffer_size);
1861 template<
typename _ForwardIterator,
typename _Predicate>
1867 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1869 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
1870 typename iterator_traits<_ForwardIterator>::value_type>)
1871 __glibcxx_requires_valid_range(__first, __last);
1873 if (__first == __last)
1877 typedef typename iterator_traits<_ForwardIterator>::value_type
1879 typedef typename iterator_traits<_ForwardIterator>::difference_type
1884 if (__buf.
size() > 0)
1889 _DistanceType(__buf.
size()));
1898 template<
typename _RandomAccessIterator>
1901 _RandomAccessIterator __middle,
1902 _RandomAccessIterator __last)
1905 for (_RandomAccessIterator __i = __middle; __i < __last; ++__i)
1906 if (*__i < *__first)
1907 std::__pop_heap(__first, __middle, __i);
1911 template<
typename _RandomAccessIterator,
typename _Compare>
1914 _RandomAccessIterator __middle,
1915 _RandomAccessIterator __last, _Compare __comp)
1918 for (_RandomAccessIterator __i = __middle; __i < __last; ++__i)
1919 if (__comp(*__i, *__first))
1920 std::__pop_heap(__first, __middle, __i, __comp);
1943 template<
typename _InputIterator,
typename _RandomAccessIterator>
1944 _RandomAccessIterator
1946 _RandomAccessIterator __result_first,
1947 _RandomAccessIterator __result_last)
1949 typedef typename iterator_traits<_InputIterator>::value_type
1951 typedef typename iterator_traits<_RandomAccessIterator>::value_type
1953 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
1957 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1958 __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
1960 __glibcxx_function_requires(_LessThanOpConcept<_InputValueType,
1962 __glibcxx_function_requires(_LessThanComparableConcept<_OutputValueType>)
1963 __glibcxx_requires_valid_range(__first, __last);
1964 __glibcxx_requires_valid_range(__result_first, __result_last);
1966 if (__result_first == __result_last)
1967 return __result_last;
1968 _RandomAccessIterator __result_real_last = __result_first;
1969 while(__first != __last && __result_real_last != __result_last)
1971 *__result_real_last = *__first;
1972 ++__result_real_last;
1976 while (__first != __last)
1978 if (*__first < *__result_first)
1979 std::__adjust_heap(__result_first, _DistanceType(0),
1980 _DistanceType(__result_real_last
1982 _InputValueType(*__first));
1986 return __result_real_last;
2009 template<
typename _InputIterator,
typename _RandomAccessIterator,
typename _Compare>
2010 _RandomAccessIterator
2012 _RandomAccessIterator __result_first,
2013 _RandomAccessIterator __result_last,
2016 typedef typename iterator_traits<_InputIterator>::value_type
2018 typedef typename iterator_traits<_RandomAccessIterator>::value_type
2020 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
2024 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
2025 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
2026 _RandomAccessIterator>)
2027 __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
2029 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2030 _InputValueType, _OutputValueType>)
2031 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2032 _OutputValueType, _OutputValueType>)
2033 __glibcxx_requires_valid_range(__first, __last);
2034 __glibcxx_requires_valid_range(__result_first, __result_last);
2036 if (__result_first == __result_last)
2037 return __result_last;
2038 _RandomAccessIterator __result_real_last = __result_first;
2039 while(__first != __last && __result_real_last != __result_last)
2041 *__result_real_last = *__first;
2042 ++__result_real_last;
2046 while (__first != __last)
2048 if (__comp(*__first, *__result_first))
2049 std::__adjust_heap(__result_first, _DistanceType(0),
2050 _DistanceType(__result_real_last
2052 _InputValueType(*__first),
2057 return __result_real_last;
2061 template<
typename _RandomAccessIterator,
typename _Tp>
2065 _RandomAccessIterator __next = __last;
2067 while (__val < *__next)
2077 template<
typename _RandomAccessIterator,
typename _Tp,
typename _Compare>
2082 _RandomAccessIterator __next = __last;
2084 while (__comp(__val, *__next))
2094 template<
typename _RandomAccessIterator>
2097 _RandomAccessIterator __last)
2099 if (__first == __last)
2102 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
2104 typename iterator_traits<_RandomAccessIterator>::value_type
2106 if (__val < *__first)
2117 template<
typename _RandomAccessIterator,
typename _Compare>
2120 _RandomAccessIterator __last, _Compare __comp)
2122 if (__first == __last)
return;
2124 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
2126 typename iterator_traits<_RandomAccessIterator>::value_type
2128 if (__comp(__val, *__first))
2139 template<
typename _RandomAccessIterator>
2142 _RandomAccessIterator __last)
2144 typedef typename iterator_traits<_RandomAccessIterator>::value_type
2147 for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
2152 template<
typename _RandomAccessIterator,
typename _Compare>
2155 _RandomAccessIterator __last, _Compare __comp)
2157 typedef typename iterator_traits<_RandomAccessIterator>::value_type
2160 for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
2168 enum { _S_threshold = 16 };
2171 template<
typename _RandomAccessIterator>
2174 _RandomAccessIterator __last)
2176 if (__last - __first >
int(_S_threshold))
2186 template<
typename _RandomAccessIterator,
typename _Compare>
2189 _RandomAccessIterator __last, _Compare __comp)
2191 if (__last - __first >
int(_S_threshold))
2202 template<
typename _RandomAccessIterator,
typename _Tp>
2203 _RandomAccessIterator
2205 _RandomAccessIterator __last, _Tp __pivot)
2209 while (*__first < __pivot)
2212 while (__pivot < *__last)
2214 if (!(__first < __last))
2222 template<
typename _RandomAccessIterator,
typename _Tp,
typename _Compare>
2223 _RandomAccessIterator
2225 _RandomAccessIterator __last,
2226 _Tp __pivot, _Compare __comp)
2230 while (__comp(*__first, __pivot))
2233 while (__comp(__pivot, *__last))
2235 if (!(__first < __last))
2243 template<
typename _RandomAccessIterator,
typename _Size>
2246 _RandomAccessIterator __last,
2247 _Size __depth_limit)
2249 typedef typename iterator_traits<_RandomAccessIterator>::value_type
2252 while (__last - __first >
int(_S_threshold))
2254 if (__depth_limit == 0)
2260 _RandomAccessIterator __cut =
2275 template<
typename _RandomAccessIterator,
typename _Size,
typename _Compare>
2278 _RandomAccessIterator __last,
2279 _Size __depth_limit, _Compare __comp)
2281 typedef typename iterator_traits<_RandomAccessIterator>::value_type
2284 while (__last - __first >
int(_S_threshold))
2286 if (__depth_limit == 0)
2292 _RandomAccessIterator __cut =
2308 template<
typename _Size>
2313 for (__k = 0; __n != 0; __n >>= 1)
2320 {
return sizeof(int) * __CHAR_BIT__ - 1 - __builtin_clz(__n); }
2324 {
return sizeof(long) * __CHAR_BIT__ - 1 - __builtin_clzl(__n); }
2328 {
return sizeof(
long long) * __CHAR_BIT__ - 1 - __builtin_clzll(__n); }
2332 template<
typename _RandomAccessIterator,
typename _Size>
2334 __introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth,
2335 _RandomAccessIterator __last, _Size __depth_limit)
2337 typedef typename iterator_traits<_RandomAccessIterator>::value_type
2340 while (__last - __first > 3)
2342 if (__depth_limit == 0)
2351 _RandomAccessIterator __cut =
2368 template<
typename _RandomAccessIterator,
typename _Size,
typename _Compare>
2370 __introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth,
2371 _RandomAccessIterator __last, _Size __depth_limit,
2374 typedef typename iterator_traits<_RandomAccessIterator>::value_type
2377 while (__last - __first > 3)
2379 if (__depth_limit == 0)
2387 _RandomAccessIterator __cut =
2418 template<
typename _ForwardIterator,
typename _Tp>
2423 typedef typename iterator_traits<_ForwardIterator>::value_type
2425 typedef typename iterator_traits<_ForwardIterator>::difference_type
2429 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2430 __glibcxx_function_requires(_LessThanOpConcept<_ValueType, _Tp>)
2431 __glibcxx_requires_partitioned_lower(__first, __last, __val);
2434 _DistanceType __half;
2435 _ForwardIterator __middle;
2439 __half = __len >> 1;
2442 if (*__middle < __val)
2446 __len = __len - __half - 1;
2469 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2472 const _Tp& __val, _Compare __comp)
2474 typedef typename iterator_traits<_ForwardIterator>::value_type
2476 typedef typename iterator_traits<_ForwardIterator>::difference_type
2480 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2481 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2483 __glibcxx_requires_partitioned_lower_pred(__first, __last,
2487 _DistanceType __half;
2488 _ForwardIterator __middle;
2492 __half = __len >> 1;
2495 if (__comp(*__middle, __val))
2499 __len = __len - __half - 1;
2518 template<
typename _ForwardIterator,
typename _Tp>
2523 typedef typename iterator_traits<_ForwardIterator>::value_type
2525 typedef typename iterator_traits<_ForwardIterator>::difference_type
2529 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2530 __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>)
2531 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2534 _DistanceType __half;
2535 _ForwardIterator __middle;
2539 __half = __len >> 1;
2542 if (__val < *__middle)
2548 __len = __len - __half - 1;
2569 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2572 const _Tp& __val, _Compare __comp)
2574 typedef typename iterator_traits<_ForwardIterator>::value_type
2576 typedef typename iterator_traits<_ForwardIterator>::difference_type
2580 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2581 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2583 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2587 _DistanceType __half;
2588 _ForwardIterator __middle;
2592 __half = __len >> 1;
2595 if (__comp(__val, *__middle))
2601 __len = __len - __half - 1;
2624 template<
typename _ForwardIterator,
typename _Tp>
2625 pair<_ForwardIterator, _ForwardIterator>
2629 typedef typename iterator_traits<_ForwardIterator>::value_type
2631 typedef typename iterator_traits<_ForwardIterator>::difference_type
2635 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2636 __glibcxx_function_requires(_LessThanOpConcept<_ValueType, _Tp>)
2637 __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>)
2638 __glibcxx_requires_partitioned_lower(__first, __last, __val);
2639 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2642 _DistanceType __half;
2643 _ForwardIterator __middle, __left, __right;
2647 __half = __len >> 1;
2650 if (*__middle < __val)
2654 __len = __len - __half - 1;
2656 else if (__val < *__middle)
2686 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2687 pair<_ForwardIterator, _ForwardIterator>
2692 typedef typename iterator_traits<_ForwardIterator>::value_type
2694 typedef typename iterator_traits<_ForwardIterator>::difference_type
2698 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2699 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2701 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2703 __glibcxx_requires_partitioned_lower_pred(__first, __last,
2705 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2709 _DistanceType __half;
2710 _ForwardIterator __middle, __left, __right;
2714 __half = __len >> 1;
2717 if (__comp(*__middle, __val))
2721 __len = __len - __half - 1;
2723 else if (__comp(__val, *__middle))
2747 template<
typename _ForwardIterator,
typename _Tp>
2752 typedef typename iterator_traits<_ForwardIterator>::value_type
2756 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2757 __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>)
2758 __glibcxx_requires_partitioned_lower(__first, __last, __val);
2759 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2762 return __i != __last && !(__val < *__i);
2780 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2783 const _Tp& __val, _Compare __comp)
2785 typedef typename iterator_traits<_ForwardIterator>::value_type
2789 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2790 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2792 __glibcxx_requires_partitioned_lower_pred(__first, __last,
2794 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2798 return __i != __last && !bool(__comp(__val, *__i));
2804 template<
typename _BidirectionalIterator1,
typename _BidirectionalIterator2,
2805 typename _BidirectionalIterator3>
2806 _BidirectionalIterator3
2808 _BidirectionalIterator1 __last1,
2809 _BidirectionalIterator2 __first2,
2810 _BidirectionalIterator2 __last2,
2811 _BidirectionalIterator3 __result)
2813 if (__first1 == __last1)
2815 if (__first2 == __last2)
2821 if (*__last2 < *__last1)
2823 *--__result = *__last1;
2824 if (__first1 == __last1)
2830 *--__result = *__last2;
2831 if (__first2 == __last2)
2839 template<
typename _BidirectionalIterator1,
typename _BidirectionalIterator2,
2840 typename _BidirectionalIterator3,
typename _Compare>
2841 _BidirectionalIterator3
2843 _BidirectionalIterator1 __last1,
2844 _BidirectionalIterator2 __first2,
2845 _BidirectionalIterator2 __last2,
2846 _BidirectionalIterator3 __result,
2849 if (__first1 == __last1)
2851 if (__first2 == __last2)
2857 if (__comp(*__last2, *__last1))
2859 *--__result = *__last1;
2860 if (__first1 == __last1)
2866 *--__result = *__last2;
2867 if (__first2 == __last2)
2875 template<
typename _BidirectionalIterator1,
typename _BidirectionalIterator2,
2877 _BidirectionalIterator1
2879 _BidirectionalIterator1 __middle,
2880 _BidirectionalIterator1 __last,
2881 _Distance __len1, _Distance __len2,
2882 _BidirectionalIterator2 __buffer,
2883 _Distance __buffer_size)
2885 _BidirectionalIterator2 __buffer_end;
2886 if (__len1 > __len2 && __len2 <= __buffer_size)
2888 __buffer_end = std::copy(__middle, __last, __buffer);
2890 return std::copy(__buffer, __buffer_end, __first);
2892 else if (__len1 <= __buffer_size)
2894 __buffer_end = std::copy(__first, __middle, __buffer);
2895 std::copy(__middle, __last, __first);
2907 template<
typename _BidirectionalIterator,
typename _Distance,
2911 _BidirectionalIterator __middle,
2912 _BidirectionalIterator __last,
2913 _Distance __len1, _Distance __len2,
2914 _Pointer __buffer, _Distance __buffer_size)
2916 if (__len1 <= __len2 && __len1 <= __buffer_size)
2918 _Pointer __buffer_end = std::copy(__first, __middle, __buffer);
2922 else if (__len2 <= __buffer_size)
2924 _Pointer __buffer_end = std::copy(__middle, __last, __buffer);
2926 __buffer_end, __last);
2930 _BidirectionalIterator __first_cut = __first;
2931 _BidirectionalIterator __second_cut = __middle;
2932 _Distance __len11 = 0;
2933 _Distance __len22 = 0;
2934 if (__len1 > __len2)
2936 __len11 = __len1 / 2;
2944 __len22 = __len2 / 2;
2950 _BidirectionalIterator __new_middle =
2952 __len1 - __len11, __len22, __buffer,
2955 __len22, __buffer, __buffer_size);
2958 __len2 - __len22, __buffer, __buffer_size);
2963 template<
typename _BidirectionalIterator,
typename _Distance,
2964 typename _Pointer,
typename _Compare>
2967 _BidirectionalIterator __middle,
2968 _BidirectionalIterator __last,
2969 _Distance __len1, _Distance __len2,
2970 _Pointer __buffer, _Distance __buffer_size,
2973 if (__len1 <= __len2 && __len1 <= __buffer_size)
2975 _Pointer __buffer_end = std::copy(__first, __middle, __buffer);
2979 else if (__len2 <= __buffer_size)
2981 _Pointer __buffer_end = std::copy(__middle, __last, __buffer);
2987 _BidirectionalIterator __first_cut = __first;
2988 _BidirectionalIterator __second_cut = __middle;
2989 _Distance __len11 = 0;
2990 _Distance __len22 = 0;
2991 if (__len1 > __len2)
2993 __len11 = __len1 / 2;
3001 __len22 = __len2 / 2;
3007 _BidirectionalIterator __new_middle =
3009 __len1 - __len11, __len22, __buffer,
3012 __len22, __buffer, __buffer_size, __comp);
3015 __len2 - __len22, __buffer,
3016 __buffer_size, __comp);
3021 template<
typename _B
idirectionalIterator,
typename _Distance>
3024 _BidirectionalIterator __middle,
3025 _BidirectionalIterator __last,
3026 _Distance __len1, _Distance __len2)
3028 if (__len1 == 0 || __len2 == 0)
3030 if (__len1 + __len2 == 2)
3032 if (*__middle < *__first)
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;
3049 __len22 = __len2 / 2;
3055 _BidirectionalIterator __new_middle = __first_cut;
3060 __len1 - __len11, __len2 - __len22);
3064 template<
typename _BidirectionalIterator,
typename _Distance,
3068 _BidirectionalIterator __middle,
3069 _BidirectionalIterator __last,
3070 _Distance __len1, _Distance __len2,
3073 if (__len1 == 0 || __len2 == 0)
3075 if (__len1 + __len2 == 2)
3077 if (__comp(*__middle, *__first))
3081 _BidirectionalIterator __first_cut = __first;
3082 _BidirectionalIterator __second_cut = __middle;
3083 _Distance __len11 = 0;
3084 _Distance __len22 = 0;
3085 if (__len1 > __len2)
3087 __len11 = __len1 / 2;
3095 __len22 = __len2 / 2;
3102 _BidirectionalIterator __new_middle = __first_cut;
3105 __len11, __len22, __comp);
3107 __len1 - __len11, __len2 - __len22, __comp);
3128 template<
typename _B
idirectionalIterator>
3131 _BidirectionalIterator __middle,
3132 _BidirectionalIterator __last)
3134 typedef typename iterator_traits<_BidirectionalIterator>::value_type
3136 typedef typename iterator_traits<_BidirectionalIterator>::difference_type
3140 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
3141 _BidirectionalIterator>)
3142 __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
3143 __glibcxx_requires_sorted(__first, __middle);
3144 __glibcxx_requires_sorted(__middle, __last);
3146 if (__first == __middle || __middle == __last)
3154 if (__buf.
begin() == 0)
3158 __buf.
begin(), _DistanceType(__buf.
size()));
3183 template<
typename _B
idirectionalIterator,
typename _Compare>
3186 _BidirectionalIterator __middle,
3187 _BidirectionalIterator __last,
3190 typedef typename iterator_traits<_BidirectionalIterator>::value_type
3192 typedef typename iterator_traits<_BidirectionalIterator>::difference_type
3196 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
3197 _BidirectionalIterator>)
3198 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3199 _ValueType, _ValueType>)
3200 __glibcxx_requires_sorted_pred(__first, __middle, __comp);
3201 __glibcxx_requires_sorted_pred(__middle, __last, __comp);
3203 if (__first == __middle || __middle == __last)
3206 const _DistanceType __len1 =
std::distance(__first, __middle);
3207 const _DistanceType __len2 =
std::distance(__middle, __last);
3211 if (__buf.
begin() == 0)
3216 __buf.
begin(), _DistanceType(__buf.
size()),
3220 template<
typename _RandomAccessIterator1,
typename _RandomAccessIterator2,
3223 __merge_sort_loop(_RandomAccessIterator1 __first,
3224 _RandomAccessIterator1 __last,
3225 _RandomAccessIterator2 __result,
3226 _Distance __step_size)
3228 const _Distance __two_step = 2 * __step_size;
3230 while (__last - __first >= __two_step)
3233 __first + __step_size,
3234 __first + __two_step,
3236 __first += __two_step;
3239 __step_size =
std::min(_Distance(__last - __first), __step_size);
3241 __first + __step_size, __last,
3245 template<
typename _RandomAccessIterator1,
typename _RandomAccessIterator2,
3246 typename _Distance,
typename _Compare>
3248 __merge_sort_loop(_RandomAccessIterator1 __first,
3249 _RandomAccessIterator1 __last,
3250 _RandomAccessIterator2 __result, _Distance __step_size,
3253 const _Distance __two_step = 2 * __step_size;
3255 while (__last - __first >= __two_step)
3258 __first + __step_size, __first + __two_step,
3261 __first += __two_step;
3263 __step_size =
std::min(_Distance(__last - __first), __step_size);
3266 __first + __step_size, __last, __result, __comp);
3269 template<
typename _RandomAccessIterator,
typename _Distance>
3271 __chunk_insertion_sort(_RandomAccessIterator __first,
3272 _RandomAccessIterator __last,
3273 _Distance __chunk_size)
3275 while (__last - __first >= __chunk_size)
3278 __first += __chunk_size;
3283 template<
typename _RandomAccessIterator,
typename _Distance,
3286 __chunk_insertion_sort(_RandomAccessIterator __first,
3287 _RandomAccessIterator __last,
3288 _Distance __chunk_size, _Compare __comp)
3290 while (__last - __first >= __chunk_size)
3293 __first += __chunk_size;
3298 enum { _S_chunk_size = 7 };
3300 template<
typename _RandomAccessIterator,
typename _Po
inter>
3302 __merge_sort_with_buffer(_RandomAccessIterator __first,
3303 _RandomAccessIterator __last,
3306 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
3309 const _Distance __len = __last - __first;
3310 const _Pointer __buffer_last = __buffer + __len;
3312 _Distance __step_size = _S_chunk_size;
3313 std::__chunk_insertion_sort(__first, __last, __step_size);
3315 while (__step_size < __len)
3317 std::__merge_sort_loop(__first, __last, __buffer, __step_size);
3319 std::__merge_sort_loop(__buffer, __buffer_last, __first, __step_size);
3324 template<
typename _RandomAccessIterator,
typename _Po
inter,
typename _Compare>
3326 __merge_sort_with_buffer(_RandomAccessIterator __first,
3327 _RandomAccessIterator __last,
3328 _Pointer __buffer, _Compare __comp)
3330 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
3333 const _Distance __len = __last - __first;
3334 const _Pointer __buffer_last = __buffer + __len;
3336 _Distance __step_size = _S_chunk_size;
3337 std::__chunk_insertion_sort(__first, __last, __step_size, __comp);
3339 while (__step_size < __len)
3341 std::__merge_sort_loop(__first, __last, __buffer,
3342 __step_size, __comp);
3344 std::__merge_sort_loop(__buffer, __buffer_last, __first,
3345 __step_size, __comp);
3350 template<
typename _RandomAccessIterator,
typename _Pointer,
3353 __stable_sort_adaptive(_RandomAccessIterator __first,
3354 _RandomAccessIterator __last,
3355 _Pointer __buffer, _Distance __buffer_size)
3357 const _Distance __len = (__last - __first + 1) / 2;
3358 const _RandomAccessIterator __middle = __first + __len;
3359 if (__len > __buffer_size)
3361 std::__stable_sort_adaptive(__first, __middle,
3362 __buffer, __buffer_size);
3363 std::__stable_sort_adaptive(__middle, __last,
3364 __buffer, __buffer_size);
3368 std::__merge_sort_with_buffer(__first, __middle, __buffer);
3369 std::__merge_sort_with_buffer(__middle, __last, __buffer);
3372 _Distance(__middle - __first),
3373 _Distance(__last - __middle),
3374 __buffer, __buffer_size);
3377 template<
typename _RandomAccessIterator,
typename _Pointer,
3378 typename _Distance,
typename _Compare>
3380 __stable_sort_adaptive(_RandomAccessIterator __first,
3381 _RandomAccessIterator __last,
3382 _Pointer __buffer, _Distance __buffer_size,
3385 const _Distance __len = (__last - __first + 1) / 2;
3386 const _RandomAccessIterator __middle = __first + __len;
3387 if (__len > __buffer_size)
3389 std::__stable_sort_adaptive(__first, __middle, __buffer,
3390 __buffer_size, __comp);
3391 std::__stable_sort_adaptive(__middle, __last, __buffer,
3392 __buffer_size, __comp);
3396 std::__merge_sort_with_buffer(__first, __middle, __buffer, __comp);
3397 std::__merge_sort_with_buffer(__middle, __last, __buffer, __comp);
3400 _Distance(__middle - __first),
3401 _Distance(__last - __middle),
3402 __buffer, __buffer_size,
3407 template<
typename _RandomAccessIterator>
3410 _RandomAccessIterator __last)
3412 if (__last - __first < 15)
3417 _RandomAccessIterator __middle = __first + (__last - __first) / 2;
3426 template<
typename _RandomAccessIterator,
typename _Compare>
3429 _RandomAccessIterator __last, _Compare __comp)
3431 if (__last - __first < 15)
3436 _RandomAccessIterator __middle = __first + (__last - __first) / 2;
3468 template<
typename _InputIterator1,
typename _InputIterator2>
3470 includes(_InputIterator1 __first1, _InputIterator1 __last1,
3471 _InputIterator2 __first2, _InputIterator2 __last2)
3473 typedef typename iterator_traits<_InputIterator1>::value_type
3475 typedef typename iterator_traits<_InputIterator2>::value_type
3479 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
3480 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
3481 __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
3482 __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
3483 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
3484 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
3486 while (__first1 != __last1 && __first2 != __last2)
3487 if (*__first2 < *__first1)
3489 else if(*__first1 < *__first2)
3492 ++__first1, ++__first2;
3494 return __first2 == __last2;
3517 template<
typename _InputIterator1,
typename _InputIterator2,
3520 includes(_InputIterator1 __first1, _InputIterator1 __last1,
3521 _InputIterator2 __first2, _InputIterator2 __last2,
3524 typedef typename iterator_traits<_InputIterator1>::value_type
3526 typedef typename iterator_traits<_InputIterator2>::value_type
3530 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
3531 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
3532 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3533 _ValueType1, _ValueType2>)
3534 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3535 _ValueType2, _ValueType1>)
3536 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
3537 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
3539 while (__first1 != __last1 && __first2 != __last2)
3540 if (__comp(*__first2, *__first1))
3542 else if(__comp(*__first1, *__first2))
3545 ++__first1, ++__first2;
3547 return __first2 == __last2;
3572 template<
typename _B
idirectionalIterator>
3575 _BidirectionalIterator __last)
3578 __glibcxx_function_requires(_BidirectionalIteratorConcept<
3579 _BidirectionalIterator>)
3580 __glibcxx_function_requires(_LessThanComparableConcept<
3581 typename iterator_traits<_BidirectionalIterator>::value_type>)
3582 __glibcxx_requires_valid_range(__first, __last);
3584 if (__first == __last)
3586 _BidirectionalIterator __i = __first;
3595 _BidirectionalIterator __ii = __i;
3599 _BidirectionalIterator __j = __last;
3600 while (!(*__i < *--__j))
3629 template<
typename _B
idirectionalIterator,
typename _Compare>
3632 _BidirectionalIterator __last, _Compare __comp)
3635 __glibcxx_function_requires(_BidirectionalIteratorConcept<
3636 _BidirectionalIterator>)
3637 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3638 typename iterator_traits<_BidirectionalIterator>::value_type,
3639 typename iterator_traits<_BidirectionalIterator>::value_type>)
3640 __glibcxx_requires_valid_range(__first, __last);
3642 if (__first == __last)
3644 _BidirectionalIterator __i = __first;
3653 _BidirectionalIterator __ii = __i;
3655 if (__comp(*__i, *__ii))
3657 _BidirectionalIterator __j = __last;
3658 while (!
bool(__comp(*__i, *--__j)))
3685 template<
typename _B
idirectionalIterator>
3688 _BidirectionalIterator __last)
3691 __glibcxx_function_requires(_BidirectionalIteratorConcept<
3692 _BidirectionalIterator>)
3693 __glibcxx_function_requires(_LessThanComparableConcept<
3694 typename iterator_traits<_BidirectionalIterator>::value_type>)
3695 __glibcxx_requires_valid_range(__first, __last);
3697 if (__first == __last)
3699 _BidirectionalIterator __i = __first;
3708 _BidirectionalIterator __ii = __i;
3712 _BidirectionalIterator __j = __last;
3713 while (!(*--__j < *__i))
3742 template<
typename _B
idirectionalIterator,
typename _Compare>
3745 _BidirectionalIterator __last, _Compare __comp)
3748 __glibcxx_function_requires(_BidirectionalIteratorConcept<
3749 _BidirectionalIterator>)
3750 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3751 typename iterator_traits<_BidirectionalIterator>::value_type,
3752 typename iterator_traits<_BidirectionalIterator>::value_type>)
3753 __glibcxx_requires_valid_range(__first, __last);
3755 if (__first == __last)
3757 _BidirectionalIterator __i = __first;
3766 _BidirectionalIterator __ii = __i;
3768 if (__comp(*__ii, *__i))
3770 _BidirectionalIterator __j = __last;
3771 while (!
bool(__comp(*--__j, *__i)))
3802 template<
typename _InputIterator,
typename _OutputIterator,
typename _Tp>
3805 _OutputIterator __result,
3806 const _Tp& __old_value,
const _Tp& __new_value)
3809 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3810 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
3811 typename iterator_traits<_InputIterator>::value_type>)
3812 __glibcxx_function_requires(_EqualOpConcept<
3813 typename iterator_traits<_InputIterator>::value_type, _Tp>)
3814 __glibcxx_requires_valid_range(__first, __last);
3816 for (; __first != __last; ++__first, ++__result)
3817 if (*__first == __old_value)
3818 *__result = __new_value;
3820 *__result = *__first;
3839 template<
typename _InputIterator,
typename _OutputIterator,
3840 typename _Predicate,
typename _Tp>
3843 _OutputIterator __result,
3844 _Predicate __pred,
const _Tp& __new_value)
3847 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3848 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
3849 typename iterator_traits<_InputIterator>::value_type>)
3850 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
3851 typename iterator_traits<_InputIterator>::value_type>)
3852 __glibcxx_requires_valid_range(__first, __last);
3854 for (; __first != __last; ++__first, ++__result)
3855 if (__pred(*__first))
3856 *__result = __new_value;
3858 *__result = *__first;
3862 #ifdef __GXX_EXPERIMENTAL_CXX0X__
3870 template<
typename _ForwardIterator>
3872 is_sorted(_ForwardIterator __first, _ForwardIterator __last)
3884 template<
typename _ForwardIterator,
typename _Compare>
3886 is_sorted(_ForwardIterator __first, _ForwardIterator __last,
3898 template<
typename _ForwardIterator>
3903 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3904 __glibcxx_function_requires(_LessThanComparableConcept<
3905 typename iterator_traits<_ForwardIterator>::value_type>)
3906 __glibcxx_requires_valid_range(__first, __last);
3908 if (__first == __last)
3911 _ForwardIterator __next = __first;
3912 for (++__next; __next != __last; __first = __next, ++__next)
3913 if (*__next < *__first)
3927 template<
typename _ForwardIterator,
typename _Compare>
3933 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3934 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3935 typename iterator_traits<_ForwardIterator>::value_type,
3936 typename iterator_traits<_ForwardIterator>::value_type>)
3937 __glibcxx_requires_valid_range(__first, __last);
3939 if (__first == __last)
3942 _ForwardIterator __next = __first;
3943 for (++__next; __next != __last; __first = __next, ++__next)
3944 if (__comp(*__next, *__first))
3956 template<
typename _Tp>
3957 inline pair<const _Tp&, const _Tp&>
3961 __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
3963 return __b < __a ? pair<const _Tp&, const _Tp&>(__b, __a)
3975 template<
typename _Tp,
typename _Compare>
3976 inline pair<const _Tp&, const _Tp&>
3977 minmax(
const _Tp& __a,
const _Tp& __b, _Compare __comp)
3994 template<
typename _ForwardIterator>
3995 pair<_ForwardIterator, _ForwardIterator>
3999 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4000 __glibcxx_function_requires(_LessThanComparableConcept<
4001 typename iterator_traits<_ForwardIterator>::value_type>)
4002 __glibcxx_requires_valid_range(__first, __last);
4004 _ForwardIterator __next = __first;
4005 if (__first == __last
4006 || ++__next == __last)
4007 return std::make_pair(__first, __first);
4009 _ForwardIterator __min, __max;
4010 if (*__next < *__first)
4024 while (__first != __last)
4027 if (++__next == __last)
4029 if (*__first < *__min)
4031 else if (!(*__first < *__max))
4036 if (*__next < *__first)
4038 if (*__next < *__min)
4040 if (!(*__first < *__max))
4045 if (*__first < *__min)
4047 if (!(*__next < *__max))
4055 return std::make_pair(__min, __max);
4070 template<
typename _ForwardIterator,
typename _Compare>
4071 pair<_ForwardIterator, _ForwardIterator>
4076 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4077 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4078 typename iterator_traits<_ForwardIterator>::value_type,
4079 typename iterator_traits<_ForwardIterator>::value_type>)
4080 __glibcxx_requires_valid_range(__first, __last);
4082 _ForwardIterator __next = __first;
4083 if (__first == __last
4084 || ++__next == __last)
4085 return std::make_pair(__first, __first);
4087 _ForwardIterator __min, __max;
4088 if (__comp(*__next, *__first))
4102 while (__first != __last)
4105 if (++__next == __last)
4107 if (__comp(*__first, *__min))
4109 else if (!__comp(*__first, *__max))
4114 if (__comp(*__next, *__first))
4116 if (__comp(*__next, *__min))
4118 if (!__comp(*__first, *__max))
4123 if (__comp(*__first, *__min))
4125 if (!__comp(*__next, *__max))
4133 return std::make_pair(__min, __max);
4137 template<
typename _Tp>
4139 min(initializer_list<_Tp> __l)
4140 {
return *std::min_element(__l.begin(), __l.end()); }
4142 template<
typename _Tp,
typename _Compare>
4144 min(initializer_list<_Tp> __l, _Compare __comp)
4147 template<
typename _Tp>
4149 max(initializer_list<_Tp> __l)
4152 template<
typename _Tp,
typename _Compare>
4154 max(initializer_list<_Tp> __l, _Compare __comp)
4157 template<
typename _Tp>
4158 inline pair<_Tp, _Tp>
4159 minmax(initializer_list<_Tp> __l)
4161 pair<const _Tp*, const _Tp*> __p =
4163 return std::make_pair(*__p.first, *__p.second);
4166 template<
typename _Tp,
typename _Compare>
4167 inline pair<_Tp, _Tp>
4168 minmax(initializer_list<_Tp> __l, _Compare __comp)
4170 pair<const _Tp*, const _Tp*> __p =
4172 return std::make_pair(*__p.first, *__p.second);
4174 #endif // __GXX_EXPERIMENTAL_CXX0X__
4176 _GLIBCXX_END_NAMESPACE
4178 _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_P)
4192 template<typename _InputIterator, typename _Function>
4194 for_each(_InputIterator __first, _InputIterator __last, _Function __f)
4197 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4198 __glibcxx_requires_valid_range(__first, __last);
4199 for (; __first != __last; ++__first)
4213 template<
typename _InputIterator,
typename _Tp>
4214 inline _InputIterator
4215 find(_InputIterator __first, _InputIterator __last,
4219 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4220 __glibcxx_function_requires(_EqualOpConcept<
4221 typename iterator_traits<_InputIterator>::value_type, _Tp>)
4222 __glibcxx_requires_valid_range(__first, __last);
4237 template<
typename _InputIterator,
typename _Predicate>
4238 inline _InputIterator
4239 find_if(_InputIterator __first, _InputIterator __last,
4243 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4244 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4245 typename iterator_traits<_InputIterator>::value_type>)
4246 __glibcxx_requires_valid_range(__first, __last);
4266 template<
typename _InputIterator,
typename _ForwardIterator>
4269 _ForwardIterator __first2, _ForwardIterator __last2)
4272 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4273 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4274 __glibcxx_function_requires(_EqualOpConcept<
4275 typename iterator_traits<_InputIterator>::value_type,
4276 typename iterator_traits<_ForwardIterator>::value_type>)
4277 __glibcxx_requires_valid_range(__first1, __last1);
4278 __glibcxx_requires_valid_range(__first2, __last2);
4280 for (; __first1 != __last1; ++__first1)
4281 for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
4282 if (*__first1 == *__iter)
4305 template<
typename _InputIterator,
typename _ForwardIterator,
4306 typename _BinaryPredicate>
4309 _ForwardIterator __first2, _ForwardIterator __last2,
4310 _BinaryPredicate __comp)
4313 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4314 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4315 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4316 typename iterator_traits<_InputIterator>::value_type,
4317 typename iterator_traits<_ForwardIterator>::value_type>)
4318 __glibcxx_requires_valid_range(__first1, __last1);
4319 __glibcxx_requires_valid_range(__first2, __last2);
4321 for (; __first1 != __last1; ++__first1)
4322 for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
4323 if (__comp(*__first1, *__iter))
4337 template<
typename _ForwardIterator>
4342 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4343 __glibcxx_function_requires(_EqualityComparableConcept<
4344 typename iterator_traits<_ForwardIterator>::value_type>)
4345 __glibcxx_requires_valid_range(__first, __last);
4346 if (__first == __last)
4348 _ForwardIterator __next = __first;
4349 while(++__next != __last)
4351 if (*__first == *__next)
4369 template<
typename _ForwardIterator,
typename _BinaryPredicate>
4372 _BinaryPredicate __binary_pred)
4375 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4376 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4377 typename iterator_traits<_ForwardIterator>::value_type,
4378 typename iterator_traits<_ForwardIterator>::value_type>)
4379 __glibcxx_requires_valid_range(__first, __last);
4380 if (__first == __last)
4382 _ForwardIterator __next = __first;
4383 while(++__next != __last)
4385 if (__binary_pred(*__first, *__next))
4401 template<
typename _InputIterator,
typename _Tp>
4402 typename iterator_traits<_InputIterator>::difference_type
4403 count(_InputIterator __first, _InputIterator __last,
const _Tp& __value)
4406 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4407 __glibcxx_function_requires(_EqualOpConcept<
4408 typename iterator_traits<_InputIterator>::value_type, _Tp>)
4409 __glibcxx_requires_valid_range(__first, __last);
4410 typename iterator_traits<_InputIterator>::difference_type __n = 0;
4411 for (; __first != __last; ++__first)
4412 if (*__first == __value)
4426 template<
typename _InputIterator,
typename _Predicate>
4427 typename iterator_traits<_InputIterator>::difference_type
4428 count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
4431 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4432 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4433 typename iterator_traits<_InputIterator>::value_type>)
4434 __glibcxx_requires_valid_range(__first, __last);
4435 typename iterator_traits<_InputIterator>::difference_type __n = 0;
4436 for (; __first != __last; ++__first)
4437 if (__pred(*__first))
4466 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
4468 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
4469 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
4472 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
4473 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
4474 __glibcxx_function_requires(_EqualOpConcept<
4475 typename iterator_traits<_ForwardIterator1>::value_type,
4476 typename iterator_traits<_ForwardIterator2>::value_type>)
4477 __glibcxx_requires_valid_range(__first1, __last1);
4478 __glibcxx_requires_valid_range(__first2, __last2);
4481 if (__first1 == __last1 || __first2 == __last2)
4485 _ForwardIterator2 __p1(__first2);
4486 if (++__p1 == __last2)
4490 _ForwardIterator2 __p;
4491 _ForwardIterator1 __current = __first1;
4496 if (__first1 == __last1)
4500 __current = __first1;
4501 if (++__current == __last1)
4504 while (*__current == *__p)
4506 if (++__p == __last2)
4508 if (++__current == __last1)
4537 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
4538 typename _BinaryPredicate>
4540 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
4541 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
4542 _BinaryPredicate __predicate)
4545 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
4546 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
4547 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4548 typename iterator_traits<_ForwardIterator1>::value_type,
4549 typename iterator_traits<_ForwardIterator2>::value_type>)
4550 __glibcxx_requires_valid_range(__first1, __last1);
4551 __glibcxx_requires_valid_range(__first2, __last2);
4554 if (__first1 == __last1 || __first2 == __last2)
4558 _ForwardIterator2 __p1(__first2);
4559 if (++__p1 == __last2)
4561 while (__first1 != __last1
4562 && !
bool(__predicate(*__first1, *__first2)))
4568 _ForwardIterator2 __p;
4569 _ForwardIterator1 __current = __first1;
4573 while (__first1 != __last1
4574 && !
bool(__predicate(*__first1, *__first2)))
4576 if (__first1 == __last1)
4580 __current = __first1;
4581 if (++__current == __last1)
4584 while (__predicate(*__current, *__p))
4586 if (++__p == __last2)
4588 if (++__current == __last1)
4611 template<
typename _ForwardIterator,
typename _Integer,
typename _Tp>
4613 search_n(_ForwardIterator __first, _ForwardIterator __last,
4614 _Integer __count,
const _Tp& __val)
4617 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4618 __glibcxx_function_requires(_EqualOpConcept<
4619 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
4620 __glibcxx_requires_valid_range(__first, __last);
4647 template<
typename _ForwardIterator,
typename _Integer,
typename _Tp,
4648 typename _BinaryPredicate>
4650 search_n(_ForwardIterator __first, _ForwardIterator __last,
4651 _Integer __count,
const _Tp& __val,
4652 _BinaryPredicate __binary_pred)
4655 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4656 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4657 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
4658 __glibcxx_requires_valid_range(__first, __last);
4664 while (__first != __last && !
bool(__binary_pred(*__first, __val)))
4668 return std::__search_n(__first, __last, __count, __val, __binary_pred,
4689 template<
typename _InputIterator,
typename _OutputIterator,
4690 typename _UnaryOperation>
4693 _OutputIterator __result, _UnaryOperation __unary_op)
4696 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4697 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4699 __typeof__(__unary_op(*__first))>)
4700 __glibcxx_requires_valid_range(__first, __last);
4702 for (; __first != __last; ++__first, ++__result)
4703 *__result = __unary_op(*__first);
4725 template<
typename _InputIterator1,
typename _InputIterator2,
4726 typename _OutputIterator,
typename _BinaryOperation>
4728 transform(_InputIterator1 __first1, _InputIterator1 __last1,
4729 _InputIterator2 __first2, _OutputIterator __result,
4730 _BinaryOperation __binary_op)
4733 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4734 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4735 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4737 __typeof__(__binary_op(*__first1,*__first2))>)
4738 __glibcxx_requires_valid_range(__first1, __last1);
4740 for (; __first1 != __last1; ++__first1, ++__first2, ++__result)
4741 *__result = __binary_op(*__first1, *__first2);
4758 template<
typename _ForwardIterator,
typename _Tp>
4760 replace(_ForwardIterator __first, _ForwardIterator __last,
4761 const _Tp& __old_value,
const _Tp& __new_value)
4764 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4766 __glibcxx_function_requires(_EqualOpConcept<
4767 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
4768 __glibcxx_function_requires(_ConvertibleConcept<_Tp,
4769 typename iterator_traits<_ForwardIterator>::value_type>)
4770 __glibcxx_requires_valid_range(__first, __last);
4772 for (; __first != __last; ++__first)
4773 if (*__first == __old_value)
4774 *__first = __new_value;
4790 template<
typename _ForwardIterator,
typename _Predicate,
typename _Tp>
4793 _Predicate __pred,
const _Tp& __new_value)
4796 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4798 __glibcxx_function_requires(_ConvertibleConcept<_Tp,
4799 typename iterator_traits<_ForwardIterator>::value_type>)
4800 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4801 typename iterator_traits<_ForwardIterator>::value_type>)
4802 __glibcxx_requires_valid_range(__first, __last);
4804 for (; __first != __last; ++__first)
4805 if (__pred(*__first))
4806 *__first = __new_value;
4822 template<
typename _ForwardIterator,
typename _Generator>
4824 generate(_ForwardIterator __first, _ForwardIterator __last,
4828 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4829 __glibcxx_function_requires(_GeneratorConcept<_Generator,
4830 typename iterator_traits<_ForwardIterator>::value_type>)
4831 __glibcxx_requires_valid_range(__first, __last);
4833 for (; __first != __last; ++__first)
4850 template<
typename _OutputIterator,
typename _Size,
typename _Generator>
4855 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4857 __typeof__(__gen())>)
4859 for (; __n > 0; --__n, ++__first)
4886 template<
typename _InputIterator,
typename _OutputIterator>
4887 inline _OutputIterator
4889 _OutputIterator __result)
4892 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4893 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4894 typename iterator_traits<_InputIterator>::value_type>)
4895 __glibcxx_function_requires(_EqualityComparableConcept<
4896 typename iterator_traits<_InputIterator>::value_type>)
4897 __glibcxx_requires_valid_range(__first, __last);
4899 if (__first == __last)
4925 template<
typename _InputIterator,
typename _OutputIterator,
4926 typename _BinaryPredicate>
4927 inline _OutputIterator
4929 _OutputIterator __result,
4930 _BinaryPredicate __binary_pred)
4933 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4934 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4935 typename iterator_traits<_InputIterator>::value_type>)
4936 __glibcxx_requires_valid_range(__first, __last);
4938 if (__first == __last)
4957 template<
typename _RandomAccessIterator>
4962 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4963 _RandomAccessIterator>)
4964 __glibcxx_requires_valid_range(__first, __last);
4966 if (__first != __last)
4967 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
4968 std::iter_swap(__i, __first + (std::rand() % ((__i - __first) + 1)));
4985 template<
typename _RandomAccessIterator,
typename _RandomNumberGenerator>
4988 _RandomNumberGenerator& __rand)
4991 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4992 _RandomAccessIterator>)
4993 __glibcxx_requires_valid_range(__first, __last);
4995 if (__first == __last)
4997 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
5017 template<
typename _ForwardIterator,
typename _Predicate>
5018 inline _ForwardIterator
5019 partition(_ForwardIterator __first, _ForwardIterator __last,
5023 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
5025 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
5026 typename iterator_traits<_ForwardIterator>::value_type>)
5027 __glibcxx_requires_valid_range(__first, __last);
5051 template<
typename _RandomAccessIterator>
5054 _RandomAccessIterator __middle,
5055 _RandomAccessIterator __last)
5057 typedef typename iterator_traits<_RandomAccessIterator>::value_type
5061 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5062 _RandomAccessIterator>)
5063 __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
5064 __glibcxx_requires_valid_range(__first, __middle);
5065 __glibcxx_requires_valid_range(__middle, __last);
5090 template<
typename _RandomAccessIterator,
typename _Compare>
5093 _RandomAccessIterator __middle,
5094 _RandomAccessIterator __last,
5097 typedef typename iterator_traits<_RandomAccessIterator>::value_type
5101 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5102 _RandomAccessIterator>)
5103 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5104 _ValueType, _ValueType>)
5105 __glibcxx_requires_valid_range(__first, __middle);
5106 __glibcxx_requires_valid_range(__middle, __last);
5128 template<
typename _RandomAccessIterator>
5130 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
5131 _RandomAccessIterator __last)
5133 typedef typename iterator_traits<_RandomAccessIterator>::value_type
5137 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5138 _RandomAccessIterator>)
5139 __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
5140 __glibcxx_requires_valid_range(__first, __nth);
5141 __glibcxx_requires_valid_range(__nth, __last);
5143 if (__first == __last || __nth == __last)
5146 std::__introselect(__first, __nth, __last,
5167 template<
typename _RandomAccessIterator,
typename _Compare>
5169 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
5170 _RandomAccessIterator __last, _Compare __comp)
5172 typedef typename iterator_traits<_RandomAccessIterator>::value_type
5176 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5177 _RandomAccessIterator>)
5178 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5179 _ValueType, _ValueType>)
5180 __glibcxx_requires_valid_range(__first, __nth);
5181 __glibcxx_requires_valid_range(__nth, __last);
5183 if (__first == __last || __nth == __last)
5186 std::__introselect(__first, __nth, __last,
5187 std::__lg(__last - __first) * 2, __comp);
5205 template<
typename _RandomAccessIterator>
5207 sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
5209 typedef typename iterator_traits<_RandomAccessIterator>::value_type
5213 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5214 _RandomAccessIterator>)
5215 __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
5216 __glibcxx_requires_valid_range(__first, __last);
5218 if (__first != __last)
5241 template<
typename _RandomAccessIterator,
typename _Compare>
5243 sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
5246 typedef typename iterator_traits<_RandomAccessIterator>::value_type
5250 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5251 _RandomAccessIterator>)
5252 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, _ValueType,
5254 __glibcxx_requires_valid_range(__first, __last);
5256 if (__first != __last)
5259 std::__lg(__last - __first) * 2, __comp);
5282 template<
typename _InputIterator1,
typename _InputIterator2,
5283 typename _OutputIterator>
5285 merge(_InputIterator1 __first1, _InputIterator1 __last1,
5286 _InputIterator2 __first2, _InputIterator2 __last2,
5287 _OutputIterator __result)
5289 typedef typename iterator_traits<_InputIterator1>::value_type
5291 typedef typename iterator_traits<_InputIterator2>::value_type
5295 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5296 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5297 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5299 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5301 __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
5302 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5303 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5305 while (__first1 != __last1 && __first2 != __last2)
5307 if (*__first2 < *__first1)
5309 *__result = *__first2;
5314 *__result = *__first1;
5319 return std::copy(__first2, __last2, std::copy(__first1, __last1,
5345 template<
typename _InputIterator1,
typename _InputIterator2,
5346 typename _OutputIterator,
typename _Compare>
5348 merge(_InputIterator1 __first1, _InputIterator1 __last1,
5349 _InputIterator2 __first2, _InputIterator2 __last2,
5350 _OutputIterator __result, _Compare __comp)
5352 typedef typename iterator_traits<_InputIterator1>::value_type
5354 typedef typename iterator_traits<_InputIterator2>::value_type
5358 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5359 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5360 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5362 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5364 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5365 _ValueType2, _ValueType1>)
5366 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5367 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5369 while (__first1 != __last1 && __first2 != __last2)
5371 if (__comp(*__first2, *__first1))
5373 *__result = *__first2;
5378 *__result = *__first1;
5383 return std::copy(__first2, __last2, std::copy(__first1, __last1,
5405 template<
typename _RandomAccessIterator>
5407 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
5409 typedef typename iterator_traits<_RandomAccessIterator>::value_type
5411 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
5415 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5416 _RandomAccessIterator>)
5417 __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
5418 __glibcxx_requires_valid_range(__first, __last);
5422 if (__buf.
begin() == 0)
5425 std::__stable_sort_adaptive(__first, __last, __buf.
begin(),
5426 _DistanceType(__buf.
size()));
5447 template<
typename _RandomAccessIterator,
typename _Compare>
5449 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
5452 typedef typename iterator_traits<_RandomAccessIterator>::value_type
5454 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
5458 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5459 _RandomAccessIterator>)
5460 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5463 __glibcxx_requires_valid_range(__first, __last);
5467 if (__buf.
begin() == 0)
5470 std::__stable_sort_adaptive(__first, __last, __buf.
begin(),
5471 _DistanceType(__buf.
size()), __comp);
5493 template<
typename _InputIterator1,
typename _InputIterator2,
5494 typename _OutputIterator>
5496 set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5497 _InputIterator2 __first2, _InputIterator2 __last2,
5498 _OutputIterator __result)
5500 typedef typename iterator_traits<_InputIterator1>::value_type
5502 typedef typename iterator_traits<_InputIterator2>::value_type
5506 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5507 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5508 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5510 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5512 __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
5513 __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
5514 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5515 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5517 while (__first1 != __last1 && __first2 != __last2)
5519 if (*__first1 < *__first2)
5521 *__result = *__first1;
5524 else if (*__first2 < *__first1)
5526 *__result = *__first2;
5531 *__result = *__first1;
5537 return std::copy(__first2, __last2, std::copy(__first1, __last1,
5560 template<
typename _InputIterator1,
typename _InputIterator2,
5561 typename _OutputIterator,
typename _Compare>
5563 set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5564 _InputIterator2 __first2, _InputIterator2 __last2,
5565 _OutputIterator __result, _Compare __comp)
5567 typedef typename iterator_traits<_InputIterator1>::value_type
5569 typedef typename iterator_traits<_InputIterator2>::value_type
5573 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5574 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5575 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5577 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5579 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5580 _ValueType1, _ValueType2>)
5581 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5582 _ValueType2, _ValueType1>)
5583 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5584 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5586 while (__first1 != __last1 && __first2 != __last2)
5588 if (__comp(*__first1, *__first2))
5590 *__result = *__first1;
5593 else if (__comp(*__first2, *__first1))
5595 *__result = *__first2;
5600 *__result = *__first1;
5606 return std::copy(__first2, __last2, std::copy(__first1, __last1,
5627 template<
typename _InputIterator1,
typename _InputIterator2,
5628 typename _OutputIterator>
5631 _InputIterator2 __first2, _InputIterator2 __last2,
5632 _OutputIterator __result)
5634 typedef typename iterator_traits<_InputIterator1>::value_type
5636 typedef typename iterator_traits<_InputIterator2>::value_type
5640 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5641 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5642 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5644 __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
5645 __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
5646 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5647 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5649 while (__first1 != __last1 && __first2 != __last2)
5650 if (*__first1 < *__first2)
5652 else if (*__first2 < *__first1)
5656 *__result = *__first1;
5684 template<
typename _InputIterator1,
typename _InputIterator2,
5685 typename _OutputIterator,
typename _Compare>
5688 _InputIterator2 __first2, _InputIterator2 __last2,
5689 _OutputIterator __result, _Compare __comp)
5691 typedef typename iterator_traits<_InputIterator1>::value_type
5693 typedef typename iterator_traits<_InputIterator2>::value_type
5697 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5698 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5699 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5701 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5702 _ValueType1, _ValueType2>)
5703 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5704 _ValueType2, _ValueType1>)
5705 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5706 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5708 while (__first1 != __last1 && __first2 != __last2)
5709 if (__comp(*__first1, *__first2))
5711 else if (__comp(*__first2, *__first1))
5715 *__result = *__first1;
5742 template<
typename _InputIterator1,
typename _InputIterator2,
5743 typename _OutputIterator>
5746 _InputIterator2 __first2, _InputIterator2 __last2,
5747 _OutputIterator __result)
5749 typedef typename iterator_traits<_InputIterator1>::value_type
5751 typedef typename iterator_traits<_InputIterator2>::value_type
5755 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5756 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5757 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5759 __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
5760 __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
5761 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5762 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5764 while (__first1 != __last1 && __first2 != __last2)
5765 if (*__first1 < *__first2)
5767 *__result = *__first1;
5771 else if (*__first2 < *__first1)
5778 return std::copy(__first1, __last1, __result);
5803 template<
typename _InputIterator1,
typename _InputIterator2,
5804 typename _OutputIterator,
typename _Compare>
5807 _InputIterator2 __first2, _InputIterator2 __last2,
5808 _OutputIterator __result, _Compare __comp)
5810 typedef typename iterator_traits<_InputIterator1>::value_type
5812 typedef typename iterator_traits<_InputIterator2>::value_type
5816 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5817 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5818 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5820 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5821 _ValueType1, _ValueType2>)
5822 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5823 _ValueType2, _ValueType1>)
5824 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5825 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5827 while (__first1 != __last1 && __first2 != __last2)
5828 if (__comp(*__first1, *__first2))
5830 *__result = *__first1;
5834 else if (__comp(*__first2, *__first1))
5841 return std::copy(__first1, __last1, __result);
5861 template<
typename _InputIterator1,
typename _InputIterator2,
5862 typename _OutputIterator>
5865 _InputIterator2 __first2, _InputIterator2 __last2,
5866 _OutputIterator __result)
5868 typedef typename iterator_traits<_InputIterator1>::value_type
5870 typedef typename iterator_traits<_InputIterator2>::value_type
5874 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5875 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5876 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5878 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5880 __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
5881 __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
5882 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5883 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5885 while (__first1 != __last1 && __first2 != __last2)
5886 if (*__first1 < *__first2)
5888 *__result = *__first1;
5892 else if (*__first2 < *__first1)
5894 *__result = *__first2;
5903 return std::copy(__first2, __last2, std::copy(__first1,
5904 __last1, __result));
5927 template<
typename _InputIterator1,
typename _InputIterator2,
5928 typename _OutputIterator,
typename _Compare>
5931 _InputIterator2 __first2, _InputIterator2 __last2,
5932 _OutputIterator __result,
5935 typedef typename iterator_traits<_InputIterator1>::value_type
5937 typedef typename iterator_traits<_InputIterator2>::value_type
5941 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5942 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5943 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5945 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5947 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5948 _ValueType1, _ValueType2>)
5949 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5950 _ValueType2, _ValueType1>)
5951 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5952 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5954 while (__first1 != __last1 && __first2 != __last2)
5955 if (__comp(*__first1, *__first2))
5957 *__result = *__first1;
5961 else if (__comp(*__first2, *__first1))
5963 *__result = *__first2;
5972 return std::copy(__first2, __last2,
5973 std::copy(__first1, __last1, __result));
5984 template<
typename _ForwardIterator>
5989 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5990 __glibcxx_function_requires(_LessThanComparableConcept<
5991 typename iterator_traits<_ForwardIterator>::value_type>)
5992 __glibcxx_requires_valid_range(__first, __last);
5994 if (__first == __last)
5996 _ForwardIterator __result = __first;
5997 while (++__first != __last)
5998 if (*__first < *__result)
6012 template<
typename _ForwardIterator,
typename _Compare>
6018 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
6019 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
6020 typename iterator_traits<_ForwardIterator>::value_type,
6021 typename iterator_traits<_ForwardIterator>::value_type>)
6022 __glibcxx_requires_valid_range(__first, __last);
6024 if (__first == __last)
6026 _ForwardIterator __result = __first;
6027 while (++__first != __last)
6028 if (__comp(*__first, *__result))
6040 template<
typename _ForwardIterator>
6045 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
6046 __glibcxx_function_requires(_LessThanComparableConcept<
6047 typename iterator_traits<_ForwardIterator>::value_type>)
6048 __glibcxx_requires_valid_range(__first, __last);
6050 if (__first == __last)
6052 _ForwardIterator __result = __first;
6053 while (++__first != __last)
6054 if (*__result < *__first)
6068 template<
typename _ForwardIterator,
typename _Compare>
6074 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
6075 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
6076 typename iterator_traits<_ForwardIterator>::value_type,
6077 typename iterator_traits<_ForwardIterator>::value_type>)
6078 __glibcxx_requires_valid_range(__first, __last);
6080 if (__first == __last)
return __first;
6081 _ForwardIterator __result = __first;
6082 while (++__first != __last)
6083 if (__comp(*__result, *__first))
6088 _GLIBCXX_END_NESTED_NAMESPACE
bool none_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
Checks that a predicate is false for all the elements of a sequence.
void __merge_without_buffer(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last, _Distance __len1, _Distance __len2, _Compare __comp)
This is a helper function for the merge routines.
iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
size_type size() const
As per Table mumble.
_EuclideanRingElement __gcd(_EuclideanRingElement __m, _EuclideanRingElement __n)
_BidirectionalIterator __partition(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred, bidirectional_iterator_tag)
This is a helper function...
_ForwardIterator1 find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __comp)
Find last matching subsequence in a sequence using a predicate.
void __heap_select(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last)
This is a helper function for the sort routines.
_RandomAccessIterator __unguarded_partition(_RandomAccessIterator __first, _RandomAccessIterator __last, _Tp __pivot, _Compare __comp)
This is a helper function...
void make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
Construct a heap over a range using comparison functor.
void __merge_adaptive(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last, _Distance __len1, _Distance __len2, _Pointer __buffer, _Distance __buffer_size, _Compare __comp)
This is a helper function for the merge routines.
_RandomAccessIter __search_n(_RandomAccessIter __first, _RandomAccessIter __last, _Integer __count, const _Tp &__val, _BinaryPredicate __binary_pred, std::random_access_iterator_tag)
void __merge_without_buffer(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last, _Distance __len1, _Distance __len2)
This is a helper function for the merge routines.
pair holds two objects of arbitrary type.
_ForwardIterator lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp &__val, _Compare __comp)
Finds the first position in which val could be inserted without changing the ordering.
void __unguarded_insertion_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
This is a helper function for the sort routine.
_ForwardIterator2 swap_ranges(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2)
Swap the elements of two sequences.
void sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
Sort the elements of a sequence using a predicate for comparison.
_RandomAccessIterator __find_if_not(_RandomAccessIterator __first, _RandomAccessIterator __last, _Predicate __pred, random_access_iterator_tag)
This is an overload used by find_if_not() for the RAI case.
Bidirectional iterators support a superset of forward iterator operations.
void iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b)
Swaps the contents of two iterators.
_OutputIterator merge(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
Merges two sorted ranges.
void inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last, _Compare __comp)
Merges two sorted ranges in place.
_Function for_each(_InputIterator __first, _InputIterator __last, _Function __f)
Apply a function to every element of a sequence.
_ForwardIterator is_sorted_until(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
Determines the end of a sorted sequence using comparison functor.
void __rotate(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last, random_access_iterator_tag)
This is a helper function for the rotate algorithm.
_ForwardIterator __inplace_stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, _Distance __len)
This is a helper function...
_RandomAccessIterator partial_sort_copy(_InputIterator __first, _InputIterator __last, _RandomAccessIterator __result_first, _RandomAccessIterator __result_last, _Compare __comp)
Copy the smallest elements of a sequence using a predicate for comparison.
_OutputIterator unique_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _BinaryPredicate __binary_pred)
Copy a sequence, removing consecutive values using a predicate.
_ForwardIterator stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
Move elements for which a predicate is true to the beginning of a sequence, preserving relative order...
_ForwardIterator min_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
Return the minimum element in a range using comparison functor.
_OutputIterator replace_copy_if(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _Predicate __pred, const _Tp &__new_value)
Copy a sequence, replacing each value for which a predicate returns true with another value...
void __introsort_loop(_RandomAccessIterator __first, _RandomAccessIterator __last, _Size __depth_limit)
This is a helper function for the sort routine.
_RandomAccessIterator __unguarded_partition(_RandomAccessIterator __first, _RandomAccessIterator __last, _Tp __pivot)
This is a helper function...
bool is_partitioned(_InputIterator __first, _InputIterator __last, _Predicate __pred)
Checks whether the sequence is partitioned.
_ForwardIterator search_n(_ForwardIterator __first, _ForwardIterator __last, _Integer __count, const _Tp &__val, _BinaryPredicate __binary_pred)
Search a sequence for a number of consecutive values using a predicate.
_BI2 copy_backward(_BI1 __first, _BI1 __last, _BI2 __result)
Copies the range [first,last) into result.
_ForwardIterator unique(_ForwardIterator __first, _ForwardIterator __last, _BinaryPredicate __binary_pred)
Remove consecutive values from a sequence using a predicate.
bool any_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
Checks that a predicate is false for at least an element of a sequence.
const _Tp & __median(const _Tp &__a, const _Tp &__b, const _Tp &__c, _Compare __comp)
Find the median of three values using a predicate for comparison.
void __final_insertion_sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
This is a helper function for the sort routine.
_InputIterator __find_if_not(_InputIterator __first, _InputIterator __last, _Predicate __pred, input_iterator_tag)
This is an overload used by find_if_not() for the Input Iterator case.
const _Tp & max(const _Tp &, const _Tp &)
This does what you think it does.
size_type requested_size() const
Returns the size requested by the constructor; may be >size().
void advance(_InputIterator &__i, _Distance __n)
A generalization of pointer arithmetic.
pair< _ForwardIterator, _ForwardIterator > equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp &__val, _Compare __comp)
Finds the largest subrange in which val could be inserted at any place in it without changing the ord...
_ForwardIterator __unique_copy(_InputIterator __first, _InputIterator __last, _ForwardIterator __result, _BinaryPredicate __binary_pred, input_iterator_tag, forward_iterator_tag)
_BidirectionalIterator3 __merge_backward(_BidirectionalIterator1 __first1, _BidirectionalIterator1 __last1, _BidirectionalIterator2 __first2, _BidirectionalIterator2 __last2, _BidirectionalIterator3 __result)
This is a helper function for the merge routines.
_OutputIterator set_union(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
Return the union of two sorted ranges using a comparison functor.
_ForwardIterator __stable_partition_adaptive(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, _Distance __len, _Pointer __buffer, _Distance __buffer_size)
This is a helper function...
void __heap_select(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last, _Compare __comp)
This is a helper function for the sort routines.
bool is_sorted(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
Determines whether the elements of a sequence are sorted according to a comparison functor...
pair< _OutputIterator1, _OutputIterator2 > partition_copy(_InputIterator __first, _InputIterator __last, _OutputIterator1 __out_true, _OutputIterator2 __out_false, _Predicate __pred)
Copy the elements of a sequence to separate output sequences depending on the truth value of a predic...
void __unguarded_linear_insert(_RandomAccessIterator __last, _Tp __val, _Compare __comp)
This is a helper function for the sort routine.
_OutputIterator set_intersection(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
Return the intersection of two sorted ranges using comparison functor.
void __rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last, forward_iterator_tag)
This is a helper function for the rotate algorithm.
void rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last)
Rotate the elements of a sequence.
_OutputIterator __unique_copy(_ForwardIterator __first, _ForwardIterator __last, _OutputIterator __result, forward_iterator_tag, output_iterator_tag)
_BidirectionalIterator1 __rotate_adaptive(_BidirectionalIterator1 __first, _BidirectionalIterator1 __middle, _BidirectionalIterator1 __last, _Distance __len1, _Distance __len2, _BidirectionalIterator2 __buffer, _Distance __buffer_size)
This is a helper function for the merge routines.
_ForwardIterator __search_n(_ForwardIterator __first, _ForwardIterator __last, _Integer __count, const _Tp &__val, std::forward_iterator_tag)
_RandomAccessIterator __find_if(_RandomAccessIterator __first, _RandomAccessIterator __last, _Predicate __pred, random_access_iterator_tag)
This is an overload used by find_if() for the RAI case.
void __insertion_sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
This is a helper function for the sort routine.
_RandomAccessIterator __find(_RandomAccessIterator __first, _RandomAccessIterator __last, const _Tp &__val, random_access_iterator_tag)
This is an overload used by find() for the RAI case.
_OutputIterator set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
Return the symmetric difference of two sorted ranges using comparison functor.
const _Tp & __median(const _Tp &__a, const _Tp &__b, const _Tp &__c)
Find the median of three values.
void generate(_ForwardIterator __first, _ForwardIterator __last, _Generator __gen)
Assign the result of a function object to each value in a sequence.
iterator_traits< _InputIterator >::difference_type count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
Count the elements of a sequence for which a predicate is true.
void __merge_adaptive(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last, _Distance __len1, _Distance __len2, _Pointer __buffer, _Distance __buffer_size)
This is a helper function for the merge routines.
void sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
Sort a heap using comparison functor.
_ForwardIterator upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp &__val, _Compare __comp)
Finds the last position in which val could be inserted without changing the ordering.
Marking output iterators.
bool includes(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, _Compare __comp)
Determines whether all elements of a sequence exists in a range using comparison. ...
void random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last, _RandomNumberGenerator &__rand)
Shuffle the elements of a sequence using a random number generator.
void __final_insertion_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
This is a helper function for the sort routine.
bool next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
Permute range into the next "dictionary" ordering using comparison functor.
_OutputIterator transform(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _OutputIterator __result, _BinaryOperation __binary_op)
Perform an operation on corresponding elements of two sequences.
_ForwardIterator remove_if(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
Remove elements from a sequence using a predicate.
void __inplace_stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
This is a helper function for the stable sorting routines.
_BidirectionalIterator3 __merge_backward(_BidirectionalIterator1 __first1, _BidirectionalIterator1 __last1, _BidirectionalIterator2 __first2, _BidirectionalIterator2 __last2, _BidirectionalIterator3 __result, _Compare __comp)
This is a helper function for the merge routines.
iterator_traits< _Iter >::iterator_category __iterator_category(const _Iter &)
_ForwardIterator max_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
Return the maximum element in a range using comparison functor.
void __unguarded_insertion_sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
This is a helper function for the sort routine.
bool prev_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
Permute range into the previous "dictionary" ordering using comparison functor.
_OutputIterator rotate_copy(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last, _OutputIterator __result)
Copy a sequence, rotating its elements.
_OutputIterator copy_n(_InputIterator __first, _Size __n, _OutputIterator __result)
Copies the range [first,first+n) into [result,result+n).
_OutputIterator replace_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result, const _Tp &__old_value, const _Tp &__new_value)
Copy a sequence, replacing each element of one value with another value.
pair< _ForwardIterator, _ForwardIterator > minmax_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
Return a pair of iterators pointing to the minimum and maximum elements in a range.
_ForwardIterator adjacent_find(_ForwardIterator __first, _ForwardIterator __last, _BinaryPredicate __binary_pred)
Find two adjacent values in a sequence using a predicate.
_InputIterator find_first_of(_InputIterator __first1, _InputIterator __last1, _ForwardIterator __first2, _ForwardIterator __last2, _BinaryPredicate __comp)
Find element from a set in a sequence using a predicate.
iterator begin()
As per Table mumble.
const _Tp & min(const _Tp &, const _Tp &)
This does what you think it does.
_OutputIterator generate_n(_OutputIterator __first, _Size __n, _Generator __gen)
Assign the result of a function object to each value in a sequence.
_OutputIterator copy_if(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _Predicate __pred)
Copy the elements of a sequence for which a predicate is true.
void __reverse(_RandomAccessIterator __first, _RandomAccessIterator __last, random_access_iterator_tag)
_Size __lg(_Size __n)
This is a helper function for the sort routines. Precondition: __n > 0.
void __introsort_loop(_RandomAccessIterator __first, _RandomAccessIterator __last, _Size __depth_limit, _Compare __comp)
This is a helper function for the sort routine.
pair< const _Tp &, const _Tp & > minmax(const _Tp &, const _Tp &)
Determines min and max at once as an ordered pair.
iterator_traits< _InputIterator >::difference_type count(_InputIterator __first, _InputIterator __last, const _Tp &__value)
Count the number of copies of a value in a sequence.
_InputIterator find_if_not(_InputIterator __first, _InputIterator __last, _Predicate __pred)
Find the first element in a sequence for which a predicate is false.
void reverse(_BidirectionalIterator __first, _BidirectionalIterator __last)
Reverse a sequence.
Random-access iterators support a superset of bidirectional iterator operations.
bool binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp &__val, _Compare __comp)
Determines whether an element exists in a range.
_OutputIterator set_difference(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
Return the difference of two sorted ranges using comparison functor.
void stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
Sort the elements of a sequence using a predicate for comparison, preserving the relative order of eq...
_ForwardIterator1 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __predicate)
Search a sequence for a matching sub-sequence using a predicate.
_InputIterator __find_if(_InputIterator __first, _InputIterator __last, _Predicate __pred, input_iterator_tag)
This is an overload used by find_if() for the Input Iterator case.
bool all_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
Checks that a predicate is true for all the elements of a sequence.
void __inplace_stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
This is a helper function for the stable sorting routines.
_InputIterator __find(_InputIterator __first, _InputIterator __last, const _Tp &__val, input_iterator_tag)
This is an overload used by find() for the Input Iterator case.
void nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last, _Compare __comp)
Sort a sequence just enough to find a particular position using a predicate for comparison.
_InputIterator find(_InputIterator __first, _InputIterator __last, const _Tp &__val)
Find the first occurrence of a value in a sequence.
_OutputIterator reverse_copy(_BidirectionalIterator __first, _BidirectionalIterator __last, _OutputIterator __result)
Copy a sequence, reversing its elements.
Forward iterators support a superset of input iterator operations.
void __unguarded_linear_insert(_RandomAccessIterator __last, _Tp __val)
This is a helper function for the sort routine.
void __insertion_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
This is a helper function for the sort routine.
_OutputIterator remove_copy_if(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _Predicate __pred)
Copy a sequence, removing elements for which a predicate is true.
_ForwardIterator partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
Move elements for which a predicate is true to the beginning of a sequence.
void partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last, _Compare __comp)
Sort the smallest elements of a sequence using a predicate for comparison.
void replace_if(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, const _Tp &__new_value)
Replace each value in a sequence for which a predicate returns true with another value.
_OutputIterator remove_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result, const _Tp &__value)
Copy a sequence, removing elements of a given value.
_InputIterator find_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
Find the first element in a sequence for which a predicate is true.
_ForwardIterator partition_point(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
Find the partition point of a partitioned range.
void replace(_ForwardIterator __first, _ForwardIterator __last, const _Tp &__old_value, const _Tp &__new_value)
Replace each occurrence of one value in a sequence with another value.
_ForwardIterator __partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, forward_iterator_tag)
This is a helper function...
void __reverse(_BidirectionalIterator __first, _BidirectionalIterator __last, bidirectional_iterator_tag)