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