libstdc++
algo.h
Go to the documentation of this file.
1// -*- C++ -*-
2
3// Copyright (C) 2007-2019 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,
76 _IteratorTag)
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>
81 _Function
82 __for_each_switch(_RAIter __begin, _RAIter __end,
83 _Function __f, random_access_iterator_tag,
84 __gnu_parallel::_Parallelism __parallelism_tag)
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,
97 __gnu_parallel::_DummyReduct(), true, __dummy, -1,
98 __parallelism_tag);
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,
108 __gnu_parallel::_Parallelism __parallelism_tag)
109 {
110 return __for_each_switch(__begin, __end, __f,
112 __parallelism_tag);
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,
134 _IteratorTag)
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,
180 _IteratorTag)
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,
187 _Predicate __pred, random_access_iterator_tag)
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,
222 _BinaryPredicate __comp, __gnu_parallel::sequential_tag)
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,
232 _IteratorTag1, _IteratorTag2)
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,
243 _BinaryPredicate __comp, random_access_iterator_tag,
244 _IteratorTag)
245 {
246 return __gnu_parallel::
247 __find_template(__begin1, __end1, __begin1, __comp,
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,
259 _BinaryPredicate __comp, _IteratorTag1, _IteratorTag2)
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,
272 std::__iterator_category(__begin1),
273 std::__iterator_category(__begin2));
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 {
282 typedef typename std::iterator_traits<_IIter>::value_type _IValueType;
283 typedef typename std::iterator_traits<_FIterator>::value_type _FValueType;
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,
301 _Predicate __pred, __gnu_parallel::sequential_tag)
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,
310 _IteratorTag1, _IteratorTag2)
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>
316 RandomAccessOutputIterator
317 __unique_copy_switch(_RAIter __begin, _RAIter __last,
318 RandomAccessOutputIterator __out, _Predicate __pred,
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(
338 __begin1, __end1, __out, equal_to<_ValueType>(),
339 std::__iterator_category(__begin1),
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(
350 __begin1, __end1, __out, __pred,
351 std::__iterator_category(__begin1),
353 }
354
355 // Sequential fallback
356 template<typename _IIter1, typename _IIter2,
357 typename _OutputIterator>
358 inline _OutputIterator
359 set_union(_IIter1 __begin1, _IIter1 __end1,
360 _IIter2 __begin2, _IIter2 __end2,
361 _OutputIterator __out, __gnu_parallel::sequential_tag)
362 { return _GLIBCXX_STD_A::set_union(
363 __begin1, __end1, __begin2, __end2, __out); }
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,
370 _IIter2 __begin2, _IIter2 __end2,
371 _OutputIterator __out, _Predicate __pred,
373 { return _GLIBCXX_STD_A::set_union(__begin1, __end1,
374 __begin2, __end2, __out, __pred); }
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(
382 _IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, _IIter2 __end2,
383 _OutputIterator __result, _Predicate __pred,
384 _IteratorTag1, _IteratorTag2, _IteratorTag3)
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>
391 _Output_RAIter
392 __set_union_switch(_RAIter1 __begin1, _RAIter1 __end1,
393 _RAIter2 __begin2, _RAIter2 __end2,
394 _Output_RAIter __result, _Predicate __pred,
397 {
399 static_cast<__gnu_parallel::_SequenceIndex>(__end1 - __begin1)
400 >= __gnu_parallel::_Settings::get().set_union_minimal_n
401 || static_cast<__gnu_parallel::_SequenceIndex>(__end2 - __begin2)
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 {
417 typedef typename std::iterator_traits<_IIter1>::value_type _ValueType1;
418 typedef typename std::iterator_traits<_IIter2>::value_type _ValueType2;
419
420 return __set_union_switch(
421 __begin1, __end1, __begin2, __end2, __out,
423 std::__iterator_category(__begin1),
424 std::__iterator_category(__begin2),
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,
433 _IIter2 __begin2, _IIter2 __end2,
434 _OutputIterator __out, _Predicate __pred)
435 {
436 return __set_union_switch(
437 __begin1, __end1, __begin2, __end2, __out, __pred,
438 std::__iterator_category(__begin1),
439 std::__iterator_category(__begin2),
441 }
442
443 // Sequential fallback.
444 template<typename _IIter1, typename _IIter2,
445 typename _OutputIterator>
446 inline _OutputIterator
447 set_intersection(_IIter1 __begin1, _IIter1 __end1,
448 _IIter2 __begin2, _IIter2 __end2,
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,
458 _IIter2 __begin2, _IIter2 __end2,
459 _OutputIterator __out, _Predicate __pred,
461 { return _GLIBCXX_STD_A::set_intersection(
462 __begin1, __end1, __begin2, __end2, __out, __pred); }
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,
471 _IIter2 __begin2, _IIter2 __end2,
472 _OutputIterator __result, _Predicate __pred,
473 _IteratorTag1, _IteratorTag2, _IteratorTag3)
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>
480 _Output_RAIter
481 __set_intersection_switch(_RAIter1 __begin1,
482 _RAIter1 __end1,
483 _RAIter2 __begin2,
484 _RAIter2 __end2,
485 _Output_RAIter __result,
486 _Predicate __pred,
490 {
492 static_cast<__gnu_parallel::_SequenceIndex>(__end1 - __begin1)
493 >= __gnu_parallel::_Settings::get().set_union_minimal_n
494 || static_cast<__gnu_parallel::_SequenceIndex>(__end2 - __begin2)
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,
508 _IIter2 __begin2, _IIter2 __end2,
509 _OutputIterator __out)
510 {
511 typedef typename std::iterator_traits<_IIter1>::value_type _ValueType1;
512 typedef typename std::iterator_traits<_IIter2>::value_type _ValueType2;
513
514 return __set_intersection_switch(
515 __begin1, __end1, __begin2, __end2, __out,
517 std::__iterator_category(__begin1),
518 std::__iterator_category(__begin2),
520 }
521
522 template<typename _IIter1, typename _IIter2,
523 typename _OutputIterator, typename _Predicate>
524 inline _OutputIterator
525 set_intersection(_IIter1 __begin1, _IIter1 __end1,
526 _IIter2 __begin2, _IIter2 __end2,
527 _OutputIterator __out, _Predicate __pred)
528 {
529 return __set_intersection_switch(
530 __begin1, __end1, __begin2, __end2, __out, __pred,
531 std::__iterator_category(__begin1),
532 std::__iterator_category(__begin2),
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,
541 _IIter2 __begin2, _IIter2 __end2,
542 _OutputIterator __out,
544 { return _GLIBCXX_STD_A::set_symmetric_difference(
545 __begin1, __end1, __begin2, __end2, __out); }
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,
552 _IIter2 __begin2, _IIter2 __end2,
553 _OutputIterator __out, _Predicate __pred,
555 { return _GLIBCXX_STD_A::set_symmetric_difference(
556 __begin1, __end1, __begin2, __end2, __out, __pred); }
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(
565 _IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, _IIter2 __end2,
566 _OutputIterator __result, _Predicate __pred,
567 _IteratorTag1, _IteratorTag2, _IteratorTag3)
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>
574 _Output_RAIter
575 __set_symmetric_difference_switch(_RAIter1 __begin1,
576 _RAIter1 __end1,
577 _RAIter2 __begin2,
578 _RAIter2 __end2,
579 _Output_RAIter __result,
580 _Predicate __pred,
584 {
586 static_cast<__gnu_parallel::_SequenceIndex>(__end1 - __begin1)
587 >= __gnu_parallel::_Settings::get().set_symmetric_difference_minimal_n
588 || static_cast<__gnu_parallel::_SequenceIndex>(__end2 - __begin2)
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,
602 _IIter2 __begin2, _IIter2 __end2,
603 _OutputIterator __out)
604 {
605 typedef typename std::iterator_traits<_IIter1>::value_type _ValueType1;
606 typedef typename std::iterator_traits<_IIter2>::value_type _ValueType2;
607
608 return __set_symmetric_difference_switch(
609 __begin1, __end1, __begin2, __end2, __out,
611 std::__iterator_category(__begin1),
612 std::__iterator_category(__begin2),
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,
621 _IIter2 __begin2, _IIter2 __end2,
622 _OutputIterator __out, _Predicate __pred)
623 {
624 return __set_symmetric_difference_switch(
625 __begin1, __end1, __begin2, __end2, __out, __pred,
626 std::__iterator_category(__begin1),
627 std::__iterator_category(__begin2),
629 }
630
631 // Sequential fallback.
632 template<typename _IIter1, typename _IIter2,
633 typename _OutputIterator>
634 inline _OutputIterator
635 set_difference(_IIter1 __begin1, _IIter1 __end1,
636 _IIter2 __begin2, _IIter2 __end2,
637 _OutputIterator __out, __gnu_parallel::sequential_tag)
638 { return _GLIBCXX_STD_A::set_difference(
639 __begin1,__end1, __begin2, __end2, __out); }
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,
646 _IIter2 __begin2, _IIter2 __end2,
647 _OutputIterator __out, _Predicate __pred,
649 { return _GLIBCXX_STD_A::set_difference(__begin1, __end1,
650 __begin2, __end2, __out, __pred); }
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,
658 _IIter2 __begin2, _IIter2 __end2,
659 _OutputIterator __result, _Predicate __pred,
660 _IteratorTag1, _IteratorTag2, _IteratorTag3)
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>
667 _Output_RAIter
668 __set_difference_switch(_RAIter1 __begin1,
669 _RAIter1 __end1,
670 _RAIter2 __begin2,
671 _RAIter2 __end2,
672 _Output_RAIter __result, _Predicate __pred,
676 {
678 static_cast<__gnu_parallel::_SequenceIndex>(__end1 - __begin1)
679 >= __gnu_parallel::_Settings::get().set_difference_minimal_n
680 || static_cast<__gnu_parallel::_SequenceIndex>(__end2 - __begin2)
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,
694 _IIter2 __begin2, _IIter2 __end2,
695 _OutputIterator __out)
696 {
697 typedef typename std::iterator_traits<_IIter1>::value_type _ValueType1;
698 typedef typename std::iterator_traits<_IIter2>::value_type _ValueType2;
699
700 return __set_difference_switch(
701 __begin1, __end1, __begin2, __end2, __out,
703 std::__iterator_category(__begin1),
704 std::__iterator_category(__begin2),
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,
713 _IIter2 __begin2, _IIter2 __end2,
714 _OutputIterator __out, _Predicate __pred)
715 {
716 return __set_difference_switch(
717 __begin1, __end1, __begin2, __end2, __out, __pred,
718 std::__iterator_category(__begin1),
719 std::__iterator_category(__begin2),
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,
734 _BinaryPredicate __binary_pred,
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,
767 _IteratorTag)
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,
784 _BinaryPredicate __pred, _IteratorTag)
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,
792 _BinaryPredicate __pred, random_access_iterator_tag)
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,
807 _BinaryPredicate __pred)
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>
815 inline typename iterator_traits<_IIter>::difference_type
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>
822 typename iterator_traits<_RAIter>::difference_type
823 __count_switch(_RAIter __begin, _RAIter __end,
824 const _Tp& __value, random_access_iterator_tag,
825 __gnu_parallel::_Parallelism __parallelism_tag)
826 {
827 typedef iterator_traits<_RAIter> _TraitsType;
828 typedef typename _TraitsType::value_type _ValueType;
829 typedef typename _TraitsType::difference_type _DifferenceType;
831
833 static_cast<_SequenceIndex>(__end - __begin)
834 >= __gnu_parallel::_Settings::get().count_minimal_n
835 && __gnu_parallel::__is_parallel(__parallelism_tag)))
836 {
838 __functionality;
839 _DifferenceType __res = 0;
842 __begin, __end, __value, __functionality,
843 std::plus<_SequenceIndex>(), __res, __res, -1,
844 __parallelism_tag);
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>
854 inline typename iterator_traits<_IIter>::difference_type
855 __count_switch(_IIter __begin, _IIter __end, const _Tp& __value,
856 _IteratorTag)
857 { return count(__begin, __end, __value, __gnu_parallel::sequential_tag());
858 }
859
860 // Public interface.
861 template<typename _IIter, typename _Tp>
862 inline typename iterator_traits<_IIter>::difference_type
863 count(_IIter __begin, _IIter __end, const _Tp& __value,
864 __gnu_parallel::_Parallelism __parallelism_tag)
865 {
866 return __count_switch(__begin, __end, __value,
868 __parallelism_tag);
869 }
870
871 template<typename _IIter, typename _Tp>
872 inline typename iterator_traits<_IIter>::difference_type
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>
882 inline typename iterator_traits<_IIter>::difference_type
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>
889 typename iterator_traits<_RAIter>::difference_type
890 __count_if_switch(_RAIter __begin, _RAIter __end,
891 _Predicate __pred, random_access_iterator_tag,
892 __gnu_parallel::_Parallelism __parallelism_tag)
893 {
894 typedef iterator_traits<_RAIter> _TraitsType;
895 typedef typename _TraitsType::value_type _ValueType;
896 typedef typename _TraitsType::difference_type _DifferenceType;
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>
907 __functionality;
910 __begin, __end, __pred, __functionality,
911 std::plus<_SequenceIndex>(), __res, __res, -1,
912 __parallelism_tag);
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>
922 inline typename iterator_traits<_IIter>::difference_type
923 __count_if_switch(_IIter __begin, _IIter __end, _Predicate __pred,
924 _IteratorTag)
925 { return count_if(__begin, __end, __pred,
927
928 // Public interface.
929 template<typename _IIter, typename _Predicate>
930 inline typename iterator_traits<_IIter>::difference_type
931 count_if(_IIter __begin, _IIter __end, _Predicate __pred,
932 __gnu_parallel::_Parallelism __parallelism_tag)
933 {
934 return __count_if_switch(__begin, __end, __pred,
936 __parallelism_tag);
937 }
938
939 template<typename _IIter, typename _Predicate>
940 inline typename iterator_traits<_IIter>::difference_type
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
951 search(_FIterator1 __begin1, _FIterator1 __end1,
952 _FIterator2 __begin2, _FIterator2 __end2,
954 { return _GLIBCXX_STD_A::search(__begin1, __end1, __begin2, __end2); }
955
956 // Parallel algorithm for random access iterator
957 template<typename _RAIter1, typename _RAIter2>
958 _RAIter1
959 __search_switch(_RAIter1 __begin1, _RAIter1 __end1,
960 _RAIter2 __begin2, _RAIter2 __end2,
962 {
963 typedef typename std::iterator_traits<_RAIter1>::value_type _ValueType1;
964 typedef typename std::iterator_traits<_RAIter2>::value_type _ValueType2;
965
967 static_cast<__gnu_parallel::_SequenceIndex>(__end1 - __begin1)
968 >= __gnu_parallel::_Settings::get().search_minimal_n))
969 return __gnu_parallel::
971 __begin1, __end1, __begin2, __end2,
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,
983 _FIterator2 __begin2, _FIterator2 __end2,
984 _IteratorTag1, _IteratorTag2)
985 { return search(__begin1, __end1, __begin2, __end2,
987
988 // Public interface.
989 template<typename _FIterator1, typename _FIterator2>
990 inline _FIterator1
991 search(_FIterator1 __begin1, _FIterator1 __end1,
992 _FIterator2 __begin2, _FIterator2 __end2)
993 {
994 return __search_switch(__begin1, __end1, __begin2, __end2,
995 std::__iterator_category(__begin1),
996 std::__iterator_category(__begin2));
997 }
998
999 // Public interface.
1000 template<typename _FIterator1, typename _FIterator2,
1001 typename _BinaryPredicate>
1002 inline _FIterator1
1003 search(_FIterator1 __begin1, _FIterator1 __end1,
1004 _FIterator2 __begin2, _FIterator2 __end2,
1005 _BinaryPredicate __pred, __gnu_parallel::sequential_tag)
1006 { return _GLIBCXX_STD_A::search(
1007 __begin1, __end1, __begin2, __end2, __pred); }
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,
1014 _RAIter2 __begin2, _RAIter2 __end2,
1015 _BinaryPredicate __pred,
1017 {
1019 static_cast<__gnu_parallel::_SequenceIndex>(__end1 - __begin1)
1020 >= __gnu_parallel::_Settings::get().search_minimal_n))
1021 return __gnu_parallel::__search_template(__begin1, __end1,
1022 __begin2, __end2, __pred);
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,
1034 _FIterator2 __begin2, _FIterator2 __end2,
1035 _BinaryPredicate __pred, _IteratorTag1, _IteratorTag2)
1036 { return search(__begin1, __end1, __begin2, __end2, __pred,
1038
1039 // Public interface
1040 template<typename _FIterator1, typename _FIterator2,
1041 typename _BinaryPredicate>
1042 inline _FIterator1
1043 search(_FIterator1 __begin1, _FIterator1 __end1,
1044 _FIterator2 __begin2, _FIterator2 __end2,
1045 _BinaryPredicate __pred)
1046 {
1047 return __search_switch(__begin1, __end1, __begin2, __end2, __pred,
1048 std::__iterator_category(__begin1),
1049 std::__iterator_category(__begin2));
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,
1098 __binary_pred);
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,
1107 _IteratorTag)
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,
1128 _UnaryOperation __unary_op, __gnu_parallel::sequential_tag)
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,
1136 _RAIter2 __result, _UnaryOperation __unary_op,
1138 __gnu_parallel::_Parallelism __parallelism_tag)
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;
1146 typedef __gnu_parallel::_IteratorPair<_RAIter1,
1147 _RAIter2, random_access_iterator_tag> _ItTrip;
1148 _ItTrip __begin_pair(__begin, __result),
1149 __end_pair(__end, __result + (__end - __begin));
1153 __begin_pair, __end_pair, __unary_op, __functionality,
1155 __dummy, __dummy, -1, __parallelism_tag);
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,
1169 _RAIter2 __result, _UnaryOperation __unary_op,
1170 _IteratorTag1, _IteratorTag2)
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,
1179 _UnaryOperation __unary_op,
1180 __gnu_parallel::_Parallelism __parallelism_tag)
1181 {
1182 return __transform1_switch(__begin, __end, __result, __unary_op,
1183 std::__iterator_category(__begin),
1184 std::__iterator_category(__result),
1185 __parallelism_tag);
1186 }
1187
1188 template<typename _IIter, typename _OutputIterator,
1189 typename _UnaryOperation>
1190 inline _OutputIterator
1191 transform(_IIter __begin, _IIter __end, _OutputIterator __result,
1192 _UnaryOperation __unary_op)
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,
1206 _BinaryOperation __binary_op, __gnu_parallel::sequential_tag)
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,
1215 _RAIter2 __begin2,
1216 _RAIter3 __result, _BinaryOperation __binary_op,
1219 __gnu_parallel::_Parallelism __parallelism_tag)
1220 {
1222 (__end1 - __begin1) >=
1223 __gnu_parallel::_Settings::get().transform_minimal_n
1224 && __gnu_parallel::__is_parallel(__parallelism_tag)))
1225 {
1226 bool __dummy = true;
1227 typedef __gnu_parallel::_IteratorTriple<_RAIter1,
1228 _RAIter2, _RAIter3,
1230 _ItTrip __begin_triple(__begin1, __begin2, __result),
1231 __end_triple(__end1, __begin2 + (__end1 - __begin1),
1232 __result + (__end1 - __begin1));
1235 __for_each_template_random_access(__begin_triple, __end_triple,
1236 __binary_op, __functionality,
1238 __dummy, __dummy, -1,
1239 __parallelism_tag);
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,
1254 _BinaryOperation __binary_op, _Tag1, _Tag2, _Tag3)
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,
1264 _BinaryOperation __binary_op,
1265 __gnu_parallel::_Parallelism __parallelism_tag)
1266 {
1267 return __transform2_switch(
1268 __begin1, __end1, __begin2, __result, __binary_op,
1269 std::__iterator_category(__begin1),
1270 std::__iterator_category(__begin2),
1271 std::__iterator_category(__result),
1272 __parallelism_tag);
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,
1280 _BinaryOperation __binary_op)
1281 {
1282 return __transform2_switch(
1283 __begin1, __end1, __begin2, __result, __binary_op,
1284 std::__iterator_category(__begin1),
1285 std::__iterator_category(__begin2),
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,
1293 const _Tp& __new_value, __gnu_parallel::sequential_tag)
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,
1301 _IteratorTag)
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,
1311 __gnu_parallel::_Parallelism __parallelism_tag)
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,
1323 __gnu_parallel::_Parallelism __parallelism_tag)
1324 {
1325 __replace_switch(__begin, __end, __old_value, __new_value,
1326 std::__iterator_category(__begin),
1327 __parallelism_tag);
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,
1344 const _Tp& __new_value, __gnu_parallel::sequential_tag)
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,
1362 __gnu_parallel::_Parallelism __parallelism_tag)
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>
1372 __functionality(__new_value);
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,
1389 __gnu_parallel::_Parallelism __parallelism_tag)
1390 {
1391 __replace_if_switch(__begin, __end, __pred, __new_value,
1392 std::__iterator_category(__begin),
1393 __parallelism_tag);
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,
1416 _IteratorTag)
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,
1423 _Generator __gen, random_access_iterator_tag,
1424 __gnu_parallel::_Parallelism __parallelism_tag)
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;
1433 __functionality;
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,
1448 _Generator __gen, __gnu_parallel::_Parallelism __parallelism_tag)
1449 {
1450 __generate_switch(__begin, __end, __gen,
1451 std::__iterator_category(__begin),
1452 __parallelism_tag);
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,
1476 _IteratorTag)
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,
1485 __gnu_parallel::_Parallelism __parallelism_tag)
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,
1495 __gnu_parallel::_Parallelism __parallelism_tag)
1496 {
1497 return __generate_n_switch(__begin, __n, __gen,
1498 std::__iterator_category(__begin),
1499 __parallelism_tag);
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,
1522 _RandomNumberGenerator& __rand,
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
1551 _RandomNumberGenerator&& __rand)
1552#else
1553 _RandomNumberGenerator& __rand)
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))
1561 __gnu_parallel::__parallel_random_shuffle(__begin, __end, __rand);
1562 else
1563 __gnu_parallel::__sequential_random_shuffle(__begin, __end, __rand);
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} // end namespace
2193} // end namespace
2194
2195#endif /* _GLIBCXX_PARALLEL_ALGO_H */
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...
Main interface for embarrassingly parallel functions.
Functors representing different tasks to be plugged into the generic parallelization methods for emba...
Parallel implementation of std::partition(), std::nth_element(), and std::partial_sort()....
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 with static sched...
#define _GLIBCXX_PARALLEL_CONDITION(__c)
Determine at compile(?)-time if the parallel variant of an algorithm should be called.
Definition: settings.h:95
Parallelization of embarrassingly parallel execution by means of work-stealing.
Helper iterator classes for the std::transform() functions. This file is a GNU parallel extension to ...
Parallelization of embarrassingly parallel execution by means of an OpenMP for loop....
Parallel implementation base for std::find(), std::equal() and related functions. This file is a GNU ...
Parallel implementation of std::random_shuffle(). This file is a GNU parallel extension to the Standa...
Parallel implementations of set operations for random-access iterators. This file is a GNU parallel e...
Parallel sorting algorithm switch. This file is a GNU parallel extension to the Standard C++ Library.
_Function objects representing different tasks to be plugged into the parallel find algorithm....
Parallelization of embarrassingly parallel execution by means of equal splitting. This file is a GNU ...
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
One of the math functors.
Definition: stl_function.h:168
One of the comparison functors.
Definition: stl_function.h:352
One of the comparison functors.
Definition: stl_function.h:382
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.
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...
iterator begin() const
Begin iterator.
iterator end() const
End iterator.
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.
_It _M_finish_iterator
_Iterator on last element processed; needed for some algorithms (e. g. std::transform()).
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.