Where Online Learning is simpler!
The C and C++ Include Header Files
cat -n /usr/include/c++/15/bits/stl_algo.h
1 // Algorithm implementation -*- 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 bits/stl_algo.h 52 * This is an internal header file, included by other library headers. 53 * Do not attempt to use it directly. @headername{algorithm} 54 */ 55 56 #ifndef _STL_ALGO_H 57 #define _STL_ALGO_H 1 58 59 #include <bits/algorithmfwd.h> 60 #include <bits/stl_algobase.h> 61 #include <bits/stl_heap.h> 62 #include <bits/predefined_ops.h> 63 64 #if __cplusplus >= 201103L 65 #include <bits/uniform_int_dist.h> 66 #endif 67 68 #if _GLIBCXX_HOSTED 69 # include <bits/stl_tempbuf.h> // for _Temporary_buffer 70 # if (__cplusplus <= 201103L || _GLIBCXX_USE_DEPRECATED) 71 # include <cstdlib> // for rand 72 # endif 73 #endif 74 75 #pragma GCC diagnostic push 76 #pragma GCC diagnostic ignored "-Wc++11-extensions" // inline namespace 77 78 // See concept_check.h for the __glibcxx_*_requires macros. 79 80 namespace std _GLIBCXX_VISIBILITY(default) 81 { 82 _GLIBCXX_BEGIN_NAMESPACE_VERSION 83 84 /// Swaps the median value of *__a, *__b and *__c under __comp to *__result 85 template<typename _Iterator, typename _Compare> 86 _GLIBCXX20_CONSTEXPR 87 void 88 __move_median_to_first(_Iterator __result,_Iterator __a, _Iterator __b, 89 _Iterator __c, _Compare __comp) 90 { 91 if (__comp(__a, __b)) 92 { 93 if (__comp(__b, __c)) 94 std::iter_swap(__result, __b); 95 else if (__comp(__a, __c)) 96 std::iter_swap(__result, __c); 97 else 98 std::iter_swap(__result, __a); 99 } 100 else if (__comp(__a, __c)) 101 std::iter_swap(__result, __a); 102 else if (__comp(__b, __c)) 103 std::iter_swap(__result, __c); 104 else 105 std::iter_swap(__result, __b); 106 } 107 108 /// Provided for stable_partition to use. 109 template<typename _InputIterator, typename _Predicate> 110 _GLIBCXX20_CONSTEXPR 111 inline _InputIterator 112 __find_if_not(_InputIterator __first, _InputIterator __last, 113 _Predicate __pred) 114 { 115 return std::__find_if(__first, __last, 116 __gnu_cxx::__ops::__negate(__pred)); 117 } 118 119 /// Like find_if_not(), but uses and updates a count of the 120 /// remaining range length instead of comparing against an end 121 /// iterator. 122 template<typename _InputIterator, typename _Predicate, typename _Distance> 123 _GLIBCXX20_CONSTEXPR 124 _InputIterator 125 __find_if_not_n(_InputIterator __first, _Distance& __len, _Predicate __pred) 126 { 127 for (; __len; --__len, (void) ++__first) 128 if (!__pred(__first)) 129 break; 130 return __first; 131 } 132 133 // set_difference 134 // set_intersection 135 // set_symmetric_difference 136 // set_union 137 // for_each 138 // find 139 // find_if 140 // find_first_of 141 // adjacent_find 142 // count 143 // count_if 144 // search 145 // search_n 146 147 /** 148 * This is an helper function for search_n overloaded for forward iterators. 149 */ 150 template<typename _ForwardIterator, typename _Integer, 151 typename _UnaryPredicate> 152 _GLIBCXX20_CONSTEXPR 153 _ForwardIterator 154 __search_n_aux(_ForwardIterator __first, _ForwardIterator __last, 155 _Integer __count, _UnaryPredicate __unary_pred, 156 std::forward_iterator_tag) 157 { 158 __first = std::__find_if(__first, __last, __unary_pred); 159 while (__first != __last) 160 { 161 typename iterator_traits<_ForwardIterator>::difference_type 162 __n = __count; 163 _ForwardIterator __i = __first; 164 ++__i; 165 while (__i != __last && __n != 1 && __unary_pred(__i)) 166 { 167 ++__i; 168 --__n; 169 } 170 if (__n == 1) 171 return __first; 172 if (__i == __last) 173 return __last; 174 __first = std::__find_if(++__i, __last, __unary_pred); 175 } 176 return __last; 177 } 178 179 /** 180 * This is an helper function for search_n overloaded for random access 181 * iterators. 182 */ 183 template<typename _RandomAccessIter, typename _Integer, 184 typename _UnaryPredicate> 185 _GLIBCXX20_CONSTEXPR 186 _RandomAccessIter 187 __search_n_aux(_RandomAccessIter __first, _RandomAccessIter __last, 188 _Integer __count, _UnaryPredicate __unary_pred, 189 std::random_access_iterator_tag) 190 { 191 typedef typename std::iterator_traits<_RandomAccessIter>::difference_type 192 _DistanceType; 193 194 _DistanceType __tailSize = __last - __first; 195 _DistanceType __remainder = __count; 196 197 while (__remainder <= __tailSize) // the main loop... 198 { 199 __first += __remainder; 200 __tailSize -= __remainder; 201 // __first here is always pointing to one past the last element of 202 // next possible match. 203 _RandomAccessIter __backTrack = __first; 204 while (__unary_pred(--__backTrack)) 205 { 206 if (--__remainder == 0) 207 return (__first - __count); // Success 208 } 209 __remainder = __count + 1 - (__first - __backTrack); 210 } 211 return __last; // Failure 212 } 213 214 template<typename _ForwardIterator, typename _Integer, 215 typename _UnaryPredicate> 216 _GLIBCXX20_CONSTEXPR 217 _ForwardIterator 218 __search_n(_ForwardIterator __first, _ForwardIterator __last, 219 _Integer __count, 220 _UnaryPredicate __unary_pred) 221 { 222 if (__count <= 0) 223 return __first; 224 225 if (__count == 1) 226 return std::__find_if(__first, __last, __unary_pred); 227 228 return std::__search_n_aux(__first, __last, __count, __unary_pred, 229 std::__iterator_category(__first)); 230 } 231 232 // find_end for forward iterators. 233 template<typename _ForwardIterator1, typename _ForwardIterator2, 234 typename _BinaryPredicate> 235 _GLIBCXX20_CONSTEXPR 236 _ForwardIterator1 237 __find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 238 _ForwardIterator2 __first2, _ForwardIterator2 __last2, 239 forward_iterator_tag, forward_iterator_tag, 240 _BinaryPredicate __comp) 241 { 242 if (__first2 == __last2) 243 return __last1; 244 245 _ForwardIterator1 __result = __last1; 246 while (1) 247 { 248 _ForwardIterator1 __new_result 249 = std::__search(__first1, __last1, __first2, __last2, __comp); 250 if (__new_result == __last1) 251 return __result; 252 else 253 { 254 __result = __new_result; 255 __first1 = __new_result; 256 ++__first1; 257 } 258 } 259 } 260 261 // find_end for bidirectional iterators (much faster). 262 template<typename _BidirectionalIterator1, typename _BidirectionalIterator2, 263 typename _BinaryPredicate> 264 _GLIBCXX20_CONSTEXPR 265 _BidirectionalIterator1 266 __find_end(_BidirectionalIterator1 __first1, 267 _BidirectionalIterator1 __last1, 268 _BidirectionalIterator2 __first2, 269 _BidirectionalIterator2 __last2, 270 bidirectional_iterator_tag, bidirectional_iterator_tag, 271 _BinaryPredicate __comp) 272 { 273 // concept requirements 274 __glibcxx_function_requires(_BidirectionalIteratorConcept< 275 _BidirectionalIterator1>) 276 __glibcxx_function_requires(_BidirectionalIteratorConcept< 277 _BidirectionalIterator2>) 278 279 typedef reverse_iterator<_BidirectionalIterator1> _RevIterator1; 280 typedef reverse_iterator<_BidirectionalIterator2> _RevIterator2; 281 282 _RevIterator1 __rlast1(__first1); 283 _RevIterator2 __rlast2(__first2); 284 _RevIterator1 __rresult = std::__search(_RevIterator1(__last1), __rlast1, 285 _RevIterator2(__last2), __rlast2, 286 __comp); 287 288 if (__rresult == __rlast1) 289 return __last1; 290 else 291 { 292 _BidirectionalIterator1 __result = __rresult.base(); 293 std::advance(__result, -std::distance(__first2, __last2)); 294 return __result; 295 } 296 } 297 298 /** 299 * @brief Find last matching subsequence in a sequence. 300 * @ingroup non_mutating_algorithms 301 * @param __first1 Start of range to search. 302 * @param __last1 End of range to search. 303 * @param __first2 Start of sequence to match. 304 * @param __last2 End of sequence to match. 305 * @return The last iterator @c i in the range 306 * @p [__first1,__last1-(__last2-__first2)) such that @c *(i+N) == 307 * @p *(__first2+N) for each @c N in the range @p 308 * [0,__last2-__first2), or @p __last1 if no such iterator exists. 309 * 310 * Searches the range @p [__first1,__last1) for a sub-sequence that 311 * compares equal value-by-value with the sequence given by @p 312 * [__first2,__last2) and returns an iterator to the __first 313 * element of the sub-sequence, or @p __last1 if the sub-sequence 314 * is not found. The sub-sequence will be the last such 315 * subsequence contained in [__first1,__last1). 316 * 317 * Because the sub-sequence must lie completely within the range @p 318 * [__first1,__last1) it must start at a position less than @p 319 * __last1-(__last2-__first2) where @p __last2-__first2 is the 320 * length of the sub-sequence. This means that the returned 321 * iterator @c i will be in the range @p 322 * [__first1,__last1-(__last2-__first2)) 323 */ 324 template<typename _ForwardIterator1, typename _ForwardIterator2> 325 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR 326 inline _ForwardIterator1 327 find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 328 _ForwardIterator2 __first2, _ForwardIterator2 __last2) 329 { 330 // concept requirements 331 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>) 332 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>) 333 __glibcxx_function_requires(_EqualOpConcept< 334 typename iterator_traits<_ForwardIterator1>::value_type, 335 typename iterator_traits<_ForwardIterator2>::value_type>) 336 __glibcxx_requires_valid_range(__first1, __last1); 337 __glibcxx_requires_valid_range(__first2, __last2); 338 339 return std::__find_end(__first1, __last1, __first2, __last2, 340 std::__iterator_category(__first1), 341 std::__iterator_category(__first2), 342 __gnu_cxx::__ops::__iter_equal_to_iter()); 343 } 344 345 /** 346 * @brief Find last matching subsequence in a sequence using a predicate. 347 * @ingroup non_mutating_algorithms 348 * @param __first1 Start of range to search. 349 * @param __last1 End of range to search. 350 * @param __first2 Start of sequence to match. 351 * @param __last2 End of sequence to match. 352 * @param __comp The predicate to use. 353 * @return The last iterator @c i in the range @p 354 * [__first1,__last1-(__last2-__first2)) such that @c 355 * predicate(*(i+N), @p (__first2+N)) is true for each @c N in the 356 * range @p [0,__last2-__first2), or @p __last1 if no such iterator 357 * exists. 358 * 359 * Searches the range @p [__first1,__last1) for a sub-sequence that 360 * compares equal value-by-value with the sequence given by @p 361 * [__first2,__last2) using comp as a predicate and returns an 362 * iterator to the first element of the sub-sequence, or @p __last1 363 * if the sub-sequence is not found. The sub-sequence will be the 364 * last such subsequence contained in [__first,__last1). 365 * 366 * Because the sub-sequence must lie completely within the range @p 367 * [__first1,__last1) it must start at a position less than @p 368 * __last1-(__last2-__first2) where @p __last2-__first2 is the 369 * length of the sub-sequence. This means that the returned 370 * iterator @c i will be in the range @p 371 * [__first1,__last1-(__last2-__first2)) 372 */ 373 template<typename _ForwardIterator1, typename _ForwardIterator2, 374 typename _BinaryPredicate> 375 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR 376 inline _ForwardIterator1 377 find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 378 _ForwardIterator2 __first2, _ForwardIterator2 __last2, 379 _BinaryPredicate __comp) 380 { 381 // concept requirements 382 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>) 383 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>) 384 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 385 typename iterator_traits<_ForwardIterator1>::value_type, 386 typename iterator_traits<_ForwardIterator2>::value_type>) 387 __glibcxx_requires_valid_range(__first1, __last1); 388 __glibcxx_requires_valid_range(__first2, __last2); 389 390 return std::__find_end(__first1, __last1, __first2, __last2, 391 std::__iterator_category(__first1), 392 std::__iterator_category(__first2), 393 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 394 } 395 396 #if __cplusplus >= 201103L 397 /** 398 * @brief Checks that a predicate is true for all the elements 399 * of a sequence. 400 * @ingroup non_mutating_algorithms 401 * @param __first An input iterator. 402 * @param __last An input iterator. 403 * @param __pred A predicate. 404 * @return True if the check is true, false otherwise. 405 * 406 * Returns true if @p __pred is true for each element in the range 407 * @p [__first,__last), and false otherwise. 408 */ 409 template<typename _InputIterator, typename _Predicate> 410 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR 411 inline bool 412 all_of(_InputIterator __first, _InputIterator __last, _Predicate __pred) 413 { return __last == std::find_if_not(__first, __last, __pred); } 414 415 /** 416 * @brief Checks that a predicate is false for all the elements 417 * of a sequence. 418 * @ingroup non_mutating_algorithms 419 * @param __first An input iterator. 420 * @param __last An input iterator. 421 * @param __pred A predicate. 422 * @return True if the check is true, false otherwise. 423 * 424 * Returns true if @p __pred is false for each element in the range 425 * @p [__first,__last), and false otherwise. 426 */ 427 template<typename _InputIterator, typename _Predicate> 428 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR 429 inline bool 430 none_of(_InputIterator __first, _InputIterator __last, _Predicate __pred) 431 { return __last == _GLIBCXX_STD_A::find_if(__first, __last, __pred); } 432 433 /** 434 * @brief Checks that a predicate is true for at least one element 435 * of a sequence. 436 * @ingroup non_mutating_algorithms 437 * @param __first An input iterator. 438 * @param __last An input iterator. 439 * @param __pred A predicate. 440 * @return True if the check is true, false otherwise. 441 * 442 * Returns true if an element exists in the range @p 443 * [__first,__last) such that @p __pred is true, and false 444 * otherwise. 445 */ 446 template<typename _InputIterator, typename _Predicate> 447 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR 448 inline bool 449 any_of(_InputIterator __first, _InputIterator __last, _Predicate __pred) 450 { return !std::none_of(__first, __last, __pred); } 451 452 /** 453 * @brief Find the first element in a sequence for which a 454 * predicate is false. 455 * @ingroup non_mutating_algorithms 456 * @param __first An input iterator. 457 * @param __last An input iterator. 458 * @param __pred A predicate. 459 * @return The first iterator @c i in the range @p [__first,__last) 460 * such that @p __pred(*i) is false, or @p __last if no such iterator exists. 461 */ 462 template<typename _InputIterator, typename _Predicate> 463 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR 464 inline _InputIterator 465 find_if_not(_InputIterator __first, _InputIterator __last, 466 _Predicate __pred) 467 { 468 // concept requirements 469 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 470 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 471 typename iterator_traits<_InputIterator>::value_type>) 472 __glibcxx_requires_valid_range(__first, __last); 473 return std::__find_if_not(__first, __last, 474 __gnu_cxx::__ops::__pred_iter(__pred)); 475 } 476 477 /** 478 * @brief Checks whether the sequence is partitioned. 479 * @ingroup mutating_algorithms 480 * @param __first An input iterator. 481 * @param __last An input iterator. 482 * @param __pred A predicate. 483 * @return True if the range @p [__first,__last) is partioned by @p __pred, 484 * i.e. if all elements that satisfy @p __pred appear before those that 485 * do not. 486 */ 487 template<typename _InputIterator, typename _Predicate> 488 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR 489 inline bool 490 is_partitioned(_InputIterator __first, _InputIterator __last, 491 _Predicate __pred) 492 { 493 __first = std::find_if_not(__first, __last, __pred); 494 if (__first == __last) 495 return true; 496 ++__first; 497 return std::none_of(__first, __last, __pred); 498 } 499 500 /** 501 * @brief Find the partition point of a partitioned range. 502 * @ingroup mutating_algorithms 503 * @param __first An iterator. 504 * @param __last Another iterator. 505 * @param __pred A predicate. 506 * @return An iterator @p mid such that @p all_of(__first, mid, __pred) 507 * and @p none_of(mid, __last, __pred) are both true. 508 */ 509 template<typename _ForwardIterator, typename _Predicate> 510 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR 511 _ForwardIterator 512 partition_point(_ForwardIterator __first, _ForwardIterator __last, 513 _Predicate __pred) 514 { 515 // concept requirements 516 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 517 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 518 typename iterator_traits<_ForwardIterator>::value_type>) 519 520 // A specific debug-mode test will be necessary... 521 __glibcxx_requires_valid_range(__first, __last); 522 523 typedef typename iterator_traits<_ForwardIterator>::difference_type 524 _DistanceType; 525 526 _DistanceType __len = std::distance(__first, __last); 527 528 while (__len > 0) 529 { 530 _DistanceType __half = __len >> 1; 531 _ForwardIterator __middle = __first; 532 std::advance(__middle, __half); 533 if (__pred(*__middle)) 534 { 535 __first = __middle; 536 ++__first; 537 __len = __len - __half - 1; 538 } 539 else 540 __len = __half; 541 } 542 return __first; 543 } 544 #endif 545 546 template<typename _InputIterator, typename _OutputIterator, 547 typename _Predicate> 548 _GLIBCXX20_CONSTEXPR 549 _OutputIterator 550 __remove_copy_if(_InputIterator __first, _InputIterator __last, 551 _OutputIterator __result, _Predicate __pred) 552 { 553 for (; __first != __last; ++__first) 554 if (!__pred(__first)) 555 { 556 *__result = *__first; 557 ++__result; 558 } 559 return __result; 560 } 561 562 /** 563 * @brief Copy a sequence, removing elements of a given value. 564 * @ingroup mutating_algorithms 565 * @param __first An input iterator. 566 * @param __last An input iterator. 567 * @param __result An output iterator. 568 * @param __value The value to be removed. 569 * @return An iterator designating the end of the resulting sequence. 570 * 571 * Copies each element in the range @p [__first,__last) not equal 572 * to @p __value to the range beginning at @p __result. 573 * remove_copy() is stable, so the relative order of elements that 574 * are copied is unchanged. 575 */ 576 template<typename _InputIterator, typename _OutputIterator, typename _Tp> 577 _GLIBCXX20_CONSTEXPR 578 inline _OutputIterator 579 remove_copy(_InputIterator __first, _InputIterator __last, 580 _OutputIterator __result, const _Tp& __value) 581 { 582 // concept requirements 583 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 584 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 585 typename iterator_traits<_InputIterator>::value_type>) 586 __glibcxx_function_requires(_EqualOpConcept< 587 typename iterator_traits<_InputIterator>::value_type, _Tp>) 588 __glibcxx_requires_valid_range(__first, __last); 589 590 return std::__remove_copy_if(__first, __last, __result, 591 __gnu_cxx::__ops::__iter_equals_val(__value)); 592 } 593 594 /** 595 * @brief Copy a sequence, removing elements for which a predicate is true. 596 * @ingroup mutating_algorithms 597 * @param __first An input iterator. 598 * @param __last An input iterator. 599 * @param __result An output iterator. 600 * @param __pred A predicate. 601 * @return An iterator designating the end of the resulting sequence. 602 * 603 * Copies each element in the range @p [__first,__last) for which 604 * @p __pred returns false to the range beginning at @p __result. 605 * 606 * remove_copy_if() is stable, so the relative order of elements that are 607 * copied is unchanged. 608 */ 609 template<typename _InputIterator, typename _OutputIterator, 610 typename _Predicate> 611 _GLIBCXX20_CONSTEXPR 612 inline _OutputIterator 613 remove_copy_if(_InputIterator __first, _InputIterator __last, 614 _OutputIterator __result, _Predicate __pred) 615 { 616 // concept requirements 617 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 618 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 619 typename iterator_traits<_InputIterator>::value_type>) 620 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 621 typename iterator_traits<_InputIterator>::value_type>) 622 __glibcxx_requires_valid_range(__first, __last); 623 624 return std::__remove_copy_if(__first, __last, __result, 625 __gnu_cxx::__ops::__pred_iter(__pred)); 626 } 627 628 #if __cplusplus >= 201103L 629 /** 630 * @brief Copy the elements of a sequence for which a predicate is true. 631 * @ingroup mutating_algorithms 632 * @param __first An input iterator. 633 * @param __last An input iterator. 634 * @param __result An output iterator. 635 * @param __pred A predicate. 636 * @return An iterator designating the end of the resulting sequence. 637 * 638 * Copies each element in the range @p [__first,__last) for which 639 * @p __pred returns true to the range beginning at @p __result. 640 * 641 * copy_if() is stable, so the relative order of elements that are 642 * copied is unchanged. 643 */ 644 template<typename _InputIterator, typename _OutputIterator, 645 typename _Predicate> 646 _GLIBCXX20_CONSTEXPR 647 _OutputIterator 648 copy_if(_InputIterator __first, _InputIterator __last, 649 _OutputIterator __result, _Predicate __pred) 650 { 651 // concept requirements 652 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 653 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 654 typename iterator_traits<_InputIterator>::value_type>) 655 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 656 typename iterator_traits<_InputIterator>::value_type>) 657 __glibcxx_requires_valid_range(__first, __last); 658 659 for (; __first != __last; ++__first) 660 if (__pred(*__first)) 661 { 662 *__result = *__first; 663 ++__result; 664 } 665 return __result; 666 } 667 668 /** 669 * @brief Copies the range [first,first+n) into [result,result+n). 670 * @ingroup mutating_algorithms 671 * @param __first An input iterator. 672 * @param __n The number of elements to copy. 673 * @param __result An output iterator. 674 * @return result+n. 675 * 676 * This inline function will boil down to a call to @c memmove whenever 677 * possible. Failing that, if random access iterators are passed, then the 678 * loop count will be known (and therefore a candidate for compiler 679 * optimizations such as unrolling). 680 */ 681 template<typename _InputIterator, typename _Size, typename _OutputIterator> 682 _GLIBCXX20_CONSTEXPR 683 inline _OutputIterator 684 copy_n(_InputIterator __first, _Size __n, _OutputIterator __result) 685 { 686 // concept requirements 687 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 688 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 689 typename iterator_traits<_InputIterator>::value_type>) 690 691 const auto __n2 = std::__size_to_integer(__n); 692 if (__n2 <= 0) 693 return __result; 694 695 __glibcxx_requires_can_increment(__first, __n2); 696 __glibcxx_requires_can_increment(__result, __n2); 697 698 auto __res = std::__copy_n_a(std::__niter_base(__first), __n2, 699 std::__niter_base(__result), true); 700 return std::__niter_wrap(__result, std::move(__res)); 701 } 702 703 /** 704 * @brief Copy the elements of a sequence to separate output sequences 705 * depending on the truth value of a predicate. 706 * @ingroup mutating_algorithms 707 * @param __first An input iterator. 708 * @param __last An input iterator. 709 * @param __out_true An output iterator. 710 * @param __out_false An output iterator. 711 * @param __pred A predicate. 712 * @return A pair designating the ends of the resulting sequences. 713 * 714 * Copies each element in the range @p [__first,__last) for which 715 * @p __pred returns true to the range beginning at @p out_true 716 * and each element for which @p __pred returns false to @p __out_false. 717 */ 718 template<typename _InputIterator, typename _OutputIterator1, 719 typename _OutputIterator2, typename _Predicate> 720 _GLIBCXX20_CONSTEXPR 721 pair<_OutputIterator1, _OutputIterator2> 722 partition_copy(_InputIterator __first, _InputIterator __last, 723 _OutputIterator1 __out_true, _OutputIterator2 __out_false, 724 _Predicate __pred) 725 { 726 // concept requirements 727 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 728 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator1, 729 typename iterator_traits<_InputIterator>::value_type>) 730 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator2, 731 typename iterator_traits<_InputIterator>::value_type>) 732 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 733 typename iterator_traits<_InputIterator>::value_type>) 734 __glibcxx_requires_valid_range(__first, __last); 735 736 for (; __first != __last; ++__first) 737 if (__pred(*__first)) 738 { 739 *__out_true = *__first; 740 ++__out_true; 741 } 742 else 743 { 744 *__out_false = *__first; 745 ++__out_false; 746 } 747 748 return pair<_OutputIterator1, _OutputIterator2>(__out_true, __out_false); 749 } 750 #endif // C++11 751 752 /** 753 * @brief Remove elements from a sequence. 754 * @ingroup mutating_algorithms 755 * @param __first An input iterator. 756 * @param __last An input iterator. 757 * @param __value The value to be removed. 758 * @return An iterator designating the end of the resulting sequence. 759 * 760 * All elements equal to @p __value are removed from the range 761 * @p [__first,__last). 762 * 763 * remove() is stable, so the relative order of elements that are 764 * not removed is unchanged. 765 * 766 * Elements between the end of the resulting sequence and @p __last 767 * are still present, but their value is unspecified. 768 */ 769 template<typename _ForwardIterator, typename _Tp> 770 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR 771 inline _ForwardIterator 772 remove(_ForwardIterator __first, _ForwardIterator __last, 773 const _Tp& __value) 774 { 775 // concept requirements 776 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 777 _ForwardIterator>) 778 __glibcxx_function_requires(_EqualOpConcept< 779 typename iterator_traits<_ForwardIterator>::value_type, _Tp>) 780 __glibcxx_requires_valid_range(__first, __last); 781 782 return std::__remove_if(__first, __last, 783 __gnu_cxx::__ops::__iter_equals_val(__value)); 784 } 785 786 /** 787 * @brief Remove elements from a sequence using a predicate. 788 * @ingroup mutating_algorithms 789 * @param __first A forward iterator. 790 * @param __last A forward iterator. 791 * @param __pred A predicate. 792 * @return An iterator designating the end of the resulting sequence. 793 * 794 * All elements for which @p __pred returns true are removed from the range 795 * @p [__first,__last). 796 * 797 * remove_if() is stable, so the relative order of elements that are 798 * not removed is unchanged. 799 * 800 * Elements between the end of the resulting sequence and @p __last 801 * are still present, but their value is unspecified. 802 */ 803 template<typename _ForwardIterator, typename _Predicate> 804 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR 805 inline _ForwardIterator 806 remove_if(_ForwardIterator __first, _ForwardIterator __last, 807 _Predicate __pred) 808 { 809 // concept requirements 810 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 811 _ForwardIterator>) 812 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 813 typename iterator_traits<_ForwardIterator>::value_type>) 814 __glibcxx_requires_valid_range(__first, __last); 815 816 return std::__remove_if(__first, __last, 817 __gnu_cxx::__ops::__pred_iter(__pred)); 818 } 819 820 template<typename _ForwardIterator, typename _BinaryPredicate> 821 _GLIBCXX20_CONSTEXPR 822 _ForwardIterator 823 __adjacent_find(_ForwardIterator __first, _ForwardIterator __last, 824 _BinaryPredicate __binary_pred) 825 { 826 if (__first == __last) 827 return __last; 828 _ForwardIterator __next = __first; 829 while (++__next != __last) 830 { 831 if (__binary_pred(__first, __next)) 832 return __first; 833 __first = __next; 834 } 835 return __last; 836 } 837 838 template<typename _ForwardIterator, typename _BinaryPredicate> 839 _GLIBCXX20_CONSTEXPR 840 _ForwardIterator 841 __unique(_ForwardIterator __first, _ForwardIterator __last, 842 _BinaryPredicate __binary_pred) 843 { 844 // Skip the beginning, if already unique. 845 __first = std::__adjacent_find(__first, __last, __binary_pred); 846 if (__first == __last) 847 return __last; 848 849 // Do the real copy work. 850 _ForwardIterator __dest = __first; 851 ++__first; 852 while (++__first != __last) 853 if (!__binary_pred(__dest, __first)) 854 *++__dest = _GLIBCXX_MOVE(*__first); 855 return ++__dest; 856 } 857 858 /** 859 * @brief Remove consecutive duplicate values from a sequence. 860 * @ingroup mutating_algorithms 861 * @param __first A forward iterator. 862 * @param __last A forward iterator. 863 * @return An iterator designating the end of the resulting sequence. 864 * 865 * Removes all but the first element from each group of consecutive 866 * values that compare equal. 867 * unique() is stable, so the relative order of elements that are 868 * not removed is unchanged. 869 * Elements between the end of the resulting sequence and @p __last 870 * are still present, but their value is unspecified. 871 */ 872 template<typename _ForwardIterator> 873 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR 874 inline _ForwardIterator 875 unique(_ForwardIterator __first, _ForwardIterator __last) 876 { 877 // concept requirements 878 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 879 _ForwardIterator>) 880 __glibcxx_function_requires(_EqualityComparableConcept< 881 typename iterator_traits<_ForwardIterator>::value_type>) 882 __glibcxx_requires_valid_range(__first, __last); 883 884 return std::__unique(__first, __last, 885 __gnu_cxx::__ops::__iter_equal_to_iter()); 886 } 887 888 /** 889 * @brief Remove consecutive values from a sequence using a predicate. 890 * @ingroup mutating_algorithms 891 * @param __first A forward iterator. 892 * @param __last A forward iterator. 893 * @param __binary_pred A binary predicate. 894 * @return An iterator designating the end of the resulting sequence. 895 * 896 * Removes all but the first element from each group of consecutive 897 * values for which @p __binary_pred returns true. 898 * unique() is stable, so the relative order of elements that are 899 * not removed is unchanged. 900 * Elements between the end of the resulting sequence and @p __last 901 * are still present, but their value is unspecified. 902 */ 903 template<typename _ForwardIterator, typename _BinaryPredicate> 904 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR 905 inline _ForwardIterator 906 unique(_ForwardIterator __first, _ForwardIterator __last, 907 _BinaryPredicate __binary_pred) 908 { 909 // concept requirements 910 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 911 _ForwardIterator>) 912 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 913 typename iterator_traits<_ForwardIterator>::value_type, 914 typename iterator_traits<_ForwardIterator>::value_type>) 915 __glibcxx_requires_valid_range(__first, __last); 916 917 return std::__unique(__first, __last, 918 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred)); 919 } 920 921 /** 922 * This is an uglified 923 * unique_copy(_InputIterator, _InputIterator, _OutputIterator, 924 * _BinaryPredicate) 925 * overloaded for forward iterators and output iterator as result. 926 */ 927 template<typename _ForwardIterator, typename _OutputIterator, 928 typename _BinaryPredicate> 929 _GLIBCXX20_CONSTEXPR 930 _OutputIterator 931 __unique_copy(_ForwardIterator __first, _ForwardIterator __last, 932 _OutputIterator __result, _BinaryPredicate __binary_pred, 933 forward_iterator_tag, output_iterator_tag) 934 { 935 // concept requirements -- iterators already checked 936 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 937 typename iterator_traits<_ForwardIterator>::value_type, 938 typename iterator_traits<_ForwardIterator>::value_type>) 939 940 _ForwardIterator __next = __first; 941 *__result = *__first; 942 while (++__next != __last) 943 if (!__binary_pred(__first, __next)) 944 { 945 __first = __next; 946 *++__result = *__first; 947 } 948 return ++__result; 949 } 950 951 /** 952 * This is an uglified 953 * unique_copy(_InputIterator, _InputIterator, _OutputIterator, 954 * _BinaryPredicate) 955 * overloaded for input iterators and output iterator as result. 956 */ 957 template<typename _InputIterator, typename _OutputIterator, 958 typename _BinaryPredicate> 959 _GLIBCXX20_CONSTEXPR 960 _OutputIterator 961 __unique_copy(_InputIterator __first, _InputIterator __last, 962 _OutputIterator __result, _BinaryPredicate __binary_pred, 963 input_iterator_tag, output_iterator_tag) 964 { 965 // concept requirements -- iterators already checked 966 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 967 typename iterator_traits<_InputIterator>::value_type, 968 typename iterator_traits<_InputIterator>::value_type>) 969 970 typename iterator_traits<_InputIterator>::value_type __value = *__first; 971 __decltype(__gnu_cxx::__ops::__iter_comp_val(__binary_pred)) 972 __rebound_pred 973 = __gnu_cxx::__ops::__iter_comp_val(__binary_pred); 974 *__result = __value; 975 while (++__first != __last) 976 if (!__rebound_pred(__first, __value)) 977 { 978 __value = *__first; 979 *++__result = __value; 980 } 981 return ++__result; 982 } 983 984 /** 985 * This is an uglified 986 * unique_copy(_InputIterator, _InputIterator, _OutputIterator, 987 * _BinaryPredicate) 988 * overloaded for input iterators and forward iterator as result. 989 */ 990 template<typename _InputIterator, typename _ForwardIterator, 991 typename _BinaryPredicate> 992 _GLIBCXX20_CONSTEXPR 993 _ForwardIterator 994 __unique_copy(_InputIterator __first, _InputIterator __last, 995 _ForwardIterator __result, _BinaryPredicate __binary_pred, 996 input_iterator_tag, forward_iterator_tag) 997 { 998 // concept requirements -- iterators already checked 999 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 1000 typename iterator_traits<_ForwardIterator>::value_type, 1001 typename iterator_traits<_InputIterator>::value_type>) 1002 *__result = *__first; 1003 while (++__first != __last) 1004 if (!__binary_pred(__result, __first)) 1005 *++__result = *__first; 1006 return ++__result; 1007 } 1008 1009 /** 1010 * This is an uglified reverse(_BidirectionalIterator, 1011 * _BidirectionalIterator) 1012 * overloaded for bidirectional iterators. 1013 */ 1014 template<typename _BidirectionalIterator> 1015 _GLIBCXX20_CONSTEXPR 1016 void 1017 __reverse(_BidirectionalIterator __first, _BidirectionalIterator __last, 1018 bidirectional_iterator_tag) 1019 { 1020 while (true) 1021 if (__first == __last || __first == --__last) 1022 return; 1023 else 1024 { 1025 std::iter_swap(__first, __last); 1026 ++__first; 1027 } 1028 } 1029 1030 /** 1031 * This is an uglified reverse(_BidirectionalIterator, 1032 * _BidirectionalIterator) 1033 * overloaded for random access iterators. 1034 */ 1035 template<typename _RandomAccessIterator> 1036 _GLIBCXX20_CONSTEXPR 1037 void 1038 __reverse(_RandomAccessIterator __first, _RandomAccessIterator __last, 1039 random_access_iterator_tag) 1040 { 1041 if (__first == __last) 1042 return; 1043 --__last; 1044 while (__first < __last) 1045 { 1046 std::iter_swap(__first, __last); 1047 ++__first; 1048 --__last; 1049 } 1050 } 1051 1052 /** 1053 * @brief Reverse a sequence. 1054 * @ingroup mutating_algorithms 1055 * @param __first A bidirectional iterator. 1056 * @param __last A bidirectional iterator. 1057 * @return reverse() returns no value. 1058 * 1059 * Reverses the order of the elements in the range @p [__first,__last), 1060 * so that the first element becomes the last etc. 1061 * For every @c i such that @p 0<=i<=(__last-__first)/2), @p reverse() 1062 * swaps @p *(__first+i) and @p *(__last-(i+1)) 1063 */ 1064 template<typename _BidirectionalIterator> 1065 _GLIBCXX20_CONSTEXPR 1066 inline void 1067 reverse(_BidirectionalIterator __first, _BidirectionalIterator __last) 1068 { 1069 // concept requirements 1070 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept< 1071 _BidirectionalIterator>) 1072 __glibcxx_requires_valid_range(__first, __last); 1073 std::__reverse(__first, __last, std::__iterator_category(__first)); 1074 } 1075 1076 /** 1077 * @brief Copy a sequence, reversing its elements. 1078 * @ingroup mutating_algorithms 1079 * @param __first A bidirectional iterator. 1080 * @param __last A bidirectional iterator. 1081 * @param __result An output iterator. 1082 * @return An iterator designating the end of the resulting sequence. 1083 * 1084 * Copies the elements in the range @p [__first,__last) to the 1085 * range @p [__result,__result+(__last-__first)) such that the 1086 * order of the elements is reversed. For every @c i such that @p 1087 * 0<=i<=(__last-__first), @p reverse_copy() performs the 1088 * assignment @p *(__result+(__last-__first)-1-i) = *(__first+i). 1089 * The ranges @p [__first,__last) and @p 1090 * [__result,__result+(__last-__first)) must not overlap. 1091 */ 1092 template<typename _BidirectionalIterator, typename _OutputIterator> 1093 _GLIBCXX20_CONSTEXPR 1094 _OutputIterator 1095 reverse_copy(_BidirectionalIterator __first, _BidirectionalIterator __last, 1096 _OutputIterator __result) 1097 { 1098 // concept requirements 1099 __glibcxx_function_requires(_BidirectionalIteratorConcept< 1100 _BidirectionalIterator>) 1101 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 1102 typename iterator_traits<_BidirectionalIterator>::value_type>) 1103 __glibcxx_requires_valid_range(__first, __last); 1104 1105 while (__first != __last) 1106 { 1107 --__last; 1108 *__result = *__last; 1109 ++__result; 1110 } 1111 return __result; 1112 } 1113 1114 /** 1115 * This is a helper function for the rotate algorithm specialized on RAIs. 1116 * It returns the greatest common divisor of two integer values. 1117 */ 1118 template<typename _EuclideanRingElement> 1119 _GLIBCXX20_CONSTEXPR 1120 _EuclideanRingElement 1121 __gcd(_EuclideanRingElement __m, _EuclideanRingElement __n) 1122 { 1123 while (__n != 0) 1124 { 1125 _EuclideanRingElement __t = __m % __n; 1126 __m = __n; 1127 __n = __t; 1128 } 1129 return __m; 1130 } 1131 1132 _GLIBCXX_BEGIN_INLINE_ABI_NAMESPACE(_V2) 1133 1134 /// This is a helper function for the rotate algorithm. 1135 template<typename _ForwardIterator> 1136 _GLIBCXX20_CONSTEXPR 1137 _ForwardIterator 1138 __rotate(_ForwardIterator __first, 1139 _ForwardIterator __middle, 1140 _ForwardIterator __last, 1141 forward_iterator_tag) 1142 { 1143 if (__first == __middle) 1144 return __last; 1145 else if (__last == __middle) 1146 return __first; 1147 1148 _ForwardIterator __first2 = __middle; 1149 do 1150 { 1151 std::iter_swap(__first, __first2); 1152 ++__first; 1153 ++__first2; 1154 if (__first == __middle) 1155 __middle = __first2; 1156 } 1157 while (__first2 != __last); 1158 1159 _ForwardIterator __ret = __first; 1160 1161 __first2 = __middle; 1162 1163 while (__first2 != __last) 1164 { 1165 std::iter_swap(__first, __first2); 1166 ++__first; 1167 ++__first2; 1168 if (__first == __middle) 1169 __middle = __first2; 1170 else if (__first2 == __last) 1171 __first2 = __middle; 1172 } 1173 return __ret; 1174 } 1175 1176 /// This is a helper function for the rotate algorithm. 1177 template<typename _BidirectionalIterator> 1178 _GLIBCXX20_CONSTEXPR 1179 _BidirectionalIterator 1180 __rotate(_BidirectionalIterator __first, 1181 _BidirectionalIterator __middle, 1182 _BidirectionalIterator __last, 1183 bidirectional_iterator_tag) 1184 { 1185 // concept requirements 1186 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept< 1187 _BidirectionalIterator>) 1188 1189 if (__first == __middle) 1190 return __last; 1191 else if (__last == __middle) 1192 return __first; 1193 1194 std::__reverse(__first, __middle, bidirectional_iterator_tag()); 1195 std::__reverse(__middle, __last, bidirectional_iterator_tag()); 1196 1197 while (__first != __middle && __middle != __last) 1198 { 1199 std::iter_swap(__first, --__last); 1200 ++__first; 1201 } 1202 1203 if (__first == __middle) 1204 { 1205 std::__reverse(__middle, __last, bidirectional_iterator_tag()); 1206 return __last; 1207 } 1208 else 1209 { 1210 std::__reverse(__first, __middle, bidirectional_iterator_tag()); 1211 return __first; 1212 } 1213 } 1214 1215 /// This is a helper function for the rotate algorithm. 1216 template<typename _RandomAccessIterator> 1217 _GLIBCXX20_CONSTEXPR 1218 _RandomAccessIterator 1219 __rotate(_RandomAccessIterator __first, 1220 _RandomAccessIterator __middle, 1221 _RandomAccessIterator __last, 1222 random_access_iterator_tag) 1223 { 1224 // concept requirements 1225 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 1226 _RandomAccessIterator>) 1227 1228 if (__first == __middle) 1229 return __last; 1230 else if (__last == __middle) 1231 return __first; 1232 1233 typedef typename iterator_traits<_RandomAccessIterator>::difference_type 1234 _Distance; 1235 typedef typename iterator_traits<_RandomAccessIterator>::value_type 1236 _ValueType; 1237 1238 #if __cplusplus >= 201103L 1239 typedef typename make_unsigned<_Distance>::type _UDistance; 1240 #else 1241 typedef _Distance _UDistance; 1242 #endif 1243 1244 _Distance __n = __last - __first; 1245 _Distance __k = __middle - __first; 1246 1247 if (__k == __n - __k) 1248 { 1249 std::swap_ranges(__first, __middle, __middle); 1250 return __middle; 1251 } 1252 1253 _RandomAccessIterator __p = __first; 1254 _RandomAccessIterator __ret = __first + (__last - __middle); 1255 1256 for (;;) 1257 { 1258 if (__k < __n - __k) 1259 { 1260 if (__is_pod(_ValueType) && __k == 1) 1261 { 1262 _ValueType __t = _GLIBCXX_MOVE(*__p); 1263 _GLIBCXX_MOVE3(__p + 1, __p + __n, __p); 1264 *(__p + __n - 1) = _GLIBCXX_MOVE(__t); 1265 return __ret; 1266 } 1267 _RandomAccessIterator __q = __p + __k; 1268 for (_Distance __i = 0; __i < __n - __k; ++ __i) 1269 { 1270 std::iter_swap(__p, __q); 1271 ++__p; 1272 ++__q; 1273 } 1274 __n = static_cast<_UDistance>(__n) % static_cast<_UDistance>(__k); 1275 if (__n == 0) 1276 return __ret; 1277 std::swap(__n, __k); 1278 __k = __n - __k; 1279 } 1280 else 1281 { 1282 __k = __n - __k; 1283 if (__is_pod(_ValueType) && __k == 1) 1284 { 1285 _ValueType __t = _GLIBCXX_MOVE(*(__p + __n - 1)); 1286 _GLIBCXX_MOVE_BACKWARD3(__p, __p + __n - 1, __p + __n); 1287 *__p = _GLIBCXX_MOVE(__t); 1288 return __ret; 1289 } 1290 _RandomAccessIterator __q = __p + __n; 1291 __p = __q - __k; 1292 for (_Distance __i = 0; __i < __n - __k; ++ __i) 1293 { 1294 --__p; 1295 --__q; 1296 std::iter_swap(__p, __q); 1297 } 1298 __n = static_cast<_UDistance>(__n) % static_cast<_UDistance>(__k); 1299 if (__n == 0) 1300 return __ret; 1301 std::swap(__n, __k); 1302 } 1303 } 1304 } 1305 1306 // _GLIBCXX_RESOLVE_LIB_DEFECTS 1307 // DR 488. rotate throws away useful information 1308 /** 1309 * @brief Rotate the elements of a sequence. 1310 * @ingroup mutating_algorithms 1311 * @param __first A forward iterator. 1312 * @param __middle A forward iterator. 1313 * @param __last A forward iterator. 1314 * @return first + (last - middle). 1315 * 1316 * Rotates the elements of the range @p [__first,__last) by 1317 * @p (__middle - __first) positions so that the element at @p __middle 1318 * is moved to @p __first, the element at @p __middle+1 is moved to 1319 * @p __first+1 and so on for each element in the range 1320 * @p [__first,__last). 1321 * 1322 * This effectively swaps the ranges @p [__first,__middle) and 1323 * @p [__middle,__last). 1324 * 1325 * Performs 1326 * @p *(__first+(n+(__last-__middle))%(__last-__first))=*(__first+n) 1327 * for each @p n in the range @p [0,__last-__first). 1328 */ 1329 template<typename _ForwardIterator> 1330 _GLIBCXX20_CONSTEXPR 1331 inline _ForwardIterator 1332 rotate(_ForwardIterator __first, _ForwardIterator __middle, 1333 _ForwardIterator __last) 1334 { 1335 // concept requirements 1336 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 1337 _ForwardIterator>) 1338 __glibcxx_requires_valid_range(__first, __middle); 1339 __glibcxx_requires_valid_range(__middle, __last); 1340 1341 return std::__rotate(__first, __middle, __last, 1342 std::__iterator_category(__first)); 1343 } 1344 1345 _GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2) 1346 1347 /** 1348 * @brief Copy a sequence, rotating its elements. 1349 * @ingroup mutating_algorithms 1350 * @param __first A forward iterator. 1351 * @param __middle A forward iterator. 1352 * @param __last A forward iterator. 1353 * @param __result An output iterator. 1354 * @return An iterator designating the end of the resulting sequence. 1355 * 1356 * Copies the elements of the range @p [__first,__last) to the 1357 * range beginning at @result, rotating the copied elements by 1358 * @p (__middle-__first) positions so that the element at @p __middle 1359 * is moved to @p __result, the element at @p __middle+1 is moved 1360 * to @p __result+1 and so on for each element in the range @p 1361 * [__first,__last). 1362 * 1363 * Performs 1364 * @p *(__result+(n+(__last-__middle))%(__last-__first))=*(__first+n) 1365 * for each @p n in the range @p [0,__last-__first). 1366 */ 1367 template<typename _ForwardIterator, typename _OutputIterator> 1368 _GLIBCXX20_CONSTEXPR 1369 inline _OutputIterator 1370 rotate_copy(_ForwardIterator __first, _ForwardIterator __middle, 1371 _ForwardIterator __last, _OutputIterator __result) 1372 { 1373 // concept requirements 1374 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 1375 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 1376 typename iterator_traits<_ForwardIterator>::value_type>) 1377 __glibcxx_requires_valid_range(__first, __middle); 1378 __glibcxx_requires_valid_range(__middle, __last); 1379 1380 return std::copy(__first, __middle, 1381 std::copy(__middle, __last, __result)); 1382 } 1383 1384 /// This is a helper function... 1385 template<typename _ForwardIterator, typename _Predicate> 1386 _GLIBCXX20_CONSTEXPR 1387 _ForwardIterator 1388 __partition(_ForwardIterator __first, _ForwardIterator __last, 1389 _Predicate __pred, forward_iterator_tag) 1390 { 1391 if (__first == __last) 1392 return __first; 1393 1394 while (__pred(*__first)) 1395 if (++__first == __last) 1396 return __first; 1397 1398 _ForwardIterator __next = __first; 1399 1400 while (++__next != __last) 1401 if (__pred(*__next)) 1402 { 1403 std::iter_swap(__first, __next); 1404 ++__first; 1405 } 1406 1407 return __first; 1408 } 1409 1410 /// This is a helper function... 1411 template<typename _BidirectionalIterator, typename _Predicate> 1412 _GLIBCXX20_CONSTEXPR 1413 _BidirectionalIterator 1414 __partition(_BidirectionalIterator __first, _BidirectionalIterator __last, 1415 _Predicate __pred, bidirectional_iterator_tag) 1416 { 1417 while (true) 1418 { 1419 while (true) 1420 if (__first == __last) 1421 return __first; 1422 else if (__pred(*__first)) 1423 ++__first; 1424 else 1425 break; 1426 --__last; 1427 while (true) 1428 if (__first == __last) 1429 return __first; 1430 else if (!bool(__pred(*__last))) 1431 --__last; 1432 else 1433 break; 1434 std::iter_swap(__first, __last); 1435 ++__first; 1436 } 1437 } 1438 1439 #if _GLIBCXX_HOSTED 1440 // partition 1441 1442 /// This is a helper function... 1443 /// Requires __first != __last and !__pred(__first) 1444 /// and __len == distance(__first, __last). 1445 /// 1446 /// !__pred(__first) allows us to guarantee that we don't 1447 /// move-assign an element onto itself. 1448 template<typename _ForwardIterator, typename _Pointer, typename _Predicate, 1449 typename _Distance> 1450 _GLIBCXX26_CONSTEXPR 1451 _ForwardIterator 1452 __stable_partition_adaptive(_ForwardIterator __first, 1453 _ForwardIterator __last, 1454 _Predicate __pred, _Distance __len, 1455 _Pointer __buffer, 1456 _Distance __buffer_size) 1457 { 1458 if (__len == 1) 1459 return __first; 1460 1461 if (__len <= __buffer_size) 1462 { 1463 _ForwardIterator __result1 = __first; 1464 _Pointer __result2 = __buffer; 1465 1466 // The precondition guarantees that !__pred(__first), so 1467 // move that element to the buffer before starting the loop. 1468 // This ensures that we only call __pred once per element. 1469 *__result2 = _GLIBCXX_MOVE(*__first); 1470 ++__result2; 1471 ++__first; 1472 for (; __first != __last; ++__first) 1473 if (__pred(__first)) 1474 { 1475 *__result1 = _GLIBCXX_MOVE(*__first); 1476 ++__result1; 1477 } 1478 else 1479 { 1480 *__result2 = _GLIBCXX_MOVE(*__first); 1481 ++__result2; 1482 } 1483 1484 _GLIBCXX_MOVE3(__buffer, __result2, __result1); 1485 return __result1; 1486 } 1487 1488 _ForwardIterator __middle = __first; 1489 std::advance(__middle, __len / 2); 1490 _ForwardIterator __left_split = 1491 std::__stable_partition_adaptive(__first, __middle, __pred, 1492 __len / 2, __buffer, 1493 __buffer_size); 1494 1495 // Advance past true-predicate values to satisfy this 1496 // function's preconditions. 1497 _Distance __right_len = __len - __len / 2; 1498 _ForwardIterator __right_split = 1499 std::__find_if_not_n(__middle, __right_len, __pred); 1500 1501 if (__right_len) 1502 __right_split = 1503 std::__stable_partition_adaptive(__right_split, __last, __pred, 1504 __right_len, 1505 __buffer, __buffer_size); 1506 1507 return std::rotate(__left_split, __middle, __right_split); 1508 } 1509 1510 template<typename _ForwardIterator, typename _Predicate> 1511 _GLIBCXX26_CONSTEXPR 1512 _ForwardIterator 1513 __stable_partition(_ForwardIterator __first, _ForwardIterator __last, 1514 _Predicate __pred) 1515 { 1516 __first = std::__find_if_not(__first, __last, __pred); 1517 1518 if (__first == __last) 1519 return __first; 1520 1521 typedef typename iterator_traits<_ForwardIterator>::value_type 1522 _ValueType; 1523 typedef typename iterator_traits<_ForwardIterator>::difference_type 1524 _DistanceType; 1525 1526 const _DistanceType __len = std::distance(__first, __last); 1527 1528 #if __glibcxx_constexpr_algorithms >= 202306L // >= C++26 1529 if consteval { 1530 // Simulate a _Temporary_buffer of length 1: 1531 _ValueType __buf = std::move(*__first); 1532 *__first = std::move(__buf); 1533 return std::__stable_partition_adaptive(__first, __last, __pred, 1534 __len, 1535 &__buf, 1536 _DistanceType(1)); 1537 } 1538 #endif 1539 1540 _Temporary_buffer<_ForwardIterator, _ValueType> 1541 __buf(__first, __len); 1542 return 1543 std::__stable_partition_adaptive(__first, __last, __pred, 1544 __len, 1545 __buf.begin(), 1546 _DistanceType(__buf.size())); 1547 } 1548 1549 /** 1550 * @brief Move elements for which a predicate is true to the beginning 1551 * of a sequence, preserving relative ordering. 1552 * @ingroup mutating_algorithms 1553 * @param __first A forward iterator. 1554 * @param __last A forward iterator. 1555 * @param __pred A predicate functor. 1556 * @return An iterator @p middle such that @p __pred(i) is true for each 1557 * iterator @p i in the range @p [first,middle) and false for each @p i 1558 * in the range @p [middle,last). 1559 * 1560 * Performs the same function as @p partition() with the additional 1561 * guarantee that the relative ordering of elements in each group is 1562 * preserved, so any two elements @p x and @p y in the range 1563 * @p [__first,__last) such that @p __pred(x)==__pred(y) will have the same 1564 * relative ordering after calling @p stable_partition(). 1565 */ 1566 template<typename _ForwardIterator, typename _Predicate> 1567 _GLIBCXX26_CONSTEXPR 1568 inline _ForwardIterator 1569 stable_partition(_ForwardIterator __first, _ForwardIterator __last, 1570 _Predicate __pred) 1571 { 1572 // concept requirements 1573 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 1574 _ForwardIterator>) 1575 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 1576 typename iterator_traits<_ForwardIterator>::value_type>) 1577 __glibcxx_requires_valid_range(__first, __last); 1578 1579 return std::__stable_partition(__first, __last, 1580 __gnu_cxx::__ops::__pred_iter(__pred)); 1581 } 1582 #endif // HOSTED 1583 1584 /// @cond undocumented 1585 1586 /// This is a helper function for the sort routines. 1587 template<typename _RandomAccessIterator, typename _Compare> 1588 _GLIBCXX20_CONSTEXPR 1589 void 1590 __heap_select(_RandomAccessIterator __first, 1591 _RandomAccessIterator __middle, 1592 _RandomAccessIterator __last, _Compare __comp) 1593 { 1594 std::__make_heap(__first, __middle, __comp); 1595 for (_RandomAccessIterator __i = __middle; __i < __last; ++__i) 1596 if (__comp(__i, __first)) 1597 std::__pop_heap(__first, __middle, __i, __comp); 1598 } 1599 1600 // partial_sort 1601 1602 template<typename _InputIterator, typename _RandomAccessIterator, 1603 typename _Compare> 1604 _GLIBCXX20_CONSTEXPR 1605 _RandomAccessIterator 1606 __partial_sort_copy(_InputIterator __first, _InputIterator __last, 1607 _RandomAccessIterator __result_first, 1608 _RandomAccessIterator __result_last, 1609 _Compare __comp) 1610 { 1611 typedef typename iterator_traits<_InputIterator>::value_type 1612 _InputValueType; 1613 typedef iterator_traits<_RandomAccessIterator> _RItTraits; 1614 typedef typename _RItTraits::difference_type _DistanceType; 1615 1616 if (__result_first == __result_last) 1617 return __result_last; 1618 _RandomAccessIterator __result_real_last = __result_first; 1619 while (__first != __last && __result_real_last != __result_last) 1620 { 1621 *__result_real_last = *__first; 1622 ++__result_real_last; 1623 ++__first; 1624 } 1625 1626 std::__make_heap(__result_first, __result_real_last, __comp); 1627 while (__first != __last) 1628 { 1629 if (__comp(__first, __result_first)) 1630 std::__adjust_heap(__result_first, _DistanceType(0), 1631 _DistanceType(__result_real_last 1632 - __result_first), 1633 _InputValueType(*__first), __comp); 1634 ++__first; 1635 } 1636 std::__sort_heap(__result_first, __result_real_last, __comp); 1637 return __result_real_last; 1638 } 1639 1640 /// @endcond 1641 1642 /** 1643 * @brief Copy the smallest elements of a sequence. 1644 * @ingroup sorting_algorithms 1645 * @param __first An iterator. 1646 * @param __last Another iterator. 1647 * @param __result_first A random-access iterator. 1648 * @param __result_last Another random-access iterator. 1649 * @return An iterator indicating the end of the resulting sequence. 1650 * 1651 * Copies and sorts the smallest `N` values from the range 1652 * `[__first, __last)` to the range beginning at `__result_first`, where 1653 * the number of elements to be copied, `N`, is the smaller of 1654 * `(__last - __first)` and `(__result_last - __result_first)`. 1655 * After the sort if `i` and `j` are iterators in the range 1656 * `[__result_first,__result_first + N)` such that `i` precedes `j` then 1657 * `*j < *i` is false. 1658 * The value returned is `__result_first + N`. 1659 */ 1660 template<typename _InputIterator, typename _RandomAccessIterator> 1661 _GLIBCXX20_CONSTEXPR 1662 inline _RandomAccessIterator 1663 partial_sort_copy(_InputIterator __first, _InputIterator __last, 1664 _RandomAccessIterator __result_first, 1665 _RandomAccessIterator __result_last) 1666 { 1667 #ifdef _GLIBCXX_CONCEPT_CHECKS 1668 typedef typename iterator_traits<_InputIterator>::value_type 1669 _InputValueType; 1670 typedef typename iterator_traits<_RandomAccessIterator>::value_type 1671 _OutputValueType; 1672 #endif 1673 1674 // concept requirements 1675 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 1676 __glibcxx_function_requires(_ConvertibleConcept<_InputValueType, 1677 _OutputValueType>) 1678 __glibcxx_function_requires(_LessThanOpConcept<_InputValueType, 1679 _OutputValueType>) 1680 __glibcxx_function_requires(_LessThanComparableConcept<_OutputValueType>) 1681 __glibcxx_requires_valid_range(__first, __last); 1682 __glibcxx_requires_irreflexive(__first, __last); 1683 __glibcxx_requires_valid_range(__result_first, __result_last); 1684 1685 return std::__partial_sort_copy(__first, __last, 1686 __result_first, __result_last, 1687 __gnu_cxx::__ops::__iter_less_iter()); 1688 } 1689 1690 /** 1691 * @brief Copy the smallest elements of a sequence using a predicate for 1692 * comparison. 1693 * @ingroup sorting_algorithms 1694 * @param __first An input iterator. 1695 * @param __last Another input iterator. 1696 * @param __result_first A random-access iterator. 1697 * @param __result_last Another random-access iterator. 1698 * @param __comp A comparison functor. 1699 * @return An iterator indicating the end of the resulting sequence. 1700 * 1701 * Copies and sorts the smallest `N` values from the range 1702 * `[__first, __last)` to the range beginning at `result_first`, where 1703 * the number of elements to be copied, `N`, is the smaller of 1704 * `(__last - __first)` and `(__result_last - __result_first)`. 1705 * After the sort if `i` and `j` are iterators in the range 1706 * `[__result_first, __result_first + N)` such that `i` precedes `j` then 1707 * `__comp(*j, *i)` is false. 1708 * The value returned is `__result_first + N`. 1709 */ 1710 template<typename _InputIterator, typename _RandomAccessIterator, 1711 typename _Compare> 1712 _GLIBCXX20_CONSTEXPR 1713 inline _RandomAccessIterator 1714 partial_sort_copy(_InputIterator __first, _InputIterator __last, 1715 _RandomAccessIterator __result_first, 1716 _RandomAccessIterator __result_last, 1717 _Compare __comp) 1718 { 1719 #ifdef _GLIBCXX_CONCEPT_CHECKS 1720 typedef typename iterator_traits<_InputIterator>::value_type 1721 _InputValueType; 1722 typedef typename iterator_traits<_RandomAccessIterator>::value_type 1723 _OutputValueType; 1724 #endif 1725 1726 // concept requirements 1727 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 1728 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 1729 _RandomAccessIterator>) 1730 __glibcxx_function_requires(_ConvertibleConcept<_InputValueType, 1731 _OutputValueType>) 1732 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 1733 _InputValueType, _OutputValueType>) 1734 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 1735 _OutputValueType, _OutputValueType>) 1736 __glibcxx_requires_valid_range(__first, __last); 1737 __glibcxx_requires_irreflexive_pred(__first, __last, __comp); 1738 __glibcxx_requires_valid_range(__result_first, __result_last); 1739 1740 return std::__partial_sort_copy(__first, __last, 1741 __result_first, __result_last, 1742 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 1743 } 1744 1745 /// @cond undocumented 1746 1747 /// This is a helper function for the sort routine. 1748 template<typename _RandomAccessIterator, typename _Compare> 1749 _GLIBCXX20_CONSTEXPR 1750 void 1751 __unguarded_linear_insert(_RandomAccessIterator __last, 1752 _Compare __comp) 1753 { 1754 typename iterator_traits<_RandomAccessIterator>::value_type 1755 __val = _GLIBCXX_MOVE(*__last); 1756 _RandomAccessIterator __next = __last; 1757 --__next; 1758 while (__comp(__val, __next)) 1759 { 1760 *__last = _GLIBCXX_MOVE(*__next); 1761 __last = __next; 1762 --__next; 1763 } 1764 *__last = _GLIBCXX_MOVE(__val); 1765 } 1766 1767 /// This is a helper function for the sort routine. 1768 template<typename _RandomAccessIterator, typename _Compare> 1769 _GLIBCXX20_CONSTEXPR 1770 void 1771 __insertion_sort(_RandomAccessIterator __first, 1772 _RandomAccessIterator __last, _Compare __comp) 1773 { 1774 if (__first == __last) return; 1775 1776 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i) 1777 { 1778 if (__comp(__i, __first)) 1779 { 1780 typename iterator_traits<_RandomAccessIterator>::value_type 1781 __val = _GLIBCXX_MOVE(*__i); 1782 _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1); 1783 *__first = _GLIBCXX_MOVE(__val); 1784 } 1785 else 1786 std::__unguarded_linear_insert(__i, 1787 __gnu_cxx::__ops::__val_comp_iter(__comp)); 1788 } 1789 } 1790 1791 /// This is a helper function for the sort routine. 1792 template<typename _RandomAccessIterator, typename _Compare> 1793 _GLIBCXX20_CONSTEXPR 1794 inline void 1795 __unguarded_insertion_sort(_RandomAccessIterator __first, 1796 _RandomAccessIterator __last, _Compare __comp) 1797 { 1798 for (_RandomAccessIterator __i = __first; __i != __last; ++__i) 1799 std::__unguarded_linear_insert(__i, 1800 __gnu_cxx::__ops::__val_comp_iter(__comp)); 1801 } 1802 1803 /** 1804 * @doctodo 1805 * This controls some aspect of the sort routines. 1806 */ 1807 enum { _S_threshold = 16 }; 1808 1809 /// This is a helper function for the sort routine. 1810 template<typename _RandomAccessIterator, typename _Compare> 1811 _GLIBCXX20_CONSTEXPR 1812 void 1813 __final_insertion_sort(_RandomAccessIterator __first, 1814 _RandomAccessIterator __last, _Compare __comp) 1815 { 1816 if (__last - __first > int(_S_threshold)) 1817 { 1818 std::__insertion_sort(__first, __first + int(_S_threshold), __comp); 1819 std::__unguarded_insertion_sort(__first + int(_S_threshold), __last, 1820 __comp); 1821 } 1822 else 1823 std::__insertion_sort(__first, __last, __comp); 1824 } 1825 1826 /// This is a helper function... 1827 template<typename _RandomAccessIterator, typename _Compare> 1828 _GLIBCXX20_CONSTEXPR 1829 _RandomAccessIterator 1830 __unguarded_partition(_RandomAccessIterator __first, 1831 _RandomAccessIterator __last, 1832 _RandomAccessIterator __pivot, _Compare __comp) 1833 { 1834 while (true) 1835 { 1836 while (__comp(__first, __pivot)) 1837 ++__first; 1838 --__last; 1839 while (__comp(__pivot, __last)) 1840 --__last; 1841 if (!(__first < __last)) 1842 return __first; 1843 std::iter_swap(__first, __last); 1844 ++__first; 1845 } 1846 } 1847 1848 /// This is a helper function... 1849 template<typename _RandomAccessIterator, typename _Compare> 1850 _GLIBCXX20_CONSTEXPR 1851 inline _RandomAccessIterator 1852 __unguarded_partition_pivot(_RandomAccessIterator __first, 1853 _RandomAccessIterator __last, _Compare __comp) 1854 { 1855 _RandomAccessIterator __mid = __first + (__last - __first) / 2; 1856 std::__move_median_to_first(__first, __first + 1, __mid, __last - 1, 1857 __comp); 1858 return std::__unguarded_partition(__first + 1, __last, __first, __comp); 1859 } 1860 1861 template<typename _RandomAccessIterator, typename _Compare> 1862 _GLIBCXX20_CONSTEXPR 1863 inline void 1864 __partial_sort(_RandomAccessIterator __first, 1865 _RandomAccessIterator __middle, 1866 _RandomAccessIterator __last, 1867 _Compare __comp) 1868 { 1869 std::__heap_select(__first, __middle, __last, __comp); 1870 std::__sort_heap(__first, __middle, __comp); 1871 } 1872 1873 /// This is a helper function for the sort routine. 1874 template<typename _RandomAccessIterator, typename _Size, typename _Compare> 1875 _GLIBCXX20_CONSTEXPR 1876 void 1877 __introsort_loop(_RandomAccessIterator __first, 1878 _RandomAccessIterator __last, 1879 _Size __depth_limit, _Compare __comp) 1880 { 1881 while (__last - __first > int(_S_threshold)) 1882 { 1883 if (__depth_limit == 0) 1884 { 1885 std::__partial_sort(__first, __last, __last, __comp); 1886 return; 1887 } 1888 --__depth_limit; 1889 _RandomAccessIterator __cut = 1890 std::__unguarded_partition_pivot(__first, __last, __comp); 1891 std::__introsort_loop(__cut, __last, __depth_limit, __comp); 1892 __last = __cut; 1893 } 1894 } 1895 1896 // sort 1897 1898 template<typename _RandomAccessIterator, typename _Compare> 1899 _GLIBCXX20_CONSTEXPR 1900 inline void 1901 __sort(_RandomAccessIterator __first, _RandomAccessIterator __last, 1902 _Compare __comp) 1903 { 1904 if (__first != __last) 1905 { 1906 std::__introsort_loop(__first, __last, 1907 std::__lg(__last - __first) * 2, 1908 __comp); 1909 std::__final_insertion_sort(__first, __last, __comp); 1910 } 1911 } 1912 1913 template<typename _RandomAccessIterator, typename _Size, typename _Compare> 1914 _GLIBCXX20_CONSTEXPR 1915 void 1916 __introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth, 1917 _RandomAccessIterator __last, _Size __depth_limit, 1918 _Compare __comp) 1919 { 1920 while (__last - __first > 3) 1921 { 1922 if (__depth_limit == 0) 1923 { 1924 std::__heap_select(__first, __nth + 1, __last, __comp); 1925 // Place the nth largest element in its final position. 1926 std::iter_swap(__first, __nth); 1927 return; 1928 } 1929 --__depth_limit; 1930 _RandomAccessIterator __cut = 1931 std::__unguarded_partition_pivot(__first, __last, __comp); 1932 if (__cut <= __nth) 1933 __first = __cut; 1934 else 1935 __last = __cut; 1936 } 1937 std::__insertion_sort(__first, __last, __comp); 1938 } 1939 1940 /// @endcond 1941 1942 // nth_element 1943 1944 // lower_bound moved to stl_algobase.h 1945 1946 /** 1947 * @brief Finds the first position in which `__val` could be inserted 1948 * without changing the ordering. 1949 * @ingroup binary_search_algorithms 1950 * @param __first An iterator to the start of a sorted range. 1951 * @param __last A past-the-end iterator for the sorted range. 1952 * @param __val The search term. 1953 * @param __comp A functor to use for comparisons. 1954 * @return An iterator pointing to the first element _not less than_ 1955 * `__val`, or `end()` if every element is less than `__val`. 1956 * @ingroup binary_search_algorithms 1957 * 1958 * The comparison function should have the same effects on ordering as 1959 * the function used for the initial sort. 1960 */ 1961 template<typename _ForwardIterator, typename _Tp, typename _Compare> 1962 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR 1963 inline _ForwardIterator 1964 lower_bound(_ForwardIterator __first, _ForwardIterator __last, 1965 const _Tp& __val, _Compare __comp) 1966 { 1967 // concept requirements 1968 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 1969 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 1970 typename iterator_traits<_ForwardIterator>::value_type, _Tp>) 1971 __glibcxx_requires_partitioned_lower_pred(__first, __last, 1972 __val, __comp); 1973 1974 return std::__lower_bound(__first, __last, __val, 1975 __gnu_cxx::__ops::__iter_comp_val(__comp)); 1976 } 1977 1978 template<typename _ForwardIterator, typename _Tp, typename _Compare> 1979 _GLIBCXX20_CONSTEXPR 1980 _ForwardIterator 1981 __upper_bound(_ForwardIterator __first, _ForwardIterator __last, 1982 const _Tp& __val, _Compare __comp) 1983 { 1984 typedef typename iterator_traits<_ForwardIterator>::difference_type 1985 _DistanceType; 1986 1987 _DistanceType __len = std::distance(__first, __last); 1988 1989 while (__len > 0) 1990 { 1991 _DistanceType __half = __len >> 1; 1992 _ForwardIterator __middle = __first; 1993 std::advance(__middle, __half); 1994 if (__comp(__val, __middle)) 1995 __len = __half; 1996 else 1997 { 1998 __first = __middle; 1999 ++__first; 2000 __len = __len - __half - 1; 2001 } 2002 } 2003 return __first; 2004 } 2005 2006 /** 2007 * @brief Finds the last position in which @p __val could be inserted 2008 * without changing the ordering. 2009 * @ingroup binary_search_algorithms 2010 * @param __first An iterator. 2011 * @param __last Another iterator. 2012 * @param __val The search term. 2013 * @return An iterator pointing to the first element greater than @p __val, 2014 * or end() if no elements are greater than @p __val. 2015 * @ingroup binary_search_algorithms 2016 */ 2017 template<typename _ForwardIterator, typename _Tp> 2018 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR 2019 inline _ForwardIterator 2020 upper_bound(_ForwardIterator __first, _ForwardIterator __last, 2021 const _Tp& __val) 2022 { 2023 // concept requirements 2024 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 2025 __glibcxx_function_requires(_LessThanOpConcept< 2026 _Tp, typename iterator_traits<_ForwardIterator>::value_type>) 2027 __glibcxx_requires_partitioned_upper(__first, __last, __val); 2028 2029 return std::__upper_bound(__first, __last, __val, 2030 __gnu_cxx::__ops::__val_less_iter()); 2031 } 2032 2033 /** 2034 * @brief Finds the last position in which @p __val could be inserted 2035 * without changing the ordering. 2036 * @ingroup binary_search_algorithms 2037 * @param __first An iterator. 2038 * @param __last Another iterator. 2039 * @param __val The search term. 2040 * @param __comp A functor to use for comparisons. 2041 * @return An iterator pointing to the first element greater than @p __val, 2042 * or end() if no elements are greater than @p __val. 2043 * @ingroup binary_search_algorithms 2044 * 2045 * The comparison function should have the same effects on ordering as 2046 * the function used for the initial sort. 2047 */ 2048 template<typename _ForwardIterator, typename _Tp, typename _Compare> 2049 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR 2050 inline _ForwardIterator 2051 upper_bound(_ForwardIterator __first, _ForwardIterator __last, 2052 const _Tp& __val, _Compare __comp) 2053 { 2054 // concept requirements 2055 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 2056 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 2057 _Tp, typename iterator_traits<_ForwardIterator>::value_type>) 2058 __glibcxx_requires_partitioned_upper_pred(__first, __last, 2059 __val, __comp); 2060 2061 return std::__upper_bound(__first, __last, __val, 2062 __gnu_cxx::__ops::__val_comp_iter(__comp)); 2063 } 2064 2065 template<typename _ForwardIterator, typename _Tp, 2066 typename _CompareItTp, typename _CompareTpIt> 2067 _GLIBCXX20_CONSTEXPR 2068 pair<_ForwardIterator, _ForwardIterator> 2069 __equal_range(_ForwardIterator __first, _ForwardIterator __last, 2070 const _Tp& __val, 2071 _CompareItTp __comp_it_val, _CompareTpIt __comp_val_it) 2072 { 2073 typedef typename iterator_traits<_ForwardIterator>::difference_type 2074 _DistanceType; 2075 2076 _DistanceType __len = std::distance(__first, __last); 2077 2078 while (__len > 0) 2079 { 2080 _DistanceType __half = __len >> 1; 2081 _ForwardIterator __middle = __first; 2082 std::advance(__middle, __half); 2083 if (__comp_it_val(__middle, __val)) 2084 { 2085 __first = __middle; 2086 ++__first; 2087 __len = __len - __half - 1; 2088 } 2089 else if (__comp_val_it(__val, __middle)) 2090 __len = __half; 2091 else 2092 { 2093 _ForwardIterator __left 2094 = std::__lower_bound(__first, __middle, __val, __comp_it_val); 2095 std::advance(__first, __len); 2096 _ForwardIterator __right 2097 = std::__upper_bound(++__middle, __first, __val, __comp_val_it); 2098 return pair<_ForwardIterator, _ForwardIterator>(__left, __right); 2099 } 2100 } 2101 return pair<_ForwardIterator, _ForwardIterator>(__first, __first); 2102 } 2103 2104 /** 2105 * @brief Finds the largest subrange in which @p __val could be inserted 2106 * at any place in it without changing the ordering. 2107 * @ingroup binary_search_algorithms 2108 * @param __first An iterator. 2109 * @param __last Another iterator. 2110 * @param __val The search term. 2111 * @return An pair of iterators defining the subrange. 2112 * @ingroup binary_search_algorithms 2113 * 2114 * This is equivalent to 2115 * @code 2116 * std::make_pair(lower_bound(__first, __last, __val), 2117 * upper_bound(__first, __last, __val)) 2118 * @endcode 2119 * but does not actually call those functions. 2120 */ 2121 template<typename _ForwardIterator, typename _Tp> 2122 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR 2123 inline pair<_ForwardIterator, _ForwardIterator> 2124 equal_range(_ForwardIterator __first, _ForwardIterator __last, 2125 const _Tp& __val) 2126 { 2127 // concept requirements 2128 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 2129 __glibcxx_function_requires(_LessThanOpConcept< 2130 typename iterator_traits<_ForwardIterator>::value_type, _Tp>) 2131 __glibcxx_function_requires(_LessThanOpConcept< 2132 _Tp, typename iterator_traits<_ForwardIterator>::value_type>) 2133 __glibcxx_requires_partitioned_lower(__first, __last, __val); 2134 __glibcxx_requires_partitioned_upper(__first, __last, __val); 2135 2136 return std::__equal_range(__first, __last, __val, 2137 __gnu_cxx::__ops::__iter_less_val(), 2138 __gnu_cxx::__ops::__val_less_iter()); 2139 } 2140 2141 /** 2142 * @brief Finds the largest subrange in which @p __val could be inserted 2143 * at any place in it without changing the ordering. 2144 * @param __first An iterator. 2145 * @param __last Another iterator. 2146 * @param __val The search term. 2147 * @param __comp A functor to use for comparisons. 2148 * @return An pair of iterators defining the subrange. 2149 * @ingroup binary_search_algorithms 2150 * 2151 * This is equivalent to 2152 * @code 2153 * std::make_pair(lower_bound(__first, __last, __val, __comp), 2154 * upper_bound(__first, __last, __val, __comp)) 2155 * @endcode 2156 * but does not actually call those functions. 2157 */ 2158 template<typename _ForwardIterator, typename _Tp, typename _Compare> 2159 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR 2160 inline pair<_ForwardIterator, _ForwardIterator> 2161 equal_range(_ForwardIterator __first, _ForwardIterator __last, 2162 const _Tp& __val, _Compare __comp) 2163 { 2164 // concept requirements 2165 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 2166 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 2167 typename iterator_traits<_ForwardIterator>::value_type, _Tp>) 2168 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 2169 _Tp, typename iterator_traits<_ForwardIterator>::value_type>) 2170 __glibcxx_requires_partitioned_lower_pred(__first, __last, 2171 __val, __comp); 2172 __glibcxx_requires_partitioned_upper_pred(__first, __last, 2173 __val, __comp); 2174 2175 return std::__equal_range(__first, __last, __val, 2176 __gnu_cxx::__ops::__iter_comp_val(__comp), 2177 __gnu_cxx::__ops::__val_comp_iter(__comp)); 2178 } 2179 2180 /** 2181 * @brief Determines whether an element exists in a range. 2182 * @ingroup binary_search_algorithms 2183 * @param __first An iterator. 2184 * @param __last Another iterator. 2185 * @param __val The search term. 2186 * @return True if @p __val (or its equivalent) is in [@p 2187 * __first,@p __last ]. 2188 * 2189 * Note that this does not actually return an iterator to @p __val. For 2190 * that, use std::find or a container's specialized find member functions. 2191 */ 2192 template<typename _ForwardIterator, typename _Tp> 2193 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR 2194 bool 2195 binary_search(_ForwardIterator __first, _ForwardIterator __last, 2196 const _Tp& __val) 2197 { 2198 // concept requirements 2199 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 2200 __glibcxx_function_requires(_LessThanOpConcept< 2201 _Tp, typename iterator_traits<_ForwardIterator>::value_type>) 2202 __glibcxx_requires_partitioned_lower(__first, __last, __val); 2203 __glibcxx_requires_partitioned_upper(__first, __last, __val); 2204 2205 _ForwardIterator __i 2206 = std::__lower_bound(__first, __last, __val, 2207 __gnu_cxx::__ops::__iter_less_val()); 2208 return __i != __last && !(__val < *__i); 2209 } 2210 2211 /** 2212 * @brief Determines whether an element exists in a range. 2213 * @ingroup binary_search_algorithms 2214 * @param __first An iterator. 2215 * @param __last Another iterator. 2216 * @param __val The search term. 2217 * @param __comp A functor to use for comparisons. 2218 * @return True if @p __val (or its equivalent) is in @p [__first,__last]. 2219 * 2220 * Note that this does not actually return an iterator to @p __val. For 2221 * that, use std::find or a container's specialized find member functions. 2222 * 2223 * The comparison function should have the same effects on ordering as 2224 * the function used for the initial sort. 2225 */ 2226 template<typename _ForwardIterator, typename _Tp, typename _Compare> 2227 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR 2228 bool 2229 binary_search(_ForwardIterator __first, _ForwardIterator __last, 2230 const _Tp& __val, _Compare __comp) 2231 { 2232 // concept requirements 2233 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 2234 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 2235 _Tp, typename iterator_traits<_ForwardIterator>::value_type>) 2236 __glibcxx_requires_partitioned_lower_pred(__first, __last, 2237 __val, __comp); 2238 __glibcxx_requires_partitioned_upper_pred(__first, __last, 2239 __val, __comp); 2240 2241 _ForwardIterator __i 2242 = std::__lower_bound(__first, __last, __val, 2243 __gnu_cxx::__ops::__iter_comp_val(__comp)); 2244 return __i != __last && !bool(__comp(__val, *__i)); 2245 } 2246 2247 // merge 2248 2249 /// This is a helper function for the __merge_adaptive routines. 2250 template<typename _InputIterator1, typename _InputIterator2, 2251 typename _OutputIterator, typename _Compare> 2252 void 2253 __move_merge_adaptive(_InputIterator1 __first1, _InputIterator1 __last1, 2254 _InputIterator2 __first2, _InputIterator2 __last2, 2255 _OutputIterator __result, _Compare __comp) 2256 { 2257 while (__first1 != __last1 && __first2 != __last2) 2258 { 2259 if (__comp(__first2, __first1)) 2260 { 2261 *__result = _GLIBCXX_MOVE(*__first2); 2262 ++__first2; 2263 } 2264 else 2265 { 2266 *__result = _GLIBCXX_MOVE(*__first1); 2267 ++__first1; 2268 } 2269 ++__result; 2270 } 2271 if (__first1 != __last1) 2272 _GLIBCXX_MOVE3(__first1, __last1, __result); 2273 } 2274 2275 /// This is a helper function for the __merge_adaptive routines. 2276 template<typename _BidirectionalIterator1, typename _BidirectionalIterator2, 2277 typename _BidirectionalIterator3, typename _Compare> 2278 void 2279 __move_merge_adaptive_backward(_BidirectionalIterator1 __first1, 2280 _BidirectionalIterator1 __last1, 2281 _BidirectionalIterator2 __first2, 2282 _BidirectionalIterator2 __last2, 2283 _BidirectionalIterator3 __result, 2284 _Compare __comp) 2285 { 2286 if (__first1 == __last1) 2287 { 2288 _GLIBCXX_MOVE_BACKWARD3(__first2, __last2, __result); 2289 return; 2290 } 2291 else if (__first2 == __last2) 2292 return; 2293 2294 --__last1; 2295 --__last2; 2296 while (true) 2297 { 2298 if (__comp(__last2, __last1)) 2299 { 2300 *--__result = _GLIBCXX_MOVE(*__last1); 2301 if (__first1 == __last1) 2302 { 2303 _GLIBCXX_MOVE_BACKWARD3(__first2, ++__last2, __result); 2304 return; 2305 } 2306 --__last1; 2307 } 2308 else 2309 { 2310 *--__result = _GLIBCXX_MOVE(*__last2); 2311 if (__first2 == __last2) 2312 return; 2313 --__last2; 2314 } 2315 } 2316 } 2317 2318 /// This is a helper function for the merge routines. 2319 template<typename _BidirectionalIterator1, typename _BidirectionalIterator2, 2320 typename _Distance> 2321 _BidirectionalIterator1 2322 __rotate_adaptive(_BidirectionalIterator1 __first, 2323 _BidirectionalIterator1 __middle, 2324 _BidirectionalIterator1 __last, 2325 _Distance __len1, _Distance __len2, 2326 _BidirectionalIterator2 __buffer, 2327 _Distance __buffer_size) 2328 { 2329 _BidirectionalIterator2 __buffer_end; 2330 if (__len1 > __len2 && __len2 <= __buffer_size) 2331 { 2332 if (__len2) 2333 { 2334 __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer); 2335 _GLIBCXX_MOVE_BACKWARD3(__first, __middle, __last); 2336 return _GLIBCXX_MOVE3(__buffer, __buffer_end, __first); 2337 } 2338 else 2339 return __first; 2340 } 2341 else if (__len1 <= __buffer_size) 2342 { 2343 if (__len1) 2344 { 2345 __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer); 2346 _GLIBCXX_MOVE3(__middle, __last, __first); 2347 return _GLIBCXX_MOVE_BACKWARD3(__buffer, __buffer_end, __last); 2348 } 2349 else 2350 return __last; 2351 } 2352 else 2353 return std::rotate(__first, __middle, __last); 2354 } 2355 2356 /// This is a helper function for the merge routines. 2357 template<typename _BidirectionalIterator, typename _Distance, 2358 typename _Pointer, typename _Compare> 2359 void 2360 __merge_adaptive(_BidirectionalIterator __first, 2361 _BidirectionalIterator __middle, 2362 _BidirectionalIterator __last, 2363 _Distance __len1, _Distance __len2, 2364 _Pointer __buffer, _Compare __comp) 2365 { 2366 if (__len1 <= __len2) 2367 { 2368 _Pointer __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer); 2369 std::__move_merge_adaptive(__buffer, __buffer_end, __middle, __last, 2370 __first, __comp); 2371 } 2372 else 2373 { 2374 _Pointer __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer); 2375 std::__move_merge_adaptive_backward(__first, __middle, __buffer, 2376 __buffer_end, __last, __comp); 2377 } 2378 } 2379 2380 template<typename _BidirectionalIterator, typename _Distance, 2381 typename _Pointer, typename _Compare> 2382 void 2383 __merge_adaptive_resize(_BidirectionalIterator __first, 2384 _BidirectionalIterator __middle, 2385 _BidirectionalIterator __last, 2386 _Distance __len1, _Distance __len2, 2387 _Pointer __buffer, _Distance __buffer_size, 2388 _Compare __comp) 2389 { 2390 if (__len1 <= __buffer_size || __len2 <= __buffer_size) 2391 std::__merge_adaptive(__first, __middle, __last, 2392 __len1, __len2, __buffer, __comp); 2393 else 2394 { 2395 _BidirectionalIterator __first_cut = __first; 2396 _BidirectionalIterator __second_cut = __middle; 2397 _Distance __len11 = 0; 2398 _Distance __len22 = 0; 2399 if (__len1 > __len2) 2400 { 2401 __len11 = __len1 / 2; 2402 std::advance(__first_cut, __len11); 2403 __second_cut 2404 = std::__lower_bound(__middle, __last, *__first_cut, 2405 __gnu_cxx::__ops::__iter_comp_val(__comp)); 2406 __len22 = std::distance(__middle, __second_cut); 2407 } 2408 else 2409 { 2410 __len22 = __len2 / 2; 2411 std::advance(__second_cut, __len22); 2412 __first_cut 2413 = std::__upper_bound(__first, __middle, *__second_cut, 2414 __gnu_cxx::__ops::__val_comp_iter(__comp)); 2415 __len11 = std::distance(__first, __first_cut); 2416 } 2417 2418 _BidirectionalIterator __new_middle 2419 = std::__rotate_adaptive(__first_cut, __middle, __second_cut, 2420 _Distance(__len1 - __len11), __len22, 2421 __buffer, __buffer_size); 2422 std::__merge_adaptive_resize(__first, __first_cut, __new_middle, 2423 __len11, __len22, 2424 __buffer, __buffer_size, __comp); 2425 std::__merge_adaptive_resize(__new_middle, __second_cut, __last, 2426 _Distance(__len1 - __len11), 2427 _Distance(__len2 - __len22), 2428 __buffer, __buffer_size, __comp); 2429 } 2430 } 2431 2432 /// This is a helper function for the merge routines. 2433 template<typename _BidirectionalIterator, typename _Distance, 2434 typename _Compare> 2435 _GLIBCXX26_CONSTEXPR 2436 void 2437 __merge_without_buffer(_BidirectionalIterator __first, 2438 _BidirectionalIterator __middle, 2439 _BidirectionalIterator __last, 2440 _Distance __len1, _Distance __len2, 2441 _Compare __comp) 2442 { 2443 if (__len1 == 0 || __len2 == 0) 2444 return; 2445 2446 if (__len1 + __len2 == 2) 2447 { 2448 if (__comp(__middle, __first)) 2449 std::iter_swap(__first, __middle); 2450 return; 2451 } 2452 2453 _BidirectionalIterator __first_cut = __first; 2454 _BidirectionalIterator __second_cut = __middle; 2455 _Distance __len11 = 0; 2456 _Distance __len22 = 0; 2457 if (__len1 > __len2) 2458 { 2459 __len11 = __len1 / 2; 2460 std::advance(__first_cut, __len11); 2461 __second_cut 2462 = std::__lower_bound(__middle, __last, *__first_cut, 2463 __gnu_cxx::__ops::__iter_comp_val(__comp)); 2464 __len22 = std::distance(__middle, __second_cut); 2465 } 2466 else 2467 { 2468 __len22 = __len2 / 2; 2469 std::advance(__second_cut, __len22); 2470 __first_cut 2471 = std::__upper_bound(__first, __middle, *__second_cut, 2472 __gnu_cxx::__ops::__val_comp_iter(__comp)); 2473 __len11 = std::distance(__first, __first_cut); 2474 } 2475 2476 _BidirectionalIterator __new_middle 2477 = std::rotate(__first_cut, __middle, __second_cut); 2478 std::__merge_without_buffer(__first, __first_cut, __new_middle, 2479 __len11, __len22, __comp); 2480 std::__merge_without_buffer(__new_middle, __second_cut, __last, 2481 __len1 - __len11, __len2 - __len22, __comp); 2482 } 2483 2484 template<typename _BidirectionalIterator, typename _Compare> 2485 _GLIBCXX26_CONSTEXPR 2486 void 2487 __inplace_merge(_BidirectionalIterator __first, 2488 _BidirectionalIterator __middle, 2489 _BidirectionalIterator __last, 2490 _Compare __comp) 2491 { 2492 typedef typename iterator_traits<_BidirectionalIterator>::value_type 2493 _ValueType; 2494 typedef typename iterator_traits<_BidirectionalIterator>::difference_type 2495 _DistanceType; 2496 2497 if (__first == __middle || __middle == __last) 2498 return; 2499 2500 const _DistanceType __len1 = std::distance(__first, __middle); 2501 const _DistanceType __len2 = std::distance(__middle, __last); 2502 2503 #if _GLIBCXX_HOSTED 2504 # if __glibcxx_constexpr_algorithms >= 202306L // >= C++26 2505 if consteval { 2506 return std::__merge_without_buffer 2507 (__first, __middle, __last, __len1, __len2, __comp); 2508 } 2509 # endif 2510 typedef _Temporary_buffer<_BidirectionalIterator, _ValueType> _TmpBuf; 2511 // __merge_adaptive will use a buffer for the smaller of 2512 // [first,middle) and [middle,last). 2513 _TmpBuf __buf(__first, std::min(__len1, __len2)); 2514 2515 if (__builtin_expect(__buf.size() == __buf.requested_size(), true)) 2516 std::__merge_adaptive 2517 (__first, __middle, __last, __len1, __len2, __buf.begin(), __comp); 2518 else if (__builtin_expect(__buf.begin() == 0, false)) 2519 std::__merge_without_buffer 2520 (__first, __middle, __last, __len1, __len2, __comp); 2521 else 2522 std::__merge_adaptive_resize 2523 (__first, __middle, __last, __len1, __len2, __buf.begin(), 2524 _DistanceType(__buf.size()), __comp); 2525 #else 2526 std::__merge_without_buffer 2527 (__first, __middle, __last, __len1, __len2, __comp); 2528 #endif 2529 } 2530 2531 /** 2532 * @brief Merges two sorted ranges in place. 2533 * @ingroup sorting_algorithms 2534 * @param __first An iterator. 2535 * @param __middle Another iterator. 2536 * @param __last Another iterator. 2537 * @return Nothing. 2538 * 2539 * Merges two sorted and consecutive ranges, [__first,__middle) and 2540 * [__middle,__last), and puts the result in [__first,__last). The 2541 * output will be sorted. The sort is @e stable, that is, for 2542 * equivalent elements in the two ranges, elements from the first 2543 * range will always come before elements from the second. 2544 * 2545 * If enough additional memory is available, this takes (__last-__first)-1 2546 * comparisons. Otherwise an NlogN algorithm is used, where N is 2547 * distance(__first,__last). 2548 */ 2549 template<typename _BidirectionalIterator> 2550 _GLIBCXX26_CONSTEXPR 2551 inline void 2552 inplace_merge(_BidirectionalIterator __first, 2553 _BidirectionalIterator __middle, 2554 _BidirectionalIterator __last) 2555 { 2556 // concept requirements 2557 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept< 2558 _BidirectionalIterator>) 2559 __glibcxx_function_requires(_LessThanComparableConcept< 2560 typename iterator_traits<_BidirectionalIterator>::value_type>) 2561 __glibcxx_requires_sorted(__first, __middle); 2562 __glibcxx_requires_sorted(__middle, __last); 2563 __glibcxx_requires_irreflexive(__first, __last); 2564 2565 std::__inplace_merge(__first, __middle, __last, 2566 __gnu_cxx::__ops::__iter_less_iter()); 2567 } 2568 2569 /** 2570 * @brief Merges two sorted ranges in place. 2571 * @ingroup sorting_algorithms 2572 * @param __first An iterator. 2573 * @param __middle Another iterator. 2574 * @param __last Another iterator. 2575 * @param __comp A functor to use for comparisons. 2576 * @return Nothing. 2577 * 2578 * Merges two sorted and consecutive ranges, [__first,__middle) and 2579 * [middle,last), and puts the result in [__first,__last). The output will 2580 * be sorted. The sort is @e stable, that is, for equivalent 2581 * elements in the two ranges, elements from the first range will always 2582 * come before elements from the second. 2583 * 2584 * If enough additional memory is available, this takes (__last-__first)-1 2585 * comparisons. Otherwise an NlogN algorithm is used, where N is 2586 * distance(__first,__last). 2587 * 2588 * The comparison function should have the same effects on ordering as 2589 * the function used for the initial sort. 2590 */ 2591 template<typename _BidirectionalIterator, typename _Compare> 2592 _GLIBCXX26_CONSTEXPR 2593 inline void 2594 inplace_merge(_BidirectionalIterator __first, 2595 _BidirectionalIterator __middle, 2596 _BidirectionalIterator __last, 2597 _Compare __comp) 2598 { 2599 // concept requirements 2600 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept< 2601 _BidirectionalIterator>) 2602 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 2603 typename iterator_traits<_BidirectionalIterator>::value_type, 2604 typename iterator_traits<_BidirectionalIterator>::value_type>) 2605 __glibcxx_requires_sorted_pred(__first, __middle, __comp); 2606 __glibcxx_requires_sorted_pred(__middle, __last, __comp); 2607 __glibcxx_requires_irreflexive_pred(__first, __last, __comp); 2608 2609 std::__inplace_merge(__first, __middle, __last, 2610 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 2611 } 2612 2613 2614 /// This is a helper function for the __merge_sort_loop routines. 2615 template<typename _InputIterator, typename _OutputIterator, 2616 typename _Compare> 2617 _OutputIterator 2618 __move_merge(_InputIterator __first1, _InputIterator __last1, 2619 _InputIterator __first2, _InputIterator __last2, 2620 _OutputIterator __result, _Compare __comp) 2621 { 2622 while (__first1 != __last1 && __first2 != __last2) 2623 { 2624 if (__comp(__first2, __first1)) 2625 { 2626 *__result = _GLIBCXX_MOVE(*__first2); 2627 ++__first2; 2628 } 2629 else 2630 { 2631 *__result = _GLIBCXX_MOVE(*__first1); 2632 ++__first1; 2633 } 2634 ++__result; 2635 } 2636 return _GLIBCXX_MOVE3(__first2, __last2, 2637 _GLIBCXX_MOVE3(__first1, __last1, 2638 __result)); 2639 } 2640 2641 template<typename _RandomAccessIterator1, typename _RandomAccessIterator2, 2642 typename _Distance, typename _Compare> 2643 void 2644 __merge_sort_loop(_RandomAccessIterator1 __first, 2645 _RandomAccessIterator1 __last, 2646 _RandomAccessIterator2 __result, _Distance __step_size, 2647 _Compare __comp) 2648 { 2649 const _Distance __two_step = 2 * __step_size; 2650 2651 while (__last - __first >= __two_step) 2652 { 2653 __result = std::__move_merge(__first, __first + __step_size, 2654 __first + __step_size, 2655 __first + __two_step, 2656 __result, __comp); 2657 __first += __two_step; 2658 } 2659 __step_size = std::min(_Distance(__last - __first), __step_size); 2660 2661 std::__move_merge(__first, __first + __step_size, 2662 __first + __step_size, __last, __result, __comp); 2663 } 2664 2665 template<typename _RandomAccessIterator, typename _Distance, 2666 typename _Compare> 2667 _GLIBCXX20_CONSTEXPR 2668 void 2669 __chunk_insertion_sort(_RandomAccessIterator __first, 2670 _RandomAccessIterator __last, 2671 _Distance __chunk_size, _Compare __comp) 2672 { 2673 while (__last - __first >= __chunk_size) 2674 { 2675 std::__insertion_sort(__first, __first + __chunk_size, __comp); 2676 __first += __chunk_size; 2677 } 2678 std::__insertion_sort(__first, __last, __comp); 2679 } 2680 2681 enum { _S_chunk_size = 7 }; 2682 2683 template<typename _RandomAccessIterator, typename _Pointer, typename _Compare> 2684 void 2685 __merge_sort_with_buffer(_RandomAccessIterator __first, 2686 _RandomAccessIterator __last, 2687 _Pointer __buffer, _Compare __comp) 2688 { 2689 typedef typename iterator_traits<_RandomAccessIterator>::difference_type 2690 _Distance; 2691 2692 const _Distance __len = __last - __first; 2693 const _Pointer __buffer_last = __buffer + __len; 2694 2695 _Distance __step_size = _S_chunk_size; 2696 std::__chunk_insertion_sort(__first, __last, __step_size, __comp); 2697 2698 while (__step_size < __len) 2699 { 2700 std::__merge_sort_loop(__first, __last, __buffer, 2701 __step_size, __comp); 2702 __step_size *= 2; 2703 std::__merge_sort_loop(__buffer, __buffer_last, __first, 2704 __step_size, __comp); 2705 __step_size *= 2; 2706 } 2707 } 2708 2709 template<typename _RandomAccessIterator, typename _Pointer, typename _Compare> 2710 void 2711 __stable_sort_adaptive(_RandomAccessIterator __first, 2712 _RandomAccessIterator __middle, 2713 _RandomAccessIterator __last, 2714 _Pointer __buffer, _Compare __comp) 2715 { 2716 std::__merge_sort_with_buffer(__first, __middle, __buffer, __comp); 2717 std::__merge_sort_with_buffer(__middle, __last, __buffer, __comp); 2718 2719 std::__merge_adaptive(__first, __middle, __last, 2720 __middle - __first, __last - __middle, 2721 __buffer, __comp); 2722 } 2723 2724 template<typename _RandomAccessIterator, typename _Pointer, 2725 typename _Distance, typename _Compare> 2726 void 2727 __stable_sort_adaptive_resize(_RandomAccessIterator __first, 2728 _RandomAccessIterator __last, 2729 _Pointer __buffer, _Distance __buffer_size, 2730 _Compare __comp) 2731 { 2732 const _Distance __len = (__last - __first + 1) / 2; 2733 const _RandomAccessIterator __middle = __first + __len; 2734 if (__len > __buffer_size) 2735 { 2736 std::__stable_sort_adaptive_resize(__first, __middle, __buffer, 2737 __buffer_size, __comp); 2738 std::__stable_sort_adaptive_resize(__middle, __last, __buffer, 2739 __buffer_size, __comp); 2740 std::__merge_adaptive_resize(__first, __middle, __last, 2741 _Distance(__middle - __first), 2742 _Distance(__last - __middle), 2743 __buffer, __buffer_size, 2744 __comp); 2745 } 2746 else 2747 std::__stable_sort_adaptive(__first, __middle, __last, 2748 __buffer, __comp); 2749 } 2750 2751 /// This is a helper function for the stable sorting routines. 2752 template<typename _RandomAccessIterator, typename _Compare> 2753 _GLIBCXX26_CONSTEXPR 2754 void 2755 __inplace_stable_sort(_RandomAccessIterator __first, 2756 _RandomAccessIterator __last, _Compare __comp) 2757 { 2758 if (__last - __first < 15) 2759 { 2760 std::__insertion_sort(__first, __last, __comp); 2761 return; 2762 } 2763 _RandomAccessIterator __middle = __first + (__last - __first) / 2; 2764 std::__inplace_stable_sort(__first, __middle, __comp); 2765 std::__inplace_stable_sort(__middle, __last, __comp); 2766 std::__merge_without_buffer(__first, __middle, __last, 2767 __middle - __first, 2768 __last - __middle, 2769 __comp); 2770 } 2771 2772 // stable_sort 2773 2774 // Set algorithms: includes, set_union, set_intersection, set_difference, 2775 // set_symmetric_difference. All of these algorithms have the precondition 2776 // that their input ranges are sorted and the postcondition that their output 2777 // ranges are sorted. 2778 2779 template<typename _InputIterator1, typename _InputIterator2, 2780 typename _Compare> 2781 _GLIBCXX20_CONSTEXPR 2782 bool 2783 __includes(_InputIterator1 __first1, _InputIterator1 __last1, 2784 _InputIterator2 __first2, _InputIterator2 __last2, 2785 _Compare __comp) 2786 { 2787 while (__first1 != __last1 && __first2 != __last2) 2788 { 2789 if (__comp(__first2, __first1)) 2790 return false; 2791 if (!__comp(__first1, __first2)) 2792 ++__first2; 2793 ++__first1; 2794 } 2795 2796 return __first2 == __last2; 2797 } 2798 2799 /** 2800 * @brief Determines whether all elements of a sequence exists in a range. 2801 * @param __first1 Start of search range. 2802 * @param __last1 End of search range. 2803 * @param __first2 Start of sequence 2804 * @param __last2 End of sequence. 2805 * @return True if each element in [__first2,__last2) is contained in order 2806 * within [__first1,__last1). False otherwise. 2807 * @ingroup set_algorithms 2808 * 2809 * This operation expects both [__first1,__last1) and 2810 * [__first2,__last2) to be sorted. Searches for the presence of 2811 * each element in [__first2,__last2) within [__first1,__last1). 2812 * The iterators over each range only move forward, so this is a 2813 * linear algorithm. If an element in [__first2,__last2) is not 2814 * found before the search iterator reaches @p __last2, false is 2815 * returned. 2816 */ 2817 template<typename _InputIterator1, typename _InputIterator2> 2818 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR 2819 inline bool 2820 includes(_InputIterator1 __first1, _InputIterator1 __last1, 2821 _InputIterator2 __first2, _InputIterator2 __last2) 2822 { 2823 // concept requirements 2824 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 2825 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 2826 __glibcxx_function_requires(_LessThanOpConcept< 2827 typename iterator_traits<_InputIterator1>::value_type, 2828 typename iterator_traits<_InputIterator2>::value_type>) 2829 __glibcxx_function_requires(_LessThanOpConcept< 2830 typename iterator_traits<_InputIterator2>::value_type, 2831 typename iterator_traits<_InputIterator1>::value_type>) 2832 __glibcxx_requires_sorted_set(__first1, __last1, __first2); 2833 __glibcxx_requires_sorted_set(__first2, __last2, __first1); 2834 __glibcxx_requires_irreflexive2(__first1, __last1); 2835 __glibcxx_requires_irreflexive2(__first2, __last2); 2836 2837 return std::__includes(__first1, __last1, __first2, __last2, 2838 __gnu_cxx::__ops::__iter_less_iter()); 2839 } 2840 2841 /** 2842 * @brief Determines whether all elements of a sequence exists in a range 2843 * using comparison. 2844 * @ingroup set_algorithms 2845 * @param __first1 Start of search range. 2846 * @param __last1 End of search range. 2847 * @param __first2 Start of sequence 2848 * @param __last2 End of sequence. 2849 * @param __comp Comparison function to use. 2850 * @return True if each element in [__first2,__last2) is contained 2851 * in order within [__first1,__last1) according to comp. False 2852 * otherwise. @ingroup set_algorithms 2853 * 2854 * This operation expects both [__first1,__last1) and 2855 * [__first2,__last2) to be sorted. Searches for the presence of 2856 * each element in [__first2,__last2) within [__first1,__last1), 2857 * using comp to decide. The iterators over each range only move 2858 * forward, so this is a linear algorithm. If an element in 2859 * [__first2,__last2) is not found before the search iterator 2860 * reaches @p __last2, false is returned. 2861 */ 2862 template<typename _InputIterator1, typename _InputIterator2, 2863 typename _Compare> 2864 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR 2865 inline bool 2866 includes(_InputIterator1 __first1, _InputIterator1 __last1, 2867 _InputIterator2 __first2, _InputIterator2 __last2, 2868 _Compare __comp) 2869 { 2870 // concept requirements 2871 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 2872 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 2873 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 2874 typename iterator_traits<_InputIterator1>::value_type, 2875 typename iterator_traits<_InputIterator2>::value_type>) 2876 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 2877 typename iterator_traits<_InputIterator2>::value_type, 2878 typename iterator_traits<_InputIterator1>::value_type>) 2879 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp); 2880 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp); 2881 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp); 2882 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp); 2883 2884 return std::__includes(__first1, __last1, __first2, __last2, 2885 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 2886 } 2887 2888 // nth_element 2889 // merge 2890 // set_difference 2891 // set_intersection 2892 // set_union 2893 // stable_sort 2894 // set_symmetric_difference 2895 // min_element 2896 // max_element 2897 2898 template<typename _BidirectionalIterator, typename _Compare> 2899 _GLIBCXX20_CONSTEXPR 2900 bool 2901 __next_permutation(_BidirectionalIterator __first, 2902 _BidirectionalIterator __last, _Compare __comp) 2903 { 2904 if (__first == __last) 2905 return false; 2906 _BidirectionalIterator __i = __first; 2907 ++__i; 2908 if (__i == __last) 2909 return false; 2910 __i = __last; 2911 --__i; 2912 2913 for(;;) 2914 { 2915 _BidirectionalIterator __ii = __i; 2916 --__i; 2917 if (__comp(__i, __ii)) 2918 { 2919 _BidirectionalIterator __j = __last; 2920 while (!__comp(__i, --__j)) 2921 {} 2922 std::iter_swap(__i, __j); 2923 std::__reverse(__ii, __last, 2924 std::__iterator_category(__first)); 2925 return true; 2926 } 2927 if (__i == __first) 2928 { 2929 std::__reverse(__first, __last, 2930 std::__iterator_category(__first)); 2931 return false; 2932 } 2933 } 2934 } 2935 2936 /** 2937 * @brief Permute range into the next @e dictionary ordering. 2938 * @ingroup sorting_algorithms 2939 * @param __first Start of range. 2940 * @param __last End of range. 2941 * @return False if wrapped to first permutation, true otherwise. 2942 * 2943 * Treats all permutations of the range as a set of @e dictionary sorted 2944 * sequences. Permutes the current sequence into the next one of this set. 2945 * Returns true if there are more sequences to generate. If the sequence 2946 * is the largest of the set, the smallest is generated and false returned. 2947 */ 2948 template<typename _BidirectionalIterator> 2949 _GLIBCXX20_CONSTEXPR 2950 inline bool 2951 next_permutation(_BidirectionalIterator __first, 2952 _BidirectionalIterator __last) 2953 { 2954 // concept requirements 2955 __glibcxx_function_requires(_BidirectionalIteratorConcept< 2956 _BidirectionalIterator>) 2957 __glibcxx_function_requires(_LessThanComparableConcept< 2958 typename iterator_traits<_BidirectionalIterator>::value_type>) 2959 __glibcxx_requires_valid_range(__first, __last); 2960 __glibcxx_requires_irreflexive(__first, __last); 2961 2962 return std::__next_permutation 2963 (__first, __last, __gnu_cxx::__ops::__iter_less_iter()); 2964 } 2965 2966 /** 2967 * @brief Permute range into the next @e dictionary ordering using 2968 * comparison functor. 2969 * @ingroup sorting_algorithms 2970 * @param __first Start of range. 2971 * @param __last End of range. 2972 * @param __comp A comparison functor. 2973 * @return False if wrapped to first permutation, true otherwise. 2974 * 2975 * Treats all permutations of the range [__first,__last) as a set of 2976 * @e dictionary sorted sequences ordered by @p __comp. Permutes the current 2977 * sequence into the next one of this set. Returns true if there are more 2978 * sequences to generate. If the sequence is the largest of the set, the 2979 * smallest is generated and false returned. 2980 */ 2981 template<typename _BidirectionalIterator, typename _Compare> 2982 _GLIBCXX20_CONSTEXPR 2983 inline bool 2984 next_permutation(_BidirectionalIterator __first, 2985 _BidirectionalIterator __last, _Compare __comp) 2986 { 2987 // concept requirements 2988 __glibcxx_function_requires(_BidirectionalIteratorConcept< 2989 _BidirectionalIterator>) 2990 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 2991 typename iterator_traits<_BidirectionalIterator>::value_type, 2992 typename iterator_traits<_BidirectionalIterator>::value_type>) 2993 __glibcxx_requires_valid_range(__first, __last); 2994 __glibcxx_requires_irreflexive_pred(__first, __last, __comp); 2995 2996 return std::__next_permutation 2997 (__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp)); 2998 } 2999 3000 template<typename _BidirectionalIterator, typename _Compare> 3001 _GLIBCXX20_CONSTEXPR 3002 bool 3003 __prev_permutation(_BidirectionalIterator __first, 3004 _BidirectionalIterator __last, _Compare __comp) 3005 { 3006 if (__first == __last) 3007 return false; 3008 _BidirectionalIterator __i = __first; 3009 ++__i; 3010 if (__i == __last) 3011 return false; 3012 __i = __last; 3013 --__i; 3014 3015 for(;;) 3016 { 3017 _BidirectionalIterator __ii = __i; 3018 --__i; 3019 if (__comp(__ii, __i)) 3020 { 3021 _BidirectionalIterator __j = __last; 3022 while (!__comp(--__j, __i)) 3023 {} 3024 std::iter_swap(__i, __j); 3025 std::__reverse(__ii, __last, 3026 std::__iterator_category(__first)); 3027 return true; 3028 } 3029 if (__i == __first) 3030 { 3031 std::__reverse(__first, __last, 3032 std::__iterator_category(__first)); 3033 return false; 3034 } 3035 } 3036 } 3037 3038 /** 3039 * @brief Permute range into the previous @e dictionary ordering. 3040 * @ingroup sorting_algorithms 3041 * @param __first Start of range. 3042 * @param __last End of range. 3043 * @return False if wrapped to last permutation, true otherwise. 3044 * 3045 * Treats all permutations of the range as a set of @e dictionary sorted 3046 * sequences. Permutes the current sequence into the previous one of this 3047 * set. Returns true if there are more sequences to generate. If the 3048 * sequence is the smallest of the set, the largest is generated and false 3049 * returned. 3050 */ 3051 template<typename _BidirectionalIterator> 3052 _GLIBCXX20_CONSTEXPR 3053 inline bool 3054 prev_permutation(_BidirectionalIterator __first, 3055 _BidirectionalIterator __last) 3056 { 3057 // concept requirements 3058 __glibcxx_function_requires(_BidirectionalIteratorConcept< 3059 _BidirectionalIterator>) 3060 __glibcxx_function_requires(_LessThanComparableConcept< 3061 typename iterator_traits<_BidirectionalIterator>::value_type>) 3062 __glibcxx_requires_valid_range(__first, __last); 3063 __glibcxx_requires_irreflexive(__first, __last); 3064 3065 return std::__prev_permutation(__first, __last, 3066 __gnu_cxx::__ops::__iter_less_iter()); 3067 } 3068 3069 /** 3070 * @brief Permute range into the previous @e dictionary ordering using 3071 * comparison functor. 3072 * @ingroup sorting_algorithms 3073 * @param __first Start of range. 3074 * @param __last End of range. 3075 * @param __comp A comparison functor. 3076 * @return False if wrapped to last permutation, true otherwise. 3077 * 3078 * Treats all permutations of the range [__first,__last) as a set of 3079 * @e dictionary sorted sequences ordered by @p __comp. Permutes the current 3080 * sequence into the previous one of this set. Returns true if there are 3081 * more sequences to generate. If the sequence is the smallest of the set, 3082 * the largest is generated and false returned. 3083 */ 3084 template<typename _BidirectionalIterator, typename _Compare> 3085 _GLIBCXX20_CONSTEXPR 3086 inline bool 3087 prev_permutation(_BidirectionalIterator __first, 3088 _BidirectionalIterator __last, _Compare __comp) 3089 { 3090 // concept requirements 3091 __glibcxx_function_requires(_BidirectionalIteratorConcept< 3092 _BidirectionalIterator>) 3093 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 3094 typename iterator_traits<_BidirectionalIterator>::value_type, 3095 typename iterator_traits<_BidirectionalIterator>::value_type>) 3096 __glibcxx_requires_valid_range(__first, __last); 3097 __glibcxx_requires_irreflexive_pred(__first, __last, __comp); 3098 3099 return std::__prev_permutation(__first, __last, 3100 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 3101 } 3102 3103 // replace 3104 // replace_if 3105 3106 template<typename _InputIterator, typename _OutputIterator, 3107 typename _Predicate, typename _Tp> 3108 _GLIBCXX20_CONSTEXPR 3109 _OutputIterator 3110 __replace_copy_if(_InputIterator __first, _InputIterator __last, 3111 _OutputIterator __result, 3112 _Predicate __pred, const _Tp& __new_value) 3113 { 3114 for (; __first != __last; ++__first, (void)++__result) 3115 if (__pred(__first)) 3116 *__result = __new_value; 3117 else 3118 *__result = *__first; 3119 return __result; 3120 } 3121 3122 /** 3123 * @brief Copy a sequence, replacing each element of one value with another 3124 * value. 3125 * @param __first An input iterator. 3126 * @param __last An input iterator. 3127 * @param __result An output iterator. 3128 * @param __old_value The value to be replaced. 3129 * @param __new_value The replacement value. 3130 * @return The end of the output sequence, @p result+(last-first). 3131 * 3132 * Copies each element in the input range @p [__first,__last) to the 3133 * output range @p [__result,__result+(__last-__first)) replacing elements 3134 * equal to @p __old_value with @p __new_value. 3135 */ 3136 template<typename _InputIterator, typename _OutputIterator, typename _Tp> 3137 _GLIBCXX20_CONSTEXPR 3138 inline _OutputIterator 3139 replace_copy(_InputIterator __first, _InputIterator __last, 3140 _OutputIterator __result, 3141 const _Tp& __old_value, const _Tp& __new_value) 3142 { 3143 // concept requirements 3144 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 3145 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 3146 typename iterator_traits<_InputIterator>::value_type>) 3147 __glibcxx_function_requires(_EqualOpConcept< 3148 typename iterator_traits<_InputIterator>::value_type, _Tp>) 3149 __glibcxx_requires_valid_range(__first, __last); 3150 3151 return std::__replace_copy_if(__first, __last, __result, 3152 __gnu_cxx::__ops::__iter_equals_val(__old_value), 3153 __new_value); 3154 } 3155 3156 /** 3157 * @brief Copy a sequence, replacing each value for which a predicate 3158 * returns true with another value. 3159 * @ingroup mutating_algorithms 3160 * @param __first An input iterator. 3161 * @param __last An input iterator. 3162 * @param __result An output iterator. 3163 * @param __pred A predicate. 3164 * @param __new_value The replacement value. 3165 * @return The end of the output sequence, @p __result+(__last-__first). 3166 * 3167 * Copies each element in the range @p [__first,__last) to the range 3168 * @p [__result,__result+(__last-__first)) replacing elements for which 3169 * @p __pred returns true with @p __new_value. 3170 */ 3171 template<typename _InputIterator, typename _OutputIterator, 3172 typename _Predicate, typename _Tp> 3173 _GLIBCXX20_CONSTEXPR 3174 inline _OutputIterator 3175 replace_copy_if(_InputIterator __first, _InputIterator __last, 3176 _OutputIterator __result, 3177 _Predicate __pred, const _Tp& __new_value) 3178 { 3179 // concept requirements 3180 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 3181 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 3182 typename iterator_traits<_InputIterator>::value_type>) 3183 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 3184 typename iterator_traits<_InputIterator>::value_type>) 3185 __glibcxx_requires_valid_range(__first, __last); 3186 3187 return std::__replace_copy_if(__first, __last, __result, 3188 __gnu_cxx::__ops::__pred_iter(__pred), 3189 __new_value); 3190 } 3191 3192 #if __cplusplus >= 201103L 3193 /** 3194 * @brief Determines whether the elements of a sequence are sorted. 3195 * @ingroup sorting_algorithms 3196 * @param __first An iterator. 3197 * @param __last Another iterator. 3198 * @return True if the elements are sorted, false otherwise. 3199 */ 3200 template<typename _ForwardIterator> 3201 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR 3202 inline bool 3203 is_sorted(_ForwardIterator __first, _ForwardIterator __last) 3204 { return std::is_sorted_until(__first, __last) == __last; } 3205 3206 /** 3207 * @brief Determines whether the elements of a sequence are sorted 3208 * according to a comparison functor. 3209 * @ingroup sorting_algorithms 3210 * @param __first An iterator. 3211 * @param __last Another iterator. 3212 * @param __comp A comparison functor. 3213 * @return True if the elements are sorted, false otherwise. 3214 */ 3215 template<typename _ForwardIterator, typename _Compare> 3216 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR 3217 inline bool 3218 is_sorted(_ForwardIterator __first, _ForwardIterator __last, 3219 _Compare __comp) 3220 { return std::is_sorted_until(__first, __last, __comp) == __last; } 3221 3222 template<typename _ForwardIterator, typename _Compare> 3223 _GLIBCXX20_CONSTEXPR 3224 _ForwardIterator 3225 __is_sorted_until(_ForwardIterator __first, _ForwardIterator __last, 3226 _Compare __comp) 3227 { 3228 if (__first == __last) 3229 return __last; 3230 3231 _ForwardIterator __next = __first; 3232 for (++__next; __next != __last; __first = __next, (void)++__next) 3233 if (__comp(__next, __first)) 3234 return __next; 3235 return __next; 3236 } 3237 3238 /** 3239 * @brief Determines the end of a sorted sequence. 3240 * @ingroup sorting_algorithms 3241 * @param __first An iterator. 3242 * @param __last Another iterator. 3243 * @return An iterator pointing to the last iterator i in [__first, __last) 3244 * for which the range [__first, i) is sorted. 3245 */ 3246 template<typename _ForwardIterator> 3247 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR 3248 inline _ForwardIterator 3249 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last) 3250 { 3251 // concept requirements 3252 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 3253 __glibcxx_function_requires(_LessThanComparableConcept< 3254 typename iterator_traits<_ForwardIterator>::value_type>) 3255 __glibcxx_requires_valid_range(__first, __last); 3256 __glibcxx_requires_irreflexive(__first, __last); 3257 3258 return std::__is_sorted_until(__first, __last, 3259 __gnu_cxx::__ops::__iter_less_iter()); 3260 } 3261 3262 /** 3263 * @brief Determines the end of a sorted sequence using comparison functor. 3264 * @ingroup sorting_algorithms 3265 * @param __first An iterator. 3266 * @param __last Another iterator. 3267 * @param __comp A comparison functor. 3268 * @return An iterator pointing to the last iterator i in [__first, __last) 3269 * for which the range [__first, i) is sorted. 3270 */ 3271 template<typename _ForwardIterator, typename _Compare> 3272 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR 3273 inline _ForwardIterator 3274 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last, 3275 _Compare __comp) 3276 { 3277 // concept requirements 3278 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 3279 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 3280 typename iterator_traits<_ForwardIterator>::value_type, 3281 typename iterator_traits<_ForwardIterator>::value_type>) 3282 __glibcxx_requires_valid_range(__first, __last); 3283 __glibcxx_requires_irreflexive_pred(__first, __last, __comp); 3284 3285 return std::__is_sorted_until(__first, __last, 3286 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 3287 } 3288 3289 /** 3290 * @brief Determines min and max at once as an ordered pair. 3291 * @ingroup sorting_algorithms 3292 * @param __a A thing of arbitrary type. 3293 * @param __b Another thing of arbitrary type. 3294 * @return A pair(__b, __a) if __b is smaller than __a, pair(__a, 3295 * __b) otherwise. 3296 */ 3297 template<typename _Tp> 3298 _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR 3299 inline pair<const _Tp&, const _Tp&> 3300 minmax(const _Tp& __a, const _Tp& __b) 3301 { 3302 // concept requirements 3303 __glibcxx_function_requires(_LessThanComparableConcept<_Tp>) 3304 3305 return __b < __a ? pair<const _Tp&, const _Tp&>(__b, __a) 3306 : pair<const _Tp&, const _Tp&>(__a, __b); 3307 } 3308 3309 /** 3310 * @brief Determines min and max at once as an ordered pair. 3311 * @ingroup sorting_algorithms 3312 * @param __a A thing of arbitrary type. 3313 * @param __b Another thing of arbitrary type. 3314 * @param __comp A @link comparison_functors comparison functor @endlink. 3315 * @return A pair(__b, __a) if __b is smaller than __a, pair(__a, 3316 * __b) otherwise. 3317 */ 3318 template<typename _Tp, typename _Compare> 3319 _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR 3320 inline pair<const _Tp&, const _Tp&> 3321 minmax(const _Tp& __a, const _Tp& __b, _Compare __comp) 3322 { 3323 return __comp(__b, __a) ? pair<const _Tp&, const _Tp&>(__b, __a) 3324 : pair<const _Tp&, const _Tp&>(__a, __b); 3325 } 3326 3327 template<typename _ForwardIterator, typename _Compare> 3328 _GLIBCXX14_CONSTEXPR 3329 pair<_ForwardIterator, _ForwardIterator> 3330 __minmax_element(_ForwardIterator __first, _ForwardIterator __last, 3331 _Compare __comp) 3332 { 3333 _ForwardIterator __next = __first; 3334 if (__first == __last 3335 || ++__next == __last) 3336 return std::make_pair(__first, __first); 3337 3338 _ForwardIterator __min{}, __max{}; 3339 if (__comp(__next, __first)) 3340 { 3341 __min = __next; 3342 __max = __first; 3343 } 3344 else 3345 { 3346 __min = __first; 3347 __max = __next; 3348 } 3349 3350 __first = __next; 3351 ++__first; 3352 3353 while (__first != __last) 3354 { 3355 __next = __first; 3356 if (++__next == __last) 3357 { 3358 if (__comp(__first, __min)) 3359 __min = __first; 3360 else if (!__comp(__first, __max)) 3361 __max = __first; 3362 break; 3363 } 3364 3365 if (__comp(__next, __first)) 3366 { 3367 if (__comp(__next, __min)) 3368 __min = __next; 3369 if (!__comp(__first, __max)) 3370 __max = __first; 3371 } 3372 else 3373 { 3374 if (__comp(__first, __min)) 3375 __min = __first; 3376 if (!__comp(__next, __max)) 3377 __max = __next; 3378 } 3379 3380 __first = __next; 3381 ++__first; 3382 } 3383 3384 return std::make_pair(__min, __max); 3385 } 3386 3387 /** 3388 * @brief Return a pair of iterators pointing to the minimum and maximum 3389 * elements in a range. 3390 * @ingroup sorting_algorithms 3391 * @param __first Start of range. 3392 * @param __last End of range. 3393 * @return make_pair(m, M), where m is the first iterator i in 3394 * [__first, __last) such that no other element in the range is 3395 * smaller, and where M is the last iterator i in [__first, __last) 3396 * such that no other element in the range is larger. 3397 */ 3398 template<typename _ForwardIterator> 3399 _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR 3400 inline pair<_ForwardIterator, _ForwardIterator> 3401 minmax_element(_ForwardIterator __first, _ForwardIterator __last) 3402 { 3403 // concept requirements 3404 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 3405 __glibcxx_function_requires(_LessThanComparableConcept< 3406 typename iterator_traits<_ForwardIterator>::value_type>) 3407 __glibcxx_requires_valid_range(__first, __last); 3408 __glibcxx_requires_irreflexive(__first, __last); 3409 3410 return std::__minmax_element(__first, __last, 3411 __gnu_cxx::__ops::__iter_less_iter()); 3412 } 3413 3414 /** 3415 * @brief Return a pair of iterators pointing to the minimum and maximum 3416 * elements in a range. 3417 * @ingroup sorting_algorithms 3418 * @param __first Start of range. 3419 * @param __last End of range. 3420 * @param __comp Comparison functor. 3421 * @return make_pair(m, M), where m is the first iterator i in 3422 * [__first, __last) such that no other element in the range is 3423 * smaller, and where M is the last iterator i in [__first, __last) 3424 * such that no other element in the range is larger. 3425 */ 3426 template<typename _ForwardIterator, typename _Compare> 3427 _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR 3428 inline pair<_ForwardIterator, _ForwardIterator> 3429 minmax_element(_ForwardIterator __first, _ForwardIterator __last, 3430 _Compare __comp) 3431 { 3432 // concept requirements 3433 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 3434 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 3435 typename iterator_traits<_ForwardIterator>::value_type, 3436 typename iterator_traits<_ForwardIterator>::value_type>) 3437 __glibcxx_requires_valid_range(__first, __last); 3438 __glibcxx_requires_irreflexive_pred(__first, __last, __comp); 3439 3440 return std::__minmax_element(__first, __last, 3441 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 3442 } 3443 3444 template<typename _Tp> 3445 _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR 3446 inline pair<_Tp, _Tp> 3447 minmax(initializer_list<_Tp> __l) 3448 { 3449 __glibcxx_requires_irreflexive(__l.begin(), __l.end()); 3450 pair<const _Tp*, const _Tp*> __p = 3451 std::__minmax_element(__l.begin(), __l.end(), 3452 __gnu_cxx::__ops::__iter_less_iter()); 3453 return std::make_pair(*__p.first, *__p.second); 3454 } 3455 3456 template<typename _Tp, typename _Compare> 3457 _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR 3458 inline pair<_Tp, _Tp> 3459 minmax(initializer_list<_Tp> __l, _Compare __comp) 3460 { 3461 __glibcxx_requires_irreflexive_pred(__l.begin(), __l.end(), __comp); 3462 pair<const _Tp*, const _Tp*> __p = 3463 std::__minmax_element(__l.begin(), __l.end(), 3464 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 3465 return std::make_pair(*__p.first, *__p.second); 3466 } 3467 3468 /** 3469 * @brief Checks whether a permutation of the second sequence is equal 3470 * to the first sequence. 3471 * @ingroup non_mutating_algorithms 3472 * @param __first1 Start of first range. 3473 * @param __last1 End of first range. 3474 * @param __first2 Start of second range. 3475 * @param __pred A binary predicate. 3476 * @return true if there exists a permutation of the elements in 3477 * the range [__first2, __first2 + (__last1 - __first1)), 3478 * beginning with ForwardIterator2 begin, such that 3479 * equal(__first1, __last1, __begin, __pred) returns true; 3480 * otherwise, returns false. 3481 */ 3482 template<typename _ForwardIterator1, typename _ForwardIterator2, 3483 typename _BinaryPredicate> 3484 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR 3485 inline bool 3486 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 3487 _ForwardIterator2 __first2, _BinaryPredicate __pred) 3488 { 3489 // concept requirements 3490 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>) 3491 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>) 3492 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 3493 typename iterator_traits<_ForwardIterator1>::value_type, 3494 typename iterator_traits<_ForwardIterator2>::value_type>) 3495 __glibcxx_requires_valid_range(__first1, __last1); 3496 3497 return std::__is_permutation(__first1, __last1, __first2, 3498 __gnu_cxx::__ops::__iter_comp_iter(__pred)); 3499 } 3500 3501 #if __cplusplus > 201103L 3502 #pragma GCC diagnostic push 3503 #pragma GCC diagnostic ignored "-Wc++17-extensions" // if constexpr 3504 template<typename _ForwardIterator1, typename _ForwardIterator2, 3505 typename _BinaryPredicate> 3506 _GLIBCXX20_CONSTEXPR 3507 bool 3508 __is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 3509 _ForwardIterator2 __first2, _ForwardIterator2 __last2, 3510 _BinaryPredicate __pred) 3511 { 3512 using _Cat1 3513 = typename iterator_traits<_ForwardIterator1>::iterator_category; 3514 using _Cat2 3515 = typename iterator_traits<_ForwardIterator2>::iterator_category; 3516 using _It1_is_RA = is_same<_Cat1, random_access_iterator_tag>; 3517 using _It2_is_RA = is_same<_Cat2, random_access_iterator_tag>; 3518 constexpr bool __ra_iters = __and_<_It1_is_RA, _It2_is_RA>::value; 3519 if constexpr (__ra_iters) 3520 { 3521 if ((__last1 - __first1) != (__last2 - __first2)) 3522 return false; 3523 } 3524 3525 // Efficiently compare identical prefixes: O(N) if sequences 3526 // have the same elements in the same order. 3527 for (; __first1 != __last1 && __first2 != __last2; 3528 ++__first1, (void)++__first2) 3529 if (!__pred(__first1, __first2)) 3530 break; 3531 3532 if constexpr (__ra_iters) 3533 { 3534 if (__first1 == __last1) 3535 return true; 3536 } 3537 else 3538 { 3539 auto __d1 = std::distance(__first1, __last1); 3540 auto __d2 = std::distance(__first2, __last2); 3541 if (__d1 == 0 && __d2 == 0) 3542 return true; 3543 if (__d1 != __d2) 3544 return false; 3545 } 3546 3547 for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan) 3548 { 3549 if (__scan != std::__find_if(__first1, __scan, 3550 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan))) 3551 continue; // We've seen this one before. 3552 3553 auto __matches = std::__count_if(__first2, __last2, 3554 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)); 3555 if (0 == __matches 3556 || std::__count_if(__scan, __last1, 3557 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)) 3558 != __matches) 3559 return false; 3560 } 3561 return true; 3562 } 3563 #pragma GCC diagnostic pop 3564 3565 /** 3566 * @brief Checks whether a permutaion of the second sequence is equal 3567 * to the first sequence. 3568 * @ingroup non_mutating_algorithms 3569 * @param __first1 Start of first range. 3570 * @param __last1 End of first range. 3571 * @param __first2 Start of second range. 3572 * @param __last2 End of first range. 3573 * @return true if there exists a permutation of the elements in the range 3574 * [__first2, __last2), beginning with ForwardIterator2 begin, 3575 * such that equal(__first1, __last1, begin) returns true; 3576 * otherwise, returns false. 3577 */ 3578 template<typename _ForwardIterator1, typename _ForwardIterator2> 3579 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR 3580 inline bool 3581 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 3582 _ForwardIterator2 __first2, _ForwardIterator2 __last2) 3583 { 3584 __glibcxx_requires_valid_range(__first1, __last1); 3585 __glibcxx_requires_valid_range(__first2, __last2); 3586 3587 return 3588 std::__is_permutation(__first1, __last1, __first2, __last2, 3589 __gnu_cxx::__ops::__iter_equal_to_iter()); 3590 } 3591 3592 /** 3593 * @brief Checks whether a permutation of the second sequence is equal 3594 * to the first sequence. 3595 * @ingroup non_mutating_algorithms 3596 * @param __first1 Start of first range. 3597 * @param __last1 End of first range. 3598 * @param __first2 Start of second range. 3599 * @param __last2 End of first range. 3600 * @param __pred A binary predicate. 3601 * @return true if there exists a permutation of the elements in the range 3602 * [__first2, __last2), beginning with ForwardIterator2 begin, 3603 * such that equal(__first1, __last1, __begin, __pred) returns true; 3604 * otherwise, returns false. 3605 */ 3606 template<typename _ForwardIterator1, typename _ForwardIterator2, 3607 typename _BinaryPredicate> 3608 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR 3609 inline bool 3610 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 3611 _ForwardIterator2 __first2, _ForwardIterator2 __last2, 3612 _BinaryPredicate __pred) 3613 { 3614 __glibcxx_requires_valid_range(__first1, __last1); 3615 __glibcxx_requires_valid_range(__first2, __last2); 3616 3617 return std::__is_permutation(__first1, __last1, __first2, __last2, 3618 __gnu_cxx::__ops::__iter_comp_iter(__pred)); 3619 } 3620 #endif // C++14 3621 3622 #ifdef __glibcxx_clamp // C++ >= 17 3623 /** 3624 * @brief Returns the value clamped between lo and hi. 3625 * @ingroup sorting_algorithms 3626 * @param __val A value of arbitrary type. 3627 * @param __lo A lower limit of arbitrary type. 3628 * @param __hi An upper limit of arbitrary type. 3629 * @retval `__lo` if `__val < __lo` 3630 * @retval `__hi` if `__hi < __val` 3631 * @retval `__val` otherwise. 3632 * @pre `_Tp` is LessThanComparable and `(__hi < __lo)` is false. 3633 */ 3634 template<typename _Tp> 3635 [[nodiscard]] constexpr const _Tp& 3636 clamp(const _Tp& __val, const _Tp& __lo, const _Tp& __hi) 3637 { 3638 __glibcxx_assert(!(__hi < __lo)); 3639 return std::min(std::max(__val, __lo), __hi); 3640 } 3641 3642 /** 3643 * @brief Returns the value clamped between lo and hi. 3644 * @ingroup sorting_algorithms 3645 * @param __val A value of arbitrary type. 3646 * @param __lo A lower limit of arbitrary type. 3647 * @param __hi An upper limit of arbitrary type. 3648 * @param __comp A comparison functor. 3649 * @retval `__lo` if `__comp(__val, __lo)` 3650 * @retval `__hi` if `__comp(__hi, __val)` 3651 * @retval `__val` otherwise. 3652 * @pre `__comp(__hi, __lo)` is false. 3653 */ 3654 template<typename _Tp, typename _Compare> 3655 [[nodiscard]] constexpr const _Tp& 3656 clamp(const _Tp& __val, const _Tp& __lo, const _Tp& __hi, _Compare __comp) 3657 { 3658 __glibcxx_assert(!__comp(__hi, __lo)); 3659 return std::min(std::max(__val, __lo, __comp), __hi, __comp); 3660 } 3661 #endif // __glibcxx_clamp 3662 3663 /** 3664 * @brief Generate two uniformly distributed integers using a 3665 * single distribution invocation. 3666 * @param __b0 The upper bound for the first integer. 3667 * @param __b1 The upper bound for the second integer. 3668 * @param __g A UniformRandomBitGenerator. 3669 * @return A pair (i, j) with i and j uniformly distributed 3670 * over [0, __b0) and [0, __b1), respectively. 3671 * 3672 * Requires: __b0 * __b1 <= __g.max() - __g.min(). 3673 * 3674 * Using uniform_int_distribution with a range that is very 3675 * small relative to the range of the generator ends up wasting 3676 * potentially expensively generated randomness, since 3677 * uniform_int_distribution does not store leftover randomness 3678 * between invocations. 3679 * 3680 * If we know we want two integers in ranges that are sufficiently 3681 * small, we can compose the ranges, use a single distribution 3682 * invocation, and significantly reduce the waste. 3683 */ 3684 template<typename _IntType, typename _UniformRandomBitGenerator> 3685 pair<_IntType, _IntType> 3686 __gen_two_uniform_ints(_IntType __b0, _IntType __b1, 3687 _UniformRandomBitGenerator&& __g) 3688 { 3689 _IntType __x 3690 = uniform_int_distribution<_IntType>{0, (__b0 * __b1) - 1}(__g); 3691 return std::make_pair(__x / __b1, __x % __b1); 3692 } 3693 3694 /** 3695 * @brief Shuffle the elements of a sequence using a uniform random 3696 * number generator. 3697 * @ingroup mutating_algorithms 3698 * @param __first A forward iterator. 3699 * @param __last A forward iterator. 3700 * @param __g A UniformRandomNumberGenerator (26.5.1.3). 3701 * @return Nothing. 3702 * 3703 * Reorders the elements in the range @p [__first,__last) using @p __g to 3704 * provide random numbers. 3705 */ 3706 template<typename _RandomAccessIterator, 3707 typename _UniformRandomNumberGenerator> 3708 void 3709 shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last, 3710 _UniformRandomNumberGenerator&& __g) 3711 { 3712 // concept requirements 3713 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 3714 _RandomAccessIterator>) 3715 __glibcxx_requires_valid_range(__first, __last); 3716 3717 if (__first == __last) 3718 return; 3719 3720 typedef typename iterator_traits<_RandomAccessIterator>::difference_type 3721 _DistanceType; 3722 3723 typedef typename std::make_unsigned<_DistanceType>::type __ud_type; 3724 typedef typename std::uniform_int_distribution<__ud_type> __distr_type; 3725 typedef typename __distr_type::param_type __p_type; 3726 3727 typedef typename remove_reference<_UniformRandomNumberGenerator>::type 3728 _Gen; 3729 typedef typename common_type<typename _Gen::result_type, __ud_type>::type 3730 __uc_type; 3731 3732 const __uc_type __urngrange = __g.max() - __g.min(); 3733 const __uc_type __urange = __uc_type(__last - __first); 3734 3735 if (__urngrange / __urange >= __urange) 3736 // I.e. (__urngrange >= __urange * __urange) but without wrap issues. 3737 { 3738 _RandomAccessIterator __i = __first + 1; 3739 3740 // Since we know the range isn't empty, an even number of elements 3741 // means an uneven number of elements /to swap/, in which case we 3742 // do the first one up front: 3743 3744 if ((__urange % 2) == 0) 3745 { 3746 __distr_type __d{0, 1}; 3747 std::iter_swap(__i++, __first + __d(__g)); 3748 } 3749 3750 // Now we know that __last - __i is even, so we do the rest in pairs, 3751 // using a single distribution invocation to produce swap positions 3752 // for two successive elements at a time: 3753 3754 while (__i != __last) 3755 { 3756 const __uc_type __swap_range = __uc_type(__i - __first) + 1; 3757 3758 const pair<__uc_type, __uc_type> __pospos = 3759 __gen_two_uniform_ints(__swap_range, __swap_range + 1, __g); 3760 3761 std::iter_swap(__i++, __first + __pospos.first); 3762 std::iter_swap(__i++, __first + __pospos.second); 3763 } 3764 3765 return; 3766 } 3767 3768 __distr_type __d; 3769 3770 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i) 3771 std::iter_swap(__i, __first + __d(__g, __p_type(0, __i - __first))); 3772 } 3773 #endif // C++11 3774 3775 _GLIBCXX_BEGIN_NAMESPACE_ALGO 3776 3777 /** 3778 * @brief Apply a function to every element of a sequence. 3779 * @ingroup non_mutating_algorithms 3780 * @param __first An input iterator. 3781 * @param __last An input iterator. 3782 * @param __f A unary function object. 3783 * @return @p __f 3784 * 3785 * Applies the function object @p __f to each element in the range 3786 * @p [first,last). @p __f must not modify the order of the sequence. 3787 * If @p __f has a return value it is ignored. 3788 */ 3789 template<typename _InputIterator, typename _Function> 3790 _GLIBCXX20_CONSTEXPR 3791 _Function 3792 for_each(_InputIterator __first, _InputIterator __last, _Function __f) 3793 { 3794 // concept requirements 3795 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 3796 __glibcxx_requires_valid_range(__first, __last); 3797 for (; __first != __last; ++__first) 3798 __f(*__first); 3799 return __f; // N.B. [alg.foreach] says std::move(f) but it's redundant. 3800 } 3801 3802 #if __cplusplus >= 201703L 3803 /** 3804 * @brief Apply a function to every element of a sequence. 3805 * @ingroup non_mutating_algorithms 3806 * @param __first An input iterator. 3807 * @param __n A value convertible to an integer. 3808 * @param __f A unary function object. 3809 * @return `__first+__n` 3810 * 3811 * Applies the function object `__f` to each element in the range 3812 * `[first, first+n)`. `__f` must not modify the order of the sequence. 3813 * If `__f` has a return value it is ignored. 3814 */ 3815 template<typename _InputIterator, typename _Size, typename _Function> 3816 _GLIBCXX20_CONSTEXPR 3817 _InputIterator 3818 for_each_n(_InputIterator __first, _Size __n, _Function __f) 3819 { 3820 auto __n2 = std::__size_to_integer(__n); 3821 using _Cat = typename iterator_traits<_InputIterator>::iterator_category; 3822 if constexpr (is_base_of_v<random_access_iterator_tag, _Cat>) 3823 { 3824 if (__n2 <= 0) 3825 return __first; 3826 auto __last = __first + __n2; 3827 std::for_each(__first, __last, std::move(__f)); 3828 return __last; 3829 } 3830 else 3831 { 3832 while (__n2-->0) 3833 { 3834 __f(*__first); 3835 ++__first; 3836 } 3837 return __first; 3838 } 3839 } 3840 #endif // C++17 3841 3842 /** 3843 * @brief Find the first occurrence of a value in a sequence. 3844 * @ingroup non_mutating_algorithms 3845 * @param __first An input iterator. 3846 * @param __last An input iterator. 3847 * @param __val The value to find. 3848 * @return The first iterator @c i in the range @p [__first,__last) 3849 * such that @c *i == @p __val, or @p __last if no such iterator exists. 3850 */ 3851 template<typename _InputIterator, typename _Tp> 3852 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR 3853 inline _InputIterator 3854 find(_InputIterator __first, _InputIterator __last, const _Tp& __val) 3855 { 3856 // concept requirements 3857 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 3858 __glibcxx_function_requires(_EqualOpConcept< 3859 typename iterator_traits<_InputIterator>::value_type, _Tp>) 3860 __glibcxx_requires_valid_range(__first, __last); 3861 3862 #if __cpp_if_constexpr && __glibcxx_type_trait_variable_templates 3863 using _ValT = typename iterator_traits<_InputIterator>::value_type; 3864 if constexpr (__can_use_memchr_for_find<_ValT, _Tp>) 3865 if constexpr (is_pointer_v<decltype(std::__niter_base(__first))> 3866 #if __glibcxx_concepts && __glibcxx_to_address 3867 || contiguous_iterator<_InputIterator> 3868 #endif 3869 ) 3870 { 3871 // If conversion to the 1-byte value_type alters the value, 3872 // it would not be found by std::find using equality comparison. 3873 // We need to check this here, because otherwise something like 3874 // memchr("a", 'a'+256, 1) would give a false positive match. 3875 if (!(static_cast<_ValT>(__val) == __val)) 3876 return __last; 3877 else if (!__is_constant_evaluated()) 3878 { 3879 const int __ival = static_cast<int>(__val); 3880 if (auto __n = __last - __first; __n > 0) 3881 { 3882 #if __glibcxx_concepts && __glibcxx_to_address 3883 const void* __p0 = std::to_address(__first); 3884 #else 3885 const void* __p0 = std::__niter_base(__first); 3886 #endif 3887 if (auto __p1 = __builtin_memchr(__p0, __ival, __n)) 3888 return __first + ((const char*)__p1 - (const char*)__p0); 3889 } 3890 return __last; 3891 } 3892 } 3893 #endif 3894 3895 return std::__find_if(__first, __last, 3896 __gnu_cxx::__ops::__iter_equals_val(__val)); 3897 } 3898 3899 /** 3900 * @brief Find the first element in a sequence for which a 3901 * predicate is true. 3902 * @ingroup non_mutating_algorithms 3903 * @param __first An input iterator. 3904 * @param __last An input iterator. 3905 * @param __pred A predicate. 3906 * @return The first iterator @c i in the range @p [__first,__last) 3907 * such that @p __pred(*i) is true, or @p __last if no such iterator exists. 3908 */ 3909 template<typename _InputIterator, typename _Predicate> 3910 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR 3911 inline _InputIterator 3912 find_if(_InputIterator __first, _InputIterator __last, 3913 _Predicate __pred) 3914 { 3915 // concept requirements 3916 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 3917 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 3918 typename iterator_traits<_InputIterator>::value_type>) 3919 __glibcxx_requires_valid_range(__first, __last); 3920 3921 return std::__find_if(__first, __last, 3922 __gnu_cxx::__ops::__pred_iter(__pred)); 3923 } 3924 3925 /** 3926 * @brief Find element from a set in a sequence. 3927 * @ingroup non_mutating_algorithms 3928 * @param __first1 Start of range to search. 3929 * @param __last1 End of range to search. 3930 * @param __first2 Start of match candidates. 3931 * @param __last2 End of match candidates. 3932 * @return The first iterator @c i in the range 3933 * @p [__first1,__last1) such that @c *i == @p *(i2) such that i2 is an 3934 * iterator in [__first2,__last2), or @p __last1 if no such iterator exists. 3935 * 3936 * Searches the range @p [__first1,__last1) for an element that is 3937 * equal to some element in the range [__first2,__last2). If 3938 * found, returns an iterator in the range [__first1,__last1), 3939 * otherwise returns @p __last1. 3940 */ 3941 template<typename _InputIterator, typename _ForwardIterator> 3942 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR 3943 _InputIterator 3944 find_first_of(_InputIterator __first1, _InputIterator __last1, 3945 _ForwardIterator __first2, _ForwardIterator __last2) 3946 { 3947 // concept requirements 3948 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 3949 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 3950 __glibcxx_function_requires(_EqualOpConcept< 3951 typename iterator_traits<_InputIterator>::value_type, 3952 typename iterator_traits<_ForwardIterator>::value_type>) 3953 __glibcxx_requires_valid_range(__first1, __last1); 3954 __glibcxx_requires_valid_range(__first2, __last2); 3955 3956 for (; __first1 != __last1; ++__first1) 3957 for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter) 3958 if (*__first1 == *__iter) 3959 return __first1; 3960 return __last1; 3961 } 3962 3963 /** 3964 * @brief Find element from a set in a sequence using a predicate. 3965 * @ingroup non_mutating_algorithms 3966 * @param __first1 Start of range to search. 3967 * @param __last1 End of range to search. 3968 * @param __first2 Start of match candidates. 3969 * @param __last2 End of match candidates. 3970 * @param __comp Predicate to use. 3971 * @return The first iterator @c i in the range 3972 * @p [__first1,__last1) such that @c comp(*i, @p *(i2)) is true 3973 * and i2 is an iterator in [__first2,__last2), or @p __last1 if no 3974 * such iterator exists. 3975 * 3976 3977 * Searches the range @p [__first1,__last1) for an element that is 3978 * equal to some element in the range [__first2,__last2). If 3979 * found, returns an iterator in the range [__first1,__last1), 3980 * otherwise returns @p __last1. 3981 */ 3982 template<typename _InputIterator, typename _ForwardIterator, 3983 typename _BinaryPredicate> 3984 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR 3985 _InputIterator 3986 find_first_of(_InputIterator __first1, _InputIterator __last1, 3987 _ForwardIterator __first2, _ForwardIterator __last2, 3988 _BinaryPredicate __comp) 3989 { 3990 // concept requirements 3991 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 3992 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 3993 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 3994 typename iterator_traits<_InputIterator>::value_type, 3995 typename iterator_traits<_ForwardIterator>::value_type>) 3996 __glibcxx_requires_valid_range(__first1, __last1); 3997 __glibcxx_requires_valid_range(__first2, __last2); 3998 3999 for (; __first1 != __last1; ++__first1) 4000 for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter) 4001 if (__comp(*__first1, *__iter)) 4002 return __first1; 4003 return __last1; 4004 } 4005 4006 /** 4007 * @brief Find two adjacent values in a sequence that are equal. 4008 * @ingroup non_mutating_algorithms 4009 * @param __first A forward iterator. 4010 * @param __last A forward iterator. 4011 * @return The first iterator @c i such that @c i and @c i+1 are both 4012 * valid iterators in @p [__first,__last) and such that @c *i == @c *(i+1), 4013 * or @p __last if no such iterator exists. 4014 */ 4015 template<typename _ForwardIterator> 4016 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR 4017 inline _ForwardIterator 4018 adjacent_find(_ForwardIterator __first, _ForwardIterator __last) 4019 { 4020 // concept requirements 4021 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 4022 __glibcxx_function_requires(_EqualityComparableConcept< 4023 typename iterator_traits<_ForwardIterator>::value_type>) 4024 __glibcxx_requires_valid_range(__first, __last); 4025 4026 return std::__adjacent_find(__first, __last, 4027 __gnu_cxx::__ops::__iter_equal_to_iter()); 4028 } 4029 4030 /** 4031 * @brief Find two adjacent values in a sequence using a predicate. 4032 * @ingroup non_mutating_algorithms 4033 * @param __first A forward iterator. 4034 * @param __last A forward iterator. 4035 * @param __binary_pred A binary predicate. 4036 * @return The first iterator @c i such that @c i and @c i+1 are both 4037 * valid iterators in @p [__first,__last) and such that 4038 * @p __binary_pred(*i,*(i+1)) is true, or @p __last if no such iterator 4039 * exists. 4040 */ 4041 template<typename _ForwardIterator, typename _BinaryPredicate> 4042 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR 4043 inline _ForwardIterator 4044 adjacent_find(_ForwardIterator __first, _ForwardIterator __last, 4045 _BinaryPredicate __binary_pred) 4046 { 4047 // concept requirements 4048 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 4049 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 4050 typename iterator_traits<_ForwardIterator>::value_type, 4051 typename iterator_traits<_ForwardIterator>::value_type>) 4052 __glibcxx_requires_valid_range(__first, __last); 4053 4054 return std::__adjacent_find(__first, __last, 4055 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred)); 4056 } 4057 4058 /** 4059 * @brief Count the number of copies of a value in a sequence. 4060 * @ingroup non_mutating_algorithms 4061 * @param __first An input iterator. 4062 * @param __last An input iterator. 4063 * @param __value The value to be counted. 4064 * @return The number of iterators @c i in the range @p [__first,__last) 4065 * for which @c *i == @p __value 4066 */ 4067 template<typename _InputIterator, typename _Tp> 4068 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR 4069 inline typename iterator_traits<_InputIterator>::difference_type 4070 count(_InputIterator __first, _InputIterator __last, const _Tp& __value) 4071 { 4072 // concept requirements 4073 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 4074 __glibcxx_function_requires(_EqualOpConcept< 4075 typename iterator_traits<_InputIterator>::value_type, _Tp>) 4076 __glibcxx_requires_valid_range(__first, __last); 4077 4078 return std::__count_if(__first, __last, 4079 __gnu_cxx::__ops::__iter_equals_val(__value)); 4080 } 4081 4082 /** 4083 * @brief Count the elements of a sequence for which a predicate is true. 4084 * @ingroup non_mutating_algorithms 4085 * @param __first An input iterator. 4086 * @param __last An input iterator. 4087 * @param __pred A predicate. 4088 * @return The number of iterators @c i in the range @p [__first,__last) 4089 * for which @p __pred(*i) is true. 4090 */ 4091 template<typename _InputIterator, typename _Predicate> 4092 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR 4093 inline typename iterator_traits<_InputIterator>::difference_type 4094 count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred) 4095 { 4096 // concept requirements 4097 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 4098 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 4099 typename iterator_traits<_InputIterator>::value_type>) 4100 __glibcxx_requires_valid_range(__first, __last); 4101 4102 return std::__count_if(__first, __last, 4103 __gnu_cxx::__ops::__pred_iter(__pred)); 4104 } 4105 4106 /** 4107 * @brief Search a sequence for a matching sub-sequence. 4108 * @ingroup non_mutating_algorithms 4109 * @param __first1 A forward iterator. 4110 * @param __last1 A forward iterator. 4111 * @param __first2 A forward iterator. 4112 * @param __last2 A forward iterator. 4113 * @return The first iterator @c i in the range @p 4114 * [__first1,__last1-(__last2-__first2)) such that @c *(i+N) == @p 4115 * *(__first2+N) for each @c N in the range @p 4116 * [0,__last2-__first2), or @p __last1 if no such iterator exists. 4117 * 4118 * Searches the range @p [__first1,__last1) for a sub-sequence that 4119 * compares equal value-by-value with the sequence given by @p 4120 * [__first2,__last2) and returns an iterator to the first element 4121 * of the sub-sequence, or @p __last1 if the sub-sequence is not 4122 * found. 4123 * 4124 * Because the sub-sequence must lie completely within the range @p 4125 * [__first1,__last1) it must start at a position less than @p 4126 * __last1-(__last2-__first2) where @p __last2-__first2 is the 4127 * length of the sub-sequence. 4128 * 4129 * This means that the returned iterator @c i will be in the range 4130 * @p [__first1,__last1-(__last2-__first2)) 4131 */ 4132 template<typename _ForwardIterator1, typename _ForwardIterator2> 4133 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR 4134 inline _ForwardIterator1 4135 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 4136 _ForwardIterator2 __first2, _ForwardIterator2 __last2) 4137 { 4138 // concept requirements 4139 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>) 4140 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>) 4141 __glibcxx_function_requires(_EqualOpConcept< 4142 typename iterator_traits<_ForwardIterator1>::value_type, 4143 typename iterator_traits<_ForwardIterator2>::value_type>) 4144 __glibcxx_requires_valid_range(__first1, __last1); 4145 __glibcxx_requires_valid_range(__first2, __last2); 4146 4147 return std::__search(__first1, __last1, __first2, __last2, 4148 __gnu_cxx::__ops::__iter_equal_to_iter()); 4149 } 4150 4151 /** 4152 * @brief Search a sequence for a number of consecutive values. 4153 * @ingroup non_mutating_algorithms 4154 * @param __first A forward iterator. 4155 * @param __last A forward iterator. 4156 * @param __count The number of consecutive values. 4157 * @param __val The value to find. 4158 * @return The first iterator @c i in the range @p 4159 * [__first,__last-__count) such that @c *(i+N) == @p __val for 4160 * each @c N in the range @p [0,__count), or @p __last if no such 4161 * iterator exists. 4162 * 4163 * Searches the range @p [__first,__last) for @p count consecutive elements 4164 * equal to @p __val. 4165 */ 4166 template<typename _ForwardIterator, typename _Integer, typename _Tp> 4167 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR 4168 inline _ForwardIterator 4169 search_n(_ForwardIterator __first, _ForwardIterator __last, 4170 _Integer __count, const _Tp& __val) 4171 { 4172 // concept requirements 4173 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 4174 __glibcxx_function_requires(_EqualOpConcept< 4175 typename iterator_traits<_ForwardIterator>::value_type, _Tp>) 4176 __glibcxx_requires_valid_range(__first, __last); 4177 4178 return std::__search_n(__first, __last, __count, 4179 __gnu_cxx::__ops::__iter_equals_val(__val)); 4180 } 4181 4182 4183 /** 4184 * @brief Search a sequence for a number of consecutive values using a 4185 * predicate. 4186 * @ingroup non_mutating_algorithms 4187 * @param __first A forward iterator. 4188 * @param __last A forward iterator. 4189 * @param __count The number of consecutive values. 4190 * @param __val The value to find. 4191 * @param __binary_pred A binary predicate. 4192 * @return The first iterator @c i in the range @p 4193 * [__first,__last-__count) such that @p 4194 * __binary_pred(*(i+N),__val) is true for each @c N in the range 4195 * @p [0,__count), or @p __last if no such iterator exists. 4196 * 4197 * Searches the range @p [__first,__last) for @p __count 4198 * consecutive elements for which the predicate returns true. 4199 */ 4200 template<typename _ForwardIterator, typename _Integer, typename _Tp, 4201 typename _BinaryPredicate> 4202 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR 4203 inline _ForwardIterator 4204 search_n(_ForwardIterator __first, _ForwardIterator __last, 4205 _Integer __count, const _Tp& __val, 4206 _BinaryPredicate __binary_pred) 4207 { 4208 // concept requirements 4209 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 4210 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 4211 typename iterator_traits<_ForwardIterator>::value_type, _Tp>) 4212 __glibcxx_requires_valid_range(__first, __last); 4213 4214 return std::__search_n(__first, __last, __count, 4215 __gnu_cxx::__ops::__iter_comp_val(__binary_pred, __val)); 4216 } 4217 4218 #if __cplusplus >= 201703L 4219 /** @brief Search a sequence using a Searcher object. 4220 * 4221 * @param __first A forward iterator. 4222 * @param __last A forward iterator. 4223 * @param __searcher A callable object. 4224 * @return @p __searcher(__first,__last).first 4225 */ 4226 template<typename _ForwardIterator, typename _Searcher> 4227 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR 4228 inline _ForwardIterator 4229 search(_ForwardIterator __first, _ForwardIterator __last, 4230 const _Searcher& __searcher) 4231 { return __searcher(__first, __last).first; } 4232 #endif 4233 4234 /** 4235 * @brief Perform an operation on a sequence. 4236 * @ingroup mutating_algorithms 4237 * @param __first An input iterator. 4238 * @param __last An input iterator. 4239 * @param __result An output iterator. 4240 * @param __unary_op A unary operator. 4241 * @return An output iterator equal to @p __result+(__last-__first). 4242 * 4243 * Applies the operator to each element in the input range and assigns 4244 * the results to successive elements of the output sequence. 4245 * Evaluates @p *(__result+N)=unary_op(*(__first+N)) for each @c N in the 4246 * range @p [0,__last-__first). 4247 * 4248 * @p unary_op must not alter its argument. 4249 */ 4250 template<typename _InputIterator, typename _OutputIterator, 4251 typename _UnaryOperation> 4252 _GLIBCXX20_CONSTEXPR 4253 _OutputIterator 4254 transform(_InputIterator __first, _InputIterator __last, 4255 _OutputIterator __result, _UnaryOperation __unary_op) 4256 { 4257 // concept requirements 4258 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 4259 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 4260 // "the type returned by a _UnaryOperation" 4261 __typeof__(__unary_op(*__first))>) 4262 __glibcxx_requires_valid_range(__first, __last); 4263 4264 for (; __first != __last; ++__first, (void)++__result) 4265 *__result = __unary_op(*__first); 4266 return __result; 4267 } 4268 4269 /** 4270 * @brief Perform an operation on corresponding elements of two sequences. 4271 * @ingroup mutating_algorithms 4272 * @param __first1 An input iterator. 4273 * @param __last1 An input iterator. 4274 * @param __first2 An input iterator. 4275 * @param __result An output iterator. 4276 * @param __binary_op A binary operator. 4277 * @return An output iterator equal to @p result+(last-first). 4278 * 4279 * Applies the operator to the corresponding elements in the two 4280 * input ranges and assigns the results to successive elements of the 4281 * output sequence. 4282 * Evaluates @p 4283 * *(__result+N)=__binary_op(*(__first1+N),*(__first2+N)) for each 4284 * @c N in the range @p [0,__last1-__first1). 4285 * 4286 * @p binary_op must not alter either of its arguments. 4287 */ 4288 template<typename _InputIterator1, typename _InputIterator2, 4289 typename _OutputIterator, typename _BinaryOperation> 4290 _GLIBCXX20_CONSTEXPR 4291 _OutputIterator 4292 transform(_InputIterator1 __first1, _InputIterator1 __last1, 4293 _InputIterator2 __first2, _OutputIterator __result, 4294 _BinaryOperation __binary_op) 4295 { 4296 // concept requirements 4297 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 4298 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 4299 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 4300 // "the type returned by a _BinaryOperation" 4301 __typeof__(__binary_op(*__first1,*__first2))>) 4302 __glibcxx_requires_valid_range(__first1, __last1); 4303 4304 for (; __first1 != __last1; ++__first1, (void)++__first2, ++__result) 4305 *__result = __binary_op(*__first1, *__first2); 4306 return __result; 4307 } 4308 4309 /** 4310 * @brief Replace each occurrence of one value in a sequence with another 4311 * value. 4312 * @ingroup mutating_algorithms 4313 * @param __first A forward iterator. 4314 * @param __last A forward iterator. 4315 * @param __old_value The value to be replaced. 4316 * @param __new_value The replacement value. 4317 * @return replace() returns no value. 4318 * 4319 * For each iterator `i` in the range `[__first,__last)` if 4320 * `*i == __old_value` then the assignment `*i = __new_value` is performed. 4321 */ 4322 template<typename _ForwardIterator, typename _Tp> 4323 _GLIBCXX20_CONSTEXPR 4324 void 4325 replace(_ForwardIterator __first, _ForwardIterator __last, 4326 const _Tp& __old_value, const _Tp& __new_value) 4327 { 4328 // concept requirements 4329 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 4330 _ForwardIterator>) 4331 __glibcxx_function_requires(_EqualOpConcept< 4332 typename iterator_traits<_ForwardIterator>::value_type, _Tp>) 4333 __glibcxx_function_requires(_ConvertibleConcept<_Tp, 4334 typename iterator_traits<_ForwardIterator>::value_type>) 4335 __glibcxx_requires_valid_range(__first, __last); 4336 4337 for (; __first != __last; ++__first) 4338 if (*__first == __old_value) 4339 *__first = __new_value; 4340 } 4341 4342 /** 4343 * @brief Replace each value in a sequence for which a predicate returns 4344 * true with another value. 4345 * @ingroup mutating_algorithms 4346 * @param __first A forward iterator. 4347 * @param __last A forward iterator. 4348 * @param __pred A predicate. 4349 * @param __new_value The replacement value. 4350 * @return replace_if() returns no value. 4351 * 4352 * For each iterator `i` in the range `[__first,__last)` if `__pred(*i)` 4353 * is true then the assignment `*i = __new_value` is performed. 4354 */ 4355 template<typename _ForwardIterator, typename _Predicate, typename _Tp> 4356 _GLIBCXX20_CONSTEXPR 4357 void 4358 replace_if(_ForwardIterator __first, _ForwardIterator __last, 4359 _Predicate __pred, const _Tp& __new_value) 4360 { 4361 // concept requirements 4362 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 4363 _ForwardIterator>) 4364 __glibcxx_function_requires(_ConvertibleConcept<_Tp, 4365 typename iterator_traits<_ForwardIterator>::value_type>) 4366 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 4367 typename iterator_traits<_ForwardIterator>::value_type>) 4368 __glibcxx_requires_valid_range(__first, __last); 4369 4370 for (; __first != __last; ++__first) 4371 if (__pred(*__first)) 4372 *__first = __new_value; 4373 } 4374 4375 /** 4376 * @brief Assign the result of a function object to each value in a 4377 * sequence. 4378 * @ingroup mutating_algorithms 4379 * @param __first A forward iterator. 4380 * @param __last A forward iterator. 4381 * @param __gen A function object callable with no arguments. 4382 * @return generate() returns no value. 4383 * 4384 * Performs the assignment `*i = __gen()` for each `i` in the range 4385 * `[__first, __last)`. 4386 */ 4387 template<typename _ForwardIterator, typename _Generator> 4388 _GLIBCXX20_CONSTEXPR 4389 void 4390 generate(_ForwardIterator __first, _ForwardIterator __last, 4391 _Generator __gen) 4392 { 4393 // concept requirements 4394 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 4395 __glibcxx_function_requires(_GeneratorConcept<_Generator, 4396 typename iterator_traits<_ForwardIterator>::value_type>) 4397 __glibcxx_requires_valid_range(__first, __last); 4398 4399 for (; __first != __last; ++__first) 4400 *__first = __gen(); 4401 } 4402 4403 /** 4404 * @brief Assign the result of a function object to each value in a 4405 * sequence. 4406 * @ingroup mutating_algorithms 4407 * @param __first A forward iterator. 4408 * @param __n The length of the sequence. 4409 * @param __gen A function object callable with no arguments. 4410 * @return The end of the sequence, i.e., `__first + __n` 4411 * 4412 * Performs the assignment `*i = __gen()` for each `i` in the range 4413 * `[__first, __first + __n)`. 4414 * 4415 * If `__n` is negative, the function does nothing and returns `__first`. 4416 */ 4417 // _GLIBCXX_RESOLVE_LIB_DEFECTS 4418 // DR 865. More algorithms that throw away information 4419 // DR 426. search_n(), fill_n(), and generate_n() with negative n 4420 template<typename _OutputIterator, typename _Size, typename _Generator> 4421 _GLIBCXX20_CONSTEXPR 4422 _OutputIterator 4423 generate_n(_OutputIterator __first, _Size __n, _Generator __gen) 4424 { 4425 // concept requirements 4426 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 4427 // "the type returned by a _Generator" 4428 __typeof__(__gen())>) 4429 4430 typedef __decltype(std::__size_to_integer(__n)) _IntSize; 4431 for (_IntSize __niter = std::__size_to_integer(__n); 4432 __niter > 0; --__niter, (void) ++__first) 4433 *__first = __gen(); 4434 return __first; 4435 } 4436 4437 /** 4438 * @brief Copy a sequence, removing consecutive duplicate values. 4439 * @ingroup mutating_algorithms 4440 * @param __first An input iterator. 4441 * @param __last An input iterator. 4442 * @param __result An output iterator. 4443 * @return An iterator designating the end of the resulting sequence. 4444 * 4445 * Copies each element in the range `[__first, __last)` to the range 4446 * beginning at `__result`, except that only the first element is copied 4447 * from groups of consecutive elements that compare equal. 4448 * `unique_copy()` is stable, so the relative order of elements that are 4449 * copied is unchanged. 4450 */ 4451 // _GLIBCXX_RESOLVE_LIB_DEFECTS 4452 // DR 241. Does unique_copy() require CopyConstructible and Assignable? 4453 // DR 538. 241 again: Does unique_copy() require CopyConstructible and 4454 // Assignable? 4455 template<typename _InputIterator, typename _OutputIterator> 4456 _GLIBCXX20_CONSTEXPR 4457 inline _OutputIterator 4458 unique_copy(_InputIterator __first, _InputIterator __last, 4459 _OutputIterator __result) 4460 { 4461 // concept requirements 4462 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 4463 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 4464 typename iterator_traits<_InputIterator>::value_type>) 4465 __glibcxx_function_requires(_EqualityComparableConcept< 4466 typename iterator_traits<_InputIterator>::value_type>) 4467 __glibcxx_requires_valid_range(__first, __last); 4468 4469 if (__first == __last) 4470 return __result; 4471 return std::__unique_copy(__first, __last, __result, 4472 __gnu_cxx::__ops::__iter_equal_to_iter(), 4473 std::__iterator_category(__first), 4474 std::__iterator_category(__result)); 4475 } 4476 4477 /** 4478 * @brief Copy a sequence, removing consecutive values using a predicate. 4479 * @ingroup mutating_algorithms 4480 * @param __first An input iterator. 4481 * @param __last An input iterator. 4482 * @param __result An output iterator. 4483 * @param __binary_pred A binary predicate. 4484 * @return An iterator designating the end of the resulting sequence. 4485 * 4486 * Copies each element in the range `[__first, __last)` to the range 4487 * beginning at `__result`, except that only the first element is copied 4488 * from groups of consecutive elements for which `__binary_pred` returns 4489 * true. 4490 * `unique_copy()` is stable, so the relative order of elements that are 4491 * copied is unchanged. 4492 */ 4493 // _GLIBCXX_RESOLVE_LIB_DEFECTS 4494 // DR 241. Does unique_copy() require CopyConstructible and Assignable? 4495 template<typename _InputIterator, typename _OutputIterator, 4496 typename _BinaryPredicate> 4497 _GLIBCXX20_CONSTEXPR 4498 inline _OutputIterator 4499 unique_copy(_InputIterator __first, _InputIterator __last, 4500 _OutputIterator __result, 4501 _BinaryPredicate __binary_pred) 4502 { 4503 // concept requirements -- predicates checked later 4504 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 4505 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 4506 typename iterator_traits<_InputIterator>::value_type>) 4507 __glibcxx_requires_valid_range(__first, __last); 4508 4509 if (__first == __last) 4510 return __result; 4511 return std::__unique_copy(__first, __last, __result, 4512 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred), 4513 std::__iterator_category(__first), 4514 std::__iterator_category(__result)); 4515 } 4516 4517 #if __cplusplus <= 201103L || _GLIBCXX_USE_DEPRECATED 4518 #if _GLIBCXX_HOSTED 4519 /** 4520 * @brief Randomly shuffle the elements of a sequence. 4521 * @ingroup mutating_algorithms 4522 * @param __first A forward iterator. 4523 * @param __last A forward iterator. 4524 * @return Nothing. 4525 * 4526 * Reorder the elements in the range `[__first, __last)` using a random 4527 * distribution, so that every possible ordering of the sequence is 4528 * equally likely. 4529 * 4530 * @deprecated 4531 * Since C++17, `std::random_shuffle` is not part of the C++ standard. 4532 * Use `std::shuffle` instead, which was introduced in C++11. 4533 */ 4534 template<typename _RandomAccessIterator> 4535 _GLIBCXX14_DEPRECATED_SUGGEST("std::shuffle") 4536 inline void 4537 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last) 4538 { 4539 // concept requirements 4540 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 4541 _RandomAccessIterator>) 4542 __glibcxx_requires_valid_range(__first, __last); 4543 4544 if (__first == __last) 4545 return; 4546 4547 #if RAND_MAX < __INT_MAX__ 4548 if (__builtin_expect((__last - __first) >= RAND_MAX / 4, 0)) 4549 { 4550 // Use a xorshift implementation seeded by two calls to rand() 4551 // instead of using rand() for all the random numbers needed. 4552 unsigned __xss 4553 = (unsigned)std::rand() ^ ((unsigned)std::rand() << 15); 4554 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i) 4555 { 4556 __xss += !__xss; 4557 __xss ^= __xss << 13; 4558 __xss ^= __xss >> 17; 4559 __xss ^= __xss << 5; 4560 _RandomAccessIterator __j = __first 4561 + (__xss % ((__i - __first) + 1)); 4562 if (__i != __j) 4563 std::iter_swap(__i, __j); 4564 } 4565 return; 4566 } 4567 #endif 4568 4569 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i) 4570 { 4571 // XXX rand() % N is not uniformly distributed 4572 _RandomAccessIterator __j = __first 4573 + (std::rand() % ((__i - __first) + 1)); 4574 if (__i != __j) 4575 std::iter_swap(__i, __j); 4576 } 4577 } 4578 4579 /** 4580 * @brief Shuffle the elements of a sequence using a random number 4581 * generator. 4582 * @ingroup mutating_algorithms 4583 * @param __first A forward iterator. 4584 * @param __last A forward iterator. 4585 * @param __rand The RNG functor or function. 4586 * @return Nothing. 4587 * 4588 * Reorders the elements in the range `[__first, __last)` using `__rand` 4589 * to provide a random distribution. Calling `__rand(N)` for a positive 4590 * integer `N` should return a randomly chosen integer from the 4591 * range `[0, N)`. 4592 * 4593 * @deprecated 4594 * Since C++17, `std::random_shuffle` is not part of the C++ standard. 4595 * Use `std::shuffle` instead, which was introduced in C++11. 4596 */ 4597 template<typename _RandomAccessIterator, typename _RandomNumberGenerator> 4598 _GLIBCXX14_DEPRECATED_SUGGEST("std::shuffle") 4599 void 4600 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last, 4601 #if __cplusplus >= 201103L 4602 _RandomNumberGenerator&& __rand) 4603 #else 4604 _RandomNumberGenerator& __rand) 4605 #endif 4606 { 4607 // concept requirements 4608 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 4609 _RandomAccessIterator>) 4610 __glibcxx_requires_valid_range(__first, __last); 4611 4612 if (__first == __last) 4613 return; 4614 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i) 4615 { 4616 _RandomAccessIterator __j = __first + __rand((__i - __first) + 1); 4617 if (__i != __j) 4618 std::iter_swap(__i, __j); 4619 } 4620 } 4621 #endif // HOSTED 4622 #endif // <= C++11 || USE_DEPRECATED 4623 4624 /** 4625 * @brief Move elements for which a predicate is true to the beginning 4626 * of a sequence. 4627 * @ingroup mutating_algorithms 4628 * @param __first A forward iterator. 4629 * @param __last A forward iterator. 4630 * @param __pred A predicate functor. 4631 * @return An iterator `middle` such that `__pred(i)` is true for each 4632 * iterator `i` in the range `[__first, middle)` and false for each `i` 4633 * in the range `[middle, __last)`. 4634 * 4635 * `__pred` must not modify its operand. `partition()` does not preserve 4636 * the relative ordering of elements in each group, use 4637 * `stable_partition()` if this is needed. 4638 */ 4639 template<typename _ForwardIterator, typename _Predicate> 4640 _GLIBCXX20_CONSTEXPR 4641 inline _ForwardIterator 4642 partition(_ForwardIterator __first, _ForwardIterator __last, 4643 _Predicate __pred) 4644 { 4645 // concept requirements 4646 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 4647 _ForwardIterator>) 4648 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 4649 typename iterator_traits<_ForwardIterator>::value_type>) 4650 __glibcxx_requires_valid_range(__first, __last); 4651 4652 return std::__partition(__first, __last, __pred, 4653 std::__iterator_category(__first)); 4654 } 4655 4656 4657 /** 4658 * @brief Sort the smallest elements of a sequence. 4659 * @ingroup sorting_algorithms 4660 * @param __first An iterator. 4661 * @param __middle Another iterator. 4662 * @param __last Another iterator. 4663 * @return Nothing. 4664 * 4665 * Sorts the smallest `(__middle - __first)` elements in the range 4666 * `[first, last)` and moves them to the range `[__first, __middle)`. The 4667 * order of the remaining elements in the range `[__middle, __last)` is 4668 * unspecified. 4669 * After the sort if `i` and `j` are iterators in the range 4670 * `[__first, __middle)` such that `i` precedes `j` and `k` is an iterator 4671 * in the range `[__middle, __last)` then `*j < *i` and `*k < *i` are 4672 * both false. 4673 */ 4674 template<typename _RandomAccessIterator> 4675 _GLIBCXX20_CONSTEXPR 4676 inline void 4677 partial_sort(_RandomAccessIterator __first, 4678 _RandomAccessIterator __middle, 4679 _RandomAccessIterator __last) 4680 { 4681 // concept requirements 4682 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 4683 _RandomAccessIterator>) 4684 __glibcxx_function_requires(_LessThanComparableConcept< 4685 typename iterator_traits<_RandomAccessIterator>::value_type>) 4686 __glibcxx_requires_valid_range(__first, __middle); 4687 __glibcxx_requires_valid_range(__middle, __last); 4688 __glibcxx_requires_irreflexive(__first, __last); 4689 4690 std::__partial_sort(__first, __middle, __last, 4691 __gnu_cxx::__ops::__iter_less_iter()); 4692 } 4693 4694 /** 4695 * @brief Sort the smallest elements of a sequence using a predicate 4696 * for comparison. 4697 * @ingroup sorting_algorithms 4698 * @param __first An iterator. 4699 * @param __middle Another iterator. 4700 * @param __last Another iterator. 4701 * @param __comp A comparison functor. 4702 * @return Nothing. 4703 * 4704 * Sorts the smallest `(__middle - __first)` elements in the range 4705 * `[__first, __last)` and moves them to the range `[__first, __middle)`. 4706 * The order of the remaining elements in the range `[__middle, __last)` is 4707 * unspecified. 4708 * After the sort if `i` and `j` are iterators in the range 4709 * `[__first, __middle)` such that `i` precedes `j` and `k` is an iterator 4710 * in the range `[__middle, __last)` then `*__comp(j, *i)` and 4711 * `__comp(*k, *i)` are both false. 4712 */ 4713 template<typename _RandomAccessIterator, typename _Compare> 4714 _GLIBCXX20_CONSTEXPR 4715 inline void 4716 partial_sort(_RandomAccessIterator __first, 4717 _RandomAccessIterator __middle, 4718 _RandomAccessIterator __last, 4719 _Compare __comp) 4720 { 4721 // concept requirements 4722 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 4723 _RandomAccessIterator>) 4724 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 4725 typename iterator_traits<_RandomAccessIterator>::value_type, 4726 typename iterator_traits<_RandomAccessIterator>::value_type>) 4727 __glibcxx_requires_valid_range(__first, __middle); 4728 __glibcxx_requires_valid_range(__middle, __last); 4729 __glibcxx_requires_irreflexive_pred(__first, __last, __comp); 4730 4731 std::__partial_sort(__first, __middle, __last, 4732 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 4733 } 4734 4735 /** 4736 * @brief Sort a sequence just enough to find a particular position. 4737 * @ingroup sorting_algorithms 4738 * @param __first An iterator. 4739 * @param __nth Another iterator. 4740 * @param __last Another iterator. 4741 * @return Nothing. 4742 * 4743 * Rearranges the elements in the range `[__first, __last)` so that `*__nth` 4744 * is the same element that would have been in that position had the 4745 * whole sequence been sorted. The elements either side of `*__nth` are 4746 * not completely sorted, but for any iterator `i` in the range 4747 * `[__first, __nth)` and any iterator `j` in the range `[__nth, __last)` it 4748 * holds that `*j < *i` is false. 4749 */ 4750 template<typename _RandomAccessIterator> 4751 _GLIBCXX20_CONSTEXPR 4752 inline void 4753 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, 4754 _RandomAccessIterator __last) 4755 { 4756 // concept requirements 4757 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 4758 _RandomAccessIterator>) 4759 __glibcxx_function_requires(_LessThanComparableConcept< 4760 typename iterator_traits<_RandomAccessIterator>::value_type>) 4761 __glibcxx_requires_valid_range(__first, __nth); 4762 __glibcxx_requires_valid_range(__nth, __last); 4763 __glibcxx_requires_irreflexive(__first, __last); 4764 4765 if (__first == __last || __nth == __last) 4766 return; 4767 4768 std::__introselect(__first, __nth, __last, 4769 std::__lg(__last - __first) * 2, 4770 __gnu_cxx::__ops::__iter_less_iter()); 4771 } 4772 4773 /** 4774 * @brief Sort a sequence just enough to find a particular position 4775 * using a predicate for comparison. 4776 * @ingroup sorting_algorithms 4777 * @param __first An iterator. 4778 * @param __nth Another iterator. 4779 * @param __last Another iterator. 4780 * @param __comp A comparison functor. 4781 * @return Nothing. 4782 * 4783 * Rearranges the elements in the range `[__first, __last)` so that `*__nth` 4784 * is the same element that would have been in that position had the 4785 * whole sequence been sorted. The elements either side of `*__nth` are 4786 * not completely sorted, but for any iterator `i` in the range 4787 * `[__first, __nth)` and any iterator `j` in the range `[__nth, __last)` 4788 * it holds that `__comp(*j, *i)` is false. 4789 */ 4790 template<typename _RandomAccessIterator, typename _Compare> 4791 _GLIBCXX20_CONSTEXPR 4792 inline void 4793 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, 4794 _RandomAccessIterator __last, _Compare __comp) 4795 { 4796 // concept requirements 4797 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 4798 _RandomAccessIterator>) 4799 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 4800 typename iterator_traits<_RandomAccessIterator>::value_type, 4801 typename iterator_traits<_RandomAccessIterator>::value_type>) 4802 __glibcxx_requires_valid_range(__first, __nth); 4803 __glibcxx_requires_valid_range(__nth, __last); 4804 __glibcxx_requires_irreflexive_pred(__first, __last, __comp); 4805 4806 if (__first == __last || __nth == __last) 4807 return; 4808 4809 std::__introselect(__first, __nth, __last, 4810 std::__lg(__last - __first) * 2, 4811 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 4812 } 4813 4814 /** 4815 * @brief Sort the elements of a sequence. 4816 * @ingroup sorting_algorithms 4817 * @param __first An iterator. 4818 * @param __last Another iterator. 4819 * @return Nothing. 4820 * 4821 * Sorts the elements in the range `[__first, __last)` in ascending order, 4822 * such that for each iterator `i` in the range `[__first, __last - 1)`, 4823 * `*(i+1) < *i` is false. 4824 * 4825 * The relative ordering of equivalent elements is not preserved, use 4826 * `stable_sort()` if this is needed. 4827 */ 4828 template<typename _RandomAccessIterator> 4829 _GLIBCXX20_CONSTEXPR 4830 inline void 4831 sort(_RandomAccessIterator __first, _RandomAccessIterator __last) 4832 { 4833 // concept requirements 4834 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 4835 _RandomAccessIterator>) 4836 __glibcxx_function_requires(_LessThanComparableConcept< 4837 typename iterator_traits<_RandomAccessIterator>::value_type>) 4838 __glibcxx_requires_valid_range(__first, __last); 4839 __glibcxx_requires_irreflexive(__first, __last); 4840 4841 std::__sort(__first, __last, __gnu_cxx::__ops::__iter_less_iter()); 4842 } 4843 4844 /** 4845 * @brief Sort the elements of a sequence using a predicate for comparison. 4846 * @ingroup sorting_algorithms 4847 * @param __first An iterator. 4848 * @param __last Another iterator. 4849 * @param __comp A comparison functor. 4850 * @return Nothing. 4851 * 4852 * Sorts the elements in the range `[__first, __last)` in ascending order, 4853 * such that `__comp(*(i+1), *i)` is false for every iterator `i` in the 4854 * range `[__first, __last - 1)`. 4855 * 4856 * The relative ordering of equivalent elements is not preserved, use 4857 * `stable_sort()` if this is needed. 4858 */ 4859 template<typename _RandomAccessIterator, typename _Compare> 4860 _GLIBCXX20_CONSTEXPR 4861 inline void 4862 sort(_RandomAccessIterator __first, _RandomAccessIterator __last, 4863 _Compare __comp) 4864 { 4865 // concept requirements 4866 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 4867 _RandomAccessIterator>) 4868 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 4869 typename iterator_traits<_RandomAccessIterator>::value_type, 4870 typename iterator_traits<_RandomAccessIterator>::value_type>) 4871 __glibcxx_requires_valid_range(__first, __last); 4872 __glibcxx_requires_irreflexive_pred(__first, __last, __comp); 4873 4874 std::__sort(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp)); 4875 } 4876 4877 template<typename _InputIterator1, typename _InputIterator2, 4878 typename _OutputIterator, typename _Compare> 4879 _GLIBCXX20_CONSTEXPR 4880 _OutputIterator 4881 __merge(_InputIterator1 __first1, _InputIterator1 __last1, 4882 _InputIterator2 __first2, _InputIterator2 __last2, 4883 _OutputIterator __result, _Compare __comp) 4884 { 4885 while (__first1 != __last1 && __first2 != __last2) 4886 { 4887 if (__comp(__first2, __first1)) 4888 { 4889 *__result = *__first2; 4890 ++__first2; 4891 } 4892 else 4893 { 4894 *__result = *__first1; 4895 ++__first1; 4896 } 4897 ++__result; 4898 } 4899 return std::copy(__first2, __last2, 4900 std::copy(__first1, __last1, __result)); 4901 } 4902 4903 /** 4904 * @brief Merges two sorted ranges. 4905 * @ingroup sorting_algorithms 4906 * @param __first1 An iterator. 4907 * @param __first2 Another iterator. 4908 * @param __last1 Another iterator. 4909 * @param __last2 Another iterator. 4910 * @param __result An iterator pointing to the end of the merged range. 4911 * @return An output iterator equal to @p __result + (__last1 - __first1) 4912 * + (__last2 - __first2). 4913 * 4914 * Merges the ranges @p [__first1,__last1) and @p [__first2,__last2) into 4915 * the sorted range @p [__result, __result + (__last1-__first1) + 4916 * (__last2-__first2)). Both input ranges must be sorted, and the 4917 * output range must not overlap with either of the input ranges. 4918 * The sort is @e stable, that is, for equivalent elements in the 4919 * two ranges, elements from the first range will always come 4920 * before elements from the second. 4921 */ 4922 template<typename _InputIterator1, typename _InputIterator2, 4923 typename _OutputIterator> 4924 _GLIBCXX20_CONSTEXPR 4925 inline _OutputIterator 4926 merge(_InputIterator1 __first1, _InputIterator1 __last1, 4927 _InputIterator2 __first2, _InputIterator2 __last2, 4928 _OutputIterator __result) 4929 { 4930 // concept requirements 4931 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 4932 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 4933 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 4934 typename iterator_traits<_InputIterator1>::value_type>) 4935 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 4936 typename iterator_traits<_InputIterator2>::value_type>) 4937 __glibcxx_function_requires(_LessThanOpConcept< 4938 typename iterator_traits<_InputIterator2>::value_type, 4939 typename iterator_traits<_InputIterator1>::value_type>) 4940 __glibcxx_requires_sorted_set(__first1, __last1, __first2); 4941 __glibcxx_requires_sorted_set(__first2, __last2, __first1); 4942 __glibcxx_requires_irreflexive2(__first1, __last1); 4943 __glibcxx_requires_irreflexive2(__first2, __last2); 4944 4945 return _GLIBCXX_STD_A::__merge(__first1, __last1, 4946 __first2, __last2, __result, 4947 __gnu_cxx::__ops::__iter_less_iter()); 4948 } 4949 4950 /** 4951 * @brief Merges two sorted ranges. 4952 * @ingroup sorting_algorithms 4953 * @param __first1 An iterator. 4954 * @param __first2 Another iterator. 4955 * @param __last1 Another iterator. 4956 * @param __last2 Another iterator. 4957 * @param __result An iterator pointing to the end of the merged range. 4958 * @param __comp A functor to use for comparisons. 4959 * @return An output iterator equal to @p __result + (__last1 - __first1) 4960 * + (__last2 - __first2). 4961 * 4962 * Merges the ranges @p [__first1,__last1) and @p [__first2,__last2) into 4963 * the sorted range @p [__result, __result + (__last1-__first1) + 4964 * (__last2-__first2)). Both input ranges must be sorted, and the 4965 * output range must not overlap with either of the input ranges. 4966 * The sort is @e stable, that is, for equivalent elements in the 4967 * two ranges, elements from the first range will always come 4968 * before elements from the second. 4969 * 4970 * The comparison function should have the same effects on ordering as 4971 * the function used for the initial sort. 4972 */ 4973 template<typename _InputIterator1, typename _InputIterator2, 4974 typename _OutputIterator, typename _Compare> 4975 _GLIBCXX20_CONSTEXPR 4976 inline _OutputIterator 4977 merge(_InputIterator1 __first1, _InputIterator1 __last1, 4978 _InputIterator2 __first2, _InputIterator2 __last2, 4979 _OutputIterator __result, _Compare __comp) 4980 { 4981 // concept requirements 4982 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 4983 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 4984 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 4985 typename iterator_traits<_InputIterator1>::value_type>) 4986 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 4987 typename iterator_traits<_InputIterator2>::value_type>) 4988 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 4989 typename iterator_traits<_InputIterator2>::value_type, 4990 typename iterator_traits<_InputIterator1>::value_type>) 4991 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp); 4992 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp); 4993 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp); 4994 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp); 4995 4996 return _GLIBCXX_STD_A::__merge(__first1, __last1, 4997 __first2, __last2, __result, 4998 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 4999 } 5000 5001 template<typename _RandomAccessIterator, typename _Compare> 5002 _GLIBCXX26_CONSTEXPR 5003 inline void 5004 __stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, 5005 _Compare __comp) 5006 { 5007 typedef typename iterator_traits<_RandomAccessIterator>::value_type 5008 _ValueType; 5009 typedef typename iterator_traits<_RandomAccessIterator>::difference_type 5010 _DistanceType; 5011 5012 if (__first == __last) 5013 return; 5014 5015 #if _GLIBCXX_HOSTED 5016 # if __glibcxx_constexpr_algorithms >= 202306L // >= C++26 5017 if consteval { 5018 return std::__inplace_stable_sort(__first, __last, __comp); 5019 } 5020 # endif 5021 5022 typedef _Temporary_buffer<_RandomAccessIterator, _ValueType> _TmpBuf; 5023 // __stable_sort_adaptive sorts the range in two halves, 5024 // so the buffer only needs to fit half the range at once. 5025 _TmpBuf __buf(__first, (__last - __first + 1) / 2); 5026 5027 if (__builtin_expect(__buf.requested_size() == __buf.size(), true)) 5028 std::__stable_sort_adaptive(__first, 5029 __first + _DistanceType(__buf.size()), 5030 __last, __buf.begin(), __comp); 5031 else if (__builtin_expect(__buf.begin() == 0, false)) 5032 std::__inplace_stable_sort(__first, __last, __comp); 5033 else 5034 std::__stable_sort_adaptive_resize(__first, __last, __buf.begin(), 5035 _DistanceType(__buf.size()), __comp); 5036 #else 5037 std::__inplace_stable_sort(__first, __last, __comp); 5038 #endif 5039 } 5040 5041 /** 5042 * @brief Sort the elements of a sequence, preserving the relative order 5043 * of equivalent elements. 5044 * @ingroup sorting_algorithms 5045 * @param __first An iterator. 5046 * @param __last Another iterator. 5047 * @return Nothing. 5048 * 5049 * Sorts the elements in the range @p [__first,__last) in ascending order, 5050 * such that for each iterator @p i in the range @p [__first,__last-1), 5051 * @p *(i+1)<*i is false. 5052 * 5053 * The relative ordering of equivalent elements is preserved, so any two 5054 * elements @p x and @p y in the range @p [__first,__last) such that 5055 * @p x<y is false and @p y<x is false will have the same relative 5056 * ordering after calling @p stable_sort(). 5057 */ 5058 template<typename _RandomAccessIterator> 5059 _GLIBCXX26_CONSTEXPR 5060 inline void 5061 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last) 5062 { 5063 // concept requirements 5064 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 5065 _RandomAccessIterator>) 5066 __glibcxx_function_requires(_LessThanComparableConcept< 5067 typename iterator_traits<_RandomAccessIterator>::value_type>) 5068 __glibcxx_requires_valid_range(__first, __last); 5069 __glibcxx_requires_irreflexive(__first, __last); 5070 5071 _GLIBCXX_STD_A::__stable_sort(__first, __last, 5072 __gnu_cxx::__ops::__iter_less_iter()); 5073 } 5074 5075 /** 5076 * @brief Sort the elements of a sequence using a predicate for comparison, 5077 * preserving the relative order of equivalent elements. 5078 * @ingroup sorting_algorithms 5079 * @param __first An iterator. 5080 * @param __last Another iterator. 5081 * @param __comp A comparison functor. 5082 * @return Nothing. 5083 * 5084 * Sorts the elements in the range @p [__first,__last) in ascending order, 5085 * such that for each iterator @p i in the range @p [__first,__last-1), 5086 * @p __comp(*(i+1),*i) is false. 5087 * 5088 * The relative ordering of equivalent elements is preserved, so any two 5089 * elements @p x and @p y in the range @p [__first,__last) such that 5090 * @p __comp(x,y) is false and @p __comp(y,x) is false will have the same 5091 * relative ordering after calling @p stable_sort(). 5092 */ 5093 template<typename _RandomAccessIterator, typename _Compare> 5094 _GLIBCXX26_CONSTEXPR 5095 inline void 5096 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, 5097 _Compare __comp) 5098 { 5099 // concept requirements 5100 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 5101 _RandomAccessIterator>) 5102 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 5103 typename iterator_traits<_RandomAccessIterator>::value_type, 5104 typename iterator_traits<_RandomAccessIterator>::value_type>) 5105 __glibcxx_requires_valid_range(__first, __last); 5106 __glibcxx_requires_irreflexive_pred(__first, __last, __comp); 5107 5108 _GLIBCXX_STD_A::__stable_sort(__first, __last, 5109 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 5110 } 5111 5112 template<typename _InputIterator1, typename _InputIterator2, 5113 typename _OutputIterator, 5114 typename _Compare> 5115 _GLIBCXX20_CONSTEXPR 5116 _OutputIterator 5117 __set_union(_InputIterator1 __first1, _InputIterator1 __last1, 5118 _InputIterator2 __first2, _InputIterator2 __last2, 5119 _OutputIterator __result, _Compare __comp) 5120 { 5121 while (__first1 != __last1 && __first2 != __last2) 5122 { 5123 if (__comp(__first1, __first2)) 5124 { 5125 *__result = *__first1; 5126 ++__first1; 5127 } 5128 else if (__comp(__first2, __first1)) 5129 { 5130 *__result = *__first2; 5131 ++__first2; 5132 } 5133 else 5134 { 5135 *__result = *__first1; 5136 ++__first1; 5137 ++__first2; 5138 } 5139 ++__result; 5140 } 5141 return std::copy(__first2, __last2, 5142 std::copy(__first1, __last1, __result)); 5143 } 5144 5145 /** 5146 * @brief Return the union of two sorted ranges. 5147 * @ingroup set_algorithms 5148 * @param __first1 Start of first range. 5149 * @param __last1 End of first range. 5150 * @param __first2 Start of second range. 5151 * @param __last2 End of second range. 5152 * @param __result Start of output range. 5153 * @return End of the output range. 5154 * @ingroup set_algorithms 5155 * 5156 * This operation iterates over both ranges, copying elements present in 5157 * each range in order to the output range. Iterators increment for each 5158 * range. When the current element of one range is less than the other, 5159 * that element is copied and the iterator advanced. If an element is 5160 * contained in both ranges, the element from the first range is copied and 5161 * both ranges advance. The output range may not overlap either input 5162 * range. 5163 */ 5164 template<typename _InputIterator1, typename _InputIterator2, 5165 typename _OutputIterator> 5166 _GLIBCXX20_CONSTEXPR 5167 inline _OutputIterator 5168 set_union(_InputIterator1 __first1, _InputIterator1 __last1, 5169 _InputIterator2 __first2, _InputIterator2 __last2, 5170 _OutputIterator __result) 5171 { 5172 // concept requirements 5173 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 5174 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 5175 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 5176 typename iterator_traits<_InputIterator1>::value_type>) 5177 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 5178 typename iterator_traits<_InputIterator2>::value_type>) 5179 __glibcxx_function_requires(_LessThanOpConcept< 5180 typename iterator_traits<_InputIterator1>::value_type, 5181 typename iterator_traits<_InputIterator2>::value_type>) 5182 __glibcxx_function_requires(_LessThanOpConcept< 5183 typename iterator_traits<_InputIterator2>::value_type, 5184 typename iterator_traits<_InputIterator1>::value_type>) 5185 __glibcxx_requires_sorted_set(__first1, __last1, __first2); 5186 __glibcxx_requires_sorted_set(__first2, __last2, __first1); 5187 __glibcxx_requires_irreflexive2(__first1, __last1); 5188 __glibcxx_requires_irreflexive2(__first2, __last2); 5189 5190 return _GLIBCXX_STD_A::__set_union(__first1, __last1, 5191 __first2, __last2, __result, 5192 __gnu_cxx::__ops::__iter_less_iter()); 5193 } 5194 5195 /** 5196 * @brief Return the union of two sorted ranges using a comparison functor. 5197 * @ingroup set_algorithms 5198 * @param __first1 Start of first range. 5199 * @param __last1 End of first range. 5200 * @param __first2 Start of second range. 5201 * @param __last2 End of second range. 5202 * @param __result Start of output range. 5203 * @param __comp The comparison functor. 5204 * @return End of the output range. 5205 * @ingroup set_algorithms 5206 * 5207 * This operation iterates over both ranges, copying elements present in 5208 * each range in order to the output range. Iterators increment for each 5209 * range. When the current element of one range is less than the other 5210 * according to @p __comp, that element is copied and the iterator advanced. 5211 * If an equivalent element according to @p __comp is contained in both 5212 * ranges, the element from the first range is copied and both ranges 5213 * advance. The output range may not overlap either input range. 5214 */ 5215 template<typename _InputIterator1, typename _InputIterator2, 5216 typename _OutputIterator, typename _Compare> 5217 _GLIBCXX20_CONSTEXPR 5218 inline _OutputIterator 5219 set_union(_InputIterator1 __first1, _InputIterator1 __last1, 5220 _InputIterator2 __first2, _InputIterator2 __last2, 5221 _OutputIterator __result, _Compare __comp) 5222 { 5223 // concept requirements 5224 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 5225 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 5226 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 5227 typename iterator_traits<_InputIterator1>::value_type>) 5228 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 5229 typename iterator_traits<_InputIterator2>::value_type>) 5230 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 5231 typename iterator_traits<_InputIterator1>::value_type, 5232 typename iterator_traits<_InputIterator2>::value_type>) 5233 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 5234 typename iterator_traits<_InputIterator2>::value_type, 5235 typename iterator_traits<_InputIterator1>::value_type>) 5236 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp); 5237 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp); 5238 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp); 5239 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp); 5240 5241 return _GLIBCXX_STD_A::__set_union(__first1, __last1, 5242 __first2, __last2, __result, 5243 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 5244 } 5245 5246 template<typename _InputIterator1, typename _InputIterator2, 5247 typename _OutputIterator, 5248 typename _Compare> 5249 _GLIBCXX20_CONSTEXPR 5250 _OutputIterator 5251 __set_intersection(_InputIterator1 __first1, _InputIterator1 __last1, 5252 _InputIterator2 __first2, _InputIterator2 __last2, 5253 _OutputIterator __result, _Compare __comp) 5254 { 5255 while (__first1 != __last1 && __first2 != __last2) 5256 if (__comp(__first1, __first2)) 5257 ++__first1; 5258 else if (__comp(__first2, __first1)) 5259 ++__first2; 5260 else 5261 { 5262 *__result = *__first1; 5263 ++__first1; 5264 ++__first2; 5265 ++__result; 5266 } 5267 return __result; 5268 } 5269 5270 /** 5271 * @brief Return the intersection of two sorted ranges. 5272 * @ingroup set_algorithms 5273 * @param __first1 Start of first range. 5274 * @param __last1 End of first range. 5275 * @param __first2 Start of second range. 5276 * @param __last2 End of second range. 5277 * @param __result Start of output range. 5278 * @return End of the output range. 5279 * @ingroup set_algorithms 5280 * 5281 * This operation iterates over both ranges, copying elements present in 5282 * both ranges in order to the output range. Iterators increment for each 5283 * range. When the current element of one range is less than the other, 5284 * that iterator advances. If an element is contained in both ranges, the 5285 * element from the first range is copied and both ranges advance. The 5286 * output range may not overlap either input range. 5287 */ 5288 template<typename _InputIterator1, typename _InputIterator2, 5289 typename _OutputIterator> 5290 _GLIBCXX20_CONSTEXPR 5291 inline _OutputIterator 5292 set_intersection(_InputIterator1 __first1, _InputIterator1 __last1, 5293 _InputIterator2 __first2, _InputIterator2 __last2, 5294 _OutputIterator __result) 5295 { 5296 // concept requirements 5297 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 5298 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 5299 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 5300 typename iterator_traits<_InputIterator1>::value_type>) 5301 __glibcxx_function_requires(_LessThanOpConcept< 5302 typename iterator_traits<_InputIterator1>::value_type, 5303 typename iterator_traits<_InputIterator2>::value_type>) 5304 __glibcxx_function_requires(_LessThanOpConcept< 5305 typename iterator_traits<_InputIterator2>::value_type, 5306 typename iterator_traits<_InputIterator1>::value_type>) 5307 __glibcxx_requires_sorted_set(__first1, __last1, __first2); 5308 __glibcxx_requires_sorted_set(__first2, __last2, __first1); 5309 __glibcxx_requires_irreflexive2(__first1, __last1); 5310 __glibcxx_requires_irreflexive2(__first2, __last2); 5311 5312 return _GLIBCXX_STD_A::__set_intersection(__first1, __last1, 5313 __first2, __last2, __result, 5314 __gnu_cxx::__ops::__iter_less_iter()); 5315 } 5316 5317 /** 5318 * @brief Return the intersection of two sorted ranges using comparison 5319 * functor. 5320 * @ingroup set_algorithms 5321 * @param __first1 Start of first range. 5322 * @param __last1 End of first range. 5323 * @param __first2 Start of second range. 5324 * @param __last2 End of second range. 5325 * @param __result Start of output range. 5326 * @param __comp The comparison functor. 5327 * @return End of the output range. 5328 * @ingroup set_algorithms 5329 * 5330 * This operation iterates over both ranges, copying elements present in 5331 * both ranges in order to the output range. Iterators increment for each 5332 * range. When the current element of one range is less than the other 5333 * according to @p __comp, that iterator advances. If an element is 5334 * contained in both ranges according to @p __comp, the element from the 5335 * first range is copied and both ranges advance. The output range may not 5336 * overlap either input range. 5337 */ 5338 template<typename _InputIterator1, typename _InputIterator2, 5339 typename _OutputIterator, typename _Compare> 5340 _GLIBCXX20_CONSTEXPR 5341 inline _OutputIterator 5342 set_intersection(_InputIterator1 __first1, _InputIterator1 __last1, 5343 _InputIterator2 __first2, _InputIterator2 __last2, 5344 _OutputIterator __result, _Compare __comp) 5345 { 5346 // concept requirements 5347 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 5348 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 5349 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 5350 typename iterator_traits<_InputIterator1>::value_type>) 5351 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 5352 typename iterator_traits<_InputIterator1>::value_type, 5353 typename iterator_traits<_InputIterator2>::value_type>) 5354 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 5355 typename iterator_traits<_InputIterator2>::value_type, 5356 typename iterator_traits<_InputIterator1>::value_type>) 5357 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp); 5358 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp); 5359 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp); 5360 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp); 5361 5362 return _GLIBCXX_STD_A::__set_intersection(__first1, __last1, 5363 __first2, __last2, __result, 5364 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 5365 } 5366 5367 template<typename _InputIterator1, typename _InputIterator2, 5368 typename _OutputIterator, 5369 typename _Compare> 5370 _GLIBCXX20_CONSTEXPR 5371 _OutputIterator 5372 __set_difference(_InputIterator1 __first1, _InputIterator1 __last1, 5373 _InputIterator2 __first2, _InputIterator2 __last2, 5374 _OutputIterator __result, _Compare __comp) 5375 { 5376 while (__first1 != __last1 && __first2 != __last2) 5377 if (__comp(__first1, __first2)) 5378 { 5379 *__result = *__first1; 5380 ++__first1; 5381 ++__result; 5382 } 5383 else if (__comp(__first2, __first1)) 5384 ++__first2; 5385 else 5386 { 5387 ++__first1; 5388 ++__first2; 5389 } 5390 return std::copy(__first1, __last1, __result); 5391 } 5392 5393 /** 5394 * @brief Return the difference of two sorted ranges. 5395 * @ingroup set_algorithms 5396 * @param __first1 Start of first range. 5397 * @param __last1 End of first range. 5398 * @param __first2 Start of second range. 5399 * @param __last2 End of second range. 5400 * @param __result Start of output range. 5401 * @return End of the output range. 5402 * @ingroup set_algorithms 5403 * 5404 * This operation iterates over both ranges, copying elements present in 5405 * the first range but not the second in order to the output range. 5406 * Iterators increment for each range. When the current element of the 5407 * first range is less than the second, that element is copied and the 5408 * iterator advances. If the current element of the second range is less, 5409 * the iterator advances, but no element is copied. If an element is 5410 * contained in both ranges, no elements are copied and both ranges 5411 * advance. The output range may not overlap either input range. 5412 */ 5413 template<typename _InputIterator1, typename _InputIterator2, 5414 typename _OutputIterator> 5415 _GLIBCXX20_CONSTEXPR 5416 inline _OutputIterator 5417 set_difference(_InputIterator1 __first1, _InputIterator1 __last1, 5418 _InputIterator2 __first2, _InputIterator2 __last2, 5419 _OutputIterator __result) 5420 { 5421 // concept requirements 5422 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 5423 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 5424 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 5425 typename iterator_traits<_InputIterator1>::value_type>) 5426 __glibcxx_function_requires(_LessThanOpConcept< 5427 typename iterator_traits<_InputIterator1>::value_type, 5428 typename iterator_traits<_InputIterator2>::value_type>) 5429 __glibcxx_function_requires(_LessThanOpConcept< 5430 typename iterator_traits<_InputIterator2>::value_type, 5431 typename iterator_traits<_InputIterator1>::value_type>) 5432 __glibcxx_requires_sorted_set(__first1, __last1, __first2); 5433 __glibcxx_requires_sorted_set(__first2, __last2, __first1); 5434 __glibcxx_requires_irreflexive2(__first1, __last1); 5435 __glibcxx_requires_irreflexive2(__first2, __last2); 5436 5437 return _GLIBCXX_STD_A::__set_difference(__first1, __last1, 5438 __first2, __last2, __result, 5439 __gnu_cxx::__ops::__iter_less_iter()); 5440 } 5441 5442 /** 5443 * @brief Return the difference of two sorted ranges using comparison 5444 * functor. 5445 * @ingroup set_algorithms 5446 * @param __first1 Start of first range. 5447 * @param __last1 End of first range. 5448 * @param __first2 Start of second range. 5449 * @param __last2 End of second range. 5450 * @param __result Start of output range. 5451 * @param __comp The comparison functor. 5452 * @return End of the output range. 5453 * @ingroup set_algorithms 5454 * 5455 * This operation iterates over both ranges, copying elements present in 5456 * the first range but not the second in order to the output range. 5457 * Iterators increment for each range. When the current element of the 5458 * first range is less than the second according to @p __comp, that element 5459 * is copied and the iterator advances. If the current element of the 5460 * second range is less, no element is copied and the iterator advances. 5461 * If an element is contained in both ranges according to @p __comp, no 5462 * elements are copied and both ranges advance. The output range may not 5463 * overlap either input range. 5464 */ 5465 template<typename _InputIterator1, typename _InputIterator2, 5466 typename _OutputIterator, typename _Compare> 5467 _GLIBCXX20_CONSTEXPR 5468 inline _OutputIterator 5469 set_difference(_InputIterator1 __first1, _InputIterator1 __last1, 5470 _InputIterator2 __first2, _InputIterator2 __last2, 5471 _OutputIterator __result, _Compare __comp) 5472 { 5473 // concept requirements 5474 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 5475 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 5476 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 5477 typename iterator_traits<_InputIterator1>::value_type>) 5478 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 5479 typename iterator_traits<_InputIterator1>::value_type, 5480 typename iterator_traits<_InputIterator2>::value_type>) 5481 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 5482 typename iterator_traits<_InputIterator2>::value_type, 5483 typename iterator_traits<_InputIterator1>::value_type>) 5484 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp); 5485 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp); 5486 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp); 5487 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp); 5488 5489 return _GLIBCXX_STD_A::__set_difference(__first1, __last1, 5490 __first2, __last2, __result, 5491 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 5492 } 5493 5494 template<typename _InputIterator1, typename _InputIterator2, 5495 typename _OutputIterator, 5496 typename _Compare> 5497 _GLIBCXX20_CONSTEXPR 5498 _OutputIterator 5499 __set_symmetric_difference(_InputIterator1 __first1, 5500 _InputIterator1 __last1, 5501 _InputIterator2 __first2, 5502 _InputIterator2 __last2, 5503 _OutputIterator __result, 5504 _Compare __comp) 5505 { 5506 while (__first1 != __last1 && __first2 != __last2) 5507 if (__comp(__first1, __first2)) 5508 { 5509 *__result = *__first1; 5510 ++__first1; 5511 ++__result; 5512 } 5513 else if (__comp(__first2, __first1)) 5514 { 5515 *__result = *__first2; 5516 ++__first2; 5517 ++__result; 5518 } 5519 else 5520 { 5521 ++__first1; 5522 ++__first2; 5523 } 5524 return std::copy(__first2, __last2, 5525 std::copy(__first1, __last1, __result)); 5526 } 5527 5528 /** 5529 * @brief Return the symmetric difference of two sorted ranges. 5530 * @ingroup set_algorithms 5531 * @param __first1 Start of first range. 5532 * @param __last1 End of first range. 5533 * @param __first2 Start of second range. 5534 * @param __last2 End of second range. 5535 * @param __result Start of output range. 5536 * @return End of the output range. 5537 * @ingroup set_algorithms 5538 * 5539 * This operation iterates over both ranges, copying elements present in 5540 * one range but not the other in order to the output range. Iterators 5541 * increment for each range. When the current element of one range is less 5542 * than the other, that element is copied and the iterator advances. If an 5543 * element is contained in both ranges, no elements are copied and both 5544 * ranges advance. The output range may not overlap either input range. 5545 */ 5546 template<typename _InputIterator1, typename _InputIterator2, 5547 typename _OutputIterator> 5548 _GLIBCXX20_CONSTEXPR 5549 inline _OutputIterator 5550 set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1, 5551 _InputIterator2 __first2, _InputIterator2 __last2, 5552 _OutputIterator __result) 5553 { 5554 // concept requirements 5555 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 5556 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 5557 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 5558 typename iterator_traits<_InputIterator1>::value_type>) 5559 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 5560 typename iterator_traits<_InputIterator2>::value_type>) 5561 __glibcxx_function_requires(_LessThanOpConcept< 5562 typename iterator_traits<_InputIterator1>::value_type, 5563 typename iterator_traits<_InputIterator2>::value_type>) 5564 __glibcxx_function_requires(_LessThanOpConcept< 5565 typename iterator_traits<_InputIterator2>::value_type, 5566 typename iterator_traits<_InputIterator1>::value_type>) 5567 __glibcxx_requires_sorted_set(__first1, __last1, __first2); 5568 __glibcxx_requires_sorted_set(__first2, __last2, __first1); 5569 __glibcxx_requires_irreflexive2(__first1, __last1); 5570 __glibcxx_requires_irreflexive2(__first2, __last2); 5571 5572 return _GLIBCXX_STD_A::__set_symmetric_difference(__first1, __last1, 5573 __first2, __last2, __result, 5574 __gnu_cxx::__ops::__iter_less_iter()); 5575 } 5576 5577 /** 5578 * @brief Return the symmetric difference of two sorted ranges using 5579 * comparison functor. 5580 * @ingroup set_algorithms 5581 * @param __first1 Start of first range. 5582 * @param __last1 End of first range. 5583 * @param __first2 Start of second range. 5584 * @param __last2 End of second range. 5585 * @param __result Start of output range. 5586 * @param __comp The comparison functor. 5587 * @return End of the output range. 5588 * @ingroup set_algorithms 5589 * 5590 * This operation iterates over both ranges, copying elements present in 5591 * one range but not the other in order to the output range. Iterators 5592 * increment for each range. When the current element of one range is less 5593 * than the other according to @p comp, that element is copied and the 5594 * iterator advances. If an element is contained in both ranges according 5595 * to @p __comp, no elements are copied and both ranges advance. The output 5596 * range may not overlap either input range. 5597 */ 5598 template<typename _InputIterator1, typename _InputIterator2, 5599 typename _OutputIterator, typename _Compare> 5600 _GLIBCXX20_CONSTEXPR 5601 inline _OutputIterator 5602 set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1, 5603 _InputIterator2 __first2, _InputIterator2 __last2, 5604 _OutputIterator __result, 5605 _Compare __comp) 5606 { 5607 // concept requirements 5608 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 5609 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 5610 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 5611 typename iterator_traits<_InputIterator1>::value_type>) 5612 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 5613 typename iterator_traits<_InputIterator2>::value_type>) 5614 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 5615 typename iterator_traits<_InputIterator1>::value_type, 5616 typename iterator_traits<_InputIterator2>::value_type>) 5617 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 5618 typename iterator_traits<_InputIterator2>::value_type, 5619 typename iterator_traits<_InputIterator1>::value_type>) 5620 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp); 5621 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp); 5622 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp); 5623 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp); 5624 5625 return _GLIBCXX_STD_A::__set_symmetric_difference(__first1, __last1, 5626 __first2, __last2, __result, 5627 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 5628 } 5629 5630 template<typename _ForwardIterator, typename _Compare> 5631 _GLIBCXX14_CONSTEXPR 5632 _ForwardIterator 5633 __min_element(_ForwardIterator __first, _ForwardIterator __last, 5634 _Compare __comp) 5635 { 5636 if (__first == __last) 5637 return __first; 5638 _ForwardIterator __result = __first; 5639 while (++__first != __last) 5640 if (__comp(__first, __result)) 5641 __result = __first; 5642 return __result; 5643 } 5644 5645 /** 5646 * @brief Return the minimum element in a range. 5647 * @ingroup sorting_algorithms 5648 * @param __first Start of range. 5649 * @param __last End of range. 5650 * @return Iterator referencing the first instance of the smallest value. 5651 */ 5652 template<typename _ForwardIterator> 5653 _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR 5654 _ForwardIterator 5655 inline min_element(_ForwardIterator __first, _ForwardIterator __last) 5656 { 5657 // concept requirements 5658 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 5659 __glibcxx_function_requires(_LessThanComparableConcept< 5660 typename iterator_traits<_ForwardIterator>::value_type>) 5661 __glibcxx_requires_valid_range(__first, __last); 5662 __glibcxx_requires_irreflexive(__first, __last); 5663 5664 return _GLIBCXX_STD_A::__min_element(__first, __last, 5665 __gnu_cxx::__ops::__iter_less_iter()); 5666 } 5667 5668 /** 5669 * @brief Return the minimum element in a range using comparison functor. 5670 * @ingroup sorting_algorithms 5671 * @param __first Start of range. 5672 * @param __last End of range. 5673 * @param __comp Comparison functor. 5674 * @return Iterator referencing the first instance of the smallest value 5675 * according to __comp. 5676 */ 5677 template<typename _ForwardIterator, typename _Compare> 5678 _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR 5679 inline _ForwardIterator 5680 min_element(_ForwardIterator __first, _ForwardIterator __last, 5681 _Compare __comp) 5682 { 5683 // concept requirements 5684 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 5685 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 5686 typename iterator_traits<_ForwardIterator>::value_type, 5687 typename iterator_traits<_ForwardIterator>::value_type>) 5688 __glibcxx_requires_valid_range(__first, __last); 5689 __glibcxx_requires_irreflexive_pred(__first, __last, __comp); 5690 5691 return _GLIBCXX_STD_A::__min_element(__first, __last, 5692 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 5693 } 5694 5695 template<typename _ForwardIterator, typename _Compare> 5696 _GLIBCXX14_CONSTEXPR 5697 _ForwardIterator 5698 __max_element(_ForwardIterator __first, _ForwardIterator __last, 5699 _Compare __comp) 5700 { 5701 if (__first == __last) return __first; 5702 _ForwardIterator __result = __first; 5703 while (++__first != __last) 5704 if (__comp(__result, __first)) 5705 __result = __first; 5706 return __result; 5707 } 5708 5709 /** 5710 * @brief Return the maximum element in a range. 5711 * @ingroup sorting_algorithms 5712 * @param __first Start of range. 5713 * @param __last End of range. 5714 * @return Iterator referencing the first instance of the largest value. 5715 */ 5716 template<typename _ForwardIterator> 5717 _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR 5718 inline _ForwardIterator 5719 max_element(_ForwardIterator __first, _ForwardIterator __last) 5720 { 5721 // concept requirements 5722 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 5723 __glibcxx_function_requires(_LessThanComparableConcept< 5724 typename iterator_traits<_ForwardIterator>::value_type>) 5725 __glibcxx_requires_valid_range(__first, __last); 5726 __glibcxx_requires_irreflexive(__first, __last); 5727 5728 return _GLIBCXX_STD_A::__max_element(__first, __last, 5729 __gnu_cxx::__ops::__iter_less_iter()); 5730 } 5731 5732 /** 5733 * @brief Return the maximum element in a range using comparison functor. 5734 * @ingroup sorting_algorithms 5735 * @param __first Start of range. 5736 * @param __last End of range. 5737 * @param __comp Comparison functor. 5738 * @return Iterator referencing the first instance of the largest value 5739 * according to __comp. 5740 */ 5741 template<typename _ForwardIterator, typename _Compare> 5742 _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR 5743 inline _ForwardIterator 5744 max_element(_ForwardIterator __first, _ForwardIterator __last, 5745 _Compare __comp) 5746 { 5747 // concept requirements 5748 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 5749 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 5750 typename iterator_traits<_ForwardIterator>::value_type, 5751 typename iterator_traits<_ForwardIterator>::value_type>) 5752 __glibcxx_requires_valid_range(__first, __last); 5753 __glibcxx_requires_irreflexive_pred(__first, __last, __comp); 5754 5755 return _GLIBCXX_STD_A::__max_element(__first, __last, 5756 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 5757 } 5758 5759 #if __cplusplus >= 201103L 5760 // N2722 + DR 915. 5761 template<typename _Tp> 5762 _GLIBCXX14_CONSTEXPR 5763 inline _Tp 5764 min(initializer_list<_Tp> __l) 5765 { 5766 __glibcxx_requires_irreflexive(__l.begin(), __l.end()); 5767 return *_GLIBCXX_STD_A::__min_element(__l.begin(), __l.end(), 5768 __gnu_cxx::__ops::__iter_less_iter()); 5769 } 5770 5771 template<typename _Tp, typename _Compare> 5772 _GLIBCXX14_CONSTEXPR 5773 inline _Tp 5774 min(initializer_list<_Tp> __l, _Compare __comp) 5775 { 5776 __glibcxx_requires_irreflexive_pred(__l.begin(), __l.end(), __comp); 5777 return *_GLIBCXX_STD_A::__min_element(__l.begin(), __l.end(), 5778 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 5779 } 5780 5781 template<typename _Tp> 5782 _GLIBCXX14_CONSTEXPR 5783 inline _Tp 5784 max(initializer_list<_Tp> __l) 5785 { 5786 __glibcxx_requires_irreflexive(__l.begin(), __l.end()); 5787 return *_GLIBCXX_STD_A::__max_element(__l.begin(), __l.end(), 5788 __gnu_cxx::__ops::__iter_less_iter()); 5789 } 5790 5791 template<typename _Tp, typename _Compare> 5792 _GLIBCXX14_CONSTEXPR 5793 inline _Tp 5794 max(initializer_list<_Tp> __l, _Compare __comp) 5795 { 5796 __glibcxx_requires_irreflexive_pred(__l.begin(), __l.end(), __comp); 5797 return *_GLIBCXX_STD_A::__max_element(__l.begin(), __l.end(), 5798 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 5799 } 5800 #endif // C++11 5801 5802 #if __cplusplus >= 201402L 5803 /// Reservoir sampling algorithm. 5804 template<typename _InputIterator, typename _RandomAccessIterator, 5805 typename _Size, typename _UniformRandomBitGenerator> 5806 _RandomAccessIterator 5807 __sample(_InputIterator __first, _InputIterator __last, input_iterator_tag, 5808 _RandomAccessIterator __out, random_access_iterator_tag, 5809 _Size __n, _UniformRandomBitGenerator&& __g) 5810 { 5811 using __distrib_type = uniform_int_distribution<_Size>; 5812 using __param_type = typename __distrib_type::param_type; 5813 __distrib_type __d{}; 5814 _Size __sample_sz = 0; 5815 while (__first != __last && __sample_sz != __n) 5816 { 5817 __out[__sample_sz++] = *__first; 5818 ++__first; 5819 } 5820 for (auto __pop_sz = __sample_sz; __first != __last; 5821 ++__first, (void) ++__pop_sz) 5822 { 5823 const auto __k = __d(__g, __param_type{0, __pop_sz}); 5824 if (__k < __n) 5825 __out[__k] = *__first; 5826 } 5827 return __out + __sample_sz; 5828 } 5829 5830 /// Selection sampling algorithm. 5831 template<typename _ForwardIterator, typename _OutputIterator, typename _Cat, 5832 typename _Size, typename _UniformRandomBitGenerator> 5833 _OutputIterator 5834 __sample(_ForwardIterator __first, _ForwardIterator __last, 5835 forward_iterator_tag, 5836 _OutputIterator __out, _Cat, 5837 _Size __n, _UniformRandomBitGenerator&& __g) 5838 { 5839 using __distrib_type = uniform_int_distribution<_Size>; 5840 using __param_type = typename __distrib_type::param_type; 5841 using _USize = make_unsigned_t<_Size>; 5842 using _Gen = remove_reference_t<_UniformRandomBitGenerator>; 5843 using __uc_type = common_type_t<typename _Gen::result_type, _USize>; 5844 5845 if (__first == __last) 5846 return __out; 5847 5848 __distrib_type __d{}; 5849 _Size __unsampled_sz = std::distance(__first, __last); 5850 __n = std::min(__n, __unsampled_sz); 5851 5852 // If possible, we use __gen_two_uniform_ints to efficiently produce 5853 // two random numbers using a single distribution invocation: 5854 5855 const __uc_type __urngrange = __g.max() - __g.min(); 5856 if (__urngrange / __uc_type(__unsampled_sz) >= __uc_type(__unsampled_sz)) 5857 // I.e. (__urngrange >= __unsampled_sz * __unsampled_sz) but without 5858 // wrapping issues. 5859 { 5860 while (__n != 0 && __unsampled_sz >= 2) 5861 { 5862 const pair<_Size, _Size> __p = 5863 __gen_two_uniform_ints(__unsampled_sz, __unsampled_sz - 1, __g); 5864 5865 --__unsampled_sz; 5866 if (__p.first < __n) 5867 { 5868 *__out++ = *__first; 5869 --__n; 5870 } 5871 5872 ++__first; 5873 5874 if (__n == 0) break; 5875 5876 --__unsampled_sz; 5877 if (__p.second < __n) 5878 { 5879 *__out++ = *__first; 5880 --__n; 5881 } 5882 5883 ++__first; 5884 } 5885 } 5886 5887 // The loop above is otherwise equivalent to this one-at-a-time version: 5888 5889 for (; __n != 0; ++__first) 5890 if (__d(__g, __param_type{0, --__unsampled_sz}) < __n) 5891 { 5892 *__out++ = *__first; 5893 --__n; 5894 } 5895 return __out; 5896 } 5897 #endif // C++14 5898 5899 #ifdef __glibcxx_sample // C++ >= 17 5900 /// Take a random sample from a population. 5901 template<typename _PopulationIterator, typename _SampleIterator, 5902 typename _Distance, typename _UniformRandomBitGenerator> 5903 _SampleIterator 5904 sample(_PopulationIterator __first, _PopulationIterator __last, 5905 _SampleIterator __out, _Distance __n, 5906 _UniformRandomBitGenerator&& __g) 5907 { 5908 using __pop_cat = typename 5909 std::iterator_traits<_PopulationIterator>::iterator_category; 5910 using __samp_cat = typename 5911 std::iterator_traits<_SampleIterator>::iterator_category; 5912 5913 static_assert( 5914 __or_<is_convertible<__pop_cat, forward_iterator_tag>, 5915 is_convertible<__samp_cat, random_access_iterator_tag>>::value, 5916 "output range must use a RandomAccessIterator when input range" 5917 " does not meet the ForwardIterator requirements"); 5918 5919 static_assert(is_integral<_Distance>::value, 5920 "sample size must be an integer type"); 5921 5922 typename iterator_traits<_PopulationIterator>::difference_type __d = __n; 5923 return _GLIBCXX_STD_A:: 5924 __sample(__first, __last, __pop_cat{}, __out, __samp_cat{}, __d, 5925 std::forward<_UniformRandomBitGenerator>(__g)); 5926 } 5927 #endif // __glibcxx_sample 5928 5929 _GLIBCXX_END_NAMESPACE_ALGO 5930 _GLIBCXX_END_NAMESPACE_VERSION 5931 } // namespace std 5932 5933 #pragma GCC diagnostic pop 5934 5935 #endif /* _STL_ALGO_H */
