Where Online Learning is simpler!
The C and C++ Include Header Files
cat -n /usr/include/c++/15/ext/algorithm
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 */
