libstdc++
algo.h
Go to the documentation of this file.
1 // -*- C++ -*-
2 
3 // Copyright (C) 2007-2022 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 #if __cplusplus >= 201703L
1053  /** @brief Search a sequence using a Searcher object.
1054  *
1055  * @param __first A forward iterator.
1056  * @param __last A forward iterator.
1057  * @param __searcher A callable object.
1058  * @return @p __searcher(__first,__last).first
1059  */
1060  template<typename _ForwardIterator, typename _Searcher>
1061  inline _ForwardIterator
1062  search(_ForwardIterator __first, _ForwardIterator __last,
1063  const _Searcher& __searcher)
1064  { return __searcher(__first, __last).first; }
1065 #endif
1066 
1067  // Sequential fallback
1068  template<typename _FIterator, typename _Integer, typename _Tp>
1069  inline _FIterator
1070  search_n(_FIterator __begin, _FIterator __end, _Integer __count,
1071  const _Tp& __val, __gnu_parallel::sequential_tag)
1072  { return _GLIBCXX_STD_A::search_n(__begin, __end, __count, __val); }
1073 
1074  // Sequential fallback
1075  template<typename _FIterator, typename _Integer, typename _Tp,
1076  typename _BinaryPredicate>
1077  inline _FIterator
1078  search_n(_FIterator __begin, _FIterator __end, _Integer __count,
1079  const _Tp& __val, _BinaryPredicate __binary_pred,
1080  __gnu_parallel::sequential_tag)
1081  { return _GLIBCXX_STD_A::search_n(
1082  __begin, __end, __count, __val, __binary_pred); }
1083 
1084  // Public interface.
1085  template<typename _FIterator, typename _Integer, typename _Tp>
1086  inline _FIterator
1087  search_n(_FIterator __begin, _FIterator __end, _Integer __count,
1088  const _Tp& __val)
1089  {
1090  typedef typename iterator_traits<_FIterator>::value_type _ValueType;
1091  return __gnu_parallel::search_n(__begin, __end, __count, __val,
1092  __gnu_parallel::_EqualTo<_ValueType, _Tp>());
1093  }
1094 
1095  // Parallel algorithm for random access iterators.
1096  template<typename _RAIter, typename _Integer,
1097  typename _Tp, typename _BinaryPredicate>
1098  _RAIter
1099  __search_n_switch(_RAIter __begin, _RAIter __end, _Integer __count,
1100  const _Tp& __val, _BinaryPredicate __binary_pred,
1101  random_access_iterator_tag)
1102  {
1103  if (_GLIBCXX_PARALLEL_CONDITION(
1104  static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
1105  >= __gnu_parallel::_Settings::get().search_minimal_n))
1106  {
1107  __gnu_parallel::_PseudoSequence<_Tp, _Integer> __ps(__val, __count);
1108  return __gnu_parallel::__search_template(
1109  __begin, __end, __ps.begin(), __ps.end(), __binary_pred);
1110  }
1111  else
1112  return _GLIBCXX_STD_A::search_n(__begin, __end, __count, __val,
1113  __binary_pred);
1114  }
1115 
1116  // Sequential fallback for input iterator case.
1117  template<typename _FIterator, typename _Integer, typename _Tp,
1118  typename _BinaryPredicate, typename _IteratorTag>
1119  inline _FIterator
1120  __search_n_switch(_FIterator __begin, _FIterator __end, _Integer __count,
1121  const _Tp& __val, _BinaryPredicate __binary_pred,
1122  _IteratorTag)
1123  { return _GLIBCXX_STD_A::search_n(__begin, __end, __count, __val,
1124  __binary_pred); }
1125 
1126  // Public interface.
1127  template<typename _FIterator, typename _Integer, typename _Tp,
1128  typename _BinaryPredicate>
1129  inline _FIterator
1130  search_n(_FIterator __begin, _FIterator __end, _Integer __count,
1131  const _Tp& __val, _BinaryPredicate __binary_pred)
1132  {
1133  return __search_n_switch(__begin, __end, __count, __val, __binary_pred,
1134  std::__iterator_category(__begin));
1135  }
1136 
1137 
1138  // Sequential fallback.
1139  template<typename _IIter, typename _OutputIterator,
1140  typename _UnaryOperation>
1141  inline _OutputIterator
1142  transform(_IIter __begin, _IIter __end, _OutputIterator __result,
1143  _UnaryOperation __unary_op, __gnu_parallel::sequential_tag)
1144  { return _GLIBCXX_STD_A::transform(__begin, __end, __result, __unary_op); }
1145 
1146  // Parallel unary transform for random access iterators.
1147  template<typename _RAIter1, typename _RAIter2,
1148  typename _UnaryOperation>
1149  _RAIter2
1150  __transform1_switch(_RAIter1 __begin, _RAIter1 __end,
1151  _RAIter2 __result, _UnaryOperation __unary_op,
1152  random_access_iterator_tag, random_access_iterator_tag,
1153  __gnu_parallel::_Parallelism __parallelism_tag)
1154  {
1155  if (_GLIBCXX_PARALLEL_CONDITION(
1156  static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
1157  >= __gnu_parallel::_Settings::get().transform_minimal_n
1158  && __gnu_parallel::__is_parallel(__parallelism_tag)))
1159  {
1160  bool __dummy = true;
1161  typedef __gnu_parallel::_IteratorPair<_RAIter1,
1162  _RAIter2, random_access_iterator_tag> _ItTrip;
1163  _ItTrip __begin_pair(__begin, __result),
1164  __end_pair(__end, __result + (__end - __begin));
1165  __gnu_parallel::__transform1_selector<_ItTrip> __functionality;
1166  __gnu_parallel::
1167  __for_each_template_random_access(
1168  __begin_pair, __end_pair, __unary_op, __functionality,
1169  __gnu_parallel::_DummyReduct(),
1170  __dummy, __dummy, -1, __parallelism_tag);
1171  return __functionality._M_finish_iterator;
1172  }
1173  else
1174  return transform(__begin, __end, __result, __unary_op,
1175  __gnu_parallel::sequential_tag());
1176  }
1177 
1178  // Sequential fallback for input iterator case.
1179  template<typename _RAIter1, typename _RAIter2,
1180  typename _UnaryOperation, typename _IteratorTag1,
1181  typename _IteratorTag2>
1182  inline _RAIter2
1183  __transform1_switch(_RAIter1 __begin, _RAIter1 __end,
1184  _RAIter2 __result, _UnaryOperation __unary_op,
1185  _IteratorTag1, _IteratorTag2)
1186  { return transform(__begin, __end, __result, __unary_op,
1187  __gnu_parallel::sequential_tag()); }
1188 
1189  // Public interface.
1190  template<typename _IIter, typename _OutputIterator,
1191  typename _UnaryOperation>
1192  inline _OutputIterator
1193  transform(_IIter __begin, _IIter __end, _OutputIterator __result,
1194  _UnaryOperation __unary_op,
1195  __gnu_parallel::_Parallelism __parallelism_tag)
1196  {
1197  return __transform1_switch(__begin, __end, __result, __unary_op,
1198  std::__iterator_category(__begin),
1199  std::__iterator_category(__result),
1200  __parallelism_tag);
1201  }
1202 
1203  template<typename _IIter, typename _OutputIterator,
1204  typename _UnaryOperation>
1205  inline _OutputIterator
1206  transform(_IIter __begin, _IIter __end, _OutputIterator __result,
1207  _UnaryOperation __unary_op)
1208  {
1209  return __transform1_switch(__begin, __end, __result, __unary_op,
1210  std::__iterator_category(__begin),
1211  std::__iterator_category(__result));
1212  }
1213 
1214 
1215  // Sequential fallback
1216  template<typename _IIter1, typename _IIter2,
1217  typename _OutputIterator, typename _BinaryOperation>
1218  inline _OutputIterator
1219  transform(_IIter1 __begin1, _IIter1 __end1,
1220  _IIter2 __begin2, _OutputIterator __result,
1221  _BinaryOperation __binary_op, __gnu_parallel::sequential_tag)
1222  { return _GLIBCXX_STD_A::transform(__begin1, __end1,
1223  __begin2, __result, __binary_op); }
1224 
1225  // Parallel binary transform for random access iterators.
1226  template<typename _RAIter1, typename _RAIter2,
1227  typename _RAIter3, typename _BinaryOperation>
1228  _RAIter3
1229  __transform2_switch(_RAIter1 __begin1, _RAIter1 __end1,
1230  _RAIter2 __begin2,
1231  _RAIter3 __result, _BinaryOperation __binary_op,
1232  random_access_iterator_tag, random_access_iterator_tag,
1233  random_access_iterator_tag,
1234  __gnu_parallel::_Parallelism __parallelism_tag)
1235  {
1236  if (_GLIBCXX_PARALLEL_CONDITION(
1237  (__end1 - __begin1) >=
1238  __gnu_parallel::_Settings::get().transform_minimal_n
1239  && __gnu_parallel::__is_parallel(__parallelism_tag)))
1240  {
1241  bool __dummy = true;
1242  typedef __gnu_parallel::_IteratorTriple<_RAIter1,
1243  _RAIter2, _RAIter3,
1244  random_access_iterator_tag> _ItTrip;
1245  _ItTrip __begin_triple(__begin1, __begin2, __result),
1246  __end_triple(__end1, __begin2 + (__end1 - __begin1),
1247  __result + (__end1 - __begin1));
1248  __gnu_parallel::__transform2_selector<_ItTrip> __functionality;
1249  __gnu_parallel::
1250  __for_each_template_random_access(__begin_triple, __end_triple,
1251  __binary_op, __functionality,
1252  __gnu_parallel::_DummyReduct(),
1253  __dummy, __dummy, -1,
1254  __parallelism_tag);
1255  return __functionality._M_finish_iterator;
1256  }
1257  else
1258  return transform(__begin1, __end1, __begin2, __result, __binary_op,
1259  __gnu_parallel::sequential_tag());
1260  }
1261 
1262  // Sequential fallback for input iterator case.
1263  template<typename _IIter1, typename _IIter2,
1264  typename _OutputIterator, typename _BinaryOperation,
1265  typename _Tag1, typename _Tag2, typename _Tag3>
1266  inline _OutputIterator
1267  __transform2_switch(_IIter1 __begin1, _IIter1 __end1,
1268  _IIter2 __begin2, _OutputIterator __result,
1269  _BinaryOperation __binary_op, _Tag1, _Tag2, _Tag3)
1270  { return transform(__begin1, __end1, __begin2, __result, __binary_op,
1271  __gnu_parallel::sequential_tag()); }
1272 
1273  // Public interface.
1274  template<typename _IIter1, typename _IIter2,
1275  typename _OutputIterator, typename _BinaryOperation>
1276  inline _OutputIterator
1277  transform(_IIter1 __begin1, _IIter1 __end1,
1278  _IIter2 __begin2, _OutputIterator __result,
1279  _BinaryOperation __binary_op,
1280  __gnu_parallel::_Parallelism __parallelism_tag)
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  __parallelism_tag);
1288  }
1289 
1290  template<typename _IIter1, typename _IIter2,
1291  typename _OutputIterator, typename _BinaryOperation>
1292  inline _OutputIterator
1293  transform(_IIter1 __begin1, _IIter1 __end1,
1294  _IIter2 __begin2, _OutputIterator __result,
1295  _BinaryOperation __binary_op)
1296  {
1297  return __transform2_switch(
1298  __begin1, __end1, __begin2, __result, __binary_op,
1299  std::__iterator_category(__begin1),
1300  std::__iterator_category(__begin2),
1301  std::__iterator_category(__result));
1302  }
1303 
1304  // Sequential fallback
1305  template<typename _FIterator, typename _Tp>
1306  inline void
1307  replace(_FIterator __begin, _FIterator __end, const _Tp& __old_value,
1308  const _Tp& __new_value, __gnu_parallel::sequential_tag)
1309  { _GLIBCXX_STD_A::replace(__begin, __end, __old_value, __new_value); }
1310 
1311  // Sequential fallback for input iterator case
1312  template<typename _FIterator, typename _Tp, typename _IteratorTag>
1313  inline void
1314  __replace_switch(_FIterator __begin, _FIterator __end,
1315  const _Tp& __old_value, const _Tp& __new_value,
1316  _IteratorTag)
1317  { replace(__begin, __end, __old_value, __new_value,
1318  __gnu_parallel::sequential_tag()); }
1319 
1320  // Parallel replace for random access iterators
1321  template<typename _RAIter, typename _Tp>
1322  inline void
1323  __replace_switch(_RAIter __begin, _RAIter __end,
1324  const _Tp& __old_value, const _Tp& __new_value,
1325  random_access_iterator_tag,
1326  __gnu_parallel::_Parallelism __parallelism_tag)
1327  {
1328  // XXX parallel version is where?
1329  replace(__begin, __end, __old_value, __new_value,
1330  __gnu_parallel::sequential_tag());
1331  }
1332 
1333  // Public interface
1334  template<typename _FIterator, typename _Tp>
1335  inline void
1336  replace(_FIterator __begin, _FIterator __end, const _Tp& __old_value,
1337  const _Tp& __new_value,
1338  __gnu_parallel::_Parallelism __parallelism_tag)
1339  {
1340  __replace_switch(__begin, __end, __old_value, __new_value,
1341  std::__iterator_category(__begin),
1342  __parallelism_tag);
1343  }
1344 
1345  template<typename _FIterator, typename _Tp>
1346  inline void
1347  replace(_FIterator __begin, _FIterator __end, const _Tp& __old_value,
1348  const _Tp& __new_value)
1349  {
1350  __replace_switch(__begin, __end, __old_value, __new_value,
1351  std::__iterator_category(__begin));
1352  }
1353 
1354 
1355  // Sequential fallback
1356  template<typename _FIterator, typename _Predicate, typename _Tp>
1357  inline void
1358  replace_if(_FIterator __begin, _FIterator __end, _Predicate __pred,
1359  const _Tp& __new_value, __gnu_parallel::sequential_tag)
1360  { _GLIBCXX_STD_A::replace_if(__begin, __end, __pred, __new_value); }
1361 
1362  // Sequential fallback for input iterator case
1363  template<typename _FIterator, typename _Predicate, typename _Tp,
1364  typename _IteratorTag>
1365  inline void
1366  __replace_if_switch(_FIterator __begin, _FIterator __end,
1367  _Predicate __pred, const _Tp& __new_value, _IteratorTag)
1368  { replace_if(__begin, __end, __pred, __new_value,
1369  __gnu_parallel::sequential_tag()); }
1370 
1371  // Parallel algorithm for random access iterators.
1372  template<typename _RAIter, typename _Predicate, typename _Tp>
1373  void
1374  __replace_if_switch(_RAIter __begin, _RAIter __end,
1375  _Predicate __pred, const _Tp& __new_value,
1376  random_access_iterator_tag,
1377  __gnu_parallel::_Parallelism __parallelism_tag)
1378  {
1379  if (_GLIBCXX_PARALLEL_CONDITION(
1380  static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
1381  >= __gnu_parallel::_Settings::get().replace_minimal_n
1382  && __gnu_parallel::__is_parallel(__parallelism_tag)))
1383  {
1384  bool __dummy;
1385  __gnu_parallel::
1386  __replace_if_selector<_RAIter, _Predicate, _Tp>
1387  __functionality(__new_value);
1388  __gnu_parallel::
1389  __for_each_template_random_access(
1390  __begin, __end, __pred, __functionality,
1391  __gnu_parallel::_DummyReduct(),
1392  true, __dummy, -1, __parallelism_tag);
1393  }
1394  else
1395  replace_if(__begin, __end, __pred, __new_value,
1396  __gnu_parallel::sequential_tag());
1397  }
1398 
1399  // Public interface.
1400  template<typename _FIterator, typename _Predicate, typename _Tp>
1401  inline void
1402  replace_if(_FIterator __begin, _FIterator __end,
1403  _Predicate __pred, const _Tp& __new_value,
1404  __gnu_parallel::_Parallelism __parallelism_tag)
1405  {
1406  __replace_if_switch(__begin, __end, __pred, __new_value,
1407  std::__iterator_category(__begin),
1408  __parallelism_tag);
1409  }
1410 
1411  template<typename _FIterator, typename _Predicate, typename _Tp>
1412  inline void
1413  replace_if(_FIterator __begin, _FIterator __end,
1414  _Predicate __pred, const _Tp& __new_value)
1415  {
1416  __replace_if_switch(__begin, __end, __pred, __new_value,
1417  std::__iterator_category(__begin));
1418  }
1419 
1420  // Sequential fallback
1421  template<typename _FIterator, typename _Generator>
1422  inline void
1423  generate(_FIterator __begin, _FIterator __end, _Generator __gen,
1424  __gnu_parallel::sequential_tag)
1425  { _GLIBCXX_STD_A::generate(__begin, __end, __gen); }
1426 
1427  // Sequential fallback for input iterator case.
1428  template<typename _FIterator, typename _Generator, typename _IteratorTag>
1429  inline void
1430  __generate_switch(_FIterator __begin, _FIterator __end, _Generator __gen,
1431  _IteratorTag)
1432  { generate(__begin, __end, __gen, __gnu_parallel::sequential_tag()); }
1433 
1434  // Parallel algorithm for random access iterators.
1435  template<typename _RAIter, typename _Generator>
1436  void
1437  __generate_switch(_RAIter __begin, _RAIter __end,
1438  _Generator __gen, random_access_iterator_tag,
1439  __gnu_parallel::_Parallelism __parallelism_tag)
1440  {
1441  if (_GLIBCXX_PARALLEL_CONDITION(
1442  static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
1443  >= __gnu_parallel::_Settings::get().generate_minimal_n
1444  && __gnu_parallel::__is_parallel(__parallelism_tag)))
1445  {
1446  bool __dummy;
1447  __gnu_parallel::__generate_selector<_RAIter>
1448  __functionality;
1449  __gnu_parallel::
1450  __for_each_template_random_access(
1451  __begin, __end, __gen, __functionality,
1452  __gnu_parallel::_DummyReduct(),
1453  true, __dummy, -1, __parallelism_tag);
1454  }
1455  else
1456  generate(__begin, __end, __gen, __gnu_parallel::sequential_tag());
1457  }
1458 
1459  // Public interface.
1460  template<typename _FIterator, typename _Generator>
1461  inline void
1462  generate(_FIterator __begin, _FIterator __end,
1463  _Generator __gen, __gnu_parallel::_Parallelism __parallelism_tag)
1464  {
1465  __generate_switch(__begin, __end, __gen,
1466  std::__iterator_category(__begin),
1467  __parallelism_tag);
1468  }
1469 
1470  template<typename _FIterator, typename _Generator>
1471  inline void
1472  generate(_FIterator __begin, _FIterator __end, _Generator __gen)
1473  {
1474  __generate_switch(__begin, __end, __gen,
1475  std::__iterator_category(__begin));
1476  }
1477 
1478 
1479  // Sequential fallback.
1480  template<typename _OutputIterator, typename _Size, typename _Generator>
1481  inline _OutputIterator
1482  generate_n(_OutputIterator __begin, _Size __n, _Generator __gen,
1483  __gnu_parallel::sequential_tag)
1484  { return _GLIBCXX_STD_A::generate_n(__begin, __n, __gen); }
1485 
1486  // Sequential fallback for input iterator case.
1487  template<typename _OutputIterator, typename _Size, typename _Generator,
1488  typename _IteratorTag>
1489  inline _OutputIterator
1490  __generate_n_switch(_OutputIterator __begin, _Size __n, _Generator __gen,
1491  _IteratorTag)
1492  { return generate_n(__begin, __n, __gen,
1493  __gnu_parallel::sequential_tag()); }
1494 
1495  // Parallel algorithm for random access iterators.
1496  template<typename _RAIter, typename _Size, typename _Generator>
1497  inline _RAIter
1498  __generate_n_switch(_RAIter __begin, _Size __n, _Generator __gen,
1499  random_access_iterator_tag,
1500  __gnu_parallel::_Parallelism __parallelism_tag)
1501  {
1502  // XXX parallel version is where?
1503  return generate_n(__begin, __n, __gen, __gnu_parallel::sequential_tag());
1504  }
1505 
1506  // Public interface.
1507  template<typename _OutputIterator, typename _Size, typename _Generator>
1508  inline _OutputIterator
1509  generate_n(_OutputIterator __begin, _Size __n, _Generator __gen,
1510  __gnu_parallel::_Parallelism __parallelism_tag)
1511  {
1512  return __generate_n_switch(__begin, __n, __gen,
1513  std::__iterator_category(__begin),
1514  __parallelism_tag);
1515  }
1516 
1517  template<typename _OutputIterator, typename _Size, typename _Generator>
1518  inline _OutputIterator
1519  generate_n(_OutputIterator __begin, _Size __n, _Generator __gen)
1520  {
1521  return __generate_n_switch(__begin, __n, __gen,
1522  std::__iterator_category(__begin));
1523  }
1524 
1525 
1526  // Sequential fallback.
1527  template<typename _RAIter>
1528  inline void
1529  random_shuffle(_RAIter __begin, _RAIter __end,
1530  __gnu_parallel::sequential_tag)
1531  { _GLIBCXX_STD_A::random_shuffle(__begin, __end); }
1532 
1533  // Sequential fallback.
1534  template<typename _RAIter, typename _RandomNumberGenerator>
1535  inline void
1536  random_shuffle(_RAIter __begin, _RAIter __end,
1537  _RandomNumberGenerator& __rand,
1538  __gnu_parallel::sequential_tag)
1539  { _GLIBCXX_STD_A::random_shuffle(__begin, __end, __rand); }
1540 
1541 
1542  /** @brief Functor wrapper for std::rand(). */
1543  template<typename _MustBeInt = int>
1544  struct _CRandNumber
1545  {
1546  int
1547  operator()(int __limit)
1548  { return rand() % __limit; }
1549  };
1550 
1551  // Fill in random number generator.
1552  template<typename _RAIter>
1553  inline void
1554  random_shuffle(_RAIter __begin, _RAIter __end)
1555  {
1556  _CRandNumber<> __r;
1557  // Parallelization still possible.
1558  __gnu_parallel::random_shuffle(__begin, __end, __r);
1559  }
1560 
1561  // Parallel algorithm for random access iterators.
1562  template<typename _RAIter, typename _RandomNumberGenerator>
1563  void
1564  random_shuffle(_RAIter __begin, _RAIter __end,
1565 #if __cplusplus >= 201103L
1566  _RandomNumberGenerator&& __rand)
1567 #else
1568  _RandomNumberGenerator& __rand)
1569 #endif
1570  {
1571  if (__begin == __end)
1572  return;
1573  if (_GLIBCXX_PARALLEL_CONDITION(
1574  static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
1575  >= __gnu_parallel::_Settings::get().random_shuffle_minimal_n))
1576  __gnu_parallel::__parallel_random_shuffle(__begin, __end, __rand);
1577  else
1578  __gnu_parallel::__sequential_random_shuffle(__begin, __end, __rand);
1579  }
1580 
1581  // Sequential fallback.
1582  template<typename _FIterator, typename _Predicate>
1583  inline _FIterator
1584  partition(_FIterator __begin, _FIterator __end,
1585  _Predicate __pred, __gnu_parallel::sequential_tag)
1586  { return _GLIBCXX_STD_A::partition(__begin, __end, __pred); }
1587 
1588  // Sequential fallback for input iterator case.
1589  template<typename _FIterator, typename _Predicate, typename _IteratorTag>
1590  inline _FIterator
1591  __partition_switch(_FIterator __begin, _FIterator __end,
1592  _Predicate __pred, _IteratorTag)
1593  { return partition(__begin, __end, __pred,
1594  __gnu_parallel::sequential_tag()); }
1595 
1596  // Parallel algorithm for random access iterators.
1597  template<typename _RAIter, typename _Predicate>
1598  _RAIter
1599  __partition_switch(_RAIter __begin, _RAIter __end,
1600  _Predicate __pred, random_access_iterator_tag)
1601  {
1602  if (_GLIBCXX_PARALLEL_CONDITION(
1603  static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
1604  >= __gnu_parallel::_Settings::get().partition_minimal_n))
1605  {
1606  typedef typename std::iterator_traits<_RAIter>::
1607  difference_type _DifferenceType;
1608  _DifferenceType __middle = __gnu_parallel::
1609  __parallel_partition(__begin, __end, __pred,
1610  __gnu_parallel::__get_max_threads());
1611  return __begin + __middle;
1612  }
1613  else
1614  return partition(__begin, __end, __pred,
1615  __gnu_parallel::sequential_tag());
1616  }
1617 
1618  // Public interface.
1619  template<typename _FIterator, typename _Predicate>
1620  inline _FIterator
1621  partition(_FIterator __begin, _FIterator __end, _Predicate __pred)
1622  {
1623  return __partition_switch(__begin, __end, __pred,
1624  std::__iterator_category(__begin));
1625  }
1626 
1627  // sort interface
1628 
1629  // Sequential fallback
1630  template<typename _RAIter>
1631  inline void
1632  sort(_RAIter __begin, _RAIter __end,
1633  __gnu_parallel::sequential_tag)
1634  { _GLIBCXX_STD_A::sort(__begin, __end); }
1635 
1636  // Sequential fallback
1637  template<typename _RAIter, typename _Compare>
1638  inline void
1639  sort(_RAIter __begin, _RAIter __end, _Compare __comp,
1640  __gnu_parallel::sequential_tag)
1641  { _GLIBCXX_STD_A::sort<_RAIter, _Compare>(__begin, __end,
1642  __comp); }
1643 
1644  // Public interface
1645  template<typename _RAIter, typename _Compare,
1646  typename _Parallelism>
1647  void
1648  sort(_RAIter __begin, _RAIter __end, _Compare __comp,
1649  _Parallelism __parallelism)
1650  {
1651  typedef typename iterator_traits<_RAIter>::value_type _ValueType;
1652 
1653  if (__begin != __end)
1654  {
1655  if (_GLIBCXX_PARALLEL_CONDITION(
1656  static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin) >=
1657  __gnu_parallel::_Settings::get().sort_minimal_n))
1658  __gnu_parallel::__parallel_sort<false>(
1659  __begin, __end, __comp, __parallelism);
1660  else
1661  sort(__begin, __end, __comp, __gnu_parallel::sequential_tag());
1662  }
1663  }
1664 
1665  // Public interface, insert default comparator
1666  template<typename _RAIter>
1667  inline void
1668  sort(_RAIter __begin, _RAIter __end)
1669  {
1670  typedef typename iterator_traits<_RAIter>::value_type _ValueType;
1671  sort(__begin, __end, std::less<_ValueType>(),
1672  __gnu_parallel::default_parallel_tag());
1673  }
1674 
1675  // Public interface, insert default comparator
1676  template<typename _RAIter>
1677  inline void
1678  sort(_RAIter __begin, _RAIter __end,
1679  __gnu_parallel::default_parallel_tag __parallelism)
1680  {
1681  typedef typename iterator_traits<_RAIter>::value_type _ValueType;
1682  sort(__begin, __end, std::less<_ValueType>(), __parallelism);
1683  }
1684 
1685  // Public interface, insert default comparator
1686  template<typename _RAIter>
1687  inline void
1688  sort(_RAIter __begin, _RAIter __end,
1689  __gnu_parallel::parallel_tag __parallelism)
1690  {
1691  typedef typename iterator_traits<_RAIter>::value_type _ValueType;
1692  sort(__begin, __end, std::less<_ValueType>(), __parallelism);
1693  }
1694 
1695  // Public interface, insert default comparator
1696  template<typename _RAIter>
1697  inline void
1698  sort(_RAIter __begin, _RAIter __end,
1699  __gnu_parallel::multiway_mergesort_tag __parallelism)
1700  {
1701  typedef typename iterator_traits<_RAIter>::value_type _ValueType;
1702  sort(__begin, __end, std::less<_ValueType>(), __parallelism);
1703  }
1704 
1705  // Public interface, insert default comparator
1706  template<typename _RAIter>
1707  inline void
1708  sort(_RAIter __begin, _RAIter __end,
1709  __gnu_parallel::multiway_mergesort_sampling_tag __parallelism)
1710  {
1711  typedef typename iterator_traits<_RAIter>::value_type _ValueType;
1712  sort(__begin, __end, std::less<_ValueType>(), __parallelism);
1713  }
1714 
1715  // Public interface, insert default comparator
1716  template<typename _RAIter>
1717  inline void
1718  sort(_RAIter __begin, _RAIter __end,
1719  __gnu_parallel::multiway_mergesort_exact_tag __parallelism)
1720  {
1721  typedef typename iterator_traits<_RAIter>::value_type _ValueType;
1722  sort(__begin, __end, std::less<_ValueType>(), __parallelism);
1723  }
1724 
1725  // Public interface, insert default comparator
1726  template<typename _RAIter>
1727  inline void
1728  sort(_RAIter __begin, _RAIter __end,
1729  __gnu_parallel::quicksort_tag __parallelism)
1730  {
1731  typedef typename iterator_traits<_RAIter>::value_type _ValueType;
1732  sort(__begin, __end, std::less<_ValueType>(), __parallelism);
1733  }
1734 
1735  // Public interface, insert default comparator
1736  template<typename _RAIter>
1737  inline void
1738  sort(_RAIter __begin, _RAIter __end,
1739  __gnu_parallel::balanced_quicksort_tag __parallelism)
1740  {
1741  typedef typename iterator_traits<_RAIter>::value_type _ValueType;
1742  sort(__begin, __end, std::less<_ValueType>(), __parallelism);
1743  }
1744 
1745  // Public interface
1746  template<typename _RAIter, typename _Compare>
1747  void
1748  sort(_RAIter __begin, _RAIter __end, _Compare __comp)
1749  {
1750  typedef typename iterator_traits<_RAIter>::value_type _ValueType;
1751  sort(__begin, __end, __comp, __gnu_parallel::default_parallel_tag());
1752  }
1753 
1754  // stable_sort interface
1755 
1756 
1757  // Sequential fallback
1758  template<typename _RAIter>
1759  inline void
1760  stable_sort(_RAIter __begin, _RAIter __end,
1761  __gnu_parallel::sequential_tag)
1762  { _GLIBCXX_STD_A::stable_sort(__begin, __end); }
1763 
1764  // Sequential fallback
1765  template<typename _RAIter, typename _Compare>
1766  inline void
1767  stable_sort(_RAIter __begin, _RAIter __end,
1768  _Compare __comp, __gnu_parallel::sequential_tag)
1769  { _GLIBCXX_STD_A::stable_sort<_RAIter, _Compare>(__begin, __end, __comp); }
1770 
1771  // Public interface
1772  template<typename _RAIter, typename _Compare,
1773  typename _Parallelism>
1774  void
1775  stable_sort(_RAIter __begin, _RAIter __end,
1776  _Compare __comp, _Parallelism __parallelism)
1777  {
1778  typedef iterator_traits<_RAIter> _TraitsType;
1779  typedef typename _TraitsType::value_type _ValueType;
1780 
1781  if (__begin != __end)
1782  {
1783  if (_GLIBCXX_PARALLEL_CONDITION(
1784  static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin) >=
1785  __gnu_parallel::_Settings::get().sort_minimal_n))
1786  __gnu_parallel::__parallel_sort<true>(__begin, __end,
1787  __comp, __parallelism);
1788  else
1789  stable_sort(__begin, __end, __comp,
1790  __gnu_parallel::sequential_tag());
1791  }
1792  }
1793 
1794  // Public interface, insert default comparator
1795  template<typename _RAIter>
1796  inline void
1797  stable_sort(_RAIter __begin, _RAIter __end)
1798  {
1799  typedef typename iterator_traits<_RAIter>::value_type _ValueType;
1800  stable_sort(__begin, __end, std::less<_ValueType>(),
1801  __gnu_parallel::default_parallel_tag());
1802  }
1803 
1804  // Public interface, insert default comparator
1805  template<typename _RAIter>
1806  inline void
1807  stable_sort(_RAIter __begin, _RAIter __end,
1808  __gnu_parallel::default_parallel_tag __parallelism)
1809  {
1810  typedef typename iterator_traits<_RAIter>::value_type _ValueType;
1811  stable_sort(__begin, __end, std::less<_ValueType>(), __parallelism);
1812  }
1813 
1814  // Public interface, insert default comparator
1815  template<typename _RAIter>
1816  inline void
1817  stable_sort(_RAIter __begin, _RAIter __end,
1818  __gnu_parallel::parallel_tag __parallelism)
1819  {
1820  typedef typename iterator_traits<_RAIter>::value_type _ValueType;
1821  stable_sort(__begin, __end, std::less<_ValueType>(), __parallelism);
1822  }
1823 
1824  // Public interface, insert default comparator
1825  template<typename _RAIter>
1826  inline void
1827  stable_sort(_RAIter __begin, _RAIter __end,
1828  __gnu_parallel::multiway_mergesort_tag __parallelism)
1829  {
1830  typedef typename iterator_traits<_RAIter>::value_type _ValueType;
1831  stable_sort(__begin, __end, std::less<_ValueType>(), __parallelism);
1832  }
1833 
1834  // Public interface, insert default comparator
1835  template<typename _RAIter>
1836  inline void
1837  stable_sort(_RAIter __begin, _RAIter __end,
1838  __gnu_parallel::quicksort_tag __parallelism)
1839  {
1840  typedef typename iterator_traits<_RAIter>::value_type _ValueType;
1841  stable_sort(__begin, __end, std::less<_ValueType>(), __parallelism);
1842  }
1843 
1844  // Public interface, insert default comparator
1845  template<typename _RAIter>
1846  inline void
1847  stable_sort(_RAIter __begin, _RAIter __end,
1848  __gnu_parallel::balanced_quicksort_tag __parallelism)
1849  {
1850  typedef typename iterator_traits<_RAIter>::value_type _ValueType;
1851  stable_sort(__begin, __end, std::less<_ValueType>(), __parallelism);
1852  }
1853 
1854  // Public interface
1855  template<typename _RAIter, typename _Compare>
1856  void
1857  stable_sort(_RAIter __begin, _RAIter __end, _Compare __comp)
1858  {
1859  stable_sort(
1860  __begin, __end, __comp, __gnu_parallel::default_parallel_tag());
1861  }
1862 
1863  // Sequential fallback
1864  template<typename _IIter1, typename _IIter2,
1865  typename _OutputIterator>
1866  inline _OutputIterator
1867  merge(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2,
1868  _IIter2 __end2, _OutputIterator __result,
1869  __gnu_parallel::sequential_tag)
1870  { return _GLIBCXX_STD_A::merge(
1871  __begin1, __end1, __begin2, __end2, __result); }
1872 
1873  // Sequential fallback
1874  template<typename _IIter1, typename _IIter2,
1875  typename _OutputIterator, typename _Compare>
1876  inline _OutputIterator
1877  merge(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2,
1878  _IIter2 __end2, _OutputIterator __result, _Compare __comp,
1879  __gnu_parallel::sequential_tag)
1880  { return _GLIBCXX_STD_A::merge(
1881  __begin1, __end1, __begin2, __end2, __result, __comp); }
1882 
1883  // Sequential fallback for input iterator case
1884  template<typename _IIter1, typename _IIter2, typename _OutputIterator,
1885  typename _Compare, typename _IteratorTag1,
1886  typename _IteratorTag2, typename _IteratorTag3>
1887  inline _OutputIterator
1888  __merge_switch(_IIter1 __begin1, _IIter1 __end1,
1889  _IIter2 __begin2, _IIter2 __end2,
1890  _OutputIterator __result, _Compare __comp,
1891  _IteratorTag1, _IteratorTag2, _IteratorTag3)
1892  { return _GLIBCXX_STD_A::merge(__begin1, __end1, __begin2, __end2,
1893  __result, __comp); }
1894 
1895  // Parallel algorithm for random access iterators
1896  template<typename _IIter1, typename _IIter2,
1897  typename _OutputIterator, typename _Compare>
1898  _OutputIterator
1899  __merge_switch(_IIter1 __begin1, _IIter1 __end1,
1900  _IIter2 __begin2, _IIter2 __end2,
1901  _OutputIterator __result, _Compare __comp,
1902  random_access_iterator_tag, random_access_iterator_tag,
1903  random_access_iterator_tag)
1904  {
1905  if (_GLIBCXX_PARALLEL_CONDITION(
1906  (static_cast<__gnu_parallel::_SequenceIndex>(__end1 - __begin1)
1907  >= __gnu_parallel::_Settings::get().merge_minimal_n
1908  || static_cast<__gnu_parallel::_SequenceIndex>(__end2 - __begin2)
1909  >= __gnu_parallel::_Settings::get().merge_minimal_n)))
1910  return __gnu_parallel::__parallel_merge_advance(
1911  __begin1, __end1, __begin2, __end2, __result,
1912  (__end1 - __begin1) + (__end2 - __begin2), __comp);
1913  else
1914  return __gnu_parallel::__merge_advance(
1915  __begin1, __end1, __begin2, __end2, __result,
1916  (__end1 - __begin1) + (__end2 - __begin2), __comp);
1917  }
1918 
1919  // Public interface
1920  template<typename _IIter1, typename _IIter2,
1921  typename _OutputIterator, typename _Compare>
1922  inline _OutputIterator
1923  merge(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2,
1924  _IIter2 __end2, _OutputIterator __result, _Compare __comp)
1925  {
1926  return __merge_switch(
1927  __begin1, __end1, __begin2, __end2, __result, __comp,
1928  std::__iterator_category(__begin1),
1929  std::__iterator_category(__begin2),
1930  std::__iterator_category(__result));
1931  }
1932 
1933  // Public interface, insert default comparator
1934  template<typename _IIter1, typename _IIter2,
1935  typename _OutputIterator>
1936  inline _OutputIterator
1937  merge(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2,
1938  _IIter2 __end2, _OutputIterator __result)
1939  {
1940  typedef typename std::iterator_traits<_IIter1>::value_type _ValueType1;
1941  typedef typename std::iterator_traits<_IIter2>::value_type _ValueType2;
1942 
1943  return __gnu_parallel::merge(__begin1, __end1, __begin2, __end2,
1944  __result, __gnu_parallel::_Less<_ValueType1, _ValueType2>());
1945  }
1946 
1947  // Sequential fallback
1948  template<typename _RAIter>
1949  inline void
1950  nth_element(_RAIter __begin, _RAIter __nth,
1951  _RAIter __end, __gnu_parallel::sequential_tag)
1952  { return _GLIBCXX_STD_A::nth_element(__begin, __nth, __end); }
1953 
1954  // Sequential fallback
1955  template<typename _RAIter, typename _Compare>
1956  inline void
1957  nth_element(_RAIter __begin, _RAIter __nth,
1958  _RAIter __end, _Compare __comp,
1959  __gnu_parallel::sequential_tag)
1960  { return _GLIBCXX_STD_A::nth_element(__begin, __nth, __end, __comp); }
1961 
1962  // Public interface
1963  template<typename _RAIter, typename _Compare>
1964  inline void
1965  nth_element(_RAIter __begin, _RAIter __nth,
1966  _RAIter __end, _Compare __comp)
1967  {
1968  if (_GLIBCXX_PARALLEL_CONDITION(
1969  static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
1970  >= __gnu_parallel::_Settings::get().nth_element_minimal_n))
1971  __gnu_parallel::__parallel_nth_element(__begin, __nth, __end, __comp);
1972  else
1973  nth_element(__begin, __nth, __end, __comp,
1974  __gnu_parallel::sequential_tag());
1975  }
1976 
1977  // Public interface, insert default comparator
1978  template<typename _RAIter>
1979  inline void
1980  nth_element(_RAIter __begin, _RAIter __nth,
1981  _RAIter __end)
1982  {
1983  typedef typename iterator_traits<_RAIter>::value_type _ValueType;
1984  __gnu_parallel::nth_element(__begin, __nth, __end,
1985  std::less<_ValueType>());
1986  }
1987 
1988  // Sequential fallback
1989  template<typename _RAIter, typename _Compare>
1990  inline void
1991  partial_sort(_RAIter __begin, _RAIter __middle,
1992  _RAIter __end, _Compare __comp,
1993  __gnu_parallel::sequential_tag)
1994  { _GLIBCXX_STD_A::partial_sort(__begin, __middle, __end, __comp); }
1995 
1996  // Sequential fallback
1997  template<typename _RAIter>
1998  inline void
1999  partial_sort(_RAIter __begin, _RAIter __middle,
2000  _RAIter __end, __gnu_parallel::sequential_tag)
2001  { _GLIBCXX_STD_A::partial_sort(__begin, __middle, __end); }
2002 
2003  // Public interface, parallel algorithm for random access iterators
2004  template<typename _RAIter, typename _Compare>
2005  void
2006  partial_sort(_RAIter __begin, _RAIter __middle,
2007  _RAIter __end, _Compare __comp)
2008  {
2009  if (_GLIBCXX_PARALLEL_CONDITION(
2010  static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
2011  >= __gnu_parallel::_Settings::get().partial_sort_minimal_n))
2012  __gnu_parallel::
2013  __parallel_partial_sort(__begin, __middle, __end, __comp);
2014  else
2015  partial_sort(__begin, __middle, __end, __comp,
2016  __gnu_parallel::sequential_tag());
2017  }
2018 
2019  // Public interface, insert default comparator
2020  template<typename _RAIter>
2021  inline void
2022  partial_sort(_RAIter __begin, _RAIter __middle,
2023  _RAIter __end)
2024  {
2025  typedef iterator_traits<_RAIter> _TraitsType;
2026  typedef typename _TraitsType::value_type _ValueType;
2027  __gnu_parallel::partial_sort(__begin, __middle, __end,
2028  std::less<_ValueType>());
2029  }
2030 
2031  // Sequential fallback
2032  template<typename _FIterator>
2033  inline _FIterator
2034  max_element(_FIterator __begin, _FIterator __end,
2035  __gnu_parallel::sequential_tag)
2036  { return _GLIBCXX_STD_A::max_element(__begin, __end); }
2037 
2038  // Sequential fallback
2039  template<typename _FIterator, typename _Compare>
2040  inline _FIterator
2041  max_element(_FIterator __begin, _FIterator __end, _Compare __comp,
2042  __gnu_parallel::sequential_tag)
2043  { return _GLIBCXX_STD_A::max_element(__begin, __end, __comp); }
2044 
2045  // Sequential fallback for input iterator case
2046  template<typename _FIterator, typename _Compare, typename _IteratorTag>
2047  inline _FIterator
2048  __max_element_switch(_FIterator __begin, _FIterator __end,
2049  _Compare __comp, _IteratorTag)
2050  { return max_element(__begin, __end, __comp,
2051  __gnu_parallel::sequential_tag()); }
2052 
2053  // Parallel algorithm for random access iterators
2054  template<typename _RAIter, typename _Compare>
2055  _RAIter
2056  __max_element_switch(_RAIter __begin, _RAIter __end,
2057  _Compare __comp, random_access_iterator_tag,
2058  __gnu_parallel::_Parallelism __parallelism_tag)
2059  {
2060  if (_GLIBCXX_PARALLEL_CONDITION(
2061  static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
2062  >= __gnu_parallel::_Settings::get().max_element_minimal_n
2063  && __gnu_parallel::__is_parallel(__parallelism_tag)))
2064  {
2065  _RAIter __res(__begin);
2066  __gnu_parallel::__identity_selector<_RAIter>
2067  __functionality;
2068  __gnu_parallel::
2069  __for_each_template_random_access(
2070  __begin, __end, __gnu_parallel::_Nothing(), __functionality,
2071  __gnu_parallel::__max_element_reduct<_Compare, _RAIter>(__comp),
2072  __res, __res, -1, __parallelism_tag);
2073  return __res;
2074  }
2075  else
2076  return max_element(__begin, __end, __comp,
2077  __gnu_parallel::sequential_tag());
2078  }
2079 
2080  // Public interface, insert default comparator
2081  template<typename _FIterator>
2082  inline _FIterator
2083  max_element(_FIterator __begin, _FIterator __end,
2084  __gnu_parallel::_Parallelism __parallelism_tag)
2085  {
2086  typedef typename iterator_traits<_FIterator>::value_type _ValueType;
2087  return max_element(__begin, __end, std::less<_ValueType>(),
2088  __parallelism_tag);
2089  }
2090 
2091  template<typename _FIterator>
2092  inline _FIterator
2093  max_element(_FIterator __begin, _FIterator __end)
2094  {
2095  typedef typename iterator_traits<_FIterator>::value_type _ValueType;
2096  return __gnu_parallel::max_element(__begin, __end,
2097  std::less<_ValueType>());
2098  }
2099 
2100  // Public interface
2101  template<typename _FIterator, typename _Compare>
2102  inline _FIterator
2103  max_element(_FIterator __begin, _FIterator __end, _Compare __comp,
2104  __gnu_parallel::_Parallelism __parallelism_tag)
2105  {
2106  return __max_element_switch(__begin, __end, __comp,
2107  std::__iterator_category(__begin),
2108  __parallelism_tag);
2109  }
2110 
2111  template<typename _FIterator, typename _Compare>
2112  inline _FIterator
2113  max_element(_FIterator __begin, _FIterator __end, _Compare __comp)
2114  {
2115  return __max_element_switch(__begin, __end, __comp,
2116  std::__iterator_category(__begin));
2117  }
2118 
2119 
2120  // Sequential fallback
2121  template<typename _FIterator>
2122  inline _FIterator
2123  min_element(_FIterator __begin, _FIterator __end,
2124  __gnu_parallel::sequential_tag)
2125  { return _GLIBCXX_STD_A::min_element(__begin, __end); }
2126 
2127  // Sequential fallback
2128  template<typename _FIterator, typename _Compare>
2129  inline _FIterator
2130  min_element(_FIterator __begin, _FIterator __end, _Compare __comp,
2131  __gnu_parallel::sequential_tag)
2132  { return _GLIBCXX_STD_A::min_element(__begin, __end, __comp); }
2133 
2134  // Sequential fallback for input iterator case
2135  template<typename _FIterator, typename _Compare, typename _IteratorTag>
2136  inline _FIterator
2137  __min_element_switch(_FIterator __begin, _FIterator __end,
2138  _Compare __comp, _IteratorTag)
2139  { return min_element(__begin, __end, __comp,
2140  __gnu_parallel::sequential_tag()); }
2141 
2142  // Parallel algorithm for random access iterators
2143  template<typename _RAIter, typename _Compare>
2144  _RAIter
2145  __min_element_switch(_RAIter __begin, _RAIter __end,
2146  _Compare __comp, random_access_iterator_tag,
2147  __gnu_parallel::_Parallelism __parallelism_tag)
2148  {
2149  if (_GLIBCXX_PARALLEL_CONDITION(
2150  static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
2151  >= __gnu_parallel::_Settings::get().min_element_minimal_n
2152  && __gnu_parallel::__is_parallel(__parallelism_tag)))
2153  {
2154  _RAIter __res(__begin);
2155  __gnu_parallel::__identity_selector<_RAIter>
2156  __functionality;
2157  __gnu_parallel::
2158  __for_each_template_random_access(
2159  __begin, __end, __gnu_parallel::_Nothing(), __functionality,
2160  __gnu_parallel::__min_element_reduct<_Compare, _RAIter>(__comp),
2161  __res, __res, -1, __parallelism_tag);
2162  return __res;
2163  }
2164  else
2165  return min_element(__begin, __end, __comp,
2166  __gnu_parallel::sequential_tag());
2167  }
2168 
2169  // Public interface, insert default comparator
2170  template<typename _FIterator>
2171  inline _FIterator
2172  min_element(_FIterator __begin, _FIterator __end,
2173  __gnu_parallel::_Parallelism __parallelism_tag)
2174  {
2175  typedef typename iterator_traits<_FIterator>::value_type _ValueType;
2176  return min_element(__begin, __end, std::less<_ValueType>(),
2177  __parallelism_tag);
2178  }
2179 
2180  template<typename _FIterator>
2181  inline _FIterator
2182  min_element(_FIterator __begin, _FIterator __end)
2183  {
2184  typedef typename iterator_traits<_FIterator>::value_type _ValueType;
2185  return __gnu_parallel::min_element(__begin, __end,
2186  std::less<_ValueType>());
2187  }
2188 
2189  // Public interface
2190  template<typename _FIterator, typename _Compare>
2191  inline _FIterator
2192  min_element(_FIterator __begin, _FIterator __end, _Compare __comp,
2193  __gnu_parallel::_Parallelism __parallelism_tag)
2194  {
2195  return __min_element_switch(__begin, __end, __comp,
2196  std::__iterator_category(__begin),
2197  __parallelism_tag);
2198  }
2199 
2200  template<typename _FIterator, typename _Compare>
2201  inline _FIterator
2202  min_element(_FIterator __begin, _FIterator __end, _Compare __comp)
2203  {
2204  return __min_element_switch(__begin, __end, __comp,
2205  std::__iterator_category(__begin));
2206  }
2207 
2208 #if __cplusplus >= 201703L
2209  using _GLIBCXX_STD_A::for_each_n;
2210  using _GLIBCXX_STD_A::sample;
2211 #endif
2212 } // end namespace
2213 } // end namespace
2214 
2215 #endif /* _GLIBCXX_PARALLEL_ALGO_H */
base.h
Sequential helper functions. This file is a GNU parallel extension to the Standard C++ Library.
find.h
Parallel implementation base for std::find(), std::equal() and related functions. This file is a GNU ...
find_selectors.h
_Function objects representing different tasks to be plugged into the parallel find algorithm....
for_each.h
Main interface for embarrassingly parallel functions.
for_each_selectors.h
Functors representing different tasks to be plugged into the generic parallelization methods for emba...
iterator.h
Helper iterator classes for the std::transform() functions. This file is a GNU parallel extension to ...
merge.h
Parallel implementation of std::merge(). This file is a GNU parallel extension to the Standard C++ Li...
omp_loop.h
Parallelization of embarrassingly parallel execution by means of an OpenMP for loop....
omp_loop_static.h
Parallelization of embarrassingly parallel execution by means of an OpenMP for loop with static sched...
par_loop.h
Parallelization of embarrassingly parallel execution by means of equal splitting. This file is a GNU ...
partition.h
Parallel implementation of std::partition(), std::nth_element(), and std::partial_sort()....
random_shuffle.h
Parallel implementation of std::random_shuffle(). This file is a GNU parallel extension to the Standa...
search.h
Parallel implementation base for std::search() and std::search_n(). This file is a GNU parallel exten...
set_operations.h
Parallel implementations of set operations for random-access iterators. This file is a GNU parallel e...
_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:94
sort.h
Parallel sorting algorithm switch. This file is a GNU parallel extension to the Standard C++ Library.
unique_copy.h
Parallel implementations of std::unique_copy(). This file is a GNU parallel extension to the Standard...
workstealing.h
Parallelization of embarrassingly parallel execution by means of work-stealing.
std::__iterator_category
constexpr iterator_traits< _Iter >::iterator_category __iterator_category(const _Iter &)
Definition: stl_iterator_base_types.h:238
std
ISO C++ entities toplevel namespace is std.
std::__parallel::search
_ForwardIterator search(_ForwardIterator __first, _ForwardIterator __last, const _Searcher &__searcher)
Search a sequence using a Searcher object.
Definition: algo.h:1062
__gnu_parallel
GNU parallel code for public use.
Definition: balanced_quicksort.h:62
__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::__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
__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::__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
__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
__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::_Parallelism
_Parallelism
Run-time equivalents for the compile-time tags.
Definition: types.h:45
__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
__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::__sequential_random_shuffle
void __sequential_random_shuffle(_RAIter __begin, _RAIter __end, _RandomNumberGenerator &__rng)
Sequential cache-efficient random shuffle.
Definition: random_shuffle.h:410
__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
__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
__gnu_parallel::__search_template
__RAIter1 __search_template(__RAIter1 __begin1, __RAIter1 __end1, __RAIter2 __begin2, __RAIter2 __end2, _Pred __pred)
Parallel std::search.
Definition: search.h:81
std::iterator_traits
Traits class for iterators.
Definition: stl_iterator_base_types.h:178
std::plus
One of the math functors.
Definition: stl_function.h:185
std::equal_to
One of the comparison functors.
Definition: stl_function.h:374
std::less
One of the comparison functors.
Definition: stl_function.h:404
std::random_access_iterator_tag
Random-access iterators support a superset of bidirectional iterator operations.
Definition: stl_iterator_base_types.h:107
std::__parallel::_CRandNumber
Functor wrapper for std::rand().
Definition: algo.h:1545
__gnu_parallel::__binder2nd
Similar to std::binder2nd, but giving the argument types explicitly.
Definition: base.h:222
__gnu_parallel::_EqualTo
Similar to std::equal_to, but allows two different types.
Definition: base.h:245
__gnu_parallel::_Less
Similar to std::less, but allows two different types.
Definition: base.h:253
__gnu_parallel::_PseudoSequence
Sequence that conceptually consists of multiple copies of the same element. The copies are not stored...
Definition: base.h:360
__gnu_parallel::__find_if_selector
Test predicate on a single element, used for std::find() and std::find_if ().
Definition: find_selectors.h:51
__gnu_parallel::__adjacent_find_selector
Test predicate on two adjacent elements.
Definition: find_selectors.h:81
__gnu_parallel::__find_first_of_selector
Test predicate on several elements.
Definition: find_selectors.h:154
__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
__gnu_parallel::__transform1_selector
std::transform() __selector, one input sequence variant.
Definition: for_each_selectors.h:101
__gnu_parallel::__transform2_selector
std::transform() __selector, two input sequences variant.
Definition: for_each_selectors.h:117
__gnu_parallel::__identity_selector
Selector that just returns the passed iterator.
Definition: for_each_selectors.h:254
__gnu_parallel::_Nothing
Functor doing nothing.
Definition: for_each_selectors.h:289
__gnu_parallel::_DummyReduct
Reduction function doing nothing.
Definition: for_each_selectors.h:299
__gnu_parallel::__min_element_reduct
Reduction for finding the maximum element, using a comparator.
Definition: for_each_selectors.h:308
__gnu_parallel::__max_element_reduct
Reduction for finding the maximum element, using a comparator.
Definition: for_each_selectors.h:322
__gnu_parallel::_IteratorPair
A pair of iterators. The usual iterator operations are applied to both child iterators.
Definition: iterator.h:46
__gnu_parallel::_IteratorTriple
A triple of iterators. The usual iterator operations are applied to all three child iterators.
Definition: iterator.h:121
__gnu_parallel::_Settings::get
static const _Settings & get()
Get the global settings.
__gnu_parallel::sequential_tag
Forces sequential execution at compile time.
Definition: tags.h:42
__gnu_parallel::parallel_tag
Recommends parallel execution at compile time, optionally using a user-specified number of threads.
Definition: tags.h:47
__gnu_parallel::default_parallel_tag
Recommends parallel execution using the default parallel algorithm.
Definition: tags.h:80
__gnu_parallel::multiway_mergesort_tag
Forces parallel sorting using multiway mergesort at compile time.
Definition: tags.h:129
__gnu_parallel::multiway_mergesort_exact_tag
Forces parallel sorting using multiway mergesort with exact splitting at compile time.
Definition: tags.h:138
__gnu_parallel::multiway_mergesort_sampling_tag
Forces parallel sorting using multiway mergesort with splitting by sampling at compile time.
Definition: tags.h:147
__gnu_parallel::quicksort_tag
Forces parallel sorting using unbalanced quicksort at compile time.
Definition: tags.h:156
__gnu_parallel::balanced_quicksort_tag
Forces parallel sorting using balanced quicksort at compile time.
Definition: tags.h:165