3 // Copyright (C) 2007, 2008, 2009, 2010 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 std::binder2nd
<__gnu_parallel::_EqualTo
<_ValueType
, const _Tp
&> >
154 __comp(__gnu_parallel::_EqualTo
<_ValueType
, const _Tp
&>(), __val
);
155 return __gnu_parallel::__find_template(
156 __begin
, __end
, __begin
, __comp
,
157 __gnu_parallel::__find_if_selector()).first
;
160 return _GLIBCXX_STD_A::find(__begin
, __end
, __val
);
164 template<typename _IIter
, typename _Tp
>
166 find(_IIter __begin
, _IIter __end
, const _Tp
& __val
)
168 typedef std::iterator_traits
<_IIter
> _IteratorTraits
;
169 typedef typename
_IteratorTraits::iterator_category _IteratorCategory
;
170 return __find_switch(__begin
, __end
, __val
, _IteratorCategory());
173 // Sequential fallback
174 template<typename _IIter
, typename _Predicate
>
176 find_if(_IIter __begin
, _IIter __end
, _Predicate __pred
,
177 __gnu_parallel::sequential_tag
)
178 { return _GLIBCXX_STD_A::find_if(__begin
, __end
, __pred
); }
180 // Sequential fallback for input iterator case
181 template<typename _IIter
, typename _Predicate
, typename _IteratorTag
>
183 __find_if_switch(_IIter __begin
, _IIter __end
, _Predicate __pred
,
185 { return _GLIBCXX_STD_A::find_if(__begin
, __end
, __pred
); }
187 // Parallel find_if for random access iterators
188 template<typename _RAIter
, typename _Predicate
>
190 __find_if_switch(_RAIter __begin
, _RAIter __end
,
191 _Predicate __pred
, random_access_iterator_tag
)
193 if (_GLIBCXX_PARALLEL_CONDITION(true))
194 return __gnu_parallel::__find_template(__begin
, __end
, __begin
, __pred
,
196 __find_if_selector()).first
;
198 return _GLIBCXX_STD_A::find_if(__begin
, __end
, __pred
);
202 template<typename _IIter
, typename _Predicate
>
204 find_if(_IIter __begin
, _IIter __end
, _Predicate __pred
)
206 typedef std::iterator_traits
<_IIter
> _IteratorTraits
;
207 typedef typename
_IteratorTraits::iterator_category _IteratorCategory
;
208 return __find_if_switch(__begin
, __end
, __pred
, _IteratorCategory());
211 // Sequential fallback
212 template<typename _IIter
, typename _FIterator
>
214 find_first_of(_IIter __begin1
, _IIter __end1
,
215 _FIterator __begin2
, _FIterator __end2
,
216 __gnu_parallel::sequential_tag
)
217 { return _GLIBCXX_STD_A::find_first_of(__begin1
, __end1
, __begin2
, __end2
);
220 // Sequential fallback
221 template<typename _IIter
, typename _FIterator
,
222 typename _BinaryPredicate
>
224 find_first_of(_IIter __begin1
, _IIter __end1
,
225 _FIterator __begin2
, _FIterator __end2
,
226 _BinaryPredicate __comp
, __gnu_parallel::sequential_tag
)
227 { return _GLIBCXX_STD_A::find_first_of(
228 __begin1
, __end1
, __begin2
, __end2
, __comp
); }
230 // Sequential fallback for input iterator type
231 template<typename _IIter
, typename _FIterator
,
232 typename _IteratorTag1
, typename _IteratorTag2
>
234 __find_first_of_switch(_IIter __begin1
, _IIter __end1
,
235 _FIterator __begin2
, _FIterator __end2
,
236 _IteratorTag1
, _IteratorTag2
)
237 { return find_first_of(__begin1
, __end1
, __begin2
, __end2
,
238 __gnu_parallel::sequential_tag()); }
240 // Parallel algorithm for random access iterators
241 template<typename _RAIter
, typename _FIterator
,
242 typename _BinaryPredicate
, typename _IteratorTag
>
244 __find_first_of_switch(_RAIter __begin1
,
246 _FIterator __begin2
, _FIterator __end2
,
247 _BinaryPredicate __comp
, random_access_iterator_tag
,
250 return __gnu_parallel::
251 __find_template(__begin1
, __end1
, __begin1
, __comp
,
252 __gnu_parallel::__find_first_of_selector
253 <_FIterator
>(__begin2
, __end2
)).first
;
256 // Sequential fallback for input iterator type
257 template<typename _IIter
, typename _FIterator
,
258 typename _BinaryPredicate
, typename _IteratorTag1
,
259 typename _IteratorTag2
>
261 __find_first_of_switch(_IIter __begin1
, _IIter __end1
,
262 _FIterator __begin2
, _FIterator __end2
,
263 _BinaryPredicate __comp
, _IteratorTag1
, _IteratorTag2
)
264 { return find_first_of(__begin1
, __end1
, __begin2
, __end2
, __comp
,
265 __gnu_parallel::sequential_tag()); }
268 template<typename _IIter
, typename _FIterator
,
269 typename _BinaryPredicate
>
271 find_first_of(_IIter __begin1
, _IIter __end1
,
272 _FIterator __begin2
, _FIterator __end2
,
273 _BinaryPredicate __comp
)
275 typedef std::iterator_traits
<_IIter
> _IIterTraits
;
276 typedef std::iterator_traits
<_FIterator
> _FIterTraits
;
277 typedef typename
_IIterTraits::iterator_category _IIteratorCategory
;
278 typedef typename
_FIterTraits::iterator_category _FIteratorCategory
;
280 return __find_first_of_switch(__begin1
, __end1
, __begin2
, __end2
, __comp
,
281 _IIteratorCategory(), _FIteratorCategory());
284 // Public interface, insert default comparator
285 template<typename _IIter
, typename _FIterator
>
287 find_first_of(_IIter __begin1
, _IIter __end1
,
288 _FIterator __begin2
, _FIterator __end2
)
290 typedef std::iterator_traits
<_IIter
> _IIterTraits
;
291 typedef std::iterator_traits
<_FIterator
> _FIterTraits
;
292 typedef typename
_IIterTraits::value_type _IValueType
;
293 typedef typename
_FIterTraits::value_type _FValueType
;
295 return __gnu_parallel::find_first_of(__begin1
, __end1
, __begin2
, __end2
,
296 __gnu_parallel::_EqualTo
<_IValueType
, _FValueType
>());
299 // Sequential fallback
300 template<typename _IIter
, typename _OutputIterator
>
301 inline _OutputIterator
302 unique_copy(_IIter __begin1
, _IIter __end1
, _OutputIterator __out
,
303 __gnu_parallel::sequential_tag
)
304 { return _GLIBCXX_STD_A::unique_copy(__begin1
, __end1
, __out
); }
306 // Sequential fallback
307 template<typename _IIter
, typename _OutputIterator
,
309 inline _OutputIterator
310 unique_copy(_IIter __begin1
, _IIter __end1
, _OutputIterator __out
,
311 _Predicate __pred
, __gnu_parallel::sequential_tag
)
312 { return _GLIBCXX_STD_A::unique_copy(__begin1
, __end1
, __out
, __pred
); }
314 // Sequential fallback for input iterator case
315 template<typename _IIter
, typename _OutputIterator
,
316 typename _Predicate
, typename _IteratorTag1
, typename _IteratorTag2
>
317 inline _OutputIterator
318 __unique_copy_switch(_IIter __begin
, _IIter __last
,
319 _OutputIterator __out
, _Predicate __pred
,
320 _IteratorTag1
, _IteratorTag2
)
321 { return _GLIBCXX_STD_A::unique_copy(__begin
, __last
, __out
, __pred
); }
323 // Parallel unique_copy for random access iterators
324 template<typename _RAIter
, typename RandomAccessOutputIterator
,
326 RandomAccessOutputIterator
327 __unique_copy_switch(_RAIter __begin
, _RAIter __last
,
328 RandomAccessOutputIterator __out
, _Predicate __pred
,
329 random_access_iterator_tag
, random_access_iterator_tag
)
331 if (_GLIBCXX_PARALLEL_CONDITION(
332 static_cast<__gnu_parallel::_SequenceIndex
>(__last
- __begin
)
333 > __gnu_parallel::_Settings::get().unique_copy_minimal_n
))
334 return __gnu_parallel::__parallel_unique_copy(
335 __begin
, __last
, __out
, __pred
);
337 return _GLIBCXX_STD_A::unique_copy(__begin
, __last
, __out
, __pred
);
341 template<typename _IIter
, typename _OutputIterator
>
342 inline _OutputIterator
343 unique_copy(_IIter __begin1
, _IIter __end1
, _OutputIterator __out
)
345 typedef std::iterator_traits
<_IIter
> _IIterTraits
;
346 typedef std::iterator_traits
<_OutputIterator
> _OIterTraits
;
347 typedef typename
_IIterTraits::iterator_category _IIteratorCategory
;
348 typedef typename
_IIterTraits::value_type _ValueType
;
349 typedef typename
_OIterTraits::iterator_category _OIterCategory
;
351 return __unique_copy_switch(
352 __begin1
, __end1
, __out
, equal_to
<_ValueType
>(),
353 _IIteratorCategory(), _OIterCategory());
357 template<typename _IIter
, typename _OutputIterator
, typename _Predicate
>
358 inline _OutputIterator
359 unique_copy(_IIter __begin1
, _IIter __end1
, _OutputIterator __out
,
362 typedef std::iterator_traits
<_IIter
> _IIterTraits
;
363 typedef std::iterator_traits
<_OutputIterator
> _OIterTraits
;
364 typedef typename
_IIterTraits::iterator_category _IIteratorCategory
;
365 typedef typename
_OIterTraits::iterator_category _OIterCategory
;
367 return __unique_copy_switch(
368 __begin1
, __end1
, __out
, __pred
,
369 _IIteratorCategory(), _OIterCategory());
372 // Sequential fallback
373 template<typename _IIter1
, typename _IIter2
,
374 typename _OutputIterator
>
375 inline _OutputIterator
376 set_union(_IIter1 __begin1
, _IIter1 __end1
,
377 _IIter2 __begin2
, _IIter2 __end2
,
378 _OutputIterator __out
, __gnu_parallel::sequential_tag
)
379 { return _GLIBCXX_STD_A::set_union(
380 __begin1
, __end1
, __begin2
, __end2
, __out
); }
382 // Sequential fallback
383 template<typename _IIter1
, typename _IIter2
,
384 typename _OutputIterator
, typename _Predicate
>
385 inline _OutputIterator
386 set_union(_IIter1 __begin1
, _IIter1 __end1
,
387 _IIter2 __begin2
, _IIter2 __end2
,
388 _OutputIterator __out
, _Predicate __pred
,
389 __gnu_parallel::sequential_tag
)
390 { return _GLIBCXX_STD_A::set_union(__begin1
, __end1
,
391 __begin2
, __end2
, __out
, __pred
); }
393 // Sequential fallback for input iterator case
394 template<typename _IIter1
, typename _IIter2
, typename _Predicate
,
395 typename _OutputIterator
, typename _IteratorTag1
,
396 typename _IteratorTag2
, typename _IteratorTag3
>
397 inline _OutputIterator
399 _IIter1 __begin1
, _IIter1 __end1
, _IIter2 __begin2
, _IIter2 __end2
,
400 _OutputIterator __result
, _Predicate __pred
,
401 _IteratorTag1
, _IteratorTag2
, _IteratorTag3
)
402 { return _GLIBCXX_STD_A::set_union(__begin1
, __end1
,
403 __begin2
, __end2
, __result
, __pred
); }
405 // Parallel set_union for random access iterators
406 template<typename _RAIter1
, typename _RAIter2
,
407 typename _Output_RAIter
, typename _Predicate
>
409 __set_union_switch(_RAIter1 __begin1
, _RAIter1 __end1
,
410 _RAIter2 __begin2
, _RAIter2 __end2
,
411 _Output_RAIter __result
, _Predicate __pred
,
412 random_access_iterator_tag
, random_access_iterator_tag
,
413 random_access_iterator_tag
)
415 if (_GLIBCXX_PARALLEL_CONDITION(
416 static_cast<__gnu_parallel::_SequenceIndex
>(__end1
- __begin1
)
417 >= __gnu_parallel::_Settings::get().set_union_minimal_n
418 || static_cast<__gnu_parallel::_SequenceIndex
>(__end2
- __begin2
)
419 >= __gnu_parallel::_Settings::get().set_union_minimal_n
))
420 return __gnu_parallel::__parallel_set_union(
421 __begin1
, __end1
, __begin2
, __end2
, __result
, __pred
);
423 return _GLIBCXX_STD_A::set_union(__begin1
, __end1
,
424 __begin2
, __end2
, __result
, __pred
);
428 template<typename _IIter1
, typename _IIter2
,
429 typename _OutputIterator
>
430 inline _OutputIterator
431 set_union(_IIter1 __begin1
, _IIter1 __end1
,
432 _IIter2 __begin2
, _IIter2 __end2
, _OutputIterator __out
)
434 typedef std::iterator_traits
<_IIter1
> _IIterTraits1
;
435 typedef std::iterator_traits
<_IIter2
> _IIterTraits2
;
436 typedef std::iterator_traits
<_OutputIterator
> _OIterTraits
;
437 typedef typename
_IIterTraits1::iterator_category
439 typedef typename
_IIterTraits2::iterator_category
441 typedef typename
_OIterTraits::iterator_category _OIterCategory
;
442 typedef typename
_IIterTraits1::value_type _ValueType1
;
443 typedef typename
_IIterTraits2::value_type _ValueType2
;
445 return __set_union_switch(
446 __begin1
, __end1
, __begin2
, __end2
, __out
,
447 __gnu_parallel::_Less
<_ValueType1
, _ValueType2
>(),
448 _IIterCategory1(), _IIterCategory2(), _OIterCategory());
452 template<typename _IIter1
, typename _IIter2
,
453 typename _OutputIterator
, typename _Predicate
>
454 inline _OutputIterator
455 set_union(_IIter1 __begin1
, _IIter1 __end1
,
456 _IIter2 __begin2
, _IIter2 __end2
,
457 _OutputIterator __out
, _Predicate __pred
)
459 typedef std::iterator_traits
<_IIter1
> _IIterTraits1
;
460 typedef std::iterator_traits
<_IIter2
> _IIterTraits2
;
461 typedef std::iterator_traits
<_OutputIterator
> _OIterTraits
;
462 typedef typename
_IIterTraits1::iterator_category
464 typedef typename
_IIterTraits2::iterator_category
466 typedef typename
_OIterTraits::iterator_category _OIterCategory
;
468 return __set_union_switch(
469 __begin1
, __end1
, __begin2
, __end2
, __out
, __pred
,
470 _IIterCategory1(), _IIterCategory2(), _OIterCategory());
473 // Sequential fallback.
474 template<typename _IIter1
, typename _IIter2
,
475 typename _OutputIterator
>
476 inline _OutputIterator
477 set_intersection(_IIter1 __begin1
, _IIter1 __end1
,
478 _IIter2 __begin2
, _IIter2 __end2
,
479 _OutputIterator __out
, __gnu_parallel::sequential_tag
)
480 { return _GLIBCXX_STD_A::set_intersection(__begin1
, __end1
,
481 __begin2
, __end2
, __out
); }
483 // Sequential fallback.
484 template<typename _IIter1
, typename _IIter2
,
485 typename _OutputIterator
, typename _Predicate
>
486 inline _OutputIterator
487 set_intersection(_IIter1 __begin1
, _IIter1 __end1
,
488 _IIter2 __begin2
, _IIter2 __end2
,
489 _OutputIterator __out
, _Predicate __pred
,
490 __gnu_parallel::sequential_tag
)
491 { return _GLIBCXX_STD_A::set_intersection(
492 __begin1
, __end1
, __begin2
, __end2
, __out
, __pred
); }
494 // Sequential fallback for input iterator case
495 template<typename _IIter1
, typename _IIter2
,
496 typename _Predicate
, typename _OutputIterator
,
497 typename _IteratorTag1
, typename _IteratorTag2
,
498 typename _IteratorTag3
>
499 inline _OutputIterator
500 __set_intersection_switch(_IIter1 __begin1
, _IIter1 __end1
,
501 _IIter2 __begin2
, _IIter2 __end2
,
502 _OutputIterator __result
, _Predicate __pred
,
503 _IteratorTag1
, _IteratorTag2
, _IteratorTag3
)
504 { return _GLIBCXX_STD_A::set_intersection(__begin1
, __end1
, __begin2
,
505 __end2
, __result
, __pred
); }
507 // Parallel set_intersection for random access iterators
508 template<typename _RAIter1
, typename _RAIter2
,
509 typename _Output_RAIter
, typename _Predicate
>
511 __set_intersection_switch(_RAIter1 __begin1
,
515 _Output_RAIter __result
,
517 random_access_iterator_tag
,
518 random_access_iterator_tag
,
519 random_access_iterator_tag
)
521 if (_GLIBCXX_PARALLEL_CONDITION(
522 static_cast<__gnu_parallel::_SequenceIndex
>(__end1
- __begin1
)
523 >= __gnu_parallel::_Settings::get().set_union_minimal_n
524 || static_cast<__gnu_parallel::_SequenceIndex
>(__end2
- __begin2
)
525 >= __gnu_parallel::_Settings::get().set_union_minimal_n
))
526 return __gnu_parallel::__parallel_set_intersection(
527 __begin1
, __end1
, __begin2
, __end2
, __result
, __pred
);
529 return _GLIBCXX_STD_A::set_intersection(
530 __begin1
, __end1
, __begin2
, __end2
, __result
, __pred
);
534 template<typename _IIter1
, typename _IIter2
,
535 typename _OutputIterator
>
536 inline _OutputIterator
537 set_intersection(_IIter1 __begin1
, _IIter1 __end1
,
538 _IIter2 __begin2
, _IIter2 __end2
,
539 _OutputIterator __out
)
541 typedef std::iterator_traits
<_IIter1
> _IIterTraits1
;
542 typedef std::iterator_traits
<_IIter2
> _IIterTraits2
;
543 typedef std::iterator_traits
<_OutputIterator
> _OIterTraits
;
544 typedef typename
_IIterTraits1::iterator_category
546 typedef typename
_IIterTraits2::iterator_category
548 typedef typename
_OIterTraits::iterator_category _OIterCategory
;
549 typedef typename
_IIterTraits1::value_type _ValueType1
;
550 typedef typename
_IIterTraits2::value_type _ValueType2
;
552 return __set_intersection_switch(
553 __begin1
, __end1
, __begin2
, __end2
, __out
,
554 __gnu_parallel::_Less
<_ValueType1
, _ValueType2
>(),
555 _IIterCategory1(), _IIterCategory2(), _OIterCategory());
558 template<typename _IIter1
, typename _IIter2
,
559 typename _OutputIterator
, typename _Predicate
>
560 inline _OutputIterator
561 set_intersection(_IIter1 __begin1
, _IIter1 __end1
,
562 _IIter2 __begin2
, _IIter2 __end2
,
563 _OutputIterator __out
, _Predicate __pred
)
565 typedef std::iterator_traits
<_IIter1
> _IIterTraits1
;
566 typedef std::iterator_traits
<_IIter2
> _IIterTraits2
;
567 typedef std::iterator_traits
<_OutputIterator
> _OIterTraits
;
568 typedef typename
_IIterTraits1::iterator_category
570 typedef typename
_IIterTraits2::iterator_category
572 typedef typename
_OIterTraits::iterator_category _OIterCategory
;
574 return __set_intersection_switch(
575 __begin1
, __end1
, __begin2
, __end2
, __out
, __pred
,
576 _IIterCategory1(), _IIterCategory2(), _OIterCategory());
579 // Sequential fallback
580 template<typename _IIter1
, typename _IIter2
,
581 typename _OutputIterator
>
582 inline _OutputIterator
583 set_symmetric_difference(_IIter1 __begin1
, _IIter1 __end1
,
584 _IIter2 __begin2
, _IIter2 __end2
,
585 _OutputIterator __out
,
586 __gnu_parallel::sequential_tag
)
587 { return _GLIBCXX_STD_A::set_symmetric_difference(
588 __begin1
, __end1
, __begin2
, __end2
, __out
); }
590 // Sequential fallback
591 template<typename _IIter1
, typename _IIter2
,
592 typename _OutputIterator
, typename _Predicate
>
593 inline _OutputIterator
594 set_symmetric_difference(_IIter1 __begin1
, _IIter1 __end1
,
595 _IIter2 __begin2
, _IIter2 __end2
,
596 _OutputIterator __out
, _Predicate __pred
,
597 __gnu_parallel::sequential_tag
)
598 { return _GLIBCXX_STD_A::set_symmetric_difference(
599 __begin1
, __end1
, __begin2
, __end2
, __out
, __pred
); }
601 // Sequential fallback for input iterator case
602 template<typename _IIter1
, typename _IIter2
,
603 typename _Predicate
, typename _OutputIterator
,
604 typename _IteratorTag1
, typename _IteratorTag2
,
605 typename _IteratorTag3
>
606 inline _OutputIterator
607 __set_symmetric_difference_switch(
608 _IIter1 __begin1
, _IIter1 __end1
, _IIter2 __begin2
, _IIter2 __end2
,
609 _OutputIterator __result
, _Predicate __pred
,
610 _IteratorTag1
, _IteratorTag2
, _IteratorTag3
)
611 { return _GLIBCXX_STD_A::set_symmetric_difference(
612 __begin1
, __end1
, __begin2
, __end2
, __result
, __pred
); }
614 // Parallel set_symmetric_difference for random access iterators
615 template<typename _RAIter1
, typename _RAIter2
,
616 typename _Output_RAIter
, typename _Predicate
>
618 __set_symmetric_difference_switch(_RAIter1 __begin1
,
622 _Output_RAIter __result
,
624 random_access_iterator_tag
,
625 random_access_iterator_tag
,
626 random_access_iterator_tag
)
628 if (_GLIBCXX_PARALLEL_CONDITION(
629 static_cast<__gnu_parallel::_SequenceIndex
>(__end1
- __begin1
)
630 >= __gnu_parallel::_Settings::get().set_symmetric_difference_minimal_n
631 || static_cast<__gnu_parallel::_SequenceIndex
>(__end2
- __begin2
)
632 >= __gnu_parallel::_Settings::get().set_symmetric_difference_minimal_n
))
633 return __gnu_parallel::__parallel_set_symmetric_difference(
634 __begin1
, __end1
, __begin2
, __end2
, __result
, __pred
);
636 return _GLIBCXX_STD_A::set_symmetric_difference(
637 __begin1
, __end1
, __begin2
, __end2
, __result
, __pred
);
641 template<typename _IIter1
, typename _IIter2
,
642 typename _OutputIterator
>
643 inline _OutputIterator
644 set_symmetric_difference(_IIter1 __begin1
, _IIter1 __end1
,
645 _IIter2 __begin2
, _IIter2 __end2
,
646 _OutputIterator __out
)
648 typedef std::iterator_traits
<_IIter1
> _IIterTraits1
;
649 typedef std::iterator_traits
<_IIter2
> _IIterTraits2
;
650 typedef std::iterator_traits
<_OutputIterator
> _OIterTraits
;
651 typedef typename
_IIterTraits1::iterator_category
653 typedef typename
_IIterTraits2::iterator_category
655 typedef typename
_OIterTraits::iterator_category _OIterCategory
;
656 typedef typename
_IIterTraits1::value_type _ValueType1
;
657 typedef typename
_IIterTraits2::value_type _ValueType2
;
659 return __set_symmetric_difference_switch(
660 __begin1
, __end1
, __begin2
, __end2
, __out
,
661 __gnu_parallel::_Less
<_ValueType1
, _ValueType2
>(),
662 _IIterCategory1(), _IIterCategory2(), _OIterCategory());
666 template<typename _IIter1
, typename _IIter2
,
667 typename _OutputIterator
, typename _Predicate
>
668 inline _OutputIterator
669 set_symmetric_difference(_IIter1 __begin1
, _IIter1 __end1
,
670 _IIter2 __begin2
, _IIter2 __end2
,
671 _OutputIterator __out
, _Predicate __pred
)
673 typedef std::iterator_traits
<_IIter1
> _IIterTraits1
;
674 typedef std::iterator_traits
<_IIter2
> _IIterTraits2
;
675 typedef std::iterator_traits
<_OutputIterator
> _OIterTraits
;
676 typedef typename
_IIterTraits1::iterator_category
678 typedef typename
_IIterTraits2::iterator_category
680 typedef typename
_OIterTraits::iterator_category _OIterCategory
;
682 return __set_symmetric_difference_switch(
683 __begin1
, __end1
, __begin2
, __end2
, __out
, __pred
,
684 _IIterCategory1(), _IIterCategory2(), _OIterCategory());
687 // Sequential fallback.
688 template<typename _IIter1
, typename _IIter2
,
689 typename _OutputIterator
>
690 inline _OutputIterator
691 set_difference(_IIter1 __begin1
, _IIter1 __end1
,
692 _IIter2 __begin2
, _IIter2 __end2
,
693 _OutputIterator __out
, __gnu_parallel::sequential_tag
)
694 { return _GLIBCXX_STD_A::set_difference(
695 __begin1
,__end1
, __begin2
, __end2
, __out
); }
697 // Sequential fallback.
698 template<typename _IIter1
, typename _IIter2
,
699 typename _OutputIterator
, typename _Predicate
>
700 inline _OutputIterator
701 set_difference(_IIter1 __begin1
, _IIter1 __end1
,
702 _IIter2 __begin2
, _IIter2 __end2
,
703 _OutputIterator __out
, _Predicate __pred
,
704 __gnu_parallel::sequential_tag
)
705 { return _GLIBCXX_STD_A::set_difference(__begin1
, __end1
,
706 __begin2
, __end2
, __out
, __pred
); }
708 // Sequential fallback for input iterator case.
709 template<typename _IIter1
, typename _IIter2
, typename _Predicate
,
710 typename _OutputIterator
, typename _IteratorTag1
,
711 typename _IteratorTag2
, typename _IteratorTag3
>
712 inline _OutputIterator
713 __set_difference_switch(_IIter1 __begin1
, _IIter1 __end1
,
714 _IIter2 __begin2
, _IIter2 __end2
,
715 _OutputIterator __result
, _Predicate __pred
,
716 _IteratorTag1
, _IteratorTag2
, _IteratorTag3
)
717 { return _GLIBCXX_STD_A::set_difference(
718 __begin1
, __end1
, __begin2
, __end2
, __result
, __pred
); }
720 // Parallel set_difference for random access iterators
721 template<typename _RAIter1
, typename _RAIter2
,
722 typename _Output_RAIter
, typename _Predicate
>
724 __set_difference_switch(_RAIter1 __begin1
,
728 _Output_RAIter __result
, _Predicate __pred
,
729 random_access_iterator_tag
,
730 random_access_iterator_tag
,
731 random_access_iterator_tag
)
733 if (_GLIBCXX_PARALLEL_CONDITION(
734 static_cast<__gnu_parallel::_SequenceIndex
>(__end1
- __begin1
)
735 >= __gnu_parallel::_Settings::get().set_difference_minimal_n
736 || static_cast<__gnu_parallel::_SequenceIndex
>(__end2
- __begin2
)
737 >= __gnu_parallel::_Settings::get().set_difference_minimal_n
))
738 return __gnu_parallel::__parallel_set_difference(
739 __begin1
, __end1
, __begin2
, __end2
, __result
, __pred
);
741 return _GLIBCXX_STD_A::set_difference(
742 __begin1
, __end1
, __begin2
, __end2
, __result
, __pred
);
746 template<typename _IIter1
, typename _IIter2
,
747 typename _OutputIterator
>
748 inline _OutputIterator
749 set_difference(_IIter1 __begin1
, _IIter1 __end1
,
750 _IIter2 __begin2
, _IIter2 __end2
,
751 _OutputIterator __out
)
753 typedef std::iterator_traits
<_IIter1
> _IIterTraits1
;
754 typedef std::iterator_traits
<_IIter2
> _IIterTraits2
;
755 typedef std::iterator_traits
<_OutputIterator
> _OIterTraits
;
756 typedef typename
_IIterTraits1::iterator_category
758 typedef typename
_IIterTraits2::iterator_category
760 typedef typename
_OIterTraits::iterator_category _OIterCategory
;
761 typedef typename
_IIterTraits1::value_type _ValueType1
;
762 typedef typename
_IIterTraits2::value_type _ValueType2
;
764 return __set_difference_switch(
765 __begin1
, __end1
, __begin2
, __end2
, __out
,
766 __gnu_parallel::_Less
<_ValueType1
, _ValueType2
>(),
767 _IIterCategory1(), _IIterCategory2(), _OIterCategory());
771 template<typename _IIter1
, typename _IIter2
,
772 typename _OutputIterator
, typename _Predicate
>
773 inline _OutputIterator
774 set_difference(_IIter1 __begin1
, _IIter1 __end1
,
775 _IIter2 __begin2
, _IIter2 __end2
,
776 _OutputIterator __out
, _Predicate __pred
)
778 typedef std::iterator_traits
<_IIter1
> _IIterTraits1
;
779 typedef std::iterator_traits
<_IIter2
> _IIterTraits2
;
780 typedef std::iterator_traits
<_OutputIterator
> _OIterTraits
;
781 typedef typename
_IIterTraits1::iterator_category
783 typedef typename
_IIterTraits2::iterator_category
785 typedef typename
_OIterTraits::iterator_category _OIterCategory
;
787 return __set_difference_switch(
788 __begin1
, __end1
, __begin2
, __end2
, __out
, __pred
,
789 _IIterCategory1(), _IIterCategory2(), _OIterCategory());
792 // Sequential fallback
793 template<typename _FIterator
>
795 adjacent_find(_FIterator __begin
, _FIterator __end
,
796 __gnu_parallel::sequential_tag
)
797 { return _GLIBCXX_STD_A::adjacent_find(__begin
, __end
); }
799 // Sequential fallback
800 template<typename _FIterator
, typename _BinaryPredicate
>
802 adjacent_find(_FIterator __begin
, _FIterator __end
,
803 _BinaryPredicate __binary_pred
,
804 __gnu_parallel::sequential_tag
)
805 { return _GLIBCXX_STD_A::adjacent_find(__begin
, __end
, __binary_pred
); }
807 // Parallel algorithm for random access iterators
808 template<typename _RAIter
>
810 __adjacent_find_switch(_RAIter __begin
, _RAIter __end
,
811 random_access_iterator_tag
)
813 typedef iterator_traits
<_RAIter
> _TraitsType
;
814 typedef typename
_TraitsType::value_type _ValueType
;
816 if (_GLIBCXX_PARALLEL_CONDITION(true))
818 _RAIter __spot
= __gnu_parallel::
820 __begin
, __end
- 1, __begin
, equal_to
<_ValueType
>(),
821 __gnu_parallel::__adjacent_find_selector())
823 if (__spot
== (__end
- 1))
829 return adjacent_find(__begin
, __end
, __gnu_parallel::sequential_tag());
832 // Sequential fallback for input iterator case
833 template<typename _FIterator
, typename _IteratorTag
>
835 __adjacent_find_switch(_FIterator __begin
, _FIterator __end
,
837 { return adjacent_find(__begin
, __end
, __gnu_parallel::sequential_tag()); }
840 template<typename _FIterator
>
842 adjacent_find(_FIterator __begin
, _FIterator __end
)
844 typedef iterator_traits
<_FIterator
> _TraitsType
;
845 typedef typename
_TraitsType::iterator_category _IteratorCategory
;
846 return __adjacent_find_switch(__begin
, __end
, _IteratorCategory());
849 // Sequential fallback for input iterator case
850 template<typename _FIterator
, typename _BinaryPredicate
,
851 typename _IteratorTag
>
853 __adjacent_find_switch(_FIterator __begin
, _FIterator __end
,
854 _BinaryPredicate __pred
, _IteratorTag
)
855 { return adjacent_find(__begin
, __end
, __pred
,
856 __gnu_parallel::sequential_tag()); }
858 // Parallel algorithm for random access iterators
859 template<typename _RAIter
, typename _BinaryPredicate
>
861 __adjacent_find_switch(_RAIter __begin
, _RAIter __end
,
862 _BinaryPredicate __pred
, random_access_iterator_tag
)
864 if (_GLIBCXX_PARALLEL_CONDITION(true))
865 return __gnu_parallel::__find_template(__begin
, __end
, __begin
, __pred
,
867 __adjacent_find_selector()).first
;
869 return adjacent_find(__begin
, __end
, __pred
,
870 __gnu_parallel::sequential_tag());
874 template<typename _FIterator
, typename _BinaryPredicate
>
876 adjacent_find(_FIterator __begin
, _FIterator __end
,
877 _BinaryPredicate __pred
)
879 typedef iterator_traits
<_FIterator
> _TraitsType
;
880 typedef typename
_TraitsType::iterator_category _IteratorCategory
;
881 return __adjacent_find_switch(__begin
, __end
, __pred
,
882 _IteratorCategory());
885 // Sequential fallback
886 template<typename _IIter
, typename _Tp
>
887 inline typename iterator_traits
<_IIter
>::difference_type
888 count(_IIter __begin
, _IIter __end
, const _Tp
& __value
,
889 __gnu_parallel::sequential_tag
)
890 { return _GLIBCXX_STD_A::count(__begin
, __end
, __value
); }
892 // Parallel code for random access iterators
893 template<typename _RAIter
, typename _Tp
>
894 typename iterator_traits
<_RAIter
>::difference_type
895 __count_switch(_RAIter __begin
, _RAIter __end
,
896 const _Tp
& __value
, random_access_iterator_tag
,
897 __gnu_parallel::_Parallelism __parallelism_tag
898 = __gnu_parallel::parallel_unbalanced
)
900 typedef iterator_traits
<_RAIter
> _TraitsType
;
901 typedef typename
_TraitsType::value_type _ValueType
;
902 typedef typename
_TraitsType::difference_type _DifferenceType
;
903 typedef __gnu_parallel::_SequenceIndex _SequenceIndex
;
905 if (_GLIBCXX_PARALLEL_CONDITION(
906 static_cast<_SequenceIndex
>(__end
- __begin
)
907 >= __gnu_parallel::_Settings::get().count_minimal_n
908 && __gnu_parallel::__is_parallel(__parallelism_tag
)))
910 __gnu_parallel::__count_selector
<_RAIter
, _DifferenceType
>
912 _DifferenceType __res
= 0;
914 __for_each_template_random_access(
915 __begin
, __end
, __value
, __functionality
,
916 std::plus
<_SequenceIndex
>(), __res
, __res
, -1,
921 return count(__begin
, __end
, __value
,
922 __gnu_parallel::sequential_tag());
925 // Sequential fallback for input iterator case.
926 template<typename _IIter
, typename _Tp
, typename _IteratorTag
>
927 inline typename iterator_traits
<_IIter
>::difference_type
928 __count_switch(_IIter __begin
, _IIter __end
, const _Tp
& __value
,
930 { return count(__begin
, __end
, __value
, __gnu_parallel::sequential_tag());
934 template<typename _IIter
, typename _Tp
>
935 inline typename iterator_traits
<_IIter
>::difference_type
936 count(_IIter __begin
, _IIter __end
, const _Tp
& __value
,
937 __gnu_parallel::_Parallelism __parallelism_tag
)
939 typedef iterator_traits
<_IIter
> _TraitsType
;
940 typedef typename
_TraitsType::iterator_category _IteratorCategory
;
941 return __count_switch(__begin
, __end
, __value
, _IteratorCategory(),
945 template<typename _IIter
, typename _Tp
>
946 inline typename iterator_traits
<_IIter
>::difference_type
947 count(_IIter __begin
, _IIter __end
, const _Tp
& __value
)
949 typedef iterator_traits
<_IIter
> _TraitsType
;
950 typedef typename
_TraitsType::iterator_category _IteratorCategory
;
951 return __count_switch(__begin
, __end
, __value
, _IteratorCategory());
955 // Sequential fallback.
956 template<typename _IIter
, typename _Predicate
>
957 inline typename iterator_traits
<_IIter
>::difference_type
958 count_if(_IIter __begin
, _IIter __end
, _Predicate __pred
,
959 __gnu_parallel::sequential_tag
)
960 { return _GLIBCXX_STD_A::count_if(__begin
, __end
, __pred
); }
962 // Parallel count_if for random access iterators
963 template<typename _RAIter
, typename _Predicate
>
964 typename iterator_traits
<_RAIter
>::difference_type
965 __count_if_switch(_RAIter __begin
, _RAIter __end
,
966 _Predicate __pred
, random_access_iterator_tag
,
967 __gnu_parallel::_Parallelism __parallelism_tag
968 = __gnu_parallel::parallel_unbalanced
)
970 typedef iterator_traits
<_RAIter
> _TraitsType
;
971 typedef typename
_TraitsType::value_type _ValueType
;
972 typedef typename
_TraitsType::difference_type _DifferenceType
;
973 typedef __gnu_parallel::_SequenceIndex _SequenceIndex
;
975 if (_GLIBCXX_PARALLEL_CONDITION(
976 static_cast<_SequenceIndex
>(__end
- __begin
)
977 >= __gnu_parallel::_Settings::get().count_minimal_n
978 && __gnu_parallel::__is_parallel(__parallelism_tag
)))
980 _DifferenceType __res
= 0;
982 __count_if_selector
<_RAIter
, _DifferenceType
>
985 __for_each_template_random_access(
986 __begin
, __end
, __pred
, __functionality
,
987 std::plus
<_SequenceIndex
>(), __res
, __res
, -1,
992 return count_if(__begin
, __end
, __pred
,
993 __gnu_parallel::sequential_tag());
996 // Sequential fallback for input iterator case.
997 template<typename _IIter
, typename _Predicate
, typename _IteratorTag
>
998 inline typename iterator_traits
<_IIter
>::difference_type
999 __count_if_switch(_IIter __begin
, _IIter __end
, _Predicate __pred
,
1001 { return count_if(__begin
, __end
, __pred
,
1002 __gnu_parallel::sequential_tag()); }
1004 // Public interface.
1005 template<typename _IIter
, typename _Predicate
>
1006 inline typename iterator_traits
<_IIter
>::difference_type
1007 count_if(_IIter __begin
, _IIter __end
, _Predicate __pred
,
1008 __gnu_parallel::_Parallelism __parallelism_tag
)
1010 typedef iterator_traits
<_IIter
> _TraitsType
;
1011 typedef typename
_TraitsType::iterator_category _IteratorCategory
;
1012 return __count_if_switch(__begin
, __end
, __pred
, _IteratorCategory(),
1016 template<typename _IIter
, typename _Predicate
>
1017 inline typename iterator_traits
<_IIter
>::difference_type
1018 count_if(_IIter __begin
, _IIter __end
, _Predicate __pred
)
1020 typedef iterator_traits
<_IIter
> _TraitsType
;
1021 typedef typename
_TraitsType::iterator_category _IteratorCategory
;
1022 return __count_if_switch(__begin
, __end
, __pred
, _IteratorCategory());
1026 // Sequential fallback.
1027 template<typename _FIterator1
, typename _FIterator2
>
1029 search(_FIterator1 __begin1
, _FIterator1 __end1
,
1030 _FIterator2 __begin2
, _FIterator2 __end2
,
1031 __gnu_parallel::sequential_tag
)
1032 { return _GLIBCXX_STD_A::search(__begin1
, __end1
, __begin2
, __end2
); }
1034 // Parallel algorithm for random access iterator
1035 template<typename _RAIter1
, typename _RAIter2
>
1037 __search_switch(_RAIter1 __begin1
, _RAIter1 __end1
,
1038 _RAIter2 __begin2
, _RAIter2 __end2
,
1039 random_access_iterator_tag
, random_access_iterator_tag
)
1041 typedef std::iterator_traits
<_RAIter1
> _Iterator1Traits
;
1042 typedef typename
_Iterator1Traits::value_type _ValueType1
;
1043 typedef std::iterator_traits
<_RAIter2
> _Iterator2Traits
;
1044 typedef typename
_Iterator2Traits::value_type _ValueType2
;
1046 if (_GLIBCXX_PARALLEL_CONDITION(
1047 static_cast<__gnu_parallel::_SequenceIndex
>(__end1
- __begin1
)
1048 >= __gnu_parallel::_Settings::get().search_minimal_n
))
1049 return __gnu_parallel::
1051 __begin1
, __end1
, __begin2
, __end2
,
1052 __gnu_parallel::_EqualTo
<_ValueType1
, _ValueType2
>());
1054 return search(__begin1
, __end1
, __begin2
, __end2
,
1055 __gnu_parallel::sequential_tag());
1058 // Sequential fallback for input iterator case
1059 template<typename _FIterator1
, typename _FIterator2
,
1060 typename _IteratorTag1
, typename _IteratorTag2
>
1062 __search_switch(_FIterator1 __begin1
, _FIterator1 __end1
,
1063 _FIterator2 __begin2
, _FIterator2 __end2
,
1064 _IteratorTag1
, _IteratorTag2
)
1065 { return search(__begin1
, __end1
, __begin2
, __end2
,
1066 __gnu_parallel::sequential_tag()); }
1068 // Public interface.
1069 template<typename _FIterator1
, typename _FIterator2
>
1071 search(_FIterator1 __begin1
, _FIterator1 __end1
,
1072 _FIterator2 __begin2
, _FIterator2 __end2
)
1074 typedef std::iterator_traits
<_FIterator1
> _Iterator1Traits
;
1075 typedef typename
_Iterator1Traits::iterator_category _IteratorCategory1
;
1076 typedef std::iterator_traits
<_FIterator2
> _Iterator2Traits
;
1077 typedef typename
_Iterator2Traits::iterator_category _IteratorCategory2
;
1079 return __search_switch(__begin1
, __end1
, __begin2
, __end2
,
1080 _IteratorCategory1(), _IteratorCategory2());
1083 // Public interface.
1084 template<typename _FIterator1
, typename _FIterator2
,
1085 typename _BinaryPredicate
>
1087 search(_FIterator1 __begin1
, _FIterator1 __end1
,
1088 _FIterator2 __begin2
, _FIterator2 __end2
,
1089 _BinaryPredicate __pred
, __gnu_parallel::sequential_tag
)
1090 { return _GLIBCXX_STD_A::search(
1091 __begin1
, __end1
, __begin2
, __end2
, __pred
); }
1093 // Parallel algorithm for random access iterator.
1094 template<typename _RAIter1
, typename _RAIter2
,
1095 typename _BinaryPredicate
>
1097 __search_switch(_RAIter1 __begin1
, _RAIter1 __end1
,
1098 _RAIter2 __begin2
, _RAIter2 __end2
,
1099 _BinaryPredicate __pred
,
1100 random_access_iterator_tag
, random_access_iterator_tag
)
1102 if (_GLIBCXX_PARALLEL_CONDITION(
1103 static_cast<__gnu_parallel::_SequenceIndex
>(__end1
- __begin1
)
1104 >= __gnu_parallel::_Settings::get().search_minimal_n
))
1105 return __gnu_parallel::__search_template(__begin1
, __end1
,
1106 __begin2
, __end2
, __pred
);
1108 return search(__begin1
, __end1
, __begin2
, __end2
, __pred
,
1109 __gnu_parallel::sequential_tag());
1112 // Sequential fallback for input iterator case
1113 template<typename _FIterator1
, typename _FIterator2
,
1114 typename _BinaryPredicate
, typename _IteratorTag1
,
1115 typename _IteratorTag2
>
1117 __search_switch(_FIterator1 __begin1
, _FIterator1 __end1
,
1118 _FIterator2 __begin2
, _FIterator2 __end2
,
1119 _BinaryPredicate __pred
, _IteratorTag1
, _IteratorTag2
)
1120 { return search(__begin1
, __end1
, __begin2
, __end2
, __pred
,
1121 __gnu_parallel::sequential_tag()); }
1124 template<typename _FIterator1
, typename _FIterator2
,
1125 typename _BinaryPredicate
>
1127 search(_FIterator1 __begin1
, _FIterator1 __end1
,
1128 _FIterator2 __begin2
, _FIterator2 __end2
,
1129 _BinaryPredicate __pred
)
1131 typedef std::iterator_traits
<_FIterator1
> _Iterator1Traits
;
1132 typedef typename
_Iterator1Traits::iterator_category _IteratorCategory1
;
1133 typedef std::iterator_traits
<_FIterator2
> _Iterator2Traits
;
1134 typedef typename
_Iterator2Traits::iterator_category _IteratorCategory2
;
1135 return __search_switch(__begin1
, __end1
, __begin2
, __end2
, __pred
,
1136 _IteratorCategory1(), _IteratorCategory2());
1139 // Sequential fallback
1140 template<typename _FIterator
, typename _Integer
, typename _Tp
>
1142 search_n(_FIterator __begin
, _FIterator __end
, _Integer __count
,
1143 const _Tp
& __val
, __gnu_parallel::sequential_tag
)
1144 { return _GLIBCXX_STD_A::search_n(__begin
, __end
, __count
, __val
); }
1146 // Sequential fallback
1147 template<typename _FIterator
, typename _Integer
, typename _Tp
,
1148 typename _BinaryPredicate
>
1150 search_n(_FIterator __begin
, _FIterator __end
, _Integer __count
,
1151 const _Tp
& __val
, _BinaryPredicate __binary_pred
,
1152 __gnu_parallel::sequential_tag
)
1153 { return _GLIBCXX_STD_A::search_n(
1154 __begin
, __end
, __count
, __val
, __binary_pred
); }
1156 // Public interface.
1157 template<typename _FIterator
, typename _Integer
, typename _Tp
>
1159 search_n(_FIterator __begin
, _FIterator __end
, _Integer __count
,
1162 typedef typename iterator_traits
<_FIterator
>::value_type _ValueType
;
1163 return __gnu_parallel::search_n(__begin
, __end
, __count
, __val
,
1164 __gnu_parallel::_EqualTo
<_ValueType
, _Tp
>());
1167 // Parallel algorithm for random access iterators.
1168 template<typename _RAIter
, typename _Integer
,
1169 typename _Tp
, typename _BinaryPredicate
>
1171 __search_n_switch(_RAIter __begin
, _RAIter __end
, _Integer __count
,
1172 const _Tp
& __val
, _BinaryPredicate __binary_pred
,
1173 random_access_iterator_tag
)
1175 if (_GLIBCXX_PARALLEL_CONDITION(
1176 static_cast<__gnu_parallel::_SequenceIndex
>(__end
- __begin
)
1177 >= __gnu_parallel::_Settings::get().search_minimal_n
))
1179 __gnu_parallel::_PseudoSequence
<_Tp
, _Integer
> __ps(__val
, __count
);
1180 return __gnu_parallel::__search_template(
1181 __begin
, __end
, __ps
.begin(), __ps
.end(), __binary_pred
);
1184 return _GLIBCXX_STD_A::search_n(__begin
, __end
, __count
, __val
,
1188 // Sequential fallback for input iterator case.
1189 template<typename _FIterator
, typename _Integer
, typename _Tp
,
1190 typename _BinaryPredicate
, typename _IteratorTag
>
1192 __search_n_switch(_FIterator __begin
, _FIterator __end
, _Integer __count
,
1193 const _Tp
& __val
, _BinaryPredicate __binary_pred
,
1195 { return _GLIBCXX_STD_A::search_n(__begin
, __end
, __count
, __val
,
1198 // Public interface.
1199 template<typename _FIterator
, typename _Integer
, typename _Tp
,
1200 typename _BinaryPredicate
>
1202 search_n(_FIterator __begin
, _FIterator __end
, _Integer __count
,
1203 const _Tp
& __val
, _BinaryPredicate __binary_pred
)
1205 return __search_n_switch(__begin
, __end
, __count
, __val
, __binary_pred
,
1206 typename
std::iterator_traits
<_FIterator
>::
1207 iterator_category());
1211 // Sequential fallback.
1212 template<typename _IIter
, typename _OutputIterator
,
1213 typename _UnaryOperation
>
1214 inline _OutputIterator
1215 transform(_IIter __begin
, _IIter __end
, _OutputIterator __result
,
1216 _UnaryOperation __unary_op
, __gnu_parallel::sequential_tag
)
1217 { return _GLIBCXX_STD_A::transform(__begin
, __end
, __result
, __unary_op
); }
1219 // Parallel unary transform for random access iterators.
1220 template<typename _RAIter1
, typename _RAIter2
,
1221 typename _UnaryOperation
>
1223 __transform1_switch(_RAIter1 __begin
, _RAIter1 __end
,
1224 _RAIter2 __result
, _UnaryOperation __unary_op
,
1225 random_access_iterator_tag
, random_access_iterator_tag
,
1226 __gnu_parallel::_Parallelism __parallelism_tag
1227 = __gnu_parallel::parallel_balanced
)
1229 if (_GLIBCXX_PARALLEL_CONDITION(
1230 static_cast<__gnu_parallel::_SequenceIndex
>(__end
- __begin
)
1231 >= __gnu_parallel::_Settings::get().transform_minimal_n
1232 && __gnu_parallel::__is_parallel(__parallelism_tag
)))
1234 bool __dummy
= true;
1235 typedef __gnu_parallel::_IteratorPair
<_RAIter1
,
1236 _RAIter2
, random_access_iterator_tag
> _ItTrip
;
1237 _ItTrip
__begin_pair(__begin
, __result
),
1238 __end_pair(__end
, __result
+ (__end
- __begin
));
1239 __gnu_parallel::__transform1_selector
<_ItTrip
> __functionality
;
1241 __for_each_template_random_access(
1242 __begin_pair
, __end_pair
, __unary_op
, __functionality
,
1243 __gnu_parallel::_DummyReduct(),
1244 __dummy
, __dummy
, -1, __parallelism_tag
);
1245 return __functionality
._M_finish_iterator
;
1248 return transform(__begin
, __end
, __result
, __unary_op
,
1249 __gnu_parallel::sequential_tag());
1252 // Sequential fallback for input iterator case.
1253 template<typename _RAIter1
, typename _RAIter2
,
1254 typename _UnaryOperation
, typename _IteratorTag1
,
1255 typename _IteratorTag2
>
1257 __transform1_switch(_RAIter1 __begin
, _RAIter1 __end
,
1258 _RAIter2 __result
, _UnaryOperation __unary_op
,
1259 _IteratorTag1
, _IteratorTag2
)
1260 { return transform(__begin
, __end
, __result
, __unary_op
,
1261 __gnu_parallel::sequential_tag()); }
1263 // Public interface.
1264 template<typename _IIter
, typename _OutputIterator
,
1265 typename _UnaryOperation
>
1266 inline _OutputIterator
1267 transform(_IIter __begin
, _IIter __end
, _OutputIterator __result
,
1268 _UnaryOperation __unary_op
,
1269 __gnu_parallel::_Parallelism __parallelism_tag
)
1271 typedef std::iterator_traits
<_IIter
> _IIterTraits
;
1272 typedef std::iterator_traits
<_OutputIterator
> _OIterTraits
;
1273 typedef typename
_IIterTraits::iterator_category _IIteratorCategory
;
1274 typedef typename
_OIterTraits::iterator_category _OIterCategory
;
1276 return __transform1_switch(__begin
, __end
, __result
, __unary_op
,
1277 _IIteratorCategory(), _OIterCategory(),
1281 template<typename _IIter
, typename _OutputIterator
,
1282 typename _UnaryOperation
>
1283 inline _OutputIterator
1284 transform(_IIter __begin
, _IIter __end
, _OutputIterator __result
,
1285 _UnaryOperation __unary_op
)
1287 typedef std::iterator_traits
<_IIter
> _IIterTraits
;
1288 typedef std::iterator_traits
<_OutputIterator
> _OIterTraits
;
1289 typedef typename
_IIterTraits::iterator_category _IIteratorCategory
;
1290 typedef typename
_OIterTraits::iterator_category _OIterCategory
;
1292 return __transform1_switch(__begin
, __end
, __result
, __unary_op
,
1293 _IIteratorCategory(), _OIterCategory());
1297 // Sequential fallback
1298 template<typename _IIter1
, typename _IIter2
,
1299 typename _OutputIterator
, typename _BinaryOperation
>
1300 inline _OutputIterator
1301 transform(_IIter1 __begin1
, _IIter1 __end1
,
1302 _IIter2 __begin2
, _OutputIterator __result
,
1303 _BinaryOperation __binary_op
, __gnu_parallel::sequential_tag
)
1304 { return _GLIBCXX_STD_A::transform(__begin1
, __end1
,
1305 __begin2
, __result
, __binary_op
); }
1307 // Parallel binary transform for random access iterators.
1308 template<typename _RAIter1
, typename _RAIter2
,
1309 typename _RAIter3
, typename _BinaryOperation
>
1311 __transform2_switch(_RAIter1 __begin1
, _RAIter1 __end1
,
1313 _RAIter3 __result
, _BinaryOperation __binary_op
,
1314 random_access_iterator_tag
, random_access_iterator_tag
,
1315 random_access_iterator_tag
,
1316 __gnu_parallel::_Parallelism __parallelism_tag
1317 = __gnu_parallel::parallel_balanced
)
1319 if (_GLIBCXX_PARALLEL_CONDITION(
1320 (__end1
- __begin1
) >=
1321 __gnu_parallel::_Settings::get().transform_minimal_n
1322 && __gnu_parallel::__is_parallel(__parallelism_tag
)))
1324 bool __dummy
= true;
1325 typedef __gnu_parallel::_IteratorTriple
<_RAIter1
,
1327 random_access_iterator_tag
> _ItTrip
;
1328 _ItTrip
__begin_triple(__begin1
, __begin2
, __result
),
1329 __end_triple(__end1
, __begin2
+ (__end1
- __begin1
),
1330 __result
+ (__end1
- __begin1
));
1331 __gnu_parallel::__transform2_selector
<_ItTrip
> __functionality
;
1333 __for_each_template_random_access(__begin_triple
, __end_triple
,
1334 __binary_op
, __functionality
,
1335 __gnu_parallel::_DummyReduct(),
1336 __dummy
, __dummy
, -1,
1338 return __functionality
._M_finish_iterator
;
1341 return transform(__begin1
, __end1
, __begin2
, __result
, __binary_op
,
1342 __gnu_parallel::sequential_tag());
1345 // Sequential fallback for input iterator case.
1346 template<typename _IIter1
, typename _IIter2
,
1347 typename _OutputIterator
, typename _BinaryOperation
,
1348 typename _Tag1
, typename _Tag2
, typename _Tag3
>
1349 inline _OutputIterator
1350 __transform2_switch(_IIter1 __begin1
, _IIter1 __end1
,
1351 _IIter2 __begin2
, _OutputIterator __result
,
1352 _BinaryOperation __binary_op
, _Tag1
, _Tag2
, _Tag3
)
1353 { return transform(__begin1
, __end1
, __begin2
, __result
, __binary_op
,
1354 __gnu_parallel::sequential_tag()); }
1356 // Public interface.
1357 template<typename _IIter1
, typename _IIter2
,
1358 typename _OutputIterator
, typename _BinaryOperation
>
1359 inline _OutputIterator
1360 transform(_IIter1 __begin1
, _IIter1 __end1
,
1361 _IIter2 __begin2
, _OutputIterator __result
,
1362 _BinaryOperation __binary_op
,
1363 __gnu_parallel::_Parallelism __parallelism_tag
)
1365 typedef std::iterator_traits
<_IIter1
> _IIterTraits1
;
1366 typedef typename
_IIterTraits1::iterator_category
1368 typedef std::iterator_traits
<_IIter2
> _IIterTraits2
;
1369 typedef typename
_IIterTraits2::iterator_category
1371 typedef std::iterator_traits
<_OutputIterator
> _OIterTraits
;
1372 typedef typename
_OIterTraits::iterator_category _OIterCategory
;
1374 return __transform2_switch(
1375 __begin1
, __end1
, __begin2
, __result
, __binary_op
,
1376 _IIterCategory1(), _IIterCategory2(), _OIterCategory(),
1380 template<typename _IIter1
, typename _IIter2
,
1381 typename _OutputIterator
, typename _BinaryOperation
>
1382 inline _OutputIterator
1383 transform(_IIter1 __begin1
, _IIter1 __end1
,
1384 _IIter2 __begin2
, _OutputIterator __result
,
1385 _BinaryOperation __binary_op
)
1387 typedef std::iterator_traits
<_IIter1
> _IIterTraits1
;
1388 typedef typename
_IIterTraits1::iterator_category
1390 typedef std::iterator_traits
<_IIter2
> _IIterTraits2
;
1391 typedef typename
_IIterTraits2::iterator_category
1393 typedef std::iterator_traits
<_OutputIterator
> _OIterTraits
;
1394 typedef typename
_OIterTraits::iterator_category _OIterCategory
;
1396 return __transform2_switch(
1397 __begin1
, __end1
, __begin2
, __result
, __binary_op
,
1398 _IIterCategory1(), _IIterCategory2(), _OIterCategory());
1401 // Sequential fallback
1402 template<typename _FIterator
, typename _Tp
>
1404 replace(_FIterator __begin
, _FIterator __end
, const _Tp
& __old_value
,
1405 const _Tp
& __new_value
, __gnu_parallel::sequential_tag
)
1406 { _GLIBCXX_STD_A::replace(__begin
, __end
, __old_value
, __new_value
); }
1408 // Sequential fallback for input iterator case
1409 template<typename _FIterator
, typename _Tp
, typename _IteratorTag
>
1411 __replace_switch(_FIterator __begin
, _FIterator __end
,
1412 const _Tp
& __old_value
, const _Tp
& __new_value
,
1414 { replace(__begin
, __end
, __old_value
, __new_value
,
1415 __gnu_parallel::sequential_tag()); }
1417 // Parallel replace for random access iterators
1418 template<typename _RAIter
, typename _Tp
>
1420 __replace_switch(_RAIter __begin
, _RAIter __end
,
1421 const _Tp
& __old_value
, const _Tp
& __new_value
,
1422 random_access_iterator_tag
,
1423 __gnu_parallel::_Parallelism __parallelism_tag
1424 = __gnu_parallel::parallel_balanced
)
1426 // XXX parallel version is where?
1427 replace(__begin
, __end
, __old_value
, __new_value
,
1428 __gnu_parallel::sequential_tag());
1432 template<typename _FIterator
, typename _Tp
>
1434 replace(_FIterator __begin
, _FIterator __end
, const _Tp
& __old_value
,
1435 const _Tp
& __new_value
,
1436 __gnu_parallel::_Parallelism __parallelism_tag
)
1438 typedef iterator_traits
<_FIterator
> _TraitsType
;
1439 typedef typename
_TraitsType::iterator_category _IteratorCategory
;
1440 __replace_switch(__begin
, __end
, __old_value
, __new_value
,
1441 _IteratorCategory(),
1445 template<typename _FIterator
, typename _Tp
>
1447 replace(_FIterator __begin
, _FIterator __end
, const _Tp
& __old_value
,
1448 const _Tp
& __new_value
)
1450 typedef iterator_traits
<_FIterator
> _TraitsType
;
1451 typedef typename
_TraitsType::iterator_category _IteratorCategory
;
1452 __replace_switch(__begin
, __end
, __old_value
, __new_value
,
1453 _IteratorCategory());
1457 // Sequential fallback
1458 template<typename _FIterator
, typename _Predicate
, typename _Tp
>
1460 replace_if(_FIterator __begin
, _FIterator __end
, _Predicate __pred
,
1461 const _Tp
& __new_value
, __gnu_parallel::sequential_tag
)
1462 { _GLIBCXX_STD_A::replace_if(__begin
, __end
, __pred
, __new_value
); }
1464 // Sequential fallback for input iterator case
1465 template<typename _FIterator
, typename _Predicate
, typename _Tp
,
1466 typename _IteratorTag
>
1468 __replace_if_switch(_FIterator __begin
, _FIterator __end
,
1469 _Predicate __pred
, const _Tp
& __new_value
, _IteratorTag
)
1470 { replace_if(__begin
, __end
, __pred
, __new_value
,
1471 __gnu_parallel::sequential_tag()); }
1473 // Parallel algorithm for random access iterators.
1474 template<typename _RAIter
, typename _Predicate
, typename _Tp
>
1476 __replace_if_switch(_RAIter __begin
, _RAIter __end
,
1477 _Predicate __pred
, const _Tp
& __new_value
,
1478 random_access_iterator_tag
,
1479 __gnu_parallel::_Parallelism __parallelism_tag
1480 = __gnu_parallel::parallel_balanced
)
1482 if (_GLIBCXX_PARALLEL_CONDITION(
1483 static_cast<__gnu_parallel::_SequenceIndex
>(__end
- __begin
)
1484 >= __gnu_parallel::_Settings::get().replace_minimal_n
1485 && __gnu_parallel::__is_parallel(__parallelism_tag
)))
1489 __replace_if_selector
<_RAIter
, _Predicate
, _Tp
>
1490 __functionality(__new_value
);
1492 __for_each_template_random_access(
1493 __begin
, __end
, __pred
, __functionality
,
1494 __gnu_parallel::_DummyReduct(),
1495 true, __dummy
, -1, __parallelism_tag
);
1498 replace_if(__begin
, __end
, __pred
, __new_value
,
1499 __gnu_parallel::sequential_tag());
1502 // Public interface.
1503 template<typename _FIterator
, typename _Predicate
, typename _Tp
>
1505 replace_if(_FIterator __begin
, _FIterator __end
,
1506 _Predicate __pred
, const _Tp
& __new_value
,
1507 __gnu_parallel::_Parallelism __parallelism_tag
)
1509 typedef std::iterator_traits
<_FIterator
> _IteratorTraits
;
1510 typedef typename
_IteratorTraits::iterator_category _IteratorCategory
;
1511 __replace_if_switch(__begin
, __end
, __pred
, __new_value
,
1512 _IteratorCategory(), __parallelism_tag
);
1515 template<typename _FIterator
, typename _Predicate
, typename _Tp
>
1517 replace_if(_FIterator __begin
, _FIterator __end
,
1518 _Predicate __pred
, const _Tp
& __new_value
)
1520 typedef std::iterator_traits
<_FIterator
> _IteratorTraits
;
1521 typedef typename
_IteratorTraits::iterator_category _IteratorCategory
;
1522 __replace_if_switch(__begin
, __end
, __pred
, __new_value
,
1523 _IteratorCategory());
1526 // Sequential fallback
1527 template<typename _FIterator
, typename _Generator
>
1529 generate(_FIterator __begin
, _FIterator __end
, _Generator __gen
,
1530 __gnu_parallel::sequential_tag
)
1531 { _GLIBCXX_STD_A::generate(__begin
, __end
, __gen
); }
1533 // Sequential fallback for input iterator case.
1534 template<typename _FIterator
, typename _Generator
, typename _IteratorTag
>
1536 __generate_switch(_FIterator __begin
, _FIterator __end
, _Generator __gen
,
1538 { generate(__begin
, __end
, __gen
, __gnu_parallel::sequential_tag()); }
1540 // Parallel algorithm for random access iterators.
1541 template<typename _RAIter
, typename _Generator
>
1543 __generate_switch(_RAIter __begin
, _RAIter __end
,
1544 _Generator __gen
, random_access_iterator_tag
,
1545 __gnu_parallel::_Parallelism __parallelism_tag
1546 = __gnu_parallel::parallel_balanced
)
1548 if (_GLIBCXX_PARALLEL_CONDITION(
1549 static_cast<__gnu_parallel::_SequenceIndex
>(__end
- __begin
)
1550 >= __gnu_parallel::_Settings::get().generate_minimal_n
1551 && __gnu_parallel::__is_parallel(__parallelism_tag
)))
1554 __gnu_parallel::__generate_selector
<_RAIter
>
1557 __for_each_template_random_access(
1558 __begin
, __end
, __gen
, __functionality
,
1559 __gnu_parallel::_DummyReduct(),
1560 true, __dummy
, -1, __parallelism_tag
);
1563 generate(__begin
, __end
, __gen
, __gnu_parallel::sequential_tag());
1566 // Public interface.
1567 template<typename _FIterator
, typename _Generator
>
1569 generate(_FIterator __begin
, _FIterator __end
,
1570 _Generator __gen
, __gnu_parallel::_Parallelism __parallelism_tag
)
1572 typedef std::iterator_traits
<_FIterator
> _IteratorTraits
;
1573 typedef typename
_IteratorTraits::iterator_category _IteratorCategory
;
1574 __generate_switch(__begin
, __end
, __gen
, _IteratorCategory(),
1578 template<typename _FIterator
, typename _Generator
>
1580 generate(_FIterator __begin
, _FIterator __end
, _Generator __gen
)
1582 typedef std::iterator_traits
<_FIterator
> _IteratorTraits
;
1583 typedef typename
_IteratorTraits::iterator_category _IteratorCategory
;
1584 __generate_switch(__begin
, __end
, __gen
, _IteratorCategory());
1588 // Sequential fallback.
1589 template<typename _OutputIterator
, typename _Size
, typename _Generator
>
1590 inline _OutputIterator
1591 generate_n(_OutputIterator __begin
, _Size __n
, _Generator __gen
,
1592 __gnu_parallel::sequential_tag
)
1593 { return _GLIBCXX_STD_A::generate_n(__begin
, __n
, __gen
); }
1595 // Sequential fallback for input iterator case.
1596 template<typename _OutputIterator
, typename _Size
, typename _Generator
,
1597 typename _IteratorTag
>
1598 inline _OutputIterator
1599 __generate_n_switch(_OutputIterator __begin
, _Size __n
, _Generator __gen
,
1601 { return generate_n(__begin
, __n
, __gen
,
1602 __gnu_parallel::sequential_tag()); }
1604 // Parallel algorithm for random access iterators.
1605 template<typename _RAIter
, typename _Size
, typename _Generator
>
1607 __generate_n_switch(_RAIter __begin
, _Size __n
, _Generator __gen
,
1608 random_access_iterator_tag
,
1609 __gnu_parallel::_Parallelism __parallelism_tag
1610 = __gnu_parallel::parallel_balanced
)
1612 // XXX parallel version is where?
1613 return generate_n(__begin
, __n
, __gen
, __gnu_parallel::sequential_tag());
1616 // Public interface.
1617 template<typename _OutputIterator
, typename _Size
, typename _Generator
>
1618 inline _OutputIterator
1619 generate_n(_OutputIterator __begin
, _Size __n
, _Generator __gen
,
1620 __gnu_parallel::_Parallelism __parallelism_tag
)
1622 typedef std::iterator_traits
<_OutputIterator
> _IteratorTraits
;
1623 typedef typename
_IteratorTraits::iterator_category _IteratorCategory
;
1624 return __generate_n_switch(__begin
, __n
, __gen
, _IteratorCategory(),
1628 template<typename _OutputIterator
, typename _Size
, typename _Generator
>
1629 inline _OutputIterator
1630 generate_n(_OutputIterator __begin
, _Size __n
, _Generator __gen
)
1632 typedef std::iterator_traits
<_OutputIterator
> _IteratorTraits
;
1633 typedef typename
_IteratorTraits::iterator_category _IteratorCategory
;
1634 return __generate_n_switch(__begin
, __n
, __gen
, _IteratorCategory());
1638 // Sequential fallback.
1639 template<typename _RAIter
>
1641 random_shuffle(_RAIter __begin
, _RAIter __end
,
1642 __gnu_parallel::sequential_tag
)
1643 { _GLIBCXX_STD_A::random_shuffle(__begin
, __end
); }
1645 // Sequential fallback.
1646 template<typename _RAIter
, typename _RandomNumberGenerator
>
1648 random_shuffle(_RAIter __begin
, _RAIter __end
,
1649 _RandomNumberGenerator
& __rand
,
1650 __gnu_parallel::sequential_tag
)
1651 { _GLIBCXX_STD_A::random_shuffle(__begin
, __end
, __rand
); }
1654 /** @brief Functor wrapper for std::rand(). */
1655 template<typename _MustBeInt
= int>
1659 operator()(int __limit
)
1660 { return rand() % __limit
; }
1663 // Fill in random number generator.
1664 template<typename _RAIter
>
1666 random_shuffle(_RAIter __begin
, _RAIter __end
)
1669 // Parallelization still possible.
1670 __gnu_parallel::random_shuffle(__begin
, __end
, __r
);
1673 // Parallel algorithm for random access iterators.
1674 template<typename _RAIter
, typename _RandomNumberGenerator
>
1676 random_shuffle(_RAIter __begin
, _RAIter __end
,
1677 #if __cplusplus >= 201103L
1678 _RandomNumberGenerator
&& __rand
)
1680 _RandomNumberGenerator
& __rand
)
1683 if (__begin
== __end
)
1685 if (_GLIBCXX_PARALLEL_CONDITION(
1686 static_cast<__gnu_parallel::_SequenceIndex
>(__end
- __begin
)
1687 >= __gnu_parallel::_Settings::get().random_shuffle_minimal_n
))
1688 __gnu_parallel::__parallel_random_shuffle(__begin
, __end
, __rand
);
1690 __gnu_parallel::__sequential_random_shuffle(__begin
, __end
, __rand
);
1693 // Sequential fallback.
1694 template<typename _FIterator
, typename _Predicate
>
1696 partition(_FIterator __begin
, _FIterator __end
,
1697 _Predicate __pred
, __gnu_parallel::sequential_tag
)
1698 { return _GLIBCXX_STD_A::partition(__begin
, __end
, __pred
); }
1700 // Sequential fallback for input iterator case.
1701 template<typename _FIterator
, typename _Predicate
, typename _IteratorTag
>
1703 __partition_switch(_FIterator __begin
, _FIterator __end
,
1704 _Predicate __pred
, _IteratorTag
)
1705 { return partition(__begin
, __end
, __pred
,
1706 __gnu_parallel::sequential_tag()); }
1708 // Parallel algorithm for random access iterators.
1709 template<typename _RAIter
, typename _Predicate
>
1711 __partition_switch(_RAIter __begin
, _RAIter __end
,
1712 _Predicate __pred
, random_access_iterator_tag
)
1714 if (_GLIBCXX_PARALLEL_CONDITION(
1715 static_cast<__gnu_parallel::_SequenceIndex
>(__end
- __begin
)
1716 >= __gnu_parallel::_Settings::get().partition_minimal_n
))
1718 typedef typename
std::iterator_traits
<_RAIter
>::
1719 difference_type _DifferenceType
;
1720 _DifferenceType __middle
= __gnu_parallel::
1721 __parallel_partition(__begin
, __end
, __pred
,
1722 __gnu_parallel::__get_max_threads());
1723 return __begin
+ __middle
;
1726 return partition(__begin
, __end
, __pred
,
1727 __gnu_parallel::sequential_tag());
1730 // Public interface.
1731 template<typename _FIterator
, typename _Predicate
>
1733 partition(_FIterator __begin
, _FIterator __end
, _Predicate __pred
)
1735 typedef iterator_traits
<_FIterator
> _TraitsType
;
1736 typedef typename
_TraitsType::iterator_category _IteratorCategory
;
1737 return __partition_switch(__begin
, __end
, __pred
, _IteratorCategory());
1742 // Sequential fallback
1743 template<typename _RAIter
>
1745 sort(_RAIter __begin
, _RAIter __end
,
1746 __gnu_parallel::sequential_tag
)
1747 { _GLIBCXX_STD_A::sort(__begin
, __end
); }
1749 // Sequential fallback
1750 template<typename _RAIter
, typename _Compare
>
1752 sort(_RAIter __begin
, _RAIter __end
, _Compare __comp
,
1753 __gnu_parallel::sequential_tag
)
1754 { _GLIBCXX_STD_A::sort
<_RAIter
, _Compare
>(__begin
, __end
,
1758 template<typename _RAIter
, typename _Compare
,
1759 typename _Parallelism
>
1761 sort(_RAIter __begin
, _RAIter __end
, _Compare __comp
,
1762 _Parallelism __parallelism
)
1764 typedef iterator_traits
<_RAIter
> _TraitsType
;
1765 typedef typename
_TraitsType::value_type _ValueType
;
1767 if (__begin
!= __end
)
1769 if (_GLIBCXX_PARALLEL_CONDITION(
1770 static_cast<__gnu_parallel::_SequenceIndex
>(__end
- __begin
) >=
1771 __gnu_parallel::_Settings::get().sort_minimal_n
))
1772 __gnu_parallel::__parallel_sort
<false>(
1773 __begin
, __end
, __comp
, __parallelism
);
1775 sort(__begin
, __end
, __comp
, __gnu_parallel::sequential_tag());
1779 // Public interface, insert default comparator
1780 template<typename _RAIter
>
1782 sort(_RAIter __begin
, _RAIter __end
)
1784 typedef iterator_traits
<_RAIter
> _TraitsType
;
1785 typedef typename
_TraitsType::value_type _ValueType
;
1786 sort(__begin
, __end
, std::less
<_ValueType
>(),
1787 __gnu_parallel::default_parallel_tag());
1790 // Public interface, insert default comparator
1791 template<typename _RAIter
>
1793 sort(_RAIter __begin
, _RAIter __end
,
1794 __gnu_parallel::default_parallel_tag __parallelism
)
1796 typedef iterator_traits
<_RAIter
> _TraitsType
;
1797 typedef typename
_TraitsType::value_type _ValueType
;
1798 sort(__begin
, __end
, std::less
<_ValueType
>(), __parallelism
);
1801 // Public interface, insert default comparator
1802 template<typename _RAIter
>
1804 sort(_RAIter __begin
, _RAIter __end
,
1805 __gnu_parallel::parallel_tag __parallelism
)
1807 typedef iterator_traits
<_RAIter
> _TraitsType
;
1808 typedef typename
_TraitsType::value_type _ValueType
;
1809 sort(__begin
, __end
, std::less
<_ValueType
>(), __parallelism
);
1812 // Public interface, insert default comparator
1813 template<typename _RAIter
>
1815 sort(_RAIter __begin
, _RAIter __end
,
1816 __gnu_parallel::multiway_mergesort_tag __parallelism
)
1818 typedef iterator_traits
<_RAIter
> _TraitsType
;
1819 typedef typename
_TraitsType::value_type _ValueType
;
1820 sort(__begin
, __end
, std::less
<_ValueType
>(), __parallelism
);
1823 // Public interface, insert default comparator
1824 template<typename _RAIter
>
1826 sort(_RAIter __begin
, _RAIter __end
,
1827 __gnu_parallel::multiway_mergesort_sampling_tag __parallelism
)
1829 typedef iterator_traits
<_RAIter
> _TraitsType
;
1830 typedef typename
_TraitsType::value_type _ValueType
;
1831 sort(__begin
, __end
, std::less
<_ValueType
>(), __parallelism
);
1834 // Public interface, insert default comparator
1835 template<typename _RAIter
>
1837 sort(_RAIter __begin
, _RAIter __end
,
1838 __gnu_parallel::multiway_mergesort_exact_tag __parallelism
)
1840 typedef iterator_traits
<_RAIter
> _TraitsType
;
1841 typedef typename
_TraitsType::value_type _ValueType
;
1842 sort(__begin
, __end
, std::less
<_ValueType
>(), __parallelism
);
1845 // Public interface, insert default comparator
1846 template<typename _RAIter
>
1848 sort(_RAIter __begin
, _RAIter __end
,
1849 __gnu_parallel::quicksort_tag __parallelism
)
1851 typedef iterator_traits
<_RAIter
> _TraitsType
;
1852 typedef typename
_TraitsType::value_type _ValueType
;
1853 sort(__begin
, __end
, std::less
<_ValueType
>(), __parallelism
);
1856 // Public interface, insert default comparator
1857 template<typename _RAIter
>
1859 sort(_RAIter __begin
, _RAIter __end
,
1860 __gnu_parallel::balanced_quicksort_tag __parallelism
)
1862 typedef iterator_traits
<_RAIter
> _TraitsType
;
1863 typedef typename
_TraitsType::value_type _ValueType
;
1864 sort(__begin
, __end
, std::less
<_ValueType
>(), __parallelism
);
1868 template<typename _RAIter
, typename _Compare
>
1870 sort(_RAIter __begin
, _RAIter __end
, _Compare __comp
)
1872 typedef iterator_traits
<_RAIter
> _TraitsType
;
1873 typedef typename
_TraitsType::value_type _ValueType
;
1874 sort(__begin
, __end
, __comp
, __gnu_parallel::default_parallel_tag());
1878 // stable_sort interface
1881 // Sequential fallback
1882 template<typename _RAIter
>
1884 stable_sort(_RAIter __begin
, _RAIter __end
,
1885 __gnu_parallel::sequential_tag
)
1886 { _GLIBCXX_STD_A::stable_sort(__begin
, __end
); }
1888 // Sequential fallback
1889 template<typename _RAIter
, typename _Compare
>
1891 stable_sort(_RAIter __begin
, _RAIter __end
,
1892 _Compare __comp
, __gnu_parallel::sequential_tag
)
1893 { _GLIBCXX_STD_A::stable_sort
<_RAIter
, _Compare
>(
1894 __begin
, __end
, __comp
); }
1897 template<typename _RAIter
, typename _Compare
,
1898 typename _Parallelism
>
1900 stable_sort(_RAIter __begin
, _RAIter __end
,
1901 _Compare __comp
, _Parallelism __parallelism
)
1903 typedef iterator_traits
<_RAIter
> _TraitsType
;
1904 typedef typename
_TraitsType::value_type _ValueType
;
1906 if (__begin
!= __end
)
1908 if (_GLIBCXX_PARALLEL_CONDITION(
1909 static_cast<__gnu_parallel::_SequenceIndex
>(__end
- __begin
) >=
1910 __gnu_parallel::_Settings::get().sort_minimal_n
))
1911 __gnu_parallel::__parallel_sort
<true>(
1912 __begin
, __end
, __comp
, __parallelism
);
1914 stable_sort(__begin
, __end
, __comp
,
1915 __gnu_parallel::sequential_tag());
1919 // Public interface, insert default comparator
1920 template<typename _RAIter
>
1922 stable_sort(_RAIter __begin
, _RAIter __end
)
1924 typedef iterator_traits
<_RAIter
> _TraitsType
;
1925 typedef typename
_TraitsType::value_type _ValueType
;
1926 stable_sort(__begin
, __end
, std::less
<_ValueType
>(),
1927 __gnu_parallel::default_parallel_tag());
1930 // Public interface, insert default comparator
1931 template<typename _RAIter
>
1933 stable_sort(_RAIter __begin
, _RAIter __end
,
1934 __gnu_parallel::default_parallel_tag __parallelism
)
1936 typedef iterator_traits
<_RAIter
> _TraitsType
;
1937 typedef typename
_TraitsType::value_type _ValueType
;
1938 stable_sort(__begin
, __end
, std::less
<_ValueType
>(), __parallelism
);
1941 // Public interface, insert default comparator
1942 template<typename _RAIter
>
1944 stable_sort(_RAIter __begin
, _RAIter __end
,
1945 __gnu_parallel::parallel_tag __parallelism
)
1947 typedef iterator_traits
<_RAIter
> _TraitsType
;
1948 typedef typename
_TraitsType::value_type _ValueType
;
1949 stable_sort(__begin
, __end
, std::less
<_ValueType
>(), __parallelism
);
1952 // Public interface, insert default comparator
1953 template<typename _RAIter
>
1955 stable_sort(_RAIter __begin
, _RAIter __end
,
1956 __gnu_parallel::multiway_mergesort_tag __parallelism
)
1958 typedef iterator_traits
<_RAIter
> _TraitsType
;
1959 typedef typename
_TraitsType::value_type _ValueType
;
1960 stable_sort(__begin
, __end
, std::less
<_ValueType
>(), __parallelism
);
1963 // Public interface, insert default comparator
1964 template<typename _RAIter
>
1966 stable_sort(_RAIter __begin
, _RAIter __end
,
1967 __gnu_parallel::quicksort_tag __parallelism
)
1969 typedef iterator_traits
<_RAIter
> _TraitsType
;
1970 typedef typename
_TraitsType::value_type _ValueType
;
1971 stable_sort(__begin
, __end
, std::less
<_ValueType
>(), __parallelism
);
1974 // Public interface, insert default comparator
1975 template<typename _RAIter
>
1977 stable_sort(_RAIter __begin
, _RAIter __end
,
1978 __gnu_parallel::balanced_quicksort_tag __parallelism
)
1980 typedef iterator_traits
<_RAIter
> _TraitsType
;
1981 typedef typename
_TraitsType::value_type _ValueType
;
1982 stable_sort(__begin
, __end
, std::less
<_ValueType
>(), __parallelism
);
1986 template<typename _RAIter
, typename _Compare
>
1988 stable_sort(_RAIter __begin
, _RAIter __end
,
1991 typedef iterator_traits
<_RAIter
> _TraitsType
;
1992 typedef typename
_TraitsType::value_type _ValueType
;
1994 __begin
, __end
, __comp
, __gnu_parallel::default_parallel_tag());
1997 // Sequential fallback
1998 template<typename _IIter1
, typename _IIter2
,
1999 typename _OutputIterator
>
2000 inline _OutputIterator
2001 merge(_IIter1 __begin1
, _IIter1 __end1
, _IIter2 __begin2
,
2002 _IIter2 __end2
, _OutputIterator __result
,
2003 __gnu_parallel::sequential_tag
)
2004 { return _GLIBCXX_STD_A::merge(
2005 __begin1
, __end1
, __begin2
, __end2
, __result
); }
2007 // Sequential fallback
2008 template<typename _IIter1
, typename _IIter2
,
2009 typename _OutputIterator
, typename _Compare
>
2010 inline _OutputIterator
2011 merge(_IIter1 __begin1
, _IIter1 __end1
, _IIter2 __begin2
,
2012 _IIter2 __end2
, _OutputIterator __result
, _Compare __comp
,
2013 __gnu_parallel::sequential_tag
)
2014 { return _GLIBCXX_STD_A::merge(
2015 __begin1
, __end1
, __begin2
, __end2
, __result
, __comp
); }
2017 // Sequential fallback for input iterator case
2018 template<typename _IIter1
, typename _IIter2
, typename _OutputIterator
,
2019 typename _Compare
, typename _IteratorTag1
,
2020 typename _IteratorTag2
, typename _IteratorTag3
>
2021 inline _OutputIterator
2022 __merge_switch(_IIter1 __begin1
, _IIter1 __end1
,
2023 _IIter2 __begin2
, _IIter2 __end2
,
2024 _OutputIterator __result
, _Compare __comp
,
2025 _IteratorTag1
, _IteratorTag2
, _IteratorTag3
)
2026 { return _GLIBCXX_STD_A::merge(__begin1
, __end1
, __begin2
, __end2
,
2027 __result
, __comp
); }
2029 // Parallel algorithm for random access iterators
2030 template<typename _IIter1
, typename _IIter2
,
2031 typename _OutputIterator
, typename _Compare
>
2033 __merge_switch(_IIter1 __begin1
, _IIter1 __end1
,
2034 _IIter2 __begin2
, _IIter2 __end2
,
2035 _OutputIterator __result
, _Compare __comp
,
2036 random_access_iterator_tag
, random_access_iterator_tag
,
2037 random_access_iterator_tag
)
2039 if (_GLIBCXX_PARALLEL_CONDITION(
2040 (static_cast<__gnu_parallel::_SequenceIndex
>(__end1
- __begin1
)
2041 >= __gnu_parallel::_Settings::get().merge_minimal_n
2042 || static_cast<__gnu_parallel::_SequenceIndex
>(__end2
- __begin2
)
2043 >= __gnu_parallel::_Settings::get().merge_minimal_n
)))
2044 return __gnu_parallel::__parallel_merge_advance(
2045 __begin1
, __end1
, __begin2
, __end2
, __result
,
2046 (__end1
- __begin1
) + (__end2
- __begin2
), __comp
);
2048 return __gnu_parallel::__merge_advance(
2049 __begin1
, __end1
, __begin2
, __end2
, __result
,
2050 (__end1
- __begin1
) + (__end2
- __begin2
), __comp
);
2054 template<typename _IIter1
, typename _IIter2
,
2055 typename _OutputIterator
, typename _Compare
>
2056 inline _OutputIterator
2057 merge(_IIter1 __begin1
, _IIter1 __end1
, _IIter2 __begin2
,
2058 _IIter2 __end2
, _OutputIterator __result
, _Compare __comp
)
2060 typedef typename iterator_traits
<_IIter1
>::value_type _ValueType
;
2062 typedef std::iterator_traits
<_IIter1
> _IIterTraits1
;
2063 typedef std::iterator_traits
<_IIter2
> _IIterTraits2
;
2064 typedef std::iterator_traits
<_OutputIterator
> _OIterTraits
;
2065 typedef typename
_IIterTraits1::iterator_category
2067 typedef typename
_IIterTraits2::iterator_category
2069 typedef typename
_OIterTraits::iterator_category _OIterCategory
;
2071 return __merge_switch(
2072 __begin1
, __end1
, __begin2
, __end2
, __result
, __comp
,
2073 _IIterCategory1(), _IIterCategory2(), _OIterCategory());
2077 // Public interface, insert default comparator
2078 template<typename _IIter1
, typename _IIter2
,
2079 typename _OutputIterator
>
2080 inline _OutputIterator
2081 merge(_IIter1 __begin1
, _IIter1 __end1
, _IIter2 __begin2
,
2082 _IIter2 __end2
, _OutputIterator __result
)
2084 typedef std::iterator_traits
<_IIter1
> _Iterator1Traits
;
2085 typedef std::iterator_traits
<_IIter2
> _Iterator2Traits
;
2086 typedef typename
_Iterator1Traits::value_type _ValueType1
;
2087 typedef typename
_Iterator2Traits::value_type _ValueType2
;
2089 return __gnu_parallel::merge(__begin1
, __end1
, __begin2
, __end2
,
2090 __result
, __gnu_parallel::_Less
<_ValueType1
, _ValueType2
>());
2093 // Sequential fallback
2094 template<typename _RAIter
>
2096 nth_element(_RAIter __begin
, _RAIter __nth
,
2097 _RAIter __end
, __gnu_parallel::sequential_tag
)
2098 { return _GLIBCXX_STD_A::nth_element(__begin
, __nth
, __end
); }
2100 // Sequential fallback
2101 template<typename _RAIter
, typename _Compare
>
2103 nth_element(_RAIter __begin
, _RAIter __nth
,
2104 _RAIter __end
, _Compare __comp
,
2105 __gnu_parallel::sequential_tag
)
2106 { return _GLIBCXX_STD_A::nth_element(__begin
, __nth
, __end
, __comp
); }
2109 template<typename _RAIter
, typename _Compare
>
2111 nth_element(_RAIter __begin
, _RAIter __nth
,
2112 _RAIter __end
, _Compare __comp
)
2114 if (_GLIBCXX_PARALLEL_CONDITION(
2115 static_cast<__gnu_parallel::_SequenceIndex
>(__end
- __begin
)
2116 >= __gnu_parallel::_Settings::get().nth_element_minimal_n
))
2117 __gnu_parallel::__parallel_nth_element(__begin
, __nth
, __end
, __comp
);
2119 nth_element(__begin
, __nth
, __end
, __comp
,
2120 __gnu_parallel::sequential_tag());
2123 // Public interface, insert default comparator
2124 template<typename _RAIter
>
2126 nth_element(_RAIter __begin
, _RAIter __nth
,
2129 typedef iterator_traits
<_RAIter
> _TraitsType
;
2130 typedef typename
_TraitsType::value_type _ValueType
;
2131 __gnu_parallel::nth_element(__begin
, __nth
, __end
,
2132 std::less
<_ValueType
>());
2135 // Sequential fallback
2136 template<typename _RAIter
, typename _Compare
>
2138 partial_sort(_RAIter __begin
, _RAIter __middle
,
2139 _RAIter __end
, _Compare __comp
,
2140 __gnu_parallel::sequential_tag
)
2141 { _GLIBCXX_STD_A::partial_sort(__begin
, __middle
, __end
, __comp
); }
2143 // Sequential fallback
2144 template<typename _RAIter
>
2146 partial_sort(_RAIter __begin
, _RAIter __middle
,
2147 _RAIter __end
, __gnu_parallel::sequential_tag
)
2148 { _GLIBCXX_STD_A::partial_sort(__begin
, __middle
, __end
); }
2150 // Public interface, parallel algorithm for random access iterators
2151 template<typename _RAIter
, typename _Compare
>
2153 partial_sort(_RAIter __begin
, _RAIter __middle
,
2154 _RAIter __end
, _Compare __comp
)
2156 if (_GLIBCXX_PARALLEL_CONDITION(
2157 static_cast<__gnu_parallel::_SequenceIndex
>(__end
- __begin
)
2158 >= __gnu_parallel::_Settings::get().partial_sort_minimal_n
))
2160 __parallel_partial_sort(__begin
, __middle
, __end
, __comp
);
2162 partial_sort(__begin
, __middle
, __end
, __comp
,
2163 __gnu_parallel::sequential_tag());
2166 // Public interface, insert default comparator
2167 template<typename _RAIter
>
2169 partial_sort(_RAIter __begin
, _RAIter __middle
,
2172 typedef iterator_traits
<_RAIter
> _TraitsType
;
2173 typedef typename
_TraitsType::value_type _ValueType
;
2174 __gnu_parallel::partial_sort(__begin
, __middle
, __end
,
2175 std::less
<_ValueType
>());
2178 // Sequential fallback
2179 template<typename _FIterator
>
2181 max_element(_FIterator __begin
, _FIterator __end
,
2182 __gnu_parallel::sequential_tag
)
2183 { return _GLIBCXX_STD_A::max_element(__begin
, __end
); }
2185 // Sequential fallback
2186 template<typename _FIterator
, typename _Compare
>
2188 max_element(_FIterator __begin
, _FIterator __end
, _Compare __comp
,
2189 __gnu_parallel::sequential_tag
)
2190 { return _GLIBCXX_STD_A::max_element(__begin
, __end
, __comp
); }
2192 // Sequential fallback for input iterator case
2193 template<typename _FIterator
, typename _Compare
, typename _IteratorTag
>
2195 __max_element_switch(_FIterator __begin
, _FIterator __end
,
2196 _Compare __comp
, _IteratorTag
)
2197 { return max_element(__begin
, __end
, __comp
,
2198 __gnu_parallel::sequential_tag()); }
2200 // Parallel algorithm for random access iterators
2201 template<typename _RAIter
, typename _Compare
>
2203 __max_element_switch(_RAIter __begin
, _RAIter __end
,
2204 _Compare __comp
, random_access_iterator_tag
,
2205 __gnu_parallel::_Parallelism __parallelism_tag
2206 = __gnu_parallel::parallel_balanced
)
2208 if (_GLIBCXX_PARALLEL_CONDITION(
2209 static_cast<__gnu_parallel::_SequenceIndex
>(__end
- __begin
)
2210 >= __gnu_parallel::_Settings::get().max_element_minimal_n
2211 && __gnu_parallel::__is_parallel(__parallelism_tag
)))
2213 _RAIter
__res(__begin
);
2214 __gnu_parallel::__identity_selector
<_RAIter
>
2217 __for_each_template_random_access(
2218 __begin
, __end
, __gnu_parallel::_Nothing(), __functionality
,
2219 __gnu_parallel::__max_element_reduct
<_Compare
, _RAIter
>(__comp
),
2220 __res
, __res
, -1, __parallelism_tag
);
2224 return max_element(__begin
, __end
, __comp
,
2225 __gnu_parallel::sequential_tag());
2228 // Public interface, insert default comparator
2229 template<typename _FIterator
>
2231 max_element(_FIterator __begin
, _FIterator __end
,
2232 __gnu_parallel::_Parallelism __parallelism_tag
)
2234 typedef typename iterator_traits
<_FIterator
>::value_type _ValueType
;
2235 return max_element(__begin
, __end
, std::less
<_ValueType
>(),
2239 template<typename _FIterator
>
2241 max_element(_FIterator __begin
, _FIterator __end
)
2243 typedef typename iterator_traits
<_FIterator
>::value_type _ValueType
;
2244 return __gnu_parallel::max_element(__begin
, __end
,
2245 std::less
<_ValueType
>());
2249 template<typename _FIterator
, typename _Compare
>
2251 max_element(_FIterator __begin
, _FIterator __end
, _Compare __comp
,
2252 __gnu_parallel::_Parallelism __parallelism_tag
)
2254 typedef iterator_traits
<_FIterator
> _TraitsType
;
2255 typedef typename
_TraitsType::iterator_category _IteratorCategory
;
2256 return __max_element_switch(__begin
, __end
, __comp
, _IteratorCategory(),
2260 template<typename _FIterator
, typename _Compare
>
2262 max_element(_FIterator __begin
, _FIterator __end
, _Compare __comp
)
2264 typedef iterator_traits
<_FIterator
> _TraitsType
;
2265 typedef typename
_TraitsType::iterator_category _IteratorCategory
;
2266 return __max_element_switch(__begin
, __end
, __comp
, _IteratorCategory());
2270 // Sequential fallback
2271 template<typename _FIterator
>
2273 min_element(_FIterator __begin
, _FIterator __end
,
2274 __gnu_parallel::sequential_tag
)
2275 { return _GLIBCXX_STD_A::min_element(__begin
, __end
); }
2277 // Sequential fallback
2278 template<typename _FIterator
, typename _Compare
>
2280 min_element(_FIterator __begin
, _FIterator __end
, _Compare __comp
,
2281 __gnu_parallel::sequential_tag
)
2282 { return _GLIBCXX_STD_A::min_element(__begin
, __end
, __comp
); }
2284 // Sequential fallback for input iterator case
2285 template<typename _FIterator
, typename _Compare
, typename _IteratorTag
>
2287 __min_element_switch(_FIterator __begin
, _FIterator __end
,
2288 _Compare __comp
, _IteratorTag
)
2289 { return min_element(__begin
, __end
, __comp
,
2290 __gnu_parallel::sequential_tag()); }
2292 // Parallel algorithm for random access iterators
2293 template<typename _RAIter
, typename _Compare
>
2295 __min_element_switch(_RAIter __begin
, _RAIter __end
,
2296 _Compare __comp
, random_access_iterator_tag
,
2297 __gnu_parallel::_Parallelism __parallelism_tag
2298 = __gnu_parallel::parallel_balanced
)
2300 if (_GLIBCXX_PARALLEL_CONDITION(
2301 static_cast<__gnu_parallel::_SequenceIndex
>(__end
- __begin
)
2302 >= __gnu_parallel::_Settings::get().min_element_minimal_n
2303 && __gnu_parallel::__is_parallel(__parallelism_tag
)))
2305 _RAIter
__res(__begin
);
2306 __gnu_parallel::__identity_selector
<_RAIter
>
2309 __for_each_template_random_access(
2310 __begin
, __end
, __gnu_parallel::_Nothing(), __functionality
,
2311 __gnu_parallel::__min_element_reduct
<_Compare
, _RAIter
>(__comp
),
2312 __res
, __res
, -1, __parallelism_tag
);
2316 return min_element(__begin
, __end
, __comp
,
2317 __gnu_parallel::sequential_tag());
2320 // Public interface, insert default comparator
2321 template<typename _FIterator
>
2323 min_element(_FIterator __begin
, _FIterator __end
,
2324 __gnu_parallel::_Parallelism __parallelism_tag
)
2326 typedef typename iterator_traits
<_FIterator
>::value_type _ValueType
;
2327 return min_element(__begin
, __end
, std::less
<_ValueType
>(),
2331 template<typename _FIterator
>
2333 min_element(_FIterator __begin
, _FIterator __end
)
2335 typedef typename iterator_traits
<_FIterator
>::value_type _ValueType
;
2336 return __gnu_parallel::min_element(__begin
, __end
,
2337 std::less
<_ValueType
>());
2341 template<typename _FIterator
, typename _Compare
>
2343 min_element(_FIterator __begin
, _FIterator __end
, _Compare __comp
,
2344 __gnu_parallel::_Parallelism __parallelism_tag
)
2346 typedef iterator_traits
<_FIterator
> _TraitsType
;
2347 typedef typename
_TraitsType::iterator_category _IteratorCategory
;
2348 return __min_element_switch(__begin
, __end
, __comp
, _IteratorCategory(),
2352 template<typename _FIterator
, typename _Compare
>
2354 min_element(_FIterator __begin
, _FIterator __end
, _Compare __comp
)
2356 typedef iterator_traits
<_FIterator
> _TraitsType
;
2357 typedef typename
_TraitsType::iterator_category _IteratorCategory
;
2358 return __min_element_switch(__begin
, __end
, __comp
, _IteratorCategory());
2363 #endif /* _GLIBCXX_PARALLEL_ALGO_H */