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