libstdc++
ext/algorithm
Go to the documentation of this file.
1 // Algorithm extensions -*- C++ -*-
2 
3 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009
4 // Free Software Foundation, Inc.
5 //
6 // This file is part of the GNU ISO C++ Library. This library is free
7 // software; you can redistribute it and/or modify it under the
8 // terms of the GNU General Public License as published by the
9 // Free Software Foundation; either version 3, or (at your option)
10 // any later version.
11 
12 // This library is distributed in the hope that it will be useful,
13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 // GNU General Public License for more details.
16 
17 // Under Section 7 of GPL version 3, you are granted additional
18 // permissions described in the GCC Runtime Library Exception, version
19 // 3.1, as published by the Free Software Foundation.
20 
21 // You should have received a copy of the GNU General Public License and
22 // a copy of the GCC Runtime Library Exception along with this program;
23 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
24 // <http://www.gnu.org/licenses/>.
25 
26 /*
27  *
28  * Copyright (c) 1994
29  * Hewlett-Packard Company
30  *
31  * Permission to use, copy, modify, distribute and sell this software
32  * and its documentation for any purpose is hereby granted without fee,
33  * provided that the above copyright notice appear in all copies and
34  * that both that copyright notice and this permission notice appear
35  * in supporting documentation. Hewlett-Packard Company makes no
36  * representations about the suitability of this software for any
37  * purpose. It is provided "as is" without express or implied warranty.
38  *
39  *
40  * Copyright (c) 1996
41  * Silicon Graphics Computer Systems, Inc.
42  *
43  * Permission to use, copy, modify, distribute and sell this software
44  * and its documentation for any purpose is hereby granted without fee,
45  * provided that the above copyright notice appear in all copies and
46  * that both that copyright notice and this permission notice appear
47  * in supporting documentation. Silicon Graphics makes no
48  * representations about the suitability of this software for any
49  * purpose. It is provided "as is" without express or implied warranty.
50  */
51 
52 /** @file ext/algorithm
53  * This file is a GNU extension to the Standard C++ Library (possibly
54  * containing extensions from the HP/SGI STL subset).
55  */
56 
57 #ifndef _EXT_ALGORITHM
58 #define _EXT_ALGORITHM 1
59 
60 #pragma GCC system_header
61 
62 #include <algorithm>
63 
64 _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx)
65 
66  using std::ptrdiff_t;
67  using std::min;
68  using std::pair;
69  using std::input_iterator_tag;
70  using std::random_access_iterator_tag;
71  using std::iterator_traits;
72 
73  //--------------------------------------------------
74  // copy_n (not part of the C++ standard)
75 
76  template<typename _InputIterator, typename _Size, typename _OutputIterator>
77  pair<_InputIterator, _OutputIterator>
78  __copy_n(_InputIterator __first, _Size __count,
79  _OutputIterator __result,
80  input_iterator_tag)
81  {
82  for ( ; __count > 0; --__count)
83  {
84  *__result = *__first;
85  ++__first;
86  ++__result;
87  }
88  return pair<_InputIterator, _OutputIterator>(__first, __result);
89  }
90 
91  template<typename _RAIterator, typename _Size, typename _OutputIterator>
92  inline pair<_RAIterator, _OutputIterator>
93  __copy_n(_RAIterator __first, _Size __count,
94  _OutputIterator __result,
95  random_access_iterator_tag)
96  {
97  _RAIterator __last = __first + __count;
98  return pair<_RAIterator, _OutputIterator>(__last, std::copy(__first,
99  __last,
100  __result));
101  }
102 
103  /**
104  * @brief Copies the range [first,first+count) into [result,result+count).
105  * @param first An input iterator.
106  * @param count The number of elements to copy.
107  * @param result An output iterator.
108  * @return A std::pair composed of first+count and result+count.
109  *
110  * This is an SGI extension.
111  * This inline function will boil down to a call to @c memmove whenever
112  * possible. Failing that, if random access iterators are passed, then the
113  * loop count will be known (and therefore a candidate for compiler
114  * optimizations such as unrolling).
115  * @ingroup SGIextensions
116  */
117  template<typename _InputIterator, typename _Size, typename _OutputIterator>
118  inline pair<_InputIterator, _OutputIterator>
119  copy_n(_InputIterator __first, _Size __count, _OutputIterator __result)
120  {
121  // concept requirements
122  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
123  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
124  typename iterator_traits<_InputIterator>::value_type>)
125 
126  return __copy_n(__first, __count, __result,
127  std::__iterator_category(__first));
128  }
129 
130  template<typename _InputIterator1, typename _InputIterator2>
131  int
132  __lexicographical_compare_3way(_InputIterator1 __first1,
133  _InputIterator1 __last1,
134  _InputIterator2 __first2,
135  _InputIterator2 __last2)
136  {
137  while (__first1 != __last1 && __first2 != __last2)
138  {
139  if (*__first1 < *__first2)
140  return -1;
141  if (*__first2 < *__first1)
142  return 1;
143  ++__first1;
144  ++__first2;
145  }
146  if (__first2 == __last2)
147  return !(__first1 == __last1);
148  else
149  return -1;
150  }
151 
152  inline int
153  __lexicographical_compare_3way(const unsigned char* __first1,
154  const unsigned char* __last1,
155  const unsigned char* __first2,
156  const unsigned char* __last2)
157  {
158  const ptrdiff_t __len1 = __last1 - __first1;
159  const ptrdiff_t __len2 = __last2 - __first2;
160  const int __result = __builtin_memcmp(__first1, __first2,
161  min(__len1, __len2));
162  return __result != 0 ? __result
163  : (__len1 == __len2 ? 0 : (__len1 < __len2 ? -1 : 1));
164  }
165 
166  inline int
167  __lexicographical_compare_3way(const char* __first1, const char* __last1,
168  const char* __first2, const char* __last2)
169  {
170 #if CHAR_MAX == SCHAR_MAX
171  return __lexicographical_compare_3way((const signed char*) __first1,
172  (const signed char*) __last1,
173  (const signed char*) __first2,
174  (const signed char*) __last2);
175 #else
176  return __lexicographical_compare_3way((const unsigned char*) __first1,
177  (const unsigned char*) __last1,
178  (const unsigned char*) __first2,
179  (const unsigned char*) __last2);
180 #endif
181  }
182 
183  /**
184  * @brief @c memcmp on steroids.
185  * @param first1 An input iterator.
186  * @param last1 An input iterator.
187  * @param first2 An input iterator.
188  * @param last2 An input iterator.
189  * @return An int, as with @c memcmp.
190  *
191  * The return value will be less than zero if the first range is
192  * "lexigraphically less than" the second, greater than zero if the second
193  * range is "lexigraphically less than" the first, and zero otherwise.
194  * This is an SGI extension.
195  * @ingroup SGIextensions
196  */
197  template<typename _InputIterator1, typename _InputIterator2>
198  int
199  lexicographical_compare_3way(_InputIterator1 __first1,
200  _InputIterator1 __last1,
201  _InputIterator2 __first2,
202  _InputIterator2 __last2)
203  {
204  // concept requirements
205  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
206  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
207  __glibcxx_function_requires(_LessThanComparableConcept<
208  typename iterator_traits<_InputIterator1>::value_type>)
209  __glibcxx_function_requires(_LessThanComparableConcept<
210  typename iterator_traits<_InputIterator2>::value_type>)
211  __glibcxx_requires_valid_range(__first1, __last1);
212  __glibcxx_requires_valid_range(__first2, __last2);
213 
214  return __lexicographical_compare_3way(__first1, __last1, __first2,
215  __last2);
216  }
217 
218  // count and count_if: this version, whose return type is void, was present
219  // in the HP STL, and is retained as an extension for backward compatibility.
220  template<typename _InputIterator, typename _Tp, typename _Size>
221  void
222  count(_InputIterator __first, _InputIterator __last,
223  const _Tp& __value,
224  _Size& __n)
225  {
226  // concept requirements
227  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
228  __glibcxx_function_requires(_EqualityComparableConcept<
229  typename iterator_traits<_InputIterator>::value_type >)
230  __glibcxx_function_requires(_EqualityComparableConcept<_Tp>)
231  __glibcxx_requires_valid_range(__first, __last);
232 
233  for ( ; __first != __last; ++__first)
234  if (*__first == __value)
235  ++__n;
236  }
237 
238  template<typename _InputIterator, typename _Predicate, typename _Size>
239  void
240  count_if(_InputIterator __first, _InputIterator __last,
241  _Predicate __pred,
242  _Size& __n)
243  {
244  // concept requirements
245  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
246  __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
247  typename iterator_traits<_InputIterator>::value_type>)
248  __glibcxx_requires_valid_range(__first, __last);
249 
250  for ( ; __first != __last; ++__first)
251  if (__pred(*__first))
252  ++__n;
253  }
254 
255  // random_sample and random_sample_n (extensions, not part of the standard).
256 
257  /**
258  * This is an SGI extension.
259  * @ingroup SGIextensions
260  * @doctodo
261  */
262  template<typename _ForwardIterator, typename _OutputIterator,
263  typename _Distance>
264  _OutputIterator
265  random_sample_n(_ForwardIterator __first, _ForwardIterator __last,
266  _OutputIterator __out, const _Distance __n)
267  {
268  // concept requirements
269  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
270  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
271  typename iterator_traits<_ForwardIterator>::value_type>)
272  __glibcxx_requires_valid_range(__first, __last);
273 
274  _Distance __remaining = std::distance(__first, __last);
275  _Distance __m = min(__n, __remaining);
276 
277  while (__m > 0)
278  {
279  if ((std::rand() % __remaining) < __m)
280  {
281  *__out = *__first;
282  ++__out;
283  --__m;
284  }
285  --__remaining;
286  ++__first;
287  }
288  return __out;
289  }
290 
291  /**
292  * This is an SGI extension.
293  * @ingroup SGIextensions
294  * @doctodo
295  */
296  template<typename _ForwardIterator, typename _OutputIterator,
297  typename _Distance, typename _RandomNumberGenerator>
298  _OutputIterator
299  random_sample_n(_ForwardIterator __first, _ForwardIterator __last,
300  _OutputIterator __out, const _Distance __n,
301  _RandomNumberGenerator& __rand)
302  {
303  // concept requirements
304  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
305  __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
306  typename iterator_traits<_ForwardIterator>::value_type>)
307  __glibcxx_function_requires(_UnaryFunctionConcept<
308  _RandomNumberGenerator, _Distance, _Distance>)
309  __glibcxx_requires_valid_range(__first, __last);
310 
311  _Distance __remaining = std::distance(__first, __last);
312  _Distance __m = min(__n, __remaining);
313 
314  while (__m > 0)
315  {
316  if (__rand(__remaining) < __m)
317  {
318  *__out = *__first;
319  ++__out;
320  --__m;
321  }
322  --__remaining;
323  ++__first;
324  }
325  return __out;
326  }
327 
328  template<typename _InputIterator, typename _RandomAccessIterator,
329  typename _Distance>
330  _RandomAccessIterator
331  __random_sample(_InputIterator __first, _InputIterator __last,
332  _RandomAccessIterator __out,
333  const _Distance __n)
334  {
335  _Distance __m = 0;
336  _Distance __t = __n;
337  for ( ; __first != __last && __m < __n; ++__m, ++__first)
338  __out[__m] = *__first;
339 
340  while (__first != __last)
341  {
342  ++__t;
343  _Distance __M = std::rand() % (__t);
344  if (__M < __n)
345  __out[__M] = *__first;
346  ++__first;
347  }
348  return __out + __m;
349  }
350 
351  template<typename _InputIterator, typename _RandomAccessIterator,
352  typename _RandomNumberGenerator, typename _Distance>
353  _RandomAccessIterator
354  __random_sample(_InputIterator __first, _InputIterator __last,
355  _RandomAccessIterator __out,
356  _RandomNumberGenerator& __rand,
357  const _Distance __n)
358  {
359  // concept requirements
360  __glibcxx_function_requires(_UnaryFunctionConcept<
361  _RandomNumberGenerator, _Distance, _Distance>)
362 
363  _Distance __m = 0;
364  _Distance __t = __n;
365  for ( ; __first != __last && __m < __n; ++__m, ++__first)
366  __out[__m] = *__first;
367 
368  while (__first != __last)
369  {
370  ++__t;
371  _Distance __M = __rand(__t);
372  if (__M < __n)
373  __out[__M] = *__first;
374  ++__first;
375  }
376  return __out + __m;
377  }
378 
379  /**
380  * This is an SGI extension.
381  * @ingroup SGIextensions
382  * @doctodo
383  */
384  template<typename _InputIterator, typename _RandomAccessIterator>
385  inline _RandomAccessIterator
386  random_sample(_InputIterator __first, _InputIterator __last,
387  _RandomAccessIterator __out_first,
388  _RandomAccessIterator __out_last)
389  {
390  // concept requirements
391  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
392  __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
393  _RandomAccessIterator>)
394  __glibcxx_requires_valid_range(__first, __last);
395  __glibcxx_requires_valid_range(__out_first, __out_last);
396 
397  return __random_sample(__first, __last,
398  __out_first, __out_last - __out_first);
399  }
400 
401  /**
402  * This is an SGI extension.
403  * @ingroup SGIextensions
404  * @doctodo
405  */
406  template<typename _InputIterator, typename _RandomAccessIterator,
407  typename _RandomNumberGenerator>
408  inline _RandomAccessIterator
409  random_sample(_InputIterator __first, _InputIterator __last,
410  _RandomAccessIterator __out_first,
411  _RandomAccessIterator __out_last,
412  _RandomNumberGenerator& __rand)
413  {
414  // concept requirements
415  __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
416  __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
417  _RandomAccessIterator>)
418  __glibcxx_requires_valid_range(__first, __last);
419  __glibcxx_requires_valid_range(__out_first, __out_last);
420 
421  return __random_sample(__first, __last,
422  __out_first, __rand,
423  __out_last - __out_first);
424  }
425 
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 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 iterator_traits<_RandomAccessIterator>::value_type,
460  typename iterator_traits<_RandomAccessIterator>::value_type>)
461  __glibcxx_requires_valid_range(__first, __last);
462 
463  return std::__is_heap(__first, __comp, __last - __first);
464  }
465 
466  // is_sorted, a predicated testing whether a range is sorted in
467  // nondescending order. This is an extension, not part of the C++
468  // standard.
469 
470  /**
471  * This is an SGI extension.
472  * @ingroup SGIextensions
473  * @doctodo
474  */
475  template<typename _ForwardIterator>
476  bool
477  is_sorted(_ForwardIterator __first, _ForwardIterator __last)
478  {
479  // concept requirements
480  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
481  __glibcxx_function_requires(_LessThanComparableConcept<
482  typename iterator_traits<_ForwardIterator>::value_type>)
483  __glibcxx_requires_valid_range(__first, __last);
484 
485  if (__first == __last)
486  return true;
487 
488  _ForwardIterator __next = __first;
489  for (++__next; __next != __last; __first = __next, ++__next)
490  if (*__next < *__first)
491  return false;
492  return true;
493  }
494 
495  /**
496  * This is an SGI extension.
497  * @ingroup SGIextensions
498  * @doctodo
499  */
500  template<typename _ForwardIterator, typename _StrictWeakOrdering>
501  bool
502  is_sorted(_ForwardIterator __first, _ForwardIterator __last,
503  _StrictWeakOrdering __comp)
504  {
505  // concept requirements
506  __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
507  __glibcxx_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering,
508  typename iterator_traits<_ForwardIterator>::value_type,
509  typename iterator_traits<_ForwardIterator>::value_type>)
510  __glibcxx_requires_valid_range(__first, __last);
511 
512  if (__first == __last)
513  return true;
514 
515  _ForwardIterator __next = __first;
516  for (++__next; __next != __last; __first = __next, ++__next)
517  if (__comp(*__next, *__first))
518  return false;
519  return true;
520  }
521 
522 _GLIBCXX_END_NAMESPACE
523 
524 #endif /* _EXT_ALGORITHM */
iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
bool is_sorted(_ForwardIterator __first, _ForwardIterator __last, _StrictWeakOrdering __comp)
Definition: ext/algorithm:502
bool is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _StrictWeakOrdering __comp)
Definition: ext/algorithm:452
_OutputIterator random_sample_n(_ForwardIterator __first, _ForwardIterator __last, _OutputIterator __out, const _Distance __n, _RandomNumberGenerator &__rand)
Definition: ext/algorithm:299
int lexicographical_compare_3way(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2)
memcmp on steroids.
Definition: ext/algorithm:199
iterator_traits< _Iter >::iterator_category __iterator_category(const _Iter &)
const _Tp & min(const _Tp &, const _Tp &)
This does what you think it does.
Definition: stl_algobase.h:186
pair< _InputIterator, _OutputIterator > copy_n(_InputIterator __first, _Size __count, _OutputIterator __result)
Copies the range [first,first+count) into [result,result+count).
Definition: ext/algorithm:119
_RandomAccessIterator random_sample(_InputIterator __first, _InputIterator __last, _RandomAccessIterator __out_first, _RandomAccessIterator __out_last, _RandomNumberGenerator &__rand)
Definition: ext/algorithm:409