| blob | 0fdc924cbe39ff730c715d0bc69594e8c5279be9 |
1 // Algorithm implementation -*- C++ -*-
3 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
4 // Free Software Foundation, Inc.
5 //
6 // This file is part of the GNU ISO C++ Library. This library is free
7 // software; you can redistribute it and/or modify it under the
8 // terms of the GNU General Public License as published by the
9 // Free Software Foundation; either version 3, or (at your option)
10 // any later version.
12 // This library is distributed in the hope that it will be useful,
13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 // GNU General Public License for more details.
17 // Under Section 7 of GPL version 3, you are granted additional
18 // permissions described in the GCC Runtime Library Exception, version
19 // 3.1, as published by the Free Software Foundation.
21 // You should have received a copy of the GNU General Public License and
22 // a copy of the GCC Runtime Library Exception along with this program;
23 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
24 // <http://www.gnu.org/licenses/>.
26 /*
27 *
28 * Copyright (c) 1994
29 * Hewlett-Packard Company
30 *
31 * Permission to use, copy, modify, distribute and sell this software
32 * and its documentation for any purpose is hereby granted without fee,
33 * provided that the above copyright notice appear in all copies and
34 * that both that copyright notice and this permission notice appear
35 * in supporting documentation. Hewlett-Packard Company makes no
36 * representations about the suitability of this software for any
37 * purpose. It is provided "as is" without express or implied warranty.
38 *
39 *
40 * Copyright (c) 1996
41 * Silicon Graphics Computer Systems, Inc.
42 *
43 * Permission to use, copy, modify, distribute and sell this software
44 * and its documentation for any purpose is hereby granted without fee,
45 * provided that the above copyright notice appear in all copies and
46 * that both that copyright notice and this permission notice appear
47 * in supporting documentation. Silicon Graphics makes no
48 * representations about the suitability of this software for any
49 * purpose. It is provided "as is" without express or implied warranty.
50 */
52 /** @file bits/stl_algo.h
53 * This is an internal header file, included by other library headers.
54 * Do not attempt to use it directly. @headername{algorithm}
55 */
57 #ifndef _STL_ALGO_H
58 #define _STL_ALGO_H 1
61 #include <bits/algorithmfwd.h>
62 #include <bits/stl_heap.h>
65 #ifdef __GXX_EXPERIMENTAL_CXX0X__
67 #endif
69 // See concept_check.h for the __glibcxx_*_requires macros.
73 /// Swaps the median value of *__a, *__b and *__c to *__a
75 void
77 {
78 // concept requirements
83 {
88 }
93 else
95 }
97 /// Swaps the median value of *__a, *__b and *__c under __comp to *__a
99 void
101 _Compare __comp)
102 {
103 // concept requirements
109 {
114 }
119 else
121 }
123 // for_each
125 /// This is an overload used by find() for the Input Iterator case.
127 inline _InputIterator
130 {
134 }
136 /// This is an overload used by find_if() for the Input Iterator case.
138 inline _InputIterator
141 {
145 }
147 /// This is an overload used by find() for the RAI case.
149 _RandomAccessIterator
152 {
157 {
173 }
176 {
192 }
193 }
195 /// This is an overload used by find_if() for the RAI case.
197 _RandomAccessIterator
200 {
205 {
221 }
224 {
240 }
241 }
243 #ifdef __GXX_EXPERIMENTAL_CXX0X__
244 /// This is an overload used by find_if_not() for the Input Iterator case.
246 inline _InputIterator
249 {
253 }
255 /// This is an overload used by find_if_not() for the RAI case.
257 _RandomAccessIterator
260 {
265 {
281 }
284 {
300 }
301 }
302 #endif
304 // set_difference
305 // set_intersection
306 // set_symmetric_difference
307 // set_union
308 // for_each
309 // find
310 // find_if
311 // find_first_of
312 // adjacent_find
313 // count
314 // count_if
315 // search
317 /**
318 * This is an uglified
319 * search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&)
320 * overloaded for forward iterators.
321 */
323 _ForwardIterator
327 {
330 {
336 {
339 }
345 }
347 }
349 /**
350 * This is an uglified
351 * search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&)
352 * overloaded for random access iterators.
353 */
355 _RandomAccessIter
359 {
362 _DistanceType;
375 {
376 // __lookAhead here is always pointing to the last element of next
377 // possible match.
379 {
384 }
388 {
391 }
396 }
397 }
399 // search_n
401 /**
402 * This is an uglified
403 * search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&,
404 * _BinaryPredicate)
405 * overloaded for forward iterators.
406 */
408 typename _BinaryPredicate>
409 _ForwardIterator
413 {
418 {
424 {
427 }
436 }
438 }
440 /**
441 * This is an uglified
442 * search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&,
443 * _BinaryPredicate)
444 * overloaded for random access iterators.
445 */
447 typename _BinaryPredicate>
448 _RandomAccessIter
452 {
455 _DistanceType;
468 {
469 // __lookAhead here is always pointing to the last element of next
470 // possible match.
472 {
477 }
481 {
484 }
489 }
490 }
492 // find_end for forward iterators.
494 _ForwardIterator1
498 {
501 else
502 {
505 {
506 _ForwardIterator1 __new_result
510 else
511 {
515 }
516 }
517 }
518 }
521 typename _BinaryPredicate>
522 _ForwardIterator1
526 _BinaryPredicate __comp)
527 {
530 else
531 {
534 {
535 _ForwardIterator1 __new_result
540 else
541 {
545 }
546 }
547 }
548 }
550 // find_end for bidirectional iterators (much faster).
552 _BidirectionalIterator1
554 _BidirectionalIterator1 __last1,
555 _BidirectionalIterator2 __first2,
556 _BidirectionalIterator2 __last2,
558 {
559 // concept requirements
561 _BidirectionalIterator1>)
563 _BidirectionalIterator2>)
571 __rlast1,
573 __rlast2);
577 else
578 {
582 }
583 }
586 typename _BinaryPredicate>
587 _BidirectionalIterator1
589 _BidirectionalIterator1 __last1,
590 _BidirectionalIterator2 __first2,
591 _BidirectionalIterator2 __last2,
593 _BinaryPredicate __comp)
594 {
595 // concept requirements
597 _BidirectionalIterator1>)
599 _BidirectionalIterator2>)
608 __comp);
612 else
613 {
617 }
618 }
620 /**
621 * @brief Find last matching subsequence in a sequence.
622 * @ingroup non_mutating_algorithms
623 * @param first1 Start of range to search.
624 * @param last1 End of range to search.
625 * @param first2 Start of sequence to match.
626 * @param last2 End of sequence to match.
627 * @return The last iterator @c i in the range
628 * @p [first1,last1-(last2-first2)) such that @c *(i+N) == @p *(first2+N)
629 * for each @c N in the range @p [0,last2-first2), or @p last1 if no
630 * such iterator exists.
631 *
632 * Searches the range @p [first1,last1) for a sub-sequence that compares
633 * equal value-by-value with the sequence given by @p [first2,last2) and
634 * returns an iterator to the first element of the sub-sequence, or
635 * @p last1 if the sub-sequence is not found. The sub-sequence will be the
636 * last such subsequence contained in [first,last1).
637 *
638 * Because the sub-sequence must lie completely within the range
639 * @p [first1,last1) it must start at a position less than
640 * @p last1-(last2-first2) where @p last2-first2 is the length of the
641 * sub-sequence.
642 * This means that the returned iterator @c i will be in the range
643 * @p [first1,last1-(last2-first2))
644 */
646 inline _ForwardIterator1
649 {
650 // concept requirements
662 }
664 /**
665 * @brief Find last matching subsequence in a sequence using a predicate.
666 * @ingroup non_mutating_algorithms
667 * @param first1 Start of range to search.
668 * @param last1 End of range to search.
669 * @param first2 Start of sequence to match.
670 * @param last2 End of sequence to match.
671 * @param comp The predicate to use.
672 * @return The last iterator @c i in the range
673 * @p [first1,last1-(last2-first2)) such that @c predicate(*(i+N), @p
674 * (first2+N)) is true for each @c N in the range @p [0,last2-first2), or
675 * @p last1 if no such iterator exists.
676 *
677 * Searches the range @p [first1,last1) for a sub-sequence that compares
678 * equal value-by-value with the sequence given by @p [first2,last2) using
679 * comp as a predicate and returns an iterator to the first element of the
680 * sub-sequence, or @p last1 if the sub-sequence is not found. The
681 * sub-sequence will be the last such subsequence contained in
682 * [first,last1).
683 *
684 * Because the sub-sequence must lie completely within the range
685 * @p [first1,last1) it must start at a position less than
686 * @p last1-(last2-first2) where @p last2-first2 is the length of the
687 * sub-sequence.
688 * This means that the returned iterator @c i will be in the range
689 * @p [first1,last1-(last2-first2))
690 */
692 typename _BinaryPredicate>
693 inline _ForwardIterator1
696 _BinaryPredicate __comp)
697 {
698 // concept requirements
710 __comp);
711 }
713 #ifdef __GXX_EXPERIMENTAL_CXX0X__
714 /**
715 * @brief Checks that a predicate is true for all the elements
716 * of a sequence.
717 * @ingroup non_mutating_algorithms
718 * @param first An input iterator.
719 * @param last An input iterator.
720 * @param pred A predicate.
721 * @return True if the check is true, false otherwise.
722 *
723 * Returns true if @p pred is true for each element in the range
724 * @p [first,last), and false otherwise.
725 */
731 /**
732 * @brief Checks that a predicate is false for all the elements
733 * of a sequence.
734 * @ingroup non_mutating_algorithms
735 * @param first An input iterator.
736 * @param last An input iterator.
737 * @param pred A predicate.
738 * @return True if the check is true, false otherwise.
739 *
740 * Returns true if @p pred is false for each element in the range
741 * @p [first,last), and false otherwise.
742 */
748 /**
749 * @brief Checks that a predicate is false for at least an element
750 * of a sequence.
751 * @ingroup non_mutating_algorithms
752 * @param first An input iterator.
753 * @param last An input iterator.
754 * @param pred A predicate.
755 * @return True if the check is true, false otherwise.
756 *
757 * Returns true if an element exists in the range @p [first,last) such that
758 * @p pred is true, and false otherwise.
759 */
765 /**
766 * @brief Find the first element in a sequence for which a
767 * predicate is false.
768 * @ingroup non_mutating_algorithms
769 * @param first An input iterator.
770 * @param last An input iterator.
771 * @param pred A predicate.
772 * @return The first iterator @c i in the range @p [first,last)
773 * such that @p pred(*i) is false, or @p last if no such iterator exists.
774 */
776 inline _InputIterator
778 _Predicate __pred)
779 {
780 // concept requirements
787 }
789 /**
790 * @brief Checks whether the sequence is partitioned.
791 * @ingroup mutating_algorithms
792 * @param first An input iterator.
793 * @param last An input iterator.
794 * @param pred A predicate.
795 * @return True if the range @p [first,last) is partioned by @p pred,
796 * i.e. if all elements that satisfy @p pred appear before those that
797 * do not.
798 */
802 _Predicate __pred)
803 {
806 }
808 /**
809 * @brief Find the partition point of a partitioned range.
810 * @ingroup mutating_algorithms
811 * @param first An iterator.
812 * @param last Another iterator.
813 * @param pred A predicate.
814 * @return An iterator @p mid such that @p all_of(first, mid, pred)
815 * and @p none_of(mid, last, pred) are both true.
816 */
818 _ForwardIterator
820 _Predicate __pred)
821 {
822 // concept requirements
827 // A specific debug-mode test will be necessary...
831 _DistanceType;
834 _DistanceType __half;
835 _ForwardIterator __middle;
838 {
843 {
847 }
848 else
850 }
852 }
853 #endif
856 /**
857 * @brief Copy a sequence, removing elements of a given value.
858 * @ingroup mutating_algorithms
859 * @param first An input iterator.
860 * @param last An input iterator.
861 * @param result An output iterator.
862 * @param value The value to be removed.
863 * @return An iterator designating the end of the resulting sequence.
864 *
865 * Copies each element in the range @p [first,last) not equal to @p value
866 * to the range beginning at @p result.
867 * remove_copy() is stable, so the relative order of elements that are
868 * copied is unchanged.
869 */
871 _OutputIterator
874 {
875 // concept requirements
885 {
888 }
890 }
892 /**
893 * @brief Copy a sequence, removing elements for which a predicate is true.
894 * @ingroup mutating_algorithms
895 * @param first An input iterator.
896 * @param last An input iterator.
897 * @param result An output iterator.
898 * @param pred A predicate.
899 * @return An iterator designating the end of the resulting sequence.
900 *
901 * Copies each element in the range @p [first,last) for which
902 * @p pred returns false to the range beginning at @p result.
903 *
904 * remove_copy_if() is stable, so the relative order of elements that are
905 * copied is unchanged.
906 */
908 typename _Predicate>
909 _OutputIterator
912 {
913 // concept requirements
923 {
926 }
928 }
930 #ifdef __GXX_EXPERIMENTAL_CXX0X__
931 /**
932 * @brief Copy the elements of a sequence for which a predicate is true.
933 * @ingroup mutating_algorithms
934 * @param first An input iterator.
935 * @param last An input iterator.
936 * @param result An output iterator.
937 * @param pred A predicate.
938 * @return An iterator designating the end of the resulting sequence.
939 *
940 * Copies each element in the range @p [first,last) for which
941 * @p pred returns true to the range beginning at @p result.
942 *
943 * copy_if() is stable, so the relative order of elements that are
944 * copied is unchanged.
945 */
947 typename _Predicate>
948 _OutputIterator
951 {
952 // concept requirements
962 {
965 }
967 }
971 _OutputIterator
974 {
976 {
980 }
982 }
985 typename _OutputIterator>
986 inline _OutputIterator
991 /**
992 * @brief Copies the range [first,first+n) into [result,result+n).
993 * @ingroup mutating_algorithms
994 * @param first An input iterator.
995 * @param n The number of elements to copy.
996 * @param result An output iterator.
997 * @return result+n.
998 *
999 * This inline function will boil down to a call to @c memmove whenever
1000 * possible. Failing that, if random access iterators are passed, then the
1001 * loop count will be known (and therefore a candidate for compiler
1002 * optimizations such as unrolling).
1003 */
1005 inline _OutputIterator
1007 {
1008 // concept requirements
1015 }
1017 /**
1018 * @brief Copy the elements of a sequence to separate output sequences
1019 * depending on the truth value of a predicate.
1020 * @ingroup mutating_algorithms
1021 * @param first An input iterator.
1022 * @param last An input iterator.
1023 * @param out_true An output iterator.
1024 * @param out_false An output iterator.
1025 * @param pred A predicate.
1026 * @return A pair designating the ends of the resulting sequences.
1027 *
1028 * Copies each element in the range @p [first,last) for which
1029 * @p pred returns true to the range beginning at @p out_true
1030 * and each element for which @p pred returns false to @p out_false.
1031 */
1037 _Predicate __pred)
1038 {
1039 // concept requirements
1051 {
1054 }
1055 else
1056 {
1059 }
1062 }
1063 #endif
1065 /**
1066 * @brief Remove elements from a sequence.
1067 * @ingroup mutating_algorithms
1068 * @param first An input iterator.
1069 * @param last An input iterator.
1070 * @param value The value to be removed.
1071 * @return An iterator designating the end of the resulting sequence.
1072 *
1073 * All elements equal to @p value are removed from the range
1074 * @p [first,last).
1075 *
1076 * remove() is stable, so the relative order of elements that are
1077 * not removed is unchanged.
1078 *
1079 * Elements between the end of the resulting sequence and @p last
1080 * are still present, but their value is unspecified.
1081 */
1083 _ForwardIterator
1086 {
1087 // concept requirements
1089 _ForwardIterator>)
1101 {
1104 }
1106 }
1108 /**
1109 * @brief Remove elements from a sequence using a predicate.
1110 * @ingroup mutating_algorithms
1111 * @param first A forward iterator.
1112 * @param last A forward iterator.
1113 * @param pred A predicate.
1114 * @return An iterator designating the end of the resulting sequence.
1115 *
1116 * All elements for which @p pred returns true are removed from the range
1117 * @p [first,last).
1118 *
1119 * remove_if() is stable, so the relative order of elements that are
1120 * not removed is unchanged.
1121 *
1122 * Elements between the end of the resulting sequence and @p last
1123 * are still present, but their value is unspecified.
1124 */
1126 _ForwardIterator
1128 _Predicate __pred)
1129 {
1130 // concept requirements
1132 _ForwardIterator>)
1144 {
1147 }
1149 }
1151 /**
1152 * @brief Remove consecutive duplicate values from a sequence.
1153 * @ingroup mutating_algorithms
1154 * @param first A forward iterator.
1155 * @param last A forward iterator.
1156 * @return An iterator designating the end of the resulting sequence.
1157 *
1158 * Removes all but the first element from each group of consecutive
1159 * values that compare equal.
1160 * unique() is stable, so the relative order of elements that are
1161 * not removed is unchanged.
1162 * Elements between the end of the resulting sequence and @p last
1163 * are still present, but their value is unspecified.
1164 */
1166 _ForwardIterator
1168 {
1169 // concept requirements
1171 _ForwardIterator>)
1176 // Skip the beginning, if already unique.
1181 // Do the real copy work.
1188 }
1190 /**
1191 * @brief Remove consecutive values from a sequence using a predicate.
1192 * @ingroup mutating_algorithms
1193 * @param first A forward iterator.
1194 * @param last A forward iterator.
1195 * @param binary_pred A binary predicate.
1196 * @return An iterator designating the end of the resulting sequence.
1197 *
1198 * Removes all but the first element from each group of consecutive
1199 * values for which @p binary_pred returns true.
1200 * unique() is stable, so the relative order of elements that are
1201 * not removed is unchanged.
1202 * Elements between the end of the resulting sequence and @p last
1203 * are still present, but their value is unspecified.
1204 */
1206 _ForwardIterator
1208 _BinaryPredicate __binary_pred)
1209 {
1210 // concept requirements
1212 _ForwardIterator>)
1218 // Skip the beginning, if already unique.
1223 // Do the real copy work.
1230 }
1232 /**
1233 * This is an uglified unique_copy(_InputIterator, _InputIterator,
1234 * _OutputIterator)
1235 * overloaded for forward iterators and output iterator as result.
1236 */
1238 _OutputIterator
1240 _OutputIterator __result,
1242 {
1243 // concept requirements -- taken care of in dispatching function
1248 {
1251 }
1253 }
1255 /**
1256 * This is an uglified unique_copy(_InputIterator, _InputIterator,
1257 * _OutputIterator)
1258 * overloaded for input iterators and output iterator as result.
1259 */
1261 _OutputIterator
1263 _OutputIterator __result,
1265 {
1266 // concept requirements -- taken care of in dispatching function
1271 {
1274 }
1276 }
1278 /**
1279 * This is an uglified unique_copy(_InputIterator, _InputIterator,
1280 * _OutputIterator)
1281 * overloaded for input iterators and forward iterator as result.
1282 */
1284 _ForwardIterator
1286 _ForwardIterator __result,
1288 {
1289 // concept requirements -- taken care of in dispatching function
1295 }
1297 /**
1298 * This is an uglified
1299 * unique_copy(_InputIterator, _InputIterator, _OutputIterator,
1300 * _BinaryPredicate)
1301 * overloaded for forward iterators and output iterator as result.
1302 */
1304 typename _BinaryPredicate>
1305 _OutputIterator
1309 {
1310 // concept requirements -- iterators already checked
1319 {
1322 }
1324 }
1326 /**
1327 * This is an uglified
1328 * unique_copy(_InputIterator, _InputIterator, _OutputIterator,
1329 * _BinaryPredicate)
1330 * overloaded for input iterators and output iterator as result.
1331 */
1333 typename _BinaryPredicate>
1334 _OutputIterator
1338 {
1339 // concept requirements -- iterators already checked
1348 {
1351 }
1353 }
1355 /**
1356 * This is an uglified
1357 * unique_copy(_InputIterator, _InputIterator, _OutputIterator,
1358 * _BinaryPredicate)
1359 * overloaded for input iterators and forward iterator as result.
1360 */
1362 typename _BinaryPredicate>
1363 _ForwardIterator
1367 {
1368 // concept requirements -- iterators already checked
1378 }
1380 /**
1381 * This is an uglified reverse(_BidirectionalIterator,
1382 * _BidirectionalIterator)
1383 * overloaded for bidirectional iterators.
1384 */
1386 void
1388 bidirectional_iterator_tag)
1389 {
1393 else
1394 {
1397 }
1398 }
1400 /**
1401 * This is an uglified reverse(_BidirectionalIterator,
1402 * _BidirectionalIterator)
1403 * overloaded for random access iterators.
1404 */
1406 void
1408 random_access_iterator_tag)
1409 {
1414 {
1418 }
1419 }
1421 /**
1422 * @brief Reverse a sequence.
1423 * @ingroup mutating_algorithms
1424 * @param first A bidirectional iterator.
1425 * @param last A bidirectional iterator.
1426 * @return reverse() returns no value.
1427 *
1428 * Reverses the order of the elements in the range @p [first,last),
1429 * so that the first element becomes the last etc.
1430 * For every @c i such that @p 0<=i<=(last-first)/2), @p reverse()
1431 * swaps @p *(first+i) and @p *(last-(i+1))
1432 */
1436 {
1437 // concept requirements
1439 _BidirectionalIterator>)
1442 }
1444 /**
1445 * @brief Copy a sequence, reversing its elements.
1446 * @ingroup mutating_algorithms
1447 * @param first A bidirectional iterator.
1448 * @param last A bidirectional iterator.
1449 * @param result An output iterator.
1450 * @return An iterator designating the end of the resulting sequence.
1451 *
1452 * Copies the elements in the range @p [first,last) to the range
1453 * @p [result,result+(last-first)) such that the order of the
1454 * elements is reversed.
1455 * For every @c i such that @p 0<=i<=(last-first), @p reverse_copy()
1456 * performs the assignment @p *(result+(last-first)-i) = *(first+i).
1457 * The ranges @p [first,last) and @p [result,result+(last-first))
1458 * must not overlap.
1459 */
1461 _OutputIterator
1463 _OutputIterator __result)
1464 {
1465 // concept requirements
1467 _BidirectionalIterator>)
1473 {
1477 }
1479 }
1481 /**
1482 * This is a helper function for the rotate algorithm specialized on RAIs.
1483 * It returns the greatest common divisor of two integer values.
1484 */
1486 _EuclideanRingElement
1488 {
1490 {
1494 }
1496 }
1498 /// This is a helper function for the rotate algorithm.
1500 void
1502 _ForwardIterator __middle,
1503 _ForwardIterator __last,
1504 forward_iterator_tag)
1505 {
1510 do
1511 {
1517 }
1523 {
1531 }
1532 }
1534 /// This is a helper function for the rotate algorithm.
1536 void
1538 _BidirectionalIterator __middle,
1539 _BidirectionalIterator __last,
1540 bidirectional_iterator_tag)
1541 {
1542 // concept requirements
1544 _BidirectionalIterator>)
1553 {
1556 }
1560 else
1562 }
1564 /// This is a helper function for the rotate algorithm.
1566 void
1568 _RandomAccessIterator __middle,
1569 _RandomAccessIterator __last,
1570 random_access_iterator_tag)
1571 {
1572 // concept requirements
1574 _RandomAccessIterator>)
1580 _Distance;
1582 _ValueType;
1588 {
1591 }
1596 {
1598 {
1600 {
1605 }
1608 {
1612 }
1618 }
1619 else
1620 {
1623 {
1628 }
1632 {
1636 }
1641 }
1642 }
1643 }
1645 /**
1646 * @brief Rotate the elements of a sequence.
1647 * @ingroup mutating_algorithms
1648 * @param first A forward iterator.
1649 * @param middle A forward iterator.
1650 * @param last A forward iterator.
1651 * @return Nothing.
1652 *
1653 * Rotates the elements of the range @p [first,last) by @p (middle-first)
1654 * positions so that the element at @p middle is moved to @p first, the
1655 * element at @p middle+1 is moved to @first+1 and so on for each element
1656 * in the range @p [first,last).
1657 *
1658 * This effectively swaps the ranges @p [first,middle) and
1659 * @p [middle,last).
1660 *
1661 * Performs @p *(first+(n+(last-middle))%(last-first))=*(first+n) for
1662 * each @p n in the range @p [0,last-first).
1663 */
1667 _ForwardIterator __last)
1668 {
1669 // concept requirements
1671 _ForwardIterator>)
1676 _IterType;
1678 }
1680 /**
1681 * @brief Copy a sequence, rotating its elements.
1682 * @ingroup mutating_algorithms
1683 * @param first A forward iterator.
1684 * @param middle A forward iterator.
1685 * @param last A forward iterator.
1686 * @param result An output iterator.
1687 * @return An iterator designating the end of the resulting sequence.
1688 *
1689 * Copies the elements of the range @p [first,last) to the range
1690 * beginning at @result, rotating the copied elements by @p (middle-first)
1691 * positions so that the element at @p middle is moved to @p result, the
1692 * element at @p middle+1 is moved to @result+1 and so on for each element
1693 * in the range @p [first,last).
1694 *
1695 * Performs @p *(result+(n+(last-middle))%(last-first))=*(first+n) for
1696 * each @p n in the range @p [0,last-first).
1697 */
1699 _OutputIterator
1702 {
1703 // concept requirements
1712 }
1714 /// This is a helper function...
1716 _ForwardIterator
1719 {
1731 {
1734 }
1737 }
1739 /// This is a helper function...
1741 _BidirectionalIterator
1744 {
1746 {
1752 else
1760 else
1764 }
1765 }
1767 // partition
1769 /// This is a helper function...
1771 _ForwardIterator
1773 _ForwardIterator __last,
1775 {
1781 __middle,
1782 __pred,
1785 __pred,
1786 __len
1791 }
1793 /// This is a helper function...
1795 typename _Distance>
1796 _ForwardIterator
1798 _ForwardIterator __last,
1800 _Pointer __buffer,
1801 _Distance __buffer_size)
1802 {
1804 {
1809 {
1812 }
1813 else
1814 {
1817 }
1820 }
1821 else
1822 {
1825 _ForwardIterator __begin =
1828 __buffer_size);
1829 _ForwardIterator __end =
1836 }
1837 }
1839 /**
1840 * @brief Move elements for which a predicate is true to the beginning
1841 * of a sequence, preserving relative ordering.
1842 * @ingroup mutating_algorithms
1843 * @param first A forward iterator.
1844 * @param last A forward iterator.
1845 * @param pred A predicate functor.
1846 * @return An iterator @p middle such that @p pred(i) is true for each
1847 * iterator @p i in the range @p [first,middle) and false for each @p i
1848 * in the range @p [middle,last).
1849 *
1850 * Performs the same function as @p partition() with the additional
1851 * guarantee that the relative ordering of elements in each group is
1852 * preserved, so any two elements @p x and @p y in the range
1853 * @p [first,last) such that @p pred(x)==pred(y) will have the same
1854 * relative ordering after calling @p stable_partition().
1855 */
1857 _ForwardIterator
1859 _Predicate __pred)
1860 {
1861 // concept requirements
1863 _ForwardIterator>)
1870 else
1871 {
1873 _ValueType;
1875 _DistanceType;
1878 __last);
1880 return
1885 else
1886 return
1889 }
1890 }
1892 /// This is a helper function for the sort routines.
1894 void
1896 _RandomAccessIterator __middle,
1897 _RandomAccessIterator __last)
1898 {
1903 }
1905 /// This is a helper function for the sort routines.
1907 void
1909 _RandomAccessIterator __middle,
1911 {
1916 }
1918 // partial_sort
1920 /**
1921 * @brief Copy the smallest elements of a sequence.
1922 * @ingroup sorting_algorithms
1923 * @param first An iterator.
1924 * @param last Another iterator.
1925 * @param result_first A random-access iterator.
1926 * @param result_last Another random-access iterator.
1927 * @return An iterator indicating the end of the resulting sequence.
1928 *
1929 * Copies and sorts the smallest N values from the range @p [first,last)
1930 * to the range beginning at @p result_first, where the number of
1931 * elements to be copied, @p N, is the smaller of @p (last-first) and
1932 * @p (result_last-result_first).
1933 * After the sort if @p i and @j are iterators in the range
1934 * @p [result_first,result_first+N) such that @i precedes @j then
1935 * @p *j<*i is false.
1936 * The value returned is @p result_first+N.
1937 */
1939 _RandomAccessIterator
1941 _RandomAccessIterator __result_first,
1942 _RandomAccessIterator __result_last)
1943 {
1945 _InputValueType;
1947 _OutputValueType;
1949 _DistanceType;
1951 // concept requirements
1954 _OutputValueType>)
1956 _OutputValueType>)
1965 {
1969 }
1972 {
1979 }
1982 }
1984 /**
1985 * @brief Copy the smallest elements of a sequence using a predicate for
1986 * comparison.
1987 * @ingroup sorting_algorithms
1988 * @param first An input iterator.
1989 * @param last Another input iterator.
1990 * @param result_first A random-access iterator.
1991 * @param result_last Another random-access iterator.
1992 * @param comp A comparison functor.
1993 * @return An iterator indicating the end of the resulting sequence.
1994 *
1995 * Copies and sorts the smallest N values from the range @p [first,last)
1996 * to the range beginning at @p result_first, where the number of
1997 * elements to be copied, @p N, is the smaller of @p (last-first) and
1998 * @p (result_last-result_first).
1999 * After the sort if @p i and @j are iterators in the range
2000 * @p [result_first,result_first+N) such that @i precedes @j then
2001 * @p comp(*j,*i) is false.
2002 * The value returned is @p result_first+N.
2003 */
2005 _RandomAccessIterator
2007 _RandomAccessIterator __result_first,
2008 _RandomAccessIterator __result_last,
2009 _Compare __comp)
2010 {
2012 _InputValueType;
2014 _OutputValueType;
2016 _DistanceType;
2018 // concept requirements
2021 _RandomAccessIterator>)
2023 _OutputValueType>)
2035 {
2039 }
2042 {
2048 __comp);
2050 }
2053 }
2055 /// This is a helper function for the sort routine.
2057 void
2059 {
2065 {
2069 }
2071 }
2073 /// This is a helper function for the sort routine.
2075 void
2077 _Compare __comp)
2078 {
2084 {
2088 }
2090 }
2092 /// This is a helper function for the sort routine.
2094 void
2096 _RandomAccessIterator __last)
2097 {
2102 {
2104 {
2109 }
2110 else
2112 }
2113 }
2115 /// This is a helper function for the sort routine.
2117 void
2120 {
2124 {
2126 {
2131 }
2132 else
2134 }
2135 }
2137 /// This is a helper function for the sort routine.
2141 _RandomAccessIterator __last)
2142 {
2144 _ValueType;
2148 }
2150 /// This is a helper function for the sort routine.
2155 {
2157 _ValueType;
2161 }
2163 /**
2164 * @doctodo
2165 * This controls some aspect of the sort routines.
2166 */
2169 /// This is a helper function for the sort routine.
2171 void
2173 _RandomAccessIterator __last)
2174 {
2176 {
2179 }
2180 else
2182 }
2184 /// This is a helper function for the sort routine.
2186 void
2189 {
2191 {
2194 __comp);
2195 }
2196 else
2198 }
2200 /// This is a helper function...
2202 _RandomAccessIterator
2205 {
2207 {
2217 }
2218 }
2220 /// This is a helper function...
2222 _RandomAccessIterator
2224 _RandomAccessIterator __last,
2226 {
2228 {
2238 }
2239 }
2241 /// This is a helper function...
2243 inline _RandomAccessIterator
2245 _RandomAccessIterator __last)
2246 {
2250 }
2253 /// This is a helper function...
2255 inline _RandomAccessIterator
2258 {
2262 }
2264 /// This is a helper function for the sort routine.
2266 void
2268 _RandomAccessIterator __last,
2269 _Size __depth_limit)
2270 {
2272 {
2274 {
2277 }
2279 _RandomAccessIterator __cut =
2283 }
2284 }
2286 /// This is a helper function for the sort routine.
2288 void
2290 _RandomAccessIterator __last,
2292 {
2294 {
2296 {
2299 }
2301 _RandomAccessIterator __cut =
2305 }
2306 }
2308 // sort
2311 void
2314 {
2316 _ValueType;
2319 {
2321 {
2324 // Place the nth largest element in its final position.
2327 }
2329 _RandomAccessIterator __cut =
2333 else
2335 }
2337 }
2340 void
2343 _Compare __comp)
2344 {
2346 _ValueType;
2349 {
2351 {
2353 // Place the nth largest element in its final position.
2356 }
2358 _RandomAccessIterator __cut =
2362 else
2364 }
2366 }
2368 // nth_element
2370 // lower_bound moved to stl_algobase.h
2372 /**
2373 * @brief Finds the first position in which @a val could be inserted
2374 * without changing the ordering.
2375 * @ingroup binary_search_algorithms
2376 * @param first An iterator.
2377 * @param last Another iterator.
2378 * @param val The search term.
2379 * @param comp A functor to use for comparisons.
2380 * @return An iterator pointing to the first element <em>not less
2381 * than</em> @a val, or end() if every element is less
2382 * than @a val.
2383 * @ingroup binary_search_algorithms
2384 *
2385 * The comparison function should have the same effects on ordering as
2386 * the function used for the initial sort.
2387 */
2389 _ForwardIterator
2392 {
2394 _ValueType;
2396 _DistanceType;
2398 // concept requirements
2408 {
2413 {
2417 }
2418 else
2420 }
2422 }
2424 /**
2425 * @brief Finds the last position in which @a val could be inserted
2426 * without changing the ordering.
2427 * @ingroup binary_search_algorithms
2428 * @param first An iterator.
2429 * @param last Another iterator.
2430 * @param val The search term.
2431 * @return An iterator pointing to the first element greater than @a val,
2432 * or end() if no elements are greater than @a val.
2433 * @ingroup binary_search_algorithms
2434 */
2436 _ForwardIterator
2439 {
2441 _ValueType;
2443 _DistanceType;
2445 // concept requirements
2453 {
2459 else
2460 {
2464 }
2465 }
2467 }
2469 /**
2470 * @brief Finds the last position in which @a val could be inserted
2471 * without changing the ordering.
2472 * @ingroup binary_search_algorithms
2473 * @param first An iterator.
2474 * @param last Another iterator.
2475 * @param val The search term.
2476 * @param comp A functor to use for comparisons.
2477 * @return An iterator pointing to the first element greater than @a val,
2478 * or end() if no elements are greater than @a val.
2479 * @ingroup binary_search_algorithms
2480 *
2481 * The comparison function should have the same effects on ordering as
2482 * the function used for the initial sort.
2483 */
2485 _ForwardIterator
2488 {
2490 _ValueType;
2492 _DistanceType;
2494 // concept requirements
2504 {
2510 else
2511 {
2515 }
2516 }
2518 }
2520 /**
2521 * @brief Finds the largest subrange in which @a val could be inserted
2522 * at any place in it without changing the ordering.
2523 * @ingroup binary_search_algorithms
2524 * @param first An iterator.
2525 * @param last Another iterator.
2526 * @param val The search term.
2527 * @return An pair of iterators defining the subrange.
2528 * @ingroup binary_search_algorithms
2529 *
2530 * This is equivalent to
2531 * @code
2532 * std::make_pair(lower_bound(first, last, val),
2533 * upper_bound(first, last, val))
2534 * @endcode
2535 * but does not actually call those functions.
2536 */
2541 {
2543 _ValueType;
2545 _DistanceType;
2547 // concept requirements
2557 {
2562 {
2566 }
2569 else
2570 {
2572 __val);
2575 __val);
2577 }
2578 }
2580 }
2582 /**
2583 * @brief Finds the largest subrange in which @a val could be inserted
2584 * at any place in it without changing the ordering.
2585 * @param first An iterator.
2586 * @param last Another iterator.
2587 * @param val The search term.
2588 * @param comp A functor to use for comparisons.
2589 * @return An pair of iterators defining the subrange.
2590 * @ingroup binary_search_algorithms
2591 *
2592 * This is equivalent to
2593 * @code
2594 * std::make_pair(lower_bound(first, last, val, comp),
2595 * upper_bound(first, last, val, comp))
2596 * @endcode
2597 * but does not actually call those functions.
2598 */
2603 {
2605 _ValueType;
2607 _DistanceType;
2609 // concept requirements
2623 {
2628 {
2632 }
2635 else
2636 {
2643 }
2644 }
2646 }
2648 /**
2649 * @brief Determines whether an element exists in a range.
2650 * @ingroup binary_search_algorithms
2651 * @param first An iterator.
2652 * @param last Another iterator.
2653 * @param val The search term.
2654 * @return True if @a val (or its equivalent) is in [@a first,@a last ].
2655 *
2656 * Note that this does not actually return an iterator to @a val. For
2657 * that, use std::find or a container's specialized find member functions.
2658 */
2660 bool
2663 {
2665 _ValueType;
2667 // concept requirements
2675 }
2677 /**
2678 * @brief Determines whether an element exists in a range.
2679 * @ingroup binary_search_algorithms
2680 * @param first An iterator.
2681 * @param last Another iterator.
2682 * @param val The search term.
2683 * @param comp A functor to use for comparisons.
2684 * @return True if @a val (or its equivalent) is in [@a first,@a last ].
2685 *
2686 * Note that this does not actually return an iterator to @a val. For
2687 * that, use std::find or a container's specialized find member functions.
2688 *
2689 * The comparison function should have the same effects on ordering as
2690 * the function used for the initial sort.
2691 */
2693 bool
2696 {
2698 _ValueType;
2700 // concept requirements
2711 }
2713 // merge
2715 /// This is a helper function for the merge routines.
2717 typename _BidirectionalIterator3>
2718 _BidirectionalIterator3
2720 _BidirectionalIterator1 __last1,
2721 _BidirectionalIterator2 __first2,
2722 _BidirectionalIterator2 __last2,
2723 _BidirectionalIterator3 __result)
2724 {
2732 {
2734 {
2739 }
2740 else
2741 {
2746 }
2747 }
2748 }
2750 /// This is a helper function for the merge routines.
2753 _BidirectionalIterator3
2755 _BidirectionalIterator1 __last1,
2756 _BidirectionalIterator2 __first2,
2757 _BidirectionalIterator2 __last2,
2758 _BidirectionalIterator3 __result,
2759 _Compare __comp)
2760 {
2768 {
2770 {
2775 }
2776 else
2777 {
2782 }
2783 }
2784 }
2786 /// This is a helper function for the merge routines.
2788 typename _Distance>
2789 _BidirectionalIterator1
2791 _BidirectionalIterator1 __middle,
2792 _BidirectionalIterator1 __last,
2794 _BidirectionalIterator2 __buffer,
2795 _Distance __buffer_size)
2796 {
2797 _BidirectionalIterator2 __buffer_end;
2799 {
2803 }
2805 {
2809 }
2810 else
2811 {
2815 }
2816 }
2818 /// This is a helper function for the merge routines.
2820 typename _Pointer>
2821 void
2823 _BidirectionalIterator __middle,
2824 _BidirectionalIterator __last,
2827 {
2829 {
2835 __first);
2836 }
2838 {
2844 __last);
2845 }
2846 else
2847 {
2853 {
2859 }
2860 else
2861 {
2867 }
2868 _BidirectionalIterator __new_middle =
2871 __buffer_size);
2877 }
2878 }
2880 /// This is a helper function for the merge routines.
2883 void
2885 _BidirectionalIterator __middle,
2886 _BidirectionalIterator __last,
2889 _Compare __comp)
2890 {
2892 {
2899 }
2901 {
2908 }
2909 else
2910 {
2916 {
2920 __comp);
2922 }
2923 else
2924 {
2928 __comp);
2930 }
2931 _BidirectionalIterator __new_middle =
2934 __buffer_size);
2941 }
2942 }
2944 /// This is a helper function for the merge routines.
2946 void
2948 _BidirectionalIterator __middle,
2949 _BidirectionalIterator __last,
2951 {
2955 {
2959 }
2965 {
2970 }
2971 else
2972 {
2977 }
2985 }
2987 /// This is a helper function for the merge routines.
2989 typename _Compare>
2990 void
2992 _BidirectionalIterator __middle,
2993 _BidirectionalIterator __last,
2995 _Compare __comp)
2996 {
3000 {
3004 }
3010 {
3014 __comp);
3016 }
3017 else
3018 {
3022 __comp);
3024 }
3032 }
3034 /**
3035 * @brief Merges two sorted ranges in place.
3036 * @ingroup sorting_algorithms
3037 * @param first An iterator.
3038 * @param middle Another iterator.
3039 * @param last Another iterator.
3040 * @return Nothing.
3041 *
3042 * Merges two sorted and consecutive ranges, [first,middle) and
3043 * [middle,last), and puts the result in [first,last). The output will
3044 * be sorted. The sort is @e stable, that is, for equivalent
3045 * elements in the two ranges, elements from the first range will always
3046 * come before elements from the second.
3047 *
3048 * If enough additional memory is available, this takes (last-first)-1
3049 * comparisons. Otherwise an NlogN algorithm is used, where N is
3050 * distance(first,last).
3051 */
3053 void
3055 _BidirectionalIterator __middle,
3056 _BidirectionalIterator __last)
3057 {
3059 _ValueType;
3061 _DistanceType;
3063 // concept requirements
3065 _BidirectionalIterator>)
3077 __last);
3080 else
3083 }
3085 /**
3086 * @brief Merges two sorted ranges in place.
3087 * @ingroup sorting_algorithms
3088 * @param first An iterator.
3089 * @param middle Another iterator.
3090 * @param last Another iterator.
3091 * @param comp A functor to use for comparisons.
3092 * @return Nothing.
3093 *
3094 * Merges two sorted and consecutive ranges, [first,middle) and
3095 * [middle,last), and puts the result in [first,last). The output will
3096 * be sorted. The sort is @e stable, that is, for equivalent
3097 * elements in the two ranges, elements from the first range will always
3098 * come before elements from the second.
3099 *
3100 * If enough additional memory is available, this takes (last-first)-1
3101 * comparisons. Otherwise an NlogN algorithm is used, where N is
3102 * distance(first,last).
3103 *
3104 * The comparison function should have the same effects on ordering as
3105 * the function used for the initial sort.
3106 */
3108 void
3110 _BidirectionalIterator __middle,
3111 _BidirectionalIterator __last,
3112 _Compare __comp)
3113 {
3115 _ValueType;
3117 _DistanceType;
3119 // concept requirements
3121 _BidirectionalIterator>)
3134 __last);
3138 else
3141 __comp);
3142 }
3145 typename _Distance>
3146 void
3148 _RandomAccessIterator1 __last,
3149 _RandomAccessIterator2 __result,
3150 _Distance __step_size)
3151 {
3155 {
3161 __result);
3163 }
3168 __step_size),
3170 __step_size),
3172 __result);
3173 }
3177 void
3179 _RandomAccessIterator1 __last,
3181 _Compare __comp)
3182 {
3186 {
3194 }
3199 __step_size),
3201 __step_size),
3204 }
3207 void
3209 _RandomAccessIterator __last,
3210 _Distance __chunk_size)
3211 {
3213 {
3216 }
3218 }
3221 typename _Compare>
3222 void
3224 _RandomAccessIterator __last,
3226 {
3228 {
3231 }
3233 }
3238 void
3240 _RandomAccessIterator __last,
3241 _Pointer __buffer)
3242 {
3244 _Distance;
3253 {
3258 }
3259 }
3262 void
3264 _RandomAccessIterator __last,
3266 {
3268 _Distance;
3277 {
3284 }
3285 }
3288 typename _Distance>
3289 void
3291 _RandomAccessIterator __last,
3293 {
3297 {
3302 }
3303 else
3304 {
3307 }
3312 }
3316 void
3318 _RandomAccessIterator __last,
3320 _Compare __comp)
3321 {
3325 {
3330 }
3331 else
3332 {
3335 }
3340 __comp);
3341 }
3343 /// This is a helper function for the stable sorting routines.
3345 void
3347 _RandomAccessIterator __last)
3348 {
3350 {
3353 }
3360 }
3362 /// This is a helper function for the stable sorting routines.
3364 void
3367 {
3369 {
3372 }
3379 __comp);
3380 }
3382 // stable_sort
3384 // Set algorithms: includes, set_union, set_intersection, set_difference,
3385 // set_symmetric_difference. All of these algorithms have the precondition
3386 // that their input ranges are sorted and the postcondition that their output
3387 // ranges are sorted.
3389 /**
3390 * @brief Determines whether all elements of a sequence exists in a range.
3391 * @param first1 Start of search range.
3392 * @param last1 End of search range.
3393 * @param first2 Start of sequence
3394 * @param last2 End of sequence.
3395 * @return True if each element in [first2,last2) is contained in order
3396 * within [first1,last1). False otherwise.
3397 * @ingroup set_algorithms
3398 *
3399 * This operation expects both [first1,last1) and [first2,last2) to be
3400 * sorted. Searches for the presence of each element in [first2,last2)
3401 * within [first1,last1). The iterators over each range only move forward,
3402 * so this is a linear algorithm. If an element in [first2,last2) is not
3403 * found before the search iterator reaches @a last2, false is returned.
3404 */
3406 bool
3409 {
3411 _ValueType1;
3413 _ValueType2;
3415 // concept requirements
3428 else
3432 }
3434 /**
3435 * @brief Determines whether all elements of a sequence exists in a range
3436 * using comparison.
3437 * @ingroup set_algorithms
3438 * @param first1 Start of search range.
3439 * @param last1 End of search range.
3440 * @param first2 Start of sequence
3441 * @param last2 End of sequence.
3442 * @param comp Comparison function to use.
3443 * @return True if each element in [first2,last2) is contained in order
3444 * within [first1,last1) according to comp. False otherwise.
3445 * @ingroup set_algorithms
3446 *
3447 * This operation expects both [first1,last1) and [first2,last2) to be
3448 * sorted. Searches for the presence of each element in [first2,last2)
3449 * within [first1,last1), using comp to decide. The iterators over each
3450 * range only move forward, so this is a linear algorithm. If an element
3451 * in [first2,last2) is not found before the search iterator reaches @a
3452 * last2, false is returned.
3453 */
3455 typename _Compare>
3456 bool
3459 _Compare __comp)
3460 {
3462 _ValueType1;
3464 _ValueType2;
3466 // concept requirements
3481 else
3485 }
3487 // nth_element
3488 // merge
3489 // set_difference
3490 // set_intersection
3491 // set_union
3492 // stable_sort
3493 // set_symmetric_difference
3494 // min_element
3495 // max_element
3497 /**
3498 * @brief Permute range into the next @a dictionary ordering.
3499 * @ingroup sorting_algorithms
3500 * @param first Start of range.
3501 * @param last End of range.
3502 * @return False if wrapped to first permutation, true otherwise.
3503 *
3504 * Treats all permutations of the range as a set of @a dictionary sorted
3505 * sequences. Permutes the current sequence into the next one of this set.
3506 * Returns true if there are more sequences to generate. If the sequence
3507 * is the largest of the set, the smallest is generated and false returned.
3508 */
3510 bool
3512 _BidirectionalIterator __last)
3513 {
3514 // concept requirements
3516 _BidirectionalIterator>)
3531 {
3535 {
3538 {}
3542 }
3544 {
3547 }
3548 }
3549 }
3551 /**
3552 * @brief Permute range into the next @a dictionary ordering using
3553 * comparison functor.
3554 * @ingroup sorting_algorithms
3555 * @param first Start of range.
3556 * @param last End of range.
3557 * @param comp A comparison functor.
3558 * @return False if wrapped to first permutation, true otherwise.
3559 *
3560 * Treats all permutations of the range [first,last) as a set of
3561 * @a dictionary sorted sequences ordered by @a comp. Permutes the current
3562 * sequence into the next one of this set. Returns true if there are more
3563 * sequences to generate. If the sequence is the largest of the set, the
3564 * smallest is generated and false returned.
3565 */
3567 bool
3570 {
3571 // concept requirements
3573 _BidirectionalIterator>)
3589 {
3593 {
3596 {}
3600 }
3602 {
3605 }
3606 }
3607 }
3609 /**
3610 * @brief Permute range into the previous @a dictionary ordering.
3611 * @ingroup sorting_algorithms
3612 * @param first Start of range.
3613 * @param last End of range.
3614 * @return False if wrapped to last permutation, true otherwise.
3615 *
3616 * Treats all permutations of the range as a set of @a dictionary sorted
3617 * sequences. Permutes the current sequence into the previous one of this
3618 * set. Returns true if there are more sequences to generate. If the
3619 * sequence is the smallest of the set, the largest is generated and false
3620 * returned.
3621 */
3623 bool
3625 _BidirectionalIterator __last)
3626 {
3627 // concept requirements
3629 _BidirectionalIterator>)
3644 {
3648 {
3651 {}
3655 }
3657 {
3660 }
3661 }
3662 }
3664 /**
3665 * @brief Permute range into the previous @a dictionary ordering using
3666 * comparison functor.
3667 * @ingroup sorting_algorithms
3668 * @param first Start of range.
3669 * @param last End of range.
3670 * @param comp A comparison functor.
3671 * @return False if wrapped to last permutation, true otherwise.
3672 *
3673 * Treats all permutations of the range [first,last) as a set of
3674 * @a dictionary sorted sequences ordered by @a comp. Permutes the current
3675 * sequence into the previous one of this set. Returns true if there are
3676 * more sequences to generate. If the sequence is the smallest of the set,
3677 * the largest is generated and false returned.
3678 */
3680 bool
3683 {
3684 // concept requirements
3686 _BidirectionalIterator>)
3702 {
3706 {
3709 {}
3713 }
3715 {
3718 }
3719 }
3720 }
3722 // replace
3723 // replace_if
3725 /**
3726 * @brief Copy a sequence, replacing each element of one value with another
3727 * value.
3728 * @param first An input iterator.
3729 * @param last An input iterator.
3730 * @param result An output iterator.
3731 * @param old_value The value to be replaced.
3732 * @param new_value The replacement value.
3733 * @return The end of the output sequence, @p result+(last-first).
3734 *
3735 * Copies each element in the input range @p [first,last) to the
3736 * output range @p [result,result+(last-first)) replacing elements
3737 * equal to @p old_value with @p new_value.
3738 */
3740 _OutputIterator
3742 _OutputIterator __result,
3744 {
3745 // concept requirements
3756 else
3759 }
3761 /**
3762 * @brief Copy a sequence, replacing each value for which a predicate
3763 * returns true with another value.
3764 * @ingroup mutating_algorithms
3765 * @param first An input iterator.
3766 * @param last An input iterator.
3767 * @param result An output iterator.
3768 * @param pred A predicate.
3769 * @param new_value The replacement value.
3770 * @return The end of the output sequence, @p result+(last-first).
3771 *
3772 * Copies each element in the range @p [first,last) to the range
3773 * @p [result,result+(last-first)) replacing elements for which
3774 * @p pred returns true with @p new_value.
3775 */
3778 _OutputIterator
3780 _OutputIterator __result,
3782 {
3783 // concept requirements
3794 else
3797 }
3799 #ifdef __GXX_EXPERIMENTAL_CXX0X__
3800 /**
3801 * @brief Determines whether the elements of a sequence are sorted.
3802 * @ingroup sorting_algorithms
3803 * @param first An iterator.
3804 * @param last Another iterator.
3805 * @return True if the elements are sorted, false otherwise.
3806 */
3812 /**
3813 * @brief Determines whether the elements of a sequence are sorted
3814 * according to a comparison functor.
3815 * @ingroup sorting_algorithms
3816 * @param first An iterator.
3817 * @param last Another iterator.
3818 * @param comp A comparison functor.
3819 * @return True if the elements are sorted, false otherwise.
3820 */
3824 _Compare __comp)
3827 /**
3828 * @brief Determines the end of a sorted sequence.
3829 * @ingroup sorting_algorithms
3830 * @param first An iterator.
3831 * @param last Another iterator.
3832 * @return An iterator pointing to the last iterator i in [first, last)
3833 * for which the range [first, i) is sorted.
3834 */
3836 _ForwardIterator
3838 {
3839 // concept requirements
3853 }
3855 /**
3856 * @brief Determines the end of a sorted sequence using comparison functor.
3857 * @ingroup sorting_algorithms
3858 * @param first An iterator.
3859 * @param last Another iterator.
3860 * @param comp A comparison functor.
3861 * @return An iterator pointing to the last iterator i in [first, last)
3862 * for which the range [first, i) is sorted.
3863 */
3865 _ForwardIterator
3867 _Compare __comp)
3868 {
3869 // concept requirements
3884 }
3886 /**
3887 * @brief Determines min and max at once as an ordered pair.
3888 * @ingroup sorting_algorithms
3889 * @param a A thing of arbitrary type.
3890 * @param b Another thing of arbitrary type.
3891 * @return A pair(b, a) if b is smaller than a, pair(a, b) otherwise.
3892 */
3896 {
3897 // concept requirements
3902 }
3904 /**
3905 * @brief Determines min and max at once as an ordered pair.
3906 * @ingroup sorting_algorithms
3907 * @param a A thing of arbitrary type.
3908 * @param b Another thing of arbitrary type.
3909 * @param comp A @link comparison_functor comparison functor@endlink.
3910 * @return A pair(b, a) if b is smaller than a, pair(a, b) otherwise.
3911 */
3915 {
3918 }
3920 /**
3921 * @brief Return a pair of iterators pointing to the minimum and maximum
3922 * elements in a range.
3923 * @ingroup sorting_algorithms
3924 * @param first Start of range.
3925 * @param last End of range.
3926 * @return make_pair(m, M), where m is the first iterator i in
3927 * [first, last) such that no other element in the range is
3928 * smaller, and where M is the last iterator i in [first, last)
3929 * such that no other element in the range is larger.
3930 */
3934 {
3935 // concept requirements
3948 {
3951 }
3952 else
3953 {
3956 }
3962 {
3965 {
3971 }
3974 {
3979 }
3980 else
3981 {
3986 }
3990 }
3993 }
3995 /**
3996 * @brief Return a pair of iterators pointing to the minimum and maximum
3997 * elements in a range.
3998 * @ingroup sorting_algorithms
3999 * @param first Start of range.
4000 * @param last End of range.
4001 * @param comp Comparison functor.
4002 * @return make_pair(m, M), where m is the first iterator i in
4003 * [first, last) such that no other element in the range is
4004 * smaller, and where M is the last iterator i in [first, last)
4005 * such that no other element in the range is larger.
4006 */
4010 _Compare __comp)
4011 {
4012 // concept requirements
4026 {
4029 }
4030 else
4031 {
4034 }
4040 {
4043 {
4049 }
4052 {
4057 }
4058 else
4059 {
4064 }
4068 }
4071 }
4073 // N2722 + DR 915.
4075 inline _Tp
4080 inline _Tp
4085 inline _Tp
4090 inline _Tp
4097 {
4101 }
4106 {
4110 }
4112 #ifdef _GLIBCXX_USE_C99_STDINT_TR1
4113 /**
4114 * @brief Shuffle the elements of a sequence using a uniform random
4115 * number generator.
4116 * @ingroup mutating_algorithms
4117 * @param first A forward iterator.
4118 * @param last A forward iterator.
4119 * @param g A UniformRandomNumberGenerator (26.5.1.3).
4120 * @return Nothing.
4121 *
4122 * Reorders the elements in the range @p [first,last) using @p g to
4123 * provide random numbers.
4124 */
4126 typename _UniformRandomNumberGenerator>
4127 void
4130 {
4131 // concept requirements
4133 _RandomAccessIterator>)
4140 _DistanceType;
4145 __distr_type __d;
4149 }
4150 #endif
4154 _GLIBCXX_END_NAMESPACE
4158 /**
4159 * @brief Apply a function to every element of a sequence.
4160 * @ingroup non_mutating_algorithms
4161 * @param first An input iterator.
4162 * @param last An input iterator.
4163 * @param f A unary function object.
4164 * @return @p f (std::move(@p f) in C++0x).
4165 *
4166 * Applies the function object @p f to each element in the range
4167 * @p [first,last). @p f must not modify the order of the sequence.
4168 * If @p f has a return value it is ignored.
4169 */
4171 _Function
4173 {
4174 // concept requirements
4180 }
4182 /**
4183 * @brief Find the first occurrence of a value in a sequence.
4184 * @ingroup non_mutating_algorithms
4185 * @param first An input iterator.
4186 * @param last An input iterator.
4187 * @param val The value to find.
4188 * @return The first iterator @c i in the range @p [first,last)
4189 * such that @c *i == @p val, or @p last if no such iterator exists.
4190 */
4192 inline _InputIterator
4195 {
4196 // concept requirements
4203 }
4205 /**
4206 * @brief Find the first element in a sequence for which a
4207 * predicate is true.
4208 * @ingroup non_mutating_algorithms
4209 * @param first An input iterator.
4210 * @param last An input iterator.
4211 * @param pred A predicate.
4212 * @return The first iterator @c i in the range @p [first,last)
4213 * such that @p pred(*i) is true, or @p last if no such iterator exists.
4214 */
4216 inline _InputIterator
4218 _Predicate __pred)
4219 {
4220 // concept requirements
4227 }
4229 /**
4230 * @brief Find element from a set in a sequence.
4231 * @ingroup non_mutating_algorithms
4232 * @param first1 Start of range to search.
4233 * @param last1 End of range to search.
4234 * @param first2 Start of match candidates.
4235 * @param last2 End of match candidates.
4236 * @return The first iterator @c i in the range
4237 * @p [first1,last1) such that @c *i == @p *(i2) such that i2 is an
4238 * iterator in [first2,last2), or @p last1 if no such iterator exists.
4239 *
4240 * Searches the range @p [first1,last1) for an element that is equal to
4241 * some element in the range [first2,last2). If found, returns an iterator
4242 * in the range [first1,last1), otherwise returns @p last1.
4243 */
4245 _InputIterator
4248 {
4249 // concept requirements
4263 }
4265 /**
4266 * @brief Find element from a set in a sequence using a predicate.
4267 * @ingroup non_mutating_algorithms
4268 * @param first1 Start of range to search.
4269 * @param last1 End of range to search.
4270 * @param first2 Start of match candidates.
4271 * @param last2 End of match candidates.
4272 * @param comp Predicate to use.
4273 * @return The first iterator @c i in the range
4274 * @p [first1,last1) such that @c comp(*i, @p *(i2)) is true and i2 is an
4275 * iterator in [first2,last2), or @p last1 if no such iterator exists.
4276 *
4278 * Searches the range @p [first1,last1) for an element that is
4279 * equal to some element in the range [first2,last2). If found,
4280 * returns an iterator in the range [first1,last1), otherwise
4281 * returns @p last1.
4282 */
4284 typename _BinaryPredicate>
4285 _InputIterator
4288 _BinaryPredicate __comp)
4289 {
4290 // concept requirements
4304 }
4306 /**
4307 * @brief Find two adjacent values in a sequence that are equal.
4308 * @ingroup non_mutating_algorithms
4309 * @param first A forward iterator.
4310 * @param last A forward iterator.
4311 * @return The first iterator @c i such that @c i and @c i+1 are both
4312 * valid iterators in @p [first,last) and such that @c *i == @c *(i+1),
4313 * or @p last if no such iterator exists.
4314 */
4316 _ForwardIterator
4318 {
4319 // concept requirements
4328 {
4332 }
4334 }
4336 /**
4337 * @brief Find two adjacent values in a sequence using a predicate.
4338 * @ingroup non_mutating_algorithms
4339 * @param first A forward iterator.
4340 * @param last A forward iterator.
4341 * @param binary_pred A binary predicate.
4342 * @return The first iterator @c i such that @c i and @c i+1 are both
4343 * valid iterators in @p [first,last) and such that
4344 * @p binary_pred(*i,*(i+1)) is true, or @p last if no such iterator
4345 * exists.
4346 */
4348 _ForwardIterator
4350 _BinaryPredicate __binary_pred)
4351 {
4352 // concept requirements
4362 {
4366 }
4368 }
4370 /**
4371 * @brief Count the number of copies of a value in a sequence.
4372 * @ingroup non_mutating_algorithms
4373 * @param first An input iterator.
4374 * @param last An input iterator.
4375 * @param value The value to be counted.
4376 * @return The number of iterators @c i in the range @p [first,last)
4377 * for which @c *i == @p value
4378 */
4382 {
4383 // concept requirements
4393 }
4395 /**
4396 * @brief Count the elements of a sequence for which a predicate is true.
4397 * @ingroup non_mutating_algorithms
4398 * @param first An input iterator.
4399 * @param last An input iterator.
4400 * @param pred A predicate.
4401 * @return The number of iterators @c i in the range @p [first,last)
4402 * for which @p pred(*i) is true.
4403 */
4407 {
4408 // concept requirements
4418 }
4420 /**
4421 * @brief Search a sequence for a matching sub-sequence.
4422 * @ingroup non_mutating_algorithms
4423 * @param first1 A forward iterator.
4424 * @param last1 A forward iterator.
4425 * @param first2 A forward iterator.
4426 * @param last2 A forward iterator.
4427 * @return The first iterator @c i in the range
4428 * @p [first1,last1-(last2-first2)) such that @c *(i+N) == @p *(first2+N)
4429 * for each @c N in the range @p [0,last2-first2), or @p last1 if no
4430 * such iterator exists.
4431 *
4432 * Searches the range @p [first1,last1) for a sub-sequence that compares
4433 * equal value-by-value with the sequence given by @p [first2,last2) and
4434 * returns an iterator to the first element of the sub-sequence, or
4435 * @p last1 if the sub-sequence is not found.
4436 *
4437 * Because the sub-sequence must lie completely within the range
4438 * @p [first1,last1) it must start at a position less than
4439 * @p last1-(last2-first2) where @p last2-first2 is the length of the
4440 * sub-sequence.
4441 * This means that the returned iterator @c i will be in the range
4442 * @p [first1,last1-(last2-first2))
4443 */
4445 _ForwardIterator1
4448 {
4449 // concept requirements
4458 // Test for empty ranges
4462 // Test for a pattern of length 1.
4467 // General case.
4468 _ForwardIterator2 __p;
4472 {
4483 {
4488 }
4490 }
4492 }
4494 /**
4495 * @brief Search a sequence for a matching sub-sequence using a predicate.
4496 * @ingroup non_mutating_algorithms
4497 * @param first1 A forward iterator.
4498 * @param last1 A forward iterator.
4499 * @param first2 A forward iterator.
4500 * @param last2 A forward iterator.
4501 * @param predicate A binary predicate.
4502 * @return The first iterator @c i in the range
4503 * @p [first1,last1-(last2-first2)) such that
4504 * @p predicate(*(i+N),*(first2+N)) is true for each @c N in the range
4505 * @p [0,last2-first2), or @p last1 if no such iterator exists.
4506 *
4507 * Searches the range @p [first1,last1) for a sub-sequence that compares
4508 * equal value-by-value with the sequence given by @p [first2,last2),
4509 * using @p predicate to determine equality, and returns an iterator
4510 * to the first element of the sub-sequence, or @p last1 if no such
4511 * iterator exists.
4512 *
4513 * @see search(_ForwardIter1, _ForwardIter1, _ForwardIter2, _ForwardIter2)
4514 */
4516 typename _BinaryPredicate>
4517 _ForwardIterator1
4520 _BinaryPredicate __predicate)
4521 {
4522 // concept requirements
4531 // Test for empty ranges
4535 // Test for a pattern of length 1.
4538 {
4543 }
4545 // General case.
4546 _ForwardIterator2 __p;
4550 {
4563 {
4568 }
4570 }
4572 }
4575 /**
4576 * @brief Search a sequence for a number of consecutive values.
4577 * @ingroup non_mutating_algorithms
4578 * @param first A forward iterator.
4579 * @param last A forward iterator.
4580 * @param count The number of consecutive values.
4581 * @param val The value to find.
4582 * @return The first iterator @c i in the range @p [first,last-count)
4583 * such that @c *(i+N) == @p val for each @c N in the range @p [0,count),
4584 * or @p last if no such iterator exists.
4585 *
4586 * Searches the range @p [first,last) for @p count consecutive elements
4587 * equal to @p val.
4588 */
4590 _ForwardIterator
4593 {
4594 // concept requirements
4606 }
4609 /**
4610 * @brief Search a sequence for a number of consecutive values using a
4611 * predicate.
4612 * @ingroup non_mutating_algorithms
4613 * @param first A forward iterator.
4614 * @param last A forward iterator.
4615 * @param count The number of consecutive values.
4616 * @param val The value to find.
4617 * @param binary_pred A binary predicate.
4618 * @return The first iterator @c i in the range @p [first,last-count)
4619 * such that @p binary_pred(*(i+N),val) is true for each @c N in the
4620 * range @p [0,count), or @p last if no such iterator exists.
4621 *
4622 * Searches the range @p [first,last) for @p count consecutive elements
4623 * for which the predicate returns true.
4624 */
4626 typename _BinaryPredicate>
4627 _ForwardIterator
4630 _BinaryPredicate __binary_pred)
4631 {
4632 // concept requirements
4641 {
4645 }
4648 }
4651 /**
4652 * @brief Perform an operation on a sequence.
4653 * @ingroup mutating_algorithms
4654 * @param first An input iterator.
4655 * @param last An input iterator.
4656 * @param result An output iterator.
4657 * @param unary_op A unary operator.
4658 * @return An output iterator equal to @p result+(last-first).
4659 *
4660 * Applies the operator to each element in the input range and assigns
4661 * the results to successive elements of the output sequence.
4662 * Evaluates @p *(result+N)=unary_op(*(first+N)) for each @c N in the
4663 * range @p [0,last-first).
4664 *
4665 * @p unary_op must not alter its argument.
4666 */
4668 typename _UnaryOperation>
4669 _OutputIterator
4672 {
4673 // concept requirements
4676 // "the type returned by a _UnaryOperation"
4683 }
4685 /**
4686 * @brief Perform an operation on corresponding elements of two sequences.
4687 * @ingroup mutating_algorithms
4688 * @param first1 An input iterator.
4689 * @param last1 An input iterator.
4690 * @param first2 An input iterator.
4691 * @param result An output iterator.
4692 * @param binary_op A binary operator.
4693 * @return An output iterator equal to @p result+(last-first).
4694 *
4695 * Applies the operator to the corresponding elements in the two
4696 * input ranges and assigns the results to successive elements of the
4697 * output sequence.
4698 * Evaluates @p *(result+N)=binary_op(*(first1+N),*(first2+N)) for each
4699 * @c N in the range @p [0,last1-first1).
4700 *
4701 * @p binary_op must not alter either of its arguments.
4702 */
4705 _OutputIterator
4708 _BinaryOperation __binary_op)
4709 {
4710 // concept requirements
4714 // "the type returned by a _BinaryOperation"
4721 }
4723 /**
4724 * @brief Replace each occurrence of one value in a sequence with another
4725 * value.
4726 * @ingroup mutating_algorithms
4727 * @param first A forward iterator.
4728 * @param last A forward iterator.
4729 * @param old_value The value to be replaced.
4730 * @param new_value The replacement value.
4731 * @return replace() returns no value.
4732 *
4733 * For each iterator @c i in the range @p [first,last) if @c *i ==
4734 * @p old_value then the assignment @c *i = @p new_value is performed.
4735 */
4737 void
4740 {
4741 // concept requirements
4743 _ForwardIterator>)
4753 }
4755 /**
4756 * @brief Replace each value in a sequence for which a predicate returns
4757 * true with another value.
4758 * @ingroup mutating_algorithms
4759 * @param first A forward iterator.
4760 * @param last A forward iterator.
4761 * @param pred A predicate.
4762 * @param new_value The replacement value.
4763 * @return replace_if() returns no value.
4764 *
4765 * For each iterator @c i in the range @p [first,last) if @p pred(*i)
4766 * is true then the assignment @c *i = @p new_value is performed.
4767 */
4769 void
4772 {
4773 // concept requirements
4775 _ForwardIterator>)
4785 }
4787 /**
4788 * @brief Assign the result of a function object to each value in a
4789 * sequence.
4790 * @ingroup mutating_algorithms
4791 * @param first A forward iterator.
4792 * @param last A forward iterator.
4793 * @param gen A function object taking no arguments and returning
4794 * std::iterator_traits<_ForwardIterator>::value_type
4795 * @return generate() returns no value.
4796 *
4797 * Performs the assignment @c *i = @p gen() for each @c i in the range
4798 * @p [first,last).
4799 */
4801 void
4803 _Generator __gen)
4804 {
4805 // concept requirements
4813 }
4815 /**
4816 * @brief Assign the result of a function object to each value in a
4817 * sequence.
4818 * @ingroup mutating_algorithms
4819 * @param first A forward iterator.
4820 * @param n The length of the sequence.
4821 * @param gen A function object taking no arguments and returning
4822 * std::iterator_traits<_ForwardIterator>::value_type
4823 * @return The end of the sequence, @p first+n
4824 *
4825 * Performs the assignment @c *i = @p gen() for each @c i in the range
4826 * @p [first,first+n).
4827 *
4828 * _GLIBCXX_RESOLVE_LIB_DEFECTS
4829 * DR 865. More algorithms that throw away information
4830 */
4832 _OutputIterator
4834 {
4835 // concept requirements
4837 // "the type returned by a _Generator"
4844 }
4847 /**
4848 * @brief Copy a sequence, removing consecutive duplicate values.
4849 * @ingroup mutating_algorithms
4850 * @param first An input iterator.
4851 * @param last An input iterator.
4852 * @param result An output iterator.
4853 * @return An iterator designating the end of the resulting sequence.
4854 *
4855 * Copies each element in the range @p [first,last) to the range
4856 * beginning at @p result, except that only the first element is copied
4857 * from groups of consecutive elements that compare equal.
4858 * unique_copy() is stable, so the relative order of elements that are
4859 * copied is unchanged.
4860 *
4861 * _GLIBCXX_RESOLVE_LIB_DEFECTS
4862 * DR 241. Does unique_copy() require CopyConstructible and Assignable?
4863 *
4864 * _GLIBCXX_RESOLVE_LIB_DEFECTS
4865 * DR 538. 241 again: Does unique_copy() require CopyConstructible and
4866 * Assignable?
4867 */
4869 inline _OutputIterator
4871 _OutputIterator __result)
4872 {
4873 // concept requirements
4886 }
4888 /**
4889 * @brief Copy a sequence, removing consecutive values using a predicate.
4890 * @ingroup mutating_algorithms
4891 * @param first An input iterator.
4892 * @param last An input iterator.
4893 * @param result An output iterator.
4894 * @param binary_pred A binary predicate.
4895 * @return An iterator designating the end of the resulting sequence.
4896 *
4897 * Copies each element in the range @p [first,last) to the range
4898 * beginning at @p result, except that only the first element is copied
4899 * from groups of consecutive elements for which @p binary_pred returns
4900 * true.
4901 * unique_copy() is stable, so the relative order of elements that are
4902 * copied is unchanged.
4903 *
4904 * _GLIBCXX_RESOLVE_LIB_DEFECTS
4905 * DR 241. Does unique_copy() require CopyConstructible and Assignable?
4906 */
4908 typename _BinaryPredicate>
4909 inline _OutputIterator
4911 _OutputIterator __result,
4912 _BinaryPredicate __binary_pred)
4913 {
4914 // concept requirements -- predicates checked later
4925 }
4928 /**
4929 * @brief Randomly shuffle the elements of a sequence.
4930 * @ingroup mutating_algorithms
4931 * @param first A forward iterator.
4932 * @param last A forward iterator.
4933 * @return Nothing.
4934 *
4935 * Reorder the elements in the range @p [first,last) using a random
4936 * distribution, so that every possible ordering of the sequence is
4937 * equally likely.
4938 */
4942 {
4943 // concept requirements
4945 _RandomAccessIterator>)
4951 }
4953 /**
4954 * @brief Shuffle the elements of a sequence using a random number
4955 * generator.
4956 * @ingroup mutating_algorithms
4957 * @param first A forward iterator.
4958 * @param last A forward iterator.
4959 * @param rand The RNG functor or function.
4960 * @return Nothing.
4961 *
4962 * Reorders the elements in the range @p [first,last) using @p rand to
4963 * provide a random distribution. Calling @p rand(N) for a positive
4964 * integer @p N should return a randomly chosen integer from the
4965 * range [0,N).
4966 */
4968 void
4970 #ifdef __GXX_EXPERIMENTAL_CXX0X__
4972 #else
4974 #endif
4975 {
4976 // concept requirements
4978 _RandomAccessIterator>)
4985 }
4988 /**
4989 * @brief Move elements for which a predicate is true to the beginning
4990 * of a sequence.
4991 * @ingroup mutating_algorithms
4992 * @param first A forward iterator.
4993 * @param last A forward iterator.
4994 * @param pred A predicate functor.
4995 * @return An iterator @p middle such that @p pred(i) is true for each
4996 * iterator @p i in the range @p [first,middle) and false for each @p i
4997 * in the range @p [middle,last).
4998 *
4999 * @p pred must not modify its operand. @p partition() does not preserve
5000 * the relative ordering of elements in each group, use
5001 * @p stable_partition() if this is needed.
5002 */
5004 inline _ForwardIterator
5006 _Predicate __pred)
5007 {
5008 // concept requirements
5010 _ForwardIterator>)
5017 }
5021 /**
5022 * @brief Sort the smallest elements of a sequence.
5023 * @ingroup sorting_algorithms
5024 * @param first An iterator.
5025 * @param middle Another iterator.
5026 * @param last Another iterator.
5027 * @return Nothing.
5028 *
5029 * Sorts the smallest @p (middle-first) elements in the range
5030 * @p [first,last) and moves them to the range @p [first,middle). The
5031 * order of the remaining elements in the range @p [middle,last) is
5032 * undefined.
5033 * After the sort if @p i and @j are iterators in the range
5034 * @p [first,middle) such that @i precedes @j and @k is an iterator in
5035 * the range @p [middle,last) then @p *j<*i and @p *k<*i are both false.
5036 */
5040 _RandomAccessIterator __middle,
5041 _RandomAccessIterator __last)
5042 {
5044 _ValueType;
5046 // concept requirements
5048 _RandomAccessIterator>)
5055 }
5057 /**
5058 * @brief Sort the smallest elements of a sequence using a predicate
5059 * for comparison.
5060 * @ingroup sorting_algorithms
5061 * @param first An iterator.
5062 * @param middle Another iterator.
5063 * @param last Another iterator.
5064 * @param comp A comparison functor.
5065 * @return Nothing.
5066 *
5067 * Sorts the smallest @p (middle-first) elements in the range
5068 * @p [first,last) and moves them to the range @p [first,middle). The
5069 * order of the remaining elements in the range @p [middle,last) is
5070 * undefined.
5071 * After the sort if @p i and @j are iterators in the range
5072 * @p [first,middle) such that @i precedes @j and @k is an iterator in
5073 * the range @p [middle,last) then @p *comp(j,*i) and @p comp(*k,*i)
5074 * are both false.
5075 */
5079 _RandomAccessIterator __middle,
5080 _RandomAccessIterator __last,
5081 _Compare __comp)
5082 {
5084 _ValueType;
5086 // concept requirements
5088 _RandomAccessIterator>)
5096 }
5098 /**
5099 * @brief Sort a sequence just enough to find a particular position.
5100 * @ingroup sorting_algorithms
5101 * @param first An iterator.
5102 * @param nth Another iterator.
5103 * @param last Another iterator.
5104 * @return Nothing.
5105 *
5106 * Rearranges the elements in the range @p [first,last) so that @p *nth
5107 * is the same element that would have been in that position had the
5108 * whole sequence been sorted.
5109 * whole sequence been sorted. The elements either side of @p *nth are
5110 * not completely sorted, but for any iterator @i in the range
5111 * @p [first,nth) and any iterator @j in the range @p [nth,last) it
5112 * holds that @p *j<*i is false.
5113 */
5117 _RandomAccessIterator __last)
5118 {
5120 _ValueType;
5122 // concept requirements
5124 _RandomAccessIterator>)
5134 }
5136 /**
5137 * @brief Sort a sequence just enough to find a particular position
5138 * using a predicate for comparison.
5139 * @ingroup sorting_algorithms
5140 * @param first An iterator.
5141 * @param nth Another iterator.
5142 * @param last Another iterator.
5143 * @param comp A comparison functor.
5144 * @return Nothing.
5145 *
5146 * Rearranges the elements in the range @p [first,last) so that @p *nth
5147 * is the same element that would have been in that position had the
5148 * whole sequence been sorted. The elements either side of @p *nth are
5149 * not completely sorted, but for any iterator @i in the range
5150 * @p [first,nth) and any iterator @j in the range @p [nth,last) it
5151 * holds that @p comp(*j,*i) is false.
5152 */
5157 {
5159 _ValueType;
5161 // concept requirements
5163 _RandomAccessIterator>)
5174 }
5177 /**
5178 * @brief Sort the elements of a sequence.
5179 * @ingroup sorting_algorithms
5180 * @param first An iterator.
5181 * @param last Another iterator.
5182 * @return Nothing.
5183 *
5184 * Sorts the elements in the range @p [first,last) in ascending order,
5185 * such that @p *(i+1)<*i is false for each iterator @p i in the range
5186 * @p [first,last-1).
5187 *
5188 * The relative ordering of equivalent elements is not preserved, use
5189 * @p stable_sort() if this is needed.
5190 */
5194 {
5196 _ValueType;
5198 // concept requirements
5200 _RandomAccessIterator>)
5205 {
5209 }
5210 }
5212 /**
5213 * @brief Sort the elements of a sequence using a predicate for comparison.
5214 * @ingroup sorting_algorithms
5215 * @param first An iterator.
5216 * @param last Another iterator.
5217 * @param comp A comparison functor.
5218 * @return Nothing.
5219 *
5220 * Sorts the elements in the range @p [first,last) in ascending order,
5221 * such that @p comp(*(i+1),*i) is false for every iterator @p i in the
5222 * range @p [first,last-1).
5223 *
5224 * The relative ordering of equivalent elements is not preserved, use
5225 * @p stable_sort() if this is needed.
5226 */
5230 _Compare __comp)
5231 {
5233 _ValueType;
5235 // concept requirements
5237 _RandomAccessIterator>)
5239 _ValueType>)
5243 {
5247 }
5248 }
5250 /**
5251 * @brief Merges two sorted ranges.
5252 * @ingroup sorting_algorithms
5253 * @param first1 An iterator.
5254 * @param first2 Another iterator.
5255 * @param last1 Another iterator.
5256 * @param last2 Another iterator.
5257 * @param result An iterator pointing to the end of the merged range.
5258 * @return An iterator pointing to the first element <em>not less
5259 * than</em> @a val.
5260 *
5261 * Merges the ranges [first1,last1) and [first2,last2) into the sorted range
5262 * [result, result + (last1-first1) + (last2-first2)). Both input ranges
5263 * must be sorted, and the output range must not overlap with either of
5264 * the input ranges. The sort is @e stable, that is, for equivalent
5265 * elements in the two ranges, elements from the first range will always
5266 * come before elements from the second.
5267 */
5269 typename _OutputIterator>
5270 _OutputIterator
5273 _OutputIterator __result)
5274 {
5276 _ValueType1;
5278 _ValueType2;
5280 // concept requirements
5284 _ValueType1>)
5286 _ValueType2>)
5292 {
5294 {
5297 }
5298 else
5299 {
5302 }
5304 }
5306 __result));
5307 }
5309 /**
5310 * @brief Merges two sorted ranges.
5311 * @ingroup sorting_algorithms
5312 * @param first1 An iterator.
5313 * @param first2 Another iterator.
5314 * @param last1 Another iterator.
5315 * @param last2 Another iterator.
5316 * @param result An iterator pointing to the end of the merged range.
5317 * @param comp A functor to use for comparisons.
5318 * @return An iterator pointing to the first element "not less
5319 * than" @a val.
5320 *
5321 * Merges the ranges [first1,last1) and [first2,last2) into the sorted range
5322 * [result, result + (last1-first1) + (last2-first2)). Both input ranges
5323 * must be sorted, and the output range must not overlap with either of
5324 * the input ranges. The sort is @e stable, that is, for equivalent
5325 * elements in the two ranges, elements from the first range will always
5326 * come before elements from the second.
5327 *
5328 * The comparison function should have the same effects on ordering as
5329 * the function used for the initial sort.
5330 */
5333 _OutputIterator
5337 {
5339 _ValueType1;
5341 _ValueType2;
5343 // concept requirements
5347 _ValueType1>)
5349 _ValueType2>)
5356 {
5358 {
5361 }
5362 else
5363 {
5366 }
5368 }
5370 __result));
5371 }
5374 /**
5375 * @brief Sort the elements of a sequence, preserving the relative order
5376 * of equivalent elements.
5377 * @ingroup sorting_algorithms
5378 * @param first An iterator.
5379 * @param last Another iterator.
5380 * @return Nothing.
5381 *
5382 * Sorts the elements in the range @p [first,last) in ascending order,
5383 * such that @p *(i+1)<*i is false for each iterator @p i in the range
5384 * @p [first,last-1).
5385 *
5386 * The relative ordering of equivalent elements is preserved, so any two
5387 * elements @p x and @p y in the range @p [first,last) such that
5388 * @p x<y is false and @p y<x is false will have the same relative
5389 * ordering after calling @p stable_sort().
5390 */
5394 {
5396 _ValueType;
5398 _DistanceType;
5400 // concept requirements
5402 _RandomAccessIterator>)
5407 __last);
5410 else
5413 }
5415 /**
5416 * @brief Sort the elements of a sequence using a predicate for comparison,
5417 * preserving the relative order of equivalent elements.
5418 * @ingroup sorting_algorithms
5419 * @param first An iterator.
5420 * @param last Another iterator.
5421 * @param comp A comparison functor.
5422 * @return Nothing.
5423 *
5424 * Sorts the elements in the range @p [first,last) in ascending order,
5425 * such that @p comp(*(i+1),*i) is false for each iterator @p i in the
5426 * range @p [first,last-1).
5427 *
5428 * The relative ordering of equivalent elements is preserved, so any two
5429 * elements @p x and @p y in the range @p [first,last) such that
5430 * @p comp(x,y) is false and @p comp(y,x) is false will have the same
5431 * relative ordering after calling @p stable_sort().
5432 */
5436 _Compare __comp)
5437 {
5439 _ValueType;
5441 _DistanceType;
5443 // concept requirements
5445 _RandomAccessIterator>)
5447 _ValueType,
5448 _ValueType>)
5452 __last);
5455 else
5458 }
5461 /**
5462 * @brief Return the union of two sorted ranges.
5463 * @ingroup set_algorithms
5464 * @param first1 Start of first range.
5465 * @param last1 End of first range.
5466 * @param first2 Start of second range.
5467 * @param last2 End of second range.
5468 * @return End of the output range.
5469 * @ingroup set_algorithms
5470 *
5471 * This operation iterates over both ranges, copying elements present in
5472 * each range in order to the output range. Iterators increment for each
5473 * range. When the current element of one range is less than the other,
5474 * that element is copied and the iterator advanced. If an element is
5475 * contained in both ranges, the element from the first range is copied and
5476 * both ranges advance. The output range may not overlap either input
5477 * range.
5478 */
5480 typename _OutputIterator>
5481 _OutputIterator
5484 _OutputIterator __result)
5485 {
5487 _ValueType1;
5489 _ValueType2;
5491 // concept requirements
5495 _ValueType1>)
5497 _ValueType2>)
5504 {
5506 {
5509 }
5511 {
5514 }
5515 else
5516 {
5520 }
5522 }
5524 __result));
5525 }
5527 /**
5528 * @brief Return the union of two sorted ranges using a comparison functor.
5529 * @ingroup set_algorithms
5530 * @param first1 Start of first range.
5531 * @param last1 End of first range.
5532 * @param first2 Start of second range.
5533 * @param last2 End of second range.
5534 * @param comp The comparison functor.
5535 * @return End of the output range.
5536 * @ingroup set_algorithms
5537 *
5538 * This operation iterates over both ranges, copying elements present in
5539 * each range in order to the output range. Iterators increment for each
5540 * range. When the current element of one range is less than the other
5541 * according to @a comp, that element is copied and the iterator advanced.
5542 * If an equivalent element according to @a comp is contained in both
5543 * ranges, the element from the first range is copied and both ranges
5544 * advance. The output range may not overlap either input range.
5545 */
5548 _OutputIterator
5552 {
5554 _ValueType1;
5556 _ValueType2;
5558 // concept requirements
5562 _ValueType1>)
5564 _ValueType2>)
5573 {
5575 {
5578 }
5580 {
5583 }
5584 else
5585 {
5589 }
5591 }
5593 __result));
5594 }
5596 /**
5597 * @brief Return the intersection of two sorted ranges.
5598 * @ingroup set_algorithms
5599 * @param first1 Start of first range.
5600 * @param last1 End of first range.
5601 * @param first2 Start of second range.
5602 * @param last2 End of second range.
5603 * @return End of the output range.
5604 * @ingroup set_algorithms
5605 *
5606 * This operation iterates over both ranges, copying elements present in
5607 * both ranges in order to the output range. Iterators increment for each
5608 * range. When the current element of one range is less than the other,
5609 * that iterator advances. If an element is contained in both ranges, the
5610 * element from the first range is copied and both ranges advance. The
5611 * output range may not overlap either input range.
5612 */
5614 typename _OutputIterator>
5615 _OutputIterator
5618 _OutputIterator __result)
5619 {
5621 _ValueType1;
5623 _ValueType2;
5625 // concept requirements
5629 _ValueType1>)
5640 else
5641 {
5646 }
5648 }
5650 /**
5651 * @brief Return the intersection of two sorted ranges using comparison
5652 * functor.
5653 * @ingroup set_algorithms
5654 * @param first1 Start of first range.
5655 * @param last1 End of first range.
5656 * @param first2 Start of second range.
5657 * @param last2 End of second range.
5658 * @param comp The comparison functor.
5659 * @return End of the output range.
5660 * @ingroup set_algorithms
5661 *
5662 * This operation iterates over both ranges, copying elements present in
5663 * both ranges in order to the output range. Iterators increment for each
5664 * range. When the current element of one range is less than the other
5665 * according to @a comp, that iterator advances. If an element is
5666 * contained in both ranges according to @a comp, the element from the
5667 * first range is copied and both ranges advance. The output range may not
5668 * overlap either input range.
5669 */
5672 _OutputIterator
5676 {
5678 _ValueType1;
5680 _ValueType2;
5682 // concept requirements
5686 _ValueType1>)
5699 else
5700 {
5705 }
5707 }
5709 /**
5710 * @brief Return the difference of two sorted ranges.
5711 * @ingroup set_algorithms
5712 * @param first1 Start of first range.
5713 * @param last1 End of first range.
5714 * @param first2 Start of second range.
5715 * @param last2 End of second range.
5716 * @return End of the output range.
5717 * @ingroup set_algorithms
5718 *
5719 * This operation iterates over both ranges, copying elements present in
5720 * the first range but not the second in order to the output range.
5721 * Iterators increment for each range. When the current element of the
5722 * first range is less than the second, that element is copied and the
5723 * iterator advances. If the current element of the second range is less,
5724 * the iterator advances, but no element is copied. If an element is
5725 * contained in both ranges, no elements are copied and both ranges
5726 * advance. The output range may not overlap either input range.
5727 */
5729 typename _OutputIterator>
5730 _OutputIterator
5733 _OutputIterator __result)
5734 {
5736 _ValueType1;
5738 _ValueType2;
5740 // concept requirements
5744 _ValueType1>)
5752 {
5756 }
5759 else
5760 {
5763 }
5765 }
5767 /**
5768 * @brief Return the difference of two sorted ranges using comparison
5769 * functor.
5770 * @ingroup set_algorithms
5771 * @param first1 Start of first range.
5772 * @param last1 End of first range.
5773 * @param first2 Start of second range.
5774 * @param last2 End of second range.
5775 * @param comp The comparison functor.
5776 * @return End of the output range.
5777 * @ingroup set_algorithms
5778 *
5779 * This operation iterates over both ranges, copying elements present in
5780 * the first range but not the second in order to the output range.
5781 * Iterators increment for each range. When the current element of the
5782 * first range is less than the second according to @a comp, that element
5783 * is copied and the iterator advances. If the current element of the
5784 * second range is less, no element is copied and the iterator advances.
5785 * If an element is contained in both ranges according to @a comp, no
5786 * elements are copied and both ranges advance. The output range may not
5787 * overlap either input range.
5788 */
5791 _OutputIterator
5795 {
5797 _ValueType1;
5799 _ValueType2;
5801 // concept requirements
5805 _ValueType1>)
5815 {
5819 }
5822 else
5823 {
5826 }
5828 }
5830 /**
5831 * @brief Return the symmetric difference of two sorted ranges.
5832 * @ingroup set_algorithms
5833 * @param first1 Start of first range.
5834 * @param last1 End of first range.
5835 * @param first2 Start of second range.
5836 * @param last2 End of second range.
5837 * @return End of the output range.
5838 * @ingroup set_algorithms
5839 *
5840 * This operation iterates over both ranges, copying elements present in
5841 * one range but not the other in order to the output range. Iterators
5842 * increment for each range. When the current element of one range is less
5843 * than the other, that element is copied and the iterator advances. If an
5844 * element is contained in both ranges, no elements are copied and both
5845 * ranges advance. The output range may not overlap either input range.
5846 */
5848 typename _OutputIterator>
5849 _OutputIterator
5852 _OutputIterator __result)
5853 {
5855 _ValueType1;
5857 _ValueType2;
5859 // concept requirements
5863 _ValueType1>)
5865 _ValueType2>)
5873 {
5877 }
5879 {
5883 }
5884 else
5885 {
5888 }
5891 }
5893 /**
5894 * @brief Return the symmetric difference of two sorted ranges using
5895 * comparison functor.
5896 * @ingroup set_algorithms
5897 * @param first1 Start of first range.
5898 * @param last1 End of first range.
5899 * @param first2 Start of second range.
5900 * @param last2 End of second range.
5901 * @param comp The comparison functor.
5902 * @return End of the output range.
5903 * @ingroup set_algorithms
5904 *
5905 * This operation iterates over both ranges, copying elements present in
5906 * one range but not the other in order to the output range. Iterators
5907 * increment for each range. When the current element of one range is less
5908 * than the other according to @a comp, that element is copied and the
5909 * iterator advances. If an element is contained in both ranges according
5910 * to @a comp, no elements are copied and both ranges advance. The output
5911 * range may not overlap either input range.
5912 */
5915 _OutputIterator
5918 _OutputIterator __result,
5919 _Compare __comp)
5920 {
5922 _ValueType1;
5924 _ValueType2;
5926 // concept requirements
5930 _ValueType1>)
5932 _ValueType2>)
5942 {
5946 }
5948 {
5952 }
5953 else
5954 {
5957 }
5960 }
5963 /**
5964 * @brief Return the minimum element in a range.
5965 * @ingroup sorting_algorithms
5966 * @param first Start of range.
5967 * @param last End of range.
5968 * @return Iterator referencing the first instance of the smallest value.
5969 */
5971 _ForwardIterator
5973 {
5974 // concept requirements
5987 }
5989 /**
5990 * @brief Return the minimum element in a range using comparison functor.
5991 * @ingroup sorting_algorithms
5992 * @param first Start of range.
5993 * @param last End of range.
5994 * @param comp Comparison functor.
5995 * @return Iterator referencing the first instance of the smallest value
5996 * according to comp.
5997 */
5999 _ForwardIterator
6001 _Compare __comp)
6002 {
6003 // concept requirements
6017 }
6019 /**
6020 * @brief Return the maximum element in a range.
6021 * @ingroup sorting_algorithms
6022 * @param first Start of range.
6023 * @param last End of range.
6024 * @return Iterator referencing the first instance of the largest value.
6025 */
6027 _ForwardIterator
6029 {
6030 // concept requirements
6043 }
6045 /**
6046 * @brief Return the maximum element in a range using comparison functor.
6047 * @ingroup sorting_algorithms
6048 * @param first Start of range.
6049 * @param last End of range.
6050 * @param comp Comparison functor.
6051 * @return Iterator referencing the first instance of the largest value
6052 * according to comp.
6053 */
6055 _ForwardIterator
6057 _Compare __comp)
6058 {
6059 // concept requirements
6072 }
6074 _GLIBCXX_END_NESTED_NAMESPACE