libstdc++
ext/algorithm
Go to the documentation of this file.
1 // Algorithm extensions -*- C++ -*-
2 
3 // Copyright (C) 2001-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
7 // terms of the GNU General Public License as published by the
8 // Free Software Foundation; either version 3, or (at your option)
9 // any later version.
10 
11 // This library is distributed in the hope that it will be useful,
12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 // GNU 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 /*
26  *
27  * Copyright (c) 1994
28  * Hewlett-Packard Company
29  *
30  * Permission to use, copy, modify, distribute and sell this software
31  * and its documentation for any purpose is hereby granted without fee,
32  * provided that the above copyright notice appear in all copies and
33  * that both that copyright notice and this permission notice appear
34  * in supporting documentation. Hewlett-Packard Company makes no
35  * representations about the suitability of this software for any
36  * purpose. It is provided "as is" without express or implied warranty.
37  *
38  *
39  * Copyright (c) 1996
40  * Silicon Graphics Computer Systems, Inc.
41  *
42  * Permission to use, copy, modify, distribute and sell this software
43  * and its documentation for any purpose is hereby granted without fee,
44  * provided that the above copyright notice appear in all copies and
45  * that both that copyright notice and this permission notice appear
46  * in supporting documentation. Silicon Graphics makes no
47  * representations about the suitability of this software for any
48  * purpose. It is provided "as is" without express or implied warranty.
49  */
50 
51 /** @file ext/algorithm
52  * This file is a GNU extension to the Standard C++ Library (possibly
53  * containing extensions from the HP/SGI STL subset).
54  */
55 
56 #ifndef _EXT_ALGORITHM
57 #define _EXT_ALGORITHM 1
58 
59 #ifdef _GLIBCXX_SYSHDR
60 #pragma GCC system_header
61 #endif
62 
63 #include <bits/requires_hosted.h> // GNU extensions are currently omitted
64 
65 #include <algorithm>
66 
67 namespace __gnu_cxx _GLIBCXX_VISIBILITY(default)
68 {
69 _GLIBCXX_BEGIN_NAMESPACE_VERSION
70 
71  //--------------------------------------------------
72  // copy_n (not part of the C++ standard)
73 
74  template<typename _InputIterator, typename _Size, typename _OutputIterator>
75  std::pair<_InputIterator, _OutputIterator>
76  __copy_n(_InputIterator __first, _Size __count,
77  _OutputIterator __result,
78  std::input_iterator_tag)
79  {
80  for ( ; __count > 0; --__count)
81  {
82  *__result = *__first;
83  ++__first;
84  ++__result;
85  }
86  return std::pair<_InputIterator, _OutputIterator>(__first, __result);
87  }
88 
89  template<typename _RAIterator, typename _Size, typename _OutputIterator>
90  inline std::pair<_RAIterator, _OutputIterator>
91  __copy_n(_RAIterator __first, _Size __count,
92  _OutputIterator __result,
93  std::random_access_iterator_tag)
94  {
95  _RAIterator __last = __first + __count;
96  return std::pair<_RAIterator, _OutputIterator>(__last, std::copy(__first,
97  __last,
98  __result));
99  }
100 
101  /**
102  * @brief Copies the range [first,first+count) into [result,result+count).
103  * @param __first An input iterator.
104  * @param __count The number of elements to copy.
105  * @param __result An output iterator.
106  * @return A std::pair composed of first+count and result+count.
107  *
108  * This is an SGI extension.
109  * This inline function will boil down to a call to @c memmove whenever
110  * possible. Failing that, if random access iterators are passed, then the
111  * loop count will be known (and therefore a candidate for compiler
112  * optimizations such as unrolling).
113  * @ingroup SGIextensions
114  */
115  template<typename _InputIterator, typename _Size, typename _OutputIterator>
116  inline std::pair<_InputIterator, _OutputIterator>
117  copy_n(_InputIterator __first, _Size __count, _OutputIterator __result)
118  {
119  // concept requirements
120  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
121  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
122  typename std::iterator_traits<_InputIterator>::value_type>)
123 
124  return __gnu_cxx::__copy_n(__first, __count, __result,
125  std::__iterator_category(__first));
126  }
127 
128  template<typename _InputIterator1, typename _InputIterator2>
129  int
130  __lexicographical_compare_3way(_InputIterator1 __first1,
131  _InputIterator1 __last1,
132  _InputIterator2 __first2,
133  _InputIterator2 __last2)
134  {
135  while (__first1 != __last1 && __first2 != __last2)
136  {
137  if (*__first1 < *__first2)
138  return -1;
139  if (*__first2 < *__first1)
140  return 1;
141  ++__first1;
142  ++__first2;
143  }
144  if (__first2 == __last2)
145  return !(__first1 == __last1);
146  else
147  return -1;
148  }
149 
150  inline int
151  __lexicographical_compare_3way(const unsigned char* __first1,
152  const unsigned char* __last1,
153  const unsigned char* __first2,
154  const unsigned char* __last2)
155  {
156  const std::ptrdiff_t __len1 = __last1 - __first1;
157  const std::ptrdiff_t __len2 = __last2 - __first2;
158  const int __result = __builtin_memcmp(__first1, __first2,
159  (std::min)(__len1, __len2));
160  return __result != 0 ? __result
161  : (__len1 == __len2 ? 0 : (__len1 < __len2 ? -1 : 1));
162  }
163 
164  inline int
165  __lexicographical_compare_3way(const char* __first1, const char* __last1,
166  const char* __first2, const char* __last2)
167  {
168 #if CHAR_MAX == SCHAR_MAX
169  return __lexicographical_compare_3way((const signed char*) __first1,
170  (const signed char*) __last1,
171  (const signed char*) __first2,
172  (const signed char*) __last2);
173 #else
174  return __lexicographical_compare_3way((const unsigned char*) __first1,
175  (const unsigned char*) __last1,
176  (const unsigned char*) __first2,
177  (const unsigned char*) __last2);
178 #endif
179  }
180 
181  /**
182  * @brief @c memcmp on steroids.
183  * @param __first1 An input iterator.
184  * @param __last1 An input iterator.
185  * @param __first2 An input iterator.
186  * @param __last2 An input iterator.
187  * @return An int, as with @c memcmp.
188  *
189  * The return value will be less than zero if the first range is
190  * <em>lexigraphically less than</em> the second, greater than zero
191  * if the second range is <em>lexigraphically less than</em> the
192  * first, and zero otherwise.
193  * This is an SGI extension.
194  * @ingroup SGIextensions
195  */
196  template<typename _InputIterator1, typename _InputIterator2>
197  int
198  lexicographical_compare_3way(_InputIterator1 __first1,
199  _InputIterator1 __last1,
200  _InputIterator2 __first2,
201  _InputIterator2 __last2)
202  {
203  // concept requirements
204  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
205  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
206  __glibcxx_function_requires(_LessThanComparableConcept<
207  typename std::iterator_traits<_InputIterator1>::value_type>)
208  __glibcxx_function_requires(_LessThanComparableConcept<
209  typename std::iterator_traits<_InputIterator2>::value_type>)
210  __glibcxx_requires_valid_range(__first1, __last1);
211  __glibcxx_requires_valid_range(__first2, __last2);
212 
213  return __lexicographical_compare_3way(__first1, __last1, __first2,
214  __last2);
215  }
216 
217  // count and count_if: this version, whose return type is void, was present
218  // in the HP STL, and is retained as an extension for backward compatibility.
219  template<typename _InputIterator, typename _Tp, typename _Size>
220  void
221  count(_InputIterator __first, _InputIterator __last,
222  const _Tp& __value,
223  _Size& __n)
224  {
225  // concept requirements
226  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
227  __glibcxx_function_requires(_EqualityComparableConcept<
228  typename std::iterator_traits<_InputIterator>::value_type >)
229  __glibcxx_function_requires(_EqualityComparableConcept<_Tp>)
230  __glibcxx_requires_valid_range(__first, __last);
231 
232  for ( ; __first != __last; ++__first)
233  if (*__first == __value)
234  ++__n;
235  }
236 
237  template<typename _InputIterator, typename _Predicate, typename _Size>
238  void
239  count_if(_InputIterator __first, _InputIterator __last,
240  _Predicate __pred,
241  _Size& __n)
242  {
243  // concept requirements
244  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
245  __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
246  typename std::iterator_traits<_InputIterator>::value_type>)
247  __glibcxx_requires_valid_range(__first, __last);
248 
249  for ( ; __first != __last; ++__first)
250  if (__pred(*__first))
251  ++__n;
252  }
253 
254  // random_sample and random_sample_n (extensions, not part of the standard).
255 
256  /**
257  * This is an SGI extension.
258  * @ingroup SGIextensions
259  * @doctodo
260  */
261  template<typename _ForwardIterator, typename _OutputIterator,
262  typename _Distance>
263  _OutputIterator
264  random_sample_n(_ForwardIterator __first, _ForwardIterator __last,
265  _OutputIterator __out, const _Distance __n)
266  {
267  // concept requirements
268  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
269  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
270  typename std::iterator_traits<_ForwardIterator>::value_type>)
271  __glibcxx_requires_valid_range(__first, __last);
272 
273  _Distance __remaining = std::distance(__first, __last);
274  _Distance __m = (std::min)(__n, __remaining);
275 
276  while (__m > 0)
277  {
278  if ((std::rand() % __remaining) < __m)
279  {
280  *__out = *__first;
281  ++__out;
282  --__m;
283  }
284  --__remaining;
285  ++__first;
286  }
287  return __out;
288  }
289 
290  /**
291  * This is an SGI extension.
292  * @ingroup SGIextensions
293  * @doctodo
294  */
295  template<typename _ForwardIterator, typename _OutputIterator,
296  typename _Distance, typename _RandomNumberGenerator>
297  _OutputIterator
298  random_sample_n(_ForwardIterator __first, _ForwardIterator __last,
299  _OutputIterator __out, const _Distance __n,
300  _RandomNumberGenerator& __rand)
301  {
302  // concept requirements
303  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
304  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
305  typename std::iterator_traits<_ForwardIterator>::value_type>)
306  __glibcxx_function_requires(_UnaryFunctionConcept<
307  _RandomNumberGenerator, _Distance, _Distance>)
308  __glibcxx_requires_valid_range(__first, __last);
309 
310  _Distance __remaining = std::distance(__first, __last);
311  _Distance __m = (std::min)(__n, __remaining);
312 
313  while (__m > 0)
314  {
315  if (__rand(__remaining) < __m)
316  {
317  *__out = *__first;
318  ++__out;
319  --__m;
320  }
321  --__remaining;
322  ++__first;
323  }
324  return __out;
325  }
326 
327  template<typename _InputIterator, typename _RandomAccessIterator,
328  typename _Distance>
329  _RandomAccessIterator
330  __random_sample(_InputIterator __first, _InputIterator __last,
331  _RandomAccessIterator __out,
332  const _Distance __n)
333  {
334  _Distance __m = 0;
335  _Distance __t = __n;
336  for ( ; __first != __last && __m < __n; ++__m, ++__first)
337  __out[__m] = *__first;
338 
339  while (__first != __last)
340  {
341  ++__t;
342  _Distance __M = std::rand() % (__t);
343  if (__M < __n)
344  __out[__M] = *__first;
345  ++__first;
346  }
347  return __out + __m;
348  }
349 
350  template<typename _InputIterator, typename _RandomAccessIterator,
351  typename _RandomNumberGenerator, typename _Distance>
352  _RandomAccessIterator
353  __random_sample(_InputIterator __first, _InputIterator __last,
354  _RandomAccessIterator __out,
355  _RandomNumberGenerator& __rand,
356  const _Distance __n)
357  {
358  // concept requirements
359  __glibcxx_function_requires(_UnaryFunctionConcept<
360  _RandomNumberGenerator, _Distance, _Distance>)
361 
362  _Distance __m = 0;
363  _Distance __t = __n;
364  for ( ; __first != __last && __m < __n; ++__m, ++__first)
365  __out[__m] = *__first;
366 
367  while (__first != __last)
368  {
369  ++__t;
370  _Distance __M = __rand(__t);
371  if (__M < __n)
372  __out[__M] = *__first;
373  ++__first;
374  }
375  return __out + __m;
376  }
377 
378  /**
379  * This is an SGI extension.
380  * @ingroup SGIextensions
381  * @doctodo
382  */
383  template<typename _InputIterator, typename _RandomAccessIterator>
384  inline _RandomAccessIterator
385  random_sample(_InputIterator __first, _InputIterator __last,
386  _RandomAccessIterator __out_first,
387  _RandomAccessIterator __out_last)
388  {
389  // concept requirements
390  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
391  __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
392  _RandomAccessIterator>)
393  __glibcxx_requires_valid_range(__first, __last);
394  __glibcxx_requires_valid_range(__out_first, __out_last);
395 
396  return __random_sample(__first, __last,
397  __out_first, __out_last - __out_first);
398  }
399 
400  /**
401  * This is an SGI extension.
402  * @ingroup SGIextensions
403  * @doctodo
404  */
405  template<typename _InputIterator, typename _RandomAccessIterator,
406  typename _RandomNumberGenerator>
407  inline _RandomAccessIterator
408  random_sample(_InputIterator __first, _InputIterator __last,
409  _RandomAccessIterator __out_first,
410  _RandomAccessIterator __out_last,
411  _RandomNumberGenerator& __rand)
412  {
413  // concept requirements
414  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
415  __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
416  _RandomAccessIterator>)
417  __glibcxx_requires_valid_range(__first, __last);
418  __glibcxx_requires_valid_range(__out_first, __out_last);
419 
420  return __random_sample(__first, __last,
421  __out_first, __rand,
422  __out_last - __out_first);
423  }
424 
425 #if __cplusplus >= 201103L
426  using std::is_heap;
427 #else
428  /**
429  * This is an SGI extension.
430  * @ingroup SGIextensions
431  * @doctodo
432  */
433  template<typename _RandomAccessIterator>
434  inline bool
435  is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
436  {
437  // concept requirements
438  __glibcxx_function_requires(_RandomAccessIteratorConcept<
439  _RandomAccessIterator>)
440  __glibcxx_function_requires(_LessThanComparableConcept<
441  typename std::iterator_traits<_RandomAccessIterator>::value_type>)
442  __glibcxx_requires_valid_range(__first, __last);
443 
444  return std::__is_heap(__first, __last - __first);
445  }
446 
447  /**
448  * This is an SGI extension.
449  * @ingroup SGIextensions
450  * @doctodo
451  */
452  template<typename _RandomAccessIterator, typename _StrictWeakOrdering>
453  inline bool
454  is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
455  _StrictWeakOrdering __comp)
456  {
457  // concept requirements
458  __glibcxx_function_requires(_RandomAccessIteratorConcept<
459  _RandomAccessIterator>)
460  __glibcxx_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering,
461  typename std::iterator_traits<_RandomAccessIterator>::value_type,
462  typename std::iterator_traits<_RandomAccessIterator>::value_type>)
463  __glibcxx_requires_valid_range(__first, __last);
464 
465  return std::__is_heap(__first, __comp, __last - __first);
466  }
467 #endif
468 
469 #if __cplusplus >= 201103L
470  using std::is_sorted;
471 #else
472  // is_sorted, a predicated testing whether a range is sorted in
473  // nondescending order. This is an extension, not part of the C++
474  // standard.
475 
476  /**
477  * This is an SGI extension.
478  * @ingroup SGIextensions
479  * @doctodo
480  */
481  template<typename _ForwardIterator>
482  bool
483  is_sorted(_ForwardIterator __first, _ForwardIterator __last)
484  {
485  // concept requirements
486  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
487  __glibcxx_function_requires(_LessThanComparableConcept<
488  typename std::iterator_traits<_ForwardIterator>::value_type>)
489  __glibcxx_requires_valid_range(__first, __last);
490 
491  if (__first == __last)
492  return true;
493 
494  _ForwardIterator __next = __first;
495  for (++__next; __next != __last; __first = __next, ++__next)
496  if (*__next < *__first)
497  return false;
498  return true;
499  }
500 
501  /**
502  * This is an SGI extension.
503  * @ingroup SGIextensions
504  * @doctodo
505  */
506  template<typename _ForwardIterator, typename _StrictWeakOrdering>
507  bool
508  is_sorted(_ForwardIterator __first, _ForwardIterator __last,
509  _StrictWeakOrdering __comp)
510  {
511  // concept requirements
512  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
513  __glibcxx_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering,
514  typename std::iterator_traits<_ForwardIterator>::value_type,
515  typename std::iterator_traits<_ForwardIterator>::value_type>)
516  __glibcxx_requires_valid_range(__first, __last);
517 
518  if (__first == __last)
519  return true;
520 
521  _ForwardIterator __next = __first;
522  for (++__next; __next != __last; __first = __next, ++__next)
523  if (__comp(*__next, *__first))
524  return false;
525  return true;
526  }
527 #endif // C++11
528 
529  /**
530  * @brief Find the median of three values.
531  * @param __a A value.
532  * @param __b A value.
533  * @param __c A value.
534  * @return One of @p a, @p b or @p c.
535  *
536  * If @c {l,m,n} is some convolution of @p {a,b,c} such that @c l<=m<=n
537  * then the value returned will be @c m.
538  * This is an SGI extension.
539  * @ingroup SGIextensions
540  */
541  template<typename _Tp>
542  const _Tp&
543  __median(const _Tp& __a, const _Tp& __b, const _Tp& __c)
544  {
545  // concept requirements
546  __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
547  if (__a < __b)
548  if (__b < __c)
549  return __b;
550  else if (__a < __c)
551  return __c;
552  else
553  return __a;
554  else if (__a < __c)
555  return __a;
556  else if (__b < __c)
557  return __c;
558  else
559  return __b;
560  }
561 
562  /**
563  * @brief Find the median of three values using a predicate for comparison.
564  * @param __a A value.
565  * @param __b A value.
566  * @param __c A value.
567  * @param __comp A binary predicate.
568  * @return One of @p a, @p b or @p c.
569  *
570  * If @c {l,m,n} is some convolution of @p {a,b,c} such that @p comp(l,m)
571  * and @p comp(m,n) are both true then the value returned will be @c m.
572  * This is an SGI extension.
573  * @ingroup SGIextensions
574  */
575  template<typename _Tp, typename _Compare>
576  const _Tp&
577  __median(const _Tp& __a, const _Tp& __b, const _Tp& __c, _Compare __comp)
578  {
579  // concept requirements
580  __glibcxx_function_requires(_BinaryFunctionConcept<_Compare, bool,
581  _Tp, _Tp>)
582  if (__comp(__a, __b))
583  if (__comp(__b, __c))
584  return __b;
585  else if (__comp(__a, __c))
586  return __c;
587  else
588  return __a;
589  else if (__comp(__a, __c))
590  return __a;
591  else if (__comp(__b, __c))
592  return __c;
593  else
594  return __b;
595  }
596 
597 _GLIBCXX_END_NAMESPACE_VERSION
598 } // namespace
599 
600 #endif /* _EXT_ALGORITHM */