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