| blob | 530999797f09b2f4f96ecfb41ed56b62be497e9c |
1 // Algorithm implementation -*- C++ -*-
3 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009
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 2, 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 // You should have received a copy of the GNU General Public License along
18 // with this library; see the file COPYING. If not, write to the Free
19 // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
20 // USA.
22 // As a special exception, you may use this file as part of a free software
23 // library without restriction. Specifically, if other files instantiate
24 // templates or use macros or inline functions from this file, or you compile
25 // this file and link it with other files to produce an executable, this
26 // file does not by itself cause the resulting executable to be covered by
27 // the GNU General Public License. This exception does not however
28 // invalidate any other reasons why the executable file might be covered by
29 // the GNU General Public License.
31 /*
32 *
33 * Copyright (c) 1994
34 * Hewlett-Packard Company
35 *
36 * Permission to use, copy, modify, distribute and sell this software
37 * and its documentation for any purpose is hereby granted without fee,
38 * provided that the above copyright notice appear in all copies and
39 * that both that copyright notice and this permission notice appear
40 * in supporting documentation. Hewlett-Packard Company makes no
41 * representations about the suitability of this software for any
42 * purpose. It is provided "as is" without express or implied warranty.
43 *
44 *
45 * Copyright (c) 1996
46 * Silicon Graphics Computer Systems, Inc.
47 *
48 * Permission to use, copy, modify, distribute and sell this software
49 * and its documentation for any purpose is hereby granted without fee,
50 * provided that the above copyright notice appear in all copies and
51 * that both that copyright notice and this permission notice appear
52 * in supporting documentation. Silicon Graphics makes no
53 * representations about the suitability of this software for any
54 * purpose. It is provided "as is" without express or implied warranty.
55 */
57 /** @file stl_algo.h
58 * This is an internal header file, included by other library headers.
59 * You should not attempt to use it directly.
60 */
62 #ifndef _STL_ALGO_H
63 #define _STL_ALGO_H 1
66 #include <bits/algorithmfwd.h>
67 #include <bits/stl_heap.h>
69 #include <debug/debug.h>
70 #include <initializer_list>
72 // See concept_check.h for the __glibcxx_*_requires macros.
76 /**
77 * @brief Find the median of three values.
78 * @param a A value.
79 * @param b A value.
80 * @param c A value.
81 * @return One of @p a, @p b or @p c.
82 *
83 * If @c {l,m,n} is some convolution of @p {a,b,c} such that @c l<=m<=n
84 * then the value returned will be @c m.
85 * This is an SGI extension.
86 * @ingroup SGIextensions
87 */
91 {
92 // concept requirements
99 else
105 else
107 }
109 /**
110 * @brief Find the median of three values using a predicate for comparison.
111 * @param a A value.
112 * @param b A value.
113 * @param c A value.
114 * @param comp A binary predicate.
115 * @return One of @p a, @p b or @p c.
116 *
117 * If @c {l,m,n} is some convolution of @p {a,b,c} such that @p comp(l,m)
118 * and @p comp(m,n) are both true then the value returned will be @c m.
119 * This is an SGI extension.
120 * @ingroup SGIextensions
121 */
125 {
126 // concept requirements
134 else
140 else
142 }
144 // for_each
146 /// This is an overload used by find() for the Input Iterator case.
148 inline _InputIterator
151 {
155 }
157 /// This is an overload used by find_if() for the Input Iterator case.
159 inline _InputIterator
162 {
166 }
168 /// This is an overload used by find() for the RAI case.
170 _RandomAccessIterator
173 {
178 {
194 }
197 {
213 }
214 }
216 /// This is an overload used by find_if() for the RAI case.
218 _RandomAccessIterator
221 {
226 {
242 }
245 {
261 }
262 }
264 #ifdef __GXX_EXPERIMENTAL_CXX0X__
265 /// This is an overload used by find_if_not() for the Input Iterator case.
267 inline _InputIterator
270 {
274 }
276 /// This is an overload used by find_if_not() for the RAI case.
278 _RandomAccessIterator
281 {
286 {
302 }
305 {
321 }
322 }
323 #endif
325 // set_difference
326 // set_intersection
327 // set_symmetric_difference
328 // set_union
329 // for_each
330 // find
331 // find_if
332 // find_first_of
333 // adjacent_find
334 // count
335 // count_if
336 // search
338 /**
339 * This is an uglified
340 * search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&)
341 * overloaded for forward iterators.
342 */
344 _ForwardIterator
348 {
351 {
357 {
360 }
366 }
368 }
370 /**
371 * This is an uglified
372 * search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&)
373 * overloaded for random access iterators.
374 */
376 _RandomAccessIter
380 {
383 _DistanceType;
396 {
397 // __lookAhead here is always pointing to the last element of next
398 // possible match.
400 {
405 }
409 {
412 }
417 }
418 }
420 // search_n
422 /**
423 * This is an uglified
424 * search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&,
425 * _BinaryPredicate)
426 * overloaded for forward iterators.
427 */
429 typename _BinaryPredicate>
430 _ForwardIterator
434 {
439 {
445 {
448 }
457 }
459 }
461 /**
462 * This is an uglified
463 * search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&,
464 * _BinaryPredicate)
465 * overloaded for random access iterators.
466 */
468 typename _BinaryPredicate>
469 _RandomAccessIter
473 {
476 _DistanceType;
489 {
490 // __lookAhead here is always pointing to the last element of next
491 // possible match.
493 {
498 }
502 {
505 }
510 }
511 }
513 // find_end for forward iterators.
515 _ForwardIterator1
519 {
522 else
523 {
526 {
527 _ForwardIterator1 __new_result
531 else
532 {
536 }
537 }
538 }
539 }
542 typename _BinaryPredicate>
543 _ForwardIterator1
547 _BinaryPredicate __comp)
548 {
551 else
552 {
555 {
556 _ForwardIterator1 __new_result
561 else
562 {
566 }
567 }
568 }
569 }
571 // find_end for bidirectional iterators (much faster).
573 _BidirectionalIterator1
575 _BidirectionalIterator1 __last1,
576 _BidirectionalIterator2 __first2,
577 _BidirectionalIterator2 __last2,
579 {
580 // concept requirements
582 _BidirectionalIterator1>)
584 _BidirectionalIterator2>)
592 __rlast1,
594 __rlast2);
598 else
599 {
603 }
604 }
607 typename _BinaryPredicate>
608 _BidirectionalIterator1
610 _BidirectionalIterator1 __last1,
611 _BidirectionalIterator2 __first2,
612 _BidirectionalIterator2 __last2,
614 _BinaryPredicate __comp)
615 {
616 // concept requirements
618 _BidirectionalIterator1>)
620 _BidirectionalIterator2>)
629 __comp);
633 else
634 {
638 }
639 }
641 /**
642 * @brief Find last matching subsequence in a sequence.
643 * @ingroup non_mutating_algorithms
644 * @param first1 Start of range to search.
645 * @param last1 End of range to search.
646 * @param first2 Start of sequence to match.
647 * @param last2 End of sequence to match.
648 * @return The last iterator @c i in the range
649 * @p [first1,last1-(last2-first2)) such that @c *(i+N) == @p *(first2+N)
650 * for each @c N in the range @p [0,last2-first2), or @p last1 if no
651 * such iterator exists.
652 *
653 * Searches the range @p [first1,last1) for a sub-sequence that compares
654 * equal value-by-value with the sequence given by @p [first2,last2) and
655 * returns an iterator to the first element of the sub-sequence, or
656 * @p last1 if the sub-sequence is not found. The sub-sequence will be the
657 * last such subsequence contained in [first,last1).
658 *
659 * Because the sub-sequence must lie completely within the range
660 * @p [first1,last1) it must start at a position less than
661 * @p last1-(last2-first2) where @p last2-first2 is the length of the
662 * sub-sequence.
663 * This means that the returned iterator @c i will be in the range
664 * @p [first1,last1-(last2-first2))
665 */
667 inline _ForwardIterator1
670 {
671 // concept requirements
683 }
685 /**
686 * @brief Find last matching subsequence in a sequence using a predicate.
687 * @ingroup non_mutating_algorithms
688 * @param first1 Start of range to search.
689 * @param last1 End of range to search.
690 * @param first2 Start of sequence to match.
691 * @param last2 End of sequence to match.
692 * @param comp The predicate to use.
693 * @return The last iterator @c i in the range
694 * @p [first1,last1-(last2-first2)) such that @c predicate(*(i+N), @p
695 * (first2+N)) is true for each @c N in the range @p [0,last2-first2), or
696 * @p last1 if no such iterator exists.
697 *
698 * Searches the range @p [first1,last1) for a sub-sequence that compares
699 * equal value-by-value with the sequence given by @p [first2,last2) using
700 * comp as a predicate and returns an iterator to the first element of the
701 * sub-sequence, or @p last1 if the sub-sequence is not found. The
702 * sub-sequence will be the last such subsequence contained in
703 * [first,last1).
704 *
705 * Because the sub-sequence must lie completely within the range
706 * @p [first1,last1) it must start at a position less than
707 * @p last1-(last2-first2) where @p last2-first2 is the length of the
708 * sub-sequence.
709 * This means that the returned iterator @c i will be in the range
710 * @p [first1,last1-(last2-first2))
711 */
713 typename _BinaryPredicate>
714 inline _ForwardIterator1
717 _BinaryPredicate __comp)
718 {
719 // concept requirements
731 __comp);
732 }
734 #ifdef __GXX_EXPERIMENTAL_CXX0X__
735 /**
736 * @brief Checks that a predicate is true for all the elements
737 * of a sequence.
738 * @ingroup non_mutating_algorithms
739 * @param first An input iterator.
740 * @param last An input iterator.
741 * @param pred A predicate.
742 * @return True if the check is true, false otherwise.
743 *
744 * Returns true if @p pred is true for each element in the range
745 * @p [first,last), and false otherwise.
746 */
752 /**
753 * @brief Checks that a predicate is false for all the elements
754 * of a sequence.
755 * @ingroup non_mutating_algorithms
756 * @param first An input iterator.
757 * @param last An input iterator.
758 * @param pred A predicate.
759 * @return True if the check is true, false otherwise.
760 *
761 * Returns true if @p pred is false for each element in the range
762 * @p [first,last), and false otherwise.
763 */
769 /**
770 * @brief Checks that a predicate is false for at least an element
771 * of a sequence.
772 * @ingroup non_mutating_algorithms
773 * @param first An input iterator.
774 * @param last An input iterator.
775 * @param pred A predicate.
776 * @return True if the check is true, false otherwise.
777 *
778 * Returns true if an element exists in the range @p [first,last) such that
779 * @p pred is true, and false otherwise.
780 */
786 /**
787 * @brief Find the first element in a sequence for which a
788 * predicate is false.
789 * @ingroup non_mutating_algorithms
790 * @param first An input iterator.
791 * @param last An input iterator.
792 * @param pred A predicate.
793 * @return The first iterator @c i in the range @p [first,last)
794 * such that @p pred(*i) is false, or @p last if no such iterator exists.
795 */
797 inline _InputIterator
799 _Predicate __pred)
800 {
801 // concept requirements
808 }
810 /**
811 * @brief Checks whether the sequence is partitioned.
812 * @ingroup mutating_algorithms
813 * @param first An input iterator.
814 * @param last An input iterator.
815 * @param pred A predicate.
816 * @return True if the range @p [first,last) is partioned by @p pred,
817 * i.e. if all elements that satisfy @p pred appear before those that
818 * do not.
819 */
823 _Predicate __pred)
824 {
827 }
829 /**
830 * @brief Find the partition point of a partitioned range.
831 * @ingroup mutating_algorithms
832 * @param first An iterator.
833 * @param last Another iterator.
834 * @param pred A predicate.
835 * @return An iterator @p mid such that @p all_of(first, mid, pred)
836 * and @p none_of(mid, last, pred) are both true.
837 */
839 _ForwardIterator
841 _Predicate __pred)
842 {
843 // concept requirements
848 // A specific debug-mode test will be necessary...
852 _DistanceType;
855 _DistanceType __half;
856 _ForwardIterator __middle;
859 {
864 {
868 }
869 else
871 }
873 }
874 #endif
877 /**
878 * @brief Copy a sequence, removing elements of a given value.
879 * @ingroup mutating_algorithms
880 * @param first An input iterator.
881 * @param last An input iterator.
882 * @param result An output iterator.
883 * @param value The value to be removed.
884 * @return An iterator designating the end of the resulting sequence.
885 *
886 * Copies each element in the range @p [first,last) not equal to @p value
887 * to the range beginning at @p result.
888 * remove_copy() is stable, so the relative order of elements that are
889 * copied is unchanged.
890 */
892 _OutputIterator
895 {
896 // concept requirements
906 {
909 }
911 }
913 /**
914 * @brief Copy a sequence, removing elements for which a predicate is true.
915 * @ingroup mutating_algorithms
916 * @param first An input iterator.
917 * @param last An input iterator.
918 * @param result An output iterator.
919 * @param pred A predicate.
920 * @return An iterator designating the end of the resulting sequence.
921 *
922 * Copies each element in the range @p [first,last) for which
923 * @p pred returns false to the range beginning at @p result.
924 *
925 * remove_copy_if() is stable, so the relative order of elements that are
926 * copied is unchanged.
927 */
929 typename _Predicate>
930 _OutputIterator
933 {
934 // concept requirements
944 {
947 }
949 }
951 #ifdef __GXX_EXPERIMENTAL_CXX0X__
952 /**
953 * @brief Copy the elements of a sequence for which a predicate is true.
954 * @ingroup mutating_algorithms
955 * @param first An input iterator.
956 * @param last An input iterator.
957 * @param result An output iterator.
958 * @param pred A predicate.
959 * @return An iterator designating the end of the resulting sequence.
960 *
961 * Copies each element in the range @p [first,last) for which
962 * @p pred returns true to the range beginning at @p result.
963 *
964 * copy_if() is stable, so the relative order of elements that are
965 * copied is unchanged.
966 */
968 typename _Predicate>
969 _OutputIterator
972 {
973 // concept requirements
983 {
986 }
988 }
992 _OutputIterator
995 {
997 {
1001 }
1003 }
1006 typename _OutputIterator>
1007 inline _OutputIterator
1012 /**
1013 * @brief Copies the range [first,first+n) into [result,result+n).
1014 * @ingroup mutating_algorithms
1015 * @param first An input iterator.
1016 * @param n The number of elements to copy.
1017 * @param result An output iterator.
1018 * @return result+n.
1019 *
1020 * This inline function will boil down to a call to @c memmove whenever
1021 * possible. Failing that, if random access iterators are passed, then the
1022 * loop count will be known (and therefore a candidate for compiler
1023 * optimizations such as unrolling).
1024 */
1026 inline _OutputIterator
1028 {
1029 // concept requirements
1036 }
1038 /**
1039 * @brief Copy the elements of a sequence to separate output sequences
1040 * depending on the truth value of a predicate.
1041 * @ingroup mutating_algorithms
1042 * @param first An input iterator.
1043 * @param last An input iterator.
1044 * @param out_true An output iterator.
1045 * @param out_false An output iterator.
1046 * @param pred A predicate.
1047 * @return A pair designating the ends of the resulting sequences.
1048 *
1049 * Copies each element in the range @p [first,last) for which
1050 * @p pred returns true to the range beginning at @p out_true
1051 * and each element for which @p pred returns false to @p out_false.
1052 */
1058 _Predicate __pred)
1059 {
1060 // concept requirements
1072 {
1075 }
1076 else
1077 {
1080 }
1083 }
1084 #endif
1086 /**
1087 * @brief Remove elements from a sequence.
1088 * @ingroup mutating_algorithms
1089 * @param first An input iterator.
1090 * @param last An input iterator.
1091 * @param value The value to be removed.
1092 * @return An iterator designating the end of the resulting sequence.
1093 *
1094 * All elements equal to @p value are removed from the range
1095 * @p [first,last).
1096 *
1097 * remove() is stable, so the relative order of elements that are
1098 * not removed is unchanged.
1099 *
1100 * Elements between the end of the resulting sequence and @p last
1101 * are still present, but their value is unspecified.
1102 */
1104 _ForwardIterator
1107 {
1108 // concept requirements
1110 _ForwardIterator>)
1122 {
1125 }
1127 }
1129 /**
1130 * @brief Remove elements from a sequence using a predicate.
1131 * @ingroup mutating_algorithms
1132 * @param first A forward iterator.
1133 * @param last A forward iterator.
1134 * @param pred A predicate.
1135 * @return An iterator designating the end of the resulting sequence.
1136 *
1137 * All elements for which @p pred returns true are removed from the range
1138 * @p [first,last).
1139 *
1140 * remove_if() is stable, so the relative order of elements that are
1141 * not removed is unchanged.
1142 *
1143 * Elements between the end of the resulting sequence and @p last
1144 * are still present, but their value is unspecified.
1145 */
1147 _ForwardIterator
1149 _Predicate __pred)
1150 {
1151 // concept requirements
1153 _ForwardIterator>)
1165 {
1168 }
1170 }
1172 /**
1173 * @brief Remove consecutive duplicate values from a sequence.
1174 * @ingroup mutating_algorithms
1175 * @param first A forward iterator.
1176 * @param last A forward iterator.
1177 * @return An iterator designating the end of the resulting sequence.
1178 *
1179 * Removes all but the first element from each group of consecutive
1180 * values that compare equal.
1181 * unique() is stable, so the relative order of elements that are
1182 * not removed is unchanged.
1183 * Elements between the end of the resulting sequence and @p last
1184 * are still present, but their value is unspecified.
1185 */
1187 _ForwardIterator
1189 {
1190 // concept requirements
1192 _ForwardIterator>)
1197 // Skip the beginning, if already unique.
1202 // Do the real copy work.
1209 }
1211 /**
1212 * @brief Remove consecutive values from a sequence using a predicate.
1213 * @ingroup mutating_algorithms
1214 * @param first A forward iterator.
1215 * @param last A forward iterator.
1216 * @param binary_pred A binary predicate.
1217 * @return An iterator designating the end of the resulting sequence.
1218 *
1219 * Removes all but the first element from each group of consecutive
1220 * values for which @p binary_pred returns true.
1221 * unique() is stable, so the relative order of elements that are
1222 * not removed is unchanged.
1223 * Elements between the end of the resulting sequence and @p last
1224 * are still present, but their value is unspecified.
1225 */
1227 _ForwardIterator
1229 _BinaryPredicate __binary_pred)
1230 {
1231 // concept requirements
1233 _ForwardIterator>)
1239 // Skip the beginning, if already unique.
1244 // Do the real copy work.
1251 }
1253 /**
1254 * This is an uglified unique_copy(_InputIterator, _InputIterator,
1255 * _OutputIterator)
1256 * overloaded for forward iterators and output iterator as result.
1257 */
1259 _OutputIterator
1261 _OutputIterator __result,
1263 {
1264 // concept requirements -- taken care of in dispatching function
1269 {
1272 }
1274 }
1276 /**
1277 * This is an uglified unique_copy(_InputIterator, _InputIterator,
1278 * _OutputIterator)
1279 * overloaded for input iterators and output iterator as result.
1280 */
1282 _OutputIterator
1284 _OutputIterator __result,
1286 {
1287 // concept requirements -- taken care of in dispatching function
1292 {
1295 }
1297 }
1299 /**
1300 * This is an uglified unique_copy(_InputIterator, _InputIterator,
1301 * _OutputIterator)
1302 * overloaded for input iterators and forward iterator as result.
1303 */
1305 _ForwardIterator
1307 _ForwardIterator __result,
1309 {
1310 // concept requirements -- taken care of in dispatching function
1316 }
1318 /**
1319 * This is an uglified
1320 * unique_copy(_InputIterator, _InputIterator, _OutputIterator,
1321 * _BinaryPredicate)
1322 * overloaded for forward iterators and output iterator as result.
1323 */
1325 typename _BinaryPredicate>
1326 _OutputIterator
1330 {
1331 // concept requirements -- iterators already checked
1340 {
1343 }
1345 }
1347 /**
1348 * This is an uglified
1349 * unique_copy(_InputIterator, _InputIterator, _OutputIterator,
1350 * _BinaryPredicate)
1351 * overloaded for input iterators and output iterator as result.
1352 */
1354 typename _BinaryPredicate>
1355 _OutputIterator
1359 {
1360 // concept requirements -- iterators already checked
1369 {
1372 }
1374 }
1376 /**
1377 * This is an uglified
1378 * unique_copy(_InputIterator, _InputIterator, _OutputIterator,
1379 * _BinaryPredicate)
1380 * overloaded for input iterators and forward iterator as result.
1381 */
1383 typename _BinaryPredicate>
1384 _ForwardIterator
1388 {
1389 // concept requirements -- iterators already checked
1399 }
1401 /**
1402 * This is an uglified reverse(_BidirectionalIterator,
1403 * _BidirectionalIterator)
1404 * overloaded for bidirectional iterators.
1405 */
1407 void
1409 bidirectional_iterator_tag)
1410 {
1414 else
1415 {
1418 }
1419 }
1421 /**
1422 * This is an uglified reverse(_BidirectionalIterator,
1423 * _BidirectionalIterator)
1424 * overloaded for random access iterators.
1425 */
1427 void
1429 random_access_iterator_tag)
1430 {
1435 {
1439 }
1440 }
1442 /**
1443 * @brief Reverse a sequence.
1444 * @ingroup mutating_algorithms
1445 * @param first A bidirectional iterator.
1446 * @param last A bidirectional iterator.
1447 * @return reverse() returns no value.
1448 *
1449 * Reverses the order of the elements in the range @p [first,last),
1450 * so that the first element becomes the last etc.
1451 * For every @c i such that @p 0<=i<=(last-first)/2), @p reverse()
1452 * swaps @p *(first+i) and @p *(last-(i+1))
1453 */
1457 {
1458 // concept requirements
1460 _BidirectionalIterator>)
1463 }
1465 /**
1466 * @brief Copy a sequence, reversing its elements.
1467 * @ingroup mutating_algorithms
1468 * @param first A bidirectional iterator.
1469 * @param last A bidirectional iterator.
1470 * @param result An output iterator.
1471 * @return An iterator designating the end of the resulting sequence.
1472 *
1473 * Copies the elements in the range @p [first,last) to the range
1474 * @p [result,result+(last-first)) such that the order of the
1475 * elements is reversed.
1476 * For every @c i such that @p 0<=i<=(last-first), @p reverse_copy()
1477 * performs the assignment @p *(result+(last-first)-i) = *(first+i).
1478 * The ranges @p [first,last) and @p [result,result+(last-first))
1479 * must not overlap.
1480 */
1482 _OutputIterator
1484 _OutputIterator __result)
1485 {
1486 // concept requirements
1488 _BidirectionalIterator>)
1494 {
1498 }
1500 }
1502 /**
1503 * This is a helper function for the rotate algorithm specialized on RAIs.
1504 * It returns the greatest common divisor of two integer values.
1505 */
1507 _EuclideanRingElement
1509 {
1511 {
1515 }
1517 }
1519 /// This is a helper function for the rotate algorithm.
1521 void
1523 _ForwardIterator __middle,
1524 _ForwardIterator __last,
1525 forward_iterator_tag)
1526 {
1531 do
1532 {
1538 }
1544 {
1552 }
1553 }
1555 /// This is a helper function for the rotate algorithm.
1557 void
1559 _BidirectionalIterator __middle,
1560 _BidirectionalIterator __last,
1561 bidirectional_iterator_tag)
1562 {
1563 // concept requirements
1565 _BidirectionalIterator>)
1574 {
1577 }
1581 else
1583 }
1585 /// This is a helper function for the rotate algorithm.
1587 void
1589 _RandomAccessIterator __middle,
1590 _RandomAccessIterator __last,
1591 random_access_iterator_tag)
1592 {
1593 // concept requirements
1595 _RandomAccessIterator>)
1601 _Distance;
1603 _ValueType;
1610 {
1613 }
1618 {
1623 {
1625 {
1627 {
1630 }
1634 }
1635 }
1636 else
1637 {
1639 {
1641 {
1644 }
1647 }
1648 }
1652 }
1653 }
1655 /**
1656 * @brief Rotate the elements of a sequence.
1657 * @ingroup mutating_algorithms
1658 * @param first A forward iterator.
1659 * @param middle A forward iterator.
1660 * @param last A forward iterator.
1661 * @return Nothing.
1662 *
1663 * Rotates the elements of the range @p [first,last) by @p (middle-first)
1664 * positions so that the element at @p middle is moved to @p first, the
1665 * element at @p middle+1 is moved to @first+1 and so on for each element
1666 * in the range @p [first,last).
1667 *
1668 * This effectively swaps the ranges @p [first,middle) and
1669 * @p [middle,last).
1670 *
1671 * Performs @p *(first+(n+(last-middle))%(last-first))=*(first+n) for
1672 * each @p n in the range @p [0,last-first).
1673 */
1677 _ForwardIterator __last)
1678 {
1679 // concept requirements
1681 _ForwardIterator>)
1686 _IterType;
1688 }
1690 /**
1691 * @brief Copy a sequence, rotating its elements.
1692 * @ingroup mutating_algorithms
1693 * @param first A forward iterator.
1694 * @param middle A forward iterator.
1695 * @param last A forward iterator.
1696 * @param result An output iterator.
1697 * @return An iterator designating the end of the resulting sequence.
1698 *
1699 * Copies the elements of the range @p [first,last) to the range
1700 * beginning at @result, rotating the copied elements by @p (middle-first)
1701 * positions so that the element at @p middle is moved to @p result, the
1702 * element at @p middle+1 is moved to @result+1 and so on for each element
1703 * in the range @p [first,last).
1704 *
1705 * Performs @p *(result+(n+(last-middle))%(last-first))=*(first+n) for
1706 * each @p n in the range @p [0,last-first).
1707 */
1709 _OutputIterator
1712 {
1713 // concept requirements
1722 }
1724 /// This is a helper function...
1726 _ForwardIterator
1729 {
1741 {
1744 }
1747 }
1749 /// This is a helper function...
1751 _BidirectionalIterator
1754 {
1756 {
1762 else
1770 else
1774 }
1775 }
1777 // partition
1779 /// This is a helper function...
1781 _ForwardIterator
1783 _ForwardIterator __last,
1785 {
1791 __middle,
1792 __pred,
1795 __pred,
1796 __len
1801 }
1803 /// This is a helper function...
1805 typename _Distance>
1806 _ForwardIterator
1808 _ForwardIterator __last,
1810 _Pointer __buffer,
1811 _Distance __buffer_size)
1812 {
1814 {
1819 {
1822 }
1823 else
1824 {
1827 }
1830 }
1831 else
1832 {
1835 _ForwardIterator __begin =
1838 __buffer_size);
1839 _ForwardIterator __end =
1846 }
1847 }
1849 /**
1850 * @brief Move elements for which a predicate is true to the beginning
1851 * of a sequence, preserving relative ordering.
1852 * @ingroup mutating_algorithms
1853 * @param first A forward iterator.
1854 * @param last A forward iterator.
1855 * @param pred A predicate functor.
1856 * @return An iterator @p middle such that @p pred(i) is true for each
1857 * iterator @p i in the range @p [first,middle) and false for each @p i
1858 * in the range @p [middle,last).
1859 *
1860 * Performs the same function as @p partition() with the additional
1861 * guarantee that the relative ordering of elements in each group is
1862 * preserved, so any two elements @p x and @p y in the range
1863 * @p [first,last) such that @p pred(x)==pred(y) will have the same
1864 * relative ordering after calling @p stable_partition().
1865 */
1867 _ForwardIterator
1869 _Predicate __pred)
1870 {
1871 // concept requirements
1873 _ForwardIterator>)
1880 else
1881 {
1883 _ValueType;
1885 _DistanceType;
1888 __last);
1890 return
1895 else
1896 return
1899 }
1900 }
1902 /// This is a helper function for the sort routines.
1904 void
1906 _RandomAccessIterator __middle,
1907 _RandomAccessIterator __last)
1908 {
1913 }
1915 /// This is a helper function for the sort routines.
1917 void
1919 _RandomAccessIterator __middle,
1921 {
1926 }
1928 // partial_sort
1930 /**
1931 * @brief Copy the smallest elements of a sequence.
1932 * @ingroup sorting_algorithms
1933 * @param first An iterator.
1934 * @param last Another iterator.
1935 * @param result_first A random-access iterator.
1936 * @param result_last Another random-access iterator.
1937 * @return An iterator indicating the end of the resulting sequence.
1938 *
1939 * Copies and sorts the smallest N values from the range @p [first,last)
1940 * to the range beginning at @p result_first, where the number of
1941 * elements to be copied, @p N, is the smaller of @p (last-first) and
1942 * @p (result_last-result_first).
1943 * After the sort if @p i and @j are iterators in the range
1944 * @p [result_first,result_first+N) such that @i precedes @j then
1945 * @p *j<*i is false.
1946 * The value returned is @p result_first+N.
1947 */
1949 _RandomAccessIterator
1951 _RandomAccessIterator __result_first,
1952 _RandomAccessIterator __result_last)
1953 {
1955 _InputValueType;
1957 _OutputValueType;
1959 _DistanceType;
1961 // concept requirements
1964 _OutputValueType>)
1966 _OutputValueType>)
1975 {
1979 }
1982 {
1989 }
1992 }
1994 /**
1995 * @brief Copy the smallest elements of a sequence using a predicate for
1996 * comparison.
1997 * @ingroup sorting_algorithms
1998 * @param first An input iterator.
1999 * @param last Another input iterator.
2000 * @param result_first A random-access iterator.
2001 * @param result_last Another random-access iterator.
2002 * @param comp A comparison functor.
2003 * @return An iterator indicating the end of the resulting sequence.
2004 *
2005 * Copies and sorts the smallest N values from the range @p [first,last)
2006 * to the range beginning at @p result_first, where the number of
2007 * elements to be copied, @p N, is the smaller of @p (last-first) and
2008 * @p (result_last-result_first).
2009 * After the sort if @p i and @j are iterators in the range
2010 * @p [result_first,result_first+N) such that @i precedes @j then
2011 * @p comp(*j,*i) is false.
2012 * The value returned is @p result_first+N.
2013 */
2015 _RandomAccessIterator
2017 _RandomAccessIterator __result_first,
2018 _RandomAccessIterator __result_last,
2019 _Compare __comp)
2020 {
2022 _InputValueType;
2024 _OutputValueType;
2026 _DistanceType;
2028 // concept requirements
2031 _RandomAccessIterator>)
2033 _OutputValueType>)
2045 {
2049 }
2052 {
2058 __comp);
2060 }
2063 }
2065 /// This is a helper function for the sort routine.
2067 void
2069 {
2073 {
2077 }
2079 }
2081 /// This is a helper function for the sort routine.
2083 void
2085 _Compare __comp)
2086 {
2090 {
2094 }
2096 }
2098 /// This is a helper function for the sort routine.
2100 void
2102 _RandomAccessIterator __last)
2103 {
2108 {
2112 {
2115 }
2116 else
2118 }
2119 }
2121 /// This is a helper function for the sort routine.
2123 void
2126 {
2130 {
2134 {
2137 }
2138 else
2140 }
2141 }
2143 /// This is a helper function for the sort routine.
2147 _RandomAccessIterator __last)
2148 {
2150 _ValueType;
2154 }
2156 /// This is a helper function for the sort routine.
2161 {
2163 _ValueType;
2167 }
2169 /**
2170 * @doctodo
2171 * This controls some aspect of the sort routines.
2172 */
2175 /// This is a helper function for the sort routine.
2177 void
2179 _RandomAccessIterator __last)
2180 {
2182 {
2185 }
2186 else
2188 }
2190 /// This is a helper function for the sort routine.
2192 void
2195 {
2197 {
2200 __comp);
2201 }
2202 else
2204 }
2206 /// This is a helper function...
2208 _RandomAccessIterator
2211 {
2213 {
2223 }
2224 }
2226 /// This is a helper function...
2228 _RandomAccessIterator
2230 _RandomAccessIterator __last,
2232 {
2234 {
2244 }
2245 }
2247 /// This is a helper function for the sort routine.
2249 void
2251 _RandomAccessIterator __last,
2252 _Size __depth_limit)
2253 {
2255 _ValueType;
2258 {
2260 {
2263 }
2265 _RandomAccessIterator __cut =
2268 *(__first
2269 + (__last
2272 *(__last
2276 }
2277 }
2279 /// This is a helper function for the sort routine.
2281 void
2283 _RandomAccessIterator __last,
2285 {
2287 _ValueType;
2290 {
2292 {
2295 }
2297 _RandomAccessIterator __cut =
2300 *(__first
2301 + (__last
2305 __comp)),
2306 __comp);
2309 }
2310 }
2312 /// This is a helper function for the sort routines. Precondition: __n > 0.
2314 inline _Size
2316 {
2317 _Size __k;
2321 }
2335 // sort
2338 void
2341 {
2343 _ValueType;
2346 {
2348 {
2351 // Place the nth largest element in its final position.
2354 }
2356 _RandomAccessIterator __cut =
2359 *(__first
2360 + (__last
2363 *(__last
2367 else
2369 }
2371 }
2374 void
2377 _Compare __comp)
2378 {
2380 _ValueType;
2383 {
2385 {
2387 // Place the nth largest element in its final position.
2390 }
2392 _RandomAccessIterator __cut =
2395 *(__first
2396 + (__last
2400 __comp)),
2401 __comp);
2404 else
2406 }
2408 }
2410 // nth_element
2412 /**
2413 * @brief Finds the first position in which @a val could be inserted
2414 * without changing the ordering.
2415 * @param first An iterator.
2416 * @param last Another iterator.
2417 * @param val The search term.
2418 * @return An iterator pointing to the first element "not less
2419 * than" @a val, or end() if every element is less than
2420 * @a val.
2421 * @ingroup binary_search_algorithms
2422 */
2424 _ForwardIterator
2427 {
2429 _ValueType;
2431 _DistanceType;
2433 // concept requirements
2439 _DistanceType __half;
2440 _ForwardIterator __middle;
2443 {
2448 {
2452 }
2453 else
2455 }
2457 }
2459 /**
2460 * @brief Finds the first position in which @a val could be inserted
2461 * without changing the ordering.
2462 * @ingroup binary_search_algorithms
2463 * @param first An iterator.
2464 * @param last Another iterator.
2465 * @param val The search term.
2466 * @param comp A functor to use for comparisons.
2467 * @return An iterator pointing to the first element "not less than" @a val,
2468 * or end() if every element is less than @a val.
2469 * @ingroup binary_search_algorithms
2470 *
2471 * The comparison function should have the same effects on ordering as
2472 * the function used for the initial sort.
2473 */
2475 _ForwardIterator
2478 {
2480 _ValueType;
2482 _DistanceType;
2484 // concept requirements
2492 _DistanceType __half;
2493 _ForwardIterator __middle;
2496 {
2501 {
2505 }
2506 else
2508 }
2510 }
2512 /**
2513 * @brief Finds the last position in which @a val could be inserted
2514 * without changing the ordering.
2515 * @ingroup binary_search_algorithms
2516 * @param first An iterator.
2517 * @param last Another iterator.
2518 * @param val The search term.
2519 * @return An iterator pointing to the first element greater than @a val,
2520 * or end() if no elements are greater than @a val.
2521 * @ingroup binary_search_algorithms
2522 */
2524 _ForwardIterator
2527 {
2529 _ValueType;
2531 _DistanceType;
2533 // concept requirements
2539 _DistanceType __half;
2540 _ForwardIterator __middle;
2543 {
2549 else
2550 {
2554 }
2555 }
2557 }
2559 /**
2560 * @brief Finds the last position in which @a val could be inserted
2561 * without changing the ordering.
2562 * @ingroup binary_search_algorithms
2563 * @param first An iterator.
2564 * @param last Another iterator.
2565 * @param val The search term.
2566 * @param comp A functor to use for comparisons.
2567 * @return An iterator pointing to the first element greater than @a val,
2568 * or end() if no elements are greater than @a val.
2569 * @ingroup binary_search_algorithms
2570 *
2571 * The comparison function should have the same effects on ordering as
2572 * the function used for the initial sort.
2573 */
2575 _ForwardIterator
2578 {
2580 _ValueType;
2582 _DistanceType;
2584 // concept requirements
2592 _DistanceType __half;
2593 _ForwardIterator __middle;
2596 {
2602 else
2603 {
2607 }
2608 }
2610 }
2612 /**
2613 * @brief Finds the largest subrange in which @a val could be inserted
2614 * at any place in it without changing the ordering.
2615 * @ingroup binary_search_algorithms
2616 * @param first An iterator.
2617 * @param last Another iterator.
2618 * @param val The search term.
2619 * @return An pair of iterators defining the subrange.
2620 * @ingroup binary_search_algorithms
2621 *
2622 * This is equivalent to
2623 * @code
2624 * std::make_pair(lower_bound(first, last, val),
2625 * upper_bound(first, last, val))
2626 * @endcode
2627 * but does not actually call those functions.
2628 */
2633 {
2635 _ValueType;
2637 _DistanceType;
2639 // concept requirements
2647 _DistanceType __half;
2651 {
2656 {
2660 }
2663 else
2664 {
2669 }
2670 }
2672 }
2674 /**
2675 * @brief Finds the largest subrange in which @a val could be inserted
2676 * at any place in it without changing the ordering.
2677 * @param first An iterator.
2678 * @param last Another iterator.
2679 * @param val The search term.
2680 * @param comp A functor to use for comparisons.
2681 * @return An pair of iterators defining the subrange.
2682 * @ingroup binary_search_algorithms
2683 *
2684 * This is equivalent to
2685 * @code
2686 * std::make_pair(lower_bound(first, last, val, comp),
2687 * upper_bound(first, last, val, comp))
2688 * @endcode
2689 * but does not actually call those functions.
2690 */
2695 _Compare __comp)
2696 {
2698 _ValueType;
2700 _DistanceType;
2702 // concept requirements
2714 _DistanceType __half;
2718 {
2723 {
2727 }
2730 else
2731 {
2736 }
2737 }
2739 }
2741 /**
2742 * @brief Determines whether an element exists in a range.
2743 * @ingroup binary_search_algorithms
2744 * @param first An iterator.
2745 * @param last Another iterator.
2746 * @param val The search term.
2747 * @return True if @a val (or its equivalent) is in [@a first,@a last ].
2748 *
2749 * Note that this does not actually return an iterator to @a val. For
2750 * that, use std::find or a container's specialized find member functions.
2751 */
2753 bool
2756 {
2758 _ValueType;
2760 // concept requirements
2768 }
2770 /**
2771 * @brief Determines whether an element exists in a range.
2772 * @ingroup binary_search_algorithms
2773 * @param first An iterator.
2774 * @param last Another iterator.
2775 * @param val The search term.
2776 * @param comp A functor to use for comparisons.
2777 * @return True if @a val (or its equivalent) is in [@a first,@a last ].
2778 *
2779 * Note that this does not actually return an iterator to @a val. For
2780 * that, use std::find or a container's specialized find member functions.
2781 *
2782 * The comparison function should have the same effects on ordering as
2783 * the function used for the initial sort.
2784 */
2786 bool
2789 {
2791 _ValueType;
2793 // concept requirements
2804 }
2806 // merge
2808 /// This is a helper function for the merge routines.
2810 typename _BidirectionalIterator3>
2811 _BidirectionalIterator3
2813 _BidirectionalIterator1 __last1,
2814 _BidirectionalIterator2 __first2,
2815 _BidirectionalIterator2 __last2,
2816 _BidirectionalIterator3 __result)
2817 {
2825 {
2827 {
2832 }
2833 else
2834 {
2839 }
2840 }
2841 }
2843 /// This is a helper function for the merge routines.
2846 _BidirectionalIterator3
2848 _BidirectionalIterator1 __last1,
2849 _BidirectionalIterator2 __first2,
2850 _BidirectionalIterator2 __last2,
2851 _BidirectionalIterator3 __result,
2852 _Compare __comp)
2853 {
2861 {
2863 {
2868 }
2869 else
2870 {
2875 }
2876 }
2877 }
2879 /// This is a helper function for the merge routines.
2881 typename _Distance>
2882 _BidirectionalIterator1
2884 _BidirectionalIterator1 __middle,
2885 _BidirectionalIterator1 __last,
2887 _BidirectionalIterator2 __buffer,
2888 _Distance __buffer_size)
2889 {
2890 _BidirectionalIterator2 __buffer_end;
2892 {
2896 }
2898 {
2902 }
2903 else
2904 {
2908 }
2909 }
2911 /// This is a helper function for the merge routines.
2913 typename _Pointer>
2914 void
2916 _BidirectionalIterator __middle,
2917 _BidirectionalIterator __last,
2920 {
2922 {
2925 __first);
2926 }
2928 {
2932 }
2933 else
2934 {
2940 {
2946 }
2947 else
2948 {
2954 }
2955 _BidirectionalIterator __new_middle =
2958 __buffer_size);
2964 }
2965 }
2967 /// This is a helper function for the merge routines.
2970 void
2972 _BidirectionalIterator __middle,
2973 _BidirectionalIterator __last,
2976 _Compare __comp)
2977 {
2979 {
2983 }
2985 {
2989 }
2990 else
2991 {
2997 {
3001 __comp);
3003 }
3004 else
3005 {
3009 __comp);
3011 }
3012 _BidirectionalIterator __new_middle =
3015 __buffer_size);
3022 }
3023 }
3025 /// This is a helper function for the merge routines.
3027 void
3029 _BidirectionalIterator __middle,
3030 _BidirectionalIterator __last,
3032 {
3036 {
3040 }
3046 {
3051 }
3052 else
3053 {
3058 }
3066 }
3068 /// This is a helper function for the merge routines.
3070 typename _Compare>
3071 void
3073 _BidirectionalIterator __middle,
3074 _BidirectionalIterator __last,
3076 _Compare __comp)
3077 {
3081 {
3085 }
3091 {
3095 __comp);
3097 }
3098 else
3099 {
3103 __comp);
3105 }
3113 }
3115 /**
3116 * @brief Merges two sorted ranges in place.
3117 * @ingroup sorting_algorithms
3118 * @param first An iterator.
3119 * @param middle Another iterator.
3120 * @param last Another iterator.
3121 * @return Nothing.
3122 *
3123 * Merges two sorted and consecutive ranges, [first,middle) and
3124 * [middle,last), and puts the result in [first,last). The output will
3125 * be sorted. The sort is @e stable, that is, for equivalent
3126 * elements in the two ranges, elements from the first range will always
3127 * come before elements from the second.
3128 *
3129 * If enough additional memory is available, this takes (last-first)-1
3130 * comparisons. Otherwise an NlogN algorithm is used, where N is
3131 * distance(first,last).
3132 */
3134 void
3136 _BidirectionalIterator __middle,
3137 _BidirectionalIterator __last)
3138 {
3140 _ValueType;
3142 _DistanceType;
3144 // concept requirements
3146 _BidirectionalIterator>)
3158 __last);
3161 else
3164 }
3166 /**
3167 * @brief Merges two sorted ranges in place.
3168 * @ingroup sorting_algorithms
3169 * @param first An iterator.
3170 * @param middle Another iterator.
3171 * @param last Another iterator.
3172 * @param comp A functor to use for comparisons.
3173 * @return Nothing.
3174 *
3175 * Merges two sorted and consecutive ranges, [first,middle) and
3176 * [middle,last), and puts the result in [first,last). The output will
3177 * be sorted. The sort is @e stable, that is, for equivalent
3178 * elements in the two ranges, elements from the first range will always
3179 * come before elements from the second.
3180 *
3181 * If enough additional memory is available, this takes (last-first)-1
3182 * comparisons. Otherwise an NlogN algorithm is used, where N is
3183 * distance(first,last).
3184 *
3185 * The comparison function should have the same effects on ordering as
3186 * the function used for the initial sort.
3187 */
3189 void
3191 _BidirectionalIterator __middle,
3192 _BidirectionalIterator __last,
3193 _Compare __comp)
3194 {
3196 _ValueType;
3198 _DistanceType;
3200 // concept requirements
3202 _BidirectionalIterator>)
3215 __last);
3219 else
3222 __comp);
3223 }
3226 typename _Distance>
3227 void
3229 _RandomAccessIterator1 __last,
3230 _RandomAccessIterator2 __result,
3231 _Distance __step_size)
3232 {
3236 {
3240 __result);
3242 }
3247 __result);
3248 }
3252 void
3254 _RandomAccessIterator1 __last,
3256 _Compare __comp)
3257 {
3261 {
3264 __result,
3265 __comp);
3267 }
3272 }
3275 void
3277 _RandomAccessIterator __last,
3278 _Distance __chunk_size)
3279 {
3281 {
3284 }
3286 }
3289 typename _Compare>
3290 void
3292 _RandomAccessIterator __last,
3294 {
3296 {
3299 }
3301 }
3306 void
3308 _RandomAccessIterator __last,
3309 _Pointer __buffer)
3310 {
3312 _Distance;
3321 {
3326 }
3327 }
3330 void
3332 _RandomAccessIterator __last,
3334 {
3336 _Distance;
3345 {
3352 }
3353 }
3356 typename _Distance>
3357 void
3359 _RandomAccessIterator __last,
3361 {
3365 {
3370 }
3371 else
3372 {
3375 }
3380 }
3384 void
3386 _RandomAccessIterator __last,
3388 _Compare __comp)
3389 {
3393 {
3398 }
3399 else
3400 {
3403 }
3408 __comp);
3409 }
3411 /// This is a helper function for the stable sorting routines.
3413 void
3415 _RandomAccessIterator __last)
3416 {
3418 {
3421 }
3428 }
3430 /// This is a helper function for the stable sorting routines.
3432 void
3435 {
3437 {
3440 }
3447 __comp);
3448 }
3450 // stable_sort
3452 // Set algorithms: includes, set_union, set_intersection, set_difference,
3453 // set_symmetric_difference. All of these algorithms have the precondition
3454 // that their input ranges are sorted and the postcondition that their output
3455 // ranges are sorted.
3457 /**
3458 * @brief Determines whether all elements of a sequence exists in a range.
3459 * @param first1 Start of search range.
3460 * @param last1 End of search range.
3461 * @param first2 Start of sequence
3462 * @param last2 End of sequence.
3463 * @return True if each element in [first2,last2) is contained in order
3464 * within [first1,last1). False otherwise.
3465 * @ingroup set_algorithms
3466 *
3467 * This operation expects both [first1,last1) and [first2,last2) to be
3468 * sorted. Searches for the presence of each element in [first2,last2)
3469 * within [first1,last1). The iterators over each range only move forward,
3470 * so this is a linear algorithm. If an element in [first2,last2) is not
3471 * found before the search iterator reaches @a last2, false is returned.
3472 */
3474 bool
3477 {
3479 _ValueType1;
3481 _ValueType2;
3483 // concept requirements
3496 else
3500 }
3502 /**
3503 * @brief Determines whether all elements of a sequence exists in a range
3504 * using comparison.
3505 * @ingroup set_algorithms
3506 * @param first1 Start of search range.
3507 * @param last1 End of search range.
3508 * @param first2 Start of sequence
3509 * @param last2 End of sequence.
3510 * @param comp Comparison function to use.
3511 * @return True if each element in [first2,last2) is contained in order
3512 * within [first1,last1) according to comp. False otherwise.
3513 * @ingroup set_algorithms
3514 *
3515 * This operation expects both [first1,last1) and [first2,last2) to be
3516 * sorted. Searches for the presence of each element in [first2,last2)
3517 * within [first1,last1), using comp to decide. The iterators over each
3518 * range only move forward, so this is a linear algorithm. If an element
3519 * in [first2,last2) is not found before the search iterator reaches @a
3520 * last2, false is returned.
3521 */
3523 typename _Compare>
3524 bool
3527 _Compare __comp)
3528 {
3530 _ValueType1;
3532 _ValueType2;
3534 // concept requirements
3549 else
3553 }
3555 // nth_element
3556 // merge
3557 // set_difference
3558 // set_intersection
3559 // set_union
3560 // stable_sort
3561 // set_symmetric_difference
3562 // min_element
3563 // max_element
3565 /**
3566 * @brief Permute range into the next "dictionary" ordering.
3567 * @ingroup sorting_algorithms
3568 * @param first Start of range.
3569 * @param last End of range.
3570 * @return False if wrapped to first permutation, true otherwise.
3571 *
3572 * Treats all permutations of the range as a set of "dictionary" sorted
3573 * sequences. Permutes the current sequence into the next one of this set.
3574 * Returns true if there are more sequences to generate. If the sequence
3575 * is the largest of the set, the smallest is generated and false returned.
3576 */
3578 bool
3580 _BidirectionalIterator __last)
3581 {
3582 // concept requirements
3584 _BidirectionalIterator>)
3599 {
3603 {
3606 {}
3610 }
3612 {
3615 }
3616 }
3617 }
3619 /**
3620 * @brief Permute range into the next "dictionary" ordering using
3621 * comparison functor.
3622 * @ingroup sorting_algorithms
3623 * @param first Start of range.
3624 * @param last End of range.
3625 * @param comp A comparison functor.
3626 * @return False if wrapped to first permutation, true otherwise.
3627 *
3628 * Treats all permutations of the range [first,last) as a set of
3629 * "dictionary" sorted sequences ordered by @a comp. Permutes the current
3630 * sequence into the next one of this set. Returns true if there are more
3631 * sequences to generate. If the sequence is the largest of the set, the
3632 * smallest is generated and false returned.
3633 */
3635 bool
3638 {
3639 // concept requirements
3641 _BidirectionalIterator>)
3657 {
3661 {
3664 {}
3668 }
3670 {
3673 }
3674 }
3675 }
3677 /**
3678 * @brief Permute range into the previous "dictionary" ordering.
3679 * @ingroup sorting_algorithms
3680 * @param first Start of range.
3681 * @param last End of range.
3682 * @return False if wrapped to last permutation, true otherwise.
3683 *
3684 * Treats all permutations of the range as a set of "dictionary" sorted
3685 * sequences. Permutes the current sequence into the previous one of this
3686 * set. Returns true if there are more sequences to generate. If the
3687 * sequence is the smallest of the set, the largest is generated and false
3688 * returned.
3689 */
3691 bool
3693 _BidirectionalIterator __last)
3694 {
3695 // concept requirements
3697 _BidirectionalIterator>)
3712 {
3716 {
3719 {}
3723 }
3725 {
3728 }
3729 }
3730 }
3732 /**
3733 * @brief Permute range into the previous "dictionary" ordering using
3734 * comparison functor.
3735 * @ingroup sorting_algorithms
3736 * @param first Start of range.
3737 * @param last End of range.
3738 * @param comp A comparison functor.
3739 * @return False if wrapped to last permutation, true otherwise.
3740 *
3741 * Treats all permutations of the range [first,last) as a set of
3742 * "dictionary" sorted sequences ordered by @a comp. Permutes the current
3743 * sequence into the previous one of this set. Returns true if there are
3744 * more sequences to generate. If the sequence is the smallest of the set,
3745 * the largest is generated and false returned.
3746 */
3748 bool
3751 {
3752 // concept requirements
3754 _BidirectionalIterator>)
3770 {
3774 {
3777 {}
3781 }
3783 {
3786 }
3787 }
3788 }
3790 // replace
3791 // replace_if
3793 /**
3794 * @brief Copy a sequence, replacing each element of one value with another
3795 * value.
3796 * @param first An input iterator.
3797 * @param last An input iterator.
3798 * @param result An output iterator.
3799 * @param old_value The value to be replaced.
3800 * @param new_value The replacement value.
3801 * @return The end of the output sequence, @p result+(last-first).
3802 *
3803 * Copies each element in the input range @p [first,last) to the
3804 * output range @p [result,result+(last-first)) replacing elements
3805 * equal to @p old_value with @p new_value.
3806 */
3808 _OutputIterator
3810 _OutputIterator __result,
3812 {
3813 // concept requirements
3824 else
3827 }
3829 /**
3830 * @brief Copy a sequence, replacing each value for which a predicate
3831 * returns true with another value.
3832 * @ingroup mutating_algorithms
3833 * @param first An input iterator.
3834 * @param last An input iterator.
3835 * @param result An output iterator.
3836 * @param pred A predicate.
3837 * @param new_value The replacement value.
3838 * @return The end of the output sequence, @p result+(last-first).
3839 *
3840 * Copies each element in the range @p [first,last) to the range
3841 * @p [result,result+(last-first)) replacing elements for which
3842 * @p pred returns true with @p new_value.
3843 */
3846 _OutputIterator
3848 _OutputIterator __result,
3850 {
3851 // concept requirements
3862 else
3865 }
3867 #ifdef __GXX_EXPERIMENTAL_CXX0X__
3868 /**
3869 * @brief Determines whether the elements of a sequence are sorted.
3870 * @ingroup sorting_algorithms
3871 * @param first An iterator.
3872 * @param last Another iterator.
3873 * @return True if the elements are sorted, false otherwise.
3874 */
3880 /**
3881 * @brief Determines whether the elements of a sequence are sorted
3882 * according to a comparison functor.
3883 * @ingroup sorting_algorithms
3884 * @param first An iterator.
3885 * @param last Another iterator.
3886 * @param comp A comparison functor.
3887 * @return True if the elements are sorted, false otherwise.
3888 */
3892 _Compare __comp)
3895 /**
3896 * @brief Determines the end of a sorted sequence.
3897 * @ingroup sorting_algorithms
3898 * @param first An iterator.
3899 * @param last Another iterator.
3900 * @return An iterator pointing to the last iterator i in [first, last)
3901 * for which the range [first, i) is sorted.
3902 */
3904 _ForwardIterator
3906 {
3907 // concept requirements
3921 }
3923 /**
3924 * @brief Determines the end of a sorted sequence using comparison functor.
3925 * @ingroup sorting_algorithms
3926 * @param first An iterator.
3927 * @param last Another iterator.
3928 * @param comp A comparison functor.
3929 * @return An iterator pointing to the last iterator i in [first, last)
3930 * for which the range [first, i) is sorted.
3931 */
3933 _ForwardIterator
3935 _Compare __comp)
3936 {
3937 // concept requirements
3952 }
3954 /**
3955 * @brief Determines min and max at once as an ordered pair.
3956 * @ingroup sorting_algorithms
3957 * @param a A thing of arbitrary type.
3958 * @param b Another thing of arbitrary type.
3959 * @return A pair(b, a) if b is smaller than a, pair(a, b) otherwise.
3960 */
3964 {
3965 // concept requirements
3970 }
3972 /**
3973 * @brief Determines min and max at once as an ordered pair.
3974 * @ingroup sorting_algorithms
3975 * @param a A thing of arbitrary type.
3976 * @param b Another thing of arbitrary type.
3977 * @param comp A @link comparison_functor comparison functor@endlink.
3978 * @return A pair(b, a) if b is smaller than a, pair(a, b) otherwise.
3979 */
3983 {
3986 }
3988 /**
3989 * @brief Return a pair of iterators pointing to the minimum and maximum
3990 * elements in a range.
3991 * @ingroup sorting_algorithms
3992 * @param first Start of range.
3993 * @param last End of range.
3994 * @return make_pair(m, M), where m is the first iterator i in
3995 * [first, last) such that no other element in the range is
3996 * smaller, and where M is the last iterator i in [first, last)
3997 * such that no other element in the range is larger.
3998 */
4002 {
4003 // concept requirements
4016 {
4019 }
4020 else
4021 {
4024 }
4030 {
4033 {
4039 }
4042 {
4047 }
4048 else
4049 {
4054 }
4058 }
4061 }
4063 /**
4064 * @brief Return a pair of iterators pointing to the minimum and maximum
4065 * elements in a range.
4066 * @ingroup sorting_algorithms
4067 * @param first Start of range.
4068 * @param last End of range.
4069 * @param comp Comparison functor.
4070 * @return make_pair(m, M), where m is the first iterator i in
4071 * [first, last) such that no other element in the range is
4072 * smaller, and where M is the last iterator i in [first, last)
4073 * such that no other element in the range is larger.
4074 */
4078 _Compare __comp)
4079 {
4080 // concept requirements
4094 {
4097 }
4098 else
4099 {
4102 }
4108 {
4111 {
4117 }
4120 {
4125 }
4126 else
4127 {
4132 }
4136 }
4139 }
4141 // N2722 + fixes.
4143 inline _Tp
4148 inline _Tp
4153 inline _Tp
4158 inline _Tp
4165 {
4169 }
4174 {
4178 }
4181 _GLIBCXX_END_NAMESPACE
4185 /**
4186 * @brief Apply a function to every element of a sequence.
4187 * @ingroup non_mutating_algorithms
4188 * @param first An input iterator.
4189 * @param last An input iterator.
4190 * @param f A unary function object.
4191 * @return @p f.
4192 *
4193 * Applies the function object @p f to each element in the range
4194 * @p [first,last). @p f must not modify the order of the sequence.
4195 * If @p f has a return value it is ignored.
4196 */
4198 _Function
4200 {
4201 // concept requirements
4207 }
4209 /**
4210 * @brief Find the first occurrence of a value in a sequence.
4211 * @ingroup non_mutating_algorithms
4212 * @param first An input iterator.
4213 * @param last An input iterator.
4214 * @param val The value to find.
4215 * @return The first iterator @c i in the range @p [first,last)
4216 * such that @c *i == @p val, or @p last if no such iterator exists.
4217 */
4219 inline _InputIterator
4222 {
4223 // concept requirements
4230 }
4232 /**
4233 * @brief Find the first element in a sequence for which a
4234 * predicate is true.
4235 * @ingroup non_mutating_algorithms
4236 * @param first An input iterator.
4237 * @param last An input iterator.
4238 * @param pred A predicate.
4239 * @return The first iterator @c i in the range @p [first,last)
4240 * such that @p pred(*i) is true, or @p last if no such iterator exists.
4241 */
4243 inline _InputIterator
4245 _Predicate __pred)
4246 {
4247 // concept requirements
4254 }
4256 /**
4257 * @brief Find element from a set in a sequence.
4258 * @ingroup non_mutating_algorithms
4259 * @param first1 Start of range to search.
4260 * @param last1 End of range to search.
4261 * @param first2 Start of match candidates.
4262 * @param last2 End of match candidates.
4263 * @return The first iterator @c i in the range
4264 * @p [first1,last1) such that @c *i == @p *(i2) such that i2 is an
4265 * iterator in [first2,last2), or @p last1 if no such iterator exists.
4266 *
4267 * Searches the range @p [first1,last1) for an element that is equal to
4268 * some element in the range [first2,last2). If found, returns an iterator
4269 * in the range [first1,last1), otherwise returns @p last1.
4270 */
4272 _InputIterator
4275 {
4276 // concept requirements
4290 }
4292 /**
4293 * @brief Find element from a set in a sequence using a predicate.
4294 * @ingroup non_mutating_algorithms
4295 * @param first1 Start of range to search.
4296 * @param last1 End of range to search.
4297 * @param first2 Start of match candidates.
4298 * @param last2 End of match candidates.
4299 * @param comp Predicate to use.
4300 * @return The first iterator @c i in the range
4301 * @p [first1,last1) such that @c comp(*i, @p *(i2)) is true and i2 is an
4302 * iterator in [first2,last2), or @p last1 if no such iterator exists.
4303 *
4305 * Searches the range @p [first1,last1) for an element that is
4306 * equal to some element in the range [first2,last2). If found,
4307 * returns an iterator in the range [first1,last1), otherwise
4308 * returns @p last1.
4309 */
4311 typename _BinaryPredicate>
4312 _InputIterator
4315 _BinaryPredicate __comp)
4316 {
4317 // concept requirements
4331 }
4333 /**
4334 * @brief Find two adjacent values in a sequence that are equal.
4335 * @ingroup non_mutating_algorithms
4336 * @param first A forward iterator.
4337 * @param last A forward iterator.
4338 * @return The first iterator @c i such that @c i and @c i+1 are both
4339 * valid iterators in @p [first,last) and such that @c *i == @c *(i+1),
4340 * or @p last if no such iterator exists.
4341 */
4343 _ForwardIterator
4345 {
4346 // concept requirements
4355 {
4359 }
4361 }
4363 /**
4364 * @brief Find two adjacent values in a sequence using a predicate.
4365 * @ingroup non_mutating_algorithms
4366 * @param first A forward iterator.
4367 * @param last A forward iterator.
4368 * @param binary_pred A binary predicate.
4369 * @return The first iterator @c i such that @c i and @c i+1 are both
4370 * valid iterators in @p [first,last) and such that
4371 * @p binary_pred(*i,*(i+1)) is true, or @p last if no such iterator
4372 * exists.
4373 */
4375 _ForwardIterator
4377 _BinaryPredicate __binary_pred)
4378 {
4379 // concept requirements
4389 {
4393 }
4395 }
4397 /**
4398 * @brief Count the number of copies of a value in a sequence.
4399 * @ingroup non_mutating_algorithms
4400 * @param first An input iterator.
4401 * @param last An input iterator.
4402 * @param value The value to be counted.
4403 * @return The number of iterators @c i in the range @p [first,last)
4404 * for which @c *i == @p value
4405 */
4409 {
4410 // concept requirements
4420 }
4422 /**
4423 * @brief Count the elements of a sequence for which a predicate is true.
4424 * @ingroup non_mutating_algorithms
4425 * @param first An input iterator.
4426 * @param last An input iterator.
4427 * @param pred A predicate.
4428 * @return The number of iterators @c i in the range @p [first,last)
4429 * for which @p pred(*i) is true.
4430 */
4434 {
4435 // concept requirements
4445 }
4447 /**
4448 * @brief Search a sequence for a matching sub-sequence.
4449 * @ingroup non_mutating_algorithms
4450 * @param first1 A forward iterator.
4451 * @param last1 A forward iterator.
4452 * @param first2 A forward iterator.
4453 * @param last2 A forward iterator.
4454 * @return The first iterator @c i in the range
4455 * @p [first1,last1-(last2-first2)) such that @c *(i+N) == @p *(first2+N)
4456 * for each @c N in the range @p [0,last2-first2), or @p last1 if no
4457 * such iterator exists.
4458 *
4459 * Searches the range @p [first1,last1) for a sub-sequence that compares
4460 * equal value-by-value with the sequence given by @p [first2,last2) and
4461 * returns an iterator to the first element of the sub-sequence, or
4462 * @p last1 if the sub-sequence is not found.
4463 *
4464 * Because the sub-sequence must lie completely within the range
4465 * @p [first1,last1) it must start at a position less than
4466 * @p last1-(last2-first2) where @p last2-first2 is the length of the
4467 * sub-sequence.
4468 * This means that the returned iterator @c i will be in the range
4469 * @p [first1,last1-(last2-first2))
4470 */
4472 _ForwardIterator1
4475 {
4476 // concept requirements
4485 // Test for empty ranges
4489 // Test for a pattern of length 1.
4494 // General case.
4495 _ForwardIterator2 __p;
4499 {
4510 {
4515 }
4517 }
4519 }
4521 /**
4522 * @brief Search a sequence for a matching sub-sequence using a predicate.
4523 * @ingroup non_mutating_algorithms
4524 * @param first1 A forward iterator.
4525 * @param last1 A forward iterator.
4526 * @param first2 A forward iterator.
4527 * @param last2 A forward iterator.
4528 * @param predicate A binary predicate.
4529 * @return The first iterator @c i in the range
4530 * @p [first1,last1-(last2-first2)) such that
4531 * @p predicate(*(i+N),*(first2+N)) is true for each @c N in the range
4532 * @p [0,last2-first2), or @p last1 if no such iterator exists.
4533 *
4534 * Searches the range @p [first1,last1) for a sub-sequence that compares
4535 * equal value-by-value with the sequence given by @p [first2,last2),
4536 * using @p predicate to determine equality, and returns an iterator
4537 * to the first element of the sub-sequence, or @p last1 if no such
4538 * iterator exists.
4539 *
4540 * @see search(_ForwardIter1, _ForwardIter1, _ForwardIter2, _ForwardIter2)
4541 */
4543 typename _BinaryPredicate>
4544 _ForwardIterator1
4547 _BinaryPredicate __predicate)
4548 {
4549 // concept requirements
4558 // Test for empty ranges
4562 // Test for a pattern of length 1.
4565 {
4570 }
4572 // General case.
4573 _ForwardIterator2 __p;
4577 {
4590 {
4595 }
4597 }
4599 }
4602 /**
4603 * @brief Search a sequence for a number of consecutive values.
4604 * @ingroup non_mutating_algorithms
4605 * @param first A forward iterator.
4606 * @param last A forward iterator.
4607 * @param count The number of consecutive values.
4608 * @param val The value to find.
4609 * @return The first iterator @c i in the range @p [first,last-count)
4610 * such that @c *(i+N) == @p val for each @c N in the range @p [0,count),
4611 * or @p last if no such iterator exists.
4612 *
4613 * Searches the range @p [first,last) for @p count consecutive elements
4614 * equal to @p val.
4615 */
4617 _ForwardIterator
4620 {
4621 // concept requirements
4633 }
4636 /**
4637 * @brief Search a sequence for a number of consecutive values using a
4638 * predicate.
4639 * @ingroup non_mutating_algorithms
4640 * @param first A forward iterator.
4641 * @param last A forward iterator.
4642 * @param count The number of consecutive values.
4643 * @param val The value to find.
4644 * @param binary_pred A binary predicate.
4645 * @return The first iterator @c i in the range @p [first,last-count)
4646 * such that @p binary_pred(*(i+N),val) is true for each @c N in the
4647 * range @p [0,count), or @p last if no such iterator exists.
4648 *
4649 * Searches the range @p [first,last) for @p count consecutive elements
4650 * for which the predicate returns true.
4651 */
4653 typename _BinaryPredicate>
4654 _ForwardIterator
4657 _BinaryPredicate __binary_pred)
4658 {
4659 // concept requirements
4668 {
4672 }
4675 }
4678 /**
4679 * @brief Perform an operation on a sequence.
4680 * @ingroup mutating_algorithms
4681 * @param first An input iterator.
4682 * @param last An input iterator.
4683 * @param result An output iterator.
4684 * @param unary_op A unary operator.
4685 * @return An output iterator equal to @p result+(last-first).
4686 *
4687 * Applies the operator to each element in the input range and assigns
4688 * the results to successive elements of the output sequence.
4689 * Evaluates @p *(result+N)=unary_op(*(first+N)) for each @c N in the
4690 * range @p [0,last-first).
4691 *
4692 * @p unary_op must not alter its argument.
4693 */
4695 typename _UnaryOperation>
4696 _OutputIterator
4699 {
4700 // concept requirements
4703 // "the type returned by a _UnaryOperation"
4710 }
4712 /**
4713 * @brief Perform an operation on corresponding elements of two sequences.
4714 * @ingroup mutating_algorithms
4715 * @param first1 An input iterator.
4716 * @param last1 An input iterator.
4717 * @param first2 An input iterator.
4718 * @param result An output iterator.
4719 * @param binary_op A binary operator.
4720 * @return An output iterator equal to @p result+(last-first).
4721 *
4722 * Applies the operator to the corresponding elements in the two
4723 * input ranges and assigns the results to successive elements of the
4724 * output sequence.
4725 * Evaluates @p *(result+N)=binary_op(*(first1+N),*(first2+N)) for each
4726 * @c N in the range @p [0,last1-first1).
4727 *
4728 * @p binary_op must not alter either of its arguments.
4729 */
4732 _OutputIterator
4735 _BinaryOperation __binary_op)
4736 {
4737 // concept requirements
4741 // "the type returned by a _BinaryOperation"
4748 }
4750 /**
4751 * @brief Replace each occurrence of one value in a sequence with another
4752 * value.
4753 * @ingroup mutating_algorithms
4754 * @param first A forward iterator.
4755 * @param last A forward iterator.
4756 * @param old_value The value to be replaced.
4757 * @param new_value The replacement value.
4758 * @return replace() returns no value.
4759 *
4760 * For each iterator @c i in the range @p [first,last) if @c *i ==
4761 * @p old_value then the assignment @c *i = @p new_value is performed.
4762 */
4764 void
4767 {
4768 // concept requirements
4770 _ForwardIterator>)
4780 }
4782 /**
4783 * @brief Replace each value in a sequence for which a predicate returns
4784 * true with another value.
4785 * @ingroup mutating_algorithms
4786 * @param first A forward iterator.
4787 * @param last A forward iterator.
4788 * @param pred A predicate.
4789 * @param new_value The replacement value.
4790 * @return replace_if() returns no value.
4791 *
4792 * For each iterator @c i in the range @p [first,last) if @p pred(*i)
4793 * is true then the assignment @c *i = @p new_value is performed.
4794 */
4796 void
4799 {
4800 // concept requirements
4802 _ForwardIterator>)
4812 }
4814 /**
4815 * @brief Assign the result of a function object to each value in a
4816 * sequence.
4817 * @ingroup mutating_algorithms
4818 * @param first A forward iterator.
4819 * @param last A forward iterator.
4820 * @param gen A function object taking no arguments and returning
4821 * std::iterator_traits<_ForwardIterator>::value_type
4822 * @return generate() returns no value.
4823 *
4824 * Performs the assignment @c *i = @p gen() for each @c i in the range
4825 * @p [first,last).
4826 */
4828 void
4830 _Generator __gen)
4831 {
4832 // concept requirements
4840 }
4842 /**
4843 * @brief Assign the result of a function object to each value in a
4844 * sequence.
4845 * @ingroup mutating_algorithms
4846 * @param first A forward iterator.
4847 * @param n The length of the sequence.
4848 * @param gen A function object taking no arguments and returning
4849 * std::iterator_traits<_ForwardIterator>::value_type
4850 * @return The end of the sequence, @p first+n
4851 *
4852 * Performs the assignment @c *i = @p gen() for each @c i in the range
4853 * @p [first,first+n).
4854 */
4856 _OutputIterator
4858 {
4859 // concept requirements
4861 // "the type returned by a _Generator"
4867 }
4870 /**
4871 * @brief Copy a sequence, removing consecutive duplicate values.
4872 * @ingroup mutating_algorithms
4873 * @param first An input iterator.
4874 * @param last An input iterator.
4875 * @param result An output iterator.
4876 * @return An iterator designating the end of the resulting sequence.
4877 *
4878 * Copies each element in the range @p [first,last) to the range
4879 * beginning at @p result, except that only the first element is copied
4880 * from groups of consecutive elements that compare equal.
4881 * unique_copy() is stable, so the relative order of elements that are
4882 * copied is unchanged.
4883 *
4884 * _GLIBCXX_RESOLVE_LIB_DEFECTS
4885 * DR 241. Does unique_copy() require CopyConstructible and Assignable?
4886 *
4887 * _GLIBCXX_RESOLVE_LIB_DEFECTS
4888 * DR 538. 241 again: Does unique_copy() require CopyConstructible and
4889 * Assignable?
4890 */
4892 inline _OutputIterator
4894 _OutputIterator __result)
4895 {
4896 // concept requirements
4909 }
4911 /**
4912 * @brief Copy a sequence, removing consecutive values using a predicate.
4913 * @ingroup mutating_algorithms
4914 * @param first An input iterator.
4915 * @param last An input iterator.
4916 * @param result An output iterator.
4917 * @param binary_pred A binary predicate.
4918 * @return An iterator designating the end of the resulting sequence.
4919 *
4920 * Copies each element in the range @p [first,last) to the range
4921 * beginning at @p result, except that only the first element is copied
4922 * from groups of consecutive elements for which @p binary_pred returns
4923 * true.
4924 * unique_copy() is stable, so the relative order of elements that are
4925 * copied is unchanged.
4926 *
4927 * _GLIBCXX_RESOLVE_LIB_DEFECTS
4928 * DR 241. Does unique_copy() require CopyConstructible and Assignable?
4929 */
4931 typename _BinaryPredicate>
4932 inline _OutputIterator
4934 _OutputIterator __result,
4935 _BinaryPredicate __binary_pred)
4936 {
4937 // concept requirements -- predicates checked later
4948 }
4951 /**
4952 * @brief Randomly shuffle the elements of a sequence.
4953 * @ingroup mutating_algorithms
4954 * @param first A forward iterator.
4955 * @param last A forward iterator.
4956 * @return Nothing.
4957 *
4958 * Reorder the elements in the range @p [first,last) using a random
4959 * distribution, so that every possible ordering of the sequence is
4960 * equally likely.
4961 */
4965 {
4966 // concept requirements
4968 _RandomAccessIterator>)
4974 }
4976 /**
4977 * @brief Shuffle the elements of a sequence using a random number
4978 * generator.
4979 * @ingroup mutating_algorithms
4980 * @param first A forward iterator.
4981 * @param last A forward iterator.
4982 * @param rand The RNG functor or function.
4983 * @return Nothing.
4984 *
4985 * Reorders the elements in the range @p [first,last) using @p rand to
4986 * provide a random distribution. Calling @p rand(N) for a positive
4987 * integer @p N should return a randomly chosen integer from the
4988 * range [0,N).
4989 */
4991 void
4994 {
4995 // concept requirements
4997 _RandomAccessIterator>)
5004 }
5007 /**
5008 * @brief Move elements for which a predicate is true to the beginning
5009 * of a sequence.
5010 * @ingroup mutating_algorithms
5011 * @param first A forward iterator.
5012 * @param last A forward iterator.
5013 * @param pred A predicate functor.
5014 * @return An iterator @p middle such that @p pred(i) is true for each
5015 * iterator @p i in the range @p [first,middle) and false for each @p i
5016 * in the range @p [middle,last).
5017 *
5018 * @p pred must not modify its operand. @p partition() does not preserve
5019 * the relative ordering of elements in each group, use
5020 * @p stable_partition() if this is needed.
5021 */
5023 inline _ForwardIterator
5025 _Predicate __pred)
5026 {
5027 // concept requirements
5029 _ForwardIterator>)
5036 }
5040 /**
5041 * @brief Sort the smallest elements of a sequence.
5042 * @ingroup sorting_algorithms
5043 * @param first An iterator.
5044 * @param middle Another iterator.
5045 * @param last Another iterator.
5046 * @return Nothing.
5047 *
5048 * Sorts the smallest @p (middle-first) elements in the range
5049 * @p [first,last) and moves them to the range @p [first,middle). The
5050 * order of the remaining elements in the range @p [middle,last) is
5051 * undefined.
5052 * After the sort if @p i and @j are iterators in the range
5053 * @p [first,middle) such that @i precedes @j and @k is an iterator in
5054 * the range @p [middle,last) then @p *j<*i and @p *k<*i are both false.
5055 */
5059 _RandomAccessIterator __middle,
5060 _RandomAccessIterator __last)
5061 {
5063 _ValueType;
5065 // concept requirements
5067 _RandomAccessIterator>)
5074 }
5076 /**
5077 * @brief Sort the smallest elements of a sequence using a predicate
5078 * for comparison.
5079 * @ingroup sorting_algorithms
5080 * @param first An iterator.
5081 * @param middle Another iterator.
5082 * @param last Another iterator.
5083 * @param comp A comparison functor.
5084 * @return Nothing.
5085 *
5086 * Sorts the smallest @p (middle-first) elements in the range
5087 * @p [first,last) and moves them to the range @p [first,middle). The
5088 * order of the remaining elements in the range @p [middle,last) is
5089 * undefined.
5090 * After the sort if @p i and @j are iterators in the range
5091 * @p [first,middle) such that @i precedes @j and @k is an iterator in
5092 * the range @p [middle,last) then @p *comp(j,*i) and @p comp(*k,*i)
5093 * are both false.
5094 */
5098 _RandomAccessIterator __middle,
5099 _RandomAccessIterator __last,
5100 _Compare __comp)
5101 {
5103 _ValueType;
5105 // concept requirements
5107 _RandomAccessIterator>)
5115 }
5117 /**
5118 * @brief Sort a sequence just enough to find a particular position.
5119 * @ingroup sorting_algorithms
5120 * @param first An iterator.
5121 * @param nth Another iterator.
5122 * @param last Another iterator.
5123 * @return Nothing.
5124 *
5125 * Rearranges the elements in the range @p [first,last) so that @p *nth
5126 * is the same element that would have been in that position had the
5127 * whole sequence been sorted.
5128 * whole sequence been sorted. The elements either side of @p *nth are
5129 * not completely sorted, but for any iterator @i in the range
5130 * @p [first,nth) and any iterator @j in the range @p [nth,last) it
5131 * holds that @p *j<*i is false.
5132 */
5136 _RandomAccessIterator __last)
5137 {
5139 _ValueType;
5141 // concept requirements
5143 _RandomAccessIterator>)
5153 }
5155 /**
5156 * @brief Sort a sequence just enough to find a particular position
5157 * using a predicate for comparison.
5158 * @ingroup sorting_algorithms
5159 * @param first An iterator.
5160 * @param nth Another iterator.
5161 * @param last Another iterator.
5162 * @param comp A comparison functor.
5163 * @return Nothing.
5164 *
5165 * Rearranges the elements in the range @p [first,last) so that @p *nth
5166 * is the same element that would have been in that position had the
5167 * whole sequence been sorted. The elements either side of @p *nth are
5168 * not completely sorted, but for any iterator @i in the range
5169 * @p [first,nth) and any iterator @j in the range @p [nth,last) it
5170 * holds that @p comp(*j,*i) is false.
5171 */
5176 {
5178 _ValueType;
5180 // concept requirements
5182 _RandomAccessIterator>)
5193 }
5196 /**
5197 * @brief Sort the elements of a sequence.
5198 * @ingroup sorting_algorithms
5199 * @param first An iterator.
5200 * @param last Another iterator.
5201 * @return Nothing.
5202 *
5203 * Sorts the elements in the range @p [first,last) in ascending order,
5204 * such that @p *(i+1)<*i is false for each iterator @p i in the range
5205 * @p [first,last-1).
5206 *
5207 * The relative ordering of equivalent elements is not preserved, use
5208 * @p stable_sort() if this is needed.
5209 */
5213 {
5215 _ValueType;
5217 // concept requirements
5219 _RandomAccessIterator>)
5224 {
5228 }
5229 }
5231 /**
5232 * @brief Sort the elements of a sequence using a predicate for comparison.
5233 * @ingroup sorting_algorithms
5234 * @param first An iterator.
5235 * @param last Another iterator.
5236 * @param comp A comparison functor.
5237 * @return Nothing.
5238 *
5239 * Sorts the elements in the range @p [first,last) in ascending order,
5240 * such that @p comp(*(i+1),*i) is false for every iterator @p i in the
5241 * range @p [first,last-1).
5242 *
5243 * The relative ordering of equivalent elements is not preserved, use
5244 * @p stable_sort() if this is needed.
5245 */
5249 _Compare __comp)
5250 {
5252 _ValueType;
5254 // concept requirements
5256 _RandomAccessIterator>)
5258 _ValueType>)
5262 {
5266 }
5267 }
5269 /**
5270 * @brief Merges two sorted ranges.
5271 * @ingroup sorting_algorithms
5272 * @param first1 An iterator.
5273 * @param first2 Another iterator.
5274 * @param last1 Another iterator.
5275 * @param last2 Another iterator.
5276 * @param result An iterator pointing to the end of the merged range.
5277 * @return An iterator pointing to the first element "not less
5278 * than" @a val.
5279 *
5280 * Merges the ranges [first1,last1) and [first2,last2) into the sorted range
5281 * [result, result + (last1-first1) + (last2-first2)). Both input ranges
5282 * must be sorted, and the output range must not overlap with either of
5283 * the input ranges. The sort is @e stable, that is, for equivalent
5284 * elements in the two ranges, elements from the first range will always
5285 * come before elements from the second.
5286 */
5288 typename _OutputIterator>
5289 _OutputIterator
5292 _OutputIterator __result)
5293 {
5295 _ValueType1;
5297 _ValueType2;
5299 // concept requirements
5303 _ValueType1>)
5305 _ValueType2>)
5311 {
5313 {
5316 }
5317 else
5318 {
5321 }
5323 }
5325 __result));
5326 }
5328 /**
5329 * @brief Merges two sorted ranges.
5330 * @ingroup sorting_algorithms
5331 * @param first1 An iterator.
5332 * @param first2 Another iterator.
5333 * @param last1 Another iterator.
5334 * @param last2 Another iterator.
5335 * @param result An iterator pointing to the end of the merged range.
5336 * @param comp A functor to use for comparisons.
5337 * @return An iterator pointing to the first element "not less
5338 * than" @a val.
5339 *
5340 * Merges the ranges [first1,last1) and [first2,last2) into the sorted range
5341 * [result, result + (last1-first1) + (last2-first2)). Both input ranges
5342 * must be sorted, and the output range must not overlap with either of
5343 * the input ranges. The sort is @e stable, that is, for equivalent
5344 * elements in the two ranges, elements from the first range will always
5345 * come before elements from the second.
5346 *
5347 * The comparison function should have the same effects on ordering as
5348 * the function used for the initial sort.
5349 */
5352 _OutputIterator
5356 {
5358 _ValueType1;
5360 _ValueType2;
5362 // concept requirements
5366 _ValueType1>)
5368 _ValueType2>)
5375 {
5377 {
5380 }
5381 else
5382 {
5385 }
5387 }
5389 __result));
5390 }
5393 /**
5394 * @brief Sort the elements of a sequence, preserving the relative order
5395 * of equivalent elements.
5396 * @ingroup sorting_algorithms
5397 * @param first An iterator.
5398 * @param last Another iterator.
5399 * @return Nothing.
5400 *
5401 * Sorts the elements in the range @p [first,last) in ascending order,
5402 * such that @p *(i+1)<*i is false for each iterator @p i in the range
5403 * @p [first,last-1).
5404 *
5405 * The relative ordering of equivalent elements is preserved, so any two
5406 * elements @p x and @p y in the range @p [first,last) such that
5407 * @p x<y is false and @p y<x is false will have the same relative
5408 * ordering after calling @p stable_sort().
5409 */
5413 {
5415 _ValueType;
5417 _DistanceType;
5419 // concept requirements
5421 _RandomAccessIterator>)
5426 __last);
5429 else
5432 }
5434 /**
5435 * @brief Sort the elements of a sequence using a predicate for comparison,
5436 * preserving the relative order of equivalent elements.
5437 * @ingroup sorting_algorithms
5438 * @param first An iterator.
5439 * @param last Another iterator.
5440 * @param comp A comparison functor.
5441 * @return Nothing.
5442 *
5443 * Sorts the elements in the range @p [first,last) in ascending order,
5444 * such that @p comp(*(i+1),*i) is false for each iterator @p i in the
5445 * range @p [first,last-1).
5446 *
5447 * The relative ordering of equivalent elements is preserved, so any two
5448 * elements @p x and @p y in the range @p [first,last) such that
5449 * @p comp(x,y) is false and @p comp(y,x) is false will have the same
5450 * relative ordering after calling @p stable_sort().
5451 */
5455 _Compare __comp)
5456 {
5458 _ValueType;
5460 _DistanceType;
5462 // concept requirements
5464 _RandomAccessIterator>)
5466 _ValueType,
5467 _ValueType>)
5471 __last);
5474 else
5477 }
5480 /**
5481 * @brief Return the union of two sorted ranges.
5482 * @ingroup set_algorithms
5483 * @param first1 Start of first range.
5484 * @param last1 End of first range.
5485 * @param first2 Start of second range.
5486 * @param last2 End of second range.
5487 * @return End of the output range.
5488 * @ingroup set_algorithms
5489 *
5490 * This operation iterates over both ranges, copying elements present in
5491 * each range in order to the output range. Iterators increment for each
5492 * range. When the current element of one range is less than the other,
5493 * that element is copied and the iterator advanced. If an element is
5494 * contained in both ranges, the element from the first range is copied and
5495 * both ranges advance. The output range may not overlap either input
5496 * range.
5497 */
5499 typename _OutputIterator>
5500 _OutputIterator
5503 _OutputIterator __result)
5504 {
5506 _ValueType1;
5508 _ValueType2;
5510 // concept requirements
5514 _ValueType1>)
5516 _ValueType2>)
5523 {
5525 {
5528 }
5530 {
5533 }
5534 else
5535 {
5539 }
5541 }
5543 __result));
5544 }
5546 /**
5547 * @brief Return the union of two sorted ranges using a comparison functor.
5548 * @ingroup set_algorithms
5549 * @param first1 Start of first range.
5550 * @param last1 End of first range.
5551 * @param first2 Start of second range.
5552 * @param last2 End of second range.
5553 * @param comp The comparison functor.
5554 * @return End of the output range.
5555 * @ingroup set_algorithms
5556 *
5557 * This operation iterates over both ranges, copying elements present in
5558 * each range in order to the output range. Iterators increment for each
5559 * range. When the current element of one range is less than the other
5560 * according to @a comp, that element is copied and the iterator advanced.
5561 * If an equivalent element according to @a comp is contained in both
5562 * ranges, the element from the first range is copied and both ranges
5563 * advance. The output range may not overlap either input range.
5564 */
5567 _OutputIterator
5571 {
5573 _ValueType1;
5575 _ValueType2;
5577 // concept requirements
5581 _ValueType1>)
5583 _ValueType2>)
5592 {
5594 {
5597 }
5599 {
5602 }
5603 else
5604 {
5608 }
5610 }
5612 __result));
5613 }
5615 /**
5616 * @brief Return the intersection of two sorted ranges.
5617 * @ingroup set_algorithms
5618 * @param first1 Start of first range.
5619 * @param last1 End of first range.
5620 * @param first2 Start of second range.
5621 * @param last2 End of second range.
5622 * @return End of the output range.
5623 * @ingroup set_algorithms
5624 *
5625 * This operation iterates over both ranges, copying elements present in
5626 * both ranges in order to the output range. Iterators increment for each
5627 * range. When the current element of one range is less than the other,
5628 * that iterator advances. If an element is contained in both ranges, the
5629 * element from the first range is copied and both ranges advance. The
5630 * output range may not overlap either input range.
5631 */
5633 typename _OutputIterator>
5634 _OutputIterator
5637 _OutputIterator __result)
5638 {
5640 _ValueType1;
5642 _ValueType2;
5644 // concept requirements
5648 _ValueType1>)
5659 else
5660 {
5665 }
5667 }
5669 /**
5670 * @brief Return the intersection of two sorted ranges using comparison
5671 * functor.
5672 * @ingroup set_algorithms
5673 * @param first1 Start of first range.
5674 * @param last1 End of first range.
5675 * @param first2 Start of second range.
5676 * @param last2 End of second range.
5677 * @param comp The comparison functor.
5678 * @return End of the output range.
5679 * @ingroup set_algorithms
5680 *
5681 * This operation iterates over both ranges, copying elements present in
5682 * both ranges in order to the output range. Iterators increment for each
5683 * range. When the current element of one range is less than the other
5684 * according to @a comp, that iterator advances. If an element is
5685 * contained in both ranges according to @a comp, the element from the
5686 * first range is copied and both ranges advance. The output range may not
5687 * overlap either input range.
5688 */
5691 _OutputIterator
5695 {
5697 _ValueType1;
5699 _ValueType2;
5701 // concept requirements
5705 _ValueType1>)
5718 else
5719 {
5724 }
5726 }
5728 /**
5729 * @brief Return the difference of two sorted ranges.
5730 * @ingroup set_algorithms
5731 * @param first1 Start of first range.
5732 * @param last1 End of first range.
5733 * @param first2 Start of second range.
5734 * @param last2 End of second range.
5735 * @return End of the output range.
5736 * @ingroup set_algorithms
5737 *
5738 * This operation iterates over both ranges, copying elements present in
5739 * the first range but not the second in order to the output range.
5740 * Iterators increment for each range. When the current element of the
5741 * first range is less than the second, that element is copied and the
5742 * iterator advances. If the current element of the second range is less,
5743 * the iterator advances, but no element is copied. If an element is
5744 * contained in both ranges, no elements are copied and both ranges
5745 * advance. The output range may not overlap either input range.
5746 */
5748 typename _OutputIterator>
5749 _OutputIterator
5752 _OutputIterator __result)
5753 {
5755 _ValueType1;
5757 _ValueType2;
5759 // concept requirements
5763 _ValueType1>)
5771 {
5775 }
5778 else
5779 {
5782 }
5784 }
5786 /**
5787 * @brief Return the difference of two sorted ranges using comparison
5788 * functor.
5789 * @ingroup set_algorithms
5790 * @param first1 Start of first range.
5791 * @param last1 End of first range.
5792 * @param first2 Start of second range.
5793 * @param last2 End of second range.
5794 * @param comp The comparison functor.
5795 * @return End of the output range.
5796 * @ingroup set_algorithms
5797 *
5798 * This operation iterates over both ranges, copying elements present in
5799 * the first range but not the second in order to the output range.
5800 * Iterators increment for each range. When the current element of the
5801 * first range is less than the second according to @a comp, that element
5802 * is copied and the iterator advances. If the current element of the
5803 * second range is less, no element is copied and the iterator advances.
5804 * If an element is contained in both ranges according to @a comp, no
5805 * elements are copied and both ranges advance. The output range may not
5806 * overlap either input range.
5807 */
5810 _OutputIterator
5814 {
5816 _ValueType1;
5818 _ValueType2;
5820 // concept requirements
5824 _ValueType1>)
5834 {
5838 }
5841 else
5842 {
5845 }
5847 }
5849 /**
5850 * @brief Return the symmetric difference of two sorted ranges.
5851 * @ingroup set_algorithms
5852 * @param first1 Start of first range.
5853 * @param last1 End of first range.
5854 * @param first2 Start of second range.
5855 * @param last2 End of second range.
5856 * @return End of the output range.
5857 * @ingroup set_algorithms
5858 *
5859 * This operation iterates over both ranges, copying elements present in
5860 * one range but not the other in order to the output range. Iterators
5861 * increment for each range. When the current element of one range is less
5862 * than the other, that element is copied and the iterator advances. If an
5863 * element is contained in both ranges, no elements are copied and both
5864 * ranges advance. The output range may not overlap either input range.
5865 */
5867 typename _OutputIterator>
5868 _OutputIterator
5871 _OutputIterator __result)
5872 {
5874 _ValueType1;
5876 _ValueType2;
5878 // concept requirements
5882 _ValueType1>)
5884 _ValueType2>)
5892 {
5896 }
5898 {
5902 }
5903 else
5904 {
5907 }
5910 }
5912 /**
5913 * @brief Return the symmetric difference of two sorted ranges using
5914 * comparison functor.
5915 * @ingroup set_algorithms
5916 * @param first1 Start of first range.
5917 * @param last1 End of first range.
5918 * @param first2 Start of second range.
5919 * @param last2 End of second range.
5920 * @param comp The comparison functor.
5921 * @return End of the output range.
5922 * @ingroup set_algorithms
5923 *
5924 * This operation iterates over both ranges, copying elements present in
5925 * one range but not the other in order to the output range. Iterators
5926 * increment for each range. When the current element of one range is less
5927 * than the other according to @a comp, that element is copied and the
5928 * iterator advances. If an element is contained in both ranges according
5929 * to @a comp, no elements are copied and both ranges advance. The output
5930 * range may not overlap either input range.
5931 */
5934 _OutputIterator
5937 _OutputIterator __result,
5938 _Compare __comp)
5939 {
5941 _ValueType1;
5943 _ValueType2;
5945 // concept requirements
5949 _ValueType1>)
5951 _ValueType2>)
5961 {
5965 }
5967 {
5971 }
5972 else
5973 {
5976 }
5979 }
5982 /**
5983 * @brief Return the minimum element in a range.
5984 * @ingroup sorting_algorithms
5985 * @param first Start of range.
5986 * @param last End of range.
5987 * @return Iterator referencing the first instance of the smallest value.
5988 */
5990 _ForwardIterator
5992 {
5993 // concept requirements
6006 }
6008 /**
6009 * @brief Return the minimum element in a range using comparison functor.
6010 * @ingroup sorting_algorithms
6011 * @param first Start of range.
6012 * @param last End of range.
6013 * @param comp Comparison functor.
6014 * @return Iterator referencing the first instance of the smallest value
6015 * according to comp.
6016 */
6018 _ForwardIterator
6020 _Compare __comp)
6021 {
6022 // concept requirements
6036 }
6038 /**
6039 * @brief Return the maximum element in a range.
6040 * @ingroup sorting_algorithms
6041 * @param first Start of range.
6042 * @param last End of range.
6043 * @return Iterator referencing the first instance of the largest value.
6044 */
6046 _ForwardIterator
6048 {
6049 // concept requirements
6062 }
6064 /**
6065 * @brief Return the maximum element in a range using comparison functor.
6066 * @ingroup sorting_algorithms
6067 * @param first Start of range.
6068 * @param last End of range.
6069 * @param comp Comparison functor.
6070 * @return Iterator referencing the first instance of the largest value
6071 * according to comp.
6072 */
6074 _ForwardIterator
6076 _Compare __comp)
6077 {
6078 // concept requirements
6091 }
6093 _GLIBCXX_END_NESTED_NAMESPACE