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