| blob | cfdbbc0637a503519d12f728d8b8b1aacb22043d |
1 // Algorithm implementation -*- C++ -*-
3 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008
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 _STL_ALGO_H
63 #define _STL_ALGO_H 1
66 #include <bits/algorithmfwd.h>
67 #include <bits/stl_heap.h>
69 #include <debug/debug.h>
71 // See concept_check.h for the __glibcxx_*_requires macros.
75 /**
76 * @brief Find the median of three values.
77 * @param a A value.
78 * @param b A value.
79 * @param c A value.
80 * @return One of @p a, @p b or @p c.
81 *
82 * If @c {l,m,n} is some convolution of @p {a,b,c} such that @c l<=m<=n
83 * then the value returned will be @c m.
84 * This is an SGI extension.
85 * @ingroup SGIextensions
86 */
90 {
91 // concept requirements
98 else
104 else
106 }
108 /**
109 * @brief Find the median of three values using a predicate for comparison.
110 * @param a A value.
111 * @param b A value.
112 * @param c A value.
113 * @param comp A binary predicate.
114 * @return One of @p a, @p b or @p c.
115 *
116 * If @c {l,m,n} is some convolution of @p {a,b,c} such that @p comp(l,m)
117 * and @p comp(m,n) are both true then the value returned will be @c m.
118 * This is an SGI extension.
119 * @ingroup SGIextensions
120 */
124 {
125 // concept requirements
133 else
139 else
141 }
143 // for_each
145 /// This is an overload used by find() for the Input Iterator case.
147 inline _InputIterator
150 {
154 }
156 /// This is an overload used by find_if() for the Input Iterator case.
158 inline _InputIterator
161 {
165 }
167 /// This is an overload used by find() for the RAI case.
169 _RandomAccessIterator
172 {
177 {
193 }
196 {
212 }
213 }
215 /// This is an overload used by find_if() for the RAI case.
217 _RandomAccessIterator
220 {
225 {
241 }
244 {
260 }
261 }
263 // set_difference
264 // set_intersection
265 // set_symmetric_difference
266 // set_union
267 // for_each
268 // find
269 // find_if
270 // find_first_of
271 // adjacent_find
272 // count
273 // count_if
274 // search
276 /**
277 * This is an uglified
278 * search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&)
279 * overloaded for forward iterators.
280 */
282 _ForwardIterator
286 {
289 {
295 {
298 }
304 }
306 }
308 /**
309 * This is an uglified
310 * search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&)
311 * overloaded for random access iterators.
312 */
314 _RandomAccessIter
318 {
321 _DistanceType;
334 {
335 // __lookAhead here is always pointing to the last element of next
336 // possible match.
338 {
343 }
347 {
350 }
355 }
356 }
358 // search_n
360 /**
361 * This is an uglified
362 * search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&,
363 * _BinaryPredicate)
364 * overloaded for forward iterators.
365 */
367 typename _BinaryPredicate>
368 _ForwardIterator
372 {
377 {
383 {
386 }
395 }
397 }
399 /**
400 * This is an uglified
401 * search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&,
402 * _BinaryPredicate)
403 * overloaded for random access iterators.
404 */
406 typename _BinaryPredicate>
407 _RandomAccessIter
411 {
414 _DistanceType;
427 {
428 // __lookAhead here is always pointing to the last element of next
429 // possible match.
431 {
436 }
440 {
443 }
448 }
449 }
451 // find_end for forward iterators.
453 _ForwardIterator1
457 {
460 else
461 {
464 {
465 _ForwardIterator1 __new_result
469 else
470 {
474 }
475 }
476 }
477 }
480 typename _BinaryPredicate>
481 _ForwardIterator1
485 _BinaryPredicate __comp)
486 {
489 else
490 {
493 {
494 _ForwardIterator1 __new_result
499 else
500 {
504 }
505 }
506 }
507 }
509 // find_end for bidirectional iterators (much faster).
511 _BidirectionalIterator1
513 _BidirectionalIterator1 __last1,
514 _BidirectionalIterator2 __first2,
515 _BidirectionalIterator2 __last2,
517 {
518 // concept requirements
520 _BidirectionalIterator1>)
522 _BidirectionalIterator2>)
530 __rlast1,
532 __rlast2);
536 else
537 {
541 }
542 }
545 typename _BinaryPredicate>
546 _BidirectionalIterator1
548 _BidirectionalIterator1 __last1,
549 _BidirectionalIterator2 __first2,
550 _BidirectionalIterator2 __last2,
552 _BinaryPredicate __comp)
553 {
554 // concept requirements
556 _BidirectionalIterator1>)
558 _BidirectionalIterator2>)
567 __comp);
571 else
572 {
576 }
577 }
579 /**
580 * @brief Find last matching subsequence in a sequence.
581 * @param first1 Start of range to search.
582 * @param last1 End of range to search.
583 * @param first2 Start of sequence to match.
584 * @param last2 End of sequence to match.
585 * @return The last iterator @c i in the range
586 * @p [first1,last1-(last2-first2)) such that @c *(i+N) == @p *(first2+N)
587 * for each @c N in the range @p [0,last2-first2), or @p last1 if no
588 * such iterator exists.
589 *
590 * Searches the range @p [first1,last1) for a sub-sequence that compares
591 * equal value-by-value with the sequence given by @p [first2,last2) and
592 * returns an iterator to the first element of the sub-sequence, or
593 * @p last1 if the sub-sequence is not found. The sub-sequence will be the
594 * last such subsequence contained in [first,last1).
595 *
596 * Because the sub-sequence must lie completely within the range
597 * @p [first1,last1) it must start at a position less than
598 * @p last1-(last2-first2) where @p last2-first2 is the length of the
599 * sub-sequence.
600 * This means that the returned iterator @c i will be in the range
601 * @p [first1,last1-(last2-first2))
602 */
604 inline _ForwardIterator1
607 {
608 // concept requirements
620 }
622 /**
623 * @brief Find last matching subsequence in a sequence using a predicate.
624 * @param first1 Start of range to search.
625 * @param last1 End of range to search.
626 * @param first2 Start of sequence to match.
627 * @param last2 End of sequence to match.
628 * @param comp The predicate to use.
629 * @return The last iterator @c i in the range
630 * @p [first1,last1-(last2-first2)) such that @c predicate(*(i+N), @p
631 * (first2+N)) is true for each @c N in the range @p [0,last2-first2), or
632 * @p last1 if no such iterator exists.
633 *
634 * Searches the range @p [first1,last1) for a sub-sequence that compares
635 * equal value-by-value with the sequence given by @p [first2,last2) using
636 * comp as a predicate and returns an iterator to the first element of the
637 * sub-sequence, or @p last1 if the sub-sequence is not found. The
638 * sub-sequence will be the last such subsequence contained in
639 * [first,last1).
640 *
641 * Because the sub-sequence must lie completely within the range
642 * @p [first1,last1) it must start at a position less than
643 * @p last1-(last2-first2) where @p last2-first2 is the length of the
644 * sub-sequence.
645 * This means that the returned iterator @c i will be in the range
646 * @p [first1,last1-(last2-first2))
647 */
649 typename _BinaryPredicate>
650 inline _ForwardIterator1
653 _BinaryPredicate __comp)
654 {
655 // concept requirements
667 __comp);
668 }
671 /**
672 * @brief Copy a sequence, removing elements of a given value.
673 * @param first An input iterator.
674 * @param last An input iterator.
675 * @param result An output iterator.
676 * @param value The value to be removed.
677 * @return An iterator designating the end of the resulting sequence.
678 *
679 * Copies each element in the range @p [first,last) not equal to @p value
680 * to the range beginning at @p result.
681 * remove_copy() is stable, so the relative order of elements that are
682 * copied is unchanged.
683 */
685 _OutputIterator
688 {
689 // concept requirements
699 {
702 }
704 }
706 /**
707 * @brief Copy a sequence, removing elements for which a predicate is true.
708 * @param first An input iterator.
709 * @param last An input iterator.
710 * @param result An output iterator.
711 * @param pred A predicate.
712 * @return An iterator designating the end of the resulting sequence.
713 *
714 * Copies each element in the range @p [first,last) for which
715 * @p pred returns false to the range beginning at @p result.
716 *
717 * remove_copy_if() is stable, so the relative order of elements that are
718 * copied is unchanged.
719 */
721 typename _Predicate>
722 _OutputIterator
725 {
726 // concept requirements
736 {
739 }
741 }
743 /**
744 * @brief Remove elements from a sequence.
745 * @param first An input iterator.
746 * @param last An input iterator.
747 * @param value The value to be removed.
748 * @return An iterator designating the end of the resulting sequence.
749 *
750 * All elements equal to @p value are removed from the range
751 * @p [first,last).
752 *
753 * remove() is stable, so the relative order of elements that are
754 * not removed is unchanged.
755 *
756 * Elements between the end of the resulting sequence and @p last
757 * are still present, but their value is unspecified.
758 */
760 _ForwardIterator
763 {
764 // concept requirements
766 _ForwardIterator>)
778 {
781 }
783 }
785 /**
786 * @brief Remove elements from a sequence using a predicate.
787 * @param first A forward iterator.
788 * @param last A forward iterator.
789 * @param pred A predicate.
790 * @return An iterator designating the end of the resulting sequence.
791 *
792 * All elements for which @p pred returns true are removed from the range
793 * @p [first,last).
794 *
795 * remove_if() is stable, so the relative order of elements that are
796 * not removed is unchanged.
797 *
798 * Elements between the end of the resulting sequence and @p last
799 * are still present, but their value is unspecified.
800 */
802 _ForwardIterator
804 _Predicate __pred)
805 {
806 // concept requirements
808 _ForwardIterator>)
820 {
823 }
825 }
827 /**
828 * @brief Remove consecutive duplicate values from a sequence.
829 * @param first A forward iterator.
830 * @param last A forward iterator.
831 * @return An iterator designating the end of the resulting sequence.
832 *
833 * Removes all but the first element from each group of consecutive
834 * values that compare equal.
835 * unique() is stable, so the relative order of elements that are
836 * not removed is unchanged.
837 * Elements between the end of the resulting sequence and @p last
838 * are still present, but their value is unspecified.
839 */
841 _ForwardIterator
843 {
844 // concept requirements
846 _ForwardIterator>)
851 // Skip the beginning, if already unique.
856 // Do the real copy work.
863 }
865 /**
866 * @brief Remove consecutive values from a sequence using a predicate.
867 * @param first A forward iterator.
868 * @param last A forward iterator.
869 * @param binary_pred A binary predicate.
870 * @return An iterator designating the end of the resulting sequence.
871 *
872 * Removes all but the first element from each group of consecutive
873 * values for which @p binary_pred returns true.
874 * unique() is stable, so the relative order of elements that are
875 * not removed is unchanged.
876 * Elements between the end of the resulting sequence and @p last
877 * are still present, but their value is unspecified.
878 */
880 _ForwardIterator
882 _BinaryPredicate __binary_pred)
883 {
884 // concept requirements
886 _ForwardIterator>)
892 // Skip the beginning, if already unique.
897 // Do the real copy work.
904 }
906 /**
907 * This is an uglified unique_copy(_InputIterator, _InputIterator,
908 * _OutputIterator)
909 * overloaded for forward iterators and output iterator as result.
910 */
912 _OutputIterator
914 _OutputIterator __result,
916 {
917 // concept requirements -- taken care of in dispatching function
922 {
925 }
927 }
929 /**
930 * This is an uglified unique_copy(_InputIterator, _InputIterator,
931 * _OutputIterator)
932 * overloaded for input iterators and output iterator as result.
933 */
935 _OutputIterator
937 _OutputIterator __result,
939 {
940 // concept requirements -- taken care of in dispatching function
945 {
948 }
950 }
952 /**
953 * This is an uglified unique_copy(_InputIterator, _InputIterator,
954 * _OutputIterator)
955 * overloaded for input iterators and forward iterator as result.
956 */
958 _ForwardIterator
960 _ForwardIterator __result,
962 {
963 // concept requirements -- taken care of in dispatching function
969 }
971 /**
972 * This is an uglified
973 * unique_copy(_InputIterator, _InputIterator, _OutputIterator,
974 * _BinaryPredicate)
975 * overloaded for forward iterators and output iterator as result.
976 */
978 typename _BinaryPredicate>
979 _OutputIterator
983 {
984 // concept requirements -- iterators already checked
993 {
996 }
998 }
1000 /**
1001 * This is an uglified
1002 * unique_copy(_InputIterator, _InputIterator, _OutputIterator,
1003 * _BinaryPredicate)
1004 * overloaded for input iterators and output iterator as result.
1005 */
1007 typename _BinaryPredicate>
1008 _OutputIterator
1012 {
1013 // concept requirements -- iterators already checked
1022 {
1025 }
1027 }
1029 /**
1030 * This is an uglified
1031 * unique_copy(_InputIterator, _InputIterator, _OutputIterator,
1032 * _BinaryPredicate)
1033 * overloaded for input iterators and forward iterator as result.
1034 */
1036 typename _BinaryPredicate>
1037 _ForwardIterator
1041 {
1042 // concept requirements -- iterators already checked
1052 }
1054 /**
1055 * This is an uglified reverse(_BidirectionalIterator,
1056 * _BidirectionalIterator)
1057 * overloaded for bidirectional iterators.
1058 */
1060 void
1062 bidirectional_iterator_tag)
1063 {
1067 else
1068 {
1071 }
1072 }
1074 /**
1075 * This is an uglified reverse(_BidirectionalIterator,
1076 * _BidirectionalIterator)
1077 * overloaded for random access iterators.
1078 */
1080 void
1082 random_access_iterator_tag)
1083 {
1088 {
1092 }
1093 }
1095 /**
1096 * @brief Reverse a sequence.
1097 * @param first A bidirectional iterator.
1098 * @param last A bidirectional iterator.
1099 * @return reverse() returns no value.
1100 *
1101 * Reverses the order of the elements in the range @p [first,last),
1102 * so that the first element becomes the last etc.
1103 * For every @c i such that @p 0<=i<=(last-first)/2), @p reverse()
1104 * swaps @p *(first+i) and @p *(last-(i+1))
1105 */
1109 {
1110 // concept requirements
1112 _BidirectionalIterator>)
1115 }
1117 /**
1118 * @brief Copy a sequence, reversing its elements.
1119 * @param first A bidirectional iterator.
1120 * @param last A bidirectional iterator.
1121 * @param result An output iterator.
1122 * @return An iterator designating the end of the resulting sequence.
1123 *
1124 * Copies the elements in the range @p [first,last) to the range
1125 * @p [result,result+(last-first)) such that the order of the
1126 * elements is reversed.
1127 * For every @c i such that @p 0<=i<=(last-first), @p reverse_copy()
1128 * performs the assignment @p *(result+(last-first)-i) = *(first+i).
1129 * The ranges @p [first,last) and @p [result,result+(last-first))
1130 * must not overlap.
1131 */
1133 _OutputIterator
1135 _OutputIterator __result)
1136 {
1137 // concept requirements
1139 _BidirectionalIterator>)
1145 {
1149 }
1151 }
1153 /**
1154 * This is a helper function for the rotate algorithm specialized on RAIs.
1155 * It returns the greatest common divisor of two integer values.
1156 */
1158 _EuclideanRingElement
1160 {
1162 {
1166 }
1168 }
1170 /// This is a helper function for the rotate algorithm.
1172 void
1174 _ForwardIterator __middle,
1175 _ForwardIterator __last,
1176 forward_iterator_tag)
1177 {
1182 do
1183 {
1189 }
1195 {
1203 }
1204 }
1206 /// This is a helper function for the rotate algorithm.
1208 void
1210 _BidirectionalIterator __middle,
1211 _BidirectionalIterator __last,
1212 bidirectional_iterator_tag)
1213 {
1214 // concept requirements
1216 _BidirectionalIterator>)
1225 {
1228 }
1232 else
1234 }
1236 /// This is a helper function for the rotate algorithm.
1238 void
1240 _RandomAccessIterator __middle,
1241 _RandomAccessIterator __last,
1242 random_access_iterator_tag)
1243 {
1244 // concept requirements
1246 _RandomAccessIterator>)
1252 _Distance;
1254 _ValueType;
1261 {
1264 }
1269 {
1274 {
1276 {
1278 {
1281 }
1285 }
1286 }
1287 else
1288 {
1290 {
1292 {
1295 }
1298 }
1299 }
1303 }
1304 }
1306 /**
1307 * @brief Rotate the elements of a sequence.
1308 * @param first A forward iterator.
1309 * @param middle A forward iterator.
1310 * @param last A forward iterator.
1311 * @return Nothing.
1312 *
1313 * Rotates the elements of the range @p [first,last) by @p (middle-first)
1314 * positions so that the element at @p middle is moved to @p first, the
1315 * element at @p middle+1 is moved to @first+1 and so on for each element
1316 * in the range @p [first,last).
1317 *
1318 * This effectively swaps the ranges @p [first,middle) and
1319 * @p [middle,last).
1320 *
1321 * Performs @p *(first+(n+(last-middle))%(last-first))=*(first+n) for
1322 * each @p n in the range @p [0,last-first).
1323 */
1327 _ForwardIterator __last)
1328 {
1329 // concept requirements
1331 _ForwardIterator>)
1336 _IterType;
1338 }
1340 /**
1341 * @brief Copy a sequence, rotating its elements.
1342 * @param first A forward iterator.
1343 * @param middle A forward iterator.
1344 * @param last A forward iterator.
1345 * @param result An output iterator.
1346 * @return An iterator designating the end of the resulting sequence.
1347 *
1348 * Copies the elements of the range @p [first,last) to the range
1349 * beginning at @result, rotating the copied elements by @p (middle-first)
1350 * positions so that the element at @p middle is moved to @p result, the
1351 * element at @p middle+1 is moved to @result+1 and so on for each element
1352 * in the range @p [first,last).
1353 *
1354 * Performs @p *(result+(n+(last-middle))%(last-first))=*(first+n) for
1355 * each @p n in the range @p [0,last-first).
1356 */
1358 _OutputIterator
1361 {
1362 // concept requirements
1371 }
1373 /// This is a helper function...
1375 _ForwardIterator
1378 {
1390 {
1393 }
1396 }
1398 /// This is a helper function...
1400 _BidirectionalIterator
1403 {
1405 {
1411 else
1419 else
1423 }
1424 }
1426 // partition
1428 /// This is a helper function...
1430 _ForwardIterator
1432 _ForwardIterator __last,
1434 {
1440 __middle,
1441 __pred,
1444 __pred,
1445 __len
1450 }
1452 /// This is a helper function...
1454 typename _Distance>
1455 _ForwardIterator
1457 _ForwardIterator __last,
1459 _Pointer __buffer,
1460 _Distance __buffer_size)
1461 {
1463 {
1468 {
1471 }
1472 else
1473 {
1476 }
1479 }
1480 else
1481 {
1484 _ForwardIterator __begin =
1487 __buffer_size);
1488 _ForwardIterator __end =
1495 }
1496 }
1498 /**
1499 * @brief Move elements for which a predicate is true to the beginning
1500 * of a sequence, preserving relative ordering.
1501 * @param first A forward iterator.
1502 * @param last A forward iterator.
1503 * @param pred A predicate functor.
1504 * @return An iterator @p middle such that @p pred(i) is true for each
1505 * iterator @p i in the range @p [first,middle) and false for each @p i
1506 * in the range @p [middle,last).
1507 *
1508 * Performs the same function as @p partition() with the additional
1509 * guarantee that the relative ordering of elements in each group is
1510 * preserved, so any two elements @p x and @p y in the range
1511 * @p [first,last) such that @p pred(x)==pred(y) will have the same
1512 * relative ordering after calling @p stable_partition().
1513 */
1515 _ForwardIterator
1517 _Predicate __pred)
1518 {
1519 // concept requirements
1521 _ForwardIterator>)
1528 else
1529 {
1531 _ValueType;
1533 _DistanceType;
1536 __last);
1538 return
1543 else
1544 return
1547 }
1548 }
1550 /// This is a helper function for the sort routines.
1552 void
1554 _RandomAccessIterator __middle,
1555 _RandomAccessIterator __last)
1556 {
1561 }
1563 /// This is a helper function for the sort routines.
1565 void
1567 _RandomAccessIterator __middle,
1569 {
1574 }
1576 // partial_sort
1578 /**
1579 * @brief Copy the smallest elements of a sequence.
1580 * @param first An iterator.
1581 * @param last Another iterator.
1582 * @param result_first A random-access iterator.
1583 * @param result_last Another random-access iterator.
1584 * @return An iterator indicating the end of the resulting sequence.
1585 *
1586 * Copies and sorts the smallest N values from the range @p [first,last)
1587 * to the range beginning at @p result_first, where the number of
1588 * elements to be copied, @p N, is the smaller of @p (last-first) and
1589 * @p (result_last-result_first).
1590 * After the sort if @p i and @j are iterators in the range
1591 * @p [result_first,result_first+N) such that @i precedes @j then
1592 * @p *j<*i is false.
1593 * The value returned is @p result_first+N.
1594 */
1596 _RandomAccessIterator
1598 _RandomAccessIterator __result_first,
1599 _RandomAccessIterator __result_last)
1600 {
1602 _InputValueType;
1604 _OutputValueType;
1606 _DistanceType;
1608 // concept requirements
1611 _OutputValueType>)
1613 _OutputValueType>)
1622 {
1626 }
1629 {
1636 }
1639 }
1641 /**
1642 * @brief Copy the smallest elements of a sequence using a predicate for
1643 * comparison.
1644 * @param first An input iterator.
1645 * @param last Another input iterator.
1646 * @param result_first A random-access iterator.
1647 * @param result_last Another random-access iterator.
1648 * @param comp A comparison functor.
1649 * @return An iterator indicating the end of the resulting sequence.
1650 *
1651 * Copies and sorts the smallest N values from the range @p [first,last)
1652 * to the range beginning at @p result_first, where the number of
1653 * elements to be copied, @p N, is the smaller of @p (last-first) and
1654 * @p (result_last-result_first).
1655 * After the sort if @p i and @j are iterators in the range
1656 * @p [result_first,result_first+N) such that @i precedes @j then
1657 * @p comp(*j,*i) is false.
1658 * The value returned is @p result_first+N.
1659 */
1661 _RandomAccessIterator
1663 _RandomAccessIterator __result_first,
1664 _RandomAccessIterator __result_last,
1665 _Compare __comp)
1666 {
1668 _InputValueType;
1670 _OutputValueType;
1672 _DistanceType;
1674 // concept requirements
1677 _RandomAccessIterator>)
1679 _OutputValueType>)
1691 {
1695 }
1698 {
1704 __comp);
1706 }
1709 }
1711 /// This is a helper function for the sort routine.
1713 void
1715 {
1719 {
1723 }
1725 }
1727 /// This is a helper function for the sort routine.
1729 void
1731 _Compare __comp)
1732 {
1736 {
1740 }
1742 }
1744 /// This is a helper function for the sort routine.
1746 void
1748 _RandomAccessIterator __last)
1749 {
1754 {
1758 {
1761 }
1762 else
1764 }
1765 }
1767 /// This is a helper function for the sort routine.
1769 void
1772 {
1776 {
1780 {
1783 }
1784 else
1786 }
1787 }
1789 /// This is a helper function for the sort routine.
1793 _RandomAccessIterator __last)
1794 {
1796 _ValueType;
1800 }
1802 /// This is a helper function for the sort routine.
1807 {
1809 _ValueType;
1813 }
1815 /**
1816 * @doctodo
1817 * This controls some aspect of the sort routines.
1818 */
1821 /// This is a helper function for the sort routine.
1823 void
1825 _RandomAccessIterator __last)
1826 {
1828 {
1831 }
1832 else
1834 }
1836 /// This is a helper function for the sort routine.
1838 void
1841 {
1843 {
1846 __comp);
1847 }
1848 else
1850 }
1852 /// This is a helper function...
1854 _RandomAccessIterator
1857 {
1859 {
1869 }
1870 }
1872 /// This is a helper function...
1874 _RandomAccessIterator
1876 _RandomAccessIterator __last,
1878 {
1880 {
1890 }
1891 }
1893 /// This is a helper function for the sort routine.
1895 void
1897 _RandomAccessIterator __last,
1898 _Size __depth_limit)
1899 {
1901 _ValueType;
1904 {
1906 {
1909 }
1911 _RandomAccessIterator __cut =
1914 *(__first
1915 + (__last
1918 *(__last
1922 }
1923 }
1925 /// This is a helper function for the sort routine.
1927 void
1929 _RandomAccessIterator __last,
1931 {
1933 _ValueType;
1936 {
1938 {
1941 }
1943 _RandomAccessIterator __cut =
1946 *(__first
1947 + (__last
1951 __comp)),
1952 __comp);
1955 }
1956 }
1958 /// This is a helper function for the sort routines. Precondition: __n > 0.
1960 inline _Size
1962 {
1963 _Size __k;
1967 }
1981 // sort
1984 void
1987 {
1989 _ValueType;
1992 {
1994 {
1997 // Place the nth largest element in its final position.
2000 }
2002 _RandomAccessIterator __cut =
2005 *(__first
2006 + (__last
2009 *(__last
2013 else
2015 }
2017 }
2020 void
2023 _Compare __comp)
2024 {
2026 _ValueType;
2029 {
2031 {
2033 // Place the nth largest element in its final position.
2036 }
2038 _RandomAccessIterator __cut =
2041 *(__first
2042 + (__last
2046 __comp)),
2047 __comp);
2050 else
2052 }
2054 }
2056 // nth_element
2058 /**
2059 * @brief Finds the first position in which @a val could be inserted
2060 * without changing the ordering.
2061 * @param first An iterator.
2062 * @param last Another iterator.
2063 * @param val The search term.
2064 * @return An iterator pointing to the first element "not less
2065 * than" @a val, or end() if every element is less than
2066 * @a val.
2067 * @ingroup binarysearch
2068 */
2070 _ForwardIterator
2073 {
2075 _ValueType;
2077 _DistanceType;
2079 // concept requirements
2085 _DistanceType __half;
2086 _ForwardIterator __middle;
2089 {
2094 {
2098 }
2099 else
2101 }
2103 }
2105 /**
2106 * @brief Finds the first position in which @a val could be inserted
2107 * without changing the ordering.
2108 * @param first An iterator.
2109 * @param last Another iterator.
2110 * @param val The search term.
2111 * @param comp A functor to use for comparisons.
2112 * @return An iterator pointing to the first element "not less than" @a val,
2113 * or end() if every element is less than @a val.
2114 * @ingroup binarysearch
2115 *
2116 * The comparison function should have the same effects on ordering as
2117 * the function used for the initial sort.
2118 */
2120 _ForwardIterator
2123 {
2125 _ValueType;
2127 _DistanceType;
2129 // concept requirements
2137 _DistanceType __half;
2138 _ForwardIterator __middle;
2141 {
2146 {
2150 }
2151 else
2153 }
2155 }
2157 /**
2158 * @brief Finds the last position in which @a val could be inserted
2159 * without changing the ordering.
2160 * @param first An iterator.
2161 * @param last Another iterator.
2162 * @param val The search term.
2163 * @return An iterator pointing to the first element greater than @a val,
2164 * or end() if no elements are greater than @a val.
2165 * @ingroup binarysearch
2166 */
2168 _ForwardIterator
2171 {
2173 _ValueType;
2175 _DistanceType;
2177 // concept requirements
2183 _DistanceType __half;
2184 _ForwardIterator __middle;
2187 {
2193 else
2194 {
2198 }
2199 }
2201 }
2203 /**
2204 * @brief Finds the last position in which @a val could be inserted
2205 * without changing the ordering.
2206 * @param first An iterator.
2207 * @param last Another iterator.
2208 * @param val The search term.
2209 * @param comp A functor to use for comparisons.
2210 * @return An iterator pointing to the first element greater than @a val,
2211 * or end() if no elements are greater than @a val.
2212 * @ingroup binarysearch
2213 *
2214 * The comparison function should have the same effects on ordering as
2215 * the function used for the initial sort.
2216 */
2218 _ForwardIterator
2221 {
2223 _ValueType;
2225 _DistanceType;
2227 // concept requirements
2235 _DistanceType __half;
2236 _ForwardIterator __middle;
2239 {
2245 else
2246 {
2250 }
2251 }
2253 }
2255 /**
2256 * @brief Finds the largest subrange in which @a val could be inserted
2257 * at any place in it without changing the ordering.
2258 * @param first An iterator.
2259 * @param last Another iterator.
2260 * @param val The search term.
2261 * @return An pair of iterators defining the subrange.
2262 * @ingroup binarysearch
2263 *
2264 * This is equivalent to
2265 * @code
2266 * std::make_pair(lower_bound(first, last, val),
2267 * upper_bound(first, last, val))
2268 * @endcode
2269 * but does not actually call those functions.
2270 */
2275 {
2277 _ValueType;
2279 _DistanceType;
2281 // concept requirements
2289 _DistanceType __half;
2293 {
2298 {
2302 }
2305 else
2306 {
2311 }
2312 }
2314 }
2316 /**
2317 * @brief Finds the largest subrange in which @a val could be inserted
2318 * at any place in it without changing the ordering.
2319 * @param first An iterator.
2320 * @param last Another iterator.
2321 * @param val The search term.
2322 * @param comp A functor to use for comparisons.
2323 * @return An pair of iterators defining the subrange.
2324 * @ingroup binarysearch
2325 *
2326 * This is equivalent to
2327 * @code
2328 * std::make_pair(lower_bound(first, last, val, comp),
2329 * upper_bound(first, last, val, comp))
2330 * @endcode
2331 * but does not actually call those functions.
2332 */
2337 _Compare __comp)
2338 {
2340 _ValueType;
2342 _DistanceType;
2344 // concept requirements
2356 _DistanceType __half;
2360 {
2365 {
2369 }
2372 else
2373 {
2378 }
2379 }
2381 }
2383 /**
2384 * @brief Determines whether an element exists in a range.
2385 * @param first An iterator.
2386 * @param last Another iterator.
2387 * @param val The search term.
2388 * @return True if @a val (or its equivalent) is in [@a first,@a last ].
2389 * @ingroup binarysearch
2390 *
2391 * Note that this does not actually return an iterator to @a val. For
2392 * that, use std::find or a container's specialized find member functions.
2393 */
2395 bool
2398 {
2400 _ValueType;
2402 // concept requirements
2410 }
2412 /**
2413 * @brief Determines whether an element exists in a range.
2414 * @param first An iterator.
2415 * @param last Another iterator.
2416 * @param val The search term.
2417 * @param comp A functor to use for comparisons.
2418 * @return True if @a val (or its equivalent) is in [@a first,@a last ].
2419 * @ingroup binarysearch
2420 *
2421 * Note that this does not actually return an iterator to @a val. For
2422 * that, use std::find or a container's specialized find member functions.
2423 *
2424 * The comparison function should have the same effects on ordering as
2425 * the function used for the initial sort.
2426 */
2428 bool
2431 {
2433 _ValueType;
2435 // concept requirements
2446 }
2448 // merge
2450 /// This is a helper function for the merge routines.
2452 typename _BidirectionalIterator3>
2453 _BidirectionalIterator3
2455 _BidirectionalIterator1 __last1,
2456 _BidirectionalIterator2 __first2,
2457 _BidirectionalIterator2 __last2,
2458 _BidirectionalIterator3 __result)
2459 {
2467 {
2469 {
2474 }
2475 else
2476 {
2481 }
2482 }
2483 }
2485 /// This is a helper function for the merge routines.
2488 _BidirectionalIterator3
2490 _BidirectionalIterator1 __last1,
2491 _BidirectionalIterator2 __first2,
2492 _BidirectionalIterator2 __last2,
2493 _BidirectionalIterator3 __result,
2494 _Compare __comp)
2495 {
2503 {
2505 {
2510 }
2511 else
2512 {
2517 }
2518 }
2519 }
2521 /// This is a helper function for the merge routines.
2523 typename _Distance>
2524 _BidirectionalIterator1
2526 _BidirectionalIterator1 __middle,
2527 _BidirectionalIterator1 __last,
2529 _BidirectionalIterator2 __buffer,
2530 _Distance __buffer_size)
2531 {
2532 _BidirectionalIterator2 __buffer_end;
2534 {
2538 }
2540 {
2544 }
2545 else
2546 {
2550 }
2551 }
2553 /// This is a helper function for the merge routines.
2555 typename _Pointer>
2556 void
2558 _BidirectionalIterator __middle,
2559 _BidirectionalIterator __last,
2562 {
2564 {
2567 __first);
2568 }
2570 {
2574 }
2575 else
2576 {
2582 {
2588 }
2589 else
2590 {
2596 }
2597 _BidirectionalIterator __new_middle =
2600 __buffer_size);
2606 }
2607 }
2609 /// This is a helper function for the merge routines.
2612 void
2614 _BidirectionalIterator __middle,
2615 _BidirectionalIterator __last,
2618 _Compare __comp)
2619 {
2621 {
2625 }
2627 {
2631 }
2632 else
2633 {
2639 {
2643 __comp);
2645 }
2646 else
2647 {
2651 __comp);
2653 }
2654 _BidirectionalIterator __new_middle =
2657 __buffer_size);
2664 }
2665 }
2667 /// This is a helper function for the merge routines.
2669 void
2671 _BidirectionalIterator __middle,
2672 _BidirectionalIterator __last,
2674 {
2678 {
2682 }
2688 {
2693 }
2694 else
2695 {
2700 }
2708 }
2710 /// This is a helper function for the merge routines.
2712 typename _Compare>
2713 void
2715 _BidirectionalIterator __middle,
2716 _BidirectionalIterator __last,
2718 _Compare __comp)
2719 {
2723 {
2727 }
2733 {
2737 __comp);
2739 }
2740 else
2741 {
2745 __comp);
2747 }
2755 }
2757 /**
2758 * @brief Merges two sorted ranges in place.
2759 * @param first An iterator.
2760 * @param middle Another iterator.
2761 * @param last Another iterator.
2762 * @return Nothing.
2763 *
2764 * Merges two sorted and consecutive ranges, [first,middle) and
2765 * [middle,last), and puts the result in [first,last). The output will
2766 * be sorted. The sort is @e stable, that is, for equivalent
2767 * elements in the two ranges, elements from the first range will always
2768 * come before elements from the second.
2769 *
2770 * If enough additional memory is available, this takes (last-first)-1
2771 * comparisons. Otherwise an NlogN algorithm is used, where N is
2772 * distance(first,last).
2773 */
2775 void
2777 _BidirectionalIterator __middle,
2778 _BidirectionalIterator __last)
2779 {
2781 _ValueType;
2783 _DistanceType;
2785 // concept requirements
2787 _BidirectionalIterator>)
2799 __last);
2802 else
2805 }
2807 /**
2808 * @brief Merges two sorted ranges in place.
2809 * @param first An iterator.
2810 * @param middle Another iterator.
2811 * @param last Another iterator.
2812 * @param comp A functor to use for comparisons.
2813 * @return Nothing.
2814 *
2815 * Merges two sorted and consecutive ranges, [first,middle) and
2816 * [middle,last), and puts the result in [first,last). The output will
2817 * be sorted. The sort is @e stable, that is, for equivalent
2818 * elements in the two ranges, elements from the first range will always
2819 * come before elements from the second.
2820 *
2821 * If enough additional memory is available, this takes (last-first)-1
2822 * comparisons. Otherwise an NlogN algorithm is used, where N is
2823 * distance(first,last).
2824 *
2825 * The comparison function should have the same effects on ordering as
2826 * the function used for the initial sort.
2827 */
2829 void
2831 _BidirectionalIterator __middle,
2832 _BidirectionalIterator __last,
2833 _Compare __comp)
2834 {
2836 _ValueType;
2838 _DistanceType;
2840 // concept requirements
2842 _BidirectionalIterator>)
2855 __last);
2859 else
2862 __comp);
2863 }
2866 typename _Distance>
2867 void
2869 _RandomAccessIterator1 __last,
2870 _RandomAccessIterator2 __result,
2871 _Distance __step_size)
2872 {
2876 {
2880 __result);
2882 }
2887 __result);
2888 }
2892 void
2894 _RandomAccessIterator1 __last,
2896 _Compare __comp)
2897 {
2901 {
2904 __result,
2905 __comp);
2907 }
2912 }
2915 void
2917 _RandomAccessIterator __last,
2918 _Distance __chunk_size)
2919 {
2921 {
2924 }
2926 }
2929 typename _Compare>
2930 void
2932 _RandomAccessIterator __last,
2934 {
2936 {
2939 }
2941 }
2946 void
2948 _RandomAccessIterator __last,
2949 _Pointer __buffer)
2950 {
2952 _Distance;
2961 {
2966 }
2967 }
2970 void
2972 _RandomAccessIterator __last,
2974 {
2976 _Distance;
2985 {
2992 }
2993 }
2996 typename _Distance>
2997 void
2999 _RandomAccessIterator __last,
3001 {
3005 {
3010 }
3011 else
3012 {
3015 }
3020 }
3024 void
3026 _RandomAccessIterator __last,
3028 _Compare __comp)
3029 {
3033 {
3038 }
3039 else
3040 {
3043 }
3048 __comp);
3049 }
3051 /// This is a helper function for the stable sorting routines.
3053 void
3055 _RandomAccessIterator __last)
3056 {
3058 {
3061 }
3068 }
3070 /// This is a helper function for the stable sorting routines.
3072 void
3075 {
3077 {
3080 }
3087 __comp);
3088 }
3090 // stable_sort
3092 // Set algorithms: includes, set_union, set_intersection, set_difference,
3093 // set_symmetric_difference. All of these algorithms have the precondition
3094 // that their input ranges are sorted and the postcondition that their output
3095 // ranges are sorted.
3097 /**
3098 * @brief Determines whether all elements of a sequence exists in a range.
3099 * @param first1 Start of search range.
3100 * @param last1 End of search range.
3101 * @param first2 Start of sequence
3102 * @param last2 End of sequence.
3103 * @return True if each element in [first2,last2) is contained in order
3104 * within [first1,last1). False otherwise.
3105 * @ingroup setoperations
3106 *
3107 * This operation expects both [first1,last1) and [first2,last2) to be
3108 * sorted. Searches for the presence of each element in [first2,last2)
3109 * within [first1,last1). The iterators over each range only move forward,
3110 * so this is a linear algorithm. If an element in [first2,last2) is not
3111 * found before the search iterator reaches @a last2, false is returned.
3112 */
3114 bool
3117 {
3119 _ValueType1;
3121 _ValueType2;
3123 // concept requirements
3136 else
3140 }
3142 /**
3143 * @brief Determines whether all elements of a sequence exists in a range
3144 * using comparison.
3145 * @param first1 Start of search range.
3146 * @param last1 End of search range.
3147 * @param first2 Start of sequence
3148 * @param last2 End of sequence.
3149 * @param comp Comparison function to use.
3150 * @return True if each element in [first2,last2) is contained in order
3151 * within [first1,last1) according to comp. False otherwise.
3152 * @ingroup setoperations
3153 *
3154 * This operation expects both [first1,last1) and [first2,last2) to be
3155 * sorted. Searches for the presence of each element in [first2,last2)
3156 * within [first1,last1), using comp to decide. The iterators over each
3157 * range only move forward, so this is a linear algorithm. If an element
3158 * in [first2,last2) is not found before the search iterator reaches @a
3159 * last2, false is returned.
3160 */
3162 typename _Compare>
3163 bool
3166 _Compare __comp)
3167 {
3169 _ValueType1;
3171 _ValueType2;
3173 // concept requirements
3188 else
3192 }
3194 // nth_element
3195 // merge
3196 // set_difference
3197 // set_intersection
3198 // set_union
3199 // stable_sort
3200 // set_symmetric_difference
3201 // min_element
3202 // max_element
3204 /**
3205 * @brief Permute range into the next "dictionary" ordering.
3206 * @param first Start of range.
3207 * @param last End of range.
3208 * @return False if wrapped to first permutation, true otherwise.
3209 *
3210 * Treats all permutations of the range as a set of "dictionary" sorted
3211 * sequences. Permutes the current sequence into the next one of this set.
3212 * Returns true if there are more sequences to generate. If the sequence
3213 * is the largest of the set, the smallest is generated and false returned.
3214 */
3216 bool
3218 _BidirectionalIterator __last)
3219 {
3220 // concept requirements
3222 _BidirectionalIterator>)
3237 {
3241 {
3244 {}
3248 }
3250 {
3253 }
3254 }
3255 }
3257 /**
3258 * @brief Permute range into the next "dictionary" ordering using
3259 * comparison functor.
3260 * @param first Start of range.
3261 * @param last End of range.
3262 * @param comp A comparison functor.
3263 * @return False if wrapped to first permutation, true otherwise.
3264 *
3265 * Treats all permutations of the range [first,last) as a set of
3266 * "dictionary" sorted sequences ordered by @a comp. Permutes the current
3267 * sequence into the next one of this set. Returns true if there are more
3268 * sequences to generate. If the sequence is the largest of the set, the
3269 * smallest is generated and false returned.
3270 */
3272 bool
3275 {
3276 // concept requirements
3278 _BidirectionalIterator>)
3294 {
3298 {
3301 {}
3305 }
3307 {
3310 }
3311 }
3312 }
3314 /**
3315 * @brief Permute range into the previous "dictionary" ordering.
3316 * @param first Start of range.
3317 * @param last End of range.
3318 * @return False if wrapped to last permutation, true otherwise.
3319 *
3320 * Treats all permutations of the range as a set of "dictionary" sorted
3321 * sequences. Permutes the current sequence into the previous one of this
3322 * set. Returns true if there are more sequences to generate. If the
3323 * sequence is the smallest of the set, the largest is generated and false
3324 * returned.
3325 */
3327 bool
3329 _BidirectionalIterator __last)
3330 {
3331 // concept requirements
3333 _BidirectionalIterator>)
3348 {
3352 {
3355 {}
3359 }
3361 {
3364 }
3365 }
3366 }
3368 /**
3369 * @brief Permute range into the previous "dictionary" ordering using
3370 * comparison functor.
3371 * @param first Start of range.
3372 * @param last End of range.
3373 * @param comp A comparison functor.
3374 * @return False if wrapped to last permutation, true otherwise.
3375 *
3376 * Treats all permutations of the range [first,last) as a set of
3377 * "dictionary" sorted sequences ordered by @a comp. Permutes the current
3378 * sequence into the previous one of this set. Returns true if there are
3379 * more sequences to generate. If the sequence is the smallest of the set,
3380 * the largest is generated and false returned.
3381 */
3383 bool
3386 {
3387 // concept requirements
3389 _BidirectionalIterator>)
3405 {
3409 {
3412 {}
3416 }
3418 {
3421 }
3422 }
3423 }
3425 // replace
3426 // replace_if
3428 /**
3429 * @brief Copy a sequence, replacing each element of one value with another
3430 * value.
3431 * @param first An input iterator.
3432 * @param last An input iterator.
3433 * @param result An output iterator.
3434 * @param old_value The value to be replaced.
3435 * @param new_value The replacement value.
3436 * @return The end of the output sequence, @p result+(last-first).
3437 *
3438 * Copies each element in the input range @p [first,last) to the
3439 * output range @p [result,result+(last-first)) replacing elements
3440 * equal to @p old_value with @p new_value.
3441 */
3443 _OutputIterator
3445 _OutputIterator __result,
3447 {
3448 // concept requirements
3459 else
3462 }
3464 /**
3465 * @brief Copy a sequence, replacing each value for which a predicate
3466 * returns true with another value.
3467 * @param first An input iterator.
3468 * @param last An input iterator.
3469 * @param result An output iterator.
3470 * @param pred A predicate.
3471 * @param new_value The replacement value.
3472 * @return The end of the output sequence, @p result+(last-first).
3473 *
3474 * Copies each element in the range @p [first,last) to the range
3475 * @p [result,result+(last-first)) replacing elements for which
3476 * @p pred returns true with @p new_value.
3477 */
3480 _OutputIterator
3482 _OutputIterator __result,
3484 {
3485 // concept requirements
3496 else
3499 }
3501 #ifdef __GXX_EXPERIMENTAL_CXX0X__
3502 /**
3503 * @brief Determines whether the elements of a sequence are sorted.
3504 * @param first An iterator.
3505 * @param last Another iterator.
3506 * @return True if the elements are sorted, false otherwise.
3507 */
3513 /**
3514 * @brief Determines whether the elements of a sequence are sorted
3515 * according to a comparison functor.
3516 * @param first An iterator.
3517 * @param last Another iterator.
3518 * @param comp A comparison functor.
3519 * @return True if the elements are sorted, false otherwise.
3520 */
3524 _Compare __comp)
3527 /**
3528 * @brief Determines the end of a sorted sequence.
3529 * @param first An iterator.
3530 * @param last Another iterator.
3531 * @return An iterator pointing to the last iterator i in [first, last)
3532 * for which the range [first, i) is sorted.
3533 */
3535 _ForwardIterator
3537 {
3538 // concept requirements
3552 }
3554 /**
3555 * @brief Determines the end of a sorted sequence using comparison functor.
3556 * @param first An iterator.
3557 * @param last Another iterator.
3558 * @param comp A comparison functor.
3559 * @return An iterator pointing to the last iterator i in [first, last)
3560 * for which the range [first, i) is sorted.
3561 */
3563 _ForwardIterator
3565 _Compare __comp)
3566 {
3567 // concept requirements
3582 }
3584 /**
3585 * @brief Determines min and max at once as an ordered pair.
3586 * @param a A thing of arbitrary type.
3587 * @param b Another thing of arbitrary type.
3588 * @return A pair(b, a) if b is smaller than a, pair(a, b) otherwise.
3589 */
3593 {
3594 // concept requirements
3599 }
3601 /**
3602 * @brief Determines min and max at once as an ordered pair.
3603 * @param a A thing of arbitrary type.
3604 * @param b Another thing of arbitrary type.
3605 * @param comp A @link s20_3_3_comparisons comparison functor@endlink.
3606 * @return A pair(b, a) if b is smaller than a, pair(a, b) otherwise.
3607 */
3611 {
3614 }
3616 /**
3617 * @brief Return a pair of iterators pointing to the minimum and maximum
3618 * elements in a range.
3619 * @param first Start of range.
3620 * @param last End of range.
3621 * @return make_pair(m, M), where m is the first iterator i in
3622 * [first, last) such that no other element in the range is
3623 * smaller, and where M is the last iterator i in [first, last)
3624 * such that no other element in the range is larger.
3625 */
3629 {
3630 // concept requirements
3643 {
3646 }
3647 else
3648 {
3651 }
3657 {
3660 {
3666 }
3669 {
3674 }
3675 else
3676 {
3681 }
3685 }
3688 }
3690 /**
3691 * @brief Return a pair of iterators pointing to the minimum and maximum
3692 * elements in a range.
3693 * @param first Start of range.
3694 * @param last End of range.
3695 * @param comp Comparison functor.
3696 * @return make_pair(m, M), where m is the first iterator i in
3697 * [first, last) such that no other element in the range is
3698 * smaller, and where M is the last iterator i in [first, last)
3699 * such that no other element in the range is larger.
3700 */
3704 _Compare __comp)
3705 {
3706 // concept requirements
3720 {
3723 }
3724 else
3725 {
3728 }
3734 {
3737 {
3743 }
3746 {
3751 }
3752 else
3753 {
3758 }
3762 }
3765 }
3768 _GLIBCXX_END_NAMESPACE
3772 /**
3773 * @brief Apply a function to every element of a sequence.
3774 * @param first An input iterator.
3775 * @param last An input iterator.
3776 * @param f A unary function object.
3777 * @return @p f.
3778 *
3779 * Applies the function object @p f to each element in the range
3780 * @p [first,last). @p f must not modify the order of the sequence.
3781 * If @p f has a return value it is ignored.
3782 */
3784 _Function
3786 {
3787 // concept requirements
3793 }
3795 /**
3796 * @brief Find the first occurrence of a value in a sequence.
3797 * @param first An input iterator.
3798 * @param last An input iterator.
3799 * @param val The value to find.
3800 * @return The first iterator @c i in the range @p [first,last)
3801 * such that @c *i == @p val, or @p last if no such iterator exists.
3802 */
3804 inline _InputIterator
3807 {
3808 // concept requirements
3815 }
3817 /**
3818 * @brief Find the first element in a sequence for which a
3819 * predicate is true.
3820 * @param first An input iterator.
3821 * @param last An input iterator.
3822 * @param pred A predicate.
3823 * @return The first iterator @c i in the range @p [first,last)
3824 * such that @p pred(*i) is true, or @p last if no such iterator exists.
3825 */
3827 inline _InputIterator
3829 _Predicate __pred)
3830 {
3831 // concept requirements
3838 }
3840 /**
3841 * @brief Find element from a set in a sequence.
3842 * @param first1 Start of range to search.
3843 * @param last1 End of range to search.
3844 * @param first2 Start of match candidates.
3845 * @param last2 End of match candidates.
3846 * @return The first iterator @c i in the range
3847 * @p [first1,last1) such that @c *i == @p *(i2) such that i2 is an
3848 * iterator in [first2,last2), or @p last1 if no such iterator exists.
3849 *
3850 * Searches the range @p [first1,last1) for an element that is equal to
3851 * some element in the range [first2,last2). If found, returns an iterator
3852 * in the range [first1,last1), otherwise returns @p last1.
3853 */
3855 _InputIterator
3858 {
3859 // concept requirements
3873 }
3875 /**
3876 * @brief Find element from a set in a sequence using a predicate.
3877 * @param first1 Start of range to search.
3878 * @param last1 End of range to search.
3879 * @param first2 Start of match candidates.
3880 * @param last2 End of match candidates.
3881 * @param comp Predicate to use.
3882 * @return The first iterator @c i in the range
3883 * @p [first1,last1) such that @c comp(*i, @p *(i2)) is true and i2 is an
3884 * iterator in [first2,last2), or @p last1 if no such iterator exists.
3885 *
3887 * Searches the range @p [first1,last1) for an element that is
3888 * equal to some element in the range [first2,last2). If found,
3889 * returns an iterator in the range [first1,last1), otherwise
3890 * returns @p last1.
3891 */
3893 typename _BinaryPredicate>
3894 _InputIterator
3897 _BinaryPredicate __comp)
3898 {
3899 // concept requirements
3913 }
3915 /**
3916 * @brief Find two adjacent values in a sequence that are equal.
3917 * @param first A forward iterator.
3918 * @param last A forward iterator.
3919 * @return The first iterator @c i such that @c i and @c i+1 are both
3920 * valid iterators in @p [first,last) and such that @c *i == @c *(i+1),
3921 * or @p last if no such iterator exists.
3922 */
3924 _ForwardIterator
3926 {
3927 // concept requirements
3936 {
3940 }
3942 }
3944 /**
3945 * @brief Find two adjacent values in a sequence using a predicate.
3946 * @param first A forward iterator.
3947 * @param last A forward iterator.
3948 * @param binary_pred A binary predicate.
3949 * @return The first iterator @c i such that @c i and @c i+1 are both
3950 * valid iterators in @p [first,last) and such that
3951 * @p binary_pred(*i,*(i+1)) is true, or @p last if no such iterator
3952 * exists.
3953 */
3955 _ForwardIterator
3957 _BinaryPredicate __binary_pred)
3958 {
3959 // concept requirements
3969 {
3973 }
3975 }
3977 /**
3978 * @brief Count the number of copies of a value in a sequence.
3979 * @param first An input iterator.
3980 * @param last An input iterator.
3981 * @param value The value to be counted.
3982 * @return The number of iterators @c i in the range @p [first,last)
3983 * for which @c *i == @p value
3984 */
3988 {
3989 // concept requirements
3999 }
4001 /**
4002 * @brief Count the elements of a sequence for which a predicate is true.
4003 * @param first An input iterator.
4004 * @param last An input iterator.
4005 * @param pred A predicate.
4006 * @return The number of iterators @c i in the range @p [first,last)
4007 * for which @p pred(*i) is true.
4008 */
4012 {
4013 // concept requirements
4023 }
4025 /**
4026 * @brief Search a sequence for a matching sub-sequence.
4027 * @param first1 A forward iterator.
4028 * @param last1 A forward iterator.
4029 * @param first2 A forward iterator.
4030 * @param last2 A forward iterator.
4031 * @return The first iterator @c i in the range
4032 * @p [first1,last1-(last2-first2)) such that @c *(i+N) == @p *(first2+N)
4033 * for each @c N in the range @p [0,last2-first2), or @p last1 if no
4034 * such iterator exists.
4035 *
4036 * Searches the range @p [first1,last1) for a sub-sequence that compares
4037 * equal value-by-value with the sequence given by @p [first2,last2) and
4038 * returns an iterator to the first element of the sub-sequence, or
4039 * @p last1 if the sub-sequence is not found.
4040 *
4041 * Because the sub-sequence must lie completely within the range
4042 * @p [first1,last1) it must start at a position less than
4043 * @p last1-(last2-first2) where @p last2-first2 is the length of the
4044 * sub-sequence.
4045 * This means that the returned iterator @c i will be in the range
4046 * @p [first1,last1-(last2-first2))
4047 */
4049 _ForwardIterator1
4052 {
4053 // concept requirements
4062 // Test for empty ranges
4066 // Test for a pattern of length 1.
4071 // General case.
4072 _ForwardIterator2 __p;
4076 {
4087 {
4092 }
4094 }
4096 }
4098 /**
4099 * @brief Search a sequence for a matching sub-sequence using a predicate.
4100 * @param first1 A forward iterator.
4101 * @param last1 A forward iterator.
4102 * @param first2 A forward iterator.
4103 * @param last2 A forward iterator.
4104 * @param predicate A binary predicate.
4105 * @return The first iterator @c i in the range
4106 * @p [first1,last1-(last2-first2)) such that
4107 * @p predicate(*(i+N),*(first2+N)) is true for each @c N in the range
4108 * @p [0,last2-first2), or @p last1 if no such iterator exists.
4109 *
4110 * Searches the range @p [first1,last1) for a sub-sequence that compares
4111 * equal value-by-value with the sequence given by @p [first2,last2),
4112 * using @p predicate to determine equality, and returns an iterator
4113 * to the first element of the sub-sequence, or @p last1 if no such
4114 * iterator exists.
4115 *
4116 * @see search(_ForwardIter1, _ForwardIter1, _ForwardIter2, _ForwardIter2)
4117 */
4119 typename _BinaryPredicate>
4120 _ForwardIterator1
4123 _BinaryPredicate __predicate)
4124 {
4125 // concept requirements
4134 // Test for empty ranges
4138 // Test for a pattern of length 1.
4141 {
4146 }
4148 // General case.
4149 _ForwardIterator2 __p;
4153 {
4166 {
4171 }
4173 }
4175 }
4178 /**
4179 * @brief Search a sequence for a number of consecutive values.
4180 * @param first A forward iterator.
4181 * @param last A forward iterator.
4182 * @param count The number of consecutive values.
4183 * @param val The value to find.
4184 * @return The first iterator @c i in the range @p [first,last-count)
4185 * such that @c *(i+N) == @p val for each @c N in the range @p [0,count),
4186 * or @p last if no such iterator exists.
4187 *
4188 * Searches the range @p [first,last) for @p count consecutive elements
4189 * equal to @p val.
4190 */
4192 _ForwardIterator
4195 {
4196 // concept requirements
4208 }
4211 /**
4212 * @brief Search a sequence for a number of consecutive values using a
4213 * predicate.
4214 * @param first A forward iterator.
4215 * @param last A forward iterator.
4216 * @param count The number of consecutive values.
4217 * @param val The value to find.
4218 * @param binary_pred A binary predicate.
4219 * @return The first iterator @c i in the range @p [first,last-count)
4220 * such that @p binary_pred(*(i+N),val) is true for each @c N in the
4221 * range @p [0,count), or @p last if no such iterator exists.
4222 *
4223 * Searches the range @p [first,last) for @p count consecutive elements
4224 * for which the predicate returns true.
4225 */
4227 typename _BinaryPredicate>
4228 _ForwardIterator
4231 _BinaryPredicate __binary_pred)
4232 {
4233 // concept requirements
4242 {
4246 }
4249 }
4252 /**
4253 * @brief Perform an operation on a sequence.
4254 * @param first An input iterator.
4255 * @param last An input iterator.
4256 * @param result An output iterator.
4257 * @param unary_op A unary operator.
4258 * @return An output iterator equal to @p result+(last-first).
4259 *
4260 * Applies the operator to each element in the input range and assigns
4261 * the results to successive elements of the output sequence.
4262 * Evaluates @p *(result+N)=unary_op(*(first+N)) for each @c N in the
4263 * range @p [0,last-first).
4264 *
4265 * @p unary_op must not alter its argument.
4266 */
4268 typename _UnaryOperation>
4269 _OutputIterator
4272 {
4273 // concept requirements
4276 // "the type returned by a _UnaryOperation"
4283 }
4285 /**
4286 * @brief Perform an operation on corresponding elements of two sequences.
4287 * @param first1 An input iterator.
4288 * @param last1 An input iterator.
4289 * @param first2 An input iterator.
4290 * @param result An output iterator.
4291 * @param binary_op A binary operator.
4292 * @return An output iterator equal to @p result+(last-first).
4293 *
4294 * Applies the operator to the corresponding elements in the two
4295 * input ranges and assigns the results to successive elements of the
4296 * output sequence.
4297 * Evaluates @p *(result+N)=binary_op(*(first1+N),*(first2+N)) for each
4298 * @c N in the range @p [0,last1-first1).
4299 *
4300 * @p binary_op must not alter either of its arguments.
4301 */
4304 _OutputIterator
4307 _BinaryOperation __binary_op)
4308 {
4309 // concept requirements
4313 // "the type returned by a _BinaryOperation"
4320 }
4322 /**
4323 * @brief Replace each occurrence of one value in a sequence with another
4324 * value.
4325 * @param first A forward iterator.
4326 * @param last A forward iterator.
4327 * @param old_value The value to be replaced.
4328 * @param new_value The replacement value.
4329 * @return replace() returns no value.
4330 *
4331 * For each iterator @c i in the range @p [first,last) if @c *i ==
4332 * @p old_value then the assignment @c *i = @p new_value is performed.
4333 */
4335 void
4338 {
4339 // concept requirements
4341 _ForwardIterator>)
4351 }
4353 /**
4354 * @brief Replace each value in a sequence for which a predicate returns
4355 * true with another value.
4356 * @param first A forward iterator.
4357 * @param last A forward iterator.
4358 * @param pred A predicate.
4359 * @param new_value The replacement value.
4360 * @return replace_if() returns no value.
4361 *
4362 * For each iterator @c i in the range @p [first,last) if @p pred(*i)
4363 * is true then the assignment @c *i = @p new_value is performed.
4364 */
4366 void
4369 {
4370 // concept requirements
4372 _ForwardIterator>)
4382 }
4384 /**
4385 * @brief Assign the result of a function object to each value in a
4386 * sequence.
4387 * @param first A forward iterator.
4388 * @param last A forward iterator.
4389 * @param gen A function object taking no arguments and returning
4390 * std::iterator_traits<_ForwardIterator>::value_type
4391 * @return generate() returns no value.
4392 *
4393 * Performs the assignment @c *i = @p gen() for each @c i in the range
4394 * @p [first,last).
4395 */
4397 void
4399 _Generator __gen)
4400 {
4401 // concept requirements
4409 }
4411 /**
4412 * @brief Assign the result of a function object to each value in a
4413 * sequence.
4414 * @param first A forward iterator.
4415 * @param n The length of the sequence.
4416 * @param gen A function object taking no arguments and returning
4417 * std::iterator_traits<_ForwardIterator>::value_type
4418 * @return The end of the sequence, @p first+n
4419 *
4420 * Performs the assignment @c *i = @p gen() for each @c i in the range
4421 * @p [first,first+n).
4422 */
4424 _OutputIterator
4426 {
4427 // concept requirements
4429 // "the type returned by a _Generator"
4435 }
4438 /**
4439 * @brief Copy a sequence, removing consecutive duplicate values.
4440 * @param first An input iterator.
4441 * @param last An input iterator.
4442 * @param result An output iterator.
4443 * @return An iterator designating the end of the resulting sequence.
4444 *
4445 * Copies each element in the range @p [first,last) to the range
4446 * beginning at @p result, except that only the first element is copied
4447 * from groups of consecutive elements that compare equal.
4448 * unique_copy() is stable, so the relative order of elements that are
4449 * copied is unchanged.
4450 *
4451 * _GLIBCXX_RESOLVE_LIB_DEFECTS
4452 * DR 241. Does unique_copy() require CopyConstructible and Assignable?
4453 *
4454 * _GLIBCXX_RESOLVE_LIB_DEFECTS
4455 * DR 538. 241 again: Does unique_copy() require CopyConstructible and
4456 * Assignable?
4457 */
4459 inline _OutputIterator
4461 _OutputIterator __result)
4462 {
4463 // concept requirements
4476 }
4478 /**
4479 * @brief Copy a sequence, removing consecutive values using a predicate.
4480 * @param first An input iterator.
4481 * @param last An input iterator.
4482 * @param result An output iterator.
4483 * @param binary_pred A binary predicate.
4484 * @return An iterator designating the end of the resulting sequence.
4485 *
4486 * Copies each element in the range @p [first,last) to the range
4487 * beginning at @p result, except that only the first element is copied
4488 * from groups of consecutive elements for which @p binary_pred returns
4489 * true.
4490 * unique_copy() is stable, so the relative order of elements that are
4491 * copied is unchanged.
4492 *
4493 * _GLIBCXX_RESOLVE_LIB_DEFECTS
4494 * DR 241. Does unique_copy() require CopyConstructible and Assignable?
4495 */
4497 typename _BinaryPredicate>
4498 inline _OutputIterator
4500 _OutputIterator __result,
4501 _BinaryPredicate __binary_pred)
4502 {
4503 // concept requirements -- predicates checked later
4514 }
4517 /**
4518 * @brief Randomly shuffle the elements of a sequence.
4519 * @param first A forward iterator.
4520 * @param last A forward iterator.
4521 * @return Nothing.
4522 *
4523 * Reorder the elements in the range @p [first,last) using a random
4524 * distribution, so that every possible ordering of the sequence is
4525 * equally likely.
4526 */
4530 {
4531 // concept requirements
4533 _RandomAccessIterator>)
4539 }
4541 /**
4542 * @brief Shuffle the elements of a sequence using a random number
4543 * generator.
4544 * @param first A forward iterator.
4545 * @param last A forward iterator.
4546 * @param rand The RNG functor or function.
4547 * @return Nothing.
4548 *
4549 * Reorders the elements in the range @p [first,last) using @p rand to
4550 * provide a random distribution. Calling @p rand(N) for a positive
4551 * integer @p N should return a randomly chosen integer from the
4552 * range [0,N).
4553 */
4555 void
4558 {
4559 // concept requirements
4561 _RandomAccessIterator>)
4568 }
4571 /**
4572 * @brief Move elements for which a predicate is true to the beginning
4573 * of a sequence.
4574 * @param first A forward iterator.
4575 * @param last A forward iterator.
4576 * @param pred A predicate functor.
4577 * @return An iterator @p middle such that @p pred(i) is true for each
4578 * iterator @p i in the range @p [first,middle) and false for each @p i
4579 * in the range @p [middle,last).
4580 *
4581 * @p pred must not modify its operand. @p partition() does not preserve
4582 * the relative ordering of elements in each group, use
4583 * @p stable_partition() if this is needed.
4584 */
4586 inline _ForwardIterator
4588 _Predicate __pred)
4589 {
4590 // concept requirements
4592 _ForwardIterator>)
4599 }
4603 /**
4604 * @brief Sort the smallest elements of a sequence.
4605 * @param first An iterator.
4606 * @param middle Another iterator.
4607 * @param last Another iterator.
4608 * @return Nothing.
4609 *
4610 * Sorts the smallest @p (middle-first) elements in the range
4611 * @p [first,last) and moves them to the range @p [first,middle). The
4612 * order of the remaining elements in the range @p [middle,last) is
4613 * undefined.
4614 * After the sort if @p i and @j are iterators in the range
4615 * @p [first,middle) such that @i precedes @j and @k is an iterator in
4616 * the range @p [middle,last) then @p *j<*i and @p *k<*i are both false.
4617 */
4621 _RandomAccessIterator __middle,
4622 _RandomAccessIterator __last)
4623 {
4625 _ValueType;
4627 // concept requirements
4629 _RandomAccessIterator>)
4636 }
4638 /**
4639 * @brief Sort the smallest elements of a sequence using a predicate
4640 * for comparison.
4641 * @param first An iterator.
4642 * @param middle Another iterator.
4643 * @param last Another iterator.
4644 * @param comp A comparison functor.
4645 * @return Nothing.
4646 *
4647 * Sorts the smallest @p (middle-first) elements in the range
4648 * @p [first,last) and moves them to the range @p [first,middle). The
4649 * order of the remaining elements in the range @p [middle,last) is
4650 * undefined.
4651 * After the sort if @p i and @j are iterators in the range
4652 * @p [first,middle) such that @i precedes @j and @k is an iterator in
4653 * the range @p [middle,last) then @p *comp(j,*i) and @p comp(*k,*i)
4654 * are both false.
4655 */
4659 _RandomAccessIterator __middle,
4660 _RandomAccessIterator __last,
4661 _Compare __comp)
4662 {
4664 _ValueType;
4666 // concept requirements
4668 _RandomAccessIterator>)
4676 }
4678 /**
4679 * @brief Sort a sequence just enough to find a particular position.
4680 * @param first An iterator.
4681 * @param nth Another iterator.
4682 * @param last Another iterator.
4683 * @return Nothing.
4684 *
4685 * Rearranges the elements in the range @p [first,last) so that @p *nth
4686 * is the same element that would have been in that position had the
4687 * whole sequence been sorted.
4688 * whole sequence been sorted. The elements either side of @p *nth are
4689 * not completely sorted, but for any iterator @i in the range
4690 * @p [first,nth) and any iterator @j in the range @p [nth,last) it
4691 * holds that @p *j<*i is false.
4692 */
4696 _RandomAccessIterator __last)
4697 {
4699 _ValueType;
4701 // concept requirements
4703 _RandomAccessIterator>)
4713 }
4715 /**
4716 * @brief Sort a sequence just enough to find a particular position
4717 * using a predicate for comparison.
4718 * @param first An iterator.
4719 * @param nth Another iterator.
4720 * @param last Another iterator.
4721 * @param comp A comparison functor.
4722 * @return Nothing.
4723 *
4724 * Rearranges the elements in the range @p [first,last) so that @p *nth
4725 * is the same element that would have been in that position had the
4726 * whole sequence been sorted. The elements either side of @p *nth are
4727 * not completely sorted, but for any iterator @i in the range
4728 * @p [first,nth) and any iterator @j in the range @p [nth,last) it
4729 * holds that @p comp(*j,*i) is false.
4730 */
4735 {
4737 _ValueType;
4739 // concept requirements
4741 _RandomAccessIterator>)
4752 }
4755 /**
4756 * @brief Sort the elements of a sequence.
4757 * @param first An iterator.
4758 * @param last Another iterator.
4759 * @return Nothing.
4760 *
4761 * Sorts the elements in the range @p [first,last) in ascending order,
4762 * such that @p *(i+1)<*i is false for each iterator @p i in the range
4763 * @p [first,last-1).
4764 *
4765 * The relative ordering of equivalent elements is not preserved, use
4766 * @p stable_sort() if this is needed.
4767 */
4771 {
4773 _ValueType;
4775 // concept requirements
4777 _RandomAccessIterator>)
4782 {
4786 }
4787 }
4789 /**
4790 * @brief Sort the elements of a sequence using a predicate for comparison.
4791 * @param first An iterator.
4792 * @param last Another iterator.
4793 * @param comp A comparison functor.
4794 * @return Nothing.
4795 *
4796 * Sorts the elements in the range @p [first,last) in ascending order,
4797 * such that @p comp(*(i+1),*i) is false for every iterator @p i in the
4798 * range @p [first,last-1).
4799 *
4800 * The relative ordering of equivalent elements is not preserved, use
4801 * @p stable_sort() if this is needed.
4802 */
4806 _Compare __comp)
4807 {
4809 _ValueType;
4811 // concept requirements
4813 _RandomAccessIterator>)
4815 _ValueType>)
4819 {
4823 }
4824 }
4826 /**
4827 * @brief Merges two sorted ranges.
4828 * @param first1 An iterator.
4829 * @param first2 Another iterator.
4830 * @param last1 Another iterator.
4831 * @param last2 Another iterator.
4832 * @param result An iterator pointing to the end of the merged range.
4833 * @return An iterator pointing to the first element "not less
4834 * than" @a val.
4835 *
4836 * Merges the ranges [first1,last1) and [first2,last2) into the sorted range
4837 * [result, result + (last1-first1) + (last2-first2)). Both input ranges
4838 * must be sorted, and the output range must not overlap with either of
4839 * the input ranges. The sort is @e stable, that is, for equivalent
4840 * elements in the two ranges, elements from the first range will always
4841 * come before elements from the second.
4842 */
4844 typename _OutputIterator>
4845 _OutputIterator
4848 _OutputIterator __result)
4849 {
4851 _ValueType1;
4853 _ValueType2;
4855 // concept requirements
4859 _ValueType1>)
4861 _ValueType2>)
4867 {
4869 {
4872 }
4873 else
4874 {
4877 }
4879 }
4881 __result));
4882 }
4884 /**
4885 * @brief Merges two sorted ranges.
4886 * @param first1 An iterator.
4887 * @param first2 Another iterator.
4888 * @param last1 Another iterator.
4889 * @param last2 Another iterator.
4890 * @param result An iterator pointing to the end of the merged range.
4891 * @param comp A functor to use for comparisons.
4892 * @return An iterator pointing to the first element "not less
4893 * than" @a val.
4894 *
4895 * Merges the ranges [first1,last1) and [first2,last2) into the sorted range
4896 * [result, result + (last1-first1) + (last2-first2)). Both input ranges
4897 * must be sorted, and the output range must not overlap with either of
4898 * the input ranges. The sort is @e stable, that is, for equivalent
4899 * elements in the two ranges, elements from the first range will always
4900 * come before elements from the second.
4901 *
4902 * The comparison function should have the same effects on ordering as
4903 * the function used for the initial sort.
4904 */
4907 _OutputIterator
4911 {
4913 _ValueType1;
4915 _ValueType2;
4917 // concept requirements
4921 _ValueType1>)
4923 _ValueType2>)
4930 {
4932 {
4935 }
4936 else
4937 {
4940 }
4942 }
4944 __result));
4945 }
4948 /**
4949 * @brief Sort the elements of a sequence, preserving the relative order
4950 * of equivalent elements.
4951 * @param first An iterator.
4952 * @param last Another iterator.
4953 * @return Nothing.
4954 *
4955 * Sorts the elements in the range @p [first,last) in ascending order,
4956 * such that @p *(i+1)<*i is false for each iterator @p i in the range
4957 * @p [first,last-1).
4958 *
4959 * The relative ordering of equivalent elements is preserved, so any two
4960 * elements @p x and @p y in the range @p [first,last) such that
4961 * @p x<y is false and @p y<x is false will have the same relative
4962 * ordering after calling @p stable_sort().
4963 */
4967 {
4969 _ValueType;
4971 _DistanceType;
4973 // concept requirements
4975 _RandomAccessIterator>)
4980 __last);
4983 else
4986 }
4988 /**
4989 * @brief Sort the elements of a sequence using a predicate for comparison,
4990 * preserving the relative order of equivalent elements.
4991 * @param first An iterator.
4992 * @param last Another iterator.
4993 * @param comp A comparison functor.
4994 * @return Nothing.
4995 *
4996 * Sorts the elements in the range @p [first,last) in ascending order,
4997 * such that @p comp(*(i+1),*i) is false for each iterator @p i in the
4998 * range @p [first,last-1).
4999 *
5000 * The relative ordering of equivalent elements is preserved, so any two
5001 * elements @p x and @p y in the range @p [first,last) such that
5002 * @p comp(x,y) is false and @p comp(y,x) is false will have the same
5003 * relative ordering after calling @p stable_sort().
5004 */
5008 _Compare __comp)
5009 {
5011 _ValueType;
5013 _DistanceType;
5015 // concept requirements
5017 _RandomAccessIterator>)
5019 _ValueType,
5020 _ValueType>)
5024 __last);
5027 else
5030 }
5033 /**
5034 * @brief Return the union of two sorted ranges.
5035 * @param first1 Start of first range.
5036 * @param last1 End of first range.
5037 * @param first2 Start of second range.
5038 * @param last2 End of second range.
5039 * @return End of the output range.
5040 * @ingroup setoperations
5041 *
5042 * This operation iterates over both ranges, copying elements present in
5043 * each range in order to the output range. Iterators increment for each
5044 * range. When the current element of one range is less than the other,
5045 * that element is copied and the iterator advanced. If an element is
5046 * contained in both ranges, the element from the first range is copied and
5047 * both ranges advance. The output range may not overlap either input
5048 * range.
5049 */
5051 typename _OutputIterator>
5052 _OutputIterator
5055 _OutputIterator __result)
5056 {
5058 _ValueType1;
5060 _ValueType2;
5062 // concept requirements
5066 _ValueType1>)
5068 _ValueType2>)
5075 {
5077 {
5080 }
5082 {
5085 }
5086 else
5087 {
5091 }
5093 }
5095 __result));
5096 }
5098 /**
5099 * @brief Return the union of two sorted ranges using a comparison functor.
5100 * @param first1 Start of first range.
5101 * @param last1 End of first range.
5102 * @param first2 Start of second range.
5103 * @param last2 End of second range.
5104 * @param comp The comparison functor.
5105 * @return End of the output range.
5106 * @ingroup setoperations
5107 *
5108 * This operation iterates over both ranges, copying elements present in
5109 * each range in order to the output range. Iterators increment for each
5110 * range. When the current element of one range is less than the other
5111 * according to @a comp, that element is copied and the iterator advanced.
5112 * If an equivalent element according to @a comp is contained in both
5113 * ranges, the element from the first range is copied and both ranges
5114 * advance. The output range may not overlap either input range.
5115 */
5118 _OutputIterator
5122 {
5124 _ValueType1;
5126 _ValueType2;
5128 // concept requirements
5132 _ValueType1>)
5134 _ValueType2>)
5143 {
5145 {
5148 }
5150 {
5153 }
5154 else
5155 {
5159 }
5161 }
5163 __result));
5164 }
5166 /**
5167 * @brief Return the intersection of two sorted ranges.
5168 * @param first1 Start of first range.
5169 * @param last1 End of first range.
5170 * @param first2 Start of second range.
5171 * @param last2 End of second range.
5172 * @return End of the output range.
5173 * @ingroup setoperations
5174 *
5175 * This operation iterates over both ranges, copying elements present in
5176 * both ranges in order to the output range. Iterators increment for each
5177 * range. When the current element of one range is less than the other,
5178 * that iterator advances. If an element is contained in both ranges, the
5179 * element from the first range is copied and both ranges advance. The
5180 * output range may not overlap either input range.
5181 */
5183 typename _OutputIterator>
5184 _OutputIterator
5187 _OutputIterator __result)
5188 {
5190 _ValueType1;
5192 _ValueType2;
5194 // concept requirements
5198 _ValueType1>)
5209 else
5210 {
5215 }
5217 }
5219 /**
5220 * @brief Return the intersection of two sorted ranges using comparison
5221 * functor.
5222 * @param first1 Start of first range.
5223 * @param last1 End of first range.
5224 * @param first2 Start of second range.
5225 * @param last2 End of second range.
5226 * @param comp The comparison functor.
5227 * @return End of the output range.
5228 * @ingroup setoperations
5229 *
5230 * This operation iterates over both ranges, copying elements present in
5231 * both ranges in order to the output range. Iterators increment for each
5232 * range. When the current element of one range is less than the other
5233 * according to @a comp, that iterator advances. If an element is
5234 * contained in both ranges according to @a comp, the element from the
5235 * first range is copied and both ranges advance. The output range may not
5236 * overlap either input range.
5237 */
5240 _OutputIterator
5244 {
5246 _ValueType1;
5248 _ValueType2;
5250 // concept requirements
5254 _ValueType1>)
5267 else
5268 {
5273 }
5275 }
5277 /**
5278 * @brief Return the difference of two sorted ranges.
5279 * @param first1 Start of first range.
5280 * @param last1 End of first range.
5281 * @param first2 Start of second range.
5282 * @param last2 End of second range.
5283 * @return End of the output range.
5284 * @ingroup setoperations
5285 *
5286 * This operation iterates over both ranges, copying elements present in
5287 * the first range but not the second in order to the output range.
5288 * Iterators increment for each range. When the current element of the
5289 * first range is less than the second, that element is copied and the
5290 * iterator advances. If the current element of the second range is less,
5291 * the iterator advances, but no element is copied. If an element is
5292 * contained in both ranges, no elements are copied and both ranges
5293 * advance. The output range may not overlap either input range.
5294 */
5296 typename _OutputIterator>
5297 _OutputIterator
5300 _OutputIterator __result)
5301 {
5303 _ValueType1;
5305 _ValueType2;
5307 // concept requirements
5311 _ValueType1>)
5319 {
5323 }
5326 else
5327 {
5330 }
5332 }
5334 /**
5335 * @brief Return the difference of two sorted ranges using comparison
5336 * functor.
5337 * @param first1 Start of first range.
5338 * @param last1 End of first range.
5339 * @param first2 Start of second range.
5340 * @param last2 End of second range.
5341 * @param comp The comparison functor.
5342 * @return End of the output range.
5343 * @ingroup setoperations
5344 *
5345 * This operation iterates over both ranges, copying elements present in
5346 * the first range but not the second in order to the output range.
5347 * Iterators increment for each range. When the current element of the
5348 * first range is less than the second according to @a comp, that element
5349 * is copied and the iterator advances. If the current element of the
5350 * second range is less, no element is copied and the iterator advances.
5351 * If an element is contained in both ranges according to @a comp, no
5352 * elements are copied and both ranges advance. The output range may not
5353 * overlap either input range.
5354 */
5357 _OutputIterator
5361 {
5363 _ValueType1;
5365 _ValueType2;
5367 // concept requirements
5371 _ValueType1>)
5381 {
5385 }
5388 else
5389 {
5392 }
5394 }
5396 /**
5397 * @brief Return the symmetric difference of two sorted ranges.
5398 * @param first1 Start of first range.
5399 * @param last1 End of first range.
5400 * @param first2 Start of second range.
5401 * @param last2 End of second range.
5402 * @return End of the output range.
5403 * @ingroup setoperations
5404 *
5405 * This operation iterates over both ranges, copying elements present in
5406 * one range but not the other in order to the output range. Iterators
5407 * increment for each range. When the current element of one range is less
5408 * than the other, that element is copied and the iterator advances. If an
5409 * element is contained in both ranges, no elements are copied and both
5410 * ranges advance. The output range may not overlap either input range.
5411 */
5413 typename _OutputIterator>
5414 _OutputIterator
5417 _OutputIterator __result)
5418 {
5420 _ValueType1;
5422 _ValueType2;
5424 // concept requirements
5428 _ValueType1>)
5430 _ValueType2>)
5438 {
5442 }
5444 {
5448 }
5449 else
5450 {
5453 }
5456 }
5458 /**
5459 * @brief Return the symmetric difference of two sorted ranges using
5460 * comparison functor.
5461 * @param first1 Start of first range.
5462 * @param last1 End of first range.
5463 * @param first2 Start of second range.
5464 * @param last2 End of second range.
5465 * @param comp The comparison functor.
5466 * @return End of the output range.
5467 * @ingroup setoperations
5468 *
5469 * This operation iterates over both ranges, copying elements present in
5470 * one range but not the other in order to the output range. Iterators
5471 * increment for each range. When the current element of one range is less
5472 * than the other according to @a comp, that element is copied and the
5473 * iterator advances. If an element is contained in both ranges according
5474 * to @a comp, no elements are copied and both ranges advance. The output
5475 * range may not overlap either input range.
5476 */
5479 _OutputIterator
5482 _OutputIterator __result,
5483 _Compare __comp)
5484 {
5486 _ValueType1;
5488 _ValueType2;
5490 // concept requirements
5494 _ValueType1>)
5496 _ValueType2>)
5506 {
5510 }
5512 {
5516 }
5517 else
5518 {
5521 }
5524 }
5527 /**
5528 * @brief Return the minimum element in a range.
5529 * @param first Start of range.
5530 * @param last End of range.
5531 * @return Iterator referencing the first instance of the smallest value.
5532 */
5534 _ForwardIterator
5536 {
5537 // concept requirements
5550 }
5552 /**
5553 * @brief Return the minimum element in a range using comparison functor.
5554 * @param first Start of range.
5555 * @param last End of range.
5556 * @param comp Comparison functor.
5557 * @return Iterator referencing the first instance of the smallest value
5558 * according to comp.
5559 */
5561 _ForwardIterator
5563 _Compare __comp)
5564 {
5565 // concept requirements
5579 }
5581 /**
5582 * @brief Return the maximum element in a range.
5583 * @param first Start of range.
5584 * @param last End of range.
5585 * @return Iterator referencing the first instance of the largest value.
5586 */
5588 _ForwardIterator
5590 {
5591 // concept requirements
5604 }
5606 /**
5607 * @brief Return the maximum element in a range using comparison functor.
5608 * @param first Start of range.
5609 * @param last End of range.
5610 * @param comp Comparison functor.
5611 * @return Iterator referencing the first instance of the largest value
5612 * according to comp.
5613 */
5615 _ForwardIterator
5617 _Compare __comp)
5618 {
5619 // concept requirements
5632 }
5634 _GLIBCXX_END_NESTED_NAMESPACE