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,
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,
148 typedef typename traits_type::value_type value_type;
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,
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,
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,
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;
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,
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,
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,
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,
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,
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,
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,
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,
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)
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,
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)
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,
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,
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)
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,
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,
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)
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,
1041 typedef typename iterator1_traits::value_type value1_type;
1043 typedef typename iterator2_traits::value_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,
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,
1171 ps.
end(), binary_pred);
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,
1218 static_cast<__gnu_parallel::sequence_index_t>(end - begin)
1220 && __gnu_parallel::is_parallel(parallelism_tag)))
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,
1309 && __gnu_parallel::is_parallel(parallelism_tag)))
1313 RandomAccessIterator2, RandomAccessIterator3,
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,
1412 replace(begin, end, old_value, new_value,
1417 template<
typename ForwardIterator,
typename T>
1419 replace(ForwardIterator begin, ForwardIterator end,
const T& old_value,
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,
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,
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,
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,
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());
Forces parallel sorting using multiway mergesort at compile time.
uint64 sequence_index_t
Unsigned integer to index elements. The total number of elements for each algorithm must fit into thi...
Forces parallel sorting using multiway mergesort with exact splitting at compile time.
One of the binder functors.
One of the math functors.
UserOp for_each_template_random_access(InputIterator begin, InputIterator end, UserOp user_op, Functionality &functionality, Red reduction, Result reduction_start, Result &output, typename std::iterator_traits< InputIterator >::difference_type bound, _Parallelism parallelism_tag)
Chose the desired algorithm by evaluating parallelism_tag.
A pair of iterators. The usual iterator operations are applied to both child iterators.
std::iterator_traits< RandomAccessIterator >::difference_type parallel_partition(RandomAccessIterator begin, RandomAccessIterator end, Predicate pred, thread_index_t num_threads)
Parallel implementation of std::partition.
Functor wrapper for std::rand().
Parallelization of embarrassingly parallel execution by means of an OpenMP for loop with static sched...
OutputIterator parallel_unique_copy(InputIterator first, InputIterator last, OutputIterator result, BinaryPredicate binary_pred)
Parallel std::unique_copy(), w/o explicit equality predicate.
std::transform() selector, one input sequence variant.
Forces parallel sorting using balanced quicksort at compile time.
Forces parallel sorting using unbalanced quicksort at compile time.
Parallelization of embarrassingly parallel execution by means of equal splitting. This file is a GNU ...
Parallel implementation base for std::find(), std::equal() and related functions. This file is a GNU ...
Forces parallel sorting using multiway mergesort with splitting by sampling at compile time...
ISO C++ entities toplevel namespace is std.
_RandomAccessIterator1 search_template(_RandomAccessIterator1 begin1, _RandomAccessIterator1 end1, _RandomAccessIterator2 begin2, _RandomAccessIterator2 end2, Pred pred)
Parallel std::search.
std::generate() selector.
Parallel implementation of std::partition(), std::nth_element(), and std::partial_sort(). This file is a GNU parallel extension to the Standard C++ Library.
_ForwardIterator __search_n(_ForwardIterator __first, _ForwardIterator __last, _Integer __count, const _Tp &__val, std::forward_iterator_tag)
One of the comparison functors.
Parallel implementation of std::random_shuffle(). This file is a GNU parallel extension to the Standa...
Forces sequential execution at compile time.
GNU parallel code for public use.
Sequential helper functions. This file is a GNU parallel extension to the Standard C++ Library...
Parallelization of embarrassingly parallel execution by means of work-stealing.
Test predicate on two adjacent elements.
OutputIterator merge_advance(RandomAccessIterator1 &begin1, RandomAccessIterator1 end1, RandomAccessIterator2 &begin2, RandomAccessIterator2 end2, OutputIterator target, _DifferenceTp max_length, Comparator comp)
Merge routine being able to merge only the max_length smallest elements.
Function objects representing different tasks to be plugged into the parallel find algorithm...
void parallel_partial_sort(RandomAccessIterator begin, RandomAccessIterator middle, RandomAccessIterator end, Comparator comp)
Parallel implementation of std::partial_sort().
Helper iterator classes for the std::transform() functions. This file is a GNU parallel extension to ...
std::for_each() selector.
Parallelization of embarrassingly parallel execution by means of an OpenMP for loop. This file is a GNU parallel extension to the Standard C++ Library.
static const _Settings & get()
Get the global settings.
_Parallelism
Run-time equivalents for the compile-time tags.
Sequence that conceptually consists of multiple copies of the same element. The copies are not stored...
#define _GLIBCXX_PARALLEL_CONDITION(c)
Determine at compile(?)-time if the parallel variant of an algorithm should be called.
void sequential_random_shuffle(RandomAccessIterator begin, RandomAccessIterator end, RandomNumberGenerator &rng)
Sequential cache-efficient random shuffle.
Functors representing different tasks to be plugged into the generic parallelization methods for emba...
One of the comparison functors.
RandomAccessIterator3 parallel_merge_advance(RandomAccessIterator1 &begin1, RandomAccessIterator1 end1, RandomAccessIterator2 &begin2, RandomAccessIterator2 end2, RandomAccessIterator3 target, typename std::iterator_traits< RandomAccessIterator1 >::difference_type max_length, Comparator comp)
Merge routine fallback to sequential in case the iterators of the two input sequences are of differen...
std::count_if () selector.
Parallel implementation of std::merge(). This file is a GNU parallel extension to the Standard C++ Li...
Random-access iterators support a superset of bidirectional iterator operations.
Parallel balanced (work-stealing).
Parallel implementation base for std::search() and std::search_n(). This file is a GNU parallel exten...
Reduction function doing nothing.
Parallel sorting algorithm switch. This file is a GNU parallel extension to the Standard C++ Library...
Selector that just returns the passed iterator.
std::pair< RandomAccessIterator1, RandomAccessIterator2 > find_template(RandomAccessIterator1 begin1, RandomAccessIterator1 end1, RandomAccessIterator2 begin2, Pred pred, Selector selector)
Parallel std::find, switch for different algorithms.
void parallel_nth_element(RandomAccessIterator begin, RandomAccessIterator nth, RandomAccessIterator end, Comparator comp)
Parallel implementation of std::nth_element().
It finish_iterator
Iterator on last element processed; needed for some algorithms (e. g. std::transform()).
Similar to std::equal_to, but allows two different types.
Similar to std::less, but allows two different types.
Main interface for embarrassingly parallel functions.
A triple of iterators. The usual iterator operations are applied to all three child iterators...
Recommends parallel execution at compile time, optionally using a user-specified number of threads...
Test predicate on several elements.
Parallel implementations of std::unique_copy(). This file is a GNU parallel extension to the Standard...
iterator end() const
End iterator.
void parallel_random_shuffle(RandomAccessIterator begin, RandomAccessIterator end, RandomNumberGenerator rng=random_number())
Parallel random public call.
Parallel unbalanced (equal-sized chunks).
Parallel implementations of set operations for random-access iterators. This file is a GNU parallel e...
iterator begin() const
Begin iterator.
std::transform() selector, two input sequences variant.
Recommends parallel execution using the default parallel algorithm.