| blob | f568a0671e3a287298c273a4dce44a31265fdcc1 |
1 // Algorithm implementation -*- C++ -*-
3 // Copyright (C) 2001, 2002, 2003, 2004 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 _ALGO_H
62 #define _ALGO_H 1
64 #include <bits/stl_heap.h>
66 #include <debug/debug.h>
68 // See concept_check.h for the __glibcxx_*_requires macros.
70 namespace std
71 {
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
160 }
162 /**
163 * @if maint
164 * This is an overload used by find() for the Input Iterator case.
165 * @endif
166 */
168 inline _InputIterator
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 _InputIterator
186 {
190 }
192 /**
193 * @if maint
194 * This is an overload used by find() for the RAI case.
195 * @endif
196 */
198 _RandomAccessIterator
201 {
206 {
222 }
225 {
241 }
242 }
244 /**
245 * @if maint
246 * This is an overload used by find_if() for the RAI case.
247 * @endif
248 */
250 _RandomAccessIterator
253 {
258 {
274 }
277 {
293 }
294 }
296 /**
297 * @brief Find the first occurrence of a value in a sequence.
298 * @param first An input iterator.
299 * @param last An input iterator.
300 * @param val The value to find.
301 * @return The first iterator @c i in the range @p [first,last)
302 * such that @c *i == @p val, or @p last if no such iterator exists.
303 */
305 inline _InputIterator
308 {
309 // concept requirements
316 }
318 /**
319 * @brief Find the first element in a sequence for which a predicate is true.
320 * @param first An input iterator.
321 * @param last An input iterator.
322 * @param pred A predicate.
323 * @return The first iterator @c i in the range @p [first,last)
324 * such that @p pred(*i) is true, or @p last if no such iterator exists.
325 */
327 inline _InputIterator
329 _Predicate __pred)
330 {
331 // concept requirements
338 }
340 /**
341 * @brief Find two adjacent values in a sequence that are equal.
342 * @param first A forward iterator.
343 * @param last A forward iterator.
344 * @return The first iterator @c i such that @c i and @c i+1 are both
345 * valid iterators in @p [first,last) and such that @c *i == @c *(i+1),
346 * or @p last if no such iterator exists.
347 */
349 _ForwardIterator
351 {
352 // concept requirements
361 {
365 }
367 }
369 /**
370 * @brief Find two adjacent values in a sequence using a predicate.
371 * @param first A forward iterator.
372 * @param last A forward iterator.
373 * @param binary_pred A binary predicate.
374 * @return The first iterator @c i such that @c i and @c i+1 are both
375 * valid iterators in @p [first,last) and such that
376 * @p binary_pred(*i,*(i+1)) is true, or @p last if no such iterator
377 * exists.
378 */
380 _ForwardIterator
382 _BinaryPredicate __binary_pred)
383 {
384 // concept requirements
394 {
398 }
400 }
402 /**
403 * @brief Count the number of copies of a value in a sequence.
404 * @param first An input iterator.
405 * @param last An input iterator.
406 * @param value The value to be counted.
407 * @return The number of iterators @c i in the range @p [first,last)
408 * for which @c *i == @p value
409 */
413 {
414 // concept requirements
425 }
427 /**
428 * @brief Count the elements of a sequence for which a predicate is true.
429 * @param first An input iterator.
430 * @param last An input iterator.
431 * @param pred A predicate.
432 * @return The number of iterators @c i in the range @p [first,last)
433 * for which @p pred(*i) is true.
434 */
438 {
439 // concept requirements
449 }
451 /**
452 * @brief Search a sequence for a matching sub-sequence.
453 * @param first1 A forward iterator.
454 * @param last1 A forward iterator.
455 * @param first2 A forward iterator.
456 * @param last2 A forward iterator.
457 * @return The first iterator @c i in the range
458 * @p [first1,last1-(last2-first2)) such that @c *(i+N) == @p *(first2+N)
459 * for each @c N in the range @p [0,last2-first2), or @p last1 if no
460 * such iterator exists.
461 *
462 * Searches the range @p [first1,last1) for a sub-sequence that compares
463 * equal value-by-value with the sequence given by @p [first2,last2) and
464 * returns an iterator to the first element of the sub-sequence, or
465 * @p last1 if the sub-sequence is not found.
466 *
467 * Because the sub-sequence must lie completely within the range
468 * @p [first1,last1) it must start at a position less than
469 * @p last1-(last2-first2) where @p last2-first2 is the length of the
470 * sub-sequence.
471 * This means that the returned iterator @c i will be in the range
472 * @p [first1,last1-(last2-first2))
473 */
475 _ForwardIterator1
478 {
479 // concept requirements
487 // Test for empty ranges
491 // Test for a pattern of length 1.
497 // General case.
503 {
514 {
519 }
521 }
523 }
525 /**
526 * @brief Search a sequence for a matching sub-sequence using a predicate.
527 * @param first1 A forward iterator.
528 * @param last1 A forward iterator.
529 * @param first2 A forward iterator.
530 * @param last2 A forward iterator.
531 * @param predicate A binary predicate.
532 * @return The first iterator @c i in the range
533 * @p [first1,last1-(last2-first2)) such that
534 * @p predicate(*(i+N),*(first2+N)) is true for each @c N in the range
535 * @p [0,last2-first2), or @p last1 if no such iterator exists.
536 *
537 * Searches the range @p [first1,last1) for a sub-sequence that compares
538 * equal value-by-value with the sequence given by @p [first2,last2),
539 * using @p predicate to determine equality, and returns an iterator
540 * to the first element of the sub-sequence, or @p last1 if no such
541 * iterator exists.
542 *
543 * @see search(_ForwardIter1, _ForwardIter1, _ForwardIter2, _ForwardIter2)
544 */
546 typename _BinaryPredicate>
547 _ForwardIterator1
550 _BinaryPredicate __predicate)
551 {
552 // concept requirements
561 // Test for empty ranges
565 // Test for a pattern of length 1.
569 {
573 }
575 // General case.
581 {
583 {
587 }
599 {
604 }
606 }
608 }
610 /**
611 * @brief Search a sequence for a number of consecutive values.
612 * @param first A forward iterator.
613 * @param last A forward iterator.
614 * @param count The number of consecutive values.
615 * @param val The value to find.
616 * @return The first iterator @c i in the range @p [first,last-count)
617 * such that @c *(i+N) == @p val for each @c N in the range @p [0,count),
618 * or @p last if no such iterator exists.
619 *
620 * Searches the range @p [first,last) for @p count consecutive elements
621 * equal to @p val.
622 */
624 _ForwardIterator
627 {
628 // concept requirements
637 else
638 {
641 {
647 {
650 }
653 else
655 }
657 }
658 }
660 /**
661 * @brief Search a sequence for a number of consecutive values using a
662 * predicate.
663 * @param first A forward iterator.
664 * @param last A forward iterator.
665 * @param count The number of consecutive values.
666 * @param val The value to find.
667 * @param binary_pred A binary predicate.
668 * @return The first iterator @c i in the range @p [first,last-count)
669 * such that @p binary_pred(*(i+N),val) is true for each @c N in the
670 * range @p [0,count), or @p last if no such iterator exists.
671 *
672 * Searches the range @p [first,last) for @p count consecutive elements
673 * for which the predicate returns true.
674 */
676 typename _BinaryPredicate>
677 _ForwardIterator
680 _BinaryPredicate __binary_pred)
681 {
682 // concept requirements
690 else
691 {
693 {
697 }
699 {
705 {
708 }
711 else
712 {
714 {
718 }
720 }
721 }
723 }
724 }
726 /**
727 * @brief Swap the elements of two sequences.
728 * @param first1 A forward iterator.
729 * @param last1 A forward iterator.
730 * @param first2 A forward iterator.
731 * @return An iterator equal to @p first2+(last1-first1).
732 *
733 * Swaps each element in the range @p [first1,last1) with the
734 * corresponding element in the range @p [first2,(last1-first1)).
735 * The ranges must not overlap.
736 */
738 _ForwardIterator2
740 _ForwardIterator2 __first2)
741 {
742 // concept requirements
744 _ForwardIterator1>)
746 _ForwardIterator2>)
758 }
760 /**
761 * @brief Perform an operation on a sequence.
762 * @param first An input iterator.
763 * @param last An input iterator.
764 * @param result An output iterator.
765 * @param unary_op A unary operator.
766 * @return An output iterator equal to @p result+(last-first).
767 *
768 * Applies the operator to each element in the input range and assigns
769 * the results to successive elements of the output sequence.
770 * Evaluates @p *(result+N)=unary_op(*(first+N)) for each @c N in the
771 * range @p [0,last-first).
772 *
773 * @p unary_op must not alter its argument.
774 */
776 typename _UnaryOperation>
777 _OutputIterator
780 {
781 // concept requirements
784 // "the type returned by a _UnaryOperation"
791 }
793 /**
794 * @brief Perform an operation on corresponding elements of two sequences.
795 * @param first1 An input iterator.
796 * @param last1 An input iterator.
797 * @param first2 An input iterator.
798 * @param result An output iterator.
799 * @param binary_op A binary operator.
800 * @return An output iterator equal to @p result+(last-first).
801 *
802 * Applies the operator to the corresponding elements in the two
803 * input ranges and assigns the results to successive elements of the
804 * output sequence.
805 * Evaluates @p *(result+N)=binary_op(*(first1+N),*(first2+N)) for each
806 * @c N in the range @p [0,last1-first1).
807 *
808 * @p binary_op must not alter either of its arguments.
809 */
812 _OutputIterator
815 _BinaryOperation __binary_op)
816 {
817 // concept requirements
821 // "the type returned by a _BinaryOperation"
828 }
830 /**
831 * @brief Replace each occurrence of one value in a sequence with another
832 * value.
833 * @param first A forward iterator.
834 * @param last A forward iterator.
835 * @param old_value The value to be replaced.
836 * @param new_value The replacement value.
837 * @return replace() returns no value.
838 *
839 * For each iterator @c i in the range @p [first,last) if @c *i ==
840 * @p old_value then the assignment @c *i = @p new_value is performed.
841 */
843 void
846 {
847 // concept requirements
849 _ForwardIterator>)
859 }
861 /**
862 * @brief Replace each value in a sequence for which a predicate returns
863 * true with another value.
864 * @param first A forward iterator.
865 * @param last A forward iterator.
866 * @param pred A predicate.
867 * @param new_value The replacement value.
868 * @return replace_if() returns no value.
869 *
870 * For each iterator @c i in the range @p [first,last) if @p pred(*i)
871 * is true then the assignment @c *i = @p new_value is performed.
872 */
874 void
877 {
878 // concept requirements
880 _ForwardIterator>)
890 }
892 /**
893 * @brief Copy a sequence, replacing each element of one value with another
894 * value.
895 * @param first An input iterator.
896 * @param last An input iterator.
897 * @param result An output iterator.
898 * @param old_value The value to be replaced.
899 * @param new_value The replacement value.
900 * @return The end of the output sequence, @p result+(last-first).
901 *
902 * Copies each element in the input range @p [first,last) to the
903 * output range @p [result,result+(last-first)) replacing elements
904 * equal to @p old_value with @p new_value.
905 */
907 _OutputIterator
909 _OutputIterator __result,
911 {
912 // concept requirements
923 }
925 /**
926 * @brief Copy a sequence, replacing each value for which a predicate
927 * returns true with another value.
928 * @param first An input iterator.
929 * @param last An input iterator.
930 * @param result An output iterator.
931 * @param pred A predicate.
932 * @param new_value The replacement value.
933 * @return The end of the output sequence, @p result+(last-first).
934 *
935 * Copies each element in the range @p [first,last) to the range
936 * @p [result,result+(last-first)) replacing elements for which
937 * @p pred returns true with @p new_value.
938 */
941 _OutputIterator
943 _OutputIterator __result,
945 {
946 // concept requirements
957 }
959 /**
960 * @brief Assign the result of a function object to each value in a
961 * sequence.
962 * @param first A forward iterator.
963 * @param last A forward iterator.
964 * @param gen A function object taking no arguments.
965 * @return generate() returns no value.
966 *
967 * Performs the assignment @c *i = @p gen() for each @c i in the range
968 * @p [first,last).
969 */
971 void
973 _Generator __gen)
974 {
975 // concept requirements
983 }
985 /**
986 * @brief Assign the result of a function object to each value in a
987 * sequence.
988 * @param first A forward iterator.
989 * @param n The length of the sequence.
990 * @param gen A function object taking no arguments.
991 * @return The end of the sequence, @p first+n
992 *
993 * Performs the assignment @c *i = @p gen() for each @c i in the range
994 * @p [first,first+n).
995 */
997 _OutputIterator
999 {
1000 // concept requirements
1002 // "the type returned by a _Generator"
1008 }
1010 /**
1011 * @brief Copy a sequence, removing elements of a given value.
1012 * @param first An input iterator.
1013 * @param last An input iterator.
1014 * @param result An output iterator.
1015 * @param value The value to be removed.
1016 * @return An iterator designating the end of the resulting sequence.
1017 *
1018 * Copies each element in the range @p [first,last) not equal to @p value
1019 * to the range beginning at @p result.
1020 * remove_copy() is stable, so the relative order of elements that are
1021 * copied is unchanged.
1022 */
1024 _OutputIterator
1027 {
1028 // concept requirements
1038 {
1041 }
1043 }
1045 /**
1046 * @brief Copy a sequence, removing elements for which a predicate is true.
1047 * @param first An input iterator.
1048 * @param last An input iterator.
1049 * @param result An output iterator.
1050 * @param pred A predicate.
1051 * @return An iterator designating the end of the resulting sequence.
1052 *
1053 * Copies each element in the range @p [first,last) for which
1054 * @p pred returns true to the range beginning at @p result.
1055 *
1056 * remove_copy_if() is stable, so the relative order of elements that are
1057 * copied is unchanged.
1058 */
1060 typename _Predicate>
1061 _OutputIterator
1064 {
1065 // concept requirements
1075 {
1078 }
1080 }
1082 /**
1083 * @brief Remove elements from a sequence.
1084 * @param first An input iterator.
1085 * @param last An input iterator.
1086 * @param value The value to be removed.
1087 * @return An iterator designating the end of the resulting sequence.
1088 *
1089 * All elements equal to @p value are removed from the range
1090 * @p [first,last).
1091 *
1092 * remove() is stable, so the relative order of elements that are
1093 * not removed is unchanged.
1094 *
1095 * Elements between the end of the resulting sequence and @p last
1096 * are still present, but their value is unspecified.
1097 */
1099 _ForwardIterator
1102 {
1103 // concept requirements
1105 _ForwardIterator>)
1115 }
1117 /**
1118 * @brief Remove elements from a sequence using a predicate.
1119 * @param first A forward iterator.
1120 * @param last A forward iterator.
1121 * @param pred A predicate.
1122 * @return An iterator designating the end of the resulting sequence.
1123 *
1124 * All elements for which @p pred returns true are removed from the range
1125 * @p [first,last).
1126 *
1127 * remove_if() is stable, so the relative order of elements that are
1128 * not removed is unchanged.
1129 *
1130 * Elements between the end of the resulting sequence and @p last
1131 * are still present, but their value is unspecified.
1132 */
1134 _ForwardIterator
1136 _Predicate __pred)
1137 {
1138 // concept requirements
1140 _ForwardIterator>)
1150 }
1152 /**
1153 * @if maint
1154 * This is an uglified unique_copy(_InputIterator, _InputIterator,
1155 * _OutputIterator)
1156 * overloaded for output iterators.
1157 * @endif
1158 */
1160 _OutputIterator
1162 _OutputIterator __result,
1163 output_iterator_tag)
1164 {
1165 // concept requirements -- taken care of in dispatching function
1170 {
1173 }
1175 }
1177 /**
1178 * @if maint
1179 * This is an uglified unique_copy(_InputIterator, _InputIterator,
1180 * _OutputIterator)
1181 * overloaded for forward iterators.
1182 * @endif
1183 */
1185 _ForwardIterator
1187 _ForwardIterator __result,
1188 forward_iterator_tag)
1189 {
1190 // concept requirements -- taken care of in dispatching function
1196 }
1198 /**
1199 * @if maint
1200 * This is an uglified
1201 * unique_copy(_InputIterator, _InputIterator, _OutputIterator,
1202 * _BinaryPredicate)
1203 * overloaded for output iterators.
1204 * @endif
1205 */
1207 typename _BinaryPredicate>
1208 _OutputIterator
1210 _OutputIterator __result,
1211 _BinaryPredicate __binary_pred,
1212 output_iterator_tag)
1213 {
1214 // concept requirements -- iterators already checked
1223 {
1226 }
1228 }
1230 /**
1231 * @if maint
1232 * This is an uglified
1233 * unique_copy(_InputIterator, _InputIterator, _OutputIterator,
1234 * _BinaryPredicate)
1235 * overloaded for forward iterators.
1236 * @endif
1237 */
1239 typename _BinaryPredicate>
1240 _ForwardIterator
1242 _ForwardIterator __result,
1243 _BinaryPredicate __binary_pred,
1244 forward_iterator_tag)
1245 {
1246 // concept requirements -- iterators already checked
1255 }
1257 /**
1258 * @brief Copy a sequence, removing consecutive duplicate values.
1259 * @param first An input iterator.
1260 * @param last An input iterator.
1261 * @param result An output iterator.
1262 * @return An iterator designating the end of the resulting sequence.
1263 *
1264 * Copies each element in the range @p [first,last) to the range
1265 * beginning at @p result, except that only the first element is copied
1266 * from groups of consecutive elements that compare equal.
1267 * unique_copy() is stable, so the relative order of elements that are
1268 * copied is unchanged.
1269 */
1271 inline _OutputIterator
1273 _OutputIterator __result)
1274 {
1275 // concept requirements
1284 _IterType;
1288 }
1290 /**
1291 * @brief Copy a sequence, removing consecutive values using a predicate.
1292 * @param first An input iterator.
1293 * @param last An input iterator.
1294 * @param result An output iterator.
1295 * @param binary_pred A binary predicate.
1296 * @return An iterator designating the end of the resulting sequence.
1297 *
1298 * Copies each element in the range @p [first,last) to the range
1299 * beginning at @p result, except that only the first element is copied
1300 * from groups of consecutive elements for which @p binary_pred returns
1301 * true.
1302 * unique_copy() is stable, so the relative order of elements that are
1303 * copied is unchanged.
1304 */
1306 typename _BinaryPredicate>
1307 inline _OutputIterator
1309 _OutputIterator __result,
1310 _BinaryPredicate __binary_pred)
1311 {
1312 // concept requirements -- predicates checked later
1319 _IterType;
1324 }
1326 /**
1327 * @brief Remove consecutive duplicate values from a sequence.
1328 * @param first A forward iterator.
1329 * @param last A forward iterator.
1330 * @return An iterator designating the end of the resulting sequence.
1331 *
1332 * Removes all but the first element from each group of consecutive
1333 * values that compare equal.
1334 * unique() is stable, so the relative order of elements that are
1335 * not removed is unchanged.
1336 * Elements between the end of the resulting sequence and @p last
1337 * are still present, but their value is unspecified.
1338 */
1340 _ForwardIterator
1342 {
1343 // concept requirements
1345 _ForwardIterator>)
1350 // Skip the beginning, if already unique.
1355 // Do the real copy work.
1362 }
1364 /**
1365 * @brief Remove consecutive values from a sequence using a predicate.
1366 * @param first A forward iterator.
1367 * @param last A forward iterator.
1368 * @param binary_pred A binary predicate.
1369 * @return An iterator designating the end of the resulting sequence.
1370 *
1371 * Removes all but the first element from each group of consecutive
1372 * values for which @p binary_pred returns true.
1373 * unique() is stable, so the relative order of elements that are
1374 * not removed is unchanged.
1375 * Elements between the end of the resulting sequence and @p last
1376 * are still present, but their value is unspecified.
1377 */
1379 _ForwardIterator
1381 _BinaryPredicate __binary_pred)
1382 {
1383 // concept requirements
1385 _ForwardIterator>)
1391 // Skip the beginning, if already unique.
1396 // Do the real copy work.
1403 }
1405 /**
1406 * @if maint
1407 * This is an uglified reverse(_BidirectionalIterator,
1408 * _BidirectionalIterator)
1409 * overloaded for bidirectional iterators.
1410 * @endif
1411 */
1413 void
1415 bidirectional_iterator_tag)
1416 {
1420 else
1421 {
1424 }
1425 }
1427 /**
1428 * @if maint
1429 * This is an uglified reverse(_BidirectionalIterator,
1430 * _BidirectionalIterator)
1431 * overloaded for random access iterators.
1432 * @endif
1433 */
1435 void
1437 random_access_iterator_tag)
1438 {
1443 {
1447 }
1448 }
1450 /**
1451 * @brief Reverse a sequence.
1452 * @param first A bidirectional iterator.
1453 * @param last A bidirectional iterator.
1454 * @return reverse() returns no value.
1455 *
1456 * Reverses the order of the elements in the range @p [first,last),
1457 * so that the first element becomes the last etc.
1458 * For every @c i such that @p 0<=i<=(last-first)/2), @p reverse()
1459 * swaps @p *(first+i) and @p *(last-(i+1))
1460 */
1464 {
1465 // concept requirements
1467 _BidirectionalIterator>)
1470 }
1472 /**
1473 * @brief Copy a sequence, reversing its elements.
1474 * @param first A bidirectional iterator.
1475 * @param last A bidirectional iterator.
1476 * @param result An output iterator.
1477 * @return An iterator designating the end of the resulting sequence.
1478 *
1479 * Copies the elements in the range @p [first,last) to the range
1480 * @p [result,result+(last-first)) such that the order of the
1481 * elements is reversed.
1482 * For every @c i such that @p 0<=i<=(last-first), @p reverse_copy()
1483 * performs the assignment @p *(result+(last-first)-i) = *(first+i).
1484 * The ranges @p [first,last) and @p [result,result+(last-first))
1485 * must not overlap.
1486 */
1488 _OutputIterator
1490 _OutputIterator __result)
1491 {
1492 // concept requirements
1494 _BidirectionalIterator>)
1500 {
1504 }
1506 }
1509 /**
1510 * @if maint
1511 * This is a helper function for the rotate algorithm specialized on RAIs.
1512 * It returns the greatest common divisor of two integer values.
1513 * @endif
1514 */
1516 _EuclideanRingElement
1518 {
1520 {
1524 }
1526 }
1528 /**
1529 * @if maint
1530 * This is a helper function for the rotate algorithm.
1531 * @endif
1532 */
1534 void
1536 _ForwardIterator __middle,
1537 _ForwardIterator __last,
1538 forward_iterator_tag)
1539 {
1544 do
1545 {
1551 }
1557 {
1565 }
1566 }
1568 /**
1569 * @if maint
1570 * This is a helper function for the rotate algorithm.
1571 * @endif
1572 */
1574 void
1576 _BidirectionalIterator __middle,
1577 _BidirectionalIterator __last,
1578 bidirectional_iterator_tag)
1579 {
1580 // concept requirements
1582 _BidirectionalIterator>)
1591 {
1594 }
1598 else
1600 }
1602 /**
1603 * @if maint
1604 * This is a helper function for the rotate algorithm.
1605 * @endif
1606 */
1608 void
1610 _RandomAccessIterator __middle,
1611 _RandomAccessIterator __last,
1612 random_access_iterator_tag)
1613 {
1614 // concept requirements
1616 _RandomAccessIterator>)
1622 _Distance;
1624 _ValueType;
1631 {
1634 }
1639 {
1644 {
1646 {
1648 {
1651 }
1655 }
1656 }
1657 else
1658 {
1660 {
1662 {
1665 }
1668 }
1669 }
1673 }
1674 }
1676 /**
1677 * @brief Rotate the elements of a sequence.
1678 * @param first A forward iterator.
1679 * @param middle A forward iterator.
1680 * @param last A forward iterator.
1681 * @return Nothing.
1682 *
1683 * Rotates the elements of the range @p [first,last) by @p (middle-first)
1684 * positions so that the element at @p middle is moved to @p first, the
1685 * element at @p middle+1 is moved to @first+1 and so on for each element
1686 * in the range @p [first,last).
1687 *
1688 * This effectively swaps the ranges @p [first,middle) and
1689 * @p [middle,last).
1690 *
1691 * Performs @p *(first+(n+(last-middle))%(last-first))=*(first+n) for
1692 * each @p n in the range @p [0,last-first).
1693 */
1697 _ForwardIterator __last)
1698 {
1699 // concept requirements
1701 _ForwardIterator>)
1706 _IterType;
1708 }
1710 /**
1711 * @brief Copy a sequence, rotating its elements.
1712 * @param first A forward iterator.
1713 * @param middle A forward iterator.
1714 * @param last A forward iterator.
1715 * @param result An output iterator.
1716 * @return An iterator designating the end of the resulting sequence.
1717 *
1718 * Copies the elements of the range @p [first,last) to the range
1719 * beginning at @result, rotating the copied elements by @p (middle-first)
1720 * positions so that the element at @p middle is moved to @p result, the
1721 * element at @p middle+1 is moved to @result+1 and so on for each element
1722 * in the range @p [first,last).
1723 *
1724 * Performs @p *(result+(n+(last-middle))%(last-first))=*(first+n) for
1725 * each @p n in the range @p [0,last-first).
1726 */
1728 _OutputIterator
1731 {
1732 // concept requirements
1740 }
1742 /**
1743 * @brief Randomly shuffle the elements of a sequence.
1744 * @param first A forward iterator.
1745 * @param last A forward iterator.
1746 * @return Nothing.
1747 *
1748 * Reorder the elements in the range @p [first,last) using a random
1749 * distribution, so that every possible ordering of the sequence is
1750 * equally likely.
1751 */
1755 {
1756 // concept requirements
1758 _RandomAccessIterator>)
1764 }
1766 /**
1767 * @brief Shuffle the elements of a sequence using a random number
1768 * generator.
1769 * @param first A forward iterator.
1770 * @param last A forward iterator.
1771 * @param rand The RNG functor or function.
1772 * @return Nothing.
1773 *
1774 * Reorders the elements in the range @p [first,last) using @p rand to
1775 * provide a random distribution. Calling @p rand(N) for a positive
1776 * integer @p N should return a randomly chosen integer from the
1777 * range [0,N).
1778 */
1780 void
1783 {
1784 // concept requirements
1786 _RandomAccessIterator>)
1793 }
1796 /**
1797 * @if maint
1798 * This is a helper function...
1799 * @endif
1800 */
1802 _ForwardIterator
1804 _Predicate __pred,
1805 forward_iterator_tag)
1806 {
1818 {
1821 }
1824 }
1826 /**
1827 * @if maint
1828 * This is a helper function...
1829 * @endif
1830 */
1832 _BidirectionalIterator
1834 _Predicate __pred,
1835 bidirectional_iterator_tag)
1836 {
1838 {
1844 else
1852 else
1856 }
1857 }
1859 /**
1860 * @brief Move elements for which a predicate is true to the beginning
1861 * of a sequence.
1862 * @param first A forward iterator.
1863 * @param last A forward iterator.
1864 * @param pred A predicate functor.
1865 * @return An iterator @p middle such that @p pred(i) is true for each
1866 * iterator @p i in the range @p [first,middle) and false for each @p i
1867 * in the range @p [middle,last).
1868 *
1869 * @p pred must not modify its operand. @p partition() does not preserve
1870 * the relative ordering of elements in each group, use
1871 * @p stable_partition() if this is needed.
1872 */
1874 inline _ForwardIterator
1876 _Predicate __pred)
1877 {
1878 // concept requirements
1880 _ForwardIterator>)
1887 }
1890 /**
1891 * @if maint
1892 * This is a helper function...
1893 * @endif
1894 */
1896 _ForwardIterator
1898 _ForwardIterator __last,
1900 {
1906 __middle,
1907 __pred,
1910 __pred,
1911 __len
1916 }
1918 /**
1919 * @if maint
1920 * This is a helper function...
1921 * @endif
1922 */
1924 typename _Distance>
1925 _ForwardIterator
1927 _ForwardIterator __last,
1929 _Pointer __buffer,
1930 _Distance __buffer_size)
1931 {
1933 {
1938 {
1941 }
1942 else
1943 {
1946 }
1949 }
1950 else
1951 {
1954 _ForwardIterator __begin =
1957 __buffer_size);
1958 _ForwardIterator __end =
1965 }
1966 }
1968 /**
1969 * @brief Move elements for which a predicate is true to the beginning
1970 * of a sequence, preserving relative ordering.
1971 * @param first A forward iterator.
1972 * @param last A forward iterator.
1973 * @param pred A predicate functor.
1974 * @return An iterator @p middle such that @p pred(i) is true for each
1975 * iterator @p i in the range @p [first,middle) and false for each @p i
1976 * in the range @p [middle,last).
1977 *
1978 * Performs the same function as @p partition() with the additional
1979 * guarantee that the relative ordering of elements in each group is
1980 * preserved, so any two elements @p x and @p y in the range
1981 * @p [first,last) such that @p pred(x)==pred(y) will have the same
1982 * relative ordering after calling @p stable_partition().
1983 */
1985 _ForwardIterator
1987 _Predicate __pred)
1988 {
1989 // concept requirements
1991 _ForwardIterator>)
1998 else
1999 {
2001 _ValueType;
2003 _DistanceType;
2006 __last);
2008 return
2012 else
2013 return
2016 }
2017 }
2019 /**
2020 * @if maint
2021 * This is a helper function...
2022 * @endif
2023 */
2025 _RandomAccessIterator
2028 {
2030 {
2040 }
2041 }
2043 /**
2044 * @if maint
2045 * This is a helper function...
2046 * @endif
2047 */
2049 _RandomAccessIterator
2051 _RandomAccessIterator __last,
2053 {
2055 {
2065 }
2066 }
2068 /**
2069 * @if maint
2070 * @doctodo
2071 * This controls some aspect of the sort routines.
2072 * @endif
2073 */
2076 /**
2077 * @if maint
2078 * This is a helper function for the sort routine.
2079 * @endif
2080 */
2082 void
2084 {
2088 {
2092 }
2094 }
2096 /**
2097 * @if maint
2098 * This is a helper function for the sort routine.
2099 * @endif
2100 */
2102 void
2104 _Compare __comp)
2105 {
2109 {
2113 }
2115 }
2117 /**
2118 * @if maint
2119 * This is a helper function for the sort routine.
2120 * @endif
2121 */
2123 void
2125 _RandomAccessIterator __last)
2126 {
2131 {
2135 {
2138 }
2139 else
2141 }
2142 }
2144 /**
2145 * @if maint
2146 * This is a helper function for the sort routine.
2147 * @endif
2148 */
2150 void
2153 {
2157 {
2161 {
2164 }
2165 else
2167 }
2168 }
2170 /**
2171 * @if maint
2172 * This is a helper function for the sort routine.
2173 * @endif
2174 */
2178 _RandomAccessIterator __last)
2179 {
2181 _ValueType;
2185 }
2187 /**
2188 * @if maint
2189 * This is a helper function for the sort routine.
2190 * @endif
2191 */
2196 {
2198 _ValueType;
2202 }
2204 /**
2205 * @if maint
2206 * This is a helper function for the sort routine.
2207 * @endif
2208 */
2210 void
2212 _RandomAccessIterator __last)
2213 {
2215 {
2218 }
2219 else
2221 }
2223 /**
2224 * @if maint
2225 * This is a helper function for the sort routine.
2226 * @endif
2227 */
2229 void
2232 {
2234 {
2237 __comp);
2238 }
2239 else
2241 }
2243 /**
2244 * @if maint
2245 * This is a helper function for the sort routine.
2246 * @endif
2247 */
2249 inline _Size
2251 {
2252 _Size __k;
2256 }
2258 /**
2259 * @brief Sort the smallest elements of a sequence.
2260 * @param first An iterator.
2261 * @param middle Another iterator.
2262 * @param last Another iterator.
2263 * @return Nothing.
2264 *
2265 * Sorts the smallest @p (middle-first) elements in the range
2266 * @p [first,last) and moves them to the range @p [first,middle). The
2267 * order of the remaining elements in the range @p [middle,last) is
2268 * undefined.
2269 * After the sort if @p i and @j are iterators in the range
2270 * @p [first,middle) such that @i precedes @j and @k is an iterator in
2271 * the range @p [middle,last) then @p *j<*i and @p *k<*i are both false.
2272 */
2274 void
2276 _RandomAccessIterator __middle,
2277 _RandomAccessIterator __last)
2278 {
2280 _ValueType;
2282 // concept requirements
2284 _RandomAccessIterator>)
2294 }
2296 /**
2297 * @brief Sort the smallest elements of a sequence using a predicate
2298 * for comparison.
2299 * @param first An iterator.
2300 * @param middle Another iterator.
2301 * @param last Another iterator.
2302 * @param comp A comparison functor.
2303 * @return Nothing.
2304 *
2305 * Sorts the smallest @p (middle-first) elements in the range
2306 * @p [first,last) and moves them to the range @p [first,middle). The
2307 * order of the remaining elements in the range @p [middle,last) is
2308 * undefined.
2309 * After the sort if @p i and @j are iterators in the range
2310 * @p [first,middle) such that @i precedes @j and @k is an iterator in
2311 * the range @p [middle,last) then @p *comp(j,*i) and @p comp(*k,*i)
2312 * are both false.
2313 */
2315 void
2317 _RandomAccessIterator __middle,
2318 _RandomAccessIterator __last,
2319 _Compare __comp)
2320 {
2322 _ValueType;
2324 // concept requirements
2326 _RandomAccessIterator>)
2337 }
2339 /**
2340 * @brief Copy the smallest elements of a sequence.
2341 * @param first An iterator.
2342 * @param last Another iterator.
2343 * @param result_first A random-access iterator.
2344 * @param result_last Another random-access iterator.
2345 * @return An iterator indicating the end of the resulting sequence.
2346 *
2347 * Copies and sorts the smallest N values from the range @p [first,last)
2348 * to the range beginning at @p result_first, where the number of
2349 * elements to be copied, @p N, is the smaller of @p (last-first) and
2350 * @p (result_last-result_first).
2351 * After the sort if @p i and @j are iterators in the range
2352 * @p [result_first,result_first+N) such that @i precedes @j then
2353 * @p *j<*i is false.
2354 * The value returned is @p result_first+N.
2355 */
2357 _RandomAccessIterator
2359 _RandomAccessIterator __result_first,
2360 _RandomAccessIterator __result_last)
2361 {
2363 _InputValueType;
2365 _OutputValueType;
2367 _DistanceType;
2369 // concept requirements
2372 _OutputValueType>)
2382 {
2386 }
2389 {
2396 }
2399 }
2401 /**
2402 * @brief Copy the smallest elements of a sequence using a predicate for
2403 * comparison.
2404 * @param first An input iterator.
2405 * @param last Another input iterator.
2406 * @param result_first A random-access iterator.
2407 * @param result_last Another random-access iterator.
2408 * @param comp A comparison functor.
2409 * @return An iterator indicating the end of the resulting sequence.
2410 *
2411 * Copies and sorts the smallest N values from the range @p [first,last)
2412 * to the range beginning at @p result_first, where the number of
2413 * elements to be copied, @p N, is the smaller of @p (last-first) and
2414 * @p (result_last-result_first).
2415 * After the sort if @p i and @j are iterators in the range
2416 * @p [result_first,result_first+N) such that @i precedes @j then
2417 * @p comp(*j,*i) is false.
2418 * The value returned is @p result_first+N.
2419 */
2421 _RandomAccessIterator
2423 _RandomAccessIterator __result_first,
2424 _RandomAccessIterator __result_last,
2425 _Compare __comp)
2426 {
2428 _InputValueType;
2430 _OutputValueType;
2432 _DistanceType;
2434 // concept requirements
2437 _RandomAccessIterator>)
2439 _OutputValueType>)
2449 {
2453 }
2456 {
2462 __comp);
2464 }
2467 }
2469 /**
2470 * @if maint
2471 * This is a helper function for the sort routine.
2472 * @endif
2473 */
2475 void
2477 _RandomAccessIterator __last,
2478 _Size __depth_limit)
2479 {
2481 _ValueType;
2484 {
2486 {
2489 }
2491 _RandomAccessIterator __cut =
2494 *(__first
2495 + (__last
2498 *(__last
2502 }
2503 }
2505 /**
2506 * @if maint
2507 * This is a helper function for the sort routine.
2508 * @endif
2509 */
2511 void
2513 _RandomAccessIterator __last,
2515 {
2517 _ValueType;
2520 {
2522 {
2525 }
2527 _RandomAccessIterator __cut =
2530 *(__first
2531 + (__last
2535 __comp)),
2536 __comp);
2539 }
2540 }
2542 /**
2543 * @brief Sort the elements of a sequence.
2544 * @param first An iterator.
2545 * @param last Another iterator.
2546 * @return Nothing.
2547 *
2548 * Sorts the elements in the range @p [first,last) in ascending order,
2549 * such that @p *(i+1)<*i is false for each iterator @p i in the range
2550 * @p [first,last-1).
2551 *
2552 * The relative ordering of equivalent elements is not preserved, use
2553 * @p stable_sort() if this is needed.
2554 */
2558 {
2560 _ValueType;
2562 // concept requirements
2564 _RandomAccessIterator>)
2569 {
2572 }
2573 }
2575 /**
2576 * @brief Sort the elements of a sequence using a predicate for comparison.
2577 * @param first An iterator.
2578 * @param last Another iterator.
2579 * @param comp A comparison functor.
2580 * @return Nothing.
2581 *
2582 * Sorts the elements in the range @p [first,last) in ascending order,
2583 * such that @p comp(*(i+1),*i) is false for every iterator @p i in the
2584 * range @p [first,last-1).
2585 *
2586 * The relative ordering of equivalent elements is not preserved, use
2587 * @p stable_sort() if this is needed.
2588 */
2592 _Compare __comp)
2593 {
2595 _ValueType;
2597 // concept requirements
2599 _RandomAccessIterator>)
2601 _ValueType>)
2605 {
2607 __comp);
2609 }
2610 }
2612 /**
2613 * @brief Finds the first position in which @a val could be inserted
2614 * without changing the ordering.
2615 * @param first An iterator.
2616 * @param last Another iterator.
2617 * @param val The search term.
2618 * @return An iterator pointing to the first element "not less than" @a val,
2619 * or end() if every element is less than @a val.
2620 * @ingroup binarysearch
2621 */
2623 _ForwardIterator
2626 {
2628 _ValueType;
2630 _DistanceType;
2632 // concept requirements
2633 // Note that these are slightly stricter than those of the 4-argument
2634 // version, defined next. The difference is in the strictness of the
2635 // comparison operations... so for looser checking, define your own
2636 // comparison function, as was intended.
2643 _DistanceType __half;
2644 _ForwardIterator __middle;
2647 {
2652 {
2656 }
2657 else
2659 }
2661 }
2663 /**
2664 * @brief Finds the first position in which @a val could be inserted
2665 * without changing the ordering.
2666 * @param first An iterator.
2667 * @param last Another iterator.
2668 * @param val The search term.
2669 * @param comp A functor to use for comparisons.
2670 * @return An iterator pointing to the first element "not less than" @a val,
2671 * or end() if every element is less than @a val.
2672 * @ingroup binarysearch
2673 *
2674 * The comparison function should have the same effects on ordering as
2675 * the function used for the initial sort.
2676 */
2678 _ForwardIterator
2681 {
2683 _ValueType;
2685 _DistanceType;
2687 // concept requirements
2694 _DistanceType __half;
2695 _ForwardIterator __middle;
2698 {
2703 {
2707 }
2708 else
2710 }
2712 }
2714 /**
2715 * @brief Finds the last position in which @a val could be inserted
2716 * without changing the ordering.
2717 * @param first An iterator.
2718 * @param last Another iterator.
2719 * @param val The search term.
2720 * @return An iterator pointing to the first element greater than @a val,
2721 * or end() if no elements are greater than @a val.
2722 * @ingroup binarysearch
2723 */
2725 _ForwardIterator
2728 {
2730 _ValueType;
2732 _DistanceType;
2734 // concept requirements
2735 // See comments on lower_bound.
2742 _DistanceType __half;
2743 _ForwardIterator __middle;
2746 {
2752 else
2753 {
2757 }
2758 }
2760 }
2762 /**
2763 * @brief Finds the last position in which @a val could be inserted
2764 * without changing the ordering.
2765 * @param first An iterator.
2766 * @param last Another iterator.
2767 * @param val The search term.
2768 * @param comp A functor to use for comparisons.
2769 * @return An iterator pointing to the first element greater than @a val,
2770 * or end() if no elements are greater than @a val.
2771 * @ingroup binarysearch
2772 *
2773 * The comparison function should have the same effects on ordering as
2774 * the function used for the initial sort.
2775 */
2777 _ForwardIterator
2780 {
2782 _ValueType;
2784 _DistanceType;
2786 // concept requirements
2793 _DistanceType __half;
2794 _ForwardIterator __middle;
2797 {
2803 else
2804 {
2808 }
2809 }
2811 }
2813 /**
2814 * @if maint
2815 * This is a helper function for the merge routines.
2816 * @endif
2817 */
2819 void
2821 _BidirectionalIterator __middle,
2822 _BidirectionalIterator __last,
2824 {
2828 {
2832 }
2838 {
2843 }
2844 else
2845 {
2850 }
2858 }
2860 /**
2861 * @if maint
2862 * This is a helper function for the merge routines.
2863 * @endif
2864 */
2866 typename _Compare>
2867 void
2869 _BidirectionalIterator __middle,
2870 _BidirectionalIterator __last,
2872 _Compare __comp)
2873 {
2877 {
2881 }
2887 {
2891 __comp);
2893 }
2894 else
2895 {
2899 __comp);
2901 }
2909 }
2911 /**
2912 * @if maint
2913 * This is a helper function for the stable sorting routines.
2914 * @endif
2915 */
2917 void
2919 _RandomAccessIterator __last)
2920 {
2922 {
2925 }
2932 }
2934 /**
2935 * @if maint
2936 * This is a helper function for the stable sorting routines.
2937 * @endif
2938 */
2940 void
2943 {
2945 {
2948 }
2955 __comp);
2956 }
2958 /**
2959 * @brief Merges two sorted ranges.
2960 * @param first1 An iterator.
2961 * @param first2 Another iterator.
2962 * @param last1 Another iterator.
2963 * @param last2 Another iterator.
2964 * @param result An iterator pointing to the end of the merged range.
2965 * @return An iterator pointing to the first element "not less than" @a val.
2966 *
2967 * Merges the ranges [first1,last1) and [first2,last2) into the sorted range
2968 * [result, result + (last1-first1) + (last2-first2)). Both input ranges
2969 * must be sorted, and the output range must not overlap with either of
2970 * the input ranges. The sort is @e stable, that is, for equivalent
2971 * elements in the two ranges, elements from the first range will always
2972 * come before elements from the second.
2973 */
2975 typename _OutputIterator>
2976 _OutputIterator
2979 _OutputIterator __result)
2980 {
2981 // concept requirements
2995 {
2997 {
3000 }
3001 else
3002 {
3005 }
3007 }
3009 __result));
3010 }
3012 /**
3013 * @brief Merges two sorted ranges.
3014 * @param first1 An iterator.
3015 * @param first2 Another iterator.
3016 * @param last1 Another iterator.
3017 * @param last2 Another iterator.
3018 * @param result An iterator pointing to the end of the merged range.
3019 * @param comp A functor to use for comparisons.
3020 * @return An iterator pointing to the first element "not less than" @a val.
3021 *
3022 * Merges the ranges [first1,last1) and [first2,last2) into the sorted range
3023 * [result, result + (last1-first1) + (last2-first2)). Both input ranges
3024 * must be sorted, and the output range must not overlap with either of
3025 * the input ranges. The sort is @e stable, that is, for equivalent
3026 * elements in the two ranges, elements from the first range will always
3027 * come before elements from the second.
3028 *
3029 * The comparison function should have the same effects on ordering as
3030 * the function used for the initial sort.
3031 */
3034 _OutputIterator
3038 {
3039 // concept requirements
3054 {
3056 {
3059 }
3060 else
3061 {
3064 }
3066 }
3068 __result));
3069 }
3072 typename _Distance>
3073 void
3075 _RandomAccessIterator1 __last,
3076 _RandomAccessIterator2 __result,
3077 _Distance __step_size)
3078 {
3082 {
3085 __result);
3087 }
3091 __result);
3092 }
3096 void
3098 _RandomAccessIterator1 __last,
3100 _Compare __comp)
3101 {
3105 {
3108 __result,
3109 __comp);
3111 }
3116 __result,
3117 __comp);
3118 }
3123 void
3125 _RandomAccessIterator __last,
3126 _Distance __chunk_size)
3127 {
3129 {
3132 }
3134 }
3137 void
3139 _RandomAccessIterator __last,
3141 {
3143 {
3146 }
3148 }
3151 void
3153 _RandomAccessIterator __last,
3154 _Pointer __buffer)
3155 {
3157 _Distance;
3166 {
3171 }
3172 }
3175 void
3177 _RandomAccessIterator __last,
3179 {
3181 _Distance;
3190 {
3197 }
3198 }
3200 /**
3201 * @if maint
3202 * This is a helper function for the merge routines.
3203 * @endif
3204 */
3206 typename _BidirectionalIterator3>
3207 _BidirectionalIterator3
3209 _BidirectionalIterator1 __last1,
3210 _BidirectionalIterator2 __first2,
3211 _BidirectionalIterator2 __last2,
3212 _BidirectionalIterator3 __result)
3213 {
3221 {
3223 {
3228 }
3229 else
3230 {
3235 }
3236 }
3237 }
3239 /**
3240 * @if maint
3241 * This is a helper function for the merge routines.
3242 * @endif
3243 */
3246 _BidirectionalIterator3
3248 _BidirectionalIterator1 __last1,
3249 _BidirectionalIterator2 __first2,
3250 _BidirectionalIterator2 __last2,
3251 _BidirectionalIterator3 __result,
3252 _Compare __comp)
3253 {
3261 {
3263 {
3268 }
3269 else
3270 {
3275 }
3276 }
3277 }
3279 /**
3280 * @if maint
3281 * This is a helper function for the merge routines.
3282 * @endif
3283 */
3285 typename _Distance>
3286 _BidirectionalIterator1
3288 _BidirectionalIterator1 __middle,
3289 _BidirectionalIterator1 __last,
3291 _BidirectionalIterator2 __buffer,
3292 _Distance __buffer_size)
3293 {
3294 _BidirectionalIterator2 __buffer_end;
3296 {
3300 }
3302 {
3306 }
3307 else
3308 {
3312 }
3313 }
3315 /**
3316 * @if maint
3317 * This is a helper function for the merge routines.
3318 * @endif
3319 */
3321 typename _Pointer>
3322 void
3324 _BidirectionalIterator __middle,
3325 _BidirectionalIterator __last,
3328 {
3330 {
3333 }
3335 {
3339 }
3340 else
3341 {
3347 {
3353 }
3354 else
3355 {
3361 }
3362 _BidirectionalIterator __new_middle =
3365 __buffer_size);
3371 }
3372 }
3374 /**
3375 * @if maint
3376 * This is a helper function for the merge routines.
3377 * @endif
3378 */
3380 typename _Compare>
3381 void
3383 _BidirectionalIterator __middle,
3384 _BidirectionalIterator __last,
3387 _Compare __comp)
3388 {
3390 {
3393 }
3395 {
3399 }
3400 else
3401 {
3407 {
3411 __comp);
3413 }
3414 else
3415 {
3419 __comp);
3421 }
3422 _BidirectionalIterator __new_middle =
3425 __buffer_size);
3432 }
3433 }
3435 /**
3436 * @brief Merges two sorted ranges in place.
3437 * @param first An iterator.
3438 * @param middle Another iterator.
3439 * @param last Another iterator.
3440 * @return Nothing.
3441 *
3442 * Merges two sorted and consecutive ranges, [first,middle) and
3443 * [middle,last), and puts the result in [first,last). The output will
3444 * be sorted. The sort is @e stable, that is, for equivalent
3445 * elements in the two ranges, elements from the first range will always
3446 * come before elements from the second.
3447 *
3448 * If enough additional memory is available, this takes (last-first)-1
3449 * comparisons. Otherwise an NlogN algorithm is used, where N is
3450 * distance(first,last).
3451 */
3453 void
3455 _BidirectionalIterator __middle,
3456 _BidirectionalIterator __last)
3457 {
3459 _ValueType;
3461 _DistanceType;
3463 // concept requirements
3465 _BidirectionalIterator>)
3477 __last);
3480 else
3483 }
3485 /**
3486 * @brief Merges two sorted ranges in place.
3487 * @param first An iterator.
3488 * @param middle Another iterator.
3489 * @param last Another iterator.
3490 * @param comp A functor to use for comparisons.
3491 * @return Nothing.
3492 *
3493 * Merges two sorted and consecutive ranges, [first,middle) and
3494 * [middle,last), and puts the result in [first,last). The output will
3495 * be sorted. The sort is @e stable, that is, for equivalent
3496 * elements in the two ranges, elements from the first range will always
3497 * come before elements from the second.
3498 *
3499 * If enough additional memory is available, this takes (last-first)-1
3500 * comparisons. Otherwise an NlogN algorithm is used, where N is
3501 * distance(first,last).
3502 *
3503 * The comparison function should have the same effects on ordering as
3504 * the function used for the initial sort.
3505 */
3507 void
3509 _BidirectionalIterator __middle,
3510 _BidirectionalIterator __last,
3511 _Compare __comp)
3512 {
3514 _ValueType;
3516 _DistanceType;
3518 // concept requirements
3520 _BidirectionalIterator>)
3533 __last);
3537 else
3540 __comp);
3541 }
3544 typename _Distance>
3545 void
3547 _RandomAccessIterator __last,
3549 {
3553 {
3558 }
3559 else
3560 {
3563 }
3568 }
3572 void
3574 _RandomAccessIterator __last,
3576 _Compare __comp)
3577 {
3581 {
3586 }
3587 else
3588 {
3591 }
3596 __comp);
3597 }
3599 /**
3600 * @brief Sort the elements of a sequence, preserving the relative order
3601 * of equivalent elements.
3602 * @param first An iterator.
3603 * @param last Another iterator.
3604 * @return Nothing.
3605 *
3606 * Sorts the elements in the range @p [first,last) in ascending order,
3607 * such that @p *(i+1)<*i is false for each iterator @p i in the range
3608 * @p [first,last-1).
3609 *
3610 * The relative ordering of equivalent elements is preserved, so any two
3611 * elements @p x and @p y in the range @p [first,last) such that
3612 * @p x<y is false and @p y<x is false will have the same relative
3613 * ordering after calling @p stable_sort().
3614 */
3618 {
3620 _ValueType;
3622 _DistanceType;
3624 // concept requirements
3626 _RandomAccessIterator>)
3634 else
3637 }
3639 /**
3640 * @brief Sort the elements of a sequence using a predicate for comparison,
3641 * preserving the relative order of equivalent elements.
3642 * @param first An iterator.
3643 * @param last Another iterator.
3644 * @param comp A comparison functor.
3645 * @return Nothing.
3646 *
3647 * Sorts the elements in the range @p [first,last) in ascending order,
3648 * such that @p comp(*(i+1),*i) is false for each iterator @p i in the
3649 * range @p [first,last-1).
3650 *
3651 * The relative ordering of equivalent elements is preserved, so any two
3652 * elements @p x and @p y in the range @p [first,last) such that
3653 * @p comp(x,y) is false and @p comp(y,x) is false will have the same
3654 * relative ordering after calling @p stable_sort().
3655 */
3659 _Compare __comp)
3660 {
3662 _ValueType;
3664 _DistanceType;
3666 // concept requirements
3668 _RandomAccessIterator>)
3670 _ValueType,
3671 _ValueType>)
3677 else
3680 }
3682 /**
3683 * @brief Sort a sequence just enough to find a particular position.
3684 * @param first An iterator.
3685 * @param nth Another iterator.
3686 * @param last Another iterator.
3687 * @return Nothing.
3688 *
3689 * Rearranges the elements in the range @p [first,last) so that @p *nth
3690 * is the same element that would have been in that position had the
3691 * whole sequence been sorted.
3692 * whole sequence been sorted. The elements either side of @p *nth are
3693 * not completely sorted, but for any iterator @i in the range
3694 * @p [first,nth) and any iterator @j in the range @p [nth,last) it
3695 * holds that @p *j<*i is false.
3696 */
3698 void
3700 _RandomAccessIterator __nth,
3701 _RandomAccessIterator __last)
3702 {
3704 _ValueType;
3706 // concept requirements
3708 _RandomAccessIterator>)
3714 {
3715 _RandomAccessIterator __cut =
3718 *(__first
3719 + (__last
3722 *(__last
3726 else
3728 }
3730 }
3732 /**
3733 * @brief Sort a sequence just enough to find a particular position
3734 * using a predicate for comparison.
3735 * @param first An iterator.
3736 * @param nth Another iterator.
3737 * @param last Another iterator.
3738 * @param comp A comparison functor.
3739 * @return Nothing.
3740 *
3741 * Rearranges the elements in the range @p [first,last) so that @p *nth
3742 * is the same element that would have been in that position had the
3743 * whole sequence been sorted. The elements either side of @p *nth are
3744 * not completely sorted, but for any iterator @i in the range
3745 * @p [first,nth) and any iterator @j in the range @p [nth,last) it
3746 * holds that @p comp(*j,*i) is false.
3747 */
3749 void
3751 _RandomAccessIterator __nth,
3752 _RandomAccessIterator __last,
3753 _Compare __comp)
3754 {
3756 _ValueType;
3758 // concept requirements
3760 _RandomAccessIterator>)
3767 {
3768 _RandomAccessIterator __cut =
3771 *(__first
3772 + (__last
3779 else
3781 }
3783 }
3785 /**
3786 * @brief Finds the largest subrange in which @a val could be inserted
3787 * at any place in it without changing the ordering.
3788 * @param first An iterator.
3789 * @param last Another iterator.
3790 * @param val The search term.
3791 * @return An pair of iterators defining the subrange.
3792 * @ingroup binarysearch
3793 *
3794 * This is equivalent to
3795 * @code
3796 * std::make_pair(lower_bound(first, last, val),
3797 * upper_bound(first, last, val))
3798 * @endcode
3799 * but does not actually call those functions.
3800 */
3805 {
3807 _ValueType;
3809 _DistanceType;
3811 // concept requirements
3812 // See comments on lower_bound.
3819 _DistanceType __half;
3823 {
3828 {
3832 }
3835 else
3836 {
3841 }
3842 }
3844 }
3846 /**
3847 * @brief Finds the largest subrange in which @a val could be inserted
3848 * at any place in it without changing the ordering.
3849 * @param first An iterator.
3850 * @param last Another iterator.
3851 * @param val The search term.
3852 * @param comp A functor to use for comparisons.
3853 * @return An pair of iterators defining the subrange.
3854 * @ingroup binarysearch
3855 *
3856 * This is equivalent to
3857 * @code
3858 * std::make_pair(lower_bound(first, last, val, comp),
3859 * upper_bound(first, last, val, comp))
3860 * @endcode
3861 * but does not actually call those functions.
3862 */
3867 _Compare __comp)
3868 {
3870 _ValueType;
3872 _DistanceType;
3874 // concept requirements
3883 _DistanceType __half;
3887 {
3892 {
3896 }
3899 else
3900 {
3905 }
3906 }
3908 }
3910 /**
3911 * @brief Determines whether an element exists in a range.
3912 * @param first An iterator.
3913 * @param last Another iterator.
3914 * @param val The search term.
3915 * @return True if @a val (or its equivelent) is in [@a first,@a last ].
3916 * @ingroup binarysearch
3917 *
3918 * Note that this does not actually return an iterator to @a val. For
3919 * that, use std::find or a container's specialized find member functions.
3920 */
3922 bool
3925 {
3926 // concept requirements
3927 // See comments on lower_bound.
3936 }
3938 /**
3939 * @brief Determines whether an element exists in a range.
3940 * @param first An iterator.
3941 * @param last Another iterator.
3942 * @param val The search term.
3943 * @param comp A functor to use for comparisons.
3944 * @return True if @a val (or its equivelent) is in [@a first,@a last ].
3945 * @ingroup binarysearch
3946 *
3947 * Note that this does not actually return an iterator to @a val. For
3948 * that, use std::find or a container's specialized find member functions.
3949 *
3950 * The comparison function should have the same effects on ordering as
3951 * the function used for the initial sort.
3952 */
3954 bool
3957 {
3958 // concept requirements
3968 }
3970 // Set algorithms: includes, set_union, set_intersection, set_difference,
3971 // set_symmetric_difference. All of these algorithms have the precondition
3972 // that their input ranges are sorted and the postcondition that their output
3973 // ranges are sorted.
3975 /**
3976 * @brief Determines whether all elements of a sequence exists in a range.
3977 * @param first1 Start of search range.
3978 * @param last1 End of search range.
3979 * @param first2 Start of sequence
3980 * @param last2 End of sequence.
3981 * @return True if each element in [first2,last2) is contained in order
3982 * within [first1,last1). False otherwise.
3983 * @ingroup setoperations
3984 *
3985 * This operation expects both [first1,last1) and [first2,last2) to be
3986 * sorted. Searches for the presence of each element in [first2,last2)
3987 * within [first1,last1). The iterators over each range only move forward,
3988 * so this is a linear algorithm. If an element in [first2,last2) is not
3989 * found before the search iterator reaches @a last2, false is returned.
3990 */
3992 bool
3995 {
3996 // concept requirements
4012 else
4016 }
4018 /**
4019 * @brief Determines whether all elements of a sequence exists in a range
4020 * using comparison.
4021 * @param first1 Start of search range.
4022 * @param last1 End of search range.
4023 * @param first2 Start of sequence
4024 * @param last2 End of sequence.
4025 * @param comp Comparison function to use.
4026 * @return True if each element in [first2,last2) is contained in order
4027 * within [first1,last1) according to comp. False otherwise.
4028 * @ingroup setoperations
4029 *
4030 * This operation expects both [first1,last1) and [first2,last2) to be
4031 * sorted. Searches for the presence of each element in [first2,last2)
4032 * within [first1,last1), using comp to decide. The iterators over each
4033 * range only move forward, so this is a linear algorithm. If an element
4034 * in [first2,last2) is not found before the search iterator reaches @a
4035 * last2, false is returned.
4036 */
4038 typename _Compare>
4039 bool
4042 {
4043 // concept requirements
4060 else
4064 }
4066 /**
4067 * @brief Return the union of two sorted ranges.
4068 * @param first1 Start of first range.
4069 * @param last1 End of first range.
4070 * @param first2 Start of second range.
4071 * @param last2 End of second range.
4072 * @return End of the output range.
4073 * @ingroup setoperations
4074 *
4075 * This operation iterates over both ranges, copying elements present in
4076 * each range in order to the output range. Iterators increment for each
4077 * range. When the current element of one range is less than the other,
4078 * that element is copied and the iterator advanced. If an element is
4079 * contained in both ranges, the element from the first range is copied and
4080 * both ranges advance. The output range may not overlap either input
4081 * range.
4082 */
4084 typename _OutputIterator>
4085 _OutputIterator
4088 _OutputIterator __result)
4089 {
4090 // concept requirements
4104 {
4106 {
4109 }
4111 {
4114 }
4115 else
4116 {
4120 }
4122 }
4124 __result));
4125 }
4127 /**
4128 * @brief Return the union of two sorted ranges using a comparison functor.
4129 * @param first1 Start of first range.
4130 * @param last1 End of first range.
4131 * @param first2 Start of second range.
4132 * @param last2 End of second range.
4133 * @param comp The comparison functor.
4134 * @return End of the output range.
4135 * @ingroup setoperations
4136 *
4137 * This operation iterates over both ranges, copying elements present in
4138 * each range in order to the output range. Iterators increment for each
4139 * range. When the current element of one range is less than the other
4140 * according to @a comp, that element is copied and the iterator advanced.
4141 * If an equivalent element according to @a comp is contained in both
4142 * ranges, the element from the first range is copied and both ranges
4143 * advance. The output range may not overlap either input range.
4144 */
4147 _OutputIterator
4151 {
4152 // concept requirements
4167 {
4169 {
4172 }
4174 {
4177 }
4178 else
4179 {
4183 }
4185 }
4187 __result));
4188 }
4190 /**
4191 * @brief Return the intersection of two sorted ranges.
4192 * @param first1 Start of first range.
4193 * @param last1 End of first range.
4194 * @param first2 Start of second range.
4195 * @param last2 End of second range.
4196 * @return End of the output range.
4197 * @ingroup setoperations
4198 *
4199 * This operation iterates over both ranges, copying elements present in
4200 * both ranges in order to the output range. Iterators increment for each
4201 * range. When the current element of one range is less than the other,
4202 * that iterator advances. If an element is contained in both ranges, the
4203 * element from the first range is copied and both ranges advance. The
4204 * output range may not overlap either input range.
4205 */
4207 typename _OutputIterator>
4208 _OutputIterator
4211 _OutputIterator __result)
4212 {
4213 // concept requirements
4231 else
4232 {
4237 }
4239 }
4241 /**
4242 * @brief Return the intersection of two sorted ranges using comparison
4243 * functor.
4244 * @param first1 Start of first range.
4245 * @param last1 End of first range.
4246 * @param first2 Start of second range.
4247 * @param last2 End of second range.
4248 * @param comp The comparison functor.
4249 * @return End of the output range.
4250 * @ingroup setoperations
4251 *
4252 * This operation iterates over both ranges, copying elements present in
4253 * both ranges in order to the output range. Iterators increment for each
4254 * range. When the current element of one range is less than the other
4255 * according to @a comp, that iterator advances. If an element is
4256 * contained in both ranges according to @a comp, the element from the
4257 * first range is copied and both ranges advance. The output range may not
4258 * overlap either input range.
4259 */
4262 _OutputIterator
4266 {
4267 // concept requirements
4286 else
4287 {
4292 }
4294 }
4296 /**
4297 * @brief Return the difference of two sorted ranges.
4298 * @param first1 Start of first range.
4299 * @param last1 End of first range.
4300 * @param first2 Start of second range.
4301 * @param last2 End of second range.
4302 * @return End of the output range.
4303 * @ingroup setoperations
4304 *
4305 * This operation iterates over both ranges, copying elements present in
4306 * the first range but not the second in order to the output range.
4307 * Iterators increment for each range. When the current element of the
4308 * first range is less than the second, that element is copied and the
4309 * iterator advances. If the current element of the second range is less,
4310 * the iterator advances, but no element is copied. If an element is
4311 * contained in both ranges, no elements are copied and both ranges
4312 * advance. The output range may not overlap either input range.
4313 */
4315 typename _OutputIterator>
4316 _OutputIterator
4319 _OutputIterator __result)
4320 {
4321 // concept requirements
4336 {
4340 }
4343 else
4344 {
4347 }
4349 }
4351 /**
4352 * @brief Return the difference of two sorted ranges using comparison
4353 * functor.
4354 * @param first1 Start of first range.
4355 * @param last1 End of first range.
4356 * @param first2 Start of second range.
4357 * @param last2 End of second range.
4358 * @param comp The comparison functor.
4359 * @return End of the output range.
4360 * @ingroup setoperations
4361 *
4362 * This operation iterates over both ranges, copying elements present in
4363 * the first range but not the second in order to the output range.
4364 * Iterators increment for each range. When the current element of the
4365 * first range is less than the second according to @a comp, that element
4366 * is copied and the iterator advances. If the current element of the
4367 * second range is less, no element is copied and the iterator advances.
4368 * If an element is contained in both ranges according to @a comp, no
4369 * elements are copied and both ranges advance. The output range may not
4370 * overlap either input range.
4371 */
4374 _OutputIterator
4378 {
4379 // concept requirements
4395 {
4399 }
4402 else
4403 {
4406 }
4408 }
4410 /**
4411 * @brief Return the symmetric difference of two sorted ranges.
4412 * @param first1 Start of first range.
4413 * @param last1 End of first range.
4414 * @param first2 Start of second range.
4415 * @param last2 End of second range.
4416 * @return End of the output range.
4417 * @ingroup setoperations
4418 *
4419 * This operation iterates over both ranges, copying elements present in
4420 * one range but not the other in order to the output range. Iterators
4421 * increment for each range. When the current element of one range is less
4422 * than the other, that element is copied and the iterator advances. If an
4423 * element is contained in both ranges, no elements are copied and both
4424 * ranges advance. The output range may not overlap either input range.
4425 */
4427 typename _OutputIterator>
4428 _OutputIterator
4431 _OutputIterator __result)
4432 {
4433 // concept requirements
4448 {
4452 }
4454 {
4458 }
4459 else
4460 {
4463 }
4466 }
4468 /**
4469 * @brief Return the symmetric difference of two sorted ranges using
4470 * comparison functor.
4471 * @param first1 Start of first range.
4472 * @param last1 End of first range.
4473 * @param first2 Start of second range.
4474 * @param last2 End of second range.
4475 * @param comp The comparison functor.
4476 * @return End of the output range.
4477 * @ingroup setoperations
4478 *
4479 * This operation iterates over both ranges, copying elements present in
4480 * one range but not the other in order to the output range. Iterators
4481 * increment for each range. When the current element of one range is less
4482 * than the other according to @a comp, that element is copied and the
4483 * iterator advances. If an element is contained in both ranges according
4484 * to @a comp, no elements are copied and both ranges advance. The output
4485 * range may not overlap either input range.
4486 */
4489 _OutputIterator
4492 _OutputIterator __result,
4493 _Compare __comp)
4494 {
4495 // concept requirements
4511 {
4515 }
4517 {
4521 }
4522 else
4523 {
4526 }
4529 }
4531 // min_element and max_element, with and without an explicitly supplied
4532 // comparison function.
4534 /**
4535 * @brief Return the maximum element in a range.
4536 * @param first Start of range.
4537 * @param last End of range.
4538 * @return Iterator referencing the first instance of the largest value.
4539 */
4541 _ForwardIterator
4543 {
4544 // concept requirements
4557 }
4559 /**
4560 * @brief Return the maximum element in a range using comparison functor.
4561 * @param first Start of range.
4562 * @param last End of range.
4563 * @param comp Comparison functor.
4564 * @return Iterator referencing the first instance of the largest value
4565 * according to comp.
4566 */
4568 _ForwardIterator
4570 _Compare __comp)
4571 {
4572 // concept requirements
4584 }
4586 /**
4587 * @brief Return the minimum element in a range.
4588 * @param first Start of range.
4589 * @param last End of range.
4590 * @return Iterator referencing the first instance of the smallest value.
4591 */
4593 _ForwardIterator
4595 {
4596 // concept requirements
4609 }
4611 /**
4612 * @brief Return the minimum element in a range using comparison functor.
4613 * @param first Start of range.
4614 * @param last End of range.
4615 * @param comp Comparison functor.
4616 * @return Iterator referencing the first instance of the smallest value
4617 * according to comp.
4618 */
4620 _ForwardIterator
4622 _Compare __comp)
4623 {
4624 // concept requirements
4638 }
4640 // next_permutation and prev_permutation, with and without an explicitly
4641 // supplied comparison function.
4643 /**
4644 * @brief Permute range into the next "dictionary" ordering.
4645 * @param first Start of range.
4646 * @param last End of range.
4647 * @return False if wrapped to first permutation, true otherwise.
4648 *
4649 * Treats all permutations of the range as a set of "dictionary" sorted
4650 * sequences. Permutes the current sequence into the next one of this set.
4651 * Returns true if there are more sequences to generate. If the sequence
4652 * is the largest of the set, the smallest is generated and false returned.
4653 */
4655 bool
4657 _BidirectionalIterator __last)
4658 {
4659 // concept requirements
4661 _BidirectionalIterator>)
4676 {
4680 {
4683 {}
4687 }
4689 {
4692 }
4693 }
4694 }
4696 /**
4697 * @brief Permute range into the next "dictionary" ordering using
4698 * comparison functor.
4699 * @param first Start of range.
4700 * @param last End of range.
4701 * @param comp
4702 * @return False if wrapped to first permutation, true otherwise.
4703 *
4704 * Treats all permutations of the range [first,last) as a set of
4705 * "dictionary" sorted sequences ordered by @a comp. Permutes the current
4706 * sequence into the next one of this set. Returns true if there are more
4707 * sequences to generate. If the sequence is the largest of the set, the
4708 * smallest is generated and false returned.
4709 */
4711 bool
4714 {
4715 // concept requirements
4717 _BidirectionalIterator>)
4733 {
4737 {
4740 {}
4744 }
4746 {
4749 }
4750 }
4751 }
4753 /**
4754 * @brief Permute range into the previous "dictionary" ordering.
4755 * @param first Start of range.
4756 * @param last End of range.
4757 * @return False if wrapped to last permutation, true otherwise.
4758 *
4759 * Treats all permutations of the range as a set of "dictionary" sorted
4760 * sequences. Permutes the current sequence into the previous one of this
4761 * set. Returns true if there are more sequences to generate. If the
4762 * sequence is the smallest of the set, the largest is generated and false
4763 * returned.
4764 */
4766 bool
4768 _BidirectionalIterator __last)
4769 {
4770 // concept requirements
4772 _BidirectionalIterator>)
4787 {
4791 {
4794 {}
4798 }
4800 {
4803 }
4804 }
4805 }
4807 /**
4808 * @brief Permute range into the previous "dictionary" ordering using
4809 * comparison functor.
4810 * @param first Start of range.
4811 * @param last End of range.
4812 * @param comp
4813 * @return False if wrapped to last permutation, true otherwise.
4814 *
4815 * Treats all permutations of the range [first,last) as a set of
4816 * "dictionary" sorted sequences ordered by @a comp. Permutes the current
4817 * sequence into the previous one of this set. Returns true if there are
4818 * more sequences to generate. If the sequence is the smallest of the set,
4819 * the largest is generated and false returned.
4820 */
4822 bool
4825 {
4826 // concept requirements
4828 _BidirectionalIterator>)
4844 {
4848 {
4851 {}
4855 }
4857 {
4860 }
4861 }
4862 }
4864 // find_first_of, with and without an explicitly supplied comparison function.
4866 /**
4867 * @brief Find element from a set in a sequence.
4868 * @param first1 Start of range to search.
4869 * @param last1 End of range to search.
4870 * @param first2 Start of match candidates.
4871 * @param last2 End of match candidates.
4872 * @return The first iterator @c i in the range
4873 * @p [first1,last1) such that @c *i == @p *(i2) such that i2 is an
4874 * interator in [first2,last2), or @p last1 if no such iterator exists.
4875 *
4876 * Searches the range @p [first1,last1) for an element that is equal to
4877 * some element in the range [first2,last2). If found, returns an iterator
4878 * in the range [first1,last1), otherwise returns @p last1.
4879 */
4881 _InputIterator
4884 {
4885 // concept requirements
4899 }
4901 /**
4902 * @brief Find element from a set in a sequence using a predicate.
4903 * @param first1 Start of range to search.
4904 * @param last1 End of range to search.
4905 * @param first2 Start of match candidates.
4906 * @param last2 End of match candidates.
4907 * @param comp Predicate to use.
4908 * @return The first iterator @c i in the range
4909 * @p [first1,last1) such that @c comp(*i, @p *(i2)) is true and i2 is an
4910 * interator in [first2,last2), or @p last1 if no such iterator exists.
4911 *
4912 * Searches the range @p [first1,last1) for an element that is equal to
4913 * some element in the range [first2,last2). If found, returns an iterator in
4914 * the range [first1,last1), otherwise returns @p last1.
4915 */
4917 typename _BinaryPredicate>
4918 _InputIterator
4921 _BinaryPredicate __comp)
4922 {
4923 // concept requirements
4937 }
4940 // find_end, with and without an explicitly supplied comparison function.
4941 // Search [first2, last2) as a subsequence in [first1, last1), and return
4942 // the *last* possible match. Note that find_end for bidirectional iterators
4943 // is much faster than for forward iterators.
4945 // find_end for forward iterators.
4947 _ForwardIterator1
4951 {
4954 else
4955 {
4958 {
4959 _ForwardIterator1 __new_result
4963 else
4964 {
4968 }
4969 }
4970 }
4971 }
4974 typename _BinaryPredicate>
4975 _ForwardIterator1
4979 _BinaryPredicate __comp)
4980 {
4983 else
4984 {
4987 {
4988 _ForwardIterator1 __new_result
4992 else
4993 {
4997 }
4998 }
4999 }
5000 }
5002 // find_end for bidirectional iterators. Requires partial specialization.
5004 _BidirectionalIterator1
5006 _BidirectionalIterator1 __last1,
5007 _BidirectionalIterator2 __first2,
5008 _BidirectionalIterator2 __last2,
5010 {
5011 // concept requirements
5013 _BidirectionalIterator1>)
5015 _BidirectionalIterator2>)
5027 else
5028 {
5032 }
5033 }
5036 typename _BinaryPredicate>
5037 _BidirectionalIterator1
5039 _BidirectionalIterator1 __last1,
5040 _BidirectionalIterator2 __first2,
5041 _BidirectionalIterator2 __last2,
5043 _BinaryPredicate __comp)
5044 {
5045 // concept requirements
5047 _BidirectionalIterator1>)
5049 _BidirectionalIterator2>)
5058 __comp);
5062 else
5063 {
5067 }
5068 }
5070 // Dispatching functions for find_end.
5072 /**
5073 * @brief Find last matching subsequence in a sequence.
5074 * @param first1 Start of range to search.
5075 * @param last1 End of range to search.
5076 * @param first2 Start of sequence to match.
5077 * @param last2 End of sequence to match.
5078 * @return The last iterator @c i in the range
5079 * @p [first1,last1-(last2-first2)) such that @c *(i+N) == @p *(first2+N)
5080 * for each @c N in the range @p [0,last2-first2), or @p last1 if no
5081 * such iterator exists.
5082 *
5083 * Searches the range @p [first1,last1) for a sub-sequence that compares
5084 * equal value-by-value with the sequence given by @p [first2,last2) and
5085 * returns an iterator to the first element of the sub-sequence, or
5086 * @p last1 if the sub-sequence is not found. The sub-sequence will be the
5087 * last such subsequence contained in [first,last1).
5088 *
5089 * Because the sub-sequence must lie completely within the range
5090 * @p [first1,last1) it must start at a position less than
5091 * @p last1-(last2-first2) where @p last2-first2 is the length of the
5092 * sub-sequence.
5093 * This means that the returned iterator @c i will be in the range
5094 * @p [first1,last1-(last2-first2))
5095 */
5097 inline _ForwardIterator1
5100 {
5101 // concept requirements
5113 }
5115 /**
5116 * @brief Find last matching subsequence in a sequence using a predicate.
5117 * @param first1 Start of range to search.
5118 * @param last1 End of range to search.
5119 * @param first2 Start of sequence to match.
5120 * @param last2 End of sequence to match.
5121 * @param comp The predicate to use.
5122 * @return The last iterator @c i in the range
5123 * @p [first1,last1-(last2-first2)) such that @c predicate(*(i+N), @p
5124 * (first2+N)) is true for each @c N in the range @p [0,last2-first2), or
5125 * @p last1 if no such iterator exists.
5126 *
5127 * Searches the range @p [first1,last1) for a sub-sequence that compares
5128 * equal value-by-value with the sequence given by @p [first2,last2) using
5129 * comp as a predicate and returns an iterator to the first element of the
5130 * sub-sequence, or @p last1 if the sub-sequence is not found. The
5131 * sub-sequence will be the last such subsequence contained in
5132 * [first,last1).
5133 *
5134 * Because the sub-sequence must lie completely within the range
5135 * @p [first1,last1) it must start at a position less than
5136 * @p last1-(last2-first2) where @p last2-first2 is the length of the
5137 * sub-sequence.
5138 * This means that the returned iterator @c i will be in the range
5139 * @p [first1,last1-(last2-first2))
5140 */
5142 typename _BinaryPredicate>
5143 inline _ForwardIterator1
5146 _BinaryPredicate __comp)
5147 {
5148 // concept requirements
5160 __comp);
5161 }