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