3 // Copyright (C) 2007-2024 Free Software Foundation, Inc.
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
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.
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.
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/>.
25 /** @file parallel/algo.h
26 * @brief Parallel STL function calls corresponding to the stl_algo.h header.
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.
35 // Written by Johannes Singler and Felix Putze.
37 #ifndef _GLIBCXX_PARALLEL_ALGO_H
38 #define _GLIBCXX_PARALLEL_ALGO_H 1
40 #include <parallel/algorithmfwd.h>
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>
46 #include <parallel/workstealing.h>
47 #include <parallel/par_loop.h>
48 #include <parallel/omp_loop.h>
49 #include <parallel/omp_loop_static.h>
50 #include <parallel/for_each_selectors.h>
51 #include <parallel/for_each.h>
52 #include <parallel/find.h>
53 #include <parallel/find_selectors.h>
54 #include <parallel/search.h>
55 #include <parallel/random_shuffle.h>
56 #include <parallel/partition.h>
57 #include <parallel/merge.h>
58 #include <parallel/unique_copy.h>
59 #include <parallel/set_operations.h>
61 namespace std
_GLIBCXX_VISIBILITY(default)
65 // Sequential fallback
66 template<typename _IIter
, typename _Function
>
68 for_each(_IIter __begin
, _IIter __end
, _Function __f
,
69 __gnu_parallel::sequential_tag
)
70 { return _GLIBCXX_STD_A::for_each(__begin
, __end
, __f
); }
72 // Sequential fallback for input iterator case
73 template<typename _IIter
, typename _Function
, typename _IteratorTag
>
75 __for_each_switch(_IIter __begin
, _IIter __end
, _Function __f
,
77 { return for_each(__begin
, __end
, __f
, __gnu_parallel::sequential_tag()); }
79 // Parallel algorithm for random access iterators
80 template<typename _RAIter
, typename _Function
>
82 __for_each_switch(_RAIter __begin
, _RAIter __end
,
83 _Function __f
, random_access_iterator_tag
,
84 __gnu_parallel::_Parallelism __parallelism_tag
)
86 if (_GLIBCXX_PARALLEL_CONDITION(
87 static_cast<__gnu_parallel::_SequenceIndex
>(__end
- __begin
)
88 >= __gnu_parallel::_Settings::get().for_each_minimal_n
89 && __gnu_parallel::__is_parallel(__parallelism_tag
)))
92 __gnu_parallel::__for_each_selector
<_RAIter
> __functionality
;
94 return __gnu_parallel::
95 __for_each_template_random_access(
96 __begin
, __end
, __f
, __functionality
,
97 __gnu_parallel::_DummyReduct(), true, __dummy
, -1,
101 return for_each(__begin
, __end
, __f
, __gnu_parallel::sequential_tag());
105 template<typename _Iterator
, typename _Function
>
107 for_each(_Iterator __begin
, _Iterator __end
, _Function __f
,
108 __gnu_parallel::_Parallelism __parallelism_tag
)
110 return __for_each_switch(__begin
, __end
, __f
,
111 std::__iterator_category(__begin
),
115 template<typename _Iterator
, typename _Function
>
117 for_each(_Iterator __begin
, _Iterator __end
, _Function __f
)
119 return __for_each_switch(__begin
, __end
, __f
,
120 std::__iterator_category(__begin
));
123 // Sequential fallback
124 template<typename _IIter
, typename _Tp
>
126 find(_IIter __begin
, _IIter __end
, const _Tp
& __val
,
127 __gnu_parallel::sequential_tag
)
128 { return _GLIBCXX_STD_A::find(__begin
, __end
, __val
); }
130 // Sequential fallback for input iterator case
131 template<typename _IIter
, typename _Tp
, typename _IteratorTag
>
133 __find_switch(_IIter __begin
, _IIter __end
, const _Tp
& __val
,
135 { return _GLIBCXX_STD_A::find(__begin
, __end
, __val
); }
137 // Parallel find for random access iterators
138 template<typename _RAIter
, typename _Tp
>
140 __find_switch(_RAIter __begin
, _RAIter __end
,
141 const _Tp
& __val
, random_access_iterator_tag
)
143 typedef iterator_traits
<_RAIter
> _TraitsType
;
144 typedef typename
_TraitsType::value_type _ValueType
;
146 if (_GLIBCXX_PARALLEL_CONDITION(true))
148 __gnu_parallel::__binder2nd
<__gnu_parallel::_EqualTo
<_ValueType
,
150 _ValueType
, const _Tp
&, bool>
151 __comp(__gnu_parallel::_EqualTo
<_ValueType
, const _Tp
&>(), __val
);
152 return __gnu_parallel::__find_template(
153 __begin
, __end
, __begin
, __comp
,
154 __gnu_parallel::__find_if_selector()).first
;
157 return _GLIBCXX_STD_A::find(__begin
, __end
, __val
);
161 template<typename _IIter
, typename _Tp
>
163 find(_IIter __begin
, _IIter __end
, const _Tp
& __val
)
165 return __find_switch(__begin
, __end
, __val
,
166 std::__iterator_category(__begin
));
169 // Sequential fallback
170 template<typename _IIter
, typename _Predicate
>
172 find_if(_IIter __begin
, _IIter __end
, _Predicate __pred
,
173 __gnu_parallel::sequential_tag
)
174 { return _GLIBCXX_STD_A::find_if(__begin
, __end
, __pred
); }
176 // Sequential fallback for input iterator case
177 template<typename _IIter
, typename _Predicate
, typename _IteratorTag
>
179 __find_if_switch(_IIter __begin
, _IIter __end
, _Predicate __pred
,
181 { return _GLIBCXX_STD_A::find_if(__begin
, __end
, __pred
); }
183 // Parallel find_if for random access iterators
184 template<typename _RAIter
, typename _Predicate
>
186 __find_if_switch(_RAIter __begin
, _RAIter __end
,
187 _Predicate __pred
, random_access_iterator_tag
)
189 if (_GLIBCXX_PARALLEL_CONDITION(true))
190 return __gnu_parallel::__find_template(__begin
, __end
, __begin
, __pred
,
192 __find_if_selector()).first
;
194 return _GLIBCXX_STD_A::find_if(__begin
, __end
, __pred
);
198 template<typename _IIter
, typename _Predicate
>
200 find_if(_IIter __begin
, _IIter __end
, _Predicate __pred
)
202 return __find_if_switch(__begin
, __end
, __pred
,
203 std::__iterator_category(__begin
));
206 // Sequential fallback
207 template<typename _IIter
, typename _FIterator
>
209 find_first_of(_IIter __begin1
, _IIter __end1
,
210 _FIterator __begin2
, _FIterator __end2
,
211 __gnu_parallel::sequential_tag
)
213 return _GLIBCXX_STD_A::find_first_of(__begin1
, __end1
, __begin2
, __end2
);
216 // Sequential fallback
217 template<typename _IIter
, typename _FIterator
,
218 typename _BinaryPredicate
>
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
); }
226 // Sequential fallback for input iterator type
227 template<typename _IIter
, typename _FIterator
,
228 typename _IteratorTag1
, typename _IteratorTag2
>
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
,
234 __gnu_parallel::sequential_tag()); }
236 // Parallel algorithm for random access iterators
237 template<typename _RAIter
, typename _FIterator
,
238 typename _BinaryPredicate
, typename _IteratorTag
>
240 __find_first_of_switch(_RAIter __begin1
,
242 _FIterator __begin2
, _FIterator __end2
,
243 _BinaryPredicate __comp
, random_access_iterator_tag
,
246 return __gnu_parallel::
247 __find_template(__begin1
, __end1
, __begin1
, __comp
,
248 __gnu_parallel::__find_first_of_selector
249 <_FIterator
>(__begin2
, __end2
)).first
;
252 // Sequential fallback for input iterator type
253 template<typename _IIter
, typename _FIterator
,
254 typename _BinaryPredicate
, typename _IteratorTag1
,
255 typename _IteratorTag2
>
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
,
261 __gnu_parallel::sequential_tag()); }
264 template<typename _IIter
, typename _FIterator
,
265 typename _BinaryPredicate
>
267 find_first_of(_IIter __begin1
, _IIter __end1
,
268 _FIterator __begin2
, _FIterator __end2
,
269 _BinaryPredicate __comp
)
271 return __find_first_of_switch(__begin1
, __end1
, __begin2
, __end2
, __comp
,
272 std::__iterator_category(__begin1
),
273 std::__iterator_category(__begin2
));
276 // Public interface, insert default comparator
277 template<typename _IIter
, typename _FIterator
>
279 find_first_of(_IIter __begin1
, _IIter __end1
,
280 _FIterator __begin2
, _FIterator __end2
)
282 typedef typename
std::iterator_traits
<_IIter
>::value_type _IValueType
;
283 typedef typename
std::iterator_traits
<_FIterator
>::value_type _FValueType
;
285 return __gnu_parallel::find_first_of(__begin1
, __end1
, __begin2
, __end2
,
286 __gnu_parallel::_EqualTo
<_IValueType
, _FValueType
>());
289 // Sequential fallback
290 template<typename _IIter
, typename _OutputIterator
>
291 inline _OutputIterator
292 unique_copy(_IIter __begin1
, _IIter __end1
, _OutputIterator __out
,
293 __gnu_parallel::sequential_tag
)
294 { return _GLIBCXX_STD_A::unique_copy(__begin1
, __end1
, __out
); }
296 // Sequential fallback
297 template<typename _IIter
, typename _OutputIterator
,
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
); }
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
); }
313 // Parallel unique_copy for random access iterators
314 template<typename _RAIter
, typename _RandomAccessOutputIterator
,
316 _RandomAccessOutputIterator
317 __unique_copy_switch(_RAIter __begin
, _RAIter __last
,
318 _RandomAccessOutputIterator __out
, _Predicate __pred
,
319 random_access_iterator_tag
, random_access_iterator_tag
)
321 if (_GLIBCXX_PARALLEL_CONDITION(
322 static_cast<__gnu_parallel::_SequenceIndex
>(__last
- __begin
)
323 > __gnu_parallel::_Settings::get().unique_copy_minimal_n
))
324 return __gnu_parallel::__parallel_unique_copy(
325 __begin
, __last
, __out
, __pred
);
327 return _GLIBCXX_STD_A::unique_copy(__begin
, __last
, __out
, __pred
);
331 template<typename _IIter
, typename _OutputIterator
>
332 inline _OutputIterator
333 unique_copy(_IIter __begin1
, _IIter __end1
, _OutputIterator __out
)
335 typedef typename
std::iterator_traits
<_IIter
>::value_type _ValueType
;
337 return __unique_copy_switch(
338 __begin1
, __end1
, __out
, equal_to
<_ValueType
>(),
339 std::__iterator_category(__begin1
),
340 std::__iterator_category(__out
));
344 template<typename _IIter
, typename _OutputIterator
, typename _Predicate
>
345 inline _OutputIterator
346 unique_copy(_IIter __begin1
, _IIter __end1
, _OutputIterator __out
,
349 return __unique_copy_switch(
350 __begin1
, __end1
, __out
, __pred
,
351 std::__iterator_category(__begin1
),
352 std::__iterator_category(__out
));
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
); }
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
,
372 __gnu_parallel::sequential_tag
)
373 { return _GLIBCXX_STD_A::set_union(__begin1
, __end1
,
374 __begin2
, __end2
, __out
, __pred
); }
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
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
); }
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
,
393 _RAIter2 __begin2
, _RAIter2 __end2
,
394 _Output_RAIter __result
, _Predicate __pred
,
395 random_access_iterator_tag
, random_access_iterator_tag
,
396 random_access_iterator_tag
)
398 if (_GLIBCXX_PARALLEL_CONDITION(
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
);
406 return _GLIBCXX_STD_A::set_union(__begin1
, __end1
,
407 __begin2
, __end2
, __result
, __pred
);
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
)
417 typedef typename
std::iterator_traits
<_IIter1
>::value_type _ValueType1
;
418 typedef typename
std::iterator_traits
<_IIter2
>::value_type _ValueType2
;
420 return __set_union_switch(
421 __begin1
, __end1
, __begin2
, __end2
, __out
,
422 __gnu_parallel::_Less
<_ValueType1
, _ValueType2
>(),
423 std::__iterator_category(__begin1
),
424 std::__iterator_category(__begin2
),
425 std::__iterator_category(__out
));
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
)
436 return __set_union_switch(
437 __begin1
, __end1
, __begin2
, __end2
, __out
, __pred
,
438 std::__iterator_category(__begin1
),
439 std::__iterator_category(__begin2
),
440 std::__iterator_category(__out
));
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
); }
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
,
460 __gnu_parallel::sequential_tag
)
461 { return _GLIBCXX_STD_A::set_intersection(
462 __begin1
, __end1
, __begin2
, __end2
, __out
, __pred
); }
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
); }
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
,
487 random_access_iterator_tag
,
488 random_access_iterator_tag
,
489 random_access_iterator_tag
)
491 if (_GLIBCXX_PARALLEL_CONDITION(
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
);
499 return _GLIBCXX_STD_A::set_intersection(
500 __begin1
, __end1
, __begin2
, __end2
, __result
, __pred
);
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
)
511 typedef typename
std::iterator_traits
<_IIter1
>::value_type _ValueType1
;
512 typedef typename
std::iterator_traits
<_IIter2
>::value_type _ValueType2
;
514 return __set_intersection_switch(
515 __begin1
, __end1
, __begin2
, __end2
, __out
,
516 __gnu_parallel::_Less
<_ValueType1
, _ValueType2
>(),
517 std::__iterator_category(__begin1
),
518 std::__iterator_category(__begin2
),
519 std::__iterator_category(__out
));
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
)
529 return __set_intersection_switch(
530 __begin1
, __end1
, __begin2
, __end2
, __out
, __pred
,
531 std::__iterator_category(__begin1
),
532 std::__iterator_category(__begin2
),
533 std::__iterator_category(__out
));
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
,
543 __gnu_parallel::sequential_tag
)
544 { return _GLIBCXX_STD_A::set_symmetric_difference(
545 __begin1
, __end1
, __begin2
, __end2
, __out
); }
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
,
554 __gnu_parallel::sequential_tag
)
555 { return _GLIBCXX_STD_A::set_symmetric_difference(
556 __begin1
, __end1
, __begin2
, __end2
, __out
, __pred
); }
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
); }
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
,
581 random_access_iterator_tag
,
582 random_access_iterator_tag
,
583 random_access_iterator_tag
)
585 if (_GLIBCXX_PARALLEL_CONDITION(
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
);
593 return _GLIBCXX_STD_A::set_symmetric_difference(
594 __begin1
, __end1
, __begin2
, __end2
, __result
, __pred
);
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
)
605 typedef typename
std::iterator_traits
<_IIter1
>::value_type _ValueType1
;
606 typedef typename
std::iterator_traits
<_IIter2
>::value_type _ValueType2
;
608 return __set_symmetric_difference_switch(
609 __begin1
, __end1
, __begin2
, __end2
, __out
,
610 __gnu_parallel::_Less
<_ValueType1
, _ValueType2
>(),
611 std::__iterator_category(__begin1
),
612 std::__iterator_category(__begin2
),
613 std::__iterator_category(__out
));
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
)
624 return __set_symmetric_difference_switch(
625 __begin1
, __end1
, __begin2
, __end2
, __out
, __pred
,
626 std::__iterator_category(__begin1
),
627 std::__iterator_category(__begin2
),
628 std::__iterator_category(__out
));
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
); }
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
,
648 __gnu_parallel::sequential_tag
)
649 { return _GLIBCXX_STD_A::set_difference(__begin1
, __end1
,
650 __begin2
, __end2
, __out
, __pred
); }
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
); }
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
,
673 random_access_iterator_tag
,
674 random_access_iterator_tag
,
675 random_access_iterator_tag
)
677 if (_GLIBCXX_PARALLEL_CONDITION(
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
);
685 return _GLIBCXX_STD_A::set_difference(
686 __begin1
, __end1
, __begin2
, __end2
, __result
, __pred
);
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
)
697 typedef typename
std::iterator_traits
<_IIter1
>::value_type _ValueType1
;
698 typedef typename
std::iterator_traits
<_IIter2
>::value_type _ValueType2
;
700 return __set_difference_switch(
701 __begin1
, __end1
, __begin2
, __end2
, __out
,
702 __gnu_parallel::_Less
<_ValueType1
, _ValueType2
>(),
703 std::__iterator_category(__begin1
),
704 std::__iterator_category(__begin2
),
705 std::__iterator_category(__out
));
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
)
716 return __set_difference_switch(
717 __begin1
, __end1
, __begin2
, __end2
, __out
, __pred
,
718 std::__iterator_category(__begin1
),
719 std::__iterator_category(__begin2
),
720 std::__iterator_category(__out
));
723 // Sequential fallback
724 template<typename _FIterator
>
726 adjacent_find(_FIterator __begin
, _FIterator __end
,
727 __gnu_parallel::sequential_tag
)
728 { return _GLIBCXX_STD_A::adjacent_find(__begin
, __end
); }
730 // Sequential fallback
731 template<typename _FIterator
, typename _BinaryPredicate
>
733 adjacent_find(_FIterator __begin
, _FIterator __end
,
734 _BinaryPredicate __binary_pred
,
735 __gnu_parallel::sequential_tag
)
736 { return _GLIBCXX_STD_A::adjacent_find(__begin
, __end
, __binary_pred
); }
738 // Parallel algorithm for random access iterators
739 template<typename _RAIter
>
741 __adjacent_find_switch(_RAIter __begin
, _RAIter __end
,
742 random_access_iterator_tag
)
744 typedef iterator_traits
<_RAIter
> _TraitsType
;
745 typedef typename
_TraitsType::value_type _ValueType
;
747 if (_GLIBCXX_PARALLEL_CONDITION(true))
749 _RAIter __spot
= __gnu_parallel::
751 __begin
, __end
- 1, __begin
, equal_to
<_ValueType
>(),
752 __gnu_parallel::__adjacent_find_selector())
754 if (__spot
== (__end
- 1))
760 return adjacent_find(__begin
, __end
, __gnu_parallel::sequential_tag());
763 // Sequential fallback for input iterator case
764 template<typename _FIterator
, typename _IteratorTag
>
766 __adjacent_find_switch(_FIterator __begin
, _FIterator __end
,
768 { return adjacent_find(__begin
, __end
, __gnu_parallel::sequential_tag()); }
771 template<typename _FIterator
>
773 adjacent_find(_FIterator __begin
, _FIterator __end
)
775 return __adjacent_find_switch(__begin
, __end
,
776 std::__iterator_category(__begin
));
779 // Sequential fallback for input iterator case
780 template<typename _FIterator
, typename _BinaryPredicate
,
781 typename _IteratorTag
>
783 __adjacent_find_switch(_FIterator __begin
, _FIterator __end
,
784 _BinaryPredicate __pred
, _IteratorTag
)
785 { return adjacent_find(__begin
, __end
, __pred
,
786 __gnu_parallel::sequential_tag()); }
788 // Parallel algorithm for random access iterators
789 template<typename _RAIter
, typename _BinaryPredicate
>
791 __adjacent_find_switch(_RAIter __begin
, _RAIter __end
,
792 _BinaryPredicate __pred
, random_access_iterator_tag
)
794 if (_GLIBCXX_PARALLEL_CONDITION(true))
795 return __gnu_parallel::__find_template(__begin
, __end
, __begin
, __pred
,
797 __adjacent_find_selector()).first
;
799 return adjacent_find(__begin
, __end
, __pred
,
800 __gnu_parallel::sequential_tag());
804 template<typename _FIterator
, typename _BinaryPredicate
>
806 adjacent_find(_FIterator __begin
, _FIterator __end
,
807 _BinaryPredicate __pred
)
809 return __adjacent_find_switch(__begin
, __end
, __pred
,
810 std::__iterator_category(__begin
));
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
,
817 __gnu_parallel::sequential_tag
)
818 { return _GLIBCXX_STD_A::count(__begin
, __end
, __value
); }
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
)
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
;
832 if (_GLIBCXX_PARALLEL_CONDITION(
833 static_cast<_SequenceIndex
>(__end
- __begin
)
834 >= __gnu_parallel::_Settings::get().count_minimal_n
835 && __gnu_parallel::__is_parallel(__parallelism_tag
)))
837 __gnu_parallel::__count_selector
<_RAIter
, _DifferenceType
>
839 _DifferenceType __res
= 0;
841 __for_each_template_random_access(
842 __begin
, __end
, __value
, __functionality
,
843 std::plus
<_SequenceIndex
>(), __res
, __res
, -1,
848 return count(__begin
, __end
, __value
,
849 __gnu_parallel::sequential_tag());
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
,
857 { return count(__begin
, __end
, __value
, __gnu_parallel::sequential_tag());
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
)
866 return __count_switch(__begin
, __end
, __value
,
867 std::__iterator_category(__begin
),
871 template<typename _IIter
, typename _Tp
>
872 inline typename iterator_traits
<_IIter
>::difference_type
873 count(_IIter __begin
, _IIter __end
, const _Tp
& __value
)
875 return __count_switch(__begin
, __end
, __value
,
876 std::__iterator_category(__begin
));
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
,
884 __gnu_parallel::sequential_tag
)
885 { return _GLIBCXX_STD_A::count_if(__begin
, __end
, __pred
); }
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
)
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
;
899 if (_GLIBCXX_PARALLEL_CONDITION(
900 static_cast<_SequenceIndex
>(__end
- __begin
)
901 >= __gnu_parallel::_Settings::get().count_minimal_n
902 && __gnu_parallel::__is_parallel(__parallelism_tag
)))
904 _DifferenceType __res
= 0;
906 __count_if_selector
<_RAIter
, _DifferenceType
>
909 __for_each_template_random_access(
910 __begin
, __end
, __pred
, __functionality
,
911 std::plus
<_SequenceIndex
>(), __res
, __res
, -1,
916 return count_if(__begin
, __end
, __pred
,
917 __gnu_parallel::sequential_tag());
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
,
925 { return count_if(__begin
, __end
, __pred
,
926 __gnu_parallel::sequential_tag()); }
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
)
934 return __count_if_switch(__begin
, __end
, __pred
,
935 std::__iterator_category(__begin
),
939 template<typename _IIter
, typename _Predicate
>
940 inline typename iterator_traits
<_IIter
>::difference_type
941 count_if(_IIter __begin
, _IIter __end
, _Predicate __pred
)
943 return __count_if_switch(__begin
, __end
, __pred
,
944 std::__iterator_category(__begin
));
948 // Sequential fallback.
949 template<typename _FIterator1
, typename _FIterator2
>
951 search(_FIterator1 __begin1
, _FIterator1 __end1
,
952 _FIterator2 __begin2
, _FIterator2 __end2
,
953 __gnu_parallel::sequential_tag
)
954 { return _GLIBCXX_STD_A::search(__begin1
, __end1
, __begin2
, __end2
); }
956 // Parallel algorithm for random access iterator
957 template<typename _RAIter1
, typename _RAIter2
>
959 __search_switch(_RAIter1 __begin1
, _RAIter1 __end1
,
960 _RAIter2 __begin2
, _RAIter2 __end2
,
961 random_access_iterator_tag
, random_access_iterator_tag
)
963 typedef typename
std::iterator_traits
<_RAIter1
>::value_type _ValueType1
;
964 typedef typename
std::iterator_traits
<_RAIter2
>::value_type _ValueType2
;
966 if (_GLIBCXX_PARALLEL_CONDITION(
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
,
972 __gnu_parallel::_EqualTo
<_ValueType1
, _ValueType2
>());
974 return search(__begin1
, __end1
, __begin2
, __end2
,
975 __gnu_parallel::sequential_tag());
978 // Sequential fallback for input iterator case
979 template<typename _FIterator1
, typename _FIterator2
,
980 typename _IteratorTag1
, typename _IteratorTag2
>
982 __search_switch(_FIterator1 __begin1
, _FIterator1 __end1
,
983 _FIterator2 __begin2
, _FIterator2 __end2
,
984 _IteratorTag1
, _IteratorTag2
)
985 { return search(__begin1
, __end1
, __begin2
, __end2
,
986 __gnu_parallel::sequential_tag()); }
989 template<typename _FIterator1
, typename _FIterator2
>
991 search(_FIterator1 __begin1
, _FIterator1 __end1
,
992 _FIterator2 __begin2
, _FIterator2 __end2
)
994 return __search_switch(__begin1
, __end1
, __begin2
, __end2
,
995 std::__iterator_category(__begin1
),
996 std::__iterator_category(__begin2
));
999 #if __cplusplus >= 201703L
1000 /** @brief Search a sequence using a Searcher object.
1002 * @param __first A forward iterator.
1003 * @param __last A forward iterator.
1004 * @param __searcher A callable object.
1005 * @return @p __searcher(__first,__last).first
1007 template<typename _ForwardIterator
, typename _Searcher
>
1008 inline _ForwardIterator
1009 search(_ForwardIterator __first
, _ForwardIterator __last
,
1010 const _Searcher
& __searcher
)
1011 { return __searcher(__first
, __last
).first
; }
1014 // Sequential fallback
1015 template<typename _FIterator
, typename _Integer
, typename _Tp
>
1017 search_n(_FIterator __begin
, _FIterator __end
, _Integer __count
,
1018 const _Tp
& __val
, __gnu_parallel::sequential_tag
)
1019 { return _GLIBCXX_STD_A::search_n(__begin
, __end
, __count
, __val
); }
1021 // Sequential fallback
1022 template<typename _FIterator
, typename _Integer
, typename _Tp
,
1023 typename _BinaryPredicate
>
1025 search_n(_FIterator __begin
, _FIterator __end
, _Integer __count
,
1026 const _Tp
& __val
, _BinaryPredicate __binary_pred
,
1027 __gnu_parallel::sequential_tag
)
1028 { return _GLIBCXX_STD_A::search_n(
1029 __begin
, __end
, __count
, __val
, __binary_pred
); }
1031 // Public interface.
1032 template<typename _FIterator
, typename _Integer
, typename _Tp
>
1034 search_n(_FIterator __begin
, _FIterator __end
, _Integer __count
,
1037 typedef typename iterator_traits
<_FIterator
>::value_type _ValueType
;
1038 return __gnu_parallel::search_n(__begin
, __end
, __count
, __val
,
1039 __gnu_parallel::_EqualTo
<_ValueType
, _Tp
>());
1042 // Parallel algorithm for random access iterators.
1043 template<typename _RAIter
, typename _Integer
,
1044 typename _Tp
, typename _BinaryPredicate
>
1046 __search_n_switch(_RAIter __begin
, _RAIter __end
, _Integer __count
,
1047 const _Tp
& __val
, _BinaryPredicate __binary_pred
,
1048 random_access_iterator_tag
)
1050 if (_GLIBCXX_PARALLEL_CONDITION(
1051 static_cast<__gnu_parallel::_SequenceIndex
>(__end
- __begin
)
1052 >= __gnu_parallel::_Settings::get().search_minimal_n
))
1054 __gnu_parallel::_PseudoSequence
<_Tp
, _Integer
> __ps(__val
, __count
);
1055 return __gnu_parallel::__search_template(
1056 __begin
, __end
, __ps
.begin(), __ps
.end(), __binary_pred
);
1059 return _GLIBCXX_STD_A::search_n(__begin
, __end
, __count
, __val
,
1063 // Sequential fallback for input iterator case.
1064 template<typename _FIterator
, typename _Integer
, typename _Tp
,
1065 typename _BinaryPredicate
, typename _IteratorTag
>
1067 __search_n_switch(_FIterator __begin
, _FIterator __end
, _Integer __count
,
1068 const _Tp
& __val
, _BinaryPredicate __binary_pred
,
1070 { return _GLIBCXX_STD_A::search_n(__begin
, __end
, __count
, __val
,
1073 // Public interface.
1074 template<typename _FIterator
, typename _Integer
, typename _Tp
,
1075 typename _BinaryPredicate
>
1077 search_n(_FIterator __begin
, _FIterator __end
, _Integer __count
,
1078 const _Tp
& __val
, _BinaryPredicate __binary_pred
)
1080 return __search_n_switch(__begin
, __end
, __count
, __val
, __binary_pred
,
1081 std::__iterator_category(__begin
));
1085 // Sequential fallback.
1086 template<typename _IIter
, typename _OutputIterator
,
1087 typename _UnaryOperation
>
1088 inline _OutputIterator
1089 transform(_IIter __begin
, _IIter __end
, _OutputIterator __result
,
1090 _UnaryOperation __unary_op
, __gnu_parallel::sequential_tag
)
1091 { return _GLIBCXX_STD_A::transform(__begin
, __end
, __result
, __unary_op
); }
1093 // Parallel unary transform for random access iterators.
1094 template<typename _RAIter1
, typename _RAIter2
,
1095 typename _UnaryOperation
>
1097 __transform1_switch(_RAIter1 __begin
, _RAIter1 __end
,
1098 _RAIter2 __result
, _UnaryOperation __unary_op
,
1099 random_access_iterator_tag
, random_access_iterator_tag
,
1100 __gnu_parallel::_Parallelism __parallelism_tag
)
1102 if (_GLIBCXX_PARALLEL_CONDITION(
1103 static_cast<__gnu_parallel::_SequenceIndex
>(__end
- __begin
)
1104 >= __gnu_parallel::_Settings::get().transform_minimal_n
1105 && __gnu_parallel::__is_parallel(__parallelism_tag
)))
1107 bool __dummy
= true;
1108 typedef __gnu_parallel::_IteratorPair
<_RAIter1
,
1109 _RAIter2
, random_access_iterator_tag
> _ItTrip
;
1110 _ItTrip
__begin_pair(__begin
, __result
),
1111 __end_pair(__end
, __result
+ (__end
- __begin
));
1112 __gnu_parallel::__transform1_selector
<_ItTrip
> __functionality
;
1114 __for_each_template_random_access(
1115 __begin_pair
, __end_pair
, __unary_op
, __functionality
,
1116 __gnu_parallel::_DummyReduct(),
1117 __dummy
, __dummy
, -1, __parallelism_tag
);
1118 return __functionality
._M_finish_iterator
;
1121 return transform(__begin
, __end
, __result
, __unary_op
,
1122 __gnu_parallel::sequential_tag());
1125 // Sequential fallback for input iterator case.
1126 template<typename _RAIter1
, typename _RAIter2
,
1127 typename _UnaryOperation
, typename _IteratorTag1
,
1128 typename _IteratorTag2
>
1130 __transform1_switch(_RAIter1 __begin
, _RAIter1 __end
,
1131 _RAIter2 __result
, _UnaryOperation __unary_op
,
1132 _IteratorTag1
, _IteratorTag2
)
1133 { return transform(__begin
, __end
, __result
, __unary_op
,
1134 __gnu_parallel::sequential_tag()); }
1136 // Public interface.
1137 template<typename _IIter
, typename _OutputIterator
,
1138 typename _UnaryOperation
>
1139 inline _OutputIterator
1140 transform(_IIter __begin
, _IIter __end
, _OutputIterator __result
,
1141 _UnaryOperation __unary_op
,
1142 __gnu_parallel::_Parallelism __parallelism_tag
)
1144 return __transform1_switch(__begin
, __end
, __result
, __unary_op
,
1145 std::__iterator_category(__begin
),
1146 std::__iterator_category(__result
),
1150 template<typename _IIter
, typename _OutputIterator
,
1151 typename _UnaryOperation
>
1152 inline _OutputIterator
1153 transform(_IIter __begin
, _IIter __end
, _OutputIterator __result
,
1154 _UnaryOperation __unary_op
)
1156 return __transform1_switch(__begin
, __end
, __result
, __unary_op
,
1157 std::__iterator_category(__begin
),
1158 std::__iterator_category(__result
));
1162 // Sequential fallback
1163 template<typename _IIter1
, typename _IIter2
,
1164 typename _OutputIterator
, typename _BinaryOperation
>
1165 inline _OutputIterator
1166 transform(_IIter1 __begin1
, _IIter1 __end1
,
1167 _IIter2 __begin2
, _OutputIterator __result
,
1168 _BinaryOperation __binary_op
, __gnu_parallel::sequential_tag
)
1169 { return _GLIBCXX_STD_A::transform(__begin1
, __end1
,
1170 __begin2
, __result
, __binary_op
); }
1172 // Parallel binary transform for random access iterators.
1173 template<typename _RAIter1
, typename _RAIter2
,
1174 typename _RAIter3
, typename _BinaryOperation
>
1176 __transform2_switch(_RAIter1 __begin1
, _RAIter1 __end1
,
1178 _RAIter3 __result
, _BinaryOperation __binary_op
,
1179 random_access_iterator_tag
, random_access_iterator_tag
,
1180 random_access_iterator_tag
,
1181 __gnu_parallel::_Parallelism __parallelism_tag
)
1183 if (_GLIBCXX_PARALLEL_CONDITION(
1184 (__end1
- __begin1
) >=
1185 __gnu_parallel::_Settings::get().transform_minimal_n
1186 && __gnu_parallel::__is_parallel(__parallelism_tag
)))
1188 bool __dummy
= true;
1189 typedef __gnu_parallel::_IteratorTriple
<_RAIter1
,
1191 random_access_iterator_tag
> _ItTrip
;
1192 _ItTrip
__begin_triple(__begin1
, __begin2
, __result
),
1193 __end_triple(__end1
, __begin2
+ (__end1
- __begin1
),
1194 __result
+ (__end1
- __begin1
));
1195 __gnu_parallel::__transform2_selector
<_ItTrip
> __functionality
;
1197 __for_each_template_random_access(__begin_triple
, __end_triple
,
1198 __binary_op
, __functionality
,
1199 __gnu_parallel::_DummyReduct(),
1200 __dummy
, __dummy
, -1,
1202 return __functionality
._M_finish_iterator
;
1205 return transform(__begin1
, __end1
, __begin2
, __result
, __binary_op
,
1206 __gnu_parallel::sequential_tag());
1209 // Sequential fallback for input iterator case.
1210 template<typename _IIter1
, typename _IIter2
,
1211 typename _OutputIterator
, typename _BinaryOperation
,
1212 typename _Tag1
, typename _Tag2
, typename _Tag3
>
1213 inline _OutputIterator
1214 __transform2_switch(_IIter1 __begin1
, _IIter1 __end1
,
1215 _IIter2 __begin2
, _OutputIterator __result
,
1216 _BinaryOperation __binary_op
, _Tag1
, _Tag2
, _Tag3
)
1217 { return transform(__begin1
, __end1
, __begin2
, __result
, __binary_op
,
1218 __gnu_parallel::sequential_tag()); }
1220 // Public interface.
1221 template<typename _IIter1
, typename _IIter2
,
1222 typename _OutputIterator
, typename _BinaryOperation
>
1223 inline _OutputIterator
1224 transform(_IIter1 __begin1
, _IIter1 __end1
,
1225 _IIter2 __begin2
, _OutputIterator __result
,
1226 _BinaryOperation __binary_op
,
1227 __gnu_parallel::_Parallelism __parallelism_tag
)
1229 return __transform2_switch(
1230 __begin1
, __end1
, __begin2
, __result
, __binary_op
,
1231 std::__iterator_category(__begin1
),
1232 std::__iterator_category(__begin2
),
1233 std::__iterator_category(__result
),
1237 template<typename _IIter1
, typename _IIter2
,
1238 typename _OutputIterator
, typename _BinaryOperation
>
1239 inline _OutputIterator
1240 transform(_IIter1 __begin1
, _IIter1 __end1
,
1241 _IIter2 __begin2
, _OutputIterator __result
,
1242 _BinaryOperation __binary_op
)
1244 return __transform2_switch(
1245 __begin1
, __end1
, __begin2
, __result
, __binary_op
,
1246 std::__iterator_category(__begin1
),
1247 std::__iterator_category(__begin2
),
1248 std::__iterator_category(__result
));
1251 // Sequential fallback
1252 template<typename _FIterator
, typename _Tp
>
1254 replace(_FIterator __begin
, _FIterator __end
, const _Tp
& __old_value
,
1255 const _Tp
& __new_value
, __gnu_parallel::sequential_tag
)
1256 { _GLIBCXX_STD_A::replace(__begin
, __end
, __old_value
, __new_value
); }
1258 // Sequential fallback for input iterator case
1259 template<typename _FIterator
, typename _Tp
, typename _IteratorTag
>
1261 __replace_switch(_FIterator __begin
, _FIterator __end
,
1262 const _Tp
& __old_value
, const _Tp
& __new_value
,
1264 { replace(__begin
, __end
, __old_value
, __new_value
,
1265 __gnu_parallel::sequential_tag()); }
1267 // Parallel replace for random access iterators
1268 template<typename _RAIter
, typename _Tp
>
1270 __replace_switch(_RAIter __begin
, _RAIter __end
,
1271 const _Tp
& __old_value
, const _Tp
& __new_value
,
1272 random_access_iterator_tag
,
1273 __gnu_parallel::_Parallelism __parallelism_tag
)
1275 // XXX parallel version is where?
1276 replace(__begin
, __end
, __old_value
, __new_value
,
1277 __gnu_parallel::sequential_tag());
1281 template<typename _FIterator
, typename _Tp
>
1283 replace(_FIterator __begin
, _FIterator __end
, const _Tp
& __old_value
,
1284 const _Tp
& __new_value
,
1285 __gnu_parallel::_Parallelism __parallelism_tag
)
1287 __replace_switch(__begin
, __end
, __old_value
, __new_value
,
1288 std::__iterator_category(__begin
),
1292 template<typename _FIterator
, typename _Tp
>
1294 replace(_FIterator __begin
, _FIterator __end
, const _Tp
& __old_value
,
1295 const _Tp
& __new_value
)
1297 __replace_switch(__begin
, __end
, __old_value
, __new_value
,
1298 std::__iterator_category(__begin
));
1302 // Sequential fallback
1303 template<typename _FIterator
, typename _Predicate
, typename _Tp
>
1305 replace_if(_FIterator __begin
, _FIterator __end
, _Predicate __pred
,
1306 const _Tp
& __new_value
, __gnu_parallel::sequential_tag
)
1307 { _GLIBCXX_STD_A::replace_if(__begin
, __end
, __pred
, __new_value
); }
1309 // Sequential fallback for input iterator case
1310 template<typename _FIterator
, typename _Predicate
, typename _Tp
,
1311 typename _IteratorTag
>
1313 __replace_if_switch(_FIterator __begin
, _FIterator __end
,
1314 _Predicate __pred
, const _Tp
& __new_value
, _IteratorTag
)
1315 { replace_if(__begin
, __end
, __pred
, __new_value
,
1316 __gnu_parallel::sequential_tag()); }
1318 // Parallel algorithm for random access iterators.
1319 template<typename _RAIter
, typename _Predicate
, typename _Tp
>
1321 __replace_if_switch(_RAIter __begin
, _RAIter __end
,
1322 _Predicate __pred
, const _Tp
& __new_value
,
1323 random_access_iterator_tag
,
1324 __gnu_parallel::_Parallelism __parallelism_tag
)
1326 if (_GLIBCXX_PARALLEL_CONDITION(
1327 static_cast<__gnu_parallel::_SequenceIndex
>(__end
- __begin
)
1328 >= __gnu_parallel::_Settings::get().replace_minimal_n
1329 && __gnu_parallel::__is_parallel(__parallelism_tag
)))
1333 __replace_if_selector
<_RAIter
, _Predicate
, _Tp
>
1334 __functionality(__new_value
);
1336 __for_each_template_random_access(
1337 __begin
, __end
, __pred
, __functionality
,
1338 __gnu_parallel::_DummyReduct(),
1339 true, __dummy
, -1, __parallelism_tag
);
1342 replace_if(__begin
, __end
, __pred
, __new_value
,
1343 __gnu_parallel::sequential_tag());
1346 // Public interface.
1347 template<typename _FIterator
, typename _Predicate
, typename _Tp
>
1349 replace_if(_FIterator __begin
, _FIterator __end
,
1350 _Predicate __pred
, const _Tp
& __new_value
,
1351 __gnu_parallel::_Parallelism __parallelism_tag
)
1353 __replace_if_switch(__begin
, __end
, __pred
, __new_value
,
1354 std::__iterator_category(__begin
),
1358 template<typename _FIterator
, typename _Predicate
, typename _Tp
>
1360 replace_if(_FIterator __begin
, _FIterator __end
,
1361 _Predicate __pred
, const _Tp
& __new_value
)
1363 __replace_if_switch(__begin
, __end
, __pred
, __new_value
,
1364 std::__iterator_category(__begin
));
1367 // Sequential fallback
1368 template<typename _FIterator
, typename _Generator
>
1370 generate(_FIterator __begin
, _FIterator __end
, _Generator __gen
,
1371 __gnu_parallel::sequential_tag
)
1372 { _GLIBCXX_STD_A::generate(__begin
, __end
, __gen
); }
1374 // Sequential fallback for input iterator case.
1375 template<typename _FIterator
, typename _Generator
, typename _IteratorTag
>
1377 __generate_switch(_FIterator __begin
, _FIterator __end
, _Generator __gen
,
1379 { generate(__begin
, __end
, __gen
, __gnu_parallel::sequential_tag()); }
1381 // Parallel algorithm for random access iterators.
1382 template<typename _RAIter
, typename _Generator
>
1384 __generate_switch(_RAIter __begin
, _RAIter __end
,
1385 _Generator __gen
, random_access_iterator_tag
,
1386 __gnu_parallel::_Parallelism __parallelism_tag
)
1388 if (_GLIBCXX_PARALLEL_CONDITION(
1389 static_cast<__gnu_parallel::_SequenceIndex
>(__end
- __begin
)
1390 >= __gnu_parallel::_Settings::get().generate_minimal_n
1391 && __gnu_parallel::__is_parallel(__parallelism_tag
)))
1394 __gnu_parallel::__generate_selector
<_RAIter
>
1397 __for_each_template_random_access(
1398 __begin
, __end
, __gen
, __functionality
,
1399 __gnu_parallel::_DummyReduct(),
1400 true, __dummy
, -1, __parallelism_tag
);
1403 generate(__begin
, __end
, __gen
, __gnu_parallel::sequential_tag());
1406 // Public interface.
1407 template<typename _FIterator
, typename _Generator
>
1409 generate(_FIterator __begin
, _FIterator __end
,
1410 _Generator __gen
, __gnu_parallel::_Parallelism __parallelism_tag
)
1412 __generate_switch(__begin
, __end
, __gen
,
1413 std::__iterator_category(__begin
),
1417 template<typename _FIterator
, typename _Generator
>
1419 generate(_FIterator __begin
, _FIterator __end
, _Generator __gen
)
1421 __generate_switch(__begin
, __end
, __gen
,
1422 std::__iterator_category(__begin
));
1426 // Sequential fallback.
1427 template<typename _OutputIterator
, typename _Size
, typename _Generator
>
1428 inline _OutputIterator
1429 generate_n(_OutputIterator __begin
, _Size __n
, _Generator __gen
,
1430 __gnu_parallel::sequential_tag
)
1431 { return _GLIBCXX_STD_A::generate_n(__begin
, __n
, __gen
); }
1433 // Sequential fallback for input iterator case.
1434 template<typename _OutputIterator
, typename _Size
, typename _Generator
,
1435 typename _IteratorTag
>
1436 inline _OutputIterator
1437 __generate_n_switch(_OutputIterator __begin
, _Size __n
, _Generator __gen
,
1439 { return generate_n(__begin
, __n
, __gen
,
1440 __gnu_parallel::sequential_tag()); }
1442 // Parallel algorithm for random access iterators.
1443 template<typename _RAIter
, typename _Size
, typename _Generator
>
1445 __generate_n_switch(_RAIter __begin
, _Size __n
, _Generator __gen
,
1446 random_access_iterator_tag
,
1447 __gnu_parallel::_Parallelism __parallelism_tag
)
1449 // XXX parallel version is where?
1450 return generate_n(__begin
, __n
, __gen
, __gnu_parallel::sequential_tag());
1453 // Public interface.
1454 template<typename _OutputIterator
, typename _Size
, typename _Generator
>
1455 inline _OutputIterator
1456 generate_n(_OutputIterator __begin
, _Size __n
, _Generator __gen
,
1457 __gnu_parallel::_Parallelism __parallelism_tag
)
1459 return __generate_n_switch(__begin
, __n
, __gen
,
1460 std::__iterator_category(__begin
),
1464 template<typename _OutputIterator
, typename _Size
, typename _Generator
>
1465 inline _OutputIterator
1466 generate_n(_OutputIterator __begin
, _Size __n
, _Generator __gen
)
1468 return __generate_n_switch(__begin
, __n
, __gen
,
1469 std::__iterator_category(__begin
));
1473 // Sequential fallback.
1474 template<typename _RAIter
>
1476 random_shuffle(_RAIter __begin
, _RAIter __end
,
1477 __gnu_parallel::sequential_tag
)
1478 { _GLIBCXX_STD_A::random_shuffle(__begin
, __end
); }
1480 // Sequential fallback.
1481 template<typename _RAIter
, typename _RandomNumberGenerator
>
1483 random_shuffle(_RAIter __begin
, _RAIter __end
,
1484 _RandomNumberGenerator
& __rand
,
1485 __gnu_parallel::sequential_tag
)
1486 { _GLIBCXX_STD_A::random_shuffle(__begin
, __end
, __rand
); }
1489 /** @brief Functor wrapper for std::rand(). */
1490 template<typename _MustBeInt
= int>
1494 operator()(int __limit
)
1495 { return rand() % __limit
; }
1498 // Fill in random number generator.
1499 template<typename _RAIter
>
1501 random_shuffle(_RAIter __begin
, _RAIter __end
)
1504 // Parallelization still possible.
1505 __gnu_parallel::random_shuffle(__begin
, __end
, __r
);
1508 // Parallel algorithm for random access iterators.
1509 template<typename _RAIter
, typename _RandomNumberGenerator
>
1511 random_shuffle(_RAIter __begin
, _RAIter __end
,
1512 #if __cplusplus >= 201103L
1513 _RandomNumberGenerator
&& __rand
)
1515 _RandomNumberGenerator
& __rand
)
1518 if (__begin
== __end
)
1520 if (_GLIBCXX_PARALLEL_CONDITION(
1521 static_cast<__gnu_parallel::_SequenceIndex
>(__end
- __begin
)
1522 >= __gnu_parallel::_Settings::get().random_shuffle_minimal_n
))
1523 __gnu_parallel::__parallel_random_shuffle(__begin
, __end
, __rand
);
1525 __gnu_parallel::__sequential_random_shuffle(__begin
, __end
, __rand
);
1528 // Sequential fallback.
1529 template<typename _FIterator
, typename _Predicate
>
1531 partition(_FIterator __begin
, _FIterator __end
,
1532 _Predicate __pred
, __gnu_parallel::sequential_tag
)
1533 { return _GLIBCXX_STD_A::partition(__begin
, __end
, __pred
); }
1535 // Sequential fallback for input iterator case.
1536 template<typename _FIterator
, typename _Predicate
, typename _IteratorTag
>
1538 __partition_switch(_FIterator __begin
, _FIterator __end
,
1539 _Predicate __pred
, _IteratorTag
)
1540 { return partition(__begin
, __end
, __pred
,
1541 __gnu_parallel::sequential_tag()); }
1543 // Parallel algorithm for random access iterators.
1544 template<typename _RAIter
, typename _Predicate
>
1546 __partition_switch(_RAIter __begin
, _RAIter __end
,
1547 _Predicate __pred
, random_access_iterator_tag
)
1549 if (_GLIBCXX_PARALLEL_CONDITION(
1550 static_cast<__gnu_parallel::_SequenceIndex
>(__end
- __begin
)
1551 >= __gnu_parallel::_Settings::get().partition_minimal_n
))
1553 typedef typename
std::iterator_traits
<_RAIter
>::
1554 difference_type _DifferenceType
;
1555 _DifferenceType __middle
= __gnu_parallel::
1556 __parallel_partition(__begin
, __end
, __pred
,
1557 __gnu_parallel::__get_max_threads());
1558 return __begin
+ __middle
;
1561 return partition(__begin
, __end
, __pred
,
1562 __gnu_parallel::sequential_tag());
1565 // Public interface.
1566 template<typename _FIterator
, typename _Predicate
>
1568 partition(_FIterator __begin
, _FIterator __end
, _Predicate __pred
)
1570 return __partition_switch(__begin
, __end
, __pred
,
1571 std::__iterator_category(__begin
));
1576 // Sequential fallback
1577 template<typename _RAIter
>
1579 sort(_RAIter __begin
, _RAIter __end
,
1580 __gnu_parallel::sequential_tag
)
1581 { _GLIBCXX_STD_A::sort(__begin
, __end
); }
1583 // Sequential fallback
1584 template<typename _RAIter
, typename _Compare
>
1586 sort(_RAIter __begin
, _RAIter __end
, _Compare __comp
,
1587 __gnu_parallel::sequential_tag
)
1588 { _GLIBCXX_STD_A::sort
<_RAIter
, _Compare
>(__begin
, __end
,
1592 template<typename _RAIter
, typename _Compare
,
1593 typename _Parallelism
>
1595 sort(_RAIter __begin
, _RAIter __end
, _Compare __comp
,
1596 _Parallelism __parallelism
)
1598 typedef typename iterator_traits
<_RAIter
>::value_type _ValueType
;
1600 if (__begin
!= __end
)
1602 if (_GLIBCXX_PARALLEL_CONDITION(
1603 static_cast<__gnu_parallel::_SequenceIndex
>(__end
- __begin
) >=
1604 __gnu_parallel::_Settings::get().sort_minimal_n
))
1605 __gnu_parallel::__parallel_sort
<false>(
1606 __begin
, __end
, __comp
, __parallelism
);
1608 sort(__begin
, __end
, __comp
, __gnu_parallel::sequential_tag());
1612 // Public interface, insert default comparator
1613 template<typename _RAIter
>
1615 sort(_RAIter __begin
, _RAIter __end
)
1617 typedef typename iterator_traits
<_RAIter
>::value_type _ValueType
;
1618 sort(__begin
, __end
, std::less
<_ValueType
>(),
1619 __gnu_parallel::default_parallel_tag());
1622 // Public interface, insert default comparator
1623 template<typename _RAIter
>
1625 sort(_RAIter __begin
, _RAIter __end
,
1626 __gnu_parallel::default_parallel_tag __parallelism
)
1628 typedef typename iterator_traits
<_RAIter
>::value_type _ValueType
;
1629 sort(__begin
, __end
, std::less
<_ValueType
>(), __parallelism
);
1632 // Public interface, insert default comparator
1633 template<typename _RAIter
>
1635 sort(_RAIter __begin
, _RAIter __end
,
1636 __gnu_parallel::parallel_tag __parallelism
)
1638 typedef typename iterator_traits
<_RAIter
>::value_type _ValueType
;
1639 sort(__begin
, __end
, std::less
<_ValueType
>(), __parallelism
);
1642 // Public interface, insert default comparator
1643 template<typename _RAIter
>
1645 sort(_RAIter __begin
, _RAIter __end
,
1646 __gnu_parallel::multiway_mergesort_tag __parallelism
)
1648 typedef typename iterator_traits
<_RAIter
>::value_type _ValueType
;
1649 sort(__begin
, __end
, std::less
<_ValueType
>(), __parallelism
);
1652 // Public interface, insert default comparator
1653 template<typename _RAIter
>
1655 sort(_RAIter __begin
, _RAIter __end
,
1656 __gnu_parallel::multiway_mergesort_sampling_tag __parallelism
)
1658 typedef typename iterator_traits
<_RAIter
>::value_type _ValueType
;
1659 sort(__begin
, __end
, std::less
<_ValueType
>(), __parallelism
);
1662 // Public interface, insert default comparator
1663 template<typename _RAIter
>
1665 sort(_RAIter __begin
, _RAIter __end
,
1666 __gnu_parallel::multiway_mergesort_exact_tag __parallelism
)
1668 typedef typename iterator_traits
<_RAIter
>::value_type _ValueType
;
1669 sort(__begin
, __end
, std::less
<_ValueType
>(), __parallelism
);
1672 // Public interface, insert default comparator
1673 template<typename _RAIter
>
1675 sort(_RAIter __begin
, _RAIter __end
,
1676 __gnu_parallel::quicksort_tag __parallelism
)
1678 typedef typename iterator_traits
<_RAIter
>::value_type _ValueType
;
1679 sort(__begin
, __end
, std::less
<_ValueType
>(), __parallelism
);
1682 // Public interface, insert default comparator
1683 template<typename _RAIter
>
1685 sort(_RAIter __begin
, _RAIter __end
,
1686 __gnu_parallel::balanced_quicksort_tag __parallelism
)
1688 typedef typename iterator_traits
<_RAIter
>::value_type _ValueType
;
1689 sort(__begin
, __end
, std::less
<_ValueType
>(), __parallelism
);
1693 template<typename _RAIter
, typename _Compare
>
1695 sort(_RAIter __begin
, _RAIter __end
, _Compare __comp
)
1697 typedef typename iterator_traits
<_RAIter
>::value_type _ValueType
;
1698 sort(__begin
, __end
, __comp
, __gnu_parallel::default_parallel_tag());
1701 // stable_sort interface
1704 // Sequential fallback
1705 template<typename _RAIter
>
1707 stable_sort(_RAIter __begin
, _RAIter __end
,
1708 __gnu_parallel::sequential_tag
)
1709 { _GLIBCXX_STD_A::stable_sort(__begin
, __end
); }
1711 // Sequential fallback
1712 template<typename _RAIter
, typename _Compare
>
1714 stable_sort(_RAIter __begin
, _RAIter __end
,
1715 _Compare __comp
, __gnu_parallel::sequential_tag
)
1716 { _GLIBCXX_STD_A::stable_sort
<_RAIter
, _Compare
>(__begin
, __end
, __comp
); }
1719 template<typename _RAIter
, typename _Compare
,
1720 typename _Parallelism
>
1722 stable_sort(_RAIter __begin
, _RAIter __end
,
1723 _Compare __comp
, _Parallelism __parallelism
)
1725 typedef iterator_traits
<_RAIter
> _TraitsType
;
1726 typedef typename
_TraitsType::value_type _ValueType
;
1728 if (__begin
!= __end
)
1730 if (_GLIBCXX_PARALLEL_CONDITION(
1731 static_cast<__gnu_parallel::_SequenceIndex
>(__end
- __begin
) >=
1732 __gnu_parallel::_Settings::get().sort_minimal_n
))
1733 __gnu_parallel::__parallel_sort
<true>(__begin
, __end
,
1734 __comp
, __parallelism
);
1736 stable_sort(__begin
, __end
, __comp
,
1737 __gnu_parallel::sequential_tag());
1741 // Public interface, insert default comparator
1742 template<typename _RAIter
>
1744 stable_sort(_RAIter __begin
, _RAIter __end
)
1746 typedef typename iterator_traits
<_RAIter
>::value_type _ValueType
;
1747 stable_sort(__begin
, __end
, std::less
<_ValueType
>(),
1748 __gnu_parallel::default_parallel_tag());
1751 // Public interface, insert default comparator
1752 template<typename _RAIter
>
1754 stable_sort(_RAIter __begin
, _RAIter __end
,
1755 __gnu_parallel::default_parallel_tag __parallelism
)
1757 typedef typename iterator_traits
<_RAIter
>::value_type _ValueType
;
1758 stable_sort(__begin
, __end
, std::less
<_ValueType
>(), __parallelism
);
1761 // Public interface, insert default comparator
1762 template<typename _RAIter
>
1764 stable_sort(_RAIter __begin
, _RAIter __end
,
1765 __gnu_parallel::parallel_tag __parallelism
)
1767 typedef typename iterator_traits
<_RAIter
>::value_type _ValueType
;
1768 stable_sort(__begin
, __end
, std::less
<_ValueType
>(), __parallelism
);
1771 // Public interface, insert default comparator
1772 template<typename _RAIter
>
1774 stable_sort(_RAIter __begin
, _RAIter __end
,
1775 __gnu_parallel::multiway_mergesort_tag __parallelism
)
1777 typedef typename iterator_traits
<_RAIter
>::value_type _ValueType
;
1778 stable_sort(__begin
, __end
, std::less
<_ValueType
>(), __parallelism
);
1781 // Public interface, insert default comparator
1782 template<typename _RAIter
>
1784 stable_sort(_RAIter __begin
, _RAIter __end
,
1785 __gnu_parallel::quicksort_tag __parallelism
)
1787 typedef typename iterator_traits
<_RAIter
>::value_type _ValueType
;
1788 stable_sort(__begin
, __end
, std::less
<_ValueType
>(), __parallelism
);
1791 // Public interface, insert default comparator
1792 template<typename _RAIter
>
1794 stable_sort(_RAIter __begin
, _RAIter __end
,
1795 __gnu_parallel::balanced_quicksort_tag __parallelism
)
1797 typedef typename iterator_traits
<_RAIter
>::value_type _ValueType
;
1798 stable_sort(__begin
, __end
, std::less
<_ValueType
>(), __parallelism
);
1802 template<typename _RAIter
, typename _Compare
>
1804 stable_sort(_RAIter __begin
, _RAIter __end
, _Compare __comp
)
1807 __begin
, __end
, __comp
, __gnu_parallel::default_parallel_tag());
1810 // Sequential fallback
1811 template<typename _IIter1
, typename _IIter2
,
1812 typename _OutputIterator
>
1813 inline _OutputIterator
1814 merge(_IIter1 __begin1
, _IIter1 __end1
, _IIter2 __begin2
,
1815 _IIter2 __end2
, _OutputIterator __result
,
1816 __gnu_parallel::sequential_tag
)
1817 { return _GLIBCXX_STD_A::merge(
1818 __begin1
, __end1
, __begin2
, __end2
, __result
); }
1820 // Sequential fallback
1821 template<typename _IIter1
, typename _IIter2
,
1822 typename _OutputIterator
, typename _Compare
>
1823 inline _OutputIterator
1824 merge(_IIter1 __begin1
, _IIter1 __end1
, _IIter2 __begin2
,
1825 _IIter2 __end2
, _OutputIterator __result
, _Compare __comp
,
1826 __gnu_parallel::sequential_tag
)
1827 { return _GLIBCXX_STD_A::merge(
1828 __begin1
, __end1
, __begin2
, __end2
, __result
, __comp
); }
1830 // Sequential fallback for input iterator case
1831 template<typename _IIter1
, typename _IIter2
, typename _OutputIterator
,
1832 typename _Compare
, typename _IteratorTag1
,
1833 typename _IteratorTag2
, typename _IteratorTag3
>
1834 inline _OutputIterator
1835 __merge_switch(_IIter1 __begin1
, _IIter1 __end1
,
1836 _IIter2 __begin2
, _IIter2 __end2
,
1837 _OutputIterator __result
, _Compare __comp
,
1838 _IteratorTag1
, _IteratorTag2
, _IteratorTag3
)
1839 { return _GLIBCXX_STD_A::merge(__begin1
, __end1
, __begin2
, __end2
,
1840 __result
, __comp
); }
1842 // Parallel algorithm for random access iterators
1843 template<typename _IIter1
, typename _IIter2
,
1844 typename _OutputIterator
, typename _Compare
>
1846 __merge_switch(_IIter1 __begin1
, _IIter1 __end1
,
1847 _IIter2 __begin2
, _IIter2 __end2
,
1848 _OutputIterator __result
, _Compare __comp
,
1849 random_access_iterator_tag
, random_access_iterator_tag
,
1850 random_access_iterator_tag
)
1852 if (_GLIBCXX_PARALLEL_CONDITION(
1853 (static_cast<__gnu_parallel::_SequenceIndex
>(__end1
- __begin1
)
1854 >= __gnu_parallel::_Settings::get().merge_minimal_n
1855 || static_cast<__gnu_parallel::_SequenceIndex
>(__end2
- __begin2
)
1856 >= __gnu_parallel::_Settings::get().merge_minimal_n
)))
1857 return __gnu_parallel::__parallel_merge_advance(
1858 __begin1
, __end1
, __begin2
, __end2
, __result
,
1859 (__end1
- __begin1
) + (__end2
- __begin2
), __comp
);
1861 return __gnu_parallel::__merge_advance(
1862 __begin1
, __end1
, __begin2
, __end2
, __result
,
1863 (__end1
- __begin1
) + (__end2
- __begin2
), __comp
);
1867 template<typename _IIter1
, typename _IIter2
,
1868 typename _OutputIterator
, typename _Compare
>
1869 inline _OutputIterator
1870 merge(_IIter1 __begin1
, _IIter1 __end1
, _IIter2 __begin2
,
1871 _IIter2 __end2
, _OutputIterator __result
, _Compare __comp
)
1873 return __merge_switch(
1874 __begin1
, __end1
, __begin2
, __end2
, __result
, __comp
,
1875 std::__iterator_category(__begin1
),
1876 std::__iterator_category(__begin2
),
1877 std::__iterator_category(__result
));
1880 // Public interface, insert default comparator
1881 template<typename _IIter1
, typename _IIter2
,
1882 typename _OutputIterator
>
1883 inline _OutputIterator
1884 merge(_IIter1 __begin1
, _IIter1 __end1
, _IIter2 __begin2
,
1885 _IIter2 __end2
, _OutputIterator __result
)
1887 typedef typename
std::iterator_traits
<_IIter1
>::value_type _ValueType1
;
1888 typedef typename
std::iterator_traits
<_IIter2
>::value_type _ValueType2
;
1890 return __gnu_parallel::merge(__begin1
, __end1
, __begin2
, __end2
,
1891 __result
, __gnu_parallel::_Less
<_ValueType1
, _ValueType2
>());
1894 // Sequential fallback
1895 template<typename _RAIter
>
1897 nth_element(_RAIter __begin
, _RAIter __nth
,
1898 _RAIter __end
, __gnu_parallel::sequential_tag
)
1899 { return _GLIBCXX_STD_A::nth_element(__begin
, __nth
, __end
); }
1901 // Sequential fallback
1902 template<typename _RAIter
, typename _Compare
>
1904 nth_element(_RAIter __begin
, _RAIter __nth
,
1905 _RAIter __end
, _Compare __comp
,
1906 __gnu_parallel::sequential_tag
)
1907 { return _GLIBCXX_STD_A::nth_element(__begin
, __nth
, __end
, __comp
); }
1910 template<typename _RAIter
, typename _Compare
>
1912 nth_element(_RAIter __begin
, _RAIter __nth
,
1913 _RAIter __end
, _Compare __comp
)
1915 if (_GLIBCXX_PARALLEL_CONDITION(
1916 static_cast<__gnu_parallel::_SequenceIndex
>(__end
- __begin
)
1917 >= __gnu_parallel::_Settings::get().nth_element_minimal_n
))
1918 __gnu_parallel::__parallel_nth_element(__begin
, __nth
, __end
, __comp
);
1920 nth_element(__begin
, __nth
, __end
, __comp
,
1921 __gnu_parallel::sequential_tag());
1924 // Public interface, insert default comparator
1925 template<typename _RAIter
>
1927 nth_element(_RAIter __begin
, _RAIter __nth
,
1930 typedef typename iterator_traits
<_RAIter
>::value_type _ValueType
;
1931 __gnu_parallel::nth_element(__begin
, __nth
, __end
,
1932 std::less
<_ValueType
>());
1935 // Sequential fallback
1936 template<typename _RAIter
, typename _Compare
>
1938 partial_sort(_RAIter __begin
, _RAIter __middle
,
1939 _RAIter __end
, _Compare __comp
,
1940 __gnu_parallel::sequential_tag
)
1941 { _GLIBCXX_STD_A::partial_sort(__begin
, __middle
, __end
, __comp
); }
1943 // Sequential fallback
1944 template<typename _RAIter
>
1946 partial_sort(_RAIter __begin
, _RAIter __middle
,
1947 _RAIter __end
, __gnu_parallel::sequential_tag
)
1948 { _GLIBCXX_STD_A::partial_sort(__begin
, __middle
, __end
); }
1950 // Public interface, parallel algorithm for random access iterators
1951 template<typename _RAIter
, typename _Compare
>
1953 partial_sort(_RAIter __begin
, _RAIter __middle
,
1954 _RAIter __end
, _Compare __comp
)
1956 if (_GLIBCXX_PARALLEL_CONDITION(
1957 static_cast<__gnu_parallel::_SequenceIndex
>(__end
- __begin
)
1958 >= __gnu_parallel::_Settings::get().partial_sort_minimal_n
))
1960 __parallel_partial_sort(__begin
, __middle
, __end
, __comp
);
1962 partial_sort(__begin
, __middle
, __end
, __comp
,
1963 __gnu_parallel::sequential_tag());
1966 // Public interface, insert default comparator
1967 template<typename _RAIter
>
1969 partial_sort(_RAIter __begin
, _RAIter __middle
,
1972 typedef iterator_traits
<_RAIter
> _TraitsType
;
1973 typedef typename
_TraitsType::value_type _ValueType
;
1974 __gnu_parallel::partial_sort(__begin
, __middle
, __end
,
1975 std::less
<_ValueType
>());
1978 // Sequential fallback
1979 template<typename _FIterator
>
1981 max_element(_FIterator __begin
, _FIterator __end
,
1982 __gnu_parallel::sequential_tag
)
1983 { return _GLIBCXX_STD_A::max_element(__begin
, __end
); }
1985 // Sequential fallback
1986 template<typename _FIterator
, typename _Compare
>
1988 max_element(_FIterator __begin
, _FIterator __end
, _Compare __comp
,
1989 __gnu_parallel::sequential_tag
)
1990 { return _GLIBCXX_STD_A::max_element(__begin
, __end
, __comp
); }
1992 // Sequential fallback for input iterator case
1993 template<typename _FIterator
, typename _Compare
, typename _IteratorTag
>
1995 __max_element_switch(_FIterator __begin
, _FIterator __end
,
1996 _Compare __comp
, _IteratorTag
)
1997 { return max_element(__begin
, __end
, __comp
,
1998 __gnu_parallel::sequential_tag()); }
2000 // Parallel algorithm for random access iterators
2001 template<typename _RAIter
, typename _Compare
>
2003 __max_element_switch(_RAIter __begin
, _RAIter __end
,
2004 _Compare __comp
, random_access_iterator_tag
,
2005 __gnu_parallel::_Parallelism __parallelism_tag
)
2007 if (_GLIBCXX_PARALLEL_CONDITION(
2008 static_cast<__gnu_parallel::_SequenceIndex
>(__end
- __begin
)
2009 >= __gnu_parallel::_Settings::get().max_element_minimal_n
2010 && __gnu_parallel::__is_parallel(__parallelism_tag
)))
2012 _RAIter
__res(__begin
);
2013 __gnu_parallel::__identity_selector
<_RAIter
>
2016 __for_each_template_random_access(
2017 __begin
, __end
, __gnu_parallel::_Nothing(), __functionality
,
2018 __gnu_parallel::__max_element_reduct
<_Compare
, _RAIter
>(__comp
),
2019 __res
, __res
, -1, __parallelism_tag
);
2023 return max_element(__begin
, __end
, __comp
,
2024 __gnu_parallel::sequential_tag());
2027 // Public interface, insert default comparator
2028 template<typename _FIterator
>
2030 max_element(_FIterator __begin
, _FIterator __end
,
2031 __gnu_parallel::_Parallelism __parallelism_tag
)
2033 typedef typename iterator_traits
<_FIterator
>::value_type _ValueType
;
2034 return max_element(__begin
, __end
, std::less
<_ValueType
>(),
2038 template<typename _FIterator
>
2040 max_element(_FIterator __begin
, _FIterator __end
)
2042 typedef typename iterator_traits
<_FIterator
>::value_type _ValueType
;
2043 return __gnu_parallel::max_element(__begin
, __end
,
2044 std::less
<_ValueType
>());
2048 template<typename _FIterator
, typename _Compare
>
2050 max_element(_FIterator __begin
, _FIterator __end
, _Compare __comp
,
2051 __gnu_parallel::_Parallelism __parallelism_tag
)
2053 return __max_element_switch(__begin
, __end
, __comp
,
2054 std::__iterator_category(__begin
),
2058 template<typename _FIterator
, typename _Compare
>
2060 max_element(_FIterator __begin
, _FIterator __end
, _Compare __comp
)
2062 return __max_element_switch(__begin
, __end
, __comp
,
2063 std::__iterator_category(__begin
));
2067 // Sequential fallback
2068 template<typename _FIterator
>
2070 min_element(_FIterator __begin
, _FIterator __end
,
2071 __gnu_parallel::sequential_tag
)
2072 { return _GLIBCXX_STD_A::min_element(__begin
, __end
); }
2074 // Sequential fallback
2075 template<typename _FIterator
, typename _Compare
>
2077 min_element(_FIterator __begin
, _FIterator __end
, _Compare __comp
,
2078 __gnu_parallel::sequential_tag
)
2079 { return _GLIBCXX_STD_A::min_element(__begin
, __end
, __comp
); }
2081 // Sequential fallback for input iterator case
2082 template<typename _FIterator
, typename _Compare
, typename _IteratorTag
>
2084 __min_element_switch(_FIterator __begin
, _FIterator __end
,
2085 _Compare __comp
, _IteratorTag
)
2086 { return min_element(__begin
, __end
, __comp
,
2087 __gnu_parallel::sequential_tag()); }
2089 // Parallel algorithm for random access iterators
2090 template<typename _RAIter
, typename _Compare
>
2092 __min_element_switch(_RAIter __begin
, _RAIter __end
,
2093 _Compare __comp
, random_access_iterator_tag
,
2094 __gnu_parallel::_Parallelism __parallelism_tag
)
2096 if (_GLIBCXX_PARALLEL_CONDITION(
2097 static_cast<__gnu_parallel::_SequenceIndex
>(__end
- __begin
)
2098 >= __gnu_parallel::_Settings::get().min_element_minimal_n
2099 && __gnu_parallel::__is_parallel(__parallelism_tag
)))
2101 _RAIter
__res(__begin
);
2102 __gnu_parallel::__identity_selector
<_RAIter
>
2105 __for_each_template_random_access(
2106 __begin
, __end
, __gnu_parallel::_Nothing(), __functionality
,
2107 __gnu_parallel::__min_element_reduct
<_Compare
, _RAIter
>(__comp
),
2108 __res
, __res
, -1, __parallelism_tag
);
2112 return min_element(__begin
, __end
, __comp
,
2113 __gnu_parallel::sequential_tag());
2116 // Public interface, insert default comparator
2117 template<typename _FIterator
>
2119 min_element(_FIterator __begin
, _FIterator __end
,
2120 __gnu_parallel::_Parallelism __parallelism_tag
)
2122 typedef typename iterator_traits
<_FIterator
>::value_type _ValueType
;
2123 return min_element(__begin
, __end
, std::less
<_ValueType
>(),
2127 template<typename _FIterator
>
2129 min_element(_FIterator __begin
, _FIterator __end
)
2131 typedef typename iterator_traits
<_FIterator
>::value_type _ValueType
;
2132 return __gnu_parallel::min_element(__begin
, __end
,
2133 std::less
<_ValueType
>());
2137 template<typename _FIterator
, typename _Compare
>
2139 min_element(_FIterator __begin
, _FIterator __end
, _Compare __comp
,
2140 __gnu_parallel::_Parallelism __parallelism_tag
)
2142 return __min_element_switch(__begin
, __end
, __comp
,
2143 std::__iterator_category(__begin
),
2147 template<typename _FIterator
, typename _Compare
>
2149 min_element(_FIterator __begin
, _FIterator __end
, _Compare __comp
)
2151 return __min_element_switch(__begin
, __end
, __comp
,
2152 std::__iterator_category(__begin
));
2155 #if __cplusplus >= 201703L
2156 using _GLIBCXX_STD_A::for_each_n
;
2157 using _GLIBCXX_STD_A::sample
;
2162 #endif /* _GLIBCXX_PARALLEL_ALGO_H */