libstdc++
algo.h
Go to the documentation of this file.
1 // -*- C++ -*-
2 
3 // Copyright (C) 2007-2020 Free Software Foundation, Inc.
4 //
5 // This file is part of the GNU ISO C++ Library. This library is free
6 // software; you can redistribute it and/or modify it under the terms
7 // of the GNU General Public License as published by the Free Software
8 // Foundation; either version 3, or (at your option) any later
9 // version.
10 
11 // This library is distributed in the hope that it will be useful, but
12 // WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 // General Public License for more details.
15 
16 // Under Section 7 of GPL version 3, you are granted additional
17 // permissions described in the GCC Runtime Library Exception, version
18 // 3.1, as published by the Free Software Foundation.
19 
20 // You should have received a copy of the GNU General Public License and
21 // a copy of the GCC Runtime Library Exception along with this program;
22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23 // <http://www.gnu.org/licenses/>.
24 
25 /** @file parallel/algo.h
26  * @brief Parallel STL function calls corresponding to the stl_algo.h header.
27  *
28  * The functions defined here mainly do case switches and
29  * call the actual parallelized versions in other files.
30  * Inlining policy: Functions that basically only contain one function call,
31  * are declared inline.
32  * This file is a GNU parallel extension to the Standard C++ Library.
33  */
34 
35 // Written by Johannes Singler and Felix Putze.
36 
37 #ifndef _GLIBCXX_PARALLEL_ALGO_H
38 #define _GLIBCXX_PARALLEL_ALGO_H 1
39 
40 #include <parallel/algorithmfwd.h>
41 #include <bits/stl_algobase.h>
42 #include <bits/stl_algo.h>
43 #include <parallel/iterator.h>
44 #include <parallel/base.h>
45 #include <parallel/sort.h>
46 #include <parallel/workstealing.h>
47 #include <parallel/par_loop.h>
48 #include <parallel/omp_loop.h>
51 #include <parallel/for_each.h>
52 #include <parallel/find.h>
54 #include <parallel/search.h>
56 #include <parallel/partition.h>
57 #include <parallel/merge.h>
58 #include <parallel/unique_copy.h>
60 
61 namespace std _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,
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  {
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;
93 
94  return __gnu_parallel::
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,
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  {
149  const _Tp&>,
150  _ValueType, const _Tp&, bool>
153  __begin, __end, __begin, __comp,
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,
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,
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,
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,
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,
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,
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,
287  }
288 
289  // Sequential fallback
290  template<typename _IIter, typename _OutputIterator>
291  inline _OutputIterator
292  unique_copy(_IIter __begin1, _IIter __end1, _OutputIterator __out,
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,
320  {
322  static_cast<__gnu_parallel::_SequenceIndex>(__last - __begin)
323  > __gnu_parallel::_Settings::get().unique_copy_minimal_n))
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,
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,
397  {
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,
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,
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,
490  {
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,
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,
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,
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,
584  {
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,
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,
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,
676  {
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,
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,
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,
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,
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::
751  __begin, __end - 1, __begin, equal_to<_ValueType>(),
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,
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,
797  __adjacent_find_selector()).first;
798  else
799  return adjacent_find(__begin, __end, __pred,
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>
816  count(_IIter __begin, _IIter __end, const _Tp& __value,
818  { return _GLIBCXX_STD_A::count(__begin, __end, __value); }
819 
820  // Parallel code for random access iterators
821  template<typename _RAIter, typename _Tp>
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;
831 
833  static_cast<_SequenceIndex>(__end - __begin)
834  >= __gnu_parallel::_Settings::get().count_minimal_n
835  && __gnu_parallel::__is_parallel(__parallelism_tag)))
836  {
838  __functionality;
839  _DifferenceType __res = 0;
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,
850  }
851 
852  // Sequential fallback for input iterator case.
853  template<typename _IIter, typename _Tp, typename _IteratorTag>
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>
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>
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>
883  count_if(_IIter __begin, _IIter __end, _Predicate __pred,
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>
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;
898 
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;
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,
918  }
919 
920  // Sequential fallback for input iterator case.
921  template<typename _IIter, typename _Predicate, typename _IteratorTag>
923  __count_if_switch(_IIter __begin, _IIter __end, _Predicate __pred,
924  _IteratorTag)
925  { return count_if(__begin, __end, __pred,
927 
928  // Public interface.
929  template<typename _IIter, typename _Predicate>
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>
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,
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,
962  {
963  typedef typename std::iterator_traits<_RAIter1>::value_type _ValueType1;
964  typedef typename std::iterator_traits<_RAIter2>::value_type _ValueType2;
965 
967  static_cast<__gnu_parallel::_SequenceIndex>(__end1 - __begin1)
968  >= __gnu_parallel::_Settings::get().search_minimal_n))
969  return __gnu_parallel::
971  __begin1, __end1, __begin2, __end2,
973  else
974  return search(__begin1, __end1, __begin2, __end2,
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,
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,
1017  {
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,
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,
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,
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,
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,
1087  {
1089  static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
1090  >= __gnu_parallel::_Settings::get().search_minimal_n))
1091  {
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,
1138  __gnu_parallel::_Parallelism __parallelism_tag)
1139  {
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));
1153  __begin_pair, __end_pair, __unary_op, __functionality,
1155  __dummy, __dummy, -1, __parallelism_tag);
1156  return __functionality._M_finish_iterator;
1157  }
1158  else
1159  return transform(__begin, __end, __result, __unary_op,
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,
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,
1219  __gnu_parallel::_Parallelism __parallelism_tag)
1220  {
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));
1235  __for_each_template_random_access(__begin_triple, __end_triple,
1236  __binary_op, __functionality,
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,
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,
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,
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,
1311  __gnu_parallel::_Parallelism __parallelism_tag)
1312  {
1313  // XXX parallel version is where?
1314  replace(__begin, __end, __old_value, __new_value,
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,
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,
1362  __gnu_parallel::_Parallelism __parallelism_tag)
1363  {
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);
1375  __begin, __end, __pred, __functionality,
1377  true, __dummy, -1, __parallelism_tag);
1378  }
1379  else
1380  replace_if(__begin, __end, __pred, __new_value,
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,
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  {
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;
1433  __functionality;
1436  __begin, __end, __gen, __functionality,
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,
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,
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,
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,
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,
1524  { _GLIBCXX_STD_A::random_shuffle(__begin, __end, __rand); }
1525 
1526 
1527  /** @brief Functor wrapper for std::rand(). */
1528  template<typename _MustBeInt = int>
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;
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,
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  {
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,
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,
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,
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  {
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>(),
1658  }
1659 
1660  // Public interface, insert default comparator
1661  template<typename _RAIter>
1662  inline void
1663  sort(_RAIter __begin, _RAIter __end,
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,
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,
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,
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,
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,
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  {
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,
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>(),
1787  }
1788 
1789  // Public interface, insert default comparator
1790  template<typename _RAIter>
1791  inline void
1792  stable_sort(_RAIter __begin, _RAIter __end,
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,
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,
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,
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,
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  {
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)))
1896  __begin1, __end1, __begin2, __end2, __result,
1897  (__end1 - __begin1) + (__end2 - __begin2), __comp);
1898  else
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,
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,
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  {
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,
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,
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,
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  {
1995  static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
1996  >= __gnu_parallel::_Settings::get().partial_sort_minimal_n))
1998  __parallel_partial_sort(__begin, __middle, __end, __comp);
1999  else
2000  partial_sort(__begin, __middle, __end, __comp,
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,
2014  }
2015 
2016  // Sequential fallback
2017  template<typename _FIterator>
2018  inline _FIterator
2019  max_element(_FIterator __begin, _FIterator __end,
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,
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,
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  {
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);
2052  __functionality;
2055  __begin, __end, __gnu_parallel::_Nothing(), __functionality,
2057  __res, __res, -1, __parallelism_tag);
2058  return __res;
2059  }
2060  else
2061  return max_element(__begin, __end, __comp,
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,
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,
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,
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,
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  {
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);
2141  __functionality;
2144  __begin, __end, __gnu_parallel::_Nothing(), __functionality,
2146  __res, __res, -1, __parallelism_tag);
2147  return __res;
2148  }
2149  else
2150  return min_element(__begin, __end, __comp,
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,
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 
2193 #if __cplusplus >= 201703L
2194  using _GLIBCXX_STD_A::for_each_n;
2195  using _GLIBCXX_STD_A::sample;
2196 #endif
2197 } // end namespace
2198 } // end namespace
2199 
2200 #endif /* _GLIBCXX_PARALLEL_ALGO_H */
Sequential helper functions. This file is a GNU parallel extension to the Standard C++ Library.
Parallel implementation base for std::find(), std::equal() and related functions. This file is a GNU ...
_Function objects representing different tasks to be plugged into the parallel find algorithm....
Main interface for embarrassingly parallel functions.
Functors representing different tasks to be plugged into the generic parallelization methods for emba...
Helper iterator classes for the std::transform() functions. This file is a GNU parallel extension to ...
Parallel implementation of std::merge(). This file is a GNU parallel extension to the Standard C++ Li...
Parallelization of embarrassingly parallel execution by means of an OpenMP for loop....
Parallelization of embarrassingly parallel execution by means of an OpenMP for loop with static sched...
Parallelization of embarrassingly parallel execution by means of equal splitting. This file is a GNU ...
Parallel implementation of std::partition(), std::nth_element(), and std::partial_sort()....
Parallel implementation of std::random_shuffle(). This file is a GNU parallel extension to the Standa...
Parallel implementation base for std::search() and std::search_n(). This file is a GNU parallel exten...
Parallel implementations of set operations for random-access iterators. This file is a GNU parallel e...
#define _GLIBCXX_PARALLEL_CONDITION(__c)
Determine at compile(?)-time if the parallel variant of an algorithm should be called.
Definition: settings.h:94
Parallel sorting algorithm switch. This file is a GNU parallel extension to the Standard C++ Library.
Parallel implementations of std::unique_copy(). This file is a GNU parallel extension to the Standard...
Parallelization of embarrassingly parallel execution by means of work-stealing.
constexpr iterator_traits< _Iter >::iterator_category __iterator_category(const _Iter &)
ISO C++ entities toplevel namespace is std.
GNU parallel code for public use.
_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
_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
void __parallel_nth_element(_RAIter __begin, _RAIter __nth, _RAIter __end, _Compare __comp)
Parallel implementation of std::nth_element().
Definition: partition.h:332
_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
uint64_t _SequenceIndex
Unsigned integer to index __elements. The total number of elements for each algorithm must fit into t...
Definition: types.h:117
void __parallel_random_shuffle(_RAIter __begin, _RAIter __end, _RandomNumberGenerator __rng=_RandomNumber())
Parallel random public call.
_Parallelism
Run-time equivalents for the compile-time tags.
Definition: types.h:45
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::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
void __sequential_random_shuffle(_RAIter __begin, _RAIter __end, _RandomNumberGenerator &__rng)
Sequential cache-efficient random shuffle.
void __parallel_partial_sort(_RAIter __begin, _RAIter __middle, _RAIter __end, _Compare __comp)
Parallel implementation of std::partial_sort().
Definition: partition.h:422
_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
__RAIter1 __search_template(__RAIter1 __begin1, __RAIter1 __end1, __RAIter2 __begin2, __RAIter2 __end2, _Pred __pred)
Parallel std::search.
Definition: search.h:81
Traits class for iterators.
One of the math functors.
Definition: stl_function.h:168
One of the comparison functors.
Definition: stl_function.h:352
One of the comparison functors.
Definition: stl_function.h:382
Random-access iterators support a superset of bidirectional iterator operations.
Functor wrapper for std::rand().
Definition: algo.h:1530
Similar to std::binder2nd, but giving the argument types explicitly.
Definition: base.h:222
Similar to std::equal_to, but allows two different types.
Definition: base.h:245
Similar to std::less, but allows two different types.
Definition: base.h:253
Sequence that conceptually consists of multiple copies of the same element. The copies are not stored...
Definition: base.h:360
iterator begin() const
Begin iterator.
Definition: base.h:376
iterator end() const
End iterator.
Definition: base.h:381
Test predicate on a single element, used for std::find() and std::find_if ().
Test predicate on two adjacent elements.
Test predicate on several elements.
_It _M_finish_iterator
_Iterator on last element processed; needed for some algorithms (e. g. std::transform()).
std::transform() __selector, one input sequence variant.
std::transform() __selector, two input sequences variant.
Selector that just returns the passed iterator.
Functor doing nothing.
Reduction function doing nothing.
Reduction for finding the maximum element, using a comparator.
Reduction for finding the maximum element, using a comparator.
A pair of iterators. The usual iterator operations are applied to both child iterators.
Definition: iterator.h:46
A triple of iterators. The usual iterator operations are applied to all three child iterators.
Definition: iterator.h:121
static const _Settings & get()
Get the global settings.
Forces sequential execution at compile time.
Definition: tags.h:42
Recommends parallel execution at compile time, optionally using a user-specified number of threads.
Definition: tags.h:47
Recommends parallel execution using the default parallel algorithm.
Definition: tags.h:80
Forces parallel sorting using multiway mergesort at compile time.
Definition: tags.h:129
Forces parallel sorting using multiway mergesort with exact splitting at compile time.
Definition: tags.h:138
Forces parallel sorting using multiway mergesort with splitting by sampling at compile time.
Definition: tags.h:147
Forces parallel sorting using unbalanced quicksort at compile time.
Definition: tags.h:156
Forces parallel sorting using balanced quicksort at compile time.
Definition: tags.h:165