libstdc++
algo.h
Go to the documentation of this file.
1 // -*- C++ -*-
2 
3 // Copyright (C) 2007, 2008, 2009 Free Software Foundation, Inc.
4 //
5 // This file is part of the GNU ISO C++ Library. This library is free
6 // software; you can redistribute it and/or modify it under the terms
7 // of the GNU General Public License as published by the Free Software
8 // Foundation; either version 3, or (at your option) any later
9 // version.
10 
11 // This library is distributed in the hope that it will be useful, but
12 // WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 // General Public License for more details.
15 
16 // Under Section 7 of GPL version 3, you are granted additional
17 // permissions described in the GCC Runtime Library Exception, version
18 // 3.1, as published by the Free Software Foundation.
19 
20 // You should have received a copy of the GNU General Public License and
21 // a copy of the GCC Runtime Library Exception along with this program;
22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23 // <http://www.gnu.org/licenses/>.
24 
25 /** @file parallel/algo.h
26  * @brief Parallel STL function calls corresponding to the stl_algo.h header.
27  *
28  * The functions defined here mainly do case switches and
29  * call the actual parallelized versions in other files.
30  * Inlining policy: Functions that basically only contain one function call,
31  * are declared inline.
32  * This file is a GNU parallel extension to the Standard C++ Library.
33  */
34 
35 // Written by Johannes Singler and Felix Putze.
36 
37 #ifndef _GLIBCXX_PARALLEL_ALGO_H
38 #define _GLIBCXX_PARALLEL_ALGO_H 1
39 
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>
51 #include <parallel/for_each.h>
52 #include <parallel/find.h>
54 #include <parallel/search.h>
56 #include <parallel/partition.h>
57 #include <parallel/merge.h>
58 #include <parallel/unique_copy.h>
60 
61 namespace std
62 {
63 namespace __parallel
64 {
65  // Sequential fallback
66  template<typename InputIterator, typename Function>
67  inline Function
68  for_each(InputIterator begin, InputIterator end, Function f,
70  { return _GLIBCXX_STD_P::for_each(begin, end, f); }
71 
72 
73  // Sequential fallback for input iterator case
74  template<typename InputIterator, typename Function, typename IteratorTag>
75  inline Function
76  for_each_switch(InputIterator begin, InputIterator end, Function f,
77  IteratorTag)
78  { return for_each(begin, end, f, __gnu_parallel::sequential_tag()); }
79 
80  // Parallel algorithm for random access iterators
81  template<typename RandomAccessIterator, typename Function>
82  Function
83  for_each_switch(RandomAccessIterator begin, RandomAccessIterator end,
84  Function f, random_access_iterator_tag,
85  __gnu_parallel::_Parallelism parallelism_tag
87  {
89  static_cast<__gnu_parallel::sequence_index_t>(end - begin)
90  >= __gnu_parallel::_Settings::get().for_each_minimal_n
91  && __gnu_parallel::is_parallel(parallelism_tag)))
92  {
93  bool dummy;
95 
96  return __gnu_parallel::
97  for_each_template_random_access(begin, end, f, functionality,
99  true, dummy, -1, parallelism_tag);
100  }
101  else
102  return for_each(begin, end, f, __gnu_parallel::sequential_tag());
103  }
104 
105  // Public interface
106  template<typename Iterator, typename Function>
107  inline Function
108  for_each(Iterator begin, Iterator end, Function f,
109  __gnu_parallel::_Parallelism parallelism_tag)
110  {
111  typedef std::iterator_traits<Iterator> iterator_traits;
112  typedef typename iterator_traits::iterator_category iterator_category;
113  return for_each_switch(begin, end, f, iterator_category(),
114  parallelism_tag);
115  }
116 
117  template<typename Iterator, typename Function>
118  inline Function
119  for_each(Iterator begin, Iterator end, Function f)
120  {
121  typedef std::iterator_traits<Iterator> iterator_traits;
122  typedef typename iterator_traits::iterator_category iterator_category;
123  return for_each_switch(begin, end, f, iterator_category());
124  }
125 
126 
127  // Sequential fallback
128  template<typename InputIterator, typename T>
129  inline InputIterator
130  find(InputIterator begin, InputIterator end, const T& val,
132  { return _GLIBCXX_STD_P::find(begin, end, val); }
133 
134  // Sequential fallback for input iterator case
135  template<typename InputIterator, typename T, typename IteratorTag>
136  inline InputIterator
137  find_switch(InputIterator begin, InputIterator end, const T& val,
138  IteratorTag)
139  { return _GLIBCXX_STD_P::find(begin, end, val); }
140 
141  // Parallel find for random access iterators
142  template<typename RandomAccessIterator, typename T>
143  RandomAccessIterator
144  find_switch(RandomAccessIterator begin, RandomAccessIterator end,
145  const T& val, random_access_iterator_tag)
146  {
147  typedef iterator_traits<RandomAccessIterator> traits_type;
148  typedef typename traits_type::value_type value_type;
149 
150  if (_GLIBCXX_PARALLEL_CONDITION(true))
151  {
152  binder2nd<__gnu_parallel::equal_to<value_type, const T&> >
154  return __gnu_parallel::find_template(begin, end, begin, comp,
155  __gnu_parallel::
156  find_if_selector()).first;
157  }
158  else
159  return _GLIBCXX_STD_P::find(begin, end, val);
160  }
161 
162  // Public interface
163  template<typename InputIterator, typename T>
164  inline InputIterator
165  find(InputIterator begin, InputIterator end, const T& val)
166  {
167  typedef std::iterator_traits<InputIterator> iterator_traits;
168  typedef typename iterator_traits::iterator_category iterator_category;
169  return find_switch(begin, end, val, iterator_category());
170  }
171 
172  // Sequential fallback
173  template<typename InputIterator, typename Predicate>
174  inline InputIterator
175  find_if(InputIterator begin, InputIterator end, Predicate pred,
177  { return _GLIBCXX_STD_P::find_if(begin, end, pred); }
178 
179  // Sequential fallback for input iterator case
180  template<typename InputIterator, typename Predicate, typename IteratorTag>
181  inline InputIterator
182  find_if_switch(InputIterator begin, InputIterator end, Predicate pred,
183  IteratorTag)
184  { return _GLIBCXX_STD_P::find_if(begin, end, pred); }
185 
186  // Parallel find_if for random access iterators
187  template<typename RandomAccessIterator, typename Predicate>
188  RandomAccessIterator
189  find_if_switch(RandomAccessIterator begin, RandomAccessIterator end,
190  Predicate pred, random_access_iterator_tag)
191  {
192  if (_GLIBCXX_PARALLEL_CONDITION(true))
193  return __gnu_parallel::find_template(begin, end, begin, pred,
194  __gnu_parallel::
195  find_if_selector()).first;
196  else
197  return _GLIBCXX_STD_P::find_if(begin, end, pred);
198  }
199 
200  // Public interface
201  template<typename InputIterator, typename Predicate>
202  inline InputIterator
203  find_if(InputIterator begin, InputIterator end, Predicate pred)
204  {
205  typedef std::iterator_traits<InputIterator> iterator_traits;
206  typedef typename iterator_traits::iterator_category iterator_category;
207  return find_if_switch(begin, end, pred, iterator_category());
208  }
209 
210  // Sequential fallback
211  template<typename InputIterator, typename ForwardIterator>
212  inline InputIterator
213  find_first_of(InputIterator begin1, InputIterator end1,
214  ForwardIterator begin2, ForwardIterator end2,
216  { return _GLIBCXX_STD_P::find_first_of(begin1, end1, begin2, end2); }
217 
218  // Sequential fallback
219  template<typename InputIterator, typename ForwardIterator,
220  typename BinaryPredicate>
221  inline InputIterator
222  find_first_of(InputIterator begin1, InputIterator end1,
223  ForwardIterator begin2, ForwardIterator end2,
224  BinaryPredicate comp, __gnu_parallel::sequential_tag)
225  { return _GLIBCXX_STD_P::find_first_of(begin1, end1, begin2, end2, comp); }
226 
227  // Sequential fallback for input iterator type
228  template<typename InputIterator, typename ForwardIterator,
229  typename IteratorTag1, typename IteratorTag2>
230  inline InputIterator
231  find_first_of_switch(InputIterator begin1, InputIterator end1,
232  ForwardIterator begin2, ForwardIterator end2,
233  IteratorTag1, IteratorTag2)
234  { return find_first_of(begin1, end1, begin2, end2,
236 
237  // Parallel algorithm for random access iterators
238  template<typename RandomAccessIterator, typename ForwardIterator,
239  typename BinaryPredicate, typename IteratorTag>
240  inline RandomAccessIterator
241  find_first_of_switch(RandomAccessIterator begin1,
242  RandomAccessIterator end1,
243  ForwardIterator begin2, ForwardIterator end2,
244  BinaryPredicate comp, random_access_iterator_tag,
245  IteratorTag)
246  {
247  return __gnu_parallel::
248  find_template(begin1, end1, begin1, comp,
250  <ForwardIterator>(begin2, end2)).first;
251  }
252 
253  // Sequential fallback for input iterator type
254  template<typename InputIterator, typename ForwardIterator,
255  typename BinaryPredicate, typename IteratorTag1,
256  typename IteratorTag2>
257  inline InputIterator
258  find_first_of_switch(InputIterator begin1, InputIterator end1,
259  ForwardIterator begin2, ForwardIterator end2,
260  BinaryPredicate comp, IteratorTag1, IteratorTag2)
261  { return find_first_of(begin1, end1, begin2, end2, comp,
263 
264  // Public interface
265  template<typename InputIterator, typename ForwardIterator,
266  typename BinaryPredicate>
267  inline InputIterator
268  find_first_of(InputIterator begin1, InputIterator end1,
269  ForwardIterator begin2, ForwardIterator end2,
270  BinaryPredicate comp)
271  {
272  typedef std::iterator_traits<InputIterator> iteratori_traits;
273  typedef std::iterator_traits<ForwardIterator> iteratorf_traits;
274  typedef typename iteratori_traits::iterator_category iteratori_category;
275  typedef typename iteratorf_traits::iterator_category iteratorf_category;
276 
277  return find_first_of_switch(begin1, end1, begin2, end2, comp,
278  iteratori_category(), iteratorf_category());
279  }
280 
281  // Public interface, insert default comparator
282  template<typename InputIterator, typename ForwardIterator>
283  inline InputIterator
284  find_first_of(InputIterator begin1, InputIterator end1,
285  ForwardIterator begin2, ForwardIterator end2)
286  {
287  typedef std::iterator_traits<InputIterator> iteratori_traits;
288  typedef std::iterator_traits<ForwardIterator> iteratorf_traits;
289  typedef typename iteratori_traits::value_type valuei_type;
290  typedef typename iteratorf_traits::value_type valuef_type;
291 
292  return _GLIBCXX_STD_P::find_first_of(begin1, end1, begin2, end2,
294  }
295 
296  // Sequential fallback
297  template<typename InputIterator, typename OutputIterator>
298  inline OutputIterator
299  unique_copy(InputIterator begin1, InputIterator end1, OutputIterator out,
301  { return _GLIBCXX_STD_P::unique_copy(begin1, end1, out); }
302 
303  // Sequential fallback
304  template<typename InputIterator, typename OutputIterator,
305  typename Predicate>
306  inline OutputIterator
307  unique_copy(InputIterator begin1, InputIterator end1, OutputIterator out,
308  Predicate pred, __gnu_parallel::sequential_tag)
309  { return _GLIBCXX_STD_P::unique_copy(begin1, end1, out, pred); }
310 
311  // Sequential fallback for input iterator case
312  template<typename InputIterator, typename OutputIterator,
313  typename Predicate, typename IteratorTag1, typename IteratorTag2>
314  inline OutputIterator
315  unique_copy_switch(InputIterator begin, InputIterator last,
316  OutputIterator out, Predicate pred,
317  IteratorTag1, IteratorTag2)
318  { return _GLIBCXX_STD_P::unique_copy(begin, last, out, pred); }
319 
320  // Parallel unique_copy for random access iterators
321  template<typename RandomAccessIterator, typename RandomAccessOutputIterator,
322  typename Predicate>
323  RandomAccessOutputIterator
324  unique_copy_switch(RandomAccessIterator begin, RandomAccessIterator last,
325  RandomAccessOutputIterator out, Predicate pred,
326  random_access_iterator_tag, random_access_iterator_tag)
327  {
329  static_cast<__gnu_parallel::sequence_index_t>(last - begin)
330  > __gnu_parallel::_Settings::get().unique_copy_minimal_n))
331  return __gnu_parallel::parallel_unique_copy(begin, last, out, pred);
332  else
333  return _GLIBCXX_STD_P::unique_copy(begin, last, out, pred);
334  }
335 
336  // Public interface
337  template<typename InputIterator, typename OutputIterator>
338  inline OutputIterator
339  unique_copy(InputIterator begin1, InputIterator end1, OutputIterator out)
340  {
341  typedef std::iterator_traits<InputIterator> iteratori_traits;
342  typedef std::iterator_traits<OutputIterator> iteratoro_traits;
343  typedef typename iteratori_traits::iterator_category iteratori_category;
344  typedef typename iteratori_traits::value_type value_type;
345  typedef typename iteratoro_traits::iterator_category iteratoro_category;
346 
347  return unique_copy_switch(begin1, end1, out, equal_to<value_type>(),
348  iteratori_category(), iteratoro_category());
349  }
350 
351  // Public interface
352  template<typename InputIterator, typename OutputIterator, typename Predicate>
353  inline OutputIterator
354  unique_copy(InputIterator begin1, InputIterator end1, OutputIterator out,
355  Predicate pred)
356  {
357  typedef std::iterator_traits<InputIterator> iteratori_traits;
358  typedef std::iterator_traits<OutputIterator> iteratoro_traits;
359  typedef typename iteratori_traits::iterator_category iteratori_category;
360  typedef typename iteratoro_traits::iterator_category iteratoro_category;
361 
362  return unique_copy_switch(begin1, end1, out, pred, iteratori_category(),
363  iteratoro_category());
364  }
365 
366  // Sequential fallback
367  template<typename InputIterator1, typename InputIterator2,
368  typename OutputIterator>
369  inline OutputIterator
370  set_union(InputIterator1 begin1, InputIterator1 end1,
371  InputIterator2 begin2, InputIterator2 end2,
372  OutputIterator out, __gnu_parallel::sequential_tag)
373  { return _GLIBCXX_STD_P::set_union(begin1, end1, begin2, end2, out); }
374 
375  // Sequential fallback
376  template<typename InputIterator1, typename InputIterator2,
377  typename OutputIterator, typename Predicate>
378  inline OutputIterator
379  set_union(InputIterator1 begin1, InputIterator1 end1,
380  InputIterator2 begin2, InputIterator2 end2,
381  OutputIterator out, Predicate pred,
383  { return _GLIBCXX_STD_P::set_union(begin1, end1,
384  begin2, end2, out, pred); }
385 
386  // Sequential fallback for input iterator case
387  template<typename InputIterator1, typename InputIterator2,
388  typename Predicate, typename OutputIterator,
389  typename IteratorTag1, typename IteratorTag2, typename IteratorTag3>
390  inline OutputIterator
391  set_union_switch(InputIterator1 begin1, InputIterator1 end1,
392  InputIterator2 begin2, InputIterator2 end2,
393  OutputIterator result, Predicate pred, IteratorTag1,
394  IteratorTag2, IteratorTag3)
395  { return _GLIBCXX_STD_P::set_union(begin1, end1,
396  begin2, end2, result, pred); }
397 
398  // Parallel set_union for random access iterators
399  template<typename RandomAccessIterator1, typename RandomAccessIterator2,
400  typename OutputRandomAccessIterator, typename Predicate>
401  OutputRandomAccessIterator
402  set_union_switch(RandomAccessIterator1 begin1, RandomAccessIterator1 end1,
403  RandomAccessIterator2 begin2, RandomAccessIterator2 end2,
404  OutputRandomAccessIterator result, Predicate pred,
405  random_access_iterator_tag, random_access_iterator_tag,
406  random_access_iterator_tag)
407  {
409  static_cast<__gnu_parallel::sequence_index_t>(end1 - begin1)
410  >= __gnu_parallel::_Settings::get().set_union_minimal_n
411  || static_cast<__gnu_parallel::sequence_index_t>(end2 - begin2)
412  >= __gnu_parallel::_Settings::get().set_union_minimal_n))
413  return __gnu_parallel::parallel_set_union(begin1, end1,
414  begin2, end2, result, pred);
415  else
416  return _GLIBCXX_STD_P::set_union(begin1, end1,
417  begin2, end2, result, pred);
418  }
419 
420  // Public interface
421  template<typename InputIterator1, typename InputIterator2,
422  typename OutputIterator>
423  inline OutputIterator
424  set_union(InputIterator1 begin1, InputIterator1 end1,
425  InputIterator2 begin2, InputIterator2 end2, OutputIterator out)
426  {
427  typedef std::iterator_traits<InputIterator1> iteratori1_traits;
428  typedef std::iterator_traits<InputIterator2> iteratori2_traits;
429  typedef std::iterator_traits<OutputIterator> iteratoro_traits;
430  typedef typename iteratori1_traits::iterator_category
431  iteratori1_category;
432  typedef typename iteratori2_traits::iterator_category
433  iteratori2_category;
434  typedef typename iteratoro_traits::iterator_category iteratoro_category;
435  typedef typename iteratori1_traits::value_type value1_type;
436  typedef typename iteratori2_traits::value_type value2_type;
437 
438  return set_union_switch(begin1, end1, begin2, end2, out,
440  iteratori1_category(), iteratori2_category(),
441  iteratoro_category());
442  }
443 
444  // Public interface
445  template<typename InputIterator1, typename InputIterator2,
446  typename OutputIterator, typename Predicate>
447  inline OutputIterator
448  set_union(InputIterator1 begin1, InputIterator1 end1,
449  InputIterator2 begin2, InputIterator2 end2,
450  OutputIterator out, Predicate pred)
451  {
452  typedef std::iterator_traits<InputIterator1> iteratori1_traits;
453  typedef std::iterator_traits<InputIterator2> iteratori2_traits;
454  typedef std::iterator_traits<OutputIterator> iteratoro_traits;
455  typedef typename iteratori1_traits::iterator_category
456  iteratori1_category;
457  typedef typename iteratori2_traits::iterator_category
458  iteratori2_category;
459  typedef typename iteratoro_traits::iterator_category iteratoro_category;
460 
461  return set_union_switch(begin1, end1, begin2, end2, out, pred,
462  iteratori1_category(), iteratori2_category(),
463  iteratoro_category());
464  }
465 
466  // Sequential fallback.
467  template<typename InputIterator1, typename InputIterator2,
468  typename OutputIterator>
469  inline OutputIterator
470  set_intersection(InputIterator1 begin1, InputIterator1 end1,
471  InputIterator2 begin2, InputIterator2 end2,
472  OutputIterator out, __gnu_parallel::sequential_tag)
473  { return _GLIBCXX_STD_P::set_intersection(begin1, end1,
474  begin2, end2, out); }
475 
476  // Sequential fallback.
477  template<typename InputIterator1, typename InputIterator2,
478  typename OutputIterator, typename Predicate>
479  inline OutputIterator
480  set_intersection(InputIterator1 begin1, InputIterator1 end1,
481  InputIterator2 begin2, InputIterator2 end2,
482  OutputIterator out, Predicate pred,
484  { return _GLIBCXX_STD_P::set_intersection(begin1, end1, begin2, end2,
485  out, pred); }
486 
487  // Sequential fallback for input iterator case
488  template<typename InputIterator1, typename InputIterator2,
489  typename Predicate, typename OutputIterator,
490  typename IteratorTag1, typename IteratorTag2,
491  typename IteratorTag3>
492  inline OutputIterator
493  set_intersection_switch(InputIterator1 begin1, InputIterator1 end1,
494  InputIterator2 begin2, InputIterator2 end2,
495  OutputIterator result, Predicate pred,
496  IteratorTag1, IteratorTag2, IteratorTag3)
497  { return _GLIBCXX_STD_P::set_intersection(begin1, end1, begin2,
498  end2, result, pred); }
499 
500  // Parallel set_intersection for random access iterators
501  template<typename RandomAccessIterator1, typename RandomAccessIterator2,
502  typename OutputRandomAccessIterator, typename Predicate>
503  OutputRandomAccessIterator
504  set_intersection_switch(RandomAccessIterator1 begin1,
505  RandomAccessIterator1 end1,
506  RandomAccessIterator2 begin2,
507  RandomAccessIterator2 end2,
508  OutputRandomAccessIterator result,
509  Predicate pred,
510  random_access_iterator_tag,
511  random_access_iterator_tag,
512  random_access_iterator_tag)
513  {
515  static_cast<__gnu_parallel::sequence_index_t>(end1 - begin1)
516  >= __gnu_parallel::_Settings::get().set_union_minimal_n
517  || static_cast<__gnu_parallel::sequence_index_t>(end2 - begin2)
518  >= __gnu_parallel::_Settings::get().set_union_minimal_n))
519  return __gnu_parallel::parallel_set_intersection(begin1, end1, begin2,
520  end2, result, pred);
521  else
522  return _GLIBCXX_STD_P::set_intersection(begin1, end1, begin2,
523  end2, result, pred);
524  }
525 
526  // Public interface
527  template<typename InputIterator1, typename InputIterator2,
528  typename OutputIterator>
529  inline OutputIterator
530  set_intersection(InputIterator1 begin1, InputIterator1 end1,
531  InputIterator2 begin2, InputIterator2 end2,
532  OutputIterator out)
533  {
534  typedef std::iterator_traits<InputIterator1> iteratori1_traits;
535  typedef std::iterator_traits<InputIterator2> iteratori2_traits;
536  typedef std::iterator_traits<OutputIterator> iteratoro_traits;
537  typedef typename iteratori1_traits::iterator_category
538  iteratori1_category;
539  typedef typename iteratori2_traits::iterator_category
540  iteratori2_category;
541  typedef typename iteratoro_traits::iterator_category iteratoro_category;
542  typedef typename iteratori1_traits::value_type value1_type;
543  typedef typename iteratori2_traits::value_type value2_type;
544 
545  return set_intersection_switch(begin1, end1, begin2, end2, out,
546  __gnu_parallel::
547  less<value1_type, value2_type>(),
548  iteratori1_category(),
549  iteratori2_category(),
550  iteratoro_category());
551  }
552 
553  template<typename InputIterator1, typename InputIterator2,
554  typename OutputIterator, typename Predicate>
555  inline OutputIterator
556  set_intersection(InputIterator1 begin1, InputIterator1 end1,
557  InputIterator2 begin2, InputIterator2 end2,
558  OutputIterator out, Predicate pred)
559  {
560  typedef std::iterator_traits<InputIterator1> iteratori1_traits;
561  typedef std::iterator_traits<InputIterator2> iteratori2_traits;
562  typedef std::iterator_traits<OutputIterator> iteratoro_traits;
563  typedef typename iteratori1_traits::iterator_category
564  iteratori1_category;
565  typedef typename iteratori2_traits::iterator_category
566  iteratori2_category;
567  typedef typename iteratoro_traits::iterator_category iteratoro_category;
568 
569  return set_intersection_switch(begin1, end1, begin2, end2, out, pred,
570  iteratori1_category(),
571  iteratori2_category(),
572  iteratoro_category());
573  }
574 
575  // Sequential fallback
576  template<typename InputIterator1, typename InputIterator2,
577  typename OutputIterator>
578  inline OutputIterator
579  set_symmetric_difference(InputIterator1 begin1, InputIterator1 end1,
580  InputIterator2 begin2, InputIterator2 end2,
581  OutputIterator out,
583  { return _GLIBCXX_STD_P::set_symmetric_difference(begin1,end1,
584  begin2, end2, out); }
585 
586  // Sequential fallback
587  template<typename InputIterator1, typename InputIterator2,
588  typename OutputIterator, typename Predicate>
589  inline OutputIterator
590  set_symmetric_difference(InputIterator1 begin1, InputIterator1 end1,
591  InputIterator2 begin2, InputIterator2 end2,
592  OutputIterator out, Predicate pred,
594  { return _GLIBCXX_STD_P::set_symmetric_difference(begin1, end1, begin2,
595  end2, out, pred); }
596 
597  // Sequential fallback for input iterator case
598  template<typename InputIterator1, typename InputIterator2,
599  typename Predicate, typename OutputIterator,
600  typename IteratorTag1, typename IteratorTag2,
601  typename IteratorTag3>
602  inline OutputIterator
603  set_symmetric_difference_switch(InputIterator1 begin1,
604  InputIterator1 end1,
605  InputIterator2 begin2,
606  InputIterator2 end2,
607  OutputIterator result, Predicate pred,
608  IteratorTag1, IteratorTag2, IteratorTag3)
609  { return _GLIBCXX_STD_P::set_symmetric_difference(begin1, end1,
610  begin2, end2,
611  result, pred); }
612 
613  // Parallel set_symmetric_difference for random access iterators
614  template<typename RandomAccessIterator1, typename RandomAccessIterator2,
615  typename OutputRandomAccessIterator, typename Predicate>
616  OutputRandomAccessIterator
617  set_symmetric_difference_switch(RandomAccessIterator1 begin1,
618  RandomAccessIterator1 end1,
619  RandomAccessIterator2 begin2,
620  RandomAccessIterator2 end2,
621  OutputRandomAccessIterator result,
622  Predicate pred,
623  random_access_iterator_tag,
624  random_access_iterator_tag,
625  random_access_iterator_tag)
626  {
628  static_cast<__gnu_parallel::sequence_index_t>(end1 - begin1)
629  >= __gnu_parallel::_Settings::get().set_symmetric_difference_minimal_n
630  || static_cast<__gnu_parallel::sequence_index_t>(end2 - begin2)
631  >= __gnu_parallel::_Settings::get().set_symmetric_difference_minimal_n))
632  return __gnu_parallel::parallel_set_symmetric_difference(begin1, end1,
633  begin2, end2,
634  result, pred);
635  else
636  return _GLIBCXX_STD_P::set_symmetric_difference(begin1, end1,
637  begin2, end2,
638  result, pred);
639  }
640 
641  // Public interface.
642  template<typename InputIterator1, typename InputIterator2,
643  typename OutputIterator>
644  inline OutputIterator
645  set_symmetric_difference(InputIterator1 begin1, InputIterator1 end1,
646  InputIterator2 begin2, InputIterator2 end2,
647  OutputIterator out)
648  {
649  typedef std::iterator_traits<InputIterator1> iteratori1_traits;
650  typedef std::iterator_traits<InputIterator2> iteratori2_traits;
651  typedef std::iterator_traits<OutputIterator> iteratoro_traits;
652  typedef typename iteratori1_traits::iterator_category
653  iteratori1_category;
654  typedef typename iteratori2_traits::iterator_category
655  iteratori2_category;
656  typedef typename iteratoro_traits::iterator_category iteratoro_category;
657  typedef typename iteratori1_traits::value_type value1_type;
658  typedef typename iteratori2_traits::value_type value2_type;
659 
660  return set_symmetric_difference_switch(begin1, end1, begin2, end2, out,
661  __gnu_parallel::
662  less<value1_type, value2_type>(),
663  iteratori1_category(),
664  iteratori2_category(),
665  iteratoro_category());
666  }
667 
668  // Public interface.
669  template<typename InputIterator1, typename InputIterator2,
670  typename OutputIterator, typename Predicate>
671  inline OutputIterator
672  set_symmetric_difference(InputIterator1 begin1, InputIterator1 end1,
673  InputIterator2 begin2, InputIterator2 end2,
674  OutputIterator out, Predicate pred)
675  {
676  typedef std::iterator_traits<InputIterator1> iteratori1_traits;
677  typedef std::iterator_traits<InputIterator2> iteratori2_traits;
678  typedef std::iterator_traits<OutputIterator> iteratoro_traits;
679  typedef typename iteratori1_traits::iterator_category
680  iteratori1_category;
681  typedef typename iteratori2_traits::iterator_category
682  iteratori2_category;
683  typedef typename iteratoro_traits::iterator_category iteratoro_category;
684 
685  return set_symmetric_difference_switch(begin1, end1, begin2, end2, out,
686  pred, iteratori1_category(),
687  iteratori2_category(),
688  iteratoro_category());
689  }
690 
691  // Sequential fallback.
692  template<typename InputIterator1, typename InputIterator2,
693  typename OutputIterator>
694  inline OutputIterator
695  set_difference(InputIterator1 begin1, InputIterator1 end1,
696  InputIterator2 begin2, InputIterator2 end2,
697  OutputIterator out, __gnu_parallel::sequential_tag)
698  { return _GLIBCXX_STD_P::set_difference(begin1,end1, begin2, end2, out); }
699 
700  // Sequential fallback.
701  template<typename InputIterator1, typename InputIterator2,
702  typename OutputIterator, typename Predicate>
703  inline OutputIterator
704  set_difference(InputIterator1 begin1, InputIterator1 end1,
705  InputIterator2 begin2, InputIterator2 end2,
706  OutputIterator out, Predicate pred,
708  { return _GLIBCXX_STD_P::set_difference(begin1, end1,
709  begin2, end2, out, pred); }
710 
711  // Sequential fallback for input iterator case.
712  template<typename InputIterator1, typename InputIterator2,
713  typename Predicate, typename OutputIterator,
714  typename IteratorTag1, typename IteratorTag2, typename IteratorTag3>
715  inline OutputIterator
716  set_difference_switch(InputIterator1 begin1, InputIterator1 end1,
717  InputIterator2 begin2, InputIterator2 end2,
718  OutputIterator result, Predicate pred,
719  IteratorTag1, IteratorTag2, IteratorTag3)
720  { return _GLIBCXX_STD_P::set_difference(begin1, end1,
721  begin2, end2, result, pred); }
722 
723  // Parallel set_difference for random access iterators
724  template<typename RandomAccessIterator1, typename RandomAccessIterator2,
725  typename OutputRandomAccessIterator, typename Predicate>
726  OutputRandomAccessIterator
727  set_difference_switch(RandomAccessIterator1 begin1,
728  RandomAccessIterator1 end1,
729  RandomAccessIterator2 begin2,
730  RandomAccessIterator2 end2,
731  OutputRandomAccessIterator result, Predicate pred,
732  random_access_iterator_tag,
733  random_access_iterator_tag,
734  random_access_iterator_tag)
735  {
737  static_cast<__gnu_parallel::sequence_index_t>(end1 - begin1)
738  >= __gnu_parallel::_Settings::get().set_difference_minimal_n
739  || static_cast<__gnu_parallel::sequence_index_t>(end2 - begin2)
740  >= __gnu_parallel::_Settings::get().set_difference_minimal_n))
741  return __gnu_parallel::parallel_set_difference(begin1, end1,
742  begin2, end2,
743  result, pred);
744  else
745  return _GLIBCXX_STD_P::set_difference(begin1, end1,
746  begin2, end2, result, pred);
747  }
748 
749  // Public interface
750  template<typename InputIterator1, typename InputIterator2,
751  typename OutputIterator>
752  inline OutputIterator
753  set_difference(InputIterator1 begin1, InputIterator1 end1,
754  InputIterator2 begin2, InputIterator2 end2,
755  OutputIterator out)
756  {
757  typedef std::iterator_traits<InputIterator1> iteratori1_traits;
758  typedef std::iterator_traits<InputIterator2> iteratori2_traits;
759  typedef std::iterator_traits<OutputIterator> iteratoro_traits;
760  typedef typename iteratori1_traits::iterator_category
761  iteratori1_category;
762  typedef typename iteratori2_traits::iterator_category
763  iteratori2_category;
764  typedef typename iteratoro_traits::iterator_category iteratoro_category;
765  typedef typename iteratori1_traits::value_type value1_type;
766  typedef typename iteratori2_traits::value_type value2_type;
767 
768  return set_difference_switch(begin1, end1, begin2, end2, out,
769  __gnu_parallel::
770  less<value1_type, value2_type>(),
771  iteratori1_category(),
772  iteratori2_category(),
773  iteratoro_category());
774  }
775 
776  // Public interface
777  template<typename InputIterator1, typename InputIterator2,
778  typename OutputIterator, typename Predicate>
779  inline OutputIterator
780  set_difference(InputIterator1 begin1, InputIterator1 end1,
781  InputIterator2 begin2, InputIterator2 end2,
782  OutputIterator out, Predicate pred)
783  {
784  typedef std::iterator_traits<InputIterator1> iteratori1_traits;
785  typedef std::iterator_traits<InputIterator2> iteratori2_traits;
786  typedef std::iterator_traits<OutputIterator> iteratoro_traits;
787  typedef typename iteratori1_traits::iterator_category
788  iteratori1_category;
789  typedef typename iteratori2_traits::iterator_category
790  iteratori2_category;
791  typedef typename iteratoro_traits::iterator_category iteratoro_category;
792 
793  return set_difference_switch(begin1, end1, begin2, end2, out, pred,
794  iteratori1_category(),
795  iteratori2_category(),
796  iteratoro_category());
797  }
798 
799  // Sequential fallback
800  template<typename ForwardIterator>
801  inline ForwardIterator
802  adjacent_find(ForwardIterator begin, ForwardIterator end,
804  { return _GLIBCXX_STD_P::adjacent_find(begin, end); }
805 
806  // Sequential fallback
807  template<typename ForwardIterator, typename BinaryPredicate>
808  inline ForwardIterator
809  adjacent_find(ForwardIterator begin, ForwardIterator end,
810  BinaryPredicate binary_pred, __gnu_parallel::sequential_tag)
811  { return _GLIBCXX_STD_P::adjacent_find(begin, end, binary_pred); }
812 
813  // Parallel algorithm for random access iterators
814  template<typename RandomAccessIterator>
815  RandomAccessIterator
816  adjacent_find_switch(RandomAccessIterator begin, RandomAccessIterator end,
817  random_access_iterator_tag)
818  {
819  typedef iterator_traits<RandomAccessIterator> traits_type;
820  typedef typename traits_type::value_type value_type;
821 
822  if (_GLIBCXX_PARALLEL_CONDITION(true))
823  {
824  RandomAccessIterator spot = __gnu_parallel::
825  find_template(begin, end - 1, begin, equal_to<value_type>(),
827  if (spot == (end - 1))
828  return end;
829  else
830  return spot;
831  }
832  else
833  return adjacent_find(begin, end, __gnu_parallel::sequential_tag());
834  }
835 
836  // Sequential fallback for input iterator case
837  template<typename ForwardIterator, typename IteratorTag>
838  inline ForwardIterator
839  adjacent_find_switch(ForwardIterator begin, ForwardIterator end,
840  IteratorTag)
841  { return adjacent_find(begin, end, __gnu_parallel::sequential_tag()); }
842 
843  // Public interface
844  template<typename ForwardIterator>
845  inline ForwardIterator
846  adjacent_find(ForwardIterator begin, ForwardIterator end)
847  {
848  typedef iterator_traits<ForwardIterator> traits_type;
849  typedef typename traits_type::iterator_category iterator_category;
850  return adjacent_find_switch(begin, end, iterator_category());
851  }
852 
853  // Sequential fallback for input iterator case
854  template<typename ForwardIterator, typename BinaryPredicate,
855  typename IteratorTag>
856  inline ForwardIterator
857  adjacent_find_switch(ForwardIterator begin, ForwardIterator end,
858  BinaryPredicate pred, IteratorTag)
859  { return adjacent_find(begin, end, pred,
861 
862  // Parallel algorithm for random access iterators
863  template<typename RandomAccessIterator, typename BinaryPredicate>
864  RandomAccessIterator
865  adjacent_find_switch(RandomAccessIterator begin, RandomAccessIterator end,
866  BinaryPredicate pred, random_access_iterator_tag)
867  {
868  if (_GLIBCXX_PARALLEL_CONDITION(true))
869  return __gnu_parallel::find_template(begin, end, begin, pred,
870  __gnu_parallel::
871  adjacent_find_selector()).first;
872  else
873  return adjacent_find(begin, end, pred,
875  }
876 
877  // Public interface
878  template<typename ForwardIterator, typename BinaryPredicate>
879  inline ForwardIterator
880  adjacent_find(ForwardIterator begin, ForwardIterator end,
881  BinaryPredicate pred)
882  {
883  typedef iterator_traits<ForwardIterator> traits_type;
884  typedef typename traits_type::iterator_category iterator_category;
885  return adjacent_find_switch(begin, end, pred, iterator_category());
886  }
887 
888  // Sequential fallback
889  template<typename InputIterator, typename T>
890  inline typename iterator_traits<InputIterator>::difference_type
891  count(InputIterator begin, InputIterator end, const T& value,
893  { return _GLIBCXX_STD_P::count(begin, end, value); }
894 
895  // Parallel code for random access iterators
896  template<typename RandomAccessIterator, typename T>
897  typename iterator_traits<RandomAccessIterator>::difference_type
898  count_switch(RandomAccessIterator begin, RandomAccessIterator end,
899  const T& value, random_access_iterator_tag,
900  __gnu_parallel::_Parallelism parallelism_tag
902  {
903  typedef iterator_traits<RandomAccessIterator> traits_type;
904  typedef typename traits_type::value_type value_type;
905  typedef typename traits_type::difference_type difference_type;
907 
909  static_cast<sequence_index_t>(end - begin)
910  >= __gnu_parallel::_Settings::get().count_minimal_n
911  && __gnu_parallel::is_parallel(parallelism_tag)))
912  {
914  functionality;
915  difference_type res = 0;
917  for_each_template_random_access(begin, end, value,
918  functionality,
920  res, res, -1, parallelism_tag);
921  return res;
922  }
923  else
924  return count(begin, end, value, __gnu_parallel::sequential_tag());
925  }
926 
927  // Sequential fallback for input iterator case.
928  template<typename InputIterator, typename T, typename IteratorTag>
929  inline typename iterator_traits<InputIterator>::difference_type
930  count_switch(InputIterator begin, InputIterator end, const T& value,
931  IteratorTag)
932  { return count(begin, end, value, __gnu_parallel::sequential_tag()); }
933 
934  // Public interface.
935  template<typename InputIterator, typename T>
936  inline typename iterator_traits<InputIterator>::difference_type
937  count(InputIterator begin, InputIterator end, const T& value,
938  __gnu_parallel::_Parallelism parallelism_tag)
939  {
940  typedef iterator_traits<InputIterator> traits_type;
941  typedef typename traits_type::iterator_category iterator_category;
942  return count_switch(begin, end, value, iterator_category(),
943  parallelism_tag);
944  }
945 
946  template<typename InputIterator, typename T>
947  inline typename iterator_traits<InputIterator>::difference_type
948  count(InputIterator begin, InputIterator end, const T& value)
949  {
950  typedef iterator_traits<InputIterator> traits_type;
951  typedef typename traits_type::iterator_category iterator_category;
952  return count_switch(begin, end, value, iterator_category());
953  }
954 
955 
956  // Sequential fallback.
957  template<typename InputIterator, typename Predicate>
958  inline typename iterator_traits<InputIterator>::difference_type
959  count_if(InputIterator begin, InputIterator end, Predicate pred,
961  { return _GLIBCXX_STD_P::count_if(begin, end, pred); }
962 
963  // Parallel count_if for random access iterators
964  template<typename RandomAccessIterator, typename Predicate>
965  typename iterator_traits<RandomAccessIterator>::difference_type
966  count_if_switch(RandomAccessIterator begin, RandomAccessIterator end,
967  Predicate pred, random_access_iterator_tag,
968  __gnu_parallel::_Parallelism parallelism_tag
970  {
971  typedef iterator_traits<RandomAccessIterator> traits_type;
972  typedef typename traits_type::value_type value_type;
973  typedef typename traits_type::difference_type difference_type;
975 
977  static_cast<sequence_index_t>(end - begin)
978  >= __gnu_parallel::_Settings::get().count_minimal_n
979  && __gnu_parallel::is_parallel(parallelism_tag)))
980  {
981  difference_type res = 0;
984  functionality;
986  for_each_template_random_access(begin, end, pred,
987  functionality,
989  res, res, -1, parallelism_tag);
990  return res;
991  }
992  else
993  return count_if(begin, end, pred, __gnu_parallel::sequential_tag());
994  }
995 
996  // Sequential fallback for input iterator case.
997  template<typename InputIterator, typename Predicate, typename IteratorTag>
998  inline typename iterator_traits<InputIterator>::difference_type
999  count_if_switch(InputIterator begin, InputIterator end, Predicate pred,
1000  IteratorTag)
1001  { return count_if(begin, end, pred, __gnu_parallel::sequential_tag()); }
1002 
1003  // Public interface.
1004  template<typename InputIterator, typename Predicate>
1005  inline typename iterator_traits<InputIterator>::difference_type
1006  count_if(InputIterator begin, InputIterator end, Predicate pred,
1007  __gnu_parallel::_Parallelism parallelism_tag)
1008  {
1009  typedef iterator_traits<InputIterator> traits_type;
1010  typedef typename traits_type::iterator_category iterator_category;
1011  return count_if_switch(begin, end, pred, iterator_category(),
1012  parallelism_tag);
1013  }
1014 
1015  template<typename InputIterator, typename Predicate>
1016  inline typename iterator_traits<InputIterator>::difference_type
1017  count_if(InputIterator begin, InputIterator end, Predicate pred)
1018  {
1019  typedef iterator_traits<InputIterator> traits_type;
1020  typedef typename traits_type::iterator_category iterator_category;
1021  return count_if_switch(begin, end, pred, iterator_category());
1022  }
1023 
1024 
1025  // Sequential fallback.
1026  template<typename ForwardIterator1, typename ForwardIterator2>
1027  inline ForwardIterator1
1028  search(ForwardIterator1 begin1, ForwardIterator1 end1,
1029  ForwardIterator2 begin2, ForwardIterator2 end2,
1031  { return _GLIBCXX_STD_P::search(begin1, end1, begin2, end2); }
1032 
1033  // Parallel algorithm for random access iterator
1034  template<typename RandomAccessIterator1, typename RandomAccessIterator2>
1035  RandomAccessIterator1
1036  search_switch(RandomAccessIterator1 begin1, RandomAccessIterator1 end1,
1037  RandomAccessIterator2 begin2, RandomAccessIterator2 end2,
1038  random_access_iterator_tag, random_access_iterator_tag)
1039  {
1040  typedef std::iterator_traits<RandomAccessIterator1> iterator1_traits;
1041  typedef typename iterator1_traits::value_type value1_type;
1042  typedef std::iterator_traits<RandomAccessIterator2> iterator2_traits;
1043  typedef typename iterator2_traits::value_type value2_type;
1044 
1045  if (_GLIBCXX_PARALLEL_CONDITION(true))
1046  return __gnu_parallel::
1047  search_template(begin1, end1, begin2, end2, __gnu_parallel::
1048  equal_to<value1_type, value2_type>());
1049  else
1050  return search(begin1, end1, begin2, end2,
1052  }
1053 
1054  // Sequential fallback for input iterator case
1055  template<typename ForwardIterator1, typename ForwardIterator2,
1056  typename IteratorTag1, typename IteratorTag2>
1057  inline ForwardIterator1
1058  search_switch(ForwardIterator1 begin1, ForwardIterator1 end1,
1059  ForwardIterator2 begin2, ForwardIterator2 end2,
1060  IteratorTag1, IteratorTag2)
1061  { return search(begin1, end1, begin2, end2,
1063 
1064  // Public interface.
1065  template<typename ForwardIterator1, typename ForwardIterator2>
1066  inline ForwardIterator1
1067  search(ForwardIterator1 begin1, ForwardIterator1 end1,
1068  ForwardIterator2 begin2, ForwardIterator2 end2)
1069  {
1070  typedef std::iterator_traits<ForwardIterator1> iterator1_traits;
1071  typedef typename iterator1_traits::iterator_category iterator1_category;
1072  typedef std::iterator_traits<ForwardIterator2> iterator2_traits;
1073  typedef typename iterator2_traits::iterator_category iterator2_category;
1074 
1075  return search_switch(begin1, end1, begin2, end2,
1076  iterator1_category(), iterator2_category());
1077  }
1078 
1079  // Public interface.
1080  template<typename ForwardIterator1, typename ForwardIterator2,
1081  typename BinaryPredicate>
1082  inline ForwardIterator1
1083  search(ForwardIterator1 begin1, ForwardIterator1 end1,
1084  ForwardIterator2 begin2, ForwardIterator2 end2,
1085  BinaryPredicate pred, __gnu_parallel::sequential_tag)
1086  { return _GLIBCXX_STD_P::search(begin1, end1, begin2, end2, pred); }
1087 
1088  // Parallel algorithm for random access iterator.
1089  template<typename RandomAccessIterator1, typename RandomAccessIterator2,
1090  typename BinaryPredicate>
1091  RandomAccessIterator1
1092  search_switch(RandomAccessIterator1 begin1, RandomAccessIterator1 end1,
1093  RandomAccessIterator2 begin2, RandomAccessIterator2 end2,
1094  BinaryPredicate pred,
1095  random_access_iterator_tag, random_access_iterator_tag)
1096  {
1097  if (_GLIBCXX_PARALLEL_CONDITION(true))
1098  return __gnu_parallel::search_template(begin1, end1,
1099  begin2, end2, pred);
1100  else
1101  return search(begin1, end1, begin2, end2, pred,
1103  }
1104 
1105  // Sequential fallback for input iterator case
1106  template<typename ForwardIterator1, typename ForwardIterator2,
1107  typename BinaryPredicate, typename IteratorTag1,
1108  typename IteratorTag2>
1109  inline ForwardIterator1
1110  search_switch(ForwardIterator1 begin1, ForwardIterator1 end1,
1111  ForwardIterator2 begin2, ForwardIterator2 end2,
1112  BinaryPredicate pred, IteratorTag1, IteratorTag2)
1113  { return search(begin1, end1, begin2, end2, pred,
1115 
1116  // Public interface
1117  template<typename ForwardIterator1, typename ForwardIterator2,
1118  typename BinaryPredicate>
1119  inline ForwardIterator1
1120  search(ForwardIterator1 begin1, ForwardIterator1 end1,
1121  ForwardIterator2 begin2, ForwardIterator2 end2,
1122  BinaryPredicate pred)
1123  {
1124  typedef std::iterator_traits<ForwardIterator1> iterator1_traits;
1125  typedef typename iterator1_traits::iterator_category iterator1_category;
1126  typedef std::iterator_traits<ForwardIterator2> iterator2_traits;
1127  typedef typename iterator2_traits::iterator_category iterator2_category;
1128  return search_switch(begin1, end1, begin2, end2, pred,
1129  iterator1_category(), iterator2_category());
1130  }
1131 
1132  // Sequential fallback
1133  template<typename ForwardIterator, typename Integer, typename T>
1134  inline ForwardIterator
1135  search_n(ForwardIterator begin, ForwardIterator end, Integer count,
1136  const T& val, __gnu_parallel::sequential_tag)
1137  { return _GLIBCXX_STD_P::search_n(begin, end, count, val); }
1138 
1139  // Sequential fallback
1140  template<typename ForwardIterator, typename Integer, typename T,
1141  typename BinaryPredicate>
1142  inline ForwardIterator
1143  search_n(ForwardIterator begin, ForwardIterator end, Integer count,
1144  const T& val, BinaryPredicate binary_pred,
1146  { return _GLIBCXX_STD_P::search_n(begin, end, count, val, binary_pred); }
1147 
1148  // Public interface.
1149  template<typename ForwardIterator, typename Integer, typename T>
1150  inline ForwardIterator
1151  search_n(ForwardIterator begin, ForwardIterator end, Integer count,
1152  const T& val)
1153  {
1154  typedef typename iterator_traits<ForwardIterator>::value_type value_type;
1155  return _GLIBCXX_STD_P::search_n(begin, end, count, val,
1157  }
1158 
1159  // Parallel algorithm for random access iterators.
1160  template<typename RandomAccessIterator, typename Integer,
1161  typename T, typename BinaryPredicate>
1162  RandomAccessIterator
1163  search_n_switch(RandomAccessIterator begin, RandomAccessIterator end,
1164  Integer count, const T& val, BinaryPredicate binary_pred,
1165  random_access_iterator_tag)
1166  {
1167  if (_GLIBCXX_PARALLEL_CONDITION(true))
1168  {
1170  return __gnu_parallel::search_template(begin, end, ps.begin(),
1171  ps.end(), binary_pred);
1172  }
1173  else
1174  return std::__search_n(begin, end, count, val,
1175  binary_pred, random_access_iterator_tag());
1176  }
1177 
1178  // Sequential fallback for input iterator case.
1179  template<typename ForwardIterator, typename Integer, typename T,
1180  typename BinaryPredicate, typename IteratorTag>
1181  inline ForwardIterator
1182  search_n_switch(ForwardIterator begin, ForwardIterator end, Integer count,
1183  const T& val, BinaryPredicate binary_pred, IteratorTag)
1184  { return __search_n(begin, end, count, val, binary_pred, IteratorTag()); }
1185 
1186  // Public interface.
1187  template<typename ForwardIterator, typename Integer, typename T,
1188  typename BinaryPredicate>
1189  inline ForwardIterator
1190  search_n(ForwardIterator begin, ForwardIterator end, Integer count,
1191  const T& val, BinaryPredicate binary_pred)
1192  {
1193  return search_n_switch(begin, end, count, val, binary_pred,
1195  iterator_category());
1196  }
1197 
1198 
1199  // Sequential fallback.
1200  template<typename InputIterator, typename OutputIterator,
1201  typename UnaryOperation>
1202  inline OutputIterator
1203  transform(InputIterator begin, InputIterator end, OutputIterator result,
1204  UnaryOperation unary_op, __gnu_parallel::sequential_tag)
1205  { return _GLIBCXX_STD_P::transform(begin, end, result, unary_op); }
1206 
1207  // Parallel unary transform for random access iterators.
1208  template<typename RandomAccessIterator1, typename RandomAccessIterator2,
1209  typename UnaryOperation>
1210  RandomAccessIterator2
1211  transform1_switch(RandomAccessIterator1 begin, RandomAccessIterator1 end,
1212  RandomAccessIterator2 result, UnaryOperation unary_op,
1213  random_access_iterator_tag, random_access_iterator_tag,
1214  __gnu_parallel::_Parallelism parallelism_tag
1216  {
1218  static_cast<__gnu_parallel::sequence_index_t>(end - begin)
1219  >= __gnu_parallel::_Settings::get().transform_minimal_n
1220  && __gnu_parallel::is_parallel(parallelism_tag)))
1221  {
1222  bool dummy = true;
1223  typedef __gnu_parallel::iterator_pair<RandomAccessIterator1,
1224  RandomAccessIterator2, random_access_iterator_tag> ip;
1225  ip begin_pair(begin, result), end_pair(end, result + (end - begin));
1228  for_each_template_random_access(begin_pair, end_pair,
1229  unary_op, functionality,
1231  dummy, dummy, -1, parallelism_tag);
1232  return functionality.finish_iterator;
1233  }
1234  else
1235  return transform(begin, end, result, unary_op,
1237  }
1238 
1239  // Sequential fallback for input iterator case.
1240  template<typename RandomAccessIterator1, typename RandomAccessIterator2,
1241  typename UnaryOperation, typename IteratorTag1,
1242  typename IteratorTag2>
1243  inline RandomAccessIterator2
1244  transform1_switch(RandomAccessIterator1 begin, RandomAccessIterator1 end,
1245  RandomAccessIterator2 result, UnaryOperation unary_op,
1246  IteratorTag1, IteratorTag2)
1247  { return transform(begin, end, result, unary_op,
1249 
1250  // Public interface.
1251  template<typename InputIterator, typename OutputIterator,
1252  typename UnaryOperation>
1253  inline OutputIterator
1254  transform(InputIterator begin, InputIterator end, OutputIterator result,
1255  UnaryOperation unary_op,
1256  __gnu_parallel::_Parallelism parallelism_tag)
1257  {
1258  typedef std::iterator_traits<InputIterator> iteratori_traits;
1259  typedef std::iterator_traits<OutputIterator> iteratoro_traits;
1260  typedef typename iteratori_traits::iterator_category iteratori_category;
1261  typedef typename iteratoro_traits::iterator_category iteratoro_category;
1262 
1263  return transform1_switch(begin, end, result, unary_op,
1264  iteratori_category(), iteratoro_category(),
1265  parallelism_tag);
1266  }
1267 
1268  template<typename InputIterator, typename OutputIterator,
1269  typename UnaryOperation>
1270  inline OutputIterator
1271  transform(InputIterator begin, InputIterator end, OutputIterator result,
1272  UnaryOperation unary_op)
1273  {
1274  typedef std::iterator_traits<InputIterator> iteratori_traits;
1275  typedef std::iterator_traits<OutputIterator> iteratoro_traits;
1276  typedef typename iteratori_traits::iterator_category iteratori_category;
1277  typedef typename iteratoro_traits::iterator_category iteratoro_category;
1278 
1279  return transform1_switch(begin, end, result, unary_op,
1280  iteratori_category(), iteratoro_category());
1281  }
1282 
1283 
1284  // Sequential fallback
1285  template<typename InputIterator1, typename InputIterator2,
1286  typename OutputIterator, typename BinaryOperation>
1287  inline OutputIterator
1288  transform(InputIterator1 begin1, InputIterator1 end1,
1289  InputIterator2 begin2, OutputIterator result,
1290  BinaryOperation binary_op, __gnu_parallel::sequential_tag)
1291  { return _GLIBCXX_STD_P::transform(begin1, end1,
1292  begin2, result, binary_op); }
1293 
1294  // Parallel binary transform for random access iterators.
1295  template<typename RandomAccessIterator1, typename RandomAccessIterator2,
1296  typename RandomAccessIterator3, typename BinaryOperation>
1297  RandomAccessIterator3
1298  transform2_switch(RandomAccessIterator1 begin1, RandomAccessIterator1 end1,
1299  RandomAccessIterator2 begin2,
1300  RandomAccessIterator3 result, BinaryOperation binary_op,
1301  random_access_iterator_tag, random_access_iterator_tag,
1302  random_access_iterator_tag,
1303  __gnu_parallel::_Parallelism parallelism_tag
1305  {
1307  (end1 - begin1) >=
1308  __gnu_parallel::_Settings::get().transform_minimal_n
1309  && __gnu_parallel::is_parallel(parallelism_tag)))
1310  {
1311  bool dummy = true;
1312  typedef __gnu_parallel::iterator_triple<RandomAccessIterator1,
1313  RandomAccessIterator2, RandomAccessIterator3,
1314  random_access_iterator_tag> ip;
1315  ip begin_triple(begin1, begin2, result),
1316  end_triple(end1, begin2 + (end1 - begin1),
1317  result + (end1 - begin1));
1320  for_each_template_random_access(begin_triple, end_triple,
1321  binary_op, functionality,
1323  dummy, dummy, -1,
1324  parallelism_tag);
1325  return functionality.finish_iterator;
1326  }
1327  else
1328  return transform(begin1, end1, begin2, result, binary_op,
1330  }
1331 
1332  // Sequential fallback for input iterator case.
1333  template<typename InputIterator1, typename InputIterator2,
1334  typename OutputIterator, typename BinaryOperation,
1335  typename tag1, typename tag2, typename tag3>
1336  inline OutputIterator
1337  transform2_switch(InputIterator1 begin1, InputIterator1 end1,
1338  InputIterator2 begin2, OutputIterator result,
1339  BinaryOperation binary_op, tag1, tag2, tag3)
1340  { return transform(begin1, end1, begin2, result, binary_op,
1342 
1343  // Public interface.
1344  template<typename InputIterator1, typename InputIterator2,
1345  typename OutputIterator, typename BinaryOperation>
1346  inline OutputIterator
1347  transform(InputIterator1 begin1, InputIterator1 end1,
1348  InputIterator2 begin2, OutputIterator result,
1349  BinaryOperation binary_op,
1350  __gnu_parallel::_Parallelism parallelism_tag)
1351  {
1352  typedef std::iterator_traits<InputIterator1> iteratori1_traits;
1353  typedef typename iteratori1_traits::iterator_category
1354  iteratori1_category;
1355  typedef std::iterator_traits<InputIterator2> iteratori2_traits;
1356  typedef typename iteratori2_traits::iterator_category
1357  iteratori2_category;
1358  typedef std::iterator_traits<OutputIterator> iteratoro_traits;
1359  typedef typename iteratoro_traits::iterator_category iteratoro_category;
1360 
1361  return transform2_switch(begin1, end1, begin2, result, binary_op,
1362  iteratori1_category(), iteratori2_category(),
1363  iteratoro_category(), parallelism_tag);
1364  }
1365 
1366  template<typename InputIterator1, typename InputIterator2,
1367  typename OutputIterator, typename BinaryOperation>
1368  inline OutputIterator
1369  transform(InputIterator1 begin1, InputIterator1 end1,
1370  InputIterator2 begin2, OutputIterator result,
1371  BinaryOperation binary_op)
1372  {
1373  typedef std::iterator_traits<InputIterator1> iteratori1_traits;
1374  typedef typename iteratori1_traits::iterator_category
1375  iteratori1_category;
1376  typedef std::iterator_traits<InputIterator2> iteratori2_traits;
1377  typedef typename iteratori2_traits::iterator_category
1378  iteratori2_category;
1379  typedef std::iterator_traits<OutputIterator> iteratoro_traits;
1380  typedef typename iteratoro_traits::iterator_category iteratoro_category;
1381 
1382  return transform2_switch(begin1, end1, begin2, result, binary_op,
1383  iteratori1_category(), iteratori2_category(),
1384  iteratoro_category());
1385  }
1386 
1387  // Sequential fallback
1388  template<typename ForwardIterator, typename T>
1389  inline void
1390  replace(ForwardIterator begin, ForwardIterator end, const T& old_value,
1391  const T& new_value, __gnu_parallel::sequential_tag)
1392  { _GLIBCXX_STD_P::replace(begin, end, old_value, new_value); }
1393 
1394  // Sequential fallback for input iterator case
1395  template<typename ForwardIterator, typename T, typename IteratorTag>
1396  inline void
1397  replace_switch(ForwardIterator begin, ForwardIterator end,
1398  const T& old_value, const T& new_value, IteratorTag)
1399  { replace(begin, end, old_value, new_value,
1401 
1402  // Parallel replace for random access iterators
1403  template<typename RandomAccessIterator, typename T>
1404  inline void
1405  replace_switch(RandomAccessIterator begin, RandomAccessIterator end,
1406  const T& old_value, const T& new_value,
1407  random_access_iterator_tag,
1408  __gnu_parallel::_Parallelism parallelism_tag
1410  {
1411  // XXX parallel version is where?
1412  replace(begin, end, old_value, new_value,
1414  }
1415 
1416  // Public interface
1417  template<typename ForwardIterator, typename T>
1418  inline void
1419  replace(ForwardIterator begin, ForwardIterator end, const T& old_value,
1420  const T& new_value, __gnu_parallel::_Parallelism parallelism_tag)
1421  {
1422  typedef iterator_traits<ForwardIterator> traits_type;
1423  typedef typename traits_type::iterator_category iterator_category;
1424  replace_switch(begin, end, old_value, new_value, iterator_category(),
1425  parallelism_tag);
1426  }
1427 
1428  template<typename ForwardIterator, typename T>
1429  inline void
1430  replace(ForwardIterator begin, ForwardIterator end, const T& old_value,
1431  const T& new_value)
1432  {
1433  typedef iterator_traits<ForwardIterator> traits_type;
1434  typedef typename traits_type::iterator_category iterator_category;
1435  replace_switch(begin, end, old_value, new_value, iterator_category());
1436  }
1437 
1438 
1439  // Sequential fallback
1440  template<typename ForwardIterator, typename Predicate, typename T>
1441  inline void
1442  replace_if(ForwardIterator begin, ForwardIterator end, Predicate pred,
1443  const T& new_value, __gnu_parallel::sequential_tag)
1444  { _GLIBCXX_STD_P::replace_if(begin, end, pred, new_value); }
1445 
1446  // Sequential fallback for input iterator case
1447  template<typename ForwardIterator, typename Predicate, typename T,
1448  typename IteratorTag>
1449  inline void
1450  replace_if_switch(ForwardIterator begin, ForwardIterator end,
1451  Predicate pred, const T& new_value, IteratorTag)
1452  { replace_if(begin, end, pred, new_value,
1454 
1455  // Parallel algorithm for random access iterators.
1456  template<typename RandomAccessIterator, typename Predicate, typename T>
1457  void
1458  replace_if_switch(RandomAccessIterator begin, RandomAccessIterator end,
1459  Predicate pred, const T& new_value,
1460  random_access_iterator_tag,
1461  __gnu_parallel::_Parallelism parallelism_tag
1463  {
1465  static_cast<__gnu_parallel::sequence_index_t>(end - begin)
1466  >= __gnu_parallel::_Settings::get().replace_minimal_n
1467  && __gnu_parallel::is_parallel(parallelism_tag)))
1468  {
1469  bool dummy;
1472  functionality(new_value);
1474  for_each_template_random_access(begin, end, pred,
1475  functionality,
1477  true, dummy, -1, parallelism_tag);
1478  }
1479  else
1480  replace_if(begin, end, pred, new_value,
1482  }
1483 
1484  // Public interface.
1485  template<typename ForwardIterator, typename Predicate, typename T>
1486  inline void
1487  replace_if(ForwardIterator begin, ForwardIterator end,
1488  Predicate pred, const T& new_value,
1489  __gnu_parallel::_Parallelism parallelism_tag)
1490  {
1491  typedef std::iterator_traits<ForwardIterator> iterator_traits;
1492  typedef typename iterator_traits::iterator_category iterator_category;
1493  replace_if_switch(begin, end, pred, new_value, iterator_category(),
1494  parallelism_tag);
1495  }
1496 
1497  template<typename ForwardIterator, typename Predicate, typename T>
1498  inline void
1499  replace_if(ForwardIterator begin, ForwardIterator end,
1500  Predicate pred, const T& new_value)
1501  {
1502  typedef std::iterator_traits<ForwardIterator> iterator_traits;
1503  typedef typename iterator_traits::iterator_category iterator_category;
1504  replace_if_switch(begin, end, pred, new_value, iterator_category());
1505  }
1506 
1507  // Sequential fallback
1508  template<typename ForwardIterator, typename Generator>
1509  inline void
1510  generate(ForwardIterator begin, ForwardIterator end, Generator gen,
1512  { _GLIBCXX_STD_P::generate(begin, end, gen); }
1513 
1514  // Sequential fallback for input iterator case.
1515  template<typename ForwardIterator, typename Generator, typename IteratorTag>
1516  inline void
1517  generate_switch(ForwardIterator begin, ForwardIterator end, Generator gen,
1518  IteratorTag)
1519  { generate(begin, end, gen, __gnu_parallel::sequential_tag()); }
1520 
1521  // Parallel algorithm for random access iterators.
1522  template<typename RandomAccessIterator, typename Generator>
1523  void
1524  generate_switch(RandomAccessIterator begin, RandomAccessIterator end,
1525  Generator gen, random_access_iterator_tag,
1526  __gnu_parallel::_Parallelism parallelism_tag
1528  {
1530  static_cast<__gnu_parallel::sequence_index_t>(end - begin)
1531  >= __gnu_parallel::_Settings::get().generate_minimal_n
1532  && __gnu_parallel::is_parallel(parallelism_tag)))
1533  {
1534  bool dummy;
1536  functionality;
1538  for_each_template_random_access(begin, end, gen, functionality,
1540  true, dummy, -1, parallelism_tag);
1541  }
1542  else
1543  generate(begin, end, gen, __gnu_parallel::sequential_tag());
1544  }
1545 
1546  // Public interface.
1547  template<typename ForwardIterator, typename Generator>
1548  inline void
1549  generate(ForwardIterator begin, ForwardIterator end,
1550  Generator gen, __gnu_parallel::_Parallelism parallelism_tag)
1551  {
1552  typedef std::iterator_traits<ForwardIterator> iterator_traits;
1553  typedef typename iterator_traits::iterator_category iterator_category;
1554  generate_switch(begin, end, gen, iterator_category(), parallelism_tag);
1555  }
1556 
1557  template<typename ForwardIterator, typename Generator>
1558  inline void
1559  generate(ForwardIterator begin, ForwardIterator end, Generator gen)
1560  {
1561  typedef std::iterator_traits<ForwardIterator> iterator_traits;
1562  typedef typename iterator_traits::iterator_category iterator_category;
1563  generate_switch(begin, end, gen, iterator_category());
1564  }
1565 
1566 
1567  // Sequential fallback.
1568  template<typename OutputIterator, typename Size, typename Generator>
1569  inline OutputIterator
1570  generate_n(OutputIterator begin, Size n, Generator gen,
1572  { return _GLIBCXX_STD_P::generate_n(begin, n, gen); }
1573 
1574  // Sequential fallback for input iterator case.
1575  template<typename OutputIterator, typename Size, typename Generator,
1576  typename IteratorTag>
1577  inline OutputIterator
1578  generate_n_switch(OutputIterator begin, Size n, Generator gen, IteratorTag)
1579  { return generate_n(begin, n, gen, __gnu_parallel::sequential_tag()); }
1580 
1581  // Parallel algorithm for random access iterators.
1582  template<typename RandomAccessIterator, typename Size, typename Generator>
1583  inline RandomAccessIterator
1584  generate_n_switch(RandomAccessIterator begin, Size n, Generator gen,
1585  random_access_iterator_tag,
1586  __gnu_parallel::_Parallelism parallelism_tag
1588  {
1589  // XXX parallel version is where?
1590  return generate_n(begin, n, gen, __gnu_parallel::sequential_tag());
1591  }
1592 
1593  // Public interface.
1594  template<typename OutputIterator, typename Size, typename Generator>
1595  inline OutputIterator
1596  generate_n(OutputIterator begin, Size n, Generator gen,
1597  __gnu_parallel::_Parallelism parallelism_tag)
1598  {
1599  typedef std::iterator_traits<OutputIterator> iterator_traits;
1600  typedef typename iterator_traits::iterator_category iterator_category;
1601  return generate_n_switch(begin, n, gen, iterator_category(),
1602  parallelism_tag);
1603  }
1604 
1605  template<typename OutputIterator, typename Size, typename Generator>
1606  inline OutputIterator
1607  generate_n(OutputIterator begin, Size n, Generator gen)
1608  {
1609  typedef std::iterator_traits<OutputIterator> iterator_traits;
1610  typedef typename iterator_traits::iterator_category iterator_category;
1611  return generate_n_switch(begin, n, gen, iterator_category());
1612  }
1613 
1614 
1615  // Sequential fallback.
1616  template<typename RandomAccessIterator>
1617  inline void
1618  random_shuffle(RandomAccessIterator begin, RandomAccessIterator end,
1620  { _GLIBCXX_STD_P::random_shuffle(begin, end); }
1621 
1622  // Sequential fallback.
1623  template<typename RandomAccessIterator, typename RandomNumberGenerator>
1624  inline void
1625  random_shuffle(RandomAccessIterator begin, RandomAccessIterator end,
1626  RandomNumberGenerator& rand, __gnu_parallel::sequential_tag)
1627  { _GLIBCXX_STD_P::random_shuffle(begin, end, rand); }
1628 
1629 
1630  /** @brief Functor wrapper for std::rand(). */
1631  template<typename must_be_int = int>
1633  {
1634  int
1635  operator()(int limit)
1636  { return rand() % limit; }
1637  };
1638 
1639  // Fill in random number generator.
1640  template<typename RandomAccessIterator>
1641  inline void
1642  random_shuffle(RandomAccessIterator begin, RandomAccessIterator end)
1643  {
1644  c_rand_number<> r;
1645  // Parallelization still possible.
1646  __gnu_parallel::random_shuffle(begin, end, r);
1647  }
1648 
1649  // Parallel algorithm for random access iterators.
1650  template<typename RandomAccessIterator, typename RandomNumberGenerator>
1651  void
1652  random_shuffle(RandomAccessIterator begin, RandomAccessIterator end,
1653  RandomNumberGenerator& rand)
1654  {
1655  if (begin == end)
1656  return;
1658  static_cast<__gnu_parallel::sequence_index_t>(end - begin)
1659  >= __gnu_parallel::_Settings::get().random_shuffle_minimal_n))
1660  __gnu_parallel::parallel_random_shuffle(begin, end, rand);
1661  else
1663  }
1664 
1665  // Sequential fallback.
1666  template<typename ForwardIterator, typename Predicate>
1667  inline ForwardIterator
1668  partition(ForwardIterator begin, ForwardIterator end,
1669  Predicate pred, __gnu_parallel::sequential_tag)
1670  { return _GLIBCXX_STD_P::partition(begin, end, pred); }
1671 
1672  // Sequential fallback for input iterator case.
1673  template<typename ForwardIterator, typename Predicate, typename IteratorTag>
1674  inline ForwardIterator
1675  partition_switch(ForwardIterator begin, ForwardIterator end,
1676  Predicate pred, IteratorTag)
1677  { return partition(begin, end, pred, __gnu_parallel::sequential_tag()); }
1678 
1679  // Parallel algorithm for random access iterators.
1680  template<typename RandomAccessIterator, typename Predicate>
1681  RandomAccessIterator
1682  partition_switch(RandomAccessIterator begin, RandomAccessIterator end,
1683  Predicate pred, random_access_iterator_tag)
1684  {
1686  static_cast<__gnu_parallel::sequence_index_t>(end - begin)
1687  >= __gnu_parallel::_Settings::get().partition_minimal_n))
1688  {
1690  difference_type difference_type;
1691  difference_type middle = __gnu_parallel::
1692  parallel_partition(begin, end, pred,
1693  __gnu_parallel::get_max_threads());
1694  return begin + middle;
1695  }
1696  else
1697  return partition(begin, end, pred, __gnu_parallel::sequential_tag());
1698  }
1699 
1700  // Public interface.
1701  template<typename ForwardIterator, typename Predicate>
1702  inline ForwardIterator
1703  partition(ForwardIterator begin, ForwardIterator end, Predicate pred)
1704  {
1705  typedef iterator_traits<ForwardIterator> traits_type;
1706  typedef typename traits_type::iterator_category iterator_category;
1707  return partition_switch(begin, end, pred, iterator_category());
1708  }
1709 
1710  // sort interface
1711 
1712  // Sequential fallback
1713  template<typename RandomAccessIterator>
1714  inline void
1715  sort(RandomAccessIterator begin, RandomAccessIterator end,
1717  { _GLIBCXX_STD_P::sort(begin, end); }
1718 
1719  // Sequential fallback
1720  template<typename RandomAccessIterator, typename Comparator>
1721  inline void
1722  sort(RandomAccessIterator begin, RandomAccessIterator end, Comparator comp,
1724  { _GLIBCXX_STD_P::sort<RandomAccessIterator, Comparator>(begin, end,
1725  comp); }
1726 
1727  // Public interface
1728  template<typename RandomAccessIterator, typename Comparator,
1729  typename Parallelism>
1730  void
1731  sort(RandomAccessIterator begin, RandomAccessIterator end, Comparator comp,
1732  Parallelism parallelism)
1733  {
1734  typedef iterator_traits<RandomAccessIterator> traits_type;
1735  typedef typename traits_type::value_type value_type;
1736 
1737  if (begin != end)
1738  {
1740  static_cast<__gnu_parallel::sequence_index_t>(end - begin) >=
1741  __gnu_parallel::_Settings::get().sort_minimal_n))
1742  __gnu_parallel::parallel_sort<false>(begin, end, comp, parallelism);
1743  else
1744  sort(begin, end, comp, __gnu_parallel::sequential_tag());
1745  }
1746  }
1747 
1748  // Public interface, insert default comparator
1749  template<typename RandomAccessIterator>
1750  inline void
1751  sort(RandomAccessIterator begin, RandomAccessIterator end)
1752  {
1753  typedef iterator_traits<RandomAccessIterator> traits_type;
1754  typedef typename traits_type::value_type value_type;
1755  sort(begin, end, std::less<value_type>(),
1757  }
1758 
1759  // Public interface, insert default comparator
1760  template<typename RandomAccessIterator>
1761  inline void
1762  sort(RandomAccessIterator begin, RandomAccessIterator end,
1764  {
1765  typedef iterator_traits<RandomAccessIterator> traits_type;
1766  typedef typename traits_type::value_type value_type;
1767  sort(begin, end, std::less<value_type>(), parallelism);
1768  }
1769 
1770  // Public interface, insert default comparator
1771  template<typename RandomAccessIterator>
1772  inline void
1773  sort(RandomAccessIterator begin, RandomAccessIterator end,
1774  __gnu_parallel::parallel_tag parallelism)
1775  {
1776  typedef iterator_traits<RandomAccessIterator> traits_type;
1777  typedef typename traits_type::value_type value_type;
1778  sort(begin, end, std::less<value_type>(), parallelism);
1779  }
1780 
1781  // Public interface, insert default comparator
1782  template<typename RandomAccessIterator>
1783  inline void
1784  sort(RandomAccessIterator begin, RandomAccessIterator end,
1786  {
1787  typedef iterator_traits<RandomAccessIterator> traits_type;
1788  typedef typename traits_type::value_type value_type;
1789  sort(begin, end, std::less<value_type>(), parallelism);
1790  }
1791 
1792  // Public interface, insert default comparator
1793  template<typename RandomAccessIterator>
1794  inline void
1795  sort(RandomAccessIterator begin, RandomAccessIterator end,
1797  {
1798  typedef iterator_traits<RandomAccessIterator> traits_type;
1799  typedef typename traits_type::value_type value_type;
1800  sort(begin, end, std::less<value_type>(), parallelism);
1801  }
1802 
1803  // Public interface, insert default comparator
1804  template<typename RandomAccessIterator>
1805  inline void
1806  sort(RandomAccessIterator begin, RandomAccessIterator end,
1808  {
1809  typedef iterator_traits<RandomAccessIterator> traits_type;
1810  typedef typename traits_type::value_type value_type;
1811  sort(begin, end, std::less<value_type>(), parallelism);
1812  }
1813 
1814  // Public interface, insert default comparator
1815  template<typename RandomAccessIterator>
1816  inline void
1817  sort(RandomAccessIterator begin, RandomAccessIterator end,
1818  __gnu_parallel::quicksort_tag parallelism)
1819  {
1820  typedef iterator_traits<RandomAccessIterator> traits_type;
1821  typedef typename traits_type::value_type value_type;
1822  sort(begin, end, std::less<value_type>(), parallelism);
1823  }
1824 
1825  // Public interface, insert default comparator
1826  template<typename RandomAccessIterator>
1827  inline void
1828  sort(RandomAccessIterator begin, RandomAccessIterator end,
1830  {
1831  typedef iterator_traits<RandomAccessIterator> traits_type;
1832  typedef typename traits_type::value_type value_type;
1833  sort(begin, end, std::less<value_type>(), parallelism);
1834  }
1835 
1836  // Public interface
1837  template<typename RandomAccessIterator, typename Comparator>
1838  void
1839  sort(RandomAccessIterator begin, RandomAccessIterator end, Comparator comp)
1840  {
1841  typedef iterator_traits<RandomAccessIterator> traits_type;
1842  typedef typename traits_type::value_type value_type;
1843  sort(begin, end, comp, __gnu_parallel::default_parallel_tag());
1844  }
1845 
1846 
1847  // stable_sort interface
1848 
1849 
1850  // Sequential fallback
1851  template<typename RandomAccessIterator>
1852  inline void
1853  stable_sort(RandomAccessIterator begin, RandomAccessIterator end,
1855  { _GLIBCXX_STD_P::stable_sort(begin, end); }
1856 
1857  // Sequential fallback
1858  template<typename RandomAccessIterator, typename Comparator>
1859  inline void
1860  stable_sort(RandomAccessIterator begin, RandomAccessIterator end,
1861  Comparator comp, __gnu_parallel::sequential_tag)
1862  { _GLIBCXX_STD_P::stable_sort<RandomAccessIterator, Comparator>(
1863  begin, end, comp); }
1864 
1865  // Public interface
1866  template<typename RandomAccessIterator, typename Comparator,
1867  typename Parallelism>
1868  void
1869  stable_sort(RandomAccessIterator begin, RandomAccessIterator end,
1870  Comparator comp, Parallelism parallelism)
1871  {
1872  typedef iterator_traits<RandomAccessIterator> traits_type;
1873  typedef typename traits_type::value_type value_type;
1874 
1875  if (begin != end)
1876  {
1878  static_cast<__gnu_parallel::sequence_index_t>(end - begin) >=
1879  __gnu_parallel::_Settings::get().sort_minimal_n))
1880  __gnu_parallel::parallel_sort<true>(begin, end, comp, parallelism);
1881  else
1882  stable_sort(begin, end, comp, __gnu_parallel::sequential_tag());
1883  }
1884  }
1885 
1886  // Public interface, insert default comparator
1887  template<typename RandomAccessIterator>
1888  inline void
1889  stable_sort(RandomAccessIterator begin, RandomAccessIterator end)
1890  {
1891  typedef iterator_traits<RandomAccessIterator> traits_type;
1892  typedef typename traits_type::value_type value_type;
1893  stable_sort(begin, end, std::less<value_type>(),
1895  }
1896 
1897  // Public interface, insert default comparator
1898  template<typename RandomAccessIterator>
1899  inline void
1900  stable_sort(RandomAccessIterator begin, RandomAccessIterator end,
1902  {
1903  typedef iterator_traits<RandomAccessIterator> traits_type;
1904  typedef typename traits_type::value_type value_type;
1905  stable_sort(begin, end, std::less<value_type>(), parallelism);
1906  }
1907 
1908  // Public interface, insert default comparator
1909  template<typename RandomAccessIterator>
1910  inline void
1911  stable_sort(RandomAccessIterator begin, RandomAccessIterator end,
1912  __gnu_parallel::parallel_tag parallelism)
1913  {
1914  typedef iterator_traits<RandomAccessIterator> traits_type;
1915  typedef typename traits_type::value_type value_type;
1916  stable_sort(begin, end, std::less<value_type>(), parallelism);
1917  }
1918 
1919  // Public interface, insert default comparator
1920  template<typename RandomAccessIterator>
1921  inline void
1922  stable_sort(RandomAccessIterator begin, RandomAccessIterator end,
1924  {
1925  typedef iterator_traits<RandomAccessIterator> traits_type;
1926  typedef typename traits_type::value_type value_type;
1927  stable_sort(begin, end, std::less<value_type>(), parallelism);
1928  }
1929 
1930  // Public interface, insert default comparator
1931  template<typename RandomAccessIterator>
1932  inline void
1933  stable_sort(RandomAccessIterator begin, RandomAccessIterator end,
1934  __gnu_parallel::quicksort_tag parallelism)
1935  {
1936  typedef iterator_traits<RandomAccessIterator> traits_type;
1937  typedef typename traits_type::value_type value_type;
1938  stable_sort(begin, end, std::less<value_type>(), parallelism);
1939  }
1940 
1941  // Public interface, insert default comparator
1942  template<typename RandomAccessIterator>
1943  inline void
1944  stable_sort(RandomAccessIterator begin, RandomAccessIterator end,
1946  {
1947  typedef iterator_traits<RandomAccessIterator> traits_type;
1948  typedef typename traits_type::value_type value_type;
1949  stable_sort(begin, end, std::less<value_type>(), parallelism);
1950  }
1951 
1952  // Public interface
1953  template<typename RandomAccessIterator, typename Comparator>
1954  void
1955  stable_sort(RandomAccessIterator begin, RandomAccessIterator end,
1956  Comparator comp)
1957  {
1958  typedef iterator_traits<RandomAccessIterator> traits_type;
1959  typedef typename traits_type::value_type value_type;
1960  stable_sort(begin, end, comp, __gnu_parallel::default_parallel_tag());
1961  }
1962 
1963 
1964 // // Sequential fallback
1965 // template<typename RandomAccessIterator>
1966 // inline void
1967 // stable_sort(RandomAccessIterator begin, RandomAccessIterator end,
1968 // __gnu_parallel::sequential_tag)
1969 // { return _GLIBCXX_STD_P::stable_sort(begin, end); }
1970 //
1971 // // Sequential fallback
1972 // template<typename RandomAccessIterator, typename Comparator>
1973 // inline void
1974 // stable_sort(RandomAccessIterator begin, RandomAccessIterator end,
1975 // Comparator comp, __gnu_parallel::sequential_tag)
1976 // { return _GLIBCXX_STD_P::stable_sort(begin, end, comp); }
1977 //
1978 // template<typename RandomAccessIterator>
1979 // void
1980 // stable_sort(RandomAccessIterator begin, RandomAccessIterator end)
1981 // {
1982 // typedef iterator_traits<RandomAccessIterator> traits_type;
1983 // typedef typename traits_type::value_type value_type;
1984 // stable_sort(begin, end, std::less<value_type>());
1985 // }
1986 //
1987 // // Parallel algorithm for random access iterators
1988 // template<typename RandomAccessIterator, typename Comparator>
1989 // void
1990 // stable_sort(RandomAccessIterator begin, RandomAccessIterator end,
1991 // Comparator comp)
1992 // {
1993 // if (begin != end)
1994 // {
1995 // if (_GLIBCXX_PARALLEL_CONDITION(
1996 // static_cast<__gnu_parallel::sequence_index_t>(end - begin) >=
1997 // __gnu_parallel::_Settings::get().sort_minimal_n))
1998 // __gnu_parallel::parallel_sort(begin, end, comp,
1999 // __gnu_parallel::parallel_tag());
2000 // else
2001 // stable_sort(begin, end, comp, __gnu_parallel::sequential_tag());
2002 // }
2003 // }
2004 
2005  // Sequential fallback
2006  template<typename InputIterator1, typename InputIterator2,
2007  typename OutputIterator>
2008  inline OutputIterator
2009  merge(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
2010  InputIterator2 end2, OutputIterator result,
2012  { return _GLIBCXX_STD_P::merge(begin1, end1, begin2, end2, result); }
2013 
2014  // Sequential fallback
2015  template<typename InputIterator1, typename InputIterator2,
2016  typename OutputIterator, typename Comparator>
2017  inline OutputIterator
2018  merge(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
2019  InputIterator2 end2, OutputIterator result, Comparator comp,
2021  { return _GLIBCXX_STD_P::merge(begin1, end1, begin2, end2, result, comp); }
2022 
2023  // Sequential fallback for input iterator case
2024  template<typename InputIterator1, typename InputIterator2,
2025  typename OutputIterator, typename Comparator,
2026  typename IteratorTag1, typename IteratorTag2, typename IteratorTag3>
2027  inline OutputIterator
2028  merge_switch(InputIterator1 begin1, InputIterator1 end1,
2029  InputIterator2 begin2, InputIterator2 end2,
2030  OutputIterator result, Comparator comp,
2031  IteratorTag1, IteratorTag2, IteratorTag3)
2032  { return _GLIBCXX_STD_P::merge(begin1, end1, begin2, end2,
2033  result, comp); }
2034 
2035  // Parallel algorithm for random access iterators
2036  template<typename InputIterator1, typename InputIterator2,
2037  typename OutputIterator, typename Comparator>
2038  OutputIterator
2039  merge_switch(InputIterator1 begin1, InputIterator1 end1,
2040  InputIterator2 begin2, InputIterator2 end2,
2041  OutputIterator result, Comparator comp,
2042  random_access_iterator_tag, random_access_iterator_tag,
2043  random_access_iterator_tag)
2044  {
2046  (static_cast<__gnu_parallel::sequence_index_t>(end1 - begin1)
2047  >= __gnu_parallel::_Settings::get().merge_minimal_n
2048  || static_cast<__gnu_parallel::sequence_index_t>(end2 - begin2)
2049  >= __gnu_parallel::_Settings::get().merge_minimal_n)))
2050  return __gnu_parallel::parallel_merge_advance(begin1, end1,
2051  begin2, end2,
2052  result, (end1 - begin1)
2053  + (end2 - begin2), comp);
2054  else
2055  return __gnu_parallel::merge_advance(begin1, end1, begin2, end2,
2056  result, (end1 - begin1)
2057  + (end2 - begin2), comp);
2058  }
2059 
2060  // Public interface
2061  template<typename InputIterator1, typename InputIterator2,
2062  typename OutputIterator, typename Comparator>
2063  inline OutputIterator
2064  merge(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
2065  InputIterator2 end2, OutputIterator result, Comparator comp)
2066  {
2067  typedef typename iterator_traits<InputIterator1>::value_type value_type;
2068 
2069  typedef std::iterator_traits<InputIterator1> iteratori1_traits;
2070  typedef std::iterator_traits<InputIterator2> iteratori2_traits;
2071  typedef std::iterator_traits<OutputIterator> iteratoro_traits;
2072  typedef typename iteratori1_traits::iterator_category
2073  iteratori1_category;
2074  typedef typename iteratori2_traits::iterator_category
2075  iteratori2_category;
2076  typedef typename iteratoro_traits::iterator_category iteratoro_category;
2077 
2078  return merge_switch(begin1, end1, begin2, end2, result, comp,
2079  iteratori1_category(), iteratori2_category(),
2080  iteratoro_category());
2081  }
2082 
2083 
2084  // Public interface, insert default comparator
2085  template<typename InputIterator1, typename InputIterator2,
2086  typename OutputIterator>
2087  inline OutputIterator
2088  merge(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2,
2089  InputIterator2 end2, OutputIterator result)
2090  {
2091  typedef std::iterator_traits<InputIterator1> iterator1_traits;
2092  typedef std::iterator_traits<InputIterator2> iterator2_traits;
2093  typedef typename iterator1_traits::value_type value1_type;
2094  typedef typename iterator2_traits::value_type value2_type;
2095 
2096  return _GLIBCXX_STD_P::merge(begin1, end1, begin2, end2, result,
2098  }
2099 
2100  // Sequential fallback
2101  template<typename RandomAccessIterator>
2102  inline void
2103  nth_element(RandomAccessIterator begin, RandomAccessIterator nth,
2104  RandomAccessIterator end, __gnu_parallel::sequential_tag)
2105  { return _GLIBCXX_STD_P::nth_element(begin, nth, end); }
2106 
2107  // Sequential fallback
2108  template<typename RandomAccessIterator, typename Comparator>
2109  inline void
2110  nth_element(RandomAccessIterator begin, RandomAccessIterator nth,
2111  RandomAccessIterator end, Comparator comp,
2113  { return _GLIBCXX_STD_P::nth_element(begin, nth, end, comp); }
2114 
2115  // Public interface
2116  template<typename RandomAccessIterator, typename Comparator>
2117  inline void
2118  nth_element(RandomAccessIterator begin, RandomAccessIterator nth,
2119  RandomAccessIterator end, Comparator comp)
2120  {
2122  static_cast<__gnu_parallel::sequence_index_t>(end - begin)
2123  >= __gnu_parallel::_Settings::get().nth_element_minimal_n))
2124  __gnu_parallel::parallel_nth_element(begin, nth, end, comp);
2125  else
2126  nth_element(begin, nth, end, comp, __gnu_parallel::sequential_tag());
2127  }
2128 
2129  // Public interface, insert default comparator
2130  template<typename RandomAccessIterator>
2131  inline void
2132  nth_element(RandomAccessIterator begin, RandomAccessIterator nth,
2133  RandomAccessIterator end)
2134  {
2135  typedef iterator_traits<RandomAccessIterator> traits_type;
2136  typedef typename traits_type::value_type value_type;
2137  _GLIBCXX_STD_P::nth_element(begin, nth, end, std::less<value_type>());
2138  }
2139 
2140  // Sequential fallback
2141  template<typename RandomAccessIterator, typename _Compare>
2142  inline void
2143  partial_sort(RandomAccessIterator begin, RandomAccessIterator middle,
2144  RandomAccessIterator end, _Compare comp,
2146  { _GLIBCXX_STD_P::partial_sort(begin, middle, end, comp); }
2147 
2148  // Sequential fallback
2149  template<typename RandomAccessIterator>
2150  inline void
2151  partial_sort(RandomAccessIterator begin, RandomAccessIterator middle,
2152  RandomAccessIterator end, __gnu_parallel::sequential_tag)
2153  { _GLIBCXX_STD_P::partial_sort(begin, middle, end); }
2154 
2155  // Public interface, parallel algorithm for random access iterators
2156  template<typename RandomAccessIterator, typename _Compare>
2157  void
2158  partial_sort(RandomAccessIterator begin, RandomAccessIterator middle,
2159  RandomAccessIterator end, _Compare comp)
2160  {
2162  static_cast<__gnu_parallel::sequence_index_t>(end - begin)
2163  >= __gnu_parallel::_Settings::get().partial_sort_minimal_n))
2164  __gnu_parallel::parallel_partial_sort(begin, middle, end, comp);
2165  else
2166  partial_sort(begin, middle, end, comp,
2168  }
2169 
2170  // Public interface, insert default comparator
2171  template<typename RandomAccessIterator>
2172  inline void
2173  partial_sort(RandomAccessIterator begin, RandomAccessIterator middle,
2174  RandomAccessIterator end)
2175  {
2176  typedef iterator_traits<RandomAccessIterator> traits_type;
2177  typedef typename traits_type::value_type value_type;
2178  _GLIBCXX_STD_P::partial_sort(begin, middle, end,
2180  }
2181 
2182  // Sequential fallback
2183  template<typename ForwardIterator>
2184  inline ForwardIterator
2185  max_element(ForwardIterator begin, ForwardIterator end,
2187  { return _GLIBCXX_STD_P::max_element(begin, end); }
2188 
2189  // Sequential fallback
2190  template<typename ForwardIterator, typename Comparator>
2191  inline ForwardIterator
2192  max_element(ForwardIterator begin, ForwardIterator end, Comparator comp,
2194  { return _GLIBCXX_STD_P::max_element(begin, end, comp); }
2195 
2196  // Sequential fallback for input iterator case
2197  template<typename ForwardIterator, typename Comparator, typename IteratorTag>
2198  inline ForwardIterator
2199  max_element_switch(ForwardIterator begin, ForwardIterator end,
2200  Comparator comp, IteratorTag)
2201  { return max_element(begin, end, comp, __gnu_parallel::sequential_tag()); }
2202 
2203  // Parallel algorithm for random access iterators
2204  template<typename RandomAccessIterator, typename Comparator>
2205  RandomAccessIterator
2206  max_element_switch(RandomAccessIterator begin, RandomAccessIterator end,
2207  Comparator comp, random_access_iterator_tag,
2208  __gnu_parallel::_Parallelism parallelism_tag
2210  {
2212  static_cast<__gnu_parallel::sequence_index_t>(end - begin)
2213  >= __gnu_parallel::_Settings::get().max_element_minimal_n
2214  && __gnu_parallel::is_parallel(parallelism_tag)))
2215  {
2216  RandomAccessIterator res(begin);
2218  functionality;
2222  functionality,
2223  __gnu_parallel::
2224  max_element_reduct<Comparator,
2225  RandomAccessIterator>(comp),
2226  res, res, -1, parallelism_tag);
2227  return res;
2228  }
2229  else
2230  return max_element(begin, end, comp, __gnu_parallel::sequential_tag());
2231  }
2232 
2233  // Public interface, insert default comparator
2234  template<typename ForwardIterator>
2235  inline ForwardIterator
2236  max_element(ForwardIterator begin, ForwardIterator end,
2237  __gnu_parallel::_Parallelism parallelism_tag)
2238  {
2239  typedef typename iterator_traits<ForwardIterator>::value_type value_type;
2240  return max_element(begin, end, std::less<value_type>(), parallelism_tag);
2241  }
2242 
2243  template<typename ForwardIterator>
2244  inline ForwardIterator
2245  max_element(ForwardIterator begin, ForwardIterator end)
2246  {
2247  typedef typename iterator_traits<ForwardIterator>::value_type value_type;
2248  return _GLIBCXX_STD_P::max_element(begin, end, std::less<value_type>());
2249  }
2250 
2251  // Public interface
2252  template<typename ForwardIterator, typename Comparator>
2253  inline ForwardIterator
2254  max_element(ForwardIterator begin, ForwardIterator end, Comparator comp,
2255  __gnu_parallel::_Parallelism parallelism_tag)
2256  {
2257  typedef iterator_traits<ForwardIterator> traits_type;
2258  typedef typename traits_type::iterator_category iterator_category;
2259  return max_element_switch(begin, end, comp, iterator_category(),
2260  parallelism_tag);
2261  }
2262 
2263  template<typename ForwardIterator, typename Comparator>
2264  inline ForwardIterator
2265  max_element(ForwardIterator begin, ForwardIterator end, Comparator comp)
2266  {
2267  typedef iterator_traits<ForwardIterator> traits_type;
2268  typedef typename traits_type::iterator_category iterator_category;
2269  return max_element_switch(begin, end, comp, iterator_category());
2270  }
2271 
2272 
2273  // Sequential fallback
2274  template<typename ForwardIterator>
2275  inline ForwardIterator
2276  min_element(ForwardIterator begin, ForwardIterator end,
2278  { return _GLIBCXX_STD_P::min_element(begin, end); }
2279 
2280  // Sequential fallback
2281  template<typename ForwardIterator, typename Comparator>
2282  inline ForwardIterator
2283  min_element(ForwardIterator begin, ForwardIterator end, Comparator comp,
2285  { return _GLIBCXX_STD_P::min_element(begin, end, comp); }
2286 
2287  // Sequential fallback for input iterator case
2288  template<typename ForwardIterator, typename Comparator, typename IteratorTag>
2289  inline ForwardIterator
2290  min_element_switch(ForwardIterator begin, ForwardIterator end,
2291  Comparator comp, IteratorTag)
2292  { return min_element(begin, end, comp, __gnu_parallel::sequential_tag()); }
2293 
2294  // Parallel algorithm for random access iterators
2295  template<typename RandomAccessIterator, typename Comparator>
2296  RandomAccessIterator
2297  min_element_switch(RandomAccessIterator begin, RandomAccessIterator end,
2298  Comparator comp, random_access_iterator_tag,
2299  __gnu_parallel::_Parallelism parallelism_tag
2301  {
2303  static_cast<__gnu_parallel::sequence_index_t>(end - begin)
2304  >= __gnu_parallel::_Settings::get().min_element_minimal_n
2305  && __gnu_parallel::is_parallel(parallelism_tag)))
2306  {
2307  RandomAccessIterator res(begin);
2309  functionality;
2313  functionality,
2314  __gnu_parallel::
2315  min_element_reduct<Comparator,
2316  RandomAccessIterator>(comp),
2317  res, res, -1, parallelism_tag);
2318  return res;
2319  }
2320  else
2321  return min_element(begin, end, comp, __gnu_parallel::sequential_tag());
2322  }
2323 
2324  // Public interface, insert default comparator
2325  template<typename ForwardIterator>
2326  inline ForwardIterator
2327  min_element(ForwardIterator begin, ForwardIterator end,
2328  __gnu_parallel::_Parallelism parallelism_tag)
2329  {
2330  typedef typename iterator_traits<ForwardIterator>::value_type value_type;
2331  return min_element(begin, end, std::less<value_type>(), parallelism_tag);
2332  }
2333 
2334  template<typename ForwardIterator>
2335  inline ForwardIterator
2336  min_element(ForwardIterator begin, ForwardIterator end)
2337  {
2338  typedef typename iterator_traits<ForwardIterator>::value_type value_type;
2339  return _GLIBCXX_STD_P::min_element(begin, end, std::less<value_type>());
2340  }
2341 
2342  // Public interface
2343  template<typename ForwardIterator, typename Comparator>
2344  inline ForwardIterator
2345  min_element(ForwardIterator begin, ForwardIterator end, Comparator comp,
2346  __gnu_parallel::_Parallelism parallelism_tag)
2347  {
2348  typedef iterator_traits<ForwardIterator> traits_type;
2349  typedef typename traits_type::iterator_category iterator_category;
2350  return min_element_switch(begin, end, comp, iterator_category(),
2351  parallelism_tag);
2352  }
2353 
2354  template<typename ForwardIterator, typename Comparator>
2355  inline ForwardIterator
2356  min_element(ForwardIterator begin, ForwardIterator end, Comparator comp)
2357  {
2358  typedef iterator_traits<ForwardIterator> traits_type;
2359  typedef typename traits_type::iterator_category iterator_category;
2360  return min_element_switch(begin, end, comp, iterator_category());
2361  }
2362 } // end namespace
2363 } // end namespace
2364 
2365 #endif /* _GLIBCXX_PARALLEL_ALGO_H */
static const _Settings & get()
Get the global settings.
A triple of iterators. The usual iterator operations are applied to all three child iterators...
Definition: iterator.h:119
Parallel implementation of std::partition(), std::nth_element(), and std::partial_sort(). This file is a GNU parallel extension to the Standard C++ Library.
Parallel implementation of std::random_shuffle(). This file is a GNU parallel extension to the Standa...
#define _GLIBCXX_PARALLEL_CONDITION(c)
Determine at compile(?)-time if the parallel variant of an algorithm should be called.
Definition: settings.h:95
Forces parallel sorting using multiway mergesort at compile time.
Definition: tags.h:134
OutputIterator merge_advance(RandomAccessIterator1 &begin1, RandomAccessIterator1 end1, RandomAccessIterator2 &begin2, RandomAccessIterator2 end2, OutputIterator target, _DifferenceTp max_length, Comparator comp)
Merge routine being able to merge only the max_length smallest elements.
Definition: merge.h:174
Parallelization of embarrassingly parallel execution by means of an OpenMP for loop. This file is a GNU parallel extension to the Standard C++ Library.
std::for_each() selector.
std::iterator_traits< RandomAccessIterator >::difference_type parallel_partition(RandomAccessIterator begin, RandomAccessIterator end, Predicate pred, thread_index_t num_threads)
Parallel implementation of std::partition.
Definition: partition.h:55
Parallel unbalanced (equal-sized chunks).
Definition: types.h:48
Sequence that conceptually consists of multiple copies of the same element. The copies are not stored...
Definition: base.h:330
_Parallelism
Run-time equivalents for the compile-time tags.
Definition: types.h:42
It finish_iterator
Iterator on last element processed; needed for some algorithms (e. g. std::transform()).
Helper iterator classes for the std::transform() functions. This file is a GNU parallel extension to ...
Forces parallel sorting using balanced quicksort at compile time.
Definition: tags.h:170
Functor doing nothing.
Parallel implementation base for std::search() and std::search_n(). This file is a GNU parallel exten...
Forces parallel sorting using multiway mergesort with splitting by sampling at compile time...
Definition: tags.h:152
std::count_if () selector.
_ForwardIterator __search_n(_ForwardIterator __first, _ForwardIterator __last, _Integer __count, const _Tp &__val, std::forward_iterator_tag)
Definition: stl_algo.h:340
A pair of iterators. The usual iterator operations are applied to both child iterators.
Definition: iterator.h:44
Forces sequential execution at compile time.
Definition: tags.h:42
Parallel balanced (work-stealing).
Definition: types.h:51
UserOp for_each_template_random_access(InputIterator begin, InputIterator end, UserOp user_op, Functionality &functionality, Red reduction, Result reduction_start, Result &output, typename std::iterator_traits< InputIterator >::difference_type bound, _Parallelism parallelism_tag)
Chose the desired algorithm by evaluating parallelism_tag.
Definition: for_each.h:61
Similar to std::equal_to, but allows two different types.
Definition: base.h:250
Similar to std::less, but allows two different types.
Definition: base.h:258
Parallel implementation of std::merge(). This file is a GNU parallel extension to the Standard C++ Li...
Sequential helper functions. This file is a GNU parallel extension to the Standard C++ Library...
Test predicate on two adjacent elements.
Recommends parallel execution at compile time, optionally using a user-specified number of threads...
Definition: tags.h:46
Function objects representing different tasks to be plugged into the parallel find algorithm...
uint64 sequence_index_t
Unsigned integer to index elements. The total number of elements for each algorithm must fit into thi...
Definition: types.h:135
Parallelization of embarrassingly parallel execution by means of work-stealing.
std::transform() selector, two input sequences variant.
Functors representing different tasks to be plugged into the generic parallelization methods for emba...
OutputIterator parallel_unique_copy(InputIterator first, InputIterator last, OutputIterator result, BinaryPredicate binary_pred)
Parallel std::unique_copy(), w/o explicit equality predicate.
Definition: unique_copy.h:51
Parallel implementations of std::unique_copy(). This file is a GNU parallel extension to the Standard...
Forces parallel sorting using multiway mergesort with exact splitting at compile time.
Definition: tags.h:143
Test predicate on several elements.
void parallel_partial_sort(RandomAccessIterator begin, RandomAccessIterator middle, RandomAccessIterator end, Comparator comp)
Parallel implementation of std::partial_sort().
Definition: partition.h:418
RandomAccessIterator3 parallel_merge_advance(RandomAccessIterator1 &begin1, RandomAccessIterator1 end1, RandomAccessIterator2 &begin2, RandomAccessIterator2 end2, RandomAccessIterator3 target, typename std::iterator_traits< RandomAccessIterator1 >::difference_type max_length, Comparator comp)
Merge routine fallback to sequential in case the iterators of the two input sequences are of differen...
Definition: merge.h:198
void sequential_random_shuffle(RandomAccessIterator begin, RandomAccessIterator end, RandomNumberGenerator &rng)
Sequential cache-efficient random shuffle.
Parallel implementations of set operations for random-access iterators. This file is a GNU parallel e...
Parallel implementation base for std::find(), std::equal() and related functions. This file is a GNU ...
Functor wrapper for std::rand().
Definition: algo.h:1632
Parallelization of embarrassingly parallel execution by means of an OpenMP for loop with static sched...
Recommends parallel execution using the default parallel algorithm.
Definition: tags.h:85
void parallel_random_shuffle(RandomAccessIterator begin, RandomAccessIterator end, RandomNumberGenerator rng=random_number())
Parallel random public call.
std::transform() selector, one input sequence variant.
Reduction function doing nothing.
Forces parallel sorting using unbalanced quicksort at compile time.
Definition: tags.h:161
Parallel sorting algorithm switch. This file is a GNU parallel extension to the Standard C++ Library...
std::generate() selector.
One of the math functors.
Definition: stl_function.h:135
void parallel_nth_element(RandomAccessIterator begin, RandomAccessIterator nth, RandomAccessIterator end, Comparator comp)
Parallel implementation of std::nth_element().
Definition: partition.h:330
_RandomAccessIterator1 search_template(_RandomAccessIterator1 begin1, _RandomAccessIterator1 end1, _RandomAccessIterator2 begin2, _RandomAccessIterator2 end2, Pred pred)
Parallel std::search.
Definition: search.h:82
One of the comparison functors.
Definition: stl_function.h:226
std::pair< RandomAccessIterator1, RandomAccessIterator2 > find_template(RandomAccessIterator1 begin1, RandomAccessIterator1 end1, RandomAccessIterator2 begin2, Pred pred, Selector selector)
Parallel std::find, switch for different algorithms.
Definition: find.h:60
Parallelization of embarrassingly parallel execution by means of equal splitting. This file is a GNU ...
Selector that just returns the passed iterator.
Main interface for embarrassingly parallel functions.