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