| blob | 009c409b6fb17d74e718d42a28174784541d9aaf |
1 // Algorithm implementation -*- C++ -*-
3 // Copyright (C) 2001, 2002 Free Software Foundation, Inc.
4 //
5 // This file is part of the GNU ISO C++ Library. This library is free
6 // software; you can redistribute it and/or modify it under the
7 // terms of the GNU General Public License as published by the
8 // Free Software Foundation; either version 2, or (at your option)
9 // any later version.
11 // This library is distributed in the hope that it will be useful,
12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 // GNU General Public License for more details.
16 // You should have received a copy of the GNU General Public License along
17 // with this library; see the file COPYING. If not, write to the Free
18 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
19 // USA.
21 // As a special exception, you may use this file as part of a free software
22 // library without restriction. Specifically, if other files instantiate
23 // templates or use macros or inline functions from this file, or you compile
24 // this file and link it with other files to produce an executable, this
25 // file does not by itself cause the resulting executable to be covered by
26 // the GNU General Public License. This exception does not however
27 // invalidate any other reasons why the executable file might be covered by
28 // the GNU General Public License.
30 /*
31 *
32 * Copyright (c) 1994
33 * Hewlett-Packard Company
34 *
35 * Permission to use, copy, modify, distribute and sell this software
36 * and its documentation for any purpose is hereby granted without fee,
37 * provided that the above copyright notice appear in all copies and
38 * that both that copyright notice and this permission notice appear
39 * in supporting documentation. Hewlett-Packard Company makes no
40 * representations about the suitability of this software for any
41 * purpose. It is provided "as is" without express or implied warranty.
42 *
43 *
44 * Copyright (c) 1996
45 * Silicon Graphics Computer Systems, Inc.
46 *
47 * Permission to use, copy, modify, distribute and sell this software
48 * and its documentation for any purpose is hereby granted without fee,
49 * provided that the above copyright notice appear in all copies and
50 * that both that copyright notice and this permission notice appear
51 * in supporting documentation. Silicon Graphics makes no
52 * representations about the suitability of this software for any
53 * purpose. It is provided "as is" without express or implied warranty.
54 */
56 /** @file stl_algo.h
57 * This is an internal header file, included by other library headers.
58 * You should not attempt to use it directly.
59 */
61 #ifndef __GLIBCPP_INTERNAL_ALGO_H
62 #define __GLIBCPP_INTERNAL_ALGO_H
64 #include <bits/stl_heap.h>
67 // See concept_check.h for the __glibcpp_*_requires macros.
69 namespace std
70 {
72 /**
73 * @brief Find the median of three values.
74 * @param a A value.
75 * @param b A value.
76 * @param c A value.
77 * @return One of @p a, @p b or @p c.
78 *
79 * If @c {l,m,n} is some convolution of @p {a,b,c} such that @c l<=m<=n
80 * then the value returned will be @c m.
81 * This is an SGI extension.
82 * @ingroup SGIextensions
83 */
87 {
88 // concept requirements
95 else
101 else
103 }
105 /**
106 * @brief Find the median of three values using a predicate for comparison.
107 * @param a A value.
108 * @param b A value.
109 * @param c A value.
110 * @param comp A binary predicate.
111 * @return One of @p a, @p b or @p c.
112 *
113 * If @c {l,m,n} is some convolution of @p {a,b,c} such that @p comp(l,m)
114 * and @p comp(m,n) are both true then the value returned will be @c m.
115 * This is an SGI extension.
116 * @ingroup SGIextensions
117 */
121 {
122 // concept requirements
129 else
135 else
137 }
139 /**
140 * @brief Apply a function to every element of a sequence.
141 * @param first An input iterator.
142 * @param last An input iterator.
143 * @param f A unary function object.
144 * @return @p f.
145 *
146 * Applies the function object @p f to each element in the range
147 * @p [first,last). @p f must not modify the order of the sequence.
148 * If @p f has a return value it is ignored.
149 */
151 _Function
153 {
154 // concept requirements
159 }
161 /**
162 * @if maint
163 * This is an overload used by find() for the Input Iterator case.
164 * @endif
165 */
167 inline _InputIter
170 input_iterator_tag)
171 {
175 }
177 /**
178 * @if maint
179 * This is an overload used by find_if() for the Input Iterator case.
180 * @endif
181 */
183 inline _InputIter
185 _Predicate __pred,
186 input_iterator_tag)
187 {
191 }
193 /**
194 * @if maint
195 * This is an overload used by find() for the RAI case.
196 * @endif
197 */
199 _RandomAccessIter
202 random_access_iterator_tag)
203 {
219 }
234 }
235 }
237 /**
238 * @if maint
239 * This is an overload used by find_if() for the RAI case.
240 * @endif
241 */
243 _RandomAccessIter
245 _Predicate __pred,
246 random_access_iterator_tag)
247 {
263 }
278 }
279 }
281 /**
282 * @brief Find the first occurrence of a value in a sequence.
283 * @param first An input iterator.
284 * @param last An input iterator.
285 * @param val The value to find.
286 * @return The first iterator @c i in the range @p [first,last)
287 * such that @c *i == @p val, or @p last if no such iterator exists.
288 */
290 inline _InputIter
293 {
294 // concept requirements
299 }
301 /**
302 * @brief Find the first element in a sequence for which a predicate is true.
303 * @param first An input iterator.
304 * @param last An input iterator.
305 * @param pred A predicate.
306 * @return The first iterator @c i in the range @p [first,last)
307 * such that @p pred(*i) is true, or @p last if no such iterator exists.
308 */
310 inline _InputIter
312 _Predicate __pred)
313 {
314 // concept requirements
319 }
321 /**
322 * @brief Find two adjacent values in a sequence that are equal.
323 * @param first A forward iterator.
324 * @param last A forward iterator.
325 * @return The first iterator @c i such that @c i and @c i+1 are both
326 * valid iterators in @p [first,last) and such that @c *i == @c *(i+1),
327 * or @p last if no such iterator exists.
328 */
330 _ForwardIter
332 {
333 // concept requirements
344 }
346 }
348 /**
349 * @brief Find two adjacent values in a sequence using a predicate.
350 * @param first A forward iterator.
351 * @param last A forward iterator.
352 * @param binary_pred A binary predicate.
353 * @return The first iterator @c i such that @c i and @c i+1 are both
354 * valid iterators in @p [first,last) and such that
355 * @p binary_pred(*i,*(i+1)) is true, or @p last if no such iterator
356 * exists.
357 */
359 _ForwardIter
361 _BinaryPredicate __binary_pred)
362 {
363 // concept requirements
375 }
377 }
379 /**
380 * @brief Count the number of copies of a value in a sequence.
381 * @param first An input iterator.
382 * @param last An input iterator.
383 * @param value The value to be counted.
384 * @return The number of iterators @c i in the range @p [first,last)
385 * for which @c *i == @p value
386 */
390 {
391 // concept requirements
401 }
403 /**
404 * @brief Count the elements of a sequence for which a predicate is true.
405 * @param first An input iterator.
406 * @param last An input iterator.
407 * @param pred A predicate.
408 * @return The number of iterators @c i in the range @p [first,last)
409 * for which @p pred(*i) is true.
410 */
414 {
415 // concept requirements
424 }
427 /**
428 * @brief Search a sequence for a matching sub-sequence.
429 * @param first1 A forward iterator.
430 * @param last1 A forward iterator.
431 * @param first2 A forward iterator.
432 * @param last2 A forward iterator.
433 * @return The first iterator @c i in the range
434 * @p [first1,last1-(last2-first2)) such that @c *(i+N) == @p *(first2+N)
435 * for each @c N in the range @p [0,last2-first2), or @p last1 if no
436 * such iterator exists.
437 *
438 * Searches the range @p [first1,last1) for a sub-sequence that compares
439 * equal value-by-value with the sequence given by @p [first2,last2) and
440 * returns an iterator to the first element of the sub-sequence, or
441 * @p last1 if the sub-sequence is not found.
442 *
443 * Because the sub-sequence must lie completely within the range
444 * @p [first1,last1) it must start at a position less than
445 * @p last1-(last2-first2) where @p last2-first2 is the length of the
446 * sub-sequence.
447 * This means that the returned iterator @c i will be in the range
448 * @p [first1,last1-(last2-first2))
449 */
451 _ForwardIter1
454 {
455 // concept requirements
462 // Test for empty ranges
466 // Test for a pattern of length 1.
472 // General case.
495 }
498 }
500 }
502 /**
503 * @brief Search a sequence for a matching sub-sequence using a predicate.
504 * @param first1 A forward iterator.
505 * @param last1 A forward iterator.
506 * @param first2 A forward iterator.
507 * @param last2 A forward iterator.
508 * @param predicate A binary predicate.
509 * @return The first iterator @c i in the range
510 * @p [first1,last1-(last2-first2)) such that
511 * @p predicate(*(i+N),*(first2+N)) is true for each @c N in the range
512 * @p [0,last2-first2), or @p last1 if no such iterator exists.
513 *
514 * Searches the range @p [first1,last1) for a sub-sequence that compares
515 * equal value-by-value with the sequence given by @p [first2,last2),
516 * using @p predicate to determine equality, and returns an iterator
517 * to the first element of the sub-sequence, or @p last1 if no such
518 * iterator exists.
519 *
520 * @see search(_ForwardIter1, _ForwardIter1, _ForwardIter2, _ForwardIter2)
521 */
523 _ForwardIter1
526 _BinaryPred __predicate)
527 {
528 // concept requirements
535 // Test for empty ranges
539 // Test for a pattern of length 1.
546 }
548 // General case.
561 }
576 }
579 }
581 }
583 /**
584 * @brief Search a sequence for a number of consecutive values.
585 * @param first A forward iterator.
586 * @param last A forward iterator.
587 * @param count The number of consecutive values.
588 * @param val The value to find.
589 * @return The first iterator @c i in the range @p [first,last-count)
590 * such that @c *(i+N) == @p val for each @c N in the range @p [0,count),
591 * or @p last if no such iterator exists.
592 *
593 * Searches the range @p [first,last) for @p count consecutive elements
594 * equal to @p val.
595 */
597 _ForwardIter
600 {
601 // concept requirements
618 }
621 else
623 }
625 }
626 }
628 /**
629 * @brief Search a sequence for a number of consecutive values using a
630 * predicate.
631 * @param first A forward iterator.
632 * @param last A forward iterator.
633 * @param count The number of consecutive values.
634 * @param val The value to find.
635 * @param binary_pred A binary predicate.
636 * @return The first iterator @c i in the range @p [first,last-count)
637 * such that @p binary_pred(*(i+N),val) is true for each @c N in the
638 * range @p [0,count), or @p last if no such iterator exists.
639 *
640 * Searches the range @p [first,last) for @p count consecutive elements
641 * for which the predicate returns true.
642 */
644 typename _BinaryPred>
645 _ForwardIter
648 _BinaryPred __binary_pred)
649 {
650 // concept requirements
662 }
670 }
678 }
680 }
681 }
683 }
684 }
686 /**
687 * @brief Swap the elements of two sequences.
688 * @param first1 A forward iterator.
689 * @param last1 A forward iterator.
690 * @param first2 A forward iterator.
691 * @return An iterator equal to @p first2+(last1-first1).
692 *
693 * Swaps each element in the range @p [first1,last1) with the
694 * corresponding element in the range @p [first2,(last1-first1)).
695 * The ranges must not overlap.
696 */
698 _ForwardIter2
700 _ForwardIter2 __first2)
701 {
702 // concept requirements
715 }
717 /**
718 * @brief Perform an operation on a sequence.
719 * @param first An input iterator.
720 * @param last An input iterator.
721 * @param result An output iterator.
722 * @param unary_op A unary operator.
723 * @return An output iterator equal to @p result+(last-first).
724 *
725 * Applies the operator to each element in the input range and assigns
726 * the results to successive elements of the output sequence.
727 * Evaluates @p *(result+N)=unary_op(*(first+N)) for each @c N in the
728 * range @p [0,last-first).
729 *
730 * @p unary_op must not alter its argument.
731 */
733 _OutputIter
736 {
737 // concept requirements
740 // "the type returned by a _UnaryOperation"
746 }
748 /**
749 * @brief Perform an operation on corresponding elements of two sequences.
750 * @param first1 An input iterator.
751 * @param last1 An input iterator.
752 * @param first2 An input iterator.
753 * @param result An output iterator.
754 * @param binary_op A binary operator.
755 * @return An output iterator equal to @p result+(last-first).
756 *
757 * Applies the operator to the corresponding elements in the two
758 * input ranges and assigns the results to successive elements of the
759 * output sequence.
760 * Evaluates @p *(result+N)=binary_op(*(first1+N),*(first2+N)) for each
761 * @c N in the range @p [0,last1-first1).
762 *
763 * @p binary_op must not alter either of its arguments.
764 */
766 typename _BinaryOperation>
767 _OutputIter
770 _BinaryOperation __binary_op)
771 {
772 // concept requirements
776 // "the type returned by a _BinaryOperation"
782 }
784 /**
785 * @brief Replace each occurrence of one value in a sequence with another
786 * value.
787 * @param first A forward iterator.
788 * @param last A forward iterator.
789 * @param old_value The value to be replaced.
790 * @param new_value The replacement value.
791 * @return replace() returns no value.
792 *
793 * For each iterator @c i in the range @p [first,last) if @c *i ==
794 * @p old_value then the assignment @c *i = @p new_value is performed.
795 */
797 void
800 {
801 // concept requirements
811 }
813 /**
814 * @brief Replace each value in a sequence for which a predicate returns
815 * true with another value.
816 * @param first A forward iterator.
817 * @param last A forward iterator.
818 * @param pred A predicate.
819 * @param new_value The replacement value.
820 * @return replace_if() returns no value.
821 *
822 * For each iterator @c i in the range @p [first,last) if @p pred(*i)
823 * is true then the assignment @c *i = @p new_value is performed.
824 */
826 void
829 {
830 // concept requirements
840 }
842 /**
843 * @brief Copy a sequence, replacing each element of one value with another
844 * value.
845 * @param first An input iterator.
846 * @param last An input iterator.
847 * @param result An output iterator.
848 * @param old_value The value to be replaced.
849 * @param new_value The replacement value.
850 * @return The end of the output sequence, @p result+(last-first).
851 *
852 * Copies each element in the input range @p [first,last) to the
853 * output range @p [result,result+(last-first)) replacing elements
854 * equal to @p old_value with @p new_value.
855 */
857 _OutputIter
859 _OutputIter __result,
861 {
862 // concept requirements
872 }
874 /**
875 * @brief Copy a sequence, replacing each value for which a predicate
876 * returns true with another value.
877 * @param first An input iterator.
878 * @param last An input iterator.
879 * @param result An output iterator.
880 * @param pred A predicate.
881 * @param new_value The replacement value.
882 * @return The end of the output sequence, @p result+(last-first).
883 *
884 * Copies each element in the range @p [first,last) to the range
885 * @p [result,result+(last-first)) replacing elements for which
886 * @p pred returns true with @p new_value.
887 */
889 typename _Tp>
890 _OutputIter
892 _OutputIter __result,
894 {
895 // concept requirements
905 }
907 /**
908 * @brief Assign the result of a function object to each value in a
909 * sequence.
910 * @param first A forward iterator.
911 * @param last A forward iterator.
912 * @param gen A function object taking no arguments.
913 * @return generate() returns no value.
914 *
915 * Performs the assignment @c *i = @p gen() for each @c i in the range
916 * @p [first,last).
917 */
919 void
921 {
922 // concept requirements
929 }
931 /**
932 * @brief Assign the result of a function object to each value in a
933 * sequence.
934 * @param first A forward iterator.
935 * @param n The length of the sequence.
936 * @param gen A function object taking no arguments.
937 * @return The end of the sequence, @p first+n
938 *
939 * Performs the assignment @c *i = @p gen() for each @c i in the range
940 * @p [first,first+n).
941 */
943 _OutputIter
945 {
946 // concept requirements
948 // "the type returned by a _Generator"
954 }
956 /**
957 * @brief Copy a sequence, removing elements of a given value.
958 * @param first An input iterator.
959 * @param last An input iterator.
960 * @param result An output iterator.
961 * @param value The value to be removed.
962 * @return An iterator designating the end of the resulting sequence.
963 *
964 * Copies each element in the range @p [first,last) not equal to @p value
965 * to the range beginning at @p result.
966 * remove_copy() is stable, so the relative order of elements that are
967 * copied is unchanged.
968 */
970 _OutputIter
973 {
974 // concept requirements
985 }
987 }
989 /**
990 * @brief Copy a sequence, removing elements for which a predicate is true.
991 * @param first An input iterator.
992 * @param last An input iterator.
993 * @param result An output iterator.
994 * @param pred A predicate.
995 * @return An iterator designating the end of the resulting sequence.
996 *
997 * Copies each element in the range @p [first,last) for which
998 * @p pred returns true to the range beginning at @p result.
999 *
1000 * remove_copy_if() is stable, so the relative order of elements that are
1001 * copied is unchanged.
1002 */
1004 _OutputIter
1007 {
1008 // concept requirements
1019 }
1021 }
1023 /**
1024 * @brief Remove elements from a sequence.
1025 * @param first An input iterator.
1026 * @param last An input iterator.
1027 * @param value The value to be removed.
1028 * @return An iterator designating the end of the resulting sequence.
1029 *
1030 * All elements equal to @p value are removed from the range
1031 * @p [first,last).
1032 *
1033 * remove() is stable, so the relative order of elements that are
1034 * not removed is unchanged.
1035 *
1036 * Elements between the end of the resulting sequence and @p last
1037 * are still present, but their value is unspecified.
1038 */
1040 _ForwardIter
1043 {
1044 // concept requirements
1055 }
1057 /**
1058 * @brief Remove elements from a sequence using a predicate.
1059 * @param first A forward iterator.
1060 * @param last A forward iterator.
1061 * @param pred A predicate.
1062 * @return An iterator designating the end of the resulting sequence.
1063 *
1064 * All elements for which @p pred returns true are removed from the range
1065 * @p [first,last).
1066 *
1067 * remove_if() is stable, so the relative order of elements that are
1068 * not removed is unchanged.
1069 *
1070 * Elements between the end of the resulting sequence and @p last
1071 * are still present, but their value is unspecified.
1072 */
1074 _ForwardIter
1076 _Predicate __pred)
1077 {
1078 // concept requirements
1087 }
1089 /**
1090 * @if maint
1091 * This is an uglified unique_copy(_InputIter, _InputIter, _OutputIter)
1092 * overloaded for output iterators.
1093 * @endif
1094 */
1096 _OutputIter
1098 _OutputIter __result,
1099 output_iterator_tag)
1100 {
1101 // concept requirements -- taken care of in dispatching function
1108 }
1110 }
1112 /**
1113 * @if maint
1114 * This is an uglified unique_copy(_InputIter, _InputIter, _OutputIter)
1115 * overloaded for forward iterators.
1116 * @endif
1117 */
1119 _ForwardIter
1121 _ForwardIter __result,
1122 forward_iterator_tag)
1123 {
1124 // concept requirements -- taken care of in dispatching function
1130 }
1132 /**
1133 * @brief Copy a sequence, removing consecutive duplicate values.
1134 * @param first An input iterator.
1135 * @param last An input iterator.
1136 * @param result An output iterator.
1137 * @return An iterator designating the end of the resulting sequence.
1138 *
1139 * Copies each element in the range @p [first,last) to the range
1140 * beginning at @p result, except that only the first element is copied
1141 * from groups of consecutive elements that compare equal.
1142 * unique_copy() is stable, so the relative order of elements that are
1143 * copied is unchanged.
1144 */
1146 inline _OutputIter
1148 _OutputIter __result)
1149 {
1150 // concept requirements
1161 }
1163 /**
1164 * @if maint
1165 * This is an uglified
1166 * unique_copy(_InputIter, _InputIter, _OutputIter, _BinaryPredicate)
1167 * overloaded for output iterators.
1168 * @endif
1169 */
1171 _OutputIter
1173 _OutputIter __result,
1174 _BinaryPredicate __binary_pred,
1175 output_iterator_tag)
1176 {
1177 // concept requirements -- iterators already checked
1188 }
1190 }
1192 /**
1193 * @if maint
1194 * This is an uglified
1195 * unique_copy(_InputIter, _InputIter, _OutputIter, _BinaryPredicate)
1196 * overloaded for forward iterators.
1197 * @endif
1198 */
1200 _ForwardIter
1202 _ForwardIter __result,
1203 _BinaryPredicate __binary_pred,
1204 forward_iterator_tag)
1205 {
1206 // concept requirements -- iterators already checked
1215 }
1217 /**
1218 * @brief Copy a sequence, removing consecutive values using a predicate.
1219 * @param first An input iterator.
1220 * @param last An input iterator.
1221 * @param result An output iterator.
1222 * @param binary_pred A binary predicate.
1223 * @return An iterator designating the end of the resulting sequence.
1224 *
1225 * Copies each element in the range @p [first,last) to the range
1226 * beginning at @p result, except that only the first element is copied
1227 * from groups of consecutive elements for which @p binary_pred returns
1228 * true.
1229 * unique_copy() is stable, so the relative order of elements that are
1230 * copied is unchanged.
1231 */
1233 inline _OutputIter
1235 _OutputIter __result,
1236 _BinaryPredicate __binary_pred)
1237 {
1238 // concept requirements -- predicates checked later
1248 }
1250 /**
1251 * @brief Remove consecutive duplicate values from a sequence.
1252 * @param first A forward iterator.
1253 * @param last A forward iterator.
1254 * @return An iterator designating the end of the resulting sequence.
1255 *
1256 * Removes all but the first element from each group of consecutive
1257 * values that compare equal.
1258 * unique() is stable, so the relative order of elements that are
1259 * not removed is unchanged.
1260 * Elements between the end of the resulting sequence and @p last
1261 * are still present, but their value is unspecified.
1262 */
1264 _ForwardIter
1266 {
1267 // concept requirements
1274 }
1276 /**
1277 * @brief Remove consecutive values from a sequence using a predicate.
1278 * @param first A forward iterator.
1279 * @param last A forward iterator.
1280 * @param binary_pred A binary predicate.
1281 * @return An iterator designating the end of the resulting sequence.
1282 *
1283 * Removes all but the first element from each group of consecutive
1284 * values for which @p binary_pred returns true.
1285 * unique() is stable, so the relative order of elements that are
1286 * not removed is unchanged.
1287 * Elements between the end of the resulting sequence and @p last
1288 * are still present, but their value is unspecified.
1289 */
1291 _ForwardIter
1293 _BinaryPredicate __binary_pred)
1294 {
1295 // concept requirements
1303 }
1305 /**
1306 * @if maint
1307 * This is an uglified reverse(_BidirectionalIter, _BidirectionalIter)
1308 * overloaded for bidirectional iterators.
1309 * @endif
1310 */
1312 void
1314 bidirectional_iterator_tag)
1315 {
1319 else
1321 }
1323 /**
1324 * @if maint
1325 * This is an uglified reverse(_BidirectionalIter, _BidirectionalIter)
1326 * overloaded for bidirectional iterators.
1327 * @endif
1328 */
1330 void
1332 random_access_iterator_tag)
1333 {
1336 }
1338 /**
1339 * @brief Reverse a sequence.
1340 * @param first A bidirectional iterator.
1341 * @param last A bidirectional iterator.
1342 * @return reverse() returns no value.
1343 *
1344 * Reverses the order of the elements in the range @p [first,last),
1345 * so that the first element becomes the last etc.
1346 * For every @c i such that @p 0<=i<=(last-first)/2), @p reverse()
1347 * swaps @p *(first+i) and @p *(last-(i+1))
1348 */
1352 {
1353 // concept requirements
1355 _BidirectionalIter>)
1357 }
1359 /**
1360 * @brief Copy a sequence, reversing its elements.
1361 * @param first A bidirectional iterator.
1362 * @param last A bidirectional iterator.
1363 * @param result An output iterator.
1364 * @return An iterator designating the end of the resulting sequence.
1365 *
1366 * Copies the elements in the range @p [first,last) to the range
1367 * @p [result,result+(last-first)) such that the order of the
1368 * elements is reversed.
1369 * For every @c i such that @p 0<=i<=(last-first), @p reverse_copy()
1370 * performs the assignment @p *(result+(last-first)-i) = *(first+i).
1371 * The ranges @p [first,last) and @p [result,result+(last-first))
1372 * must not overlap.
1373 */
1375 _OutputIter
1377 _OutputIter __result)
1378 {
1379 // concept requirements
1388 }
1390 }
1393 /**
1394 * @if maint
1395 * This is a helper function for the rotate algorithm specialized on RAIs.
1396 * It returns the greatest common divisor of two integer values.
1397 * @endif
1398 */
1400 _EuclideanRingElement
1402 {
1407 }
1409 }
1411 /**
1412 * @if maint
1413 * This is a helper function for the rotate algorithm.
1414 * @endif
1415 */
1417 void
1419 _ForwardIter __middle,
1420 _ForwardIter __last,
1421 forward_iterator_tag)
1422 {
1441 }
1442 }
1444 /**
1445 * @if maint
1446 * This is a helper function for the rotate algorithm.
1447 * @endif
1448 */
1450 void
1452 _BidirectionalIter __middle,
1453 _BidirectionalIter __last,
1454 bidirectional_iterator_tag)
1455 {
1456 // concept requirements
1458 _BidirectionalIter>)
1471 }
1474 }
1475 }
1477 /**
1478 * @if maint
1479 * This is a helper function for the rotate algorithm.
1480 * @endif
1481 */
1483 void
1485 _RandomAccessIter __middle,
1486 _RandomAccessIter __last,
1487 random_access_iterator_tag)
1488 {
1489 // concept requirements
1491 _RandomAccessIter>)
1506 }
1519 }
1523 }
1524 }
1531 }
1535 }
1536 }
1540 }
1541 }
1543 /**
1544 * @brief Rotate the elements of a sequence.
1545 * @param first A forward iterator.
1546 * @param middle A forward iterator.
1547 * @param last A forward iterator.
1548 * @return Nothing.
1549 *
1550 * Rotates the elements of the range @p [first,last) by @p (middle-first)
1551 * positions so that the element at @p middle is moved to @p first, the
1552 * element at @p middle+1 is moved to @first+1 and so on for each element
1553 * in the range @p [first,last).
1554 *
1555 * This effectively swaps the ranges @p [first,middle) and
1556 * @p [middle,last).
1557 *
1558 * Performs @p *(first+(n+(last-middle))%(last-first))=*(first+n) for
1559 * each @p n in the range @p [0,last-first).
1560 */
1564 {
1565 // concept requirements
1570 }
1572 /**
1573 * @brief Copy a sequence, rotating its elements.
1574 * @param first A forward iterator.
1575 * @param middle A forward iterator.
1576 * @param last A forward iterator.
1577 * @param result An output iterator.
1578 * @return An iterator designating the end of the resulting sequence.
1579 *
1580 * Copies the elements of the range @p [first,last) to the range
1581 * beginning at @result, rotating the copied elements by @p (middle-first)
1582 * positions so that the element at @p middle is moved to @p result, the
1583 * element at @p middle+1 is moved to @result+1 and so on for each element
1584 * in the range @p [first,last).
1585 *
1586 * Performs @p *(result+(n+(last-middle))%(last-first))=*(first+n) for
1587 * each @p n in the range @p [0,last-first).
1588 */
1590 _OutputIter
1593 {
1594 // concept requirements
1600 }
1603 /**
1604 * @if maint
1605 * Return a random number in the range [0, __n). This function encapsulates
1606 * whether we're using rand (part of the standard C library) or lrand48
1607 * (not standard, but a much better choice whenever it's available).
1608 *
1609 * XXX There is no corresponding encapsulation fn to seed the generator.
1610 * @endif
1611 */
1613 inline _Distance
1615 {
1616 #ifdef _GLIBCPP_HAVE_DRAND48
1618 #else
1620 #endif
1621 }
1624 /**
1625 * @brief Randomly shuffle the elements of a sequence.
1626 * @param first A forward iterator.
1627 * @param last A forward iterator.
1628 * @return Nothing.
1629 *
1630 * Reorder the elements in the range @p [first,last) using a random
1631 * distribution, so that every possible ordering of the sequence is
1632 * equally likely.
1633 */
1637 {
1638 // concept requirements
1640 _RandomAccessIter>)
1645 }
1647 /**
1648 * @brief Shuffle the elements of a sequence using a random number
1649 * generator.
1650 * @param first A forward iterator.
1651 * @param last A forward iterator.
1652 * @param rand The RNG functor or function.
1653 * @return Nothing.
1654 *
1655 * Reorders the elements in the range @p [first,last) using @p rand to
1656 * provide a random distribution. Calling @p rand(N) for a positive
1657 * integer @p N should return a randomly chosen integer from the
1658 * range [0,N).
1659 */
1661 void
1664 {
1665 // concept requirements
1667 _RandomAccessIter>)
1672 }
1675 /**
1676 * @if maint
1677 * This is a helper function...
1678 * @endif
1679 */
1681 _ForwardIter
1683 _Predicate __pred,
1684 forward_iterator_tag)
1685 {
1697 }
1700 }
1702 /**
1703 * @if maint
1704 * This is a helper function...
1705 * @endif
1706 */
1708 _BidirectionalIter
1710 _Predicate __pred,
1711 bidirectional_iterator_tag)
1712 {
1719 else
1727 else
1731 }
1732 }
1734 /**
1735 * @brief Move elements for which a predicate is true to the beginning
1736 * of a sequence.
1737 * @param first A forward iterator.
1738 * @param last A forward iterator.
1739 * @param pred A predicate functor.
1740 * @return An iterator @p middle such that @p pred(i) is true for each
1741 * iterator @p i in the range @p [first,middle) and false for each @p i
1742 * in the range @p [middle,last).
1743 *
1744 * @p pred must not modify its operand. @p partition() does not preserve
1745 * the relative ordering of elements in each group, use
1746 * @p stable_partition() if this is needed.
1747 */
1749 inline _ForwardIter
1751 _Predicate __pred)
1752 {
1753 // concept requirements
1759 }
1762 /**
1763 * @if maint
1764 * This is a helper function...
1765 * @endif
1766 */
1768 _ForwardIter
1771 {
1777 __pred,
1780 __pred,
1785 }
1787 /**
1788 * @if maint
1789 * This is a helper function...
1790 * @endif
1791 */
1793 typename _Distance>
1794 _ForwardIter
1797 _Pointer __buffer,
1798 _Distance __buffer_size)
1799 {
1807 }
1811 }
1814 }
1819 __pred,
1823 __pred,
1829 }
1830 }
1832 /**
1833 * @brief Move elements for which a predicate is true to the beginning
1834 * of a sequence, preserving relative ordering.
1835 * @param first A forward iterator.
1836 * @param last A forward iterator.
1837 * @param pred A predicate functor.
1838 * @return An iterator @p middle such that @p pred(i) is true for each
1839 * iterator @p i in the range @p [first,middle) and false for each @p i
1840 * in the range @p [middle,last).
1841 *
1842 * Performs the same function as @p partition() with the additional
1843 * guarantee that the relative ordering of elements in each group is
1844 * preserved, so any two elements @p x and @p y in the range
1845 * @p [first,last) such that @p pred(x)==pred(y) will have the same
1846 * relative ordering after calling @p stable_partition().
1847 */
1849 _ForwardIter
1851 _Predicate __pred)
1852 {
1853 // concept requirements
1860 else
1861 {
1870 else
1873 }
1874 }
1876 /**
1877 * @if maint
1878 * This is a helper function...
1879 * @endif
1880 */
1882 _RandomAccessIter
1884 _Tp __pivot)
1885 {
1896 }
1897 }
1899 /**
1900 * @if maint
1901 * This is a helper function...
1902 * @endif
1903 */
1905 _RandomAccessIter
1908 {
1919 }
1920 }
1923 /**
1924 * @if maint
1925 * @doctodo
1926 * This controls some aspect of the sort routines.
1927 * @endif
1928 */
1931 /**
1932 * @if maint
1933 * This is a helper function for the sort routine.
1934 * @endif
1935 */
1937 void
1939 {
1946 }
1948 }
1950 /**
1951 * @if maint
1952 * This is a helper function for the sort routine.
1953 * @endif
1954 */
1956 void
1958 {
1965 }
1967 }
1969 /**
1970 * @if maint
1971 * This is a helper function for the sort routine.
1972 * @endif
1973 */
1975 void
1977 {
1981 {
1986 }
1987 else
1989 }
1990 }
1992 /**
1993 * @if maint
1994 * This is a helper function for the sort routine.
1995 * @endif
1996 */
1998 void
2000 _Compare __comp)
2001 {
2005 {
2010 }
2011 else
2013 }
2014 }
2016 /**
2017 * @if maint
2018 * This is a helper function for the sort routine.
2019 * @endif
2020 */
2024 {
2029 }
2031 /**
2032 * @if maint
2033 * This is a helper function for the sort routine.
2034 * @endif
2035 */
2039 _Compare __comp)
2040 {
2045 }
2047 /**
2048 * @if maint
2049 * This is a helper function for the sort routine.
2050 * @endif
2051 */
2053 void
2055 {
2059 }
2060 else
2062 }
2064 /**
2065 * @if maint
2066 * This is a helper function for the sort routine.
2067 * @endif
2068 */
2070 void
2072 _Compare __comp)
2073 {
2077 }
2078 else
2080 }
2082 /**
2083 * @if maint
2084 * This is a helper function for the sort routine.
2085 * @endif
2086 */
2088 inline _Size
2090 {
2091 _Size __k;
2094 }
2096 /**
2097 * @if maint
2098 * This is a helper function for the sort routine.
2099 * @endif
2100 */
2102 void
2104 _Size __depth_limit)
2105 {
2112 }
2114 _RandomAccessIter __cut =
2121 }
2122 }
2124 /**
2125 * @if maint
2126 * This is a helper function for the sort routine.
2127 * @endif
2128 */
2130 void
2133 {
2140 }
2142 _RandomAccessIter __cut =
2147 __comp);
2150 }
2151 }
2153 /**
2154 * @brief Sort the elements of a sequence.
2155 * @param first An iterator.
2156 * @param last Another iterator.
2157 * @return Nothing.
2158 *
2159 * Sorts the elements in the range @p [first,last) in ascending order,
2160 * such that @p *(i+1)<*i is false for each iterator @p i in the range
2161 * @p [first,last-1).
2162 *
2163 * The relative ordering of equivalent elements is not preserved, use
2164 * @p stable_sort() if this is needed.
2165 */
2169 {
2172 // concept requirements
2174 _RandomAccessIter>)
2180 }
2181 }
2183 /**
2184 * @brief Sort the elements of a sequence using a predicate for comparison.
2185 * @param first An iterator.
2186 * @param last Another iterator.
2187 * @param comp A comparison functor.
2188 * @return Nothing.
2189 *
2190 * Sorts the elements in the range @p [first,last) in ascending order,
2191 * such that @p comp(*(i+1),*i) is false for every iterator @p i in the
2192 * range @p [first,last-1).
2193 *
2194 * The relative ordering of equivalent elements is not preserved, use
2195 * @p stable_sort() if this is needed.
2196 */
2200 {
2203 // concept requirements
2205 _RandomAccessIter>)
2211 }
2212 }
2215 /**
2216 * @if maint
2217 * This is a helper function for the stable sorting routines.
2218 * @endif
2219 */
2221 void
2223 {
2227 }
2234 }
2236 /**
2237 * @if maint
2238 * This is a helper function for the stable sorting routines.
2239 * @endif
2240 */
2242 void
2244 _Compare __comp)
2245 {
2249 }
2256 __comp);
2257 }
2260 typename _Distance>
2261 void
2264 {
2270 __result);
2272 }
2276 __result);
2277 }
2281 void
2284 _Compare __comp)
2285 {
2291 __result,
2292 __comp);
2294 }
2299 __result,
2300 __comp);
2301 }
2306 void
2308 _Distance __chunk_size)
2309 {
2313 }
2315 }
2318 void
2321 {
2325 }
2327 }
2330 void
2332 _Pointer __buffer)
2333 {
2347 }
2348 }
2351 void
2354 {
2368 }
2369 }
2372 void
2375 {
2381 }
2385 }
2388 }
2391 typename _Compare>
2392 void
2395 _Compare __comp)
2396 {
2401 __comp);
2403 __comp);
2404 }
2408 }
2411 __comp);
2412 }
2414 /**
2415 * @brief Sort the elements of a sequence, preserving the relative order
2416 * of equivalent elements.
2417 * @param first An iterator.
2418 * @param last Another iterator.
2419 * @return Nothing.
2420 *
2421 * Sorts the elements in the range @p [first,last) in ascending order,
2422 * such that @p *(i+1)<*i is false for each iterator @p i in the range
2423 * @p [first,last-1).
2424 *
2425 * The relative ordering of equivalent elements is preserved, so any two
2426 * elements @p x and @p y in the range @p [first,last) such that
2427 * @p x<y is false and @p y<x is false will have the same relative
2428 * ordering after calling @p stable_sort().
2429 */
2433 {
2437 // concept requirements
2439 _RandomAccessIter>)
2445 else
2447 }
2449 /**
2450 * @brief Sort the elements of a sequence using a predicate for comparison,
2451 * preserving the relative order of equivalent elements.
2452 * @param first An iterator.
2453 * @param last Another iterator.
2454 * @param comp A comparison functor.
2455 * @return Nothing.
2456 *
2457 * Sorts the elements in the range @p [first,last) in ascending order,
2458 * such that @p comp(*(i+1),*i) is false for each iterator @p i in the
2459 * range @p [first,last-1).
2460 *
2461 * The relative ordering of equivalent elements is preserved, so any two
2462 * elements @p x and @p y in the range @p [first,last) such that
2463 * @p comp(x,y) is false and @p comp(y,x) is false will have the same
2464 * relative ordering after calling @p stable_sort().
2465 */
2469 {
2473 // concept requirements
2475 _RandomAccessIter>)
2482 else
2484 __comp);
2485 }
2487 /**
2488 * @brief Sort the smallest elements of a sequence.
2489 * @param first An iterator.
2490 * @param middle Another iterator.
2491 * @param last Another iterator.
2492 * @return Nothing.
2493 *
2494 * Sorts the smallest @p (middle-first) elements in the range
2495 * @p [first,last) and moves them to the range @p [first,middle). The
2496 * order of the remaining elements in the range @p [middle,last) is
2497 * undefined.
2498 * After the sort if @p i and @j are iterators in the range
2499 * @p [first,middle) such that @i precedes @j and @k is an iterator in
2500 * the range @p [middle,last) then @p *j<*i and @p *k<*i are both false.
2501 */
2503 void
2505 _RandomAccessIter __middle,
2506 _RandomAccessIter __last)
2507 {
2510 // concept requirements
2512 _RandomAccessIter>)
2520 }
2522 /**
2523 * @brief Sort the smallest elements of a sequence using a predicate
2524 * for comparison.
2525 * @param first An iterator.
2526 * @param middle Another iterator.
2527 * @param last Another iterator.
2528 * @param comp A comparison functor.
2529 * @return Nothing.
2530 *
2531 * Sorts the smallest @p (middle-first) elements in the range
2532 * @p [first,last) and moves them to the range @p [first,middle). The
2533 * order of the remaining elements in the range @p [middle,last) is
2534 * undefined.
2535 * After the sort if @p i and @j are iterators in the range
2536 * @p [first,middle) such that @i precedes @j and @k is an iterator in
2537 * the range @p [middle,last) then @p *comp(j,*i) and @p comp(*k,*i)
2538 * are both false.
2539 */
2541 void
2543 _RandomAccessIter __middle,
2544 _RandomAccessIter __last,
2545 _Compare __comp)
2546 {
2549 // concept requirements
2551 _RandomAccessIter>)
2560 }
2562 /**
2563 * @brief Copy the smallest elements of a sequence.
2564 * @param first An iterator.
2565 * @param last Another iterator.
2566 * @param result_first A random-access iterator.
2567 * @param result_last Another random-access iterator.
2568 * @return An iterator indicating the end of the resulting sequence.
2569 *
2570 * Copies and sorts the smallest N values from the range @p [first,last)
2571 * to the range beginning at @p result_first, where the number of
2572 * elements to be copied, @p N, is the smaller of @p (last-first) and
2573 * @p (result_last-result_first).
2574 * After the sort if @p i and @j are iterators in the range
2575 * @p [result_first,result_first+N) such that @i precedes @j then
2576 * @p *j<*i is false.
2577 * The value returned is @p result_first+N.
2578 */
2580 _RandomAccessIter
2582 _RandomAccessIter __result_first,
2583 _RandomAccessIter __result_last)
2584 {
2589 // concept requirements
2601 }
2609 }
2612 }
2614 /**
2615 * @brief Copy the smallest elements of a sequence using a predicate for
2616 * comparison.
2617 * @param first An input iterator.
2618 * @param last Another input iterator.
2619 * @param result_first A random-access iterator.
2620 * @param result_last Another random-access iterator.
2621 * @param comp A comparison functor.
2622 * @return An iterator indicating the end of the resulting sequence.
2623 *
2624 * Copies and sorts the smallest N values from the range @p [first,last)
2625 * to the range beginning at @p result_first, where the number of
2626 * elements to be copied, @p N, is the smaller of @p (last-first) and
2627 * @p (result_last-result_first).
2628 * After the sort if @p i and @j are iterators in the range
2629 * @p [result_first,result_first+N) such that @i precedes @j then
2630 * @p comp(*j,*i) is false.
2631 * The value returned is @p result_first+N.
2632 */
2634 _RandomAccessIter
2636 _RandomAccessIter __result_first,
2637 _RandomAccessIter __result_last,
2638 _Compare __comp)
2639 {
2644 // concept requirements
2657 }
2664 __comp);
2666 }
2669 }
2671 /**
2672 * @brief Sort a sequence just enough to find a particular position.
2673 * @param first An iterator.
2674 * @param nth Another iterator.
2675 * @param last Another iterator.
2676 * @return Nothing.
2677 *
2678 * Rearranges the elements in the range @p [first,last) so that @p *nth
2679 * is the same element that would have been in that position had the
2680 * whole sequence been sorted.
2681 * whole sequence been sorted. The elements either side of @p *nth are
2682 * not completely sorted, but for any iterator @i in the range
2683 * @p [first,nth) and any iterator @j in the range @p [nth,last) it
2684 * holds that @p *j<*i is false.
2685 */
2687 void
2689 _RandomAccessIter __nth,
2690 _RandomAccessIter __last)
2691 {
2694 // concept requirements
2699 _RandomAccessIter __cut =
2706 else
2708 }
2710 }
2712 /**
2713 * @brief Sort a sequence just enough to find a particular position
2714 * using a predicate for comparison.
2715 * @param first An iterator.
2716 * @param nth Another iterator.
2717 * @param last Another iterator.
2718 * @param comp A comparison functor.
2719 * @return Nothing.
2720 *
2721 * Rearranges the elements in the range @p [first,last) so that @p *nth
2722 * is the same element that would have been in that position had the
2723 * whole sequence been sorted. The elements either side of @p *nth are
2724 * not completely sorted, but for any iterator @i in the range
2725 * @p [first,nth) and any iterator @j in the range @p [nth,last) it
2726 * holds that @p comp(*j,*i) is false.
2727 */
2729 void
2731 _RandomAccessIter __nth,
2732 _RandomAccessIter __last,
2733 _Compare __comp)
2734 {
2737 // concept requirements
2743 _RandomAccessIter __cut =
2748 __comp)),
2749 __comp);
2752 else
2754 }
2756 }
2759 /**
2760 * @brief Finds the first position in which @a val could be inserted
2761 * without changing the ordering.
2762 * @param first An iterator.
2763 * @param last Another iterator.
2764 * @param val The search term.
2765 * @return An iterator pointing to the first element "not less than" @a val.
2766 * @ingroup binarysearch
2767 */
2769 _ForwardIter
2771 {
2775 // concept requirements
2776 // Note that these are slightly stricter than those of the 4-argument
2777 // version, defined next. The difference is in the strictness of the
2778 // comparison operations... so for looser checking, define your own
2779 // comparison function, as was intended.
2785 _DistanceType __half;
2786 _ForwardIter __middle;
2796 }
2797 else
2799 }
2801 }
2803 /**
2804 * @brief Finds the first position in which @a val could be inserted
2805 * without changing the ordering.
2806 * @param first An iterator.
2807 * @param last Another iterator.
2808 * @param val The search term.
2809 * @param comp A functor to use for comparisons.
2810 * @return An iterator pointing to the first element "not less than" @a val.
2811 * @ingroup binarysearch
2812 *
2813 * The comparison function should have the same effects on ordering as
2814 * the function used for the initial sort.
2815 */
2817 _ForwardIter
2820 {
2824 // concept requirements
2829 _DistanceType __half;
2830 _ForwardIter __middle;
2840 }
2841 else
2843 }
2845 }
2847 /**
2848 * @brief Finds the last position in which @a val could be inserted
2849 * without changing the ordering.
2850 * @param first An iterator.
2851 * @param last Another iterator.
2852 * @param val The search term.
2853 * @return An iterator pointing to the first element greater than @a val.
2854 * @ingroup binarysearch
2855 */
2857 _ForwardIter
2859 {
2863 // concept requirements
2864 // See comments on lower_bound.
2870 _DistanceType __half;
2871 _ForwardIter __middle;
2883 }
2884 }
2886 }
2888 /**
2889 * @brief Finds the last position in which @a val could be inserted
2890 * without changing the ordering.
2891 * @param first An iterator.
2892 * @param last Another iterator.
2893 * @param val The search term.
2894 * @param comp A functor to use for comparisons.
2895 * @return An iterator pointing to the first element greater than @a val.
2896 * @ingroup binarysearch
2897 *
2898 * The comparison function should have the same effects on ordering as
2899 * the function used for the initial sort.
2900 */
2902 _ForwardIter
2905 {
2909 // concept requirements
2914 _DistanceType __half;
2915 _ForwardIter __middle;
2927 }
2928 }
2930 }
2932 /**
2933 * @brief Finds the largest subrange in which @a val could be inserted
2934 * at any place in it without changing the ordering.
2935 * @param first An iterator.
2936 * @param last Another iterator.
2937 * @param val The search term.
2938 * @return An pair of iterators defining the subrange.
2939 * @ingroup binarysearch
2940 *
2941 * This is equivalent to
2942 * @code
2943 * std::make_pair(lower_bound(first, last, val),
2944 * upper_bound(first, last, val))
2945 * @endcode
2946 * but does not actually call those functions.
2947 */
2951 {
2955 // concept requirements
2956 // See comments on lower_bound.
2962 _DistanceType __half;
2973 }
2981 }
2982 }
2984 }
2986 /**
2987 * @brief Finds the largest subrange in which @a val could be inserted
2988 * at any place in it without changing the ordering.
2989 * @param first An iterator.
2990 * @param last Another iterator.
2991 * @param val The search term.
2992 * @param comp A functor to use for comparisons.
2993 * @return An pair of iterators defining the subrange.
2994 * @ingroup binarysearch
2995 *
2996 * This is equivalent to
2997 * @code
2998 * std::make_pair(lower_bound(first, last, val, comp),
2999 * upper_bound(first, last, val, comp))
3000 * @endcode
3001 * but does not actually call those functions.
3002 */
3006 _Compare __comp)
3007 {
3011 // concept requirements
3017 _DistanceType __half;
3028 }
3036 }
3037 }
3039 }
3041 /**
3042 * @brief Determines whether an element exists in a range.
3043 * @param first An iterator.
3044 * @param last Another iterator.
3045 * @param val The search term.
3046 * @return True if @a val (or its equivelent) is in [@a first,@a last ].
3047 * @ingroup binarysearch
3048 *
3049 * Note that this does not actually return an iterator to @a val. For
3050 * that, use std::find or a container's specialized find member functions.
3051 */
3053 bool
3056 {
3057 // concept requirements
3058 // See comments on lower_bound.
3066 }
3068 /**
3069 * @brief Determines whether an element exists in a range.
3070 * @param first An iterator.
3071 * @param last Another iterator.
3072 * @param val The search term.
3073 * @param comp A functor to use for comparisons.
3074 * @return True if @a val (or its equivelent) is in [@a first,@a last ].
3075 * @ingroup binarysearch
3076 *
3077 * Note that this does not actually return an iterator to @a val. For
3078 * that, use std::find or a container's specialized find member functions.
3079 *
3080 * The comparison function should have the same effects on ordering as
3081 * the function used for the initial sort.
3082 */
3084 bool
3087 {
3088 // concept requirements
3097 }
3099 /**
3100 * @brief Merges two sorted ranges.
3101 * @param first1 An iterator.
3102 * @param first2 Another iterator.
3103 * @param last1 Another iterator.
3104 * @param last2 Another iterator.
3105 * @param result An iterator pointing to the end of the merged range.
3106 * @return An iterator pointing to the first element "not less than" @a val.
3107 *
3108 * Merges the ranges [first1,last1) and [first2,last2) into the sorted range
3109 * [result, result + (last1-first1) + (last2-first2)). Both input ranges
3110 * must be sorted, and the output range must not overlap with either of
3111 * the input ranges. The sort is @e stable, that is, for equivalent
3112 * elements in the two ranges, elements from the first range will always
3113 * come before elements from the second.
3114 */
3116 _OutputIter
3119 _OutputIter __result)
3120 {
3121 // concept requirements
3136 }
3140 }
3142 }
3144 }
3146 /**
3147 * @brief Merges two sorted ranges.
3148 * @param first1 An iterator.
3149 * @param first2 Another iterator.
3150 * @param last1 Another iterator.
3151 * @param last2 Another iterator.
3152 * @param result An iterator pointing to the end of the merged range.
3153 * @param comp A functor to use for comparisons.
3154 * @return An iterator pointing to the first element "not less than" @a val.
3155 *
3156 * Merges the ranges [first1,last1) and [first2,last2) into the sorted range
3157 * [result, result + (last1-first1) + (last2-first2)). Both input ranges
3158 * must be sorted, and the output range must not overlap with either of
3159 * the input ranges. The sort is @e stable, that is, for equivalent
3160 * elements in the two ranges, elements from the first range will always
3161 * come before elements from the second.
3162 *
3163 * The comparison function should have the same effects on ordering as
3164 * the function used for the initial sort.
3165 */
3167 typename _Compare>
3168 _OutputIter
3172 {
3173 // concept requirements
3189 }
3193 }
3195 }
3197 }
3199 /**
3200 * @if maint
3201 * This is a helper function for the merge routines.
3202 * @endif
3203 */
3205 void
3207 _BidirectionalIter __middle,
3208 _BidirectionalIter __last,
3210 {
3217 }
3227 }
3233 }
3241 }
3243 /**
3244 * @if maint
3245 * This is a helper function for the merge routines.
3246 * @endif
3247 */
3249 void
3251 _BidirectionalIter __middle,
3252 _BidirectionalIter __last,
3254 _Compare __comp)
3255 {
3262 }
3272 }
3278 }
3286 }
3288 /**
3289 * @if maint
3290 * This is a helper function for the merge routines.
3291 * @endif
3292 */
3294 typename _Distance>
3295 _BidirectionalIter1
3297 _BidirectionalIter1 __middle,
3298 _BidirectionalIter1 __last,
3300 _BidirectionalIter2 __buffer,
3301 _Distance __buffer_size)
3302 {
3303 _BidirectionalIter2 __buffer_end;
3308 }
3313 }
3318 }
3319 }
3321 /**
3322 * @if maint
3323 * This is a helper function for the merge routines.
3324 * @endif
3325 */
3327 typename _BidirectionalIter3>
3328 _BidirectionalIter3
3331 _BidirectionalIter3 __result)
3332 {
3345 }
3351 }
3352 }
3353 }
3355 /**
3356 * @if maint
3357 * This is a helper function for the merge routines.
3358 * @endif
3359 */
3362 _BidirectionalIter3
3365 _BidirectionalIter3 __result,
3366 _Compare __comp)
3367 {
3380 }
3386 }
3387 }
3388 }
3390 /**
3391 * @if maint
3392 * This is a helper function for the merge routines.
3393 * @endif
3394 */
3396 void
3398 _BidirectionalIter __middle,
3399 _BidirectionalIter __last,
3402 {
3406 }
3410 }
3421 }
3427 }
3428 _BidirectionalIter __new_middle =
3431 __buffer_size);
3436 }
3437 }
3439 /**
3440 * @if maint
3441 * This is a helper function for the merge routines.
3442 * @endif
3443 */
3445 typename _Compare>
3446 void
3448 _BidirectionalIter __middle,
3449 _BidirectionalIter __last,
3452 _Compare __comp)
3453 {
3457 }
3461 __comp);
3462 }
3473 }
3479 }
3480 _BidirectionalIter __new_middle =
3483 __buffer_size);
3488 }
3489 }
3491 /**
3492 * @brief Merges two sorted ranges in place.
3493 * @param first An iterator.
3494 * @param middle Another iterator.
3495 * @param last Another iterator.
3496 * @return Nothing.
3497 *
3498 * Merges two sorted and consecutive ranges, [first,middle) and
3499 * [middle,last), and puts the result in [first,last). The output will
3500 * be sorted. The sort is @e stable, that is, for equivalent
3501 * elements in the two ranges, elements from the first range will always
3502 * come before elements from the second.
3503 *
3504 * If enough additional memory is available, this takes (last-first)-1
3505 * comparisons. Otherwise an NlogN algorithm is used, where N is
3506 * distance(first,last).
3507 */
3509 void
3511 _BidirectionalIter __middle,
3512 _BidirectionalIter __last)
3513 {
3515 _ValueType;
3517 _DistanceType;
3519 // concept requirements
3521 _BidirectionalIter>)
3533 else
3536 }
3538 /**
3539 * @brief Merges two sorted ranges in place.
3540 * @param first An iterator.
3541 * @param middle Another iterator.
3542 * @param last Another iterator.
3543 * @param comp A functor to use for comparisons.
3544 * @return Nothing.
3545 *
3546 * Merges two sorted and consecutive ranges, [first,middle) and
3547 * [middle,last), and puts the result in [first,last). The output will
3548 * be sorted. The sort is @e stable, that is, for equivalent
3549 * elements in the two ranges, elements from the first range will always
3550 * come before elements from the second.
3551 *
3552 * If enough additional memory is available, this takes (last-first)-1
3553 * comparisons. Otherwise an NlogN algorithm is used, where N is
3554 * distance(first,last).
3555 *
3556 * The comparison function should have the same effects on ordering as
3557 * the function used for the initial sort.
3558 */
3560 void
3562 _BidirectionalIter __middle,
3563 _BidirectionalIter __last,
3564 _Compare __comp)
3565 {
3567 _ValueType;
3569 _DistanceType;
3571 // concept requirements
3573 _BidirectionalIter>)
3586 else
3589 __comp);
3590 }
3592 // Set algorithms: includes, set_union, set_intersection, set_difference,
3593 // set_symmetric_difference. All of these algorithms have the precondition
3594 // that their input ranges are sorted and the postcondition that their output
3595 // ranges are sorted.
3598 bool
3601 {
3602 // concept requirements
3616 else
3620 }
3623 bool
3626 {
3627 // concept requirements
3642 else
3646 }
3649 _OutputIter
3652 _OutputIter __result)
3653 {
3654 // concept requirements
3669 }
3673 }
3678 }
3680 }
3682 }
3685 typename _Compare>
3686 _OutputIter
3690 {
3691 // concept requirements
3707 }
3711 }
3716 }
3718 }
3720 }
3723 _OutputIter
3726 _OutputIter __result)
3727 {
3728 // concept requirements
3749 }
3751 }
3754 typename _Compare>
3755 _OutputIter
3759 {
3760 // concept requirements
3782 }
3784 }
3787 _OutputIter
3790 _OutputIter __result)
3791 {
3792 // concept requirements
3808 }
3814 }
3816 }
3819 typename _Compare>
3820 _OutputIter
3824 {
3825 // concept requirements
3842 }
3848 }
3850 }
3853 _OutputIter
3856 _OutputIter __result)
3857 {
3858 // concept requirements
3874 }
3879 }
3883 }
3885 }
3888 typename _Compare>
3889 _OutputIter
3892 _OutputIter __result,
3893 _Compare __comp)
3894 {
3895 // concept requirements
3912 }
3917 }
3921 }
3923 }
3925 // min_element and max_element, with and without an explicitly supplied
3926 // comparison function.
3929 _ForwardIter
3931 {
3932 // concept requirements
3943 }
3946 _ForwardIter
3948 _Compare __comp)
3949 {
3950 // concept requirements
3961 }
3964 _ForwardIter
3966 {
3967 // concept requirements
3978 }
3981 _ForwardIter
3983 _Compare __comp)
3984 {
3985 // concept requirements
3997 }
3999 // next_permutation and prev_permutation, with and without an explicitly
4000 // supplied comparison function.
4003 bool
4005 {
4006 // concept requirements
4026 {}
4030 }
4034 }
4035 }
4036 }
4039 bool
4041 _Compare __comp)
4042 {
4043 // concept requirements
4064 {}
4068 }
4072 }
4073 }
4074 }
4077 bool
4079 {
4080 // concept requirements
4100 {}
4104 }
4108 }
4109 }
4110 }
4113 bool
4115 _Compare __comp)
4116 {
4117 // concept requirements
4138 {}
4142 }
4146 }
4147 }
4148 }
4150 // find_first_of, with and without an explicitly supplied comparison function.
4153 _InputIter
4156 {
4157 // concept requirements
4169 }
4172 _InputIter
4175 _BinaryPredicate __comp)
4176 {
4177 // concept requirements
4192 }
4195 // find_end, with and without an explicitly supplied comparison function.
4196 // Search [first2, last2) as a subsequence in [first1, last1), and return
4197 // the *last* possible match. Note that find_end for bidirectional iterators
4198 // is much faster than for forward iterators.
4200 // find_end for forward iterators.
4202 _ForwardIter1
4206 {
4212 _ForwardIter1 __new_result
4220 }
4221 }
4222 }
4223 }
4226 typename _BinaryPredicate>
4227 _ForwardIter1
4231 _BinaryPredicate __comp)
4232 {
4238 _ForwardIter1 __new_result
4246 }
4247 }
4248 }
4249 }
4251 // find_end for bidirectional iterators. Requires partial specialization.
4253 _BidirectionalIter1
4257 {
4258 // concept requirements
4276 }
4277 }
4280 typename _BinaryPredicate>
4281 _BidirectionalIter1
4285 _BinaryPredicate __comp)
4286 {
4287 // concept requirements
4298 __comp);
4306 }
4307 }
4309 // Dispatching functions for find_end.
4312 inline _ForwardIter1
4315 {
4316 // concept requirements
4326 }
4329 typename _BinaryPredicate>
4330 inline _ForwardIter1
4333 _BinaryPredicate __comp)
4334 {
4335 // concept requirements
4345 __comp);
4346 }