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