libstdc++
algobase.h
Go to the documentation of this file.
1 // -*- C++ -*-
2 
3 // Copyright (C) 2007-2025 Free Software Foundation, Inc.
4 //
5 // This file is part of the GNU ISO C++ Library. This library is free
6 // software; you can redistribute it and/or modify it under the terms
7 // of the GNU General Public License as published by the Free Software
8 // Foundation; either version 3, or (at your option) any later
9 // version.
10 
11 // This library is distributed in the hope that it will be useful, but
12 // WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 // General Public License for more details.
15 
16 // Under Section 7 of GPL version 3, you are granted additional
17 // permissions described in the GCC Runtime Library Exception, version
18 // 3.1, as published by the Free Software Foundation.
19 
20 // You should have received a copy of the GNU General Public License and
21 // a copy of the GCC Runtime Library Exception along with this program;
22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23 // <http://www.gnu.org/licenses/>.
24 
25 /** @file parallel/algobase.h
26  * @brief Parallel STL function calls corresponding to the
27  * stl_algobase.h header. The functions defined here mainly do case
28  * switches and call the actual parallelized versions in other files.
29  * Inlining policy: Functions that basically only contain one
30  * function call, are declared inline.
31  * This file is a GNU parallel extension to the Standard C++ Library.
32  */
33 
34 // Written by Johannes Singler and Felix Putze.
35 
36 #ifndef _GLIBCXX_PARALLEL_ALGOBASE_H
37 #define _GLIBCXX_PARALLEL_ALGOBASE_H 1
38 
39 #include <bits/stl_algobase.h>
40 #include <parallel/base.h>
41 #include <parallel/algorithmfwd.h>
42 #include <parallel/find.h>
44 #include <parallel/search.h>
45 
46 namespace std _GLIBCXX_VISIBILITY(default)
47 {
48 namespace __parallel
49 {
50  // NB: equal and lexicographical_compare require mismatch.
51 
52  // Sequential fallback
53  template<typename _IIter1, typename _IIter2>
54  inline pair<_IIter1, _IIter2>
55  mismatch(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2,
57  { return _GLIBCXX_STD_A::mismatch(__begin1, __end1, __begin2); }
58 
59  // Sequential fallback
60  template<typename _IIter1, typename _IIter2, typename _Predicate>
61  inline pair<_IIter1, _IIter2>
62  mismatch(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2,
63  _Predicate __pred, __gnu_parallel::sequential_tag)
64  { return _GLIBCXX_STD_A::mismatch(__begin1, __end1, __begin2, __pred); }
65 
66  // Sequential fallback for input iterator case
67  template<typename _IIter1, typename _IIter2,
68  typename _Predicate, typename _IteratorTag1, typename _IteratorTag2>
69  inline pair<_IIter1, _IIter2>
70  __mismatch_switch(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2,
71  _Predicate __pred, _IteratorTag1, _IteratorTag2)
72  { return _GLIBCXX_STD_A::mismatch(__begin1, __end1, __begin2, __pred); }
73 
74  // Parallel mismatch for random access iterators
75  template<typename _RAIter1, typename _RAIter2, typename _Predicate>
76  pair<_RAIter1, _RAIter2>
77  __mismatch_switch(_RAIter1 __begin1, _RAIter1 __end1,
78  _RAIter2 __begin2, _Predicate __pred,
79  random_access_iterator_tag, random_access_iterator_tag)
80  {
82  {
83  _RAIter1 __res =
84  __gnu_parallel::__find_template(__begin1, __end1, __begin2, __pred,
86  __mismatch_selector()).first;
87  return std::make_pair(__res , __begin2 + (__res - __begin1));
88  }
89  else
90  return _GLIBCXX_STD_A::mismatch(__begin1, __end1, __begin2, __pred);
91  }
92 
93  // Public interface
94  template<typename _IIter1, typename _IIter2>
95  inline pair<_IIter1, _IIter2>
96  mismatch(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2)
97  {
101 
102  return __mismatch_switch(__begin1, __end1, __begin2, _EqualTo(),
103  std::__iterator_category(__begin1),
104  std::__iterator_category(__begin2));
105  }
106 
107  // Public interface
108  template<typename _IIter1, typename _IIter2, typename _Predicate>
109  inline pair<_IIter1, _IIter2>
110  mismatch(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2,
111  _Predicate __pred)
112  {
113  return __mismatch_switch(__begin1, __end1, __begin2, __pred,
114  std::__iterator_category(__begin1),
115  std::__iterator_category(__begin2));
116  }
117 
118 #if __cplusplus > 201103L
119  // Sequential fallback.
120  template<typename _InputIterator1, typename _InputIterator2>
121  inline pair<_InputIterator1, _InputIterator2>
122  mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
123  _InputIterator2 __first2, _InputIterator2 __last2,
125  { return _GLIBCXX_STD_A::mismatch(__first1, __last1, __first2, __last2); }
126 
127  // Sequential fallback.
128  template<typename _InputIterator1, typename _InputIterator2,
129  typename _BinaryPredicate>
130  inline pair<_InputIterator1, _InputIterator2>
131  mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
132  _InputIterator2 __first2, _InputIterator2 __last2,
133  _BinaryPredicate __binary_pred,
135  {
136  return _GLIBCXX_STD_A::mismatch(__first1, __last1, __first2, __last2,
137  __binary_pred);
138  }
139 
140  // Sequential fallback for input iterator case
141  template<typename _IIter1, typename _IIter2,
142  typename _Predicate, typename _IteratorTag1, typename _IteratorTag2>
143  inline pair<_IIter1, _IIter2>
144  __mismatch_switch(_IIter1 __begin1, _IIter1 __end1,
145  _IIter2 __begin2, _IIter2 __end2, _Predicate __pred,
146  _IteratorTag1, _IteratorTag2)
147  {
148  return _GLIBCXX_STD_A::mismatch(__begin1, __end1,
149  __begin2, __end2, __pred);
150  }
151 
152  // Parallel mismatch for random access iterators
153  template<typename _RAIter1, typename _RAIter2, typename _Predicate>
154  pair<_RAIter1, _RAIter2>
155  __mismatch_switch(_RAIter1 __begin1, _RAIter1 __end1,
156  _RAIter2 __begin2, _RAIter2 __end2, _Predicate __pred,
157  random_access_iterator_tag, random_access_iterator_tag)
158  {
159  if (_GLIBCXX_PARALLEL_CONDITION(true))
160  {
161  if ((__end2 - __begin2) < (__end1 - __begin1))
162  __end1 = __begin1 + (__end2 - __begin2);
163 
164  _RAIter1 __res =
165  __gnu_parallel::__find_template(__begin1, __end1, __begin2, __pred,
167  __mismatch_selector()).first;
168  return std::make_pair(__res , __begin2 + (__res - __begin1));
169  }
170  else
171  return _GLIBCXX_STD_A::mismatch(__begin1, __end1,
172  __begin2, __end2, __pred);
173  }
174 
175  template<typename _IIter1, typename _IIter2>
176  inline pair<_IIter1, _IIter2>
177  mismatch(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, _IIter2 __end2)
178  {
179  typedef __gnu_parallel::_EqualTo<
182 
183  return __mismatch_switch(__begin1, __end1, __begin2, __end2, _EqualTo(),
184  std::__iterator_category(__begin1),
185  std::__iterator_category(__begin2));
186  }
187 
188  template<typename _InputIterator1, typename _InputIterator2,
189  typename _BinaryPredicate>
190  inline pair<_InputIterator1, _InputIterator2>
191  mismatch(_InputIterator1 __begin1, _InputIterator1 __end1,
192  _InputIterator2 __begin2, _InputIterator2 __end2,
193  _BinaryPredicate __binary_pred)
194  {
195  return __mismatch_switch(__begin1, __end1, __begin2, __end2,
196  __binary_pred,
197  std::__iterator_category(__begin1),
198  std::__iterator_category(__begin2));
199  }
200 #endif
201 
202  // Sequential fallback
203  template<typename _IIter1, typename _IIter2>
204  inline bool
205  equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2,
207  { return _GLIBCXX_STD_A::equal(__begin1, __end1, __begin2); }
208 
209  // Sequential fallback
210  template<typename _IIter1, typename _IIter2, typename _Predicate>
211  inline bool
212  equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2,
213  _Predicate __pred, __gnu_parallel::sequential_tag)
214  { return _GLIBCXX_STD_A::equal(__begin1, __end1, __begin2, __pred); }
215 
216  // Public interface
217  template<typename _IIter1, typename _IIter2>
218  _GLIBCXX20_CONSTEXPR
219  inline bool
220  equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2)
221  {
222 #if __cplusplus > 201703L
223  if (std::is_constant_evaluated())
224  return _GLIBCXX_STD_A::equal(__begin1, __end1, __begin2);
225 #endif
226 
227  return __gnu_parallel::mismatch(__begin1, __end1, __begin2).first
228  == __end1;
229  }
230 
231  // Public interface
232  template<typename _IIter1, typename _IIter2, typename _Predicate>
233  _GLIBCXX20_CONSTEXPR
234  inline bool
235  equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2,
236  _Predicate __pred)
237  {
238 #if __cplusplus > 201703L
239  if (std::is_constant_evaluated())
240  return _GLIBCXX_STD_A::equal(__begin1, __end1, __begin2, __pred);
241 #endif
242 
243  return __gnu_parallel::mismatch(__begin1, __end1, __begin2, __pred).first
244  == __end1;
245  }
246 
247 #if __cplusplus > 201103L
248  // Sequential fallback
249  template<typename _IIter1, typename _IIter2>
250  inline bool
251  equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, _IIter2 __end2,
253  {
254  return _GLIBCXX_STD_A::equal(__begin1, __end1, __begin2, __end2);
255  }
256 
257  // Sequential fallback
258  template<typename _IIter1, typename _IIter2, typename _BinaryPredicate>
259  inline bool
260  equal(_IIter1 __begin1, _IIter1 __end1,
261  _IIter2 __begin2, _IIter2 __end2, _BinaryPredicate __binary_pred,
263  {
264  return _GLIBCXX_STD_A::equal(__begin1, __end1, __begin2, __end2,
265  __binary_pred);
266  }
267 
268  // Sequential fallback for input iterator case
269  template<typename _IIter1, typename _IIter2,
270  typename _Predicate, typename _IteratorTag1, typename _IteratorTag2>
271  inline bool
272  __equal_switch(_IIter1 __begin1, _IIter1 __end1,
273  _IIter2 __begin2, _IIter2 __end2, _Predicate __pred,
274  _IteratorTag1, _IteratorTag2)
275  {
276  return _GLIBCXX_STD_A::equal(__begin1, __end1,
277  __begin2, __end2, __pred);
278  }
279 
280  // Parallel equal for random access iterators
281  template<typename _RAIter1, typename _RAIter2, typename _Predicate>
282  inline bool
283  __equal_switch(_RAIter1 __begin1, _RAIter1 __end1,
284  _RAIter2 __begin2, _RAIter2 __end2, _Predicate __pred,
285  random_access_iterator_tag, random_access_iterator_tag)
286  {
287  if (_GLIBCXX_PARALLEL_CONDITION(true))
288  {
289  if (std::distance(__begin1, __end1)
290  != std::distance(__begin2, __end2))
291  return false;
292 
293  return __gnu_parallel::mismatch(__begin1, __end1, __begin2, __end2,
294  __pred).first == __end1;
295  }
296  else
297  return _GLIBCXX_STD_A::equal(__begin1, __end1,
298  __begin2, __end2, __pred);
299  }
300 
301  template<typename _IIter1, typename _IIter2>
302  _GLIBCXX20_CONSTEXPR
303  inline bool
304  equal(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, _IIter2 __end2)
305  {
306 #if __cplusplus > 201703L
307  if (std::is_constant_evaluated())
308  return _GLIBCXX_STD_A::equal(__begin1, __end1, __begin2, __end2);
309 #endif
310 
311  typedef __gnu_parallel::_EqualTo<
314 
315  return __equal_switch(__begin1, __end1, __begin2, __end2, _EqualTo(),
316  std::__iterator_category(__begin1),
317  std::__iterator_category(__begin2));
318  }
319 
320  template<typename _IIter1, typename _IIter2, typename _BinaryPredicate>
321  _GLIBCXX20_CONSTEXPR
322  inline bool
323  equal(_IIter1 __begin1, _IIter1 __end1,
324  _IIter2 __begin2, _IIter2 __end2, _BinaryPredicate __binary_pred)
325  {
326 #if __cplusplus > 201703L
327  if (std::is_constant_evaluated())
328  return _GLIBCXX_STD_A::equal(__begin1, __end1, __begin2, __end2,
329  __binary_pred);
330 #endif
331 
332  return __equal_switch(__begin1, __end1, __begin2, __end2, __binary_pred,
333  std::__iterator_category(__begin1),
334  std::__iterator_category(__begin2));
335  }
336 #endif // C++14
337 
338  // Sequential fallback
339  template<typename _IIter1, typename _IIter2>
340  inline bool
341  lexicographical_compare(_IIter1 __begin1, _IIter1 __end1,
342  _IIter2 __begin2, _IIter2 __end2,
344  { return _GLIBCXX_STD_A::lexicographical_compare(__begin1, __end1,
345  __begin2, __end2); }
346 
347  // Sequential fallback
348  template<typename _IIter1, typename _IIter2, typename _Predicate>
349  inline bool
350  lexicographical_compare(_IIter1 __begin1, _IIter1 __end1,
351  _IIter2 __begin2, _IIter2 __end2,
352  _Predicate __pred, __gnu_parallel::sequential_tag)
353  { return _GLIBCXX_STD_A::lexicographical_compare(
354  __begin1, __end1, __begin2, __end2, __pred); }
355 
356  // Sequential fallback for input iterator case
357  template<typename _IIter1, typename _IIter2,
358  typename _Predicate, typename _IteratorTag1, typename _IteratorTag2>
359  inline bool
360  __lexicographical_compare_switch(_IIter1 __begin1, _IIter1 __end1,
361  _IIter2 __begin2, _IIter2 __end2,
362  _Predicate __pred,
363  _IteratorTag1, _IteratorTag2)
364  { return _GLIBCXX_STD_A::lexicographical_compare(
365  __begin1, __end1, __begin2, __end2, __pred); }
366 
367  // Parallel lexicographical_compare for random access iterators
368  // Limitation: Both valuetypes must be the same
369  template<typename _RAIter1, typename _RAIter2, typename _Predicate>
370  bool
371  __lexicographical_compare_switch(_RAIter1 __begin1, _RAIter1 __end1,
372  _RAIter2 __begin2, _RAIter2 __end2,
373  _Predicate __pred,
374  random_access_iterator_tag,
375  random_access_iterator_tag)
376  {
377  if (_GLIBCXX_PARALLEL_CONDITION(true))
378  {
379  typedef iterator_traits<_RAIter1> _TraitsType1;
380  typedef typename _TraitsType1::value_type _ValueType1;
381 
382  typedef iterator_traits<_RAIter2> _TraitsType2;
383  typedef typename _TraitsType2::value_type _ValueType2;
384 
385  typedef __gnu_parallel::
386  _EqualFromLess<_ValueType1, _ValueType2, _Predicate>
387  _EqualFromLessCompare;
388 
389  // Longer sequence in first place.
390  if ((__end1 - __begin1) < (__end2 - __begin2))
391  {
392  typedef pair<_RAIter1, _RAIter2> _SpotType;
393  _SpotType __mm = __mismatch_switch(__begin1, __end1, __begin2,
394  _EqualFromLessCompare(__pred),
395  random_access_iterator_tag(),
396  random_access_iterator_tag());
397 
398  return (__mm.first == __end1)
399  || bool(__pred(*__mm.first, *__mm.second));
400  }
401  else
402  {
403  typedef pair<_RAIter2, _RAIter1> _SpotType;
404  _SpotType __mm = __mismatch_switch(__begin2, __end2, __begin1,
405  _EqualFromLessCompare(__pred),
406  random_access_iterator_tag(),
407  random_access_iterator_tag());
408 
409  return (__mm.first != __end2)
410  && bool(__pred(*__mm.second, *__mm.first));
411  }
412  }
413  else
414  return _GLIBCXX_STD_A::lexicographical_compare(
415  __begin1, __end1, __begin2, __end2, __pred);
416  }
417 
418  // Public interface
419  template<typename _IIter1, typename _IIter2>
420  _GLIBCXX20_CONSTEXPR
421  inline bool
422  lexicographical_compare(_IIter1 __begin1, _IIter1 __end1,
423  _IIter2 __begin2, _IIter2 __end2)
424  {
425 #if __cplusplus > 201703L
426  if (std::is_constant_evaluated())
427  return _GLIBCXX_STD_A::lexicographical_compare(__begin1, __end1,
428  __begin2, __end2);
429 #endif
430 
431  typedef iterator_traits<_IIter1> _TraitsType1;
432  typedef typename _TraitsType1::value_type _ValueType1;
433  typedef typename _TraitsType1::iterator_category _IteratorCategory1;
434 
435  typedef iterator_traits<_IIter2> _TraitsType2;
436  typedef typename _TraitsType2::value_type _ValueType2;
437  typedef typename _TraitsType2::iterator_category _IteratorCategory2;
439 
440  return __lexicographical_compare_switch(
441  __begin1, __end1, __begin2, __end2, _LessType(),
442  _IteratorCategory1(), _IteratorCategory2());
443  }
444 
445  // Public interface
446  template<typename _IIter1, typename _IIter2, typename _Predicate>
447  _GLIBCXX20_CONSTEXPR
448  inline bool
449  lexicographical_compare(_IIter1 __begin1, _IIter1 __end1,
450  _IIter2 __begin2, _IIter2 __end2,
451  _Predicate __pred)
452  {
453 #if __cplusplus > 201703L
454  if (std::is_constant_evaluated())
455  return _GLIBCXX_STD_A::lexicographical_compare(__begin1, __end1,
456  __begin2, __end2,
457  __pred);
458 #endif
459 
460  typedef iterator_traits<_IIter1> _TraitsType1;
461  typedef typename _TraitsType1::iterator_category _IteratorCategory1;
462 
463  typedef iterator_traits<_IIter2> _TraitsType2;
464  typedef typename _TraitsType2::iterator_category _IteratorCategory2;
465 
466  return __lexicographical_compare_switch(
467  __begin1, __end1, __begin2, __end2, __pred,
468  _IteratorCategory1(), _IteratorCategory2());
469  }
470 
471 #if __cpp_lib_three_way_comparison
473 #endif
474 
475  // Public interface.
476  template<typename _FIterator1, typename _FIterator2,
477  typename _BinaryPredicate>
478  inline _FIterator1
479  search(_FIterator1 __begin1, _FIterator1 __end1,
480  _FIterator2 __begin2, _FIterator2 __end2,
481  _BinaryPredicate __pred, __gnu_parallel::sequential_tag)
482  { return _GLIBCXX_STD_A::search(
483  __begin1, __end1, __begin2, __end2, __pred); }
484 
485  // Parallel algorithm for random access iterator.
486  template<typename _RAIter1, typename _RAIter2,
487  typename _BinaryPredicate>
488  _RAIter1
489  __search_switch(_RAIter1 __begin1, _RAIter1 __end1,
490  _RAIter2 __begin2, _RAIter2 __end2,
491  _BinaryPredicate __pred,
492  random_access_iterator_tag, random_access_iterator_tag)
493  {
495  static_cast<__gnu_parallel::_SequenceIndex>(__end1 - __begin1)
496  >= __gnu_parallel::_Settings::get().search_minimal_n))
497  return __gnu_parallel::__search_template(__begin1, __end1,
498  __begin2, __end2, __pred);
499  else
500  return search(__begin1, __end1, __begin2, __end2, __pred,
502  }
503 
504  // Sequential fallback for input iterator case
505  template<typename _FIterator1, typename _FIterator2,
506  typename _BinaryPredicate, typename _IteratorTag1,
507  typename _IteratorTag2>
508  inline _FIterator1
509  __search_switch(_FIterator1 __begin1, _FIterator1 __end1,
510  _FIterator2 __begin2, _FIterator2 __end2,
511  _BinaryPredicate __pred, _IteratorTag1, _IteratorTag2)
512  { return search(__begin1, __end1, __begin2, __end2, __pred,
514 
515  // Public interface
516  template<typename _FIterator1, typename _FIterator2,
517  typename _BinaryPredicate>
518  _GLIBCXX20_CONSTEXPR
519  inline _FIterator1
520  search(_FIterator1 __begin1, _FIterator1 __end1,
521  _FIterator2 __begin2, _FIterator2 __end2,
522  _BinaryPredicate __pred)
523  {
524 #if __cplusplus > 201703L
525  if (std::is_constant_evaluated())
526  return _GLIBCXX_STD_A::search(__begin1, __end1, __begin2, __end2,
527  std::move(__pred));
528 #endif
529  return __search_switch(__begin1, __end1, __begin2, __end2, __pred,
530  std::__iterator_category(__begin1),
531  std::__iterator_category(__begin2));
532  }
533 } // end namespace __parallel
534 } // end namespace std
535 
536 #endif /* _GLIBCXX_PARALLEL_ALGOBASE_H */
Sequential helper functions. This file is a GNU parallel extension to the Standard C++ Library.
Parallel implementation base for std::find(), std::equal() and related functions. This file is a GNU ...
_Function objects representing different tasks to be plugged into the parallel find algorithm....
Parallel implementation base for std::search() and std::search_n(). This file is a GNU parallel exten...
#define _GLIBCXX_PARALLEL_CONDITION(__c)
Determine at compile(?)-time if the parallel variant of an algorithm should be called.
Definition: settings.h:97
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
Definition: move.h:138
constexpr auto lexicographical_compare_three_way(_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2, _InputIter2 __last2, _Comp __comp) -> decltype(__comp(*__first1, *__first2))
Performs dictionary comparison on ranges.
constexpr iterator_traits< _Iter >::iterator_category __iterator_category(const _Iter &)
ISO C++ entities toplevel namespace is std.
constexpr iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
GNU parallel code for public use.
uint64_t _SequenceIndex
Unsigned integer to index __elements. The total number of elements for each algorithm must fit into t...
Definition: types.h:117
std::pair< _RAIter1, _RAIter2 > __find_template(_RAIter1 __begin1, _RAIter1 __end1, _RAIter2 __begin2, _Pred __pred, _Selector __selector)
Parallel std::find, switch for different algorithms.
Definition: find.h:60
__RAIter1 __search_template(__RAIter1 __begin1, __RAIter1 __end1, __RAIter2 __begin2, __RAIter2 __end2, _Pred __pred)
Parallel std::search.
Definition: search.h:81
Traits class for iterators.
Similar to std::equal_to, but allows two different types.
Definition: base.h:247
Similar to std::less, but allows two different types.
Definition: base.h:255
static const _Settings & get()
Get the global settings.
Forces sequential execution at compile time.
Definition: tags.h:42