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