3 // Copyright (C) 2007-2014 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
); }
73 // Sequential fallback for input iterator case
74 template<typename _IIter
, typename _Function
, typename _IteratorTag
>
76 __for_each_switch(_IIter __begin
, _IIter __end
, _Function __f
,
78 { return for_each(__begin
, __end
, __f
, __gnu_parallel::sequential_tag()); }
80 // Parallel algorithm for random access iterators
81 template<typename _RAIter
, typename _Function
>
83 __for_each_switch(_RAIter __begin
, _RAIter __end
,
84 _Function __f
, random_access_iterator_tag
,
85 __gnu_parallel::_Parallelism __parallelism_tag
86 = __gnu_parallel::parallel_balanced
)
88 if (_GLIBCXX_PARALLEL_CONDITION(
89 static_cast<__gnu_parallel::_SequenceIndex
>(__end
- __begin
)
90 >= __gnu_parallel::_Settings::get().for_each_minimal_n
91 && __gnu_parallel::__is_parallel(__parallelism_tag
)))
94 __gnu_parallel::__for_each_selector
<_RAIter
> __functionality
;
96 return __gnu_parallel::
97 __for_each_template_random_access(
98 __begin
, __end
, __f
, __functionality
,
99 __gnu_parallel::_DummyReduct(), true, __dummy
, -1,
103 return for_each(__begin
, __end
, __f
, __gnu_parallel::sequential_tag());
107 template<typename _Iterator
, typename _Function
>
109 for_each(_Iterator __begin
, _Iterator __end
, _Function __f
,
110 __gnu_parallel::_Parallelism __parallelism_tag
)
112 typedef std::iterator_traits
<_Iterator
> _IteratorTraits
;
113 typedef typename
_IteratorTraits::iterator_category _IteratorCategory
;
114 return __for_each_switch(__begin
, __end
, __f
, _IteratorCategory(),
118 template<typename _Iterator
, typename _Function
>
120 for_each(_Iterator __begin
, _Iterator __end
, _Function __f
)
122 typedef std::iterator_traits
<_Iterator
> _IteratorTraits
;
123 typedef typename
_IteratorTraits::iterator_category _IteratorCategory
;
124 return __for_each_switch(__begin
, __end
, __f
, _IteratorCategory());
128 // Sequential fallback
129 template<typename _IIter
, typename _Tp
>
131 find(_IIter __begin
, _IIter __end
, const _Tp
& __val
,
132 __gnu_parallel::sequential_tag
)
133 { return _GLIBCXX_STD_A::find(__begin
, __end
, __val
); }
135 // Sequential fallback for input iterator case
136 template<typename _IIter
, typename _Tp
, typename _IteratorTag
>
138 __find_switch(_IIter __begin
, _IIter __end
, const _Tp
& __val
,
140 { return _GLIBCXX_STD_A::find(__begin
, __end
, __val
); }
142 // Parallel find for random access iterators
143 template<typename _RAIter
, typename _Tp
>
145 __find_switch(_RAIter __begin
, _RAIter __end
,
146 const _Tp
& __val
, random_access_iterator_tag
)
148 typedef iterator_traits
<_RAIter
> _TraitsType
;
149 typedef typename
_TraitsType::value_type _ValueType
;
151 if (_GLIBCXX_PARALLEL_CONDITION(true))
153 __gnu_parallel::__binder2nd
<__gnu_parallel::_EqualTo
<_ValueType
,
155 _ValueType
, const _Tp
&, bool>
156 __comp(__gnu_parallel::_EqualTo
<_ValueType
, const _Tp
&>(), __val
);
157 return __gnu_parallel::__find_template(
158 __begin
, __end
, __begin
, __comp
,
159 __gnu_parallel::__find_if_selector()).first
;
162 return _GLIBCXX_STD_A::find(__begin
, __end
, __val
);
166 template<typename _IIter
, typename _Tp
>
168 find(_IIter __begin
, _IIter __end
, const _Tp
& __val
)
170 typedef std::iterator_traits
<_IIter
> _IteratorTraits
;
171 typedef typename
_IteratorTraits::iterator_category _IteratorCategory
;
172 return __find_switch(__begin
, __end
, __val
, _IteratorCategory());
175 // Sequential fallback
176 template<typename _IIter
, typename _Predicate
>
178 find_if(_IIter __begin
, _IIter __end
, _Predicate __pred
,
179 __gnu_parallel::sequential_tag
)
180 { return _GLIBCXX_STD_A::find_if(__begin
, __end
, __pred
); }
182 // Sequential fallback for input iterator case
183 template<typename _IIter
, typename _Predicate
, typename _IteratorTag
>
185 __find_if_switch(_IIter __begin
, _IIter __end
, _Predicate __pred
,
187 { return _GLIBCXX_STD_A::find_if(__begin
, __end
, __pred
); }
189 // Parallel find_if for random access iterators
190 template<typename _RAIter
, typename _Predicate
>
192 __find_if_switch(_RAIter __begin
, _RAIter __end
,
193 _Predicate __pred
, random_access_iterator_tag
)
195 if (_GLIBCXX_PARALLEL_CONDITION(true))
196 return __gnu_parallel::__find_template(__begin
, __end
, __begin
, __pred
,
198 __find_if_selector()).first
;
200 return _GLIBCXX_STD_A::find_if(__begin
, __end
, __pred
);
204 template<typename _IIter
, typename _Predicate
>
206 find_if(_IIter __begin
, _IIter __end
, _Predicate __pred
)
208 typedef std::iterator_traits
<_IIter
> _IteratorTraits
;
209 typedef typename
_IteratorTraits::iterator_category _IteratorCategory
;
210 return __find_if_switch(__begin
, __end
, __pred
, _IteratorCategory());
213 // Sequential fallback
214 template<typename _IIter
, typename _FIterator
>
216 find_first_of(_IIter __begin1
, _IIter __end1
,
217 _FIterator __begin2
, _FIterator __end2
,
218 __gnu_parallel::sequential_tag
)
219 { return _GLIBCXX_STD_A::find_first_of(__begin1
, __end1
, __begin2
, __end2
);
222 // Sequential fallback
223 template<typename _IIter
, typename _FIterator
,
224 typename _BinaryPredicate
>
226 find_first_of(_IIter __begin1
, _IIter __end1
,
227 _FIterator __begin2
, _FIterator __end2
,
228 _BinaryPredicate __comp
, __gnu_parallel::sequential_tag
)
229 { return _GLIBCXX_STD_A::find_first_of(
230 __begin1
, __end1
, __begin2
, __end2
, __comp
); }
232 // Sequential fallback for input iterator type
233 template<typename _IIter
, typename _FIterator
,
234 typename _IteratorTag1
, typename _IteratorTag2
>
236 __find_first_of_switch(_IIter __begin1
, _IIter __end1
,
237 _FIterator __begin2
, _FIterator __end2
,
238 _IteratorTag1
, _IteratorTag2
)
239 { return find_first_of(__begin1
, __end1
, __begin2
, __end2
,
240 __gnu_parallel::sequential_tag()); }
242 // Parallel algorithm for random access iterators
243 template<typename _RAIter
, typename _FIterator
,
244 typename _BinaryPredicate
, typename _IteratorTag
>
246 __find_first_of_switch(_RAIter __begin1
,
248 _FIterator __begin2
, _FIterator __end2
,
249 _BinaryPredicate __comp
, random_access_iterator_tag
,
252 return __gnu_parallel::
253 __find_template(__begin1
, __end1
, __begin1
, __comp
,
254 __gnu_parallel::__find_first_of_selector
255 <_FIterator
>(__begin2
, __end2
)).first
;
258 // Sequential fallback for input iterator type
259 template<typename _IIter
, typename _FIterator
,
260 typename _BinaryPredicate
, typename _IteratorTag1
,
261 typename _IteratorTag2
>
263 __find_first_of_switch(_IIter __begin1
, _IIter __end1
,
264 _FIterator __begin2
, _FIterator __end2
,
265 _BinaryPredicate __comp
, _IteratorTag1
, _IteratorTag2
)
266 { return find_first_of(__begin1
, __end1
, __begin2
, __end2
, __comp
,
267 __gnu_parallel::sequential_tag()); }
270 template<typename _IIter
, typename _FIterator
,
271 typename _BinaryPredicate
>
273 find_first_of(_IIter __begin1
, _IIter __end1
,
274 _FIterator __begin2
, _FIterator __end2
,
275 _BinaryPredicate __comp
)
277 typedef std::iterator_traits
<_IIter
> _IIterTraits
;
278 typedef std::iterator_traits
<_FIterator
> _FIterTraits
;
279 typedef typename
_IIterTraits::iterator_category _IIteratorCategory
;
280 typedef typename
_FIterTraits::iterator_category _FIteratorCategory
;
282 return __find_first_of_switch(__begin1
, __end1
, __begin2
, __end2
, __comp
,
283 _IIteratorCategory(), _FIteratorCategory());
286 // Public interface, insert default comparator
287 template<typename _IIter
, typename _FIterator
>
289 find_first_of(_IIter __begin1
, _IIter __end1
,
290 _FIterator __begin2
, _FIterator __end2
)
292 typedef std::iterator_traits
<_IIter
> _IIterTraits
;
293 typedef std::iterator_traits
<_FIterator
> _FIterTraits
;
294 typedef typename
_IIterTraits::value_type _IValueType
;
295 typedef typename
_FIterTraits::value_type _FValueType
;
297 return __gnu_parallel::find_first_of(__begin1
, __end1
, __begin2
, __end2
,
298 __gnu_parallel::_EqualTo
<_IValueType
, _FValueType
>());
301 // Sequential fallback
302 template<typename _IIter
, typename _OutputIterator
>
303 inline _OutputIterator
304 unique_copy(_IIter __begin1
, _IIter __end1
, _OutputIterator __out
,
305 __gnu_parallel::sequential_tag
)
306 { return _GLIBCXX_STD_A::unique_copy(__begin1
, __end1
, __out
); }
308 // Sequential fallback
309 template<typename _IIter
, typename _OutputIterator
,
311 inline _OutputIterator
312 unique_copy(_IIter __begin1
, _IIter __end1
, _OutputIterator __out
,
313 _Predicate __pred
, __gnu_parallel::sequential_tag
)
314 { return _GLIBCXX_STD_A::unique_copy(__begin1
, __end1
, __out
, __pred
); }
316 // Sequential fallback for input iterator case
317 template<typename _IIter
, typename _OutputIterator
,
318 typename _Predicate
, typename _IteratorTag1
, typename _IteratorTag2
>
319 inline _OutputIterator
320 __unique_copy_switch(_IIter __begin
, _IIter __last
,
321 _OutputIterator __out
, _Predicate __pred
,
322 _IteratorTag1
, _IteratorTag2
)
323 { return _GLIBCXX_STD_A::unique_copy(__begin
, __last
, __out
, __pred
); }
325 // Parallel unique_copy for random access iterators
326 template<typename _RAIter
, typename RandomAccessOutputIterator
,
328 RandomAccessOutputIterator
329 __unique_copy_switch(_RAIter __begin
, _RAIter __last
,
330 RandomAccessOutputIterator __out
, _Predicate __pred
,
331 random_access_iterator_tag
, random_access_iterator_tag
)
333 if (_GLIBCXX_PARALLEL_CONDITION(
334 static_cast<__gnu_parallel::_SequenceIndex
>(__last
- __begin
)
335 > __gnu_parallel::_Settings::get().unique_copy_minimal_n
))
336 return __gnu_parallel::__parallel_unique_copy(
337 __begin
, __last
, __out
, __pred
);
339 return _GLIBCXX_STD_A::unique_copy(__begin
, __last
, __out
, __pred
);
343 template<typename _IIter
, typename _OutputIterator
>
344 inline _OutputIterator
345 unique_copy(_IIter __begin1
, _IIter __end1
, _OutputIterator __out
)
347 typedef std::iterator_traits
<_IIter
> _IIterTraits
;
348 typedef std::iterator_traits
<_OutputIterator
> _OIterTraits
;
349 typedef typename
_IIterTraits::iterator_category _IIteratorCategory
;
350 typedef typename
_IIterTraits::value_type _ValueType
;
351 typedef typename
_OIterTraits::iterator_category _OIterCategory
;
353 return __unique_copy_switch(
354 __begin1
, __end1
, __out
, equal_to
<_ValueType
>(),
355 _IIteratorCategory(), _OIterCategory());
359 template<typename _IIter
, typename _OutputIterator
, typename _Predicate
>
360 inline _OutputIterator
361 unique_copy(_IIter __begin1
, _IIter __end1
, _OutputIterator __out
,
364 typedef std::iterator_traits
<_IIter
> _IIterTraits
;
365 typedef std::iterator_traits
<_OutputIterator
> _OIterTraits
;
366 typedef typename
_IIterTraits::iterator_category _IIteratorCategory
;
367 typedef typename
_OIterTraits::iterator_category _OIterCategory
;
369 return __unique_copy_switch(
370 __begin1
, __end1
, __out
, __pred
,
371 _IIteratorCategory(), _OIterCategory());
374 // Sequential fallback
375 template<typename _IIter1
, typename _IIter2
,
376 typename _OutputIterator
>
377 inline _OutputIterator
378 set_union(_IIter1 __begin1
, _IIter1 __end1
,
379 _IIter2 __begin2
, _IIter2 __end2
,
380 _OutputIterator __out
, __gnu_parallel::sequential_tag
)
381 { return _GLIBCXX_STD_A::set_union(
382 __begin1
, __end1
, __begin2
, __end2
, __out
); }
384 // Sequential fallback
385 template<typename _IIter1
, typename _IIter2
,
386 typename _OutputIterator
, typename _Predicate
>
387 inline _OutputIterator
388 set_union(_IIter1 __begin1
, _IIter1 __end1
,
389 _IIter2 __begin2
, _IIter2 __end2
,
390 _OutputIterator __out
, _Predicate __pred
,
391 __gnu_parallel::sequential_tag
)
392 { return _GLIBCXX_STD_A::set_union(__begin1
, __end1
,
393 __begin2
, __end2
, __out
, __pred
); }
395 // Sequential fallback for input iterator case
396 template<typename _IIter1
, typename _IIter2
, typename _Predicate
,
397 typename _OutputIterator
, typename _IteratorTag1
,
398 typename _IteratorTag2
, typename _IteratorTag3
>
399 inline _OutputIterator
401 _IIter1 __begin1
, _IIter1 __end1
, _IIter2 __begin2
, _IIter2 __end2
,
402 _OutputIterator __result
, _Predicate __pred
,
403 _IteratorTag1
, _IteratorTag2
, _IteratorTag3
)
404 { return _GLIBCXX_STD_A::set_union(__begin1
, __end1
,
405 __begin2
, __end2
, __result
, __pred
); }
407 // Parallel set_union for random access iterators
408 template<typename _RAIter1
, typename _RAIter2
,
409 typename _Output_RAIter
, typename _Predicate
>
411 __set_union_switch(_RAIter1 __begin1
, _RAIter1 __end1
,
412 _RAIter2 __begin2
, _RAIter2 __end2
,
413 _Output_RAIter __result
, _Predicate __pred
,
414 random_access_iterator_tag
, random_access_iterator_tag
,
415 random_access_iterator_tag
)
417 if (_GLIBCXX_PARALLEL_CONDITION(
418 static_cast<__gnu_parallel::_SequenceIndex
>(__end1
- __begin1
)
419 >= __gnu_parallel::_Settings::get().set_union_minimal_n
420 || static_cast<__gnu_parallel::_SequenceIndex
>(__end2
- __begin2
)
421 >= __gnu_parallel::_Settings::get().set_union_minimal_n
))
422 return __gnu_parallel::__parallel_set_union(
423 __begin1
, __end1
, __begin2
, __end2
, __result
, __pred
);
425 return _GLIBCXX_STD_A::set_union(__begin1
, __end1
,
426 __begin2
, __end2
, __result
, __pred
);
430 template<typename _IIter1
, typename _IIter2
,
431 typename _OutputIterator
>
432 inline _OutputIterator
433 set_union(_IIter1 __begin1
, _IIter1 __end1
,
434 _IIter2 __begin2
, _IIter2 __end2
, _OutputIterator __out
)
436 typedef std::iterator_traits
<_IIter1
> _IIterTraits1
;
437 typedef std::iterator_traits
<_IIter2
> _IIterTraits2
;
438 typedef std::iterator_traits
<_OutputIterator
> _OIterTraits
;
439 typedef typename
_IIterTraits1::iterator_category
441 typedef typename
_IIterTraits2::iterator_category
443 typedef typename
_OIterTraits::iterator_category _OIterCategory
;
444 typedef typename
_IIterTraits1::value_type _ValueType1
;
445 typedef typename
_IIterTraits2::value_type _ValueType2
;
447 return __set_union_switch(
448 __begin1
, __end1
, __begin2
, __end2
, __out
,
449 __gnu_parallel::_Less
<_ValueType1
, _ValueType2
>(),
450 _IIterCategory1(), _IIterCategory2(), _OIterCategory());
454 template<typename _IIter1
, typename _IIter2
,
455 typename _OutputIterator
, typename _Predicate
>
456 inline _OutputIterator
457 set_union(_IIter1 __begin1
, _IIter1 __end1
,
458 _IIter2 __begin2
, _IIter2 __end2
,
459 _OutputIterator __out
, _Predicate __pred
)
461 typedef std::iterator_traits
<_IIter1
> _IIterTraits1
;
462 typedef std::iterator_traits
<_IIter2
> _IIterTraits2
;
463 typedef std::iterator_traits
<_OutputIterator
> _OIterTraits
;
464 typedef typename
_IIterTraits1::iterator_category
466 typedef typename
_IIterTraits2::iterator_category
468 typedef typename
_OIterTraits::iterator_category _OIterCategory
;
470 return __set_union_switch(
471 __begin1
, __end1
, __begin2
, __end2
, __out
, __pred
,
472 _IIterCategory1(), _IIterCategory2(), _OIterCategory());
475 // Sequential fallback.
476 template<typename _IIter1
, typename _IIter2
,
477 typename _OutputIterator
>
478 inline _OutputIterator
479 set_intersection(_IIter1 __begin1
, _IIter1 __end1
,
480 _IIter2 __begin2
, _IIter2 __end2
,
481 _OutputIterator __out
, __gnu_parallel::sequential_tag
)
482 { return _GLIBCXX_STD_A::set_intersection(__begin1
, __end1
,
483 __begin2
, __end2
, __out
); }
485 // Sequential fallback.
486 template<typename _IIter1
, typename _IIter2
,
487 typename _OutputIterator
, typename _Predicate
>
488 inline _OutputIterator
489 set_intersection(_IIter1 __begin1
, _IIter1 __end1
,
490 _IIter2 __begin2
, _IIter2 __end2
,
491 _OutputIterator __out
, _Predicate __pred
,
492 __gnu_parallel::sequential_tag
)
493 { return _GLIBCXX_STD_A::set_intersection(
494 __begin1
, __end1
, __begin2
, __end2
, __out
, __pred
); }
496 // Sequential fallback for input iterator case
497 template<typename _IIter1
, typename _IIter2
,
498 typename _Predicate
, typename _OutputIterator
,
499 typename _IteratorTag1
, typename _IteratorTag2
,
500 typename _IteratorTag3
>
501 inline _OutputIterator
502 __set_intersection_switch(_IIter1 __begin1
, _IIter1 __end1
,
503 _IIter2 __begin2
, _IIter2 __end2
,
504 _OutputIterator __result
, _Predicate __pred
,
505 _IteratorTag1
, _IteratorTag2
, _IteratorTag3
)
506 { return _GLIBCXX_STD_A::set_intersection(__begin1
, __end1
, __begin2
,
507 __end2
, __result
, __pred
); }
509 // Parallel set_intersection for random access iterators
510 template<typename _RAIter1
, typename _RAIter2
,
511 typename _Output_RAIter
, typename _Predicate
>
513 __set_intersection_switch(_RAIter1 __begin1
,
517 _Output_RAIter __result
,
519 random_access_iterator_tag
,
520 random_access_iterator_tag
,
521 random_access_iterator_tag
)
523 if (_GLIBCXX_PARALLEL_CONDITION(
524 static_cast<__gnu_parallel::_SequenceIndex
>(__end1
- __begin1
)
525 >= __gnu_parallel::_Settings::get().set_union_minimal_n
526 || static_cast<__gnu_parallel::_SequenceIndex
>(__end2
- __begin2
)
527 >= __gnu_parallel::_Settings::get().set_union_minimal_n
))
528 return __gnu_parallel::__parallel_set_intersection(
529 __begin1
, __end1
, __begin2
, __end2
, __result
, __pred
);
531 return _GLIBCXX_STD_A::set_intersection(
532 __begin1
, __end1
, __begin2
, __end2
, __result
, __pred
);
536 template<typename _IIter1
, typename _IIter2
,
537 typename _OutputIterator
>
538 inline _OutputIterator
539 set_intersection(_IIter1 __begin1
, _IIter1 __end1
,
540 _IIter2 __begin2
, _IIter2 __end2
,
541 _OutputIterator __out
)
543 typedef std::iterator_traits
<_IIter1
> _IIterTraits1
;
544 typedef std::iterator_traits
<_IIter2
> _IIterTraits2
;
545 typedef std::iterator_traits
<_OutputIterator
> _OIterTraits
;
546 typedef typename
_IIterTraits1::iterator_category
548 typedef typename
_IIterTraits2::iterator_category
550 typedef typename
_OIterTraits::iterator_category _OIterCategory
;
551 typedef typename
_IIterTraits1::value_type _ValueType1
;
552 typedef typename
_IIterTraits2::value_type _ValueType2
;
554 return __set_intersection_switch(
555 __begin1
, __end1
, __begin2
, __end2
, __out
,
556 __gnu_parallel::_Less
<_ValueType1
, _ValueType2
>(),
557 _IIterCategory1(), _IIterCategory2(), _OIterCategory());
560 template<typename _IIter1
, typename _IIter2
,
561 typename _OutputIterator
, typename _Predicate
>
562 inline _OutputIterator
563 set_intersection(_IIter1 __begin1
, _IIter1 __end1
,
564 _IIter2 __begin2
, _IIter2 __end2
,
565 _OutputIterator __out
, _Predicate __pred
)
567 typedef std::iterator_traits
<_IIter1
> _IIterTraits1
;
568 typedef std::iterator_traits
<_IIter2
> _IIterTraits2
;
569 typedef std::iterator_traits
<_OutputIterator
> _OIterTraits
;
570 typedef typename
_IIterTraits1::iterator_category
572 typedef typename
_IIterTraits2::iterator_category
574 typedef typename
_OIterTraits::iterator_category _OIterCategory
;
576 return __set_intersection_switch(
577 __begin1
, __end1
, __begin2
, __end2
, __out
, __pred
,
578 _IIterCategory1(), _IIterCategory2(), _OIterCategory());
581 // Sequential fallback
582 template<typename _IIter1
, typename _IIter2
,
583 typename _OutputIterator
>
584 inline _OutputIterator
585 set_symmetric_difference(_IIter1 __begin1
, _IIter1 __end1
,
586 _IIter2 __begin2
, _IIter2 __end2
,
587 _OutputIterator __out
,
588 __gnu_parallel::sequential_tag
)
589 { return _GLIBCXX_STD_A::set_symmetric_difference(
590 __begin1
, __end1
, __begin2
, __end2
, __out
); }
592 // Sequential fallback
593 template<typename _IIter1
, typename _IIter2
,
594 typename _OutputIterator
, typename _Predicate
>
595 inline _OutputIterator
596 set_symmetric_difference(_IIter1 __begin1
, _IIter1 __end1
,
597 _IIter2 __begin2
, _IIter2 __end2
,
598 _OutputIterator __out
, _Predicate __pred
,
599 __gnu_parallel::sequential_tag
)
600 { return _GLIBCXX_STD_A::set_symmetric_difference(
601 __begin1
, __end1
, __begin2
, __end2
, __out
, __pred
); }
603 // Sequential fallback for input iterator case
604 template<typename _IIter1
, typename _IIter2
,
605 typename _Predicate
, typename _OutputIterator
,
606 typename _IteratorTag1
, typename _IteratorTag2
,
607 typename _IteratorTag3
>
608 inline _OutputIterator
609 __set_symmetric_difference_switch(
610 _IIter1 __begin1
, _IIter1 __end1
, _IIter2 __begin2
, _IIter2 __end2
,
611 _OutputIterator __result
, _Predicate __pred
,
612 _IteratorTag1
, _IteratorTag2
, _IteratorTag3
)
613 { return _GLIBCXX_STD_A::set_symmetric_difference(
614 __begin1
, __end1
, __begin2
, __end2
, __result
, __pred
); }
616 // Parallel set_symmetric_difference for random access iterators
617 template<typename _RAIter1
, typename _RAIter2
,
618 typename _Output_RAIter
, typename _Predicate
>
620 __set_symmetric_difference_switch(_RAIter1 __begin1
,
624 _Output_RAIter __result
,
626 random_access_iterator_tag
,
627 random_access_iterator_tag
,
628 random_access_iterator_tag
)
630 if (_GLIBCXX_PARALLEL_CONDITION(
631 static_cast<__gnu_parallel::_SequenceIndex
>(__end1
- __begin1
)
632 >= __gnu_parallel::_Settings::get().set_symmetric_difference_minimal_n
633 || static_cast<__gnu_parallel::_SequenceIndex
>(__end2
- __begin2
)
634 >= __gnu_parallel::_Settings::get().set_symmetric_difference_minimal_n
))
635 return __gnu_parallel::__parallel_set_symmetric_difference(
636 __begin1
, __end1
, __begin2
, __end2
, __result
, __pred
);
638 return _GLIBCXX_STD_A::set_symmetric_difference(
639 __begin1
, __end1
, __begin2
, __end2
, __result
, __pred
);
643 template<typename _IIter1
, typename _IIter2
,
644 typename _OutputIterator
>
645 inline _OutputIterator
646 set_symmetric_difference(_IIter1 __begin1
, _IIter1 __end1
,
647 _IIter2 __begin2
, _IIter2 __end2
,
648 _OutputIterator __out
)
650 typedef std::iterator_traits
<_IIter1
> _IIterTraits1
;
651 typedef std::iterator_traits
<_IIter2
> _IIterTraits2
;
652 typedef std::iterator_traits
<_OutputIterator
> _OIterTraits
;
653 typedef typename
_IIterTraits1::iterator_category
655 typedef typename
_IIterTraits2::iterator_category
657 typedef typename
_OIterTraits::iterator_category _OIterCategory
;
658 typedef typename
_IIterTraits1::value_type _ValueType1
;
659 typedef typename
_IIterTraits2::value_type _ValueType2
;
661 return __set_symmetric_difference_switch(
662 __begin1
, __end1
, __begin2
, __end2
, __out
,
663 __gnu_parallel::_Less
<_ValueType1
, _ValueType2
>(),
664 _IIterCategory1(), _IIterCategory2(), _OIterCategory());
668 template<typename _IIter1
, typename _IIter2
,
669 typename _OutputIterator
, typename _Predicate
>
670 inline _OutputIterator
671 set_symmetric_difference(_IIter1 __begin1
, _IIter1 __end1
,
672 _IIter2 __begin2
, _IIter2 __end2
,
673 _OutputIterator __out
, _Predicate __pred
)
675 typedef std::iterator_traits
<_IIter1
> _IIterTraits1
;
676 typedef std::iterator_traits
<_IIter2
> _IIterTraits2
;
677 typedef std::iterator_traits
<_OutputIterator
> _OIterTraits
;
678 typedef typename
_IIterTraits1::iterator_category
680 typedef typename
_IIterTraits2::iterator_category
682 typedef typename
_OIterTraits::iterator_category _OIterCategory
;
684 return __set_symmetric_difference_switch(
685 __begin1
, __end1
, __begin2
, __end2
, __out
, __pred
,
686 _IIterCategory1(), _IIterCategory2(), _OIterCategory());
689 // Sequential fallback.
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
, __gnu_parallel::sequential_tag
)
696 { return _GLIBCXX_STD_A::set_difference(
697 __begin1
,__end1
, __begin2
, __end2
, __out
); }
699 // Sequential fallback.
700 template<typename _IIter1
, typename _IIter2
,
701 typename _OutputIterator
, typename _Predicate
>
702 inline _OutputIterator
703 set_difference(_IIter1 __begin1
, _IIter1 __end1
,
704 _IIter2 __begin2
, _IIter2 __end2
,
705 _OutputIterator __out
, _Predicate __pred
,
706 __gnu_parallel::sequential_tag
)
707 { return _GLIBCXX_STD_A::set_difference(__begin1
, __end1
,
708 __begin2
, __end2
, __out
, __pred
); }
710 // Sequential fallback for input iterator case.
711 template<typename _IIter1
, typename _IIter2
, typename _Predicate
,
712 typename _OutputIterator
, typename _IteratorTag1
,
713 typename _IteratorTag2
, typename _IteratorTag3
>
714 inline _OutputIterator
715 __set_difference_switch(_IIter1 __begin1
, _IIter1 __end1
,
716 _IIter2 __begin2
, _IIter2 __end2
,
717 _OutputIterator __result
, _Predicate __pred
,
718 _IteratorTag1
, _IteratorTag2
, _IteratorTag3
)
719 { return _GLIBCXX_STD_A::set_difference(
720 __begin1
, __end1
, __begin2
, __end2
, __result
, __pred
); }
722 // Parallel set_difference for random access iterators
723 template<typename _RAIter1
, typename _RAIter2
,
724 typename _Output_RAIter
, typename _Predicate
>
726 __set_difference_switch(_RAIter1 __begin1
,
730 _Output_RAIter __result
, _Predicate __pred
,
731 random_access_iterator_tag
,
732 random_access_iterator_tag
,
733 random_access_iterator_tag
)
735 if (_GLIBCXX_PARALLEL_CONDITION(
736 static_cast<__gnu_parallel::_SequenceIndex
>(__end1
- __begin1
)
737 >= __gnu_parallel::_Settings::get().set_difference_minimal_n
738 || static_cast<__gnu_parallel::_SequenceIndex
>(__end2
- __begin2
)
739 >= __gnu_parallel::_Settings::get().set_difference_minimal_n
))
740 return __gnu_parallel::__parallel_set_difference(
741 __begin1
, __end1
, __begin2
, __end2
, __result
, __pred
);
743 return _GLIBCXX_STD_A::set_difference(
744 __begin1
, __end1
, __begin2
, __end2
, __result
, __pred
);
748 template<typename _IIter1
, typename _IIter2
,
749 typename _OutputIterator
>
750 inline _OutputIterator
751 set_difference(_IIter1 __begin1
, _IIter1 __end1
,
752 _IIter2 __begin2
, _IIter2 __end2
,
753 _OutputIterator __out
)
755 typedef std::iterator_traits
<_IIter1
> _IIterTraits1
;
756 typedef std::iterator_traits
<_IIter2
> _IIterTraits2
;
757 typedef std::iterator_traits
<_OutputIterator
> _OIterTraits
;
758 typedef typename
_IIterTraits1::iterator_category
760 typedef typename
_IIterTraits2::iterator_category
762 typedef typename
_OIterTraits::iterator_category _OIterCategory
;
763 typedef typename
_IIterTraits1::value_type _ValueType1
;
764 typedef typename
_IIterTraits2::value_type _ValueType2
;
766 return __set_difference_switch(
767 __begin1
, __end1
, __begin2
, __end2
, __out
,
768 __gnu_parallel::_Less
<_ValueType1
, _ValueType2
>(),
769 _IIterCategory1(), _IIterCategory2(), _OIterCategory());
773 template<typename _IIter1
, typename _IIter2
,
774 typename _OutputIterator
, typename _Predicate
>
775 inline _OutputIterator
776 set_difference(_IIter1 __begin1
, _IIter1 __end1
,
777 _IIter2 __begin2
, _IIter2 __end2
,
778 _OutputIterator __out
, _Predicate __pred
)
780 typedef std::iterator_traits
<_IIter1
> _IIterTraits1
;
781 typedef std::iterator_traits
<_IIter2
> _IIterTraits2
;
782 typedef std::iterator_traits
<_OutputIterator
> _OIterTraits
;
783 typedef typename
_IIterTraits1::iterator_category
785 typedef typename
_IIterTraits2::iterator_category
787 typedef typename
_OIterTraits::iterator_category _OIterCategory
;
789 return __set_difference_switch(
790 __begin1
, __end1
, __begin2
, __end2
, __out
, __pred
,
791 _IIterCategory1(), _IIterCategory2(), _OIterCategory());
794 // Sequential fallback
795 template<typename _FIterator
>
797 adjacent_find(_FIterator __begin
, _FIterator __end
,
798 __gnu_parallel::sequential_tag
)
799 { return _GLIBCXX_STD_A::adjacent_find(__begin
, __end
); }
801 // Sequential fallback
802 template<typename _FIterator
, typename _BinaryPredicate
>
804 adjacent_find(_FIterator __begin
, _FIterator __end
,
805 _BinaryPredicate __binary_pred
,
806 __gnu_parallel::sequential_tag
)
807 { return _GLIBCXX_STD_A::adjacent_find(__begin
, __end
, __binary_pred
); }
809 // Parallel algorithm for random access iterators
810 template<typename _RAIter
>
812 __adjacent_find_switch(_RAIter __begin
, _RAIter __end
,
813 random_access_iterator_tag
)
815 typedef iterator_traits
<_RAIter
> _TraitsType
;
816 typedef typename
_TraitsType::value_type _ValueType
;
818 if (_GLIBCXX_PARALLEL_CONDITION(true))
820 _RAIter __spot
= __gnu_parallel::
822 __begin
, __end
- 1, __begin
, equal_to
<_ValueType
>(),
823 __gnu_parallel::__adjacent_find_selector())
825 if (__spot
== (__end
- 1))
831 return adjacent_find(__begin
, __end
, __gnu_parallel::sequential_tag());
834 // Sequential fallback for input iterator case
835 template<typename _FIterator
, typename _IteratorTag
>
837 __adjacent_find_switch(_FIterator __begin
, _FIterator __end
,
839 { return adjacent_find(__begin
, __end
, __gnu_parallel::sequential_tag()); }
842 template<typename _FIterator
>
844 adjacent_find(_FIterator __begin
, _FIterator __end
)
846 typedef iterator_traits
<_FIterator
> _TraitsType
;
847 typedef typename
_TraitsType::iterator_category _IteratorCategory
;
848 return __adjacent_find_switch(__begin
, __end
, _IteratorCategory());
851 // Sequential fallback for input iterator case
852 template<typename _FIterator
, typename _BinaryPredicate
,
853 typename _IteratorTag
>
855 __adjacent_find_switch(_FIterator __begin
, _FIterator __end
,
856 _BinaryPredicate __pred
, _IteratorTag
)
857 { return adjacent_find(__begin
, __end
, __pred
,
858 __gnu_parallel::sequential_tag()); }
860 // Parallel algorithm for random access iterators
861 template<typename _RAIter
, typename _BinaryPredicate
>
863 __adjacent_find_switch(_RAIter __begin
, _RAIter __end
,
864 _BinaryPredicate __pred
, random_access_iterator_tag
)
866 if (_GLIBCXX_PARALLEL_CONDITION(true))
867 return __gnu_parallel::__find_template(__begin
, __end
, __begin
, __pred
,
869 __adjacent_find_selector()).first
;
871 return adjacent_find(__begin
, __end
, __pred
,
872 __gnu_parallel::sequential_tag());
876 template<typename _FIterator
, typename _BinaryPredicate
>
878 adjacent_find(_FIterator __begin
, _FIterator __end
,
879 _BinaryPredicate __pred
)
881 typedef iterator_traits
<_FIterator
> _TraitsType
;
882 typedef typename
_TraitsType::iterator_category _IteratorCategory
;
883 return __adjacent_find_switch(__begin
, __end
, __pred
,
884 _IteratorCategory());
887 // Sequential fallback
888 template<typename _IIter
, typename _Tp
>
889 inline typename iterator_traits
<_IIter
>::difference_type
890 count(_IIter __begin
, _IIter __end
, const _Tp
& __value
,
891 __gnu_parallel::sequential_tag
)
892 { return _GLIBCXX_STD_A::count(__begin
, __end
, __value
); }
894 // Parallel code for random access iterators
895 template<typename _RAIter
, typename _Tp
>
896 typename iterator_traits
<_RAIter
>::difference_type
897 __count_switch(_RAIter __begin
, _RAIter __end
,
898 const _Tp
& __value
, random_access_iterator_tag
,
899 __gnu_parallel::_Parallelism __parallelism_tag
900 = __gnu_parallel::parallel_unbalanced
)
902 typedef iterator_traits
<_RAIter
> _TraitsType
;
903 typedef typename
_TraitsType::value_type _ValueType
;
904 typedef typename
_TraitsType::difference_type _DifferenceType
;
905 typedef __gnu_parallel::_SequenceIndex _SequenceIndex
;
907 if (_GLIBCXX_PARALLEL_CONDITION(
908 static_cast<_SequenceIndex
>(__end
- __begin
)
909 >= __gnu_parallel::_Settings::get().count_minimal_n
910 && __gnu_parallel::__is_parallel(__parallelism_tag
)))
912 __gnu_parallel::__count_selector
<_RAIter
, _DifferenceType
>
914 _DifferenceType __res
= 0;
916 __for_each_template_random_access(
917 __begin
, __end
, __value
, __functionality
,
918 std::plus
<_SequenceIndex
>(), __res
, __res
, -1,
923 return count(__begin
, __end
, __value
,
924 __gnu_parallel::sequential_tag());
927 // Sequential fallback for input iterator case.
928 template<typename _IIter
, typename _Tp
, typename _IteratorTag
>
929 inline typename iterator_traits
<_IIter
>::difference_type
930 __count_switch(_IIter __begin
, _IIter __end
, const _Tp
& __value
,
932 { return count(__begin
, __end
, __value
, __gnu_parallel::sequential_tag());
936 template<typename _IIter
, typename _Tp
>
937 inline typename iterator_traits
<_IIter
>::difference_type
938 count(_IIter __begin
, _IIter __end
, const _Tp
& __value
,
939 __gnu_parallel::_Parallelism __parallelism_tag
)
941 typedef iterator_traits
<_IIter
> _TraitsType
;
942 typedef typename
_TraitsType::iterator_category _IteratorCategory
;
943 return __count_switch(__begin
, __end
, __value
, _IteratorCategory(),
947 template<typename _IIter
, typename _Tp
>
948 inline typename iterator_traits
<_IIter
>::difference_type
949 count(_IIter __begin
, _IIter __end
, const _Tp
& __value
)
951 typedef iterator_traits
<_IIter
> _TraitsType
;
952 typedef typename
_TraitsType::iterator_category _IteratorCategory
;
953 return __count_switch(__begin
, __end
, __value
, _IteratorCategory());
957 // Sequential fallback.
958 template<typename _IIter
, typename _Predicate
>
959 inline typename iterator_traits
<_IIter
>::difference_type
960 count_if(_IIter __begin
, _IIter __end
, _Predicate __pred
,
961 __gnu_parallel::sequential_tag
)
962 { return _GLIBCXX_STD_A::count_if(__begin
, __end
, __pred
); }
964 // Parallel count_if for random access iterators
965 template<typename _RAIter
, typename _Predicate
>
966 typename iterator_traits
<_RAIter
>::difference_type
967 __count_if_switch(_RAIter __begin
, _RAIter __end
,
968 _Predicate __pred
, random_access_iterator_tag
,
969 __gnu_parallel::_Parallelism __parallelism_tag
970 = __gnu_parallel::parallel_unbalanced
)
972 typedef iterator_traits
<_RAIter
> _TraitsType
;
973 typedef typename
_TraitsType::value_type _ValueType
;
974 typedef typename
_TraitsType::difference_type _DifferenceType
;
975 typedef __gnu_parallel::_SequenceIndex _SequenceIndex
;
977 if (_GLIBCXX_PARALLEL_CONDITION(
978 static_cast<_SequenceIndex
>(__end
- __begin
)
979 >= __gnu_parallel::_Settings::get().count_minimal_n
980 && __gnu_parallel::__is_parallel(__parallelism_tag
)))
982 _DifferenceType __res
= 0;
984 __count_if_selector
<_RAIter
, _DifferenceType
>
987 __for_each_template_random_access(
988 __begin
, __end
, __pred
, __functionality
,
989 std::plus
<_SequenceIndex
>(), __res
, __res
, -1,
994 return count_if(__begin
, __end
, __pred
,
995 __gnu_parallel::sequential_tag());
998 // Sequential fallback for input iterator case.
999 template<typename _IIter
, typename _Predicate
, typename _IteratorTag
>
1000 inline typename iterator_traits
<_IIter
>::difference_type
1001 __count_if_switch(_IIter __begin
, _IIter __end
, _Predicate __pred
,
1003 { return count_if(__begin
, __end
, __pred
,
1004 __gnu_parallel::sequential_tag()); }
1006 // Public interface.
1007 template<typename _IIter
, typename _Predicate
>
1008 inline typename iterator_traits
<_IIter
>::difference_type
1009 count_if(_IIter __begin
, _IIter __end
, _Predicate __pred
,
1010 __gnu_parallel::_Parallelism __parallelism_tag
)
1012 typedef iterator_traits
<_IIter
> _TraitsType
;
1013 typedef typename
_TraitsType::iterator_category _IteratorCategory
;
1014 return __count_if_switch(__begin
, __end
, __pred
, _IteratorCategory(),
1018 template<typename _IIter
, typename _Predicate
>
1019 inline typename iterator_traits
<_IIter
>::difference_type
1020 count_if(_IIter __begin
, _IIter __end
, _Predicate __pred
)
1022 typedef iterator_traits
<_IIter
> _TraitsType
;
1023 typedef typename
_TraitsType::iterator_category _IteratorCategory
;
1024 return __count_if_switch(__begin
, __end
, __pred
, _IteratorCategory());
1028 // Sequential fallback.
1029 template<typename _FIterator1
, typename _FIterator2
>
1031 search(_FIterator1 __begin1
, _FIterator1 __end1
,
1032 _FIterator2 __begin2
, _FIterator2 __end2
,
1033 __gnu_parallel::sequential_tag
)
1034 { return _GLIBCXX_STD_A::search(__begin1
, __end1
, __begin2
, __end2
); }
1036 // Parallel algorithm for random access iterator
1037 template<typename _RAIter1
, typename _RAIter2
>
1039 __search_switch(_RAIter1 __begin1
, _RAIter1 __end1
,
1040 _RAIter2 __begin2
, _RAIter2 __end2
,
1041 random_access_iterator_tag
, random_access_iterator_tag
)
1043 typedef std::iterator_traits
<_RAIter1
> _Iterator1Traits
;
1044 typedef typename
_Iterator1Traits::value_type _ValueType1
;
1045 typedef std::iterator_traits
<_RAIter2
> _Iterator2Traits
;
1046 typedef typename
_Iterator2Traits::value_type _ValueType2
;
1048 if (_GLIBCXX_PARALLEL_CONDITION(
1049 static_cast<__gnu_parallel::_SequenceIndex
>(__end1
- __begin1
)
1050 >= __gnu_parallel::_Settings::get().search_minimal_n
))
1051 return __gnu_parallel::
1053 __begin1
, __end1
, __begin2
, __end2
,
1054 __gnu_parallel::_EqualTo
<_ValueType1
, _ValueType2
>());
1056 return search(__begin1
, __end1
, __begin2
, __end2
,
1057 __gnu_parallel::sequential_tag());
1060 // Sequential fallback for input iterator case
1061 template<typename _FIterator1
, typename _FIterator2
,
1062 typename _IteratorTag1
, typename _IteratorTag2
>
1064 __search_switch(_FIterator1 __begin1
, _FIterator1 __end1
,
1065 _FIterator2 __begin2
, _FIterator2 __end2
,
1066 _IteratorTag1
, _IteratorTag2
)
1067 { return search(__begin1
, __end1
, __begin2
, __end2
,
1068 __gnu_parallel::sequential_tag()); }
1070 // Public interface.
1071 template<typename _FIterator1
, typename _FIterator2
>
1073 search(_FIterator1 __begin1
, _FIterator1 __end1
,
1074 _FIterator2 __begin2
, _FIterator2 __end2
)
1076 typedef std::iterator_traits
<_FIterator1
> _Iterator1Traits
;
1077 typedef typename
_Iterator1Traits::iterator_category _IteratorCategory1
;
1078 typedef std::iterator_traits
<_FIterator2
> _Iterator2Traits
;
1079 typedef typename
_Iterator2Traits::iterator_category _IteratorCategory2
;
1081 return __search_switch(__begin1
, __end1
, __begin2
, __end2
,
1082 _IteratorCategory1(), _IteratorCategory2());
1085 // Public interface.
1086 template<typename _FIterator1
, typename _FIterator2
,
1087 typename _BinaryPredicate
>
1089 search(_FIterator1 __begin1
, _FIterator1 __end1
,
1090 _FIterator2 __begin2
, _FIterator2 __end2
,
1091 _BinaryPredicate __pred
, __gnu_parallel::sequential_tag
)
1092 { return _GLIBCXX_STD_A::search(
1093 __begin1
, __end1
, __begin2
, __end2
, __pred
); }
1095 // Parallel algorithm for random access iterator.
1096 template<typename _RAIter1
, typename _RAIter2
,
1097 typename _BinaryPredicate
>
1099 __search_switch(_RAIter1 __begin1
, _RAIter1 __end1
,
1100 _RAIter2 __begin2
, _RAIter2 __end2
,
1101 _BinaryPredicate __pred
,
1102 random_access_iterator_tag
, random_access_iterator_tag
)
1104 if (_GLIBCXX_PARALLEL_CONDITION(
1105 static_cast<__gnu_parallel::_SequenceIndex
>(__end1
- __begin1
)
1106 >= __gnu_parallel::_Settings::get().search_minimal_n
))
1107 return __gnu_parallel::__search_template(__begin1
, __end1
,
1108 __begin2
, __end2
, __pred
);
1110 return search(__begin1
, __end1
, __begin2
, __end2
, __pred
,
1111 __gnu_parallel::sequential_tag());
1114 // Sequential fallback for input iterator case
1115 template<typename _FIterator1
, typename _FIterator2
,
1116 typename _BinaryPredicate
, typename _IteratorTag1
,
1117 typename _IteratorTag2
>
1119 __search_switch(_FIterator1 __begin1
, _FIterator1 __end1
,
1120 _FIterator2 __begin2
, _FIterator2 __end2
,
1121 _BinaryPredicate __pred
, _IteratorTag1
, _IteratorTag2
)
1122 { return search(__begin1
, __end1
, __begin2
, __end2
, __pred
,
1123 __gnu_parallel::sequential_tag()); }
1126 template<typename _FIterator1
, typename _FIterator2
,
1127 typename _BinaryPredicate
>
1129 search(_FIterator1 __begin1
, _FIterator1 __end1
,
1130 _FIterator2 __begin2
, _FIterator2 __end2
,
1131 _BinaryPredicate __pred
)
1133 typedef std::iterator_traits
<_FIterator1
> _Iterator1Traits
;
1134 typedef typename
_Iterator1Traits::iterator_category _IteratorCategory1
;
1135 typedef std::iterator_traits
<_FIterator2
> _Iterator2Traits
;
1136 typedef typename
_Iterator2Traits::iterator_category _IteratorCategory2
;
1137 return __search_switch(__begin1
, __end1
, __begin2
, __end2
, __pred
,
1138 _IteratorCategory1(), _IteratorCategory2());
1141 // Sequential fallback
1142 template<typename _FIterator
, typename _Integer
, typename _Tp
>
1144 search_n(_FIterator __begin
, _FIterator __end
, _Integer __count
,
1145 const _Tp
& __val
, __gnu_parallel::sequential_tag
)
1146 { return _GLIBCXX_STD_A::search_n(__begin
, __end
, __count
, __val
); }
1148 // Sequential fallback
1149 template<typename _FIterator
, typename _Integer
, typename _Tp
,
1150 typename _BinaryPredicate
>
1152 search_n(_FIterator __begin
, _FIterator __end
, _Integer __count
,
1153 const _Tp
& __val
, _BinaryPredicate __binary_pred
,
1154 __gnu_parallel::sequential_tag
)
1155 { return _GLIBCXX_STD_A::search_n(
1156 __begin
, __end
, __count
, __val
, __binary_pred
); }
1158 // Public interface.
1159 template<typename _FIterator
, typename _Integer
, typename _Tp
>
1161 search_n(_FIterator __begin
, _FIterator __end
, _Integer __count
,
1164 typedef typename iterator_traits
<_FIterator
>::value_type _ValueType
;
1165 return __gnu_parallel::search_n(__begin
, __end
, __count
, __val
,
1166 __gnu_parallel::_EqualTo
<_ValueType
, _Tp
>());
1169 // Parallel algorithm for random access iterators.
1170 template<typename _RAIter
, typename _Integer
,
1171 typename _Tp
, typename _BinaryPredicate
>
1173 __search_n_switch(_RAIter __begin
, _RAIter __end
, _Integer __count
,
1174 const _Tp
& __val
, _BinaryPredicate __binary_pred
,
1175 random_access_iterator_tag
)
1177 if (_GLIBCXX_PARALLEL_CONDITION(
1178 static_cast<__gnu_parallel::_SequenceIndex
>(__end
- __begin
)
1179 >= __gnu_parallel::_Settings::get().search_minimal_n
))
1181 __gnu_parallel::_PseudoSequence
<_Tp
, _Integer
> __ps(__val
, __count
);
1182 return __gnu_parallel::__search_template(
1183 __begin
, __end
, __ps
.begin(), __ps
.end(), __binary_pred
);
1186 return _GLIBCXX_STD_A::search_n(__begin
, __end
, __count
, __val
,
1190 // Sequential fallback for input iterator case.
1191 template<typename _FIterator
, typename _Integer
, typename _Tp
,
1192 typename _BinaryPredicate
, typename _IteratorTag
>
1194 __search_n_switch(_FIterator __begin
, _FIterator __end
, _Integer __count
,
1195 const _Tp
& __val
, _BinaryPredicate __binary_pred
,
1197 { return _GLIBCXX_STD_A::search_n(__begin
, __end
, __count
, __val
,
1200 // Public interface.
1201 template<typename _FIterator
, typename _Integer
, typename _Tp
,
1202 typename _BinaryPredicate
>
1204 search_n(_FIterator __begin
, _FIterator __end
, _Integer __count
,
1205 const _Tp
& __val
, _BinaryPredicate __binary_pred
)
1207 return __search_n_switch(__begin
, __end
, __count
, __val
, __binary_pred
,
1208 typename
std::iterator_traits
<_FIterator
>::
1209 iterator_category());
1213 // Sequential fallback.
1214 template<typename _IIter
, typename _OutputIterator
,
1215 typename _UnaryOperation
>
1216 inline _OutputIterator
1217 transform(_IIter __begin
, _IIter __end
, _OutputIterator __result
,
1218 _UnaryOperation __unary_op
, __gnu_parallel::sequential_tag
)
1219 { return _GLIBCXX_STD_A::transform(__begin
, __end
, __result
, __unary_op
); }
1221 // Parallel unary transform for random access iterators.
1222 template<typename _RAIter1
, typename _RAIter2
,
1223 typename _UnaryOperation
>
1225 __transform1_switch(_RAIter1 __begin
, _RAIter1 __end
,
1226 _RAIter2 __result
, _UnaryOperation __unary_op
,
1227 random_access_iterator_tag
, random_access_iterator_tag
,
1228 __gnu_parallel::_Parallelism __parallelism_tag
1229 = __gnu_parallel::parallel_balanced
)
1231 if (_GLIBCXX_PARALLEL_CONDITION(
1232 static_cast<__gnu_parallel::_SequenceIndex
>(__end
- __begin
)
1233 >= __gnu_parallel::_Settings::get().transform_minimal_n
1234 && __gnu_parallel::__is_parallel(__parallelism_tag
)))
1236 bool __dummy
= true;
1237 typedef __gnu_parallel::_IteratorPair
<_RAIter1
,
1238 _RAIter2
, random_access_iterator_tag
> _ItTrip
;
1239 _ItTrip
__begin_pair(__begin
, __result
),
1240 __end_pair(__end
, __result
+ (__end
- __begin
));
1241 __gnu_parallel::__transform1_selector
<_ItTrip
> __functionality
;
1243 __for_each_template_random_access(
1244 __begin_pair
, __end_pair
, __unary_op
, __functionality
,
1245 __gnu_parallel::_DummyReduct(),
1246 __dummy
, __dummy
, -1, __parallelism_tag
);
1247 return __functionality
._M_finish_iterator
;
1250 return transform(__begin
, __end
, __result
, __unary_op
,
1251 __gnu_parallel::sequential_tag());
1254 // Sequential fallback for input iterator case.
1255 template<typename _RAIter1
, typename _RAIter2
,
1256 typename _UnaryOperation
, typename _IteratorTag1
,
1257 typename _IteratorTag2
>
1259 __transform1_switch(_RAIter1 __begin
, _RAIter1 __end
,
1260 _RAIter2 __result
, _UnaryOperation __unary_op
,
1261 _IteratorTag1
, _IteratorTag2
)
1262 { return transform(__begin
, __end
, __result
, __unary_op
,
1263 __gnu_parallel::sequential_tag()); }
1265 // Public interface.
1266 template<typename _IIter
, typename _OutputIterator
,
1267 typename _UnaryOperation
>
1268 inline _OutputIterator
1269 transform(_IIter __begin
, _IIter __end
, _OutputIterator __result
,
1270 _UnaryOperation __unary_op
,
1271 __gnu_parallel::_Parallelism __parallelism_tag
)
1273 typedef std::iterator_traits
<_IIter
> _IIterTraits
;
1274 typedef std::iterator_traits
<_OutputIterator
> _OIterTraits
;
1275 typedef typename
_IIterTraits::iterator_category _IIteratorCategory
;
1276 typedef typename
_OIterTraits::iterator_category _OIterCategory
;
1278 return __transform1_switch(__begin
, __end
, __result
, __unary_op
,
1279 _IIteratorCategory(), _OIterCategory(),
1283 template<typename _IIter
, typename _OutputIterator
,
1284 typename _UnaryOperation
>
1285 inline _OutputIterator
1286 transform(_IIter __begin
, _IIter __end
, _OutputIterator __result
,
1287 _UnaryOperation __unary_op
)
1289 typedef std::iterator_traits
<_IIter
> _IIterTraits
;
1290 typedef std::iterator_traits
<_OutputIterator
> _OIterTraits
;
1291 typedef typename
_IIterTraits::iterator_category _IIteratorCategory
;
1292 typedef typename
_OIterTraits::iterator_category _OIterCategory
;
1294 return __transform1_switch(__begin
, __end
, __result
, __unary_op
,
1295 _IIteratorCategory(), _OIterCategory());
1299 // Sequential fallback
1300 template<typename _IIter1
, typename _IIter2
,
1301 typename _OutputIterator
, typename _BinaryOperation
>
1302 inline _OutputIterator
1303 transform(_IIter1 __begin1
, _IIter1 __end1
,
1304 _IIter2 __begin2
, _OutputIterator __result
,
1305 _BinaryOperation __binary_op
, __gnu_parallel::sequential_tag
)
1306 { return _GLIBCXX_STD_A::transform(__begin1
, __end1
,
1307 __begin2
, __result
, __binary_op
); }
1309 // Parallel binary transform for random access iterators.
1310 template<typename _RAIter1
, typename _RAIter2
,
1311 typename _RAIter3
, typename _BinaryOperation
>
1313 __transform2_switch(_RAIter1 __begin1
, _RAIter1 __end1
,
1315 _RAIter3 __result
, _BinaryOperation __binary_op
,
1316 random_access_iterator_tag
, random_access_iterator_tag
,
1317 random_access_iterator_tag
,
1318 __gnu_parallel::_Parallelism __parallelism_tag
1319 = __gnu_parallel::parallel_balanced
)
1321 if (_GLIBCXX_PARALLEL_CONDITION(
1322 (__end1
- __begin1
) >=
1323 __gnu_parallel::_Settings::get().transform_minimal_n
1324 && __gnu_parallel::__is_parallel(__parallelism_tag
)))
1326 bool __dummy
= true;
1327 typedef __gnu_parallel::_IteratorTriple
<_RAIter1
,
1329 random_access_iterator_tag
> _ItTrip
;
1330 _ItTrip
__begin_triple(__begin1
, __begin2
, __result
),
1331 __end_triple(__end1
, __begin2
+ (__end1
- __begin1
),
1332 __result
+ (__end1
- __begin1
));
1333 __gnu_parallel::__transform2_selector
<_ItTrip
> __functionality
;
1335 __for_each_template_random_access(__begin_triple
, __end_triple
,
1336 __binary_op
, __functionality
,
1337 __gnu_parallel::_DummyReduct(),
1338 __dummy
, __dummy
, -1,
1340 return __functionality
._M_finish_iterator
;
1343 return transform(__begin1
, __end1
, __begin2
, __result
, __binary_op
,
1344 __gnu_parallel::sequential_tag());
1347 // Sequential fallback for input iterator case.
1348 template<typename _IIter1
, typename _IIter2
,
1349 typename _OutputIterator
, typename _BinaryOperation
,
1350 typename _Tag1
, typename _Tag2
, typename _Tag3
>
1351 inline _OutputIterator
1352 __transform2_switch(_IIter1 __begin1
, _IIter1 __end1
,
1353 _IIter2 __begin2
, _OutputIterator __result
,
1354 _BinaryOperation __binary_op
, _Tag1
, _Tag2
, _Tag3
)
1355 { return transform(__begin1
, __end1
, __begin2
, __result
, __binary_op
,
1356 __gnu_parallel::sequential_tag()); }
1358 // Public interface.
1359 template<typename _IIter1
, typename _IIter2
,
1360 typename _OutputIterator
, typename _BinaryOperation
>
1361 inline _OutputIterator
1362 transform(_IIter1 __begin1
, _IIter1 __end1
,
1363 _IIter2 __begin2
, _OutputIterator __result
,
1364 _BinaryOperation __binary_op
,
1365 __gnu_parallel::_Parallelism __parallelism_tag
)
1367 typedef std::iterator_traits
<_IIter1
> _IIterTraits1
;
1368 typedef typename
_IIterTraits1::iterator_category
1370 typedef std::iterator_traits
<_IIter2
> _IIterTraits2
;
1371 typedef typename
_IIterTraits2::iterator_category
1373 typedef std::iterator_traits
<_OutputIterator
> _OIterTraits
;
1374 typedef typename
_OIterTraits::iterator_category _OIterCategory
;
1376 return __transform2_switch(
1377 __begin1
, __end1
, __begin2
, __result
, __binary_op
,
1378 _IIterCategory1(), _IIterCategory2(), _OIterCategory(),
1382 template<typename _IIter1
, typename _IIter2
,
1383 typename _OutputIterator
, typename _BinaryOperation
>
1384 inline _OutputIterator
1385 transform(_IIter1 __begin1
, _IIter1 __end1
,
1386 _IIter2 __begin2
, _OutputIterator __result
,
1387 _BinaryOperation __binary_op
)
1389 typedef std::iterator_traits
<_IIter1
> _IIterTraits1
;
1390 typedef typename
_IIterTraits1::iterator_category
1392 typedef std::iterator_traits
<_IIter2
> _IIterTraits2
;
1393 typedef typename
_IIterTraits2::iterator_category
1395 typedef std::iterator_traits
<_OutputIterator
> _OIterTraits
;
1396 typedef typename
_OIterTraits::iterator_category _OIterCategory
;
1398 return __transform2_switch(
1399 __begin1
, __end1
, __begin2
, __result
, __binary_op
,
1400 _IIterCategory1(), _IIterCategory2(), _OIterCategory());
1403 // Sequential fallback
1404 template<typename _FIterator
, typename _Tp
>
1406 replace(_FIterator __begin
, _FIterator __end
, const _Tp
& __old_value
,
1407 const _Tp
& __new_value
, __gnu_parallel::sequential_tag
)
1408 { _GLIBCXX_STD_A::replace(__begin
, __end
, __old_value
, __new_value
); }
1410 // Sequential fallback for input iterator case
1411 template<typename _FIterator
, typename _Tp
, typename _IteratorTag
>
1413 __replace_switch(_FIterator __begin
, _FIterator __end
,
1414 const _Tp
& __old_value
, const _Tp
& __new_value
,
1416 { replace(__begin
, __end
, __old_value
, __new_value
,
1417 __gnu_parallel::sequential_tag()); }
1419 // Parallel replace for random access iterators
1420 template<typename _RAIter
, typename _Tp
>
1422 __replace_switch(_RAIter __begin
, _RAIter __end
,
1423 const _Tp
& __old_value
, const _Tp
& __new_value
,
1424 random_access_iterator_tag
,
1425 __gnu_parallel::_Parallelism __parallelism_tag
1426 = __gnu_parallel::parallel_balanced
)
1428 // XXX parallel version is where?
1429 replace(__begin
, __end
, __old_value
, __new_value
,
1430 __gnu_parallel::sequential_tag());
1434 template<typename _FIterator
, typename _Tp
>
1436 replace(_FIterator __begin
, _FIterator __end
, const _Tp
& __old_value
,
1437 const _Tp
& __new_value
,
1438 __gnu_parallel::_Parallelism __parallelism_tag
)
1440 typedef iterator_traits
<_FIterator
> _TraitsType
;
1441 typedef typename
_TraitsType::iterator_category _IteratorCategory
;
1442 __replace_switch(__begin
, __end
, __old_value
, __new_value
,
1443 _IteratorCategory(),
1447 template<typename _FIterator
, typename _Tp
>
1449 replace(_FIterator __begin
, _FIterator __end
, const _Tp
& __old_value
,
1450 const _Tp
& __new_value
)
1452 typedef iterator_traits
<_FIterator
> _TraitsType
;
1453 typedef typename
_TraitsType::iterator_category _IteratorCategory
;
1454 __replace_switch(__begin
, __end
, __old_value
, __new_value
,
1455 _IteratorCategory());
1459 // Sequential fallback
1460 template<typename _FIterator
, typename _Predicate
, typename _Tp
>
1462 replace_if(_FIterator __begin
, _FIterator __end
, _Predicate __pred
,
1463 const _Tp
& __new_value
, __gnu_parallel::sequential_tag
)
1464 { _GLIBCXX_STD_A::replace_if(__begin
, __end
, __pred
, __new_value
); }
1466 // Sequential fallback for input iterator case
1467 template<typename _FIterator
, typename _Predicate
, typename _Tp
,
1468 typename _IteratorTag
>
1470 __replace_if_switch(_FIterator __begin
, _FIterator __end
,
1471 _Predicate __pred
, const _Tp
& __new_value
, _IteratorTag
)
1472 { replace_if(__begin
, __end
, __pred
, __new_value
,
1473 __gnu_parallel::sequential_tag()); }
1475 // Parallel algorithm for random access iterators.
1476 template<typename _RAIter
, typename _Predicate
, typename _Tp
>
1478 __replace_if_switch(_RAIter __begin
, _RAIter __end
,
1479 _Predicate __pred
, const _Tp
& __new_value
,
1480 random_access_iterator_tag
,
1481 __gnu_parallel::_Parallelism __parallelism_tag
1482 = __gnu_parallel::parallel_balanced
)
1484 if (_GLIBCXX_PARALLEL_CONDITION(
1485 static_cast<__gnu_parallel::_SequenceIndex
>(__end
- __begin
)
1486 >= __gnu_parallel::_Settings::get().replace_minimal_n
1487 && __gnu_parallel::__is_parallel(__parallelism_tag
)))
1491 __replace_if_selector
<_RAIter
, _Predicate
, _Tp
>
1492 __functionality(__new_value
);
1494 __for_each_template_random_access(
1495 __begin
, __end
, __pred
, __functionality
,
1496 __gnu_parallel::_DummyReduct(),
1497 true, __dummy
, -1, __parallelism_tag
);
1500 replace_if(__begin
, __end
, __pred
, __new_value
,
1501 __gnu_parallel::sequential_tag());
1504 // Public interface.
1505 template<typename _FIterator
, typename _Predicate
, typename _Tp
>
1507 replace_if(_FIterator __begin
, _FIterator __end
,
1508 _Predicate __pred
, const _Tp
& __new_value
,
1509 __gnu_parallel::_Parallelism __parallelism_tag
)
1511 typedef std::iterator_traits
<_FIterator
> _IteratorTraits
;
1512 typedef typename
_IteratorTraits::iterator_category _IteratorCategory
;
1513 __replace_if_switch(__begin
, __end
, __pred
, __new_value
,
1514 _IteratorCategory(), __parallelism_tag
);
1517 template<typename _FIterator
, typename _Predicate
, typename _Tp
>
1519 replace_if(_FIterator __begin
, _FIterator __end
,
1520 _Predicate __pred
, const _Tp
& __new_value
)
1522 typedef std::iterator_traits
<_FIterator
> _IteratorTraits
;
1523 typedef typename
_IteratorTraits::iterator_category _IteratorCategory
;
1524 __replace_if_switch(__begin
, __end
, __pred
, __new_value
,
1525 _IteratorCategory());
1528 // Sequential fallback
1529 template<typename _FIterator
, typename _Generator
>
1531 generate(_FIterator __begin
, _FIterator __end
, _Generator __gen
,
1532 __gnu_parallel::sequential_tag
)
1533 { _GLIBCXX_STD_A::generate(__begin
, __end
, __gen
); }
1535 // Sequential fallback for input iterator case.
1536 template<typename _FIterator
, typename _Generator
, typename _IteratorTag
>
1538 __generate_switch(_FIterator __begin
, _FIterator __end
, _Generator __gen
,
1540 { generate(__begin
, __end
, __gen
, __gnu_parallel::sequential_tag()); }
1542 // Parallel algorithm for random access iterators.
1543 template<typename _RAIter
, typename _Generator
>
1545 __generate_switch(_RAIter __begin
, _RAIter __end
,
1546 _Generator __gen
, random_access_iterator_tag
,
1547 __gnu_parallel::_Parallelism __parallelism_tag
1548 = __gnu_parallel::parallel_balanced
)
1550 if (_GLIBCXX_PARALLEL_CONDITION(
1551 static_cast<__gnu_parallel::_SequenceIndex
>(__end
- __begin
)
1552 >= __gnu_parallel::_Settings::get().generate_minimal_n
1553 && __gnu_parallel::__is_parallel(__parallelism_tag
)))
1556 __gnu_parallel::__generate_selector
<_RAIter
>
1559 __for_each_template_random_access(
1560 __begin
, __end
, __gen
, __functionality
,
1561 __gnu_parallel::_DummyReduct(),
1562 true, __dummy
, -1, __parallelism_tag
);
1565 generate(__begin
, __end
, __gen
, __gnu_parallel::sequential_tag());
1568 // Public interface.
1569 template<typename _FIterator
, typename _Generator
>
1571 generate(_FIterator __begin
, _FIterator __end
,
1572 _Generator __gen
, __gnu_parallel::_Parallelism __parallelism_tag
)
1574 typedef std::iterator_traits
<_FIterator
> _IteratorTraits
;
1575 typedef typename
_IteratorTraits::iterator_category _IteratorCategory
;
1576 __generate_switch(__begin
, __end
, __gen
, _IteratorCategory(),
1580 template<typename _FIterator
, typename _Generator
>
1582 generate(_FIterator __begin
, _FIterator __end
, _Generator __gen
)
1584 typedef std::iterator_traits
<_FIterator
> _IteratorTraits
;
1585 typedef typename
_IteratorTraits::iterator_category _IteratorCategory
;
1586 __generate_switch(__begin
, __end
, __gen
, _IteratorCategory());
1590 // Sequential fallback.
1591 template<typename _OutputIterator
, typename _Size
, typename _Generator
>
1592 inline _OutputIterator
1593 generate_n(_OutputIterator __begin
, _Size __n
, _Generator __gen
,
1594 __gnu_parallel::sequential_tag
)
1595 { return _GLIBCXX_STD_A::generate_n(__begin
, __n
, __gen
); }
1597 // Sequential fallback for input iterator case.
1598 template<typename _OutputIterator
, typename _Size
, typename _Generator
,
1599 typename _IteratorTag
>
1600 inline _OutputIterator
1601 __generate_n_switch(_OutputIterator __begin
, _Size __n
, _Generator __gen
,
1603 { return generate_n(__begin
, __n
, __gen
,
1604 __gnu_parallel::sequential_tag()); }
1606 // Parallel algorithm for random access iterators.
1607 template<typename _RAIter
, typename _Size
, typename _Generator
>
1609 __generate_n_switch(_RAIter __begin
, _Size __n
, _Generator __gen
,
1610 random_access_iterator_tag
,
1611 __gnu_parallel::_Parallelism __parallelism_tag
1612 = __gnu_parallel::parallel_balanced
)
1614 // XXX parallel version is where?
1615 return generate_n(__begin
, __n
, __gen
, __gnu_parallel::sequential_tag());
1618 // Public interface.
1619 template<typename _OutputIterator
, typename _Size
, typename _Generator
>
1620 inline _OutputIterator
1621 generate_n(_OutputIterator __begin
, _Size __n
, _Generator __gen
,
1622 __gnu_parallel::_Parallelism __parallelism_tag
)
1624 typedef std::iterator_traits
<_OutputIterator
> _IteratorTraits
;
1625 typedef typename
_IteratorTraits::iterator_category _IteratorCategory
;
1626 return __generate_n_switch(__begin
, __n
, __gen
, _IteratorCategory(),
1630 template<typename _OutputIterator
, typename _Size
, typename _Generator
>
1631 inline _OutputIterator
1632 generate_n(_OutputIterator __begin
, _Size __n
, _Generator __gen
)
1634 typedef std::iterator_traits
<_OutputIterator
> _IteratorTraits
;
1635 typedef typename
_IteratorTraits::iterator_category _IteratorCategory
;
1636 return __generate_n_switch(__begin
, __n
, __gen
, _IteratorCategory());
1640 // Sequential fallback.
1641 template<typename _RAIter
>
1643 random_shuffle(_RAIter __begin
, _RAIter __end
,
1644 __gnu_parallel::sequential_tag
)
1645 { _GLIBCXX_STD_A::random_shuffle(__begin
, __end
); }
1647 // Sequential fallback.
1648 template<typename _RAIter
, typename _RandomNumberGenerator
>
1650 random_shuffle(_RAIter __begin
, _RAIter __end
,
1651 _RandomNumberGenerator
& __rand
,
1652 __gnu_parallel::sequential_tag
)
1653 { _GLIBCXX_STD_A::random_shuffle(__begin
, __end
, __rand
); }
1656 /** @brief Functor wrapper for std::rand(). */
1657 template<typename _MustBeInt
= int>
1661 operator()(int __limit
)
1662 { return rand() % __limit
; }
1665 // Fill in random number generator.
1666 template<typename _RAIter
>
1668 random_shuffle(_RAIter __begin
, _RAIter __end
)
1671 // Parallelization still possible.
1672 __gnu_parallel::random_shuffle(__begin
, __end
, __r
);
1675 // Parallel algorithm for random access iterators.
1676 template<typename _RAIter
, typename _RandomNumberGenerator
>
1678 random_shuffle(_RAIter __begin
, _RAIter __end
,
1679 #if __cplusplus >= 201103L
1680 _RandomNumberGenerator
&& __rand
)
1682 _RandomNumberGenerator
& __rand
)
1685 if (__begin
== __end
)
1687 if (_GLIBCXX_PARALLEL_CONDITION(
1688 static_cast<__gnu_parallel::_SequenceIndex
>(__end
- __begin
)
1689 >= __gnu_parallel::_Settings::get().random_shuffle_minimal_n
))
1690 __gnu_parallel::__parallel_random_shuffle(__begin
, __end
, __rand
);
1692 __gnu_parallel::__sequential_random_shuffle(__begin
, __end
, __rand
);
1695 // Sequential fallback.
1696 template<typename _FIterator
, typename _Predicate
>
1698 partition(_FIterator __begin
, _FIterator __end
,
1699 _Predicate __pred
, __gnu_parallel::sequential_tag
)
1700 { return _GLIBCXX_STD_A::partition(__begin
, __end
, __pred
); }
1702 // Sequential fallback for input iterator case.
1703 template<typename _FIterator
, typename _Predicate
, typename _IteratorTag
>
1705 __partition_switch(_FIterator __begin
, _FIterator __end
,
1706 _Predicate __pred
, _IteratorTag
)
1707 { return partition(__begin
, __end
, __pred
,
1708 __gnu_parallel::sequential_tag()); }
1710 // Parallel algorithm for random access iterators.
1711 template<typename _RAIter
, typename _Predicate
>
1713 __partition_switch(_RAIter __begin
, _RAIter __end
,
1714 _Predicate __pred
, random_access_iterator_tag
)
1716 if (_GLIBCXX_PARALLEL_CONDITION(
1717 static_cast<__gnu_parallel::_SequenceIndex
>(__end
- __begin
)
1718 >= __gnu_parallel::_Settings::get().partition_minimal_n
))
1720 typedef typename
std::iterator_traits
<_RAIter
>::
1721 difference_type _DifferenceType
;
1722 _DifferenceType __middle
= __gnu_parallel::
1723 __parallel_partition(__begin
, __end
, __pred
,
1724 __gnu_parallel::__get_max_threads());
1725 return __begin
+ __middle
;
1728 return partition(__begin
, __end
, __pred
,
1729 __gnu_parallel::sequential_tag());
1732 // Public interface.
1733 template<typename _FIterator
, typename _Predicate
>
1735 partition(_FIterator __begin
, _FIterator __end
, _Predicate __pred
)
1737 typedef iterator_traits
<_FIterator
> _TraitsType
;
1738 typedef typename
_TraitsType::iterator_category _IteratorCategory
;
1739 return __partition_switch(__begin
, __end
, __pred
, _IteratorCategory());
1744 // Sequential fallback
1745 template<typename _RAIter
>
1747 sort(_RAIter __begin
, _RAIter __end
,
1748 __gnu_parallel::sequential_tag
)
1749 { _GLIBCXX_STD_A::sort(__begin
, __end
); }
1751 // Sequential fallback
1752 template<typename _RAIter
, typename _Compare
>
1754 sort(_RAIter __begin
, _RAIter __end
, _Compare __comp
,
1755 __gnu_parallel::sequential_tag
)
1756 { _GLIBCXX_STD_A::sort
<_RAIter
, _Compare
>(__begin
, __end
,
1760 template<typename _RAIter
, typename _Compare
,
1761 typename _Parallelism
>
1763 sort(_RAIter __begin
, _RAIter __end
, _Compare __comp
,
1764 _Parallelism __parallelism
)
1766 typedef iterator_traits
<_RAIter
> _TraitsType
;
1767 typedef typename
_TraitsType::value_type _ValueType
;
1769 if (__begin
!= __end
)
1771 if (_GLIBCXX_PARALLEL_CONDITION(
1772 static_cast<__gnu_parallel::_SequenceIndex
>(__end
- __begin
) >=
1773 __gnu_parallel::_Settings::get().sort_minimal_n
))
1774 __gnu_parallel::__parallel_sort
<false>(
1775 __begin
, __end
, __comp
, __parallelism
);
1777 sort(__begin
, __end
, __comp
, __gnu_parallel::sequential_tag());
1781 // Public interface, insert default comparator
1782 template<typename _RAIter
>
1784 sort(_RAIter __begin
, _RAIter __end
)
1786 typedef iterator_traits
<_RAIter
> _TraitsType
;
1787 typedef typename
_TraitsType::value_type _ValueType
;
1788 sort(__begin
, __end
, std::less
<_ValueType
>(),
1789 __gnu_parallel::default_parallel_tag());
1792 // Public interface, insert default comparator
1793 template<typename _RAIter
>
1795 sort(_RAIter __begin
, _RAIter __end
,
1796 __gnu_parallel::default_parallel_tag __parallelism
)
1798 typedef iterator_traits
<_RAIter
> _TraitsType
;
1799 typedef typename
_TraitsType::value_type _ValueType
;
1800 sort(__begin
, __end
, std::less
<_ValueType
>(), __parallelism
);
1803 // Public interface, insert default comparator
1804 template<typename _RAIter
>
1806 sort(_RAIter __begin
, _RAIter __end
,
1807 __gnu_parallel::parallel_tag __parallelism
)
1809 typedef iterator_traits
<_RAIter
> _TraitsType
;
1810 typedef typename
_TraitsType::value_type _ValueType
;
1811 sort(__begin
, __end
, std::less
<_ValueType
>(), __parallelism
);
1814 // Public interface, insert default comparator
1815 template<typename _RAIter
>
1817 sort(_RAIter __begin
, _RAIter __end
,
1818 __gnu_parallel::multiway_mergesort_tag __parallelism
)
1820 typedef iterator_traits
<_RAIter
> _TraitsType
;
1821 typedef typename
_TraitsType::value_type _ValueType
;
1822 sort(__begin
, __end
, std::less
<_ValueType
>(), __parallelism
);
1825 // Public interface, insert default comparator
1826 template<typename _RAIter
>
1828 sort(_RAIter __begin
, _RAIter __end
,
1829 __gnu_parallel::multiway_mergesort_sampling_tag __parallelism
)
1831 typedef iterator_traits
<_RAIter
> _TraitsType
;
1832 typedef typename
_TraitsType::value_type _ValueType
;
1833 sort(__begin
, __end
, std::less
<_ValueType
>(), __parallelism
);
1836 // Public interface, insert default comparator
1837 template<typename _RAIter
>
1839 sort(_RAIter __begin
, _RAIter __end
,
1840 __gnu_parallel::multiway_mergesort_exact_tag __parallelism
)
1842 typedef iterator_traits
<_RAIter
> _TraitsType
;
1843 typedef typename
_TraitsType::value_type _ValueType
;
1844 sort(__begin
, __end
, std::less
<_ValueType
>(), __parallelism
);
1847 // Public interface, insert default comparator
1848 template<typename _RAIter
>
1850 sort(_RAIter __begin
, _RAIter __end
,
1851 __gnu_parallel::quicksort_tag __parallelism
)
1853 typedef iterator_traits
<_RAIter
> _TraitsType
;
1854 typedef typename
_TraitsType::value_type _ValueType
;
1855 sort(__begin
, __end
, std::less
<_ValueType
>(), __parallelism
);
1858 // Public interface, insert default comparator
1859 template<typename _RAIter
>
1861 sort(_RAIter __begin
, _RAIter __end
,
1862 __gnu_parallel::balanced_quicksort_tag __parallelism
)
1864 typedef iterator_traits
<_RAIter
> _TraitsType
;
1865 typedef typename
_TraitsType::value_type _ValueType
;
1866 sort(__begin
, __end
, std::less
<_ValueType
>(), __parallelism
);
1870 template<typename _RAIter
, typename _Compare
>
1872 sort(_RAIter __begin
, _RAIter __end
, _Compare __comp
)
1874 typedef iterator_traits
<_RAIter
> _TraitsType
;
1875 typedef typename
_TraitsType::value_type _ValueType
;
1876 sort(__begin
, __end
, __comp
, __gnu_parallel::default_parallel_tag());
1880 // stable_sort interface
1883 // Sequential fallback
1884 template<typename _RAIter
>
1886 stable_sort(_RAIter __begin
, _RAIter __end
,
1887 __gnu_parallel::sequential_tag
)
1888 { _GLIBCXX_STD_A::stable_sort(__begin
, __end
); }
1890 // Sequential fallback
1891 template<typename _RAIter
, typename _Compare
>
1893 stable_sort(_RAIter __begin
, _RAIter __end
,
1894 _Compare __comp
, __gnu_parallel::sequential_tag
)
1895 { _GLIBCXX_STD_A::stable_sort
<_RAIter
, _Compare
>(
1896 __begin
, __end
, __comp
); }
1899 template<typename _RAIter
, typename _Compare
,
1900 typename _Parallelism
>
1902 stable_sort(_RAIter __begin
, _RAIter __end
,
1903 _Compare __comp
, _Parallelism __parallelism
)
1905 typedef iterator_traits
<_RAIter
> _TraitsType
;
1906 typedef typename
_TraitsType::value_type _ValueType
;
1908 if (__begin
!= __end
)
1910 if (_GLIBCXX_PARALLEL_CONDITION(
1911 static_cast<__gnu_parallel::_SequenceIndex
>(__end
- __begin
) >=
1912 __gnu_parallel::_Settings::get().sort_minimal_n
))
1913 __gnu_parallel::__parallel_sort
<true>(
1914 __begin
, __end
, __comp
, __parallelism
);
1916 stable_sort(__begin
, __end
, __comp
,
1917 __gnu_parallel::sequential_tag());
1921 // Public interface, insert default comparator
1922 template<typename _RAIter
>
1924 stable_sort(_RAIter __begin
, _RAIter __end
)
1926 typedef iterator_traits
<_RAIter
> _TraitsType
;
1927 typedef typename
_TraitsType::value_type _ValueType
;
1928 stable_sort(__begin
, __end
, std::less
<_ValueType
>(),
1929 __gnu_parallel::default_parallel_tag());
1932 // Public interface, insert default comparator
1933 template<typename _RAIter
>
1935 stable_sort(_RAIter __begin
, _RAIter __end
,
1936 __gnu_parallel::default_parallel_tag __parallelism
)
1938 typedef iterator_traits
<_RAIter
> _TraitsType
;
1939 typedef typename
_TraitsType::value_type _ValueType
;
1940 stable_sort(__begin
, __end
, std::less
<_ValueType
>(), __parallelism
);
1943 // Public interface, insert default comparator
1944 template<typename _RAIter
>
1946 stable_sort(_RAIter __begin
, _RAIter __end
,
1947 __gnu_parallel::parallel_tag __parallelism
)
1949 typedef iterator_traits
<_RAIter
> _TraitsType
;
1950 typedef typename
_TraitsType::value_type _ValueType
;
1951 stable_sort(__begin
, __end
, std::less
<_ValueType
>(), __parallelism
);
1954 // Public interface, insert default comparator
1955 template<typename _RAIter
>
1957 stable_sort(_RAIter __begin
, _RAIter __end
,
1958 __gnu_parallel::multiway_mergesort_tag __parallelism
)
1960 typedef iterator_traits
<_RAIter
> _TraitsType
;
1961 typedef typename
_TraitsType::value_type _ValueType
;
1962 stable_sort(__begin
, __end
, std::less
<_ValueType
>(), __parallelism
);
1965 // Public interface, insert default comparator
1966 template<typename _RAIter
>
1968 stable_sort(_RAIter __begin
, _RAIter __end
,
1969 __gnu_parallel::quicksort_tag __parallelism
)
1971 typedef iterator_traits
<_RAIter
> _TraitsType
;
1972 typedef typename
_TraitsType::value_type _ValueType
;
1973 stable_sort(__begin
, __end
, std::less
<_ValueType
>(), __parallelism
);
1976 // Public interface, insert default comparator
1977 template<typename _RAIter
>
1979 stable_sort(_RAIter __begin
, _RAIter __end
,
1980 __gnu_parallel::balanced_quicksort_tag __parallelism
)
1982 typedef iterator_traits
<_RAIter
> _TraitsType
;
1983 typedef typename
_TraitsType::value_type _ValueType
;
1984 stable_sort(__begin
, __end
, std::less
<_ValueType
>(), __parallelism
);
1988 template<typename _RAIter
, typename _Compare
>
1990 stable_sort(_RAIter __begin
, _RAIter __end
,
1993 typedef iterator_traits
<_RAIter
> _TraitsType
;
1994 typedef typename
_TraitsType::value_type _ValueType
;
1996 __begin
, __end
, __comp
, __gnu_parallel::default_parallel_tag());
1999 // Sequential fallback
2000 template<typename _IIter1
, typename _IIter2
,
2001 typename _OutputIterator
>
2002 inline _OutputIterator
2003 merge(_IIter1 __begin1
, _IIter1 __end1
, _IIter2 __begin2
,
2004 _IIter2 __end2
, _OutputIterator __result
,
2005 __gnu_parallel::sequential_tag
)
2006 { return _GLIBCXX_STD_A::merge(
2007 __begin1
, __end1
, __begin2
, __end2
, __result
); }
2009 // Sequential fallback
2010 template<typename _IIter1
, typename _IIter2
,
2011 typename _OutputIterator
, typename _Compare
>
2012 inline _OutputIterator
2013 merge(_IIter1 __begin1
, _IIter1 __end1
, _IIter2 __begin2
,
2014 _IIter2 __end2
, _OutputIterator __result
, _Compare __comp
,
2015 __gnu_parallel::sequential_tag
)
2016 { return _GLIBCXX_STD_A::merge(
2017 __begin1
, __end1
, __begin2
, __end2
, __result
, __comp
); }
2019 // Sequential fallback for input iterator case
2020 template<typename _IIter1
, typename _IIter2
, typename _OutputIterator
,
2021 typename _Compare
, typename _IteratorTag1
,
2022 typename _IteratorTag2
, typename _IteratorTag3
>
2023 inline _OutputIterator
2024 __merge_switch(_IIter1 __begin1
, _IIter1 __end1
,
2025 _IIter2 __begin2
, _IIter2 __end2
,
2026 _OutputIterator __result
, _Compare __comp
,
2027 _IteratorTag1
, _IteratorTag2
, _IteratorTag3
)
2028 { return _GLIBCXX_STD_A::merge(__begin1
, __end1
, __begin2
, __end2
,
2029 __result
, __comp
); }
2031 // Parallel algorithm for random access iterators
2032 template<typename _IIter1
, typename _IIter2
,
2033 typename _OutputIterator
, typename _Compare
>
2035 __merge_switch(_IIter1 __begin1
, _IIter1 __end1
,
2036 _IIter2 __begin2
, _IIter2 __end2
,
2037 _OutputIterator __result
, _Compare __comp
,
2038 random_access_iterator_tag
, random_access_iterator_tag
,
2039 random_access_iterator_tag
)
2041 if (_GLIBCXX_PARALLEL_CONDITION(
2042 (static_cast<__gnu_parallel::_SequenceIndex
>(__end1
- __begin1
)
2043 >= __gnu_parallel::_Settings::get().merge_minimal_n
2044 || static_cast<__gnu_parallel::_SequenceIndex
>(__end2
- __begin2
)
2045 >= __gnu_parallel::_Settings::get().merge_minimal_n
)))
2046 return __gnu_parallel::__parallel_merge_advance(
2047 __begin1
, __end1
, __begin2
, __end2
, __result
,
2048 (__end1
- __begin1
) + (__end2
- __begin2
), __comp
);
2050 return __gnu_parallel::__merge_advance(
2051 __begin1
, __end1
, __begin2
, __end2
, __result
,
2052 (__end1
- __begin1
) + (__end2
- __begin2
), __comp
);
2056 template<typename _IIter1
, typename _IIter2
,
2057 typename _OutputIterator
, typename _Compare
>
2058 inline _OutputIterator
2059 merge(_IIter1 __begin1
, _IIter1 __end1
, _IIter2 __begin2
,
2060 _IIter2 __end2
, _OutputIterator __result
, _Compare __comp
)
2062 typedef typename iterator_traits
<_IIter1
>::value_type _ValueType
;
2064 typedef std::iterator_traits
<_IIter1
> _IIterTraits1
;
2065 typedef std::iterator_traits
<_IIter2
> _IIterTraits2
;
2066 typedef std::iterator_traits
<_OutputIterator
> _OIterTraits
;
2067 typedef typename
_IIterTraits1::iterator_category
2069 typedef typename
_IIterTraits2::iterator_category
2071 typedef typename
_OIterTraits::iterator_category _OIterCategory
;
2073 return __merge_switch(
2074 __begin1
, __end1
, __begin2
, __end2
, __result
, __comp
,
2075 _IIterCategory1(), _IIterCategory2(), _OIterCategory());
2079 // Public interface, insert default comparator
2080 template<typename _IIter1
, typename _IIter2
,
2081 typename _OutputIterator
>
2082 inline _OutputIterator
2083 merge(_IIter1 __begin1
, _IIter1 __end1
, _IIter2 __begin2
,
2084 _IIter2 __end2
, _OutputIterator __result
)
2086 typedef std::iterator_traits
<_IIter1
> _Iterator1Traits
;
2087 typedef std::iterator_traits
<_IIter2
> _Iterator2Traits
;
2088 typedef typename
_Iterator1Traits::value_type _ValueType1
;
2089 typedef typename
_Iterator2Traits::value_type _ValueType2
;
2091 return __gnu_parallel::merge(__begin1
, __end1
, __begin2
, __end2
,
2092 __result
, __gnu_parallel::_Less
<_ValueType1
, _ValueType2
>());
2095 // Sequential fallback
2096 template<typename _RAIter
>
2098 nth_element(_RAIter __begin
, _RAIter __nth
,
2099 _RAIter __end
, __gnu_parallel::sequential_tag
)
2100 { return _GLIBCXX_STD_A::nth_element(__begin
, __nth
, __end
); }
2102 // Sequential fallback
2103 template<typename _RAIter
, typename _Compare
>
2105 nth_element(_RAIter __begin
, _RAIter __nth
,
2106 _RAIter __end
, _Compare __comp
,
2107 __gnu_parallel::sequential_tag
)
2108 { return _GLIBCXX_STD_A::nth_element(__begin
, __nth
, __end
, __comp
); }
2111 template<typename _RAIter
, typename _Compare
>
2113 nth_element(_RAIter __begin
, _RAIter __nth
,
2114 _RAIter __end
, _Compare __comp
)
2116 if (_GLIBCXX_PARALLEL_CONDITION(
2117 static_cast<__gnu_parallel::_SequenceIndex
>(__end
- __begin
)
2118 >= __gnu_parallel::_Settings::get().nth_element_minimal_n
))
2119 __gnu_parallel::__parallel_nth_element(__begin
, __nth
, __end
, __comp
);
2121 nth_element(__begin
, __nth
, __end
, __comp
,
2122 __gnu_parallel::sequential_tag());
2125 // Public interface, insert default comparator
2126 template<typename _RAIter
>
2128 nth_element(_RAIter __begin
, _RAIter __nth
,
2131 typedef iterator_traits
<_RAIter
> _TraitsType
;
2132 typedef typename
_TraitsType::value_type _ValueType
;
2133 __gnu_parallel::nth_element(__begin
, __nth
, __end
,
2134 std::less
<_ValueType
>());
2137 // Sequential fallback
2138 template<typename _RAIter
, typename _Compare
>
2140 partial_sort(_RAIter __begin
, _RAIter __middle
,
2141 _RAIter __end
, _Compare __comp
,
2142 __gnu_parallel::sequential_tag
)
2143 { _GLIBCXX_STD_A::partial_sort(__begin
, __middle
, __end
, __comp
); }
2145 // Sequential fallback
2146 template<typename _RAIter
>
2148 partial_sort(_RAIter __begin
, _RAIter __middle
,
2149 _RAIter __end
, __gnu_parallel::sequential_tag
)
2150 { _GLIBCXX_STD_A::partial_sort(__begin
, __middle
, __end
); }
2152 // Public interface, parallel algorithm for random access iterators
2153 template<typename _RAIter
, typename _Compare
>
2155 partial_sort(_RAIter __begin
, _RAIter __middle
,
2156 _RAIter __end
, _Compare __comp
)
2158 if (_GLIBCXX_PARALLEL_CONDITION(
2159 static_cast<__gnu_parallel::_SequenceIndex
>(__end
- __begin
)
2160 >= __gnu_parallel::_Settings::get().partial_sort_minimal_n
))
2162 __parallel_partial_sort(__begin
, __middle
, __end
, __comp
);
2164 partial_sort(__begin
, __middle
, __end
, __comp
,
2165 __gnu_parallel::sequential_tag());
2168 // Public interface, insert default comparator
2169 template<typename _RAIter
>
2171 partial_sort(_RAIter __begin
, _RAIter __middle
,
2174 typedef iterator_traits
<_RAIter
> _TraitsType
;
2175 typedef typename
_TraitsType::value_type _ValueType
;
2176 __gnu_parallel::partial_sort(__begin
, __middle
, __end
,
2177 std::less
<_ValueType
>());
2180 // Sequential fallback
2181 template<typename _FIterator
>
2183 max_element(_FIterator __begin
, _FIterator __end
,
2184 __gnu_parallel::sequential_tag
)
2185 { return _GLIBCXX_STD_A::max_element(__begin
, __end
); }
2187 // Sequential fallback
2188 template<typename _FIterator
, typename _Compare
>
2190 max_element(_FIterator __begin
, _FIterator __end
, _Compare __comp
,
2191 __gnu_parallel::sequential_tag
)
2192 { return _GLIBCXX_STD_A::max_element(__begin
, __end
, __comp
); }
2194 // Sequential fallback for input iterator case
2195 template<typename _FIterator
, typename _Compare
, typename _IteratorTag
>
2197 __max_element_switch(_FIterator __begin
, _FIterator __end
,
2198 _Compare __comp
, _IteratorTag
)
2199 { return max_element(__begin
, __end
, __comp
,
2200 __gnu_parallel::sequential_tag()); }
2202 // Parallel algorithm for random access iterators
2203 template<typename _RAIter
, typename _Compare
>
2205 __max_element_switch(_RAIter __begin
, _RAIter __end
,
2206 _Compare __comp
, random_access_iterator_tag
,
2207 __gnu_parallel::_Parallelism __parallelism_tag
2208 = __gnu_parallel::parallel_balanced
)
2210 if (_GLIBCXX_PARALLEL_CONDITION(
2211 static_cast<__gnu_parallel::_SequenceIndex
>(__end
- __begin
)
2212 >= __gnu_parallel::_Settings::get().max_element_minimal_n
2213 && __gnu_parallel::__is_parallel(__parallelism_tag
)))
2215 _RAIter
__res(__begin
);
2216 __gnu_parallel::__identity_selector
<_RAIter
>
2219 __for_each_template_random_access(
2220 __begin
, __end
, __gnu_parallel::_Nothing(), __functionality
,
2221 __gnu_parallel::__max_element_reduct
<_Compare
, _RAIter
>(__comp
),
2222 __res
, __res
, -1, __parallelism_tag
);
2226 return max_element(__begin
, __end
, __comp
,
2227 __gnu_parallel::sequential_tag());
2230 // Public interface, insert default comparator
2231 template<typename _FIterator
>
2233 max_element(_FIterator __begin
, _FIterator __end
,
2234 __gnu_parallel::_Parallelism __parallelism_tag
)
2236 typedef typename iterator_traits
<_FIterator
>::value_type _ValueType
;
2237 return max_element(__begin
, __end
, std::less
<_ValueType
>(),
2241 template<typename _FIterator
>
2243 max_element(_FIterator __begin
, _FIterator __end
)
2245 typedef typename iterator_traits
<_FIterator
>::value_type _ValueType
;
2246 return __gnu_parallel::max_element(__begin
, __end
,
2247 std::less
<_ValueType
>());
2251 template<typename _FIterator
, typename _Compare
>
2253 max_element(_FIterator __begin
, _FIterator __end
, _Compare __comp
,
2254 __gnu_parallel::_Parallelism __parallelism_tag
)
2256 typedef iterator_traits
<_FIterator
> _TraitsType
;
2257 typedef typename
_TraitsType::iterator_category _IteratorCategory
;
2258 return __max_element_switch(__begin
, __end
, __comp
, _IteratorCategory(),
2262 template<typename _FIterator
, typename _Compare
>
2264 max_element(_FIterator __begin
, _FIterator __end
, _Compare __comp
)
2266 typedef iterator_traits
<_FIterator
> _TraitsType
;
2267 typedef typename
_TraitsType::iterator_category _IteratorCategory
;
2268 return __max_element_switch(__begin
, __end
, __comp
, _IteratorCategory());
2272 // Sequential fallback
2273 template<typename _FIterator
>
2275 min_element(_FIterator __begin
, _FIterator __end
,
2276 __gnu_parallel::sequential_tag
)
2277 { return _GLIBCXX_STD_A::min_element(__begin
, __end
); }
2279 // Sequential fallback
2280 template<typename _FIterator
, typename _Compare
>
2282 min_element(_FIterator __begin
, _FIterator __end
, _Compare __comp
,
2283 __gnu_parallel::sequential_tag
)
2284 { return _GLIBCXX_STD_A::min_element(__begin
, __end
, __comp
); }
2286 // Sequential fallback for input iterator case
2287 template<typename _FIterator
, typename _Compare
, typename _IteratorTag
>
2289 __min_element_switch(_FIterator __begin
, _FIterator __end
,
2290 _Compare __comp
, _IteratorTag
)
2291 { return min_element(__begin
, __end
, __comp
,
2292 __gnu_parallel::sequential_tag()); }
2294 // Parallel algorithm for random access iterators
2295 template<typename _RAIter
, typename _Compare
>
2297 __min_element_switch(_RAIter __begin
, _RAIter __end
,
2298 _Compare __comp
, random_access_iterator_tag
,
2299 __gnu_parallel::_Parallelism __parallelism_tag
2300 = __gnu_parallel::parallel_balanced
)
2302 if (_GLIBCXX_PARALLEL_CONDITION(
2303 static_cast<__gnu_parallel::_SequenceIndex
>(__end
- __begin
)
2304 >= __gnu_parallel::_Settings::get().min_element_minimal_n
2305 && __gnu_parallel::__is_parallel(__parallelism_tag
)))
2307 _RAIter
__res(__begin
);
2308 __gnu_parallel::__identity_selector
<_RAIter
>
2311 __for_each_template_random_access(
2312 __begin
, __end
, __gnu_parallel::_Nothing(), __functionality
,
2313 __gnu_parallel::__min_element_reduct
<_Compare
, _RAIter
>(__comp
),
2314 __res
, __res
, -1, __parallelism_tag
);
2318 return min_element(__begin
, __end
, __comp
,
2319 __gnu_parallel::sequential_tag());
2322 // Public interface, insert default comparator
2323 template<typename _FIterator
>
2325 min_element(_FIterator __begin
, _FIterator __end
,
2326 __gnu_parallel::_Parallelism __parallelism_tag
)
2328 typedef typename iterator_traits
<_FIterator
>::value_type _ValueType
;
2329 return min_element(__begin
, __end
, std::less
<_ValueType
>(),
2333 template<typename _FIterator
>
2335 min_element(_FIterator __begin
, _FIterator __end
)
2337 typedef typename iterator_traits
<_FIterator
>::value_type _ValueType
;
2338 return __gnu_parallel::min_element(__begin
, __end
,
2339 std::less
<_ValueType
>());
2343 template<typename _FIterator
, typename _Compare
>
2345 min_element(_FIterator __begin
, _FIterator __end
, _Compare __comp
,
2346 __gnu_parallel::_Parallelism __parallelism_tag
)
2348 typedef iterator_traits
<_FIterator
> _TraitsType
;
2349 typedef typename
_TraitsType::iterator_category _IteratorCategory
;
2350 return __min_element_switch(__begin
, __end
, __comp
, _IteratorCategory(),
2354 template<typename _FIterator
, typename _Compare
>
2356 min_element(_FIterator __begin
, _FIterator __end
, _Compare __comp
)
2358 typedef iterator_traits
<_FIterator
> _TraitsType
;
2359 typedef typename
_TraitsType::iterator_category _IteratorCategory
;
2360 return __min_element_switch(__begin
, __end
, __comp
, _IteratorCategory());
2365 #endif /* _GLIBCXX_PARALLEL_ALGO_H */