libstdc++-v3/include/parallel/algo.h

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2007-2023 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   // 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 */