| blob | 405f9a8a816e9d89fa2daad77a6d54163b56eff6 |
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.
71 namespace std
72 {
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 * @brief Find the first occurrence of a value in a sequence.
299 * @param first An input iterator.
300 * @param last An input iterator.
301 * @param val The value to find.
302 * @return The first iterator @c i in the range @p [first,last)
303 * such that @c *i == @p val, or @p last if no such iterator exists.
304 */
306 inline _InputIterator
309 {
310 // concept requirements
317 }
319 /**
320 * @brief Find the first element in a sequence for which a predicate is true.
321 * @param first An input iterator.
322 * @param last An input iterator.
323 * @param pred A predicate.
324 * @return The first iterator @c i in the range @p [first,last)
325 * such that @p pred(*i) is true, or @p last if no such iterator exists.
326 */
328 inline _InputIterator
330 _Predicate __pred)
331 {
332 // concept requirements
339 }
341 /**
342 * @brief Find two adjacent values in a sequence that are equal.
343 * @param first A forward iterator.
344 * @param last A forward iterator.
345 * @return The first iterator @c i such that @c i and @c i+1 are both
346 * valid iterators in @p [first,last) and such that @c *i == @c *(i+1),
347 * or @p last if no such iterator exists.
348 */
350 _ForwardIterator
352 {
353 // concept requirements
362 {
366 }
368 }
370 /**
371 * @brief Find two adjacent values in a sequence using a predicate.
372 * @param first A forward iterator.
373 * @param last A forward iterator.
374 * @param binary_pred A binary predicate.
375 * @return The first iterator @c i such that @c i and @c i+1 are both
376 * valid iterators in @p [first,last) and such that
377 * @p binary_pred(*i,*(i+1)) is true, or @p last if no such iterator
378 * exists.
379 */
381 _ForwardIterator
383 _BinaryPredicate __binary_pred)
384 {
385 // concept requirements
395 {
399 }
401 }
403 /**
404 * @brief Count the number of copies of a value in a sequence.
405 * @param first An input iterator.
406 * @param last An input iterator.
407 * @param value The value to be counted.
408 * @return The number of iterators @c i in the range @p [first,last)
409 * for which @c *i == @p value
410 */
414 {
415 // 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 * @if maint
612 * This is an uglified
613 * search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&)
614 * overloaded for forward iterators.
615 * @endif
616 */
618 _ForwardIterator
622 {
625 {
631 {
634 }
640 }
642 }
644 /**
645 * @if maint
646 * This is an uglified
647 * search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&)
648 * overloaded for random access iterators.
649 * @endif
650 */
652 _RandomAccessIter
656 {
659 _DistanceType;
672 {
673 // __lookAhead here is always pointing to the last element of next
674 // possible match.
676 {
681 }
685 {
688 }
693 }
694 }
696 /**
697 * @brief Search a sequence for a number of consecutive values.
698 * @param first A forward iterator.
699 * @param last A forward iterator.
700 * @param count The number of consecutive values.
701 * @param val The value to find.
702 * @return The first iterator @c i in the range @p [first,last-count)
703 * such that @c *(i+N) == @p val for each @c N in the range @p [0,count),
704 * or @p last if no such iterator exists.
705 *
706 * Searches the range @p [first,last) for @p count consecutive elements
707 * equal to @p val.
708 */
710 _ForwardIterator
713 {
714 // concept requirements
726 }
728 /**
729 * @if maint
730 * This is an uglified
731 * search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&,
732 * _BinaryPredicate)
733 * overloaded for forward iterators.
734 * @endif
735 */
737 typename _BinaryPredicate>
738 _ForwardIterator
742 {
747 {
753 {
756 }
764 }
766 }
768 /**
769 * @if maint
770 * This is an uglified
771 * search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&,
772 * _BinaryPredicate)
773 * overloaded for random access iterators.
774 * @endif
775 */
777 typename _BinaryPredicate>
778 _RandomAccessIter
782 {
785 _DistanceType;
798 {
799 // __lookAhead here is always pointing to the last element of next
800 // possible match.
802 {
807 }
811 {
814 }
819 }
820 }
822 /**
823 * @brief Search a sequence for a number of consecutive values using a
824 * predicate.
825 * @param first A forward iterator.
826 * @param last A forward iterator.
827 * @param count The number of consecutive values.
828 * @param val The value to find.
829 * @param binary_pred A binary predicate.
830 * @return The first iterator @c i in the range @p [first,last-count)
831 * such that @p binary_pred(*(i+N),val) is true for each @c N in the
832 * range @p [0,count), or @p last if no such iterator exists.
833 *
834 * Searches the range @p [first,last) for @p count consecutive elements
835 * for which the predicate returns true.
836 */
838 typename _BinaryPredicate>
839 _ForwardIterator
842 _BinaryPredicate __binary_pred)
843 {
844 // concept requirements
853 {
857 }
860 }
862 /**
863 * @brief Swap the elements of two sequences.
864 * @param first1 A forward iterator.
865 * @param last1 A forward iterator.
866 * @param first2 A forward iterator.
867 * @return An iterator equal to @p first2+(last1-first1).
868 *
869 * Swaps each element in the range @p [first1,last1) with the
870 * corresponding element in the range @p [first2,(last1-first1)).
871 * The ranges must not overlap.
872 */
874 _ForwardIterator2
876 _ForwardIterator2 __first2)
877 {
878 // concept requirements
880 _ForwardIterator1>)
882 _ForwardIterator2>)
894 }
896 /**
897 * @brief Perform an operation on a sequence.
898 * @param first An input iterator.
899 * @param last An input iterator.
900 * @param result An output iterator.
901 * @param unary_op A unary operator.
902 * @return An output iterator equal to @p result+(last-first).
903 *
904 * Applies the operator to each element in the input range and assigns
905 * the results to successive elements of the output sequence.
906 * Evaluates @p *(result+N)=unary_op(*(first+N)) for each @c N in the
907 * range @p [0,last-first).
908 *
909 * @p unary_op must not alter its argument.
910 */
912 typename _UnaryOperation>
913 _OutputIterator
916 {
917 // concept requirements
920 // "the type returned by a _UnaryOperation"
927 }
929 /**
930 * @brief Perform an operation on corresponding elements of two sequences.
931 * @param first1 An input iterator.
932 * @param last1 An input iterator.
933 * @param first2 An input iterator.
934 * @param result An output iterator.
935 * @param binary_op A binary operator.
936 * @return An output iterator equal to @p result+(last-first).
937 *
938 * Applies the operator to the corresponding elements in the two
939 * input ranges and assigns the results to successive elements of the
940 * output sequence.
941 * Evaluates @p *(result+N)=binary_op(*(first1+N),*(first2+N)) for each
942 * @c N in the range @p [0,last1-first1).
943 *
944 * @p binary_op must not alter either of its arguments.
945 */
948 _OutputIterator
951 _BinaryOperation __binary_op)
952 {
953 // concept requirements
957 // "the type returned by a _BinaryOperation"
964 }
966 /**
967 * @brief Replace each occurrence of one value in a sequence with another
968 * value.
969 * @param first A forward iterator.
970 * @param last A forward iterator.
971 * @param old_value The value to be replaced.
972 * @param new_value The replacement value.
973 * @return replace() returns no value.
974 *
975 * For each iterator @c i in the range @p [first,last) if @c *i ==
976 * @p old_value then the assignment @c *i = @p new_value is performed.
977 */
979 void
982 {
983 // concept requirements
985 _ForwardIterator>)
995 }
997 /**
998 * @brief Replace each value in a sequence for which a predicate returns
999 * true with another value.
1000 * @param first A forward iterator.
1001 * @param last A forward iterator.
1002 * @param pred A predicate.
1003 * @param new_value The replacement value.
1004 * @return replace_if() returns no value.
1005 *
1006 * For each iterator @c i in the range @p [first,last) if @p pred(*i)
1007 * is true then the assignment @c *i = @p new_value is performed.
1008 */
1010 void
1013 {
1014 // concept requirements
1016 _ForwardIterator>)
1026 }
1028 /**
1029 * @brief Copy a sequence, replacing each element of one value with another
1030 * value.
1031 * @param first An input iterator.
1032 * @param last An input iterator.
1033 * @param result An output iterator.
1034 * @param old_value The value to be replaced.
1035 * @param new_value The replacement value.
1036 * @return The end of the output sequence, @p result+(last-first).
1037 *
1038 * Copies each element in the input range @p [first,last) to the
1039 * output range @p [result,result+(last-first)) replacing elements
1040 * equal to @p old_value with @p new_value.
1041 */
1043 _OutputIterator
1045 _OutputIterator __result,
1047 {
1048 // concept requirements
1059 else
1062 }
1064 /**
1065 * @brief Copy a sequence, replacing each value for which a predicate
1066 * returns true with another value.
1067 * @param first An input iterator.
1068 * @param last An input iterator.
1069 * @param result An output iterator.
1070 * @param pred A predicate.
1071 * @param new_value The replacement value.
1072 * @return The end of the output sequence, @p result+(last-first).
1073 *
1074 * Copies each element in the range @p [first,last) to the range
1075 * @p [result,result+(last-first)) replacing elements for which
1076 * @p pred returns true with @p new_value.
1077 */
1080 _OutputIterator
1082 _OutputIterator __result,
1084 {
1085 // concept requirements
1096 else
1099 }
1101 /**
1102 * @brief Assign the result of a function object to each value in a
1103 * sequence.
1104 * @param first A forward iterator.
1105 * @param last A forward iterator.
1106 * @param gen A function object taking no arguments.
1107 * @return generate() returns no value.
1108 *
1109 * Performs the assignment @c *i = @p gen() for each @c i in the range
1110 * @p [first,last).
1111 */
1113 void
1115 _Generator __gen)
1116 {
1117 // concept requirements
1125 }
1127 /**
1128 * @brief Assign the result of a function object to each value in a
1129 * sequence.
1130 * @param first A forward iterator.
1131 * @param n The length of the sequence.
1132 * @param gen A function object taking no arguments.
1133 * @return The end of the sequence, @p first+n
1134 *
1135 * Performs the assignment @c *i = @p gen() for each @c i in the range
1136 * @p [first,first+n).
1137 */
1139 _OutputIterator
1141 {
1142 // concept requirements
1144 // "the type returned by a _Generator"
1150 }
1152 /**
1153 * @brief Copy a sequence, removing elements of a given value.
1154 * @param first An input iterator.
1155 * @param last An input iterator.
1156 * @param result An output iterator.
1157 * @param value The value to be removed.
1158 * @return An iterator designating the end of the resulting sequence.
1159 *
1160 * Copies each element in the range @p [first,last) not equal to @p value
1161 * to the range beginning at @p result.
1162 * remove_copy() is stable, so the relative order of elements that are
1163 * copied is unchanged.
1164 */
1166 _OutputIterator
1169 {
1170 // concept requirements
1180 {
1183 }
1185 }
1187 /**
1188 * @brief Copy a sequence, removing elements for which a predicate is true.
1189 * @param first An input iterator.
1190 * @param last An input iterator.
1191 * @param result An output iterator.
1192 * @param pred A predicate.
1193 * @return An iterator designating the end of the resulting sequence.
1194 *
1195 * Copies each element in the range @p [first,last) for which
1196 * @p pred returns true to the range beginning at @p result.
1197 *
1198 * remove_copy_if() is stable, so the relative order of elements that are
1199 * copied is unchanged.
1200 */
1202 typename _Predicate>
1203 _OutputIterator
1206 {
1207 // concept requirements
1217 {
1220 }
1222 }
1224 /**
1225 * @brief Remove elements from a sequence.
1226 * @param first An input iterator.
1227 * @param last An input iterator.
1228 * @param value The value to be removed.
1229 * @return An iterator designating the end of the resulting sequence.
1230 *
1231 * All elements equal to @p value are removed from the range
1232 * @p [first,last).
1233 *
1234 * remove() is stable, so the relative order of elements that are
1235 * not removed is unchanged.
1236 *
1237 * Elements between the end of the resulting sequence and @p last
1238 * are still present, but their value is unspecified.
1239 */
1241 _ForwardIterator
1244 {
1245 // concept requirements
1247 _ForwardIterator>)
1257 }
1259 /**
1260 * @brief Remove elements from a sequence using a predicate.
1261 * @param first A forward iterator.
1262 * @param last A forward iterator.
1263 * @param pred A predicate.
1264 * @return An iterator designating the end of the resulting sequence.
1265 *
1266 * All elements for which @p pred returns true are removed from the range
1267 * @p [first,last).
1268 *
1269 * remove_if() is stable, so the relative order of elements that are
1270 * not removed is unchanged.
1271 *
1272 * Elements between the end of the resulting sequence and @p last
1273 * are still present, but their value is unspecified.
1274 */
1276 _ForwardIterator
1278 _Predicate __pred)
1279 {
1280 // concept requirements
1282 _ForwardIterator>)
1292 }
1294 /**
1295 * @if maint
1296 * This is an uglified unique_copy(_InputIterator, _InputIterator,
1297 * _OutputIterator)
1298 * overloaded for output iterators.
1299 * @endif
1300 */
1302 _OutputIterator
1304 _OutputIterator __result,
1305 output_iterator_tag)
1306 {
1307 // concept requirements -- taken care of in dispatching function
1312 {
1315 }
1317 }
1319 /**
1320 * @if maint
1321 * This is an uglified unique_copy(_InputIterator, _InputIterator,
1322 * _OutputIterator)
1323 * overloaded for forward iterators.
1324 * @endif
1325 */
1327 _ForwardIterator
1329 _ForwardIterator __result,
1330 forward_iterator_tag)
1331 {
1332 // concept requirements -- taken care of in dispatching function
1338 }
1340 /**
1341 * @if maint
1342 * This is an uglified
1343 * unique_copy(_InputIterator, _InputIterator, _OutputIterator,
1344 * _BinaryPredicate)
1345 * overloaded for output iterators.
1346 * @endif
1347 */
1349 typename _BinaryPredicate>
1350 _OutputIterator
1352 _OutputIterator __result,
1353 _BinaryPredicate __binary_pred,
1354 output_iterator_tag)
1355 {
1356 // concept requirements -- iterators already checked
1365 {
1368 }
1370 }
1372 /**
1373 * @if maint
1374 * This is an uglified
1375 * unique_copy(_InputIterator, _InputIterator, _OutputIterator,
1376 * _BinaryPredicate)
1377 * overloaded for forward iterators.
1378 * @endif
1379 */
1381 typename _BinaryPredicate>
1382 _ForwardIterator
1384 _ForwardIterator __result,
1385 _BinaryPredicate __binary_pred,
1386 forward_iterator_tag)
1387 {
1388 // concept requirements -- iterators already checked
1397 }
1399 /**
1400 * @brief Copy a sequence, removing consecutive duplicate values.
1401 * @param first An input iterator.
1402 * @param last An input iterator.
1403 * @param result An output iterator.
1404 * @return An iterator designating the end of the resulting sequence.
1405 *
1406 * Copies each element in the range @p [first,last) to the range
1407 * beginning at @p result, except that only the first element is copied
1408 * from groups of consecutive elements that compare equal.
1409 * unique_copy() is stable, so the relative order of elements that are
1410 * copied is unchanged.
1411 */
1413 inline _OutputIterator
1415 _OutputIterator __result)
1416 {
1417 // concept requirements
1426 _IterType;
1430 }
1432 /**
1433 * @brief Copy a sequence, removing consecutive values using a predicate.
1434 * @param first An input iterator.
1435 * @param last An input iterator.
1436 * @param result An output iterator.
1437 * @param binary_pred A binary predicate.
1438 * @return An iterator designating the end of the resulting sequence.
1439 *
1440 * Copies each element in the range @p [first,last) to the range
1441 * beginning at @p result, except that only the first element is copied
1442 * from groups of consecutive elements for which @p binary_pred returns
1443 * true.
1444 * unique_copy() is stable, so the relative order of elements that are
1445 * copied is unchanged.
1446 */
1448 typename _BinaryPredicate>
1449 inline _OutputIterator
1451 _OutputIterator __result,
1452 _BinaryPredicate __binary_pred)
1453 {
1454 // concept requirements -- predicates checked later
1461 _IterType;
1466 }
1468 /**
1469 * @brief Remove consecutive duplicate values from a sequence.
1470 * @param first A forward iterator.
1471 * @param last A forward iterator.
1472 * @return An iterator designating the end of the resulting sequence.
1473 *
1474 * Removes all but the first element from each group of consecutive
1475 * values that compare equal.
1476 * unique() is stable, so the relative order of elements that are
1477 * not removed is unchanged.
1478 * Elements between the end of the resulting sequence and @p last
1479 * are still present, but their value is unspecified.
1480 */
1482 _ForwardIterator
1484 {
1485 // concept requirements
1487 _ForwardIterator>)
1492 // Skip the beginning, if already unique.
1497 // Do the real copy work.
1504 }
1506 /**
1507 * @brief Remove consecutive values from a sequence using a predicate.
1508 * @param first A forward iterator.
1509 * @param last A forward iterator.
1510 * @param binary_pred A binary predicate.
1511 * @return An iterator designating the end of the resulting sequence.
1512 *
1513 * Removes all but the first element from each group of consecutive
1514 * values for which @p binary_pred returns true.
1515 * unique() is stable, so the relative order of elements that are
1516 * not removed is unchanged.
1517 * Elements between the end of the resulting sequence and @p last
1518 * are still present, but their value is unspecified.
1519 */
1521 _ForwardIterator
1523 _BinaryPredicate __binary_pred)
1524 {
1525 // concept requirements
1527 _ForwardIterator>)
1533 // Skip the beginning, if already unique.
1538 // Do the real copy work.
1545 }
1547 /**
1548 * @if maint
1549 * This is an uglified reverse(_BidirectionalIterator,
1550 * _BidirectionalIterator)
1551 * overloaded for bidirectional iterators.
1552 * @endif
1553 */
1555 void
1557 bidirectional_iterator_tag)
1558 {
1562 else
1563 {
1566 }
1567 }
1569 /**
1570 * @if maint
1571 * This is an uglified reverse(_BidirectionalIterator,
1572 * _BidirectionalIterator)
1573 * overloaded for random access iterators.
1574 * @endif
1575 */
1577 void
1579 random_access_iterator_tag)
1580 {
1585 {
1589 }
1590 }
1592 /**
1593 * @brief Reverse a sequence.
1594 * @param first A bidirectional iterator.
1595 * @param last A bidirectional iterator.
1596 * @return reverse() returns no value.
1597 *
1598 * Reverses the order of the elements in the range @p [first,last),
1599 * so that the first element becomes the last etc.
1600 * For every @c i such that @p 0<=i<=(last-first)/2), @p reverse()
1601 * swaps @p *(first+i) and @p *(last-(i+1))
1602 */
1606 {
1607 // concept requirements
1609 _BidirectionalIterator>)
1612 }
1614 /**
1615 * @brief Copy a sequence, reversing its elements.
1616 * @param first A bidirectional iterator.
1617 * @param last A bidirectional iterator.
1618 * @param result An output iterator.
1619 * @return An iterator designating the end of the resulting sequence.
1620 *
1621 * Copies the elements in the range @p [first,last) to the range
1622 * @p [result,result+(last-first)) such that the order of the
1623 * elements is reversed.
1624 * For every @c i such that @p 0<=i<=(last-first), @p reverse_copy()
1625 * performs the assignment @p *(result+(last-first)-i) = *(first+i).
1626 * The ranges @p [first,last) and @p [result,result+(last-first))
1627 * must not overlap.
1628 */
1630 _OutputIterator
1632 _OutputIterator __result)
1633 {
1634 // concept requirements
1636 _BidirectionalIterator>)
1642 {
1646 }
1648 }
1651 /**
1652 * @if maint
1653 * This is a helper function for the rotate algorithm specialized on RAIs.
1654 * It returns the greatest common divisor of two integer values.
1655 * @endif
1656 */
1658 _EuclideanRingElement
1660 {
1662 {
1666 }
1668 }
1670 /**
1671 * @if maint
1672 * This is a helper function for the rotate algorithm.
1673 * @endif
1674 */
1676 void
1678 _ForwardIterator __middle,
1679 _ForwardIterator __last,
1680 forward_iterator_tag)
1681 {
1686 do
1687 {
1693 }
1699 {
1707 }
1708 }
1710 /**
1711 * @if maint
1712 * This is a helper function for the rotate algorithm.
1713 * @endif
1714 */
1716 void
1718 _BidirectionalIterator __middle,
1719 _BidirectionalIterator __last,
1720 bidirectional_iterator_tag)
1721 {
1722 // concept requirements
1724 _BidirectionalIterator>)
1733 {
1736 }
1740 else
1742 }
1744 /**
1745 * @if maint
1746 * This is a helper function for the rotate algorithm.
1747 * @endif
1748 */
1750 void
1752 _RandomAccessIterator __middle,
1753 _RandomAccessIterator __last,
1754 random_access_iterator_tag)
1755 {
1756 // concept requirements
1758 _RandomAccessIterator>)
1764 _Distance;
1766 _ValueType;
1773 {
1776 }
1781 {
1786 {
1788 {
1790 {
1793 }
1797 }
1798 }
1799 else
1800 {
1802 {
1804 {
1807 }
1810 }
1811 }
1815 }
1816 }
1818 /**
1819 * @brief Rotate the elements of a sequence.
1820 * @param first A forward iterator.
1821 * @param middle A forward iterator.
1822 * @param last A forward iterator.
1823 * @return Nothing.
1824 *
1825 * Rotates the elements of the range @p [first,last) by @p (middle-first)
1826 * positions so that the element at @p middle is moved to @p first, the
1827 * element at @p middle+1 is moved to @first+1 and so on for each element
1828 * in the range @p [first,last).
1829 *
1830 * This effectively swaps the ranges @p [first,middle) and
1831 * @p [middle,last).
1832 *
1833 * Performs @p *(first+(n+(last-middle))%(last-first))=*(first+n) for
1834 * each @p n in the range @p [0,last-first).
1835 */
1839 _ForwardIterator __last)
1840 {
1841 // concept requirements
1843 _ForwardIterator>)
1848 _IterType;
1850 }
1852 /**
1853 * @brief Copy a sequence, rotating its elements.
1854 * @param first A forward iterator.
1855 * @param middle A forward iterator.
1856 * @param last A forward iterator.
1857 * @param result An output iterator.
1858 * @return An iterator designating the end of the resulting sequence.
1859 *
1860 * Copies the elements of the range @p [first,last) to the range
1861 * beginning at @result, rotating the copied elements by @p (middle-first)
1862 * positions so that the element at @p middle is moved to @p result, the
1863 * element at @p middle+1 is moved to @result+1 and so on for each element
1864 * in the range @p [first,last).
1865 *
1866 * Performs @p *(result+(n+(last-middle))%(last-first))=*(first+n) for
1867 * each @p n in the range @p [0,last-first).
1868 */
1870 _OutputIterator
1873 {
1874 // concept requirements
1883 }
1885 /**
1886 * @brief Randomly shuffle the elements of a sequence.
1887 * @param first A forward iterator.
1888 * @param last A forward iterator.
1889 * @return Nothing.
1890 *
1891 * Reorder the elements in the range @p [first,last) using a random
1892 * distribution, so that every possible ordering of the sequence is
1893 * equally likely.
1894 */
1898 {
1899 // concept requirements
1901 _RandomAccessIterator>)
1907 }
1909 /**
1910 * @brief Shuffle the elements of a sequence using a random number
1911 * generator.
1912 * @param first A forward iterator.
1913 * @param last A forward iterator.
1914 * @param rand The RNG functor or function.
1915 * @return Nothing.
1916 *
1917 * Reorders the elements in the range @p [first,last) using @p rand to
1918 * provide a random distribution. Calling @p rand(N) for a positive
1919 * integer @p N should return a randomly chosen integer from the
1920 * range [0,N).
1921 */
1923 void
1926 {
1927 // concept requirements
1929 _RandomAccessIterator>)
1936 }
1939 /**
1940 * @if maint
1941 * This is a helper function...
1942 * @endif
1943 */
1945 _ForwardIterator
1947 _Predicate __pred,
1948 forward_iterator_tag)
1949 {
1961 {
1964 }
1967 }
1969 /**
1970 * @if maint
1971 * This is a helper function...
1972 * @endif
1973 */
1975 _BidirectionalIterator
1977 _Predicate __pred,
1978 bidirectional_iterator_tag)
1979 {
1981 {
1987 else
1995 else
1999 }
2000 }
2002 /**
2003 * @brief Move elements for which a predicate is true to the beginning
2004 * of a sequence.
2005 * @param first A forward iterator.
2006 * @param last A forward iterator.
2007 * @param pred A predicate functor.
2008 * @return An iterator @p middle such that @p pred(i) is true for each
2009 * iterator @p i in the range @p [first,middle) and false for each @p i
2010 * in the range @p [middle,last).
2011 *
2012 * @p pred must not modify its operand. @p partition() does not preserve
2013 * the relative ordering of elements in each group, use
2014 * @p stable_partition() if this is needed.
2015 */
2017 inline _ForwardIterator
2019 _Predicate __pred)
2020 {
2021 // concept requirements
2023 _ForwardIterator>)
2030 }
2033 /**
2034 * @if maint
2035 * This is a helper function...
2036 * @endif
2037 */
2039 _ForwardIterator
2041 _ForwardIterator __last,
2043 {
2049 __middle,
2050 __pred,
2053 __pred,
2054 __len
2059 }
2061 /**
2062 * @if maint
2063 * This is a helper function...
2064 * @endif
2065 */
2067 typename _Distance>
2068 _ForwardIterator
2070 _ForwardIterator __last,
2072 _Pointer __buffer,
2073 _Distance __buffer_size)
2074 {
2076 {
2081 {
2084 }
2085 else
2086 {
2089 }
2092 }
2093 else
2094 {
2097 _ForwardIterator __begin =
2100 __buffer_size);
2101 _ForwardIterator __end =
2108 }
2109 }
2111 /**
2112 * @brief Move elements for which a predicate is true to the beginning
2113 * of a sequence, preserving relative ordering.
2114 * @param first A forward iterator.
2115 * @param last A forward iterator.
2116 * @param pred A predicate functor.
2117 * @return An iterator @p middle such that @p pred(i) is true for each
2118 * iterator @p i in the range @p [first,middle) and false for each @p i
2119 * in the range @p [middle,last).
2120 *
2121 * Performs the same function as @p partition() with the additional
2122 * guarantee that the relative ordering of elements in each group is
2123 * preserved, so any two elements @p x and @p y in the range
2124 * @p [first,last) such that @p pred(x)==pred(y) will have the same
2125 * relative ordering after calling @p stable_partition().
2126 */
2128 _ForwardIterator
2130 _Predicate __pred)
2131 {
2132 // concept requirements
2134 _ForwardIterator>)
2141 else
2142 {
2144 _ValueType;
2146 _DistanceType;
2149 __last);
2151 return
2155 else
2156 return
2159 }
2160 }
2162 /**
2163 * @if maint
2164 * This is a helper function...
2165 * @endif
2166 */
2168 _RandomAccessIterator
2171 {
2173 {
2183 }
2184 }
2186 /**
2187 * @if maint
2188 * This is a helper function...
2189 * @endif
2190 */
2192 _RandomAccessIterator
2194 _RandomAccessIterator __last,
2196 {
2198 {
2208 }
2209 }
2211 /**
2212 * @if maint
2213 * @doctodo
2214 * This controls some aspect of the sort routines.
2215 * @endif
2216 */
2219 /**
2220 * @if maint
2221 * This is a helper function for the sort routine.
2222 * @endif
2223 */
2225 void
2227 {
2231 {
2235 }
2237 }
2239 /**
2240 * @if maint
2241 * This is a helper function for the sort routine.
2242 * @endif
2243 */
2245 void
2247 _Compare __comp)
2248 {
2252 {
2256 }
2258 }
2260 /**
2261 * @if maint
2262 * This is a helper function for the sort routine.
2263 * @endif
2264 */
2266 void
2268 _RandomAccessIterator __last)
2269 {
2274 {
2278 {
2281 }
2282 else
2284 }
2285 }
2287 /**
2288 * @if maint
2289 * This is a helper function for the sort routine.
2290 * @endif
2291 */
2293 void
2296 {
2300 {
2304 {
2307 }
2308 else
2310 }
2311 }
2313 /**
2314 * @if maint
2315 * This is a helper function for the sort routine.
2316 * @endif
2317 */
2321 _RandomAccessIterator __last)
2322 {
2324 _ValueType;
2328 }
2330 /**
2331 * @if maint
2332 * This is a helper function for the sort routine.
2333 * @endif
2334 */
2339 {
2341 _ValueType;
2345 }
2347 /**
2348 * @if maint
2349 * This is a helper function for the sort routine.
2350 * @endif
2351 */
2353 void
2355 _RandomAccessIterator __last)
2356 {
2358 {
2361 }
2362 else
2364 }
2366 /**
2367 * @if maint
2368 * This is a helper function for the sort routine.
2369 * @endif
2370 */
2372 void
2375 {
2377 {
2380 __comp);
2381 }
2382 else
2384 }
2386 /**
2387 * @if maint
2388 * This is a helper function for the sort routine.
2389 * @endif
2390 */
2392 inline _Size
2394 {
2395 _Size __k;
2399 }
2401 /**
2402 * @brief Sort the smallest elements of a sequence.
2403 * @param first An iterator.
2404 * @param middle Another iterator.
2405 * @param last Another iterator.
2406 * @return Nothing.
2407 *
2408 * Sorts the smallest @p (middle-first) elements in the range
2409 * @p [first,last) and moves them to the range @p [first,middle). The
2410 * order of the remaining elements in the range @p [middle,last) is
2411 * undefined.
2412 * After the sort if @p i and @j are iterators in the range
2413 * @p [first,middle) such that @i precedes @j and @k is an iterator in
2414 * the range @p [middle,last) then @p *j<*i and @p *k<*i are both false.
2415 */
2417 void
2419 _RandomAccessIterator __middle,
2420 _RandomAccessIterator __last)
2421 {
2423 _ValueType;
2425 // concept requirements
2427 _RandomAccessIterator>)
2437 }
2439 /**
2440 * @brief Sort the smallest elements of a sequence using a predicate
2441 * for comparison.
2442 * @param first An iterator.
2443 * @param middle Another iterator.
2444 * @param last Another iterator.
2445 * @param comp A comparison functor.
2446 * @return Nothing.
2447 *
2448 * Sorts the smallest @p (middle-first) elements in the range
2449 * @p [first,last) and moves them to the range @p [first,middle). The
2450 * order of the remaining elements in the range @p [middle,last) is
2451 * undefined.
2452 * After the sort if @p i and @j are iterators in the range
2453 * @p [first,middle) such that @i precedes @j and @k is an iterator in
2454 * the range @p [middle,last) then @p *comp(j,*i) and @p comp(*k,*i)
2455 * are both false.
2456 */
2458 void
2460 _RandomAccessIterator __middle,
2461 _RandomAccessIterator __last,
2462 _Compare __comp)
2463 {
2465 _ValueType;
2467 // concept requirements
2469 _RandomAccessIterator>)
2480 }
2482 /**
2483 * @brief Copy the smallest elements of a sequence.
2484 * @param first An iterator.
2485 * @param last Another iterator.
2486 * @param result_first A random-access iterator.
2487 * @param result_last Another random-access iterator.
2488 * @return An iterator indicating the end of the resulting sequence.
2489 *
2490 * Copies and sorts the smallest N values from the range @p [first,last)
2491 * to the range beginning at @p result_first, where the number of
2492 * elements to be copied, @p N, is the smaller of @p (last-first) and
2493 * @p (result_last-result_first).
2494 * After the sort if @p i and @j are iterators in the range
2495 * @p [result_first,result_first+N) such that @i precedes @j then
2496 * @p *j<*i is false.
2497 * The value returned is @p result_first+N.
2498 */
2500 _RandomAccessIterator
2502 _RandomAccessIterator __result_first,
2503 _RandomAccessIterator __result_last)
2504 {
2506 _InputValueType;
2508 _OutputValueType;
2510 _DistanceType;
2512 // concept requirements
2515 _OutputValueType>)
2525 {
2529 }
2532 {
2539 }
2542 }
2544 /**
2545 * @brief Copy the smallest elements of a sequence using a predicate for
2546 * comparison.
2547 * @param first An input iterator.
2548 * @param last Another input iterator.
2549 * @param result_first A random-access iterator.
2550 * @param result_last Another random-access iterator.
2551 * @param comp A comparison functor.
2552 * @return An iterator indicating the end of the resulting sequence.
2553 *
2554 * Copies and sorts the smallest N values from the range @p [first,last)
2555 * to the range beginning at @p result_first, where the number of
2556 * elements to be copied, @p N, is the smaller of @p (last-first) and
2557 * @p (result_last-result_first).
2558 * After the sort if @p i and @j are iterators in the range
2559 * @p [result_first,result_first+N) such that @i precedes @j then
2560 * @p comp(*j,*i) is false.
2561 * The value returned is @p result_first+N.
2562 */
2564 _RandomAccessIterator
2566 _RandomAccessIterator __result_first,
2567 _RandomAccessIterator __result_last,
2568 _Compare __comp)
2569 {
2571 _InputValueType;
2573 _OutputValueType;
2575 _DistanceType;
2577 // concept requirements
2580 _RandomAccessIterator>)
2582 _OutputValueType>)
2592 {
2596 }
2599 {
2605 __comp);
2607 }
2610 }
2612 /**
2613 * @if maint
2614 * This is a helper function for the sort routine.
2615 * @endif
2616 */
2618 void
2620 _RandomAccessIterator __last,
2621 _Size __depth_limit)
2622 {
2624 _ValueType;
2627 {
2629 {
2632 }
2634 _RandomAccessIterator __cut =
2637 *(__first
2638 + (__last
2641 *(__last
2645 }
2646 }
2648 /**
2649 * @if maint
2650 * This is a helper function for the sort routine.
2651 * @endif
2652 */
2654 void
2656 _RandomAccessIterator __last,
2658 {
2660 _ValueType;
2663 {
2665 {
2668 }
2670 _RandomAccessIterator __cut =
2673 *(__first
2674 + (__last
2678 __comp)),
2679 __comp);
2682 }
2683 }
2685 /**
2686 * @brief Sort the elements of a sequence.
2687 * @param first An iterator.
2688 * @param last Another iterator.
2689 * @return Nothing.
2690 *
2691 * Sorts the elements in the range @p [first,last) in ascending order,
2692 * such that @p *(i+1)<*i is false for each iterator @p i in the range
2693 * @p [first,last-1).
2694 *
2695 * The relative ordering of equivalent elements is not preserved, use
2696 * @p stable_sort() if this is needed.
2697 */
2701 {
2703 _ValueType;
2705 // concept requirements
2707 _RandomAccessIterator>)
2712 {
2715 }
2716 }
2718 /**
2719 * @brief Sort the elements of a sequence using a predicate for comparison.
2720 * @param first An iterator.
2721 * @param last Another iterator.
2722 * @param comp A comparison functor.
2723 * @return Nothing.
2724 *
2725 * Sorts the elements in the range @p [first,last) in ascending order,
2726 * such that @p comp(*(i+1),*i) is false for every iterator @p i in the
2727 * range @p [first,last-1).
2728 *
2729 * The relative ordering of equivalent elements is not preserved, use
2730 * @p stable_sort() if this is needed.
2731 */
2735 _Compare __comp)
2736 {
2738 _ValueType;
2740 // concept requirements
2742 _RandomAccessIterator>)
2744 _ValueType>)
2748 {
2750 __comp);
2752 }
2753 }
2755 /**
2756 * @brief Finds the first position in which @a val could be inserted
2757 * without changing the ordering.
2758 * @param first An iterator.
2759 * @param last Another iterator.
2760 * @param val The search term.
2761 * @return An iterator pointing to the first element "not less than" @a val,
2762 * or end() if every element is less than @a val.
2763 * @ingroup binarysearch
2764 */
2766 _ForwardIterator
2769 {
2771 _ValueType;
2773 _DistanceType;
2775 // concept requirements
2776 // Note that these are slightly stricter than those of the 4-argument
2777 // version, defined next. The difference is in the strictness of the
2778 // comparison operations... so for looser checking, define your own
2779 // comparison function, as was intended.
2786 _DistanceType __half;
2787 _ForwardIterator __middle;
2790 {
2795 {
2799 }
2800 else
2802 }
2804 }
2806 /**
2807 * @brief Finds the first position in which @a val could be inserted
2808 * without changing the ordering.
2809 * @param first An iterator.
2810 * @param last Another iterator.
2811 * @param val The search term.
2812 * @param comp A functor to use for comparisons.
2813 * @return An iterator pointing to the first element "not less than" @a val,
2814 * or end() if every element is less than @a val.
2815 * @ingroup binarysearch
2816 *
2817 * The comparison function should have the same effects on ordering as
2818 * the function used for the initial sort.
2819 */
2821 _ForwardIterator
2824 {
2826 _ValueType;
2828 _DistanceType;
2830 // concept requirements
2837 _DistanceType __half;
2838 _ForwardIterator __middle;
2841 {
2846 {
2850 }
2851 else
2853 }
2855 }
2857 /**
2858 * @brief Finds the last position in which @a val could be inserted
2859 * without changing the ordering.
2860 * @param first An iterator.
2861 * @param last Another iterator.
2862 * @param val The search term.
2863 * @return An iterator pointing to the first element greater than @a val,
2864 * or end() if no elements are greater than @a val.
2865 * @ingroup binarysearch
2866 */
2868 _ForwardIterator
2871 {
2873 _ValueType;
2875 _DistanceType;
2877 // concept requirements
2878 // See comments on lower_bound.
2885 _DistanceType __half;
2886 _ForwardIterator __middle;
2889 {
2895 else
2896 {
2900 }
2901 }
2903 }
2905 /**
2906 * @brief Finds the last position in which @a val could be inserted
2907 * without changing the ordering.
2908 * @param first An iterator.
2909 * @param last Another iterator.
2910 * @param val The search term.
2911 * @param comp A functor to use for comparisons.
2912 * @return An iterator pointing to the first element greater than @a val,
2913 * or end() if no elements are greater than @a val.
2914 * @ingroup binarysearch
2915 *
2916 * The comparison function should have the same effects on ordering as
2917 * the function used for the initial sort.
2918 */
2920 _ForwardIterator
2923 {
2925 _ValueType;
2927 _DistanceType;
2929 // concept requirements
2936 _DistanceType __half;
2937 _ForwardIterator __middle;
2940 {
2946 else
2947 {
2951 }
2952 }
2954 }
2956 /**
2957 * @if maint
2958 * This is a helper function for the merge routines.
2959 * @endif
2960 */
2962 void
2964 _BidirectionalIterator __middle,
2965 _BidirectionalIterator __last,
2967 {
2971 {
2975 }
2981 {
2986 }
2987 else
2988 {
2993 }
3001 }
3003 /**
3004 * @if maint
3005 * This is a helper function for the merge routines.
3006 * @endif
3007 */
3009 typename _Compare>
3010 void
3012 _BidirectionalIterator __middle,
3013 _BidirectionalIterator __last,
3015 _Compare __comp)
3016 {
3020 {
3024 }
3030 {
3034 __comp);
3036 }
3037 else
3038 {
3042 __comp);
3044 }
3052 }
3054 /**
3055 * @if maint
3056 * This is a helper function for the stable sorting routines.
3057 * @endif
3058 */
3060 void
3062 _RandomAccessIterator __last)
3063 {
3065 {
3068 }
3075 }
3077 /**
3078 * @if maint
3079 * This is a helper function for the stable sorting routines.
3080 * @endif
3081 */
3083 void
3086 {
3088 {
3091 }
3098 __comp);
3099 }
3101 /**
3102 * @brief Merges two sorted ranges.
3103 * @param first1 An iterator.
3104 * @param first2 Another iterator.
3105 * @param last1 Another iterator.
3106 * @param last2 Another iterator.
3107 * @param result An iterator pointing to the end of the merged range.
3108 * @return An iterator pointing to the first element "not less than" @a val.
3109 *
3110 * Merges the ranges [first1,last1) and [first2,last2) into the sorted range
3111 * [result, result + (last1-first1) + (last2-first2)). Both input ranges
3112 * must be sorted, and the output range must not overlap with either of
3113 * the input ranges. The sort is @e stable, that is, for equivalent
3114 * elements in the two ranges, elements from the first range will always
3115 * come before elements from the second.
3116 */
3118 typename _OutputIterator>
3119 _OutputIterator
3122 _OutputIterator __result)
3123 {
3124 // concept requirements
3138 {
3140 {
3143 }
3144 else
3145 {
3148 }
3150 }
3152 __result));
3153 }
3155 /**
3156 * @brief Merges two sorted ranges.
3157 * @param first1 An iterator.
3158 * @param first2 Another iterator.
3159 * @param last1 Another iterator.
3160 * @param last2 Another iterator.
3161 * @param result An iterator pointing to the end of the merged range.
3162 * @param comp A functor to use for comparisons.
3163 * @return An iterator pointing to the first element "not less than" @a val.
3164 *
3165 * Merges the ranges [first1,last1) and [first2,last2) into the sorted range
3166 * [result, result + (last1-first1) + (last2-first2)). Both input ranges
3167 * must be sorted, and the output range must not overlap with either of
3168 * the input ranges. The sort is @e stable, that is, for equivalent
3169 * elements in the two ranges, elements from the first range will always
3170 * come before elements from the second.
3171 *
3172 * The comparison function should have the same effects on ordering as
3173 * the function used for the initial sort.
3174 */
3177 _OutputIterator
3181 {
3182 // concept requirements
3197 {
3199 {
3202 }
3203 else
3204 {
3207 }
3209 }
3211 __result));
3212 }
3215 typename _Distance>
3216 void
3218 _RandomAccessIterator1 __last,
3219 _RandomAccessIterator2 __result,
3220 _Distance __step_size)
3221 {
3225 {
3228 __result);
3230 }
3234 __result);
3235 }
3239 void
3241 _RandomAccessIterator1 __last,
3243 _Compare __comp)
3244 {
3248 {
3251 __result,
3252 __comp);
3254 }
3259 __result,
3260 __comp);
3261 }
3266 void
3268 _RandomAccessIterator __last,
3269 _Distance __chunk_size)
3270 {
3272 {
3275 }
3277 }
3280 void
3282 _RandomAccessIterator __last,
3284 {
3286 {
3289 }
3291 }
3294 void
3296 _RandomAccessIterator __last,
3297 _Pointer __buffer)
3298 {
3300 _Distance;
3309 {
3314 }
3315 }
3318 void
3320 _RandomAccessIterator __last,
3322 {
3324 _Distance;
3333 {
3340 }
3341 }
3343 /**
3344 * @if maint
3345 * This is a helper function for the merge routines.
3346 * @endif
3347 */
3349 typename _BidirectionalIterator3>
3350 _BidirectionalIterator3
3352 _BidirectionalIterator1 __last1,
3353 _BidirectionalIterator2 __first2,
3354 _BidirectionalIterator2 __last2,
3355 _BidirectionalIterator3 __result)
3356 {
3364 {
3366 {
3371 }
3372 else
3373 {
3378 }
3379 }
3380 }
3382 /**
3383 * @if maint
3384 * This is a helper function for the merge routines.
3385 * @endif
3386 */
3389 _BidirectionalIterator3
3391 _BidirectionalIterator1 __last1,
3392 _BidirectionalIterator2 __first2,
3393 _BidirectionalIterator2 __last2,
3394 _BidirectionalIterator3 __result,
3395 _Compare __comp)
3396 {
3404 {
3406 {
3411 }
3412 else
3413 {
3418 }
3419 }
3420 }
3422 /**
3423 * @if maint
3424 * This is a helper function for the merge routines.
3425 * @endif
3426 */
3428 typename _Distance>
3429 _BidirectionalIterator1
3431 _BidirectionalIterator1 __middle,
3432 _BidirectionalIterator1 __last,
3434 _BidirectionalIterator2 __buffer,
3435 _Distance __buffer_size)
3436 {
3437 _BidirectionalIterator2 __buffer_end;
3439 {
3443 }
3445 {
3449 }
3450 else
3451 {
3455 }
3456 }
3458 /**
3459 * @if maint
3460 * This is a helper function for the merge routines.
3461 * @endif
3462 */
3464 typename _Pointer>
3465 void
3467 _BidirectionalIterator __middle,
3468 _BidirectionalIterator __last,
3471 {
3473 {
3476 }
3478 {
3482 }
3483 else
3484 {
3490 {
3496 }
3497 else
3498 {
3504 }
3505 _BidirectionalIterator __new_middle =
3508 __buffer_size);
3514 }
3515 }
3517 /**
3518 * @if maint
3519 * This is a helper function for the merge routines.
3520 * @endif
3521 */
3523 typename _Compare>
3524 void
3526 _BidirectionalIterator __middle,
3527 _BidirectionalIterator __last,
3530 _Compare __comp)
3531 {
3533 {
3536 }
3538 {
3542 }
3543 else
3544 {
3550 {
3554 __comp);
3556 }
3557 else
3558 {
3562 __comp);
3564 }
3565 _BidirectionalIterator __new_middle =
3568 __buffer_size);
3575 }
3576 }
3578 /**
3579 * @brief Merges two sorted ranges in place.
3580 * @param first An iterator.
3581 * @param middle Another iterator.
3582 * @param last Another iterator.
3583 * @return Nothing.
3584 *
3585 * Merges two sorted and consecutive ranges, [first,middle) and
3586 * [middle,last), and puts the result in [first,last). The output will
3587 * be sorted. The sort is @e stable, that is, for equivalent
3588 * elements in the two ranges, elements from the first range will always
3589 * come before elements from the second.
3590 *
3591 * If enough additional memory is available, this takes (last-first)-1
3592 * comparisons. Otherwise an NlogN algorithm is used, where N is
3593 * distance(first,last).
3594 */
3596 void
3598 _BidirectionalIterator __middle,
3599 _BidirectionalIterator __last)
3600 {
3602 _ValueType;
3604 _DistanceType;
3606 // concept requirements
3608 _BidirectionalIterator>)
3620 __last);
3623 else
3626 }
3628 /**
3629 * @brief Merges two sorted ranges in place.
3630 * @param first An iterator.
3631 * @param middle Another iterator.
3632 * @param last Another iterator.
3633 * @param comp A functor to use for comparisons.
3634 * @return Nothing.
3635 *
3636 * Merges two sorted and consecutive ranges, [first,middle) and
3637 * [middle,last), and puts the result in [first,last). The output will
3638 * be sorted. The sort is @e stable, that is, for equivalent
3639 * elements in the two ranges, elements from the first range will always
3640 * come before elements from the second.
3641 *
3642 * If enough additional memory is available, this takes (last-first)-1
3643 * comparisons. Otherwise an NlogN algorithm is used, where N is
3644 * distance(first,last).
3645 *
3646 * The comparison function should have the same effects on ordering as
3647 * the function used for the initial sort.
3648 */
3650 void
3652 _BidirectionalIterator __middle,
3653 _BidirectionalIterator __last,
3654 _Compare __comp)
3655 {
3657 _ValueType;
3659 _DistanceType;
3661 // concept requirements
3663 _BidirectionalIterator>)
3676 __last);
3680 else
3683 __comp);
3684 }
3687 typename _Distance>
3688 void
3690 _RandomAccessIterator __last,
3692 {
3696 {
3701 }
3702 else
3703 {
3706 }
3711 }
3715 void
3717 _RandomAccessIterator __last,
3719 _Compare __comp)
3720 {
3724 {
3729 }
3730 else
3731 {
3734 }
3739 __comp);
3740 }
3742 /**
3743 * @brief Sort the elements of a sequence, preserving the relative order
3744 * of equivalent elements.
3745 * @param first An iterator.
3746 * @param last Another iterator.
3747 * @return Nothing.
3748 *
3749 * Sorts the elements in the range @p [first,last) in ascending order,
3750 * such that @p *(i+1)<*i is false for each iterator @p i in the range
3751 * @p [first,last-1).
3752 *
3753 * The relative ordering of equivalent elements is preserved, so any two
3754 * elements @p x and @p y in the range @p [first,last) such that
3755 * @p x<y is false and @p y<x is false will have the same relative
3756 * ordering after calling @p stable_sort().
3757 */
3761 {
3763 _ValueType;
3765 _DistanceType;
3767 // concept requirements
3769 _RandomAccessIterator>)
3777 else
3780 }
3782 /**
3783 * @brief Sort the elements of a sequence using a predicate for comparison,
3784 * preserving the relative order of equivalent elements.
3785 * @param first An iterator.
3786 * @param last Another iterator.
3787 * @param comp A comparison functor.
3788 * @return Nothing.
3789 *
3790 * Sorts the elements in the range @p [first,last) in ascending order,
3791 * such that @p comp(*(i+1),*i) is false for each iterator @p i in the
3792 * range @p [first,last-1).
3793 *
3794 * The relative ordering of equivalent elements is preserved, so any two
3795 * elements @p x and @p y in the range @p [first,last) such that
3796 * @p comp(x,y) is false and @p comp(y,x) is false will have the same
3797 * relative ordering after calling @p stable_sort().
3798 */
3802 _Compare __comp)
3803 {
3805 _ValueType;
3807 _DistanceType;
3809 // concept requirements
3811 _RandomAccessIterator>)
3813 _ValueType,
3814 _ValueType>)
3820 else
3823 }
3825 /**
3826 * @brief Sort a sequence just enough to find a particular position.
3827 * @param first An iterator.
3828 * @param nth Another iterator.
3829 * @param last Another iterator.
3830 * @return Nothing.
3831 *
3832 * Rearranges the elements in the range @p [first,last) so that @p *nth
3833 * is the same element that would have been in that position had the
3834 * whole sequence been sorted.
3835 * whole sequence been sorted. The elements either side of @p *nth are
3836 * not completely sorted, but for any iterator @i in the range
3837 * @p [first,nth) and any iterator @j in the range @p [nth,last) it
3838 * holds that @p *j<*i is false.
3839 */
3841 void
3843 _RandomAccessIterator __nth,
3844 _RandomAccessIterator __last)
3845 {
3847 _ValueType;
3849 // concept requirements
3851 _RandomAccessIterator>)
3857 {
3858 _RandomAccessIterator __cut =
3861 *(__first
3862 + (__last
3865 *(__last
3869 else
3871 }
3873 }
3875 /**
3876 * @brief Sort a sequence just enough to find a particular position
3877 * using a predicate for comparison.
3878 * @param first An iterator.
3879 * @param nth Another iterator.
3880 * @param last Another iterator.
3881 * @param comp A comparison functor.
3882 * @return Nothing.
3883 *
3884 * Rearranges the elements in the range @p [first,last) so that @p *nth
3885 * is the same element that would have been in that position had the
3886 * whole sequence been sorted. The elements either side of @p *nth are
3887 * not completely sorted, but for any iterator @i in the range
3888 * @p [first,nth) and any iterator @j in the range @p [nth,last) it
3889 * holds that @p comp(*j,*i) is false.
3890 */
3892 void
3894 _RandomAccessIterator __nth,
3895 _RandomAccessIterator __last,
3896 _Compare __comp)
3897 {
3899 _ValueType;
3901 // concept requirements
3903 _RandomAccessIterator>)
3910 {
3911 _RandomAccessIterator __cut =
3914 *(__first
3915 + (__last
3922 else
3924 }
3926 }
3928 /**
3929 * @brief Finds the largest subrange in which @a val could be inserted
3930 * at any place in it without changing the ordering.
3931 * @param first An iterator.
3932 * @param last Another iterator.
3933 * @param val The search term.
3934 * @return An pair of iterators defining the subrange.
3935 * @ingroup binarysearch
3936 *
3937 * This is equivalent to
3938 * @code
3939 * std::make_pair(lower_bound(first, last, val),
3940 * upper_bound(first, last, val))
3941 * @endcode
3942 * but does not actually call those functions.
3943 */
3948 {
3950 _ValueType;
3952 _DistanceType;
3954 // concept requirements
3955 // See comments on lower_bound.
3962 _DistanceType __half;
3966 {
3971 {
3975 }
3978 else
3979 {
3984 }
3985 }
3987 }
3989 /**
3990 * @brief Finds the largest subrange in which @a val could be inserted
3991 * at any place in it without changing the ordering.
3992 * @param first An iterator.
3993 * @param last Another iterator.
3994 * @param val The search term.
3995 * @param comp A functor to use for comparisons.
3996 * @return An pair of iterators defining the subrange.
3997 * @ingroup binarysearch
3998 *
3999 * This is equivalent to
4000 * @code
4001 * std::make_pair(lower_bound(first, last, val, comp),
4002 * upper_bound(first, last, val, comp))
4003 * @endcode
4004 * but does not actually call those functions.
4005 */
4010 _Compare __comp)
4011 {
4013 _ValueType;
4015 _DistanceType;
4017 // concept requirements
4026 _DistanceType __half;
4030 {
4035 {
4039 }
4042 else
4043 {
4048 }
4049 }
4051 }
4053 /**
4054 * @brief Determines whether an element exists in a range.
4055 * @param first An iterator.
4056 * @param last Another iterator.
4057 * @param val The search term.
4058 * @return True if @a val (or its equivelent) is in [@a first,@a last ].
4059 * @ingroup binarysearch
4060 *
4061 * Note that this does not actually return an iterator to @a val. For
4062 * that, use std::find or a container's specialized find member functions.
4063 */
4065 bool
4068 {
4069 // concept requirements
4070 // See comments on lower_bound.
4079 }
4081 /**
4082 * @brief Determines whether an element exists in a range.
4083 * @param first An iterator.
4084 * @param last Another iterator.
4085 * @param val The search term.
4086 * @param comp A functor to use for comparisons.
4087 * @return True if @a val (or its equivelent) is in [@a first,@a last ].
4088 * @ingroup binarysearch
4089 *
4090 * Note that this does not actually return an iterator to @a val. For
4091 * that, use std::find or a container's specialized find member functions.
4092 *
4093 * The comparison function should have the same effects on ordering as
4094 * the function used for the initial sort.
4095 */
4097 bool
4100 {
4101 // concept requirements
4111 }
4113 // Set algorithms: includes, set_union, set_intersection, set_difference,
4114 // set_symmetric_difference. All of these algorithms have the precondition
4115 // that their input ranges are sorted and the postcondition that their output
4116 // ranges are sorted.
4118 /**
4119 * @brief Determines whether all elements of a sequence exists in a range.
4120 * @param first1 Start of search range.
4121 * @param last1 End of search range.
4122 * @param first2 Start of sequence
4123 * @param last2 End of sequence.
4124 * @return True if each element in [first2,last2) is contained in order
4125 * within [first1,last1). False otherwise.
4126 * @ingroup setoperations
4127 *
4128 * This operation expects both [first1,last1) and [first2,last2) to be
4129 * sorted. Searches for the presence of each element in [first2,last2)
4130 * within [first1,last1). The iterators over each range only move forward,
4131 * so this is a linear algorithm. If an element in [first2,last2) is not
4132 * found before the search iterator reaches @a last2, false is returned.
4133 */
4135 bool
4138 {
4139 // concept requirements
4155 else
4159 }
4161 /**
4162 * @brief Determines whether all elements of a sequence exists in a range
4163 * using comparison.
4164 * @param first1 Start of search range.
4165 * @param last1 End of search range.
4166 * @param first2 Start of sequence
4167 * @param last2 End of sequence.
4168 * @param comp Comparison function to use.
4169 * @return True if each element in [first2,last2) is contained in order
4170 * within [first1,last1) according to comp. False otherwise.
4171 * @ingroup setoperations
4172 *
4173 * This operation expects both [first1,last1) and [first2,last2) to be
4174 * sorted. Searches for the presence of each element in [first2,last2)
4175 * within [first1,last1), using comp to decide. The iterators over each
4176 * range only move forward, so this is a linear algorithm. If an element
4177 * in [first2,last2) is not found before the search iterator reaches @a
4178 * last2, false is returned.
4179 */
4181 typename _Compare>
4182 bool
4185 {
4186 // concept requirements
4203 else
4207 }
4209 /**
4210 * @brief Return the union of two sorted ranges.
4211 * @param first1 Start of first range.
4212 * @param last1 End of first range.
4213 * @param first2 Start of second range.
4214 * @param last2 End of second range.
4215 * @return End of the output range.
4216 * @ingroup setoperations
4217 *
4218 * This operation iterates over both ranges, copying elements present in
4219 * each range in order to the output range. Iterators increment for each
4220 * range. When the current element of one range is less than the other,
4221 * that element is copied and the iterator advanced. If an element is
4222 * contained in both ranges, the element from the first range is copied and
4223 * both ranges advance. The output range may not overlap either input
4224 * range.
4225 */
4227 typename _OutputIterator>
4228 _OutputIterator
4231 _OutputIterator __result)
4232 {
4233 // concept requirements
4247 {
4249 {
4252 }
4254 {
4257 }
4258 else
4259 {
4263 }
4265 }
4267 __result));
4268 }
4270 /**
4271 * @brief Return the union of two sorted ranges using a comparison functor.
4272 * @param first1 Start of first range.
4273 * @param last1 End of first range.
4274 * @param first2 Start of second range.
4275 * @param last2 End of second range.
4276 * @param comp The comparison functor.
4277 * @return End of the output range.
4278 * @ingroup setoperations
4279 *
4280 * This operation iterates over both ranges, copying elements present in
4281 * each range in order to the output range. Iterators increment for each
4282 * range. When the current element of one range is less than the other
4283 * according to @a comp, that element is copied and the iterator advanced.
4284 * If an equivalent element according to @a comp is contained in both
4285 * ranges, the element from the first range is copied and both ranges
4286 * advance. The output range may not overlap either input range.
4287 */
4290 _OutputIterator
4294 {
4295 // concept requirements
4310 {
4312 {
4315 }
4317 {
4320 }
4321 else
4322 {
4326 }
4328 }
4330 __result));
4331 }
4333 /**
4334 * @brief Return the intersection of two sorted ranges.
4335 * @param first1 Start of first range.
4336 * @param last1 End of first range.
4337 * @param first2 Start of second range.
4338 * @param last2 End of second range.
4339 * @return End of the output range.
4340 * @ingroup setoperations
4341 *
4342 * This operation iterates over both ranges, copying elements present in
4343 * both ranges in order to the output range. Iterators increment for each
4344 * range. When the current element of one range is less than the other,
4345 * that iterator advances. If an element is contained in both ranges, the
4346 * element from the first range is copied and both ranges advance. The
4347 * output range may not overlap either input range.
4348 */
4350 typename _OutputIterator>
4351 _OutputIterator
4354 _OutputIterator __result)
4355 {
4356 // concept requirements
4374 else
4375 {
4380 }
4382 }
4384 /**
4385 * @brief Return the intersection of two sorted ranges using comparison
4386 * functor.
4387 * @param first1 Start of first range.
4388 * @param last1 End of first range.
4389 * @param first2 Start of second range.
4390 * @param last2 End of second range.
4391 * @param comp The comparison functor.
4392 * @return End of the output range.
4393 * @ingroup setoperations
4394 *
4395 * This operation iterates over both ranges, copying elements present in
4396 * both ranges in order to the output range. Iterators increment for each
4397 * range. When the current element of one range is less than the other
4398 * according to @a comp, that iterator advances. If an element is
4399 * contained in both ranges according to @a comp, the element from the
4400 * first range is copied and both ranges advance. The output range may not
4401 * overlap either input range.
4402 */
4405 _OutputIterator
4409 {
4410 // concept requirements
4429 else
4430 {
4435 }
4437 }
4439 /**
4440 * @brief Return the difference of two sorted ranges.
4441 * @param first1 Start of first range.
4442 * @param last1 End of first range.
4443 * @param first2 Start of second range.
4444 * @param last2 End of second range.
4445 * @return End of the output range.
4446 * @ingroup setoperations
4447 *
4448 * This operation iterates over both ranges, copying elements present in
4449 * the first range but not the second in order to the output range.
4450 * Iterators increment for each range. When the current element of the
4451 * first range is less than the second, that element is copied and the
4452 * iterator advances. If the current element of the second range is less,
4453 * the iterator advances, but no element is copied. If an element is
4454 * contained in both ranges, no elements are copied and both ranges
4455 * advance. The output range may not overlap either input range.
4456 */
4458 typename _OutputIterator>
4459 _OutputIterator
4462 _OutputIterator __result)
4463 {
4464 // concept requirements
4479 {
4483 }
4486 else
4487 {
4490 }
4492 }
4494 /**
4495 * @brief Return the difference of two sorted ranges using comparison
4496 * functor.
4497 * @param first1 Start of first range.
4498 * @param last1 End of first range.
4499 * @param first2 Start of second range.
4500 * @param last2 End of second range.
4501 * @param comp The comparison functor.
4502 * @return End of the output range.
4503 * @ingroup setoperations
4504 *
4505 * This operation iterates over both ranges, copying elements present in
4506 * the first range but not the second in order to the output range.
4507 * Iterators increment for each range. When the current element of the
4508 * first range is less than the second according to @a comp, that element
4509 * is copied and the iterator advances. If the current element of the
4510 * second range is less, no element is copied and the iterator advances.
4511 * If an element is contained in both ranges according to @a comp, no
4512 * elements are copied and both ranges advance. The output range may not
4513 * overlap either input range.
4514 */
4517 _OutputIterator
4521 {
4522 // concept requirements
4538 {
4542 }
4545 else
4546 {
4549 }
4551 }
4553 /**
4554 * @brief Return the symmetric difference of two sorted ranges.
4555 * @param first1 Start of first range.
4556 * @param last1 End of first range.
4557 * @param first2 Start of second range.
4558 * @param last2 End of second range.
4559 * @return End of the output range.
4560 * @ingroup setoperations
4561 *
4562 * This operation iterates over both ranges, copying elements present in
4563 * one range but not the other in order to the output range. Iterators
4564 * increment for each range. When the current element of one range is less
4565 * than the other, that element is copied and the iterator advances. If an
4566 * element is contained in both ranges, no elements are copied and both
4567 * ranges advance. The output range may not overlap either input range.
4568 */
4570 typename _OutputIterator>
4571 _OutputIterator
4574 _OutputIterator __result)
4575 {
4576 // concept requirements
4591 {
4595 }
4597 {
4601 }
4602 else
4603 {
4606 }
4609 }
4611 /**
4612 * @brief Return the symmetric difference of two sorted ranges using
4613 * comparison functor.
4614 * @param first1 Start of first range.
4615 * @param last1 End of first range.
4616 * @param first2 Start of second range.
4617 * @param last2 End of second range.
4618 * @param comp The comparison functor.
4619 * @return End of the output range.
4620 * @ingroup setoperations
4621 *
4622 * This operation iterates over both ranges, copying elements present in
4623 * one range but not the other in order to the output range. Iterators
4624 * increment for each range. When the current element of one range is less
4625 * than the other according to @a comp, that element is copied and the
4626 * iterator advances. If an element is contained in both ranges according
4627 * to @a comp, no elements are copied and both ranges advance. The output
4628 * range may not overlap either input range.
4629 */
4632 _OutputIterator
4635 _OutputIterator __result,
4636 _Compare __comp)
4637 {
4638 // concept requirements
4654 {
4658 }
4660 {
4664 }
4665 else
4666 {
4669 }
4672 }
4674 // min_element and max_element, with and without an explicitly supplied
4675 // comparison function.
4677 /**
4678 * @brief Return the maximum element in a range.
4679 * @param first Start of range.
4680 * @param last End of range.
4681 * @return Iterator referencing the first instance of the largest value.
4682 */
4684 _ForwardIterator
4686 {
4687 // concept requirements
4700 }
4702 /**
4703 * @brief Return the maximum element in a range using comparison functor.
4704 * @param first Start of range.
4705 * @param last End of range.
4706 * @param comp Comparison functor.
4707 * @return Iterator referencing the first instance of the largest value
4708 * according to comp.
4709 */
4711 _ForwardIterator
4713 _Compare __comp)
4714 {
4715 // concept requirements
4727 }
4729 /**
4730 * @brief Return the minimum element in a range.
4731 * @param first Start of range.
4732 * @param last End of range.
4733 * @return Iterator referencing the first instance of the smallest value.
4734 */
4736 _ForwardIterator
4738 {
4739 // concept requirements
4752 }
4754 /**
4755 * @brief Return the minimum element in a range using comparison functor.
4756 * @param first Start of range.
4757 * @param last End of range.
4758 * @param comp Comparison functor.
4759 * @return Iterator referencing the first instance of the smallest value
4760 * according to comp.
4761 */
4763 _ForwardIterator
4765 _Compare __comp)
4766 {
4767 // concept requirements
4781 }
4783 // next_permutation and prev_permutation, with and without an explicitly
4784 // supplied comparison function.
4786 /**
4787 * @brief Permute range into the next "dictionary" ordering.
4788 * @param first Start of range.
4789 * @param last End of range.
4790 * @return False if wrapped to first permutation, true otherwise.
4791 *
4792 * Treats all permutations of the range as a set of "dictionary" sorted
4793 * sequences. Permutes the current sequence into the next one of this set.
4794 * Returns true if there are more sequences to generate. If the sequence
4795 * is the largest of the set, the smallest is generated and false returned.
4796 */
4798 bool
4800 _BidirectionalIterator __last)
4801 {
4802 // concept requirements
4804 _BidirectionalIterator>)
4819 {
4823 {
4826 {}
4830 }
4832 {
4835 }
4836 }
4837 }
4839 /**
4840 * @brief Permute range into the next "dictionary" ordering using
4841 * comparison functor.
4842 * @param first Start of range.
4843 * @param last End of range.
4844 * @param comp
4845 * @return False if wrapped to first permutation, true otherwise.
4846 *
4847 * Treats all permutations of the range [first,last) as a set of
4848 * "dictionary" sorted sequences ordered by @a comp. Permutes the current
4849 * sequence into the next one of this set. Returns true if there are more
4850 * sequences to generate. If the sequence is the largest of the set, the
4851 * smallest is generated and false returned.
4852 */
4854 bool
4857 {
4858 // concept requirements
4860 _BidirectionalIterator>)
4876 {
4880 {
4883 {}
4887 }
4889 {
4892 }
4893 }
4894 }
4896 /**
4897 * @brief Permute range into the previous "dictionary" ordering.
4898 * @param first Start of range.
4899 * @param last End of range.
4900 * @return False if wrapped to last permutation, true otherwise.
4901 *
4902 * Treats all permutations of the range as a set of "dictionary" sorted
4903 * sequences. Permutes the current sequence into the previous one of this
4904 * set. Returns true if there are more sequences to generate. If the
4905 * sequence is the smallest of the set, the largest is generated and false
4906 * returned.
4907 */
4909 bool
4911 _BidirectionalIterator __last)
4912 {
4913 // concept requirements
4915 _BidirectionalIterator>)
4930 {
4934 {
4937 {}
4941 }
4943 {
4946 }
4947 }
4948 }
4950 /**
4951 * @brief Permute range into the previous "dictionary" ordering using
4952 * comparison functor.
4953 * @param first Start of range.
4954 * @param last End of range.
4955 * @param comp
4956 * @return False if wrapped to last permutation, true otherwise.
4957 *
4958 * Treats all permutations of the range [first,last) as a set of
4959 * "dictionary" sorted sequences ordered by @a comp. Permutes the current
4960 * sequence into the previous one of this set. Returns true if there are
4961 * more sequences to generate. If the sequence is the smallest of the set,
4962 * the largest is generated and false returned.
4963 */
4965 bool
4968 {
4969 // concept requirements
4971 _BidirectionalIterator>)
4987 {
4991 {
4994 {}
4998 }
5000 {
5003 }
5004 }
5005 }
5007 // find_first_of, with and without an explicitly supplied comparison function.
5009 /**
5010 * @brief Find element from a set in a sequence.
5011 * @param first1 Start of range to search.
5012 * @param last1 End of range to search.
5013 * @param first2 Start of match candidates.
5014 * @param last2 End of match candidates.
5015 * @return The first iterator @c i in the range
5016 * @p [first1,last1) such that @c *i == @p *(i2) such that i2 is an
5017 * interator in [first2,last2), or @p last1 if no such iterator exists.
5018 *
5019 * Searches the range @p [first1,last1) for an element that is equal to
5020 * some element in the range [first2,last2). If found, returns an iterator
5021 * in the range [first1,last1), otherwise returns @p last1.
5022 */
5024 _InputIterator
5027 {
5028 // concept requirements
5042 }
5044 /**
5045 * @brief Find element from a set in a sequence using a predicate.
5046 * @param first1 Start of range to search.
5047 * @param last1 End of range to search.
5048 * @param first2 Start of match candidates.
5049 * @param last2 End of match candidates.
5050 * @param comp Predicate to use.
5051 * @return The first iterator @c i in the range
5052 * @p [first1,last1) such that @c comp(*i, @p *(i2)) is true and i2 is an
5053 * interator in [first2,last2), or @p last1 if no such iterator exists.
5054 *
5055 * Searches the range @p [first1,last1) for an element that is equal to
5056 * some element in the range [first2,last2). If found, returns an iterator in
5057 * the range [first1,last1), otherwise returns @p last1.
5058 */
5060 typename _BinaryPredicate>
5061 _InputIterator
5064 _BinaryPredicate __comp)
5065 {
5066 // concept requirements
5080 }
5083 // find_end, with and without an explicitly supplied comparison function.
5084 // Search [first2, last2) as a subsequence in [first1, last1), and return
5085 // the *last* possible match. Note that find_end for bidirectional iterators
5086 // is much faster than for forward iterators.
5088 // find_end for forward iterators.
5090 _ForwardIterator1
5094 {
5097 else
5098 {
5101 {
5102 _ForwardIterator1 __new_result
5106 else
5107 {
5111 }
5112 }
5113 }
5114 }
5117 typename _BinaryPredicate>
5118 _ForwardIterator1
5122 _BinaryPredicate __comp)
5123 {
5126 else
5127 {
5130 {
5131 _ForwardIterator1 __new_result
5135 else
5136 {
5140 }
5141 }
5142 }
5143 }
5145 // find_end for bidirectional iterators. Requires partial specialization.
5147 _BidirectionalIterator1
5149 _BidirectionalIterator1 __last1,
5150 _BidirectionalIterator2 __first2,
5151 _BidirectionalIterator2 __last2,
5153 {
5154 // concept requirements
5156 _BidirectionalIterator1>)
5158 _BidirectionalIterator2>)
5170 else
5171 {
5175 }
5176 }
5179 typename _BinaryPredicate>
5180 _BidirectionalIterator1
5182 _BidirectionalIterator1 __last1,
5183 _BidirectionalIterator2 __first2,
5184 _BidirectionalIterator2 __last2,
5186 _BinaryPredicate __comp)
5187 {
5188 // concept requirements
5190 _BidirectionalIterator1>)
5192 _BidirectionalIterator2>)
5201 __comp);
5205 else
5206 {
5210 }
5211 }
5213 // Dispatching functions for find_end.
5215 /**
5216 * @brief Find last matching subsequence in a sequence.
5217 * @param first1 Start of range to search.
5218 * @param last1 End of range to search.
5219 * @param first2 Start of sequence to match.
5220 * @param last2 End of sequence to match.
5221 * @return The last iterator @c i in the range
5222 * @p [first1,last1-(last2-first2)) such that @c *(i+N) == @p *(first2+N)
5223 * for each @c N in the range @p [0,last2-first2), or @p last1 if no
5224 * such iterator exists.
5225 *
5226 * Searches the range @p [first1,last1) for a sub-sequence that compares
5227 * equal value-by-value with the sequence given by @p [first2,last2) and
5228 * returns an iterator to the first element of the sub-sequence, or
5229 * @p last1 if the sub-sequence is not found. The sub-sequence will be the
5230 * last such subsequence contained in [first,last1).
5231 *
5232 * Because the sub-sequence must lie completely within the range
5233 * @p [first1,last1) it must start at a position less than
5234 * @p last1-(last2-first2) where @p last2-first2 is the length of the
5235 * sub-sequence.
5236 * This means that the returned iterator @c i will be in the range
5237 * @p [first1,last1-(last2-first2))
5238 */
5240 inline _ForwardIterator1
5243 {
5244 // concept requirements
5256 }
5258 /**
5259 * @brief Find last matching subsequence in a sequence using a predicate.
5260 * @param first1 Start of range to search.
5261 * @param last1 End of range to search.
5262 * @param first2 Start of sequence to match.
5263 * @param last2 End of sequence to match.
5264 * @param comp The predicate to use.
5265 * @return The last iterator @c i in the range
5266 * @p [first1,last1-(last2-first2)) such that @c predicate(*(i+N), @p
5267 * (first2+N)) is true for each @c N in the range @p [0,last2-first2), or
5268 * @p last1 if no such iterator exists.
5269 *
5270 * Searches the range @p [first1,last1) for a sub-sequence that compares
5271 * equal value-by-value with the sequence given by @p [first2,last2) using
5272 * comp as a predicate and returns an iterator to the first element of the
5273 * sub-sequence, or @p last1 if the sub-sequence is not found. The
5274 * sub-sequence will be the last such subsequence contained in
5275 * [first,last1).
5276 *
5277 * Because the sub-sequence must lie completely within the range
5278 * @p [first1,last1) it must start at a position less than
5279 * @p last1-(last2-first2) where @p last2-first2 is the length of the
5280 * sub-sequence.
5281 * This means that the returned iterator @c i will be in the range
5282 * @p [first1,last1-(last2-first2))
5283 */
5285 typename _BinaryPredicate>
5286 inline _ForwardIterator1
5289 _BinaryPredicate __comp)
5290 {
5291 // concept requirements
5303 __comp);
5304 }