libstdc++
algo.h
Go to the documentation of this file.
1// -*- C++ -*-
2
3// Copyright (C) 2007-2016 Free Software Foundation, Inc.
4//
5// This file is part of the GNU ISO C++ Library. This library is free
6// software; you can redistribute it and/or modify it under the terms
7// of the GNU General Public License as published by the Free Software
8// Foundation; either version 3, or (at your option) any later
9// version.
10
11// This library is distributed in the hope that it will be useful, but
12// WITHOUT ANY WARRANTY; without even the implied warranty of
13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14// General Public License for more details.
15
16// Under Section 7 of GPL version 3, you are granted additional
17// permissions described in the GCC Runtime Library Exception, version
18// 3.1, as published by the Free Software Foundation.
19
20// You should have received a copy of the GNU General Public License and
21// a copy of the GCC Runtime Library Exception along with this program;
22// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23// <http://www.gnu.org/licenses/>.
24
25/** @file parallel/algo.h
26 * @brief Parallel STL function calls corresponding to the stl_algo.h header.
27 *
28 * The functions defined here mainly do case switches and
29 * call the actual parallelized versions in other files.
30 * Inlining policy: Functions that basically only contain one function call,
31 * are declared inline.
32 * This file is a GNU parallel extension to the Standard C++ Library.
33 */
34
35// Written by Johannes Singler and Felix Putze.
36
37#ifndef _GLIBCXX_PARALLEL_ALGO_H
38#define _GLIBCXX_PARALLEL_ALGO_H 1
39
41#include <bits/stl_algobase.h>
42#include <bits/stl_algo.h>
43#include <parallel/iterator.h>
44#include <parallel/base.h>
45#include <parallel/sort.h>
47#include <parallel/par_loop.h>
48#include <parallel/omp_loop.h>
51#include <parallel/for_each.h>
52#include <parallel/find.h>
54#include <parallel/search.h>
56#include <parallel/partition.h>
57#include <parallel/merge.h>
60
61namespace std _GLIBCXX_VISIBILITY(default)
62{
63namespace __parallel
64{
65 // Sequential fallback
66 template<typename _IIter, typename _Function>
67 inline _Function
68 for_each(_IIter __begin, _IIter __end, _Function __f,
70 { return _GLIBCXX_STD_A::for_each(__begin, __end, __f); }
71
72
73 // Sequential fallback for input iterator case
74 template<typename _IIter, typename _Function, typename _IteratorTag>
75 inline _Function
76 __for_each_switch(_IIter __begin, _IIter __end, _Function __f,
78 { return for_each(__begin, __end, __f, __gnu_parallel::sequential_tag()); }
79
80 // Parallel algorithm for random access iterators
81 template<typename _RAIter, typename _Function>
83 __for_each_switch(_RAIter __begin, _RAIter __end,
86 {
88 static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
89 >= __gnu_parallel::_Settings::get().for_each_minimal_n
90 && __gnu_parallel::__is_parallel(__parallelism_tag)))
91 {
92 bool __dummy;
94
95 return __gnu_parallel::
97 __begin, __end, __f, __functionality,
100 }
101 else
102 return for_each(__begin, __end, __f, __gnu_parallel::sequential_tag());
103 }
104
105 // Public interface
106 template<typename _Iterator, typename _Function>
107 inline _Function
108 for_each(_Iterator __begin, _Iterator __end, _Function __f,
110 {
112 typedef typename _IteratorTraits::iterator_category _IteratorCategory;
113 return __for_each_switch(__begin, __end, __f, _IteratorCategory(),
115 }
116
117 template<typename _Iterator, typename _Function>
118 inline _Function
119 for_each(_Iterator __begin, _Iterator __end, _Function __f)
120 {
122 typedef typename _IteratorTraits::iterator_category _IteratorCategory;
123 return __for_each_switch(__begin, __end, __f, _IteratorCategory());
124 }
125
126
127 // Sequential fallback
128 template<typename _IIter, typename _Tp>
129 inline _IIter
130 find(_IIter __begin, _IIter __end, const _Tp& __val,
132 { return _GLIBCXX_STD_A::find(__begin, __end, __val); }
133
134 // Sequential fallback for input iterator case
135 template<typename _IIter, typename _Tp, typename _IteratorTag>
136 inline _IIter
137 __find_switch(_IIter __begin, _IIter __end, const _Tp& __val,
139 { return _GLIBCXX_STD_A::find(__begin, __end, __val); }
140
141 // Parallel find for random access iterators
142 template<typename _RAIter, typename _Tp>
143 _RAIter
144 __find_switch(_RAIter __begin, _RAIter __end,
145 const _Tp& __val, random_access_iterator_tag)
146 {
147 typedef iterator_traits<_RAIter> _TraitsType;
148 typedef typename _TraitsType::value_type _ValueType;
149
151 {
153 const _Tp&>,
154 _ValueType, const _Tp&, bool>
157 __begin, __end, __begin, __comp,
159 }
160 else
161 return _GLIBCXX_STD_A::find(__begin, __end, __val);
162 }
163
164 // Public interface
165 template<typename _IIter, typename _Tp>
166 inline _IIter
167 find(_IIter __begin, _IIter __end, const _Tp& __val)
168 {
170 typedef typename _IteratorTraits::iterator_category _IteratorCategory;
171 return __find_switch(__begin, __end, __val, _IteratorCategory());
172 }
173
174 // Sequential fallback
175 template<typename _IIter, typename _Predicate>
176 inline _IIter
177 find_if(_IIter __begin, _IIter __end, _Predicate __pred,
179 { return _GLIBCXX_STD_A::find_if(__begin, __end, __pred); }
180
181 // Sequential fallback for input iterator case
182 template<typename _IIter, typename _Predicate, typename _IteratorTag>
183 inline _IIter
184 __find_if_switch(_IIter __begin, _IIter __end, _Predicate __pred,
186 { return _GLIBCXX_STD_A::find_if(__begin, __end, __pred); }
187
188 // Parallel find_if for random access iterators
189 template<typename _RAIter, typename _Predicate>
190 _RAIter
191 __find_if_switch(_RAIter __begin, _RAIter __end,
193 {
195 return __gnu_parallel::__find_template(__begin, __end, __begin, __pred,
197 __find_if_selector()).first;
198 else
199 return _GLIBCXX_STD_A::find_if(__begin, __end, __pred);
200 }
201
202 // Public interface
203 template<typename _IIter, typename _Predicate>
204 inline _IIter
205 find_if(_IIter __begin, _IIter __end, _Predicate __pred)
206 {
208 typedef typename _IteratorTraits::iterator_category _IteratorCategory;
209 return __find_if_switch(__begin, __end, __pred, _IteratorCategory());
210 }
211
212 // Sequential fallback
213 template<typename _IIter, typename _FIterator>
214 inline _IIter
215 find_first_of(_IIter __begin1, _IIter __end1,
216 _FIterator __begin2, _FIterator __end2,
218 { return _GLIBCXX_STD_A::find_first_of(__begin1, __end1, __begin2, __end2);
219 }
220
221 // Sequential fallback
222 template<typename _IIter, typename _FIterator,
223 typename _BinaryPredicate>
224 inline _IIter
225 find_first_of(_IIter __begin1, _IIter __end1,
226 _FIterator __begin2, _FIterator __end2,
228 { return _GLIBCXX_STD_A::find_first_of(
229 __begin1, __end1, __begin2, __end2, __comp); }
230
231 // Sequential fallback for input iterator type
232 template<typename _IIter, typename _FIterator,
233 typename _IteratorTag1, typename _IteratorTag2>
234 inline _IIter
235 __find_first_of_switch(_IIter __begin1, _IIter __end1,
236 _FIterator __begin2, _FIterator __end2,
238 { return find_first_of(__begin1, __end1, __begin2, __end2,
240
241 // Parallel algorithm for random access iterators
242 template<typename _RAIter, typename _FIterator,
243 typename _BinaryPredicate, typename _IteratorTag>
244 inline _RAIter
245 __find_first_of_switch(_RAIter __begin1,
246 _RAIter __end1,
247 _FIterator __begin2, _FIterator __end2,
250 {
251 return __gnu_parallel::
254 <_FIterator>(__begin2, __end2)).first;
255 }
256
257 // Sequential fallback for input iterator type
258 template<typename _IIter, typename _FIterator,
259 typename _BinaryPredicate, typename _IteratorTag1,
260 typename _IteratorTag2>
261 inline _IIter
262 __find_first_of_switch(_IIter __begin1, _IIter __end1,
263 _FIterator __begin2, _FIterator __end2,
265 { return find_first_of(__begin1, __end1, __begin2, __end2, __comp,
267
268 // Public interface
269 template<typename _IIter, typename _FIterator,
270 typename _BinaryPredicate>
271 inline _IIter
272 find_first_of(_IIter __begin1, _IIter __end1,
273 _FIterator __begin2, _FIterator __end2,
274 _BinaryPredicate __comp)
275 {
278 typedef typename _IIterTraits::iterator_category _IIteratorCategory;
279 typedef typename _FIterTraits::iterator_category _FIteratorCategory;
280
281 return __find_first_of_switch(__begin1, __end1, __begin2, __end2, __comp,
283 }
284
285 // Public interface, insert default comparator
286 template<typename _IIter, typename _FIterator>
287 inline _IIter
288 find_first_of(_IIter __begin1, _IIter __end1,
289 _FIterator __begin2, _FIterator __end2)
290 {
293 typedef typename _IIterTraits::value_type _IValueType;
294 typedef typename _FIterTraits::value_type _FValueType;
295
296 return __gnu_parallel::find_first_of(__begin1, __end1, __begin2, __end2,
298 }
299
300 // Sequential fallback
301 template<typename _IIter, typename _OutputIterator>
302 inline _OutputIterator
303 unique_copy(_IIter __begin1, _IIter __end1, _OutputIterator __out,
305 { return _GLIBCXX_STD_A::unique_copy(__begin1, __end1, __out); }
306
307 // Sequential fallback
308 template<typename _IIter, typename _OutputIterator,
309 typename _Predicate>
310 inline _OutputIterator
311 unique_copy(_IIter __begin1, _IIter __end1, _OutputIterator __out,
313 { return _GLIBCXX_STD_A::unique_copy(__begin1, __end1, __out, __pred); }
314
315 // Sequential fallback for input iterator case
316 template<typename _IIter, typename _OutputIterator,
317 typename _Predicate, typename _IteratorTag1, typename _IteratorTag2>
318 inline _OutputIterator
319 __unique_copy_switch(_IIter __begin, _IIter __last,
320 _OutputIterator __out, _Predicate __pred,
322 { return _GLIBCXX_STD_A::unique_copy(__begin, __last, __out, __pred); }
323
324 // Parallel unique_copy for random access iterators
325 template<typename _RAIter, typename RandomAccessOutputIterator,
326 typename _Predicate>
328 __unique_copy_switch(_RAIter __begin, _RAIter __last,
331 {
333 static_cast<__gnu_parallel::_SequenceIndex>(__last - __begin)
334 > __gnu_parallel::_Settings::get().unique_copy_minimal_n))
336 __begin, __last, __out, __pred);
337 else
338 return _GLIBCXX_STD_A::unique_copy(__begin, __last, __out, __pred);
339 }
340
341 // Public interface
342 template<typename _IIter, typename _OutputIterator>
343 inline _OutputIterator
344 unique_copy(_IIter __begin1, _IIter __end1, _OutputIterator __out)
345 {
348 typedef typename _IIterTraits::iterator_category _IIteratorCategory;
349 typedef typename _IIterTraits::value_type _ValueType;
350 typedef typename _OIterTraits::iterator_category _OIterCategory;
351
352 return __unique_copy_switch(
355 }
356
357 // Public interface
358 template<typename _IIter, typename _OutputIterator, typename _Predicate>
359 inline _OutputIterator
360 unique_copy(_IIter __begin1, _IIter __end1, _OutputIterator __out,
361 _Predicate __pred)
362 {
365 typedef typename _IIterTraits::iterator_category _IIteratorCategory;
366 typedef typename _OIterTraits::iterator_category _OIterCategory;
367
368 return __unique_copy_switch(
371 }
372
373 // Sequential fallback
374 template<typename _IIter1, typename _IIter2,
375 typename _OutputIterator>
376 inline _OutputIterator
377 set_union(_IIter1 __begin1, _IIter1 __end1,
379 _OutputIterator __out, __gnu_parallel::sequential_tag)
380 { return _GLIBCXX_STD_A::set_union(
382
383 // Sequential fallback
384 template<typename _IIter1, typename _IIter2,
385 typename _OutputIterator, typename _Predicate>
386 inline _OutputIterator
387 set_union(_IIter1 __begin1, _IIter1 __end1,
389 _OutputIterator __out, _Predicate __pred,
391 { return _GLIBCXX_STD_A::set_union(__begin1, __end1,
393
394 // Sequential fallback for input iterator case
395 template<typename _IIter1, typename _IIter2, typename _Predicate,
396 typename _OutputIterator, typename _IteratorTag1,
397 typename _IteratorTag2, typename _IteratorTag3>
398 inline _OutputIterator
399 __set_union_switch(
401 _OutputIterator __result, _Predicate __pred,
403 { return _GLIBCXX_STD_A::set_union(__begin1, __end1,
405
406 // Parallel set_union for random access iterators
407 template<typename _RAIter1, typename _RAIter2,
408 typename _Output_RAIter, typename _Predicate>
410 __set_union_switch(_RAIter1 __begin1, _RAIter1 __end1,
412 _Output_RAIter __result, _Predicate __pred,
415 {
418 >= __gnu_parallel::_Settings::get().set_union_minimal_n
420 >= __gnu_parallel::_Settings::get().set_union_minimal_n))
421 return __gnu_parallel::__parallel_set_union(
423 else
424 return _GLIBCXX_STD_A::set_union(__begin1, __end1,
426 }
427
428 // Public interface
429 template<typename _IIter1, typename _IIter2,
430 typename _OutputIterator>
431 inline _OutputIterator
432 set_union(_IIter1 __begin1, _IIter1 __end1,
433 _IIter2 __begin2, _IIter2 __end2, _OutputIterator __out)
434 {
438 typedef typename _IIterTraits1::iterator_category
440 typedef typename _IIterTraits2::iterator_category
442 typedef typename _OIterTraits::iterator_category _OIterCategory;
443 typedef typename _IIterTraits1::value_type _ValueType1;
444 typedef typename _IIterTraits2::value_type _ValueType2;
445
446 return __set_union_switch(
450 }
451
452 // Public interface
453 template<typename _IIter1, typename _IIter2,
454 typename _OutputIterator, typename _Predicate>
455 inline _OutputIterator
456 set_union(_IIter1 __begin1, _IIter1 __end1,
458 _OutputIterator __out, _Predicate __pred)
459 {
463 typedef typename _IIterTraits1::iterator_category
465 typedef typename _IIterTraits2::iterator_category
467 typedef typename _OIterTraits::iterator_category _OIterCategory;
468
469 return __set_union_switch(
472 }
473
474 // Sequential fallback.
475 template<typename _IIter1, typename _IIter2,
476 typename _OutputIterator>
477 inline _OutputIterator
478 set_intersection(_IIter1 __begin1, _IIter1 __end1,
480 _OutputIterator __out, __gnu_parallel::sequential_tag)
481 { return _GLIBCXX_STD_A::set_intersection(__begin1, __end1,
482 __begin2, __end2, __out); }
483
484 // Sequential fallback.
485 template<typename _IIter1, typename _IIter2,
486 typename _OutputIterator, typename _Predicate>
487 inline _OutputIterator
488 set_intersection(_IIter1 __begin1, _IIter1 __end1,
490 _OutputIterator __out, _Predicate __pred,
492 { return _GLIBCXX_STD_A::set_intersection(
494
495 // Sequential fallback for input iterator case
496 template<typename _IIter1, typename _IIter2,
497 typename _Predicate, typename _OutputIterator,
498 typename _IteratorTag1, typename _IteratorTag2,
499 typename _IteratorTag3>
500 inline _OutputIterator
501 __set_intersection_switch(_IIter1 __begin1, _IIter1 __end1,
503 _OutputIterator __result, _Predicate __pred,
505 { return _GLIBCXX_STD_A::set_intersection(__begin1, __end1, __begin2,
507
508 // Parallel set_intersection for random access iterators
509 template<typename _RAIter1, typename _RAIter2,
510 typename _Output_RAIter, typename _Predicate>
512 __set_intersection_switch(_RAIter1 __begin1,
517 _Predicate __pred,
521 {
524 >= __gnu_parallel::_Settings::get().set_union_minimal_n
526 >= __gnu_parallel::_Settings::get().set_union_minimal_n))
527 return __gnu_parallel::__parallel_set_intersection(
529 else
530 return _GLIBCXX_STD_A::set_intersection(
532 }
533
534 // Public interface
535 template<typename _IIter1, typename _IIter2,
536 typename _OutputIterator>
537 inline _OutputIterator
538 set_intersection(_IIter1 __begin1, _IIter1 __end1,
540 _OutputIterator __out)
541 {
545 typedef typename _IIterTraits1::iterator_category
547 typedef typename _IIterTraits2::iterator_category
549 typedef typename _OIterTraits::iterator_category _OIterCategory;
550 typedef typename _IIterTraits1::value_type _ValueType1;
551 typedef typename _IIterTraits2::value_type _ValueType2;
552
553 return __set_intersection_switch(
557 }
558
559 template<typename _IIter1, typename _IIter2,
560 typename _OutputIterator, typename _Predicate>
561 inline _OutputIterator
562 set_intersection(_IIter1 __begin1, _IIter1 __end1,
564 _OutputIterator __out, _Predicate __pred)
565 {
569 typedef typename _IIterTraits1::iterator_category
571 typedef typename _IIterTraits2::iterator_category
573 typedef typename _OIterTraits::iterator_category _OIterCategory;
574
575 return __set_intersection_switch(
578 }
579
580 // Sequential fallback
581 template<typename _IIter1, typename _IIter2,
582 typename _OutputIterator>
583 inline _OutputIterator
584 set_symmetric_difference(_IIter1 __begin1, _IIter1 __end1,
586 _OutputIterator __out,
588 { return _GLIBCXX_STD_A::set_symmetric_difference(
590
591 // Sequential fallback
592 template<typename _IIter1, typename _IIter2,
593 typename _OutputIterator, typename _Predicate>
594 inline _OutputIterator
595 set_symmetric_difference(_IIter1 __begin1, _IIter1 __end1,
597 _OutputIterator __out, _Predicate __pred,
599 { return _GLIBCXX_STD_A::set_symmetric_difference(
601
602 // Sequential fallback for input iterator case
603 template<typename _IIter1, typename _IIter2,
604 typename _Predicate, typename _OutputIterator,
605 typename _IteratorTag1, typename _IteratorTag2,
606 typename _IteratorTag3>
607 inline _OutputIterator
608 __set_symmetric_difference_switch(
610 _OutputIterator __result, _Predicate __pred,
612 { return _GLIBCXX_STD_A::set_symmetric_difference(
614
615 // Parallel set_symmetric_difference for random access iterators
616 template<typename _RAIter1, typename _RAIter2,
617 typename _Output_RAIter, typename _Predicate>
619 __set_symmetric_difference_switch(_RAIter1 __begin1,
624 _Predicate __pred,
628 {
631 >= __gnu_parallel::_Settings::get().set_symmetric_difference_minimal_n
633 >= __gnu_parallel::_Settings::get().set_symmetric_difference_minimal_n))
634 return __gnu_parallel::__parallel_set_symmetric_difference(
636 else
637 return _GLIBCXX_STD_A::set_symmetric_difference(
639 }
640
641 // Public interface.
642 template<typename _IIter1, typename _IIter2,
643 typename _OutputIterator>
644 inline _OutputIterator
645 set_symmetric_difference(_IIter1 __begin1, _IIter1 __end1,
647 _OutputIterator __out)
648 {
652 typedef typename _IIterTraits1::iterator_category
654 typedef typename _IIterTraits2::iterator_category
656 typedef typename _OIterTraits::iterator_category _OIterCategory;
657 typedef typename _IIterTraits1::value_type _ValueType1;
658 typedef typename _IIterTraits2::value_type _ValueType2;
659
660 return __set_symmetric_difference_switch(
664 }
665
666 // Public interface.
667 template<typename _IIter1, typename _IIter2,
668 typename _OutputIterator, typename _Predicate>
669 inline _OutputIterator
670 set_symmetric_difference(_IIter1 __begin1, _IIter1 __end1,
672 _OutputIterator __out, _Predicate __pred)
673 {
677 typedef typename _IIterTraits1::iterator_category
679 typedef typename _IIterTraits2::iterator_category
681 typedef typename _OIterTraits::iterator_category _OIterCategory;
682
683 return __set_symmetric_difference_switch(
686 }
687
688 // Sequential fallback.
689 template<typename _IIter1, typename _IIter2,
690 typename _OutputIterator>
691 inline _OutputIterator
692 set_difference(_IIter1 __begin1, _IIter1 __end1,
694 _OutputIterator __out, __gnu_parallel::sequential_tag)
695 { return _GLIBCXX_STD_A::set_difference(
697
698 // Sequential fallback.
699 template<typename _IIter1, typename _IIter2,
700 typename _OutputIterator, typename _Predicate>
701 inline _OutputIterator
702 set_difference(_IIter1 __begin1, _IIter1 __end1,
704 _OutputIterator __out, _Predicate __pred,
706 { return _GLIBCXX_STD_A::set_difference(__begin1, __end1,
708
709 // Sequential fallback for input iterator case.
710 template<typename _IIter1, typename _IIter2, typename _Predicate,
711 typename _OutputIterator, typename _IteratorTag1,
712 typename _IteratorTag2, typename _IteratorTag3>
713 inline _OutputIterator
714 __set_difference_switch(_IIter1 __begin1, _IIter1 __end1,
716 _OutputIterator __result, _Predicate __pred,
718 { return _GLIBCXX_STD_A::set_difference(
720
721 // Parallel set_difference for random access iterators
722 template<typename _RAIter1, typename _RAIter2,
723 typename _Output_RAIter, typename _Predicate>
725 __set_difference_switch(_RAIter1 __begin1,
729 _Output_RAIter __result, _Predicate __pred,
733 {
736 >= __gnu_parallel::_Settings::get().set_difference_minimal_n
738 >= __gnu_parallel::_Settings::get().set_difference_minimal_n))
739 return __gnu_parallel::__parallel_set_difference(
741 else
742 return _GLIBCXX_STD_A::set_difference(
744 }
745
746 // Public interface
747 template<typename _IIter1, typename _IIter2,
748 typename _OutputIterator>
749 inline _OutputIterator
750 set_difference(_IIter1 __begin1, _IIter1 __end1,
752 _OutputIterator __out)
753 {
757 typedef typename _IIterTraits1::iterator_category
759 typedef typename _IIterTraits2::iterator_category
761 typedef typename _OIterTraits::iterator_category _OIterCategory;
762 typedef typename _IIterTraits1::value_type _ValueType1;
763 typedef typename _IIterTraits2::value_type _ValueType2;
764
765 return __set_difference_switch(
769 }
770
771 // Public interface
772 template<typename _IIter1, typename _IIter2,
773 typename _OutputIterator, typename _Predicate>
774 inline _OutputIterator
775 set_difference(_IIter1 __begin1, _IIter1 __end1,
777 _OutputIterator __out, _Predicate __pred)
778 {
782 typedef typename _IIterTraits1::iterator_category
784 typedef typename _IIterTraits2::iterator_category
786 typedef typename _OIterTraits::iterator_category _OIterCategory;
787
788 return __set_difference_switch(
791 }
792
793 // Sequential fallback
794 template<typename _FIterator>
795 inline _FIterator
796 adjacent_find(_FIterator __begin, _FIterator __end,
798 { return _GLIBCXX_STD_A::adjacent_find(__begin, __end); }
799
800 // Sequential fallback
801 template<typename _FIterator, typename _BinaryPredicate>
802 inline _FIterator
803 adjacent_find(_FIterator __begin, _FIterator __end,
806 { return _GLIBCXX_STD_A::adjacent_find(__begin, __end, __binary_pred); }
807
808 // Parallel algorithm for random access iterators
809 template<typename _RAIter>
810 _RAIter
811 __adjacent_find_switch(_RAIter __begin, _RAIter __end,
813 {
814 typedef iterator_traits<_RAIter> _TraitsType;
815 typedef typename _TraitsType::value_type _ValueType;
816
818 {
819 _RAIter __spot = __gnu_parallel::
821 __begin, __end - 1, __begin, equal_to<_ValueType>(),
823 .first;
824 if (__spot == (__end - 1))
825 return __end;
826 else
827 return __spot;
828 }
829 else
830 return adjacent_find(__begin, __end, __gnu_parallel::sequential_tag());
831 }
832
833 // Sequential fallback for input iterator case
834 template<typename _FIterator, typename _IteratorTag>
835 inline _FIterator
836 __adjacent_find_switch(_FIterator __begin, _FIterator __end,
838 { return adjacent_find(__begin, __end, __gnu_parallel::sequential_tag()); }
839
840 // Public interface
841 template<typename _FIterator>
842 inline _FIterator
843 adjacent_find(_FIterator __begin, _FIterator __end)
844 {
845 typedef iterator_traits<_FIterator> _TraitsType;
846 typedef typename _TraitsType::iterator_category _IteratorCategory;
847 return __adjacent_find_switch(__begin, __end, _IteratorCategory());
848 }
849
850 // Sequential fallback for input iterator case
851 template<typename _FIterator, typename _BinaryPredicate,
852 typename _IteratorTag>
853 inline _FIterator
854 __adjacent_find_switch(_FIterator __begin, _FIterator __end,
856 { return adjacent_find(__begin, __end, __pred,
858
859 // Parallel algorithm for random access iterators
860 template<typename _RAIter, typename _BinaryPredicate>
861 _RAIter
862 __adjacent_find_switch(_RAIter __begin, _RAIter __end,
864 {
866 return __gnu_parallel::__find_template(__begin, __end, __begin, __pred,
868 __adjacent_find_selector()).first;
869 else
870 return adjacent_find(__begin, __end, __pred,
872 }
873
874 // Public interface
875 template<typename _FIterator, typename _BinaryPredicate>
876 inline _FIterator
877 adjacent_find(_FIterator __begin, _FIterator __end,
879 {
880 typedef iterator_traits<_FIterator> _TraitsType;
881 typedef typename _TraitsType::iterator_category _IteratorCategory;
882 return __adjacent_find_switch(__begin, __end, __pred,
884 }
885
886 // Sequential fallback
887 template<typename _IIter, typename _Tp>
888 inline typename iterator_traits<_IIter>::difference_type
889 count(_IIter __begin, _IIter __end, const _Tp& __value,
891 { return _GLIBCXX_STD_A::count(__begin, __end, __value); }
892
893 // Parallel code for random access iterators
894 template<typename _RAIter, typename _Tp>
895 typename iterator_traits<_RAIter>::difference_type
896 __count_switch(_RAIter __begin, _RAIter __end,
897 const _Tp& __value, random_access_iterator_tag,
899 {
900 typedef iterator_traits<_RAIter> _TraitsType;
901 typedef typename _TraitsType::value_type _ValueType;
902 typedef typename _TraitsType::difference_type _DifferenceType;
903 typedef __gnu_parallel::_SequenceIndex _SequenceIndex;
904
906 static_cast<_SequenceIndex>(__end - __begin)
907 >= __gnu_parallel::_Settings::get().count_minimal_n
908 && __gnu_parallel::__is_parallel(__parallelism_tag)))
909 {
912 _DifferenceType __res = 0;
915 __begin, __end, __value, __functionality,
918 return __res;
919 }
920 else
921 return count(__begin, __end, __value,
923 }
924
925 // Sequential fallback for input iterator case.
926 template<typename _IIter, typename _Tp, typename _IteratorTag>
927 inline typename iterator_traits<_IIter>::difference_type
928 __count_switch(_IIter __begin, _IIter __end, const _Tp& __value,
930 { return count(__begin, __end, __value, __gnu_parallel::sequential_tag());
931 }
932
933 // Public interface.
934 template<typename _IIter, typename _Tp>
935 inline typename iterator_traits<_IIter>::difference_type
936 count(_IIter __begin, _IIter __end, const _Tp& __value,
938 {
939 typedef iterator_traits<_IIter> _TraitsType;
940 typedef typename _TraitsType::iterator_category _IteratorCategory;
941 return __count_switch(__begin, __end, __value, _IteratorCategory(),
943 }
944
945 template<typename _IIter, typename _Tp>
946 inline typename iterator_traits<_IIter>::difference_type
947 count(_IIter __begin, _IIter __end, const _Tp& __value)
948 {
949 typedef iterator_traits<_IIter> _TraitsType;
950 typedef typename _TraitsType::iterator_category _IteratorCategory;
951 return __count_switch(__begin, __end, __value, _IteratorCategory());
952 }
953
954
955 // Sequential fallback.
956 template<typename _IIter, typename _Predicate>
957 inline typename iterator_traits<_IIter>::difference_type
958 count_if(_IIter __begin, _IIter __end, _Predicate __pred,
960 { return _GLIBCXX_STD_A::count_if(__begin, __end, __pred); }
961
962 // Parallel count_if for random access iterators
963 template<typename _RAIter, typename _Predicate>
964 typename iterator_traits<_RAIter>::difference_type
965 __count_if_switch(_RAIter __begin, _RAIter __end,
968 {
969 typedef iterator_traits<_RAIter> _TraitsType;
970 typedef typename _TraitsType::value_type _ValueType;
971 typedef typename _TraitsType::difference_type _DifferenceType;
972 typedef __gnu_parallel::_SequenceIndex _SequenceIndex;
973
975 static_cast<_SequenceIndex>(__end - __begin)
976 >= __gnu_parallel::_Settings::get().count_minimal_n
977 && __gnu_parallel::__is_parallel(__parallelism_tag)))
978 {
979 _DifferenceType __res = 0;
980 __gnu_parallel::
981 __count_if_selector<_RAIter, _DifferenceType>
985 __begin, __end, __pred, __functionality,
988 return __res;
989 }
990 else
991 return count_if(__begin, __end, __pred,
993 }
994
995 // Sequential fallback for input iterator case.
996 template<typename _IIter, typename _Predicate, typename _IteratorTag>
997 inline typename iterator_traits<_IIter>::difference_type
998 __count_if_switch(_IIter __begin, _IIter __end, _Predicate __pred,
1000 { return count_if(__begin, __end, __pred,
1002
1003 // Public interface.
1004 template<typename _IIter, typename _Predicate>
1005 inline typename iterator_traits<_IIter>::difference_type
1006 count_if(_IIter __begin, _IIter __end, _Predicate __pred,
1008 {
1009 typedef iterator_traits<_IIter> _TraitsType;
1010 typedef typename _TraitsType::iterator_category _IteratorCategory;
1011 return __count_if_switch(__begin, __end, __pred, _IteratorCategory(),
1013 }
1014
1015 template<typename _IIter, typename _Predicate>
1016 inline typename iterator_traits<_IIter>::difference_type
1017 count_if(_IIter __begin, _IIter __end, _Predicate __pred)
1018 {
1019 typedef iterator_traits<_IIter> _TraitsType;
1020 typedef typename _TraitsType::iterator_category _IteratorCategory;
1021 return __count_if_switch(__begin, __end, __pred, _IteratorCategory());
1022 }
1023
1024
1025 // Sequential fallback.
1026 template<typename _FIterator1, typename _FIterator2>
1027 inline _FIterator1
1031 { return _GLIBCXX_STD_A::search(__begin1, __end1, __begin2, __end2); }
1032
1033 // Parallel algorithm for random access iterator
1034 template<typename _RAIter1, typename _RAIter2>
1035 _RAIter1
1036 __search_switch(_RAIter1 __begin1, _RAIter1 __end1,
1039 {
1041 typedef typename _Iterator1Traits::value_type _ValueType1;
1043 typedef typename _Iterator2Traits::value_type _ValueType2;
1044
1047 >= __gnu_parallel::_Settings::get().search_minimal_n))
1048 return __gnu_parallel::
1052 else
1053 return search(__begin1, __end1, __begin2, __end2,
1055 }
1056
1057 // Sequential fallback for input iterator case
1058 template<typename _FIterator1, typename _FIterator2,
1059 typename _IteratorTag1, typename _IteratorTag2>
1060 inline _FIterator1
1061 __search_switch(_FIterator1 __begin1, _FIterator1 __end1,
1064 { return search(__begin1, __end1, __begin2, __end2,
1066
1067 // Public interface.
1068 template<typename _FIterator1, typename _FIterator2>
1069 inline _FIterator1
1072 {
1074 typedef typename _Iterator1Traits::iterator_category _IteratorCategory1;
1076 typedef typename _Iterator2Traits::iterator_category _IteratorCategory2;
1077
1078 return __search_switch(__begin1, __end1, __begin2, __end2,
1080 }
1081
1082 // Public interface.
1083 template<typename _FIterator1, typename _FIterator2,
1084 typename _BinaryPredicate>
1085 inline _FIterator1
1089 { return _GLIBCXX_STD_A::search(
1091
1092 // Parallel algorithm for random access iterator.
1093 template<typename _RAIter1, typename _RAIter2,
1094 typename _BinaryPredicate>
1095 _RAIter1
1096 __search_switch(_RAIter1 __begin1, _RAIter1 __end1,
1100 {
1103 >= __gnu_parallel::_Settings::get().search_minimal_n))
1106 else
1107 return search(__begin1, __end1, __begin2, __end2, __pred,
1109 }
1110
1111 // Sequential fallback for input iterator case
1112 template<typename _FIterator1, typename _FIterator2,
1113 typename _BinaryPredicate, typename _IteratorTag1,
1114 typename _IteratorTag2>
1115 inline _FIterator1
1116 __search_switch(_FIterator1 __begin1, _FIterator1 __end1,
1119 { return search(__begin1, __end1, __begin2, __end2, __pred,
1121
1122 // Public interface
1123 template<typename _FIterator1, typename _FIterator2,
1124 typename _BinaryPredicate>
1125 inline _FIterator1
1129 {
1131 typedef typename _Iterator1Traits::iterator_category _IteratorCategory1;
1133 typedef typename _Iterator2Traits::iterator_category _IteratorCategory2;
1134 return __search_switch(__begin1, __end1, __begin2, __end2, __pred,
1136 }
1137
1138 // Sequential fallback
1139 template<typename _FIterator, typename _Integer, typename _Tp>
1140 inline _FIterator
1141 search_n(_FIterator __begin, _FIterator __end, _Integer __count,
1142 const _Tp& __val, __gnu_parallel::sequential_tag)
1143 { return _GLIBCXX_STD_A::search_n(__begin, __end, __count, __val); }
1144
1145 // Sequential fallback
1146 template<typename _FIterator, typename _Integer, typename _Tp,
1147 typename _BinaryPredicate>
1148 inline _FIterator
1149 search_n(_FIterator __begin, _FIterator __end, _Integer __count,
1150 const _Tp& __val, _BinaryPredicate __binary_pred,
1152 { return _GLIBCXX_STD_A::search_n(
1153 __begin, __end, __count, __val, __binary_pred); }
1154
1155 // Public interface.
1156 template<typename _FIterator, typename _Integer, typename _Tp>
1157 inline _FIterator
1158 search_n(_FIterator __begin, _FIterator __end, _Integer __count,
1159 const _Tp& __val)
1160 {
1161 typedef typename iterator_traits<_FIterator>::value_type _ValueType;
1162 return __gnu_parallel::search_n(__begin, __end, __count, __val,
1164 }
1165
1166 // Parallel algorithm for random access iterators.
1167 template<typename _RAIter, typename _Integer,
1168 typename _Tp, typename _BinaryPredicate>
1169 _RAIter
1170 __search_n_switch(_RAIter __begin, _RAIter __end, _Integer __count,
1171 const _Tp& __val, _BinaryPredicate __binary_pred,
1173 {
1175 static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
1176 >= __gnu_parallel::_Settings::get().search_minimal_n))
1177 {
1180 __begin, __end, __ps.begin(), __ps.end(), __binary_pred);
1181 }
1182 else
1183 return _GLIBCXX_STD_A::search_n(__begin, __end, __count, __val,
1185 }
1186
1187 // Sequential fallback for input iterator case.
1188 template<typename _FIterator, typename _Integer, typename _Tp,
1189 typename _BinaryPredicate, typename _IteratorTag>
1190 inline _FIterator
1191 __search_n_switch(_FIterator __begin, _FIterator __end, _Integer __count,
1192 const _Tp& __val, _BinaryPredicate __binary_pred,
1194 { return _GLIBCXX_STD_A::search_n(__begin, __end, __count, __val,
1195 __binary_pred); }
1196
1197 // Public interface.
1198 template<typename _FIterator, typename _Integer, typename _Tp,
1199 typename _BinaryPredicate>
1200 inline _FIterator
1201 search_n(_FIterator __begin, _FIterator __end, _Integer __count,
1202 const _Tp& __val, _BinaryPredicate __binary_pred)
1203 {
1204 return __search_n_switch(__begin, __end, __count, __val, __binary_pred,
1206 iterator_category());
1207 }
1208
1209
1210 // Sequential fallback.
1211 template<typename _IIter, typename _OutputIterator,
1212 typename _UnaryOperation>
1213 inline _OutputIterator
1214 transform(_IIter __begin, _IIter __end, _OutputIterator __result,
1216 { return _GLIBCXX_STD_A::transform(__begin, __end, __result, __unary_op); }
1217
1218 // Parallel unary transform for random access iterators.
1219 template<typename _RAIter1, typename _RAIter2,
1220 typename _UnaryOperation>
1221 _RAIter2
1222 __transform1_switch(_RAIter1 __begin, _RAIter1 __end,
1226 {
1228 static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
1229 >= __gnu_parallel::_Settings::get().transform_minimal_n
1230 && __gnu_parallel::__is_parallel(__parallelism_tag)))
1231 {
1232 bool __dummy = true;
1235 _ItTrip __begin_pair(__begin, __result),
1236 __end_pair(__end, __result + (__end - __begin));
1243 return __functionality._M_finish_iterator;
1244 }
1245 else
1246 return transform(__begin, __end, __result, __unary_op,
1248 }
1249
1250 // Sequential fallback for input iterator case.
1251 template<typename _RAIter1, typename _RAIter2,
1252 typename _UnaryOperation, typename _IteratorTag1,
1253 typename _IteratorTag2>
1254 inline _RAIter2
1255 __transform1_switch(_RAIter1 __begin, _RAIter1 __end,
1258 { return transform(__begin, __end, __result, __unary_op,
1260
1261 // Public interface.
1262 template<typename _IIter, typename _OutputIterator,
1263 typename _UnaryOperation>
1264 inline _OutputIterator
1265 transform(_IIter __begin, _IIter __end, _OutputIterator __result,
1268 {
1271 typedef typename _IIterTraits::iterator_category _IIteratorCategory;
1272 typedef typename _OIterTraits::iterator_category _OIterCategory;
1273
1274 return __transform1_switch(__begin, __end, __result, __unary_op,
1277 }
1278
1279 template<typename _IIter, typename _OutputIterator,
1280 typename _UnaryOperation>
1281 inline _OutputIterator
1282 transform(_IIter __begin, _IIter __end, _OutputIterator __result,
1284 {
1287 typedef typename _IIterTraits::iterator_category _IIteratorCategory;
1288 typedef typename _OIterTraits::iterator_category _OIterCategory;
1289
1290 return __transform1_switch(__begin, __end, __result, __unary_op,
1292 }
1293
1294
1295 // Sequential fallback
1296 template<typename _IIter1, typename _IIter2,
1297 typename _OutputIterator, typename _BinaryOperation>
1298 inline _OutputIterator
1299 transform(_IIter1 __begin1, _IIter1 __end1,
1300 _IIter2 __begin2, _OutputIterator __result,
1302 { return _GLIBCXX_STD_A::transform(__begin1, __end1,
1304
1305 // Parallel binary transform for random access iterators.
1306 template<typename _RAIter1, typename _RAIter2,
1307 typename _RAIter3, typename _BinaryOperation>
1308 _RAIter3
1309 __transform2_switch(_RAIter1 __begin1, _RAIter1 __end1,
1315 {
1317 (__end1 - __begin1) >=
1318 __gnu_parallel::_Settings::get().transform_minimal_n
1319 && __gnu_parallel::__is_parallel(__parallelism_tag)))
1320 {
1321 bool __dummy = true;
1327 __result + (__end1 - __begin1));
1333 __dummy, __dummy, -1,
1335 return __functionality._M_finish_iterator;
1336 }
1337 else
1338 return transform(__begin1, __end1, __begin2, __result, __binary_op,
1340 }
1341
1342 // Sequential fallback for input iterator case.
1343 template<typename _IIter1, typename _IIter2,
1344 typename _OutputIterator, typename _BinaryOperation,
1345 typename _Tag1, typename _Tag2, typename _Tag3>
1346 inline _OutputIterator
1347 __transform2_switch(_IIter1 __begin1, _IIter1 __end1,
1348 _IIter2 __begin2, _OutputIterator __result,
1350 { return transform(__begin1, __end1, __begin2, __result, __binary_op,
1352
1353 // Public interface.
1354 template<typename _IIter1, typename _IIter2,
1355 typename _OutputIterator, typename _BinaryOperation>
1356 inline _OutputIterator
1357 transform(_IIter1 __begin1, _IIter1 __end1,
1358 _IIter2 __begin2, _OutputIterator __result,
1361 {
1363 typedef typename _IIterTraits1::iterator_category
1366 typedef typename _IIterTraits2::iterator_category
1369 typedef typename _OIterTraits::iterator_category _OIterCategory;
1370
1371 return __transform2_switch(
1375 }
1376
1377 template<typename _IIter1, typename _IIter2,
1378 typename _OutputIterator, typename _BinaryOperation>
1379 inline _OutputIterator
1380 transform(_IIter1 __begin1, _IIter1 __end1,
1381 _IIter2 __begin2, _OutputIterator __result,
1383 {
1385 typedef typename _IIterTraits1::iterator_category
1388 typedef typename _IIterTraits2::iterator_category
1391 typedef typename _OIterTraits::iterator_category _OIterCategory;
1392
1393 return __transform2_switch(
1396 }
1397
1398 // Sequential fallback
1399 template<typename _FIterator, typename _Tp>
1400 inline void
1401 replace(_FIterator __begin, _FIterator __end, const _Tp& __old_value,
1403 { _GLIBCXX_STD_A::replace(__begin, __end, __old_value, __new_value); }
1404
1405 // Sequential fallback for input iterator case
1406 template<typename _FIterator, typename _Tp, typename _IteratorTag>
1407 inline void
1408 __replace_switch(_FIterator __begin, _FIterator __end,
1409 const _Tp& __old_value, const _Tp& __new_value,
1411 { replace(__begin, __end, __old_value, __new_value,
1413
1414 // Parallel replace for random access iterators
1415 template<typename _RAIter, typename _Tp>
1416 inline void
1417 __replace_switch(_RAIter __begin, _RAIter __end,
1418 const _Tp& __old_value, const _Tp& __new_value,
1421 {
1422 // XXX parallel version is where?
1423 replace(__begin, __end, __old_value, __new_value,
1425 }
1426
1427 // Public interface
1428 template<typename _FIterator, typename _Tp>
1429 inline void
1430 replace(_FIterator __begin, _FIterator __end, const _Tp& __old_value,
1431 const _Tp& __new_value,
1433 {
1434 typedef iterator_traits<_FIterator> _TraitsType;
1435 typedef typename _TraitsType::iterator_category _IteratorCategory;
1436 __replace_switch(__begin, __end, __old_value, __new_value,
1439 }
1440
1441 template<typename _FIterator, typename _Tp>
1442 inline void
1443 replace(_FIterator __begin, _FIterator __end, const _Tp& __old_value,
1444 const _Tp& __new_value)
1445 {
1446 typedef iterator_traits<_FIterator> _TraitsType;
1447 typedef typename _TraitsType::iterator_category _IteratorCategory;
1448 __replace_switch(__begin, __end, __old_value, __new_value,
1450 }
1451
1452
1453 // Sequential fallback
1454 template<typename _FIterator, typename _Predicate, typename _Tp>
1455 inline void
1456 replace_if(_FIterator __begin, _FIterator __end, _Predicate __pred,
1458 { _GLIBCXX_STD_A::replace_if(__begin, __end, __pred, __new_value); }
1459
1460 // Sequential fallback for input iterator case
1461 template<typename _FIterator, typename _Predicate, typename _Tp,
1462 typename _IteratorTag>
1463 inline void
1464 __replace_if_switch(_FIterator __begin, _FIterator __end,
1465 _Predicate __pred, const _Tp& __new_value, _IteratorTag)
1466 { replace_if(__begin, __end, __pred, __new_value,
1468
1469 // Parallel algorithm for random access iterators.
1470 template<typename _RAIter, typename _Predicate, typename _Tp>
1471 void
1472 __replace_if_switch(_RAIter __begin, _RAIter __end,
1473 _Predicate __pred, const _Tp& __new_value,
1476 {
1478 static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
1479 >= __gnu_parallel::_Settings::get().replace_minimal_n
1480 && __gnu_parallel::__is_parallel(__parallelism_tag)))
1481 {
1482 bool __dummy;
1483 __gnu_parallel::
1484 __replace_if_selector<_RAIter, _Predicate, _Tp>
1488 __begin, __end, __pred, __functionality,
1490 true, __dummy, -1, __parallelism_tag);
1491 }
1492 else
1493 replace_if(__begin, __end, __pred, __new_value,
1495 }
1496
1497 // Public interface.
1498 template<typename _FIterator, typename _Predicate, typename _Tp>
1499 inline void
1500 replace_if(_FIterator __begin, _FIterator __end,
1501 _Predicate __pred, const _Tp& __new_value,
1503 {
1505 typedef typename _IteratorTraits::iterator_category _IteratorCategory;
1506 __replace_if_switch(__begin, __end, __pred, __new_value,
1508 }
1509
1510 template<typename _FIterator, typename _Predicate, typename _Tp>
1511 inline void
1512 replace_if(_FIterator __begin, _FIterator __end,
1513 _Predicate __pred, const _Tp& __new_value)
1514 {
1516 typedef typename _IteratorTraits::iterator_category _IteratorCategory;
1517 __replace_if_switch(__begin, __end, __pred, __new_value,
1519 }
1520
1521 // Sequential fallback
1522 template<typename _FIterator, typename _Generator>
1523 inline void
1524 generate(_FIterator __begin, _FIterator __end, _Generator __gen,
1526 { _GLIBCXX_STD_A::generate(__begin, __end, __gen); }
1527
1528 // Sequential fallback for input iterator case.
1529 template<typename _FIterator, typename _Generator, typename _IteratorTag>
1530 inline void
1531 __generate_switch(_FIterator __begin, _FIterator __end, _Generator __gen,
1533 { generate(__begin, __end, __gen, __gnu_parallel::sequential_tag()); }
1534
1535 // Parallel algorithm for random access iterators.
1536 template<typename _RAIter, typename _Generator>
1537 void
1538 __generate_switch(_RAIter __begin, _RAIter __end,
1541 {
1543 static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
1544 >= __gnu_parallel::_Settings::get().generate_minimal_n
1545 && __gnu_parallel::__is_parallel(__parallelism_tag)))
1546 {
1547 bool __dummy;
1552 __begin, __end, __gen, __functionality,
1554 true, __dummy, -1, __parallelism_tag);
1555 }
1556 else
1557 generate(__begin, __end, __gen, __gnu_parallel::sequential_tag());
1558 }
1559
1560 // Public interface.
1561 template<typename _FIterator, typename _Generator>
1562 inline void
1563 generate(_FIterator __begin, _FIterator __end,
1565 {
1567 typedef typename _IteratorTraits::iterator_category _IteratorCategory;
1568 __generate_switch(__begin, __end, __gen, _IteratorCategory(),
1570 }
1571
1572 template<typename _FIterator, typename _Generator>
1573 inline void
1574 generate(_FIterator __begin, _FIterator __end, _Generator __gen)
1575 {
1577 typedef typename _IteratorTraits::iterator_category _IteratorCategory;
1578 __generate_switch(__begin, __end, __gen, _IteratorCategory());
1579 }
1580
1581
1582 // Sequential fallback.
1583 template<typename _OutputIterator, typename _Size, typename _Generator>
1584 inline _OutputIterator
1585 generate_n(_OutputIterator __begin, _Size __n, _Generator __gen,
1587 { return _GLIBCXX_STD_A::generate_n(__begin, __n, __gen); }
1588
1589 // Sequential fallback for input iterator case.
1590 template<typename _OutputIterator, typename _Size, typename _Generator,
1591 typename _IteratorTag>
1592 inline _OutputIterator
1593 __generate_n_switch(_OutputIterator __begin, _Size __n, _Generator __gen,
1595 { return generate_n(__begin, __n, __gen,
1597
1598 // Parallel algorithm for random access iterators.
1599 template<typename _RAIter, typename _Size, typename _Generator>
1600 inline _RAIter
1601 __generate_n_switch(_RAIter __begin, _Size __n, _Generator __gen,
1604 {
1605 // XXX parallel version is where?
1606 return generate_n(__begin, __n, __gen, __gnu_parallel::sequential_tag());
1607 }
1608
1609 // Public interface.
1610 template<typename _OutputIterator, typename _Size, typename _Generator>
1611 inline _OutputIterator
1612 generate_n(_OutputIterator __begin, _Size __n, _Generator __gen,
1614 {
1616 typedef typename _IteratorTraits::iterator_category _IteratorCategory;
1617 return __generate_n_switch(__begin, __n, __gen, _IteratorCategory(),
1619 }
1620
1621 template<typename _OutputIterator, typename _Size, typename _Generator>
1622 inline _OutputIterator
1623 generate_n(_OutputIterator __begin, _Size __n, _Generator __gen)
1624 {
1626 typedef typename _IteratorTraits::iterator_category _IteratorCategory;
1627 return __generate_n_switch(__begin, __n, __gen, _IteratorCategory());
1628 }
1629
1630
1631 // Sequential fallback.
1632 template<typename _RAIter>
1633 inline void
1634 random_shuffle(_RAIter __begin, _RAIter __end,
1636 { _GLIBCXX_STD_A::random_shuffle(__begin, __end); }
1637
1638 // Sequential fallback.
1639 template<typename _RAIter, typename _RandomNumberGenerator>
1640 inline void
1641 random_shuffle(_RAIter __begin, _RAIter __end,
1644 { _GLIBCXX_STD_A::random_shuffle(__begin, __end, __rand); }
1645
1646
1647 /** @brief Functor wrapper for std::rand(). */
1648 template<typename _MustBeInt = int>
1650 {
1651 int
1652 operator()(int __limit)
1653 { return rand() % __limit; }
1654 };
1655
1656 // Fill in random number generator.
1657 template<typename _RAIter>
1658 inline void
1659 random_shuffle(_RAIter __begin, _RAIter __end)
1660 {
1661 _CRandNumber<> __r;
1662 // Parallelization still possible.
1663 __gnu_parallel::random_shuffle(__begin, __end, __r);
1664 }
1665
1666 // Parallel algorithm for random access iterators.
1667 template<typename _RAIter, typename _RandomNumberGenerator>
1668 void
1669 random_shuffle(_RAIter __begin, _RAIter __end,
1670#if __cplusplus >= 201103L
1672#else
1674#endif
1675 {
1676 if (__begin == __end)
1677 return;
1679 static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
1680 >= __gnu_parallel::_Settings::get().random_shuffle_minimal_n))
1682 else
1684 }
1685
1686 // Sequential fallback.
1687 template<typename _FIterator, typename _Predicate>
1688 inline _FIterator
1689 partition(_FIterator __begin, _FIterator __end,
1690 _Predicate __pred, __gnu_parallel::sequential_tag)
1691 { return _GLIBCXX_STD_A::partition(__begin, __end, __pred); }
1692
1693 // Sequential fallback for input iterator case.
1694 template<typename _FIterator, typename _Predicate, typename _IteratorTag>
1695 inline _FIterator
1696 __partition_switch(_FIterator __begin, _FIterator __end,
1697 _Predicate __pred, _IteratorTag)
1698 { return partition(__begin, __end, __pred,
1700
1701 // Parallel algorithm for random access iterators.
1702 template<typename _RAIter, typename _Predicate>
1703 _RAIter
1704 __partition_switch(_RAIter __begin, _RAIter __end,
1705 _Predicate __pred, random_access_iterator_tag)
1706 {
1708 static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
1709 >= __gnu_parallel::_Settings::get().partition_minimal_n))
1710 {
1711 typedef typename std::iterator_traits<_RAIter>::
1712 difference_type _DifferenceType;
1713 _DifferenceType __middle = __gnu_parallel::
1714 __parallel_partition(__begin, __end, __pred,
1715 __gnu_parallel::__get_max_threads());
1716 return __begin + __middle;
1717 }
1718 else
1719 return partition(__begin, __end, __pred,
1721 }
1722
1723 // Public interface.
1724 template<typename _FIterator, typename _Predicate>
1725 inline _FIterator
1726 partition(_FIterator __begin, _FIterator __end, _Predicate __pred)
1727 {
1728 typedef iterator_traits<_FIterator> _TraitsType;
1729 typedef typename _TraitsType::iterator_category _IteratorCategory;
1730 return __partition_switch(__begin, __end, __pred, _IteratorCategory());
1731 }
1732
1733 // sort interface
1734
1735 // Sequential fallback
1736 template<typename _RAIter>
1737 inline void
1738 sort(_RAIter __begin, _RAIter __end,
1740 { _GLIBCXX_STD_A::sort(__begin, __end); }
1741
1742 // Sequential fallback
1743 template<typename _RAIter, typename _Compare>
1744 inline void
1745 sort(_RAIter __begin, _RAIter __end, _Compare __comp,
1747 { _GLIBCXX_STD_A::sort<_RAIter, _Compare>(__begin, __end,
1748 __comp); }
1749
1750 // Public interface
1751 template<typename _RAIter, typename _Compare,
1752 typename _Parallelism>
1753 void
1754 sort(_RAIter __begin, _RAIter __end, _Compare __comp,
1755 _Parallelism __parallelism)
1756 {
1757 typedef iterator_traits<_RAIter> _TraitsType;
1758 typedef typename _TraitsType::value_type _ValueType;
1759
1760 if (__begin != __end)
1761 {
1763 static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin) >=
1764 __gnu_parallel::_Settings::get().sort_minimal_n))
1765 __gnu_parallel::__parallel_sort<false>(
1766 __begin, __end, __comp, __parallelism);
1767 else
1768 sort(__begin, __end, __comp, __gnu_parallel::sequential_tag());
1769 }
1770 }
1771
1772 // Public interface, insert default comparator
1773 template<typename _RAIter>
1774 inline void
1775 sort(_RAIter __begin, _RAIter __end)
1776 {
1777 typedef iterator_traits<_RAIter> _TraitsType;
1778 typedef typename _TraitsType::value_type _ValueType;
1779 sort(__begin, __end, std::less<_ValueType>(),
1781 }
1782
1783 // Public interface, insert default comparator
1784 template<typename _RAIter>
1785 inline void
1786 sort(_RAIter __begin, _RAIter __end,
1788 {
1789 typedef iterator_traits<_RAIter> _TraitsType;
1790 typedef typename _TraitsType::value_type _ValueType;
1791 sort(__begin, __end, std::less<_ValueType>(), __parallelism);
1792 }
1793
1794 // Public interface, insert default comparator
1795 template<typename _RAIter>
1796 inline void
1797 sort(_RAIter __begin, _RAIter __end,
1798 __gnu_parallel::parallel_tag __parallelism)
1799 {
1800 typedef iterator_traits<_RAIter> _TraitsType;
1801 typedef typename _TraitsType::value_type _ValueType;
1802 sort(__begin, __end, std::less<_ValueType>(), __parallelism);
1803 }
1804
1805 // Public interface, insert default comparator
1806 template<typename _RAIter>
1807 inline void
1808 sort(_RAIter __begin, _RAIter __end,
1810 {
1811 typedef iterator_traits<_RAIter> _TraitsType;
1812 typedef typename _TraitsType::value_type _ValueType;
1813 sort(__begin, __end, std::less<_ValueType>(), __parallelism);
1814 }
1815
1816 // Public interface, insert default comparator
1817 template<typename _RAIter>
1818 inline void
1819 sort(_RAIter __begin, _RAIter __end,
1821 {
1822 typedef iterator_traits<_RAIter> _TraitsType;
1823 typedef typename _TraitsType::value_type _ValueType;
1824 sort(__begin, __end, std::less<_ValueType>(), __parallelism);
1825 }
1826
1827 // Public interface, insert default comparator
1828 template<typename _RAIter>
1829 inline void
1830 sort(_RAIter __begin, _RAIter __end,
1832 {
1833 typedef iterator_traits<_RAIter> _TraitsType;
1834 typedef typename _TraitsType::value_type _ValueType;
1835 sort(__begin, __end, std::less<_ValueType>(), __parallelism);
1836 }
1837
1838 // Public interface, insert default comparator
1839 template<typename _RAIter>
1840 inline void
1841 sort(_RAIter __begin, _RAIter __end,
1842 __gnu_parallel::quicksort_tag __parallelism)
1843 {
1844 typedef iterator_traits<_RAIter> _TraitsType;
1845 typedef typename _TraitsType::value_type _ValueType;
1846 sort(__begin, __end, std::less<_ValueType>(), __parallelism);
1847 }
1848
1849 // Public interface, insert default comparator
1850 template<typename _RAIter>
1851 inline void
1852 sort(_RAIter __begin, _RAIter __end,
1854 {
1855 typedef iterator_traits<_RAIter> _TraitsType;
1856 typedef typename _TraitsType::value_type _ValueType;
1857 sort(__begin, __end, std::less<_ValueType>(), __parallelism);
1858 }
1859
1860 // Public interface
1861 template<typename _RAIter, typename _Compare>
1862 void
1863 sort(_RAIter __begin, _RAIter __end, _Compare __comp)
1864 {
1865 typedef iterator_traits<_RAIter> _TraitsType;
1866 typedef typename _TraitsType::value_type _ValueType;
1867 sort(__begin, __end, __comp, __gnu_parallel::default_parallel_tag());
1868 }
1869
1870
1871 // stable_sort interface
1872
1873
1874 // Sequential fallback
1875 template<typename _RAIter>
1876 inline void
1877 stable_sort(_RAIter __begin, _RAIter __end,
1879 { _GLIBCXX_STD_A::stable_sort(__begin, __end); }
1880
1881 // Sequential fallback
1882 template<typename _RAIter, typename _Compare>
1883 inline void
1884 stable_sort(_RAIter __begin, _RAIter __end,
1885 _Compare __comp, __gnu_parallel::sequential_tag)
1886 { _GLIBCXX_STD_A::stable_sort<_RAIter, _Compare>(
1887 __begin, __end, __comp); }
1888
1889 // Public interface
1890 template<typename _RAIter, typename _Compare,
1891 typename _Parallelism>
1892 void
1893 stable_sort(_RAIter __begin, _RAIter __end,
1894 _Compare __comp, _Parallelism __parallelism)
1895 {
1896 typedef iterator_traits<_RAIter> _TraitsType;
1897 typedef typename _TraitsType::value_type _ValueType;
1898
1899 if (__begin != __end)
1900 {
1902 static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin) >=
1903 __gnu_parallel::_Settings::get().sort_minimal_n))
1904 __gnu_parallel::__parallel_sort<true>(
1905 __begin, __end, __comp, __parallelism);
1906 else
1907 stable_sort(__begin, __end, __comp,
1909 }
1910 }
1911
1912 // Public interface, insert default comparator
1913 template<typename _RAIter>
1914 inline void
1915 stable_sort(_RAIter __begin, _RAIter __end)
1916 {
1917 typedef iterator_traits<_RAIter> _TraitsType;
1918 typedef typename _TraitsType::value_type _ValueType;
1919 stable_sort(__begin, __end, std::less<_ValueType>(),
1921 }
1922
1923 // Public interface, insert default comparator
1924 template<typename _RAIter>
1925 inline void
1926 stable_sort(_RAIter __begin, _RAIter __end,
1928 {
1929 typedef iterator_traits<_RAIter> _TraitsType;
1930 typedef typename _TraitsType::value_type _ValueType;
1931 stable_sort(__begin, __end, std::less<_ValueType>(), __parallelism);
1932 }
1933
1934 // Public interface, insert default comparator
1935 template<typename _RAIter>
1936 inline void
1937 stable_sort(_RAIter __begin, _RAIter __end,
1938 __gnu_parallel::parallel_tag __parallelism)
1939 {
1940 typedef iterator_traits<_RAIter> _TraitsType;
1941 typedef typename _TraitsType::value_type _ValueType;
1942 stable_sort(__begin, __end, std::less<_ValueType>(), __parallelism);
1943 }
1944
1945 // Public interface, insert default comparator
1946 template<typename _RAIter>
1947 inline void
1948 stable_sort(_RAIter __begin, _RAIter __end,
1950 {
1951 typedef iterator_traits<_RAIter> _TraitsType;
1952 typedef typename _TraitsType::value_type _ValueType;
1953 stable_sort(__begin, __end, std::less<_ValueType>(), __parallelism);
1954 }
1955
1956 // Public interface, insert default comparator
1957 template<typename _RAIter>
1958 inline void
1959 stable_sort(_RAIter __begin, _RAIter __end,
1960 __gnu_parallel::quicksort_tag __parallelism)
1961 {
1962 typedef iterator_traits<_RAIter> _TraitsType;
1963 typedef typename _TraitsType::value_type _ValueType;
1964 stable_sort(__begin, __end, std::less<_ValueType>(), __parallelism);
1965 }
1966
1967 // Public interface, insert default comparator
1968 template<typename _RAIter>
1969 inline void
1970 stable_sort(_RAIter __begin, _RAIter __end,
1972 {
1973 typedef iterator_traits<_RAIter> _TraitsType;
1974 typedef typename _TraitsType::value_type _ValueType;
1975 stable_sort(__begin, __end, std::less<_ValueType>(), __parallelism);
1976 }
1977
1978 // Public interface
1979 template<typename _RAIter, typename _Compare>
1980 void
1981 stable_sort(_RAIter __begin, _RAIter __end,
1982 _Compare __comp)
1983 {
1984 typedef iterator_traits<_RAIter> _TraitsType;
1985 typedef typename _TraitsType::value_type _ValueType;
1986 stable_sort(
1987 __begin, __end, __comp, __gnu_parallel::default_parallel_tag());
1988 }
1989
1990 // Sequential fallback
1991 template<typename _IIter1, typename _IIter2,
1992 typename _OutputIterator>
1993 inline _OutputIterator
1994 merge(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2,
1995 _IIter2 __end2, _OutputIterator __result,
1997 { return _GLIBCXX_STD_A::merge(
1998 __begin1, __end1, __begin2, __end2, __result); }
1999
2000 // Sequential fallback
2001 template<typename _IIter1, typename _IIter2,
2002 typename _OutputIterator, typename _Compare>
2003 inline _OutputIterator
2004 merge(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2,
2005 _IIter2 __end2, _OutputIterator __result, _Compare __comp,
2007 { return _GLIBCXX_STD_A::merge(
2008 __begin1, __end1, __begin2, __end2, __result, __comp); }
2009
2010 // Sequential fallback for input iterator case
2011 template<typename _IIter1, typename _IIter2, typename _OutputIterator,
2012 typename _Compare, typename _IteratorTag1,
2013 typename _IteratorTag2, typename _IteratorTag3>
2014 inline _OutputIterator
2015 __merge_switch(_IIter1 __begin1, _IIter1 __end1,
2016 _IIter2 __begin2, _IIter2 __end2,
2017 _OutputIterator __result, _Compare __comp,
2018 _IteratorTag1, _IteratorTag2, _IteratorTag3)
2019 { return _GLIBCXX_STD_A::merge(__begin1, __end1, __begin2, __end2,
2020 __result, __comp); }
2021
2022 // Parallel algorithm for random access iterators
2023 template<typename _IIter1, typename _IIter2,
2024 typename _OutputIterator, typename _Compare>
2025 _OutputIterator
2026 __merge_switch(_IIter1 __begin1, _IIter1 __end1,
2027 _IIter2 __begin2, _IIter2 __end2,
2028 _OutputIterator __result, _Compare __comp,
2029 random_access_iterator_tag, random_access_iterator_tag,
2030 random_access_iterator_tag)
2031 {
2033 (static_cast<__gnu_parallel::_SequenceIndex>(__end1 - __begin1)
2034 >= __gnu_parallel::_Settings::get().merge_minimal_n
2035 || static_cast<__gnu_parallel::_SequenceIndex>(__end2 - __begin2)
2036 >= __gnu_parallel::_Settings::get().merge_minimal_n)))
2038 __begin1, __end1, __begin2, __end2, __result,
2039 (__end1 - __begin1) + (__end2 - __begin2), __comp);
2040 else
2042 __begin1, __end1, __begin2, __end2, __result,
2043 (__end1 - __begin1) + (__end2 - __begin2), __comp);
2044 }
2045
2046 // Public interface
2047 template<typename _IIter1, typename _IIter2,
2048 typename _OutputIterator, typename _Compare>
2049 inline _OutputIterator
2050 merge(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2,
2051 _IIter2 __end2, _OutputIterator __result, _Compare __comp)
2052 {
2053 typedef typename iterator_traits<_IIter1>::value_type _ValueType;
2054
2055 typedef std::iterator_traits<_IIter1> _IIterTraits1;
2056 typedef std::iterator_traits<_IIter2> _IIterTraits2;
2057 typedef std::iterator_traits<_OutputIterator> _OIterTraits;
2058 typedef typename _IIterTraits1::iterator_category
2059 _IIterCategory1;
2060 typedef typename _IIterTraits2::iterator_category
2061 _IIterCategory2;
2062 typedef typename _OIterTraits::iterator_category _OIterCategory;
2063
2064 return __merge_switch(
2065 __begin1, __end1, __begin2, __end2, __result, __comp,
2066 _IIterCategory1(), _IIterCategory2(), _OIterCategory());
2067 }
2068
2069
2070 // Public interface, insert default comparator
2071 template<typename _IIter1, typename _IIter2,
2072 typename _OutputIterator>
2073 inline _OutputIterator
2074 merge(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2,
2075 _IIter2 __end2, _OutputIterator __result)
2076 {
2077 typedef std::iterator_traits<_IIter1> _Iterator1Traits;
2078 typedef std::iterator_traits<_IIter2> _Iterator2Traits;
2079 typedef typename _Iterator1Traits::value_type _ValueType1;
2080 typedef typename _Iterator2Traits::value_type _ValueType2;
2081
2082 return __gnu_parallel::merge(__begin1, __end1, __begin2, __end2,
2084 }
2085
2086 // Sequential fallback
2087 template<typename _RAIter>
2088 inline void
2089 nth_element(_RAIter __begin, _RAIter __nth,
2090 _RAIter __end, __gnu_parallel::sequential_tag)
2091 { return _GLIBCXX_STD_A::nth_element(__begin, __nth, __end); }
2092
2093 // Sequential fallback
2094 template<typename _RAIter, typename _Compare>
2095 inline void
2096 nth_element(_RAIter __begin, _RAIter __nth,
2097 _RAIter __end, _Compare __comp,
2099 { return _GLIBCXX_STD_A::nth_element(__begin, __nth, __end, __comp); }
2100
2101 // Public interface
2102 template<typename _RAIter, typename _Compare>
2103 inline void
2104 nth_element(_RAIter __begin, _RAIter __nth,
2105 _RAIter __end, _Compare __comp)
2106 {
2108 static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
2109 >= __gnu_parallel::_Settings::get().nth_element_minimal_n))
2110 __gnu_parallel::__parallel_nth_element(__begin, __nth, __end, __comp);
2111 else
2112 nth_element(__begin, __nth, __end, __comp,
2114 }
2115
2116 // Public interface, insert default comparator
2117 template<typename _RAIter>
2118 inline void
2119 nth_element(_RAIter __begin, _RAIter __nth,
2120 _RAIter __end)
2121 {
2122 typedef iterator_traits<_RAIter> _TraitsType;
2123 typedef typename _TraitsType::value_type _ValueType;
2124 __gnu_parallel::nth_element(__begin, __nth, __end,
2126 }
2127
2128 // Sequential fallback
2129 template<typename _RAIter, typename _Compare>
2130 inline void
2131 partial_sort(_RAIter __begin, _RAIter __middle,
2132 _RAIter __end, _Compare __comp,
2134 { _GLIBCXX_STD_A::partial_sort(__begin, __middle, __end, __comp); }
2135
2136 // Sequential fallback
2137 template<typename _RAIter>
2138 inline void
2139 partial_sort(_RAIter __begin, _RAIter __middle,
2140 _RAIter __end, __gnu_parallel::sequential_tag)
2141 { _GLIBCXX_STD_A::partial_sort(__begin, __middle, __end); }
2142
2143 // Public interface, parallel algorithm for random access iterators
2144 template<typename _RAIter, typename _Compare>
2145 void
2146 partial_sort(_RAIter __begin, _RAIter __middle,
2147 _RAIter __end, _Compare __comp)
2148 {
2150 static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
2151 >= __gnu_parallel::_Settings::get().partial_sort_minimal_n))
2153 __parallel_partial_sort(__begin, __middle, __end, __comp);
2154 else
2155 partial_sort(__begin, __middle, __end, __comp,
2157 }
2158
2159 // Public interface, insert default comparator
2160 template<typename _RAIter>
2161 inline void
2162 partial_sort(_RAIter __begin, _RAIter __middle,
2163 _RAIter __end)
2164 {
2165 typedef iterator_traits<_RAIter> _TraitsType;
2166 typedef typename _TraitsType::value_type _ValueType;
2167 __gnu_parallel::partial_sort(__begin, __middle, __end,
2169 }
2170
2171 // Sequential fallback
2172 template<typename _FIterator>
2173 inline _FIterator
2174 max_element(_FIterator __begin, _FIterator __end,
2176 { return _GLIBCXX_STD_A::max_element(__begin, __end); }
2177
2178 // Sequential fallback
2179 template<typename _FIterator, typename _Compare>
2180 inline _FIterator
2181 max_element(_FIterator __begin, _FIterator __end, _Compare __comp,
2183 { return _GLIBCXX_STD_A::max_element(__begin, __end, __comp); }
2184
2185 // Sequential fallback for input iterator case
2186 template<typename _FIterator, typename _Compare, typename _IteratorTag>
2187 inline _FIterator
2188 __max_element_switch(_FIterator __begin, _FIterator __end,
2189 _Compare __comp, _IteratorTag)
2190 { return max_element(__begin, __end, __comp,
2192
2193 // Parallel algorithm for random access iterators
2194 template<typename _RAIter, typename _Compare>
2195 _RAIter
2196 __max_element_switch(_RAIter __begin, _RAIter __end,
2197 _Compare __comp, random_access_iterator_tag,
2198 __gnu_parallel::_Parallelism __parallelism_tag)
2199 {
2201 static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
2202 >= __gnu_parallel::_Settings::get().max_element_minimal_n
2203 && __gnu_parallel::__is_parallel(__parallelism_tag)))
2204 {
2205 _RAIter __res(__begin);
2207 __functionality;
2210 __begin, __end, __gnu_parallel::_Nothing(), __functionality,
2212 __res, __res, -1, __parallelism_tag);
2213 return __res;
2214 }
2215 else
2216 return max_element(__begin, __end, __comp,
2218 }
2219
2220 // Public interface, insert default comparator
2221 template<typename _FIterator>
2222 inline _FIterator
2223 max_element(_FIterator __begin, _FIterator __end,
2224 __gnu_parallel::_Parallelism __parallelism_tag)
2225 {
2226 typedef typename iterator_traits<_FIterator>::value_type _ValueType;
2227 return max_element(__begin, __end, std::less<_ValueType>(),
2228 __parallelism_tag);
2229 }
2230
2231 template<typename _FIterator>
2232 inline _FIterator
2233 max_element(_FIterator __begin, _FIterator __end)
2234 {
2235 typedef typename iterator_traits<_FIterator>::value_type _ValueType;
2236 return __gnu_parallel::max_element(__begin, __end,
2238 }
2239
2240 // Public interface
2241 template<typename _FIterator, typename _Compare>
2242 inline _FIterator
2243 max_element(_FIterator __begin, _FIterator __end, _Compare __comp,
2244 __gnu_parallel::_Parallelism __parallelism_tag)
2245 {
2246 typedef iterator_traits<_FIterator> _TraitsType;
2247 typedef typename _TraitsType::iterator_category _IteratorCategory;
2248 return __max_element_switch(__begin, __end, __comp, _IteratorCategory(),
2249 __parallelism_tag);
2250 }
2251
2252 template<typename _FIterator, typename _Compare>
2253 inline _FIterator
2254 max_element(_FIterator __begin, _FIterator __end, _Compare __comp)
2255 {
2256 typedef iterator_traits<_FIterator> _TraitsType;
2257 typedef typename _TraitsType::iterator_category _IteratorCategory;
2258 return __max_element_switch(__begin, __end, __comp, _IteratorCategory());
2259 }
2260
2261
2262 // Sequential fallback
2263 template<typename _FIterator>
2264 inline _FIterator
2265 min_element(_FIterator __begin, _FIterator __end,
2267 { return _GLIBCXX_STD_A::min_element(__begin, __end); }
2268
2269 // Sequential fallback
2270 template<typename _FIterator, typename _Compare>
2271 inline _FIterator
2272 min_element(_FIterator __begin, _FIterator __end, _Compare __comp,
2274 { return _GLIBCXX_STD_A::min_element(__begin, __end, __comp); }
2275
2276 // Sequential fallback for input iterator case
2277 template<typename _FIterator, typename _Compare, typename _IteratorTag>
2278 inline _FIterator
2279 __min_element_switch(_FIterator __begin, _FIterator __end,
2280 _Compare __comp, _IteratorTag)
2281 { return min_element(__begin, __end, __comp,
2283
2284 // Parallel algorithm for random access iterators
2285 template<typename _RAIter, typename _Compare>
2286 _RAIter
2287 __min_element_switch(_RAIter __begin, _RAIter __end,
2288 _Compare __comp, random_access_iterator_tag,
2289 __gnu_parallel::_Parallelism __parallelism_tag)
2290 {
2292 static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
2293 >= __gnu_parallel::_Settings::get().min_element_minimal_n
2294 && __gnu_parallel::__is_parallel(__parallelism_tag)))
2295 {
2296 _RAIter __res(__begin);
2298 __functionality;
2301 __begin, __end, __gnu_parallel::_Nothing(), __functionality,
2303 __res, __res, -1, __parallelism_tag);
2304 return __res;
2305 }
2306 else
2307 return min_element(__begin, __end, __comp,
2309 }
2310
2311 // Public interface, insert default comparator
2312 template<typename _FIterator>
2313 inline _FIterator
2314 min_element(_FIterator __begin, _FIterator __end,
2315 __gnu_parallel::_Parallelism __parallelism_tag)
2316 {
2317 typedef typename iterator_traits<_FIterator>::value_type _ValueType;
2318 return min_element(__begin, __end, std::less<_ValueType>(),
2319 __parallelism_tag);
2320 }
2321
2322 template<typename _FIterator>
2323 inline _FIterator
2324 min_element(_FIterator __begin, _FIterator __end)
2325 {
2326 typedef typename iterator_traits<_FIterator>::value_type _ValueType;
2327 return __gnu_parallel::min_element(__begin, __end,
2329 }
2330
2331 // Public interface
2332 template<typename _FIterator, typename _Compare>
2333 inline _FIterator
2334 min_element(_FIterator __begin, _FIterator __end, _Compare __comp,
2335 __gnu_parallel::_Parallelism __parallelism_tag)
2336 {
2337 typedef iterator_traits<_FIterator> _TraitsType;
2338 typedef typename _TraitsType::iterator_category _IteratorCategory;
2339 return __min_element_switch(__begin, __end, __comp, _IteratorCategory(),
2340 __parallelism_tag);
2341 }
2342
2343 template<typename _FIterator, typename _Compare>
2344 inline _FIterator
2345 min_element(_FIterator __begin, _FIterator __end, _Compare __comp)
2346 {
2347 typedef iterator_traits<_FIterator> _TraitsType;
2348 typedef typename _TraitsType::iterator_category _IteratorCategory;
2349 return __min_element_switch(__begin, __end, __comp, _IteratorCategory());
2350 }
2351} // end namespace
2352} // end namespace
2353
2354#endif /* _GLIBCXX_PARALLEL_ALGO_H */
Parallel implementation base for std::find(), std::equal() and related functions. This file is a GNU ...
_Function objects representing different tasks to be plugged into the parallel find algorithm....
Main interface for embarrassingly parallel functions.
Functors representing different tasks to be plugged into the generic parallelization methods for emba...
Helper iterator classes for the std::transform() functions. This file is a GNU parallel extension to ...
Parallel implementation of std::merge(). This file is a GNU parallel extension to the Standard C++ Li...
Parallelization of embarrassingly parallel execution by means of an OpenMP for loop....
Parallelization of embarrassingly parallel execution by means of an OpenMP for loop with static sched...
Parallelization of embarrassingly parallel execution by means of equal splitting. This file is a GNU ...
Parallel implementation of std::partition(), std::nth_element(), and std::partial_sort()....
Parallel implementation of std::random_shuffle(). This file is a GNU parallel extension to the Standa...
Parallel implementation base for std::search() and std::search_n(). This file is a GNU parallel exten...
Parallel implementations of set operations for random-access iterators. This file is a GNU parallel e...
#define _GLIBCXX_PARALLEL_CONDITION(__c)
Determine at compile(?)-time if the parallel variant of an algorithm should be called.
Definition settings.h:95
Parallel sorting algorithm switch. This file is a GNU parallel extension to the Standard C++ Library.
Parallel implementations of std::unique_copy(). This file is a GNU parallel extension to the Standard...
Parallelization of embarrassingly parallel execution by means of work-stealing.
ISO C++ entities toplevel namespace is std.
GNU parallel code for public use.
_OutputIterator __merge_advance(_RAIter1 &__begin1, _RAIter1 __end1, _RAIter2 &__begin2, _RAIter2 __end2, _OutputIterator __target, _DifferenceTp __max_length, _Compare __comp)
Merge routine being able to merge only the __max_length smallest elements.
Definition merge.h:171
_UserOp __for_each_template_random_access(_IIter __begin, _IIter __end, _UserOp __user_op, _Functionality &__functionality, _Red __reduction, _Result __reduction_start, _Result &__output, typename std::iterator_traits< _IIter >::difference_type __bound, _Parallelism __parallelism_tag)
Chose the desired algorithm by evaluating __parallelism_tag.
Definition for_each.h:61
void __parallel_nth_element(_RAIter __begin, _RAIter __nth, _RAIter __end, _Compare __comp)
Parallel implementation of std::nth_element().
Definition partition.h:332
_OutputIterator __parallel_unique_copy(_IIter __first, _IIter __last, _OutputIterator __result, _BinaryPredicate __binary_pred)
Parallel std::unique_copy(), w/__o explicit equality predicate.
Definition unique_copy.h:50
uint64_t _SequenceIndex
Unsigned integer to index __elements. The total number of elements for each algorithm must fit into t...
Definition types.h:117
void __parallel_random_shuffle(_RAIter __begin, _RAIter __end, _RandomNumberGenerator __rng=_RandomNumber())
Parallel random public call.
_Parallelism
Run-time equivalents for the compile-time tags.
Definition types.h:45
void __sequential_random_shuffle(_RAIter __begin, _RAIter __end, _RandomNumberGenerator &__rng)
Sequential cache-efficient random shuffle.
void __parallel_partial_sort(_RAIter __begin, _RAIter __middle, _RAIter __end, _Compare __comp)
Parallel implementation of std::partial_sort().
Definition partition.h:422
std::iterator_traits< _RAIter >::difference_type __parallel_partition(_RAIter __begin, _RAIter __end, _Predicate __pred, _ThreadIndex __num_threads)
Parallel implementation of std::partition.
Definition partition.h:56
_RAIter3 __parallel_merge_advance(_RAIter1 &__begin1, _RAIter1 __end1, _RAIter2 &__begin2, _RAIter2 __end2, _RAIter3 __target, typename std::iterator_traits< _RAIter1 >::difference_type __max_length, _Compare __comp)
Merge routine fallback to sequential in case the iterators of the two input sequences are of differen...
Definition merge.h:195
__RAIter1 __search_template(__RAIter1 __begin1, __RAIter1 __end1, __RAIter2 __begin2, __RAIter2 __end2, _Pred __pred)
Parallel std::search.
Definition search.h:81
std::pair< _RAIter1, _RAIter2 > __find_template(_RAIter1 __begin1, _RAIter1 __end1, _RAIter2 __begin2, _Pred __pred, _Selector __selector)
Parallel std::find, switch for different algorithms.
Definition find.h:60
Random-access iterators support a superset of bidirectional iterator operations.
Functor wrapper for std::rand().
Definition algo.h:1650
Similar to std::binder2nd, but giving the argument types explicitly.
Similar to std::equal_to, but allows two different types.
Similar to std::less, but allows two different types.
Sequence that conceptually consists of multiple copies of the same element. The copies are not stored...
Test predicate on a single element, used for std::find() and std::find_if ().
Test predicate on two adjacent elements.
Test predicate on several elements.
std::transform() __selector, one input sequence variant.
std::transform() __selector, two input sequences variant.
Selector that just returns the passed iterator.
Functor doing nothing.
Reduction function doing nothing.
Reduction for finding the maximum element, using a comparator.
Reduction for finding the maximum element, using a comparator.
A pair of iterators. The usual iterator operations are applied to both child iterators.
Definition iterator.h:46
A triple of iterators. The usual iterator operations are applied to all three child iterators.
Definition iterator.h:121
static const _Settings & get()
Get the global settings.
Forces sequential execution at compile time.
Definition tags.h:42
Recommends parallel execution at compile time, optionally using a user-specified number of threads.
Definition tags.h:47
Recommends parallel execution using the default parallel algorithm.
Definition tags.h:80
Forces parallel sorting using multiway mergesort at compile time.
Definition tags.h:129
Forces parallel sorting using multiway mergesort with exact splitting at compile time.
Definition tags.h:138
Forces parallel sorting using multiway mergesort with splitting by sampling at compile time.
Definition tags.h:147
Forces parallel sorting using unbalanced quicksort at compile time.
Definition tags.h:156
Forces parallel sorting using balanced quicksort at compile time.
Definition tags.h:165
Sequential helper functions. This file is a GNU parallel extension to the Standard C++ Library.