libstdc++
algo.h
Go to the documentation of this file.
1// -*- C++ -*-
2
3// Copyright (C) 2007-2020 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 // Sequential fallback for input iterator case
73 template<typename _IIter, typename _Function, typename _IteratorTag>
74 inline _Function
75 __for_each_switch(_IIter __begin, _IIter __end, _Function __f,
77 { return for_each(__begin, __end, __f, __gnu_parallel::sequential_tag()); }
78
79 // Parallel algorithm for random access iterators
80 template<typename _RAIter, typename _Function>
82 __for_each_switch(_RAIter __begin, _RAIter __end,
85 {
87 static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
88 >= __gnu_parallel::_Settings::get().for_each_minimal_n
89 && __gnu_parallel::__is_parallel(__parallelism_tag)))
90 {
91 bool __dummy;
93
94 return __gnu_parallel::
96 __begin, __end, __f, __functionality,
99 }
100 else
101 return for_each(__begin, __end, __f, __gnu_parallel::sequential_tag());
102 }
103
104 // Public interface
105 template<typename _Iterator, typename _Function>
106 inline _Function
107 for_each(_Iterator __begin, _Iterator __end, _Function __f,
109 {
110 return __for_each_switch(__begin, __end, __f,
113 }
114
115 template<typename _Iterator, typename _Function>
116 inline _Function
117 for_each(_Iterator __begin, _Iterator __end, _Function __f)
118 {
119 return __for_each_switch(__begin, __end, __f,
120 std::__iterator_category(__begin));
121 }
122
123 // Sequential fallback
124 template<typename _IIter, typename _Tp>
125 inline _IIter
126 find(_IIter __begin, _IIter __end, const _Tp& __val,
128 { return _GLIBCXX_STD_A::find(__begin, __end, __val); }
129
130 // Sequential fallback for input iterator case
131 template<typename _IIter, typename _Tp, typename _IteratorTag>
132 inline _IIter
133 __find_switch(_IIter __begin, _IIter __end, const _Tp& __val,
135 { return _GLIBCXX_STD_A::find(__begin, __end, __val); }
136
137 // Parallel find for random access iterators
138 template<typename _RAIter, typename _Tp>
139 _RAIter
140 __find_switch(_RAIter __begin, _RAIter __end,
141 const _Tp& __val, random_access_iterator_tag)
142 {
143 typedef iterator_traits<_RAIter> _TraitsType;
144 typedef typename _TraitsType::value_type _ValueType;
145
147 {
149 const _Tp&>,
150 _ValueType, const _Tp&, bool>
153 __begin, __end, __begin, __comp,
155 }
156 else
157 return _GLIBCXX_STD_A::find(__begin, __end, __val);
158 }
159
160 // Public interface
161 template<typename _IIter, typename _Tp>
162 inline _IIter
163 find(_IIter __begin, _IIter __end, const _Tp& __val)
164 {
165 return __find_switch(__begin, __end, __val,
166 std::__iterator_category(__begin));
167 }
168
169 // Sequential fallback
170 template<typename _IIter, typename _Predicate>
171 inline _IIter
172 find_if(_IIter __begin, _IIter __end, _Predicate __pred,
174 { return _GLIBCXX_STD_A::find_if(__begin, __end, __pred); }
175
176 // Sequential fallback for input iterator case
177 template<typename _IIter, typename _Predicate, typename _IteratorTag>
178 inline _IIter
179 __find_if_switch(_IIter __begin, _IIter __end, _Predicate __pred,
181 { return _GLIBCXX_STD_A::find_if(__begin, __end, __pred); }
182
183 // Parallel find_if for random access iterators
184 template<typename _RAIter, typename _Predicate>
185 _RAIter
186 __find_if_switch(_RAIter __begin, _RAIter __end,
188 {
190 return __gnu_parallel::__find_template(__begin, __end, __begin, __pred,
192 __find_if_selector()).first;
193 else
194 return _GLIBCXX_STD_A::find_if(__begin, __end, __pred);
195 }
196
197 // Public interface
198 template<typename _IIter, typename _Predicate>
199 inline _IIter
200 find_if(_IIter __begin, _IIter __end, _Predicate __pred)
201 {
202 return __find_if_switch(__begin, __end, __pred,
203 std::__iterator_category(__begin));
204 }
205
206 // Sequential fallback
207 template<typename _IIter, typename _FIterator>
208 inline _IIter
209 find_first_of(_IIter __begin1, _IIter __end1,
210 _FIterator __begin2, _FIterator __end2,
212 {
213 return _GLIBCXX_STD_A::find_first_of(__begin1, __end1, __begin2, __end2);
214 }
215
216 // Sequential fallback
217 template<typename _IIter, typename _FIterator,
218 typename _BinaryPredicate>
219 inline _IIter
220 find_first_of(_IIter __begin1, _IIter __end1,
221 _FIterator __begin2, _FIterator __end2,
223 { return _GLIBCXX_STD_A::find_first_of(
224 __begin1, __end1, __begin2, __end2, __comp); }
225
226 // Sequential fallback for input iterator type
227 template<typename _IIter, typename _FIterator,
228 typename _IteratorTag1, typename _IteratorTag2>
229 inline _IIter
230 __find_first_of_switch(_IIter __begin1, _IIter __end1,
231 _FIterator __begin2, _FIterator __end2,
233 { return find_first_of(__begin1, __end1, __begin2, __end2,
235
236 // Parallel algorithm for random access iterators
237 template<typename _RAIter, typename _FIterator,
238 typename _BinaryPredicate, typename _IteratorTag>
239 inline _RAIter
240 __find_first_of_switch(_RAIter __begin1,
241 _RAIter __end1,
242 _FIterator __begin2, _FIterator __end2,
245 {
246 return __gnu_parallel::
249 <_FIterator>(__begin2, __end2)).first;
250 }
251
252 // Sequential fallback for input iterator type
253 template<typename _IIter, typename _FIterator,
254 typename _BinaryPredicate, typename _IteratorTag1,
255 typename _IteratorTag2>
256 inline _IIter
257 __find_first_of_switch(_IIter __begin1, _IIter __end1,
258 _FIterator __begin2, _FIterator __end2,
260 { return find_first_of(__begin1, __end1, __begin2, __end2, __comp,
262
263 // Public interface
264 template<typename _IIter, typename _FIterator,
265 typename _BinaryPredicate>
266 inline _IIter
267 find_first_of(_IIter __begin1, _IIter __end1,
268 _FIterator __begin2, _FIterator __end2,
269 _BinaryPredicate __comp)
270 {
271 return __find_first_of_switch(__begin1, __end1, __begin2, __end2, __comp,
274 }
275
276 // Public interface, insert default comparator
277 template<typename _IIter, typename _FIterator>
278 inline _IIter
279 find_first_of(_IIter __begin1, _IIter __end1,
280 _FIterator __begin2, _FIterator __end2)
281 {
284
285 return __gnu_parallel::find_first_of(__begin1, __end1, __begin2, __end2,
287 }
288
289 // Sequential fallback
290 template<typename _IIter, typename _OutputIterator>
291 inline _OutputIterator
292 unique_copy(_IIter __begin1, _IIter __end1, _OutputIterator __out,
294 { return _GLIBCXX_STD_A::unique_copy(__begin1, __end1, __out); }
295
296 // Sequential fallback
297 template<typename _IIter, typename _OutputIterator,
298 typename _Predicate>
299 inline _OutputIterator
300 unique_copy(_IIter __begin1, _IIter __end1, _OutputIterator __out,
302 { return _GLIBCXX_STD_A::unique_copy(__begin1, __end1, __out, __pred); }
303
304 // Sequential fallback for input iterator case
305 template<typename _IIter, typename _OutputIterator,
306 typename _Predicate, typename _IteratorTag1, typename _IteratorTag2>
307 inline _OutputIterator
308 __unique_copy_switch(_IIter __begin, _IIter __last,
309 _OutputIterator __out, _Predicate __pred,
311 { return _GLIBCXX_STD_A::unique_copy(__begin, __last, __out, __pred); }
312
313 // Parallel unique_copy for random access iterators
314 template<typename _RAIter, typename _RandomAccessOutputIterator,
315 typename _Predicate>
317 __unique_copy_switch(_RAIter __begin, _RAIter __last,
320 {
322 static_cast<__gnu_parallel::_SequenceIndex>(__last - __begin)
323 > __gnu_parallel::_Settings::get().unique_copy_minimal_n))
325 __begin, __last, __out, __pred);
326 else
327 return _GLIBCXX_STD_A::unique_copy(__begin, __last, __out, __pred);
328 }
329
330 // Public interface
331 template<typename _IIter, typename _OutputIterator>
332 inline _OutputIterator
333 unique_copy(_IIter __begin1, _IIter __end1, _OutputIterator __out)
334 {
335 typedef typename std::iterator_traits<_IIter>::value_type _ValueType;
336
337 return __unique_copy_switch(
341 }
342
343 // Public interface
344 template<typename _IIter, typename _OutputIterator, typename _Predicate>
345 inline _OutputIterator
346 unique_copy(_IIter __begin1, _IIter __end1, _OutputIterator __out,
347 _Predicate __pred)
348 {
349 return __unique_copy_switch(
353 }
354
355 // Sequential fallback
356 template<typename _IIter1, typename _IIter2,
357 typename _OutputIterator>
358 inline _OutputIterator
359 set_union(_IIter1 __begin1, _IIter1 __end1,
361 _OutputIterator __out, __gnu_parallel::sequential_tag)
362 { return _GLIBCXX_STD_A::set_union(
364
365 // Sequential fallback
366 template<typename _IIter1, typename _IIter2,
367 typename _OutputIterator, typename _Predicate>
368 inline _OutputIterator
369 set_union(_IIter1 __begin1, _IIter1 __end1,
371 _OutputIterator __out, _Predicate __pred,
373 { return _GLIBCXX_STD_A::set_union(__begin1, __end1,
375
376 // Sequential fallback for input iterator case
377 template<typename _IIter1, typename _IIter2, typename _Predicate,
378 typename _OutputIterator, typename _IteratorTag1,
379 typename _IteratorTag2, typename _IteratorTag3>
380 inline _OutputIterator
381 __set_union_switch(
383 _OutputIterator __result, _Predicate __pred,
385 { return _GLIBCXX_STD_A::set_union(__begin1, __end1,
386 __begin2, __end2, __result, __pred); }
387
388 // Parallel set_union for random access iterators
389 template<typename _RAIter1, typename _RAIter2,
390 typename _Output_RAIter, typename _Predicate>
392 __set_union_switch(_RAIter1 __begin1, _RAIter1 __end1,
394 _Output_RAIter __result, _Predicate __pred,
397 {
400 >= __gnu_parallel::_Settings::get().set_union_minimal_n
402 >= __gnu_parallel::_Settings::get().set_union_minimal_n))
403 return __gnu_parallel::__parallel_set_union(
404 __begin1, __end1, __begin2, __end2, __result, __pred);
405 else
406 return _GLIBCXX_STD_A::set_union(__begin1, __end1,
407 __begin2, __end2, __result, __pred);
408 }
409
410 // Public interface
411 template<typename _IIter1, typename _IIter2,
412 typename _OutputIterator>
413 inline _OutputIterator
414 set_union(_IIter1 __begin1, _IIter1 __end1,
415 _IIter2 __begin2, _IIter2 __end2, _OutputIterator __out)
416 {
419
420 return __set_union_switch(
426 }
427
428 // Public interface
429 template<typename _IIter1, typename _IIter2,
430 typename _OutputIterator, typename _Predicate>
431 inline _OutputIterator
432 set_union(_IIter1 __begin1, _IIter1 __end1,
434 _OutputIterator __out, _Predicate __pred)
435 {
436 return __set_union_switch(
441 }
442
443 // Sequential fallback.
444 template<typename _IIter1, typename _IIter2,
445 typename _OutputIterator>
446 inline _OutputIterator
447 set_intersection(_IIter1 __begin1, _IIter1 __end1,
449 _OutputIterator __out, __gnu_parallel::sequential_tag)
450 { return _GLIBCXX_STD_A::set_intersection(__begin1, __end1,
451 __begin2, __end2, __out); }
452
453 // Sequential fallback.
454 template<typename _IIter1, typename _IIter2,
455 typename _OutputIterator, typename _Predicate>
456 inline _OutputIterator
457 set_intersection(_IIter1 __begin1, _IIter1 __end1,
459 _OutputIterator __out, _Predicate __pred,
461 { return _GLIBCXX_STD_A::set_intersection(
463
464 // Sequential fallback for input iterator case
465 template<typename _IIter1, typename _IIter2,
466 typename _Predicate, typename _OutputIterator,
467 typename _IteratorTag1, typename _IteratorTag2,
468 typename _IteratorTag3>
469 inline _OutputIterator
470 __set_intersection_switch(_IIter1 __begin1, _IIter1 __end1,
472 _OutputIterator __result, _Predicate __pred,
474 { return _GLIBCXX_STD_A::set_intersection(__begin1, __end1, __begin2,
475 __end2, __result, __pred); }
476
477 // Parallel set_intersection for random access iterators
478 template<typename _RAIter1, typename _RAIter2,
479 typename _Output_RAIter, typename _Predicate>
481 __set_intersection_switch(_RAIter1 __begin1,
485 _Output_RAIter __result,
486 _Predicate __pred,
490 {
493 >= __gnu_parallel::_Settings::get().set_union_minimal_n
495 >= __gnu_parallel::_Settings::get().set_union_minimal_n))
496 return __gnu_parallel::__parallel_set_intersection(
497 __begin1, __end1, __begin2, __end2, __result, __pred);
498 else
499 return _GLIBCXX_STD_A::set_intersection(
500 __begin1, __end1, __begin2, __end2, __result, __pred);
501 }
502
503 // Public interface
504 template<typename _IIter1, typename _IIter2,
505 typename _OutputIterator>
506 inline _OutputIterator
507 set_intersection(_IIter1 __begin1, _IIter1 __end1,
509 _OutputIterator __out)
510 {
513
514 return __set_intersection_switch(
520 }
521
522 template<typename _IIter1, typename _IIter2,
523 typename _OutputIterator, typename _Predicate>
524 inline _OutputIterator
525 set_intersection(_IIter1 __begin1, _IIter1 __end1,
527 _OutputIterator __out, _Predicate __pred)
528 {
529 return __set_intersection_switch(
534 }
535
536 // Sequential fallback
537 template<typename _IIter1, typename _IIter2,
538 typename _OutputIterator>
539 inline _OutputIterator
540 set_symmetric_difference(_IIter1 __begin1, _IIter1 __end1,
542 _OutputIterator __out,
544 { return _GLIBCXX_STD_A::set_symmetric_difference(
546
547 // Sequential fallback
548 template<typename _IIter1, typename _IIter2,
549 typename _OutputIterator, typename _Predicate>
550 inline _OutputIterator
551 set_symmetric_difference(_IIter1 __begin1, _IIter1 __end1,
553 _OutputIterator __out, _Predicate __pred,
555 { return _GLIBCXX_STD_A::set_symmetric_difference(
557
558 // Sequential fallback for input iterator case
559 template<typename _IIter1, typename _IIter2,
560 typename _Predicate, typename _OutputIterator,
561 typename _IteratorTag1, typename _IteratorTag2,
562 typename _IteratorTag3>
563 inline _OutputIterator
564 __set_symmetric_difference_switch(
566 _OutputIterator __result, _Predicate __pred,
568 { return _GLIBCXX_STD_A::set_symmetric_difference(
569 __begin1, __end1, __begin2, __end2, __result, __pred); }
570
571 // Parallel set_symmetric_difference for random access iterators
572 template<typename _RAIter1, typename _RAIter2,
573 typename _Output_RAIter, typename _Predicate>
575 __set_symmetric_difference_switch(_RAIter1 __begin1,
579 _Output_RAIter __result,
580 _Predicate __pred,
584 {
587 >= __gnu_parallel::_Settings::get().set_symmetric_difference_minimal_n
589 >= __gnu_parallel::_Settings::get().set_symmetric_difference_minimal_n))
590 return __gnu_parallel::__parallel_set_symmetric_difference(
591 __begin1, __end1, __begin2, __end2, __result, __pred);
592 else
593 return _GLIBCXX_STD_A::set_symmetric_difference(
594 __begin1, __end1, __begin2, __end2, __result, __pred);
595 }
596
597 // Public interface.
598 template<typename _IIter1, typename _IIter2,
599 typename _OutputIterator>
600 inline _OutputIterator
601 set_symmetric_difference(_IIter1 __begin1, _IIter1 __end1,
603 _OutputIterator __out)
604 {
607
608 return __set_symmetric_difference_switch(
614 }
615
616 // Public interface.
617 template<typename _IIter1, typename _IIter2,
618 typename _OutputIterator, typename _Predicate>
619 inline _OutputIterator
620 set_symmetric_difference(_IIter1 __begin1, _IIter1 __end1,
622 _OutputIterator __out, _Predicate __pred)
623 {
624 return __set_symmetric_difference_switch(
629 }
630
631 // Sequential fallback.
632 template<typename _IIter1, typename _IIter2,
633 typename _OutputIterator>
634 inline _OutputIterator
635 set_difference(_IIter1 __begin1, _IIter1 __end1,
637 _OutputIterator __out, __gnu_parallel::sequential_tag)
638 { return _GLIBCXX_STD_A::set_difference(
640
641 // Sequential fallback.
642 template<typename _IIter1, typename _IIter2,
643 typename _OutputIterator, typename _Predicate>
644 inline _OutputIterator
645 set_difference(_IIter1 __begin1, _IIter1 __end1,
647 _OutputIterator __out, _Predicate __pred,
649 { return _GLIBCXX_STD_A::set_difference(__begin1, __end1,
651
652 // Sequential fallback for input iterator case.
653 template<typename _IIter1, typename _IIter2, typename _Predicate,
654 typename _OutputIterator, typename _IteratorTag1,
655 typename _IteratorTag2, typename _IteratorTag3>
656 inline _OutputIterator
657 __set_difference_switch(_IIter1 __begin1, _IIter1 __end1,
659 _OutputIterator __result, _Predicate __pred,
661 { return _GLIBCXX_STD_A::set_difference(
662 __begin1, __end1, __begin2, __end2, __result, __pred); }
663
664 // Parallel set_difference for random access iterators
665 template<typename _RAIter1, typename _RAIter2,
666 typename _Output_RAIter, typename _Predicate>
668 __set_difference_switch(_RAIter1 __begin1,
672 _Output_RAIter __result, _Predicate __pred,
676 {
679 >= __gnu_parallel::_Settings::get().set_difference_minimal_n
681 >= __gnu_parallel::_Settings::get().set_difference_minimal_n))
682 return __gnu_parallel::__parallel_set_difference(
683 __begin1, __end1, __begin2, __end2, __result, __pred);
684 else
685 return _GLIBCXX_STD_A::set_difference(
686 __begin1, __end1, __begin2, __end2, __result, __pred);
687 }
688
689 // Public interface
690 template<typename _IIter1, typename _IIter2,
691 typename _OutputIterator>
692 inline _OutputIterator
693 set_difference(_IIter1 __begin1, _IIter1 __end1,
695 _OutputIterator __out)
696 {
699
700 return __set_difference_switch(
706 }
707
708 // Public interface
709 template<typename _IIter1, typename _IIter2,
710 typename _OutputIterator, typename _Predicate>
711 inline _OutputIterator
712 set_difference(_IIter1 __begin1, _IIter1 __end1,
714 _OutputIterator __out, _Predicate __pred)
715 {
716 return __set_difference_switch(
721 }
722
723 // Sequential fallback
724 template<typename _FIterator>
725 inline _FIterator
726 adjacent_find(_FIterator __begin, _FIterator __end,
728 { return _GLIBCXX_STD_A::adjacent_find(__begin, __end); }
729
730 // Sequential fallback
731 template<typename _FIterator, typename _BinaryPredicate>
732 inline _FIterator
733 adjacent_find(_FIterator __begin, _FIterator __end,
736 { return _GLIBCXX_STD_A::adjacent_find(__begin, __end, __binary_pred); }
737
738 // Parallel algorithm for random access iterators
739 template<typename _RAIter>
740 _RAIter
741 __adjacent_find_switch(_RAIter __begin, _RAIter __end,
743 {
744 typedef iterator_traits<_RAIter> _TraitsType;
745 typedef typename _TraitsType::value_type _ValueType;
746
748 {
749 _RAIter __spot = __gnu_parallel::
751 __begin, __end - 1, __begin, equal_to<_ValueType>(),
753 .first;
754 if (__spot == (__end - 1))
755 return __end;
756 else
757 return __spot;
758 }
759 else
760 return adjacent_find(__begin, __end, __gnu_parallel::sequential_tag());
761 }
762
763 // Sequential fallback for input iterator case
764 template<typename _FIterator, typename _IteratorTag>
765 inline _FIterator
766 __adjacent_find_switch(_FIterator __begin, _FIterator __end,
768 { return adjacent_find(__begin, __end, __gnu_parallel::sequential_tag()); }
769
770 // Public interface
771 template<typename _FIterator>
772 inline _FIterator
773 adjacent_find(_FIterator __begin, _FIterator __end)
774 {
775 return __adjacent_find_switch(__begin, __end,
776 std::__iterator_category(__begin));
777 }
778
779 // Sequential fallback for input iterator case
780 template<typename _FIterator, typename _BinaryPredicate,
781 typename _IteratorTag>
782 inline _FIterator
783 __adjacent_find_switch(_FIterator __begin, _FIterator __end,
785 { return adjacent_find(__begin, __end, __pred,
787
788 // Parallel algorithm for random access iterators
789 template<typename _RAIter, typename _BinaryPredicate>
790 _RAIter
791 __adjacent_find_switch(_RAIter __begin, _RAIter __end,
793 {
795 return __gnu_parallel::__find_template(__begin, __end, __begin, __pred,
797 __adjacent_find_selector()).first;
798 else
799 return adjacent_find(__begin, __end, __pred,
801 }
802
803 // Public interface
804 template<typename _FIterator, typename _BinaryPredicate>
805 inline _FIterator
806 adjacent_find(_FIterator __begin, _FIterator __end,
808 {
809 return __adjacent_find_switch(__begin, __end, __pred,
810 std::__iterator_category(__begin));
811 }
812
813 // Sequential fallback
814 template<typename _IIter, typename _Tp>
816 count(_IIter __begin, _IIter __end, const _Tp& __value,
818 { return _GLIBCXX_STD_A::count(__begin, __end, __value); }
819
820 // Parallel code for random access iterators
821 template<typename _RAIter, typename _Tp>
823 __count_switch(_RAIter __begin, _RAIter __end,
824 const _Tp& __value, random_access_iterator_tag,
826 {
827 typedef iterator_traits<_RAIter> _TraitsType;
828 typedef typename _TraitsType::value_type _ValueType;
829 typedef typename _TraitsType::difference_type _DifferenceType;
830 typedef __gnu_parallel::_SequenceIndex _SequenceIndex;
831
833 static_cast<_SequenceIndex>(__end - __begin)
834 >= __gnu_parallel::_Settings::get().count_minimal_n
835 && __gnu_parallel::__is_parallel(__parallelism_tag)))
836 {
839 _DifferenceType __res = 0;
842 __begin, __end, __value, __functionality,
845 return __res;
846 }
847 else
848 return count(__begin, __end, __value,
850 }
851
852 // Sequential fallback for input iterator case.
853 template<typename _IIter, typename _Tp, typename _IteratorTag>
855 __count_switch(_IIter __begin, _IIter __end, const _Tp& __value,
857 { return count(__begin, __end, __value, __gnu_parallel::sequential_tag());
858 }
859
860 // Public interface.
861 template<typename _IIter, typename _Tp>
863 count(_IIter __begin, _IIter __end, const _Tp& __value,
865 {
866 return __count_switch(__begin, __end, __value,
869 }
870
871 template<typename _IIter, typename _Tp>
873 count(_IIter __begin, _IIter __end, const _Tp& __value)
874 {
875 return __count_switch(__begin, __end, __value,
876 std::__iterator_category(__begin));
877 }
878
879
880 // Sequential fallback.
881 template<typename _IIter, typename _Predicate>
883 count_if(_IIter __begin, _IIter __end, _Predicate __pred,
885 { return _GLIBCXX_STD_A::count_if(__begin, __end, __pred); }
886
887 // Parallel count_if for random access iterators
888 template<typename _RAIter, typename _Predicate>
890 __count_if_switch(_RAIter __begin, _RAIter __end,
893 {
894 typedef iterator_traits<_RAIter> _TraitsType;
895 typedef typename _TraitsType::value_type _ValueType;
896 typedef typename _TraitsType::difference_type _DifferenceType;
897 typedef __gnu_parallel::_SequenceIndex _SequenceIndex;
898
900 static_cast<_SequenceIndex>(__end - __begin)
901 >= __gnu_parallel::_Settings::get().count_minimal_n
902 && __gnu_parallel::__is_parallel(__parallelism_tag)))
903 {
904 _DifferenceType __res = 0;
905 __gnu_parallel::
906 __count_if_selector<_RAIter, _DifferenceType>
910 __begin, __end, __pred, __functionality,
913 return __res;
914 }
915 else
916 return count_if(__begin, __end, __pred,
918 }
919
920 // Sequential fallback for input iterator case.
921 template<typename _IIter, typename _Predicate, typename _IteratorTag>
923 __count_if_switch(_IIter __begin, _IIter __end, _Predicate __pred,
925 { return count_if(__begin, __end, __pred,
927
928 // Public interface.
929 template<typename _IIter, typename _Predicate>
931 count_if(_IIter __begin, _IIter __end, _Predicate __pred,
933 {
934 return __count_if_switch(__begin, __end, __pred,
937 }
938
939 template<typename _IIter, typename _Predicate>
941 count_if(_IIter __begin, _IIter __end, _Predicate __pred)
942 {
943 return __count_if_switch(__begin, __end, __pred,
944 std::__iterator_category(__begin));
945 }
946
947
948 // Sequential fallback.
949 template<typename _FIterator1, typename _FIterator2>
950 inline _FIterator1
954 { return _GLIBCXX_STD_A::search(__begin1, __end1, __begin2, __end2); }
955
956 // Parallel algorithm for random access iterator
957 template<typename _RAIter1, typename _RAIter2>
959 __search_switch(_RAIter1 __begin1, _RAIter1 __end1,
962 {
965
968 >= __gnu_parallel::_Settings::get().search_minimal_n))
969 return __gnu_parallel::
973 else
974 return search(__begin1, __end1, __begin2, __end2,
976 }
977
978 // Sequential fallback for input iterator case
979 template<typename _FIterator1, typename _FIterator2,
980 typename _IteratorTag1, typename _IteratorTag2>
981 inline _FIterator1
982 __search_switch(_FIterator1 __begin1, _FIterator1 __end1,
985 { return search(__begin1, __end1, __begin2, __end2,
987
988 // Public interface.
989 template<typename _FIterator1, typename _FIterator2>
990 inline _FIterator1
993 {
994 return __search_switch(__begin1, __end1, __begin2, __end2,
997 }
998
999 // Public interface.
1000 template<typename _FIterator1, typename _FIterator2,
1001 typename _BinaryPredicate>
1002 inline _FIterator1
1006 { return _GLIBCXX_STD_A::search(
1008
1009 // Parallel algorithm for random access iterator.
1010 template<typename _RAIter1, typename _RAIter2,
1011 typename _BinaryPredicate>
1012 _RAIter1
1013 __search_switch(_RAIter1 __begin1, _RAIter1 __end1,
1017 {
1020 >= __gnu_parallel::_Settings::get().search_minimal_n))
1023 else
1024 return search(__begin1, __end1, __begin2, __end2, __pred,
1026 }
1027
1028 // Sequential fallback for input iterator case
1029 template<typename _FIterator1, typename _FIterator2,
1030 typename _BinaryPredicate, typename _IteratorTag1,
1031 typename _IteratorTag2>
1032 inline _FIterator1
1033 __search_switch(_FIterator1 __begin1, _FIterator1 __end1,
1036 { return search(__begin1, __end1, __begin2, __end2, __pred,
1038
1039 // Public interface
1040 template<typename _FIterator1, typename _FIterator2,
1041 typename _BinaryPredicate>
1042 inline _FIterator1
1046 {
1047 return __search_switch(__begin1, __end1, __begin2, __end2, __pred,
1050 }
1051
1052 // Sequential fallback
1053 template<typename _FIterator, typename _Integer, typename _Tp>
1054 inline _FIterator
1055 search_n(_FIterator __begin, _FIterator __end, _Integer __count,
1056 const _Tp& __val, __gnu_parallel::sequential_tag)
1057 { return _GLIBCXX_STD_A::search_n(__begin, __end, __count, __val); }
1058
1059 // Sequential fallback
1060 template<typename _FIterator, typename _Integer, typename _Tp,
1061 typename _BinaryPredicate>
1062 inline _FIterator
1063 search_n(_FIterator __begin, _FIterator __end, _Integer __count,
1064 const _Tp& __val, _BinaryPredicate __binary_pred,
1066 { return _GLIBCXX_STD_A::search_n(
1067 __begin, __end, __count, __val, __binary_pred); }
1068
1069 // Public interface.
1070 template<typename _FIterator, typename _Integer, typename _Tp>
1071 inline _FIterator
1072 search_n(_FIterator __begin, _FIterator __end, _Integer __count,
1073 const _Tp& __val)
1074 {
1075 typedef typename iterator_traits<_FIterator>::value_type _ValueType;
1076 return __gnu_parallel::search_n(__begin, __end, __count, __val,
1078 }
1079
1080 // Parallel algorithm for random access iterators.
1081 template<typename _RAIter, typename _Integer,
1082 typename _Tp, typename _BinaryPredicate>
1083 _RAIter
1084 __search_n_switch(_RAIter __begin, _RAIter __end, _Integer __count,
1085 const _Tp& __val, _BinaryPredicate __binary_pred,
1087 {
1089 static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
1090 >= __gnu_parallel::_Settings::get().search_minimal_n))
1091 {
1094 __begin, __end, __ps.begin(), __ps.end(), __binary_pred);
1095 }
1096 else
1097 return _GLIBCXX_STD_A::search_n(__begin, __end, __count, __val,
1099 }
1100
1101 // Sequential fallback for input iterator case.
1102 template<typename _FIterator, typename _Integer, typename _Tp,
1103 typename _BinaryPredicate, typename _IteratorTag>
1104 inline _FIterator
1105 __search_n_switch(_FIterator __begin, _FIterator __end, _Integer __count,
1106 const _Tp& __val, _BinaryPredicate __binary_pred,
1108 { return _GLIBCXX_STD_A::search_n(__begin, __end, __count, __val,
1109 __binary_pred); }
1110
1111 // Public interface.
1112 template<typename _FIterator, typename _Integer, typename _Tp,
1113 typename _BinaryPredicate>
1114 inline _FIterator
1115 search_n(_FIterator __begin, _FIterator __end, _Integer __count,
1116 const _Tp& __val, _BinaryPredicate __binary_pred)
1117 {
1118 return __search_n_switch(__begin, __end, __count, __val, __binary_pred,
1119 std::__iterator_category(__begin));
1120 }
1121
1122
1123 // Sequential fallback.
1124 template<typename _IIter, typename _OutputIterator,
1125 typename _UnaryOperation>
1126 inline _OutputIterator
1127 transform(_IIter __begin, _IIter __end, _OutputIterator __result,
1129 { return _GLIBCXX_STD_A::transform(__begin, __end, __result, __unary_op); }
1130
1131 // Parallel unary transform for random access iterators.
1132 template<typename _RAIter1, typename _RAIter2,
1133 typename _UnaryOperation>
1134 _RAIter2
1135 __transform1_switch(_RAIter1 __begin, _RAIter1 __end,
1139 {
1141 static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
1142 >= __gnu_parallel::_Settings::get().transform_minimal_n
1143 && __gnu_parallel::__is_parallel(__parallelism_tag)))
1144 {
1145 bool __dummy = true;
1148 _ItTrip __begin_pair(__begin, __result),
1149 __end_pair(__end, __result + (__end - __begin));
1156 return __functionality._M_finish_iterator;
1157 }
1158 else
1159 return transform(__begin, __end, __result, __unary_op,
1161 }
1162
1163 // Sequential fallback for input iterator case.
1164 template<typename _RAIter1, typename _RAIter2,
1165 typename _UnaryOperation, typename _IteratorTag1,
1166 typename _IteratorTag2>
1167 inline _RAIter2
1168 __transform1_switch(_RAIter1 __begin, _RAIter1 __end,
1171 { return transform(__begin, __end, __result, __unary_op,
1173
1174 // Public interface.
1175 template<typename _IIter, typename _OutputIterator,
1176 typename _UnaryOperation>
1177 inline _OutputIterator
1178 transform(_IIter __begin, _IIter __end, _OutputIterator __result,
1181 {
1182 return __transform1_switch(__begin, __end, __result, __unary_op,
1183 std::__iterator_category(__begin),
1184 std::__iterator_category(__result),
1186 }
1187
1188 template<typename _IIter, typename _OutputIterator,
1189 typename _UnaryOperation>
1190 inline _OutputIterator
1191 transform(_IIter __begin, _IIter __end, _OutputIterator __result,
1193 {
1194 return __transform1_switch(__begin, __end, __result, __unary_op,
1195 std::__iterator_category(__begin),
1196 std::__iterator_category(__result));
1197 }
1198
1199
1200 // Sequential fallback
1201 template<typename _IIter1, typename _IIter2,
1202 typename _OutputIterator, typename _BinaryOperation>
1203 inline _OutputIterator
1204 transform(_IIter1 __begin1, _IIter1 __end1,
1205 _IIter2 __begin2, _OutputIterator __result,
1207 { return _GLIBCXX_STD_A::transform(__begin1, __end1,
1208 __begin2, __result, __binary_op); }
1209
1210 // Parallel binary transform for random access iterators.
1211 template<typename _RAIter1, typename _RAIter2,
1212 typename _RAIter3, typename _BinaryOperation>
1213 _RAIter3
1214 __transform2_switch(_RAIter1 __begin1, _RAIter1 __end1,
1220 {
1222 (__end1 - __begin1) >=
1223 __gnu_parallel::_Settings::get().transform_minimal_n
1224 && __gnu_parallel::__is_parallel(__parallelism_tag)))
1225 {
1226 bool __dummy = true;
1232 __result + (__end1 - __begin1));
1238 __dummy, __dummy, -1,
1240 return __functionality._M_finish_iterator;
1241 }
1242 else
1243 return transform(__begin1, __end1, __begin2, __result, __binary_op,
1245 }
1246
1247 // Sequential fallback for input iterator case.
1248 template<typename _IIter1, typename _IIter2,
1249 typename _OutputIterator, typename _BinaryOperation,
1250 typename _Tag1, typename _Tag2, typename _Tag3>
1251 inline _OutputIterator
1252 __transform2_switch(_IIter1 __begin1, _IIter1 __end1,
1253 _IIter2 __begin2, _OutputIterator __result,
1255 { return transform(__begin1, __end1, __begin2, __result, __binary_op,
1257
1258 // Public interface.
1259 template<typename _IIter1, typename _IIter2,
1260 typename _OutputIterator, typename _BinaryOperation>
1261 inline _OutputIterator
1262 transform(_IIter1 __begin1, _IIter1 __end1,
1263 _IIter2 __begin2, _OutputIterator __result,
1266 {
1267 return __transform2_switch(
1268 __begin1, __end1, __begin2, __result, __binary_op,
1271 std::__iterator_category(__result),
1273 }
1274
1275 template<typename _IIter1, typename _IIter2,
1276 typename _OutputIterator, typename _BinaryOperation>
1277 inline _OutputIterator
1278 transform(_IIter1 __begin1, _IIter1 __end1,
1279 _IIter2 __begin2, _OutputIterator __result,
1281 {
1282 return __transform2_switch(
1283 __begin1, __end1, __begin2, __result, __binary_op,
1286 std::__iterator_category(__result));
1287 }
1288
1289 // Sequential fallback
1290 template<typename _FIterator, typename _Tp>
1291 inline void
1292 replace(_FIterator __begin, _FIterator __end, const _Tp& __old_value,
1294 { _GLIBCXX_STD_A::replace(__begin, __end, __old_value, __new_value); }
1295
1296 // Sequential fallback for input iterator case
1297 template<typename _FIterator, typename _Tp, typename _IteratorTag>
1298 inline void
1299 __replace_switch(_FIterator __begin, _FIterator __end,
1300 const _Tp& __old_value, const _Tp& __new_value,
1302 { replace(__begin, __end, __old_value, __new_value,
1304
1305 // Parallel replace for random access iterators
1306 template<typename _RAIter, typename _Tp>
1307 inline void
1308 __replace_switch(_RAIter __begin, _RAIter __end,
1309 const _Tp& __old_value, const _Tp& __new_value,
1312 {
1313 // XXX parallel version is where?
1314 replace(__begin, __end, __old_value, __new_value,
1316 }
1317
1318 // Public interface
1319 template<typename _FIterator, typename _Tp>
1320 inline void
1321 replace(_FIterator __begin, _FIterator __end, const _Tp& __old_value,
1322 const _Tp& __new_value,
1324 {
1325 __replace_switch(__begin, __end, __old_value, __new_value,
1326 std::__iterator_category(__begin),
1328 }
1329
1330 template<typename _FIterator, typename _Tp>
1331 inline void
1332 replace(_FIterator __begin, _FIterator __end, const _Tp& __old_value,
1333 const _Tp& __new_value)
1334 {
1335 __replace_switch(__begin, __end, __old_value, __new_value,
1336 std::__iterator_category(__begin));
1337 }
1338
1339
1340 // Sequential fallback
1341 template<typename _FIterator, typename _Predicate, typename _Tp>
1342 inline void
1343 replace_if(_FIterator __begin, _FIterator __end, _Predicate __pred,
1345 { _GLIBCXX_STD_A::replace_if(__begin, __end, __pred, __new_value); }
1346
1347 // Sequential fallback for input iterator case
1348 template<typename _FIterator, typename _Predicate, typename _Tp,
1349 typename _IteratorTag>
1350 inline void
1351 __replace_if_switch(_FIterator __begin, _FIterator __end,
1352 _Predicate __pred, const _Tp& __new_value, _IteratorTag)
1353 { replace_if(__begin, __end, __pred, __new_value,
1355
1356 // Parallel algorithm for random access iterators.
1357 template<typename _RAIter, typename _Predicate, typename _Tp>
1358 void
1359 __replace_if_switch(_RAIter __begin, _RAIter __end,
1360 _Predicate __pred, const _Tp& __new_value,
1363 {
1365 static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
1366 >= __gnu_parallel::_Settings::get().replace_minimal_n
1367 && __gnu_parallel::__is_parallel(__parallelism_tag)))
1368 {
1369 bool __dummy;
1370 __gnu_parallel::
1371 __replace_if_selector<_RAIter, _Predicate, _Tp>
1375 __begin, __end, __pred, __functionality,
1377 true, __dummy, -1, __parallelism_tag);
1378 }
1379 else
1380 replace_if(__begin, __end, __pred, __new_value,
1382 }
1383
1384 // Public interface.
1385 template<typename _FIterator, typename _Predicate, typename _Tp>
1386 inline void
1387 replace_if(_FIterator __begin, _FIterator __end,
1388 _Predicate __pred, const _Tp& __new_value,
1390 {
1391 __replace_if_switch(__begin, __end, __pred, __new_value,
1392 std::__iterator_category(__begin),
1394 }
1395
1396 template<typename _FIterator, typename _Predicate, typename _Tp>
1397 inline void
1398 replace_if(_FIterator __begin, _FIterator __end,
1399 _Predicate __pred, const _Tp& __new_value)
1400 {
1401 __replace_if_switch(__begin, __end, __pred, __new_value,
1402 std::__iterator_category(__begin));
1403 }
1404
1405 // Sequential fallback
1406 template<typename _FIterator, typename _Generator>
1407 inline void
1408 generate(_FIterator __begin, _FIterator __end, _Generator __gen,
1410 { _GLIBCXX_STD_A::generate(__begin, __end, __gen); }
1411
1412 // Sequential fallback for input iterator case.
1413 template<typename _FIterator, typename _Generator, typename _IteratorTag>
1414 inline void
1415 __generate_switch(_FIterator __begin, _FIterator __end, _Generator __gen,
1417 { generate(__begin, __end, __gen, __gnu_parallel::sequential_tag()); }
1418
1419 // Parallel algorithm for random access iterators.
1420 template<typename _RAIter, typename _Generator>
1421 void
1422 __generate_switch(_RAIter __begin, _RAIter __end,
1425 {
1427 static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
1428 >= __gnu_parallel::_Settings::get().generate_minimal_n
1429 && __gnu_parallel::__is_parallel(__parallelism_tag)))
1430 {
1431 bool __dummy;
1436 __begin, __end, __gen, __functionality,
1438 true, __dummy, -1, __parallelism_tag);
1439 }
1440 else
1441 generate(__begin, __end, __gen, __gnu_parallel::sequential_tag());
1442 }
1443
1444 // Public interface.
1445 template<typename _FIterator, typename _Generator>
1446 inline void
1447 generate(_FIterator __begin, _FIterator __end,
1449 {
1450 __generate_switch(__begin, __end, __gen,
1451 std::__iterator_category(__begin),
1453 }
1454
1455 template<typename _FIterator, typename _Generator>
1456 inline void
1457 generate(_FIterator __begin, _FIterator __end, _Generator __gen)
1458 {
1459 __generate_switch(__begin, __end, __gen,
1460 std::__iterator_category(__begin));
1461 }
1462
1463
1464 // Sequential fallback.
1465 template<typename _OutputIterator, typename _Size, typename _Generator>
1466 inline _OutputIterator
1467 generate_n(_OutputIterator __begin, _Size __n, _Generator __gen,
1469 { return _GLIBCXX_STD_A::generate_n(__begin, __n, __gen); }
1470
1471 // Sequential fallback for input iterator case.
1472 template<typename _OutputIterator, typename _Size, typename _Generator,
1473 typename _IteratorTag>
1474 inline _OutputIterator
1475 __generate_n_switch(_OutputIterator __begin, _Size __n, _Generator __gen,
1477 { return generate_n(__begin, __n, __gen,
1479
1480 // Parallel algorithm for random access iterators.
1481 template<typename _RAIter, typename _Size, typename _Generator>
1482 inline _RAIter
1483 __generate_n_switch(_RAIter __begin, _Size __n, _Generator __gen,
1486 {
1487 // XXX parallel version is where?
1488 return generate_n(__begin, __n, __gen, __gnu_parallel::sequential_tag());
1489 }
1490
1491 // Public interface.
1492 template<typename _OutputIterator, typename _Size, typename _Generator>
1493 inline _OutputIterator
1494 generate_n(_OutputIterator __begin, _Size __n, _Generator __gen,
1496 {
1497 return __generate_n_switch(__begin, __n, __gen,
1498 std::__iterator_category(__begin),
1500 }
1501
1502 template<typename _OutputIterator, typename _Size, typename _Generator>
1503 inline _OutputIterator
1504 generate_n(_OutputIterator __begin, _Size __n, _Generator __gen)
1505 {
1506 return __generate_n_switch(__begin, __n, __gen,
1507 std::__iterator_category(__begin));
1508 }
1509
1510
1511 // Sequential fallback.
1512 template<typename _RAIter>
1513 inline void
1514 random_shuffle(_RAIter __begin, _RAIter __end,
1516 { _GLIBCXX_STD_A::random_shuffle(__begin, __end); }
1517
1518 // Sequential fallback.
1519 template<typename _RAIter, typename _RandomNumberGenerator>
1520 inline void
1521 random_shuffle(_RAIter __begin, _RAIter __end,
1524 { _GLIBCXX_STD_A::random_shuffle(__begin, __end, __rand); }
1525
1526
1527 /** @brief Functor wrapper for std::rand(). */
1528 template<typename _MustBeInt = int>
1530 {
1531 int
1532 operator()(int __limit)
1533 { return rand() % __limit; }
1534 };
1535
1536 // Fill in random number generator.
1537 template<typename _RAIter>
1538 inline void
1539 random_shuffle(_RAIter __begin, _RAIter __end)
1540 {
1541 _CRandNumber<> __r;
1542 // Parallelization still possible.
1543 __gnu_parallel::random_shuffle(__begin, __end, __r);
1544 }
1545
1546 // Parallel algorithm for random access iterators.
1547 template<typename _RAIter, typename _RandomNumberGenerator>
1548 void
1549 random_shuffle(_RAIter __begin, _RAIter __end,
1550#if __cplusplus >= 201103L
1552#else
1554#endif
1555 {
1556 if (__begin == __end)
1557 return;
1559 static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
1560 >= __gnu_parallel::_Settings::get().random_shuffle_minimal_n))
1562 else
1564 }
1565
1566 // Sequential fallback.
1567 template<typename _FIterator, typename _Predicate>
1568 inline _FIterator
1569 partition(_FIterator __begin, _FIterator __end,
1570 _Predicate __pred, __gnu_parallel::sequential_tag)
1571 { return _GLIBCXX_STD_A::partition(__begin, __end, __pred); }
1572
1573 // Sequential fallback for input iterator case.
1574 template<typename _FIterator, typename _Predicate, typename _IteratorTag>
1575 inline _FIterator
1576 __partition_switch(_FIterator __begin, _FIterator __end,
1577 _Predicate __pred, _IteratorTag)
1578 { return partition(__begin, __end, __pred,
1580
1581 // Parallel algorithm for random access iterators.
1582 template<typename _RAIter, typename _Predicate>
1583 _RAIter
1584 __partition_switch(_RAIter __begin, _RAIter __end,
1585 _Predicate __pred, random_access_iterator_tag)
1586 {
1588 static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
1589 >= __gnu_parallel::_Settings::get().partition_minimal_n))
1590 {
1591 typedef typename std::iterator_traits<_RAIter>::
1592 difference_type _DifferenceType;
1593 _DifferenceType __middle = __gnu_parallel::
1594 __parallel_partition(__begin, __end, __pred,
1595 __gnu_parallel::__get_max_threads());
1596 return __begin + __middle;
1597 }
1598 else
1599 return partition(__begin, __end, __pred,
1601 }
1602
1603 // Public interface.
1604 template<typename _FIterator, typename _Predicate>
1605 inline _FIterator
1606 partition(_FIterator __begin, _FIterator __end, _Predicate __pred)
1607 {
1608 return __partition_switch(__begin, __end, __pred,
1609 std::__iterator_category(__begin));
1610 }
1611
1612 // sort interface
1613
1614 // Sequential fallback
1615 template<typename _RAIter>
1616 inline void
1617 sort(_RAIter __begin, _RAIter __end,
1619 { _GLIBCXX_STD_A::sort(__begin, __end); }
1620
1621 // Sequential fallback
1622 template<typename _RAIter, typename _Compare>
1623 inline void
1624 sort(_RAIter __begin, _RAIter __end, _Compare __comp,
1626 { _GLIBCXX_STD_A::sort<_RAIter, _Compare>(__begin, __end,
1627 __comp); }
1628
1629 // Public interface
1630 template<typename _RAIter, typename _Compare,
1631 typename _Parallelism>
1632 void
1633 sort(_RAIter __begin, _RAIter __end, _Compare __comp,
1634 _Parallelism __parallelism)
1635 {
1636 typedef typename iterator_traits<_RAIter>::value_type _ValueType;
1637
1638 if (__begin != __end)
1639 {
1641 static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin) >=
1642 __gnu_parallel::_Settings::get().sort_minimal_n))
1643 __gnu_parallel::__parallel_sort<false>(
1644 __begin, __end, __comp, __parallelism);
1645 else
1646 sort(__begin, __end, __comp, __gnu_parallel::sequential_tag());
1647 }
1648 }
1649
1650 // Public interface, insert default comparator
1651 template<typename _RAIter>
1652 inline void
1653 sort(_RAIter __begin, _RAIter __end)
1654 {
1655 typedef typename iterator_traits<_RAIter>::value_type _ValueType;
1656 sort(__begin, __end, std::less<_ValueType>(),
1658 }
1659
1660 // Public interface, insert default comparator
1661 template<typename _RAIter>
1662 inline void
1663 sort(_RAIter __begin, _RAIter __end,
1665 {
1666 typedef typename iterator_traits<_RAIter>::value_type _ValueType;
1667 sort(__begin, __end, std::less<_ValueType>(), __parallelism);
1668 }
1669
1670 // Public interface, insert default comparator
1671 template<typename _RAIter>
1672 inline void
1673 sort(_RAIter __begin, _RAIter __end,
1674 __gnu_parallel::parallel_tag __parallelism)
1675 {
1676 typedef typename iterator_traits<_RAIter>::value_type _ValueType;
1677 sort(__begin, __end, std::less<_ValueType>(), __parallelism);
1678 }
1679
1680 // Public interface, insert default comparator
1681 template<typename _RAIter>
1682 inline void
1683 sort(_RAIter __begin, _RAIter __end,
1685 {
1686 typedef typename iterator_traits<_RAIter>::value_type _ValueType;
1687 sort(__begin, __end, std::less<_ValueType>(), __parallelism);
1688 }
1689
1690 // Public interface, insert default comparator
1691 template<typename _RAIter>
1692 inline void
1693 sort(_RAIter __begin, _RAIter __end,
1695 {
1696 typedef typename iterator_traits<_RAIter>::value_type _ValueType;
1697 sort(__begin, __end, std::less<_ValueType>(), __parallelism);
1698 }
1699
1700 // Public interface, insert default comparator
1701 template<typename _RAIter>
1702 inline void
1703 sort(_RAIter __begin, _RAIter __end,
1705 {
1706 typedef typename iterator_traits<_RAIter>::value_type _ValueType;
1707 sort(__begin, __end, std::less<_ValueType>(), __parallelism);
1708 }
1709
1710 // Public interface, insert default comparator
1711 template<typename _RAIter>
1712 inline void
1713 sort(_RAIter __begin, _RAIter __end,
1714 __gnu_parallel::quicksort_tag __parallelism)
1715 {
1716 typedef typename iterator_traits<_RAIter>::value_type _ValueType;
1717 sort(__begin, __end, std::less<_ValueType>(), __parallelism);
1718 }
1719
1720 // Public interface, insert default comparator
1721 template<typename _RAIter>
1722 inline void
1723 sort(_RAIter __begin, _RAIter __end,
1725 {
1726 typedef typename iterator_traits<_RAIter>::value_type _ValueType;
1727 sort(__begin, __end, std::less<_ValueType>(), __parallelism);
1728 }
1729
1730 // Public interface
1731 template<typename _RAIter, typename _Compare>
1732 void
1733 sort(_RAIter __begin, _RAIter __end, _Compare __comp)
1734 {
1735 typedef typename iterator_traits<_RAIter>::value_type _ValueType;
1736 sort(__begin, __end, __comp, __gnu_parallel::default_parallel_tag());
1737 }
1738
1739 // stable_sort interface
1740
1741
1742 // Sequential fallback
1743 template<typename _RAIter>
1744 inline void
1745 stable_sort(_RAIter __begin, _RAIter __end,
1747 { _GLIBCXX_STD_A::stable_sort(__begin, __end); }
1748
1749 // Sequential fallback
1750 template<typename _RAIter, typename _Compare>
1751 inline void
1752 stable_sort(_RAIter __begin, _RAIter __end,
1753 _Compare __comp, __gnu_parallel::sequential_tag)
1754 { _GLIBCXX_STD_A::stable_sort<_RAIter, _Compare>(__begin, __end, __comp); }
1755
1756 // Public interface
1757 template<typename _RAIter, typename _Compare,
1758 typename _Parallelism>
1759 void
1760 stable_sort(_RAIter __begin, _RAIter __end,
1761 _Compare __comp, _Parallelism __parallelism)
1762 {
1763 typedef iterator_traits<_RAIter> _TraitsType;
1764 typedef typename _TraitsType::value_type _ValueType;
1765
1766 if (__begin != __end)
1767 {
1769 static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin) >=
1770 __gnu_parallel::_Settings::get().sort_minimal_n))
1771 __gnu_parallel::__parallel_sort<true>(__begin, __end,
1772 __comp, __parallelism);
1773 else
1774 stable_sort(__begin, __end, __comp,
1776 }
1777 }
1778
1779 // Public interface, insert default comparator
1780 template<typename _RAIter>
1781 inline void
1782 stable_sort(_RAIter __begin, _RAIter __end)
1783 {
1784 typedef typename iterator_traits<_RAIter>::value_type _ValueType;
1785 stable_sort(__begin, __end, std::less<_ValueType>(),
1787 }
1788
1789 // Public interface, insert default comparator
1790 template<typename _RAIter>
1791 inline void
1792 stable_sort(_RAIter __begin, _RAIter __end,
1794 {
1795 typedef typename iterator_traits<_RAIter>::value_type _ValueType;
1796 stable_sort(__begin, __end, std::less<_ValueType>(), __parallelism);
1797 }
1798
1799 // Public interface, insert default comparator
1800 template<typename _RAIter>
1801 inline void
1802 stable_sort(_RAIter __begin, _RAIter __end,
1803 __gnu_parallel::parallel_tag __parallelism)
1804 {
1805 typedef typename iterator_traits<_RAIter>::value_type _ValueType;
1806 stable_sort(__begin, __end, std::less<_ValueType>(), __parallelism);
1807 }
1808
1809 // Public interface, insert default comparator
1810 template<typename _RAIter>
1811 inline void
1812 stable_sort(_RAIter __begin, _RAIter __end,
1814 {
1815 typedef typename iterator_traits<_RAIter>::value_type _ValueType;
1816 stable_sort(__begin, __end, std::less<_ValueType>(), __parallelism);
1817 }
1818
1819 // Public interface, insert default comparator
1820 template<typename _RAIter>
1821 inline void
1822 stable_sort(_RAIter __begin, _RAIter __end,
1823 __gnu_parallel::quicksort_tag __parallelism)
1824 {
1825 typedef typename iterator_traits<_RAIter>::value_type _ValueType;
1826 stable_sort(__begin, __end, std::less<_ValueType>(), __parallelism);
1827 }
1828
1829 // Public interface, insert default comparator
1830 template<typename _RAIter>
1831 inline void
1832 stable_sort(_RAIter __begin, _RAIter __end,
1834 {
1835 typedef typename iterator_traits<_RAIter>::value_type _ValueType;
1836 stable_sort(__begin, __end, std::less<_ValueType>(), __parallelism);
1837 }
1838
1839 // Public interface
1840 template<typename _RAIter, typename _Compare>
1841 void
1842 stable_sort(_RAIter __begin, _RAIter __end, _Compare __comp)
1843 {
1844 stable_sort(
1845 __begin, __end, __comp, __gnu_parallel::default_parallel_tag());
1846 }
1847
1848 // Sequential fallback
1849 template<typename _IIter1, typename _IIter2,
1850 typename _OutputIterator>
1851 inline _OutputIterator
1852 merge(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2,
1853 _IIter2 __end2, _OutputIterator __result,
1855 { return _GLIBCXX_STD_A::merge(
1856 __begin1, __end1, __begin2, __end2, __result); }
1857
1858 // Sequential fallback
1859 template<typename _IIter1, typename _IIter2,
1860 typename _OutputIterator, typename _Compare>
1861 inline _OutputIterator
1862 merge(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2,
1863 _IIter2 __end2, _OutputIterator __result, _Compare __comp,
1865 { return _GLIBCXX_STD_A::merge(
1866 __begin1, __end1, __begin2, __end2, __result, __comp); }
1867
1868 // Sequential fallback for input iterator case
1869 template<typename _IIter1, typename _IIter2, typename _OutputIterator,
1870 typename _Compare, typename _IteratorTag1,
1871 typename _IteratorTag2, typename _IteratorTag3>
1872 inline _OutputIterator
1873 __merge_switch(_IIter1 __begin1, _IIter1 __end1,
1874 _IIter2 __begin2, _IIter2 __end2,
1875 _OutputIterator __result, _Compare __comp,
1876 _IteratorTag1, _IteratorTag2, _IteratorTag3)
1877 { return _GLIBCXX_STD_A::merge(__begin1, __end1, __begin2, __end2,
1878 __result, __comp); }
1879
1880 // Parallel algorithm for random access iterators
1881 template<typename _IIter1, typename _IIter2,
1882 typename _OutputIterator, typename _Compare>
1883 _OutputIterator
1884 __merge_switch(_IIter1 __begin1, _IIter1 __end1,
1885 _IIter2 __begin2, _IIter2 __end2,
1886 _OutputIterator __result, _Compare __comp,
1887 random_access_iterator_tag, random_access_iterator_tag,
1888 random_access_iterator_tag)
1889 {
1891 (static_cast<__gnu_parallel::_SequenceIndex>(__end1 - __begin1)
1892 >= __gnu_parallel::_Settings::get().merge_minimal_n
1893 || static_cast<__gnu_parallel::_SequenceIndex>(__end2 - __begin2)
1894 >= __gnu_parallel::_Settings::get().merge_minimal_n)))
1896 __begin1, __end1, __begin2, __end2, __result,
1897 (__end1 - __begin1) + (__end2 - __begin2), __comp);
1898 else
1900 __begin1, __end1, __begin2, __end2, __result,
1901 (__end1 - __begin1) + (__end2 - __begin2), __comp);
1902 }
1903
1904 // Public interface
1905 template<typename _IIter1, typename _IIter2,
1906 typename _OutputIterator, typename _Compare>
1907 inline _OutputIterator
1908 merge(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2,
1909 _IIter2 __end2, _OutputIterator __result, _Compare __comp)
1910 {
1911 return __merge_switch(
1912 __begin1, __end1, __begin2, __end2, __result, __comp,
1913 std::__iterator_category(__begin1),
1914 std::__iterator_category(__begin2),
1915 std::__iterator_category(__result));
1916 }
1917
1918 // Public interface, insert default comparator
1919 template<typename _IIter1, typename _IIter2,
1920 typename _OutputIterator>
1921 inline _OutputIterator
1922 merge(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2,
1923 _IIter2 __end2, _OutputIterator __result)
1924 {
1925 typedef typename std::iterator_traits<_IIter1>::value_type _ValueType1;
1926 typedef typename std::iterator_traits<_IIter2>::value_type _ValueType2;
1927
1928 return __gnu_parallel::merge(__begin1, __end1, __begin2, __end2,
1930 }
1931
1932 // Sequential fallback
1933 template<typename _RAIter>
1934 inline void
1935 nth_element(_RAIter __begin, _RAIter __nth,
1936 _RAIter __end, __gnu_parallel::sequential_tag)
1937 { return _GLIBCXX_STD_A::nth_element(__begin, __nth, __end); }
1938
1939 // Sequential fallback
1940 template<typename _RAIter, typename _Compare>
1941 inline void
1942 nth_element(_RAIter __begin, _RAIter __nth,
1943 _RAIter __end, _Compare __comp,
1945 { return _GLIBCXX_STD_A::nth_element(__begin, __nth, __end, __comp); }
1946
1947 // Public interface
1948 template<typename _RAIter, typename _Compare>
1949 inline void
1950 nth_element(_RAIter __begin, _RAIter __nth,
1951 _RAIter __end, _Compare __comp)
1952 {
1954 static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
1955 >= __gnu_parallel::_Settings::get().nth_element_minimal_n))
1956 __gnu_parallel::__parallel_nth_element(__begin, __nth, __end, __comp);
1957 else
1958 nth_element(__begin, __nth, __end, __comp,
1960 }
1961
1962 // Public interface, insert default comparator
1963 template<typename _RAIter>
1964 inline void
1965 nth_element(_RAIter __begin, _RAIter __nth,
1966 _RAIter __end)
1967 {
1968 typedef typename iterator_traits<_RAIter>::value_type _ValueType;
1969 __gnu_parallel::nth_element(__begin, __nth, __end,
1971 }
1972
1973 // Sequential fallback
1974 template<typename _RAIter, typename _Compare>
1975 inline void
1976 partial_sort(_RAIter __begin, _RAIter __middle,
1977 _RAIter __end, _Compare __comp,
1979 { _GLIBCXX_STD_A::partial_sort(__begin, __middle, __end, __comp); }
1980
1981 // Sequential fallback
1982 template<typename _RAIter>
1983 inline void
1984 partial_sort(_RAIter __begin, _RAIter __middle,
1985 _RAIter __end, __gnu_parallel::sequential_tag)
1986 { _GLIBCXX_STD_A::partial_sort(__begin, __middle, __end); }
1987
1988 // Public interface, parallel algorithm for random access iterators
1989 template<typename _RAIter, typename _Compare>
1990 void
1991 partial_sort(_RAIter __begin, _RAIter __middle,
1992 _RAIter __end, _Compare __comp)
1993 {
1995 static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
1996 >= __gnu_parallel::_Settings::get().partial_sort_minimal_n))
1998 __parallel_partial_sort(__begin, __middle, __end, __comp);
1999 else
2000 partial_sort(__begin, __middle, __end, __comp,
2002 }
2003
2004 // Public interface, insert default comparator
2005 template<typename _RAIter>
2006 inline void
2007 partial_sort(_RAIter __begin, _RAIter __middle,
2008 _RAIter __end)
2009 {
2010 typedef iterator_traits<_RAIter> _TraitsType;
2011 typedef typename _TraitsType::value_type _ValueType;
2012 __gnu_parallel::partial_sort(__begin, __middle, __end,
2014 }
2015
2016 // Sequential fallback
2017 template<typename _FIterator>
2018 inline _FIterator
2019 max_element(_FIterator __begin, _FIterator __end,
2021 { return _GLIBCXX_STD_A::max_element(__begin, __end); }
2022
2023 // Sequential fallback
2024 template<typename _FIterator, typename _Compare>
2025 inline _FIterator
2026 max_element(_FIterator __begin, _FIterator __end, _Compare __comp,
2028 { return _GLIBCXX_STD_A::max_element(__begin, __end, __comp); }
2029
2030 // Sequential fallback for input iterator case
2031 template<typename _FIterator, typename _Compare, typename _IteratorTag>
2032 inline _FIterator
2033 __max_element_switch(_FIterator __begin, _FIterator __end,
2034 _Compare __comp, _IteratorTag)
2035 { return max_element(__begin, __end, __comp,
2037
2038 // Parallel algorithm for random access iterators
2039 template<typename _RAIter, typename _Compare>
2040 _RAIter
2041 __max_element_switch(_RAIter __begin, _RAIter __end,
2042 _Compare __comp, random_access_iterator_tag,
2043 __gnu_parallel::_Parallelism __parallelism_tag)
2044 {
2046 static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
2047 >= __gnu_parallel::_Settings::get().max_element_minimal_n
2048 && __gnu_parallel::__is_parallel(__parallelism_tag)))
2049 {
2050 _RAIter __res(__begin);
2052 __functionality;
2055 __begin, __end, __gnu_parallel::_Nothing(), __functionality,
2057 __res, __res, -1, __parallelism_tag);
2058 return __res;
2059 }
2060 else
2061 return max_element(__begin, __end, __comp,
2063 }
2064
2065 // Public interface, insert default comparator
2066 template<typename _FIterator>
2067 inline _FIterator
2068 max_element(_FIterator __begin, _FIterator __end,
2069 __gnu_parallel::_Parallelism __parallelism_tag)
2070 {
2071 typedef typename iterator_traits<_FIterator>::value_type _ValueType;
2072 return max_element(__begin, __end, std::less<_ValueType>(),
2073 __parallelism_tag);
2074 }
2075
2076 template<typename _FIterator>
2077 inline _FIterator
2078 max_element(_FIterator __begin, _FIterator __end)
2079 {
2080 typedef typename iterator_traits<_FIterator>::value_type _ValueType;
2081 return __gnu_parallel::max_element(__begin, __end,
2083 }
2084
2085 // Public interface
2086 template<typename _FIterator, typename _Compare>
2087 inline _FIterator
2088 max_element(_FIterator __begin, _FIterator __end, _Compare __comp,
2089 __gnu_parallel::_Parallelism __parallelism_tag)
2090 {
2091 return __max_element_switch(__begin, __end, __comp,
2092 std::__iterator_category(__begin),
2093 __parallelism_tag);
2094 }
2095
2096 template<typename _FIterator, typename _Compare>
2097 inline _FIterator
2098 max_element(_FIterator __begin, _FIterator __end, _Compare __comp)
2099 {
2100 return __max_element_switch(__begin, __end, __comp,
2101 std::__iterator_category(__begin));
2102 }
2103
2104
2105 // Sequential fallback
2106 template<typename _FIterator>
2107 inline _FIterator
2108 min_element(_FIterator __begin, _FIterator __end,
2110 { return _GLIBCXX_STD_A::min_element(__begin, __end); }
2111
2112 // Sequential fallback
2113 template<typename _FIterator, typename _Compare>
2114 inline _FIterator
2115 min_element(_FIterator __begin, _FIterator __end, _Compare __comp,
2117 { return _GLIBCXX_STD_A::min_element(__begin, __end, __comp); }
2118
2119 // Sequential fallback for input iterator case
2120 template<typename _FIterator, typename _Compare, typename _IteratorTag>
2121 inline _FIterator
2122 __min_element_switch(_FIterator __begin, _FIterator __end,
2123 _Compare __comp, _IteratorTag)
2124 { return min_element(__begin, __end, __comp,
2126
2127 // Parallel algorithm for random access iterators
2128 template<typename _RAIter, typename _Compare>
2129 _RAIter
2130 __min_element_switch(_RAIter __begin, _RAIter __end,
2131 _Compare __comp, random_access_iterator_tag,
2132 __gnu_parallel::_Parallelism __parallelism_tag)
2133 {
2135 static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
2136 >= __gnu_parallel::_Settings::get().min_element_minimal_n
2137 && __gnu_parallel::__is_parallel(__parallelism_tag)))
2138 {
2139 _RAIter __res(__begin);
2141 __functionality;
2144 __begin, __end, __gnu_parallel::_Nothing(), __functionality,
2146 __res, __res, -1, __parallelism_tag);
2147 return __res;
2148 }
2149 else
2150 return min_element(__begin, __end, __comp,
2152 }
2153
2154 // Public interface, insert default comparator
2155 template<typename _FIterator>
2156 inline _FIterator
2157 min_element(_FIterator __begin, _FIterator __end,
2158 __gnu_parallel::_Parallelism __parallelism_tag)
2159 {
2160 typedef typename iterator_traits<_FIterator>::value_type _ValueType;
2161 return min_element(__begin, __end, std::less<_ValueType>(),
2162 __parallelism_tag);
2163 }
2164
2165 template<typename _FIterator>
2166 inline _FIterator
2167 min_element(_FIterator __begin, _FIterator __end)
2168 {
2169 typedef typename iterator_traits<_FIterator>::value_type _ValueType;
2170 return __gnu_parallel::min_element(__begin, __end,
2172 }
2173
2174 // Public interface
2175 template<typename _FIterator, typename _Compare>
2176 inline _FIterator
2177 min_element(_FIterator __begin, _FIterator __end, _Compare __comp,
2178 __gnu_parallel::_Parallelism __parallelism_tag)
2179 {
2180 return __min_element_switch(__begin, __end, __comp,
2181 std::__iterator_category(__begin),
2182 __parallelism_tag);
2183 }
2184
2185 template<typename _FIterator, typename _Compare>
2186 inline _FIterator
2187 min_element(_FIterator __begin, _FIterator __end, _Compare __comp)
2188 {
2189 return __min_element_switch(__begin, __end, __comp,
2190 std::__iterator_category(__begin));
2191 }
2192
2193#if __cplusplus >= 201703L
2194 using _GLIBCXX_STD_A::for_each_n;
2195 using _GLIBCXX_STD_A::sample;
2196#endif
2197} // end namespace
2198} // end namespace
2199
2200#endif /* _GLIBCXX_PARALLEL_ALGO_H */
Parallel implementation of std::partition(), std::nth_element(), and std::partial_sort()....
Parallelization of embarrassingly parallel execution by means of work-stealing.
Parallelization of embarrassingly parallel execution by means of an OpenMP for loop....
Main interface for embarrassingly parallel functions.
Parallel implementation base for std::search() and std::search_n(). This file is a GNU parallel exten...
Parallel implementations of std::unique_copy(). This file is a GNU parallel extension to the Standard...
#define _GLIBCXX_PARALLEL_CONDITION(__c)
Determine at compile(?)-time if the parallel variant of an algorithm should be called.
Definition settings.h:94
Parallel implementations of set operations for random-access iterators. This file is a GNU parallel e...
Functors representing different tasks to be plugged into the generic parallelization methods for emba...
_Function objects representing different tasks to be plugged into the parallel find algorithm....
Parallel implementation base for std::find(), std::equal() and related functions. This file is a GNU ...
Parallelization of embarrassingly parallel execution by means of equal splitting. This file is a GNU ...
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...
Sequential helper functions. This file is a GNU parallel extension to the Standard C++ Library.
Parallelization of embarrassingly parallel execution by means of an OpenMP for loop with static sched...
Parallel sorting algorithm switch. This file is a GNU parallel extension to the Standard C++ Library.
Parallel implementation of std::random_shuffle(). This file is a GNU parallel extension to the Standa...
constexpr iterator_traits< _Iter >::iterator_category __iterator_category(const _Iter &)
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
Traits class for iterators.
Random-access iterators support a superset of bidirectional iterator operations.
Functor wrapper for std::rand().
Definition algo.h:1530
Similar to std::binder2nd, but giving the argument types explicitly.
Definition base.h:222
Similar to std::equal_to, but allows two different types.
Definition base.h:245
Similar to std::less, but allows two different types.
Definition base.h:253
Sequence that conceptually consists of multiple copies of the same element. The copies are not stored...
Definition base.h:360
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