| blob | e61f22b66a87a48c67e1949e38e05f4996e3e49c |
1 // Algorithm implementation -*- C++ -*-
3 // Copyright (C) 2001-2013 Free Software Foundation, Inc.
4 //
5 // This file is part of the GNU ISO C++ Library. This library is free
6 // software; you can redistribute it and/or modify it under the
7 // terms of the GNU General Public License as published by the
8 // Free Software Foundation; either version 3, or (at your option)
9 // any later version.
11 // This library is distributed in the hope that it will be useful,
12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 // GNU General Public License for more details.
16 // Under Section 7 of GPL version 3, you are granted additional
17 // permissions described in the GCC Runtime Library Exception, version
18 // 3.1, as published by the Free Software Foundation.
20 // You should have received a copy of the GNU General Public License and
21 // a copy of the GCC Runtime Library Exception along with this program;
22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23 // <http://www.gnu.org/licenses/>.
25 /*
26 *
27 * Copyright (c) 1994
28 * Hewlett-Packard Company
29 *
30 * Permission to use, copy, modify, distribute and sell this software
31 * and its documentation for any purpose is hereby granted without fee,
32 * provided that the above copyright notice appear in all copies and
33 * that both that copyright notice and this permission notice appear
34 * in supporting documentation. Hewlett-Packard Company makes no
35 * representations about the suitability of this software for any
36 * purpose. It is provided "as is" without express or implied warranty.
37 *
38 *
39 * Copyright (c) 1996
40 * Silicon Graphics Computer Systems, Inc.
41 *
42 * Permission to use, copy, modify, distribute and sell this software
43 * and its documentation for any purpose is hereby granted without fee,
44 * provided that the above copyright notice appear in all copies and
45 * that both that copyright notice and this permission notice appear
46 * in supporting documentation. Silicon Graphics makes no
47 * representations about the suitability of this software for any
48 * purpose. It is provided "as is" without express or implied warranty.
49 */
51 /** @file bits/stl_algo.h
52 * This is an internal header file, included by other library headers.
53 * Do not attempt to use it directly. @headername{algorithm}
54 */
56 #ifndef _STL_ALGO_H
57 #define _STL_ALGO_H 1
60 #include <bits/algorithmfwd.h>
61 #include <bits/stl_heap.h>
64 #if __cplusplus >= 201103L
67 #endif
69 // See concept_check.h for the __glibcxx_*_requires macros.
72 {
73 _GLIBCXX_BEGIN_NAMESPACE_VERSION
75 /// Swaps the median value of *__a, *__b and *__c to *__a
77 void
79 {
80 // concept requirements
85 {
90 }
95 else
97 }
99 /// Swaps the median value of *__a, *__b and *__c under __comp to *__a
101 void
103 _Compare __comp)
104 {
105 // concept requirements
111 {
116 }
121 else
123 }
125 // for_each
127 /// This is an overload used by find() for the Input Iterator case.
129 inline _InputIterator
132 {
136 }
138 /// This is an overload used by find_if() for the Input Iterator case.
140 inline _InputIterator
143 {
147 }
149 /// This is an overload used by find() for the RAI case.
151 _RandomAccessIterator
154 {
159 {
175 }
178 {
194 }
195 }
197 /// This is an overload used by find_if() for the RAI case.
199 _RandomAccessIterator
202 {
207 {
223 }
226 {
242 }
243 }
245 /// This is an overload used by find_if_not() for the Input Iterator case.
247 inline _InputIterator
250 {
254 }
256 /// This is an overload used by find_if_not() for the RAI case.
258 _RandomAccessIterator
261 {
266 {
282 }
285 {
301 }
302 }
304 /// Provided for stable_partition to use.
306 inline _InputIterator
308 _Predicate __pred)
309 {
312 }
314 /// Like find_if_not(), but uses and updates a count of the
315 /// remaining range length instead of comparing against an end
316 /// iterator.
318 _InputIterator
320 {
325 }
327 // set_difference
328 // set_intersection
329 // set_symmetric_difference
330 // set_union
331 // for_each
332 // find
333 // find_if
334 // find_first_of
335 // adjacent_find
336 // count
337 // count_if
338 // search
340 /**
341 * This is an uglified
342 * search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&)
343 * overloaded for forward iterators.
344 */
346 _ForwardIterator
350 {
353 {
359 {
362 }
368 }
370 }
372 /**
373 * This is an uglified
374 * search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&)
375 * overloaded for random access iterators.
376 */
378 _RandomAccessIter
382 {
385 _DistanceType;
398 {
399 // __lookAhead here is always pointing to the last element of next
400 // possible match.
402 {
407 }
411 {
414 }
419 }
420 }
422 // search_n
424 /**
425 * This is an uglified
426 * search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&,
427 * _BinaryPredicate)
428 * overloaded for forward iterators.
429 */
431 typename _BinaryPredicate>
432 _ForwardIterator
436 {
441 {
447 {
450 }
459 }
461 }
463 /**
464 * This is an uglified
465 * search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&,
466 * _BinaryPredicate)
467 * overloaded for random access iterators.
468 */
470 typename _BinaryPredicate>
471 _RandomAccessIter
475 {
478 _DistanceType;
491 {
492 // __lookAhead here is always pointing to the last element of next
493 // possible match.
495 {
500 }
504 {
507 }
512 }
513 }
515 // find_end for forward iterators.
517 _ForwardIterator1
521 {
524 else
525 {
528 {
529 _ForwardIterator1 __new_result
533 else
534 {
538 }
539 }
540 }
541 }
544 typename _BinaryPredicate>
545 _ForwardIterator1
549 _BinaryPredicate __comp)
550 {
553 else
554 {
557 {
558 _ForwardIterator1 __new_result
563 else
564 {
568 }
569 }
570 }
571 }
573 // find_end for bidirectional iterators (much faster).
575 _BidirectionalIterator1
577 _BidirectionalIterator1 __last1,
578 _BidirectionalIterator2 __first2,
579 _BidirectionalIterator2 __last2,
581 {
582 // concept requirements
584 _BidirectionalIterator1>)
586 _BidirectionalIterator2>)
594 __rlast1,
596 __rlast2);
600 else
601 {
605 }
606 }
609 typename _BinaryPredicate>
610 _BidirectionalIterator1
612 _BidirectionalIterator1 __last1,
613 _BidirectionalIterator2 __first2,
614 _BidirectionalIterator2 __last2,
616 _BinaryPredicate __comp)
617 {
618 // concept requirements
620 _BidirectionalIterator1>)
622 _BidirectionalIterator2>)
631 __comp);
635 else
636 {
640 }
641 }
643 /**
644 * @brief Find last matching subsequence in a sequence.
645 * @ingroup non_mutating_algorithms
646 * @param __first1 Start of range to search.
647 * @param __last1 End of range to search.
648 * @param __first2 Start of sequence to match.
649 * @param __last2 End of sequence to match.
650 * @return The last iterator @c i in the range
651 * @p [__first1,__last1-(__last2-__first2)) such that @c *(i+N) ==
652 * @p *(__first2+N) for each @c N in the range @p
653 * [0,__last2-__first2), or @p __last1 if no such iterator exists.
654 *
655 * Searches the range @p [__first1,__last1) for a sub-sequence that
656 * compares equal value-by-value with the sequence given by @p
657 * [__first2,__last2) and returns an iterator to the __first
658 * element of the sub-sequence, or @p __last1 if the sub-sequence
659 * is not found. The sub-sequence will be the last such
660 * subsequence contained in [__first,__last1).
661 *
662 * Because the sub-sequence must lie completely within the range @p
663 * [__first1,__last1) it must start at a position less than @p
664 * __last1-(__last2-__first2) where @p __last2-__first2 is the
665 * length of the sub-sequence. This means that the returned
666 * iterator @c i will be in the range @p
667 * [__first1,__last1-(__last2-__first2))
668 */
670 inline _ForwardIterator1
673 {
674 // concept requirements
686 }
688 /**
689 * @brief Find last matching subsequence in a sequence using a predicate.
690 * @ingroup non_mutating_algorithms
691 * @param __first1 Start of range to search.
692 * @param __last1 End of range to search.
693 * @param __first2 Start of sequence to match.
694 * @param __last2 End of sequence to match.
695 * @param __comp The predicate to use.
696 * @return The last iterator @c i in the range @p
697 * [__first1,__last1-(__last2-__first2)) such that @c
698 * predicate(*(i+N), @p (__first2+N)) is true for each @c N in the
699 * range @p [0,__last2-__first2), or @p __last1 if no such iterator
700 * exists.
701 *
702 * Searches the range @p [__first1,__last1) for a sub-sequence that
703 * compares equal value-by-value with the sequence given by @p
704 * [__first2,__last2) using comp as a predicate and returns an
705 * iterator to the first element of the sub-sequence, or @p __last1
706 * if the sub-sequence is not found. The sub-sequence will be the
707 * last such subsequence contained in [__first,__last1).
708 *
709 * Because the sub-sequence must lie completely within the range @p
710 * [__first1,__last1) it must start at a position less than @p
711 * __last1-(__last2-__first2) where @p __last2-__first2 is the
712 * length of the sub-sequence. This means that the returned
713 * iterator @c i will be in the range @p
714 * [__first1,__last1-(__last2-__first2))
715 */
717 typename _BinaryPredicate>
718 inline _ForwardIterator1
721 _BinaryPredicate __comp)
722 {
723 // concept requirements
735 __comp);
736 }
738 #if __cplusplus >= 201103L
739 /**
740 * @brief Checks that a predicate is true for all the elements
741 * of a sequence.
742 * @ingroup non_mutating_algorithms
743 * @param __first An input iterator.
744 * @param __last An input iterator.
745 * @param __pred A predicate.
746 * @return True if the check is true, false otherwise.
747 *
748 * Returns true if @p __pred is true for each element in the range
749 * @p [__first,__last), and false otherwise.
750 */
756 /**
757 * @brief Checks that a predicate is false for all the elements
758 * of a sequence.
759 * @ingroup non_mutating_algorithms
760 * @param __first An input iterator.
761 * @param __last An input iterator.
762 * @param __pred A predicate.
763 * @return True if the check is true, false otherwise.
764 *
765 * Returns true if @p __pred is false for each element in the range
766 * @p [__first,__last), and false otherwise.
767 */
773 /**
774 * @brief Checks that a predicate is false for at least an element
775 * of a sequence.
776 * @ingroup non_mutating_algorithms
777 * @param __first An input iterator.
778 * @param __last An input iterator.
779 * @param __pred A predicate.
780 * @return True if the check is true, false otherwise.
781 *
782 * Returns true if an element exists in the range @p
783 * [__first,__last) such that @p __pred is true, and false
784 * otherwise.
785 */
791 /**
792 * @brief Find the first element in a sequence for which a
793 * predicate is false.
794 * @ingroup non_mutating_algorithms
795 * @param __first An input iterator.
796 * @param __last An input iterator.
797 * @param __pred A predicate.
798 * @return The first iterator @c i in the range @p [__first,__last)
799 * such that @p __pred(*i) is false, or @p __last if no such iterator exists.
800 */
802 inline _InputIterator
804 _Predicate __pred)
805 {
806 // concept requirements
812 }
814 /**
815 * @brief Checks whether the sequence is partitioned.
816 * @ingroup mutating_algorithms
817 * @param __first An input iterator.
818 * @param __last An input iterator.
819 * @param __pred A predicate.
820 * @return True if the range @p [__first,__last) is partioned by @p __pred,
821 * i.e. if all elements that satisfy @p __pred appear before those that
822 * do not.
823 */
827 _Predicate __pred)
828 {
831 }
833 /**
834 * @brief Find the partition point of a partitioned range.
835 * @ingroup mutating_algorithms
836 * @param __first An iterator.
837 * @param __last Another iterator.
838 * @param __pred A predicate.
839 * @return An iterator @p mid such that @p all_of(__first, mid, __pred)
840 * and @p none_of(mid, __last, __pred) are both true.
841 */
843 _ForwardIterator
845 _Predicate __pred)
846 {
847 // concept requirements
852 // A specific debug-mode test will be necessary...
856 _DistanceType;
859 _DistanceType __half;
860 _ForwardIterator __middle;
863 {
868 {
872 }
873 else
875 }
877 }
878 #endif
881 /**
882 * @brief Copy a sequence, removing elements of a given value.
883 * @ingroup mutating_algorithms
884 * @param __first An input iterator.
885 * @param __last An input iterator.
886 * @param __result An output iterator.
887 * @param __value The value to be removed.
888 * @return An iterator designating the end of the resulting sequence.
889 *
890 * Copies each element in the range @p [__first,__last) not equal
891 * to @p __value to the range beginning at @p __result.
892 * remove_copy() is stable, so the relative order of elements that
893 * are copied is unchanged.
894 */
896 _OutputIterator
899 {
900 // concept requirements
910 {
913 }
915 }
917 /**
918 * @brief Copy a sequence, removing elements for which a predicate is true.
919 * @ingroup mutating_algorithms
920 * @param __first An input iterator.
921 * @param __last An input iterator.
922 * @param __result An output iterator.
923 * @param __pred A predicate.
924 * @return An iterator designating the end of the resulting sequence.
925 *
926 * Copies each element in the range @p [__first,__last) for which
927 * @p __pred returns false to the range beginning at @p __result.
928 *
929 * remove_copy_if() is stable, so the relative order of elements that are
930 * copied is unchanged.
931 */
933 typename _Predicate>
934 _OutputIterator
937 {
938 // concept requirements
948 {
951 }
953 }
955 #if __cplusplus >= 201103L
956 /**
957 * @brief Copy the elements of a sequence for which a predicate is true.
958 * @ingroup mutating_algorithms
959 * @param __first An input iterator.
960 * @param __last An input iterator.
961 * @param __result An output iterator.
962 * @param __pred A predicate.
963 * @return An iterator designating the end of the resulting sequence.
964 *
965 * Copies each element in the range @p [__first,__last) for which
966 * @p __pred returns true to the range beginning at @p __result.
967 *
968 * copy_if() is stable, so the relative order of elements that are
969 * copied is unchanged.
970 */
972 typename _Predicate>
973 _OutputIterator
976 {
977 // concept requirements
987 {
990 }
992 }
996 _OutputIterator
999 {
1001 {
1003 {
1008 else
1010 }
1011 }
1013 }
1016 typename _OutputIterator>
1017 inline _OutputIterator
1022 /**
1023 * @brief Copies the range [first,first+n) into [result,result+n).
1024 * @ingroup mutating_algorithms
1025 * @param __first An input iterator.
1026 * @param __n The number of elements to copy.
1027 * @param __result An output iterator.
1028 * @return result+n.
1029 *
1030 * This inline function will boil down to a call to @c memmove whenever
1031 * possible. Failing that, if random access iterators are passed, then the
1032 * loop count will be known (and therefore a candidate for compiler
1033 * optimizations such as unrolling).
1034 */
1036 inline _OutputIterator
1038 {
1039 // concept requirements
1046 }
1048 /**
1049 * @brief Copy the elements of a sequence to separate output sequences
1050 * depending on the truth value of a predicate.
1051 * @ingroup mutating_algorithms
1052 * @param __first An input iterator.
1053 * @param __last An input iterator.
1054 * @param __out_true An output iterator.
1055 * @param __out_false An output iterator.
1056 * @param __pred A predicate.
1057 * @return A pair designating the ends of the resulting sequences.
1058 *
1059 * Copies each element in the range @p [__first,__last) for which
1060 * @p __pred returns true to the range beginning at @p out_true
1061 * and each element for which @p __pred returns false to @p __out_false.
1062 */
1068 _Predicate __pred)
1069 {
1070 // concept requirements
1082 {
1085 }
1086 else
1087 {
1090 }
1093 }
1094 #endif
1096 /**
1097 * @brief Remove elements from a sequence.
1098 * @ingroup mutating_algorithms
1099 * @param __first An input iterator.
1100 * @param __last An input iterator.
1101 * @param __value The value to be removed.
1102 * @return An iterator designating the end of the resulting sequence.
1103 *
1104 * All elements equal to @p __value are removed from the range
1105 * @p [__first,__last).
1106 *
1107 * remove() is stable, so the relative order of elements that are
1108 * not removed is unchanged.
1109 *
1110 * Elements between the end of the resulting sequence and @p __last
1111 * are still present, but their value is unspecified.
1112 */
1114 _ForwardIterator
1117 {
1118 // concept requirements
1120 _ForwardIterator>)
1132 {
1135 }
1137 }
1139 /**
1140 * @brief Remove elements from a sequence using a predicate.
1141 * @ingroup mutating_algorithms
1142 * @param __first A forward iterator.
1143 * @param __last A forward iterator.
1144 * @param __pred A predicate.
1145 * @return An iterator designating the end of the resulting sequence.
1146 *
1147 * All elements for which @p __pred returns true are removed from the range
1148 * @p [__first,__last).
1149 *
1150 * remove_if() is stable, so the relative order of elements that are
1151 * not removed is unchanged.
1152 *
1153 * Elements between the end of the resulting sequence and @p __last
1154 * are still present, but their value is unspecified.
1155 */
1157 _ForwardIterator
1159 _Predicate __pred)
1160 {
1161 // concept requirements
1163 _ForwardIterator>)
1175 {
1178 }
1180 }
1182 /**
1183 * @brief Remove consecutive duplicate values from a sequence.
1184 * @ingroup mutating_algorithms
1185 * @param __first A forward iterator.
1186 * @param __last A forward iterator.
1187 * @return An iterator designating the end of the resulting sequence.
1188 *
1189 * Removes all but the first element from each group of consecutive
1190 * values that compare equal.
1191 * unique() is stable, so the relative order of elements that are
1192 * not removed is unchanged.
1193 * Elements between the end of the resulting sequence and @p __last
1194 * are still present, but their value is unspecified.
1195 */
1197 _ForwardIterator
1199 {
1200 // concept requirements
1202 _ForwardIterator>)
1207 // Skip the beginning, if already unique.
1212 // Do the real copy work.
1219 }
1221 /**
1222 * @brief Remove consecutive values from a sequence using a predicate.
1223 * @ingroup mutating_algorithms
1224 * @param __first A forward iterator.
1225 * @param __last A forward iterator.
1226 * @param __binary_pred A binary predicate.
1227 * @return An iterator designating the end of the resulting sequence.
1228 *
1229 * Removes all but the first element from each group of consecutive
1230 * values for which @p __binary_pred returns true.
1231 * unique() is stable, so the relative order of elements that are
1232 * not removed is unchanged.
1233 * Elements between the end of the resulting sequence and @p __last
1234 * are still present, but their value is unspecified.
1235 */
1237 _ForwardIterator
1239 _BinaryPredicate __binary_pred)
1240 {
1241 // concept requirements
1243 _ForwardIterator>)
1249 // Skip the beginning, if already unique.
1254 // Do the real copy work.
1261 }
1263 /**
1264 * This is an uglified unique_copy(_InputIterator, _InputIterator,
1265 * _OutputIterator)
1266 * overloaded for forward iterators and output iterator as result.
1267 */
1269 _OutputIterator
1271 _OutputIterator __result,
1273 {
1274 // concept requirements -- taken care of in dispatching function
1279 {
1282 }
1284 }
1286 /**
1287 * This is an uglified unique_copy(_InputIterator, _InputIterator,
1288 * _OutputIterator)
1289 * overloaded for input iterators and output iterator as result.
1290 */
1292 _OutputIterator
1294 _OutputIterator __result,
1296 {
1297 // concept requirements -- taken care of in dispatching function
1302 {
1305 }
1307 }
1309 /**
1310 * This is an uglified unique_copy(_InputIterator, _InputIterator,
1311 * _OutputIterator)
1312 * overloaded for input iterators and forward iterator as result.
1313 */
1315 _ForwardIterator
1317 _ForwardIterator __result,
1319 {
1320 // concept requirements -- taken care of in dispatching function
1326 }
1328 /**
1329 * This is an uglified
1330 * unique_copy(_InputIterator, _InputIterator, _OutputIterator,
1331 * _BinaryPredicate)
1332 * overloaded for forward iterators and output iterator as result.
1333 */
1335 typename _BinaryPredicate>
1336 _OutputIterator
1340 {
1341 // concept requirements -- iterators already checked
1350 {
1353 }
1355 }
1357 /**
1358 * This is an uglified
1359 * unique_copy(_InputIterator, _InputIterator, _OutputIterator,
1360 * _BinaryPredicate)
1361 * overloaded for input iterators and output iterator as result.
1362 */
1364 typename _BinaryPredicate>
1365 _OutputIterator
1369 {
1370 // concept requirements -- iterators already checked
1379 {
1382 }
1384 }
1386 /**
1387 * This is an uglified
1388 * unique_copy(_InputIterator, _InputIterator, _OutputIterator,
1389 * _BinaryPredicate)
1390 * overloaded for input iterators and forward iterator as result.
1391 */
1393 typename _BinaryPredicate>
1394 _ForwardIterator
1398 {
1399 // concept requirements -- iterators already checked
1409 }
1411 /**
1412 * This is an uglified reverse(_BidirectionalIterator,
1413 * _BidirectionalIterator)
1414 * overloaded for bidirectional iterators.
1415 */
1417 void
1419 bidirectional_iterator_tag)
1420 {
1424 else
1425 {
1428 }
1429 }
1431 /**
1432 * This is an uglified reverse(_BidirectionalIterator,
1433 * _BidirectionalIterator)
1434 * overloaded for random access iterators.
1435 */
1437 void
1439 random_access_iterator_tag)
1440 {
1445 {
1449 }
1450 }
1452 /**
1453 * @brief Reverse a sequence.
1454 * @ingroup mutating_algorithms
1455 * @param __first A bidirectional iterator.
1456 * @param __last A bidirectional iterator.
1457 * @return reverse() returns no value.
1458 *
1459 * Reverses the order of the elements in the range @p [__first,__last),
1460 * so that the first element becomes the last etc.
1461 * For every @c i such that @p 0<=i<=(__last-__first)/2), @p reverse()
1462 * swaps @p *(__first+i) and @p *(__last-(i+1))
1463 */
1467 {
1468 // concept requirements
1470 _BidirectionalIterator>)
1473 }
1475 /**
1476 * @brief Copy a sequence, reversing its elements.
1477 * @ingroup mutating_algorithms
1478 * @param __first A bidirectional iterator.
1479 * @param __last A bidirectional iterator.
1480 * @param __result An output iterator.
1481 * @return An iterator designating the end of the resulting sequence.
1482 *
1483 * Copies the elements in the range @p [__first,__last) to the
1484 * range @p [__result,__result+(__last-__first)) such that the
1485 * order of the elements is reversed. For every @c i such that @p
1486 * 0<=i<=(__last-__first), @p reverse_copy() performs the
1487 * assignment @p *(__result+(__last-__first)-1-i) = *(__first+i).
1488 * The ranges @p [__first,__last) and @p
1489 * [__result,__result+(__last-__first)) must not overlap.
1490 */
1492 _OutputIterator
1494 _OutputIterator __result)
1495 {
1496 // concept requirements
1498 _BidirectionalIterator>)
1504 {
1508 }
1510 }
1512 /**
1513 * This is a helper function for the rotate algorithm specialized on RAIs.
1514 * It returns the greatest common divisor of two integer values.
1515 */
1517 _EuclideanRingElement
1519 {
1521 {
1525 }
1527 }
1529 /// This is a helper function for the rotate algorithm.
1531 void
1533 _ForwardIterator __middle,
1534 _ForwardIterator __last,
1535 forward_iterator_tag)
1536 {
1541 do
1542 {
1548 }
1554 {
1562 }
1563 }
1565 /// This is a helper function for the rotate algorithm.
1567 void
1569 _BidirectionalIterator __middle,
1570 _BidirectionalIterator __last,
1571 bidirectional_iterator_tag)
1572 {
1573 // concept requirements
1575 _BidirectionalIterator>)
1584 {
1587 }
1591 else
1593 }
1595 /// This is a helper function for the rotate algorithm.
1597 void
1599 _RandomAccessIterator __middle,
1600 _RandomAccessIterator __last,
1601 random_access_iterator_tag)
1602 {
1603 // concept requirements
1605 _RandomAccessIterator>)
1611 _Distance;
1613 _ValueType;
1619 {
1622 }
1627 {
1629 {
1631 {
1636 }
1639 {
1643 }
1649 }
1650 else
1651 {
1654 {
1659 }
1663 {
1667 }
1672 }
1673 }
1674 }
1676 /**
1677 * @brief Rotate the elements of a sequence.
1678 * @ingroup mutating_algorithms
1679 * @param __first A forward iterator.
1680 * @param __middle A forward iterator.
1681 * @param __last A forward iterator.
1682 * @return Nothing.
1683 *
1684 * Rotates the elements of the range @p [__first,__last) by
1685 * @p (__middle - __first) positions so that the element at @p __middle
1686 * is moved to @p __first, the element at @p __middle+1 is moved to
1687 * @p __first+1 and so on for each element in the range
1688 * @p [__first,__last).
1689 *
1690 * This effectively swaps the ranges @p [__first,__middle) and
1691 * @p [__middle,__last).
1692 *
1693 * Performs
1694 * @p *(__first+(n+(__last-__middle))%(__last-__first))=*(__first+n)
1695 * for each @p n in the range @p [0,__last-__first).
1696 */
1700 _ForwardIterator __last)
1701 {
1702 // concept requirements
1704 _ForwardIterator>)
1709 _IterType;
1711 }
1713 /**
1714 * @brief Copy a sequence, rotating its elements.
1715 * @ingroup mutating_algorithms
1716 * @param __first A forward iterator.
1717 * @param __middle A forward iterator.
1718 * @param __last A forward iterator.
1719 * @param __result An output iterator.
1720 * @return An iterator designating the end of the resulting sequence.
1721 *
1722 * Copies the elements of the range @p [__first,__last) to the
1723 * range beginning at @result, rotating the copied elements by
1724 * @p (__middle-__first) positions so that the element at @p __middle
1725 * is moved to @p __result, the element at @p __middle+1 is moved
1726 * to @p __result+1 and so on for each element in the range @p
1727 * [__first,__last).
1728 *
1729 * Performs
1730 * @p *(__result+(n+(__last-__middle))%(__last-__first))=*(__first+n)
1731 * for each @p n in the range @p [0,__last-__first).
1732 */
1734 _OutputIterator
1737 {
1738 // concept requirements
1747 }
1749 /// This is a helper function...
1751 _ForwardIterator
1754 {
1766 {
1769 }
1772 }
1774 /// This is a helper function...
1776 _BidirectionalIterator
1779 {
1781 {
1787 else
1795 else
1799 }
1800 }
1802 // partition
1804 /// This is a helper function...
1805 /// Requires __len != 0 and !__pred(*__first),
1806 /// same as __stable_partition_adaptive.
1808 _ForwardIterator
1811 {
1816 _ForwardIterator __left_split =
1818 // Advance past true-predicate values to satisfy this
1819 // function's preconditions.
1821 _ForwardIterator __right_split =
1825 __pred,
1826 __right_len);
1830 }
1832 /// This is a helper function...
1833 /// Requires __first != __last and !__pred(*__first)
1834 /// and __len == distance(__first, __last).
1835 ///
1836 /// !__pred(*__first) allows us to guarantee that we don't
1837 /// move-assign an element onto itself.
1839 typename _Distance>
1840 _ForwardIterator
1842 _ForwardIterator __last,
1844 _Pointer __buffer,
1845 _Distance __buffer_size)
1846 {
1848 {
1851 // The precondition guarantees that !__pred(*__first), so
1852 // move that element to the buffer before starting the loop.
1853 // This ensures that we only call __pred once per element.
1859 {
1862 }
1863 else
1864 {
1867 }
1870 }
1871 else
1872 {
1875 _ForwardIterator __left_split =
1878 __buffer_size);
1879 // Advance past true-predicate values to satisfy this
1880 // function's preconditions.
1882 _ForwardIterator __right_split =
1885 __right_split =
1887 __right_len,
1892 }
1893 }
1895 /**
1896 * @brief Move elements for which a predicate is true to the beginning
1897 * of a sequence, preserving relative ordering.
1898 * @ingroup mutating_algorithms
1899 * @param __first A forward iterator.
1900 * @param __last A forward iterator.
1901 * @param __pred A predicate functor.
1902 * @return An iterator @p middle such that @p __pred(i) is true for each
1903 * iterator @p i in the range @p [first,middle) and false for each @p i
1904 * in the range @p [middle,last).
1905 *
1906 * Performs the same function as @p partition() with the additional
1907 * guarantee that the relative ordering of elements in each group is
1908 * preserved, so any two elements @p x and @p y in the range
1909 * @p [__first,__last) such that @p __pred(x)==__pred(y) will have the same
1910 * relative ordering after calling @p stable_partition().
1911 */
1913 _ForwardIterator
1915 _Predicate __pred)
1916 {
1917 // concept requirements
1919 _ForwardIterator>)
1928 else
1929 {
1931 _ValueType;
1933 _DistanceType;
1936 __last);
1938 return
1943 else
1944 return
1947 }
1948 }
1950 /// This is a helper function for the sort routines.
1952 void
1954 _RandomAccessIterator __middle,
1955 _RandomAccessIterator __last)
1956 {
1961 }
1963 /// This is a helper function for the sort routines.
1965 void
1967 _RandomAccessIterator __middle,
1969 {
1974 }
1976 // partial_sort
1978 /**
1979 * @brief Copy the smallest elements of a sequence.
1980 * @ingroup sorting_algorithms
1981 * @param __first An iterator.
1982 * @param __last Another iterator.
1983 * @param __result_first A random-access iterator.
1984 * @param __result_last Another random-access iterator.
1985 * @return An iterator indicating the end of the resulting sequence.
1986 *
1987 * Copies and sorts the smallest N values from the range @p [__first,__last)
1988 * to the range beginning at @p __result_first, where the number of
1989 * elements to be copied, @p N, is the smaller of @p (__last-__first) and
1990 * @p (__result_last-__result_first).
1991 * After the sort if @e i and @e j are iterators in the range
1992 * @p [__result_first,__result_first+N) such that i precedes j then
1993 * *j<*i is false.
1994 * The value returned is @p __result_first+N.
1995 */
1997 _RandomAccessIterator
1999 _RandomAccessIterator __result_first,
2000 _RandomAccessIterator __result_last)
2001 {
2003 _InputValueType;
2005 _OutputValueType;
2007 _DistanceType;
2009 // concept requirements
2012 _OutputValueType>)
2014 _OutputValueType>)
2023 {
2027 }
2030 {
2037 }
2040 }
2042 /**
2043 * @brief Copy the smallest elements of a sequence using a predicate for
2044 * comparison.
2045 * @ingroup sorting_algorithms
2046 * @param __first An input iterator.
2047 * @param __last Another input iterator.
2048 * @param __result_first A random-access iterator.
2049 * @param __result_last Another random-access iterator.
2050 * @param __comp A comparison functor.
2051 * @return An iterator indicating the end of the resulting sequence.
2052 *
2053 * Copies and sorts the smallest N values from the range @p [__first,__last)
2054 * to the range beginning at @p result_first, where the number of
2055 * elements to be copied, @p N, is the smaller of @p (__last-__first) and
2056 * @p (__result_last-__result_first).
2057 * After the sort if @e i and @e j are iterators in the range
2058 * @p [__result_first,__result_first+N) such that i precedes j then
2059 * @p __comp(*j,*i) is false.
2060 * The value returned is @p __result_first+N.
2061 */
2063 _RandomAccessIterator
2065 _RandomAccessIterator __result_first,
2066 _RandomAccessIterator __result_last,
2067 _Compare __comp)
2068 {
2070 _InputValueType;
2072 _OutputValueType;
2074 _DistanceType;
2076 // concept requirements
2079 _RandomAccessIterator>)
2081 _OutputValueType>)
2093 {
2097 }
2100 {
2106 __comp);
2108 }
2111 }
2113 /// This is a helper function for the sort routine.
2115 void
2117 {
2123 {
2127 }
2129 }
2131 /// This is a helper function for the sort routine.
2133 void
2135 _Compare __comp)
2136 {
2142 {
2146 }
2148 }
2150 /// This is a helper function for the sort routine.
2152 void
2154 _RandomAccessIterator __last)
2155 {
2160 {
2162 {
2167 }
2168 else
2170 }
2171 }
2173 /// This is a helper function for the sort routine.
2175 void
2178 {
2182 {
2184 {
2189 }
2190 else
2192 }
2193 }
2195 /// This is a helper function for the sort routine.
2199 _RandomAccessIterator __last)
2200 {
2202 _ValueType;
2206 }
2208 /// This is a helper function for the sort routine.
2213 {
2215 _ValueType;
2219 }
2221 /**
2222 * @doctodo
2223 * This controls some aspect of the sort routines.
2224 */
2227 /// This is a helper function for the sort routine.
2229 void
2231 _RandomAccessIterator __last)
2232 {
2234 {
2237 }
2238 else
2240 }
2242 /// This is a helper function for the sort routine.
2244 void
2247 {
2249 {
2252 __comp);
2253 }
2254 else
2256 }
2258 /// This is a helper function...
2260 _RandomAccessIterator
2263 {
2265 {
2275 }
2276 }
2278 /// This is a helper function...
2280 _RandomAccessIterator
2282 _RandomAccessIterator __last,
2284 {
2286 {
2296 }
2297 }
2299 /// This is a helper function...
2301 inline _RandomAccessIterator
2303 _RandomAccessIterator __last)
2304 {
2308 }
2311 /// This is a helper function...
2313 inline _RandomAccessIterator
2316 {
2320 }
2322 /// This is a helper function for the sort routine.
2324 void
2326 _RandomAccessIterator __last,
2327 _Size __depth_limit)
2328 {
2330 {
2332 {
2335 }
2337 _RandomAccessIterator __cut =
2341 }
2342 }
2344 /// This is a helper function for the sort routine.
2346 void
2348 _RandomAccessIterator __last,
2350 {
2352 {
2354 {
2357 }
2359 _RandomAccessIterator __cut =
2363 }
2364 }
2366 // sort
2369 void
2372 {
2374 _ValueType;
2377 {
2379 {
2382 // Place the nth largest element in its final position.
2385 }
2387 _RandomAccessIterator __cut =
2391 else
2393 }
2395 }
2398 void
2401 _Compare __comp)
2402 {
2404 _ValueType;
2407 {
2409 {
2411 // Place the nth largest element in its final position.
2414 }
2416 _RandomAccessIterator __cut =
2420 else
2422 }
2424 }
2426 // nth_element
2428 // lower_bound moved to stl_algobase.h
2430 /**
2431 * @brief Finds the first position in which @p __val could be inserted
2432 * without changing the ordering.
2433 * @ingroup binary_search_algorithms
2434 * @param __first An iterator.
2435 * @param __last Another iterator.
2436 * @param __val The search term.
2437 * @param __comp A functor to use for comparisons.
2438 * @return An iterator pointing to the first element <em>not less
2439 * than</em> @p __val, or end() if every element is less
2440 * than @p __val.
2441 * @ingroup binary_search_algorithms
2442 *
2443 * The comparison function should have the same effects on ordering as
2444 * the function used for the initial sort.
2445 */
2447 _ForwardIterator
2450 {
2452 _ValueType;
2454 _DistanceType;
2456 // concept requirements
2466 {
2471 {
2475 }
2476 else
2478 }
2480 }
2482 /**
2483 * @brief Finds the last position in which @p __val could be inserted
2484 * without changing the ordering.
2485 * @ingroup binary_search_algorithms
2486 * @param __first An iterator.
2487 * @param __last Another iterator.
2488 * @param __val The search term.
2489 * @return An iterator pointing to the first element greater than @p __val,
2490 * or end() if no elements are greater than @p __val.
2491 * @ingroup binary_search_algorithms
2492 */
2494 _ForwardIterator
2497 {
2499 _ValueType;
2501 _DistanceType;
2503 // concept requirements
2511 {
2517 else
2518 {
2522 }
2523 }
2525 }
2527 /**
2528 * @brief Finds the last position in which @p __val could be inserted
2529 * without changing the ordering.
2530 * @ingroup binary_search_algorithms
2531 * @param __first An iterator.
2532 * @param __last Another iterator.
2533 * @param __val The search term.
2534 * @param __comp A functor to use for comparisons.
2535 * @return An iterator pointing to the first element greater than @p __val,
2536 * or end() if no elements are greater than @p __val.
2537 * @ingroup binary_search_algorithms
2538 *
2539 * The comparison function should have the same effects on ordering as
2540 * the function used for the initial sort.
2541 */
2543 _ForwardIterator
2546 {
2548 _ValueType;
2550 _DistanceType;
2552 // concept requirements
2562 {
2568 else
2569 {
2573 }
2574 }
2576 }
2578 /**
2579 * @brief Finds the largest subrange in which @p __val could be inserted
2580 * at any place in it without changing the ordering.
2581 * @ingroup binary_search_algorithms
2582 * @param __first An iterator.
2583 * @param __last Another iterator.
2584 * @param __val The search term.
2585 * @return An pair of iterators defining the subrange.
2586 * @ingroup binary_search_algorithms
2587 *
2588 * This is equivalent to
2589 * @code
2590 * std::make_pair(lower_bound(__first, __last, __val),
2591 * upper_bound(__first, __last, __val))
2592 * @endcode
2593 * but does not actually call those functions.
2594 */
2599 {
2601 _ValueType;
2603 _DistanceType;
2605 // concept requirements
2615 {
2620 {
2624 }
2627 else
2628 {
2630 __val);
2633 __val);
2635 }
2636 }
2638 }
2640 /**
2641 * @brief Finds the largest subrange in which @p __val could be inserted
2642 * at any place in it without changing the ordering.
2643 * @param __first An iterator.
2644 * @param __last Another iterator.
2645 * @param __val The search term.
2646 * @param __comp A functor to use for comparisons.
2647 * @return An pair of iterators defining the subrange.
2648 * @ingroup binary_search_algorithms
2649 *
2650 * This is equivalent to
2651 * @code
2652 * std::make_pair(lower_bound(__first, __last, __val, __comp),
2653 * upper_bound(__first, __last, __val, __comp))
2654 * @endcode
2655 * but does not actually call those functions.
2656 */
2661 {
2663 _ValueType;
2665 _DistanceType;
2667 // concept requirements
2681 {
2686 {
2690 }
2693 else
2694 {
2701 }
2702 }
2704 }
2706 /**
2707 * @brief Determines whether an element exists in a range.
2708 * @ingroup binary_search_algorithms
2709 * @param __first An iterator.
2710 * @param __last Another iterator.
2711 * @param __val The search term.
2712 * @return True if @p __val (or its equivalent) is in [@p
2713 * __first,@p __last ].
2714 *
2715 * Note that this does not actually return an iterator to @p __val. For
2716 * that, use std::find or a container's specialized find member functions.
2717 */
2719 bool
2722 {
2724 _ValueType;
2726 // concept requirements
2734 }
2736 /**
2737 * @brief Determines whether an element exists in a range.
2738 * @ingroup binary_search_algorithms
2739 * @param __first An iterator.
2740 * @param __last Another iterator.
2741 * @param __val The search term.
2742 * @param __comp A functor to use for comparisons.
2743 * @return True if @p __val (or its equivalent) is in @p [__first,__last].
2744 *
2745 * Note that this does not actually return an iterator to @p __val. For
2746 * that, use std::find or a container's specialized find member functions.
2747 *
2748 * The comparison function should have the same effects on ordering as
2749 * the function used for the initial sort.
2750 */
2752 bool
2755 {
2757 _ValueType;
2759 // concept requirements
2770 }
2772 // merge
2774 /// This is a helper function for the __merge_adaptive routines.
2776 typename _OutputIterator>
2777 void
2780 _OutputIterator __result)
2781 {
2783 {
2785 {
2788 }
2789 else
2790 {
2793 }
2795 }
2798 }
2800 /// This is a helper function for the __merge_adaptive routines.
2803 void
2807 {
2809 {
2811 {
2814 }
2815 else
2816 {
2819 }
2821 }
2824 }
2826 /// This is a helper function for the __merge_adaptive routines.
2828 typename _BidirectionalIterator3>
2829 void
2831 _BidirectionalIterator1 __last1,
2832 _BidirectionalIterator2 __first2,
2833 _BidirectionalIterator2 __last2,
2834 _BidirectionalIterator3 __result)
2835 {
2837 {
2840 }
2847 {
2849 {
2852 {
2855 }
2857 }
2858 else
2859 {
2864 }
2865 }
2866 }
2868 /// This is a helper function for the __merge_adaptive routines.
2871 void
2873 _BidirectionalIterator1 __last1,
2874 _BidirectionalIterator2 __first2,
2875 _BidirectionalIterator2 __last2,
2876 _BidirectionalIterator3 __result,
2877 _Compare __comp)
2878 {
2880 {
2883 }
2890 {
2892 {
2895 {
2898 }
2900 }
2901 else
2902 {
2907 }
2908 }
2909 }
2911 /// This is a helper function for the merge routines.
2913 typename _Distance>
2914 _BidirectionalIterator1
2916 _BidirectionalIterator1 __middle,
2917 _BidirectionalIterator1 __last,
2919 _BidirectionalIterator2 __buffer,
2920 _Distance __buffer_size)
2921 {
2922 _BidirectionalIterator2 __buffer_end;
2924 {
2926 {
2930 }
2931 else
2933 }
2935 {
2937 {
2941 }
2942 else
2944 }
2945 else
2946 {
2950 }
2951 }
2953 /// This is a helper function for the merge routines.
2955 typename _Pointer>
2956 void
2958 _BidirectionalIterator __middle,
2959 _BidirectionalIterator __last,
2962 {
2964 {
2967 __first);
2968 }
2970 {
2974 }
2975 else
2976 {
2982 {
2988 }
2989 else
2990 {
2996 }
2997 _BidirectionalIterator __new_middle =
3000 __buffer_size);
3006 }
3007 }
3009 /// This is a helper function for the merge routines.
3012 void
3014 _BidirectionalIterator __middle,
3015 _BidirectionalIterator __last,
3018 _Compare __comp)
3019 {
3021 {
3025 }
3027 {
3031 }
3032 else
3033 {
3039 {
3043 __comp);
3045 }
3046 else
3047 {
3051 __comp);
3053 }
3054 _BidirectionalIterator __new_middle =
3057 __buffer_size);
3064 }
3065 }
3067 /// This is a helper function for the merge routines.
3069 void
3071 _BidirectionalIterator __middle,
3072 _BidirectionalIterator __last,
3074 {
3078 {
3082 }
3088 {
3093 }
3094 else
3095 {
3100 }
3108 }
3110 /// This is a helper function for the merge routines.
3112 typename _Compare>
3113 void
3115 _BidirectionalIterator __middle,
3116 _BidirectionalIterator __last,
3118 _Compare __comp)
3119 {
3123 {
3127 }
3133 {
3137 __comp);
3139 }
3140 else
3141 {
3145 __comp);
3147 }
3155 }
3157 /**
3158 * @brief Merges two sorted ranges in place.
3159 * @ingroup sorting_algorithms
3160 * @param __first An iterator.
3161 * @param __middle Another iterator.
3162 * @param __last Another iterator.
3163 * @return Nothing.
3164 *
3165 * Merges two sorted and consecutive ranges, [__first,__middle) and
3166 * [__middle,__last), and puts the result in [__first,__last). The
3167 * output will be sorted. The sort is @e stable, that is, for
3168 * equivalent elements in the two ranges, elements from the first
3169 * range will always come before elements from the second.
3170 *
3171 * If enough additional memory is available, this takes (__last-__first)-1
3172 * comparisons. Otherwise an NlogN algorithm is used, where N is
3173 * distance(__first,__last).
3174 */
3176 void
3178 _BidirectionalIterator __middle,
3179 _BidirectionalIterator __last)
3180 {
3182 _ValueType;
3184 _DistanceType;
3186 // concept requirements
3188 _BidirectionalIterator>)
3200 __last);
3203 else
3206 }
3208 /**
3209 * @brief Merges two sorted ranges in place.
3210 * @ingroup sorting_algorithms
3211 * @param __first An iterator.
3212 * @param __middle Another iterator.
3213 * @param __last Another iterator.
3214 * @param __comp A functor to use for comparisons.
3215 * @return Nothing.
3216 *
3217 * Merges two sorted and consecutive ranges, [__first,__middle) and
3218 * [middle,last), and puts the result in [__first,__last). The output will
3219 * be sorted. The sort is @e stable, that is, for equivalent
3220 * elements in the two ranges, elements from the first range will always
3221 * come before elements from the second.
3222 *
3223 * If enough additional memory is available, this takes (__last-__first)-1
3224 * comparisons. Otherwise an NlogN algorithm is used, where N is
3225 * distance(__first,__last).
3226 *
3227 * The comparison function should have the same effects on ordering as
3228 * the function used for the initial sort.
3229 */
3231 void
3233 _BidirectionalIterator __middle,
3234 _BidirectionalIterator __last,
3235 _Compare __comp)
3236 {
3238 _ValueType;
3240 _DistanceType;
3242 // concept requirements
3244 _BidirectionalIterator>)
3257 __last);
3261 else
3264 __comp);
3265 }
3268 /// This is a helper function for the __merge_sort_loop routines.
3270 typename _OutputIterator>
3271 _OutputIterator
3274 _OutputIterator __result)
3275 {
3277 {
3279 {
3282 }
3283 else
3284 {
3287 }
3289 }
3292 __result));
3293 }
3295 /// This is a helper function for the __merge_sort_loop routines.
3298 _OutputIterator
3302 {
3304 {
3306 {
3309 }
3310 else
3311 {
3314 }
3316 }
3319 __result));
3320 }
3323 typename _Distance>
3324 void
3326 _RandomAccessIterator1 __last,
3327 _RandomAccessIterator2 __result,
3328 _Distance __step_size)
3329 {
3333 {
3338 }
3343 }
3347 void
3349 _RandomAccessIterator1 __last,
3351 _Compare __comp)
3352 {
3356 {
3362 }
3367 }
3370 void
3372 _RandomAccessIterator __last,
3373 _Distance __chunk_size)
3374 {
3376 {
3379 }
3381 }
3384 typename _Compare>
3385 void
3387 _RandomAccessIterator __last,
3389 {
3391 {
3394 }
3396 }
3401 void
3403 _RandomAccessIterator __last,
3404 _Pointer __buffer)
3405 {
3407 _Distance;
3416 {
3421 }
3422 }
3425 void
3427 _RandomAccessIterator __last,
3429 {
3431 _Distance;
3440 {
3447 }
3448 }
3451 typename _Distance>
3452 void
3454 _RandomAccessIterator __last,
3456 {
3460 {
3465 }
3466 else
3467 {
3470 }
3475 }
3479 void
3481 _RandomAccessIterator __last,
3483 _Compare __comp)
3484 {
3488 {
3493 }
3494 else
3495 {
3498 }
3503 __comp);
3504 }
3506 /// This is a helper function for the stable sorting routines.
3508 void
3510 _RandomAccessIterator __last)
3511 {
3513 {
3516 }
3523 }
3525 /// This is a helper function for the stable sorting routines.
3527 void
3530 {
3532 {
3535 }
3542 __comp);
3543 }
3545 // stable_sort
3547 // Set algorithms: includes, set_union, set_intersection, set_difference,
3548 // set_symmetric_difference. All of these algorithms have the precondition
3549 // that their input ranges are sorted and the postcondition that their output
3550 // ranges are sorted.
3552 /**
3553 * @brief Determines whether all elements of a sequence exists in a range.
3554 * @param __first1 Start of search range.
3555 * @param __last1 End of search range.
3556 * @param __first2 Start of sequence
3557 * @param __last2 End of sequence.
3558 * @return True if each element in [__first2,__last2) is contained in order
3559 * within [__first1,__last1). False otherwise.
3560 * @ingroup set_algorithms
3561 *
3562 * This operation expects both [__first1,__last1) and
3563 * [__first2,__last2) to be sorted. Searches for the presence of
3564 * each element in [__first2,__last2) within [__first1,__last1).
3565 * The iterators over each range only move forward, so this is a
3566 * linear algorithm. If an element in [__first2,__last2) is not
3567 * found before the search iterator reaches @p __last2, false is
3568 * returned.
3569 */
3571 bool
3574 {
3576 _ValueType1;
3578 _ValueType2;
3580 // concept requirements
3593 else
3597 }
3599 /**
3600 * @brief Determines whether all elements of a sequence exists in a range
3601 * using comparison.
3602 * @ingroup set_algorithms
3603 * @param __first1 Start of search range.
3604 * @param __last1 End of search range.
3605 * @param __first2 Start of sequence
3606 * @param __last2 End of sequence.
3607 * @param __comp Comparison function to use.
3608 * @return True if each element in [__first2,__last2) is contained
3609 * in order within [__first1,__last1) according to comp. False
3610 * otherwise. @ingroup set_algorithms
3611 *
3612 * This operation expects both [__first1,__last1) and
3613 * [__first2,__last2) to be sorted. Searches for the presence of
3614 * each element in [__first2,__last2) within [__first1,__last1),
3615 * using comp to decide. The iterators over each range only move
3616 * forward, so this is a linear algorithm. If an element in
3617 * [__first2,__last2) is not found before the search iterator
3618 * reaches @p __last2, false is returned.
3619 */
3621 typename _Compare>
3622 bool
3625 _Compare __comp)
3626 {
3628 _ValueType1;
3630 _ValueType2;
3632 // concept requirements
3647 else
3651 }
3653 // nth_element
3654 // merge
3655 // set_difference
3656 // set_intersection
3657 // set_union
3658 // stable_sort
3659 // set_symmetric_difference
3660 // min_element
3661 // max_element
3663 /**
3664 * @brief Permute range into the next @e dictionary ordering.
3665 * @ingroup sorting_algorithms
3666 * @param __first Start of range.
3667 * @param __last End of range.
3668 * @return False if wrapped to first permutation, true otherwise.
3669 *
3670 * Treats all permutations of the range as a set of @e dictionary sorted
3671 * sequences. Permutes the current sequence into the next one of this set.
3672 * Returns true if there are more sequences to generate. If the sequence
3673 * is the largest of the set, the smallest is generated and false returned.
3674 */
3676 bool
3678 _BidirectionalIterator __last)
3679 {
3680 // concept requirements
3682 _BidirectionalIterator>)
3697 {
3701 {
3704 {}
3708 }
3710 {
3713 }
3714 }
3715 }
3717 /**
3718 * @brief Permute range into the next @e dictionary ordering using
3719 * comparison functor.
3720 * @ingroup sorting_algorithms
3721 * @param __first Start of range.
3722 * @param __last End of range.
3723 * @param __comp A comparison functor.
3724 * @return False if wrapped to first permutation, true otherwise.
3725 *
3726 * Treats all permutations of the range [__first,__last) as a set of
3727 * @e dictionary sorted sequences ordered by @p __comp. Permutes the current
3728 * sequence into the next one of this set. Returns true if there are more
3729 * sequences to generate. If the sequence is the largest of the set, the
3730 * smallest is generated and false returned.
3731 */
3733 bool
3736 {
3737 // concept requirements
3739 _BidirectionalIterator>)
3755 {
3759 {
3762 {}
3766 }
3768 {
3771 }
3772 }
3773 }
3775 /**
3776 * @brief Permute range into the previous @e dictionary ordering.
3777 * @ingroup sorting_algorithms
3778 * @param __first Start of range.
3779 * @param __last End of range.
3780 * @return False if wrapped to last permutation, true otherwise.
3781 *
3782 * Treats all permutations of the range as a set of @e dictionary sorted
3783 * sequences. Permutes the current sequence into the previous one of this
3784 * set. Returns true if there are more sequences to generate. If the
3785 * sequence is the smallest of the set, the largest is generated and false
3786 * returned.
3787 */
3789 bool
3791 _BidirectionalIterator __last)
3792 {
3793 // concept requirements
3795 _BidirectionalIterator>)
3810 {
3814 {
3817 {}
3821 }
3823 {
3826 }
3827 }
3828 }
3830 /**
3831 * @brief Permute range into the previous @e dictionary ordering using
3832 * comparison functor.
3833 * @ingroup sorting_algorithms
3834 * @param __first Start of range.
3835 * @param __last End of range.
3836 * @param __comp A comparison functor.
3837 * @return False if wrapped to last permutation, true otherwise.
3838 *
3839 * Treats all permutations of the range [__first,__last) as a set of
3840 * @e dictionary sorted sequences ordered by @p __comp. Permutes the current
3841 * sequence into the previous one of this set. Returns true if there are
3842 * more sequences to generate. If the sequence is the smallest of the set,
3843 * the largest is generated and false returned.
3844 */
3846 bool
3849 {
3850 // concept requirements
3852 _BidirectionalIterator>)
3868 {
3872 {
3875 {}
3879 }
3881 {
3884 }
3885 }
3886 }
3888 // replace
3889 // replace_if
3891 /**
3892 * @brief Copy a sequence, replacing each element of one value with another
3893 * value.
3894 * @param __first An input iterator.
3895 * @param __last An input iterator.
3896 * @param __result An output iterator.
3897 * @param __old_value The value to be replaced.
3898 * @param __new_value The replacement value.
3899 * @return The end of the output sequence, @p result+(last-first).
3900 *
3901 * Copies each element in the input range @p [__first,__last) to the
3902 * output range @p [__result,__result+(__last-__first)) replacing elements
3903 * equal to @p __old_value with @p __new_value.
3904 */
3906 _OutputIterator
3908 _OutputIterator __result,
3910 {
3911 // concept requirements
3922 else
3925 }
3927 /**
3928 * @brief Copy a sequence, replacing each value for which a predicate
3929 * returns true with another value.
3930 * @ingroup mutating_algorithms
3931 * @param __first An input iterator.
3932 * @param __last An input iterator.
3933 * @param __result An output iterator.
3934 * @param __pred A predicate.
3935 * @param __new_value The replacement value.
3936 * @return The end of the output sequence, @p __result+(__last-__first).
3937 *
3938 * Copies each element in the range @p [__first,__last) to the range
3939 * @p [__result,__result+(__last-__first)) replacing elements for which
3940 * @p __pred returns true with @p __new_value.
3941 */
3944 _OutputIterator
3946 _OutputIterator __result,
3948 {
3949 // concept requirements
3960 else
3963 }
3965 #if __cplusplus >= 201103L
3966 /**
3967 * @brief Determines whether the elements of a sequence are sorted.
3968 * @ingroup sorting_algorithms
3969 * @param __first An iterator.
3970 * @param __last Another iterator.
3971 * @return True if the elements are sorted, false otherwise.
3972 */
3978 /**
3979 * @brief Determines whether the elements of a sequence are sorted
3980 * according to a comparison functor.
3981 * @ingroup sorting_algorithms
3982 * @param __first An iterator.
3983 * @param __last Another iterator.
3984 * @param __comp A comparison functor.
3985 * @return True if the elements are sorted, false otherwise.
3986 */
3990 _Compare __comp)
3993 /**
3994 * @brief Determines the end of a sorted sequence.
3995 * @ingroup sorting_algorithms
3996 * @param __first An iterator.
3997 * @param __last Another iterator.
3998 * @return An iterator pointing to the last iterator i in [__first, __last)
3999 * for which the range [__first, i) is sorted.
4000 */
4002 _ForwardIterator
4004 {
4005 // concept requirements
4019 }
4021 /**
4022 * @brief Determines the end of a sorted sequence using comparison functor.
4023 * @ingroup sorting_algorithms
4024 * @param __first An iterator.
4025 * @param __last Another iterator.
4026 * @param __comp A comparison functor.
4027 * @return An iterator pointing to the last iterator i in [__first, __last)
4028 * for which the range [__first, i) is sorted.
4029 */
4031 _ForwardIterator
4033 _Compare __comp)
4034 {
4035 // concept requirements
4050 }
4052 /**
4053 * @brief Determines min and max at once as an ordered pair.
4054 * @ingroup sorting_algorithms
4055 * @param __a A thing of arbitrary type.
4056 * @param __b Another thing of arbitrary type.
4057 * @return A pair(__b, __a) if __b is smaller than __a, pair(__a,
4058 * __b) otherwise.
4059 */
4063 {
4064 // concept requirements
4069 }
4071 /**
4072 * @brief Determines min and max at once as an ordered pair.
4073 * @ingroup sorting_algorithms
4074 * @param __a A thing of arbitrary type.
4075 * @param __b Another thing of arbitrary type.
4076 * @param __comp A @link comparison_functors comparison functor @endlink.
4077 * @return A pair(__b, __a) if __b is smaller than __a, pair(__a,
4078 * __b) otherwise.
4079 */
4083 {
4086 }
4088 /**
4089 * @brief Return a pair of iterators pointing to the minimum and maximum
4090 * elements in a range.
4091 * @ingroup sorting_algorithms
4092 * @param __first Start of range.
4093 * @param __last End of range.
4094 * @return make_pair(m, M), where m is the first iterator i in
4095 * [__first, __last) such that no other element in the range is
4096 * smaller, and where M is the last iterator i in [__first, __last)
4097 * such that no other element in the range is larger.
4098 */
4102 {
4103 // concept requirements
4116 {
4119 }
4120 else
4121 {
4124 }
4130 {
4133 {
4139 }
4142 {
4147 }
4148 else
4149 {
4154 }
4158 }
4161 }
4163 /**
4164 * @brief Return a pair of iterators pointing to the minimum and maximum
4165 * elements in a range.
4166 * @ingroup sorting_algorithms
4167 * @param __first Start of range.
4168 * @param __last End of range.
4169 * @param __comp Comparison functor.
4170 * @return make_pair(m, M), where m is the first iterator i in
4171 * [__first, __last) such that no other element in the range is
4172 * smaller, and where M is the last iterator i in [__first, __last)
4173 * such that no other element in the range is larger.
4174 */
4178 _Compare __comp)
4179 {
4180 // concept requirements
4194 {
4197 }
4198 else
4199 {
4202 }
4208 {
4211 {
4217 }
4220 {
4225 }
4226 else
4227 {
4232 }
4236 }
4239 }
4241 // N2722 + DR 915.
4243 inline _Tp
4248 inline _Tp
4253 inline _Tp
4258 inline _Tp
4265 {
4269 }
4274 {
4278 }
4280 /**
4281 * @brief Checks whether a permutaion of the second sequence is equal
4282 * to the first sequence.
4283 * @ingroup non_mutating_algorithms
4284 * @param __first1 Start of first range.
4285 * @param __last1 End of first range.
4286 * @param __first2 Start of second range.
4287 * @return true if there exists a permutation of the elements in the range
4288 * [__first2, __first2 + (__last1 - __first1)), beginning with
4289 * ForwardIterator2 begin, such that equal(__first1, __last1, begin)
4290 * returns true; otherwise, returns false.
4291 */
4293 bool
4295 _ForwardIterator2 __first2)
4296 {
4297 // Efficiently compare identical prefixes: O(N) if sequences
4298 // have the same elements in the same order.
4306 // Establish __last2 assuming equal ranges by iterating over the
4307 // rest of the list.
4311 {
4319 }
4321 }
4323 /**
4324 * @brief Checks whether a permutation of the second sequence is equal
4325 * to the first sequence.
4326 * @ingroup non_mutating_algorithms
4327 * @param __first1 Start of first range.
4328 * @param __last1 End of first range.
4329 * @param __first2 Start of second range.
4330 * @param __pred A binary predicate.
4331 * @return true if there exists a permutation of the elements in
4332 * the range [__first2, __first2 + (__last1 - __first1)),
4333 * beginning with ForwardIterator2 begin, such that
4334 * equal(__first1, __last1, __begin, __pred) returns true;
4335 * otherwise, returns false.
4336 */
4338 typename _BinaryPredicate>
4339 bool
4342 {
4343 // Efficiently compare identical prefixes: O(N) if sequences
4344 // have the same elements in the same order.
4352 // Establish __last2 assuming equal ranges by iterating over the
4353 // rest of the list.
4357 {
4370 }
4372 }
4374 #if __cplusplus > 201103L
4375 /**
4376 * @brief Checks whether a permutaion of the second sequence is equal
4377 * to the first sequence.
4378 * @ingroup non_mutating_algorithms
4379 * @param __first1 Start of first range.
4380 * @param __last1 End of first range.
4381 * @param __first2 Start of second range.
4382 * @param __last2 End of first range.
4383 * @return true if there exists a permutation of the elements in the range
4384 * [__first2, __last2), beginning with ForwardIterator2 begin,
4385 * such that equal(__first1, __last1, begin) returns true;
4386 * otherwise, returns false.
4387 */
4389 bool
4392 {
4393 using _Cat1
4395 using _Cat2
4400 {
4405 }
4407 // Efficiently compare identical prefixes: O(N) if sequences
4408 // have the same elements in the same order.
4420 {
4428 }
4430 }
4432 /**
4433 * @brief Checks whether a permutation of the second sequence is equal
4434 * to the first sequence.
4435 * @ingroup non_mutating_algorithms
4436 * @param __first1 Start of first range.
4437 * @param __last1 End of first range.
4438 * @param __first2 Start of second range.
4439 * @param __last2 End of first range.
4440 * @param __pred A binary predicate.
4441 * @return true if there exists a permutation of the elements in the range
4442 * [__first2, __last2), beginning with ForwardIterator2 begin,
4443 * such that equal(__first1, __last1, __begin, __pred) returns true;
4444 * otherwise, returns false.
4445 */
4447 typename _BinaryPredicate>
4448 bool
4451 _BinaryPredicate __pred)
4452 {
4453 using _Cat1
4455 using _Cat2
4461 {
4466 }
4468 // Efficiently compare identical prefixes: O(N) if sequences
4469 // have the same elements in the same order.
4475 {
4478 }
4479 else
4480 {
4487 }
4490 {
4503 }
4505 }
4506 #endif
4508 #ifdef _GLIBCXX_USE_C99_STDINT_TR1
4509 /**
4510 * @brief Shuffle the elements of a sequence using a uniform random
4511 * number generator.
4512 * @ingroup mutating_algorithms
4513 * @param __first A forward iterator.
4514 * @param __last A forward iterator.
4515 * @param __g A UniformRandomNumberGenerator (26.5.1.3).
4516 * @return Nothing.
4517 *
4518 * Reorders the elements in the range @p [__first,__last) using @p __g to
4519 * provide random numbers.
4520 */
4522 typename _UniformRandomNumberGenerator>
4523 void
4526 {
4527 // concept requirements
4529 _RandomAccessIterator>)
4536 _DistanceType;
4541 __distr_type __d;
4545 }
4546 #endif
4550 _GLIBCXX_END_NAMESPACE_VERSION
4552 _GLIBCXX_BEGIN_NAMESPACE_ALGO
4554 /**
4555 * @brief Apply a function to every element of a sequence.
4556 * @ingroup non_mutating_algorithms
4557 * @param __first An input iterator.
4558 * @param __last An input iterator.
4559 * @param __f A unary function object.
4560 * @return @p __f (std::move(@p __f) in C++0x).
4561 *
4562 * Applies the function object @p __f to each element in the range
4563 * @p [first,last). @p __f must not modify the order of the sequence.
4564 * If @p __f has a return value it is ignored.
4565 */
4567 _Function
4569 {
4570 // concept requirements
4576 }
4578 /**
4579 * @brief Find the first occurrence of a value in a sequence.
4580 * @ingroup non_mutating_algorithms
4581 * @param __first An input iterator.
4582 * @param __last An input iterator.
4583 * @param __val The value to find.
4584 * @return The first iterator @c i in the range @p [__first,__last)
4585 * such that @c *i == @p __val, or @p __last if no such iterator exists.
4586 */
4588 inline _InputIterator
4591 {
4592 // concept requirements
4599 }
4601 /**
4602 * @brief Find the first element in a sequence for which a
4603 * predicate is true.
4604 * @ingroup non_mutating_algorithms
4605 * @param __first An input iterator.
4606 * @param __last An input iterator.
4607 * @param __pred A predicate.
4608 * @return The first iterator @c i in the range @p [__first,__last)
4609 * such that @p __pred(*i) is true, or @p __last if no such iterator exists.
4610 */
4612 inline _InputIterator
4614 _Predicate __pred)
4615 {
4616 // concept requirements
4623 }
4625 /**
4626 * @brief Find element from a set in a sequence.
4627 * @ingroup non_mutating_algorithms
4628 * @param __first1 Start of range to search.
4629 * @param __last1 End of range to search.
4630 * @param __first2 Start of match candidates.
4631 * @param __last2 End of match candidates.
4632 * @return The first iterator @c i in the range
4633 * @p [__first1,__last1) such that @c *i == @p *(i2) such that i2 is an
4634 * iterator in [__first2,__last2), or @p __last1 if no such iterator exists.
4635 *
4636 * Searches the range @p [__first1,__last1) for an element that is
4637 * equal to some element in the range [__first2,__last2). If
4638 * found, returns an iterator in the range [__first1,__last1),
4639 * otherwise returns @p __last1.
4640 */
4642 _InputIterator
4645 {
4646 // concept requirements
4660 }
4662 /**
4663 * @brief Find element from a set in a sequence using a predicate.
4664 * @ingroup non_mutating_algorithms
4665 * @param __first1 Start of range to search.
4666 * @param __last1 End of range to search.
4667 * @param __first2 Start of match candidates.
4668 * @param __last2 End of match candidates.
4669 * @param __comp Predicate to use.
4670 * @return The first iterator @c i in the range
4671 * @p [__first1,__last1) such that @c comp(*i, @p *(i2)) is true
4672 * and i2 is an iterator in [__first2,__last2), or @p __last1 if no
4673 * such iterator exists.
4674 *
4676 * Searches the range @p [__first1,__last1) for an element that is
4677 * equal to some element in the range [__first2,__last2). If
4678 * found, returns an iterator in the range [__first1,__last1),
4679 * otherwise returns @p __last1.
4680 */
4682 typename _BinaryPredicate>
4683 _InputIterator
4686 _BinaryPredicate __comp)
4687 {
4688 // concept requirements
4702 }
4704 /**
4705 * @brief Find two adjacent values in a sequence that are equal.
4706 * @ingroup non_mutating_algorithms
4707 * @param __first A forward iterator.
4708 * @param __last A forward iterator.
4709 * @return The first iterator @c i such that @c i and @c i+1 are both
4710 * valid iterators in @p [__first,__last) and such that @c *i == @c *(i+1),
4711 * or @p __last if no such iterator exists.
4712 */
4714 _ForwardIterator
4716 {
4717 // concept requirements
4726 {
4730 }
4732 }
4734 /**
4735 * @brief Find two adjacent values in a sequence using a predicate.
4736 * @ingroup non_mutating_algorithms
4737 * @param __first A forward iterator.
4738 * @param __last A forward iterator.
4739 * @param __binary_pred A binary predicate.
4740 * @return The first iterator @c i such that @c i and @c i+1 are both
4741 * valid iterators in @p [__first,__last) and such that
4742 * @p __binary_pred(*i,*(i+1)) is true, or @p __last if no such iterator
4743 * exists.
4744 */
4746 _ForwardIterator
4748 _BinaryPredicate __binary_pred)
4749 {
4750 // concept requirements
4760 {
4764 }
4766 }
4768 /**
4769 * @brief Count the number of copies of a value in a sequence.
4770 * @ingroup non_mutating_algorithms
4771 * @param __first An input iterator.
4772 * @param __last An input iterator.
4773 * @param __value The value to be counted.
4774 * @return The number of iterators @c i in the range @p [__first,__last)
4775 * for which @c *i == @p __value
4776 */
4780 {
4781 // concept requirements
4791 }
4793 /**
4794 * @brief Count the elements of a sequence for which a predicate is true.
4795 * @ingroup non_mutating_algorithms
4796 * @param __first An input iterator.
4797 * @param __last An input iterator.
4798 * @param __pred A predicate.
4799 * @return The number of iterators @c i in the range @p [__first,__last)
4800 * for which @p __pred(*i) is true.
4801 */
4805 {
4806 // concept requirements
4816 }
4818 /**
4819 * @brief Search a sequence for a matching sub-sequence.
4820 * @ingroup non_mutating_algorithms
4821 * @param __first1 A forward iterator.
4822 * @param __last1 A forward iterator.
4823 * @param __first2 A forward iterator.
4824 * @param __last2 A forward iterator.
4825 * @return The first iterator @c i in the range @p
4826 * [__first1,__last1-(__last2-__first2)) such that @c *(i+N) == @p
4827 * *(__first2+N) for each @c N in the range @p
4828 * [0,__last2-__first2), or @p __last1 if no such iterator exists.
4829 *
4830 * Searches the range @p [__first1,__last1) for a sub-sequence that
4831 * compares equal value-by-value with the sequence given by @p
4832 * [__first2,__last2) and returns an iterator to the first element
4833 * of the sub-sequence, or @p __last1 if the sub-sequence is not
4834 * found.
4835 *
4836 * Because the sub-sequence must lie completely within the range @p
4837 * [__first1,__last1) it must start at a position less than @p
4838 * __last1-(__last2-__first2) where @p __last2-__first2 is the
4839 * length of the sub-sequence.
4840 *
4841 * This means that the returned iterator @c i will be in the range
4842 * @p [__first1,__last1-(__last2-__first2))
4843 */
4845 _ForwardIterator1
4848 {
4849 // concept requirements
4858 // Test for empty ranges
4862 // Test for a pattern of length 1.
4867 // General case.
4868 _ForwardIterator2 __p;
4872 {
4883 {
4888 }
4890 }
4892 }
4894 /**
4895 * @brief Search a sequence for a matching sub-sequence using a predicate.
4896 * @ingroup non_mutating_algorithms
4897 * @param __first1 A forward iterator.
4898 * @param __last1 A forward iterator.
4899 * @param __first2 A forward iterator.
4900 * @param __last2 A forward iterator.
4901 * @param __predicate A binary predicate.
4902 * @return The first iterator @c i in the range
4903 * @p [__first1,__last1-(__last2-__first2)) such that
4904 * @p __predicate(*(i+N),*(__first2+N)) is true for each @c N in the range
4905 * @p [0,__last2-__first2), or @p __last1 if no such iterator exists.
4906 *
4907 * Searches the range @p [__first1,__last1) for a sub-sequence that
4908 * compares equal value-by-value with the sequence given by @p
4909 * [__first2,__last2), using @p __predicate to determine equality,
4910 * and returns an iterator to the first element of the
4911 * sub-sequence, or @p __last1 if no such iterator exists.
4912 *
4913 * @see search(_ForwardIter1, _ForwardIter1, _ForwardIter2, _ForwardIter2)
4914 */
4916 typename _BinaryPredicate>
4917 _ForwardIterator1
4920 _BinaryPredicate __predicate)
4921 {
4922 // concept requirements
4931 // Test for empty ranges
4935 // Test for a pattern of length 1.
4938 {
4943 }
4945 // General case.
4946 _ForwardIterator2 __p;
4950 {
4963 {
4968 }
4970 }
4972 }
4975 /**
4976 * @brief Search a sequence for a number of consecutive values.
4977 * @ingroup non_mutating_algorithms
4978 * @param __first A forward iterator.
4979 * @param __last A forward iterator.
4980 * @param __count The number of consecutive values.
4981 * @param __val The value to find.
4982 * @return The first iterator @c i in the range @p
4983 * [__first,__last-__count) such that @c *(i+N) == @p __val for
4984 * each @c N in the range @p [0,__count), or @p __last if no such
4985 * iterator exists.
4986 *
4987 * Searches the range @p [__first,__last) for @p count consecutive elements
4988 * equal to @p __val.
4989 */
4991 _ForwardIterator
4994 {
4995 // concept requirements
5007 }
5010 /**
5011 * @brief Search a sequence for a number of consecutive values using a
5012 * predicate.
5013 * @ingroup non_mutating_algorithms
5014 * @param __first A forward iterator.
5015 * @param __last A forward iterator.
5016 * @param __count The number of consecutive values.
5017 * @param __val The value to find.
5018 * @param __binary_pred A binary predicate.
5019 * @return The first iterator @c i in the range @p
5020 * [__first,__last-__count) such that @p
5021 * __binary_pred(*(i+N),__val) is true for each @c N in the range
5022 * @p [0,__count), or @p __last if no such iterator exists.
5023 *
5024 * Searches the range @p [__first,__last) for @p __count
5025 * consecutive elements for which the predicate returns true.
5026 */
5028 typename _BinaryPredicate>
5029 _ForwardIterator
5032 _BinaryPredicate __binary_pred)
5033 {
5034 // concept requirements
5043 {
5047 }
5050 }
5053 /**
5054 * @brief Perform an operation on a sequence.
5055 * @ingroup mutating_algorithms
5056 * @param __first An input iterator.
5057 * @param __last An input iterator.
5058 * @param __result An output iterator.
5059 * @param __unary_op A unary operator.
5060 * @return An output iterator equal to @p __result+(__last-__first).
5061 *
5062 * Applies the operator to each element in the input range and assigns
5063 * the results to successive elements of the output sequence.
5064 * Evaluates @p *(__result+N)=unary_op(*(__first+N)) for each @c N in the
5065 * range @p [0,__last-__first).
5066 *
5067 * @p unary_op must not alter its argument.
5068 */
5070 typename _UnaryOperation>
5071 _OutputIterator
5074 {
5075 // concept requirements
5078 // "the type returned by a _UnaryOperation"
5085 }
5087 /**
5088 * @brief Perform an operation on corresponding elements of two sequences.
5089 * @ingroup mutating_algorithms
5090 * @param __first1 An input iterator.
5091 * @param __last1 An input iterator.
5092 * @param __first2 An input iterator.
5093 * @param __result An output iterator.
5094 * @param __binary_op A binary operator.
5095 * @return An output iterator equal to @p result+(last-first).
5096 *
5097 * Applies the operator to the corresponding elements in the two
5098 * input ranges and assigns the results to successive elements of the
5099 * output sequence.
5100 * Evaluates @p
5101 * *(__result+N)=__binary_op(*(__first1+N),*(__first2+N)) for each
5102 * @c N in the range @p [0,__last1-__first1).
5103 *
5104 * @p binary_op must not alter either of its arguments.
5105 */
5108 _OutputIterator
5111 _BinaryOperation __binary_op)
5112 {
5113 // concept requirements
5117 // "the type returned by a _BinaryOperation"
5124 }
5126 /**
5127 * @brief Replace each occurrence of one value in a sequence with another
5128 * value.
5129 * @ingroup mutating_algorithms
5130 * @param __first A forward iterator.
5131 * @param __last A forward iterator.
5132 * @param __old_value The value to be replaced.
5133 * @param __new_value The replacement value.
5134 * @return replace() returns no value.
5135 *
5136 * For each iterator @c i in the range @p [__first,__last) if @c *i ==
5137 * @p __old_value then the assignment @c *i = @p __new_value is performed.
5138 */
5140 void
5143 {
5144 // concept requirements
5146 _ForwardIterator>)
5156 }
5158 /**
5159 * @brief Replace each value in a sequence for which a predicate returns
5160 * true with another value.
5161 * @ingroup mutating_algorithms
5162 * @param __first A forward iterator.
5163 * @param __last A forward iterator.
5164 * @param __pred A predicate.
5165 * @param __new_value The replacement value.
5166 * @return replace_if() returns no value.
5167 *
5168 * For each iterator @c i in the range @p [__first,__last) if @p __pred(*i)
5169 * is true then the assignment @c *i = @p __new_value is performed.
5170 */
5172 void
5175 {
5176 // concept requirements
5178 _ForwardIterator>)
5188 }
5190 /**
5191 * @brief Assign the result of a function object to each value in a
5192 * sequence.
5193 * @ingroup mutating_algorithms
5194 * @param __first A forward iterator.
5195 * @param __last A forward iterator.
5196 * @param __gen A function object taking no arguments and returning
5197 * std::iterator_traits<_ForwardIterator>::value_type
5198 * @return generate() returns no value.
5199 *
5200 * Performs the assignment @c *i = @p __gen() for each @c i in the range
5201 * @p [__first,__last).
5202 */
5204 void
5206 _Generator __gen)
5207 {
5208 // concept requirements
5216 }
5218 /**
5219 * @brief Assign the result of a function object to each value in a
5220 * sequence.
5221 * @ingroup mutating_algorithms
5222 * @param __first A forward iterator.
5223 * @param __n The length of the sequence.
5224 * @param __gen A function object taking no arguments and returning
5225 * std::iterator_traits<_ForwardIterator>::value_type
5226 * @return The end of the sequence, @p __first+__n
5227 *
5228 * Performs the assignment @c *i = @p __gen() for each @c i in the range
5229 * @p [__first,__first+__n).
5230 *
5231 * _GLIBCXX_RESOLVE_LIB_DEFECTS
5232 * DR 865. More algorithms that throw away information
5233 */
5235 _OutputIterator
5237 {
5238 // concept requirements
5240 // "the type returned by a _Generator"
5247 }
5250 /**
5251 * @brief Copy a sequence, removing consecutive duplicate values.
5252 * @ingroup mutating_algorithms
5253 * @param __first An input iterator.
5254 * @param __last An input iterator.
5255 * @param __result An output iterator.
5256 * @return An iterator designating the end of the resulting sequence.
5257 *
5258 * Copies each element in the range @p [__first,__last) to the range
5259 * beginning at @p __result, except that only the first element is copied
5260 * from groups of consecutive elements that compare equal.
5261 * unique_copy() is stable, so the relative order of elements that are
5262 * copied is unchanged.
5263 *
5264 * _GLIBCXX_RESOLVE_LIB_DEFECTS
5265 * DR 241. Does unique_copy() require CopyConstructible and Assignable?
5266 *
5267 * _GLIBCXX_RESOLVE_LIB_DEFECTS
5268 * DR 538. 241 again: Does unique_copy() require CopyConstructible and
5269 * Assignable?
5270 */
5272 inline _OutputIterator
5274 _OutputIterator __result)
5275 {
5276 // concept requirements
5289 }
5291 /**
5292 * @brief Copy a sequence, removing consecutive values using a predicate.
5293 * @ingroup mutating_algorithms
5294 * @param __first An input iterator.
5295 * @param __last An input iterator.
5296 * @param __result An output iterator.
5297 * @param __binary_pred A binary predicate.
5298 * @return An iterator designating the end of the resulting sequence.
5299 *
5300 * Copies each element in the range @p [__first,__last) to the range
5301 * beginning at @p __result, except that only the first element is copied
5302 * from groups of consecutive elements for which @p __binary_pred returns
5303 * true.
5304 * unique_copy() is stable, so the relative order of elements that are
5305 * copied is unchanged.
5306 *
5307 * _GLIBCXX_RESOLVE_LIB_DEFECTS
5308 * DR 241. Does unique_copy() require CopyConstructible and Assignable?
5309 */
5311 typename _BinaryPredicate>
5312 inline _OutputIterator
5314 _OutputIterator __result,
5315 _BinaryPredicate __binary_pred)
5316 {
5317 // concept requirements -- predicates checked later
5328 }
5331 /**
5332 * @brief Randomly shuffle the elements of a sequence.
5333 * @ingroup mutating_algorithms
5334 * @param __first A forward iterator.
5335 * @param __last A forward iterator.
5336 * @return Nothing.
5337 *
5338 * Reorder the elements in the range @p [__first,__last) using a random
5339 * distribution, so that every possible ordering of the sequence is
5340 * equally likely.
5341 */
5345 {
5346 // concept requirements
5348 _RandomAccessIterator>)
5354 }
5356 /**
5357 * @brief Shuffle the elements of a sequence using a random number
5358 * generator.
5359 * @ingroup mutating_algorithms
5360 * @param __first A forward iterator.
5361 * @param __last A forward iterator.
5362 * @param __rand The RNG functor or function.
5363 * @return Nothing.
5364 *
5365 * Reorders the elements in the range @p [__first,__last) using @p __rand to
5366 * provide a random distribution. Calling @p __rand(N) for a positive
5367 * integer @p N should return a randomly chosen integer from the
5368 * range [0,N).
5369 */
5371 void
5373 #if __cplusplus >= 201103L
5375 #else
5377 #endif
5378 {
5379 // concept requirements
5381 _RandomAccessIterator>)
5388 }
5391 /**
5392 * @brief Move elements for which a predicate is true to the beginning
5393 * of a sequence.
5394 * @ingroup mutating_algorithms
5395 * @param __first A forward iterator.
5396 * @param __last A forward iterator.
5397 * @param __pred A predicate functor.
5398 * @return An iterator @p middle such that @p __pred(i) is true for each
5399 * iterator @p i in the range @p [__first,middle) and false for each @p i
5400 * in the range @p [middle,__last).
5401 *
5402 * @p __pred must not modify its operand. @p partition() does not preserve
5403 * the relative ordering of elements in each group, use
5404 * @p stable_partition() if this is needed.
5405 */
5407 inline _ForwardIterator
5409 _Predicate __pred)
5410 {
5411 // concept requirements
5413 _ForwardIterator>)
5420 }
5424 /**
5425 * @brief Sort the smallest elements of a sequence.
5426 * @ingroup sorting_algorithms
5427 * @param __first An iterator.
5428 * @param __middle Another iterator.
5429 * @param __last Another iterator.
5430 * @return Nothing.
5431 *
5432 * Sorts the smallest @p (__middle-__first) elements in the range
5433 * @p [first,last) and moves them to the range @p [__first,__middle). The
5434 * order of the remaining elements in the range @p [__middle,__last) is
5435 * undefined.
5436 * After the sort if @e i and @e j are iterators in the range
5437 * @p [__first,__middle) such that i precedes j and @e k is an iterator in
5438 * the range @p [__middle,__last) then *j<*i and *k<*i are both false.
5439 */
5443 _RandomAccessIterator __middle,
5444 _RandomAccessIterator __last)
5445 {
5447 _ValueType;
5449 // concept requirements
5451 _RandomAccessIterator>)
5458 }
5460 /**
5461 * @brief Sort the smallest elements of a sequence using a predicate
5462 * for comparison.
5463 * @ingroup sorting_algorithms
5464 * @param __first An iterator.
5465 * @param __middle Another iterator.
5466 * @param __last Another iterator.
5467 * @param __comp A comparison functor.
5468 * @return Nothing.
5469 *
5470 * Sorts the smallest @p (__middle-__first) elements in the range
5471 * @p [__first,__last) and moves them to the range @p [__first,__middle). The
5472 * order of the remaining elements in the range @p [__middle,__last) is
5473 * undefined.
5474 * After the sort if @e i and @e j are iterators in the range
5475 * @p [__first,__middle) such that i precedes j and @e k is an iterator in
5476 * the range @p [__middle,__last) then @p *__comp(j,*i) and @p __comp(*k,*i)
5477 * are both false.
5478 */
5482 _RandomAccessIterator __middle,
5483 _RandomAccessIterator __last,
5484 _Compare __comp)
5485 {
5487 _ValueType;
5489 // concept requirements
5491 _RandomAccessIterator>)
5499 }
5501 /**
5502 * @brief Sort a sequence just enough to find a particular position.
5503 * @ingroup sorting_algorithms
5504 * @param __first An iterator.
5505 * @param __nth Another iterator.
5506 * @param __last Another iterator.
5507 * @return Nothing.
5508 *
5509 * Rearranges the elements in the range @p [__first,__last) so that @p *__nth
5510 * is the same element that would have been in that position had the
5511 * whole sequence been sorted. The elements either side of @p *__nth are
5512 * not completely sorted, but for any iterator @e i in the range
5513 * @p [__first,__nth) and any iterator @e j in the range @p [__nth,__last) it
5514 * holds that *j < *i is false.
5515 */
5519 _RandomAccessIterator __last)
5520 {
5522 _ValueType;
5524 // concept requirements
5526 _RandomAccessIterator>)
5536 }
5538 /**
5539 * @brief Sort a sequence just enough to find a particular position
5540 * using a predicate for comparison.
5541 * @ingroup sorting_algorithms
5542 * @param __first An iterator.
5543 * @param __nth Another iterator.
5544 * @param __last Another iterator.
5545 * @param __comp A comparison functor.
5546 * @return Nothing.
5547 *
5548 * Rearranges the elements in the range @p [__first,__last) so that @p *__nth
5549 * is the same element that would have been in that position had the
5550 * whole sequence been sorted. The elements either side of @p *__nth are
5551 * not completely sorted, but for any iterator @e i in the range
5552 * @p [__first,__nth) and any iterator @e j in the range @p [__nth,__last) it
5553 * holds that @p __comp(*j,*i) is false.
5554 */
5559 {
5561 _ValueType;
5563 // concept requirements
5565 _RandomAccessIterator>)
5576 }
5579 /**
5580 * @brief Sort the elements of a sequence.
5581 * @ingroup sorting_algorithms
5582 * @param __first An iterator.
5583 * @param __last Another iterator.
5584 * @return Nothing.
5585 *
5586 * Sorts the elements in the range @p [__first,__last) in ascending order,
5587 * such that for each iterator @e i in the range @p [__first,__last-1),
5588 * *(i+1)<*i is false.
5589 *
5590 * The relative ordering of equivalent elements is not preserved, use
5591 * @p stable_sort() if this is needed.
5592 */
5596 {
5598 _ValueType;
5600 // concept requirements
5602 _RandomAccessIterator>)
5607 {
5611 }
5612 }
5614 /**
5615 * @brief Sort the elements of a sequence using a predicate for comparison.
5616 * @ingroup sorting_algorithms
5617 * @param __first An iterator.
5618 * @param __last Another iterator.
5619 * @param __comp A comparison functor.
5620 * @return Nothing.
5621 *
5622 * Sorts the elements in the range @p [__first,__last) in ascending order,
5623 * such that @p __comp(*(i+1),*i) is false for every iterator @e i in the
5624 * range @p [__first,__last-1).
5625 *
5626 * The relative ordering of equivalent elements is not preserved, use
5627 * @p stable_sort() if this is needed.
5628 */
5632 _Compare __comp)
5633 {
5635 _ValueType;
5637 // concept requirements
5639 _RandomAccessIterator>)
5641 _ValueType>)
5645 {
5649 }
5650 }
5652 /**
5653 * @brief Merges two sorted ranges.
5654 * @ingroup sorting_algorithms
5655 * @param __first1 An iterator.
5656 * @param __first2 Another iterator.
5657 * @param __last1 Another iterator.
5658 * @param __last2 Another iterator.
5659 * @param __result An iterator pointing to the end of the merged range.
5660 * @return An iterator pointing to the first element <em>not less
5661 * than</em> @e val.
5662 *
5663 * Merges the ranges @p [__first1,__last1) and @p [__first2,__last2) into
5664 * the sorted range @p [__result, __result + (__last1-__first1) +
5665 * (__last2-__first2)). Both input ranges must be sorted, and the
5666 * output range must not overlap with either of the input ranges.
5667 * The sort is @e stable, that is, for equivalent elements in the
5668 * two ranges, elements from the first range will always come
5669 * before elements from the second.
5670 */
5672 typename _OutputIterator>
5673 _OutputIterator
5676 _OutputIterator __result)
5677 {
5679 _ValueType1;
5681 _ValueType2;
5683 // concept requirements
5687 _ValueType1>)
5689 _ValueType2>)
5695 {
5697 {
5700 }
5701 else
5702 {
5705 }
5707 }
5709 __result));
5710 }
5712 /**
5713 * @brief Merges two sorted ranges.
5714 * @ingroup sorting_algorithms
5715 * @param __first1 An iterator.
5716 * @param __first2 Another iterator.
5717 * @param __last1 Another iterator.
5718 * @param __last2 Another iterator.
5719 * @param __result An iterator pointing to the end of the merged range.
5720 * @param __comp A functor to use for comparisons.
5721 * @return An iterator pointing to the first element "not less
5722 * than" @e val.
5723 *
5724 * Merges the ranges @p [__first1,__last1) and @p [__first2,__last2) into
5725 * the sorted range @p [__result, __result + (__last1-__first1) +
5726 * (__last2-__first2)). Both input ranges must be sorted, and the
5727 * output range must not overlap with either of the input ranges.
5728 * The sort is @e stable, that is, for equivalent elements in the
5729 * two ranges, elements from the first range will always come
5730 * before elements from the second.
5731 *
5732 * The comparison function should have the same effects on ordering as
5733 * the function used for the initial sort.
5734 */
5737 _OutputIterator
5741 {
5743 _ValueType1;
5745 _ValueType2;
5747 // concept requirements
5751 _ValueType1>)
5753 _ValueType2>)
5760 {
5762 {
5765 }
5766 else
5767 {
5770 }
5772 }
5774 __result));
5775 }
5778 /**
5779 * @brief Sort the elements of a sequence, preserving the relative order
5780 * of equivalent elements.
5781 * @ingroup sorting_algorithms
5782 * @param __first An iterator.
5783 * @param __last Another iterator.
5784 * @return Nothing.
5785 *
5786 * Sorts the elements in the range @p [__first,__last) in ascending order,
5787 * such that for each iterator @p i in the range @p [__first,__last-1),
5788 * @p *(i+1)<*i is false.
5789 *
5790 * The relative ordering of equivalent elements is preserved, so any two
5791 * elements @p x and @p y in the range @p [__first,__last) such that
5792 * @p x<y is false and @p y<x is false will have the same relative
5793 * ordering after calling @p stable_sort().
5794 */
5798 {
5800 _ValueType;
5802 _DistanceType;
5804 // concept requirements
5806 _RandomAccessIterator>)
5811 __last);
5814 else
5817 }
5819 /**
5820 * @brief Sort the elements of a sequence using a predicate for comparison,
5821 * preserving the relative order of equivalent elements.
5822 * @ingroup sorting_algorithms
5823 * @param __first An iterator.
5824 * @param __last Another iterator.
5825 * @param __comp A comparison functor.
5826 * @return Nothing.
5827 *
5828 * Sorts the elements in the range @p [__first,__last) in ascending order,
5829 * such that for each iterator @p i in the range @p [__first,__last-1),
5830 * @p __comp(*(i+1),*i) is false.
5831 *
5832 * The relative ordering of equivalent elements is preserved, so any two
5833 * elements @p x and @p y in the range @p [__first,__last) such that
5834 * @p __comp(x,y) is false and @p __comp(y,x) is false will have the same
5835 * relative ordering after calling @p stable_sort().
5836 */
5840 _Compare __comp)
5841 {
5843 _ValueType;
5845 _DistanceType;
5847 // concept requirements
5849 _RandomAccessIterator>)
5851 _ValueType,
5852 _ValueType>)
5856 __last);
5859 else
5862 }
5865 /**
5866 * @brief Return the union of two sorted ranges.
5867 * @ingroup set_algorithms
5868 * @param __first1 Start of first range.
5869 * @param __last1 End of first range.
5870 * @param __first2 Start of second range.
5871 * @param __last2 End of second range.
5872 * @return End of the output range.
5873 * @ingroup set_algorithms
5874 *
5875 * This operation iterates over both ranges, copying elements present in
5876 * each range in order to the output range. Iterators increment for each
5877 * range. When the current element of one range is less than the other,
5878 * that element is copied and the iterator advanced. If an element is
5879 * contained in both ranges, the element from the first range is copied and
5880 * both ranges advance. The output range may not overlap either input
5881 * range.
5882 */
5884 typename _OutputIterator>
5885 _OutputIterator
5888 _OutputIterator __result)
5889 {
5891 _ValueType1;
5893 _ValueType2;
5895 // concept requirements
5899 _ValueType1>)
5901 _ValueType2>)
5908 {
5910 {
5913 }
5915 {
5918 }
5919 else
5920 {
5924 }
5926 }
5928 __result));
5929 }
5931 /**
5932 * @brief Return the union of two sorted ranges using a comparison functor.
5933 * @ingroup set_algorithms
5934 * @param __first1 Start of first range.
5935 * @param __last1 End of first range.
5936 * @param __first2 Start of second range.
5937 * @param __last2 End of second range.
5938 * @param __comp The comparison functor.
5939 * @return End of the output range.
5940 * @ingroup set_algorithms
5941 *
5942 * This operation iterates over both ranges, copying elements present in
5943 * each range in order to the output range. Iterators increment for each
5944 * range. When the current element of one range is less than the other
5945 * according to @p __comp, that element is copied and the iterator advanced.
5946 * If an equivalent element according to @p __comp is contained in both
5947 * ranges, the element from the first range is copied and both ranges
5948 * advance. The output range may not overlap either input range.
5949 */
5952 _OutputIterator
5956 {
5958 _ValueType1;
5960 _ValueType2;
5962 // concept requirements
5966 _ValueType1>)
5968 _ValueType2>)
5977 {
5979 {
5982 }
5984 {
5987 }
5988 else
5989 {
5993 }
5995 }
5997 __result));
5998 }
6000 /**
6001 * @brief Return the intersection of two sorted ranges.
6002 * @ingroup set_algorithms
6003 * @param __first1 Start of first range.
6004 * @param __last1 End of first range.
6005 * @param __first2 Start of second range.
6006 * @param __last2 End of second range.
6007 * @return End of the output range.
6008 * @ingroup set_algorithms
6009 *
6010 * This operation iterates over both ranges, copying elements present in
6011 * both ranges in order to the output range. Iterators increment for each
6012 * range. When the current element of one range is less than the other,
6013 * that iterator advances. If an element is contained in both ranges, the
6014 * element from the first range is copied and both ranges advance. The
6015 * output range may not overlap either input range.
6016 */
6018 typename _OutputIterator>
6019 _OutputIterator
6022 _OutputIterator __result)
6023 {
6025 _ValueType1;
6027 _ValueType2;
6029 // concept requirements
6033 _ValueType1>)
6044 else
6045 {
6050 }
6052 }
6054 /**
6055 * @brief Return the intersection of two sorted ranges using comparison
6056 * functor.
6057 * @ingroup set_algorithms
6058 * @param __first1 Start of first range.
6059 * @param __last1 End of first range.
6060 * @param __first2 Start of second range.
6061 * @param __last2 End of second range.
6062 * @param __comp The comparison functor.
6063 * @return End of the output range.
6064 * @ingroup set_algorithms
6065 *
6066 * This operation iterates over both ranges, copying elements present in
6067 * both ranges in order to the output range. Iterators increment for each
6068 * range. When the current element of one range is less than the other
6069 * according to @p __comp, that iterator advances. If an element is
6070 * contained in both ranges according to @p __comp, the element from the
6071 * first range is copied and both ranges advance. The output range may not
6072 * overlap either input range.
6073 */
6076 _OutputIterator
6080 {
6082 _ValueType1;
6084 _ValueType2;
6086 // concept requirements
6090 _ValueType1>)
6103 else
6104 {
6109 }
6111 }
6113 /**
6114 * @brief Return the difference of two sorted ranges.
6115 * @ingroup set_algorithms
6116 * @param __first1 Start of first range.
6117 * @param __last1 End of first range.
6118 * @param __first2 Start of second range.
6119 * @param __last2 End of second range.
6120 * @return End of the output range.
6121 * @ingroup set_algorithms
6122 *
6123 * This operation iterates over both ranges, copying elements present in
6124 * the first range but not the second in order to the output range.
6125 * Iterators increment for each range. When the current element of the
6126 * first range is less than the second, that element is copied and the
6127 * iterator advances. If the current element of the second range is less,
6128 * the iterator advances, but no element is copied. If an element is
6129 * contained in both ranges, no elements are copied and both ranges
6130 * advance. The output range may not overlap either input range.
6131 */
6133 typename _OutputIterator>
6134 _OutputIterator
6137 _OutputIterator __result)
6138 {
6140 _ValueType1;
6142 _ValueType2;
6144 // concept requirements
6148 _ValueType1>)
6156 {
6160 }
6163 else
6164 {
6167 }
6169 }
6171 /**
6172 * @brief Return the difference of two sorted ranges using comparison
6173 * functor.
6174 * @ingroup set_algorithms
6175 * @param __first1 Start of first range.
6176 * @param __last1 End of first range.
6177 * @param __first2 Start of second range.
6178 * @param __last2 End of second range.
6179 * @param __comp The comparison functor.
6180 * @return End of the output range.
6181 * @ingroup set_algorithms
6182 *
6183 * This operation iterates over both ranges, copying elements present in
6184 * the first range but not the second in order to the output range.
6185 * Iterators increment for each range. When the current element of the
6186 * first range is less than the second according to @p __comp, that element
6187 * is copied and the iterator advances. If the current element of the
6188 * second range is less, no element is copied and the iterator advances.
6189 * If an element is contained in both ranges according to @p __comp, no
6190 * elements are copied and both ranges advance. The output range may not
6191 * overlap either input range.
6192 */
6195 _OutputIterator
6199 {
6201 _ValueType1;
6203 _ValueType2;
6205 // concept requirements
6209 _ValueType1>)
6219 {
6223 }
6226 else
6227 {
6230 }
6232 }
6234 /**
6235 * @brief Return the symmetric difference of two sorted ranges.
6236 * @ingroup set_algorithms
6237 * @param __first1 Start of first range.
6238 * @param __last1 End of first range.
6239 * @param __first2 Start of second range.
6240 * @param __last2 End of second range.
6241 * @return End of the output range.
6242 * @ingroup set_algorithms
6243 *
6244 * This operation iterates over both ranges, copying elements present in
6245 * one range but not the other in order to the output range. Iterators
6246 * increment for each range. When the current element of one range is less
6247 * than the other, that element is copied and the iterator advances. If an
6248 * element is contained in both ranges, no elements are copied and both
6249 * ranges advance. The output range may not overlap either input range.
6250 */
6252 typename _OutputIterator>
6253 _OutputIterator
6256 _OutputIterator __result)
6257 {
6259 _ValueType1;
6261 _ValueType2;
6263 // concept requirements
6267 _ValueType1>)
6269 _ValueType2>)
6277 {
6281 }
6283 {
6287 }
6288 else
6289 {
6292 }
6295 }
6297 /**
6298 * @brief Return the symmetric difference of two sorted ranges using
6299 * comparison functor.
6300 * @ingroup set_algorithms
6301 * @param __first1 Start of first range.
6302 * @param __last1 End of first range.
6303 * @param __first2 Start of second range.
6304 * @param __last2 End of second range.
6305 * @param __comp The comparison functor.
6306 * @return End of the output range.
6307 * @ingroup set_algorithms
6308 *
6309 * This operation iterates over both ranges, copying elements present in
6310 * one range but not the other in order to the output range. Iterators
6311 * increment for each range. When the current element of one range is less
6312 * than the other according to @p comp, that element is copied and the
6313 * iterator advances. If an element is contained in both ranges according
6314 * to @p __comp, no elements are copied and both ranges advance. The output
6315 * range may not overlap either input range.
6316 */
6319 _OutputIterator
6322 _OutputIterator __result,
6323 _Compare __comp)
6324 {
6326 _ValueType1;
6328 _ValueType2;
6330 // concept requirements
6334 _ValueType1>)
6336 _ValueType2>)
6346 {
6350 }
6352 {
6356 }
6357 else
6358 {
6361 }
6364 }
6367 /**
6368 * @brief Return the minimum element in a range.
6369 * @ingroup sorting_algorithms
6370 * @param __first Start of range.
6371 * @param __last End of range.
6372 * @return Iterator referencing the first instance of the smallest value.
6373 */
6375 _ForwardIterator
6377 {
6378 // concept requirements
6391 }
6393 /**
6394 * @brief Return the minimum element in a range using comparison functor.
6395 * @ingroup sorting_algorithms
6396 * @param __first Start of range.
6397 * @param __last End of range.
6398 * @param __comp Comparison functor.
6399 * @return Iterator referencing the first instance of the smallest value
6400 * according to __comp.
6401 */
6403 _ForwardIterator
6405 _Compare __comp)
6406 {
6407 // concept requirements
6421 }
6423 /**
6424 * @brief Return the maximum element in a range.
6425 * @ingroup sorting_algorithms
6426 * @param __first Start of range.
6427 * @param __last End of range.
6428 * @return Iterator referencing the first instance of the largest value.
6429 */
6431 _ForwardIterator
6433 {
6434 // concept requirements
6447 }
6449 /**
6450 * @brief Return the maximum element in a range using comparison functor.
6451 * @ingroup sorting_algorithms
6452 * @param __first Start of range.
6453 * @param __last End of range.
6454 * @param __comp Comparison functor.
6455 * @return Iterator referencing the first instance of the largest value
6456 * according to __comp.
6457 */
6459 _ForwardIterator
6461 _Compare __comp)
6462 {
6463 // concept requirements
6476 }
6478 _GLIBCXX_END_NAMESPACE_ALGO