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