| blob | d5c8f9ddde67a3bf77d5d65ebc986112f5f32bae |
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 * @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 forward iterators and output iterator as result.
1299 * @endif
1300 */
1302 _OutputIterator
1304 _OutputIterator __result,
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 input iterators and output iterator as result.
1324 * @endif
1325 */
1327 _OutputIterator
1329 _OutputIterator __result,
1331 {
1332 // concept requirements -- taken care of in dispatching function
1335 {
1336 typename
1344 }
1346 }
1348 /**
1349 * @if maint
1350 * This is an uglified unique_copy(_InputIterator, _InputIterator,
1351 * _OutputIterator)
1352 * overloaded for input iterators and forward iterator as result.
1353 * @endif
1354 */
1356 _ForwardIterator
1358 _ForwardIterator __result,
1360 {
1361 // concept requirements -- taken care of in dispatching function
1367 }
1369 /**
1370 * @if maint
1371 * This is an uglified
1372 * unique_copy(_InputIterator, _InputIterator, _OutputIterator,
1373 * _BinaryPredicate)
1374 * overloaded for forward iterators and output iterator as result.
1375 * @endif
1376 */
1378 typename _BinaryPredicate>
1379 _OutputIterator
1383 {
1384 // concept requirements -- iterators already checked
1393 {
1396 }
1398 }
1400 /**
1401 * @if maint
1402 * This is an uglified
1403 * unique_copy(_InputIterator, _InputIterator, _OutputIterator,
1404 * _BinaryPredicate)
1405 * overloaded for input iterators and output iterator as result.
1406 * @endif
1407 */
1409 typename _BinaryPredicate>
1410 _OutputIterator
1414 {
1415 // concept requirements -- iterators already checked
1422 {
1423 typename
1431 }
1433 }
1435 /**
1436 * @if maint
1437 * This is an uglified
1438 * unique_copy(_InputIterator, _InputIterator, _OutputIterator,
1439 * _BinaryPredicate)
1440 * overloaded for input iterators and forward iterator as result.
1441 * @endif
1442 */
1444 typename _BinaryPredicate>
1445 _ForwardIterator
1449 {
1450 // concept requirements -- iterators already checked
1460 }
1462 /**
1463 * @brief Copy a sequence, removing consecutive duplicate values.
1464 * @param first An input iterator.
1465 * @param last An input iterator.
1466 * @param result An output iterator.
1467 * @return An iterator designating the end of the resulting sequence.
1468 *
1469 * Copies each element in the range @p [first,last) to the range
1470 * beginning at @p result, except that only the first element is copied
1471 * from groups of consecutive elements that compare equal.
1472 * unique_copy() is stable, so the relative order of elements that are
1473 * copied is unchanged.
1474 *
1475 * @if maint
1476 * _GLIBCXX_RESOLVE_LIB_DEFECTS
1477 * DR 241. Does unique_copy() require CopyConstructible and Assignable?
1478 * @endif
1479 */
1481 inline _OutputIterator
1483 _OutputIterator __result)
1484 {
1485 // concept requirements
1498 }
1500 /**
1501 * @brief Copy a sequence, removing consecutive values using a predicate.
1502 * @param first An input iterator.
1503 * @param last An input iterator.
1504 * @param result An output iterator.
1505 * @param binary_pred A binary predicate.
1506 * @return An iterator designating the end of the resulting sequence.
1507 *
1508 * Copies each element in the range @p [first,last) to the range
1509 * beginning at @p result, except that only the first element is copied
1510 * from groups of consecutive elements for which @p binary_pred returns
1511 * true.
1512 * unique_copy() is stable, so the relative order of elements that are
1513 * copied is unchanged.
1514 *
1515 * @if maint
1516 * _GLIBCXX_RESOLVE_LIB_DEFECTS
1517 * DR 241. Does unique_copy() require CopyConstructible and Assignable?
1518 * @endif
1519 */
1521 typename _BinaryPredicate>
1522 inline _OutputIterator
1524 _OutputIterator __result,
1525 _BinaryPredicate __binary_pred)
1526 {
1527 // concept requirements -- predicates checked later
1538 }
1540 /**
1541 * @brief Remove consecutive duplicate values from a sequence.
1542 * @param first A forward iterator.
1543 * @param last A forward iterator.
1544 * @return An iterator designating the end of the resulting sequence.
1545 *
1546 * Removes all but the first element from each group of consecutive
1547 * values that compare equal.
1548 * unique() is stable, so the relative order of elements that are
1549 * not removed is unchanged.
1550 * Elements between the end of the resulting sequence and @p last
1551 * are still present, but their value is unspecified.
1552 */
1554 _ForwardIterator
1556 {
1557 // concept requirements
1559 _ForwardIterator>)
1564 // Skip the beginning, if already unique.
1569 // Do the real copy work.
1576 }
1578 /**
1579 * @brief Remove consecutive values from a sequence using a predicate.
1580 * @param first A forward iterator.
1581 * @param last A forward iterator.
1582 * @param binary_pred A binary predicate.
1583 * @return An iterator designating the end of the resulting sequence.
1584 *
1585 * Removes all but the first element from each group of consecutive
1586 * values for which @p binary_pred returns true.
1587 * unique() is stable, so the relative order of elements that are
1588 * not removed is unchanged.
1589 * Elements between the end of the resulting sequence and @p last
1590 * are still present, but their value is unspecified.
1591 */
1593 _ForwardIterator
1595 _BinaryPredicate __binary_pred)
1596 {
1597 // concept requirements
1599 _ForwardIterator>)
1605 // Skip the beginning, if already unique.
1610 // Do the real copy work.
1617 }
1619 /**
1620 * @if maint
1621 * This is an uglified reverse(_BidirectionalIterator,
1622 * _BidirectionalIterator)
1623 * overloaded for bidirectional iterators.
1624 * @endif
1625 */
1627 void
1629 bidirectional_iterator_tag)
1630 {
1634 else
1635 {
1638 }
1639 }
1641 /**
1642 * @if maint
1643 * This is an uglified reverse(_BidirectionalIterator,
1644 * _BidirectionalIterator)
1645 * overloaded for random access iterators.
1646 * @endif
1647 */
1649 void
1651 random_access_iterator_tag)
1652 {
1657 {
1661 }
1662 }
1664 /**
1665 * @brief Reverse a sequence.
1666 * @param first A bidirectional iterator.
1667 * @param last A bidirectional iterator.
1668 * @return reverse() returns no value.
1669 *
1670 * Reverses the order of the elements in the range @p [first,last),
1671 * so that the first element becomes the last etc.
1672 * For every @c i such that @p 0<=i<=(last-first)/2), @p reverse()
1673 * swaps @p *(first+i) and @p *(last-(i+1))
1674 */
1678 {
1679 // concept requirements
1681 _BidirectionalIterator>)
1684 }
1686 /**
1687 * @brief Copy a sequence, reversing its elements.
1688 * @param first A bidirectional iterator.
1689 * @param last A bidirectional iterator.
1690 * @param result An output iterator.
1691 * @return An iterator designating the end of the resulting sequence.
1692 *
1693 * Copies the elements in the range @p [first,last) to the range
1694 * @p [result,result+(last-first)) such that the order of the
1695 * elements is reversed.
1696 * For every @c i such that @p 0<=i<=(last-first), @p reverse_copy()
1697 * performs the assignment @p *(result+(last-first)-i) = *(first+i).
1698 * The ranges @p [first,last) and @p [result,result+(last-first))
1699 * must not overlap.
1700 */
1702 _OutputIterator
1704 _OutputIterator __result)
1705 {
1706 // concept requirements
1708 _BidirectionalIterator>)
1714 {
1718 }
1720 }
1723 /**
1724 * @if maint
1725 * This is a helper function for the rotate algorithm specialized on RAIs.
1726 * It returns the greatest common divisor of two integer values.
1727 * @endif
1728 */
1730 _EuclideanRingElement
1732 {
1734 {
1738 }
1740 }
1742 /**
1743 * @if maint
1744 * This is a helper function for the rotate algorithm.
1745 * @endif
1746 */
1748 void
1750 _ForwardIterator __middle,
1751 _ForwardIterator __last,
1752 forward_iterator_tag)
1753 {
1758 do
1759 {
1765 }
1771 {
1779 }
1780 }
1782 /**
1783 * @if maint
1784 * This is a helper function for the rotate algorithm.
1785 * @endif
1786 */
1788 void
1790 _BidirectionalIterator __middle,
1791 _BidirectionalIterator __last,
1792 bidirectional_iterator_tag)
1793 {
1794 // concept requirements
1796 _BidirectionalIterator>)
1805 {
1808 }
1812 else
1814 }
1816 /**
1817 * @if maint
1818 * This is a helper function for the rotate algorithm.
1819 * @endif
1820 */
1822 void
1824 _RandomAccessIterator __middle,
1825 _RandomAccessIterator __last,
1826 random_access_iterator_tag)
1827 {
1828 // concept requirements
1830 _RandomAccessIterator>)
1836 _Distance;
1838 _ValueType;
1845 {
1848 }
1853 {
1858 {
1860 {
1862 {
1865 }
1869 }
1870 }
1871 else
1872 {
1874 {
1876 {
1879 }
1882 }
1883 }
1887 }
1888 }
1890 /**
1891 * @brief Rotate the elements of a sequence.
1892 * @param first A forward iterator.
1893 * @param middle A forward iterator.
1894 * @param last A forward iterator.
1895 * @return Nothing.
1896 *
1897 * Rotates the elements of the range @p [first,last) by @p (middle-first)
1898 * positions so that the element at @p middle is moved to @p first, the
1899 * element at @p middle+1 is moved to @first+1 and so on for each element
1900 * in the range @p [first,last).
1901 *
1902 * This effectively swaps the ranges @p [first,middle) and
1903 * @p [middle,last).
1904 *
1905 * Performs @p *(first+(n+(last-middle))%(last-first))=*(first+n) for
1906 * each @p n in the range @p [0,last-first).
1907 */
1911 _ForwardIterator __last)
1912 {
1913 // concept requirements
1915 _ForwardIterator>)
1920 _IterType;
1922 }
1924 /**
1925 * @brief Copy a sequence, rotating its elements.
1926 * @param first A forward iterator.
1927 * @param middle A forward iterator.
1928 * @param last A forward iterator.
1929 * @param result An output iterator.
1930 * @return An iterator designating the end of the resulting sequence.
1931 *
1932 * Copies the elements of the range @p [first,last) to the range
1933 * beginning at @result, rotating the copied elements by @p (middle-first)
1934 * positions so that the element at @p middle is moved to @p result, the
1935 * element at @p middle+1 is moved to @result+1 and so on for each element
1936 * in the range @p [first,last).
1937 *
1938 * Performs @p *(result+(n+(last-middle))%(last-first))=*(first+n) for
1939 * each @p n in the range @p [0,last-first).
1940 */
1942 _OutputIterator
1945 {
1946 // concept requirements
1955 }
1957 /**
1958 * @brief Randomly shuffle the elements of a sequence.
1959 * @param first A forward iterator.
1960 * @param last A forward iterator.
1961 * @return Nothing.
1962 *
1963 * Reorder the elements in the range @p [first,last) using a random
1964 * distribution, so that every possible ordering of the sequence is
1965 * equally likely.
1966 */
1970 {
1971 // concept requirements
1973 _RandomAccessIterator>)
1979 }
1981 /**
1982 * @brief Shuffle the elements of a sequence using a random number
1983 * generator.
1984 * @param first A forward iterator.
1985 * @param last A forward iterator.
1986 * @param rand The RNG functor or function.
1987 * @return Nothing.
1988 *
1989 * Reorders the elements in the range @p [first,last) using @p rand to
1990 * provide a random distribution. Calling @p rand(N) for a positive
1991 * integer @p N should return a randomly chosen integer from the
1992 * range [0,N).
1993 */
1995 void
1998 {
1999 // concept requirements
2001 _RandomAccessIterator>)
2008 }
2011 /**
2012 * @if maint
2013 * This is a helper function...
2014 * @endif
2015 */
2017 _ForwardIterator
2019 _Predicate __pred,
2020 forward_iterator_tag)
2021 {
2033 {
2036 }
2039 }
2041 /**
2042 * @if maint
2043 * This is a helper function...
2044 * @endif
2045 */
2047 _BidirectionalIterator
2049 _Predicate __pred,
2050 bidirectional_iterator_tag)
2051 {
2053 {
2059 else
2067 else
2071 }
2072 }
2074 /**
2075 * @brief Move elements for which a predicate is true to the beginning
2076 * of a sequence.
2077 * @param first A forward iterator.
2078 * @param last A forward iterator.
2079 * @param pred A predicate functor.
2080 * @return An iterator @p middle such that @p pred(i) is true for each
2081 * iterator @p i in the range @p [first,middle) and false for each @p i
2082 * in the range @p [middle,last).
2083 *
2084 * @p pred must not modify its operand. @p partition() does not preserve
2085 * the relative ordering of elements in each group, use
2086 * @p stable_partition() if this is needed.
2087 */
2089 inline _ForwardIterator
2091 _Predicate __pred)
2092 {
2093 // concept requirements
2095 _ForwardIterator>)
2102 }
2105 /**
2106 * @if maint
2107 * This is a helper function...
2108 * @endif
2109 */
2111 _ForwardIterator
2113 _ForwardIterator __last,
2115 {
2121 __middle,
2122 __pred,
2125 __pred,
2126 __len
2131 }
2133 /**
2134 * @if maint
2135 * This is a helper function...
2136 * @endif
2137 */
2139 typename _Distance>
2140 _ForwardIterator
2142 _ForwardIterator __last,
2144 _Pointer __buffer,
2145 _Distance __buffer_size)
2146 {
2148 {
2153 {
2156 }
2157 else
2158 {
2161 }
2164 }
2165 else
2166 {
2169 _ForwardIterator __begin =
2172 __buffer_size);
2173 _ForwardIterator __end =
2180 }
2181 }
2183 /**
2184 * @brief Move elements for which a predicate is true to the beginning
2185 * of a sequence, preserving relative ordering.
2186 * @param first A forward iterator.
2187 * @param last A forward iterator.
2188 * @param pred A predicate functor.
2189 * @return An iterator @p middle such that @p pred(i) is true for each
2190 * iterator @p i in the range @p [first,middle) and false for each @p i
2191 * in the range @p [middle,last).
2192 *
2193 * Performs the same function as @p partition() with the additional
2194 * guarantee that the relative ordering of elements in each group is
2195 * preserved, so any two elements @p x and @p y in the range
2196 * @p [first,last) such that @p pred(x)==pred(y) will have the same
2197 * relative ordering after calling @p stable_partition().
2198 */
2200 _ForwardIterator
2202 _Predicate __pred)
2203 {
2204 // concept requirements
2206 _ForwardIterator>)
2213 else
2214 {
2216 _ValueType;
2218 _DistanceType;
2221 __last);
2223 return
2227 else
2228 return
2231 }
2232 }
2234 /**
2235 * @if maint
2236 * This is a helper function...
2237 * @endif
2238 */
2240 _RandomAccessIterator
2243 {
2245 {
2255 }
2256 }
2258 /**
2259 * @if maint
2260 * This is a helper function...
2261 * @endif
2262 */
2264 _RandomAccessIterator
2266 _RandomAccessIterator __last,
2268 {
2270 {
2280 }
2281 }
2283 /**
2284 * @if maint
2285 * @doctodo
2286 * This controls some aspect of the sort routines.
2287 * @endif
2288 */
2291 /**
2292 * @if maint
2293 * This is a helper function for the sort routine.
2294 * @endif
2295 */
2297 void
2299 {
2303 {
2307 }
2309 }
2311 /**
2312 * @if maint
2313 * This is a helper function for the sort routine.
2314 * @endif
2315 */
2317 void
2319 _Compare __comp)
2320 {
2324 {
2328 }
2330 }
2332 /**
2333 * @if maint
2334 * This is a helper function for the sort routine.
2335 * @endif
2336 */
2338 void
2340 _RandomAccessIterator __last)
2341 {
2346 {
2350 {
2353 }
2354 else
2356 }
2357 }
2359 /**
2360 * @if maint
2361 * This is a helper function for the sort routine.
2362 * @endif
2363 */
2365 void
2368 {
2372 {
2376 {
2379 }
2380 else
2382 }
2383 }
2385 /**
2386 * @if maint
2387 * This is a helper function for the sort routine.
2388 * @endif
2389 */
2393 _RandomAccessIterator __last)
2394 {
2396 _ValueType;
2400 }
2402 /**
2403 * @if maint
2404 * This is a helper function for the sort routine.
2405 * @endif
2406 */
2411 {
2413 _ValueType;
2417 }
2419 /**
2420 * @if maint
2421 * This is a helper function for the sort routine.
2422 * @endif
2423 */
2425 void
2427 _RandomAccessIterator __last)
2428 {
2430 {
2433 }
2434 else
2436 }
2438 /**
2439 * @if maint
2440 * This is a helper function for the sort routine.
2441 * @endif
2442 */
2444 void
2447 {
2449 {
2452 __comp);
2453 }
2454 else
2456 }
2458 /**
2459 * @if maint
2460 * This is a helper function for the sort routine.
2461 * @endif
2462 */
2464 inline _Size
2466 {
2467 _Size __k;
2471 }
2473 /**
2474 * @brief Sort the smallest elements of a sequence.
2475 * @param first An iterator.
2476 * @param middle Another iterator.
2477 * @param last Another iterator.
2478 * @return Nothing.
2479 *
2480 * Sorts the smallest @p (middle-first) elements in the range
2481 * @p [first,last) and moves them to the range @p [first,middle). The
2482 * order of the remaining elements in the range @p [middle,last) is
2483 * undefined.
2484 * After the sort if @p i and @j are iterators in the range
2485 * @p [first,middle) such that @i precedes @j and @k is an iterator in
2486 * the range @p [middle,last) then @p *j<*i and @p *k<*i are both false.
2487 */
2489 void
2491 _RandomAccessIterator __middle,
2492 _RandomAccessIterator __last)
2493 {
2495 _ValueType;
2497 // concept requirements
2499 _RandomAccessIterator>)
2509 }
2511 /**
2512 * @brief Sort the smallest elements of a sequence using a predicate
2513 * for comparison.
2514 * @param first An iterator.
2515 * @param middle Another iterator.
2516 * @param last Another iterator.
2517 * @param comp A comparison functor.
2518 * @return Nothing.
2519 *
2520 * Sorts the smallest @p (middle-first) elements in the range
2521 * @p [first,last) and moves them to the range @p [first,middle). The
2522 * order of the remaining elements in the range @p [middle,last) is
2523 * undefined.
2524 * After the sort if @p i and @j are iterators in the range
2525 * @p [first,middle) such that @i precedes @j and @k is an iterator in
2526 * the range @p [middle,last) then @p *comp(j,*i) and @p comp(*k,*i)
2527 * are both false.
2528 */
2530 void
2532 _RandomAccessIterator __middle,
2533 _RandomAccessIterator __last,
2534 _Compare __comp)
2535 {
2537 _ValueType;
2539 // concept requirements
2541 _RandomAccessIterator>)
2552 }
2554 /**
2555 * @brief Copy the smallest elements of a sequence.
2556 * @param first An iterator.
2557 * @param last Another iterator.
2558 * @param result_first A random-access iterator.
2559 * @param result_last Another random-access iterator.
2560 * @return An iterator indicating the end of the resulting sequence.
2561 *
2562 * Copies and sorts the smallest N values from the range @p [first,last)
2563 * to the range beginning at @p result_first, where the number of
2564 * elements to be copied, @p N, is the smaller of @p (last-first) and
2565 * @p (result_last-result_first).
2566 * After the sort if @p i and @j are iterators in the range
2567 * @p [result_first,result_first+N) such that @i precedes @j then
2568 * @p *j<*i is false.
2569 * The value returned is @p result_first+N.
2570 */
2572 _RandomAccessIterator
2574 _RandomAccessIterator __result_first,
2575 _RandomAccessIterator __result_last)
2576 {
2578 _InputValueType;
2580 _OutputValueType;
2582 _DistanceType;
2584 // concept requirements
2587 _OutputValueType>)
2589 _OutputValueType>)
2598 {
2602 }
2605 {
2612 }
2615 }
2617 /**
2618 * @brief Copy the smallest elements of a sequence using a predicate for
2619 * comparison.
2620 * @param first An input iterator.
2621 * @param last Another input iterator.
2622 * @param result_first A random-access iterator.
2623 * @param result_last Another random-access iterator.
2624 * @param comp A comparison functor.
2625 * @return An iterator indicating the end of the resulting sequence.
2626 *
2627 * Copies and sorts the smallest N values from the range @p [first,last)
2628 * to the range beginning at @p result_first, where the number of
2629 * elements to be copied, @p N, is the smaller of @p (last-first) and
2630 * @p (result_last-result_first).
2631 * After the sort if @p i and @j are iterators in the range
2632 * @p [result_first,result_first+N) such that @i precedes @j then
2633 * @p comp(*j,*i) is false.
2634 * The value returned is @p result_first+N.
2635 */
2637 _RandomAccessIterator
2639 _RandomAccessIterator __result_first,
2640 _RandomAccessIterator __result_last,
2641 _Compare __comp)
2642 {
2644 _InputValueType;
2646 _OutputValueType;
2648 _DistanceType;
2650 // concept requirements
2653 _RandomAccessIterator>)
2655 _OutputValueType>)
2667 {
2671 }
2674 {
2680 __comp);
2682 }
2685 }
2687 /**
2688 * @if maint
2689 * This is a helper function for the sort routine.
2690 * @endif
2691 */
2693 void
2695 _RandomAccessIterator __last,
2696 _Size __depth_limit)
2697 {
2699 _ValueType;
2702 {
2704 {
2707 }
2709 _RandomAccessIterator __cut =
2712 *(__first
2713 + (__last
2716 *(__last
2720 }
2721 }
2723 /**
2724 * @if maint
2725 * This is a helper function for the sort routine.
2726 * @endif
2727 */
2729 void
2731 _RandomAccessIterator __last,
2733 {
2735 _ValueType;
2738 {
2740 {
2743 }
2745 _RandomAccessIterator __cut =
2748 *(__first
2749 + (__last
2753 __comp)),
2754 __comp);
2757 }
2758 }
2760 /**
2761 * @brief Sort the elements of a sequence.
2762 * @param first An iterator.
2763 * @param last Another iterator.
2764 * @return Nothing.
2765 *
2766 * Sorts the elements in the range @p [first,last) in ascending order,
2767 * such that @p *(i+1)<*i is false for each iterator @p i in the range
2768 * @p [first,last-1).
2769 *
2770 * The relative ordering of equivalent elements is not preserved, use
2771 * @p stable_sort() if this is needed.
2772 */
2776 {
2778 _ValueType;
2780 // concept requirements
2782 _RandomAccessIterator>)
2787 {
2790 }
2791 }
2793 /**
2794 * @brief Sort the elements of a sequence using a predicate for comparison.
2795 * @param first An iterator.
2796 * @param last Another iterator.
2797 * @param comp A comparison functor.
2798 * @return Nothing.
2799 *
2800 * Sorts the elements in the range @p [first,last) in ascending order,
2801 * such that @p comp(*(i+1),*i) is false for every iterator @p i in the
2802 * range @p [first,last-1).
2803 *
2804 * The relative ordering of equivalent elements is not preserved, use
2805 * @p stable_sort() if this is needed.
2806 */
2810 _Compare __comp)
2811 {
2813 _ValueType;
2815 // concept requirements
2817 _RandomAccessIterator>)
2819 _ValueType>)
2823 {
2825 __comp);
2827 }
2828 }
2830 /**
2831 * @brief Finds the first position in which @a val could be inserted
2832 * without changing the ordering.
2833 * @param first An iterator.
2834 * @param last Another iterator.
2835 * @param val The search term.
2836 * @return An iterator pointing to the first element "not less than" @a val,
2837 * or end() if every element is less than @a val.
2838 * @ingroup binarysearch
2839 */
2841 _ForwardIterator
2844 {
2846 _ValueType;
2848 _DistanceType;
2850 // concept requirements
2856 _DistanceType __half;
2857 _ForwardIterator __middle;
2860 {
2865 {
2869 }
2870 else
2872 }
2874 }
2876 /**
2877 * @brief Finds the first position in which @a val could be inserted
2878 * without changing the ordering.
2879 * @param first An iterator.
2880 * @param last Another iterator.
2881 * @param val The search term.
2882 * @param comp A functor to use for comparisons.
2883 * @return An iterator pointing to the first element "not less than" @a val,
2884 * or end() if every element is less than @a val.
2885 * @ingroup binarysearch
2886 *
2887 * The comparison function should have the same effects on ordering as
2888 * the function used for the initial sort.
2889 */
2891 _ForwardIterator
2894 {
2896 _ValueType;
2898 _DistanceType;
2900 // concept requirements
2907 _DistanceType __half;
2908 _ForwardIterator __middle;
2911 {
2916 {
2920 }
2921 else
2923 }
2925 }
2927 /**
2928 * @brief Finds the last position in which @a val could be inserted
2929 * without changing the ordering.
2930 * @param first An iterator.
2931 * @param last Another iterator.
2932 * @param val The search term.
2933 * @return An iterator pointing to the first element greater than @a val,
2934 * or end() if no elements are greater than @a val.
2935 * @ingroup binarysearch
2936 */
2938 _ForwardIterator
2941 {
2943 _ValueType;
2945 _DistanceType;
2947 // concept requirements
2953 _DistanceType __half;
2954 _ForwardIterator __middle;
2957 {
2963 else
2964 {
2968 }
2969 }
2971 }
2973 /**
2974 * @brief Finds the last position in which @a val could be inserted
2975 * without changing the ordering.
2976 * @param first An iterator.
2977 * @param last Another iterator.
2978 * @param val The search term.
2979 * @param comp A functor to use for comparisons.
2980 * @return An iterator pointing to the first element greater than @a val,
2981 * or end() if no elements are greater than @a val.
2982 * @ingroup binarysearch
2983 *
2984 * The comparison function should have the same effects on ordering as
2985 * the function used for the initial sort.
2986 */
2988 _ForwardIterator
2991 {
2993 _ValueType;
2995 _DistanceType;
2997 // concept requirements
3004 _DistanceType __half;
3005 _ForwardIterator __middle;
3008 {
3014 else
3015 {
3019 }
3020 }
3022 }
3024 /**
3025 * @if maint
3026 * This is a helper function for the merge routines.
3027 * @endif
3028 */
3030 void
3032 _BidirectionalIterator __middle,
3033 _BidirectionalIterator __last,
3035 {
3039 {
3043 }
3049 {
3054 }
3055 else
3056 {
3061 }
3069 }
3071 /**
3072 * @if maint
3073 * This is a helper function for the merge routines.
3074 * @endif
3075 */
3077 typename _Compare>
3078 void
3080 _BidirectionalIterator __middle,
3081 _BidirectionalIterator __last,
3083 _Compare __comp)
3084 {
3088 {
3092 }
3098 {
3102 __comp);
3104 }
3105 else
3106 {
3110 __comp);
3112 }
3120 }
3122 /**
3123 * @if maint
3124 * This is a helper function for the stable sorting routines.
3125 * @endif
3126 */
3128 void
3130 _RandomAccessIterator __last)
3131 {
3133 {
3136 }
3143 }
3145 /**
3146 * @if maint
3147 * This is a helper function for the stable sorting routines.
3148 * @endif
3149 */
3151 void
3154 {
3156 {
3159 }
3166 __comp);
3167 }
3169 /**
3170 * @brief Merges two sorted ranges.
3171 * @param first1 An iterator.
3172 * @param first2 Another iterator.
3173 * @param last1 Another iterator.
3174 * @param last2 Another iterator.
3175 * @param result An iterator pointing to the end of the merged range.
3176 * @return An iterator pointing to the first element "not less than" @a val.
3177 *
3178 * Merges the ranges [first1,last1) and [first2,last2) into the sorted range
3179 * [result, result + (last1-first1) + (last2-first2)). Both input ranges
3180 * must be sorted, and the output range must not overlap with either of
3181 * the input ranges. The sort is @e stable, that is, for equivalent
3182 * elements in the two ranges, elements from the first range will always
3183 * come before elements from the second.
3184 */
3186 typename _OutputIterator>
3187 _OutputIterator
3190 _OutputIterator __result)
3191 {
3193 _ValueType1;
3195 _ValueType2;
3197 // concept requirements
3201 _ValueType1>)
3203 _ValueType2>)
3209 {
3211 {
3214 }
3215 else
3216 {
3219 }
3221 }
3223 __result));
3224 }
3226 /**
3227 * @brief Merges two sorted ranges.
3228 * @param first1 An iterator.
3229 * @param first2 Another iterator.
3230 * @param last1 Another iterator.
3231 * @param last2 Another iterator.
3232 * @param result An iterator pointing to the end of the merged range.
3233 * @param comp A functor to use for comparisons.
3234 * @return An iterator pointing to the first element "not less than" @a val.
3235 *
3236 * Merges the ranges [first1,last1) and [first2,last2) into the sorted range
3237 * [result, result + (last1-first1) + (last2-first2)). Both input ranges
3238 * must be sorted, and the output range must not overlap with either of
3239 * the input ranges. The sort is @e stable, that is, for equivalent
3240 * elements in the two ranges, elements from the first range will always
3241 * come before elements from the second.
3242 *
3243 * The comparison function should have the same effects on ordering as
3244 * the function used for the initial sort.
3245 */
3248 _OutputIterator
3252 {
3254 _ValueType1;
3256 _ValueType2;
3258 // concept requirements
3262 _ValueType1>)
3264 _ValueType2>)
3271 {
3273 {
3276 }
3277 else
3278 {
3281 }
3283 }
3285 __result));
3286 }
3289 typename _Distance>
3290 void
3292 _RandomAccessIterator1 __last,
3293 _RandomAccessIterator2 __result,
3294 _Distance __step_size)
3295 {
3299 {
3302 __result);
3304 }
3308 __result);
3309 }
3313 void
3315 _RandomAccessIterator1 __last,
3317 _Compare __comp)
3318 {
3322 {
3325 __result,
3326 __comp);
3328 }
3333 __result,
3334 __comp);
3335 }
3340 void
3342 _RandomAccessIterator __last,
3343 _Distance __chunk_size)
3344 {
3346 {
3349 }
3351 }
3354 void
3356 _RandomAccessIterator __last,
3358 {
3360 {
3363 }
3365 }
3368 void
3370 _RandomAccessIterator __last,
3371 _Pointer __buffer)
3372 {
3374 _Distance;
3383 {
3388 }
3389 }
3392 void
3394 _RandomAccessIterator __last,
3396 {
3398 _Distance;
3407 {
3414 }
3415 }
3417 /**
3418 * @if maint
3419 * This is a helper function for the merge routines.
3420 * @endif
3421 */
3423 typename _BidirectionalIterator3>
3424 _BidirectionalIterator3
3426 _BidirectionalIterator1 __last1,
3427 _BidirectionalIterator2 __first2,
3428 _BidirectionalIterator2 __last2,
3429 _BidirectionalIterator3 __result)
3430 {
3438 {
3440 {
3445 }
3446 else
3447 {
3452 }
3453 }
3454 }
3456 /**
3457 * @if maint
3458 * This is a helper function for the merge routines.
3459 * @endif
3460 */
3463 _BidirectionalIterator3
3465 _BidirectionalIterator1 __last1,
3466 _BidirectionalIterator2 __first2,
3467 _BidirectionalIterator2 __last2,
3468 _BidirectionalIterator3 __result,
3469 _Compare __comp)
3470 {
3478 {
3480 {
3485 }
3486 else
3487 {
3492 }
3493 }
3494 }
3496 /**
3497 * @if maint
3498 * This is a helper function for the merge routines.
3499 * @endif
3500 */
3502 typename _Distance>
3503 _BidirectionalIterator1
3505 _BidirectionalIterator1 __middle,
3506 _BidirectionalIterator1 __last,
3508 _BidirectionalIterator2 __buffer,
3509 _Distance __buffer_size)
3510 {
3511 _BidirectionalIterator2 __buffer_end;
3513 {
3517 }
3519 {
3523 }
3524 else
3525 {
3529 }
3530 }
3532 /**
3533 * @if maint
3534 * This is a helper function for the merge routines.
3535 * @endif
3536 */
3538 typename _Pointer>
3539 void
3541 _BidirectionalIterator __middle,
3542 _BidirectionalIterator __last,
3545 {
3547 {
3550 }
3552 {
3556 }
3557 else
3558 {
3564 {
3570 }
3571 else
3572 {
3578 }
3579 _BidirectionalIterator __new_middle =
3582 __buffer_size);
3588 }
3589 }
3591 /**
3592 * @if maint
3593 * This is a helper function for the merge routines.
3594 * @endif
3595 */
3597 typename _Compare>
3598 void
3600 _BidirectionalIterator __middle,
3601 _BidirectionalIterator __last,
3604 _Compare __comp)
3605 {
3607 {
3610 }
3612 {
3616 }
3617 else
3618 {
3624 {
3628 __comp);
3630 }
3631 else
3632 {
3636 __comp);
3638 }
3639 _BidirectionalIterator __new_middle =
3642 __buffer_size);
3649 }
3650 }
3652 /**
3653 * @brief Merges two sorted ranges in place.
3654 * @param first An iterator.
3655 * @param middle Another iterator.
3656 * @param last Another iterator.
3657 * @return Nothing.
3658 *
3659 * Merges two sorted and consecutive ranges, [first,middle) and
3660 * [middle,last), and puts the result in [first,last). The output will
3661 * be sorted. The sort is @e stable, that is, for equivalent
3662 * elements in the two ranges, elements from the first range will always
3663 * come before elements from the second.
3664 *
3665 * If enough additional memory is available, this takes (last-first)-1
3666 * comparisons. Otherwise an NlogN algorithm is used, where N is
3667 * distance(first,last).
3668 */
3670 void
3672 _BidirectionalIterator __middle,
3673 _BidirectionalIterator __last)
3674 {
3676 _ValueType;
3678 _DistanceType;
3680 // concept requirements
3682 _BidirectionalIterator>)
3694 __last);
3697 else
3700 }
3702 /**
3703 * @brief Merges two sorted ranges in place.
3704 * @param first An iterator.
3705 * @param middle Another iterator.
3706 * @param last Another iterator.
3707 * @param comp A functor to use for comparisons.
3708 * @return Nothing.
3709 *
3710 * Merges two sorted and consecutive ranges, [first,middle) and
3711 * [middle,last), and puts the result in [first,last). The output will
3712 * be sorted. The sort is @e stable, that is, for equivalent
3713 * elements in the two ranges, elements from the first range will always
3714 * come before elements from the second.
3715 *
3716 * If enough additional memory is available, this takes (last-first)-1
3717 * comparisons. Otherwise an NlogN algorithm is used, where N is
3718 * distance(first,last).
3719 *
3720 * The comparison function should have the same effects on ordering as
3721 * the function used for the initial sort.
3722 */
3724 void
3726 _BidirectionalIterator __middle,
3727 _BidirectionalIterator __last,
3728 _Compare __comp)
3729 {
3731 _ValueType;
3733 _DistanceType;
3735 // concept requirements
3737 _BidirectionalIterator>)
3750 __last);
3754 else
3757 __comp);
3758 }
3761 typename _Distance>
3762 void
3764 _RandomAccessIterator __last,
3766 {
3770 {
3775 }
3776 else
3777 {
3780 }
3785 }
3789 void
3791 _RandomAccessIterator __last,
3793 _Compare __comp)
3794 {
3798 {
3803 }
3804 else
3805 {
3808 }
3813 __comp);
3814 }
3816 /**
3817 * @brief Sort the elements of a sequence, preserving the relative order
3818 * of equivalent elements.
3819 * @param first An iterator.
3820 * @param last Another iterator.
3821 * @return Nothing.
3822 *
3823 * Sorts the elements in the range @p [first,last) in ascending order,
3824 * such that @p *(i+1)<*i is false for each iterator @p i in the range
3825 * @p [first,last-1).
3826 *
3827 * The relative ordering of equivalent elements is preserved, so any two
3828 * elements @p x and @p y in the range @p [first,last) such that
3829 * @p x<y is false and @p y<x is false will have the same relative
3830 * ordering after calling @p stable_sort().
3831 */
3835 {
3837 _ValueType;
3839 _DistanceType;
3841 // concept requirements
3843 _RandomAccessIterator>)
3851 else
3854 }
3856 /**
3857 * @brief Sort the elements of a sequence using a predicate for comparison,
3858 * preserving the relative order of equivalent elements.
3859 * @param first An iterator.
3860 * @param last Another iterator.
3861 * @param comp A comparison functor.
3862 * @return Nothing.
3863 *
3864 * Sorts the elements in the range @p [first,last) in ascending order,
3865 * such that @p comp(*(i+1),*i) is false for each iterator @p i in the
3866 * range @p [first,last-1).
3867 *
3868 * The relative ordering of equivalent elements is preserved, so any two
3869 * elements @p x and @p y in the range @p [first,last) such that
3870 * @p comp(x,y) is false and @p comp(y,x) is false will have the same
3871 * relative ordering after calling @p stable_sort().
3872 */
3876 _Compare __comp)
3877 {
3879 _ValueType;
3881 _DistanceType;
3883 // concept requirements
3885 _RandomAccessIterator>)
3887 _ValueType,
3888 _ValueType>)
3894 else
3897 }
3899 /**
3900 * @brief Sort a sequence just enough to find a particular position.
3901 * @param first An iterator.
3902 * @param nth Another iterator.
3903 * @param last Another iterator.
3904 * @return Nothing.
3905 *
3906 * Rearranges the elements in the range @p [first,last) so that @p *nth
3907 * is the same element that would have been in that position had the
3908 * whole sequence been sorted.
3909 * whole sequence been sorted. The elements either side of @p *nth are
3910 * not completely sorted, but for any iterator @i in the range
3911 * @p [first,nth) and any iterator @j in the range @p [nth,last) it
3912 * holds that @p *j<*i is false.
3913 */
3915 void
3917 _RandomAccessIterator __nth,
3918 _RandomAccessIterator __last)
3919 {
3921 _ValueType;
3923 // concept requirements
3925 _RandomAccessIterator>)
3931 {
3932 _RandomAccessIterator __cut =
3935 *(__first
3936 + (__last
3939 *(__last
3943 else
3945 }
3947 }
3949 /**
3950 * @brief Sort a sequence just enough to find a particular position
3951 * using a predicate for comparison.
3952 * @param first An iterator.
3953 * @param nth Another iterator.
3954 * @param last Another iterator.
3955 * @param comp A comparison functor.
3956 * @return Nothing.
3957 *
3958 * Rearranges the elements in the range @p [first,last) so that @p *nth
3959 * is the same element that would have been in that position had the
3960 * whole sequence been sorted. The elements either side of @p *nth are
3961 * not completely sorted, but for any iterator @i in the range
3962 * @p [first,nth) and any iterator @j in the range @p [nth,last) it
3963 * holds that @p comp(*j,*i) is false.
3964 */
3966 void
3968 _RandomAccessIterator __nth,
3969 _RandomAccessIterator __last,
3970 _Compare __comp)
3971 {
3973 _ValueType;
3975 // concept requirements
3977 _RandomAccessIterator>)
3984 {
3985 _RandomAccessIterator __cut =
3988 *(__first
3989 + (__last
3996 else
3998 }
4000 }
4002 /**
4003 * @brief Finds the largest subrange in which @a val could be inserted
4004 * at any place in it without changing the ordering.
4005 * @param first An iterator.
4006 * @param last Another iterator.
4007 * @param val The search term.
4008 * @return An pair of iterators defining the subrange.
4009 * @ingroup binarysearch
4010 *
4011 * This is equivalent to
4012 * @code
4013 * std::make_pair(lower_bound(first, last, val),
4014 * upper_bound(first, last, val))
4015 * @endcode
4016 * but does not actually call those functions.
4017 */
4022 {
4024 _ValueType;
4026 _DistanceType;
4028 // concept requirements
4035 _DistanceType __half;
4039 {
4044 {
4048 }
4051 else
4052 {
4057 }
4058 }
4060 }
4062 /**
4063 * @brief Finds the largest subrange in which @a val could be inserted
4064 * at any place in it without changing the ordering.
4065 * @param first An iterator.
4066 * @param last Another iterator.
4067 * @param val The search term.
4068 * @param comp A functor to use for comparisons.
4069 * @return An pair of iterators defining the subrange.
4070 * @ingroup binarysearch
4071 *
4072 * This is equivalent to
4073 * @code
4074 * std::make_pair(lower_bound(first, last, val, comp),
4075 * upper_bound(first, last, val, comp))
4076 * @endcode
4077 * but does not actually call those functions.
4078 */
4083 _Compare __comp)
4084 {
4086 _ValueType;
4088 _DistanceType;
4090 // concept requirements
4099 _DistanceType __half;
4103 {
4108 {
4112 }
4115 else
4116 {
4121 }
4122 }
4124 }
4126 /**
4127 * @brief Determines whether an element exists in a range.
4128 * @param first An iterator.
4129 * @param last Another iterator.
4130 * @param val The search term.
4131 * @return True if @a val (or its equivelent) is in [@a first,@a last ].
4132 * @ingroup binarysearch
4133 *
4134 * Note that this does not actually return an iterator to @a val. For
4135 * that, use std::find or a container's specialized find member functions.
4136 */
4138 bool
4141 {
4143 _ValueType;
4145 // concept requirements
4152 }
4154 /**
4155 * @brief Determines whether an element exists in a range.
4156 * @param first An iterator.
4157 * @param last Another iterator.
4158 * @param val The search term.
4159 * @param comp A functor to use for comparisons.
4160 * @return True if @a val (or its equivelent) is in [@a first,@a last ].
4161 * @ingroup binarysearch
4162 *
4163 * Note that this does not actually return an iterator to @a val. For
4164 * that, use std::find or a container's specialized find member functions.
4165 *
4166 * The comparison function should have the same effects on ordering as
4167 * the function used for the initial sort.
4168 */
4170 bool
4173 {
4175 _ValueType;
4177 // concept requirements
4185 }
4187 // Set algorithms: includes, set_union, set_intersection, set_difference,
4188 // set_symmetric_difference. All of these algorithms have the precondition
4189 // that their input ranges are sorted and the postcondition that their output
4190 // ranges are sorted.
4192 /**
4193 * @brief Determines whether all elements of a sequence exists in a range.
4194 * @param first1 Start of search range.
4195 * @param last1 End of search range.
4196 * @param first2 Start of sequence
4197 * @param last2 End of sequence.
4198 * @return True if each element in [first2,last2) is contained in order
4199 * within [first1,last1). False otherwise.
4200 * @ingroup setoperations
4201 *
4202 * This operation expects both [first1,last1) and [first2,last2) to be
4203 * sorted. Searches for the presence of each element in [first2,last2)
4204 * within [first1,last1). The iterators over each range only move forward,
4205 * so this is a linear algorithm. If an element in [first2,last2) is not
4206 * found before the search iterator reaches @a last2, false is returned.
4207 */
4209 bool
4212 {
4214 _ValueType1;
4216 _ValueType2;
4218 // concept requirements
4231 else
4235 }
4237 /**
4238 * @brief Determines whether all elements of a sequence exists in a range
4239 * using comparison.
4240 * @param first1 Start of search range.
4241 * @param last1 End of search range.
4242 * @param first2 Start of sequence
4243 * @param last2 End of sequence.
4244 * @param comp Comparison function to use.
4245 * @return True if each element in [first2,last2) is contained in order
4246 * within [first1,last1) according to comp. False otherwise.
4247 * @ingroup setoperations
4248 *
4249 * This operation expects both [first1,last1) and [first2,last2) to be
4250 * sorted. Searches for the presence of each element in [first2,last2)
4251 * within [first1,last1), using comp to decide. The iterators over each
4252 * range only move forward, so this is a linear algorithm. If an element
4253 * in [first2,last2) is not found before the search iterator reaches @a
4254 * last2, false is returned.
4255 */
4257 typename _Compare>
4258 bool
4261 {
4263 _ValueType1;
4265 _ValueType2;
4267 // concept requirements
4282 else
4286 }
4288 /**
4289 * @brief Return the union of two sorted ranges.
4290 * @param first1 Start of first range.
4291 * @param last1 End of first range.
4292 * @param first2 Start of second range.
4293 * @param last2 End of second range.
4294 * @return End of the output range.
4295 * @ingroup setoperations
4296 *
4297 * This operation iterates over both ranges, copying elements present in
4298 * each range in order to the output range. Iterators increment for each
4299 * range. When the current element of one range is less than the other,
4300 * that element is copied and the iterator advanced. If an element is
4301 * contained in both ranges, the element from the first range is copied and
4302 * both ranges advance. The output range may not overlap either input
4303 * range.
4304 */
4306 typename _OutputIterator>
4307 _OutputIterator
4310 _OutputIterator __result)
4311 {
4313 _ValueType1;
4315 _ValueType2;
4317 // concept requirements
4321 _ValueType1>)
4323 _ValueType2>)
4330 {
4332 {
4335 }
4337 {
4340 }
4341 else
4342 {
4346 }
4348 }
4350 __result));
4351 }
4353 /**
4354 * @brief Return the union of two sorted ranges using a comparison functor.
4355 * @param first1 Start of first range.
4356 * @param last1 End of first range.
4357 * @param first2 Start of second range.
4358 * @param last2 End of second range.
4359 * @param comp The comparison functor.
4360 * @return End of the output range.
4361 * @ingroup setoperations
4362 *
4363 * This operation iterates over both ranges, copying elements present in
4364 * each range in order to the output range. Iterators increment for each
4365 * range. When the current element of one range is less than the other
4366 * according to @a comp, that element is copied and the iterator advanced.
4367 * If an equivalent element according to @a comp is contained in both
4368 * ranges, the element from the first range is copied and both ranges
4369 * advance. The output range may not overlap either input range.
4370 */
4373 _OutputIterator
4377 {
4379 _ValueType1;
4381 _ValueType2;
4383 // concept requirements
4387 _ValueType1>)
4389 _ValueType2>)
4398 {
4400 {
4403 }
4405 {
4408 }
4409 else
4410 {
4414 }
4416 }
4418 __result));
4419 }
4421 /**
4422 * @brief Return the intersection of two sorted ranges.
4423 * @param first1 Start of first range.
4424 * @param last1 End of first range.
4425 * @param first2 Start of second range.
4426 * @param last2 End of second range.
4427 * @return End of the output range.
4428 * @ingroup setoperations
4429 *
4430 * This operation iterates over both ranges, copying elements present in
4431 * both ranges in order to the output range. Iterators increment for each
4432 * range. When the current element of one range is less than the other,
4433 * that iterator advances. If an element is contained in both ranges, the
4434 * element from the first range is copied and both ranges advance. The
4435 * output range may not overlap either input range.
4436 */
4438 typename _OutputIterator>
4439 _OutputIterator
4442 _OutputIterator __result)
4443 {
4445 _ValueType1;
4447 _ValueType2;
4449 // concept requirements
4453 _ValueType1>)
4464 else
4465 {
4470 }
4472 }
4474 /**
4475 * @brief Return the intersection of two sorted ranges using comparison
4476 * functor.
4477 * @param first1 Start of first range.
4478 * @param last1 End of first range.
4479 * @param first2 Start of second range.
4480 * @param last2 End of second range.
4481 * @param comp The comparison functor.
4482 * @return End of the output range.
4483 * @ingroup setoperations
4484 *
4485 * This operation iterates over both ranges, copying elements present in
4486 * both ranges in order to the output range. Iterators increment for each
4487 * range. When the current element of one range is less than the other
4488 * according to @a comp, that iterator advances. If an element is
4489 * contained in both ranges according to @a comp, the element from the
4490 * first range is copied and both ranges advance. The output range may not
4491 * overlap either input range.
4492 */
4495 _OutputIterator
4499 {
4501 _ValueType1;
4503 _ValueType2;
4505 // concept requirements
4509 _ValueType1>)
4522 else
4523 {
4528 }
4530 }
4532 /**
4533 * @brief Return the difference of two sorted ranges.
4534 * @param first1 Start of first range.
4535 * @param last1 End of first range.
4536 * @param first2 Start of second range.
4537 * @param last2 End of second range.
4538 * @return End of the output range.
4539 * @ingroup setoperations
4540 *
4541 * This operation iterates over both ranges, copying elements present in
4542 * the first range but not the second in order to the output range.
4543 * Iterators increment for each range. When the current element of the
4544 * first range is less than the second, that element is copied and the
4545 * iterator advances. If the current element of the second range is less,
4546 * the iterator advances, but no element is copied. If an element is
4547 * contained in both ranges, no elements are copied and both ranges
4548 * advance. The output range may not overlap either input range.
4549 */
4551 typename _OutputIterator>
4552 _OutputIterator
4555 _OutputIterator __result)
4556 {
4558 _ValueType1;
4560 _ValueType2;
4562 // concept requirements
4566 _ValueType1>)
4574 {
4578 }
4581 else
4582 {
4585 }
4587 }
4589 /**
4590 * @brief Return the difference of two sorted ranges using comparison
4591 * functor.
4592 * @param first1 Start of first range.
4593 * @param last1 End of first range.
4594 * @param first2 Start of second range.
4595 * @param last2 End of second range.
4596 * @param comp The comparison functor.
4597 * @return End of the output range.
4598 * @ingroup setoperations
4599 *
4600 * This operation iterates over both ranges, copying elements present in
4601 * the first range but not the second in order to the output range.
4602 * Iterators increment for each range. When the current element of the
4603 * first range is less than the second according to @a comp, that element
4604 * is copied and the iterator advances. If the current element of the
4605 * second range is less, no element is copied and the iterator advances.
4606 * If an element is contained in both ranges according to @a comp, no
4607 * elements are copied and both ranges advance. The output range may not
4608 * overlap either input range.
4609 */
4612 _OutputIterator
4616 {
4618 _ValueType1;
4620 _ValueType2;
4622 // concept requirements
4626 _ValueType1>)
4636 {
4640 }
4643 else
4644 {
4647 }
4649 }
4651 /**
4652 * @brief Return the symmetric difference of two sorted ranges.
4653 * @param first1 Start of first range.
4654 * @param last1 End of first range.
4655 * @param first2 Start of second range.
4656 * @param last2 End of second range.
4657 * @return End of the output range.
4658 * @ingroup setoperations
4659 *
4660 * This operation iterates over both ranges, copying elements present in
4661 * one range but not the other in order to the output range. Iterators
4662 * increment for each range. When the current element of one range is less
4663 * than the other, that element is copied and the iterator advances. If an
4664 * element is contained in both ranges, no elements are copied and both
4665 * ranges advance. The output range may not overlap either input range.
4666 */
4668 typename _OutputIterator>
4669 _OutputIterator
4672 _OutputIterator __result)
4673 {
4675 _ValueType1;
4677 _ValueType2;
4679 // concept requirements
4683 _ValueType1>)
4685 _ValueType2>)
4693 {
4697 }
4699 {
4703 }
4704 else
4705 {
4708 }
4711 }
4713 /**
4714 * @brief Return the symmetric difference of two sorted ranges using
4715 * comparison functor.
4716 * @param first1 Start of first range.
4717 * @param last1 End of first range.
4718 * @param first2 Start of second range.
4719 * @param last2 End of second range.
4720 * @param comp The comparison functor.
4721 * @return End of the output range.
4722 * @ingroup setoperations
4723 *
4724 * This operation iterates over both ranges, copying elements present in
4725 * one range but not the other in order to the output range. Iterators
4726 * increment for each range. When the current element of one range is less
4727 * than the other according to @a comp, that element is copied and the
4728 * iterator advances. If an element is contained in both ranges according
4729 * to @a comp, no elements are copied and both ranges advance. The output
4730 * range may not overlap either input range.
4731 */
4734 _OutputIterator
4737 _OutputIterator __result,
4738 _Compare __comp)
4739 {
4741 _ValueType1;
4743 _ValueType2;
4745 // concept requirements
4749 _ValueType1>)
4751 _ValueType2>)
4761 {
4765 }
4767 {
4771 }
4772 else
4773 {
4776 }
4779 }
4781 // min_element and max_element, with and without an explicitly supplied
4782 // comparison function.
4784 /**
4785 * @brief Return the maximum element in a range.
4786 * @param first Start of range.
4787 * @param last End of range.
4788 * @return Iterator referencing the first instance of the largest value.
4789 */
4791 _ForwardIterator
4793 {
4794 // concept requirements
4807 }
4809 /**
4810 * @brief Return the maximum element in a range using comparison functor.
4811 * @param first Start of range.
4812 * @param last End of range.
4813 * @param comp Comparison functor.
4814 * @return Iterator referencing the first instance of the largest value
4815 * according to comp.
4816 */
4818 _ForwardIterator
4820 _Compare __comp)
4821 {
4822 // concept requirements
4834 }
4836 /**
4837 * @brief Return the minimum element in a range.
4838 * @param first Start of range.
4839 * @param last End of range.
4840 * @return Iterator referencing the first instance of the smallest value.
4841 */
4843 _ForwardIterator
4845 {
4846 // concept requirements
4859 }
4861 /**
4862 * @brief Return the minimum element in a range using comparison functor.
4863 * @param first Start of range.
4864 * @param last End of range.
4865 * @param comp Comparison functor.
4866 * @return Iterator referencing the first instance of the smallest value
4867 * according to comp.
4868 */
4870 _ForwardIterator
4872 _Compare __comp)
4873 {
4874 // concept requirements
4888 }
4890 // next_permutation and prev_permutation, with and without an explicitly
4891 // supplied comparison function.
4893 /**
4894 * @brief Permute range into the next "dictionary" ordering.
4895 * @param first Start of range.
4896 * @param last End of range.
4897 * @return False if wrapped to first permutation, true otherwise.
4898 *
4899 * Treats all permutations of the range as a set of "dictionary" sorted
4900 * sequences. Permutes the current sequence into the next one of this set.
4901 * Returns true if there are more sequences to generate. If the sequence
4902 * is the largest of the set, the smallest is generated and false returned.
4903 */
4905 bool
4907 _BidirectionalIterator __last)
4908 {
4909 // concept requirements
4911 _BidirectionalIterator>)
4926 {
4930 {
4933 {}
4937 }
4939 {
4942 }
4943 }
4944 }
4946 /**
4947 * @brief Permute range into the next "dictionary" ordering using
4948 * comparison functor.
4949 * @param first Start of range.
4950 * @param last End of range.
4951 * @param comp
4952 * @return False if wrapped to first permutation, true otherwise.
4953 *
4954 * Treats all permutations of the range [first,last) as a set of
4955 * "dictionary" sorted sequences ordered by @a comp. Permutes the current
4956 * sequence into the next one of this set. Returns true if there are more
4957 * sequences to generate. If the sequence is the largest of the set, the
4958 * smallest is generated and false returned.
4959 */
4961 bool
4964 {
4965 // concept requirements
4967 _BidirectionalIterator>)
4983 {
4987 {
4990 {}
4994 }
4996 {
4999 }
5000 }
5001 }
5003 /**
5004 * @brief Permute range into the previous "dictionary" ordering.
5005 * @param first Start of range.
5006 * @param last End of range.
5007 * @return False if wrapped to last permutation, true otherwise.
5008 *
5009 * Treats all permutations of the range as a set of "dictionary" sorted
5010 * sequences. Permutes the current sequence into the previous one of this
5011 * set. Returns true if there are more sequences to generate. If the
5012 * sequence is the smallest of the set, the largest is generated and false
5013 * returned.
5014 */
5016 bool
5018 _BidirectionalIterator __last)
5019 {
5020 // concept requirements
5022 _BidirectionalIterator>)
5037 {
5041 {
5044 {}
5048 }
5050 {
5053 }
5054 }
5055 }
5057 /**
5058 * @brief Permute range into the previous "dictionary" ordering using
5059 * comparison functor.
5060 * @param first Start of range.
5061 * @param last End of range.
5062 * @param comp
5063 * @return False if wrapped to last permutation, true otherwise.
5064 *
5065 * Treats all permutations of the range [first,last) as a set of
5066 * "dictionary" sorted sequences ordered by @a comp. Permutes the current
5067 * sequence into the previous one of this set. Returns true if there are
5068 * more sequences to generate. If the sequence is the smallest of the set,
5069 * the largest is generated and false returned.
5070 */
5072 bool
5075 {
5076 // concept requirements
5078 _BidirectionalIterator>)
5094 {
5098 {
5101 {}
5105 }
5107 {
5110 }
5111 }
5112 }
5114 // find_first_of, with and without an explicitly supplied comparison function.
5116 /**
5117 * @brief Find element from a set in a sequence.
5118 * @param first1 Start of range to search.
5119 * @param last1 End of range to search.
5120 * @param first2 Start of match candidates.
5121 * @param last2 End of match candidates.
5122 * @return The first iterator @c i in the range
5123 * @p [first1,last1) such that @c *i == @p *(i2) such that i2 is an
5124 * interator in [first2,last2), or @p last1 if no such iterator exists.
5125 *
5126 * Searches the range @p [first1,last1) for an element that is equal to
5127 * some element in the range [first2,last2). If found, returns an iterator
5128 * in the range [first1,last1), otherwise returns @p last1.
5129 */
5131 _InputIterator
5134 {
5135 // concept requirements
5149 }
5151 /**
5152 * @brief Find element from a set in a sequence using a predicate.
5153 * @param first1 Start of range to search.
5154 * @param last1 End of range to search.
5155 * @param first2 Start of match candidates.
5156 * @param last2 End of match candidates.
5157 * @param comp Predicate to use.
5158 * @return The first iterator @c i in the range
5159 * @p [first1,last1) such that @c comp(*i, @p *(i2)) is true and i2 is an
5160 * interator in [first2,last2), or @p last1 if no such iterator exists.
5161 *
5162 * Searches the range @p [first1,last1) for an element that is equal to
5163 * some element in the range [first2,last2). If found, returns an iterator in
5164 * the range [first1,last1), otherwise returns @p last1.
5165 */
5167 typename _BinaryPredicate>
5168 _InputIterator
5171 _BinaryPredicate __comp)
5172 {
5173 // concept requirements
5187 }
5190 // find_end, with and without an explicitly supplied comparison function.
5191 // Search [first2, last2) as a subsequence in [first1, last1), and return
5192 // the *last* possible match. Note that find_end for bidirectional iterators
5193 // is much faster than for forward iterators.
5195 // find_end for forward iterators.
5197 _ForwardIterator1
5201 {
5204 else
5205 {
5208 {
5209 _ForwardIterator1 __new_result
5213 else
5214 {
5218 }
5219 }
5220 }
5221 }
5224 typename _BinaryPredicate>
5225 _ForwardIterator1
5229 _BinaryPredicate __comp)
5230 {
5233 else
5234 {
5237 {
5238 _ForwardIterator1 __new_result
5242 else
5243 {
5247 }
5248 }
5249 }
5250 }
5252 // find_end for bidirectional iterators. Requires partial specialization.
5254 _BidirectionalIterator1
5256 _BidirectionalIterator1 __last1,
5257 _BidirectionalIterator2 __first2,
5258 _BidirectionalIterator2 __last2,
5260 {
5261 // concept requirements
5263 _BidirectionalIterator1>)
5265 _BidirectionalIterator2>)
5277 else
5278 {
5282 }
5283 }
5286 typename _BinaryPredicate>
5287 _BidirectionalIterator1
5289 _BidirectionalIterator1 __last1,
5290 _BidirectionalIterator2 __first2,
5291 _BidirectionalIterator2 __last2,
5293 _BinaryPredicate __comp)
5294 {
5295 // concept requirements
5297 _BidirectionalIterator1>)
5299 _BidirectionalIterator2>)
5308 __comp);
5312 else
5313 {
5317 }
5318 }
5320 // Dispatching functions for find_end.
5322 /**
5323 * @brief Find last matching subsequence in a sequence.
5324 * @param first1 Start of range to search.
5325 * @param last1 End of range to search.
5326 * @param first2 Start of sequence to match.
5327 * @param last2 End of sequence to match.
5328 * @return The last iterator @c i in the range
5329 * @p [first1,last1-(last2-first2)) such that @c *(i+N) == @p *(first2+N)
5330 * for each @c N in the range @p [0,last2-first2), or @p last1 if no
5331 * such iterator exists.
5332 *
5333 * Searches the range @p [first1,last1) for a sub-sequence that compares
5334 * equal value-by-value with the sequence given by @p [first2,last2) and
5335 * returns an iterator to the first element of the sub-sequence, or
5336 * @p last1 if the sub-sequence is not found. The sub-sequence will be the
5337 * last such subsequence contained in [first,last1).
5338 *
5339 * Because the sub-sequence must lie completely within the range
5340 * @p [first1,last1) it must start at a position less than
5341 * @p last1-(last2-first2) where @p last2-first2 is the length of the
5342 * sub-sequence.
5343 * This means that the returned iterator @c i will be in the range
5344 * @p [first1,last1-(last2-first2))
5345 */
5347 inline _ForwardIterator1
5350 {
5351 // concept requirements
5363 }
5365 /**
5366 * @brief Find last matching subsequence in a sequence using a predicate.
5367 * @param first1 Start of range to search.
5368 * @param last1 End of range to search.
5369 * @param first2 Start of sequence to match.
5370 * @param last2 End of sequence to match.
5371 * @param comp The predicate to use.
5372 * @return The last iterator @c i in the range
5373 * @p [first1,last1-(last2-first2)) such that @c predicate(*(i+N), @p
5374 * (first2+N)) is true for each @c N in the range @p [0,last2-first2), or
5375 * @p last1 if no such iterator exists.
5376 *
5377 * Searches the range @p [first1,last1) for a sub-sequence that compares
5378 * equal value-by-value with the sequence given by @p [first2,last2) using
5379 * comp as a predicate and returns an iterator to the first element of the
5380 * sub-sequence, or @p last1 if the sub-sequence is not found. The
5381 * sub-sequence will be the last such subsequence contained in
5382 * [first,last1).
5383 *
5384 * Because the sub-sequence must lie completely within the range
5385 * @p [first1,last1) it must start at a position less than
5386 * @p last1-(last2-first2) where @p last2-first2 is the length of the
5387 * sub-sequence.
5388 * This means that the returned iterator @c i will be in the range
5389 * @p [first1,last1-(last2-first2))
5390 */
5392 typename _BinaryPredicate>
5393 inline _ForwardIterator1
5396 _BinaryPredicate __comp)
5397 {
5398 // concept requirements
5410 __comp);
5411 }
5413 _GLIBCXX_END_NAMESPACE