| blob | cf3cd71851a004628f672d611954f86085c84215 |
1 // Algorithm implementation -*- C++ -*-
3 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006
4 // Free Software Foundation, Inc.
5 //
6 // This file is part of the GNU ISO C++ Library. This library is free
7 // software; you can redistribute it and/or modify it under the
8 // terms of the GNU General Public License as published by the
9 // Free Software Foundation; either version 2, or (at your option)
10 // any later version.
12 // This library is distributed in the hope that it will be useful,
13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 // GNU General Public License for more details.
17 // You should have received a copy of the GNU General Public License along
18 // with this library; see the file COPYING. If not, write to the Free
19 // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
20 // USA.
22 // As a special exception, you may use this file as part of a free software
23 // library without restriction. Specifically, if other files instantiate
24 // templates or use macros or inline functions from this file, or you compile
25 // this file and link it with other files to produce an executable, this
26 // file does not by itself cause the resulting executable to be covered by
27 // the GNU General Public License. This exception does not however
28 // invalidate any other reasons why the executable file might be covered by
29 // the GNU General Public License.
31 /*
32 *
33 * Copyright (c) 1994
34 * Hewlett-Packard Company
35 *
36 * Permission to use, copy, modify, distribute and sell this software
37 * and its documentation for any purpose is hereby granted without fee,
38 * provided that the above copyright notice appear in all copies and
39 * that both that copyright notice and this permission notice appear
40 * in supporting documentation. Hewlett-Packard Company makes no
41 * representations about the suitability of this software for any
42 * purpose. It is provided "as is" without express or implied warranty.
43 *
44 *
45 * Copyright (c) 1996
46 * Silicon Graphics Computer Systems, Inc.
47 *
48 * Permission to use, copy, modify, distribute and sell this software
49 * and its documentation for any purpose is hereby granted without fee,
50 * provided that the above copyright notice appear in all copies and
51 * that both that copyright notice and this permission notice appear
52 * in supporting documentation. Silicon Graphics makes no
53 * representations about the suitability of this software for any
54 * purpose. It is provided "as is" without express or implied warranty.
55 */
57 /** @file stl_algo.h
58 * This is an internal header file, included by other library headers.
59 * You should not attempt to use it directly.
60 */
62 #ifndef _ALGO_H
63 #define _ALGO_H 1
65 #include <bits/stl_heap.h>
67 #include <debug/debug.h>
69 // See concept_check.h for the __glibcxx_*_requires macros.
73 /**
74 * @brief Find the median of three values.
75 * @param a A value.
76 * @param b A value.
77 * @param c A value.
78 * @return One of @p a, @p b or @p c.
79 *
80 * If @c {l,m,n} is some convolution of @p {a,b,c} such that @c l<=m<=n
81 * then the value returned will be @c m.
82 * This is an SGI extension.
83 * @ingroup SGIextensions
84 */
88 {
89 // concept requirements
96 else
102 else
104 }
106 /**
107 * @brief Find the median of three values using a predicate for comparison.
108 * @param a A value.
109 * @param b A value.
110 * @param c A value.
111 * @param comp A binary predicate.
112 * @return One of @p a, @p b or @p c.
113 *
114 * If @c {l,m,n} is some convolution of @p {a,b,c} such that @p comp(l,m)
115 * and @p comp(m,n) are both true then the value returned will be @c m.
116 * This is an SGI extension.
117 * @ingroup SGIextensions
118 */
122 {
123 // concept requirements
130 else
136 else
138 }
140 /**
141 * @brief Apply a function to every element of a sequence.
142 * @param first An input iterator.
143 * @param last An input iterator.
144 * @param f A unary function object.
145 * @return @p f.
146 *
147 * Applies the function object @p f to each element in the range
148 * @p [first,last). @p f must not modify the order of the sequence.
149 * If @p f has a return value it is ignored.
150 */
152 _Function
154 {
155 // concept requirements
161 }
163 /**
164 * @if maint
165 * This is an overload used by find() for the Input Iterator case.
166 * @endif
167 */
169 inline _InputIterator
172 {
176 }
178 /**
179 * @if maint
180 * This is an overload used by find_if() for the Input Iterator case.
181 * @endif
182 */
184 inline _InputIterator
187 {
191 }
193 /**
194 * @if maint
195 * This is an overload used by find() for the RAI case.
196 * @endif
197 */
199 _RandomAccessIterator
202 {
207 {
223 }
226 {
242 }
243 }
245 /**
246 * @if maint
247 * This is an overload used by find_if() for the RAI case.
248 * @endif
249 */
251 _RandomAccessIterator
254 {
259 {
275 }
278 {
294 }
295 }
297 /**
298 * @if maint
299 * This is an overload of find() for streambuf iterators.
300 * @endif
301 */
308 /**
309 * @brief Find the first occurrence of a value in a sequence.
310 * @param first An input iterator.
311 * @param last An input iterator.
312 * @param val The value to find.
313 * @return The first iterator @c i in the range @p [first,last)
314 * such that @c *i == @p val, or @p last if no such iterator exists.
315 */
317 inline _InputIterator
320 {
321 // concept requirements
328 }
330 /**
331 * @brief Find the first element in a sequence for which a predicate is true.
332 * @param first An input iterator.
333 * @param last An input iterator.
334 * @param pred A predicate.
335 * @return The first iterator @c i in the range @p [first,last)
336 * such that @p pred(*i) is true, or @p last if no such iterator exists.
337 */
339 inline _InputIterator
341 _Predicate __pred)
342 {
343 // concept requirements
350 }
352 /**
353 * @brief Find two adjacent values in a sequence that are equal.
354 * @param first A forward iterator.
355 * @param last A forward iterator.
356 * @return The first iterator @c i such that @c i and @c i+1 are both
357 * valid iterators in @p [first,last) and such that @c *i == @c *(i+1),
358 * or @p last if no such iterator exists.
359 */
361 _ForwardIterator
363 {
364 // concept requirements
373 {
377 }
379 }
381 /**
382 * @brief Find two adjacent values in a sequence using a predicate.
383 * @param first A forward iterator.
384 * @param last A forward iterator.
385 * @param binary_pred A binary predicate.
386 * @return The first iterator @c i such that @c i and @c i+1 are both
387 * valid iterators in @p [first,last) and such that
388 * @p binary_pred(*i,*(i+1)) is true, or @p last if no such iterator
389 * exists.
390 */
392 _ForwardIterator
394 _BinaryPredicate __binary_pred)
395 {
396 // concept requirements
406 {
410 }
412 }
414 /**
415 * @brief Count the number of copies of a value in a sequence.
416 * @param first An input iterator.
417 * @param last An input iterator.
418 * @param value The value to be counted.
419 * @return The number of iterators @c i in the range @p [first,last)
420 * for which @c *i == @p value
421 */
425 {
426 // concept requirements
436 }
438 /**
439 * @brief Count the elements of a sequence for which a predicate is true.
440 * @param first An input iterator.
441 * @param last An input iterator.
442 * @param pred A predicate.
443 * @return The number of iterators @c i in the range @p [first,last)
444 * for which @p pred(*i) is true.
445 */
449 {
450 // concept requirements
460 }
462 /**
463 * @brief Search a sequence for a matching sub-sequence.
464 * @param first1 A forward iterator.
465 * @param last1 A forward iterator.
466 * @param first2 A forward iterator.
467 * @param last2 A forward iterator.
468 * @return The first iterator @c i in the range
469 * @p [first1,last1-(last2-first2)) such that @c *(i+N) == @p *(first2+N)
470 * for each @c N in the range @p [0,last2-first2), or @p last1 if no
471 * such iterator exists.
472 *
473 * Searches the range @p [first1,last1) for a sub-sequence that compares
474 * equal value-by-value with the sequence given by @p [first2,last2) and
475 * returns an iterator to the first element of the sub-sequence, or
476 * @p last1 if the sub-sequence is not found.
477 *
478 * Because the sub-sequence must lie completely within the range
479 * @p [first1,last1) it must start at a position less than
480 * @p last1-(last2-first2) where @p last2-first2 is the length of the
481 * sub-sequence.
482 * This means that the returned iterator @c i will be in the range
483 * @p [first1,last1-(last2-first2))
484 */
486 _ForwardIterator1
489 {
490 // concept requirements
498 // Test for empty ranges
502 // Test for a pattern of length 1.
508 // General case.
514 {
525 {
530 }
532 }
534 }
536 /**
537 * @brief Search a sequence for a matching sub-sequence using a predicate.
538 * @param first1 A forward iterator.
539 * @param last1 A forward iterator.
540 * @param first2 A forward iterator.
541 * @param last2 A forward iterator.
542 * @param predicate A binary predicate.
543 * @return The first iterator @c i in the range
544 * @p [first1,last1-(last2-first2)) such that
545 * @p predicate(*(i+N),*(first2+N)) is true for each @c N in the range
546 * @p [0,last2-first2), or @p last1 if no such iterator exists.
547 *
548 * Searches the range @p [first1,last1) for a sub-sequence that compares
549 * equal value-by-value with the sequence given by @p [first2,last2),
550 * using @p predicate to determine equality, and returns an iterator
551 * to the first element of the sub-sequence, or @p last1 if no such
552 * iterator exists.
553 *
554 * @see search(_ForwardIter1, _ForwardIter1, _ForwardIter2, _ForwardIter2)
555 */
557 typename _BinaryPredicate>
558 _ForwardIterator1
561 _BinaryPredicate __predicate)
562 {
563 // concept requirements
572 // Test for empty ranges
576 // Test for a pattern of length 1.
580 {
584 }
586 // General case.
592 {
594 {
598 }
610 {
615 }
617 }
619 }
621 /**
622 * @if maint
623 * This is an uglified
624 * search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&)
625 * overloaded for forward iterators.
626 * @endif
627 */
629 _ForwardIterator
633 {
636 {
642 {
645 }
651 }
653 }
655 /**
656 * @if maint
657 * This is an uglified
658 * search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&)
659 * overloaded for random access iterators.
660 * @endif
661 */
663 _RandomAccessIter
667 {
670 _DistanceType;
683 {
684 // __lookAhead here is always pointing to the last element of next
685 // possible match.
687 {
692 }
696 {
699 }
704 }
705 }
707 /**
708 * @brief Search a sequence for a number of consecutive values.
709 * @param first A forward iterator.
710 * @param last A forward iterator.
711 * @param count The number of consecutive values.
712 * @param val The value to find.
713 * @return The first iterator @c i in the range @p [first,last-count)
714 * such that @c *(i+N) == @p val for each @c N in the range @p [0,count),
715 * or @p last if no such iterator exists.
716 *
717 * Searches the range @p [first,last) for @p count consecutive elements
718 * equal to @p val.
719 */
721 _ForwardIterator
724 {
725 // concept requirements
737 }
739 /**
740 * @if maint
741 * This is an uglified
742 * search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&,
743 * _BinaryPredicate)
744 * overloaded for forward iterators.
745 * @endif
746 */
748 typename _BinaryPredicate>
749 _ForwardIterator
753 {
758 {
764 {
767 }
775 }
777 }
779 /**
780 * @if maint
781 * This is an uglified
782 * search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&,
783 * _BinaryPredicate)
784 * overloaded for random access iterators.
785 * @endif
786 */
788 typename _BinaryPredicate>
789 _RandomAccessIter
793 {
796 _DistanceType;
809 {
810 // __lookAhead here is always pointing to the last element of next
811 // possible match.
813 {
818 }
822 {
825 }
830 }
831 }
833 /**
834 * @brief Search a sequence for a number of consecutive values using a
835 * predicate.
836 * @param first A forward iterator.
837 * @param last A forward iterator.
838 * @param count The number of consecutive values.
839 * @param val The value to find.
840 * @param binary_pred A binary predicate.
841 * @return The first iterator @c i in the range @p [first,last-count)
842 * such that @p binary_pred(*(i+N),val) is true for each @c N in the
843 * range @p [0,count), or @p last if no such iterator exists.
844 *
845 * Searches the range @p [first,last) for @p count consecutive elements
846 * for which the predicate returns true.
847 */
849 typename _BinaryPredicate>
850 _ForwardIterator
853 _BinaryPredicate __binary_pred)
854 {
855 // concept requirements
864 {
868 }
871 }
873 /**
874 * @brief Swap the elements of two sequences.
875 * @param first1 A forward iterator.
876 * @param last1 A forward iterator.
877 * @param first2 A forward iterator.
878 * @return An iterator equal to @p first2+(last1-first1).
879 *
880 * Swaps each element in the range @p [first1,last1) with the
881 * corresponding element in the range @p [first2,(last1-first1)).
882 * The ranges must not overlap.
883 */
885 _ForwardIterator2
887 _ForwardIterator2 __first2)
888 {
889 // concept requirements
891 _ForwardIterator1>)
893 _ForwardIterator2>)
905 }
907 /**
908 * @brief Perform an operation on a sequence.
909 * @param first An input iterator.
910 * @param last An input iterator.
911 * @param result An output iterator.
912 * @param unary_op A unary operator.
913 * @return An output iterator equal to @p result+(last-first).
914 *
915 * Applies the operator to each element in the input range and assigns
916 * the results to successive elements of the output sequence.
917 * Evaluates @p *(result+N)=unary_op(*(first+N)) for each @c N in the
918 * range @p [0,last-first).
919 *
920 * @p unary_op must not alter its argument.
921 */
923 typename _UnaryOperation>
924 _OutputIterator
927 {
928 // concept requirements
931 // "the type returned by a _UnaryOperation"
938 }
940 /**
941 * @brief Perform an operation on corresponding elements of two sequences.
942 * @param first1 An input iterator.
943 * @param last1 An input iterator.
944 * @param first2 An input iterator.
945 * @param result An output iterator.
946 * @param binary_op A binary operator.
947 * @return An output iterator equal to @p result+(last-first).
948 *
949 * Applies the operator to the corresponding elements in the two
950 * input ranges and assigns the results to successive elements of the
951 * output sequence.
952 * Evaluates @p *(result+N)=binary_op(*(first1+N),*(first2+N)) for each
953 * @c N in the range @p [0,last1-first1).
954 *
955 * @p binary_op must not alter either of its arguments.
956 */
959 _OutputIterator
962 _BinaryOperation __binary_op)
963 {
964 // concept requirements
968 // "the type returned by a _BinaryOperation"
975 }
977 /**
978 * @brief Replace each occurrence of one value in a sequence with another
979 * value.
980 * @param first A forward iterator.
981 * @param last A forward iterator.
982 * @param old_value The value to be replaced.
983 * @param new_value The replacement value.
984 * @return replace() returns no value.
985 *
986 * For each iterator @c i in the range @p [first,last) if @c *i ==
987 * @p old_value then the assignment @c *i = @p new_value is performed.
988 */
990 void
993 {
994 // concept requirements
996 _ForwardIterator>)
1006 }
1008 /**
1009 * @brief Replace each value in a sequence for which a predicate returns
1010 * true with another value.
1011 * @param first A forward iterator.
1012 * @param last A forward iterator.
1013 * @param pred A predicate.
1014 * @param new_value The replacement value.
1015 * @return replace_if() returns no value.
1016 *
1017 * For each iterator @c i in the range @p [first,last) if @p pred(*i)
1018 * is true then the assignment @c *i = @p new_value is performed.
1019 */
1021 void
1024 {
1025 // concept requirements
1027 _ForwardIterator>)
1037 }
1039 /**
1040 * @brief Copy a sequence, replacing each element of one value with another
1041 * value.
1042 * @param first An input iterator.
1043 * @param last An input iterator.
1044 * @param result An output iterator.
1045 * @param old_value The value to be replaced.
1046 * @param new_value The replacement value.
1047 * @return The end of the output sequence, @p result+(last-first).
1048 *
1049 * Copies each element in the input range @p [first,last) to the
1050 * output range @p [result,result+(last-first)) replacing elements
1051 * equal to @p old_value with @p new_value.
1052 */
1054 _OutputIterator
1056 _OutputIterator __result,
1058 {
1059 // concept requirements
1070 else
1073 }
1075 /**
1076 * @brief Copy a sequence, replacing each value for which a predicate
1077 * returns true with another value.
1078 * @param first An input iterator.
1079 * @param last An input iterator.
1080 * @param result An output iterator.
1081 * @param pred A predicate.
1082 * @param new_value The replacement value.
1083 * @return The end of the output sequence, @p result+(last-first).
1084 *
1085 * Copies each element in the range @p [first,last) to the range
1086 * @p [result,result+(last-first)) replacing elements for which
1087 * @p pred returns true with @p new_value.
1088 */
1091 _OutputIterator
1093 _OutputIterator __result,
1095 {
1096 // concept requirements
1107 else
1110 }
1112 /**
1113 * @brief Assign the result of a function object to each value in a
1114 * sequence.
1115 * @param first A forward iterator.
1116 * @param last A forward iterator.
1117 * @param gen A function object taking no arguments.
1118 * @return generate() returns no value.
1119 *
1120 * Performs the assignment @c *i = @p gen() for each @c i in the range
1121 * @p [first,last).
1122 */
1124 void
1126 _Generator __gen)
1127 {
1128 // concept requirements
1136 }
1138 /**
1139 * @brief Assign the result of a function object to each value in a
1140 * sequence.
1141 * @param first A forward iterator.
1142 * @param n The length of the sequence.
1143 * @param gen A function object taking no arguments.
1144 * @return The end of the sequence, @p first+n
1145 *
1146 * Performs the assignment @c *i = @p gen() for each @c i in the range
1147 * @p [first,first+n).
1148 */
1150 _OutputIterator
1152 {
1153 // concept requirements
1155 // "the type returned by a _Generator"
1161 }
1163 /**
1164 * @brief Copy a sequence, removing elements of a given value.
1165 * @param first An input iterator.
1166 * @param last An input iterator.
1167 * @param result An output iterator.
1168 * @param value The value to be removed.
1169 * @return An iterator designating the end of the resulting sequence.
1170 *
1171 * Copies each element in the range @p [first,last) not equal to @p value
1172 * to the range beginning at @p result.
1173 * remove_copy() is stable, so the relative order of elements that are
1174 * copied is unchanged.
1175 */
1177 _OutputIterator
1180 {
1181 // concept requirements
1191 {
1194 }
1196 }
1198 /**
1199 * @brief Copy a sequence, removing elements for which a predicate is true.
1200 * @param first An input iterator.
1201 * @param last An input iterator.
1202 * @param result An output iterator.
1203 * @param pred A predicate.
1204 * @return An iterator designating the end of the resulting sequence.
1205 *
1206 * Copies each element in the range @p [first,last) for which
1207 * @p pred returns true to the range beginning at @p result.
1208 *
1209 * remove_copy_if() is stable, so the relative order of elements that are
1210 * copied is unchanged.
1211 */
1213 typename _Predicate>
1214 _OutputIterator
1217 {
1218 // concept requirements
1228 {
1231 }
1233 }
1235 /**
1236 * @brief Remove elements from a sequence.
1237 * @param first An input iterator.
1238 * @param last An input iterator.
1239 * @param value The value to be removed.
1240 * @return An iterator designating the end of the resulting sequence.
1241 *
1242 * All elements equal to @p value are removed from the range
1243 * @p [first,last).
1244 *
1245 * remove() is stable, so the relative order of elements that are
1246 * not removed is unchanged.
1247 *
1248 * Elements between the end of the resulting sequence and @p last
1249 * are still present, but their value is unspecified.
1250 */
1252 _ForwardIterator
1255 {
1256 // concept requirements
1258 _ForwardIterator>)
1268 }
1270 /**
1271 * @brief Remove elements from a sequence using a predicate.
1272 * @param first A forward iterator.
1273 * @param last A forward iterator.
1274 * @param pred A predicate.
1275 * @return An iterator designating the end of the resulting sequence.
1276 *
1277 * All elements for which @p pred returns true are removed from the range
1278 * @p [first,last).
1279 *
1280 * remove_if() is stable, so the relative order of elements that are
1281 * not removed is unchanged.
1282 *
1283 * Elements between the end of the resulting sequence and @p last
1284 * are still present, but their value is unspecified.
1285 */
1287 _ForwardIterator
1289 _Predicate __pred)
1290 {
1291 // concept requirements
1293 _ForwardIterator>)
1303 }
1305 /**
1306 * @if maint
1307 * This is an uglified unique_copy(_InputIterator, _InputIterator,
1308 * _OutputIterator)
1309 * overloaded for forward iterators and output iterator as result.
1310 * @endif
1311 */
1313 _OutputIterator
1315 _OutputIterator __result,
1317 {
1318 // concept requirements -- taken care of in dispatching function
1323 {
1326 }
1328 }
1330 /**
1331 * @if maint
1332 * This is an uglified unique_copy(_InputIterator, _InputIterator,
1333 * _OutputIterator)
1334 * overloaded for input iterators and output iterator as result.
1335 * @endif
1336 */
1338 _OutputIterator
1340 _OutputIterator __result,
1342 {
1343 // concept requirements -- taken care of in dispatching function
1348 {
1351 }
1353 }
1355 /**
1356 * @if maint
1357 * This is an uglified unique_copy(_InputIterator, _InputIterator,
1358 * _OutputIterator)
1359 * overloaded for input iterators and forward iterator as result.
1360 * @endif
1361 */
1363 _ForwardIterator
1365 _ForwardIterator __result,
1367 {
1368 // concept requirements -- taken care of in dispatching function
1374 }
1376 /**
1377 * @if maint
1378 * This is an uglified
1379 * unique_copy(_InputIterator, _InputIterator, _OutputIterator,
1380 * _BinaryPredicate)
1381 * overloaded for forward iterators and output iterator as result.
1382 * @endif
1383 */
1385 typename _BinaryPredicate>
1386 _OutputIterator
1390 {
1391 // concept requirements -- iterators already checked
1400 {
1403 }
1405 }
1407 /**
1408 * @if maint
1409 * This is an uglified
1410 * unique_copy(_InputIterator, _InputIterator, _OutputIterator,
1411 * _BinaryPredicate)
1412 * overloaded for input iterators and output iterator as result.
1413 * @endif
1414 */
1416 typename _BinaryPredicate>
1417 _OutputIterator
1421 {
1422 // concept requirements -- iterators already checked
1431 {
1434 }
1436 }
1438 /**
1439 * @if maint
1440 * This is an uglified
1441 * unique_copy(_InputIterator, _InputIterator, _OutputIterator,
1442 * _BinaryPredicate)
1443 * overloaded for input iterators and forward iterator as result.
1444 * @endif
1445 */
1447 typename _BinaryPredicate>
1448 _ForwardIterator
1452 {
1453 // concept requirements -- iterators already checked
1463 }
1465 /**
1466 * @brief Copy a sequence, removing consecutive duplicate values.
1467 * @param first An input iterator.
1468 * @param last An input iterator.
1469 * @param result An output iterator.
1470 * @return An iterator designating the end of the resulting sequence.
1471 *
1472 * Copies each element in the range @p [first,last) to the range
1473 * beginning at @p result, except that only the first element is copied
1474 * from groups of consecutive elements that compare equal.
1475 * unique_copy() is stable, so the relative order of elements that are
1476 * copied is unchanged.
1477 *
1478 * @if maint
1479 * _GLIBCXX_RESOLVE_LIB_DEFECTS
1480 * DR 241. Does unique_copy() require CopyConstructible and Assignable?
1481 *
1482 * _GLIBCXX_RESOLVE_LIB_DEFECTS
1483 * DR 538. 241 again: Does unique_copy() require CopyConstructible and
1484 * Assignable?
1485 * @endif
1486 */
1488 inline _OutputIterator
1490 _OutputIterator __result)
1491 {
1492 // concept requirements
1505 }
1507 /**
1508 * @brief Copy a sequence, removing consecutive values using a predicate.
1509 * @param first An input iterator.
1510 * @param last An input iterator.
1511 * @param result An output iterator.
1512 * @param binary_pred A binary predicate.
1513 * @return An iterator designating the end of the resulting sequence.
1514 *
1515 * Copies each element in the range @p [first,last) to the range
1516 * beginning at @p result, except that only the first element is copied
1517 * from groups of consecutive elements for which @p binary_pred returns
1518 * true.
1519 * unique_copy() is stable, so the relative order of elements that are
1520 * copied is unchanged.
1521 *
1522 * @if maint
1523 * _GLIBCXX_RESOLVE_LIB_DEFECTS
1524 * DR 241. Does unique_copy() require CopyConstructible and Assignable?
1525 * @endif
1526 */
1528 typename _BinaryPredicate>
1529 inline _OutputIterator
1531 _OutputIterator __result,
1532 _BinaryPredicate __binary_pred)
1533 {
1534 // concept requirements -- predicates checked later
1545 }
1547 /**
1548 * @brief Remove consecutive duplicate values from a sequence.
1549 * @param first A forward iterator.
1550 * @param last A forward iterator.
1551 * @return An iterator designating the end of the resulting sequence.
1552 *
1553 * Removes all but the first element from each group of consecutive
1554 * values that compare equal.
1555 * unique() is stable, so the relative order of elements that are
1556 * not removed is unchanged.
1557 * Elements between the end of the resulting sequence and @p last
1558 * are still present, but their value is unspecified.
1559 */
1561 _ForwardIterator
1563 {
1564 // concept requirements
1566 _ForwardIterator>)
1571 // Skip the beginning, if already unique.
1576 // Do the real copy work.
1583 }
1585 /**
1586 * @brief Remove consecutive values from a sequence using a predicate.
1587 * @param first A forward iterator.
1588 * @param last A forward iterator.
1589 * @param binary_pred A binary predicate.
1590 * @return An iterator designating the end of the resulting sequence.
1591 *
1592 * Removes all but the first element from each group of consecutive
1593 * values for which @p binary_pred returns true.
1594 * unique() is stable, so the relative order of elements that are
1595 * not removed is unchanged.
1596 * Elements between the end of the resulting sequence and @p last
1597 * are still present, but their value is unspecified.
1598 */
1600 _ForwardIterator
1602 _BinaryPredicate __binary_pred)
1603 {
1604 // concept requirements
1606 _ForwardIterator>)
1612 // Skip the beginning, if already unique.
1617 // Do the real copy work.
1624 }
1626 /**
1627 * @if maint
1628 * This is an uglified reverse(_BidirectionalIterator,
1629 * _BidirectionalIterator)
1630 * overloaded for bidirectional iterators.
1631 * @endif
1632 */
1634 void
1636 bidirectional_iterator_tag)
1637 {
1641 else
1642 {
1645 }
1646 }
1648 /**
1649 * @if maint
1650 * This is an uglified reverse(_BidirectionalIterator,
1651 * _BidirectionalIterator)
1652 * overloaded for random access iterators.
1653 * @endif
1654 */
1656 void
1658 random_access_iterator_tag)
1659 {
1664 {
1668 }
1669 }
1671 /**
1672 * @brief Reverse a sequence.
1673 * @param first A bidirectional iterator.
1674 * @param last A bidirectional iterator.
1675 * @return reverse() returns no value.
1676 *
1677 * Reverses the order of the elements in the range @p [first,last),
1678 * so that the first element becomes the last etc.
1679 * For every @c i such that @p 0<=i<=(last-first)/2), @p reverse()
1680 * swaps @p *(first+i) and @p *(last-(i+1))
1681 */
1685 {
1686 // concept requirements
1688 _BidirectionalIterator>)
1691 }
1693 /**
1694 * @brief Copy a sequence, reversing its elements.
1695 * @param first A bidirectional iterator.
1696 * @param last A bidirectional iterator.
1697 * @param result An output iterator.
1698 * @return An iterator designating the end of the resulting sequence.
1699 *
1700 * Copies the elements in the range @p [first,last) to the range
1701 * @p [result,result+(last-first)) such that the order of the
1702 * elements is reversed.
1703 * For every @c i such that @p 0<=i<=(last-first), @p reverse_copy()
1704 * performs the assignment @p *(result+(last-first)-i) = *(first+i).
1705 * The ranges @p [first,last) and @p [result,result+(last-first))
1706 * must not overlap.
1707 */
1709 _OutputIterator
1711 _OutputIterator __result)
1712 {
1713 // concept requirements
1715 _BidirectionalIterator>)
1721 {
1725 }
1727 }
1730 /**
1731 * @if maint
1732 * This is a helper function for the rotate algorithm specialized on RAIs.
1733 * It returns the greatest common divisor of two integer values.
1734 * @endif
1735 */
1737 _EuclideanRingElement
1739 {
1741 {
1745 }
1747 }
1749 /**
1750 * @if maint
1751 * This is a helper function for the rotate algorithm.
1752 * @endif
1753 */
1755 void
1757 _ForwardIterator __middle,
1758 _ForwardIterator __last,
1759 forward_iterator_tag)
1760 {
1765 do
1766 {
1772 }
1778 {
1786 }
1787 }
1789 /**
1790 * @if maint
1791 * This is a helper function for the rotate algorithm.
1792 * @endif
1793 */
1795 void
1797 _BidirectionalIterator __middle,
1798 _BidirectionalIterator __last,
1799 bidirectional_iterator_tag)
1800 {
1801 // concept requirements
1803 _BidirectionalIterator>)
1812 {
1815 }
1819 else
1821 }
1823 /**
1824 * @if maint
1825 * This is a helper function for the rotate algorithm.
1826 * @endif
1827 */
1829 void
1831 _RandomAccessIterator __middle,
1832 _RandomAccessIterator __last,
1833 random_access_iterator_tag)
1834 {
1835 // concept requirements
1837 _RandomAccessIterator>)
1843 _Distance;
1845 _ValueType;
1852 {
1855 }
1860 {
1865 {
1867 {
1869 {
1872 }
1876 }
1877 }
1878 else
1879 {
1881 {
1883 {
1886 }
1889 }
1890 }
1894 }
1895 }
1897 /**
1898 * @brief Rotate the elements of a sequence.
1899 * @param first A forward iterator.
1900 * @param middle A forward iterator.
1901 * @param last A forward iterator.
1902 * @return Nothing.
1903 *
1904 * Rotates the elements of the range @p [first,last) by @p (middle-first)
1905 * positions so that the element at @p middle is moved to @p first, the
1906 * element at @p middle+1 is moved to @first+1 and so on for each element
1907 * in the range @p [first,last).
1908 *
1909 * This effectively swaps the ranges @p [first,middle) and
1910 * @p [middle,last).
1911 *
1912 * Performs @p *(first+(n+(last-middle))%(last-first))=*(first+n) for
1913 * each @p n in the range @p [0,last-first).
1914 */
1918 _ForwardIterator __last)
1919 {
1920 // concept requirements
1922 _ForwardIterator>)
1927 _IterType;
1929 }
1931 /**
1932 * @brief Copy a sequence, rotating its elements.
1933 * @param first A forward iterator.
1934 * @param middle A forward iterator.
1935 * @param last A forward iterator.
1936 * @param result An output iterator.
1937 * @return An iterator designating the end of the resulting sequence.
1938 *
1939 * Copies the elements of the range @p [first,last) to the range
1940 * beginning at @result, rotating the copied elements by @p (middle-first)
1941 * positions so that the element at @p middle is moved to @p result, the
1942 * element at @p middle+1 is moved to @result+1 and so on for each element
1943 * in the range @p [first,last).
1944 *
1945 * Performs @p *(result+(n+(last-middle))%(last-first))=*(first+n) for
1946 * each @p n in the range @p [0,last-first).
1947 */
1949 _OutputIterator
1952 {
1953 // concept requirements
1962 }
1964 /**
1965 * @brief Randomly shuffle the elements of a sequence.
1966 * @param first A forward iterator.
1967 * @param last A forward iterator.
1968 * @return Nothing.
1969 *
1970 * Reorder the elements in the range @p [first,last) using a random
1971 * distribution, so that every possible ordering of the sequence is
1972 * equally likely.
1973 */
1977 {
1978 // concept requirements
1980 _RandomAccessIterator>)
1986 }
1988 /**
1989 * @brief Shuffle the elements of a sequence using a random number
1990 * generator.
1991 * @param first A forward iterator.
1992 * @param last A forward iterator.
1993 * @param rand The RNG functor or function.
1994 * @return Nothing.
1995 *
1996 * Reorders the elements in the range @p [first,last) using @p rand to
1997 * provide a random distribution. Calling @p rand(N) for a positive
1998 * integer @p N should return a randomly chosen integer from the
1999 * range [0,N).
2000 */
2002 void
2005 {
2006 // concept requirements
2008 _RandomAccessIterator>)
2015 }
2018 /**
2019 * @if maint
2020 * This is a helper function...
2021 * @endif
2022 */
2024 _ForwardIterator
2026 _Predicate __pred,
2027 forward_iterator_tag)
2028 {
2040 {
2043 }
2046 }
2048 /**
2049 * @if maint
2050 * This is a helper function...
2051 * @endif
2052 */
2054 _BidirectionalIterator
2056 _Predicate __pred,
2057 bidirectional_iterator_tag)
2058 {
2060 {
2066 else
2074 else
2078 }
2079 }
2081 /**
2082 * @brief Move elements for which a predicate is true to the beginning
2083 * of a sequence.
2084 * @param first A forward iterator.
2085 * @param last A forward iterator.
2086 * @param pred A predicate functor.
2087 * @return An iterator @p middle such that @p pred(i) is true for each
2088 * iterator @p i in the range @p [first,middle) and false for each @p i
2089 * in the range @p [middle,last).
2090 *
2091 * @p pred must not modify its operand. @p partition() does not preserve
2092 * the relative ordering of elements in each group, use
2093 * @p stable_partition() if this is needed.
2094 */
2096 inline _ForwardIterator
2098 _Predicate __pred)
2099 {
2100 // concept requirements
2102 _ForwardIterator>)
2109 }
2112 /**
2113 * @if maint
2114 * This is a helper function...
2115 * @endif
2116 */
2118 _ForwardIterator
2120 _ForwardIterator __last,
2122 {
2128 __middle,
2129 __pred,
2132 __pred,
2133 __len
2138 }
2140 /**
2141 * @if maint
2142 * This is a helper function...
2143 * @endif
2144 */
2146 typename _Distance>
2147 _ForwardIterator
2149 _ForwardIterator __last,
2151 _Pointer __buffer,
2152 _Distance __buffer_size)
2153 {
2155 {
2160 {
2163 }
2164 else
2165 {
2168 }
2171 }
2172 else
2173 {
2176 _ForwardIterator __begin =
2179 __buffer_size);
2180 _ForwardIterator __end =
2187 }
2188 }
2190 /**
2191 * @brief Move elements for which a predicate is true to the beginning
2192 * of a sequence, preserving relative ordering.
2193 * @param first A forward iterator.
2194 * @param last A forward iterator.
2195 * @param pred A predicate functor.
2196 * @return An iterator @p middle such that @p pred(i) is true for each
2197 * iterator @p i in the range @p [first,middle) and false for each @p i
2198 * in the range @p [middle,last).
2199 *
2200 * Performs the same function as @p partition() with the additional
2201 * guarantee that the relative ordering of elements in each group is
2202 * preserved, so any two elements @p x and @p y in the range
2203 * @p [first,last) such that @p pred(x)==pred(y) will have the same
2204 * relative ordering after calling @p stable_partition().
2205 */
2207 _ForwardIterator
2209 _Predicate __pred)
2210 {
2211 // concept requirements
2213 _ForwardIterator>)
2220 else
2221 {
2223 _ValueType;
2225 _DistanceType;
2228 __last);
2230 return
2234 else
2235 return
2238 }
2239 }
2241 /**
2242 * @if maint
2243 * This is a helper function...
2244 * @endif
2245 */
2247 _RandomAccessIterator
2250 {
2252 {
2262 }
2263 }
2265 /**
2266 * @if maint
2267 * This is a helper function...
2268 * @endif
2269 */
2271 _RandomAccessIterator
2273 _RandomAccessIterator __last,
2275 {
2277 {
2287 }
2288 }
2290 /**
2291 * @if maint
2292 * @doctodo
2293 * This controls some aspect of the sort routines.
2294 * @endif
2295 */
2298 /**
2299 * @if maint
2300 * This is a helper function for the sort routine.
2301 * @endif
2302 */
2304 void
2306 {
2310 {
2314 }
2316 }
2318 /**
2319 * @if maint
2320 * This is a helper function for the sort routine.
2321 * @endif
2322 */
2324 void
2326 _Compare __comp)
2327 {
2331 {
2335 }
2337 }
2339 /**
2340 * @if maint
2341 * This is a helper function for the sort routine.
2342 * @endif
2343 */
2345 void
2347 _RandomAccessIterator __last)
2348 {
2353 {
2357 {
2360 }
2361 else
2363 }
2364 }
2366 /**
2367 * @if maint
2368 * This is a helper function for the sort routine.
2369 * @endif
2370 */
2372 void
2375 {
2379 {
2383 {
2386 }
2387 else
2389 }
2390 }
2392 /**
2393 * @if maint
2394 * This is a helper function for the sort routine.
2395 * @endif
2396 */
2400 _RandomAccessIterator __last)
2401 {
2403 _ValueType;
2407 }
2409 /**
2410 * @if maint
2411 * This is a helper function for the sort routine.
2412 * @endif
2413 */
2418 {
2420 _ValueType;
2424 }
2426 /**
2427 * @if maint
2428 * This is a helper function for the sort routine.
2429 * @endif
2430 */
2432 void
2434 _RandomAccessIterator __last)
2435 {
2437 {
2440 }
2441 else
2443 }
2445 /**
2446 * @if maint
2447 * This is a helper function for the sort routine.
2448 * @endif
2449 */
2451 void
2454 {
2456 {
2459 __comp);
2460 }
2461 else
2463 }
2465 /**
2466 * @if maint
2467 * This is a helper function for the sort routines.
2468 * @endif
2469 */
2471 void
2473 _RandomAccessIterator __middle,
2474 _RandomAccessIterator __last)
2475 {
2477 _ValueType;
2483 }
2485 /**
2486 * @if maint
2487 * This is a helper function for the sort routines.
2488 * @endif
2489 */
2491 void
2493 _RandomAccessIterator __middle,
2495 {
2497 _ValueType;
2503 }
2505 /**
2506 * @if maint
2507 * This is a helper function for the sort routines.
2508 * @endif
2509 */
2511 inline _Size
2513 {
2514 _Size __k;
2518 }
2520 /**
2521 * @brief Sort the smallest elements of a sequence.
2522 * @param first An iterator.
2523 * @param middle Another iterator.
2524 * @param last Another iterator.
2525 * @return Nothing.
2526 *
2527 * Sorts the smallest @p (middle-first) elements in the range
2528 * @p [first,last) and moves them to the range @p [first,middle). The
2529 * order of the remaining elements in the range @p [middle,last) is
2530 * undefined.
2531 * After the sort if @p i and @j are iterators in the range
2532 * @p [first,middle) such that @i precedes @j and @k is an iterator in
2533 * the range @p [middle,last) then @p *j<*i and @p *k<*i are both false.
2534 */
2538 _RandomAccessIterator __middle,
2539 _RandomAccessIterator __last)
2540 {
2542 _ValueType;
2544 // concept requirements
2546 _RandomAccessIterator>)
2553 }
2555 /**
2556 * @brief Sort the smallest elements of a sequence using a predicate
2557 * for comparison.
2558 * @param first An iterator.
2559 * @param middle Another iterator.
2560 * @param last Another iterator.
2561 * @param comp A comparison functor.
2562 * @return Nothing.
2563 *
2564 * Sorts the smallest @p (middle-first) elements in the range
2565 * @p [first,last) and moves them to the range @p [first,middle). The
2566 * order of the remaining elements in the range @p [middle,last) is
2567 * undefined.
2568 * After the sort if @p i and @j are iterators in the range
2569 * @p [first,middle) such that @i precedes @j and @k is an iterator in
2570 * the range @p [middle,last) then @p *comp(j,*i) and @p comp(*k,*i)
2571 * are both false.
2572 */
2576 _RandomAccessIterator __middle,
2577 _RandomAccessIterator __last,
2578 _Compare __comp)
2579 {
2581 _ValueType;
2583 // concept requirements
2585 _RandomAccessIterator>)
2593 }
2595 /**
2596 * @brief Copy the smallest elements of a sequence.
2597 * @param first An iterator.
2598 * @param last Another iterator.
2599 * @param result_first A random-access iterator.
2600 * @param result_last Another random-access iterator.
2601 * @return An iterator indicating the end of the resulting sequence.
2602 *
2603 * Copies and sorts the smallest N values from the range @p [first,last)
2604 * to the range beginning at @p result_first, where the number of
2605 * elements to be copied, @p N, is the smaller of @p (last-first) and
2606 * @p (result_last-result_first).
2607 * After the sort if @p i and @j are iterators in the range
2608 * @p [result_first,result_first+N) such that @i precedes @j then
2609 * @p *j<*i is false.
2610 * The value returned is @p result_first+N.
2611 */
2613 _RandomAccessIterator
2615 _RandomAccessIterator __result_first,
2616 _RandomAccessIterator __result_last)
2617 {
2619 _InputValueType;
2621 _OutputValueType;
2623 _DistanceType;
2625 // concept requirements
2628 _OutputValueType>)
2630 _OutputValueType>)
2639 {
2643 }
2646 {
2653 }
2656 }
2658 /**
2659 * @brief Copy the smallest elements of a sequence using a predicate for
2660 * comparison.
2661 * @param first An input iterator.
2662 * @param last Another input iterator.
2663 * @param result_first A random-access iterator.
2664 * @param result_last Another random-access iterator.
2665 * @param comp A comparison functor.
2666 * @return An iterator indicating the end of the resulting sequence.
2667 *
2668 * Copies and sorts the smallest N values from the range @p [first,last)
2669 * to the range beginning at @p result_first, where the number of
2670 * elements to be copied, @p N, is the smaller of @p (last-first) and
2671 * @p (result_last-result_first).
2672 * After the sort if @p i and @j are iterators in the range
2673 * @p [result_first,result_first+N) such that @i precedes @j then
2674 * @p comp(*j,*i) is false.
2675 * The value returned is @p result_first+N.
2676 */
2678 _RandomAccessIterator
2680 _RandomAccessIterator __result_first,
2681 _RandomAccessIterator __result_last,
2682 _Compare __comp)
2683 {
2685 _InputValueType;
2687 _OutputValueType;
2689 _DistanceType;
2691 // concept requirements
2694 _RandomAccessIterator>)
2696 _OutputValueType>)
2708 {
2712 }
2715 {
2721 __comp);
2723 }
2726 }
2728 /**
2729 * @if maint
2730 * This is a helper function for the sort routine.
2731 * @endif
2732 */
2734 void
2736 _RandomAccessIterator __last,
2737 _Size __depth_limit)
2738 {
2740 _ValueType;
2743 {
2745 {
2748 }
2750 _RandomAccessIterator __cut =
2753 *(__first
2754 + (__last
2757 *(__last
2761 }
2762 }
2764 /**
2765 * @if maint
2766 * This is a helper function for the sort routine.
2767 * @endif
2768 */
2770 void
2772 _RandomAccessIterator __last,
2774 {
2776 _ValueType;
2779 {
2781 {
2784 }
2786 _RandomAccessIterator __cut =
2789 *(__first
2790 + (__last
2794 __comp)),
2795 __comp);
2798 }
2799 }
2801 /**
2802 * @brief Sort the elements of a sequence.
2803 * @param first An iterator.
2804 * @param last Another iterator.
2805 * @return Nothing.
2806 *
2807 * Sorts the elements in the range @p [first,last) in ascending order,
2808 * such that @p *(i+1)<*i is false for each iterator @p i in the range
2809 * @p [first,last-1).
2810 *
2811 * The relative ordering of equivalent elements is not preserved, use
2812 * @p stable_sort() if this is needed.
2813 */
2817 {
2819 _ValueType;
2821 // concept requirements
2823 _RandomAccessIterator>)
2828 {
2832 }
2833 }
2835 /**
2836 * @brief Sort the elements of a sequence using a predicate for comparison.
2837 * @param first An iterator.
2838 * @param last Another iterator.
2839 * @param comp A comparison functor.
2840 * @return Nothing.
2841 *
2842 * Sorts the elements in the range @p [first,last) in ascending order,
2843 * such that @p comp(*(i+1),*i) is false for every iterator @p i in the
2844 * range @p [first,last-1).
2845 *
2846 * The relative ordering of equivalent elements is not preserved, use
2847 * @p stable_sort() if this is needed.
2848 */
2852 _Compare __comp)
2853 {
2855 _ValueType;
2857 // concept requirements
2859 _RandomAccessIterator>)
2861 _ValueType>)
2865 {
2869 }
2870 }
2872 /**
2873 * @brief Finds the first position in which @a val could be inserted
2874 * without changing the ordering.
2875 * @param first An iterator.
2876 * @param last Another iterator.
2877 * @param val The search term.
2878 * @return An iterator pointing to the first element "not less than" @a val,
2879 * or end() if every element is less than @a val.
2880 * @ingroup binarysearch
2881 */
2883 _ForwardIterator
2886 {
2888 _ValueType;
2890 _DistanceType;
2892 // concept requirements
2898 _DistanceType __half;
2899 _ForwardIterator __middle;
2902 {
2907 {
2911 }
2912 else
2914 }
2916 }
2918 /**
2919 * @brief Finds the first position in which @a val could be inserted
2920 * without changing the ordering.
2921 * @param first An iterator.
2922 * @param last Another iterator.
2923 * @param val The search term.
2924 * @param comp A functor to use for comparisons.
2925 * @return An iterator pointing to the first element "not less than" @a val,
2926 * or end() if every element is less than @a val.
2927 * @ingroup binarysearch
2928 *
2929 * The comparison function should have the same effects on ordering as
2930 * the function used for the initial sort.
2931 */
2933 _ForwardIterator
2936 {
2938 _ValueType;
2940 _DistanceType;
2942 // concept requirements
2949 _DistanceType __half;
2950 _ForwardIterator __middle;
2953 {
2958 {
2962 }
2963 else
2965 }
2967 }
2969 /**
2970 * @brief Finds the last position in which @a val could be inserted
2971 * without changing the ordering.
2972 * @param first An iterator.
2973 * @param last Another iterator.
2974 * @param val The search term.
2975 * @return An iterator pointing to the first element greater than @a val,
2976 * or end() if no elements are greater than @a val.
2977 * @ingroup binarysearch
2978 */
2980 _ForwardIterator
2983 {
2985 _ValueType;
2987 _DistanceType;
2989 // concept requirements
2995 _DistanceType __half;
2996 _ForwardIterator __middle;
2999 {
3005 else
3006 {
3010 }
3011 }
3013 }
3015 /**
3016 * @brief Finds the last position in which @a val could be inserted
3017 * without changing the ordering.
3018 * @param first An iterator.
3019 * @param last Another iterator.
3020 * @param val The search term.
3021 * @param comp A functor to use for comparisons.
3022 * @return An iterator pointing to the first element greater than @a val,
3023 * or end() if no elements are greater than @a val.
3024 * @ingroup binarysearch
3025 *
3026 * The comparison function should have the same effects on ordering as
3027 * the function used for the initial sort.
3028 */
3030 _ForwardIterator
3033 {
3035 _ValueType;
3037 _DistanceType;
3039 // concept requirements
3046 _DistanceType __half;
3047 _ForwardIterator __middle;
3050 {
3056 else
3057 {
3061 }
3062 }
3064 }
3066 /**
3067 * @if maint
3068 * This is a helper function for the merge routines.
3069 * @endif
3070 */
3072 void
3074 _BidirectionalIterator __middle,
3075 _BidirectionalIterator __last,
3077 {
3081 {
3085 }
3091 {
3096 }
3097 else
3098 {
3103 }
3111 }
3113 /**
3114 * @if maint
3115 * This is a helper function for the merge routines.
3116 * @endif
3117 */
3119 typename _Compare>
3120 void
3122 _BidirectionalIterator __middle,
3123 _BidirectionalIterator __last,
3125 _Compare __comp)
3126 {
3130 {
3134 }
3140 {
3144 __comp);
3146 }
3147 else
3148 {
3152 __comp);
3154 }
3162 }
3164 /**
3165 * @if maint
3166 * This is a helper function for the stable sorting routines.
3167 * @endif
3168 */
3170 void
3172 _RandomAccessIterator __last)
3173 {
3175 {
3178 }
3185 }
3187 /**
3188 * @if maint
3189 * This is a helper function for the stable sorting routines.
3190 * @endif
3191 */
3193 void
3196 {
3198 {
3201 }
3208 __comp);
3209 }
3211 /**
3212 * @brief Merges two sorted ranges.
3213 * @param first1 An iterator.
3214 * @param first2 Another iterator.
3215 * @param last1 Another iterator.
3216 * @param last2 Another iterator.
3217 * @param result An iterator pointing to the end of the merged range.
3218 * @return An iterator pointing to the first element "not less than" @a val.
3219 *
3220 * Merges the ranges [first1,last1) and [first2,last2) into the sorted range
3221 * [result, result + (last1-first1) + (last2-first2)). Both input ranges
3222 * must be sorted, and the output range must not overlap with either of
3223 * the input ranges. The sort is @e stable, that is, for equivalent
3224 * elements in the two ranges, elements from the first range will always
3225 * come before elements from the second.
3226 */
3228 typename _OutputIterator>
3229 _OutputIterator
3232 _OutputIterator __result)
3233 {
3235 _ValueType1;
3237 _ValueType2;
3239 // concept requirements
3243 _ValueType1>)
3245 _ValueType2>)
3251 {
3253 {
3256 }
3257 else
3258 {
3261 }
3263 }
3265 __result));
3266 }
3268 /**
3269 * @brief Merges two sorted ranges.
3270 * @param first1 An iterator.
3271 * @param first2 Another iterator.
3272 * @param last1 Another iterator.
3273 * @param last2 Another iterator.
3274 * @param result An iterator pointing to the end of the merged range.
3275 * @param comp A functor to use for comparisons.
3276 * @return An iterator pointing to the first element "not less than" @a val.
3277 *
3278 * Merges the ranges [first1,last1) and [first2,last2) into the sorted range
3279 * [result, result + (last1-first1) + (last2-first2)). Both input ranges
3280 * must be sorted, and the output range must not overlap with either of
3281 * the input ranges. The sort is @e stable, that is, for equivalent
3282 * elements in the two ranges, elements from the first range will always
3283 * come before elements from the second.
3284 *
3285 * The comparison function should have the same effects on ordering as
3286 * the function used for the initial sort.
3287 */
3290 _OutputIterator
3294 {
3296 _ValueType1;
3298 _ValueType2;
3300 // concept requirements
3304 _ValueType1>)
3306 _ValueType2>)
3313 {
3315 {
3318 }
3319 else
3320 {
3323 }
3325 }
3327 __result));
3328 }
3331 typename _Distance>
3332 void
3334 _RandomAccessIterator1 __last,
3335 _RandomAccessIterator2 __result,
3336 _Distance __step_size)
3337 {
3341 {
3344 __result);
3346 }
3350 __result);
3351 }
3355 void
3357 _RandomAccessIterator1 __last,
3359 _Compare __comp)
3360 {
3364 {
3367 __result,
3368 __comp);
3370 }
3375 __result,
3376 __comp);
3377 }
3382 void
3384 _RandomAccessIterator __last,
3385 _Distance __chunk_size)
3386 {
3388 {
3391 }
3393 }
3396 void
3398 _RandomAccessIterator __last,
3400 {
3402 {
3405 }
3407 }
3410 void
3412 _RandomAccessIterator __last,
3413 _Pointer __buffer)
3414 {
3416 _Distance;
3425 {
3430 }
3431 }
3434 void
3436 _RandomAccessIterator __last,
3438 {
3440 _Distance;
3449 {
3456 }
3457 }
3459 /**
3460 * @if maint
3461 * This is a helper function for the merge routines.
3462 * @endif
3463 */
3465 typename _BidirectionalIterator3>
3466 _BidirectionalIterator3
3468 _BidirectionalIterator1 __last1,
3469 _BidirectionalIterator2 __first2,
3470 _BidirectionalIterator2 __last2,
3471 _BidirectionalIterator3 __result)
3472 {
3480 {
3482 {
3487 }
3488 else
3489 {
3494 }
3495 }
3496 }
3498 /**
3499 * @if maint
3500 * This is a helper function for the merge routines.
3501 * @endif
3502 */
3505 _BidirectionalIterator3
3507 _BidirectionalIterator1 __last1,
3508 _BidirectionalIterator2 __first2,
3509 _BidirectionalIterator2 __last2,
3510 _BidirectionalIterator3 __result,
3511 _Compare __comp)
3512 {
3520 {
3522 {
3527 }
3528 else
3529 {
3534 }
3535 }
3536 }
3538 /**
3539 * @if maint
3540 * This is a helper function for the merge routines.
3541 * @endif
3542 */
3544 typename _Distance>
3545 _BidirectionalIterator1
3547 _BidirectionalIterator1 __middle,
3548 _BidirectionalIterator1 __last,
3550 _BidirectionalIterator2 __buffer,
3551 _Distance __buffer_size)
3552 {
3553 _BidirectionalIterator2 __buffer_end;
3555 {
3559 }
3561 {
3565 }
3566 else
3567 {
3571 }
3572 }
3574 /**
3575 * @if maint
3576 * This is a helper function for the merge routines.
3577 * @endif
3578 */
3580 typename _Pointer>
3581 void
3583 _BidirectionalIterator __middle,
3584 _BidirectionalIterator __last,
3587 {
3589 {
3592 }
3594 {
3598 }
3599 else
3600 {
3606 {
3612 }
3613 else
3614 {
3620 }
3621 _BidirectionalIterator __new_middle =
3624 __buffer_size);
3630 }
3631 }
3633 /**
3634 * @if maint
3635 * This is a helper function for the merge routines.
3636 * @endif
3637 */
3639 typename _Compare>
3640 void
3642 _BidirectionalIterator __middle,
3643 _BidirectionalIterator __last,
3646 _Compare __comp)
3647 {
3649 {
3652 }
3654 {
3658 }
3659 else
3660 {
3666 {
3670 __comp);
3672 }
3673 else
3674 {
3678 __comp);
3680 }
3681 _BidirectionalIterator __new_middle =
3684 __buffer_size);
3691 }
3692 }
3694 /**
3695 * @brief Merges two sorted ranges in place.
3696 * @param first An iterator.
3697 * @param middle Another iterator.
3698 * @param last Another iterator.
3699 * @return Nothing.
3700 *
3701 * Merges two sorted and consecutive ranges, [first,middle) and
3702 * [middle,last), and puts the result in [first,last). The output will
3703 * be sorted. The sort is @e stable, that is, for equivalent
3704 * elements in the two ranges, elements from the first range will always
3705 * come before elements from the second.
3706 *
3707 * If enough additional memory is available, this takes (last-first)-1
3708 * comparisons. Otherwise an NlogN algorithm is used, where N is
3709 * distance(first,last).
3710 */
3712 void
3714 _BidirectionalIterator __middle,
3715 _BidirectionalIterator __last)
3716 {
3718 _ValueType;
3720 _DistanceType;
3722 // concept requirements
3724 _BidirectionalIterator>)
3736 __last);
3739 else
3742 }
3744 /**
3745 * @brief Merges two sorted ranges in place.
3746 * @param first An iterator.
3747 * @param middle Another iterator.
3748 * @param last Another iterator.
3749 * @param comp A functor to use for comparisons.
3750 * @return Nothing.
3751 *
3752 * Merges two sorted and consecutive ranges, [first,middle) and
3753 * [middle,last), and puts the result in [first,last). The output will
3754 * be sorted. The sort is @e stable, that is, for equivalent
3755 * elements in the two ranges, elements from the first range will always
3756 * come before elements from the second.
3757 *
3758 * If enough additional memory is available, this takes (last-first)-1
3759 * comparisons. Otherwise an NlogN algorithm is used, where N is
3760 * distance(first,last).
3761 *
3762 * The comparison function should have the same effects on ordering as
3763 * the function used for the initial sort.
3764 */
3766 void
3768 _BidirectionalIterator __middle,
3769 _BidirectionalIterator __last,
3770 _Compare __comp)
3771 {
3773 _ValueType;
3775 _DistanceType;
3777 // concept requirements
3779 _BidirectionalIterator>)
3792 __last);
3796 else
3799 __comp);
3800 }
3803 typename _Distance>
3804 void
3806 _RandomAccessIterator __last,
3808 {
3812 {
3817 }
3818 else
3819 {
3822 }
3827 }
3831 void
3833 _RandomAccessIterator __last,
3835 _Compare __comp)
3836 {
3840 {
3845 }
3846 else
3847 {
3850 }
3855 __comp);
3856 }
3858 /**
3859 * @brief Sort the elements of a sequence, preserving the relative order
3860 * of equivalent elements.
3861 * @param first An iterator.
3862 * @param last Another iterator.
3863 * @return Nothing.
3864 *
3865 * Sorts the elements in the range @p [first,last) in ascending order,
3866 * such that @p *(i+1)<*i is false for each iterator @p i in the range
3867 * @p [first,last-1).
3868 *
3869 * The relative ordering of equivalent elements is preserved, so any two
3870 * elements @p x and @p y in the range @p [first,last) such that
3871 * @p x<y is false and @p y<x is false will have the same relative
3872 * ordering after calling @p stable_sort().
3873 */
3877 {
3879 _ValueType;
3881 _DistanceType;
3883 // concept requirements
3885 _RandomAccessIterator>)
3890 __last);
3893 else
3896 }
3898 /**
3899 * @brief Sort the elements of a sequence using a predicate for comparison,
3900 * preserving the relative order of equivalent elements.
3901 * @param first An iterator.
3902 * @param last Another iterator.
3903 * @param comp A comparison functor.
3904 * @return Nothing.
3905 *
3906 * Sorts the elements in the range @p [first,last) in ascending order,
3907 * such that @p comp(*(i+1),*i) is false for each iterator @p i in the
3908 * range @p [first,last-1).
3909 *
3910 * The relative ordering of equivalent elements is preserved, so any two
3911 * elements @p x and @p y in the range @p [first,last) such that
3912 * @p comp(x,y) is false and @p comp(y,x) is false will have the same
3913 * relative ordering after calling @p stable_sort().
3914 */
3918 _Compare __comp)
3919 {
3921 _ValueType;
3923 _DistanceType;
3925 // concept requirements
3927 _RandomAccessIterator>)
3929 _ValueType,
3930 _ValueType>)
3934 __last);
3937 else
3940 }
3944 void
3947 {
3949 _ValueType;
3952 {
3954 {
3956 // Place the nth largest element in its final position.
3959 }
3961 _RandomAccessIterator __cut =
3964 *(__first
3965 + (__last
3968 *(__last
3972 else
3974 }
3976 }
3979 void
3982 _Compare __comp)
3983 {
3985 _ValueType;
3988 {
3990 {
3992 // Place the nth largest element in its final position.
3995 }
3997 _RandomAccessIterator __cut =
4000 *(__first
4001 + (__last
4005 __comp)),
4006 __comp);
4009 else
4011 }
4013 }
4015 /**
4016 * @brief Sort a sequence just enough to find a particular position.
4017 * @param first An iterator.
4018 * @param nth Another iterator.
4019 * @param last Another iterator.
4020 * @return Nothing.
4021 *
4022 * Rearranges the elements in the range @p [first,last) so that @p *nth
4023 * is the same element that would have been in that position had the
4024 * whole sequence been sorted.
4025 * whole sequence been sorted. The elements either side of @p *nth are
4026 * not completely sorted, but for any iterator @i in the range
4027 * @p [first,nth) and any iterator @j in the range @p [nth,last) it
4028 * holds that @p *j<*i is false.
4029 */
4033 _RandomAccessIterator __last)
4034 {
4036 _ValueType;
4038 // concept requirements
4040 _RandomAccessIterator>)
4050 }
4052 /**
4053 * @brief Sort a sequence just enough to find a particular position
4054 * using a predicate for comparison.
4055 * @param first An iterator.
4056 * @param nth Another iterator.
4057 * @param last Another iterator.
4058 * @param comp A comparison functor.
4059 * @return Nothing.
4060 *
4061 * Rearranges the elements in the range @p [first,last) so that @p *nth
4062 * is the same element that would have been in that position had the
4063 * whole sequence been sorted. The elements either side of @p *nth are
4064 * not completely sorted, but for any iterator @i in the range
4065 * @p [first,nth) and any iterator @j in the range @p [nth,last) it
4066 * holds that @p comp(*j,*i) is false.
4067 */
4072 {
4074 _ValueType;
4076 // concept requirements
4078 _RandomAccessIterator>)
4089 }
4091 /**
4092 * @brief Finds the largest subrange in which @a val could be inserted
4093 * at any place in it without changing the ordering.
4094 * @param first An iterator.
4095 * @param last Another iterator.
4096 * @param val The search term.
4097 * @return An pair of iterators defining the subrange.
4098 * @ingroup binarysearch
4099 *
4100 * This is equivalent to
4101 * @code
4102 * std::make_pair(lower_bound(first, last, val),
4103 * upper_bound(first, last, val))
4104 * @endcode
4105 * but does not actually call those functions.
4106 */
4111 {
4113 _ValueType;
4115 _DistanceType;
4117 // concept requirements
4124 _DistanceType __half;
4128 {
4133 {
4137 }
4140 else
4141 {
4146 }
4147 }
4149 }
4151 /**
4152 * @brief Finds the largest subrange in which @a val could be inserted
4153 * at any place in it without changing the ordering.
4154 * @param first An iterator.
4155 * @param last Another iterator.
4156 * @param val The search term.
4157 * @param comp A functor to use for comparisons.
4158 * @return An pair of iterators defining the subrange.
4159 * @ingroup binarysearch
4160 *
4161 * This is equivalent to
4162 * @code
4163 * std::make_pair(lower_bound(first, last, val, comp),
4164 * upper_bound(first, last, val, comp))
4165 * @endcode
4166 * but does not actually call those functions.
4167 */
4172 _Compare __comp)
4173 {
4175 _ValueType;
4177 _DistanceType;
4179 // concept requirements
4188 _DistanceType __half;
4192 {
4197 {
4201 }
4204 else
4205 {
4210 }
4211 }
4213 }
4215 /**
4216 * @brief Determines whether an element exists in a range.
4217 * @param first An iterator.
4218 * @param last Another iterator.
4219 * @param val The search term.
4220 * @return True if @a val (or its equivelent) is in [@a first,@a last ].
4221 * @ingroup binarysearch
4222 *
4223 * Note that this does not actually return an iterator to @a val. For
4224 * that, use std::find or a container's specialized find member functions.
4225 */
4227 bool
4230 {
4232 _ValueType;
4234 // concept requirements
4241 }
4243 /**
4244 * @brief Determines whether an element exists in a range.
4245 * @param first An iterator.
4246 * @param last Another iterator.
4247 * @param val The search term.
4248 * @param comp A functor to use for comparisons.
4249 * @return True if @a val (or its equivelent) is in [@a first,@a last ].
4250 * @ingroup binarysearch
4251 *
4252 * Note that this does not actually return an iterator to @a val. For
4253 * that, use std::find or a container's specialized find member functions.
4254 *
4255 * The comparison function should have the same effects on ordering as
4256 * the function used for the initial sort.
4257 */
4259 bool
4262 {
4264 _ValueType;
4266 // concept requirements
4274 }
4276 // Set algorithms: includes, set_union, set_intersection, set_difference,
4277 // set_symmetric_difference. All of these algorithms have the precondition
4278 // that their input ranges are sorted and the postcondition that their output
4279 // ranges are sorted.
4281 /**
4282 * @brief Determines whether all elements of a sequence exists in a range.
4283 * @param first1 Start of search range.
4284 * @param last1 End of search range.
4285 * @param first2 Start of sequence
4286 * @param last2 End of sequence.
4287 * @return True if each element in [first2,last2) is contained in order
4288 * within [first1,last1). False otherwise.
4289 * @ingroup setoperations
4290 *
4291 * This operation expects both [first1,last1) and [first2,last2) to be
4292 * sorted. Searches for the presence of each element in [first2,last2)
4293 * within [first1,last1). The iterators over each range only move forward,
4294 * so this is a linear algorithm. If an element in [first2,last2) is not
4295 * found before the search iterator reaches @a last2, false is returned.
4296 */
4298 bool
4301 {
4303 _ValueType1;
4305 _ValueType2;
4307 // concept requirements
4320 else
4324 }
4326 /**
4327 * @brief Determines whether all elements of a sequence exists in a range
4328 * using comparison.
4329 * @param first1 Start of search range.
4330 * @param last1 End of search range.
4331 * @param first2 Start of sequence
4332 * @param last2 End of sequence.
4333 * @param comp Comparison function to use.
4334 * @return True if each element in [first2,last2) is contained in order
4335 * within [first1,last1) according to comp. False otherwise.
4336 * @ingroup setoperations
4337 *
4338 * This operation expects both [first1,last1) and [first2,last2) to be
4339 * sorted. Searches for the presence of each element in [first2,last2)
4340 * within [first1,last1), using comp to decide. The iterators over each
4341 * range only move forward, so this is a linear algorithm. If an element
4342 * in [first2,last2) is not found before the search iterator reaches @a
4343 * last2, false is returned.
4344 */
4346 typename _Compare>
4347 bool
4350 {
4352 _ValueType1;
4354 _ValueType2;
4356 // concept requirements
4371 else
4375 }
4377 /**
4378 * @brief Return the union of two sorted ranges.
4379 * @param first1 Start of first range.
4380 * @param last1 End of first range.
4381 * @param first2 Start of second range.
4382 * @param last2 End of second range.
4383 * @return End of the output range.
4384 * @ingroup setoperations
4385 *
4386 * This operation iterates over both ranges, copying elements present in
4387 * each range in order to the output range. Iterators increment for each
4388 * range. When the current element of one range is less than the other,
4389 * that element is copied and the iterator advanced. If an element is
4390 * contained in both ranges, the element from the first range is copied and
4391 * both ranges advance. The output range may not overlap either input
4392 * range.
4393 */
4395 typename _OutputIterator>
4396 _OutputIterator
4399 _OutputIterator __result)
4400 {
4402 _ValueType1;
4404 _ValueType2;
4406 // concept requirements
4410 _ValueType1>)
4412 _ValueType2>)
4419 {
4421 {
4424 }
4426 {
4429 }
4430 else
4431 {
4435 }
4437 }
4439 __result));
4440 }
4442 /**
4443 * @brief Return the union of two sorted ranges using a comparison functor.
4444 * @param first1 Start of first range.
4445 * @param last1 End of first range.
4446 * @param first2 Start of second range.
4447 * @param last2 End of second range.
4448 * @param comp The comparison functor.
4449 * @return End of the output range.
4450 * @ingroup setoperations
4451 *
4452 * This operation iterates over both ranges, copying elements present in
4453 * each range in order to the output range. Iterators increment for each
4454 * range. When the current element of one range is less than the other
4455 * according to @a comp, that element is copied and the iterator advanced.
4456 * If an equivalent element according to @a comp is contained in both
4457 * ranges, the element from the first range is copied and both ranges
4458 * advance. The output range may not overlap either input range.
4459 */
4462 _OutputIterator
4466 {
4468 _ValueType1;
4470 _ValueType2;
4472 // concept requirements
4476 _ValueType1>)
4478 _ValueType2>)
4487 {
4489 {
4492 }
4494 {
4497 }
4498 else
4499 {
4503 }
4505 }
4507 __result));
4508 }
4510 /**
4511 * @brief Return the intersection of two sorted ranges.
4512 * @param first1 Start of first range.
4513 * @param last1 End of first range.
4514 * @param first2 Start of second range.
4515 * @param last2 End of second range.
4516 * @return End of the output range.
4517 * @ingroup setoperations
4518 *
4519 * This operation iterates over both ranges, copying elements present in
4520 * both ranges in order to the output range. Iterators increment for each
4521 * range. When the current element of one range is less than the other,
4522 * that iterator advances. If an element is contained in both ranges, the
4523 * element from the first range is copied and both ranges advance. The
4524 * output range may not overlap either input range.
4525 */
4527 typename _OutputIterator>
4528 _OutputIterator
4531 _OutputIterator __result)
4532 {
4534 _ValueType1;
4536 _ValueType2;
4538 // concept requirements
4542 _ValueType1>)
4553 else
4554 {
4559 }
4561 }
4563 /**
4564 * @brief Return the intersection of two sorted ranges using comparison
4565 * functor.
4566 * @param first1 Start of first range.
4567 * @param last1 End of first range.
4568 * @param first2 Start of second range.
4569 * @param last2 End of second range.
4570 * @param comp The comparison functor.
4571 * @return End of the output range.
4572 * @ingroup setoperations
4573 *
4574 * This operation iterates over both ranges, copying elements present in
4575 * both ranges in order to the output range. Iterators increment for each
4576 * range. When the current element of one range is less than the other
4577 * according to @a comp, that iterator advances. If an element is
4578 * contained in both ranges according to @a comp, the element from the
4579 * first range is copied and both ranges advance. The output range may not
4580 * overlap either input range.
4581 */
4584 _OutputIterator
4588 {
4590 _ValueType1;
4592 _ValueType2;
4594 // concept requirements
4598 _ValueType1>)
4611 else
4612 {
4617 }
4619 }
4621 /**
4622 * @brief Return the difference of two sorted ranges.
4623 * @param first1 Start of first range.
4624 * @param last1 End of first range.
4625 * @param first2 Start of second range.
4626 * @param last2 End of second range.
4627 * @return End of the output range.
4628 * @ingroup setoperations
4629 *
4630 * This operation iterates over both ranges, copying elements present in
4631 * the first range but not the second in order to the output range.
4632 * Iterators increment for each range. When the current element of the
4633 * first range is less than the second, that element is copied and the
4634 * iterator advances. If the current element of the second range is less,
4635 * the iterator advances, but no element is copied. If an element is
4636 * contained in both ranges, no elements are copied and both ranges
4637 * advance. The output range may not overlap either input range.
4638 */
4640 typename _OutputIterator>
4641 _OutputIterator
4644 _OutputIterator __result)
4645 {
4647 _ValueType1;
4649 _ValueType2;
4651 // concept requirements
4655 _ValueType1>)
4663 {
4667 }
4670 else
4671 {
4674 }
4676 }
4678 /**
4679 * @brief Return the difference of two sorted ranges using comparison
4680 * functor.
4681 * @param first1 Start of first range.
4682 * @param last1 End of first range.
4683 * @param first2 Start of second range.
4684 * @param last2 End of second range.
4685 * @param comp The comparison functor.
4686 * @return End of the output range.
4687 * @ingroup setoperations
4688 *
4689 * This operation iterates over both ranges, copying elements present in
4690 * the first range but not the second in order to the output range.
4691 * Iterators increment for each range. When the current element of the
4692 * first range is less than the second according to @a comp, that element
4693 * is copied and the iterator advances. If the current element of the
4694 * second range is less, no element is copied and the iterator advances.
4695 * If an element is contained in both ranges according to @a comp, no
4696 * elements are copied and both ranges advance. The output range may not
4697 * overlap either input range.
4698 */
4701 _OutputIterator
4705 {
4707 _ValueType1;
4709 _ValueType2;
4711 // concept requirements
4715 _ValueType1>)
4725 {
4729 }
4732 else
4733 {
4736 }
4738 }
4740 /**
4741 * @brief Return the symmetric difference of two sorted ranges.
4742 * @param first1 Start of first range.
4743 * @param last1 End of first range.
4744 * @param first2 Start of second range.
4745 * @param last2 End of second range.
4746 * @return End of the output range.
4747 * @ingroup setoperations
4748 *
4749 * This operation iterates over both ranges, copying elements present in
4750 * one range but not the other in order to the output range. Iterators
4751 * increment for each range. When the current element of one range is less
4752 * than the other, that element is copied and the iterator advances. If an
4753 * element is contained in both ranges, no elements are copied and both
4754 * ranges advance. The output range may not overlap either input range.
4755 */
4757 typename _OutputIterator>
4758 _OutputIterator
4761 _OutputIterator __result)
4762 {
4764 _ValueType1;
4766 _ValueType2;
4768 // concept requirements
4772 _ValueType1>)
4774 _ValueType2>)
4782 {
4786 }
4788 {
4792 }
4793 else
4794 {
4797 }
4800 }
4802 /**
4803 * @brief Return the symmetric difference of two sorted ranges using
4804 * comparison functor.
4805 * @param first1 Start of first range.
4806 * @param last1 End of first range.
4807 * @param first2 Start of second range.
4808 * @param last2 End of second range.
4809 * @param comp The comparison functor.
4810 * @return End of the output range.
4811 * @ingroup setoperations
4812 *
4813 * This operation iterates over both ranges, copying elements present in
4814 * one range but not the other in order to the output range. Iterators
4815 * increment for each range. When the current element of one range is less
4816 * than the other according to @a comp, that element is copied and the
4817 * iterator advances. If an element is contained in both ranges according
4818 * to @a comp, no elements are copied and both ranges advance. The output
4819 * range may not overlap either input range.
4820 */
4823 _OutputIterator
4826 _OutputIterator __result,
4827 _Compare __comp)
4828 {
4830 _ValueType1;
4832 _ValueType2;
4834 // concept requirements
4838 _ValueType1>)
4840 _ValueType2>)
4850 {
4854 }
4856 {
4860 }
4861 else
4862 {
4865 }
4868 }
4870 // min_element and max_element, with and without an explicitly supplied
4871 // comparison function.
4873 /**
4874 * @brief Return the maximum element in a range.
4875 * @param first Start of range.
4876 * @param last End of range.
4877 * @return Iterator referencing the first instance of the largest value.
4878 */
4880 _ForwardIterator
4882 {
4883 // concept requirements
4896 }
4898 /**
4899 * @brief Return the maximum element in a range using comparison functor.
4900 * @param first Start of range.
4901 * @param last End of range.
4902 * @param comp Comparison functor.
4903 * @return Iterator referencing the first instance of the largest value
4904 * according to comp.
4905 */
4907 _ForwardIterator
4909 _Compare __comp)
4910 {
4911 // concept requirements
4923 }
4925 /**
4926 * @brief Return the minimum element in a range.
4927 * @param first Start of range.
4928 * @param last End of range.
4929 * @return Iterator referencing the first instance of the smallest value.
4930 */
4932 _ForwardIterator
4934 {
4935 // concept requirements
4948 }
4950 /**
4951 * @brief Return the minimum element in a range using comparison functor.
4952 * @param first Start of range.
4953 * @param last End of range.
4954 * @param comp Comparison functor.
4955 * @return Iterator referencing the first instance of the smallest value
4956 * according to comp.
4957 */
4959 _ForwardIterator
4961 _Compare __comp)
4962 {
4963 // concept requirements
4977 }
4979 // next_permutation and prev_permutation, with and without an explicitly
4980 // supplied comparison function.
4982 /**
4983 * @brief Permute range into the next "dictionary" ordering.
4984 * @param first Start of range.
4985 * @param last End of range.
4986 * @return False if wrapped to first permutation, true otherwise.
4987 *
4988 * Treats all permutations of the range as a set of "dictionary" sorted
4989 * sequences. Permutes the current sequence into the next one of this set.
4990 * Returns true if there are more sequences to generate. If the sequence
4991 * is the largest of the set, the smallest is generated and false returned.
4992 */
4994 bool
4996 _BidirectionalIterator __last)
4997 {
4998 // concept requirements
5000 _BidirectionalIterator>)
5015 {
5019 {
5022 {}
5026 }
5028 {
5031 }
5032 }
5033 }
5035 /**
5036 * @brief Permute range into the next "dictionary" ordering using
5037 * comparison functor.
5038 * @param first Start of range.
5039 * @param last End of range.
5040 * @param comp
5041 * @return False if wrapped to first permutation, true otherwise.
5042 *
5043 * Treats all permutations of the range [first,last) as a set of
5044 * "dictionary" sorted sequences ordered by @a comp. Permutes the current
5045 * sequence into the next one of this set. Returns true if there are more
5046 * sequences to generate. If the sequence is the largest of the set, the
5047 * smallest is generated and false returned.
5048 */
5050 bool
5053 {
5054 // concept requirements
5056 _BidirectionalIterator>)
5072 {
5076 {
5079 {}
5083 }
5085 {
5088 }
5089 }
5090 }
5092 /**
5093 * @brief Permute range into the previous "dictionary" ordering.
5094 * @param first Start of range.
5095 * @param last End of range.
5096 * @return False if wrapped to last permutation, true otherwise.
5097 *
5098 * Treats all permutations of the range as a set of "dictionary" sorted
5099 * sequences. Permutes the current sequence into the previous one of this
5100 * set. Returns true if there are more sequences to generate. If the
5101 * sequence is the smallest of the set, the largest is generated and false
5102 * returned.
5103 */
5105 bool
5107 _BidirectionalIterator __last)
5108 {
5109 // concept requirements
5111 _BidirectionalIterator>)
5126 {
5130 {
5133 {}
5137 }
5139 {
5142 }
5143 }
5144 }
5146 /**
5147 * @brief Permute range into the previous "dictionary" ordering using
5148 * comparison functor.
5149 * @param first Start of range.
5150 * @param last End of range.
5151 * @param comp
5152 * @return False if wrapped to last permutation, true otherwise.
5153 *
5154 * Treats all permutations of the range [first,last) as a set of
5155 * "dictionary" sorted sequences ordered by @a comp. Permutes the current
5156 * sequence into the previous one of this set. Returns true if there are
5157 * more sequences to generate. If the sequence is the smallest of the set,
5158 * the largest is generated and false returned.
5159 */
5161 bool
5164 {
5165 // concept requirements
5167 _BidirectionalIterator>)
5183 {
5187 {
5190 {}
5194 }
5196 {
5199 }
5200 }
5201 }
5203 // find_first_of, with and without an explicitly supplied comparison function.
5205 /**
5206 * @brief Find element from a set in a sequence.
5207 * @param first1 Start of range to search.
5208 * @param last1 End of range to search.
5209 * @param first2 Start of match candidates.
5210 * @param last2 End of match candidates.
5211 * @return The first iterator @c i in the range
5212 * @p [first1,last1) such that @c *i == @p *(i2) such that i2 is an
5213 * interator in [first2,last2), or @p last1 if no such iterator exists.
5214 *
5215 * Searches the range @p [first1,last1) for an element that is equal to
5216 * some element in the range [first2,last2). If found, returns an iterator
5217 * in the range [first1,last1), otherwise returns @p last1.
5218 */
5220 _InputIterator
5223 {
5224 // concept requirements
5238 }
5240 /**
5241 * @brief Find element from a set in a sequence using a predicate.
5242 * @param first1 Start of range to search.
5243 * @param last1 End of range to search.
5244 * @param first2 Start of match candidates.
5245 * @param last2 End of match candidates.
5246 * @param comp Predicate to use.
5247 * @return The first iterator @c i in the range
5248 * @p [first1,last1) such that @c comp(*i, @p *(i2)) is true and i2 is an
5249 * interator in [first2,last2), or @p last1 if no such iterator exists.
5250 *
5251 * Searches the range @p [first1,last1) for an element that is equal to
5252 * some element in the range [first2,last2). If found, returns an iterator in
5253 * the range [first1,last1), otherwise returns @p last1.
5254 */
5256 typename _BinaryPredicate>
5257 _InputIterator
5260 _BinaryPredicate __comp)
5261 {
5262 // concept requirements
5276 }
5279 // find_end, with and without an explicitly supplied comparison function.
5280 // Search [first2, last2) as a subsequence in [first1, last1), and return
5281 // the *last* possible match. Note that find_end for bidirectional iterators
5282 // is much faster than for forward iterators.
5284 // find_end for forward iterators.
5286 _ForwardIterator1
5290 {
5293 else
5294 {
5297 {
5298 _ForwardIterator1 __new_result
5302 else
5303 {
5307 }
5308 }
5309 }
5310 }
5313 typename _BinaryPredicate>
5314 _ForwardIterator1
5318 _BinaryPredicate __comp)
5319 {
5322 else
5323 {
5326 {
5327 _ForwardIterator1 __new_result
5331 else
5332 {
5336 }
5337 }
5338 }
5339 }
5341 // find_end for bidirectional iterators. Requires partial specialization.
5343 _BidirectionalIterator1
5345 _BidirectionalIterator1 __last1,
5346 _BidirectionalIterator2 __first2,
5347 _BidirectionalIterator2 __last2,
5349 {
5350 // concept requirements
5352 _BidirectionalIterator1>)
5354 _BidirectionalIterator2>)
5366 else
5367 {
5371 }
5372 }
5375 typename _BinaryPredicate>
5376 _BidirectionalIterator1
5378 _BidirectionalIterator1 __last1,
5379 _BidirectionalIterator2 __first2,
5380 _BidirectionalIterator2 __last2,
5382 _BinaryPredicate __comp)
5383 {
5384 // concept requirements
5386 _BidirectionalIterator1>)
5388 _BidirectionalIterator2>)
5397 __comp);
5401 else
5402 {
5406 }
5407 }
5409 // Dispatching functions for find_end.
5411 /**
5412 * @brief Find last matching subsequence in a sequence.
5413 * @param first1 Start of range to search.
5414 * @param last1 End of range to search.
5415 * @param first2 Start of sequence to match.
5416 * @param last2 End of sequence to match.
5417 * @return The last iterator @c i in the range
5418 * @p [first1,last1-(last2-first2)) such that @c *(i+N) == @p *(first2+N)
5419 * for each @c N in the range @p [0,last2-first2), or @p last1 if no
5420 * such iterator exists.
5421 *
5422 * Searches the range @p [first1,last1) for a sub-sequence that compares
5423 * equal value-by-value with the sequence given by @p [first2,last2) and
5424 * returns an iterator to the first element of the sub-sequence, or
5425 * @p last1 if the sub-sequence is not found. The sub-sequence will be the
5426 * last such subsequence contained in [first,last1).
5427 *
5428 * Because the sub-sequence must lie completely within the range
5429 * @p [first1,last1) it must start at a position less than
5430 * @p last1-(last2-first2) where @p last2-first2 is the length of the
5431 * sub-sequence.
5432 * This means that the returned iterator @c i will be in the range
5433 * @p [first1,last1-(last2-first2))
5434 */
5436 inline _ForwardIterator1
5439 {
5440 // concept requirements
5452 }
5454 /**
5455 * @brief Find last matching subsequence in a sequence using a predicate.
5456 * @param first1 Start of range to search.
5457 * @param last1 End of range to search.
5458 * @param first2 Start of sequence to match.
5459 * @param last2 End of sequence to match.
5460 * @param comp The predicate to use.
5461 * @return The last iterator @c i in the range
5462 * @p [first1,last1-(last2-first2)) such that @c predicate(*(i+N), @p
5463 * (first2+N)) is true for each @c N in the range @p [0,last2-first2), or
5464 * @p last1 if no such iterator exists.
5465 *
5466 * Searches the range @p [first1,last1) for a sub-sequence that compares
5467 * equal value-by-value with the sequence given by @p [first2,last2) using
5468 * comp as a predicate and returns an iterator to the first element of the
5469 * sub-sequence, or @p last1 if the sub-sequence is not found. The
5470 * sub-sequence will be the last such subsequence contained in
5471 * [first,last1).
5472 *
5473 * Because the sub-sequence must lie completely within the range
5474 * @p [first1,last1) it must start at a position less than
5475 * @p last1-(last2-first2) where @p last2-first2 is the length of the
5476 * sub-sequence.
5477 * This means that the returned iterator @c i will be in the range
5478 * @p [first1,last1-(last2-first2))
5479 */
5481 typename _BinaryPredicate>
5482 inline _ForwardIterator1
5485 _BinaryPredicate __comp)
5486 {
5487 // concept requirements
5499 __comp);
5500 }
5502 _GLIBCXX_END_NAMESPACE