libstdc++
algo.h
Go to the documentation of this file.
1 // -*- C++ -*-
2 
3 // Copyright (C) 2007-2025 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 */
Sequential helper functions. This file is a GNU parallel extension to the Standard C++ Library.
Parallel implementation base for std::find(), std::equal() and related functions. This file is a GNU ...
_Function objects representing different tasks to be plugged into the parallel find algorithm....
Main interface for embarrassingly parallel functions.
Functors representing different tasks to be plugged into the generic parallelization methods for emba...
Helper iterator classes for the std::transform() functions. This file is a GNU parallel extension to ...
Parallel implementation of std::merge(). This file is a GNU parallel extension to the Standard C++ Li...
Parallelization of embarrassingly parallel execution by means of an OpenMP for loop....
Parallelization of embarrassingly parallel execution by means of an OpenMP for loop with static sched...
Parallelization of embarrassingly parallel execution by means of equal splitting. This file is a GNU ...
Parallel implementation of std::partition(), std::nth_element(), and std::partial_sort()....
Parallel implementation of std::random_shuffle(). This file is a GNU parallel extension to the Standa...
Parallel implementation base for std::search() and std::search_n(). This file is a GNU parallel exten...
Parallel implementations of set operations for random-access iterators. This file is a GNU parallel e...
#define _GLIBCXX_PARALLEL_CONDITION(__c)
Determine at compile(?)-time if the parallel variant of an algorithm should be called.
Definition: settings.h:97
Parallel sorting algorithm switch. This file is a GNU parallel extension to the Standard C++ Library.
Parallel implementations of std::unique_copy(). This file is a GNU parallel extension to the Standard...
Parallelization of embarrassingly parallel execution by means of work-stealing.
constexpr iterator_traits< _Iter >::iterator_category __iterator_category(const _Iter &)
ISO C++ entities toplevel namespace is std.
_ForwardIterator search(_ForwardIterator __first, _ForwardIterator __last, const _Searcher &__searcher)
Search a sequence using a Searcher object.
Definition: algo.h:1009
GNU parallel code for public use.
_OutputIterator __merge_advance(_RAIter1 &__begin1, _RAIter1 __end1, _RAIter2 &__begin2, _RAIter2 __end2, _OutputIterator __target, _DifferenceTp __max_length, _Compare __comp)
Merge routine being able to merge only the __max_length smallest elements.
Definition: merge.h:171
_UserOp __for_each_template_random_access(_IIter __begin, _IIter __end, _UserOp __user_op, _Functionality &__functionality, _Red __reduction, _Result __reduction_start, _Result &__output, typename std::iterator_traits< _IIter >::difference_type __bound, _Parallelism __parallelism_tag)
Chose the desired algorithm by evaluating __parallelism_tag.
Definition: for_each.h:61
void __parallel_nth_element(_RAIter __begin, _RAIter __nth, _RAIter __end, _Compare __comp)
Parallel implementation of std::nth_element().
Definition: partition.h:332
_OutputIterator __parallel_unique_copy(_IIter __first, _IIter __last, _OutputIterator __result, _BinaryPredicate __binary_pred)
Parallel std::unique_copy(), w/__o explicit equality predicate.
Definition: unique_copy.h:50
uint64_t _SequenceIndex
Unsigned integer to index __elements. The total number of elements for each algorithm must fit into t...
Definition: types.h:117
void __parallel_random_shuffle(_RAIter __begin, _RAIter __end, _RandomNumberGenerator __rng=_RandomNumber())
Parallel random public call.
_Parallelism
Run-time equivalents for the compile-time tags.
Definition: types.h:45
std::pair< _RAIter1, _RAIter2 > __find_template(_RAIter1 __begin1, _RAIter1 __end1, _RAIter2 __begin2, _Pred __pred, _Selector __selector)
Parallel std::find, switch for different algorithms.
Definition: find.h:60
std::iterator_traits< _RAIter >::difference_type __parallel_partition(_RAIter __begin, _RAIter __end, _Predicate __pred, _ThreadIndex __num_threads)
Parallel implementation of std::partition.
Definition: partition.h:56
void __sequential_random_shuffle(_RAIter __begin, _RAIter __end, _RandomNumberGenerator &__rng)
Sequential cache-efficient random shuffle.
void __parallel_partial_sort(_RAIter __begin, _RAIter __middle, _RAIter __end, _Compare __comp)
Parallel implementation of std::partial_sort().
Definition: partition.h:422
_RAIter3 __parallel_merge_advance(_RAIter1 &__begin1, _RAIter1 __end1, _RAIter2 &__begin2, _RAIter2 __end2, _RAIter3 __target, typename std::iterator_traits< _RAIter1 >::difference_type __max_length, _Compare __comp)
Merge routine fallback to sequential in case the iterators of the two input sequences are of differen...
Definition: merge.h:195
__RAIter1 __search_template(__RAIter1 __begin1, __RAIter1 __end1, __RAIter2 __begin2, __RAIter2 __end2, _Pred __pred)
Parallel std::search.
Definition: search.h:81
One of the math functors.
Definition: stl_function.h:185
One of the comparison functors.
Definition: stl_function.h:371
One of the comparison functors.
Definition: stl_function.h:401
Random-access iterators support a superset of bidirectional iterator operations.
Traits class for iterators.
Functor wrapper for std::rand().
Definition: algo.h:1492
Similar to std::binder2nd, but giving the argument types explicitly.
Definition: base.h:224
Similar to std::equal_to, but allows two different types.
Definition: base.h:247
Similar to std::less, but allows two different types.
Definition: base.h:255
Sequence that conceptually consists of multiple copies of the same element. The copies are not stored...
Definition: base.h:364
Test predicate on a single element, used for std::find() and std::find_if ().
Test predicate on two adjacent elements.
Test predicate on several elements.
_It _M_finish_iterator
_Iterator on last element processed; needed for some algorithms (e. g. std::transform()).
std::transform() __selector, one input sequence variant.
std::transform() __selector, two input sequences variant.
Selector that just returns the passed iterator.
Functor doing nothing.
Reduction function doing nothing.
Reduction for finding the maximum element, using a comparator.
Reduction for finding the maximum element, using a comparator.
A pair of iterators. The usual iterator operations are applied to both child iterators.
Definition: iterator.h:46
A triple of iterators. The usual iterator operations are applied to all three child iterators.
Definition: iterator.h:121
static const _Settings & get()
Get the global settings.
Forces sequential execution at compile time.
Definition: tags.h:42
Recommends parallel execution at compile time, optionally using a user-specified number of threads.
Definition: tags.h:47
Recommends parallel execution using the default parallel algorithm.
Definition: tags.h:80
Forces parallel sorting using multiway mergesort at compile time.
Definition: tags.h:129
Forces parallel sorting using multiway mergesort with exact splitting at compile time.
Definition: tags.h:138
Forces parallel sorting using multiway mergesort with splitting by sampling at compile time.
Definition: tags.h:147
Forces parallel sorting using unbalanced quicksort at compile time.
Definition: tags.h:156
Forces parallel sorting using balanced quicksort at compile time.
Definition: tags.h:165