37 #ifndef _GLIBCXX_PARALLEL_ALGO_H
38 #define _GLIBCXX_PARALLEL_ALGO_H 1
66 template<
typename InputIterator,
typename Function>
68 for_each(InputIterator begin, InputIterator end, Function f,
70 {
return _GLIBCXX_STD_P::for_each(begin, end, f); }
74 template<
typename InputIterator,
typename Function,
typename IteratorTag>
76 for_each_switch(InputIterator begin, InputIterator end, Function f,
81 template<
typename RandomAccessIterator,
typename Function>
83 for_each_switch(RandomAccessIterator begin, RandomAccessIterator end,
84 Function f, random_access_iterator_tag,
89 static_cast<__gnu_parallel::sequence_index_t>(end - begin)
91 && __gnu_parallel::is_parallel(parallelism_tag)))
99 true, dummy, -1, parallelism_tag);
106 template<
typename Iterator,
typename Function>
108 for_each(Iterator begin, Iterator end, Function f,
112 typedef typename iterator_traits::iterator_category iterator_category;
113 return for_each_switch(begin, end, f, iterator_category(),
117 template<
typename Iterator,
typename Function>
119 for_each(Iterator begin, Iterator end, Function f)
122 typedef typename iterator_traits::iterator_category iterator_category;
123 return for_each_switch(begin, end, f, iterator_category());
128 template<
typename InputIterator,
typename T>
130 find(InputIterator begin, InputIterator end,
const T& val,
132 {
return _GLIBCXX_STD_P::find(begin, end, val); }
135 template<
typename InputIterator,
typename T,
typename IteratorTag>
137 find_switch(InputIterator begin, InputIterator end,
const T& val,
139 {
return _GLIBCXX_STD_P::find(begin, end, val); }
142 template<
typename RandomAccessIterator,
typename T>
144 find_switch(RandomAccessIterator begin, RandomAccessIterator end,
145 const T& val, random_access_iterator_tag)
147 typedef iterator_traits<RandomAccessIterator> traits_type;
148 typedef typename traits_type::value_type value_type;
152 binder2nd<__gnu_parallel::equal_to<value_type, const T&> >
156 find_if_selector()).first;
159 return _GLIBCXX_STD_P::find(begin, end, val);
163 template<
typename InputIterator,
typename T>
165 find(InputIterator begin, InputIterator end,
const T& val)
168 typedef typename iterator_traits::iterator_category iterator_category;
169 return find_switch(begin, end, val, iterator_category());
173 template<
typename InputIterator,
typename Predicate>
175 find_if(InputIterator begin, InputIterator end, Predicate pred,
177 {
return _GLIBCXX_STD_P::find_if(begin, end, pred); }
180 template<
typename InputIterator,
typename Predicate,
typename IteratorTag>
182 find_if_switch(InputIterator begin, InputIterator end, Predicate pred,
184 {
return _GLIBCXX_STD_P::find_if(begin, end, pred); }
187 template<
typename RandomAccessIterator,
typename Predicate>
189 find_if_switch(RandomAccessIterator begin, RandomAccessIterator end,
190 Predicate pred, random_access_iterator_tag)
195 find_if_selector()).first;
197 return _GLIBCXX_STD_P::find_if(begin, end, pred);
201 template<
typename InputIterator,
typename Predicate>
203 find_if(InputIterator begin, InputIterator end, Predicate pred)
206 typedef typename iterator_traits::iterator_category iterator_category;
207 return find_if_switch(begin, end, pred, iterator_category());
211 template<
typename InputIterator,
typename ForwardIterator>
213 find_first_of(InputIterator begin1, InputIterator end1,
214 ForwardIterator begin2, ForwardIterator end2,
216 {
return _GLIBCXX_STD_P::find_first_of(begin1, end1, begin2, end2); }
219 template<
typename InputIterator,
typename ForwardIterator,
220 typename BinaryPredicate>
222 find_first_of(InputIterator begin1, InputIterator end1,
223 ForwardIterator begin2, ForwardIterator end2,
225 {
return _GLIBCXX_STD_P::find_first_of(begin1, end1, begin2, end2, comp); }
228 template<
typename InputIterator,
typename ForwardIterator,
229 typename IteratorTag1,
typename IteratorTag2>
231 find_first_of_switch(InputIterator begin1, InputIterator end1,
232 ForwardIterator begin2, ForwardIterator end2,
233 IteratorTag1, IteratorTag2)
234 {
return find_first_of(begin1, end1, begin2, end2,
238 template<
typename RandomAccessIterator,
typename ForwardIterator,
239 typename BinaryPredicate,
typename IteratorTag>
240 inline RandomAccessIterator
241 find_first_of_switch(RandomAccessIterator begin1,
242 RandomAccessIterator end1,
243 ForwardIterator begin2, ForwardIterator end2,
244 BinaryPredicate comp, random_access_iterator_tag,
250 <ForwardIterator>(begin2, end2)).first;
254 template<
typename InputIterator,
typename ForwardIterator,
255 typename BinaryPredicate,
typename IteratorTag1,
256 typename IteratorTag2>
258 find_first_of_switch(InputIterator begin1, InputIterator end1,
259 ForwardIterator begin2, ForwardIterator end2,
260 BinaryPredicate comp, IteratorTag1, IteratorTag2)
261 {
return find_first_of(begin1, end1, begin2, end2, comp,
265 template<
typename InputIterator,
typename ForwardIterator,
266 typename BinaryPredicate>
268 find_first_of(InputIterator begin1, InputIterator end1,
269 ForwardIterator begin2, ForwardIterator end2,
270 BinaryPredicate comp)
274 typedef typename iteratori_traits::iterator_category iteratori_category;
275 typedef typename iteratorf_traits::iterator_category iteratorf_category;
277 return find_first_of_switch(begin1, end1, begin2, end2, comp,
278 iteratori_category(), iteratorf_category());
282 template<
typename InputIterator,
typename ForwardIterator>
284 find_first_of(InputIterator begin1, InputIterator end1,
285 ForwardIterator begin2, ForwardIterator end2)
289 typedef typename iteratori_traits::value_type valuei_type;
290 typedef typename iteratorf_traits::value_type valuef_type;
292 return _GLIBCXX_STD_P::find_first_of(begin1, end1, begin2, end2,
297 template<
typename InputIterator,
typename OutputIterator>
298 inline OutputIterator
299 unique_copy(InputIterator begin1, InputIterator end1, OutputIterator out,
301 {
return _GLIBCXX_STD_P::unique_copy(begin1, end1, out); }
304 template<
typename InputIterator,
typename OutputIterator,
306 inline OutputIterator
307 unique_copy(InputIterator begin1, InputIterator end1, OutputIterator out,
309 {
return _GLIBCXX_STD_P::unique_copy(begin1, end1, out, pred); }
312 template<
typename InputIterator,
typename OutputIterator,
313 typename Predicate,
typename IteratorTag1,
typename IteratorTag2>
314 inline OutputIterator
315 unique_copy_switch(InputIterator begin, InputIterator last,
316 OutputIterator out, Predicate pred,
317 IteratorTag1, IteratorTag2)
318 {
return _GLIBCXX_STD_P::unique_copy(begin, last, out, pred); }
321 template<
typename RandomAccessIterator,
typename RandomAccessOutputIterator,
323 RandomAccessOutputIterator
324 unique_copy_switch(RandomAccessIterator begin, RandomAccessIterator last,
325 RandomAccessOutputIterator out, Predicate pred,
326 random_access_iterator_tag, random_access_iterator_tag)
329 static_cast<__gnu_parallel::sequence_index_t>(last - begin)
333 return _GLIBCXX_STD_P::unique_copy(begin, last, out, pred);
337 template<
typename InputIterator,
typename OutputIterator>
338 inline OutputIterator
339 unique_copy(InputIterator begin1, InputIterator end1, OutputIterator out)
343 typedef typename iteratori_traits::iterator_category iteratori_category;
344 typedef typename iteratori_traits::value_type value_type;
345 typedef typename iteratoro_traits::iterator_category iteratoro_category;
347 return unique_copy_switch(begin1, end1, out, equal_to<value_type>(),
348 iteratori_category(), iteratoro_category());
352 template<
typename InputIterator,
typename OutputIterator,
typename Predicate>
353 inline OutputIterator
354 unique_copy(InputIterator begin1, InputIterator end1, OutputIterator out,
359 typedef typename iteratori_traits::iterator_category iteratori_category;
360 typedef typename iteratoro_traits::iterator_category iteratoro_category;
362 return unique_copy_switch(begin1, end1, out, pred, iteratori_category(),
363 iteratoro_category());
367 template<
typename InputIterator1,
typename InputIterator2,
368 typename OutputIterator>
369 inline OutputIterator
370 set_union(InputIterator1 begin1, InputIterator1 end1,
371 InputIterator2 begin2, InputIterator2 end2,
373 {
return _GLIBCXX_STD_P::set_union(begin1, end1, begin2, end2, out); }
376 template<
typename InputIterator1,
typename InputIterator2,
377 typename OutputIterator,
typename Predicate>
378 inline OutputIterator
379 set_union(InputIterator1 begin1, InputIterator1 end1,
380 InputIterator2 begin2, InputIterator2 end2,
381 OutputIterator out, Predicate pred,
383 {
return _GLIBCXX_STD_P::set_union(begin1, end1,
384 begin2, end2, out, pred); }
387 template<
typename InputIterator1,
typename InputIterator2,
388 typename Predicate,
typename OutputIterator,
389 typename IteratorTag1,
typename IteratorTag2,
typename IteratorTag3>
390 inline OutputIterator
391 set_union_switch(InputIterator1 begin1, InputIterator1 end1,
392 InputIterator2 begin2, InputIterator2 end2,
393 OutputIterator result, Predicate pred, IteratorTag1,
394 IteratorTag2, IteratorTag3)
395 {
return _GLIBCXX_STD_P::set_union(begin1, end1,
396 begin2, end2, result, pred); }
399 template<
typename RandomAccessIterator1,
typename RandomAccessIterator2,
400 typename OutputRandomAccessIterator,
typename Predicate>
401 OutputRandomAccessIterator
402 set_union_switch(RandomAccessIterator1 begin1, RandomAccessIterator1 end1,
403 RandomAccessIterator2 begin2, RandomAccessIterator2 end2,
404 OutputRandomAccessIterator result, Predicate pred,
405 random_access_iterator_tag, random_access_iterator_tag,
406 random_access_iterator_tag)
409 static_cast<__gnu_parallel::sequence_index_t>(end1 - begin1)
411 || static_cast<__gnu_parallel::sequence_index_t>(end2 - begin2)
413 return __gnu_parallel::parallel_set_union(begin1, end1,
414 begin2, end2, result, pred);
416 return _GLIBCXX_STD_P::set_union(begin1, end1,
417 begin2, end2, result, pred);
421 template<
typename InputIterator1,
typename InputIterator2,
422 typename OutputIterator>
423 inline OutputIterator
424 set_union(InputIterator1 begin1, InputIterator1 end1,
425 InputIterator2 begin2, InputIterator2 end2, OutputIterator out)
430 typedef typename iteratori1_traits::iterator_category
432 typedef typename iteratori2_traits::iterator_category
434 typedef typename iteratoro_traits::iterator_category iteratoro_category;
435 typedef typename iteratori1_traits::value_type value1_type;
436 typedef typename iteratori2_traits::value_type value2_type;
438 return set_union_switch(begin1, end1, begin2, end2, out,
440 iteratori1_category(), iteratori2_category(),
441 iteratoro_category());
445 template<
typename InputIterator1,
typename InputIterator2,
446 typename OutputIterator,
typename Predicate>
447 inline OutputIterator
448 set_union(InputIterator1 begin1, InputIterator1 end1,
449 InputIterator2 begin2, InputIterator2 end2,
450 OutputIterator out, Predicate pred)
455 typedef typename iteratori1_traits::iterator_category
457 typedef typename iteratori2_traits::iterator_category
459 typedef typename iteratoro_traits::iterator_category iteratoro_category;
461 return set_union_switch(begin1, end1, begin2, end2, out, pred,
462 iteratori1_category(), iteratori2_category(),
463 iteratoro_category());
467 template<
typename InputIterator1,
typename InputIterator2,
468 typename OutputIterator>
469 inline OutputIterator
470 set_intersection(InputIterator1 begin1, InputIterator1 end1,
471 InputIterator2 begin2, InputIterator2 end2,
473 {
return _GLIBCXX_STD_P::set_intersection(begin1, end1,
474 begin2, end2, out); }
477 template<
typename InputIterator1,
typename InputIterator2,
478 typename OutputIterator,
typename Predicate>
479 inline OutputIterator
480 set_intersection(InputIterator1 begin1, InputIterator1 end1,
481 InputIterator2 begin2, InputIterator2 end2,
482 OutputIterator out, Predicate pred,
484 {
return _GLIBCXX_STD_P::set_intersection(begin1, end1, begin2, end2,
488 template<
typename InputIterator1,
typename InputIterator2,
489 typename Predicate,
typename OutputIterator,
490 typename IteratorTag1,
typename IteratorTag2,
491 typename IteratorTag3>
492 inline OutputIterator
493 set_intersection_switch(InputIterator1 begin1, InputIterator1 end1,
494 InputIterator2 begin2, InputIterator2 end2,
495 OutputIterator result, Predicate pred,
496 IteratorTag1, IteratorTag2, IteratorTag3)
497 {
return _GLIBCXX_STD_P::set_intersection(begin1, end1, begin2,
498 end2, result, pred); }
501 template<
typename RandomAccessIterator1,
typename RandomAccessIterator2,
502 typename OutputRandomAccessIterator,
typename Predicate>
503 OutputRandomAccessIterator
504 set_intersection_switch(RandomAccessIterator1 begin1,
505 RandomAccessIterator1 end1,
506 RandomAccessIterator2 begin2,
507 RandomAccessIterator2 end2,
508 OutputRandomAccessIterator result,
510 random_access_iterator_tag,
511 random_access_iterator_tag,
512 random_access_iterator_tag)
515 static_cast<__gnu_parallel::sequence_index_t>(end1 - begin1)
517 || static_cast<__gnu_parallel::sequence_index_t>(end2 - begin2)
519 return __gnu_parallel::parallel_set_intersection(begin1, end1, begin2,
522 return _GLIBCXX_STD_P::set_intersection(begin1, end1, begin2,
527 template<
typename InputIterator1,
typename InputIterator2,
528 typename OutputIterator>
529 inline OutputIterator
530 set_intersection(InputIterator1 begin1, InputIterator1 end1,
531 InputIterator2 begin2, InputIterator2 end2,
537 typedef typename iteratori1_traits::iterator_category
539 typedef typename iteratori2_traits::iterator_category
541 typedef typename iteratoro_traits::iterator_category iteratoro_category;
542 typedef typename iteratori1_traits::value_type value1_type;
543 typedef typename iteratori2_traits::value_type value2_type;
545 return set_intersection_switch(begin1, end1, begin2, end2, out,
547 less<value1_type, value2_type>(),
548 iteratori1_category(),
549 iteratori2_category(),
550 iteratoro_category());
553 template<
typename InputIterator1,
typename InputIterator2,
554 typename OutputIterator,
typename Predicate>
555 inline OutputIterator
556 set_intersection(InputIterator1 begin1, InputIterator1 end1,
557 InputIterator2 begin2, InputIterator2 end2,
558 OutputIterator out, Predicate pred)
563 typedef typename iteratori1_traits::iterator_category
565 typedef typename iteratori2_traits::iterator_category
567 typedef typename iteratoro_traits::iterator_category iteratoro_category;
569 return set_intersection_switch(begin1, end1, begin2, end2, out, pred,
570 iteratori1_category(),
571 iteratori2_category(),
572 iteratoro_category());
576 template<
typename InputIterator1,
typename InputIterator2,
577 typename OutputIterator>
578 inline OutputIterator
579 set_symmetric_difference(InputIterator1 begin1, InputIterator1 end1,
580 InputIterator2 begin2, InputIterator2 end2,
583 {
return _GLIBCXX_STD_P::set_symmetric_difference(begin1,end1,
584 begin2, end2, out); }
587 template<
typename InputIterator1,
typename InputIterator2,
588 typename OutputIterator,
typename Predicate>
589 inline OutputIterator
590 set_symmetric_difference(InputIterator1 begin1, InputIterator1 end1,
591 InputIterator2 begin2, InputIterator2 end2,
592 OutputIterator out, Predicate pred,
594 {
return _GLIBCXX_STD_P::set_symmetric_difference(begin1, end1, begin2,
598 template<
typename InputIterator1,
typename InputIterator2,
599 typename Predicate,
typename OutputIterator,
600 typename IteratorTag1,
typename IteratorTag2,
601 typename IteratorTag3>
602 inline OutputIterator
603 set_symmetric_difference_switch(InputIterator1 begin1,
605 InputIterator2 begin2,
607 OutputIterator result, Predicate pred,
608 IteratorTag1, IteratorTag2, IteratorTag3)
609 {
return _GLIBCXX_STD_P::set_symmetric_difference(begin1, end1,
614 template<
typename RandomAccessIterator1,
typename RandomAccessIterator2,
615 typename OutputRandomAccessIterator,
typename Predicate>
616 OutputRandomAccessIterator
617 set_symmetric_difference_switch(RandomAccessIterator1 begin1,
618 RandomAccessIterator1 end1,
619 RandomAccessIterator2 begin2,
620 RandomAccessIterator2 end2,
621 OutputRandomAccessIterator result,
623 random_access_iterator_tag,
624 random_access_iterator_tag,
625 random_access_iterator_tag)
628 static_cast<__gnu_parallel::sequence_index_t>(end1 - begin1)
630 || static_cast<__gnu_parallel::sequence_index_t>(end2 - begin2)
632 return __gnu_parallel::parallel_set_symmetric_difference(begin1, end1,
636 return _GLIBCXX_STD_P::set_symmetric_difference(begin1, end1,
642 template<
typename InputIterator1,
typename InputIterator2,
643 typename OutputIterator>
644 inline OutputIterator
645 set_symmetric_difference(InputIterator1 begin1, InputIterator1 end1,
646 InputIterator2 begin2, InputIterator2 end2,
652 typedef typename iteratori1_traits::iterator_category
654 typedef typename iteratori2_traits::iterator_category
656 typedef typename iteratoro_traits::iterator_category iteratoro_category;
657 typedef typename iteratori1_traits::value_type value1_type;
658 typedef typename iteratori2_traits::value_type value2_type;
660 return set_symmetric_difference_switch(begin1, end1, begin2, end2, out,
662 less<value1_type, value2_type>(),
663 iteratori1_category(),
664 iteratori2_category(),
665 iteratoro_category());
669 template<
typename InputIterator1,
typename InputIterator2,
670 typename OutputIterator,
typename Predicate>
671 inline OutputIterator
672 set_symmetric_difference(InputIterator1 begin1, InputIterator1 end1,
673 InputIterator2 begin2, InputIterator2 end2,
674 OutputIterator out, Predicate pred)
679 typedef typename iteratori1_traits::iterator_category
681 typedef typename iteratori2_traits::iterator_category
683 typedef typename iteratoro_traits::iterator_category iteratoro_category;
685 return set_symmetric_difference_switch(begin1, end1, begin2, end2, out,
686 pred, iteratori1_category(),
687 iteratori2_category(),
688 iteratoro_category());
692 template<
typename InputIterator1,
typename InputIterator2,
693 typename OutputIterator>
694 inline OutputIterator
695 set_difference(InputIterator1 begin1, InputIterator1 end1,
696 InputIterator2 begin2, InputIterator2 end2,
698 {
return _GLIBCXX_STD_P::set_difference(begin1,end1, begin2, end2, out); }
701 template<
typename InputIterator1,
typename InputIterator2,
702 typename OutputIterator,
typename Predicate>
703 inline OutputIterator
704 set_difference(InputIterator1 begin1, InputIterator1 end1,
705 InputIterator2 begin2, InputIterator2 end2,
706 OutputIterator out, Predicate pred,
708 {
return _GLIBCXX_STD_P::set_difference(begin1, end1,
709 begin2, end2, out, pred); }
712 template<
typename InputIterator1,
typename InputIterator2,
713 typename Predicate,
typename OutputIterator,
714 typename IteratorTag1,
typename IteratorTag2,
typename IteratorTag3>
715 inline OutputIterator
716 set_difference_switch(InputIterator1 begin1, InputIterator1 end1,
717 InputIterator2 begin2, InputIterator2 end2,
718 OutputIterator result, Predicate pred,
719 IteratorTag1, IteratorTag2, IteratorTag3)
720 {
return _GLIBCXX_STD_P::set_difference(begin1, end1,
721 begin2, end2, result, pred); }
724 template<
typename RandomAccessIterator1,
typename RandomAccessIterator2,
725 typename OutputRandomAccessIterator,
typename Predicate>
726 OutputRandomAccessIterator
727 set_difference_switch(RandomAccessIterator1 begin1,
728 RandomAccessIterator1 end1,
729 RandomAccessIterator2 begin2,
730 RandomAccessIterator2 end2,
731 OutputRandomAccessIterator result, Predicate pred,
732 random_access_iterator_tag,
733 random_access_iterator_tag,
734 random_access_iterator_tag)
737 static_cast<__gnu_parallel::sequence_index_t>(end1 - begin1)
739 || static_cast<__gnu_parallel::sequence_index_t>(end2 - begin2)
741 return __gnu_parallel::parallel_set_difference(begin1, end1,
745 return _GLIBCXX_STD_P::set_difference(begin1, end1,
746 begin2, end2, result, pred);
750 template<
typename InputIterator1,
typename InputIterator2,
751 typename OutputIterator>
752 inline OutputIterator
753 set_difference(InputIterator1 begin1, InputIterator1 end1,
754 InputIterator2 begin2, InputIterator2 end2,
760 typedef typename iteratori1_traits::iterator_category
762 typedef typename iteratori2_traits::iterator_category
764 typedef typename iteratoro_traits::iterator_category iteratoro_category;
765 typedef typename iteratori1_traits::value_type value1_type;
766 typedef typename iteratori2_traits::value_type value2_type;
768 return set_difference_switch(begin1, end1, begin2, end2, out,
770 less<value1_type, value2_type>(),
771 iteratori1_category(),
772 iteratori2_category(),
773 iteratoro_category());
777 template<
typename InputIterator1,
typename InputIterator2,
778 typename OutputIterator,
typename Predicate>
779 inline OutputIterator
780 set_difference(InputIterator1 begin1, InputIterator1 end1,
781 InputIterator2 begin2, InputIterator2 end2,
782 OutputIterator out, Predicate pred)
787 typedef typename iteratori1_traits::iterator_category
789 typedef typename iteratori2_traits::iterator_category
791 typedef typename iteratoro_traits::iterator_category iteratoro_category;
793 return set_difference_switch(begin1, end1, begin2, end2, out, pred,
794 iteratori1_category(),
795 iteratori2_category(),
796 iteratoro_category());
800 template<
typename ForwardIterator>
801 inline ForwardIterator
802 adjacent_find(ForwardIterator begin, ForwardIterator end,
804 {
return _GLIBCXX_STD_P::adjacent_find(begin, end); }
807 template<
typename ForwardIterator,
typename BinaryPredicate>
808 inline ForwardIterator
809 adjacent_find(ForwardIterator begin, ForwardIterator end,
811 {
return _GLIBCXX_STD_P::adjacent_find(begin, end, binary_pred); }
814 template<
typename RandomAccessIterator>
816 adjacent_find_switch(RandomAccessIterator begin, RandomAccessIterator end,
817 random_access_iterator_tag)
819 typedef iterator_traits<RandomAccessIterator> traits_type;
820 typedef typename traits_type::value_type value_type;
827 if (spot == (end - 1))
837 template<
typename ForwardIterator,
typename IteratorTag>
838 inline ForwardIterator
839 adjacent_find_switch(ForwardIterator begin, ForwardIterator end,
844 template<
typename ForwardIterator>
845 inline ForwardIterator
846 adjacent_find(ForwardIterator begin, ForwardIterator end)
848 typedef iterator_traits<ForwardIterator> traits_type;
849 typedef typename traits_type::iterator_category iterator_category;
850 return adjacent_find_switch(begin, end, iterator_category());
854 template<
typename ForwardIterator,
typename BinaryPredicate,
855 typename IteratorTag>
856 inline ForwardIterator
857 adjacent_find_switch(ForwardIterator begin, ForwardIterator end,
858 BinaryPredicate pred, IteratorTag)
859 {
return adjacent_find(begin, end, pred,
863 template<
typename RandomAccessIterator,
typename BinaryPredicate>
865 adjacent_find_switch(RandomAccessIterator begin, RandomAccessIterator end,
866 BinaryPredicate pred, random_access_iterator_tag)
871 adjacent_find_selector()).first;
873 return adjacent_find(begin, end, pred,
878 template<
typename ForwardIterator,
typename BinaryPredicate>
879 inline ForwardIterator
880 adjacent_find(ForwardIterator begin, ForwardIterator end,
881 BinaryPredicate pred)
883 typedef iterator_traits<ForwardIterator> traits_type;
884 typedef typename traits_type::iterator_category iterator_category;
885 return adjacent_find_switch(begin, end, pred, iterator_category());
889 template<
typename InputIterator,
typename T>
890 inline typename iterator_traits<InputIterator>::difference_type
891 count(InputIterator begin, InputIterator end,
const T& value,
893 {
return _GLIBCXX_STD_P::count(begin, end, value); }
896 template<
typename RandomAccessIterator,
typename T>
897 typename iterator_traits<RandomAccessIterator>::difference_type
898 count_switch(RandomAccessIterator begin, RandomAccessIterator end,
899 const T& value, random_access_iterator_tag,
903 typedef iterator_traits<RandomAccessIterator> traits_type;
904 typedef typename traits_type::value_type value_type;
905 typedef typename traits_type::difference_type difference_type;
909 static_cast<sequence_index_t>(end - begin)
911 && __gnu_parallel::is_parallel(parallelism_tag)))
915 difference_type res = 0;
920 res, res, -1, parallelism_tag);
928 template<
typename InputIterator,
typename T,
typename IteratorTag>
929 inline typename iterator_traits<InputIterator>::difference_type
930 count_switch(InputIterator begin, InputIterator end,
const T& value,
935 template<
typename InputIterator,
typename T>
936 inline typename iterator_traits<InputIterator>::difference_type
937 count(InputIterator begin, InputIterator end,
const T& value,
940 typedef iterator_traits<InputIterator> traits_type;
941 typedef typename traits_type::iterator_category iterator_category;
942 return count_switch(begin, end, value, iterator_category(),
946 template<
typename InputIterator,
typename T>
947 inline typename iterator_traits<InputIterator>::difference_type
948 count(InputIterator begin, InputIterator end,
const T& value)
950 typedef iterator_traits<InputIterator> traits_type;
951 typedef typename traits_type::iterator_category iterator_category;
952 return count_switch(begin, end, value, iterator_category());
957 template<
typename InputIterator,
typename Predicate>
958 inline typename iterator_traits<InputIterator>::difference_type
959 count_if(InputIterator begin, InputIterator end, Predicate pred,
961 {
return _GLIBCXX_STD_P::count_if(begin, end, pred); }
964 template<
typename RandomAccessIterator,
typename Predicate>
965 typename iterator_traits<RandomAccessIterator>::difference_type
966 count_if_switch(RandomAccessIterator begin, RandomAccessIterator end,
967 Predicate pred, random_access_iterator_tag,
971 typedef iterator_traits<RandomAccessIterator> traits_type;
972 typedef typename traits_type::value_type value_type;
973 typedef typename traits_type::difference_type difference_type;
977 static_cast<sequence_index_t>(end - begin)
979 && __gnu_parallel::is_parallel(parallelism_tag)))
981 difference_type res = 0;
989 res, res, -1, parallelism_tag);
997 template<
typename InputIterator,
typename Predicate,
typename IteratorTag>
998 inline typename iterator_traits<InputIterator>::difference_type
999 count_if_switch(InputIterator begin, InputIterator end, Predicate pred,
1004 template<
typename InputIterator,
typename Predicate>
1005 inline typename iterator_traits<InputIterator>::difference_type
1006 count_if(InputIterator begin, InputIterator end, Predicate pred,
1009 typedef iterator_traits<InputIterator> traits_type;
1010 typedef typename traits_type::iterator_category iterator_category;
1011 return count_if_switch(begin, end, pred, iterator_category(),
1015 template<
typename InputIterator,
typename Predicate>
1016 inline typename iterator_traits<InputIterator>::difference_type
1017 count_if(InputIterator begin, InputIterator end, Predicate pred)
1019 typedef iterator_traits<InputIterator> traits_type;
1020 typedef typename traits_type::iterator_category iterator_category;
1021 return count_if_switch(begin, end, pred, iterator_category());
1026 template<
typename ForwardIterator1,
typename ForwardIterator2>
1027 inline ForwardIterator1
1028 search(ForwardIterator1 begin1, ForwardIterator1 end1,
1029 ForwardIterator2 begin2, ForwardIterator2 end2,
1031 {
return _GLIBCXX_STD_P::search(begin1, end1, begin2, end2); }
1034 template<
typename RandomAccessIterator1,
typename RandomAccessIterator2>
1035 RandomAccessIterator1
1036 search_switch(RandomAccessIterator1 begin1, RandomAccessIterator1 end1,
1037 RandomAccessIterator2 begin2, RandomAccessIterator2 end2,
1038 random_access_iterator_tag, random_access_iterator_tag)
1041 typedef typename iterator1_traits::value_type value1_type;
1043 typedef typename iterator2_traits::value_type value2_type;
1048 equal_to<value1_type, value2_type>());
1050 return search(begin1, end1, begin2, end2,
1055 template<
typename ForwardIterator1,
typename ForwardIterator2,
1056 typename IteratorTag1,
typename IteratorTag2>
1057 inline ForwardIterator1
1058 search_switch(ForwardIterator1 begin1, ForwardIterator1 end1,
1059 ForwardIterator2 begin2, ForwardIterator2 end2,
1060 IteratorTag1, IteratorTag2)
1061 {
return search(begin1, end1, begin2, end2,
1065 template<
typename ForwardIterator1,
typename ForwardIterator2>
1066 inline ForwardIterator1
1067 search(ForwardIterator1 begin1, ForwardIterator1 end1,
1068 ForwardIterator2 begin2, ForwardIterator2 end2)
1071 typedef typename iterator1_traits::iterator_category iterator1_category;
1073 typedef typename iterator2_traits::iterator_category iterator2_category;
1075 return search_switch(begin1, end1, begin2, end2,
1076 iterator1_category(), iterator2_category());
1080 template<
typename ForwardIterator1,
typename ForwardIterator2,
1081 typename BinaryPredicate>
1082 inline ForwardIterator1
1083 search(ForwardIterator1 begin1, ForwardIterator1 end1,
1084 ForwardIterator2 begin2, ForwardIterator2 end2,
1086 {
return _GLIBCXX_STD_P::search(begin1, end1, begin2, end2, pred); }
1089 template<
typename RandomAccessIterator1,
typename RandomAccessIterator2,
1090 typename BinaryPredicate>
1091 RandomAccessIterator1
1092 search_switch(RandomAccessIterator1 begin1, RandomAccessIterator1 end1,
1093 RandomAccessIterator2 begin2, RandomAccessIterator2 end2,
1094 BinaryPredicate pred,
1095 random_access_iterator_tag, random_access_iterator_tag)
1099 begin2, end2, pred);
1101 return search(begin1, end1, begin2, end2, pred,
1106 template<
typename ForwardIterator1,
typename ForwardIterator2,
1107 typename BinaryPredicate,
typename IteratorTag1,
1108 typename IteratorTag2>
1109 inline ForwardIterator1
1110 search_switch(ForwardIterator1 begin1, ForwardIterator1 end1,
1111 ForwardIterator2 begin2, ForwardIterator2 end2,
1112 BinaryPredicate pred, IteratorTag1, IteratorTag2)
1113 {
return search(begin1, end1, begin2, end2, pred,
1117 template<
typename ForwardIterator1,
typename ForwardIterator2,
1118 typename BinaryPredicate>
1119 inline ForwardIterator1
1120 search(ForwardIterator1 begin1, ForwardIterator1 end1,
1121 ForwardIterator2 begin2, ForwardIterator2 end2,
1122 BinaryPredicate pred)
1125 typedef typename iterator1_traits::iterator_category iterator1_category;
1127 typedef typename iterator2_traits::iterator_category iterator2_category;
1128 return search_switch(begin1, end1, begin2, end2, pred,
1129 iterator1_category(), iterator2_category());
1133 template<
typename ForwardIterator,
typename Integer,
typename T>
1134 inline ForwardIterator
1135 search_n(ForwardIterator begin, ForwardIterator end, Integer count,
1137 {
return _GLIBCXX_STD_P::search_n(begin, end, count, val); }
1140 template<
typename ForwardIterator,
typename Integer,
typename T,
1141 typename BinaryPredicate>
1142 inline ForwardIterator
1143 search_n(ForwardIterator begin, ForwardIterator end, Integer count,
1144 const T& val, BinaryPredicate binary_pred,
1146 {
return _GLIBCXX_STD_P::search_n(begin, end, count, val, binary_pred); }
1149 template<
typename ForwardIterator,
typename Integer,
typename T>
1150 inline ForwardIterator
1151 search_n(ForwardIterator begin, ForwardIterator end, Integer count,
1154 typedef typename iterator_traits<ForwardIterator>::value_type value_type;
1155 return _GLIBCXX_STD_P::search_n(begin, end, count, val,
1160 template<
typename RandomAccessIterator,
typename Integer,
1161 typename T,
typename BinaryPredicate>
1162 RandomAccessIterator
1163 search_n_switch(RandomAccessIterator begin, RandomAccessIterator end,
1164 Integer count,
const T& val, BinaryPredicate binary_pred,
1165 random_access_iterator_tag)
1171 ps.end(), binary_pred);
1175 binary_pred, random_access_iterator_tag());
1179 template<
typename ForwardIterator,
typename Integer,
typename T,
1180 typename BinaryPredicate,
typename IteratorTag>
1181 inline ForwardIterator
1182 search_n_switch(ForwardIterator begin, ForwardIterator end, Integer count,
1183 const T& val, BinaryPredicate binary_pred, IteratorTag)
1184 {
return __search_n(begin, end, count, val, binary_pred, IteratorTag()); }
1187 template<
typename ForwardIterator,
typename Integer,
typename T,
1188 typename BinaryPredicate>
1189 inline ForwardIterator
1190 search_n(ForwardIterator begin, ForwardIterator end, Integer count,
1191 const T& val, BinaryPredicate binary_pred)
1193 return search_n_switch(begin, end, count, val, binary_pred,
1195 iterator_category());
1200 template<
typename InputIterator,
typename OutputIterator,
1201 typename UnaryOperation>
1202 inline OutputIterator
1203 transform(InputIterator begin, InputIterator end, OutputIterator result,
1205 {
return _GLIBCXX_STD_P::transform(begin, end, result, unary_op); }
1208 template<
typename RandomAccessIterator1,
typename RandomAccessIterator2,
1209 typename UnaryOperation>
1210 RandomAccessIterator2
1211 transform1_switch(RandomAccessIterator1 begin, RandomAccessIterator1 end,
1212 RandomAccessIterator2 result, UnaryOperation unary_op,
1213 random_access_iterator_tag, random_access_iterator_tag,
1218 static_cast<__gnu_parallel::sequence_index_t>(end - begin)
1220 && __gnu_parallel::is_parallel(parallelism_tag)))
1224 RandomAccessIterator2, random_access_iterator_tag> ip;
1225 ip begin_pair(begin, result), end_pair(end, result + (end - begin));
1229 unary_op, functionality,
1231 dummy, dummy, -1, parallelism_tag);
1235 return transform(begin, end, result, unary_op,
1240 template<
typename RandomAccessIterator1,
typename RandomAccessIterator2,
1241 typename UnaryOperation,
typename IteratorTag1,
1242 typename IteratorTag2>
1243 inline RandomAccessIterator2
1244 transform1_switch(RandomAccessIterator1 begin, RandomAccessIterator1 end,
1245 RandomAccessIterator2 result, UnaryOperation unary_op,
1246 IteratorTag1, IteratorTag2)
1247 {
return transform(begin, end, result, unary_op,
1251 template<
typename InputIterator,
typename OutputIterator,
1252 typename UnaryOperation>
1253 inline OutputIterator
1254 transform(InputIterator begin, InputIterator end, OutputIterator result,
1255 UnaryOperation unary_op,
1260 typedef typename iteratori_traits::iterator_category iteratori_category;
1261 typedef typename iteratoro_traits::iterator_category iteratoro_category;
1263 return transform1_switch(begin, end, result, unary_op,
1264 iteratori_category(), iteratoro_category(),
1268 template<
typename InputIterator,
typename OutputIterator,
1269 typename UnaryOperation>
1270 inline OutputIterator
1271 transform(InputIterator begin, InputIterator end, OutputIterator result,
1272 UnaryOperation unary_op)
1276 typedef typename iteratori_traits::iterator_category iteratori_category;
1277 typedef typename iteratoro_traits::iterator_category iteratoro_category;
1279 return transform1_switch(begin, end, result, unary_op,
1280 iteratori_category(), iteratoro_category());
1285 template<
typename InputIterator1,
typename InputIterator2,
1286 typename OutputIterator,
typename BinaryOperation>
1287 inline OutputIterator
1288 transform(InputIterator1 begin1, InputIterator1 end1,
1289 InputIterator2 begin2, OutputIterator result,
1291 {
return _GLIBCXX_STD_P::transform(begin1, end1,
1292 begin2, result, binary_op); }
1295 template<
typename RandomAccessIterator1,
typename RandomAccessIterator2,
1296 typename RandomAccessIterator3,
typename BinaryOperation>
1297 RandomAccessIterator3
1298 transform2_switch(RandomAccessIterator1 begin1, RandomAccessIterator1 end1,
1299 RandomAccessIterator2 begin2,
1300 RandomAccessIterator3 result, BinaryOperation binary_op,
1301 random_access_iterator_tag, random_access_iterator_tag,
1302 random_access_iterator_tag,
1309 && __gnu_parallel::is_parallel(parallelism_tag)))
1313 RandomAccessIterator2, RandomAccessIterator3,
1314 random_access_iterator_tag> ip;
1315 ip begin_triple(begin1, begin2, result),
1316 end_triple(end1, begin2 + (end1 - begin1),
1317 result + (end1 - begin1));
1321 binary_op, functionality,
1328 return transform(begin1, end1, begin2, result, binary_op,
1333 template<
typename InputIterator1,
typename InputIterator2,
1334 typename OutputIterator,
typename BinaryOperation,
1335 typename tag1,
typename tag2,
typename tag3>
1336 inline OutputIterator
1337 transform2_switch(InputIterator1 begin1, InputIterator1 end1,
1338 InputIterator2 begin2, OutputIterator result,
1339 BinaryOperation binary_op, tag1, tag2, tag3)
1340 {
return transform(begin1, end1, begin2, result, binary_op,
1344 template<
typename InputIterator1,
typename InputIterator2,
1345 typename OutputIterator,
typename BinaryOperation>
1346 inline OutputIterator
1347 transform(InputIterator1 begin1, InputIterator1 end1,
1348 InputIterator2 begin2, OutputIterator result,
1349 BinaryOperation binary_op,
1353 typedef typename iteratori1_traits::iterator_category
1354 iteratori1_category;
1356 typedef typename iteratori2_traits::iterator_category
1357 iteratori2_category;
1359 typedef typename iteratoro_traits::iterator_category iteratoro_category;
1361 return transform2_switch(begin1, end1, begin2, result, binary_op,
1362 iteratori1_category(), iteratori2_category(),
1363 iteratoro_category(), parallelism_tag);
1366 template<
typename InputIterator1,
typename InputIterator2,
1367 typename OutputIterator,
typename BinaryOperation>
1368 inline OutputIterator
1369 transform(InputIterator1 begin1, InputIterator1 end1,
1370 InputIterator2 begin2, OutputIterator result,
1371 BinaryOperation binary_op)
1374 typedef typename iteratori1_traits::iterator_category
1375 iteratori1_category;
1377 typedef typename iteratori2_traits::iterator_category
1378 iteratori2_category;
1380 typedef typename iteratoro_traits::iterator_category iteratoro_category;
1382 return transform2_switch(begin1, end1, begin2, result, binary_op,
1383 iteratori1_category(), iteratori2_category(),
1384 iteratoro_category());
1388 template<
typename ForwardIterator,
typename T>
1390 replace(ForwardIterator begin, ForwardIterator end,
const T& old_value,
1392 { _GLIBCXX_STD_P::replace(begin, end, old_value, new_value); }
1395 template<
typename ForwardIterator,
typename T,
typename IteratorTag>
1397 replace_switch(ForwardIterator begin, ForwardIterator end,
1398 const T& old_value,
const T& new_value, IteratorTag)
1399 { replace(begin, end, old_value, new_value,
1403 template<
typename RandomAccessIterator,
typename T>
1405 replace_switch(RandomAccessIterator begin, RandomAccessIterator end,
1406 const T& old_value,
const T& new_value,
1407 random_access_iterator_tag,
1412 replace(begin, end, old_value, new_value,
1417 template<
typename ForwardIterator,
typename T>
1419 replace(ForwardIterator begin, ForwardIterator end,
const T& old_value,
1422 typedef iterator_traits<ForwardIterator> traits_type;
1423 typedef typename traits_type::iterator_category iterator_category;
1424 replace_switch(begin, end, old_value, new_value, iterator_category(),
1428 template<
typename ForwardIterator,
typename T>
1430 replace(ForwardIterator begin, ForwardIterator end,
const T& old_value,
1433 typedef iterator_traits<ForwardIterator> traits_type;
1434 typedef typename traits_type::iterator_category iterator_category;
1435 replace_switch(begin, end, old_value, new_value, iterator_category());
1440 template<
typename ForwardIterator,
typename Predicate,
typename T>
1442 replace_if(ForwardIterator begin, ForwardIterator end, Predicate pred,
1444 { _GLIBCXX_STD_P::replace_if(begin, end, pred, new_value); }
1447 template<
typename ForwardIterator,
typename Predicate,
typename T,
1448 typename IteratorTag>
1450 replace_if_switch(ForwardIterator begin, ForwardIterator end,
1451 Predicate pred,
const T& new_value, IteratorTag)
1452 { replace_if(begin, end, pred, new_value,
1456 template<
typename RandomAccessIterator,
typename Predicate,
typename T>
1458 replace_if_switch(RandomAccessIterator begin, RandomAccessIterator end,
1459 Predicate pred,
const T& new_value,
1460 random_access_iterator_tag,
1465 static_cast<__gnu_parallel::sequence_index_t>(end - begin)
1467 && __gnu_parallel::is_parallel(parallelism_tag)))
1472 functionality(new_value);
1477 true, dummy, -1, parallelism_tag);
1480 replace_if(begin, end, pred, new_value,
1485 template<
typename ForwardIterator,
typename Predicate,
typename T>
1487 replace_if(ForwardIterator begin, ForwardIterator end,
1488 Predicate pred,
const T& new_value,
1492 typedef typename iterator_traits::iterator_category iterator_category;
1493 replace_if_switch(begin, end, pred, new_value, iterator_category(),
1497 template<
typename ForwardIterator,
typename Predicate,
typename T>
1499 replace_if(ForwardIterator begin, ForwardIterator end,
1500 Predicate pred,
const T& new_value)
1503 typedef typename iterator_traits::iterator_category iterator_category;
1504 replace_if_switch(begin, end, pred, new_value, iterator_category());
1508 template<
typename ForwardIterator,
typename Generator>
1510 generate(ForwardIterator begin, ForwardIterator end, Generator gen,
1512 { _GLIBCXX_STD_P::generate(begin, end, gen); }
1515 template<
typename ForwardIterator,
typename Generator,
typename IteratorTag>
1517 generate_switch(ForwardIterator begin, ForwardIterator end, Generator gen,
1522 template<
typename RandomAccessIterator,
typename Generator>
1524 generate_switch(RandomAccessIterator begin, RandomAccessIterator end,
1525 Generator gen, random_access_iterator_tag,
1530 static_cast<__gnu_parallel::sequence_index_t>(end - begin)
1532 && __gnu_parallel::is_parallel(parallelism_tag)))
1540 true, dummy, -1, parallelism_tag);
1547 template<
typename ForwardIterator,
typename Generator>
1549 generate(ForwardIterator begin, ForwardIterator end,
1553 typedef typename iterator_traits::iterator_category iterator_category;
1554 generate_switch(begin, end, gen, iterator_category(), parallelism_tag);
1557 template<
typename ForwardIterator,
typename Generator>
1559 generate(ForwardIterator begin, ForwardIterator end, Generator gen)
1562 typedef typename iterator_traits::iterator_category iterator_category;
1563 generate_switch(begin, end, gen, iterator_category());
1568 template<
typename OutputIterator,
typename Size,
typename Generator>
1569 inline OutputIterator
1570 generate_n(OutputIterator begin, Size n, Generator gen,
1572 {
return _GLIBCXX_STD_P::generate_n(begin, n, gen); }
1575 template<
typename OutputIterator,
typename Size,
typename Generator,
1576 typename IteratorTag>
1577 inline OutputIterator
1578 generate_n_switch(OutputIterator begin, Size n, Generator gen, IteratorTag)
1582 template<
typename RandomAccessIterator,
typename Size,
typename Generator>
1583 inline RandomAccessIterator
1584 generate_n_switch(RandomAccessIterator begin, Size n, Generator gen,
1585 random_access_iterator_tag,
1594 template<
typename OutputIterator,
typename Size,
typename Generator>
1595 inline OutputIterator
1596 generate_n(OutputIterator begin, Size n, Generator gen,
1600 typedef typename iterator_traits::iterator_category iterator_category;
1601 return generate_n_switch(begin, n, gen, iterator_category(),
1605 template<
typename OutputIterator,
typename Size,
typename Generator>
1606 inline OutputIterator
1607 generate_n(OutputIterator begin, Size n, Generator gen)
1610 typedef typename iterator_traits::iterator_category iterator_category;
1611 return generate_n_switch(begin, n, gen, iterator_category());
1616 template<
typename RandomAccessIterator>
1618 random_shuffle(RandomAccessIterator begin, RandomAccessIterator end,
1620 { _GLIBCXX_STD_P::random_shuffle(begin, end); }
1623 template<
typename RandomAccessIterator,
typename RandomNumberGenerator>
1625 random_shuffle(RandomAccessIterator begin, RandomAccessIterator end,
1627 { _GLIBCXX_STD_P::random_shuffle(begin, end, rand); }
1631 template<
typename must_be_
int =
int>
1635 operator()(
int limit)
1636 {
return rand() % limit; }
1640 template<
typename RandomAccessIterator>
1642 random_shuffle(RandomAccessIterator begin, RandomAccessIterator end)
1646 __gnu_parallel::random_shuffle(begin, end, r);
1650 template<
typename RandomAccessIterator,
typename RandomNumberGenerator>
1652 random_shuffle(RandomAccessIterator begin, RandomAccessIterator end,
1653 RandomNumberGenerator& rand)
1658 static_cast<__gnu_parallel::sequence_index_t>(end - begin)
1666 template<
typename ForwardIterator,
typename Predicate>
1667 inline ForwardIterator
1668 partition(ForwardIterator begin, ForwardIterator end,
1670 {
return _GLIBCXX_STD_P::partition(begin, end, pred); }
1673 template<
typename ForwardIterator,
typename Predicate,
typename IteratorTag>
1674 inline ForwardIterator
1675 partition_switch(ForwardIterator begin, ForwardIterator end,
1676 Predicate pred, IteratorTag)
1680 template<
typename RandomAccessIterator,
typename Predicate>
1681 RandomAccessIterator
1682 partition_switch(RandomAccessIterator begin, RandomAccessIterator end,
1683 Predicate pred, random_access_iterator_tag)
1686 static_cast<__gnu_parallel::sequence_index_t>(end - begin)
1690 difference_type difference_type;
1693 __gnu_parallel::get_max_threads());
1694 return begin + middle;
1701 template<
typename ForwardIterator,
typename Predicate>
1702 inline ForwardIterator
1703 partition(ForwardIterator begin, ForwardIterator end, Predicate pred)
1705 typedef iterator_traits<ForwardIterator> traits_type;
1706 typedef typename traits_type::iterator_category iterator_category;
1707 return partition_switch(begin, end, pred, iterator_category());
1713 template<
typename RandomAccessIterator>
1715 sort(RandomAccessIterator begin, RandomAccessIterator end,
1717 { _GLIBCXX_STD_P::sort(begin, end); }
1720 template<
typename RandomAccessIterator,
typename Comparator>
1722 sort(RandomAccessIterator begin, RandomAccessIterator end, Comparator comp,
1724 { _GLIBCXX_STD_P::sort<RandomAccessIterator, Comparator>(begin, end,
1728 template<
typename RandomAccessIterator,
typename Comparator,
1729 typename Parallelism>
1731 sort(RandomAccessIterator begin, RandomAccessIterator end, Comparator comp,
1732 Parallelism parallelism)
1734 typedef iterator_traits<RandomAccessIterator> traits_type;
1735 typedef typename traits_type::value_type value_type;
1740 static_cast<__gnu_parallel::sequence_index_t>(end - begin) >=
1742 __gnu_parallel::parallel_sort<false>(begin, end, comp, parallelism);
1749 template<
typename RandomAccessIterator>
1751 sort(RandomAccessIterator begin, RandomAccessIterator end)
1753 typedef iterator_traits<RandomAccessIterator> traits_type;
1754 typedef typename traits_type::value_type value_type;
1760 template<
typename RandomAccessIterator>
1762 sort(RandomAccessIterator begin, RandomAccessIterator end,
1765 typedef iterator_traits<RandomAccessIterator> traits_type;
1766 typedef typename traits_type::value_type value_type;
1771 template<
typename RandomAccessIterator>
1773 sort(RandomAccessIterator begin, RandomAccessIterator end,
1776 typedef iterator_traits<RandomAccessIterator> traits_type;
1777 typedef typename traits_type::value_type value_type;
1782 template<
typename RandomAccessIterator>
1784 sort(RandomAccessIterator begin, RandomAccessIterator end,
1787 typedef iterator_traits<RandomAccessIterator> traits_type;
1788 typedef typename traits_type::value_type value_type;
1793 template<
typename RandomAccessIterator>
1795 sort(RandomAccessIterator begin, RandomAccessIterator end,
1798 typedef iterator_traits<RandomAccessIterator> traits_type;
1799 typedef typename traits_type::value_type value_type;
1804 template<
typename RandomAccessIterator>
1806 sort(RandomAccessIterator begin, RandomAccessIterator end,
1809 typedef iterator_traits<RandomAccessIterator> traits_type;
1810 typedef typename traits_type::value_type value_type;
1815 template<
typename RandomAccessIterator>
1817 sort(RandomAccessIterator begin, RandomAccessIterator end,
1820 typedef iterator_traits<RandomAccessIterator> traits_type;
1821 typedef typename traits_type::value_type value_type;
1826 template<
typename RandomAccessIterator>
1828 sort(RandomAccessIterator begin, RandomAccessIterator end,
1831 typedef iterator_traits<RandomAccessIterator> traits_type;
1832 typedef typename traits_type::value_type value_type;
1837 template<
typename RandomAccessIterator,
typename Comparator>
1839 sort(RandomAccessIterator begin, RandomAccessIterator end, Comparator comp)
1841 typedef iterator_traits<RandomAccessIterator> traits_type;
1842 typedef typename traits_type::value_type value_type;
1851 template<
typename RandomAccessIterator>
1853 stable_sort(RandomAccessIterator begin, RandomAccessIterator end,
1855 { _GLIBCXX_STD_P::stable_sort(begin, end); }
1858 template<
typename RandomAccessIterator,
typename Comparator>
1860 stable_sort(RandomAccessIterator begin, RandomAccessIterator end,
1862 { _GLIBCXX_STD_P::stable_sort<RandomAccessIterator, Comparator>(
1863 begin, end, comp); }
1866 template<
typename RandomAccessIterator,
typename Comparator,
1867 typename Parallelism>
1869 stable_sort(RandomAccessIterator begin, RandomAccessIterator end,
1870 Comparator comp, Parallelism parallelism)
1872 typedef iterator_traits<RandomAccessIterator> traits_type;
1873 typedef typename traits_type::value_type value_type;
1878 static_cast<__gnu_parallel::sequence_index_t>(end - begin) >=
1880 __gnu_parallel::parallel_sort<true>(begin, end, comp, parallelism);
1887 template<
typename RandomAccessIterator>
1889 stable_sort(RandomAccessIterator begin, RandomAccessIterator end)
1891 typedef iterator_traits<RandomAccessIterator> traits_type;
1892 typedef typename traits_type::value_type value_type;
1898 template<
typename RandomAccessIterator>
1900 stable_sort(RandomAccessIterator begin, RandomAccessIterator end,
1903 typedef iterator_traits<RandomAccessIterator> traits_type;
1904 typedef typename traits_type::value_type value_type;
1909 template<
typename RandomAccessIterator>
1911 stable_sort(RandomAccessIterator begin, RandomAccessIterator end,
1914 typedef iterator_traits<RandomAccessIterator> traits_type;
1915 typedef typename traits_type::value_type value_type;
1920 template<
typename RandomAccessIterator>
1922 stable_sort(RandomAccessIterator begin, RandomAccessIterator end,
1925 typedef iterator_traits<RandomAccessIterator> traits_type;
1926 typedef typename traits_type::value_type value_type;
1931 template<
typename RandomAccessIterator>
1933 stable_sort(RandomAccessIterator begin, RandomAccessIterator end,
1936 typedef iterator_traits<RandomAccessIterator> traits_type;
1937 typedef typename traits_type::value_type value_type;
1942 template<
typename RandomAccessIterator>
1944 stable_sort(RandomAccessIterator begin, RandomAccessIterator end,
1947 typedef iterator_traits<RandomAccessIterator> traits_type;
1948 typedef typename traits_type::value_type value_type;
1953 template<
typename RandomAccessIterator,
typename Comparator>
1955 stable_sort(RandomAccessIterator begin, RandomAccessIterator end,
1958 typedef iterator_traits<RandomAccessIterator> traits_type;
1959 typedef typename traits_type::value_type value_type;
2006 template<
typename InputIterator1,
typename InputIterator2,
2007 typename OutputIterator>
2008 inline OutputIterator
2009 merge(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
2010 InputIterator2 end2, OutputIterator result,
2012 {
return _GLIBCXX_STD_P::merge(begin1, end1, begin2, end2, result); }
2015 template<
typename InputIterator1,
typename InputIterator2,
2016 typename OutputIterator,
typename Comparator>
2017 inline OutputIterator
2018 merge(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
2019 InputIterator2 end2, OutputIterator result, Comparator comp,
2021 {
return _GLIBCXX_STD_P::merge(begin1, end1, begin2, end2, result, comp); }
2024 template<
typename InputIterator1,
typename InputIterator2,
2025 typename OutputIterator,
typename Comparator,
2026 typename IteratorTag1,
typename IteratorTag2,
typename IteratorTag3>
2027 inline OutputIterator
2028 merge_switch(InputIterator1 begin1, InputIterator1 end1,
2029 InputIterator2 begin2, InputIterator2 end2,
2030 OutputIterator result, Comparator comp,
2031 IteratorTag1, IteratorTag2, IteratorTag3)
2032 {
return _GLIBCXX_STD_P::merge(begin1, end1, begin2, end2,
2036 template<
typename InputIterator1,
typename InputIterator2,
2037 typename OutputIterator,
typename Comparator>
2039 merge_switch(InputIterator1 begin1, InputIterator1 end1,
2040 InputIterator2 begin2, InputIterator2 end2,
2041 OutputIterator result, Comparator comp,
2042 random_access_iterator_tag, random_access_iterator_tag,
2043 random_access_iterator_tag)
2046 (static_cast<__gnu_parallel::sequence_index_t>(end1 - begin1)
2048 || static_cast<__gnu_parallel::sequence_index_t>(end2 - begin2)
2052 result, (end1 - begin1)
2053 + (end2 - begin2), comp);
2056 result, (end1 - begin1)
2057 + (end2 - begin2), comp);
2061 template<
typename InputIterator1,
typename InputIterator2,
2062 typename OutputIterator,
typename Comparator>
2063 inline OutputIterator
2064 merge(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
2065 InputIterator2 end2, OutputIterator result, Comparator comp)
2067 typedef typename iterator_traits<InputIterator1>::value_type value_type;
2072 typedef typename iteratori1_traits::iterator_category
2073 iteratori1_category;
2074 typedef typename iteratori2_traits::iterator_category
2075 iteratori2_category;
2076 typedef typename iteratoro_traits::iterator_category iteratoro_category;
2078 return merge_switch(begin1, end1, begin2, end2, result, comp,
2079 iteratori1_category(), iteratori2_category(),
2080 iteratoro_category());
2085 template<
typename InputIterator1,
typename InputIterator2,
2086 typename OutputIterator>
2087 inline OutputIterator
2088 merge(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
2089 InputIterator2 end2, OutputIterator result)
2093 typedef typename iterator1_traits::value_type value1_type;
2094 typedef typename iterator2_traits::value_type value2_type;
2096 return _GLIBCXX_STD_P::merge(begin1, end1, begin2, end2, result,
2101 template<
typename RandomAccessIterator>
2103 nth_element(RandomAccessIterator begin, RandomAccessIterator nth,
2105 {
return _GLIBCXX_STD_P::nth_element(begin, nth, end); }
2108 template<
typename RandomAccessIterator,
typename Comparator>
2110 nth_element(RandomAccessIterator begin, RandomAccessIterator nth,
2111 RandomAccessIterator end, Comparator comp,
2113 {
return _GLIBCXX_STD_P::nth_element(begin, nth, end, comp); }
2116 template<
typename RandomAccessIterator,
typename Comparator>
2118 nth_element(RandomAccessIterator begin, RandomAccessIterator nth,
2119 RandomAccessIterator end, Comparator comp)
2122 static_cast<__gnu_parallel::sequence_index_t>(end - begin)
2130 template<
typename RandomAccessIterator>
2132 nth_element(RandomAccessIterator begin, RandomAccessIterator nth,
2133 RandomAccessIterator end)
2135 typedef iterator_traits<RandomAccessIterator> traits_type;
2136 typedef typename traits_type::value_type value_type;
2141 template<
typename RandomAccessIterator,
typename _Compare>
2143 partial_sort(RandomAccessIterator begin, RandomAccessIterator middle,
2144 RandomAccessIterator end, _Compare comp,
2146 { _GLIBCXX_STD_P::partial_sort(begin, middle, end, comp); }
2149 template<
typename RandomAccessIterator>
2151 partial_sort(RandomAccessIterator begin, RandomAccessIterator middle,
2153 { _GLIBCXX_STD_P::partial_sort(begin, middle, end); }
2156 template<
typename RandomAccessIterator,
typename _Compare>
2158 partial_sort(RandomAccessIterator begin, RandomAccessIterator middle,
2159 RandomAccessIterator end, _Compare comp)
2162 static_cast<__gnu_parallel::sequence_index_t>(end - begin)
2166 partial_sort(begin, middle, end, comp,
2171 template<
typename RandomAccessIterator>
2173 partial_sort(RandomAccessIterator begin, RandomAccessIterator middle,
2174 RandomAccessIterator end)
2176 typedef iterator_traits<RandomAccessIterator> traits_type;
2177 typedef typename traits_type::value_type value_type;
2178 _GLIBCXX_STD_P::partial_sort(begin, middle, end,
2183 template<
typename ForwardIterator>
2184 inline ForwardIterator
2185 max_element(ForwardIterator begin, ForwardIterator end,
2187 {
return _GLIBCXX_STD_P::max_element(begin, end); }
2190 template<
typename ForwardIterator,
typename Comparator>
2191 inline ForwardIterator
2192 max_element(ForwardIterator begin, ForwardIterator end, Comparator comp,
2194 {
return _GLIBCXX_STD_P::max_element(begin, end, comp); }
2197 template<
typename ForwardIterator,
typename Comparator,
typename IteratorTag>
2198 inline ForwardIterator
2199 max_element_switch(ForwardIterator begin, ForwardIterator end,
2200 Comparator comp, IteratorTag)
2204 template<
typename RandomAccessIterator,
typename Comparator>
2205 RandomAccessIterator
2206 max_element_switch(RandomAccessIterator begin, RandomAccessIterator end,
2207 Comparator comp, random_access_iterator_tag,
2212 static_cast<__gnu_parallel::sequence_index_t>(end - begin)
2214 && __gnu_parallel::is_parallel(parallelism_tag)))
2216 RandomAccessIterator res(begin);
2224 max_element_reduct<Comparator,
2225 RandomAccessIterator>(comp),
2226 res, res, -1, parallelism_tag);
2234 template<
typename ForwardIterator>
2235 inline ForwardIterator
2236 max_element(ForwardIterator begin, ForwardIterator end,
2239 typedef typename iterator_traits<ForwardIterator>::value_type value_type;
2243 template<
typename ForwardIterator>
2244 inline ForwardIterator
2245 max_element(ForwardIterator begin, ForwardIterator end)
2247 typedef typename iterator_traits<ForwardIterator>::value_type value_type;
2252 template<
typename ForwardIterator,
typename Comparator>
2253 inline ForwardIterator
2254 max_element(ForwardIterator begin, ForwardIterator end, Comparator comp,
2257 typedef iterator_traits<ForwardIterator> traits_type;
2258 typedef typename traits_type::iterator_category iterator_category;
2259 return max_element_switch(begin, end, comp, iterator_category(),
2263 template<
typename ForwardIterator,
typename Comparator>
2264 inline ForwardIterator
2265 max_element(ForwardIterator begin, ForwardIterator end, Comparator comp)
2267 typedef iterator_traits<ForwardIterator> traits_type;
2268 typedef typename traits_type::iterator_category iterator_category;
2269 return max_element_switch(begin, end, comp, iterator_category());
2274 template<
typename ForwardIterator>
2275 inline ForwardIterator
2276 min_element(ForwardIterator begin, ForwardIterator end,
2278 {
return _GLIBCXX_STD_P::min_element(begin, end); }
2281 template<
typename ForwardIterator,
typename Comparator>
2282 inline ForwardIterator
2283 min_element(ForwardIterator begin, ForwardIterator end, Comparator comp,
2285 {
return _GLIBCXX_STD_P::min_element(begin, end, comp); }
2288 template<
typename ForwardIterator,
typename Comparator,
typename IteratorTag>
2289 inline ForwardIterator
2290 min_element_switch(ForwardIterator begin, ForwardIterator end,
2291 Comparator comp, IteratorTag)
2295 template<
typename RandomAccessIterator,
typename Comparator>
2296 RandomAccessIterator
2297 min_element_switch(RandomAccessIterator begin, RandomAccessIterator end,
2298 Comparator comp, random_access_iterator_tag,
2303 static_cast<__gnu_parallel::sequence_index_t>(end - begin)
2305 && __gnu_parallel::is_parallel(parallelism_tag)))
2307 RandomAccessIterator res(begin);
2315 min_element_reduct<Comparator,
2316 RandomAccessIterator>(comp),
2317 res, res, -1, parallelism_tag);
2325 template<
typename ForwardIterator>
2326 inline ForwardIterator
2327 min_element(ForwardIterator begin, ForwardIterator end,
2330 typedef typename iterator_traits<ForwardIterator>::value_type value_type;
2334 template<
typename ForwardIterator>
2335 inline ForwardIterator
2336 min_element(ForwardIterator begin, ForwardIterator end)
2338 typedef typename iterator_traits<ForwardIterator>::value_type value_type;
2343 template<
typename ForwardIterator,
typename Comparator>
2344 inline ForwardIterator
2345 min_element(ForwardIterator begin, ForwardIterator end, Comparator comp,
2348 typedef iterator_traits<ForwardIterator> traits_type;
2349 typedef typename traits_type::iterator_category iterator_category;
2350 return min_element_switch(begin, end, comp, iterator_category(),
2354 template<
typename ForwardIterator,
typename Comparator>
2355 inline ForwardIterator
2356 min_element(ForwardIterator begin, ForwardIterator end, Comparator comp)
2358 typedef iterator_traits<ForwardIterator> traits_type;
2359 typedef typename traits_type::iterator_category iterator_category;
2360 return min_element_switch(begin, end, comp, iterator_category());