libstdc++
algo.h
Go to the documentation of this file.
1 // -*- C++ -*-
2 
3 // Copyright (C) 2007-2018 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>
49 #include <parallel/omp_loop_static.h>
50 #include <parallel/for_each_selectors.h>
51 #include <parallel/for_each.h>
52 #include <parallel/find.h>
53 #include <parallel/find_selectors.h>
54 #include <parallel/search.h>
55 #include <parallel/random_shuffle.h>
56 #include <parallel/partition.h>
57 #include <parallel/merge.h>
58 #include <parallel/unique_copy.h>
59 #include <parallel/set_operations.h>
60 
61 namespace std _GLIBCXX_VISIBILITY(default)
62 {
63 namespace __parallel
64 {
65  // Sequential fallback
66  template<typename _IIter, typename _Function>
67  inline _Function
68  for_each(_IIter __begin, _IIter __end, _Function __f,
69  __gnu_parallel::sequential_tag)
70  { return _GLIBCXX_STD_A::for_each(__begin, __end, __f); }
71 
72  // Sequential fallback for input iterator case
73  template<typename _IIter, typename _Function, typename _IteratorTag>
74  inline _Function
75  __for_each_switch(_IIter __begin, _IIter __end, _Function __f,
76  _IteratorTag)
77  { return for_each(__begin, __end, __f, __gnu_parallel::sequential_tag()); }
78 
79  // Parallel algorithm for random access iterators
80  template<typename _RAIter, typename _Function>
81  _Function
82  __for_each_switch(_RAIter __begin, _RAIter __end,
83  _Function __f, random_access_iterator_tag,
84  __gnu_parallel::_Parallelism __parallelism_tag)
85  {
86  if (_GLIBCXX_PARALLEL_CONDITION(
87  static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
88  >= __gnu_parallel::_Settings::get().for_each_minimal_n
89  && __gnu_parallel::__is_parallel(__parallelism_tag)))
90  {
91  bool __dummy;
92  __gnu_parallel::__for_each_selector<_RAIter> __functionality;
93 
94  return __gnu_parallel::
95  __for_each_template_random_access(
96  __begin, __end, __f, __functionality,
97  __gnu_parallel::_DummyReduct(), true, __dummy, -1,
98  __parallelism_tag);
99  }
100  else
101  return for_each(__begin, __end, __f, __gnu_parallel::sequential_tag());
102  }
103 
104  // Public interface
105  template<typename _Iterator, typename _Function>
106  inline _Function
107  for_each(_Iterator __begin, _Iterator __end, _Function __f,
108  __gnu_parallel::_Parallelism __parallelism_tag)
109  {
110  return __for_each_switch(__begin, __end, __f,
111  std::__iterator_category(__begin),
112  __parallelism_tag);
113  }
114 
115  template<typename _Iterator, typename _Function>
116  inline _Function
117  for_each(_Iterator __begin, _Iterator __end, _Function __f)
118  {
119  return __for_each_switch(__begin, __end, __f,
120  std::__iterator_category(__begin));
121  }
122 
123  // Sequential fallback
124  template<typename _IIter, typename _Tp>
125  inline _IIter
126  find(_IIter __begin, _IIter __end, const _Tp& __val,
127  __gnu_parallel::sequential_tag)
128  { return _GLIBCXX_STD_A::find(__begin, __end, __val); }
129 
130  // Sequential fallback for input iterator case
131  template<typename _IIter, typename _Tp, typename _IteratorTag>
132  inline _IIter
133  __find_switch(_IIter __begin, _IIter __end, const _Tp& __val,
134  _IteratorTag)
135  { return _GLIBCXX_STD_A::find(__begin, __end, __val); }
136 
137  // Parallel find for random access iterators
138  template<typename _RAIter, typename _Tp>
139  _RAIter
140  __find_switch(_RAIter __begin, _RAIter __end,
141  const _Tp& __val, random_access_iterator_tag)
142  {
143  typedef iterator_traits<_RAIter> _TraitsType;
144  typedef typename _TraitsType::value_type _ValueType;
145 
146  if (_GLIBCXX_PARALLEL_CONDITION(true))
147  {
148  __gnu_parallel::__binder2nd<__gnu_parallel::_EqualTo<_ValueType,
149  const _Tp&>,
150  _ValueType, const _Tp&, bool>
151  __comp(__gnu_parallel::_EqualTo<_ValueType, const _Tp&>(), __val);
152  return __gnu_parallel::__find_template(
153  __begin, __end, __begin, __comp,
154  __gnu_parallel::__find_if_selector()).first;
155  }
156  else
157  return _GLIBCXX_STD_A::find(__begin, __end, __val);
158  }
159 
160  // Public interface
161  template<typename _IIter, typename _Tp>
162  inline _IIter
163  find(_IIter __begin, _IIter __end, const _Tp& __val)
164  {
165  return __find_switch(__begin, __end, __val,
166  std::__iterator_category(__begin));
167  }
168 
169  // Sequential fallback
170  template<typename _IIter, typename _Predicate>
171  inline _IIter
172  find_if(_IIter __begin, _IIter __end, _Predicate __pred,
173  __gnu_parallel::sequential_tag)
174  { return _GLIBCXX_STD_A::find_if(__begin, __end, __pred); }
175 
176  // Sequential fallback for input iterator case
177  template<typename _IIter, typename _Predicate, typename _IteratorTag>
178  inline _IIter
179  __find_if_switch(_IIter __begin, _IIter __end, _Predicate __pred,
180  _IteratorTag)
181  { return _GLIBCXX_STD_A::find_if(__begin, __end, __pred); }
182 
183  // Parallel find_if for random access iterators
184  template<typename _RAIter, typename _Predicate>
185  _RAIter
186  __find_if_switch(_RAIter __begin, _RAIter __end,
187  _Predicate __pred, random_access_iterator_tag)
188  {
189  if (_GLIBCXX_PARALLEL_CONDITION(true))
190  return __gnu_parallel::__find_template(__begin, __end, __begin, __pred,
191  __gnu_parallel::
192  __find_if_selector()).first;
193  else
194  return _GLIBCXX_STD_A::find_if(__begin, __end, __pred);
195  }
196 
197  // Public interface
198  template<typename _IIter, typename _Predicate>
199  inline _IIter
200  find_if(_IIter __begin, _IIter __end, _Predicate __pred)
201  {
202  return __find_if_switch(__begin, __end, __pred,
203  std::__iterator_category(__begin));
204  }
205 
206  // Sequential fallback
207  template<typename _IIter, typename _FIterator>
208  inline _IIter
209  find_first_of(_IIter __begin1, _IIter __end1,
210  _FIterator __begin2, _FIterator __end2,
211  __gnu_parallel::sequential_tag)
212  {
213  return _GLIBCXX_STD_A::find_first_of(__begin1, __end1, __begin2, __end2);
214  }
215 
216  // Sequential fallback
217  template<typename _IIter, typename _FIterator,
218  typename _BinaryPredicate>
219  inline _IIter
220  find_first_of(_IIter __begin1, _IIter __end1,
221  _FIterator __begin2, _FIterator __end2,
222  _BinaryPredicate __comp, __gnu_parallel::sequential_tag)
223  { return _GLIBCXX_STD_A::find_first_of(
224  __begin1, __end1, __begin2, __end2, __comp); }
225 
226  // Sequential fallback for input iterator type
227  template<typename _IIter, typename _FIterator,
228  typename _IteratorTag1, typename _IteratorTag2>
229  inline _IIter
230  __find_first_of_switch(_IIter __begin1, _IIter __end1,
231  _FIterator __begin2, _FIterator __end2,
232  _IteratorTag1, _IteratorTag2)
233  { return find_first_of(__begin1, __end1, __begin2, __end2,
234  __gnu_parallel::sequential_tag()); }
235 
236  // Parallel algorithm for random access iterators
237  template<typename _RAIter, typename _FIterator,
238  typename _BinaryPredicate, typename _IteratorTag>
239  inline _RAIter
240  __find_first_of_switch(_RAIter __begin1,
241  _RAIter __end1,
242  _FIterator __begin2, _FIterator __end2,
243  _BinaryPredicate __comp, random_access_iterator_tag,
244  _IteratorTag)
245  {
246  return __gnu_parallel::
247  __find_template(__begin1, __end1, __begin1, __comp,
248  __gnu_parallel::__find_first_of_selector
249  <_FIterator>(__begin2, __end2)).first;
250  }
251 
252  // Sequential fallback for input iterator type
253  template<typename _IIter, typename _FIterator,
254  typename _BinaryPredicate, typename _IteratorTag1,
255  typename _IteratorTag2>
256  inline _IIter
257  __find_first_of_switch(_IIter __begin1, _IIter __end1,
258  _FIterator __begin2, _FIterator __end2,
259  _BinaryPredicate __comp, _IteratorTag1, _IteratorTag2)
260  { return find_first_of(__begin1, __end1, __begin2, __end2, __comp,
261  __gnu_parallel::sequential_tag()); }
262 
263  // Public interface
264  template<typename _IIter, typename _FIterator,
265  typename _BinaryPredicate>
266  inline _IIter
267  find_first_of(_IIter __begin1, _IIter __end1,
268  _FIterator __begin2, _FIterator __end2,
269  _BinaryPredicate __comp)
270  {
271  return __find_first_of_switch(__begin1, __end1, __begin2, __end2, __comp,
272  std::__iterator_category(__begin1),
273  std::__iterator_category(__begin2));
274  }
275 
276  // Public interface, insert default comparator
277  template<typename _IIter, typename _FIterator>
278  inline _IIter
279  find_first_of(_IIter __begin1, _IIter __end1,
280  _FIterator __begin2, _FIterator __end2)
281  {
282  typedef typename std::iterator_traits<_IIter>::value_type _IValueType;
283  typedef typename std::iterator_traits<_FIterator>::value_type _FValueType;
284 
285  return __gnu_parallel::find_first_of(__begin1, __end1, __begin2, __end2,
286  __gnu_parallel::_EqualTo<_IValueType, _FValueType>());
287  }
288 
289  // Sequential fallback
290  template<typename _IIter, typename _OutputIterator>
291  inline _OutputIterator
292  unique_copy(_IIter __begin1, _IIter __end1, _OutputIterator __out,
293  __gnu_parallel::sequential_tag)
294  { return _GLIBCXX_STD_A::unique_copy(__begin1, __end1, __out); }
295 
296  // Sequential fallback
297  template<typename _IIter, typename _OutputIterator,
298  typename _Predicate>
299  inline _OutputIterator
300  unique_copy(_IIter __begin1, _IIter __end1, _OutputIterator __out,
301  _Predicate __pred, __gnu_parallel::sequential_tag)
302  { return _GLIBCXX_STD_A::unique_copy(__begin1, __end1, __out, __pred); }
303 
304  // Sequential fallback for input iterator case
305  template<typename _IIter, typename _OutputIterator,
306  typename _Predicate, typename _IteratorTag1, typename _IteratorTag2>
307  inline _OutputIterator
308  __unique_copy_switch(_IIter __begin, _IIter __last,
309  _OutputIterator __out, _Predicate __pred,
310  _IteratorTag1, _IteratorTag2)
311  { return _GLIBCXX_STD_A::unique_copy(__begin, __last, __out, __pred); }
312 
313  // Parallel unique_copy for random access iterators
314  template<typename _RAIter, typename RandomAccessOutputIterator,
315  typename _Predicate>
316  RandomAccessOutputIterator
317  __unique_copy_switch(_RAIter __begin, _RAIter __last,
318  RandomAccessOutputIterator __out, _Predicate __pred,
319  random_access_iterator_tag, random_access_iterator_tag)
320  {
321  if (_GLIBCXX_PARALLEL_CONDITION(
322  static_cast<__gnu_parallel::_SequenceIndex>(__last - __begin)
323  > __gnu_parallel::_Settings::get().unique_copy_minimal_n))
324  return __gnu_parallel::__parallel_unique_copy(
325  __begin, __last, __out, __pred);
326  else
327  return _GLIBCXX_STD_A::unique_copy(__begin, __last, __out, __pred);
328  }
329 
330  // Public interface
331  template<typename _IIter, typename _OutputIterator>
332  inline _OutputIterator
333  unique_copy(_IIter __begin1, _IIter __end1, _OutputIterator __out)
334  {
335  typedef typename std::iterator_traits<_IIter>::value_type _ValueType;
336 
337  return __unique_copy_switch(
338  __begin1, __end1, __out, equal_to<_ValueType>(),
339  std::__iterator_category(__begin1),
340  std::__iterator_category(__out));
341  }
342 
343  // Public interface
344  template<typename _IIter, typename _OutputIterator, typename _Predicate>
345  inline _OutputIterator
346  unique_copy(_IIter __begin1, _IIter __end1, _OutputIterator __out,
347  _Predicate __pred)
348  {
349  return __unique_copy_switch(
350  __begin1, __end1, __out, __pred,
351  std::__iterator_category(__begin1),
352  std::__iterator_category(__out));
353  }
354 
355  // Sequential fallback
356  template<typename _IIter1, typename _IIter2,
357  typename _OutputIterator>
358  inline _OutputIterator
359  set_union(_IIter1 __begin1, _IIter1 __end1,
360  _IIter2 __begin2, _IIter2 __end2,
361  _OutputIterator __out, __gnu_parallel::sequential_tag)
362  { return _GLIBCXX_STD_A::set_union(
363  __begin1, __end1, __begin2, __end2, __out); }
364 
365  // Sequential fallback
366  template<typename _IIter1, typename _IIter2,
367  typename _OutputIterator, typename _Predicate>
368  inline _OutputIterator
369  set_union(_IIter1 __begin1, _IIter1 __end1,
370  _IIter2 __begin2, _IIter2 __end2,
371  _OutputIterator __out, _Predicate __pred,
372  __gnu_parallel::sequential_tag)
373  { return _GLIBCXX_STD_A::set_union(__begin1, __end1,
374  __begin2, __end2, __out, __pred); }
375 
376  // Sequential fallback for input iterator case
377  template<typename _IIter1, typename _IIter2, typename _Predicate,
378  typename _OutputIterator, typename _IteratorTag1,
379  typename _IteratorTag2, typename _IteratorTag3>
380  inline _OutputIterator
381  __set_union_switch(
382  _IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, _IIter2 __end2,
383  _OutputIterator __result, _Predicate __pred,
384  _IteratorTag1, _IteratorTag2, _IteratorTag3)
385  { return _GLIBCXX_STD_A::set_union(__begin1, __end1,
386  __begin2, __end2, __result, __pred); }
387 
388  // Parallel set_union for random access iterators
389  template<typename _RAIter1, typename _RAIter2,
390  typename _Output_RAIter, typename _Predicate>
391  _Output_RAIter
392  __set_union_switch(_RAIter1 __begin1, _RAIter1 __end1,
393  _RAIter2 __begin2, _RAIter2 __end2,
394  _Output_RAIter __result, _Predicate __pred,
395  random_access_iterator_tag, random_access_iterator_tag,
396  random_access_iterator_tag)
397  {
398  if (_GLIBCXX_PARALLEL_CONDITION(
399  static_cast<__gnu_parallel::_SequenceIndex>(__end1 - __begin1)
400  >= __gnu_parallel::_Settings::get().set_union_minimal_n
401  || static_cast<__gnu_parallel::_SequenceIndex>(__end2 - __begin2)
402  >= __gnu_parallel::_Settings::get().set_union_minimal_n))
403  return __gnu_parallel::__parallel_set_union(
404  __begin1, __end1, __begin2, __end2, __result, __pred);
405  else
406  return _GLIBCXX_STD_A::set_union(__begin1, __end1,
407  __begin2, __end2, __result, __pred);
408  }
409 
410  // Public interface
411  template<typename _IIter1, typename _IIter2,
412  typename _OutputIterator>
413  inline _OutputIterator
414  set_union(_IIter1 __begin1, _IIter1 __end1,
415  _IIter2 __begin2, _IIter2 __end2, _OutputIterator __out)
416  {
417  typedef typename std::iterator_traits<_IIter1>::value_type _ValueType1;
418  typedef typename std::iterator_traits<_IIter2>::value_type _ValueType2;
419 
420  return __set_union_switch(
421  __begin1, __end1, __begin2, __end2, __out,
422  __gnu_parallel::_Less<_ValueType1, _ValueType2>(),
423  std::__iterator_category(__begin1),
424  std::__iterator_category(__begin2),
425  std::__iterator_category(__out));
426  }
427 
428  // Public interface
429  template<typename _IIter1, typename _IIter2,
430  typename _OutputIterator, typename _Predicate>
431  inline _OutputIterator
432  set_union(_IIter1 __begin1, _IIter1 __end1,
433  _IIter2 __begin2, _IIter2 __end2,
434  _OutputIterator __out, _Predicate __pred)
435  {
436  return __set_union_switch(
437  __begin1, __end1, __begin2, __end2, __out, __pred,
438  std::__iterator_category(__begin1),
439  std::__iterator_category(__begin2),
440  std::__iterator_category(__out));
441  }
442 
443  // Sequential fallback.
444  template<typename _IIter1, typename _IIter2,
445  typename _OutputIterator>
446  inline _OutputIterator
447  set_intersection(_IIter1 __begin1, _IIter1 __end1,
448  _IIter2 __begin2, _IIter2 __end2,
449  _OutputIterator __out, __gnu_parallel::sequential_tag)
450  { return _GLIBCXX_STD_A::set_intersection(__begin1, __end1,
451  __begin2, __end2, __out); }
452 
453  // Sequential fallback.
454  template<typename _IIter1, typename _IIter2,
455  typename _OutputIterator, typename _Predicate>
456  inline _OutputIterator
457  set_intersection(_IIter1 __begin1, _IIter1 __end1,
458  _IIter2 __begin2, _IIter2 __end2,
459  _OutputIterator __out, _Predicate __pred,
460  __gnu_parallel::sequential_tag)
461  { return _GLIBCXX_STD_A::set_intersection(
462  __begin1, __end1, __begin2, __end2, __out, __pred); }
463 
464  // Sequential fallback for input iterator case
465  template<typename _IIter1, typename _IIter2,
466  typename _Predicate, typename _OutputIterator,
467  typename _IteratorTag1, typename _IteratorTag2,
468  typename _IteratorTag3>
469  inline _OutputIterator
470  __set_intersection_switch(_IIter1 __begin1, _IIter1 __end1,
471  _IIter2 __begin2, _IIter2 __end2,
472  _OutputIterator __result, _Predicate __pred,
473  _IteratorTag1, _IteratorTag2, _IteratorTag3)
474  { return _GLIBCXX_STD_A::set_intersection(__begin1, __end1, __begin2,
475  __end2, __result, __pred); }
476 
477  // Parallel set_intersection for random access iterators
478  template<typename _RAIter1, typename _RAIter2,
479  typename _Output_RAIter, typename _Predicate>
480  _Output_RAIter
481  __set_intersection_switch(_RAIter1 __begin1,
482  _RAIter1 __end1,
483  _RAIter2 __begin2,
484  _RAIter2 __end2,
485  _Output_RAIter __result,
486  _Predicate __pred,
487  random_access_iterator_tag,
488  random_access_iterator_tag,
489  random_access_iterator_tag)
490  {
491  if (_GLIBCXX_PARALLEL_CONDITION(
492  static_cast<__gnu_parallel::_SequenceIndex>(__end1 - __begin1)
493  >= __gnu_parallel::_Settings::get().set_union_minimal_n
494  || static_cast<__gnu_parallel::_SequenceIndex>(__end2 - __begin2)
495  >= __gnu_parallel::_Settings::get().set_union_minimal_n))
496  return __gnu_parallel::__parallel_set_intersection(
497  __begin1, __end1, __begin2, __end2, __result, __pred);
498  else
499  return _GLIBCXX_STD_A::set_intersection(
500  __begin1, __end1, __begin2, __end2, __result, __pred);
501  }
502 
503  // Public interface
504  template<typename _IIter1, typename _IIter2,
505  typename _OutputIterator>
506  inline _OutputIterator
507  set_intersection(_IIter1 __begin1, _IIter1 __end1,
508  _IIter2 __begin2, _IIter2 __end2,
509  _OutputIterator __out)
510  {
511  typedef typename std::iterator_traits<_IIter1>::value_type _ValueType1;
512  typedef typename std::iterator_traits<_IIter2>::value_type _ValueType2;
513 
514  return __set_intersection_switch(
515  __begin1, __end1, __begin2, __end2, __out,
516  __gnu_parallel::_Less<_ValueType1, _ValueType2>(),
517  std::__iterator_category(__begin1),
518  std::__iterator_category(__begin2),
519  std::__iterator_category(__out));
520  }
521 
522  template<typename _IIter1, typename _IIter2,
523  typename _OutputIterator, typename _Predicate>
524  inline _OutputIterator
525  set_intersection(_IIter1 __begin1, _IIter1 __end1,
526  _IIter2 __begin2, _IIter2 __end2,
527  _OutputIterator __out, _Predicate __pred)
528  {
529  return __set_intersection_switch(
530  __begin1, __end1, __begin2, __end2, __out, __pred,
531  std::__iterator_category(__begin1),
532  std::__iterator_category(__begin2),
533  std::__iterator_category(__out));
534  }
535 
536  // Sequential fallback
537  template<typename _IIter1, typename _IIter2,
538  typename _OutputIterator>
539  inline _OutputIterator
540  set_symmetric_difference(_IIter1 __begin1, _IIter1 __end1,
541  _IIter2 __begin2, _IIter2 __end2,
542  _OutputIterator __out,
543  __gnu_parallel::sequential_tag)
544  { return _GLIBCXX_STD_A::set_symmetric_difference(
545  __begin1, __end1, __begin2, __end2, __out); }
546 
547  // Sequential fallback
548  template<typename _IIter1, typename _IIter2,
549  typename _OutputIterator, typename _Predicate>
550  inline _OutputIterator
551  set_symmetric_difference(_IIter1 __begin1, _IIter1 __end1,
552  _IIter2 __begin2, _IIter2 __end2,
553  _OutputIterator __out, _Predicate __pred,
554  __gnu_parallel::sequential_tag)
555  { return _GLIBCXX_STD_A::set_symmetric_difference(
556  __begin1, __end1, __begin2, __end2, __out, __pred); }
557 
558  // Sequential fallback for input iterator case
559  template<typename _IIter1, typename _IIter2,
560  typename _Predicate, typename _OutputIterator,
561  typename _IteratorTag1, typename _IteratorTag2,
562  typename _IteratorTag3>
563  inline _OutputIterator
564  __set_symmetric_difference_switch(
565  _IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, _IIter2 __end2,
566  _OutputIterator __result, _Predicate __pred,
567  _IteratorTag1, _IteratorTag2, _IteratorTag3)
568  { return _GLIBCXX_STD_A::set_symmetric_difference(
569  __begin1, __end1, __begin2, __end2, __result, __pred); }
570 
571  // Parallel set_symmetric_difference for random access iterators
572  template<typename _RAIter1, typename _RAIter2,
573  typename _Output_RAIter, typename _Predicate>
574  _Output_RAIter
575  __set_symmetric_difference_switch(_RAIter1 __begin1,
576  _RAIter1 __end1,
577  _RAIter2 __begin2,
578  _RAIter2 __end2,
579  _Output_RAIter __result,
580  _Predicate __pred,
581  random_access_iterator_tag,
582  random_access_iterator_tag,
583  random_access_iterator_tag)
584  {
585  if (_GLIBCXX_PARALLEL_CONDITION(
586  static_cast<__gnu_parallel::_SequenceIndex>(__end1 - __begin1)
587  >= __gnu_parallel::_Settings::get().set_symmetric_difference_minimal_n
588  || static_cast<__gnu_parallel::_SequenceIndex>(__end2 - __begin2)
589  >= __gnu_parallel::_Settings::get().set_symmetric_difference_minimal_n))
590  return __gnu_parallel::__parallel_set_symmetric_difference(
591  __begin1, __end1, __begin2, __end2, __result, __pred);
592  else
593  return _GLIBCXX_STD_A::set_symmetric_difference(
594  __begin1, __end1, __begin2, __end2, __result, __pred);
595  }
596 
597  // Public interface.
598  template<typename _IIter1, typename _IIter2,
599  typename _OutputIterator>
600  inline _OutputIterator
601  set_symmetric_difference(_IIter1 __begin1, _IIter1 __end1,
602  _IIter2 __begin2, _IIter2 __end2,
603  _OutputIterator __out)
604  {
605  typedef typename std::iterator_traits<_IIter1>::value_type _ValueType1;
606  typedef typename std::iterator_traits<_IIter2>::value_type _ValueType2;
607 
608  return __set_symmetric_difference_switch(
609  __begin1, __end1, __begin2, __end2, __out,
610  __gnu_parallel::_Less<_ValueType1, _ValueType2>(),
611  std::__iterator_category(__begin1),
612  std::__iterator_category(__begin2),
613  std::__iterator_category(__out));
614  }
615 
616  // Public interface.
617  template<typename _IIter1, typename _IIter2,
618  typename _OutputIterator, typename _Predicate>
619  inline _OutputIterator
620  set_symmetric_difference(_IIter1 __begin1, _IIter1 __end1,
621  _IIter2 __begin2, _IIter2 __end2,
622  _OutputIterator __out, _Predicate __pred)
623  {
624  return __set_symmetric_difference_switch(
625  __begin1, __end1, __begin2, __end2, __out, __pred,
626  std::__iterator_category(__begin1),
627  std::__iterator_category(__begin2),
628  std::__iterator_category(__out));
629  }
630 
631  // Sequential fallback.
632  template<typename _IIter1, typename _IIter2,
633  typename _OutputIterator>
634  inline _OutputIterator
635  set_difference(_IIter1 __begin1, _IIter1 __end1,
636  _IIter2 __begin2, _IIter2 __end2,
637  _OutputIterator __out, __gnu_parallel::sequential_tag)
638  { return _GLIBCXX_STD_A::set_difference(
639  __begin1,__end1, __begin2, __end2, __out); }
640 
641  // Sequential fallback.
642  template<typename _IIter1, typename _IIter2,
643  typename _OutputIterator, typename _Predicate>
644  inline _OutputIterator
645  set_difference(_IIter1 __begin1, _IIter1 __end1,
646  _IIter2 __begin2, _IIter2 __end2,
647  _OutputIterator __out, _Predicate __pred,
648  __gnu_parallel::sequential_tag)
649  { return _GLIBCXX_STD_A::set_difference(__begin1, __end1,
650  __begin2, __end2, __out, __pred); }
651 
652  // Sequential fallback for input iterator case.
653  template<typename _IIter1, typename _IIter2, typename _Predicate,
654  typename _OutputIterator, typename _IteratorTag1,
655  typename _IteratorTag2, typename _IteratorTag3>
656  inline _OutputIterator
657  __set_difference_switch(_IIter1 __begin1, _IIter1 __end1,
658  _IIter2 __begin2, _IIter2 __end2,
659  _OutputIterator __result, _Predicate __pred,
660  _IteratorTag1, _IteratorTag2, _IteratorTag3)
661  { return _GLIBCXX_STD_A::set_difference(
662  __begin1, __end1, __begin2, __end2, __result, __pred); }
663 
664  // Parallel set_difference for random access iterators
665  template<typename _RAIter1, typename _RAIter2,
666  typename _Output_RAIter, typename _Predicate>
667  _Output_RAIter
668  __set_difference_switch(_RAIter1 __begin1,
669  _RAIter1 __end1,
670  _RAIter2 __begin2,
671  _RAIter2 __end2,
672  _Output_RAIter __result, _Predicate __pred,
673  random_access_iterator_tag,
674  random_access_iterator_tag,
675  random_access_iterator_tag)
676  {
677  if (_GLIBCXX_PARALLEL_CONDITION(
678  static_cast<__gnu_parallel::_SequenceIndex>(__end1 - __begin1)
679  >= __gnu_parallel::_Settings::get().set_difference_minimal_n
680  || static_cast<__gnu_parallel::_SequenceIndex>(__end2 - __begin2)
681  >= __gnu_parallel::_Settings::get().set_difference_minimal_n))
682  return __gnu_parallel::__parallel_set_difference(
683  __begin1, __end1, __begin2, __end2, __result, __pred);
684  else
685  return _GLIBCXX_STD_A::set_difference(
686  __begin1, __end1, __begin2, __end2, __result, __pred);
687  }
688 
689  // Public interface
690  template<typename _IIter1, typename _IIter2,
691  typename _OutputIterator>
692  inline _OutputIterator
693  set_difference(_IIter1 __begin1, _IIter1 __end1,
694  _IIter2 __begin2, _IIter2 __end2,
695  _OutputIterator __out)
696  {
697  typedef typename std::iterator_traits<_IIter1>::value_type _ValueType1;
698  typedef typename std::iterator_traits<_IIter2>::value_type _ValueType2;
699 
700  return __set_difference_switch(
701  __begin1, __end1, __begin2, __end2, __out,
702  __gnu_parallel::_Less<_ValueType1, _ValueType2>(),
703  std::__iterator_category(__begin1),
704  std::__iterator_category(__begin2),
705  std::__iterator_category(__out));
706  }
707 
708  // Public interface
709  template<typename _IIter1, typename _IIter2,
710  typename _OutputIterator, typename _Predicate>
711  inline _OutputIterator
712  set_difference(_IIter1 __begin1, _IIter1 __end1,
713  _IIter2 __begin2, _IIter2 __end2,
714  _OutputIterator __out, _Predicate __pred)
715  {
716  return __set_difference_switch(
717  __begin1, __end1, __begin2, __end2, __out, __pred,
718  std::__iterator_category(__begin1),
719  std::__iterator_category(__begin2),
720  std::__iterator_category(__out));
721  }
722 
723  // Sequential fallback
724  template<typename _FIterator>
725  inline _FIterator
726  adjacent_find(_FIterator __begin, _FIterator __end,
727  __gnu_parallel::sequential_tag)
728  { return _GLIBCXX_STD_A::adjacent_find(__begin, __end); }
729 
730  // Sequential fallback
731  template<typename _FIterator, typename _BinaryPredicate>
732  inline _FIterator
733  adjacent_find(_FIterator __begin, _FIterator __end,
734  _BinaryPredicate __binary_pred,
735  __gnu_parallel::sequential_tag)
736  { return _GLIBCXX_STD_A::adjacent_find(__begin, __end, __binary_pred); }
737 
738  // Parallel algorithm for random access iterators
739  template<typename _RAIter>
740  _RAIter
741  __adjacent_find_switch(_RAIter __begin, _RAIter __end,
742  random_access_iterator_tag)
743  {
744  typedef iterator_traits<_RAIter> _TraitsType;
745  typedef typename _TraitsType::value_type _ValueType;
746 
747  if (_GLIBCXX_PARALLEL_CONDITION(true))
748  {
749  _RAIter __spot = __gnu_parallel::
750  __find_template(
751  __begin, __end - 1, __begin, equal_to<_ValueType>(),
752  __gnu_parallel::__adjacent_find_selector())
753  .first;
754  if (__spot == (__end - 1))
755  return __end;
756  else
757  return __spot;
758  }
759  else
760  return adjacent_find(__begin, __end, __gnu_parallel::sequential_tag());
761  }
762 
763  // Sequential fallback for input iterator case
764  template<typename _FIterator, typename _IteratorTag>
765  inline _FIterator
766  __adjacent_find_switch(_FIterator __begin, _FIterator __end,
767  _IteratorTag)
768  { return adjacent_find(__begin, __end, __gnu_parallel::sequential_tag()); }
769 
770  // Public interface
771  template<typename _FIterator>
772  inline _FIterator
773  adjacent_find(_FIterator __begin, _FIterator __end)
774  {
775  return __adjacent_find_switch(__begin, __end,
776  std::__iterator_category(__begin));
777  }
778 
779  // Sequential fallback for input iterator case
780  template<typename _FIterator, typename _BinaryPredicate,
781  typename _IteratorTag>
782  inline _FIterator
783  __adjacent_find_switch(_FIterator __begin, _FIterator __end,
784  _BinaryPredicate __pred, _IteratorTag)
785  { return adjacent_find(__begin, __end, __pred,
786  __gnu_parallel::sequential_tag()); }
787 
788  // Parallel algorithm for random access iterators
789  template<typename _RAIter, typename _BinaryPredicate>
790  _RAIter
791  __adjacent_find_switch(_RAIter __begin, _RAIter __end,
792  _BinaryPredicate __pred, random_access_iterator_tag)
793  {
794  if (_GLIBCXX_PARALLEL_CONDITION(true))
795  return __gnu_parallel::__find_template(__begin, __end, __begin, __pred,
796  __gnu_parallel::
797  __adjacent_find_selector()).first;
798  else
799  return adjacent_find(__begin, __end, __pred,
800  __gnu_parallel::sequential_tag());
801  }
802 
803  // Public interface
804  template<typename _FIterator, typename _BinaryPredicate>
805  inline _FIterator
806  adjacent_find(_FIterator __begin, _FIterator __end,
807  _BinaryPredicate __pred)
808  {
809  return __adjacent_find_switch(__begin, __end, __pred,
810  std::__iterator_category(__begin));
811  }
812 
813  // Sequential fallback
814  template<typename _IIter, typename _Tp>
815  inline typename iterator_traits<_IIter>::difference_type
816  count(_IIter __begin, _IIter __end, const _Tp& __value,
817  __gnu_parallel::sequential_tag)
818  { return _GLIBCXX_STD_A::count(__begin, __end, __value); }
819 
820  // Parallel code for random access iterators
821  template<typename _RAIter, typename _Tp>
822  typename iterator_traits<_RAIter>::difference_type
823  __count_switch(_RAIter __begin, _RAIter __end,
824  const _Tp& __value, random_access_iterator_tag,
825  __gnu_parallel::_Parallelism __parallelism_tag)
826  {
827  typedef iterator_traits<_RAIter> _TraitsType;
828  typedef typename _TraitsType::value_type _ValueType;
829  typedef typename _TraitsType::difference_type _DifferenceType;
830  typedef __gnu_parallel::_SequenceIndex _SequenceIndex;
831 
832  if (_GLIBCXX_PARALLEL_CONDITION(
833  static_cast<_SequenceIndex>(__end - __begin)
834  >= __gnu_parallel::_Settings::get().count_minimal_n
835  && __gnu_parallel::__is_parallel(__parallelism_tag)))
836  {
837  __gnu_parallel::__count_selector<_RAIter, _DifferenceType>
838  __functionality;
839  _DifferenceType __res = 0;
840  __gnu_parallel::
841  __for_each_template_random_access(
842  __begin, __end, __value, __functionality,
843  std::plus<_SequenceIndex>(), __res, __res, -1,
844  __parallelism_tag);
845  return __res;
846  }
847  else
848  return count(__begin, __end, __value,
849  __gnu_parallel::sequential_tag());
850  }
851 
852  // Sequential fallback for input iterator case.
853  template<typename _IIter, typename _Tp, typename _IteratorTag>
854  inline typename iterator_traits<_IIter>::difference_type
855  __count_switch(_IIter __begin, _IIter __end, const _Tp& __value,
856  _IteratorTag)
857  { return count(__begin, __end, __value, __gnu_parallel::sequential_tag());
858  }
859 
860  // Public interface.
861  template<typename _IIter, typename _Tp>
862  inline typename iterator_traits<_IIter>::difference_type
863  count(_IIter __begin, _IIter __end, const _Tp& __value,
864  __gnu_parallel::_Parallelism __parallelism_tag)
865  {
866  return __count_switch(__begin, __end, __value,
867  std::__iterator_category(__begin),
868  __parallelism_tag);
869  }
870 
871  template<typename _IIter, typename _Tp>
872  inline typename iterator_traits<_IIter>::difference_type
873  count(_IIter __begin, _IIter __end, const _Tp& __value)
874  {
875  return __count_switch(__begin, __end, __value,
876  std::__iterator_category(__begin));
877  }
878 
879 
880  // Sequential fallback.
881  template<typename _IIter, typename _Predicate>
882  inline typename iterator_traits<_IIter>::difference_type
883  count_if(_IIter __begin, _IIter __end, _Predicate __pred,
884  __gnu_parallel::sequential_tag)
885  { return _GLIBCXX_STD_A::count_if(__begin, __end, __pred); }
886 
887  // Parallel count_if for random access iterators
888  template<typename _RAIter, typename _Predicate>
889  typename iterator_traits<_RAIter>::difference_type
890  __count_if_switch(_RAIter __begin, _RAIter __end,
891  _Predicate __pred, random_access_iterator_tag,
892  __gnu_parallel::_Parallelism __parallelism_tag)
893  {
894  typedef iterator_traits<_RAIter> _TraitsType;
895  typedef typename _TraitsType::value_type _ValueType;
896  typedef typename _TraitsType::difference_type _DifferenceType;
897  typedef __gnu_parallel::_SequenceIndex _SequenceIndex;
898 
899  if (_GLIBCXX_PARALLEL_CONDITION(
900  static_cast<_SequenceIndex>(__end - __begin)
901  >= __gnu_parallel::_Settings::get().count_minimal_n
902  && __gnu_parallel::__is_parallel(__parallelism_tag)))
903  {
904  _DifferenceType __res = 0;
905  __gnu_parallel::
906  __count_if_selector<_RAIter, _DifferenceType>
907  __functionality;
908  __gnu_parallel::
909  __for_each_template_random_access(
910  __begin, __end, __pred, __functionality,
911  std::plus<_SequenceIndex>(), __res, __res, -1,
912  __parallelism_tag);
913  return __res;
914  }
915  else
916  return count_if(__begin, __end, __pred,
917  __gnu_parallel::sequential_tag());
918  }
919 
920  // Sequential fallback for input iterator case.
921  template<typename _IIter, typename _Predicate, typename _IteratorTag>
922  inline typename iterator_traits<_IIter>::difference_type
923  __count_if_switch(_IIter __begin, _IIter __end, _Predicate __pred,
924  _IteratorTag)
925  { return count_if(__begin, __end, __pred,
926  __gnu_parallel::sequential_tag()); }
927 
928  // Public interface.
929  template<typename _IIter, typename _Predicate>
930  inline typename iterator_traits<_IIter>::difference_type
931  count_if(_IIter __begin, _IIter __end, _Predicate __pred,
932  __gnu_parallel::_Parallelism __parallelism_tag)
933  {
934  return __count_if_switch(__begin, __end, __pred,
935  std::__iterator_category(__begin),
936  __parallelism_tag);
937  }
938 
939  template<typename _IIter, typename _Predicate>
940  inline typename iterator_traits<_IIter>::difference_type
941  count_if(_IIter __begin, _IIter __end, _Predicate __pred)
942  {
943  return __count_if_switch(__begin, __end, __pred,
944  std::__iterator_category(__begin));
945  }
946 
947 
948  // Sequential fallback.
949  template<typename _FIterator1, typename _FIterator2>
950  inline _FIterator1
951  search(_FIterator1 __begin1, _FIterator1 __end1,
952  _FIterator2 __begin2, _FIterator2 __end2,
953  __gnu_parallel::sequential_tag)
954  { return _GLIBCXX_STD_A::search(__begin1, __end1, __begin2, __end2); }
955 
956  // Parallel algorithm for random access iterator
957  template<typename _RAIter1, typename _RAIter2>
958  _RAIter1
959  __search_switch(_RAIter1 __begin1, _RAIter1 __end1,
960  _RAIter2 __begin2, _RAIter2 __end2,
961  random_access_iterator_tag, random_access_iterator_tag)
962  {
963  typedef typename std::iterator_traits<_RAIter1>::value_type _ValueType1;
964  typedef typename std::iterator_traits<_RAIter2>::value_type _ValueType2;
965 
966  if (_GLIBCXX_PARALLEL_CONDITION(
967  static_cast<__gnu_parallel::_SequenceIndex>(__end1 - __begin1)
968  >= __gnu_parallel::_Settings::get().search_minimal_n))
969  return __gnu_parallel::
970  __search_template(
971  __begin1, __end1, __begin2, __end2,
972  __gnu_parallel::_EqualTo<_ValueType1, _ValueType2>());
973  else
974  return search(__begin1, __end1, __begin2, __end2,
975  __gnu_parallel::sequential_tag());
976  }
977 
978  // Sequential fallback for input iterator case
979  template<typename _FIterator1, typename _FIterator2,
980  typename _IteratorTag1, typename _IteratorTag2>
981  inline _FIterator1
982  __search_switch(_FIterator1 __begin1, _FIterator1 __end1,
983  _FIterator2 __begin2, _FIterator2 __end2,
984  _IteratorTag1, _IteratorTag2)
985  { return search(__begin1, __end1, __begin2, __end2,
986  __gnu_parallel::sequential_tag()); }
987 
988  // Public interface.
989  template<typename _FIterator1, typename _FIterator2>
990  inline _FIterator1
991  search(_FIterator1 __begin1, _FIterator1 __end1,
992  _FIterator2 __begin2, _FIterator2 __end2)
993  {
994  return __search_switch(__begin1, __end1, __begin2, __end2,
995  std::__iterator_category(__begin1),
996  std::__iterator_category(__begin2));
997  }
998 
999  // Public interface.
1000  template<typename _FIterator1, typename _FIterator2,
1001  typename _BinaryPredicate>
1002  inline _FIterator1
1003  search(_FIterator1 __begin1, _FIterator1 __end1,
1004  _FIterator2 __begin2, _FIterator2 __end2,
1005  _BinaryPredicate __pred, __gnu_parallel::sequential_tag)
1006  { return _GLIBCXX_STD_A::search(
1007  __begin1, __end1, __begin2, __end2, __pred); }
1008 
1009  // Parallel algorithm for random access iterator.
1010  template<typename _RAIter1, typename _RAIter2,
1011  typename _BinaryPredicate>
1012  _RAIter1
1013  __search_switch(_RAIter1 __begin1, _RAIter1 __end1,
1014  _RAIter2 __begin2, _RAIter2 __end2,
1015  _BinaryPredicate __pred,
1016  random_access_iterator_tag, random_access_iterator_tag)
1017  {
1018  if (_GLIBCXX_PARALLEL_CONDITION(
1019  static_cast<__gnu_parallel::_SequenceIndex>(__end1 - __begin1)
1020  >= __gnu_parallel::_Settings::get().search_minimal_n))
1021  return __gnu_parallel::__search_template(__begin1, __end1,
1022  __begin2, __end2, __pred);
1023  else
1024  return search(__begin1, __end1, __begin2, __end2, __pred,
1025  __gnu_parallel::sequential_tag());
1026  }
1027 
1028  // Sequential fallback for input iterator case
1029  template<typename _FIterator1, typename _FIterator2,
1030  typename _BinaryPredicate, typename _IteratorTag1,
1031  typename _IteratorTag2>
1032  inline _FIterator1
1033  __search_switch(_FIterator1 __begin1, _FIterator1 __end1,
1034  _FIterator2 __begin2, _FIterator2 __end2,
1035  _BinaryPredicate __pred, _IteratorTag1, _IteratorTag2)
1036  { return search(__begin1, __end1, __begin2, __end2, __pred,
1037  __gnu_parallel::sequential_tag()); }
1038 
1039  // Public interface
1040  template<typename _FIterator1, typename _FIterator2,
1041  typename _BinaryPredicate>
1042  inline _FIterator1
1043  search(_FIterator1 __begin1, _FIterator1 __end1,
1044  _FIterator2 __begin2, _FIterator2 __end2,
1045  _BinaryPredicate __pred)
1046  {
1047  return __search_switch(__begin1, __end1, __begin2, __end2, __pred,
1048  std::__iterator_category(__begin1),
1049  std::__iterator_category(__begin2));
1050  }
1051 
1052  // Sequential fallback
1053  template<typename _FIterator, typename _Integer, typename _Tp>
1054  inline _FIterator
1055  search_n(_FIterator __begin, _FIterator __end, _Integer __count,
1056  const _Tp& __val, __gnu_parallel::sequential_tag)
1057  { return _GLIBCXX_STD_A::search_n(__begin, __end, __count, __val); }
1058 
1059  // Sequential fallback
1060  template<typename _FIterator, typename _Integer, typename _Tp,
1061  typename _BinaryPredicate>
1062  inline _FIterator
1063  search_n(_FIterator __begin, _FIterator __end, _Integer __count,
1064  const _Tp& __val, _BinaryPredicate __binary_pred,
1065  __gnu_parallel::sequential_tag)
1066  { return _GLIBCXX_STD_A::search_n(
1067  __begin, __end, __count, __val, __binary_pred); }
1068 
1069  // Public interface.
1070  template<typename _FIterator, typename _Integer, typename _Tp>
1071  inline _FIterator
1072  search_n(_FIterator __begin, _FIterator __end, _Integer __count,
1073  const _Tp& __val)
1074  {
1075  typedef typename iterator_traits<_FIterator>::value_type _ValueType;
1076  return __gnu_parallel::search_n(__begin, __end, __count, __val,
1077  __gnu_parallel::_EqualTo<_ValueType, _Tp>());
1078  }
1079 
1080  // Parallel algorithm for random access iterators.
1081  template<typename _RAIter, typename _Integer,
1082  typename _Tp, typename _BinaryPredicate>
1083  _RAIter
1084  __search_n_switch(_RAIter __begin, _RAIter __end, _Integer __count,
1085  const _Tp& __val, _BinaryPredicate __binary_pred,
1086  random_access_iterator_tag)
1087  {
1088  if (_GLIBCXX_PARALLEL_CONDITION(
1089  static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
1090  >= __gnu_parallel::_Settings::get().search_minimal_n))
1091  {
1092  __gnu_parallel::_PseudoSequence<_Tp, _Integer> __ps(__val, __count);
1093  return __gnu_parallel::__search_template(
1094  __begin, __end, __ps.begin(), __ps.end(), __binary_pred);
1095  }
1096  else
1097  return _GLIBCXX_STD_A::search_n(__begin, __end, __count, __val,
1098  __binary_pred);
1099  }
1100 
1101  // Sequential fallback for input iterator case.
1102  template<typename _FIterator, typename _Integer, typename _Tp,
1103  typename _BinaryPredicate, typename _IteratorTag>
1104  inline _FIterator
1105  __search_n_switch(_FIterator __begin, _FIterator __end, _Integer __count,
1106  const _Tp& __val, _BinaryPredicate __binary_pred,
1107  _IteratorTag)
1108  { return _GLIBCXX_STD_A::search_n(__begin, __end, __count, __val,
1109  __binary_pred); }
1110 
1111  // Public interface.
1112  template<typename _FIterator, typename _Integer, typename _Tp,
1113  typename _BinaryPredicate>
1114  inline _FIterator
1115  search_n(_FIterator __begin, _FIterator __end, _Integer __count,
1116  const _Tp& __val, _BinaryPredicate __binary_pred)
1117  {
1118  return __search_n_switch(__begin, __end, __count, __val, __binary_pred,
1119  std::__iterator_category(__begin));
1120  }
1121 
1122 
1123  // Sequential fallback.
1124  template<typename _IIter, typename _OutputIterator,
1125  typename _UnaryOperation>
1126  inline _OutputIterator
1127  transform(_IIter __begin, _IIter __end, _OutputIterator __result,
1128  _UnaryOperation __unary_op, __gnu_parallel::sequential_tag)
1129  { return _GLIBCXX_STD_A::transform(__begin, __end, __result, __unary_op); }
1130 
1131  // Parallel unary transform for random access iterators.
1132  template<typename _RAIter1, typename _RAIter2,
1133  typename _UnaryOperation>
1134  _RAIter2
1135  __transform1_switch(_RAIter1 __begin, _RAIter1 __end,
1136  _RAIter2 __result, _UnaryOperation __unary_op,
1137  random_access_iterator_tag, random_access_iterator_tag,
1138  __gnu_parallel::_Parallelism __parallelism_tag)
1139  {
1140  if (_GLIBCXX_PARALLEL_CONDITION(
1141  static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
1142  >= __gnu_parallel::_Settings::get().transform_minimal_n
1143  && __gnu_parallel::__is_parallel(__parallelism_tag)))
1144  {
1145  bool __dummy = true;
1146  typedef __gnu_parallel::_IteratorPair<_RAIter1,
1147  _RAIter2, random_access_iterator_tag> _ItTrip;
1148  _ItTrip __begin_pair(__begin, __result),
1149  __end_pair(__end, __result + (__end - __begin));
1150  __gnu_parallel::__transform1_selector<_ItTrip> __functionality;
1151  __gnu_parallel::
1152  __for_each_template_random_access(
1153  __begin_pair, __end_pair, __unary_op, __functionality,
1154  __gnu_parallel::_DummyReduct(),
1155  __dummy, __dummy, -1, __parallelism_tag);
1156  return __functionality._M_finish_iterator;
1157  }
1158  else
1159  return transform(__begin, __end, __result, __unary_op,
1160  __gnu_parallel::sequential_tag());
1161  }
1162 
1163  // Sequential fallback for input iterator case.
1164  template<typename _RAIter1, typename _RAIter2,
1165  typename _UnaryOperation, typename _IteratorTag1,
1166  typename _IteratorTag2>
1167  inline _RAIter2
1168  __transform1_switch(_RAIter1 __begin, _RAIter1 __end,
1169  _RAIter2 __result, _UnaryOperation __unary_op,
1170  _IteratorTag1, _IteratorTag2)
1171  { return transform(__begin, __end, __result, __unary_op,
1172  __gnu_parallel::sequential_tag()); }
1173 
1174  // Public interface.
1175  template<typename _IIter, typename _OutputIterator,
1176  typename _UnaryOperation>
1177  inline _OutputIterator
1178  transform(_IIter __begin, _IIter __end, _OutputIterator __result,
1179  _UnaryOperation __unary_op,
1180  __gnu_parallel::_Parallelism __parallelism_tag)
1181  {
1182  return __transform1_switch(__begin, __end, __result, __unary_op,
1183  std::__iterator_category(__begin),
1184  std::__iterator_category(__result),
1185  __parallelism_tag);
1186  }
1187 
1188  template<typename _IIter, typename _OutputIterator,
1189  typename _UnaryOperation>
1190  inline _OutputIterator
1191  transform(_IIter __begin, _IIter __end, _OutputIterator __result,
1192  _UnaryOperation __unary_op)
1193  {
1194  return __transform1_switch(__begin, __end, __result, __unary_op,
1195  std::__iterator_category(__begin),
1196  std::__iterator_category(__result));
1197  }
1198 
1199 
1200  // Sequential fallback
1201  template<typename _IIter1, typename _IIter2,
1202  typename _OutputIterator, typename _BinaryOperation>
1203  inline _OutputIterator
1204  transform(_IIter1 __begin1, _IIter1 __end1,
1205  _IIter2 __begin2, _OutputIterator __result,
1206  _BinaryOperation __binary_op, __gnu_parallel::sequential_tag)
1207  { return _GLIBCXX_STD_A::transform(__begin1, __end1,
1208  __begin2, __result, __binary_op); }
1209 
1210  // Parallel binary transform for random access iterators.
1211  template<typename _RAIter1, typename _RAIter2,
1212  typename _RAIter3, typename _BinaryOperation>
1213  _RAIter3
1214  __transform2_switch(_RAIter1 __begin1, _RAIter1 __end1,
1215  _RAIter2 __begin2,
1216  _RAIter3 __result, _BinaryOperation __binary_op,
1217  random_access_iterator_tag, random_access_iterator_tag,
1218  random_access_iterator_tag,
1219  __gnu_parallel::_Parallelism __parallelism_tag)
1220  {
1221  if (_GLIBCXX_PARALLEL_CONDITION(
1222  (__end1 - __begin1) >=
1223  __gnu_parallel::_Settings::get().transform_minimal_n
1224  && __gnu_parallel::__is_parallel(__parallelism_tag)))
1225  {
1226  bool __dummy = true;
1227  typedef __gnu_parallel::_IteratorTriple<_RAIter1,
1228  _RAIter2, _RAIter3,
1229  random_access_iterator_tag> _ItTrip;
1230  _ItTrip __begin_triple(__begin1, __begin2, __result),
1231  __end_triple(__end1, __begin2 + (__end1 - __begin1),
1232  __result + (__end1 - __begin1));
1233  __gnu_parallel::__transform2_selector<_ItTrip> __functionality;
1234  __gnu_parallel::
1235  __for_each_template_random_access(__begin_triple, __end_triple,
1236  __binary_op, __functionality,
1237  __gnu_parallel::_DummyReduct(),
1238  __dummy, __dummy, -1,
1239  __parallelism_tag);
1240  return __functionality._M_finish_iterator;
1241  }
1242  else
1243  return transform(__begin1, __end1, __begin2, __result, __binary_op,
1244  __gnu_parallel::sequential_tag());
1245  }
1246 
1247  // Sequential fallback for input iterator case.
1248  template<typename _IIter1, typename _IIter2,
1249  typename _OutputIterator, typename _BinaryOperation,
1250  typename _Tag1, typename _Tag2, typename _Tag3>
1251  inline _OutputIterator
1252  __transform2_switch(_IIter1 __begin1, _IIter1 __end1,
1253  _IIter2 __begin2, _OutputIterator __result,
1254  _BinaryOperation __binary_op, _Tag1, _Tag2, _Tag3)
1255  { return transform(__begin1, __end1, __begin2, __result, __binary_op,
1256  __gnu_parallel::sequential_tag()); }
1257 
1258  // Public interface.
1259  template<typename _IIter1, typename _IIter2,
1260  typename _OutputIterator, typename _BinaryOperation>
1261  inline _OutputIterator
1262  transform(_IIter1 __begin1, _IIter1 __end1,
1263  _IIter2 __begin2, _OutputIterator __result,
1264  _BinaryOperation __binary_op,
1265  __gnu_parallel::_Parallelism __parallelism_tag)
1266  {
1267  return __transform2_switch(
1268  __begin1, __end1, __begin2, __result, __binary_op,
1269  std::__iterator_category(__begin1),
1270  std::__iterator_category(__begin2),
1271  std::__iterator_category(__result),
1272  __parallelism_tag);
1273  }
1274 
1275  template<typename _IIter1, typename _IIter2,
1276  typename _OutputIterator, typename _BinaryOperation>
1277  inline _OutputIterator
1278  transform(_IIter1 __begin1, _IIter1 __end1,
1279  _IIter2 __begin2, _OutputIterator __result,
1280  _BinaryOperation __binary_op)
1281  {
1282  return __transform2_switch(
1283  __begin1, __end1, __begin2, __result, __binary_op,
1284  std::__iterator_category(__begin1),
1285  std::__iterator_category(__begin2),
1286  std::__iterator_category(__result));
1287  }
1288 
1289  // Sequential fallback
1290  template<typename _FIterator, typename _Tp>
1291  inline void
1292  replace(_FIterator __begin, _FIterator __end, const _Tp& __old_value,
1293  const _Tp& __new_value, __gnu_parallel::sequential_tag)
1294  { _GLIBCXX_STD_A::replace(__begin, __end, __old_value, __new_value); }
1295 
1296  // Sequential fallback for input iterator case
1297  template<typename _FIterator, typename _Tp, typename _IteratorTag>
1298  inline void
1299  __replace_switch(_FIterator __begin, _FIterator __end,
1300  const _Tp& __old_value, const _Tp& __new_value,
1301  _IteratorTag)
1302  { replace(__begin, __end, __old_value, __new_value,
1303  __gnu_parallel::sequential_tag()); }
1304 
1305  // Parallel replace for random access iterators
1306  template<typename _RAIter, typename _Tp>
1307  inline void
1308  __replace_switch(_RAIter __begin, _RAIter __end,
1309  const _Tp& __old_value, const _Tp& __new_value,
1310  random_access_iterator_tag,
1311  __gnu_parallel::_Parallelism __parallelism_tag)
1312  {
1313  // XXX parallel version is where?
1314  replace(__begin, __end, __old_value, __new_value,
1315  __gnu_parallel::sequential_tag());
1316  }
1317 
1318  // Public interface
1319  template<typename _FIterator, typename _Tp>
1320  inline void
1321  replace(_FIterator __begin, _FIterator __end, const _Tp& __old_value,
1322  const _Tp& __new_value,
1323  __gnu_parallel::_Parallelism __parallelism_tag)
1324  {
1325  __replace_switch(__begin, __end, __old_value, __new_value,
1326  std::__iterator_category(__begin),
1327  __parallelism_tag);
1328  }
1329 
1330  template<typename _FIterator, typename _Tp>
1331  inline void
1332  replace(_FIterator __begin, _FIterator __end, const _Tp& __old_value,
1333  const _Tp& __new_value)
1334  {
1335  __replace_switch(__begin, __end, __old_value, __new_value,
1336  std::__iterator_category(__begin));
1337  }
1338 
1339 
1340  // Sequential fallback
1341  template<typename _FIterator, typename _Predicate, typename _Tp>
1342  inline void
1343  replace_if(_FIterator __begin, _FIterator __end, _Predicate __pred,
1344  const _Tp& __new_value, __gnu_parallel::sequential_tag)
1345  { _GLIBCXX_STD_A::replace_if(__begin, __end, __pred, __new_value); }
1346 
1347  // Sequential fallback for input iterator case
1348  template<typename _FIterator, typename _Predicate, typename _Tp,
1349  typename _IteratorTag>
1350  inline void
1351  __replace_if_switch(_FIterator __begin, _FIterator __end,
1352  _Predicate __pred, const _Tp& __new_value, _IteratorTag)
1353  { replace_if(__begin, __end, __pred, __new_value,
1354  __gnu_parallel::sequential_tag()); }
1355 
1356  // Parallel algorithm for random access iterators.
1357  template<typename _RAIter, typename _Predicate, typename _Tp>
1358  void
1359  __replace_if_switch(_RAIter __begin, _RAIter __end,
1360  _Predicate __pred, const _Tp& __new_value,
1361  random_access_iterator_tag,
1362  __gnu_parallel::_Parallelism __parallelism_tag)
1363  {
1364  if (_GLIBCXX_PARALLEL_CONDITION(
1365  static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
1366  >= __gnu_parallel::_Settings::get().replace_minimal_n
1367  && __gnu_parallel::__is_parallel(__parallelism_tag)))
1368  {
1369  bool __dummy;
1370  __gnu_parallel::
1371  __replace_if_selector<_RAIter, _Predicate, _Tp>
1372  __functionality(__new_value);
1373  __gnu_parallel::
1374  __for_each_template_random_access(
1375  __begin, __end, __pred, __functionality,
1376  __gnu_parallel::_DummyReduct(),
1377  true, __dummy, -1, __parallelism_tag);
1378  }
1379  else
1380  replace_if(__begin, __end, __pred, __new_value,
1381  __gnu_parallel::sequential_tag());
1382  }
1383 
1384  // Public interface.
1385  template<typename _FIterator, typename _Predicate, typename _Tp>
1386  inline void
1387  replace_if(_FIterator __begin, _FIterator __end,
1388  _Predicate __pred, const _Tp& __new_value,
1389  __gnu_parallel::_Parallelism __parallelism_tag)
1390  {
1391  __replace_if_switch(__begin, __end, __pred, __new_value,
1392  std::__iterator_category(__begin),
1393  __parallelism_tag);
1394  }
1395 
1396  template<typename _FIterator, typename _Predicate, typename _Tp>
1397  inline void
1398  replace_if(_FIterator __begin, _FIterator __end,
1399  _Predicate __pred, const _Tp& __new_value)
1400  {
1401  __replace_if_switch(__begin, __end, __pred, __new_value,
1402  std::__iterator_category(__begin));
1403  }
1404 
1405  // Sequential fallback
1406  template<typename _FIterator, typename _Generator>
1407  inline void
1408  generate(_FIterator __begin, _FIterator __end, _Generator __gen,
1409  __gnu_parallel::sequential_tag)
1410  { _GLIBCXX_STD_A::generate(__begin, __end, __gen); }
1411 
1412  // Sequential fallback for input iterator case.
1413  template<typename _FIterator, typename _Generator, typename _IteratorTag>
1414  inline void
1415  __generate_switch(_FIterator __begin, _FIterator __end, _Generator __gen,
1416  _IteratorTag)
1417  { generate(__begin, __end, __gen, __gnu_parallel::sequential_tag()); }
1418 
1419  // Parallel algorithm for random access iterators.
1420  template<typename _RAIter, typename _Generator>
1421  void
1422  __generate_switch(_RAIter __begin, _RAIter __end,
1423  _Generator __gen, random_access_iterator_tag,
1424  __gnu_parallel::_Parallelism __parallelism_tag)
1425  {
1426  if (_GLIBCXX_PARALLEL_CONDITION(
1427  static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
1428  >= __gnu_parallel::_Settings::get().generate_minimal_n
1429  && __gnu_parallel::__is_parallel(__parallelism_tag)))
1430  {
1431  bool __dummy;
1432  __gnu_parallel::__generate_selector<_RAIter>
1433  __functionality;
1434  __gnu_parallel::
1435  __for_each_template_random_access(
1436  __begin, __end, __gen, __functionality,
1437  __gnu_parallel::_DummyReduct(),
1438  true, __dummy, -1, __parallelism_tag);
1439  }
1440  else
1441  generate(__begin, __end, __gen, __gnu_parallel::sequential_tag());
1442  }
1443 
1444  // Public interface.
1445  template<typename _FIterator, typename _Generator>
1446  inline void
1447  generate(_FIterator __begin, _FIterator __end,
1448  _Generator __gen, __gnu_parallel::_Parallelism __parallelism_tag)
1449  {
1450  __generate_switch(__begin, __end, __gen,
1451  std::__iterator_category(__begin),
1452  __parallelism_tag);
1453  }
1454 
1455  template<typename _FIterator, typename _Generator>
1456  inline void
1457  generate(_FIterator __begin, _FIterator __end, _Generator __gen)
1458  {
1459  __generate_switch(__begin, __end, __gen,
1460  std::__iterator_category(__begin));
1461  }
1462 
1463 
1464  // Sequential fallback.
1465  template<typename _OutputIterator, typename _Size, typename _Generator>
1466  inline _OutputIterator
1467  generate_n(_OutputIterator __begin, _Size __n, _Generator __gen,
1468  __gnu_parallel::sequential_tag)
1469  { return _GLIBCXX_STD_A::generate_n(__begin, __n, __gen); }
1470 
1471  // Sequential fallback for input iterator case.
1472  template<typename _OutputIterator, typename _Size, typename _Generator,
1473  typename _IteratorTag>
1474  inline _OutputIterator
1475  __generate_n_switch(_OutputIterator __begin, _Size __n, _Generator __gen,
1476  _IteratorTag)
1477  { return generate_n(__begin, __n, __gen,
1478  __gnu_parallel::sequential_tag()); }
1479 
1480  // Parallel algorithm for random access iterators.
1481  template<typename _RAIter, typename _Size, typename _Generator>
1482  inline _RAIter
1483  __generate_n_switch(_RAIter __begin, _Size __n, _Generator __gen,
1484  random_access_iterator_tag,
1485  __gnu_parallel::_Parallelism __parallelism_tag)
1486  {
1487  // XXX parallel version is where?
1488  return generate_n(__begin, __n, __gen, __gnu_parallel::sequential_tag());
1489  }
1490 
1491  // Public interface.
1492  template<typename _OutputIterator, typename _Size, typename _Generator>
1493  inline _OutputIterator
1494  generate_n(_OutputIterator __begin, _Size __n, _Generator __gen,
1495  __gnu_parallel::_Parallelism __parallelism_tag)
1496  {
1497  return __generate_n_switch(__begin, __n, __gen,
1498  std::__iterator_category(__begin),
1499  __parallelism_tag);
1500  }
1501 
1502  template<typename _OutputIterator, typename _Size, typename _Generator>
1503  inline _OutputIterator
1504  generate_n(_OutputIterator __begin, _Size __n, _Generator __gen)
1505  {
1506  return __generate_n_switch(__begin, __n, __gen,
1507  std::__iterator_category(__begin));
1508  }
1509 
1510 
1511  // Sequential fallback.
1512  template<typename _RAIter>
1513  inline void
1514  random_shuffle(_RAIter __begin, _RAIter __end,
1515  __gnu_parallel::sequential_tag)
1516  { _GLIBCXX_STD_A::random_shuffle(__begin, __end); }
1517 
1518  // Sequential fallback.
1519  template<typename _RAIter, typename _RandomNumberGenerator>
1520  inline void
1521  random_shuffle(_RAIter __begin, _RAIter __end,
1522  _RandomNumberGenerator& __rand,
1523  __gnu_parallel::sequential_tag)
1524  { _GLIBCXX_STD_A::random_shuffle(__begin, __end, __rand); }
1525 
1526 
1527  /** @brief Functor wrapper for std::rand(). */
1528  template<typename _MustBeInt = int>
1529  struct _CRandNumber
1530  {
1531  int
1532  operator()(int __limit)
1533  { return rand() % __limit; }
1534  };
1535 
1536  // Fill in random number generator.
1537  template<typename _RAIter>
1538  inline void
1539  random_shuffle(_RAIter __begin, _RAIter __end)
1540  {
1541  _CRandNumber<> __r;
1542  // Parallelization still possible.
1543  __gnu_parallel::random_shuffle(__begin, __end, __r);
1544  }
1545 
1546  // Parallel algorithm for random access iterators.
1547  template<typename _RAIter, typename _RandomNumberGenerator>
1548  void
1549  random_shuffle(_RAIter __begin, _RAIter __end,
1550 #if __cplusplus >= 201103L
1551  _RandomNumberGenerator&& __rand)
1552 #else
1553  _RandomNumberGenerator& __rand)
1554 #endif
1555  {
1556  if (__begin == __end)
1557  return;
1558  if (_GLIBCXX_PARALLEL_CONDITION(
1559  static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
1560  >= __gnu_parallel::_Settings::get().random_shuffle_minimal_n))
1561  __gnu_parallel::__parallel_random_shuffle(__begin, __end, __rand);
1562  else
1563  __gnu_parallel::__sequential_random_shuffle(__begin, __end, __rand);
1564  }
1565 
1566  // Sequential fallback.
1567  template<typename _FIterator, typename _Predicate>
1568  inline _FIterator
1569  partition(_FIterator __begin, _FIterator __end,
1570  _Predicate __pred, __gnu_parallel::sequential_tag)
1571  { return _GLIBCXX_STD_A::partition(__begin, __end, __pred); }
1572 
1573  // Sequential fallback for input iterator case.
1574  template<typename _FIterator, typename _Predicate, typename _IteratorTag>
1575  inline _FIterator
1576  __partition_switch(_FIterator __begin, _FIterator __end,
1577  _Predicate __pred, _IteratorTag)
1578  { return partition(__begin, __end, __pred,
1579  __gnu_parallel::sequential_tag()); }
1580 
1581  // Parallel algorithm for random access iterators.
1582  template<typename _RAIter, typename _Predicate>
1583  _RAIter
1584  __partition_switch(_RAIter __begin, _RAIter __end,
1585  _Predicate __pred, random_access_iterator_tag)
1586  {
1587  if (_GLIBCXX_PARALLEL_CONDITION(
1588  static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
1589  >= __gnu_parallel::_Settings::get().partition_minimal_n))
1590  {
1591  typedef typename std::iterator_traits<_RAIter>::
1592  difference_type _DifferenceType;
1593  _DifferenceType __middle = __gnu_parallel::
1594  __parallel_partition(__begin, __end, __pred,
1595  __gnu_parallel::__get_max_threads());
1596  return __begin + __middle;
1597  }
1598  else
1599  return partition(__begin, __end, __pred,
1600  __gnu_parallel::sequential_tag());
1601  }
1602 
1603  // Public interface.
1604  template<typename _FIterator, typename _Predicate>
1605  inline _FIterator
1606  partition(_FIterator __begin, _FIterator __end, _Predicate __pred)
1607  {
1608  return __partition_switch(__begin, __end, __pred,
1609  std::__iterator_category(__begin));
1610  }
1611 
1612  // sort interface
1613 
1614  // Sequential fallback
1615  template<typename _RAIter>
1616  inline void
1617  sort(_RAIter __begin, _RAIter __end,
1618  __gnu_parallel::sequential_tag)
1619  { _GLIBCXX_STD_A::sort(__begin, __end); }
1620 
1621  // Sequential fallback
1622  template<typename _RAIter, typename _Compare>
1623  inline void
1624  sort(_RAIter __begin, _RAIter __end, _Compare __comp,
1625  __gnu_parallel::sequential_tag)
1626  { _GLIBCXX_STD_A::sort<_RAIter, _Compare>(__begin, __end,
1627  __comp); }
1628 
1629  // Public interface
1630  template<typename _RAIter, typename _Compare,
1631  typename _Parallelism>
1632  void
1633  sort(_RAIter __begin, _RAIter __end, _Compare __comp,
1634  _Parallelism __parallelism)
1635  {
1636  typedef typename iterator_traits<_RAIter>::value_type _ValueType;
1637 
1638  if (__begin != __end)
1639  {
1640  if (_GLIBCXX_PARALLEL_CONDITION(
1641  static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin) >=
1642  __gnu_parallel::_Settings::get().sort_minimal_n))
1643  __gnu_parallel::__parallel_sort<false>(
1644  __begin, __end, __comp, __parallelism);
1645  else
1646  sort(__begin, __end, __comp, __gnu_parallel::sequential_tag());
1647  }
1648  }
1649 
1650  // Public interface, insert default comparator
1651  template<typename _RAIter>
1652  inline void
1653  sort(_RAIter __begin, _RAIter __end)
1654  {
1655  typedef typename iterator_traits<_RAIter>::value_type _ValueType;
1656  sort(__begin, __end, std::less<_ValueType>(),
1657  __gnu_parallel::default_parallel_tag());
1658  }
1659 
1660  // Public interface, insert default comparator
1661  template<typename _RAIter>
1662  inline void
1663  sort(_RAIter __begin, _RAIter __end,
1664  __gnu_parallel::default_parallel_tag __parallelism)
1665  {
1666  typedef typename iterator_traits<_RAIter>::value_type _ValueType;
1667  sort(__begin, __end, std::less<_ValueType>(), __parallelism);
1668  }
1669 
1670  // Public interface, insert default comparator
1671  template<typename _RAIter>
1672  inline void
1673  sort(_RAIter __begin, _RAIter __end,
1674  __gnu_parallel::parallel_tag __parallelism)
1675  {
1676  typedef typename iterator_traits<_RAIter>::value_type _ValueType;
1677  sort(__begin, __end, std::less<_ValueType>(), __parallelism);
1678  }
1679 
1680  // Public interface, insert default comparator
1681  template<typename _RAIter>
1682  inline void
1683  sort(_RAIter __begin, _RAIter __end,
1684  __gnu_parallel::multiway_mergesort_tag __parallelism)
1685  {
1686  typedef typename iterator_traits<_RAIter>::value_type _ValueType;
1687  sort(__begin, __end, std::less<_ValueType>(), __parallelism);
1688  }
1689 
1690  // Public interface, insert default comparator
1691  template<typename _RAIter>
1692  inline void
1693  sort(_RAIter __begin, _RAIter __end,
1694  __gnu_parallel::multiway_mergesort_sampling_tag __parallelism)
1695  {
1696  typedef typename iterator_traits<_RAIter>::value_type _ValueType;
1697  sort(__begin, __end, std::less<_ValueType>(), __parallelism);
1698  }
1699 
1700  // Public interface, insert default comparator
1701  template<typename _RAIter>
1702  inline void
1703  sort(_RAIter __begin, _RAIter __end,
1704  __gnu_parallel::multiway_mergesort_exact_tag __parallelism)
1705  {
1706  typedef typename iterator_traits<_RAIter>::value_type _ValueType;
1707  sort(__begin, __end, std::less<_ValueType>(), __parallelism);
1708  }
1709 
1710  // Public interface, insert default comparator
1711  template<typename _RAIter>
1712  inline void
1713  sort(_RAIter __begin, _RAIter __end,
1714  __gnu_parallel::quicksort_tag __parallelism)
1715  {
1716  typedef typename iterator_traits<_RAIter>::value_type _ValueType;
1717  sort(__begin, __end, std::less<_ValueType>(), __parallelism);
1718  }
1719 
1720  // Public interface, insert default comparator
1721  template<typename _RAIter>
1722  inline void
1723  sort(_RAIter __begin, _RAIter __end,
1724  __gnu_parallel::balanced_quicksort_tag __parallelism)
1725  {
1726  typedef typename iterator_traits<_RAIter>::value_type _ValueType;
1727  sort(__begin, __end, std::less<_ValueType>(), __parallelism);
1728  }
1729 
1730  // Public interface
1731  template<typename _RAIter, typename _Compare>
1732  void
1733  sort(_RAIter __begin, _RAIter __end, _Compare __comp)
1734  {
1735  typedef typename iterator_traits<_RAIter>::value_type _ValueType;
1736  sort(__begin, __end, __comp, __gnu_parallel::default_parallel_tag());
1737  }
1738 
1739  // stable_sort interface
1740 
1741 
1742  // Sequential fallback
1743  template<typename _RAIter>
1744  inline void
1745  stable_sort(_RAIter __begin, _RAIter __end,
1746  __gnu_parallel::sequential_tag)
1747  { _GLIBCXX_STD_A::stable_sort(__begin, __end); }
1748 
1749  // Sequential fallback
1750  template<typename _RAIter, typename _Compare>
1751  inline void
1752  stable_sort(_RAIter __begin, _RAIter __end,
1753  _Compare __comp, __gnu_parallel::sequential_tag)
1754  { _GLIBCXX_STD_A::stable_sort<_RAIter, _Compare>(__begin, __end, __comp); }
1755 
1756  // Public interface
1757  template<typename _RAIter, typename _Compare,
1758  typename _Parallelism>
1759  void
1760  stable_sort(_RAIter __begin, _RAIter __end,
1761  _Compare __comp, _Parallelism __parallelism)
1762  {
1763  typedef iterator_traits<_RAIter> _TraitsType;
1764  typedef typename _TraitsType::value_type _ValueType;
1765 
1766  if (__begin != __end)
1767  {
1768  if (_GLIBCXX_PARALLEL_CONDITION(
1769  static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin) >=
1770  __gnu_parallel::_Settings::get().sort_minimal_n))
1771  __gnu_parallel::__parallel_sort<true>(__begin, __end,
1772  __comp, __parallelism);
1773  else
1774  stable_sort(__begin, __end, __comp,
1775  __gnu_parallel::sequential_tag());
1776  }
1777  }
1778 
1779  // Public interface, insert default comparator
1780  template<typename _RAIter>
1781  inline void
1782  stable_sort(_RAIter __begin, _RAIter __end)
1783  {
1784  typedef typename iterator_traits<_RAIter>::value_type _ValueType;
1785  stable_sort(__begin, __end, std::less<_ValueType>(),
1786  __gnu_parallel::default_parallel_tag());
1787  }
1788 
1789  // Public interface, insert default comparator
1790  template<typename _RAIter>
1791  inline void
1792  stable_sort(_RAIter __begin, _RAIter __end,
1793  __gnu_parallel::default_parallel_tag __parallelism)
1794  {
1795  typedef typename iterator_traits<_RAIter>::value_type _ValueType;
1796  stable_sort(__begin, __end, std::less<_ValueType>(), __parallelism);
1797  }
1798 
1799  // Public interface, insert default comparator
1800  template<typename _RAIter>
1801  inline void
1802  stable_sort(_RAIter __begin, _RAIter __end,
1803  __gnu_parallel::parallel_tag __parallelism)
1804  {
1805  typedef typename iterator_traits<_RAIter>::value_type _ValueType;
1806  stable_sort(__begin, __end, std::less<_ValueType>(), __parallelism);
1807  }
1808 
1809  // Public interface, insert default comparator
1810  template<typename _RAIter>
1811  inline void
1812  stable_sort(_RAIter __begin, _RAIter __end,
1813  __gnu_parallel::multiway_mergesort_tag __parallelism)
1814  {
1815  typedef typename iterator_traits<_RAIter>::value_type _ValueType;
1816  stable_sort(__begin, __end, std::less<_ValueType>(), __parallelism);
1817  }
1818 
1819  // Public interface, insert default comparator
1820  template<typename _RAIter>
1821  inline void
1822  stable_sort(_RAIter __begin, _RAIter __end,
1823  __gnu_parallel::quicksort_tag __parallelism)
1824  {
1825  typedef typename iterator_traits<_RAIter>::value_type _ValueType;
1826  stable_sort(__begin, __end, std::less<_ValueType>(), __parallelism);
1827  }
1828 
1829  // Public interface, insert default comparator
1830  template<typename _RAIter>
1831  inline void
1832  stable_sort(_RAIter __begin, _RAIter __end,
1833  __gnu_parallel::balanced_quicksort_tag __parallelism)
1834  {
1835  typedef typename iterator_traits<_RAIter>::value_type _ValueType;
1836  stable_sort(__begin, __end, std::less<_ValueType>(), __parallelism);
1837  }
1838 
1839  // Public interface
1840  template<typename _RAIter, typename _Compare>
1841  void
1842  stable_sort(_RAIter __begin, _RAIter __end, _Compare __comp)
1843  {
1844  stable_sort(
1845  __begin, __end, __comp, __gnu_parallel::default_parallel_tag());
1846  }
1847 
1848  // Sequential fallback
1849  template<typename _IIter1, typename _IIter2,
1850  typename _OutputIterator>
1851  inline _OutputIterator
1852  merge(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2,
1853  _IIter2 __end2, _OutputIterator __result,
1854  __gnu_parallel::sequential_tag)
1855  { return _GLIBCXX_STD_A::merge(
1856  __begin1, __end1, __begin2, __end2, __result); }
1857 
1858  // Sequential fallback
1859  template<typename _IIter1, typename _IIter2,
1860  typename _OutputIterator, typename _Compare>
1861  inline _OutputIterator
1862  merge(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2,
1863  _IIter2 __end2, _OutputIterator __result, _Compare __comp,
1864  __gnu_parallel::sequential_tag)
1865  { return _GLIBCXX_STD_A::merge(
1866  __begin1, __end1, __begin2, __end2, __result, __comp); }
1867 
1868  // Sequential fallback for input iterator case
1869  template<typename _IIter1, typename _IIter2, typename _OutputIterator,
1870  typename _Compare, typename _IteratorTag1,
1871  typename _IteratorTag2, typename _IteratorTag3>
1872  inline _OutputIterator
1873  __merge_switch(_IIter1 __begin1, _IIter1 __end1,
1874  _IIter2 __begin2, _IIter2 __end2,
1875  _OutputIterator __result, _Compare __comp,
1876  _IteratorTag1, _IteratorTag2, _IteratorTag3)
1877  { return _GLIBCXX_STD_A::merge(__begin1, __end1, __begin2, __end2,
1878  __result, __comp); }
1879 
1880  // Parallel algorithm for random access iterators
1881  template<typename _IIter1, typename _IIter2,
1882  typename _OutputIterator, typename _Compare>
1883  _OutputIterator
1884  __merge_switch(_IIter1 __begin1, _IIter1 __end1,
1885  _IIter2 __begin2, _IIter2 __end2,
1886  _OutputIterator __result, _Compare __comp,
1887  random_access_iterator_tag, random_access_iterator_tag,
1888  random_access_iterator_tag)
1889  {
1890  if (_GLIBCXX_PARALLEL_CONDITION(
1891  (static_cast<__gnu_parallel::_SequenceIndex>(__end1 - __begin1)
1892  >= __gnu_parallel::_Settings::get().merge_minimal_n
1893  || static_cast<__gnu_parallel::_SequenceIndex>(__end2 - __begin2)
1894  >= __gnu_parallel::_Settings::get().merge_minimal_n)))
1895  return __gnu_parallel::__parallel_merge_advance(
1896  __begin1, __end1, __begin2, __end2, __result,
1897  (__end1 - __begin1) + (__end2 - __begin2), __comp);
1898  else
1899  return __gnu_parallel::__merge_advance(
1900  __begin1, __end1, __begin2, __end2, __result,
1901  (__end1 - __begin1) + (__end2 - __begin2), __comp);
1902  }
1903 
1904  // Public interface
1905  template<typename _IIter1, typename _IIter2,
1906  typename _OutputIterator, typename _Compare>
1907  inline _OutputIterator
1908  merge(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2,
1909  _IIter2 __end2, _OutputIterator __result, _Compare __comp)
1910  {
1911  return __merge_switch(
1912  __begin1, __end1, __begin2, __end2, __result, __comp,
1913  std::__iterator_category(__begin1),
1914  std::__iterator_category(__begin2),
1915  std::__iterator_category(__result));
1916  }
1917 
1918  // Public interface, insert default comparator
1919  template<typename _IIter1, typename _IIter2,
1920  typename _OutputIterator>
1921  inline _OutputIterator
1922  merge(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2,
1923  _IIter2 __end2, _OutputIterator __result)
1924  {
1925  typedef typename std::iterator_traits<_IIter1>::value_type _ValueType1;
1926  typedef typename std::iterator_traits<_IIter2>::value_type _ValueType2;
1927 
1928  return __gnu_parallel::merge(__begin1, __end1, __begin2, __end2,
1929  __result, __gnu_parallel::_Less<_ValueType1, _ValueType2>());
1930  }
1931 
1932  // Sequential fallback
1933  template<typename _RAIter>
1934  inline void
1935  nth_element(_RAIter __begin, _RAIter __nth,
1936  _RAIter __end, __gnu_parallel::sequential_tag)
1937  { return _GLIBCXX_STD_A::nth_element(__begin, __nth, __end); }
1938 
1939  // Sequential fallback
1940  template<typename _RAIter, typename _Compare>
1941  inline void
1942  nth_element(_RAIter __begin, _RAIter __nth,
1943  _RAIter __end, _Compare __comp,
1944  __gnu_parallel::sequential_tag)
1945  { return _GLIBCXX_STD_A::nth_element(__begin, __nth, __end, __comp); }
1946 
1947  // Public interface
1948  template<typename _RAIter, typename _Compare>
1949  inline void
1950  nth_element(_RAIter __begin, _RAIter __nth,
1951  _RAIter __end, _Compare __comp)
1952  {
1953  if (_GLIBCXX_PARALLEL_CONDITION(
1954  static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
1955  >= __gnu_parallel::_Settings::get().nth_element_minimal_n))
1956  __gnu_parallel::__parallel_nth_element(__begin, __nth, __end, __comp);
1957  else
1958  nth_element(__begin, __nth, __end, __comp,
1959  __gnu_parallel::sequential_tag());
1960  }
1961 
1962  // Public interface, insert default comparator
1963  template<typename _RAIter>
1964  inline void
1965  nth_element(_RAIter __begin, _RAIter __nth,
1966  _RAIter __end)
1967  {
1968  typedef typename iterator_traits<_RAIter>::value_type _ValueType;
1969  __gnu_parallel::nth_element(__begin, __nth, __end,
1970  std::less<_ValueType>());
1971  }
1972 
1973  // Sequential fallback
1974  template<typename _RAIter, typename _Compare>
1975  inline void
1976  partial_sort(_RAIter __begin, _RAIter __middle,
1977  _RAIter __end, _Compare __comp,
1978  __gnu_parallel::sequential_tag)
1979  { _GLIBCXX_STD_A::partial_sort(__begin, __middle, __end, __comp); }
1980 
1981  // Sequential fallback
1982  template<typename _RAIter>
1983  inline void
1984  partial_sort(_RAIter __begin, _RAIter __middle,
1985  _RAIter __end, __gnu_parallel::sequential_tag)
1986  { _GLIBCXX_STD_A::partial_sort(__begin, __middle, __end); }
1987 
1988  // Public interface, parallel algorithm for random access iterators
1989  template<typename _RAIter, typename _Compare>
1990  void
1991  partial_sort(_RAIter __begin, _RAIter __middle,
1992  _RAIter __end, _Compare __comp)
1993  {
1994  if (_GLIBCXX_PARALLEL_CONDITION(
1995  static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
1996  >= __gnu_parallel::_Settings::get().partial_sort_minimal_n))
1997  __gnu_parallel::
1998  __parallel_partial_sort(__begin, __middle, __end, __comp);
1999  else
2000  partial_sort(__begin, __middle, __end, __comp,
2001  __gnu_parallel::sequential_tag());
2002  }
2003 
2004  // Public interface, insert default comparator
2005  template<typename _RAIter>
2006  inline void
2007  partial_sort(_RAIter __begin, _RAIter __middle,
2008  _RAIter __end)
2009  {
2010  typedef iterator_traits<_RAIter> _TraitsType;
2011  typedef typename _TraitsType::value_type _ValueType;
2012  __gnu_parallel::partial_sort(__begin, __middle, __end,
2013  std::less<_ValueType>());
2014  }
2015 
2016  // Sequential fallback
2017  template<typename _FIterator>
2018  inline _FIterator
2019  max_element(_FIterator __begin, _FIterator __end,
2020  __gnu_parallel::sequential_tag)
2021  { return _GLIBCXX_STD_A::max_element(__begin, __end); }
2022 
2023  // Sequential fallback
2024  template<typename _FIterator, typename _Compare>
2025  inline _FIterator
2026  max_element(_FIterator __begin, _FIterator __end, _Compare __comp,
2027  __gnu_parallel::sequential_tag)
2028  { return _GLIBCXX_STD_A::max_element(__begin, __end, __comp); }
2029 
2030  // Sequential fallback for input iterator case
2031  template<typename _FIterator, typename _Compare, typename _IteratorTag>
2032  inline _FIterator
2033  __max_element_switch(_FIterator __begin, _FIterator __end,
2034  _Compare __comp, _IteratorTag)
2035  { return max_element(__begin, __end, __comp,
2036  __gnu_parallel::sequential_tag()); }
2037 
2038  // Parallel algorithm for random access iterators
2039  template<typename _RAIter, typename _Compare>
2040  _RAIter
2041  __max_element_switch(_RAIter __begin, _RAIter __end,
2042  _Compare __comp, random_access_iterator_tag,
2043  __gnu_parallel::_Parallelism __parallelism_tag)
2044  {
2045  if (_GLIBCXX_PARALLEL_CONDITION(
2046  static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
2047  >= __gnu_parallel::_Settings::get().max_element_minimal_n
2048  && __gnu_parallel::__is_parallel(__parallelism_tag)))
2049  {
2050  _RAIter __res(__begin);
2051  __gnu_parallel::__identity_selector<_RAIter>
2052  __functionality;
2053  __gnu_parallel::
2054  __for_each_template_random_access(
2055  __begin, __end, __gnu_parallel::_Nothing(), __functionality,
2056  __gnu_parallel::__max_element_reduct<_Compare, _RAIter>(__comp),
2057  __res, __res, -1, __parallelism_tag);
2058  return __res;
2059  }
2060  else
2061  return max_element(__begin, __end, __comp,
2062  __gnu_parallel::sequential_tag());
2063  }
2064 
2065  // Public interface, insert default comparator
2066  template<typename _FIterator>
2067  inline _FIterator
2068  max_element(_FIterator __begin, _FIterator __end,
2069  __gnu_parallel::_Parallelism __parallelism_tag)
2070  {
2071  typedef typename iterator_traits<_FIterator>::value_type _ValueType;
2072  return max_element(__begin, __end, std::less<_ValueType>(),
2073  __parallelism_tag);
2074  }
2075 
2076  template<typename _FIterator>
2077  inline _FIterator
2078  max_element(_FIterator __begin, _FIterator __end)
2079  {
2080  typedef typename iterator_traits<_FIterator>::value_type _ValueType;
2081  return __gnu_parallel::max_element(__begin, __end,
2082  std::less<_ValueType>());
2083  }
2084 
2085  // Public interface
2086  template<typename _FIterator, typename _Compare>
2087  inline _FIterator
2088  max_element(_FIterator __begin, _FIterator __end, _Compare __comp,
2089  __gnu_parallel::_Parallelism __parallelism_tag)
2090  {
2091  return __max_element_switch(__begin, __end, __comp,
2092  std::__iterator_category(__begin),
2093  __parallelism_tag);
2094  }
2095 
2096  template<typename _FIterator, typename _Compare>
2097  inline _FIterator
2098  max_element(_FIterator __begin, _FIterator __end, _Compare __comp)
2099  {
2100  return __max_element_switch(__begin, __end, __comp,
2101  std::__iterator_category(__begin));
2102  }
2103 
2104 
2105  // Sequential fallback
2106  template<typename _FIterator>
2107  inline _FIterator
2108  min_element(_FIterator __begin, _FIterator __end,
2109  __gnu_parallel::sequential_tag)
2110  { return _GLIBCXX_STD_A::min_element(__begin, __end); }
2111 
2112  // Sequential fallback
2113  template<typename _FIterator, typename _Compare>
2114  inline _FIterator
2115  min_element(_FIterator __begin, _FIterator __end, _Compare __comp,
2116  __gnu_parallel::sequential_tag)
2117  { return _GLIBCXX_STD_A::min_element(__begin, __end, __comp); }
2118 
2119  // Sequential fallback for input iterator case
2120  template<typename _FIterator, typename _Compare, typename _IteratorTag>
2121  inline _FIterator
2122  __min_element_switch(_FIterator __begin, _FIterator __end,
2123  _Compare __comp, _IteratorTag)
2124  { return min_element(__begin, __end, __comp,
2125  __gnu_parallel::sequential_tag()); }
2126 
2127  // Parallel algorithm for random access iterators
2128  template<typename _RAIter, typename _Compare>
2129  _RAIter
2130  __min_element_switch(_RAIter __begin, _RAIter __end,
2131  _Compare __comp, random_access_iterator_tag,
2132  __gnu_parallel::_Parallelism __parallelism_tag)
2133  {
2134  if (_GLIBCXX_PARALLEL_CONDITION(
2135  static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
2136  >= __gnu_parallel::_Settings::get().min_element_minimal_n
2137  && __gnu_parallel::__is_parallel(__parallelism_tag)))
2138  {
2139  _RAIter __res(__begin);
2140  __gnu_parallel::__identity_selector<_RAIter>
2141  __functionality;
2142  __gnu_parallel::
2143  __for_each_template_random_access(
2144  __begin, __end, __gnu_parallel::_Nothing(), __functionality,
2145  __gnu_parallel::__min_element_reduct<_Compare, _RAIter>(__comp),
2146  __res, __res, -1, __parallelism_tag);
2147  return __res;
2148  }
2149  else
2150  return min_element(__begin, __end, __comp,
2151  __gnu_parallel::sequential_tag());
2152  }
2153 
2154  // Public interface, insert default comparator
2155  template<typename _FIterator>
2156  inline _FIterator
2157  min_element(_FIterator __begin, _FIterator __end,
2158  __gnu_parallel::_Parallelism __parallelism_tag)
2159  {
2160  typedef typename iterator_traits<_FIterator>::value_type _ValueType;
2161  return min_element(__begin, __end, std::less<_ValueType>(),
2162  __parallelism_tag);
2163  }
2164 
2165  template<typename _FIterator>
2166  inline _FIterator
2167  min_element(_FIterator __begin, _FIterator __end)
2168  {
2169  typedef typename iterator_traits<_FIterator>::value_type _ValueType;
2170  return __gnu_parallel::min_element(__begin, __end,
2171  std::less<_ValueType>());
2172  }
2173 
2174  // Public interface
2175  template<typename _FIterator, typename _Compare>
2176  inline _FIterator
2177  min_element(_FIterator __begin, _FIterator __end, _Compare __comp,
2178  __gnu_parallel::_Parallelism __parallelism_tag)
2179  {
2180  return __min_element_switch(__begin, __end, __comp,
2181  std::__iterator_category(__begin),
2182  __parallelism_tag);
2183  }
2184 
2185  template<typename _FIterator, typename _Compare>
2186  inline _FIterator
2187  min_element(_FIterator __begin, _FIterator __end, _Compare __comp)
2188  {
2189  return __min_element_switch(__begin, __end, __comp,
2190  std::__iterator_category(__begin));
2191  }
2192 } // end namespace
2193 } // end namespace
2194 
2195 #endif /* _GLIBCXX_PARALLEL_ALGO_H */
__gnu_parallel::sequential_tag
Forces sequential execution at compile time.
Definition: tags.h:42
__gnu_parallel::__max_element_reduct
Reduction for finding the maximum element, using a comparator.
Definition: for_each_selectors.h:321
__gnu_parallel::_PseudoSequence::begin
iterator begin() const
Begin iterator.
Definition: parallel/base.h:376
__gnu_parallel::quicksort_tag
Forces parallel sorting using unbalanced quicksort at compile time.
Definition: tags.h:155
__gnu_parallel::__parallel_merge_advance
_RAIter3 __parallel_merge_advance(_RAIter1 &__begin1, _RAIter1 __end1, _RAIter2 &__begin2, _RAIter2 __end2, _RAIter3 __target, typename std::iterator_traits< _RAIter1 >::difference_type __max_length, _Compare __comp)
Merge routine fallback to sequential in case the iterators of the two input sequences are of differen...
Definition: merge.h:195
std::less
One of the comparison functors.
Definition: stl_function.h:340
__gnu_parallel::_Nothing
Functor doing nothing.
Definition: for_each_selectors.h:288
std::equal_to
One of the comparison functors.
Definition: stl_function.h:331
__gnu_parallel::_EqualTo
Similar to std::equal_to, but allows two different types.
Definition: parallel/base.h:244
__gnu_parallel::__search_template
__RAIter1 __search_template(__RAIter1 __begin1, __RAIter1 __end1, __RAIter2 __begin2, __RAIter2 __end2, _Pred __pred)
Parallel std::search.
Definition: search.h:81
find_selectors.h
_Function objects representing different tasks to be plugged into the parallel find algorithm....
__gnu_parallel::__parallel_nth_element
void __parallel_nth_element(_RAIter __begin, _RAIter __nth, _RAIter __end, _Compare __comp)
Parallel implementation of std::nth_element().
Definition: partition.h:332
__gnu_parallel::__sequential_random_shuffle
void __sequential_random_shuffle(_RAIter __begin, _RAIter __end, _RandomNumberGenerator &__rng)
Sequential cache-efficient random shuffle.
Definition: random_shuffle.h:410
search.h
Parallel implementation base for std::search() and std::search_n(). This file is a GNU parallel exten...
__gnu_parallel::__adjacent_find_selector
Test predicate on two adjacent elements.
Definition: find_selectors.h:80
__gnu_parallel::default_parallel_tag
Recommends parallel execution using the default parallel algorithm.
Definition: tags.h:79
__gnu_parallel::_IteratorPair
A pair of iterators. The usual iterator operations are applied to both child iterators.
Definition: iterator.h:45
__gnu_parallel::_PseudoSequence
Sequence that conceptually consists of multiple copies of the same element. The copies are not stored...
Definition: parallel/base.h:359
__gnu_parallel::__min_element_reduct
Reduction for finding the maximum element, using a comparator.
Definition: for_each_selectors.h:307
__gnu_parallel::__generic_for_each_selector::_M_finish_iterator
_It _M_finish_iterator
_Iterator on last element processed; needed for some algorithms (e. g. std::transform()).
Definition: for_each_selectors.h:47
set_operations.h
Parallel implementations of set operations for random-access iterators. This file is a GNU parallel e...
__gnu_parallel::__transform2_selector
std::transform() __selector, two input sequences variant.
Definition: for_each_selectors.h:116
std::__parallel::_CRandNumber
Functor wrapper for std::rand().
Definition: algo.h:1529
__gnu_parallel::multiway_mergesort_tag
Forces parallel sorting using multiway mergesort at compile time.
Definition: tags.h:128
__gnu_parallel::__parallel_partition
std::iterator_traits< _RAIter >::difference_type __parallel_partition(_RAIter __begin, _RAIter __end, _Predicate __pred, _ThreadIndex __num_threads)
Parallel implementation of std::partition.
Definition: partition.h:56
__gnu_parallel::__find_first_of_selector
Test predicate on several elements.
Definition: find_selectors.h:153
__gnu_parallel::__merge_advance
_OutputIterator __merge_advance(_RAIter1 &__begin1, _RAIter1 __end1, _RAIter2 &__begin2, _RAIter2 __end2, _OutputIterator __target, _DifferenceTp __max_length, _Compare __comp)
Merge routine being able to merge only the __max_length smallest elements.
Definition: merge.h:171
__gnu_parallel::__find_if_selector
Test predicate on a single element, used for std::find() and std::find_if ().
Definition: find_selectors.h:50
__gnu_parallel::parallel_tag
Recommends parallel execution at compile time, optionally using a user-specified number of threads.
Definition: tags.h:46
__gnu_parallel::__for_each_template_random_access
_UserOp __for_each_template_random_access(_IIter __begin, _IIter __end, _UserOp __user_op, _Functionality &__functionality, _Red __reduction, _Result __reduction_start, _Result &__output, typename std::iterator_traits< _IIter >::difference_type __bound, _Parallelism __parallelism_tag)
Chose the desired algorithm by evaluating __parallelism_tag.
Definition: for_each.h:61
_GLIBCXX_PARALLEL_CONDITION
#define _GLIBCXX_PARALLEL_CONDITION(__c)
Determine at compile(?)-time if the parallel variant of an algorithm should be called.
Definition: settings.h:95
__gnu_parallel::__binder2nd
Similar to std::binder2nd, but giving the argument types explicitly.
Definition: parallel/base.h:220
for_each.h
Main interface for embarrassingly parallel functions.
__gnu_parallel::multiway_mergesort_sampling_tag
Forces parallel sorting using multiway mergesort with splitting by sampling at compile time.
Definition: tags.h:146
__gnu_parallel::__transform1_selector
std::transform() __selector, one input sequence variant.
Definition: for_each_selectors.h:100
partition.h
Parallel implementation of std::partition(), std::nth_element(), and std::partial_sort()....
for_each_selectors.h
Functors representing different tasks to be plugged into the generic parallelization methods for emba...
__gnu_parallel::_PseudoSequence::end
iterator end() const
End iterator.
Definition: parallel/base.h:381
__gnu_parallel::balanced_quicksort_tag
Forces parallel sorting using balanced quicksort at compile time.
Definition: tags.h:164
find.h
Parallel implementation base for std::find(), std::equal() and related functions. This file is a GNU ...
__gnu_parallel::multiway_mergesort_exact_tag
Forces parallel sorting using multiway mergesort with exact splitting at compile time.
Definition: tags.h:137
omp_loop.h
Parallelization of embarrassingly parallel execution by means of an OpenMP for loop....
std
ISO C++ entities toplevel namespace is std.
base.h
Sequential helper functions. This file is a GNU parallel extension to the Standard C++ Library.
__gnu_parallel
GNU parallel code for public use.
Definition: balanced_quicksort.h:61
omp_loop_static.h
Parallelization of embarrassingly parallel execution by means of an OpenMP for loop with static sched...
std::__iterator_category
constexpr iterator_traits< _Iter >::iterator_category __iterator_category(const _Iter &)
Definition: stl_iterator_base_types.h:205
par_loop.h
Parallelization of embarrassingly parallel execution by means of equal splitting. This file is a GNU ...
__gnu_parallel::__parallel_random_shuffle
void __parallel_random_shuffle(_RAIter __begin, _RAIter __end, _RandomNumberGenerator __rng=_RandomNumber())
Parallel random public call.
Definition: random_shuffle.h:522
__gnu_parallel::__parallel_partial_sort
void __parallel_partial_sort(_RAIter __begin, _RAIter __middle, _RAIter __end, _Compare __comp)
Parallel implementation of std::partial_sort().
Definition: partition.h:422
merge.h
Parallel implementation of std::merge(). This file is a GNU parallel extension to the Standard C++ Li...
__gnu_parallel::__find_template
std::pair< _RAIter1, _RAIter2 > __find_template(_RAIter1 __begin1, _RAIter1 __end1, _RAIter2 __begin2, _Pred __pred, _Selector __selector)
Parallel std::find, switch for different algorithms.
Definition: find.h:60
std::plus
One of the math functors.
Definition: stl_function.h:147
std::random_access_iterator_tag
Random-access iterators support a superset of bidirectional iterator operations.
Definition: stl_iterator_base_types.h:103
unique_copy.h
Parallel implementations of std::unique_copy(). This file is a GNU parallel extension to the Standard...
__gnu_parallel::_Parallelism
_Parallelism
Run-time equivalents for the compile-time tags.
Definition: types.h:44
workstealing.h
Parallelization of embarrassingly parallel execution by means of work-stealing.
sort.h
Parallel sorting algorithm switch. This file is a GNU parallel extension to the Standard C++ Library.
__gnu_parallel::_Settings::get
static const _Settings & get()
Get the global settings.
__gnu_parallel::__parallel_unique_copy
_OutputIterator __parallel_unique_copy(_IIter __first, _IIter __last, _OutputIterator __result, _BinaryPredicate __binary_pred)
Parallel std::unique_copy(), w/__o explicit equality predicate.
Definition: unique_copy.h:50
random_shuffle.h
Parallel implementation of std::random_shuffle(). This file is a GNU parallel extension to the Standa...
__gnu_parallel::_DummyReduct
Reduction function doing nothing.
Definition: for_each_selectors.h:298
__gnu_parallel::__identity_selector
Selector that just returns the passed iterator.
Definition: for_each_selectors.h:253
__gnu_parallel::_Less
Similar to std::less, but allows two different types.
Definition: parallel/base.h:252
__gnu_parallel::_SequenceIndex
uint64_t _SequenceIndex
Unsigned integer to index __elements. The total number of elements for each algorithm must fit into t...
Definition: types.h:117
iterator.h
Helper iterator classes for the std::transform() functions. This file is a GNU parallel extension to ...
__gnu_parallel::_IteratorTriple
A triple of iterators. The usual iterator operations are applied to all three child iterators.
Definition: iterator.h:120