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