4 * Hewlett-Packard Company
6 * Permission to use, copy, modify, distribute and sell this software
7 * and its documentation for any purpose is hereby granted without fee,
8 * provided that the above copyright notice appear in all copies and
9 * that both that copyright notice and this permission notice appear
10 * in supporting documentation. Hewlett-Packard Company makes no
11 * representations about the suitability of this software for any
12 * purpose. It is provided "as is" without express or implied warranty.
16 * Silicon Graphics Computer Systems, Inc.
18 * Permission to use, copy, modify, distribute and sell this software
19 * and its documentation for any purpose is hereby granted without fee,
20 * provided that the above copyright notice appear in all copies and
21 * that both that copyright notice and this permission notice appear
22 * in supporting documentation. Silicon Graphics makes no
23 * representations about the suitability of this software for any
24 * purpose. It is provided "as is" without express or implied warranty.
27 #ifndef __SGI_STL_ALGO_H
28 #define __SGI_STL_ALGO_H
36 #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
41 inline const T& __median(const T& a, const T& b, const T& c) {
57 template <class T, class Compare>
58 inline const T& __median(const T& a, const T& b, const T& c, Compare comp) {
74 template <class InputIterator, class Function>
75 Function for_each(InputIterator first, InputIterator last, Function f) {
76 for ( ; first != last; ++first)
81 template <class InputIterator, class T>
82 InputIterator find(InputIterator first, InputIterator last, const T& value) {
83 while (first != last && *first != value) ++first;
87 template <class InputIterator, class Predicate>
88 InputIterator find_if(InputIterator first, InputIterator last,
90 while (first != last && !pred(*first)) ++first;
94 template <class ForwardIterator>
95 ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last) {
96 if (first == last) return last;
97 ForwardIterator next = first;
98 while(++next != last) {
99 if (*first == *next) return first;
105 template <class ForwardIterator, class BinaryPredicate>
106 ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last,
107 BinaryPredicate binary_pred) {
108 if (first == last) return last;
109 ForwardIterator next = first;
110 while(++next != last) {
111 if (binary_pred(*first, *next)) return first;
117 template <class InputIterator, class T, class Size>
118 void count(InputIterator first, InputIterator last, const T& value,
120 for ( ; first != last; ++first)
125 template <class InputIterator, class Predicate, class Size>
126 void count_if(InputIterator first, InputIterator last, Predicate pred,
128 for ( ; first != last; ++first)
133 #ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
135 template <class InputIterator, class T>
136 iterator_traits<InputIterator>::difference_type
137 count(InputIterator first, InputIterator last, const T& value) {
138 iterator_traits<InputIterator>::difference_type n = 0;
139 for ( ; first != last; ++first)
145 template <class InputIterator, class Predicate>
146 iterator_traits<InputIterator>::difference_type
147 count_if(InputIterator first, InputIterator last, Predicate pred) {
148 iterator_traits<InputIterator>::difference_type n = 0;
149 for ( ; first != last; ++first)
156 #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
158 template <class ForwardIterator1, class ForwardIterator2, class Distance1,
160 ForwardIterator1 __search(ForwardIterator1 first1, ForwardIterator1 last1,
161 ForwardIterator2 first2, ForwardIterator2 last2,
162 Distance1*, Distance2*) {
164 distance(first1, last1, d1);
166 distance(first2, last2, d2);
168 if (d1 < d2) return last1;
170 ForwardIterator1 current1 = first1;
171 ForwardIterator2 current2 = first2;
173 while (current2 != last2)
174 if (*current1 == *current2) {
190 template <class ForwardIterator1, class ForwardIterator2>
191 inline ForwardIterator1 search(ForwardIterator1 first1, ForwardIterator1 last1,
192 ForwardIterator2 first2, ForwardIterator2 last2)
194 return __search(first1, last1, first2, last2, distance_type(first1),
195 distance_type(first2));
198 template <class ForwardIterator1, class ForwardIterator2,
199 class BinaryPredicate, class Distance1, class Distance2>
200 ForwardIterator1 __search(ForwardIterator1 first1, ForwardIterator1 last1,
201 ForwardIterator2 first2, ForwardIterator2 last2,
202 BinaryPredicate binary_pred, Distance1*, Distance2*) {
204 distance(first1, last1, d1);
206 distance(first2, last2, d2);
208 if (d1 < d2) return last1;
210 ForwardIterator1 current1 = first1;
211 ForwardIterator2 current2 = first2;
213 while (current2 != last2)
214 if (binary_pred(*current1, *current2)) {
230 template <class ForwardIterator1, class ForwardIterator2,
231 class BinaryPredicate>
232 inline ForwardIterator1 search(ForwardIterator1 first1, ForwardIterator1 last1,
233 ForwardIterator2 first2, ForwardIterator2 last2,
234 BinaryPredicate binary_pred) {
235 return __search(first1, last1, first2, last2, binary_pred,
236 distance_type(first1), distance_type(first2));
239 template <class ForwardIterator1, class ForwardIterator2>
240 ForwardIterator2 swap_ranges(ForwardIterator1 first1, ForwardIterator1 last1,
241 ForwardIterator2 first2) {
242 for ( ; first1 != last1; ++first1, ++first2)
243 iter_swap(first1, first2);
247 template <class InputIterator, class OutputIterator, class UnaryOperation>
248 OutputIterator transform(InputIterator first, InputIterator last,
249 OutputIterator result, UnaryOperation op) {
250 for ( ; first != last; ++first, ++result)
251 *result = op(*first);
255 template <class InputIterator1, class InputIterator2, class OutputIterator,
256 class BinaryOperation>
257 OutputIterator transform(InputIterator1 first1, InputIterator1 last1,
258 InputIterator2 first2, OutputIterator result,
259 BinaryOperation binary_op) {
260 for ( ; first1 != last1; ++first1, ++first2, ++result)
261 *result = binary_op(*first1, *first2);
265 template <class ForwardIterator, class T>
266 void replace(ForwardIterator first, ForwardIterator last, const T& old_value,
267 const T& new_value) {
268 for ( ; first != last; ++first)
269 if (*first == old_value) *first = new_value;
272 template <class ForwardIterator, class Predicate, class T>
273 void replace_if(ForwardIterator first, ForwardIterator last, Predicate pred,
274 const T& new_value) {
275 for ( ; first != last; ++first)
276 if (pred(*first)) *first = new_value;
279 template <class InputIterator, class OutputIterator, class T>
280 OutputIterator replace_copy(InputIterator first, InputIterator last,
281 OutputIterator result, const T& old_value,
282 const T& new_value) {
283 for ( ; first != last; ++first, ++result)
284 *result = *first == old_value ? new_value : *first;
288 template <class Iterator, class OutputIterator, class Predicate, class T>
289 OutputIterator replace_copy_if(Iterator first, Iterator last,
290 OutputIterator result, Predicate pred,
291 const T& new_value) {
292 for ( ; first != last; ++first, ++result)
293 *result = pred(*first) ? new_value : *first;
297 template <class ForwardIterator, class Generator>
298 void generate(ForwardIterator first, ForwardIterator last, Generator gen) {
299 for ( ; first != last; ++first)
303 template <class OutputIterator, class Size, class Generator>
304 OutputIterator generate_n(OutputIterator first, Size n, Generator gen) {
305 for ( ; n > 0; --n, ++first)
310 template <class InputIterator, class OutputIterator, class T>
311 OutputIterator remove_copy(InputIterator first, InputIterator last,
312 OutputIterator result, const T& value) {
313 for ( ; first != last; ++first)
314 if (*first != value) {
321 template <class InputIterator, class OutputIterator, class Predicate>
322 OutputIterator remove_copy_if(InputIterator first, InputIterator last,
323 OutputIterator result, Predicate pred) {
324 for ( ; first != last; ++first)
332 template <class ForwardIterator, class T>
333 ForwardIterator remove(ForwardIterator first, ForwardIterator last,
335 first = find(first, last, value);
336 ForwardIterator next = first;
337 return first == last ? first : remove_copy(++next, last, first, value);
340 template <class ForwardIterator, class Predicate>
341 ForwardIterator remove_if(ForwardIterator first, ForwardIterator last,
343 first = find_if(first, last, pred);
344 ForwardIterator next = first;
345 return first == last ? first : remove_copy_if(++next, last, first, pred);
348 template <class InputIterator, class ForwardIterator>
349 ForwardIterator __unique_copy(InputIterator first, InputIterator last,
350 ForwardIterator result, forward_iterator_tag) {
352 while (++first != last)
353 if (*result != *first) *++result = *first;
357 template <class InputIterator, class BidirectionalIterator>
358 inline BidirectionalIterator __unique_copy(InputIterator first,
360 BidirectionalIterator result,
361 bidirectional_iterator_tag) {
362 return __unique_copy(first, last, result, forward_iterator_tag());
365 template <class InputIterator, class RandomAccessIterator>
366 inline RandomAccessIterator __unique_copy(InputIterator first,
368 RandomAccessIterator result,
369 random_access_iterator_tag) {
370 return __unique_copy(first, last, result, forward_iterator_tag());
373 template <class InputIterator, class OutputIterator, class T>
374 OutputIterator __unique_copy(InputIterator first, InputIterator last,
375 OutputIterator result, T*) {
378 while (++first != last)
379 if (value != *first) {
386 template <class InputIterator, class OutputIterator>
387 inline OutputIterator __unique_copy(InputIterator first, InputIterator last,
388 OutputIterator result,
389 output_iterator_tag) {
390 return __unique_copy(first, last, result, value_type(first));
393 template <class InputIterator, class OutputIterator>
394 inline OutputIterator unique_copy(InputIterator first, InputIterator last,
395 OutputIterator result) {
396 if (first == last) return result;
397 return __unique_copy(first, last, result, iterator_category(result));
399 template <class InputIterator, class ForwardIterator, class BinaryPredicate>
400 ForwardIterator __unique_copy(InputIterator first, InputIterator last,
401 ForwardIterator result,
402 BinaryPredicate binary_pred,
403 forward_iterator_tag) {
405 while (++first != last)
406 if (!binary_pred(*result, *first)) *++result = *first;
410 template <class InputIterator, class BidirectionalIterator,
411 class BinaryPredicate>
412 inline BidirectionalIterator __unique_copy(InputIterator first,
414 BidirectionalIterator result,
415 BinaryPredicate binary_pred,
416 bidirectional_iterator_tag) {
417 return __unique_copy(first, last, result, binary_pred,
418 forward_iterator_tag());
421 template <class InputIterator, class RandomAccessIterator,
422 class BinaryPredicate>
423 inline RandomAccessIterator __unique_copy(InputIterator first,
425 RandomAccessIterator result,
426 BinaryPredicate binary_pred,
427 random_access_iterator_tag) {
428 return __unique_copy(first, last, result, binary_pred,
429 forward_iterator_tag());
432 template <class InputIterator, class OutputIterator, class BinaryPredicate,
434 OutputIterator __unique_copy(InputIterator first, InputIterator last,
435 OutputIterator result,
436 BinaryPredicate binary_pred, T*) {
439 while (++first != last)
440 if (!binary_pred(value, *first)) {
447 template <class InputIterator, class OutputIterator, class BinaryPredicate>
448 inline OutputIterator __unique_copy(InputIterator first, InputIterator last,
449 OutputIterator result,
450 BinaryPredicate binary_pred,
451 output_iterator_tag) {
452 return __unique_copy(first, last, result, binary_pred, value_type(first));
455 template <class InputIterator, class OutputIterator, class BinaryPredicate>
456 inline OutputIterator unique_copy(InputIterator first, InputIterator last,
457 OutputIterator result,
458 BinaryPredicate binary_pred) {
459 if (first == last) return result;
460 return __unique_copy(first, last, result, binary_pred,
461 iterator_category(result));
464 template <class ForwardIterator>
465 ForwardIterator unique(ForwardIterator first, ForwardIterator last) {
466 first = adjacent_find(first, last);
467 return unique_copy(first, last, first);
470 template <class ForwardIterator, class BinaryPredicate>
471 ForwardIterator unique(ForwardIterator first, ForwardIterator last,
472 BinaryPredicate binary_pred) {
473 first = adjacent_find(first, last, binary_pred);
474 return unique_copy(first, last, first, binary_pred);
477 template <class BidirectionalIterator>
478 void __reverse(BidirectionalIterator first, BidirectionalIterator last,
479 bidirectional_iterator_tag) {
481 if (first == last || first == --last)
484 iter_swap(first++, last);
487 template <class RandomAccessIterator>
488 void __reverse(RandomAccessIterator first, RandomAccessIterator last,
489 random_access_iterator_tag) {
490 while (first < last) iter_swap(first++, --last);
493 template <class BidirectionalIterator>
494 inline void reverse(BidirectionalIterator first, BidirectionalIterator last) {
495 __reverse(first, last, iterator_category(first));
498 template <class BidirectionalIterator, class OutputIterator>
499 OutputIterator reverse_copy(BidirectionalIterator first,
500 BidirectionalIterator last,
501 OutputIterator result) {
502 while (first != last) {
510 template <class ForwardIterator, class Distance>
511 void __rotate(ForwardIterator first, ForwardIterator middle,
512 ForwardIterator last, Distance*, forward_iterator_tag) {
513 for (ForwardIterator i = middle; ;) {
517 if (first == middle) {
518 if (i == last) return;
526 template <class BidirectionalIterator, class Distance>
527 void __rotate(BidirectionalIterator first, BidirectionalIterator middle,
528 BidirectionalIterator last, Distance*,
529 bidirectional_iterator_tag) {
530 reverse(first, middle);
531 reverse(middle, last);
532 reverse(first, last);
535 template <class EuclideanRingElement>
536 EuclideanRingElement __gcd(EuclideanRingElement m, EuclideanRingElement n)
539 EuclideanRingElement t = m % n;
546 template <class RandomAccessIterator, class Distance, class T>
547 void __rotate_cycle(RandomAccessIterator first, RandomAccessIterator last,
548 RandomAccessIterator initial, Distance shift, T*) {
550 RandomAccessIterator ptr1 = initial;
551 RandomAccessIterator ptr2 = ptr1 + shift;
552 while (ptr2 != initial) {
555 if (last - ptr2 > shift)
558 ptr2 = first + (shift - (last - ptr2));
563 template <class RandomAccessIterator, class Distance>
564 void __rotate(RandomAccessIterator first, RandomAccessIterator middle,
565 RandomAccessIterator last, Distance*,
566 random_access_iterator_tag) {
567 Distance n = __gcd(last - first, middle - first);
569 __rotate_cycle(first, last, first + n, middle - first,
573 template <class ForwardIterator>
574 inline void rotate(ForwardIterator first, ForwardIterator middle,
575 ForwardIterator last) {
576 if (first == middle || middle == last) return;
577 __rotate(first, middle, last, distance_type(first),
578 iterator_category(first));
581 template <class ForwardIterator, class OutputIterator>
582 OutputIterator rotate_copy(ForwardIterator first, ForwardIterator middle,
583 ForwardIterator last, OutputIterator result) {
584 return copy(first, middle, copy(middle, last, result));
587 template <class RandomAccessIterator, class Distance>
588 void __random_shuffle(RandomAccessIterator first, RandomAccessIterator last,
590 if (first == last) return;
591 for (RandomAccessIterator i = first + 1; i != last; ++i)
592 #ifdef __STL_NO_DRAND48
593 iter_swap(i, first + Distance(rand() % ((i - first) + 1)));
595 iter_swap(i, first + Distance(lrand48() % ((i - first) + 1)));
599 template <class RandomAccessIterator>
600 inline void random_shuffle(RandomAccessIterator first,
601 RandomAccessIterator last) {
602 __random_shuffle(first, last, distance_type(first));
605 template <class RandomAccessIterator, class RandomNumberGenerator>
606 void random_shuffle(RandomAccessIterator first, RandomAccessIterator last,
607 RandomNumberGenerator& rand) {
608 if (first == last) return;
609 for (RandomAccessIterator i = first + 1; i != last; ++i)
610 iter_swap(i, first + rand((i - first) + 1));
613 template <class ForwardIterator, class OutputIterator, class Distance>
614 OutputIterator random_sample_n(ForwardIterator first, ForwardIterator last,
615 OutputIterator out, const Distance n)
617 Distance remaining = 0;
618 distance(first, last, remaining);
619 Distance m = min(n, remaining);
622 #ifdef __STL_NO_DRAND48
623 if (rand() % remaining < m) {
625 if (lrand48() % remaining < m) {
638 template <class ForwardIterator, class OutputIterator, class Distance,
639 class RandomNumberGenerator>
640 OutputIterator random_sample_n(ForwardIterator first, ForwardIterator last,
641 OutputIterator out, const Distance n,
642 RandomNumberGenerator& rand)
644 Distance remaining = 0;
645 distance(first, last, remaining);
646 Distance m = min(n, remaining);
649 if (rand(remaining) < m) {
661 template <class InputIterator, class RandomAccessIterator, class Distance>
662 RandomAccessIterator __random_sample(InputIterator first, InputIterator last,
663 RandomAccessIterator out,
668 for ( ; first != last && m < n; ++m, ++first)
671 while (first != last) {
673 #ifdef __STL_NO_DRAND48
674 Distance M = rand() % t;
676 Distance M = lrand48() % t;
686 template <class InputIterator, class RandomAccessIterator,
687 class RandomNumberGenerator, class Distance>
688 RandomAccessIterator __random_sample(InputIterator first, InputIterator last,
689 RandomAccessIterator out,
690 RandomNumberGenerator& rand,
695 for ( ; first != last && m < n; ++m, ++first)
698 while (first != last) {
700 Distance M = rand(t);
709 template <class InputIterator, class RandomAccessIterator>
710 inline RandomAccessIterator
711 random_sample(InputIterator first, InputIterator last,
712 RandomAccessIterator out_first, RandomAccessIterator out_last)
714 return __random_sample(first, last, out_first, out_last - out_first);
717 template <class InputIterator, class RandomAccessIterator,
718 class RandomNumberGenerator>
719 inline RandomAccessIterator
720 random_sample(InputIterator first, InputIterator last,
721 RandomAccessIterator out_first, RandomAccessIterator out_last,
722 RandomNumberGenerator& rand)
724 return __random_sample(first, last, out_first, rand, out_last - out_first);
729 template <class BidirectionalIterator, class Predicate>
730 BidirectionalIterator partition(BidirectionalIterator first,
731 BidirectionalIterator last, Predicate pred) {
736 else if (pred(*first))
744 else if (!pred(*last))
748 iter_swap(first, last);
753 template <class ForwardIterator, class Predicate, class Distance>
754 ForwardIterator __inplace_stable_partition(ForwardIterator first,
755 ForwardIterator last,
756 Predicate pred, Distance len) {
757 if (len == 1) return pred(*first) ? last : first;
758 ForwardIterator middle = first;
759 advance(middle, len / 2);
761 first_cut = __inplace_stable_partition(first, middle, pred, len / 2);
763 second_cut = __inplace_stable_partition(middle, last, pred,
765 rotate(first_cut, middle, second_cut);
767 distance(middle, second_cut, len);
768 advance(first_cut, len);
772 template <class ForwardIterator, class Pointer, class Predicate,
774 ForwardIterator __stable_partition_adaptive(ForwardIterator first,
775 ForwardIterator last,
776 Predicate pred, Distance len,
778 Distance buffer_size) {
779 if (len <= buffer_size) {
780 ForwardIterator result1 = first;
781 Pointer result2 = buffer;
782 for ( ; first != last ; ++first)
791 copy(buffer, result2, result1);
795 ForwardIterator middle = first;
796 advance(middle, len / 2);
797 ForwardIterator first_cut =
798 __stable_partition_adaptive(first, middle, pred, len / 2,
799 buffer, buffer_size);
800 ForwardIterator second_cut =
801 __stable_partition_adaptive(middle, last, pred, len - len / 2,
802 buffer, buffer_size);
804 rotate(first_cut, middle, second_cut);
806 distance(middle, second_cut, len);
807 advance(first_cut, len);
812 template <class ForwardIterator, class Predicate, class T, class Distance>
813 inline ForwardIterator __stable_partition_aux(ForwardIterator first,
814 ForwardIterator last,
815 Predicate pred, T*, Distance*) {
816 temporary_buffer<ForwardIterator, T> buf(first, last);
818 return __stable_partition_adaptive(first, last, pred,
819 Distance(buf.requested_size()),
820 buf.begin(), buf.size());
822 return __inplace_stable_partition(first, last, pred,
823 Distance(buf.requested_size()));
826 template <class ForwardIterator, class Predicate>
827 inline ForwardIterator stable_partition(ForwardIterator first,
828 ForwardIterator last,
833 return __stable_partition_aux(first, last, pred,
834 value_type(first), distance_type(first));
837 template <class RandomAccessIterator, class T>
838 RandomAccessIterator __unguarded_partition(RandomAccessIterator first,
839 RandomAccessIterator last,
842 while (*first < pivot) ++first;
844 while (pivot < *last) --last;
845 if (!(first < last)) return first;
846 iter_swap(first, last);
851 template <class RandomAccessIterator, class T, class Compare>
852 RandomAccessIterator __unguarded_partition(RandomAccessIterator first,
853 RandomAccessIterator last,
854 T pivot, Compare comp) {
856 while (comp(*first, pivot)) ++first;
858 while (comp(pivot, *last)) --last;
859 if (!(first < last)) return first;
860 iter_swap(first, last);
865 const int __stl_threshold = 16;
868 template <class RandomAccessIterator, class T>
869 void __unguarded_linear_insert(RandomAccessIterator last, T value) {
870 RandomAccessIterator next = last;
872 while (value < *next) {
880 template <class RandomAccessIterator, class T, class Compare>
881 void __unguarded_linear_insert(RandomAccessIterator last, T value,
883 RandomAccessIterator next = last;
885 while (comp(value , *next)) {
893 template <class RandomAccessIterator, class T>
894 inline void __linear_insert(RandomAccessIterator first,
895 RandomAccessIterator last, T*) {
897 if (value < *first) {
898 copy_backward(first, last, last + 1);
901 __unguarded_linear_insert(last, value);
904 template <class RandomAccessIterator, class T, class Compare>
905 inline void __linear_insert(RandomAccessIterator first,
906 RandomAccessIterator last, T*, Compare comp) {
908 if (comp(value, *first)) {
909 copy_backward(first, last, last + 1);
912 __unguarded_linear_insert(last, value, comp);
915 template <class RandomAccessIterator>
916 void __insertion_sort(RandomAccessIterator first, RandomAccessIterator last) {
917 if (first == last) return;
918 for (RandomAccessIterator i = first + 1; i != last; ++i)
919 __linear_insert(first, i, value_type(first));
922 template <class RandomAccessIterator, class Compare>
923 void __insertion_sort(RandomAccessIterator first,
924 RandomAccessIterator last, Compare comp) {
925 if (first == last) return;
926 for (RandomAccessIterator i = first + 1; i != last; ++i)
927 __linear_insert(first, i, value_type(first), comp);
930 template <class RandomAccessIterator, class T>
931 void __unguarded_insertion_sort_aux(RandomAccessIterator first,
932 RandomAccessIterator last, T*) {
933 for (RandomAccessIterator i = first; i != last; ++i)
934 __unguarded_linear_insert(i, T(*i));
937 template <class RandomAccessIterator>
938 inline void __unguarded_insertion_sort(RandomAccessIterator first,
939 RandomAccessIterator last) {
940 __unguarded_insertion_sort_aux(first, last, value_type(first));
943 template <class RandomAccessIterator, class T, class Compare>
944 void __unguarded_insertion_sort_aux(RandomAccessIterator first,
945 RandomAccessIterator last,
947 for (RandomAccessIterator i = first; i != last; ++i)
948 __unguarded_linear_insert(i, T(*i), comp);
951 template <class RandomAccessIterator, class Compare>
952 inline void __unguarded_insertion_sort(RandomAccessIterator first,
953 RandomAccessIterator last,
955 __unguarded_insertion_sort_aux(first, last, value_type(first), comp);
958 template <class RandomAccessIterator>
959 void __final_insertion_sort(RandomAccessIterator first,
960 RandomAccessIterator last) {
961 if (last - first > __stl_threshold) {
962 __insertion_sort(first, first + __stl_threshold);
963 __unguarded_insertion_sort(first + __stl_threshold, last);
965 __insertion_sort(first, last);
968 template <class RandomAccessIterator, class Compare>
969 void __final_insertion_sort(RandomAccessIterator first,
970 RandomAccessIterator last, Compare comp) {
971 if (last - first > __stl_threshold) {
972 __insertion_sort(first, first + __stl_threshold, comp);
973 __unguarded_insertion_sort(first + __stl_threshold, last, comp);
975 __insertion_sort(first, last, comp);
978 template <class Size>
981 for (k = 0; n != 1; n = n / 2) ++k;
985 template <class RandomAccessIterator, class T, class Size>
986 void __introsort_loop(RandomAccessIterator first,
987 RandomAccessIterator last, T*,
989 while (last - first > __stl_threshold) {
990 if (depth_limit == 0) {
991 partial_sort(first, last, last);
995 RandomAccessIterator cut = __unguarded_partition
996 (first, last, T(__median(*first, *(first + (last - first)/2),
998 __introsort_loop(cut, last, value_type(first), depth_limit);
1003 template <class RandomAccessIterator, class T, class Size, class Compare>
1004 void __introsort_loop(RandomAccessIterator first,
1005 RandomAccessIterator last, T*,
1006 Size depth_limit, Compare comp) {
1007 while (last - first > __stl_threshold) {
1008 if (depth_limit == 0) {
1009 partial_sort(first, last, last, comp);
1013 RandomAccessIterator cut = __unguarded_partition
1014 (first, last, T(__median(*first, *(first + (last - first)/2),
1015 *(last - 1), comp)), comp);
1016 __introsort_loop(cut, last, value_type(first), depth_limit, comp);
1021 template <class RandomAccessIterator>
1022 inline void sort(RandomAccessIterator first, RandomAccessIterator last) {
1023 if (first != last) {
1024 __introsort_loop(first, last, value_type(first), __lg(last - first) * 2);
1025 __final_insertion_sort(first, last);
1029 template <class RandomAccessIterator, class Compare>
1030 inline void sort(RandomAccessIterator first, RandomAccessIterator last,
1032 if (first != last) {
1033 __introsort_loop(first, last, value_type(first), __lg(last - first) * 2,
1035 __final_insertion_sort(first, last, comp);
1040 template <class RandomAccessIterator>
1041 void __inplace_stable_sort(RandomAccessIterator first,
1042 RandomAccessIterator last) {
1043 if (last - first < 15) {
1044 __insertion_sort(first, last);
1047 RandomAccessIterator middle = first + (last - first) / 2;
1048 __inplace_stable_sort(first, middle);
1049 __inplace_stable_sort(middle, last);
1050 __merge_without_buffer(first, middle, last, middle - first, last - middle);
1053 template <class RandomAccessIterator, class Compare>
1054 void __inplace_stable_sort(RandomAccessIterator first,
1055 RandomAccessIterator last, Compare comp) {
1056 if (last - first < 15) {
1057 __insertion_sort(first, last, comp);
1060 RandomAccessIterator middle = first + (last - first) / 2;
1061 __inplace_stable_sort(first, middle, comp);
1062 __inplace_stable_sort(middle, last, comp);
1063 __merge_without_buffer(first, middle, last, middle - first,
1064 last - middle, comp);
1067 template <class RandomAccessIterator1, class RandomAccessIterator2,
1069 void __merge_sort_loop(RandomAccessIterator1 first,
1070 RandomAccessIterator1 last,
1071 RandomAccessIterator2 result, Distance step_size) {
1072 Distance two_step = 2 * step_size;
1074 while (last - first >= two_step) {
1075 result = merge(first, first + step_size,
1076 first + step_size, first + two_step, result);
1080 step_size = min(Distance(last - first), step_size);
1081 merge(first, first + step_size, first + step_size, last, result);
1084 template <class RandomAccessIterator1, class RandomAccessIterator2,
1085 class Distance, class Compare>
1086 void __merge_sort_loop(RandomAccessIterator1 first,
1087 RandomAccessIterator1 last,
1088 RandomAccessIterator2 result, Distance step_size,
1090 Distance two_step = 2 * step_size;
1092 while (last - first >= two_step) {
1093 result = merge(first, first + step_size,
1094 first + step_size, first + two_step, result, comp);
1097 step_size = min(Distance(last - first), step_size);
1099 merge(first, first + step_size, first + step_size, last, result, comp);
1102 const int __stl_chunk_size = 7;
1104 template <class RandomAccessIterator, class Distance>
1105 void __chunk_insertion_sort(RandomAccessIterator first,
1106 RandomAccessIterator last, Distance chunk_size) {
1107 while (last - first >= chunk_size) {
1108 __insertion_sort(first, first + chunk_size);
1109 first += chunk_size;
1111 __insertion_sort(first, last);
1114 template <class RandomAccessIterator, class Distance, class Compare>
1115 void __chunk_insertion_sort(RandomAccessIterator first,
1116 RandomAccessIterator last,
1117 Distance chunk_size, Compare comp) {
1118 while (last - first >= chunk_size) {
1119 __insertion_sort(first, first + chunk_size, comp);
1120 first += chunk_size;
1122 __insertion_sort(first, last, comp);
1125 template <class RandomAccessIterator, class Pointer, class Distance>
1126 void __merge_sort_with_buffer(RandomAccessIterator first,
1127 RandomAccessIterator last,
1128 Pointer buffer, Distance*) {
1129 Distance len = last - first;
1130 Pointer buffer_last = buffer + len;
1132 Distance step_size = __stl_chunk_size;
1133 __chunk_insertion_sort(first, last, step_size);
1135 while (step_size < len) {
1136 __merge_sort_loop(first, last, buffer, step_size);
1138 __merge_sort_loop(buffer, buffer_last, first, step_size);
1143 template <class RandomAccessIterator, class Pointer, class Distance,
1145 void __merge_sort_with_buffer(RandomAccessIterator first,
1146 RandomAccessIterator last, Pointer buffer,
1147 Distance*, Compare comp) {
1148 Distance len = last - first;
1149 Pointer buffer_last = buffer + len;
1151 Distance step_size = __stl_chunk_size;
1152 __chunk_insertion_sort(first, last, step_size, comp);
1154 while (step_size < len) {
1155 __merge_sort_loop(first, last, buffer, step_size, comp);
1157 __merge_sort_loop(buffer, buffer_last, first, step_size, comp);
1162 template <class RandomAccessIterator, class Pointer, class Distance>
1163 void __stable_sort_adaptive(RandomAccessIterator first,
1164 RandomAccessIterator last, Pointer buffer,
1165 Distance buffer_size) {
1166 Distance len = (last - first + 1) / 2;
1167 RandomAccessIterator middle = first + len;
1168 if (len > buffer_size) {
1169 __stable_sort_adaptive(first, middle, buffer, buffer_size);
1170 __stable_sort_adaptive(middle, last, buffer, buffer_size);
1172 __merge_sort_with_buffer(first, middle, buffer, (Distance*)0);
1173 __merge_sort_with_buffer(middle, last, buffer, (Distance*)0);
1175 __merge_adaptive(first, middle, last, Distance(middle - first),
1176 Distance(last - middle), buffer, buffer_size);
1179 template <class RandomAccessIterator, class Pointer, class Distance,
1181 void __stable_sort_adaptive(RandomAccessIterator first,
1182 RandomAccessIterator last, Pointer buffer,
1183 Distance buffer_size, Compare comp) {
1184 Distance len = (last - first + 1) / 2;
1185 RandomAccessIterator middle = first + len;
1186 if (len > buffer_size) {
1187 __stable_sort_adaptive(first, middle, buffer, buffer_size,
1189 __stable_sort_adaptive(middle, last, buffer, buffer_size,
1192 __merge_sort_with_buffer(first, middle, buffer, (Distance*)0, comp);
1193 __merge_sort_with_buffer(middle, last, buffer, (Distance*)0, comp);
1195 __merge_adaptive(first, middle, last, Distance(middle - first),
1196 Distance(last - middle), buffer, buffer_size,
1200 template <class RandomAccessIterator, class T, class Distance>
1201 inline void __stable_sort_aux(RandomAccessIterator first,
1202 RandomAccessIterator last, T*, Distance*) {
1203 temporary_buffer<RandomAccessIterator, T> buf(first, last);
1204 if (buf.begin() == 0)
1205 __inplace_stable_sort(first, last);
1207 __stable_sort_adaptive(first, last, buf.begin(), Distance(buf.size()));
1210 template <class RandomAccessIterator, class T, class Distance, class Compare>
1211 inline void __stable_sort_aux(RandomAccessIterator first,
1212 RandomAccessIterator last, T*, Distance*,
1214 temporary_buffer<RandomAccessIterator, T> buf(first, last);
1215 if (buf.begin() == 0)
1216 __inplace_stable_sort(first, last, comp);
1218 __stable_sort_adaptive(first, last, buf.begin(), Distance(buf.size()),
1222 template <class RandomAccessIterator>
1223 inline void stable_sort(RandomAccessIterator first,
1224 RandomAccessIterator last) {
1225 __stable_sort_aux(first, last, value_type(first), distance_type(first));
1228 template <class RandomAccessIterator, class Compare>
1229 inline void stable_sort(RandomAccessIterator first,
1230 RandomAccessIterator last, Compare comp) {
1231 __stable_sort_aux(first, last, value_type(first), distance_type(first),
1235 template <class RandomAccessIterator, class T>
1236 void __partial_sort(RandomAccessIterator first, RandomAccessIterator middle,
1237 RandomAccessIterator last, T*) {
1238 make_heap(first, middle);
1239 for (RandomAccessIterator i = middle; i < last; ++i)
1241 __pop_heap(first, middle, i, T(*i), distance_type(first));
1242 sort_heap(first, middle);
1245 template <class RandomAccessIterator>
1246 inline void partial_sort(RandomAccessIterator first,
1247 RandomAccessIterator middle,
1248 RandomAccessIterator last) {
1249 __partial_sort(first, middle, last, value_type(first));
1252 template <class RandomAccessIterator, class T, class Compare>
1253 void __partial_sort(RandomAccessIterator first, RandomAccessIterator middle,
1254 RandomAccessIterator last, T*, Compare comp) {
1255 make_heap(first, middle, comp);
1256 for (RandomAccessIterator i = middle; i < last; ++i)
1257 if (comp(*i, *first))
1258 __pop_heap(first, middle, i, T(*i), comp, distance_type(first));
1259 sort_heap(first, middle, comp);
1262 template <class RandomAccessIterator, class Compare>
1263 inline void partial_sort(RandomAccessIterator first,
1264 RandomAccessIterator middle,
1265 RandomAccessIterator last, Compare comp) {
1266 __partial_sort(first, middle, last, value_type(first), comp);
1269 template <class InputIterator, class RandomAccessIterator, class Distance,
1271 RandomAccessIterator __partial_sort_copy(InputIterator first,
1273 RandomAccessIterator result_first,
1274 RandomAccessIterator result_last,
1276 if (result_first == result_last) return result_last;
1277 RandomAccessIterator result_real_last = result_first;
1278 while(first != last && result_real_last != result_last) {
1279 *result_real_last = *first;
1283 make_heap(result_first, result_real_last);
1284 while (first != last) {
1285 if (*first < *result_first)
1286 __adjust_heap(result_first, Distance(0),
1287 Distance(result_real_last - result_first), T(*first));
1290 sort_heap(result_first, result_real_last);
1291 return result_real_last;
1294 template <class InputIterator, class RandomAccessIterator>
1295 inline RandomAccessIterator
1296 partial_sort_copy(InputIterator first, InputIterator last,
1297 RandomAccessIterator result_first,
1298 RandomAccessIterator result_last) {
1299 return __partial_sort_copy(first, last, result_first, result_last,
1300 distance_type(result_first), value_type(first));
1303 template <class InputIterator, class RandomAccessIterator, class Compare,
1304 class Distance, class T>
1305 RandomAccessIterator __partial_sort_copy(InputIterator first,
1307 RandomAccessIterator result_first,
1308 RandomAccessIterator result_last,
1309 Compare comp, Distance*, T*) {
1310 if (result_first == result_last) return result_last;
1311 RandomAccessIterator result_real_last = result_first;
1312 while(first != last && result_real_last != result_last) {
1313 *result_real_last = *first;
1317 make_heap(result_first, result_real_last, comp);
1318 while (first != last) {
1319 if (comp(*first, *result_first))
1320 __adjust_heap(result_first, Distance(0),
1321 Distance(result_real_last - result_first), T(*first),
1325 sort_heap(result_first, result_real_last, comp);
1326 return result_real_last;
1329 template <class InputIterator, class RandomAccessIterator, class Compare>
1330 inline RandomAccessIterator
1331 partial_sort_copy(InputIterator first, InputIterator last,
1332 RandomAccessIterator result_first,
1333 RandomAccessIterator result_last, Compare comp) {
1334 return __partial_sort_copy(first, last, result_first, result_last, comp,
1335 distance_type(result_first), value_type(first));
1338 template <class RandomAccessIterator, class T>
1339 void __nth_element(RandomAccessIterator first, RandomAccessIterator nth,
1340 RandomAccessIterator last, T*) {
1341 while (last - first > 3) {
1342 RandomAccessIterator cut = __unguarded_partition
1343 (first, last, T(__median(*first, *(first + (last - first)/2),
1350 __insertion_sort(first, last);
1353 template <class RandomAccessIterator>
1354 inline void nth_element(RandomAccessIterator first, RandomAccessIterator nth,
1355 RandomAccessIterator last) {
1356 __nth_element(first, nth, last, value_type(first));
1359 template <class RandomAccessIterator, class T, class Compare>
1360 void __nth_element(RandomAccessIterator first, RandomAccessIterator nth,
1361 RandomAccessIterator last, T*, Compare comp) {
1362 while (last - first > 3) {
1363 RandomAccessIterator cut = __unguarded_partition
1364 (first, last, T(__median(*first, *(first + (last - first)/2),
1365 *(last - 1), comp)), comp);
1371 __insertion_sort(first, last, comp);
1374 template <class RandomAccessIterator, class Compare>
1375 inline void nth_element(RandomAccessIterator first, RandomAccessIterator nth,
1376 RandomAccessIterator last, Compare comp) {
1377 __nth_element(first, nth, last, value_type(first), comp);
1380 template <class ForwardIterator, class T, class Distance>
1381 ForwardIterator __lower_bound(ForwardIterator first, ForwardIterator last,
1382 const T& value, Distance*,
1383 forward_iterator_tag) {
1385 distance(first, last, len);
1387 ForwardIterator middle;
1392 advance(middle, half);
1393 if (*middle < value) {
1396 len = len - half - 1;
1403 template <class ForwardIterator, class T, class Distance>
1404 inline ForwardIterator __lower_bound(ForwardIterator first,
1405 ForwardIterator last,
1406 const T& value, Distance*,
1407 bidirectional_iterator_tag) {
1408 return __lower_bound(first, last, value, (Distance*)0,
1409 forward_iterator_tag());
1412 template <class RandomAccessIterator, class T, class Distance>
1413 RandomAccessIterator __lower_bound(RandomAccessIterator first,
1414 RandomAccessIterator last, const T& value,
1415 Distance*, random_access_iterator_tag) {
1416 Distance len = last - first;
1418 RandomAccessIterator middle;
1422 middle = first + half;
1423 if (*middle < value) {
1425 len = len - half - 1;
1432 template <class ForwardIterator, class T>
1433 inline ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last,
1435 return __lower_bound(first, last, value, distance_type(first),
1436 iterator_category(first));
1439 template <class ForwardIterator, class T, class Compare, class Distance>
1440 ForwardIterator __lower_bound(ForwardIterator first, ForwardIterator last,
1441 const T& value, Compare comp, Distance*,
1442 forward_iterator_tag) {
1444 distance(first, last, len);
1446 ForwardIterator middle;
1451 advance(middle, half);
1452 if (comp(*middle, value)) {
1455 len = len - half - 1;
1462 template <class ForwardIterator, class T, class Compare, class Distance>
1463 inline ForwardIterator __lower_bound(ForwardIterator first,
1464 ForwardIterator last,
1465 const T& value, Compare comp, Distance*,
1466 bidirectional_iterator_tag) {
1467 return __lower_bound(first, last, value, comp, (Distance*)0,
1468 forward_iterator_tag());
1471 template <class RandomAccessIterator, class T, class Compare, class Distance>
1472 RandomAccessIterator __lower_bound(RandomAccessIterator first,
1473 RandomAccessIterator last,
1474 const T& value, Compare comp, Distance*,
1475 random_access_iterator_tag) {
1476 Distance len = last - first;
1478 RandomAccessIterator middle;
1482 middle = first + half;
1483 if (comp(*middle, value)) {
1485 len = len - half - 1;
1492 template <class ForwardIterator, class T, class Compare>
1493 inline ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last,
1494 const T& value, Compare comp) {
1495 return __lower_bound(first, last, value, comp, distance_type(first),
1496 iterator_category(first));
1499 template <class ForwardIterator, class T, class Distance>
1500 ForwardIterator __upper_bound(ForwardIterator first, ForwardIterator last,
1501 const T& value, Distance*,
1502 forward_iterator_tag) {
1504 distance(first, last, len);
1506 ForwardIterator middle;
1511 advance(middle, half);
1512 if (value < *middle)
1517 len = len - half - 1;
1523 template <class ForwardIterator, class T, class Distance>
1524 inline ForwardIterator __upper_bound(ForwardIterator first,
1525 ForwardIterator last,
1526 const T& value, Distance*,
1527 bidirectional_iterator_tag) {
1528 return __upper_bound(first, last, value, (Distance*)0,
1529 forward_iterator_tag());
1532 template <class RandomAccessIterator, class T, class Distance>
1533 RandomAccessIterator __upper_bound(RandomAccessIterator first,
1534 RandomAccessIterator last, const T& value,
1535 Distance*, random_access_iterator_tag) {
1536 Distance len = last - first;
1538 RandomAccessIterator middle;
1542 middle = first + half;
1543 if (value < *middle)
1547 len = len - half - 1;
1553 template <class ForwardIterator, class T>
1554 inline ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last,
1556 return __upper_bound(first, last, value, distance_type(first),
1557 iterator_category(first));
1560 template <class ForwardIterator, class T, class Compare, class Distance>
1561 ForwardIterator __upper_bound(ForwardIterator first, ForwardIterator last,
1562 const T& value, Compare comp, Distance*,
1563 forward_iterator_tag) {
1565 distance(first, last, len);
1567 ForwardIterator middle;
1572 advance(middle, half);
1573 if (comp(value, *middle))
1578 len = len - half - 1;
1584 template <class ForwardIterator, class T, class Compare, class Distance>
1585 inline ForwardIterator __upper_bound(ForwardIterator first,
1586 ForwardIterator last,
1587 const T& value, Compare comp, Distance*,
1588 bidirectional_iterator_tag) {
1589 return __upper_bound(first, last, value, comp, (Distance*)0,
1590 forward_iterator_tag());
1593 template <class RandomAccessIterator, class T, class Compare, class Distance>
1594 RandomAccessIterator __upper_bound(RandomAccessIterator first,
1595 RandomAccessIterator last,
1596 const T& value, Compare comp, Distance*,
1597 random_access_iterator_tag) {
1598 Distance len = last - first;
1600 RandomAccessIterator middle;
1604 middle = first + half;
1605 if (comp(value, *middle))
1609 len = len - half - 1;
1615 template <class ForwardIterator, class T, class Compare>
1616 inline ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last,
1617 const T& value, Compare comp) {
1618 return __upper_bound(first, last, value, comp, distance_type(first),
1619 iterator_category(first));
1622 template <class ForwardIterator, class T, class Distance>
1623 pair<ForwardIterator, ForwardIterator>
1624 __equal_range(ForwardIterator first, ForwardIterator last, const T& value,
1625 Distance*, forward_iterator_tag) {
1627 distance(first, last, len);
1629 ForwardIterator middle, left, right;
1634 advance(middle, half);
1635 if (*middle < value) {
1638 len = len - half - 1;
1639 } else if (value < *middle)
1642 left = lower_bound(first, middle, value);
1643 advance(first, len);
1644 right = upper_bound(++middle, first, value);
1645 return pair<ForwardIterator, ForwardIterator>(left, right);
1648 return pair<ForwardIterator, ForwardIterator>(first, first);
1651 template <class ForwardIterator, class T, class Distance>
1652 inline pair<ForwardIterator, ForwardIterator>
1653 __equal_range(ForwardIterator first, ForwardIterator last, const T& value,
1654 Distance*, bidirectional_iterator_tag) {
1655 return __equal_range(first, last, value, (Distance*)0,
1656 forward_iterator_tag());
1659 template <class RandomAccessIterator, class T, class Distance>
1660 pair<RandomAccessIterator, RandomAccessIterator>
1661 __equal_range(RandomAccessIterator first, RandomAccessIterator last,
1662 const T& value, Distance*, random_access_iterator_tag) {
1663 Distance len = last - first;
1665 RandomAccessIterator middle, left, right;
1669 middle = first + half;
1670 if (*middle < value) {
1672 len = len - half - 1;
1673 } else if (value < *middle)
1676 left = lower_bound(first, middle, value);
1677 right = upper_bound(++middle, first + len, value);
1678 return pair<RandomAccessIterator, RandomAccessIterator>(left,
1682 return pair<RandomAccessIterator, RandomAccessIterator>(first, first);
1685 template <class ForwardIterator, class T>
1686 inline pair<ForwardIterator, ForwardIterator>
1687 equal_range(ForwardIterator first, ForwardIterator last, const T& value) {
1688 return __equal_range(first, last, value, distance_type(first),
1689 iterator_category(first));
1692 template <class ForwardIterator, class T, class Compare, class Distance>
1693 pair<ForwardIterator, ForwardIterator>
1694 __equal_range(ForwardIterator first, ForwardIterator last, const T& value,
1695 Compare comp, Distance*, forward_iterator_tag) {
1697 distance(first, last, len);
1699 ForwardIterator middle, left, right;
1704 advance(middle, half);
1705 if (comp(*middle, value)) {
1708 len = len - half - 1;
1709 } else if (comp(value, *middle))
1712 left = lower_bound(first, middle, value, comp);
1713 advance(first, len);
1714 right = upper_bound(++middle, first, value, comp);
1715 return pair<ForwardIterator, ForwardIterator>(left, right);
1718 return pair<ForwardIterator, ForwardIterator>(first, first);
1721 template <class ForwardIterator, class T, class Compare, class Distance>
1722 inline pair<ForwardIterator, ForwardIterator>
1723 __equal_range(ForwardIterator first, ForwardIterator last, const T& value,
1724 Compare comp, Distance*, bidirectional_iterator_tag) {
1725 return __equal_range(first, last, value, comp, (Distance*)0,
1726 forward_iterator_tag());
1729 template <class RandomAccessIterator, class T, class Compare, class Distance>
1730 pair<RandomAccessIterator, RandomAccessIterator>
1731 __equal_range(RandomAccessIterator first, RandomAccessIterator last,
1732 const T& value, Compare comp, Distance*,
1733 random_access_iterator_tag) {
1734 Distance len = last - first;
1736 RandomAccessIterator middle, left, right;
1740 middle = first + half;
1741 if (comp(*middle, value)) {
1743 len = len - half - 1;
1744 } else if (comp(value, *middle))
1747 left = lower_bound(first, middle, value, comp);
1748 right = upper_bound(++middle, first + len, value, comp);
1749 return pair<RandomAccessIterator, RandomAccessIterator>(left,
1753 return pair<RandomAccessIterator, RandomAccessIterator>(first, first);
1756 template <class ForwardIterator, class T, class Compare>
1757 inline pair<ForwardIterator, ForwardIterator>
1758 equal_range(ForwardIterator first, ForwardIterator last, const T& value,
1760 return __equal_range(first, last, value, comp, distance_type(first),
1761 iterator_category(first));
1764 template <class ForwardIterator, class T>
1765 bool binary_search(ForwardIterator first, ForwardIterator last,
1767 ForwardIterator i = lower_bound(first, last, value);
1768 return i != last && !(value < *i);
1771 template <class ForwardIterator, class T, class Compare>
1772 bool binary_search(ForwardIterator first, ForwardIterator last, const T& value,
1774 ForwardIterator i = lower_bound(first, last, value, comp);
1775 return i != last && !comp(value, *i);
1778 template <class InputIterator1, class InputIterator2, class OutputIterator>
1779 OutputIterator merge(InputIterator1 first1, InputIterator1 last1,
1780 InputIterator2 first2, InputIterator2 last2,
1781 OutputIterator result) {
1782 while (first1 != last1 && first2 != last2) {
1783 if (*first2 < *first1) {
1793 return copy(first2, last2, copy(first1, last1, result));
1796 template <class InputIterator1, class InputIterator2, class OutputIterator,
1798 OutputIterator merge(InputIterator1 first1, InputIterator1 last1,
1799 InputIterator2 first2, InputIterator2 last2,
1800 OutputIterator result, Compare comp) {
1801 while (first1 != last1 && first2 != last2) {
1802 if (comp(*first2, *first1)) {
1812 return copy(first2, last2, copy(first1, last1, result));
1815 template <class BidirectionalIterator, class Distance>
1816 void __merge_without_buffer(BidirectionalIterator first,
1817 BidirectionalIterator middle,
1818 BidirectionalIterator last,
1819 Distance len1, Distance len2) {
1820 if (len1 == 0 || len2 == 0) return;
1821 if (len1 + len2 == 2) {
1822 if (*middle < *first) iter_swap(first, middle);
1825 BidirectionalIterator first_cut = first;
1826 BidirectionalIterator second_cut = middle;
1831 advance(first_cut, len11);
1832 second_cut = lower_bound(middle, last, *first_cut);
1833 distance(middle, second_cut, len22);
1836 advance(second_cut, len22);
1837 first_cut = upper_bound(first, middle, *second_cut);
1838 distance(first, first_cut, len11);
1840 rotate(first_cut, middle, second_cut);
1841 BidirectionalIterator new_middle = first_cut;
1842 advance(new_middle, len22);
1843 __merge_without_buffer(first, first_cut, new_middle, len11, len22);
1844 __merge_without_buffer(new_middle, second_cut, last, len1 - len11,
1848 template <class BidirectionalIterator, class Distance, class Compare>
1849 void __merge_without_buffer(BidirectionalIterator first,
1850 BidirectionalIterator middle,
1851 BidirectionalIterator last,
1852 Distance len1, Distance len2, Compare comp) {
1853 if (len1 == 0 || len2 == 0) return;
1854 if (len1 + len2 == 2) {
1855 if (comp(*middle, *first)) iter_swap(first, middle);
1858 BidirectionalIterator first_cut = first;
1859 BidirectionalIterator second_cut = middle;
1864 advance(first_cut, len11);
1865 second_cut = lower_bound(middle, last, *first_cut, comp);
1866 distance(middle, second_cut, len22);
1869 advance(second_cut, len22);
1870 first_cut = upper_bound(first, middle, *second_cut, comp);
1871 distance(first, first_cut, len11);
1873 rotate(first_cut, middle, second_cut);
1874 BidirectionalIterator new_middle = first_cut;
1875 advance(new_middle, len22);
1876 __merge_without_buffer(first, first_cut, new_middle, len11, len22, comp);
1877 __merge_without_buffer(new_middle, second_cut, last, len1 - len11,
1878 len2 - len22, comp);
1881 template <class BidirectionalIterator1, class BidirectionalIterator2,
1883 BidirectionalIterator1 __rotate_adaptive(BidirectionalIterator1 first,
1884 BidirectionalIterator1 middle,
1885 BidirectionalIterator1 last,
1886 Distance len1, Distance len2,
1887 BidirectionalIterator2 buffer,
1888 Distance buffer_size) {
1889 BidirectionalIterator2 buffer_end;
1890 if (len1 > len2 && len2 <= buffer_size) {
1891 buffer_end = copy(middle, last, buffer);
1892 copy_backward(first, middle, last);
1893 return copy(buffer, buffer_end, first);
1894 } else if (len1 <= buffer_size) {
1895 buffer_end = copy(first, middle, buffer);
1896 copy(middle, last, first);
1897 return copy_backward(buffer, buffer_end, last);
1899 rotate(first, middle, last);
1900 advance(first, len2);
1905 template <class BidirectionalIterator1, class BidirectionalIterator2,
1906 class BidirectionalIterator3>
1907 BidirectionalIterator3 __merge_backward(BidirectionalIterator1 first1,
1908 BidirectionalIterator1 last1,
1909 BidirectionalIterator2 first2,
1910 BidirectionalIterator2 last2,
1911 BidirectionalIterator3 result) {
1912 if (first1 == last1) return copy_backward(first2, last2, result);
1913 if (first2 == last2) return copy_backward(first1, last1, result);
1917 if (*last2 < *last1) {
1919 if (first1 == last1) return copy_backward(first2, ++last2, result);
1923 if (first2 == last2) return copy_backward(first1, ++last1, result);
1929 template <class BidirectionalIterator1, class BidirectionalIterator2,
1930 class BidirectionalIterator3, class Compare>
1931 BidirectionalIterator3 __merge_backward(BidirectionalIterator1 first1,
1932 BidirectionalIterator1 last1,
1933 BidirectionalIterator2 first2,
1934 BidirectionalIterator2 last2,
1935 BidirectionalIterator3 result,
1937 if (first1 == last1) return copy_backward(first2, last2, result);
1938 if (first2 == last2) return copy_backward(first1, last1, result);
1942 if (comp(*last2, *last1)) {
1944 if (first1 == last1) return copy_backward(first2, ++last2, result);
1948 if (first2 == last2) return copy_backward(first1, ++last1, result);
1954 template <class BidirectionalIterator, class Distance, class Pointer>
1955 void __merge_adaptive(BidirectionalIterator first,
1956 BidirectionalIterator middle,
1957 BidirectionalIterator last, Distance len1, Distance len2,
1958 Pointer buffer, Distance buffer_size) {
1959 if (len1 <= len2 && len1 <= buffer_size) {
1960 Pointer end_buffer = copy(first, middle, buffer);
1961 merge(buffer, end_buffer, middle, last, first);
1962 } else if (len2 <= buffer_size) {
1963 Pointer end_buffer = copy(middle, last, buffer);
1964 __merge_backward(first, middle, buffer, end_buffer, last);
1966 BidirectionalIterator first_cut = first;
1967 BidirectionalIterator second_cut = middle;
1972 advance(first_cut, len11);
1973 second_cut = lower_bound(middle, last, *first_cut);
1974 distance(middle, second_cut, len22);
1977 advance(second_cut, len22);
1978 first_cut = upper_bound(first, middle, *second_cut);
1979 distance(first, first_cut, len11);
1981 BidirectionalIterator new_middle =
1982 __rotate_adaptive(first_cut, middle, second_cut, len1 - len11,
1983 len22, buffer, buffer_size);
1984 __merge_adaptive(first, first_cut, new_middle, len11, len22, buffer,
1986 __merge_adaptive(new_middle, second_cut, last, len1 - len11,
1987 len2 - len22, buffer, buffer_size);
1991 template <class BidirectionalIterator, class Distance, class Pointer,
1993 void __merge_adaptive(BidirectionalIterator first,
1994 BidirectionalIterator middle,
1995 BidirectionalIterator last, Distance len1, Distance len2,
1996 Pointer buffer, Distance buffer_size, Compare comp) {
1997 if (len1 <= len2 && len1 <= buffer_size) {
1998 Pointer end_buffer = copy(first, middle, buffer);
1999 merge(buffer, end_buffer, middle, last, first, comp);
2000 } else if (len2 <= buffer_size) {
2001 Pointer end_buffer = copy(middle, last, buffer);
2002 __merge_backward(first, middle, buffer, end_buffer, last, comp);
2004 BidirectionalIterator first_cut = first;
2005 BidirectionalIterator second_cut = middle;
2010 advance(first_cut, len11);
2011 second_cut = lower_bound(middle, last, *first_cut, comp);
2012 distance(middle, second_cut, len22);
2015 advance(second_cut, len22);
2016 first_cut = upper_bound(first, middle, *second_cut, comp);
2017 distance(first, first_cut, len11);
2019 BidirectionalIterator new_middle =
2020 __rotate_adaptive(first_cut, middle, second_cut, len1 - len11,
2021 len22, buffer, buffer_size);
2022 __merge_adaptive(first, first_cut, new_middle, len11, len22, buffer,
2024 __merge_adaptive(new_middle, second_cut, last, len1 - len11,
2025 len2 - len22, buffer, buffer_size, comp);
2029 template <class BidirectionalIterator, class T, class Distance>
2030 inline void __inplace_merge_aux(BidirectionalIterator first,
2031 BidirectionalIterator middle,
2032 BidirectionalIterator last, T*, Distance*) {
2034 distance(first, middle, len1);
2036 distance(middle, last, len2);
2038 temporary_buffer<BidirectionalIterator, T> buf(first, last);
2039 if (buf.begin() == 0)
2040 __merge_without_buffer(first, middle, last, len1, len2);
2042 __merge_adaptive(first, middle, last, len1, len2,
2043 buf.begin(), Distance(buf.size()));
2046 template <class BidirectionalIterator, class T, class Distance, class Compare>
2047 inline void __inplace_merge_aux(BidirectionalIterator first,
2048 BidirectionalIterator middle,
2049 BidirectionalIterator last, T*, Distance*,
2052 distance(first, middle, len1);
2054 distance(middle, last, len2);
2056 temporary_buffer<BidirectionalIterator, T> buf(first, last);
2057 if (buf.begin() == 0)
2058 __merge_without_buffer(first, middle, last, len1, len2, comp);
2060 __merge_adaptive(first, middle, last, len1, len2,
2061 buf.begin(), Distance(buf.size()),
2065 template <class BidirectionalIterator>
2066 inline void inplace_merge(BidirectionalIterator first,
2067 BidirectionalIterator middle,
2068 BidirectionalIterator last) {
2069 if (first == middle || middle == last) return;
2070 __inplace_merge_aux(first, middle, last, value_type(first),
2071 distance_type(first));
2074 template <class BidirectionalIterator, class Compare>
2075 inline void inplace_merge(BidirectionalIterator first,
2076 BidirectionalIterator middle,
2077 BidirectionalIterator last, Compare comp) {
2078 if (first == middle || middle == last) return;
2079 __inplace_merge_aux(first, middle, last, value_type(first),
2080 distance_type(first), comp);
2083 template <class InputIterator1, class InputIterator2>
2084 bool includes(InputIterator1 first1, InputIterator1 last1,
2085 InputIterator2 first2, InputIterator2 last2) {
2086 while (first1 != last1 && first2 != last2)
2087 if (*first2 < *first1)
2089 else if(*first1 < *first2)
2094 return first2 == last2;
2097 template <class InputIterator1, class InputIterator2, class Compare>
2098 bool includes(InputIterator1 first1, InputIterator1 last1,
2099 InputIterator2 first2, InputIterator2 last2, Compare comp) {
2100 while (first1 != last1 && first2 != last2)
2101 if (comp(*first2, *first1))
2103 else if(comp(*first1, *first2))
2108 return first2 == last2;
2111 template <class InputIterator1, class InputIterator2, class OutputIterator>
2112 OutputIterator set_union(InputIterator1 first1, InputIterator1 last1,
2113 InputIterator2 first2, InputIterator2 last2,
2114 OutputIterator result) {
2115 while (first1 != last1 && first2 != last2) {
2116 if (*first1 < *first2) {
2120 else if (*first2 < *first1) {
2131 return copy(first2, last2, copy(first1, last1, result));
2134 template <class InputIterator1, class InputIterator2, class OutputIterator,
2136 OutputIterator set_union(InputIterator1 first1, InputIterator1 last1,
2137 InputIterator2 first2, InputIterator2 last2,
2138 OutputIterator result, Compare comp) {
2139 while (first1 != last1 && first2 != last2) {
2140 if (comp(*first1, *first2)) {
2144 else if (comp(*first2, *first1)) {
2155 return copy(first2, last2, copy(first1, last1, result));
2158 template <class InputIterator1, class InputIterator2, class OutputIterator>
2159 OutputIterator set_intersection(InputIterator1 first1, InputIterator1 last1,
2160 InputIterator2 first2, InputIterator2 last2,
2161 OutputIterator result) {
2162 while (first1 != last1 && first2 != last2)
2163 if (*first1 < *first2)
2165 else if (*first2 < *first1)
2176 template <class InputIterator1, class InputIterator2, class OutputIterator,
2178 OutputIterator set_intersection(InputIterator1 first1, InputIterator1 last1,
2179 InputIterator2 first2, InputIterator2 last2,
2180 OutputIterator result, Compare comp) {
2181 while (first1 != last1 && first2 != last2)
2182 if (comp(*first1, *first2))
2184 else if (comp(*first2, *first1))
2195 template <class InputIterator1, class InputIterator2, class OutputIterator>
2196 OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1,
2197 InputIterator2 first2, InputIterator2 last2,
2198 OutputIterator result) {
2199 while (first1 != last1 && first2 != last2)
2200 if (*first1 < *first2) {
2205 else if (*first2 < *first1)
2211 return copy(first1, last1, result);
2214 template <class InputIterator1, class InputIterator2, class OutputIterator,
2216 OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1,
2217 InputIterator2 first2, InputIterator2 last2,
2218 OutputIterator result, Compare comp) {
2219 while (first1 != last1 && first2 != last2)
2220 if (comp(*first1, *first2)) {
2225 else if (comp(*first2, *first1))
2231 return copy(first1, last1, result);
2234 template <class InputIterator1, class InputIterator2, class OutputIterator>
2235 OutputIterator set_symmetric_difference(InputIterator1 first1,
2236 InputIterator1 last1,
2237 InputIterator2 first2,
2238 InputIterator2 last2,
2239 OutputIterator result) {
2240 while (first1 != last1 && first2 != last2)
2241 if (*first1 < *first2) {
2246 else if (*first2 < *first1) {
2255 return copy(first2, last2, copy(first1, last1, result));
2258 template <class InputIterator1, class InputIterator2, class OutputIterator,
2260 OutputIterator set_symmetric_difference(InputIterator1 first1,
2261 InputIterator1 last1,
2262 InputIterator2 first2,
2263 InputIterator2 last2,
2264 OutputIterator result, Compare comp) {
2265 while (first1 != last1 && first2 != last2)
2266 if (comp(*first1, *first2)) {
2271 else if (comp(*first2, *first1)) {
2280 return copy(first2, last2, copy(first1, last1, result));
2283 template <class ForwardIterator>
2284 ForwardIterator max_element(ForwardIterator first, ForwardIterator last) {
2285 if (first == last) return first;
2286 ForwardIterator result = first;
2287 while (++first != last)
2288 if (*result < *first) result = first;
2292 template <class ForwardIterator, class Compare>
2293 ForwardIterator max_element(ForwardIterator first, ForwardIterator last,
2295 if (first == last) return first;
2296 ForwardIterator result = first;
2297 while (++first != last)
2298 if (comp(*result, *first)) result = first;
2302 template <class ForwardIterator>
2303 ForwardIterator min_element(ForwardIterator first, ForwardIterator last) {
2304 if (first == last) return first;
2305 ForwardIterator result = first;
2306 while (++first != last)
2307 if (*first < *result) result = first;
2311 template <class ForwardIterator, class Compare>
2312 ForwardIterator min_element(ForwardIterator first, ForwardIterator last,
2314 if (first == last) return first;
2315 ForwardIterator result = first;
2316 while (++first != last)
2317 if (comp(*first, *result)) result = first;
2321 template <class BidirectionalIterator>
2322 bool next_permutation(BidirectionalIterator first,
2323 BidirectionalIterator last) {
2324 if (first == last) return false;
2325 BidirectionalIterator i = first;
2327 if (i == last) return false;
2332 BidirectionalIterator ii = i;
2335 BidirectionalIterator j = last;
2336 while (!(*i < *--j));
2342 reverse(first, last);
2348 template <class BidirectionalIterator, class Compare>
2349 bool next_permutation(BidirectionalIterator first, BidirectionalIterator last,
2351 if (first == last) return false;
2352 BidirectionalIterator i = first;
2354 if (i == last) return false;
2359 BidirectionalIterator ii = i;
2361 if (comp(*i, *ii)) {
2362 BidirectionalIterator j = last;
2363 while (!comp(*i, *--j));
2369 reverse(first, last);
2375 template <class BidirectionalIterator>
2376 bool prev_permutation(BidirectionalIterator first,
2377 BidirectionalIterator last) {
2378 if (first == last) return false;
2379 BidirectionalIterator i = first;
2381 if (i == last) return false;
2386 BidirectionalIterator ii = i;
2389 BidirectionalIterator j = last;
2390 while (!(*--j < *i));
2396 reverse(first, last);
2402 template <class BidirectionalIterator, class Compare>
2403 bool prev_permutation(BidirectionalIterator first, BidirectionalIterator last,
2405 if (first == last) return false;
2406 BidirectionalIterator i = first;
2408 if (i == last) return false;
2413 BidirectionalIterator ii = i;
2415 if (comp(*ii, *i)) {
2416 BidirectionalIterator j = last;
2417 while (!comp(*--j, *i));
2423 reverse(first, last);
2429 template <class InputIterator, class T>
2430 T accumulate(InputIterator first, InputIterator last, T init) {
2431 for ( ; first != last; ++first)
2432 init = init + *first;
2436 template <class InputIterator, class T, class BinaryOperation>
2437 T accumulate(InputIterator first, InputIterator last, T init,
2438 BinaryOperation binary_op) {
2439 for ( ; first != last; ++first)
2440 init = binary_op(init, *first);
2444 template <class InputIterator1, class InputIterator2, class T>
2445 T inner_product(InputIterator1 first1, InputIterator1 last1,
2446 InputIterator2 first2, T init) {
2447 for ( ; first1 != last1; ++first1, ++first2)
2448 init = init + (*first1 * *first2);
2452 template <class InputIterator1, class InputIterator2, class T,
2453 class BinaryOperation1, class BinaryOperation2>
2454 T inner_product(InputIterator1 first1, InputIterator1 last1,
2455 InputIterator2 first2, T init, BinaryOperation1 binary_op1,
2456 BinaryOperation2 binary_op2) {
2457 for ( ; first1 != last1; ++first1, ++first2)
2458 init = binary_op1(init, binary_op2(*first1, *first2));
2462 template <class InputIterator, class OutputIterator, class T>
2463 OutputIterator __partial_sum(InputIterator first, InputIterator last,
2464 OutputIterator result, T*) {
2466 while (++first != last) {
2467 value = value + *first;
2473 template <class InputIterator, class OutputIterator>
2474 OutputIterator partial_sum(InputIterator first, InputIterator last,
2475 OutputIterator result) {
2476 if (first == last) return result;
2478 return __partial_sum(first, last, result, value_type(first));
2481 template <class InputIterator, class OutputIterator, class T,
2482 class BinaryOperation>
2483 OutputIterator __partial_sum(InputIterator first, InputIterator last,
2484 OutputIterator result, T*,
2485 BinaryOperation binary_op) {
2487 while (++first != last) {
2488 value = binary_op(value, *first);
2494 template <class InputIterator, class OutputIterator, class BinaryOperation>
2495 OutputIterator partial_sum(InputIterator first, InputIterator last,
2496 OutputIterator result, BinaryOperation binary_op) {
2497 if (first == last) return result;
2499 return __partial_sum(first, last, result, value_type(first), binary_op);
2502 template <class InputIterator, class OutputIterator, class T>
2503 OutputIterator __adjacent_difference(InputIterator first, InputIterator last,
2504 OutputIterator result, T*) {
2506 while (++first != last) {
2508 *++result = tmp - value;
2514 template <class InputIterator, class OutputIterator>
2515 OutputIterator adjacent_difference(InputIterator first, InputIterator last,
2516 OutputIterator result) {
2517 if (first == last) return result;
2519 return __adjacent_difference(first, last, result, value_type(first));
2522 template <class InputIterator, class OutputIterator, class T,
2523 class BinaryOperation>
2524 OutputIterator __adjacent_difference(InputIterator first, InputIterator last,
2525 OutputIterator result, T*,
2526 BinaryOperation binary_op) {
2528 while (++first != last) {
2530 *++result = binary_op(tmp, value);
2536 template <class InputIterator, class OutputIterator, class BinaryOperation>
2537 OutputIterator adjacent_difference(InputIterator first, InputIterator last,
2538 OutputIterator result,
2539 BinaryOperation binary_op) {
2540 if (first == last) return result;
2542 return __adjacent_difference(first, last, result, value_type(first),
2546 // Returns x ** n, where n >= 0. Note that "multiplication"
2547 // is required to be associative, but not necessarily commutative.
2549 template <class T, class Integer, class MonoidOperation>
2550 T power(T x, Integer n, MonoidOperation op) {
2552 return identity_element(op);
2554 while (n % 2 == 0) {
2564 result = op(result, x);
2571 template <class T, class Integer>
2572 inline T power(T x, Integer n) {
2573 return power(x, n, multiplies<T>());
2577 template <class ForwardIterator, class T>
2578 void iota(ForwardIterator first, ForwardIterator last, T value) {
2579 while (first != last) *first++ = value++;
2582 template <class RandomAccessIterator, class Distance>
2583 bool __is_heap(RandomAccessIterator first, RandomAccessIterator last,
2586 const Distance n = last - first;
2588 Distance parent = 0;
2589 for (Distance child = 1; child < n; ++child) {
2590 if (first[parent] < first[child])
2598 template <class RandomAccessIterator>
2599 inline bool is_heap(RandomAccessIterator first, RandomAccessIterator last)
2601 return __is_heap(first, last, distance_type(first));
2605 template <class RandomAccessIterator, class Distance, class StrictWeakOrdering>
2606 bool __is_heap(RandomAccessIterator first, RandomAccessIterator last,
2607 StrictWeakOrdering comp,
2610 const Distance n = last - first;
2612 Distance parent = 0;
2613 for (Distance child = 1; child < n; ++child) {
2614 if (comp(first[parent], first[child]))
2622 template <class RandomAccessIterator, class StrictWeakOrdering>
2623 inline bool is_heap(RandomAccessIterator first, RandomAccessIterator last,
2624 StrictWeakOrdering comp)
2626 return __is_heap(first, last, comp, distance_type(first));
2630 template <class ForwardIterator>
2631 bool is_sorted(ForwardIterator first, ForwardIterator last)
2636 ForwardIterator next = first;
2637 for (++next; next != last; first = next, ++next) {
2645 template <class ForwardIterator, class StrictWeakOrdering>
2646 bool is_sorted(ForwardIterator first, ForwardIterator last,
2647 StrictWeakOrdering comp)
2652 ForwardIterator next = first;
2653 for (++next; next != last; first = next, ++next) {
2654 if (comp(*next, *first))
2661 #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
2662 #pragma reset woff 1209
2665 #endif /* __SGI_STL_ALGO_H */