3 // Copyright (C) 2007, 2008 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 2, 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 // You should have received a copy of the GNU General Public License
17 // along with this library; see the file COPYING. If not, write to
18 // the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
19 // MA 02111-1307, USA.
21 // As a special exception, you may use this file as part of a free
22 // software library without restriction. Specifically, if other files
23 // instantiate templates or use macros or inline functions from this
24 // file, or you compile this file and link it with other files to
25 // produce an executable, this file does not by itself cause the
26 // resulting executable to be covered by the GNU General Public
27 // License. This exception does not however invalidate any other
28 // reasons why the executable file might be covered by the GNU General
31 /** @file parallel/algo.h
32 * @brief Parallel STL function calls corresponding to the stl_algo.h header.
34 * The functions defined here mainly do case switches and
35 * call the actual parallelized versions in other files.
36 * Inlining policy: Functions that basically only contain one function call,
37 * are declared inline.
38 * This file is a GNU parallel extension to the Standard C++ Library.
41 // Written by Johannes Singler and Felix Putze.
43 #ifndef _GLIBCXX_PARALLEL_ALGO_H
44 #define _GLIBCXX_PARALLEL_ALGO_H 1
46 #include <parallel/algorithmfwd.h>
47 #include <bits/stl_algobase.h>
48 #include <bits/stl_algo.h>
49 #include <parallel/iterator.h>
50 #include <parallel/base.h>
51 #include <parallel/sort.h>
52 #include <parallel/workstealing.h>
53 #include <parallel/par_loop.h>
54 #include <parallel/omp_loop.h>
55 #include <parallel/omp_loop_static.h>
56 #include <parallel/for_each_selectors.h>
57 #include <parallel/for_each.h>
58 #include <parallel/find.h>
59 #include <parallel/find_selectors.h>
60 #include <parallel/search.h>
61 #include <parallel/random_shuffle.h>
62 #include <parallel/partition.h>
63 #include <parallel/merge.h>
64 #include <parallel/unique_copy.h>
65 #include <parallel/set_operations.h>
71 // Sequential fallback
72 template<typename InputIterator
, typename Function
>
74 for_each(InputIterator begin
, InputIterator end
, Function f
,
75 __gnu_parallel::sequential_tag
)
76 { return _GLIBCXX_STD_P::for_each(begin
, end
, f
); }
79 // Sequential fallback for input iterator case
80 template<typename InputIterator
, typename Function
, typename IteratorTag
>
82 for_each_switch(InputIterator begin
, InputIterator end
, Function f
,
84 { return for_each(begin
, end
, f
, __gnu_parallel::sequential_tag()); }
86 // Parallel algorithm for random access iterators
87 template<typename RandomAccessIterator
, typename Function
>
89 for_each_switch(RandomAccessIterator begin
, RandomAccessIterator end
,
90 Function f
, random_access_iterator_tag
,
91 __gnu_parallel::_Parallelism parallelism_tag
92 = __gnu_parallel::parallel_balanced
)
94 if (_GLIBCXX_PARALLEL_CONDITION(
95 static_cast<__gnu_parallel::sequence_index_t
>(end
- begin
)
96 >= __gnu_parallel::_Settings::get().for_each_minimal_n
97 && __gnu_parallel::is_parallel(parallelism_tag
)))
100 __gnu_parallel::for_each_selector
<RandomAccessIterator
> functionality
;
102 return __gnu_parallel::
103 for_each_template_random_access(begin
, end
, f
, functionality
,
104 __gnu_parallel::dummy_reduct(),
105 true, dummy
, -1, parallelism_tag
);
108 return for_each(begin
, end
, f
, __gnu_parallel::sequential_tag());
112 template<typename Iterator
, typename Function
>
114 for_each(Iterator begin
, Iterator end
, Function f
,
115 __gnu_parallel::_Parallelism parallelism_tag
)
117 typedef std::iterator_traits
<Iterator
> iterator_traits
;
118 typedef typename
iterator_traits::iterator_category iterator_category
;
119 return for_each_switch(begin
, end
, f
, iterator_category(),
123 template<typename Iterator
, typename Function
>
125 for_each(Iterator begin
, Iterator end
, Function f
)
127 typedef std::iterator_traits
<Iterator
> iterator_traits
;
128 typedef typename
iterator_traits::iterator_category iterator_category
;
129 return for_each_switch(begin
, end
, f
, iterator_category());
133 // Sequential fallback
134 template<typename InputIterator
, typename T
>
136 find(InputIterator begin
, InputIterator end
, const T
& val
,
137 __gnu_parallel::sequential_tag
)
138 { return _GLIBCXX_STD_P::find(begin
, end
, val
); }
140 // Sequential fallback for input iterator case
141 template<typename InputIterator
, typename T
, typename IteratorTag
>
143 find_switch(InputIterator begin
, InputIterator end
, const T
& val
,
145 { return _GLIBCXX_STD_P::find(begin
, end
, val
); }
147 // Parallel find for random access iterators
148 template<typename RandomAccessIterator
, typename T
>
150 find_switch(RandomAccessIterator begin
, RandomAccessIterator end
,
151 const T
& val
, random_access_iterator_tag
)
153 typedef iterator_traits
<RandomAccessIterator
> traits_type
;
154 typedef typename
traits_type::value_type value_type
;
156 if (_GLIBCXX_PARALLEL_CONDITION(true))
158 binder2nd
<__gnu_parallel::equal_to
<value_type
, T
> >
159 comp(__gnu_parallel::equal_to
<value_type
, T
>(), val
);
160 return __gnu_parallel::find_template(begin
, end
, begin
, comp
,
162 find_if_selector()).first
;
165 return _GLIBCXX_STD_P::find(begin
, end
, val
);
169 template<typename InputIterator
, typename T
>
171 find(InputIterator begin
, InputIterator end
, const T
& val
)
173 typedef std::iterator_traits
<InputIterator
> iterator_traits
;
174 typedef typename
iterator_traits::iterator_category iterator_category
;
175 return find_switch(begin
, end
, val
, iterator_category());
178 // Sequential fallback
179 template<typename InputIterator
, typename Predicate
>
181 find_if(InputIterator begin
, InputIterator end
, Predicate pred
,
182 __gnu_parallel::sequential_tag
)
183 { return _GLIBCXX_STD_P::find_if(begin
, end
, pred
); }
185 // Sequential fallback for input iterator case
186 template<typename InputIterator
, typename Predicate
, typename IteratorTag
>
188 find_if_switch(InputIterator begin
, InputIterator end
, Predicate pred
,
190 { return _GLIBCXX_STD_P::find_if(begin
, end
, pred
); }
192 // Parallel find_if for random access iterators
193 template<typename RandomAccessIterator
, typename Predicate
>
195 find_if_switch(RandomAccessIterator begin
, RandomAccessIterator end
,
196 Predicate pred
, random_access_iterator_tag
)
198 if (_GLIBCXX_PARALLEL_CONDITION(true))
199 return __gnu_parallel::find_template(begin
, end
, begin
, pred
,
201 find_if_selector()).first
;
203 return _GLIBCXX_STD_P::find_if(begin
, end
, pred
);
207 template<typename InputIterator
, typename Predicate
>
209 find_if(InputIterator begin
, InputIterator end
, Predicate pred
)
211 typedef std::iterator_traits
<InputIterator
> iterator_traits
;
212 typedef typename
iterator_traits::iterator_category iterator_category
;
213 return find_if_switch(begin
, end
, pred
, iterator_category());
216 // Sequential fallback
217 template<typename InputIterator
, typename ForwardIterator
>
219 find_first_of(InputIterator begin1
, InputIterator end1
,
220 ForwardIterator begin2
, ForwardIterator end2
,
221 __gnu_parallel::sequential_tag
)
222 { return _GLIBCXX_STD_P::find_first_of(begin1
, end1
, begin2
, end2
); }
224 // Sequential fallback
225 template<typename InputIterator
, typename ForwardIterator
,
226 typename BinaryPredicate
>
228 find_first_of(InputIterator begin1
, InputIterator end1
,
229 ForwardIterator begin2
, ForwardIterator end2
,
230 BinaryPredicate comp
, __gnu_parallel::sequential_tag
)
231 { return _GLIBCXX_STD_P::find_first_of(begin1
, end1
, begin2
, end2
, comp
); }
233 // Sequential fallback for input iterator type
234 template<typename InputIterator
, typename ForwardIterator
,
235 typename IteratorTag1
, typename IteratorTag2
>
237 find_first_of_switch(InputIterator begin1
, InputIterator end1
,
238 ForwardIterator begin2
, ForwardIterator end2
,
239 IteratorTag1
, IteratorTag2
)
240 { return find_first_of(begin1
, end1
, begin2
, end2
,
241 __gnu_parallel::sequential_tag()); }
243 // Parallel algorithm for random access iterators
244 template<typename RandomAccessIterator
, typename ForwardIterator
,
245 typename BinaryPredicate
, typename IteratorTag
>
246 inline RandomAccessIterator
247 find_first_of_switch(RandomAccessIterator begin1
,
248 RandomAccessIterator end1
,
249 ForwardIterator begin2
, ForwardIterator end2
,
250 BinaryPredicate comp
, random_access_iterator_tag
,
253 return __gnu_parallel::
254 find_template(begin1
, end1
, begin1
, comp
,
255 __gnu_parallel::find_first_of_selector
256 <ForwardIterator
>(begin2
, end2
)).first
;
259 // Sequential fallback for input iterator type
260 template<typename InputIterator
, typename ForwardIterator
,
261 typename BinaryPredicate
, typename IteratorTag1
,
262 typename IteratorTag2
>
264 find_first_of_switch(InputIterator begin1
, InputIterator end1
,
265 ForwardIterator begin2
, ForwardIterator end2
,
266 BinaryPredicate comp
, IteratorTag1
, IteratorTag2
)
267 { return find_first_of(begin1
, end1
, begin2
, end2
, comp
,
268 __gnu_parallel::sequential_tag()); }
271 template<typename InputIterator
, typename ForwardIterator
,
272 typename BinaryPredicate
>
274 find_first_of(InputIterator begin1
, InputIterator end1
,
275 ForwardIterator begin2
, ForwardIterator end2
,
276 BinaryPredicate comp
)
278 typedef std::iterator_traits
<InputIterator
> iteratori_traits
;
279 typedef std::iterator_traits
<ForwardIterator
> iteratorf_traits
;
280 typedef typename
iteratori_traits::iterator_category iteratori_category
;
281 typedef typename
iteratorf_traits::iterator_category iteratorf_category
;
283 return find_first_of_switch(begin1
, end1
, begin2
, end2
, comp
,
284 iteratori_category(), iteratorf_category());
287 // Public interface, insert default comparator
288 template<typename InputIterator
, typename ForwardIterator
>
290 find_first_of(InputIterator begin1
, InputIterator end1
,
291 ForwardIterator begin2
, ForwardIterator end2
)
293 typedef std::iterator_traits
<InputIterator
> iteratori_traits
;
294 typedef std::iterator_traits
<ForwardIterator
> iteratorf_traits
;
295 typedef typename
iteratori_traits::value_type valuei_type
;
296 typedef typename
iteratorf_traits::value_type valuef_type
;
298 return find_first_of(begin1
, end1
, begin2
, end2
, __gnu_parallel::
299 equal_to
<valuei_type
, valuef_type
>());
302 // Sequential fallback
303 template<typename InputIterator
, typename OutputIterator
>
304 inline OutputIterator
305 unique_copy(InputIterator begin1
, InputIterator end1
, OutputIterator out
,
306 __gnu_parallel::sequential_tag
)
307 { return _GLIBCXX_STD_P::unique_copy(begin1
, end1
, out
); }
309 // Sequential fallback
310 template<typename InputIterator
, typename OutputIterator
,
312 inline OutputIterator
313 unique_copy(InputIterator begin1
, InputIterator end1
, OutputIterator out
,
314 Predicate pred
, __gnu_parallel::sequential_tag
)
315 { return _GLIBCXX_STD_P::unique_copy(begin1
, end1
, out
, pred
); }
317 // Sequential fallback for input iterator case
318 template<typename InputIterator
, typename OutputIterator
,
319 typename Predicate
, typename IteratorTag1
, typename IteratorTag2
>
320 inline OutputIterator
321 unique_copy_switch(InputIterator begin
, InputIterator last
,
322 OutputIterator out
, Predicate pred
,
323 IteratorTag1
, IteratorTag2
)
324 { return _GLIBCXX_STD_P::unique_copy(begin
, last
, out
, pred
); }
326 // Parallel unique_copy for random access iterators
327 template<typename RandomAccessIterator
, typename RandomAccessOutputIterator
,
329 RandomAccessOutputIterator
330 unique_copy_switch(RandomAccessIterator begin
, RandomAccessIterator last
,
331 RandomAccessOutputIterator out
, Predicate pred
,
332 random_access_iterator_tag
, random_access_iterator_tag
)
334 if (_GLIBCXX_PARALLEL_CONDITION(
335 static_cast<__gnu_parallel::sequence_index_t
>(last
- begin
)
336 > __gnu_parallel::_Settings::get().unique_copy_minimal_n
))
337 return __gnu_parallel::parallel_unique_copy(begin
, last
, out
, pred
);
339 return _GLIBCXX_STD_P::unique_copy(begin
, last
, out
, pred
);
343 template<typename InputIterator
, typename OutputIterator
>
344 inline OutputIterator
345 unique_copy(InputIterator begin1
, InputIterator end1
, OutputIterator out
)
347 typedef std::iterator_traits
<InputIterator
> iteratori_traits
;
348 typedef std::iterator_traits
<OutputIterator
> iteratoro_traits
;
349 typedef typename
iteratori_traits::iterator_category iteratori_category
;
350 typedef typename
iteratori_traits::value_type value_type
;
351 typedef typename
iteratoro_traits::iterator_category iteratoro_category
;
353 return unique_copy_switch(begin1
, end1
, out
, equal_to
<value_type
>(),
354 iteratori_category(), iteratoro_category());
358 template<typename InputIterator
, typename OutputIterator
, typename Predicate
>
359 inline OutputIterator
360 unique_copy(InputIterator begin1
, InputIterator end1
, OutputIterator out
,
363 typedef std::iterator_traits
<InputIterator
> iteratori_traits
;
364 typedef std::iterator_traits
<OutputIterator
> iteratoro_traits
;
365 typedef typename
iteratori_traits::iterator_category iteratori_category
;
366 typedef typename
iteratoro_traits::iterator_category iteratoro_category
;
368 return unique_copy_switch(begin1
, end1
, out
, pred
, iteratori_category(),
369 iteratoro_category());
372 // Sequential fallback
373 template<typename InputIterator1
, typename InputIterator2
,
374 typename OutputIterator
>
375 inline OutputIterator
376 set_union(InputIterator1 begin1
, InputIterator1 end1
,
377 InputIterator2 begin2
, InputIterator2 end2
,
378 OutputIterator out
, __gnu_parallel::sequential_tag
)
379 { return _GLIBCXX_STD_P::set_union(begin1
, end1
, begin2
, end2
, out
); }
381 // Sequential fallback
382 template<typename InputIterator1
, typename InputIterator2
,
383 typename OutputIterator
, typename Predicate
>
384 inline OutputIterator
385 set_union(InputIterator1 begin1
, InputIterator1 end1
,
386 InputIterator2 begin2
, InputIterator2 end2
,
387 OutputIterator out
, Predicate pred
,
388 __gnu_parallel::sequential_tag
)
389 { return _GLIBCXX_STD_P::set_union(begin1
, end1
,
390 begin2
, end2
, out
, pred
); }
392 // Sequential fallback for input iterator case
393 template<typename InputIterator1
, typename InputIterator2
,
394 typename Predicate
, typename OutputIterator
,
395 typename IteratorTag1
, typename IteratorTag2
, typename IteratorTag3
>
396 inline OutputIterator
397 set_union_switch(InputIterator1 begin1
, InputIterator1 end1
,
398 InputIterator2 begin2
, InputIterator2 end2
,
399 OutputIterator result
, Predicate pred
, IteratorTag1
,
400 IteratorTag2
, IteratorTag3
)
401 { return _GLIBCXX_STD_P::set_union(begin1
, end1
,
402 begin2
, end2
, result
, pred
); }
404 // Parallel set_union for random access iterators
405 template<typename RandomAccessIterator1
, typename RandomAccessIterator2
,
406 typename OutputRandomAccessIterator
, typename Predicate
>
407 OutputRandomAccessIterator
408 set_union_switch(RandomAccessIterator1 begin1
, RandomAccessIterator1 end1
,
409 RandomAccessIterator2 begin2
, RandomAccessIterator2 end2
,
410 OutputRandomAccessIterator result
, Predicate pred
,
411 random_access_iterator_tag
, random_access_iterator_tag
,
412 random_access_iterator_tag
)
414 if (_GLIBCXX_PARALLEL_CONDITION(
415 static_cast<__gnu_parallel::sequence_index_t
>(end1
- begin1
)
416 >= __gnu_parallel::_Settings::get().set_union_minimal_n
417 || static_cast<__gnu_parallel::sequence_index_t
>(end2
- begin2
)
418 >= __gnu_parallel::_Settings::get().set_union_minimal_n
))
419 return __gnu_parallel::parallel_set_union(begin1
, end1
,
420 begin2
, end2
, result
, pred
);
422 return _GLIBCXX_STD_P::set_union(begin1
, end1
,
423 begin2
, end2
, result
, pred
);
427 template<typename InputIterator1
, typename InputIterator2
,
428 typename OutputIterator
>
429 inline OutputIterator
430 set_union(InputIterator1 begin1
, InputIterator1 end1
,
431 InputIterator2 begin2
, InputIterator2 end2
, OutputIterator out
)
433 typedef std::iterator_traits
<InputIterator1
> iteratori1_traits
;
434 typedef std::iterator_traits
<InputIterator2
> iteratori2_traits
;
435 typedef std::iterator_traits
<OutputIterator
> iteratoro_traits
;
436 typedef typename
iteratori1_traits::iterator_category
438 typedef typename
iteratori2_traits::iterator_category
440 typedef typename
iteratoro_traits::iterator_category iteratoro_category
;
441 typedef typename
iteratori1_traits::value_type value1_type
;
442 typedef typename
iteratori2_traits::value_type value2_type
;
444 return set_union_switch(begin1
, end1
, begin2
, end2
, out
,
445 __gnu_parallel::less
<value1_type
, value2_type
>(),
446 iteratori1_category(), iteratori2_category(),
447 iteratoro_category());
451 template<typename InputIterator1
, typename InputIterator2
,
452 typename OutputIterator
, typename Predicate
>
453 inline OutputIterator
454 set_union(InputIterator1 begin1
, InputIterator1 end1
,
455 InputIterator2 begin2
, InputIterator2 end2
,
456 OutputIterator out
, Predicate pred
)
458 typedef std::iterator_traits
<InputIterator1
> iteratori1_traits
;
459 typedef std::iterator_traits
<InputIterator2
> iteratori2_traits
;
460 typedef std::iterator_traits
<OutputIterator
> iteratoro_traits
;
461 typedef typename
iteratori1_traits::iterator_category
463 typedef typename
iteratori2_traits::iterator_category
465 typedef typename
iteratoro_traits::iterator_category iteratoro_category
;
467 return set_union_switch(begin1
, end1
, begin2
, end2
, out
, pred
,
468 iteratori1_category(), iteratori2_category(),
469 iteratoro_category());
472 // Sequential fallback.
473 template<typename InputIterator1
, typename InputIterator2
,
474 typename OutputIterator
>
475 inline OutputIterator
476 set_intersection(InputIterator1 begin1
, InputIterator1 end1
,
477 InputIterator2 begin2
, InputIterator2 end2
,
478 OutputIterator out
, __gnu_parallel::sequential_tag
)
479 { return _GLIBCXX_STD_P::set_intersection(begin1
, end1
,
480 begin2
, end2
, out
); }
482 // Sequential fallback.
483 template<typename InputIterator1
, typename InputIterator2
,
484 typename OutputIterator
, typename Predicate
>
485 inline OutputIterator
486 set_intersection(InputIterator1 begin1
, InputIterator1 end1
,
487 InputIterator2 begin2
, InputIterator2 end2
,
488 OutputIterator out
, Predicate pred
,
489 __gnu_parallel::sequential_tag
)
490 { return _GLIBCXX_STD_P::set_intersection(begin1
, end1
, begin2
, end2
,
493 // Sequential fallback for input iterator case
494 template<typename InputIterator1
, typename InputIterator2
,
495 typename Predicate
, typename OutputIterator
,
496 typename IteratorTag1
, typename IteratorTag2
,
497 typename IteratorTag3
>
498 inline OutputIterator
499 set_intersection_switch(InputIterator1 begin1
, InputIterator1 end1
,
500 InputIterator2 begin2
, InputIterator2 end2
,
501 OutputIterator result
, Predicate pred
,
502 IteratorTag1
, IteratorTag2
, IteratorTag3
)
503 { return _GLIBCXX_STD_P::set_intersection(begin1
, end1
, begin2
,
504 end2
, result
, pred
); }
506 // Parallel set_intersection for random access iterators
507 template<typename RandomAccessIterator1
, typename RandomAccessIterator2
,
508 typename OutputRandomAccessIterator
, typename Predicate
>
509 OutputRandomAccessIterator
510 set_intersection_switch(RandomAccessIterator1 begin1
,
511 RandomAccessIterator1 end1
,
512 RandomAccessIterator2 begin2
,
513 RandomAccessIterator2 end2
,
514 OutputRandomAccessIterator result
,
516 random_access_iterator_tag
,
517 random_access_iterator_tag
,
518 random_access_iterator_tag
)
520 if (_GLIBCXX_PARALLEL_CONDITION(
521 static_cast<__gnu_parallel::sequence_index_t
>(end1
- begin1
)
522 >= __gnu_parallel::_Settings::get().set_union_minimal_n
523 || static_cast<__gnu_parallel::sequence_index_t
>(end2
- begin2
)
524 >= __gnu_parallel::_Settings::get().set_union_minimal_n
))
525 return __gnu_parallel::parallel_set_intersection(begin1
, end1
, begin2
,
528 return _GLIBCXX_STD_P::set_intersection(begin1
, end1
, begin2
,
533 template<typename InputIterator1
, typename InputIterator2
,
534 typename OutputIterator
>
535 inline OutputIterator
536 set_intersection(InputIterator1 begin1
, InputIterator1 end1
,
537 InputIterator2 begin2
, InputIterator2 end2
,
540 typedef std::iterator_traits
<InputIterator1
> iteratori1_traits
;
541 typedef std::iterator_traits
<InputIterator2
> iteratori2_traits
;
542 typedef std::iterator_traits
<OutputIterator
> iteratoro_traits
;
543 typedef typename
iteratori1_traits::iterator_category
545 typedef typename
iteratori2_traits::iterator_category
547 typedef typename
iteratoro_traits::iterator_category iteratoro_category
;
548 typedef typename
iteratori1_traits::value_type value1_type
;
549 typedef typename
iteratori2_traits::value_type value2_type
;
551 return set_intersection_switch(begin1
, end1
, begin2
, end2
, out
,
553 less
<value1_type
, value2_type
>(),
554 iteratori1_category(),
555 iteratori2_category(),
556 iteratoro_category());
559 template<typename InputIterator1
, typename InputIterator2
,
560 typename OutputIterator
, typename Predicate
>
561 inline OutputIterator
562 set_intersection(InputIterator1 begin1
, InputIterator1 end1
,
563 InputIterator2 begin2
, InputIterator2 end2
,
564 OutputIterator out
, Predicate pred
)
566 typedef std::iterator_traits
<InputIterator1
> iteratori1_traits
;
567 typedef std::iterator_traits
<InputIterator2
> iteratori2_traits
;
568 typedef std::iterator_traits
<OutputIterator
> iteratoro_traits
;
569 typedef typename
iteratori1_traits::iterator_category
571 typedef typename
iteratori2_traits::iterator_category
573 typedef typename
iteratoro_traits::iterator_category iteratoro_category
;
575 return set_intersection_switch(begin1
, end1
, begin2
, end2
, out
, pred
,
576 iteratori1_category(),
577 iteratori2_category(),
578 iteratoro_category());
581 // Sequential fallback
582 template<typename InputIterator1
, typename InputIterator2
,
583 typename OutputIterator
>
584 inline OutputIterator
585 set_symmetric_difference(InputIterator1 begin1
, InputIterator1 end1
,
586 InputIterator2 begin2
, InputIterator2 end2
,
588 __gnu_parallel::sequential_tag
)
589 { return _GLIBCXX_STD_P::set_symmetric_difference(begin1
,end1
,
590 begin2
, end2
, out
); }
592 // Sequential fallback
593 template<typename InputIterator1
, typename InputIterator2
,
594 typename OutputIterator
, typename Predicate
>
595 inline OutputIterator
596 set_symmetric_difference(InputIterator1 begin1
, InputIterator1 end1
,
597 InputIterator2 begin2
, InputIterator2 end2
,
598 OutputIterator out
, Predicate pred
,
599 __gnu_parallel::sequential_tag
)
600 { return _GLIBCXX_STD_P::set_symmetric_difference(begin1
, end1
, begin2
,
603 // Sequential fallback for input iterator case
604 template<typename InputIterator1
, typename InputIterator2
,
605 typename Predicate
, typename OutputIterator
,
606 typename IteratorTag1
, typename IteratorTag2
,
607 typename IteratorTag3
>
608 inline OutputIterator
609 set_symmetric_difference_switch(InputIterator1 begin1
,
611 InputIterator2 begin2
,
613 OutputIterator result
, Predicate pred
,
614 IteratorTag1
, IteratorTag2
, IteratorTag3
)
615 { return _GLIBCXX_STD_P::set_symmetric_difference(begin1
, end1
,
619 // Parallel set_symmetric_difference for random access iterators
620 template<typename RandomAccessIterator1
, typename RandomAccessIterator2
,
621 typename OutputRandomAccessIterator
, typename Predicate
>
622 OutputRandomAccessIterator
623 set_symmetric_difference_switch(RandomAccessIterator1 begin1
,
624 RandomAccessIterator1 end1
,
625 RandomAccessIterator2 begin2
,
626 RandomAccessIterator2 end2
,
627 OutputRandomAccessIterator result
,
629 random_access_iterator_tag
,
630 random_access_iterator_tag
,
631 random_access_iterator_tag
)
633 if (_GLIBCXX_PARALLEL_CONDITION(
634 static_cast<__gnu_parallel::sequence_index_t
>(end1
- begin1
)
635 >= __gnu_parallel::_Settings::get().set_symmetric_difference_minimal_n
636 || static_cast<__gnu_parallel::sequence_index_t
>(end2
- begin2
)
637 >= __gnu_parallel::_Settings::get().set_symmetric_difference_minimal_n
))
638 return __gnu_parallel::parallel_set_symmetric_difference(begin1
, end1
,
642 return _GLIBCXX_STD_P::set_symmetric_difference(begin1
, end1
,
648 template<typename InputIterator1
, typename InputIterator2
,
649 typename OutputIterator
>
650 inline OutputIterator
651 set_symmetric_difference(InputIterator1 begin1
, InputIterator1 end1
,
652 InputIterator2 begin2
, InputIterator2 end2
,
655 typedef std::iterator_traits
<InputIterator1
> iteratori1_traits
;
656 typedef std::iterator_traits
<InputIterator2
> iteratori2_traits
;
657 typedef std::iterator_traits
<OutputIterator
> iteratoro_traits
;
658 typedef typename
iteratori1_traits::iterator_category
660 typedef typename
iteratori2_traits::iterator_category
662 typedef typename
iteratoro_traits::iterator_category iteratoro_category
;
663 typedef typename
iteratori1_traits::value_type value1_type
;
664 typedef typename
iteratori2_traits::value_type value2_type
;
666 return set_symmetric_difference_switch(begin1
, end1
, begin2
, end2
, out
,
668 less
<value1_type
, value2_type
>(),
669 iteratori1_category(),
670 iteratori2_category(),
671 iteratoro_category());
675 template<typename InputIterator1
, typename InputIterator2
,
676 typename OutputIterator
, typename Predicate
>
677 inline OutputIterator
678 set_symmetric_difference(InputIterator1 begin1
, InputIterator1 end1
,
679 InputIterator2 begin2
, InputIterator2 end2
,
680 OutputIterator out
, Predicate pred
)
682 typedef std::iterator_traits
<InputIterator1
> iteratori1_traits
;
683 typedef std::iterator_traits
<InputIterator2
> iteratori2_traits
;
684 typedef std::iterator_traits
<OutputIterator
> iteratoro_traits
;
685 typedef typename
iteratori1_traits::iterator_category
687 typedef typename
iteratori2_traits::iterator_category
689 typedef typename
iteratoro_traits::iterator_category iteratoro_category
;
691 return set_symmetric_difference_switch(begin1
, end1
, begin2
, end2
, out
,
692 pred
, iteratori1_category(),
693 iteratori2_category(),
694 iteratoro_category());
697 // Sequential fallback.
698 template<typename InputIterator1
, typename InputIterator2
,
699 typename OutputIterator
>
700 inline OutputIterator
701 set_difference(InputIterator1 begin1
, InputIterator1 end1
,
702 InputIterator2 begin2
, InputIterator2 end2
,
703 OutputIterator out
, __gnu_parallel::sequential_tag
)
704 { return _GLIBCXX_STD_P::set_difference(begin1
,end1
, begin2
, end2
, out
); }
706 // Sequential fallback.
707 template<typename InputIterator1
, typename InputIterator2
,
708 typename OutputIterator
, typename Predicate
>
709 inline OutputIterator
710 set_difference(InputIterator1 begin1
, InputIterator1 end1
,
711 InputIterator2 begin2
, InputIterator2 end2
,
712 OutputIterator out
, Predicate pred
,
713 __gnu_parallel::sequential_tag
)
714 { return _GLIBCXX_STD_P::set_difference(begin1
, end1
,
715 begin2
, end2
, out
, pred
); }
717 // Sequential fallback for input iterator case.
718 template<typename InputIterator1
, typename InputIterator2
,
719 typename Predicate
, typename OutputIterator
,
720 typename IteratorTag1
, typename IteratorTag2
, typename IteratorTag3
>
721 inline OutputIterator
722 set_difference_switch(InputIterator1 begin1
, InputIterator1 end1
,
723 InputIterator2 begin2
, InputIterator2 end2
,
724 OutputIterator result
, Predicate pred
,
725 IteratorTag1
, IteratorTag2
, IteratorTag3
)
726 { return _GLIBCXX_STD_P::set_difference(begin1
, end1
,
727 begin2
, end2
, result
, pred
); }
729 // Parallel set_difference for random access iterators
730 template<typename RandomAccessIterator1
, typename RandomAccessIterator2
,
731 typename OutputRandomAccessIterator
, typename Predicate
>
732 OutputRandomAccessIterator
733 set_difference_switch(RandomAccessIterator1 begin1
,
734 RandomAccessIterator1 end1
,
735 RandomAccessIterator2 begin2
,
736 RandomAccessIterator2 end2
,
737 OutputRandomAccessIterator result
, Predicate pred
,
738 random_access_iterator_tag
,
739 random_access_iterator_tag
,
740 random_access_iterator_tag
)
742 if (_GLIBCXX_PARALLEL_CONDITION(
743 static_cast<__gnu_parallel::sequence_index_t
>(end1
- begin1
)
744 >= __gnu_parallel::_Settings::get().set_difference_minimal_n
745 || static_cast<__gnu_parallel::sequence_index_t
>(end2
- begin2
)
746 >= __gnu_parallel::_Settings::get().set_difference_minimal_n
))
747 return __gnu_parallel::parallel_set_difference(begin1
, end1
,
751 return _GLIBCXX_STD_P::set_difference(begin1
, end1
,
752 begin2
, end2
, result
, pred
);
756 template<typename InputIterator1
, typename InputIterator2
,
757 typename OutputIterator
>
758 inline OutputIterator
759 set_difference(InputIterator1 begin1
, InputIterator1 end1
,
760 InputIterator2 begin2
, InputIterator2 end2
,
763 typedef std::iterator_traits
<InputIterator1
> iteratori1_traits
;
764 typedef std::iterator_traits
<InputIterator2
> iteratori2_traits
;
765 typedef std::iterator_traits
<OutputIterator
> iteratoro_traits
;
766 typedef typename
iteratori1_traits::iterator_category
768 typedef typename
iteratori2_traits::iterator_category
770 typedef typename
iteratoro_traits::iterator_category iteratoro_category
;
771 typedef typename
iteratori1_traits::value_type value1_type
;
772 typedef typename
iteratori2_traits::value_type value2_type
;
774 return set_difference_switch(begin1
, end1
, begin2
, end2
, out
,
776 less
<value1_type
, value2_type
>(),
777 iteratori1_category(),
778 iteratori2_category(),
779 iteratoro_category());
783 template<typename InputIterator1
, typename InputIterator2
,
784 typename OutputIterator
, typename Predicate
>
785 inline OutputIterator
786 set_difference(InputIterator1 begin1
, InputIterator1 end1
,
787 InputIterator2 begin2
, InputIterator2 end2
,
788 OutputIterator out
, Predicate pred
)
790 typedef std::iterator_traits
<InputIterator1
> iteratori1_traits
;
791 typedef std::iterator_traits
<InputIterator2
> iteratori2_traits
;
792 typedef std::iterator_traits
<OutputIterator
> iteratoro_traits
;
793 typedef typename
iteratori1_traits::iterator_category
795 typedef typename
iteratori2_traits::iterator_category
797 typedef typename
iteratoro_traits::iterator_category iteratoro_category
;
799 return set_difference_switch(begin1
, end1
, begin2
, end2
, out
, pred
,
800 iteratori1_category(),
801 iteratori2_category(),
802 iteratoro_category());
805 // Sequential fallback
806 template<typename ForwardIterator
>
807 inline ForwardIterator
808 adjacent_find(ForwardIterator begin
, ForwardIterator end
,
809 __gnu_parallel::sequential_tag
)
810 { return _GLIBCXX_STD_P::adjacent_find(begin
, end
); }
812 // Sequential fallback
813 template<typename ForwardIterator
, typename BinaryPredicate
>
814 inline ForwardIterator
815 adjacent_find(ForwardIterator begin
, ForwardIterator end
,
816 BinaryPredicate binary_pred
, __gnu_parallel::sequential_tag
)
817 { return _GLIBCXX_STD_P::adjacent_find(begin
, end
, binary_pred
); }
819 // Parallel algorithm for random access iterators
820 template<typename RandomAccessIterator
>
822 adjacent_find_switch(RandomAccessIterator begin
, RandomAccessIterator end
,
823 random_access_iterator_tag
)
825 typedef iterator_traits
<RandomAccessIterator
> traits_type
;
826 typedef typename
traits_type::value_type value_type
;
828 if (_GLIBCXX_PARALLEL_CONDITION(true))
830 RandomAccessIterator spot
= __gnu_parallel::
831 find_template(begin
, end
- 1, begin
, equal_to
<value_type
>(),
832 __gnu_parallel::adjacent_find_selector()).first
;
833 if (spot
== (end
- 1))
839 return adjacent_find(begin
, end
, __gnu_parallel::sequential_tag());
842 // Sequential fallback for input iterator case
843 template<typename ForwardIterator
, typename IteratorTag
>
844 inline ForwardIterator
845 adjacent_find_switch(ForwardIterator begin
, ForwardIterator end
,
847 { return adjacent_find(begin
, end
, __gnu_parallel::sequential_tag()); }
850 template<typename ForwardIterator
>
851 inline ForwardIterator
852 adjacent_find(ForwardIterator begin
, ForwardIterator end
)
854 typedef iterator_traits
<ForwardIterator
> traits_type
;
855 typedef typename
traits_type::iterator_category iterator_category
;
856 return adjacent_find_switch(begin
, end
, iterator_category());
859 // Sequential fallback for input iterator case
860 template<typename ForwardIterator
, typename BinaryPredicate
,
861 typename IteratorTag
>
862 inline ForwardIterator
863 adjacent_find_switch(ForwardIterator begin
, ForwardIterator end
,
864 BinaryPredicate pred
, IteratorTag
)
865 { return adjacent_find(begin
, end
, pred
,
866 __gnu_parallel::sequential_tag()); }
868 // Parallel algorithm for random access iterators
869 template<typename RandomAccessIterator
, typename BinaryPredicate
>
871 adjacent_find_switch(RandomAccessIterator begin
, RandomAccessIterator end
,
872 BinaryPredicate pred
, random_access_iterator_tag
)
874 if (_GLIBCXX_PARALLEL_CONDITION(true))
875 return __gnu_parallel::find_template(begin
, end
, begin
, pred
,
877 adjacent_find_selector()).first
;
879 return adjacent_find(begin
, end
, pred
,
880 __gnu_parallel::sequential_tag());
884 template<typename ForwardIterator
, typename BinaryPredicate
>
885 inline ForwardIterator
886 adjacent_find(ForwardIterator begin
, ForwardIterator end
,
887 BinaryPredicate pred
)
889 typedef iterator_traits
<ForwardIterator
> traits_type
;
890 typedef typename
traits_type::iterator_category iterator_category
;
891 return adjacent_find_switch(begin
, end
, pred
, iterator_category());
894 // Sequential fallback
895 template<typename InputIterator
, typename T
>
896 inline typename iterator_traits
<InputIterator
>::difference_type
897 count(InputIterator begin
, InputIterator end
, const T
& value
,
898 __gnu_parallel::sequential_tag
)
899 { return _GLIBCXX_STD_P::count(begin
, end
, value
); }
901 // Parallel code for random access iterators
902 template<typename RandomAccessIterator
, typename T
>
903 typename iterator_traits
<RandomAccessIterator
>::difference_type
904 count_switch(RandomAccessIterator begin
, RandomAccessIterator end
,
905 const T
& value
, random_access_iterator_tag
,
906 __gnu_parallel::_Parallelism parallelism_tag
907 = __gnu_parallel::parallel_unbalanced
)
909 typedef iterator_traits
<RandomAccessIterator
> traits_type
;
910 typedef typename
traits_type::value_type value_type
;
911 typedef typename
traits_type::difference_type difference_type
;
912 typedef __gnu_parallel::sequence_index_t sequence_index_t
;
914 if (_GLIBCXX_PARALLEL_CONDITION(
915 static_cast<sequence_index_t
>(end
- begin
)
916 >= __gnu_parallel::_Settings::get().count_minimal_n
917 && __gnu_parallel::is_parallel(parallelism_tag
)))
919 __gnu_parallel::count_selector
<RandomAccessIterator
, difference_type
>
921 difference_type res
= 0;
923 for_each_template_random_access(begin
, end
, value
,
925 std::plus
<sequence_index_t
>(),
926 res
, res
, -1, parallelism_tag
);
930 return count(begin
, end
, value
, __gnu_parallel::sequential_tag());
933 // Sequential fallback for input iterator case.
934 template<typename InputIterator
, typename T
, typename IteratorTag
>
935 inline typename iterator_traits
<InputIterator
>::difference_type
936 count_switch(InputIterator begin
, InputIterator end
, const T
& value
,
938 { return count(begin
, end
, value
, __gnu_parallel::sequential_tag()); }
941 template<typename InputIterator
, typename T
>
942 inline typename iterator_traits
<InputIterator
>::difference_type
943 count(InputIterator begin
, InputIterator end
, const T
& value
,
944 __gnu_parallel::_Parallelism parallelism_tag
)
946 typedef iterator_traits
<InputIterator
> traits_type
;
947 typedef typename
traits_type::iterator_category iterator_category
;
948 return count_switch(begin
, end
, value
, iterator_category(),
952 template<typename InputIterator
, typename T
>
953 inline typename iterator_traits
<InputIterator
>::difference_type
954 count(InputIterator begin
, InputIterator end
, const T
& value
)
956 typedef iterator_traits
<InputIterator
> traits_type
;
957 typedef typename
traits_type::iterator_category iterator_category
;
958 return count_switch(begin
, end
, value
, iterator_category());
962 // Sequential fallback.
963 template<typename InputIterator
, typename Predicate
>
964 inline typename iterator_traits
<InputIterator
>::difference_type
965 count_if(InputIterator begin
, InputIterator end
, Predicate pred
,
966 __gnu_parallel::sequential_tag
)
967 { return _GLIBCXX_STD_P::count_if(begin
, end
, pred
); }
969 // Parallel count_if for random access iterators
970 template<typename RandomAccessIterator
, typename Predicate
>
971 typename iterator_traits
<RandomAccessIterator
>::difference_type
972 count_if_switch(RandomAccessIterator begin
, RandomAccessIterator end
,
973 Predicate pred
, random_access_iterator_tag
,
974 __gnu_parallel::_Parallelism parallelism_tag
975 = __gnu_parallel::parallel_unbalanced
)
977 typedef iterator_traits
<RandomAccessIterator
> traits_type
;
978 typedef typename
traits_type::value_type value_type
;
979 typedef typename
traits_type::difference_type difference_type
;
980 typedef __gnu_parallel::sequence_index_t sequence_index_t
;
982 if (_GLIBCXX_PARALLEL_CONDITION(
983 static_cast<sequence_index_t
>(end
- begin
)
984 >= __gnu_parallel::_Settings::get().count_minimal_n
985 && __gnu_parallel::is_parallel(parallelism_tag
)))
987 difference_type res
= 0;
989 count_if_selector
<RandomAccessIterator
, difference_type
>
992 for_each_template_random_access(begin
, end
, pred
,
994 std::plus
<sequence_index_t
>(),
995 res
, res
, -1, parallelism_tag
);
999 return count_if(begin
, end
, pred
, __gnu_parallel::sequential_tag());
1002 // Sequential fallback for input iterator case.
1003 template<typename InputIterator
, typename Predicate
, typename IteratorTag
>
1004 inline typename iterator_traits
<InputIterator
>::difference_type
1005 count_if_switch(InputIterator begin
, InputIterator end
, Predicate pred
,
1007 { return count_if(begin
, end
, pred
, __gnu_parallel::sequential_tag()); }
1009 // Public interface.
1010 template<typename InputIterator
, typename Predicate
>
1011 inline typename iterator_traits
<InputIterator
>::difference_type
1012 count_if(InputIterator begin
, InputIterator end
, Predicate pred
,
1013 __gnu_parallel::_Parallelism parallelism_tag
)
1015 typedef iterator_traits
<InputIterator
> traits_type
;
1016 typedef typename
traits_type::iterator_category iterator_category
;
1017 return count_if_switch(begin
, end
, pred
, iterator_category(),
1021 template<typename InputIterator
, typename Predicate
>
1022 inline typename iterator_traits
<InputIterator
>::difference_type
1023 count_if(InputIterator begin
, InputIterator end
, Predicate pred
)
1025 typedef iterator_traits
<InputIterator
> traits_type
;
1026 typedef typename
traits_type::iterator_category iterator_category
;
1027 return count_if_switch(begin
, end
, pred
, iterator_category());
1031 // Sequential fallback.
1032 template<typename ForwardIterator1
, typename ForwardIterator2
>
1033 inline ForwardIterator1
1034 search(ForwardIterator1 begin1
, ForwardIterator1 end1
,
1035 ForwardIterator2 begin2
, ForwardIterator2 end2
,
1036 __gnu_parallel::sequential_tag
)
1037 { return _GLIBCXX_STD_P::search(begin1
, end1
, begin2
, end2
); }
1039 // Parallel algorithm for random access iterator
1040 template<typename RandomAccessIterator1
, typename RandomAccessIterator2
>
1041 RandomAccessIterator1
1042 search_switch(RandomAccessIterator1 begin1
, RandomAccessIterator1 end1
,
1043 RandomAccessIterator2 begin2
, RandomAccessIterator2 end2
,
1044 random_access_iterator_tag
, random_access_iterator_tag
)
1046 typedef std::iterator_traits
<RandomAccessIterator1
> iterator1_traits
;
1047 typedef typename
iterator1_traits::value_type value1_type
;
1048 typedef std::iterator_traits
<RandomAccessIterator2
> iterator2_traits
;
1049 typedef typename
iterator2_traits::value_type value2_type
;
1051 if (_GLIBCXX_PARALLEL_CONDITION(true))
1052 return __gnu_parallel::
1053 search_template(begin1
, end1
, begin2
, end2
, __gnu_parallel::
1054 equal_to
<value1_type
, value2_type
>());
1056 return search(begin1
, end1
, begin2
, end2
,
1057 __gnu_parallel::sequential_tag());
1060 // Sequential fallback for input iterator case
1061 template<typename ForwardIterator1
, typename ForwardIterator2
,
1062 typename IteratorTag1
, typename IteratorTag2
>
1063 inline ForwardIterator1
1064 search_switch(ForwardIterator1 begin1
, ForwardIterator1 end1
,
1065 ForwardIterator2 begin2
, ForwardIterator2 end2
,
1066 IteratorTag1
, IteratorTag2
)
1067 { return search(begin1
, end1
, begin2
, end2
,
1068 __gnu_parallel::sequential_tag()); }
1070 // Public interface.
1071 template<typename ForwardIterator1
, typename ForwardIterator2
>
1072 inline ForwardIterator1
1073 search(ForwardIterator1 begin1
, ForwardIterator1 end1
,
1074 ForwardIterator2 begin2
, ForwardIterator2 end2
)
1076 typedef std::iterator_traits
<ForwardIterator1
> iterator1_traits
;
1077 typedef typename
iterator1_traits::iterator_category iterator1_category
;
1078 typedef std::iterator_traits
<ForwardIterator2
> iterator2_traits
;
1079 typedef typename
iterator2_traits::iterator_category iterator2_category
;
1081 return search_switch(begin1
, end1
, begin2
, end2
,
1082 iterator1_category(), iterator2_category());
1085 // Public interface.
1086 template<typename ForwardIterator1
, typename ForwardIterator2
,
1087 typename BinaryPredicate
>
1088 inline ForwardIterator1
1089 search(ForwardIterator1 begin1
, ForwardIterator1 end1
,
1090 ForwardIterator2 begin2
, ForwardIterator2 end2
,
1091 BinaryPredicate pred
, __gnu_parallel::sequential_tag
)
1092 { return _GLIBCXX_STD_P::search(begin1
, end1
, begin2
, end2
, pred
); }
1094 // Parallel algorithm for random access iterator.
1095 template<typename RandomAccessIterator1
, typename RandomAccessIterator2
,
1096 typename BinaryPredicate
>
1097 RandomAccessIterator1
1098 search_switch(RandomAccessIterator1 begin1
, RandomAccessIterator1 end1
,
1099 RandomAccessIterator2 begin2
, RandomAccessIterator2 end2
,
1100 BinaryPredicate pred
,
1101 random_access_iterator_tag
, random_access_iterator_tag
)
1103 if (_GLIBCXX_PARALLEL_CONDITION(true))
1104 return __gnu_parallel::search_template(begin1
, end1
,
1105 begin2
, end2
, pred
);
1107 return search(begin1
, end1
, begin2
, end2
, pred
,
1108 __gnu_parallel::sequential_tag());
1111 // Sequential fallback for input iterator case
1112 template<typename ForwardIterator1
, typename ForwardIterator2
,
1113 typename BinaryPredicate
, typename IteratorTag1
,
1114 typename IteratorTag2
>
1115 inline ForwardIterator1
1116 search_switch(ForwardIterator1 begin1
, ForwardIterator1 end1
,
1117 ForwardIterator2 begin2
, ForwardIterator2 end2
,
1118 BinaryPredicate pred
, IteratorTag1
, IteratorTag2
)
1119 { return search(begin1
, end1
, begin2
, end2
, pred
,
1120 __gnu_parallel::sequential_tag()); }
1123 template<typename ForwardIterator1
, typename ForwardIterator2
,
1124 typename BinaryPredicate
>
1125 inline ForwardIterator1
1126 search(ForwardIterator1 begin1
, ForwardIterator1 end1
,
1127 ForwardIterator2 begin2
, ForwardIterator2 end2
,
1128 BinaryPredicate pred
)
1130 typedef std::iterator_traits
<ForwardIterator1
> iterator1_traits
;
1131 typedef typename
iterator1_traits::iterator_category iterator1_category
;
1132 typedef std::iterator_traits
<ForwardIterator2
> iterator2_traits
;
1133 typedef typename
iterator2_traits::iterator_category iterator2_category
;
1134 return search_switch(begin1
, end1
, begin2
, end2
, pred
,
1135 iterator1_category(), iterator2_category());
1138 // Sequential fallback
1139 template<typename ForwardIterator
, typename Integer
, typename T
>
1140 inline ForwardIterator
1141 search_n(ForwardIterator begin
, ForwardIterator end
, Integer count
,
1142 const T
& val
, __gnu_parallel::sequential_tag
)
1143 { return _GLIBCXX_STD_P::search_n(begin
, end
, count
, val
); }
1145 // Sequential fallback
1146 template<typename ForwardIterator
, typename Integer
, typename T
,
1147 typename BinaryPredicate
>
1148 inline ForwardIterator
1149 search_n(ForwardIterator begin
, ForwardIterator end
, Integer count
,
1150 const T
& val
, BinaryPredicate binary_pred
,
1151 __gnu_parallel::sequential_tag
)
1152 { return _GLIBCXX_STD_P::search_n(begin
, end
, count
, val
, binary_pred
); }
1154 // Public interface.
1155 template<typename ForwardIterator
, typename Integer
, typename T
>
1156 inline ForwardIterator
1157 search_n(ForwardIterator begin
, ForwardIterator end
, Integer count
,
1160 typedef typename iterator_traits
<ForwardIterator
>::value_type value_type
;
1161 return search_n(begin
, end
, count
, val
,
1162 __gnu_parallel::equal_to
<value_type
, T
>());
1165 // Parallel algorithm for random access iterators.
1166 template<typename RandomAccessIterator
, typename Integer
,
1167 typename T
, typename BinaryPredicate
>
1168 RandomAccessIterator
1169 search_n_switch(RandomAccessIterator begin
, RandomAccessIterator end
,
1170 Integer count
, const T
& val
, BinaryPredicate binary_pred
,
1171 random_access_iterator_tag
)
1173 if (_GLIBCXX_PARALLEL_CONDITION(true))
1175 __gnu_parallel::pseudo_sequence
<T
, Integer
> ps(val
, count
);
1176 return __gnu_parallel::search_template(begin
, end
, ps
.begin(),
1177 ps
.end(), binary_pred
);
1180 return std::__search_n(begin
, end
, count
, val
,
1181 binary_pred
, random_access_iterator_tag());
1184 // Sequential fallback for input iterator case.
1185 template<typename ForwardIterator
, typename Integer
, typename T
,
1186 typename BinaryPredicate
, typename IteratorTag
>
1187 inline ForwardIterator
1188 search_n_switch(ForwardIterator begin
, ForwardIterator end
, Integer count
,
1189 const T
& val
, BinaryPredicate binary_pred
, IteratorTag
)
1190 { return __search_n(begin
, end
, count
, val
, binary_pred
, IteratorTag()); }
1192 // Public interface.
1193 template<typename ForwardIterator
, typename Integer
, typename T
,
1194 typename BinaryPredicate
>
1195 inline ForwardIterator
1196 search_n(ForwardIterator begin
, ForwardIterator end
, Integer count
,
1197 const T
& val
, BinaryPredicate binary_pred
)
1199 return search_n_switch(begin
, end
, count
, val
, binary_pred
,
1200 typename
std::iterator_traits
<ForwardIterator
>::
1201 iterator_category());
1205 // Sequential fallback.
1206 template<typename InputIterator
, typename OutputIterator
,
1207 typename UnaryOperation
>
1208 inline OutputIterator
1209 transform(InputIterator begin
, InputIterator end
, OutputIterator result
,
1210 UnaryOperation unary_op
, __gnu_parallel::sequential_tag
)
1211 { return _GLIBCXX_STD_P::transform(begin
, end
, result
, unary_op
); }
1213 // Parallel unary transform for random access iterators.
1214 template<typename RandomAccessIterator1
, typename RandomAccessIterator2
,
1215 typename UnaryOperation
>
1216 RandomAccessIterator2
1217 transform1_switch(RandomAccessIterator1 begin
, RandomAccessIterator1 end
,
1218 RandomAccessIterator2 result
, UnaryOperation unary_op
,
1219 random_access_iterator_tag
, random_access_iterator_tag
,
1220 __gnu_parallel::_Parallelism parallelism_tag
1221 = __gnu_parallel::parallel_balanced
)
1223 if (_GLIBCXX_PARALLEL_CONDITION(
1224 static_cast<__gnu_parallel::sequence_index_t
>(end
- begin
)
1225 >= __gnu_parallel::_Settings::get().transform_minimal_n
1226 && __gnu_parallel::is_parallel(parallelism_tag
)))
1229 typedef __gnu_parallel::iterator_pair
<RandomAccessIterator1
,
1230 RandomAccessIterator2
, random_access_iterator_tag
> ip
;
1231 ip
begin_pair(begin
, result
), end_pair(end
, result
+ (end
- begin
));
1232 __gnu_parallel::transform1_selector
<ip
> functionality
;
1234 for_each_template_random_access(begin_pair
, end_pair
,
1235 unary_op
, functionality
,
1236 __gnu_parallel::dummy_reduct(),
1237 dummy
, dummy
, -1, parallelism_tag
);
1238 return functionality
.finish_iterator
;
1241 return transform(begin
, end
, result
, unary_op
,
1242 __gnu_parallel::sequential_tag());
1245 // Sequential fallback for input iterator case.
1246 template<typename RandomAccessIterator1
, typename RandomAccessIterator2
,
1247 typename UnaryOperation
, typename IteratorTag1
,
1248 typename IteratorTag2
>
1249 inline RandomAccessIterator2
1250 transform1_switch(RandomAccessIterator1 begin
, RandomAccessIterator1 end
,
1251 RandomAccessIterator2 result
, UnaryOperation unary_op
,
1252 IteratorTag1
, IteratorTag2
)
1253 { return transform(begin
, end
, result
, unary_op
,
1254 __gnu_parallel::sequential_tag()); }
1256 // Public interface.
1257 template<typename InputIterator
, typename OutputIterator
,
1258 typename UnaryOperation
>
1259 inline OutputIterator
1260 transform(InputIterator begin
, InputIterator end
, OutputIterator result
,
1261 UnaryOperation unary_op
,
1262 __gnu_parallel::_Parallelism parallelism_tag
)
1264 typedef std::iterator_traits
<InputIterator
> iteratori_traits
;
1265 typedef std::iterator_traits
<OutputIterator
> iteratoro_traits
;
1266 typedef typename
iteratori_traits::iterator_category iteratori_category
;
1267 typedef typename
iteratoro_traits::iterator_category iteratoro_category
;
1269 return transform1_switch(begin
, end
, result
, unary_op
,
1270 iteratori_category(), iteratoro_category(),
1274 template<typename InputIterator
, typename OutputIterator
,
1275 typename UnaryOperation
>
1276 inline OutputIterator
1277 transform(InputIterator begin
, InputIterator end
, OutputIterator result
,
1278 UnaryOperation unary_op
)
1280 typedef std::iterator_traits
<InputIterator
> iteratori_traits
;
1281 typedef std::iterator_traits
<OutputIterator
> iteratoro_traits
;
1282 typedef typename
iteratori_traits::iterator_category iteratori_category
;
1283 typedef typename
iteratoro_traits::iterator_category iteratoro_category
;
1285 return transform1_switch(begin
, end
, result
, unary_op
,
1286 iteratori_category(), iteratoro_category());
1290 // Sequential fallback
1291 template<typename InputIterator1
, typename InputIterator2
,
1292 typename OutputIterator
, typename BinaryOperation
>
1293 inline OutputIterator
1294 transform(InputIterator1 begin1
, InputIterator1 end1
,
1295 InputIterator2 begin2
, OutputIterator result
,
1296 BinaryOperation binary_op
, __gnu_parallel::sequential_tag
)
1297 { return _GLIBCXX_STD_P::transform(begin1
, end1
,
1298 begin2
, result
, binary_op
); }
1300 // Parallel binary transform for random access iterators.
1301 template<typename RandomAccessIterator1
, typename RandomAccessIterator2
,
1302 typename RandomAccessIterator3
, typename BinaryOperation
>
1303 RandomAccessIterator3
1304 transform2_switch(RandomAccessIterator1 begin1
, RandomAccessIterator1 end1
,
1305 RandomAccessIterator2 begin2
,
1306 RandomAccessIterator3 result
, BinaryOperation binary_op
,
1307 random_access_iterator_tag
, random_access_iterator_tag
,
1308 random_access_iterator_tag
,
1309 __gnu_parallel::_Parallelism parallelism_tag
1310 = __gnu_parallel::parallel_balanced
)
1312 if (_GLIBCXX_PARALLEL_CONDITION(
1314 __gnu_parallel::_Settings::get().transform_minimal_n
1315 && __gnu_parallel::is_parallel(parallelism_tag
)))
1318 typedef __gnu_parallel::iterator_triple
<RandomAccessIterator1
,
1319 RandomAccessIterator2
, RandomAccessIterator3
,
1320 random_access_iterator_tag
> ip
;
1321 ip
begin_triple(begin1
, begin2
, result
),
1322 end_triple(end1
, begin2
+ (end1
- begin1
),
1323 result
+ (end1
- begin1
));
1324 __gnu_parallel::transform2_selector
<ip
> functionality
;
1326 for_each_template_random_access(begin_triple
, end_triple
,
1327 binary_op
, functionality
,
1328 __gnu_parallel::dummy_reduct(),
1331 return functionality
.finish_iterator
;
1334 return transform(begin1
, end1
, begin2
, result
, binary_op
,
1335 __gnu_parallel::sequential_tag());
1338 // Sequential fallback for input iterator case.
1339 template<typename InputIterator1
, typename InputIterator2
,
1340 typename OutputIterator
, typename BinaryOperation
,
1341 typename tag1
, typename tag2
, typename tag3
>
1342 inline OutputIterator
1343 transform2_switch(InputIterator1 begin1
, InputIterator1 end1
,
1344 InputIterator2 begin2
, OutputIterator result
,
1345 BinaryOperation binary_op
, tag1
, tag2
, tag3
)
1346 { return transform(begin1
, end1
, begin2
, result
, binary_op
,
1347 __gnu_parallel::sequential_tag()); }
1349 // Public interface.
1350 template<typename InputIterator1
, typename InputIterator2
,
1351 typename OutputIterator
, typename BinaryOperation
>
1352 inline OutputIterator
1353 transform(InputIterator1 begin1
, InputIterator1 end1
,
1354 InputIterator2 begin2
, OutputIterator result
,
1355 BinaryOperation binary_op
,
1356 __gnu_parallel::_Parallelism parallelism_tag
)
1358 typedef std::iterator_traits
<InputIterator1
> iteratori1_traits
;
1359 typedef typename
iteratori1_traits::iterator_category
1360 iteratori1_category
;
1361 typedef std::iterator_traits
<InputIterator2
> iteratori2_traits
;
1362 typedef typename
iteratori2_traits::iterator_category
1363 iteratori2_category
;
1364 typedef std::iterator_traits
<OutputIterator
> iteratoro_traits
;
1365 typedef typename
iteratoro_traits::iterator_category iteratoro_category
;
1367 return transform2_switch(begin1
, end1
, begin2
, result
, binary_op
,
1368 iteratori1_category(), iteratori2_category(),
1369 iteratoro_category(), parallelism_tag
);
1372 template<typename InputIterator1
, typename InputIterator2
,
1373 typename OutputIterator
, typename BinaryOperation
>
1374 inline OutputIterator
1375 transform(InputIterator1 begin1
, InputIterator1 end1
,
1376 InputIterator2 begin2
, OutputIterator result
,
1377 BinaryOperation binary_op
)
1379 typedef std::iterator_traits
<InputIterator1
> iteratori1_traits
;
1380 typedef typename
iteratori1_traits::iterator_category
1381 iteratori1_category
;
1382 typedef std::iterator_traits
<InputIterator2
> iteratori2_traits
;
1383 typedef typename
iteratori2_traits::iterator_category
1384 iteratori2_category
;
1385 typedef std::iterator_traits
<OutputIterator
> iteratoro_traits
;
1386 typedef typename
iteratoro_traits::iterator_category iteratoro_category
;
1388 return transform2_switch(begin1
, end1
, begin2
, result
, binary_op
,
1389 iteratori1_category(), iteratori2_category(),
1390 iteratoro_category());
1393 // Sequential fallback
1394 template<typename ForwardIterator
, typename T
>
1396 replace(ForwardIterator begin
, ForwardIterator end
, const T
& old_value
,
1397 const T
& new_value
, __gnu_parallel::sequential_tag
)
1398 { _GLIBCXX_STD_P::replace(begin
, end
, old_value
, new_value
); }
1400 // Sequential fallback for input iterator case
1401 template<typename ForwardIterator
, typename T
, typename IteratorTag
>
1403 replace_switch(ForwardIterator begin
, ForwardIterator end
,
1404 const T
& old_value
, const T
& new_value
, IteratorTag
)
1405 { replace(begin
, end
, old_value
, new_value
,
1406 __gnu_parallel::sequential_tag()); }
1408 // Parallel replace for random access iterators
1409 template<typename RandomAccessIterator
, typename T
>
1411 replace_switch(RandomAccessIterator begin
, RandomAccessIterator end
,
1412 const T
& old_value
, const T
& new_value
,
1413 random_access_iterator_tag
,
1414 __gnu_parallel::_Parallelism parallelism_tag
1415 = __gnu_parallel::parallel_balanced
)
1417 // XXX parallel version is where?
1418 replace(begin
, end
, old_value
, new_value
,
1419 __gnu_parallel::sequential_tag());
1423 template<typename ForwardIterator
, typename T
>
1425 replace(ForwardIterator begin
, ForwardIterator end
, const T
& old_value
,
1426 const T
& new_value
, __gnu_parallel::_Parallelism parallelism_tag
)
1428 typedef iterator_traits
<ForwardIterator
> traits_type
;
1429 typedef typename
traits_type::iterator_category iterator_category
;
1430 replace_switch(begin
, end
, old_value
, new_value
, iterator_category(),
1434 template<typename ForwardIterator
, typename T
>
1436 replace(ForwardIterator begin
, ForwardIterator end
, const T
& old_value
,
1439 typedef iterator_traits
<ForwardIterator
> traits_type
;
1440 typedef typename
traits_type::iterator_category iterator_category
;
1441 replace_switch(begin
, end
, old_value
, new_value
, iterator_category());
1445 // Sequential fallback
1446 template<typename ForwardIterator
, typename Predicate
, typename T
>
1448 replace_if(ForwardIterator begin
, ForwardIterator end
, Predicate pred
,
1449 const T
& new_value
, __gnu_parallel::sequential_tag
)
1450 { _GLIBCXX_STD_P::replace_if(begin
, end
, pred
, new_value
); }
1452 // Sequential fallback for input iterator case
1453 template<typename ForwardIterator
, typename Predicate
, typename T
,
1454 typename IteratorTag
>
1456 replace_if_switch(ForwardIterator begin
, ForwardIterator end
,
1457 Predicate pred
, const T
& new_value
, IteratorTag
)
1458 { replace_if(begin
, end
, pred
, new_value
,
1459 __gnu_parallel::sequential_tag()); }
1461 // Parallel algorithm for random access iterators.
1462 template<typename RandomAccessIterator
, typename Predicate
, typename T
>
1464 replace_if_switch(RandomAccessIterator begin
, RandomAccessIterator end
,
1465 Predicate pred
, const T
& new_value
,
1466 random_access_iterator_tag
,
1467 __gnu_parallel::_Parallelism parallelism_tag
1468 = __gnu_parallel::parallel_balanced
)
1470 if (_GLIBCXX_PARALLEL_CONDITION(
1471 static_cast<__gnu_parallel::sequence_index_t
>(end
- begin
)
1472 >= __gnu_parallel::_Settings::get().replace_minimal_n
1473 && __gnu_parallel::is_parallel(parallelism_tag
)))
1477 replace_if_selector
<RandomAccessIterator
, Predicate
, T
>
1478 functionality(new_value
);
1480 for_each_template_random_access(begin
, end
, pred
,
1482 __gnu_parallel::dummy_reduct(),
1483 true, dummy
, -1, parallelism_tag
);
1486 replace_if(begin
, end
, pred
, new_value
,
1487 __gnu_parallel::sequential_tag());
1490 // Public interface.
1491 template<typename ForwardIterator
, typename Predicate
, typename T
>
1493 replace_if(ForwardIterator begin
, ForwardIterator end
,
1494 Predicate pred
, const T
& new_value
,
1495 __gnu_parallel::_Parallelism parallelism_tag
)
1497 typedef std::iterator_traits
<ForwardIterator
> iterator_traits
;
1498 typedef typename
iterator_traits::iterator_category iterator_category
;
1499 replace_if_switch(begin
, end
, pred
, new_value
, iterator_category(),
1503 template<typename ForwardIterator
, typename Predicate
, typename T
>
1505 replace_if(ForwardIterator begin
, ForwardIterator end
,
1506 Predicate pred
, const T
& new_value
)
1508 typedef std::iterator_traits
<ForwardIterator
> iterator_traits
;
1509 typedef typename
iterator_traits::iterator_category iterator_category
;
1510 replace_if_switch(begin
, end
, pred
, new_value
, iterator_category());
1513 // Sequential fallback
1514 template<typename ForwardIterator
, typename Generator
>
1516 generate(ForwardIterator begin
, ForwardIterator end
, Generator gen
,
1517 __gnu_parallel::sequential_tag
)
1518 { _GLIBCXX_STD_P::generate(begin
, end
, gen
); }
1520 // Sequential fallback for input iterator case.
1521 template<typename ForwardIterator
, typename Generator
, typename IteratorTag
>
1523 generate_switch(ForwardIterator begin
, ForwardIterator end
, Generator gen
,
1525 { generate(begin
, end
, gen
, __gnu_parallel::sequential_tag()); }
1527 // Parallel algorithm for random access iterators.
1528 template<typename RandomAccessIterator
, typename Generator
>
1530 generate_switch(RandomAccessIterator begin
, RandomAccessIterator end
,
1531 Generator gen
, random_access_iterator_tag
,
1532 __gnu_parallel::_Parallelism parallelism_tag
1533 = __gnu_parallel::parallel_balanced
)
1535 if (_GLIBCXX_PARALLEL_CONDITION(
1536 static_cast<__gnu_parallel::sequence_index_t
>(end
- begin
)
1537 >= __gnu_parallel::_Settings::get().generate_minimal_n
1538 && __gnu_parallel::is_parallel(parallelism_tag
)))
1541 __gnu_parallel::generate_selector
<RandomAccessIterator
>
1544 for_each_template_random_access(begin
, end
, gen
, functionality
,
1545 __gnu_parallel::dummy_reduct(),
1546 true, dummy
, -1, parallelism_tag
);
1549 generate(begin
, end
, gen
, __gnu_parallel::sequential_tag());
1552 // Public interface.
1553 template<typename ForwardIterator
, typename Generator
>
1555 generate(ForwardIterator begin
, ForwardIterator end
,
1556 Generator gen
, __gnu_parallel::_Parallelism parallelism_tag
)
1558 typedef std::iterator_traits
<ForwardIterator
> iterator_traits
;
1559 typedef typename
iterator_traits::iterator_category iterator_category
;
1560 generate_switch(begin
, end
, gen
, iterator_category(), parallelism_tag
);
1563 template<typename ForwardIterator
, typename Generator
>
1565 generate(ForwardIterator begin
, ForwardIterator end
, Generator gen
)
1567 typedef std::iterator_traits
<ForwardIterator
> iterator_traits
;
1568 typedef typename
iterator_traits::iterator_category iterator_category
;
1569 generate_switch(begin
, end
, gen
, iterator_category());
1573 // Sequential fallback.
1574 template<typename OutputIterator
, typename Size
, typename Generator
>
1575 inline OutputIterator
1576 generate_n(OutputIterator begin
, Size n
, Generator gen
,
1577 __gnu_parallel::sequential_tag
)
1578 { return _GLIBCXX_STD_P::generate_n(begin
, n
, gen
); }
1580 // Sequential fallback for input iterator case.
1581 template<typename OutputIterator
, typename Size
, typename Generator
,
1582 typename IteratorTag
>
1583 inline OutputIterator
1584 generate_n_switch(OutputIterator begin
, Size n
, Generator gen
, IteratorTag
)
1585 { return generate_n(begin
, n
, gen
, __gnu_parallel::sequential_tag()); }
1587 // Parallel algorithm for random access iterators.
1588 template<typename RandomAccessIterator
, typename Size
, typename Generator
>
1589 inline RandomAccessIterator
1590 generate_n_switch(RandomAccessIterator begin
, Size n
, Generator gen
,
1591 random_access_iterator_tag
,
1592 __gnu_parallel::_Parallelism parallelism_tag
1593 = __gnu_parallel::parallel_balanced
)
1595 // XXX parallel version is where?
1596 return generate_n(begin
, n
, gen
, __gnu_parallel::sequential_tag());
1599 // Public interface.
1600 template<typename OutputIterator
, typename Size
, typename Generator
>
1601 inline OutputIterator
1602 generate_n(OutputIterator begin
, Size n
, Generator gen
,
1603 __gnu_parallel::_Parallelism parallelism_tag
)
1605 typedef std::iterator_traits
<OutputIterator
> iterator_traits
;
1606 typedef typename
iterator_traits::iterator_category iterator_category
;
1607 return generate_n_switch(begin
, n
, gen
, iterator_category(),
1611 template<typename OutputIterator
, typename Size
, typename Generator
>
1612 inline OutputIterator
1613 generate_n(OutputIterator begin
, Size n
, Generator gen
)
1615 typedef std::iterator_traits
<OutputIterator
> iterator_traits
;
1616 typedef typename
iterator_traits::iterator_category iterator_category
;
1617 return generate_n_switch(begin
, n
, gen
, iterator_category());
1621 // Sequential fallback.
1622 template<typename RandomAccessIterator
>
1624 random_shuffle(RandomAccessIterator begin
, RandomAccessIterator end
,
1625 __gnu_parallel::sequential_tag
)
1626 { _GLIBCXX_STD_P::random_shuffle(begin
, end
); }
1628 // Sequential fallback.
1629 template<typename RandomAccessIterator
, typename RandomNumberGenerator
>
1631 random_shuffle(RandomAccessIterator begin
, RandomAccessIterator end
,
1632 RandomNumberGenerator
& rand
, __gnu_parallel::sequential_tag
)
1633 { _GLIBCXX_STD_P::random_shuffle(begin
, end
, rand
); }
1636 /** @brief Functor wrapper for std::rand(). */
1637 template<typename must_be_int
= int>
1638 struct c_rand_number
1641 operator()(int limit
)
1642 { return rand() % limit
; }
1645 // Fill in random number generator.
1646 template<typename RandomAccessIterator
>
1648 random_shuffle(RandomAccessIterator begin
, RandomAccessIterator end
)
1651 // Parallelization still possible.
1652 __gnu_parallel::random_shuffle(begin
, end
, r
);
1655 // Parallel algorithm for random access iterators.
1656 template<typename RandomAccessIterator
, typename RandomNumberGenerator
>
1658 random_shuffle(RandomAccessIterator begin
, RandomAccessIterator end
,
1659 RandomNumberGenerator
& rand
)
1663 if (_GLIBCXX_PARALLEL_CONDITION(
1664 static_cast<__gnu_parallel::sequence_index_t
>(end
- begin
)
1665 >= __gnu_parallel::_Settings::get().random_shuffle_minimal_n
))
1666 __gnu_parallel::parallel_random_shuffle(begin
, end
, rand
);
1668 __gnu_parallel::sequential_random_shuffle(begin
, end
, rand
);
1671 // Sequential fallback.
1672 template<typename ForwardIterator
, typename Predicate
>
1673 inline ForwardIterator
1674 partition(ForwardIterator begin
, ForwardIterator end
,
1675 Predicate pred
, __gnu_parallel::sequential_tag
)
1676 { return _GLIBCXX_STD_P::partition(begin
, end
, pred
); }
1678 // Sequential fallback for input iterator case.
1679 template<typename ForwardIterator
, typename Predicate
, typename IteratorTag
>
1680 inline ForwardIterator
1681 partition_switch(ForwardIterator begin
, ForwardIterator end
,
1682 Predicate pred
, IteratorTag
)
1683 { return partition(begin
, end
, pred
, __gnu_parallel::sequential_tag()); }
1685 // Parallel algorithm for random access iterators.
1686 template<typename RandomAccessIterator
, typename Predicate
>
1687 RandomAccessIterator
1688 partition_switch(RandomAccessIterator begin
, RandomAccessIterator end
,
1689 Predicate pred
, random_access_iterator_tag
)
1691 if (_GLIBCXX_PARALLEL_CONDITION(
1692 static_cast<__gnu_parallel::sequence_index_t
>(end
- begin
)
1693 >= __gnu_parallel::_Settings::get().partition_minimal_n
))
1695 typedef typename
std::iterator_traits
<RandomAccessIterator
>::
1696 difference_type difference_type
;
1697 difference_type middle
= __gnu_parallel::
1698 parallel_partition(begin
, end
, pred
,
1699 __gnu_parallel::get_max_threads());
1700 return begin
+ middle
;
1703 return partition(begin
, end
, pred
, __gnu_parallel::sequential_tag());
1706 // Public interface.
1707 template<typename ForwardIterator
, typename Predicate
>
1708 inline ForwardIterator
1709 partition(ForwardIterator begin
, ForwardIterator end
, Predicate pred
)
1711 typedef iterator_traits
<ForwardIterator
> traits_type
;
1712 typedef typename
traits_type::iterator_category iterator_category
;
1713 return partition_switch(begin
, end
, pred
, iterator_category());
1718 // Sequential fallback
1719 template<typename RandomAccessIterator
>
1721 sort(RandomAccessIterator begin
, RandomAccessIterator end
,
1722 __gnu_parallel::sequential_tag
)
1723 { _GLIBCXX_STD_P::sort(begin
, end
); }
1725 // Sequential fallback
1726 template<typename RandomAccessIterator
, typename Comparator
>
1728 sort(RandomAccessIterator begin
, RandomAccessIterator end
, Comparator comp
,
1729 __gnu_parallel::sequential_tag
)
1730 { _GLIBCXX_STD_P::sort
<RandomAccessIterator
, Comparator
>(begin
, end
,
1734 template<typename RandomAccessIterator
, typename Comparator
,
1735 typename Parallelism
>
1737 sort(RandomAccessIterator begin
, RandomAccessIterator end
, Comparator comp
,
1738 Parallelism parallelism
)
1740 typedef iterator_traits
<RandomAccessIterator
> traits_type
;
1741 typedef typename
traits_type::value_type value_type
;
1745 if (_GLIBCXX_PARALLEL_CONDITION(
1746 static_cast<__gnu_parallel::sequence_index_t
>(end
- begin
) >=
1747 __gnu_parallel::_Settings::get().sort_minimal_n
))
1748 __gnu_parallel::parallel_sort
<false>(begin
, end
, comp
, parallelism
);
1750 sort(begin
, end
, comp
, __gnu_parallel::sequential_tag());
1754 // Public interface, insert default comparator
1755 template<typename RandomAccessIterator
>
1757 sort(RandomAccessIterator begin
, RandomAccessIterator end
)
1759 typedef iterator_traits
<RandomAccessIterator
> traits_type
;
1760 typedef typename
traits_type::value_type value_type
;
1761 sort(begin
, end
, std::less
<value_type
>(),
1762 __gnu_parallel::default_parallel_tag());
1765 // Public interface, insert default comparator
1766 template<typename RandomAccessIterator
>
1768 sort(RandomAccessIterator begin
, RandomAccessIterator end
,
1769 __gnu_parallel::default_parallel_tag parallelism
)
1771 typedef iterator_traits
<RandomAccessIterator
> traits_type
;
1772 typedef typename
traits_type::value_type value_type
;
1773 sort(begin
, end
, std::less
<value_type
>(), parallelism
);
1776 // Public interface, insert default comparator
1777 template<typename RandomAccessIterator
>
1779 sort(RandomAccessIterator begin
, RandomAccessIterator end
,
1780 __gnu_parallel::parallel_tag parallelism
)
1782 typedef iterator_traits
<RandomAccessIterator
> traits_type
;
1783 typedef typename
traits_type::value_type value_type
;
1784 sort(begin
, end
, std::less
<value_type
>(), parallelism
);
1787 // Public interface, insert default comparator
1788 template<typename RandomAccessIterator
>
1790 sort(RandomAccessIterator begin
, RandomAccessIterator end
,
1791 __gnu_parallel::multiway_mergesort_tag parallelism
)
1793 typedef iterator_traits
<RandomAccessIterator
> traits_type
;
1794 typedef typename
traits_type::value_type value_type
;
1795 sort(begin
, end
, std::less
<value_type
>(), parallelism
);
1798 // Public interface, insert default comparator
1799 template<typename RandomAccessIterator
>
1801 sort(RandomAccessIterator begin
, RandomAccessIterator end
,
1802 __gnu_parallel::multiway_mergesort_sampling_tag parallelism
)
1804 typedef iterator_traits
<RandomAccessIterator
> traits_type
;
1805 typedef typename
traits_type::value_type value_type
;
1806 sort(begin
, end
, std::less
<value_type
>(), parallelism
);
1809 // Public interface, insert default comparator
1810 template<typename RandomAccessIterator
>
1812 sort(RandomAccessIterator begin
, RandomAccessIterator end
,
1813 __gnu_parallel::multiway_mergesort_exact_tag parallelism
)
1815 typedef iterator_traits
<RandomAccessIterator
> traits_type
;
1816 typedef typename
traits_type::value_type value_type
;
1817 sort(begin
, end
, std::less
<value_type
>(), parallelism
);
1820 // Public interface, insert default comparator
1821 template<typename RandomAccessIterator
>
1823 sort(RandomAccessIterator begin
, RandomAccessIterator end
,
1824 __gnu_parallel::quicksort_tag parallelism
)
1826 typedef iterator_traits
<RandomAccessIterator
> traits_type
;
1827 typedef typename
traits_type::value_type value_type
;
1828 sort(begin
, end
, std::less
<value_type
>(), parallelism
);
1831 // Public interface, insert default comparator
1832 template<typename RandomAccessIterator
>
1834 sort(RandomAccessIterator begin
, RandomAccessIterator end
,
1835 __gnu_parallel::balanced_quicksort_tag parallelism
)
1837 typedef iterator_traits
<RandomAccessIterator
> traits_type
;
1838 typedef typename
traits_type::value_type value_type
;
1839 sort(begin
, end
, std::less
<value_type
>(), parallelism
);
1843 template<typename RandomAccessIterator
, typename Comparator
>
1845 sort(RandomAccessIterator begin
, RandomAccessIterator end
, Comparator comp
)
1847 typedef iterator_traits
<RandomAccessIterator
> traits_type
;
1848 typedef typename
traits_type::value_type value_type
;
1849 sort(begin
, end
, comp
, __gnu_parallel::default_parallel_tag());
1853 // stable_sort interface
1856 // Sequential fallback
1857 template<typename RandomAccessIterator
>
1859 stable_sort(RandomAccessIterator begin
, RandomAccessIterator end
,
1860 __gnu_parallel::sequential_tag
)
1861 { _GLIBCXX_STD_P::stable_sort(begin
, end
); }
1863 // Sequential fallback
1864 template<typename RandomAccessIterator
, typename Comparator
>
1866 stable_sort(RandomAccessIterator begin
, RandomAccessIterator end
,
1867 Comparator comp
, __gnu_parallel::sequential_tag
)
1868 { _GLIBCXX_STD_P::stable_sort
<RandomAccessIterator
, Comparator
>(
1869 begin
, end
, comp
); }
1872 template<typename RandomAccessIterator
, typename Comparator
,
1873 typename Parallelism
>
1875 stable_sort(RandomAccessIterator begin
, RandomAccessIterator end
,
1876 Comparator comp
, Parallelism parallelism
)
1878 typedef iterator_traits
<RandomAccessIterator
> traits_type
;
1879 typedef typename
traits_type::value_type value_type
;
1883 if (_GLIBCXX_PARALLEL_CONDITION(
1884 static_cast<__gnu_parallel::sequence_index_t
>(end
- begin
) >=
1885 __gnu_parallel::_Settings::get().sort_minimal_n
))
1886 __gnu_parallel::parallel_sort
<true>(begin
, end
, comp
, parallelism
);
1888 stable_sort(begin
, end
, comp
, __gnu_parallel::sequential_tag());
1892 // Public interface, insert default comparator
1893 template<typename RandomAccessIterator
>
1895 stable_sort(RandomAccessIterator begin
, RandomAccessIterator end
)
1897 typedef iterator_traits
<RandomAccessIterator
> traits_type
;
1898 typedef typename
traits_type::value_type value_type
;
1899 stable_sort(begin
, end
, std::less
<value_type
>(),
1900 __gnu_parallel::default_parallel_tag());
1903 // Public interface, insert default comparator
1904 template<typename RandomAccessIterator
>
1906 stable_sort(RandomAccessIterator begin
, RandomAccessIterator end
,
1907 __gnu_parallel::default_parallel_tag parallelism
)
1909 typedef iterator_traits
<RandomAccessIterator
> traits_type
;
1910 typedef typename
traits_type::value_type value_type
;
1911 stable_sort(begin
, end
, std::less
<value_type
>(), parallelism
);
1914 // Public interface, insert default comparator
1915 template<typename RandomAccessIterator
>
1917 stable_sort(RandomAccessIterator begin
, RandomAccessIterator end
,
1918 __gnu_parallel::parallel_tag parallelism
)
1920 typedef iterator_traits
<RandomAccessIterator
> traits_type
;
1921 typedef typename
traits_type::value_type value_type
;
1922 stable_sort(begin
, end
, std::less
<value_type
>(), parallelism
);
1925 // Public interface, insert default comparator
1926 template<typename RandomAccessIterator
>
1928 stable_sort(RandomAccessIterator begin
, RandomAccessIterator end
,
1929 __gnu_parallel::multiway_mergesort_tag parallelism
)
1931 typedef iterator_traits
<RandomAccessIterator
> traits_type
;
1932 typedef typename
traits_type::value_type value_type
;
1933 stable_sort(begin
, end
, std::less
<value_type
>(), parallelism
);
1936 // Public interface, insert default comparator
1937 template<typename RandomAccessIterator
>
1939 stable_sort(RandomAccessIterator begin
, RandomAccessIterator end
,
1940 __gnu_parallel::quicksort_tag parallelism
)
1942 typedef iterator_traits
<RandomAccessIterator
> traits_type
;
1943 typedef typename
traits_type::value_type value_type
;
1944 stable_sort(begin
, end
, std::less
<value_type
>(), parallelism
);
1947 // Public interface, insert default comparator
1948 template<typename RandomAccessIterator
>
1950 stable_sort(RandomAccessIterator begin
, RandomAccessIterator end
,
1951 __gnu_parallel::balanced_quicksort_tag parallelism
)
1953 typedef iterator_traits
<RandomAccessIterator
> traits_type
;
1954 typedef typename
traits_type::value_type value_type
;
1955 stable_sort(begin
, end
, std::less
<value_type
>(), parallelism
);
1959 template<typename RandomAccessIterator
, typename Comparator
>
1961 stable_sort(RandomAccessIterator begin
, RandomAccessIterator end
,
1964 typedef iterator_traits
<RandomAccessIterator
> traits_type
;
1965 typedef typename
traits_type::value_type value_type
;
1966 stable_sort(begin
, end
, comp
, __gnu_parallel::default_parallel_tag());
1970 // // Sequential fallback
1971 // template<typename RandomAccessIterator>
1973 // stable_sort(RandomAccessIterator begin, RandomAccessIterator end,
1974 // __gnu_parallel::sequential_tag)
1975 // { return _GLIBCXX_STD_P::stable_sort(begin, end); }
1977 // // Sequential fallback
1978 // template<typename RandomAccessIterator, typename Comparator>
1980 // stable_sort(RandomAccessIterator begin, RandomAccessIterator end,
1981 // Comparator comp, __gnu_parallel::sequential_tag)
1982 // { return _GLIBCXX_STD_P::stable_sort(begin, end, comp); }
1984 // template<typename RandomAccessIterator>
1986 // stable_sort(RandomAccessIterator begin, RandomAccessIterator end)
1988 // typedef iterator_traits<RandomAccessIterator> traits_type;
1989 // typedef typename traits_type::value_type value_type;
1990 // stable_sort(begin, end, std::less<value_type>());
1993 // // Parallel algorithm for random access iterators
1994 // template<typename RandomAccessIterator, typename Comparator>
1996 // stable_sort(RandomAccessIterator begin, RandomAccessIterator end,
1999 // if (begin != end)
2001 // if (_GLIBCXX_PARALLEL_CONDITION(
2002 // static_cast<__gnu_parallel::sequence_index_t>(end - begin) >=
2003 // __gnu_parallel::_Settings::get().sort_minimal_n))
2004 // __gnu_parallel::parallel_sort(begin, end, comp,
2005 // __gnu_parallel::parallel_tag());
2007 // stable_sort(begin, end, comp, __gnu_parallel::sequential_tag());
2011 // Sequential fallback
2012 template<typename InputIterator1
, typename InputIterator2
,
2013 typename OutputIterator
>
2014 inline OutputIterator
2015 merge(InputIterator1 begin1
, InputIterator1 end1
, InputIterator2 begin2
,
2016 InputIterator2 end2
, OutputIterator result
,
2017 __gnu_parallel::sequential_tag
)
2018 { return _GLIBCXX_STD_P::merge(begin1
, end1
, begin2
, end2
, result
); }
2020 // Sequential fallback
2021 template<typename InputIterator1
, typename InputIterator2
,
2022 typename OutputIterator
, typename Comparator
>
2023 inline OutputIterator
2024 merge(InputIterator1 begin1
, InputIterator1 end1
, InputIterator2 begin2
,
2025 InputIterator2 end2
, OutputIterator result
, Comparator comp
,
2026 __gnu_parallel::sequential_tag
)
2027 { return _GLIBCXX_STD_P::merge(begin1
, end1
, begin2
, end2
, result
, comp
); }
2029 // Sequential fallback for input iterator case
2030 template<typename InputIterator1
, typename InputIterator2
,
2031 typename OutputIterator
, typename Comparator
,
2032 typename IteratorTag1
, typename IteratorTag2
, typename IteratorTag3
>
2033 inline OutputIterator
2034 merge_switch(InputIterator1 begin1
, InputIterator1 end1
,
2035 InputIterator2 begin2
, InputIterator2 end2
,
2036 OutputIterator result
, Comparator comp
,
2037 IteratorTag1
, IteratorTag2
, IteratorTag3
)
2038 { return _GLIBCXX_STD_P::merge(begin1
, end1
, begin2
, end2
,
2041 // Parallel algorithm for random access iterators
2042 template<typename InputIterator1
, typename InputIterator2
,
2043 typename OutputIterator
, typename Comparator
>
2045 merge_switch(InputIterator1 begin1
, InputIterator1 end1
,
2046 InputIterator2 begin2
, InputIterator2 end2
,
2047 OutputIterator result
, Comparator comp
,
2048 random_access_iterator_tag
, random_access_iterator_tag
,
2049 random_access_iterator_tag
)
2051 if (_GLIBCXX_PARALLEL_CONDITION(
2052 (static_cast<__gnu_parallel::sequence_index_t
>(end1
- begin1
)
2053 >= __gnu_parallel::_Settings::get().merge_minimal_n
2054 || static_cast<__gnu_parallel::sequence_index_t
>(end2
- begin2
)
2055 >= __gnu_parallel::_Settings::get().merge_minimal_n
)))
2056 return __gnu_parallel::parallel_merge_advance(begin1
, end1
,
2058 result
, (end1
- begin1
)
2059 + (end2
- begin2
), comp
);
2061 return __gnu_parallel::merge_advance(begin1
, end1
, begin2
, end2
,
2062 result
, (end1
- begin1
)
2063 + (end2
- begin2
), comp
);
2067 template<typename InputIterator1
, typename InputIterator2
,
2068 typename OutputIterator
, typename Comparator
>
2069 inline OutputIterator
2070 merge(InputIterator1 begin1
, InputIterator1 end1
, InputIterator2 begin2
,
2071 InputIterator2 end2
, OutputIterator result
, Comparator comp
)
2073 typedef typename iterator_traits
<InputIterator1
>::value_type value_type
;
2075 typedef std::iterator_traits
<InputIterator1
> iteratori1_traits
;
2076 typedef std::iterator_traits
<InputIterator2
> iteratori2_traits
;
2077 typedef std::iterator_traits
<OutputIterator
> iteratoro_traits
;
2078 typedef typename
iteratori1_traits::iterator_category
2079 iteratori1_category
;
2080 typedef typename
iteratori2_traits::iterator_category
2081 iteratori2_category
;
2082 typedef typename
iteratoro_traits::iterator_category iteratoro_category
;
2084 return merge_switch(begin1
, end1
, begin2
, end2
, result
, comp
,
2085 iteratori1_category(), iteratori2_category(),
2086 iteratoro_category());
2090 // Public interface, insert default comparator
2091 template<typename InputIterator1
, typename InputIterator2
,
2092 typename OutputIterator
>
2093 inline OutputIterator
2094 merge(InputIterator1 begin1
, InputIterator1 end1
, InputIterator2 begin2
,
2095 InputIterator2 end2
, OutputIterator result
)
2097 typedef std::iterator_traits
<InputIterator1
> iterator1_traits
;
2098 typedef std::iterator_traits
<InputIterator2
> iterator2_traits
;
2099 typedef typename
iterator1_traits::value_type value1_type
;
2100 typedef typename
iterator2_traits::value_type value2_type
;
2102 return merge(begin1
, end1
, begin2
, end2
, result
,
2103 __gnu_parallel::less
<value1_type
, value2_type
>());
2106 // Sequential fallback
2107 template<typename RandomAccessIterator
>
2109 nth_element(RandomAccessIterator begin
, RandomAccessIterator nth
,
2110 RandomAccessIterator end
, __gnu_parallel::sequential_tag
)
2111 { return _GLIBCXX_STD_P::nth_element(begin
, nth
, end
); }
2113 // Sequential fallback
2114 template<typename RandomAccessIterator
, typename Comparator
>
2116 nth_element(RandomAccessIterator begin
, RandomAccessIterator nth
,
2117 RandomAccessIterator end
, Comparator comp
,
2118 __gnu_parallel::sequential_tag
)
2119 { return _GLIBCXX_STD_P::nth_element(begin
, nth
, end
, comp
); }
2122 template<typename RandomAccessIterator
, typename Comparator
>
2124 nth_element(RandomAccessIterator begin
, RandomAccessIterator nth
,
2125 RandomAccessIterator end
, Comparator comp
)
2127 if (_GLIBCXX_PARALLEL_CONDITION(
2128 static_cast<__gnu_parallel::sequence_index_t
>(end
- begin
)
2129 >= __gnu_parallel::_Settings::get().nth_element_minimal_n
))
2130 __gnu_parallel::parallel_nth_element(begin
, nth
, end
, comp
);
2132 nth_element(begin
, nth
, end
, comp
, __gnu_parallel::sequential_tag());
2135 // Public interface, insert default comparator
2136 template<typename RandomAccessIterator
>
2138 nth_element(RandomAccessIterator begin
, RandomAccessIterator nth
,
2139 RandomAccessIterator end
)
2141 typedef iterator_traits
<RandomAccessIterator
> traits_type
;
2142 typedef typename
traits_type::value_type value_type
;
2143 nth_element(begin
, nth
, end
, std::less
<value_type
>());
2146 // Sequential fallback
2147 template<typename RandomAccessIterator
, typename _Compare
>
2149 partial_sort(RandomAccessIterator begin
, RandomAccessIterator middle
,
2150 RandomAccessIterator end
, _Compare comp
,
2151 __gnu_parallel::sequential_tag
)
2152 { _GLIBCXX_STD_P::partial_sort(begin
, middle
, end
, comp
); }
2154 // Sequential fallback
2155 template<typename RandomAccessIterator
>
2157 partial_sort(RandomAccessIterator begin
, RandomAccessIterator middle
,
2158 RandomAccessIterator end
, __gnu_parallel::sequential_tag
)
2159 { _GLIBCXX_STD_P::partial_sort(begin
, middle
, end
); }
2161 // Public interface, parallel algorithm for random access iterators
2162 template<typename RandomAccessIterator
, typename _Compare
>
2164 partial_sort(RandomAccessIterator begin
, RandomAccessIterator middle
,
2165 RandomAccessIterator end
, _Compare comp
)
2167 if (_GLIBCXX_PARALLEL_CONDITION(
2168 static_cast<__gnu_parallel::sequence_index_t
>(end
- begin
)
2169 >= __gnu_parallel::_Settings::get().partial_sort_minimal_n
))
2170 __gnu_parallel::parallel_partial_sort(begin
, middle
, end
, comp
);
2172 partial_sort(begin
, middle
, end
, comp
,
2173 __gnu_parallel::sequential_tag());
2176 // Public interface, insert default comparator
2177 template<typename RandomAccessIterator
>
2179 partial_sort(RandomAccessIterator begin
, RandomAccessIterator middle
,
2180 RandomAccessIterator end
)
2182 typedef iterator_traits
<RandomAccessIterator
> traits_type
;
2183 typedef typename
traits_type::value_type value_type
;
2184 partial_sort(begin
, middle
, end
, std::less
<value_type
>());
2187 // Sequential fallback
2188 template<typename ForwardIterator
>
2189 inline ForwardIterator
2190 max_element(ForwardIterator begin
, ForwardIterator end
,
2191 __gnu_parallel::sequential_tag
)
2192 { return _GLIBCXX_STD_P::max_element(begin
, end
); }
2194 // Sequential fallback
2195 template<typename ForwardIterator
, typename Comparator
>
2196 inline ForwardIterator
2197 max_element(ForwardIterator begin
, ForwardIterator end
, Comparator comp
,
2198 __gnu_parallel::sequential_tag
)
2199 { return _GLIBCXX_STD_P::max_element(begin
, end
, comp
); }
2201 // Sequential fallback for input iterator case
2202 template<typename ForwardIterator
, typename Comparator
, typename IteratorTag
>
2203 inline ForwardIterator
2204 max_element_switch(ForwardIterator begin
, ForwardIterator end
,
2205 Comparator comp
, IteratorTag
)
2206 { return max_element(begin
, end
, comp
, __gnu_parallel::sequential_tag()); }
2208 // Parallel algorithm for random access iterators
2209 template<typename RandomAccessIterator
, typename Comparator
>
2210 RandomAccessIterator
2211 max_element_switch(RandomAccessIterator begin
, RandomAccessIterator end
,
2212 Comparator comp
, random_access_iterator_tag
,
2213 __gnu_parallel::_Parallelism parallelism_tag
2214 = __gnu_parallel::parallel_balanced
)
2216 if (_GLIBCXX_PARALLEL_CONDITION(
2217 static_cast<__gnu_parallel::sequence_index_t
>(end
- begin
)
2218 >= __gnu_parallel::_Settings::get().max_element_minimal_n
2219 && __gnu_parallel::is_parallel(parallelism_tag
)))
2221 RandomAccessIterator
res(begin
);
2222 __gnu_parallel::identity_selector
<RandomAccessIterator
>
2225 for_each_template_random_access(begin
, end
,
2226 __gnu_parallel::nothing(),
2229 max_element_reduct
<Comparator
,
2230 RandomAccessIterator
>(comp
),
2231 res
, res
, -1, parallelism_tag
);
2235 return max_element(begin
, end
, comp
, __gnu_parallel::sequential_tag());
2238 // Public interface, insert default comparator
2239 template<typename ForwardIterator
>
2240 inline ForwardIterator
2241 max_element(ForwardIterator begin
, ForwardIterator end
,
2242 __gnu_parallel::_Parallelism parallelism_tag
)
2244 typedef typename iterator_traits
<ForwardIterator
>::value_type value_type
;
2245 return max_element(begin
, end
, std::less
<value_type
>(), parallelism_tag
);
2248 template<typename ForwardIterator
>
2249 inline ForwardIterator
2250 max_element(ForwardIterator begin
, ForwardIterator end
)
2252 typedef typename iterator_traits
<ForwardIterator
>::value_type value_type
;
2253 return max_element(begin
, end
, std::less
<value_type
>());
2257 template<typename ForwardIterator
, typename Comparator
>
2258 inline ForwardIterator
2259 max_element(ForwardIterator begin
, ForwardIterator end
, Comparator comp
,
2260 __gnu_parallel::_Parallelism parallelism_tag
)
2262 typedef iterator_traits
<ForwardIterator
> traits_type
;
2263 typedef typename
traits_type::iterator_category iterator_category
;
2264 return max_element_switch(begin
, end
, comp
, iterator_category(),
2268 template<typename ForwardIterator
, typename Comparator
>
2269 inline ForwardIterator
2270 max_element(ForwardIterator begin
, ForwardIterator end
, Comparator comp
)
2272 typedef iterator_traits
<ForwardIterator
> traits_type
;
2273 typedef typename
traits_type::iterator_category iterator_category
;
2274 return max_element_switch(begin
, end
, comp
, iterator_category());
2278 // Sequential fallback
2279 template<typename ForwardIterator
>
2280 inline ForwardIterator
2281 min_element(ForwardIterator begin
, ForwardIterator end
,
2282 __gnu_parallel::sequential_tag
)
2283 { return _GLIBCXX_STD_P::min_element(begin
, end
); }
2285 // Sequential fallback
2286 template<typename ForwardIterator
, typename Comparator
>
2287 inline ForwardIterator
2288 min_element(ForwardIterator begin
, ForwardIterator end
, Comparator comp
,
2289 __gnu_parallel::sequential_tag
)
2290 { return _GLIBCXX_STD_P::min_element(begin
, end
, comp
); }
2292 // Sequential fallback for input iterator case
2293 template<typename ForwardIterator
, typename Comparator
, typename IteratorTag
>
2294 inline ForwardIterator
2295 min_element_switch(ForwardIterator begin
, ForwardIterator end
,
2296 Comparator comp
, IteratorTag
)
2297 { return min_element(begin
, end
, comp
, __gnu_parallel::sequential_tag()); }
2299 // Parallel algorithm for random access iterators
2300 template<typename RandomAccessIterator
, typename Comparator
>
2301 RandomAccessIterator
2302 min_element_switch(RandomAccessIterator begin
, RandomAccessIterator end
,
2303 Comparator comp
, random_access_iterator_tag
,
2304 __gnu_parallel::_Parallelism parallelism_tag
2305 = __gnu_parallel::parallel_balanced
)
2307 if (_GLIBCXX_PARALLEL_CONDITION(
2308 static_cast<__gnu_parallel::sequence_index_t
>(end
- begin
)
2309 >= __gnu_parallel::_Settings::get().min_element_minimal_n
2310 && __gnu_parallel::is_parallel(parallelism_tag
)))
2312 RandomAccessIterator
res(begin
);
2313 __gnu_parallel::identity_selector
<RandomAccessIterator
>
2316 for_each_template_random_access(begin
, end
,
2317 __gnu_parallel::nothing(),
2320 min_element_reduct
<Comparator
,
2321 RandomAccessIterator
>(comp
),
2322 res
, res
, -1, parallelism_tag
);
2326 return min_element(begin
, end
, comp
, __gnu_parallel::sequential_tag());
2329 // Public interface, insert default comparator
2330 template<typename ForwardIterator
>
2331 inline ForwardIterator
2332 min_element(ForwardIterator begin
, ForwardIterator end
,
2333 __gnu_parallel::_Parallelism parallelism_tag
)
2335 typedef typename iterator_traits
<ForwardIterator
>::value_type value_type
;
2336 return min_element(begin
, end
, std::less
<value_type
>(), parallelism_tag
);
2339 template<typename ForwardIterator
>
2340 inline ForwardIterator
2341 min_element(ForwardIterator begin
, ForwardIterator end
)
2343 typedef typename iterator_traits
<ForwardIterator
>::value_type value_type
;
2344 return min_element(begin
, end
, std::less
<value_type
>());
2348 template<typename ForwardIterator
, typename Comparator
>
2349 inline ForwardIterator
2350 min_element(ForwardIterator begin
, ForwardIterator end
, Comparator comp
,
2351 __gnu_parallel::_Parallelism parallelism_tag
)
2353 typedef iterator_traits
<ForwardIterator
> traits_type
;
2354 typedef typename
traits_type::iterator_category iterator_category
;
2355 return min_element_switch(begin
, end
, comp
, iterator_category(),
2359 template<typename ForwardIterator
, typename Comparator
>
2360 inline ForwardIterator
2361 min_element(ForwardIterator begin
, ForwardIterator end
, Comparator comp
)
2363 typedef iterator_traits
<ForwardIterator
> traits_type
;
2364 typedef typename
traits_type::iterator_category iterator_category
;
2365 return min_element_switch(begin
, end
, comp
, iterator_category());
2370 #endif /* _GLIBCXX_ALGORITHM_H */