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
67namespace __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 */