1 // Algorithm implementation -*- C++ -*- 2 3 // Copyright (C) 2001-2017 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, ++__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 std::rotate(__left_split, __middle, __right_split); 1605 std::advance(__left_split, std::distance(__middle, __right_split)); 1606 return __left_split; 1607 } 1608 1609 template<typename _ForwardIterator, typename _Predicate> 1610 _ForwardIterator 1611 __stable_partition(_ForwardIterator __first, _ForwardIterator __last, 1612 _Predicate __pred) 1613 { 1614 __first = std::__find_if_not(__first, __last, __pred); 1615 1616 if (__first == __last) 1617 return __first; 1618 1619 typedef typename iterator_traits<_ForwardIterator>::value_type 1620 _ValueType; 1621 typedef typename iterator_traits<_ForwardIterator>::difference_type 1622 _DistanceType; 1623 1624 _Temporary_buffer<_ForwardIterator, _ValueType> __buf(__first, __last); 1625 return 1626 std::__stable_partition_adaptive(__first, __last, __pred, 1627 _DistanceType(__buf.requested_size()), 1628 __buf.begin(), 1629 _DistanceType(__buf.size())); 1630 } 1631 1632 /** 1633 * @brief Move elements for which a predicate is true to the beginning 1634 * of a sequence, preserving relative ordering. 1635 * @ingroup mutating_algorithms 1636 * @param __first A forward iterator. 1637 * @param __last A forward iterator. 1638 * @param __pred A predicate functor. 1639 * @return An iterator @p middle such that @p __pred(i) is true for each 1640 * iterator @p i in the range @p [first,middle) and false for each @p i 1641 * in the range @p [middle,last). 1642 * 1643 * Performs the same function as @p partition() with the additional 1644 * guarantee that the relative ordering of elements in each group is 1645 * preserved, so any two elements @p x and @p y in the range 1646 * @p [__first,__last) such that @p __pred(x)==__pred(y) will have the same 1647 * relative ordering after calling @p stable_partition(). 1648 */ 1649 template<typename _ForwardIterator, typename _Predicate> 1650 inline _ForwardIterator 1651 stable_partition(_ForwardIterator __first, _ForwardIterator __last, 1652 _Predicate __pred) 1653 { 1654 // concept requirements 1655 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 1656 _ForwardIterator>) 1657 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 1658 typename iterator_traits<_ForwardIterator>::value_type>) 1659 __glibcxx_requires_valid_range(__first, __last); 1660 1661 return std::__stable_partition(__first, __last, 1662 __gnu_cxx::__ops::__pred_iter(__pred)); 1663 } 1664 1665 /// This is a helper function for the sort routines. 1666 template<typename _RandomAccessIterator, typename _Compare> 1667 void 1668 __heap_select(_RandomAccessIterator __first, 1669 _RandomAccessIterator __middle, 1670 _RandomAccessIterator __last, _Compare __comp) 1671 { 1672 std::__make_heap(__first, __middle, __comp); 1673 for (_RandomAccessIterator __i = __middle; __i < __last; ++__i) 1674 if (__comp(__i, __first)) 1675 std::__pop_heap(__first, __middle, __i, __comp); 1676 } 1677 1678 // partial_sort 1679 1680 template<typename _InputIterator, typename _RandomAccessIterator, 1681 typename _Compare> 1682 _RandomAccessIterator 1683 __partial_sort_copy(_InputIterator __first, _InputIterator __last, 1684 _RandomAccessIterator __result_first, 1685 _RandomAccessIterator __result_last, 1686 _Compare __comp) 1687 { 1688 typedef typename iterator_traits<_InputIterator>::value_type 1689 _InputValueType; 1690 typedef iterator_traits<_RandomAccessIterator> _RItTraits; 1691 typedef typename _RItTraits::difference_type _DistanceType; 1692 1693 if (__result_first == __result_last) 1694 return __result_last; 1695 _RandomAccessIterator __result_real_last = __result_first; 1696 while (__first != __last && __result_real_last != __result_last) 1697 { 1698 *__result_real_last = *__first; 1699 ++__result_real_last; 1700 ++__first; 1701 } 1702 1703 std::__make_heap(__result_first, __result_real_last, __comp); 1704 while (__first != __last) 1705 { 1706 if (__comp(__first, __result_first)) 1707 std::__adjust_heap(__result_first, _DistanceType(0), 1708 _DistanceType(__result_real_last 1709 - __result_first), 1710 _InputValueType(*__first), __comp); 1711 ++__first; 1712 } 1713 std::__sort_heap(__result_first, __result_real_last, __comp); 1714 return __result_real_last; 1715 } 1716 1717 /** 1718 * @brief Copy the smallest elements of a sequence. 1719 * @ingroup sorting_algorithms 1720 * @param __first An iterator. 1721 * @param __last Another iterator. 1722 * @param __result_first A random-access iterator. 1723 * @param __result_last Another random-access iterator. 1724 * @return An iterator indicating the end of the resulting sequence. 1725 * 1726 * Copies and sorts the smallest N values from the range @p [__first,__last) 1727 * to the range beginning at @p __result_first, where the number of 1728 * elements to be copied, @p N, is the smaller of @p (__last-__first) and 1729 * @p (__result_last-__result_first). 1730 * After the sort if @e i and @e j are iterators in the range 1731 * @p [__result_first,__result_first+N) such that i precedes j then 1732 * *j<*i is false. 1733 * The value returned is @p __result_first+N. 1734 */ 1735 template<typename _InputIterator, typename _RandomAccessIterator> 1736 inline _RandomAccessIterator 1737 partial_sort_copy(_InputIterator __first, _InputIterator __last, 1738 _RandomAccessIterator __result_first, 1739 _RandomAccessIterator __result_last) 1740 { 1741 #ifdef _GLIBCXX_CONCEPT_CHECKS 1742 typedef typename iterator_traits<_InputIterator>::value_type 1743 _InputValueType __attribute__((__unused__)); 1744 typedef typename iterator_traits<_RandomAccessIterator>::value_type 1745 _OutputValueType __attribute__((__unused__)); 1746 #endif 1747 1748 // concept requirements 1749 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 1750 __glibcxx_function_requires(_ConvertibleConcept<_InputValueType, 1751 _OutputValueType>) 1752 __glibcxx_function_requires(_LessThanOpConcept<_InputValueType, 1753 _OutputValueType>) 1754 __glibcxx_function_requires(_LessThanComparableConcept<_OutputValueType>) 1755 __glibcxx_requires_valid_range(__first, __last); 1756 __glibcxx_requires_irreflexive(__first, __last); 1757 __glibcxx_requires_valid_range(__result_first, __result_last); 1758 1759 return std::__partial_sort_copy(__first, __last, 1760 __result_first, __result_last, 1761 __gnu_cxx::__ops::__iter_less_iter()); 1762 } 1763 1764 /** 1765 * @brief Copy the smallest elements of a sequence using a predicate for 1766 * comparison. 1767 * @ingroup sorting_algorithms 1768 * @param __first An input iterator. 1769 * @param __last Another input iterator. 1770 * @param __result_first A random-access iterator. 1771 * @param __result_last Another random-access iterator. 1772 * @param __comp A comparison functor. 1773 * @return An iterator indicating the end of the resulting sequence. 1774 * 1775 * Copies and sorts the smallest N values from the range @p [__first,__last) 1776 * to the range beginning at @p result_first, where the number of 1777 * elements to be copied, @p N, is the smaller of @p (__last-__first) and 1778 * @p (__result_last-__result_first). 1779 * After the sort if @e i and @e j are iterators in the range 1780 * @p [__result_first,__result_first+N) such that i precedes j then 1781 * @p __comp(*j,*i) is false. 1782 * The value returned is @p __result_first+N. 1783 */ 1784 template<typename _InputIterator, typename _RandomAccessIterator, 1785 typename _Compare> 1786 inline _RandomAccessIterator 1787 partial_sort_copy(_InputIterator __first, _InputIterator __last, 1788 _RandomAccessIterator __result_first, 1789 _RandomAccessIterator __result_last, 1790 _Compare __comp) 1791 { 1792 #ifdef _GLIBCXX_CONCEPT_CHECKS 1793 typedef typename iterator_traits<_InputIterator>::value_type 1794 _InputValueType __attribute__((__unused__)); 1795 typedef typename iterator_traits<_RandomAccessIterator>::value_type 1796 _OutputValueType __attribute__((__unused__)); 1797 #endif 1798 1799 // concept requirements 1800 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 1801 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 1802 _RandomAccessIterator>) 1803 __glibcxx_function_requires(_ConvertibleConcept<_InputValueType, 1804 _OutputValueType>) 1805 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 1806 _InputValueType, _OutputValueType>) 1807 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 1808 _OutputValueType, _OutputValueType>) 1809 __glibcxx_requires_valid_range(__first, __last); 1810 __glibcxx_requires_irreflexive_pred(__first, __last, __comp); 1811 __glibcxx_requires_valid_range(__result_first, __result_last); 1812 1813 return std::__partial_sort_copy(__first, __last, 1814 __result_first, __result_last, 1815 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 1816 } 1817 1818 /// This is a helper function for the sort routine. 1819 template<typename _RandomAccessIterator, typename _Compare> 1820 void 1821 __unguarded_linear_insert(_RandomAccessIterator __last, 1822 _Compare __comp) 1823 { 1824 typename iterator_traits<_RandomAccessIterator>::value_type 1825 __val = _GLIBCXX_MOVE(*__last); 1826 _RandomAccessIterator __next = __last; 1827 --__next; 1828 while (__comp(__val, __next)) 1829 { 1830 *__last = _GLIBCXX_MOVE(*__next); 1831 __last = __next; 1832 --__next; 1833 } 1834 *__last = _GLIBCXX_MOVE(__val); 1835 } 1836 1837 /// This is a helper function for the sort routine. 1838 template<typename _RandomAccessIterator, typename _Compare> 1839 void 1840 __insertion_sort(_RandomAccessIterator __first, 1841 _RandomAccessIterator __last, _Compare __comp) 1842 { 1843 if (__first == __last) return; 1844 1845 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i) 1846 { 1847 if (__comp(__i, __first)) 1848 { 1849 typename iterator_traits<_RandomAccessIterator>::value_type 1850 __val = _GLIBCXX_MOVE(*__i); 1851 _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1); 1852 *__first = _GLIBCXX_MOVE(__val); 1853 } 1854 else 1855 std::__unguarded_linear_insert(__i, 1856 __gnu_cxx::__ops::__val_comp_iter(__comp)); 1857 } 1858 } 1859 1860 /// This is a helper function for the sort routine. 1861 template<typename _RandomAccessIterator, typename _Compare> 1862 inline void 1863 __unguarded_insertion_sort(_RandomAccessIterator __first, 1864 _RandomAccessIterator __last, _Compare __comp) 1865 { 1866 for (_RandomAccessIterator __i = __first; __i != __last; ++__i) 1867 std::__unguarded_linear_insert(__i, 1868 __gnu_cxx::__ops::__val_comp_iter(__comp)); 1869 } 1870 1871 /** 1872 * @doctodo 1873 * This controls some aspect of the sort routines. 1874 */ 1875 enum { _S_threshold = 16 }; 1876 1877 /// This is a helper function for the sort routine. 1878 template<typename _RandomAccessIterator, typename _Compare> 1879 void 1880 __final_insertion_sort(_RandomAccessIterator __first, 1881 _RandomAccessIterator __last, _Compare __comp) 1882 { 1883 if (__last - __first > int(_S_threshold)) 1884 { 1885 std::__insertion_sort(__first, __first + int(_S_threshold), __comp); 1886 std::__unguarded_insertion_sort(__first + int(_S_threshold), __last, 1887 __comp); 1888 } 1889 else 1890 std::__insertion_sort(__first, __last, __comp); 1891 } 1892 1893 /// This is a helper function... 1894 template<typename _RandomAccessIterator, typename _Compare> 1895 _RandomAccessIterator 1896 __unguarded_partition(_RandomAccessIterator __first, 1897 _RandomAccessIterator __last, 1898 _RandomAccessIterator __pivot, _Compare __comp) 1899 { 1900 while (true) 1901 { 1902 while (__comp(__first, __pivot)) 1903 ++__first; 1904 --__last; 1905 while (__comp(__pivot, __last)) 1906 --__last; 1907 if (!(__first < __last)) 1908 return __first; 1909 std::iter_swap(__first, __last); 1910 ++__first; 1911 } 1912 } 1913 1914 /// This is a helper function... 1915 template<typename _RandomAccessIterator, typename _Compare> 1916 inline _RandomAccessIterator 1917 __unguarded_partition_pivot(_RandomAccessIterator __first, 1918 _RandomAccessIterator __last, _Compare __comp) 1919 { 1920 _RandomAccessIterator __mid = __first + (__last - __first) / 2; 1921 std::__move_median_to_first(__first, __first + 1, __mid, __last - 1, 1922 __comp); 1923 return std::__unguarded_partition(__first + 1, __last, __first, __comp); 1924 } 1925 1926 template<typename _RandomAccessIterator, typename _Compare> 1927 inline void 1928 __partial_sort(_RandomAccessIterator __first, 1929 _RandomAccessIterator __middle, 1930 _RandomAccessIterator __last, 1931 _Compare __comp) 1932 { 1933 std::__heap_select(__first, __middle, __last, __comp); 1934 std::__sort_heap(__first, __middle, __comp); 1935 } 1936 1937 /// This is a helper function for the sort routine. 1938 template<typename _RandomAccessIterator, typename _Size, typename _Compare> 1939 void 1940 __introsort_loop(_RandomAccessIterator __first, 1941 _RandomAccessIterator __last, 1942 _Size __depth_limit, _Compare __comp) 1943 { 1944 while (__last - __first > int(_S_threshold)) 1945 { 1946 if (__depth_limit == 0) 1947 { 1948 std::__partial_sort(__first, __last, __last, __comp); 1949 return; 1950 } 1951 --__depth_limit; 1952 _RandomAccessIterator __cut = 1953 std::__unguarded_partition_pivot(__first, __last, __comp); 1954 std::__introsort_loop(__cut, __last, __depth_limit, __comp); 1955 __last = __cut; 1956 } 1957 } 1958 1959 // sort 1960 1961 template<typename _RandomAccessIterator, typename _Compare> 1962 inline void 1963 __sort(_RandomAccessIterator __first, _RandomAccessIterator __last, 1964 _Compare __comp) 1965 { 1966 if (__first != __last) 1967 { 1968 std::__introsort_loop(__first, __last, 1969 std::__lg(__last - __first) * 2, 1970 __comp); 1971 std::__final_insertion_sort(__first, __last, __comp); 1972 } 1973 } 1974 1975 template<typename _RandomAccessIterator, typename _Size, typename _Compare> 1976 void 1977 __introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth, 1978 _RandomAccessIterator __last, _Size __depth_limit, 1979 _Compare __comp) 1980 { 1981 while (__last - __first > 3) 1982 { 1983 if (__depth_limit == 0) 1984 { 1985 std::__heap_select(__first, __nth + 1, __last, __comp); 1986 // Place the nth largest element in its final position. 1987 std::iter_swap(__first, __nth); 1988 return; 1989 } 1990 --__depth_limit; 1991 _RandomAccessIterator __cut = 1992 std::__unguarded_partition_pivot(__first, __last, __comp); 1993 if (__cut <= __nth) 1994 __first = __cut; 1995 else 1996 __last = __cut; 1997 } 1998 std::__insertion_sort(__first, __last, __comp); 1999 } 2000 2001 // nth_element 2002 2003 // lower_bound moved to stl_algobase.h 2004 2005 /** 2006 * @brief Finds the first position in which @p __val could be inserted 2007 * without changing the ordering. 2008 * @ingroup binary_search_algorithms 2009 * @param __first An iterator. 2010 * @param __last Another iterator. 2011 * @param __val The search term. 2012 * @param __comp A functor to use for comparisons. 2013 * @return An iterator pointing to the first element <em>not less 2014 * than</em> @p __val, or end() if every element is less 2015 * than @p __val. 2016 * @ingroup binary_search_algorithms 2017 * 2018 * The comparison function should have the same effects on ordering as 2019 * the function used for the initial sort. 2020 */ 2021 template<typename _ForwardIterator, typename _Tp, typename _Compare> 2022 inline _ForwardIterator 2023 lower_bound(_ForwardIterator __first, _ForwardIterator __last, 2024 const _Tp& __val, _Compare __comp) 2025 { 2026 // concept requirements 2027 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 2028 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 2029 typename iterator_traits<_ForwardIterator>::value_type, _Tp>) 2030 __glibcxx_requires_partitioned_lower_pred(__first, __last, 2031 __val, __comp); 2032 2033 return std::__lower_bound(__first, __last, __val, 2034 __gnu_cxx::__ops::__iter_comp_val(__comp)); 2035 } 2036 2037 template<typename _ForwardIterator, typename _Tp, typename _Compare> 2038 _ForwardIterator 2039 __upper_bound(_ForwardIterator __first, _ForwardIterator __last, 2040 const _Tp& __val, _Compare __comp) 2041 { 2042 typedef typename iterator_traits<_ForwardIterator>::difference_type 2043 _DistanceType; 2044 2045 _DistanceType __len = std::distance(__first, __last); 2046 2047 while (__len > 0) 2048 { 2049 _DistanceType __half = __len >> 1; 2050 _ForwardIterator __middle = __first; 2051 std::advance(__middle, __half); 2052 if (__comp(__val, __middle)) 2053 __len = __half; 2054 else 2055 { 2056 __first = __middle; 2057 ++__first; 2058 __len = __len - __half - 1; 2059 } 2060 } 2061 return __first; 2062 } 2063 2064 /** 2065 * @brief Finds the last position in which @p __val could be inserted 2066 * without changing the ordering. 2067 * @ingroup binary_search_algorithms 2068 * @param __first An iterator. 2069 * @param __last Another iterator. 2070 * @param __val The search term. 2071 * @return An iterator pointing to the first element greater than @p __val, 2072 * or end() if no elements are greater than @p __val. 2073 * @ingroup binary_search_algorithms 2074 */ 2075 template<typename _ForwardIterator, typename _Tp> 2076 inline _ForwardIterator 2077 upper_bound(_ForwardIterator __first, _ForwardIterator __last, 2078 const _Tp& __val) 2079 { 2080 // concept requirements 2081 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 2082 __glibcxx_function_requires(_LessThanOpConcept< 2083 _Tp, typename iterator_traits<_ForwardIterator>::value_type>) 2084 __glibcxx_requires_partitioned_upper(__first, __last, __val); 2085 2086 return std::__upper_bound(__first, __last, __val, 2087 __gnu_cxx::__ops::__val_less_iter()); 2088 } 2089 2090 /** 2091 * @brief Finds the last position in which @p __val could be inserted 2092 * without changing the ordering. 2093 * @ingroup binary_search_algorithms 2094 * @param __first An iterator. 2095 * @param __last Another iterator. 2096 * @param __val The search term. 2097 * @param __comp A functor to use for comparisons. 2098 * @return An iterator pointing to the first element greater than @p __val, 2099 * or end() if no elements are greater than @p __val. 2100 * @ingroup binary_search_algorithms 2101 * 2102 * The comparison function should have the same effects on ordering as 2103 * the function used for the initial sort. 2104 */ 2105 template<typename _ForwardIterator, typename _Tp, typename _Compare> 2106 inline _ForwardIterator 2107 upper_bound(_ForwardIterator __first, _ForwardIterator __last, 2108 const _Tp& __val, _Compare __comp) 2109 { 2110 // concept requirements 2111 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 2112 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 2113 _Tp, typename iterator_traits<_ForwardIterator>::value_type>) 2114 __glibcxx_requires_partitioned_upper_pred(__first, __last, 2115 __val, __comp); 2116 2117 return std::__upper_bound(__first, __last, __val, 2118 __gnu_cxx::__ops::__val_comp_iter(__comp)); 2119 } 2120 2121 template<typename _ForwardIterator, typename _Tp, 2122 typename _CompareItTp, typename _CompareTpIt> 2123 pair<_ForwardIterator, _ForwardIterator> 2124 __equal_range(_ForwardIterator __first, _ForwardIterator __last, 2125 const _Tp& __val, 2126 _CompareItTp __comp_it_val, _CompareTpIt __comp_val_it) 2127 { 2128 typedef typename iterator_traits<_ForwardIterator>::difference_type 2129 _DistanceType; 2130 2131 _DistanceType __len = std::distance(__first, __last); 2132 2133 while (__len > 0) 2134 { 2135 _DistanceType __half = __len >> 1; 2136 _ForwardIterator __middle = __first; 2137 std::advance(__middle, __half); 2138 if (__comp_it_val(__middle, __val)) 2139 { 2140 __first = __middle; 2141 ++__first; 2142 __len = __len - __half - 1; 2143 } 2144 else if (__comp_val_it(__val, __middle)) 2145 __len = __half; 2146 else 2147 { 2148 _ForwardIterator __left 2149 = std::__lower_bound(__first, __middle, __val, __comp_it_val); 2150 std::advance(__first, __len); 2151 _ForwardIterator __right 2152 = std::__upper_bound(++__middle, __first, __val, __comp_val_it); 2153 return pair<_ForwardIterator, _ForwardIterator>(__left, __right); 2154 } 2155 } 2156 return pair<_ForwardIterator, _ForwardIterator>(__first, __first); 2157 } 2158 2159 /** 2160 * @brief Finds the largest subrange in which @p __val could be inserted 2161 * at any place in it without changing the ordering. 2162 * @ingroup binary_search_algorithms 2163 * @param __first An iterator. 2164 * @param __last Another iterator. 2165 * @param __val The search term. 2166 * @return An pair of iterators defining the subrange. 2167 * @ingroup binary_search_algorithms 2168 * 2169 * This is equivalent to 2170 * @code 2171 * std::make_pair(lower_bound(__first, __last, __val), 2172 * upper_bound(__first, __last, __val)) 2173 * @endcode 2174 * but does not actually call those functions. 2175 */ 2176 template<typename _ForwardIterator, typename _Tp> 2177 inline pair<_ForwardIterator, _ForwardIterator> 2178 equal_range(_ForwardIterator __first, _ForwardIterator __last, 2179 const _Tp& __val) 2180 { 2181 // concept requirements 2182 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 2183 __glibcxx_function_requires(_LessThanOpConcept< 2184 typename iterator_traits<_ForwardIterator>::value_type, _Tp>) 2185 __glibcxx_function_requires(_LessThanOpConcept< 2186 _Tp, typename iterator_traits<_ForwardIterator>::value_type>) 2187 __glibcxx_requires_partitioned_lower(__first, __last, __val); 2188 __glibcxx_requires_partitioned_upper(__first, __last, __val); 2189 2190 return std::__equal_range(__first, __last, __val, 2191 __gnu_cxx::__ops::__iter_less_val(), 2192 __gnu_cxx::__ops::__val_less_iter()); 2193 } 2194 2195 /** 2196 * @brief Finds the largest subrange in which @p __val could be inserted 2197 * at any place in it without changing the ordering. 2198 * @param __first An iterator. 2199 * @param __last Another iterator. 2200 * @param __val The search term. 2201 * @param __comp A functor to use for comparisons. 2202 * @return An pair of iterators defining the subrange. 2203 * @ingroup binary_search_algorithms 2204 * 2205 * This is equivalent to 2206 * @code 2207 * std::make_pair(lower_bound(__first, __last, __val, __comp), 2208 * upper_bound(__first, __last, __val, __comp)) 2209 * @endcode 2210 * but does not actually call those functions. 2211 */ 2212 template<typename _ForwardIterator, typename _Tp, typename _Compare> 2213 inline pair<_ForwardIterator, _ForwardIterator> 2214 equal_range(_ForwardIterator __first, _ForwardIterator __last, 2215 const _Tp& __val, _Compare __comp) 2216 { 2217 // concept requirements 2218 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 2219 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 2220 typename iterator_traits<_ForwardIterator>::value_type, _Tp>) 2221 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 2222 _Tp, typename iterator_traits<_ForwardIterator>::value_type>) 2223 __glibcxx_requires_partitioned_lower_pred(__first, __last, 2224 __val, __comp); 2225 __glibcxx_requires_partitioned_upper_pred(__first, __last, 2226 __val, __comp); 2227 2228 return std::__equal_range(__first, __last, __val, 2229 __gnu_cxx::__ops::__iter_comp_val(__comp), 2230 __gnu_cxx::__ops::__val_comp_iter(__comp)); 2231 } 2232 2233 /** 2234 * @brief Determines whether an element exists in a range. 2235 * @ingroup binary_search_algorithms 2236 * @param __first An iterator. 2237 * @param __last Another iterator. 2238 * @param __val The search term. 2239 * @return True if @p __val (or its equivalent) is in [@p 2240 * __first,@p __last ]. 2241 * 2242 * Note that this does not actually return an iterator to @p __val. For 2243 * that, use std::find or a container's specialized find member functions. 2244 */ 2245 template<typename _ForwardIterator, typename _Tp> 2246 bool 2247 binary_search(_ForwardIterator __first, _ForwardIterator __last, 2248 const _Tp& __val) 2249 { 2250 // concept requirements 2251 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 2252 __glibcxx_function_requires(_LessThanOpConcept< 2253 _Tp, typename iterator_traits<_ForwardIterator>::value_type>) 2254 __glibcxx_requires_partitioned_lower(__first, __last, __val); 2255 __glibcxx_requires_partitioned_upper(__first, __last, __val); 2256 2257 _ForwardIterator __i 2258 = std::__lower_bound(__first, __last, __val, 2259 __gnu_cxx::__ops::__iter_less_val()); 2260 return __i != __last && !(__val < *__i); 2261 } 2262 2263 /** 2264 * @brief Determines whether an element exists in a range. 2265 * @ingroup binary_search_algorithms 2266 * @param __first An iterator. 2267 * @param __last Another iterator. 2268 * @param __val The search term. 2269 * @param __comp A functor to use for comparisons. 2270 * @return True if @p __val (or its equivalent) is in @p [__first,__last]. 2271 * 2272 * Note that this does not actually return an iterator to @p __val. For 2273 * that, use std::find or a container's specialized find member functions. 2274 * 2275 * The comparison function should have the same effects on ordering as 2276 * the function used for the initial sort. 2277 */ 2278 template<typename _ForwardIterator, typename _Tp, typename _Compare> 2279 bool 2280 binary_search(_ForwardIterator __first, _ForwardIterator __last, 2281 const _Tp& __val, _Compare __comp) 2282 { 2283 // concept requirements 2284 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 2285 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 2286 _Tp, typename iterator_traits<_ForwardIterator>::value_type>) 2287 __glibcxx_requires_partitioned_lower_pred(__first, __last, 2288 __val, __comp); 2289 __glibcxx_requires_partitioned_upper_pred(__first, __last, 2290 __val, __comp); 2291 2292 _ForwardIterator __i 2293 = std::__lower_bound(__first, __last, __val, 2294 __gnu_cxx::__ops::__iter_comp_val(__comp)); 2295 return __i != __last && !bool(__comp(__val, *__i)); 2296 } 2297 2298 // merge 2299 2300 /// This is a helper function for the __merge_adaptive routines. 2301 template<typename _InputIterator1, typename _InputIterator2, 2302 typename _OutputIterator, typename _Compare> 2303 void 2304 __move_merge_adaptive(_InputIterator1 __first1, _InputIterator1 __last1, 2305 _InputIterator2 __first2, _InputIterator2 __last2, 2306 _OutputIterator __result, _Compare __comp) 2307 { 2308 while (__first1 != __last1 && __first2 != __last2) 2309 { 2310 if (__comp(__first2, __first1)) 2311 { 2312 *__result = _GLIBCXX_MOVE(*__first2); 2313 ++__first2; 2314 } 2315 else 2316 { 2317 *__result = _GLIBCXX_MOVE(*__first1); 2318 ++__first1; 2319 } 2320 ++__result; 2321 } 2322 if (__first1 != __last1) 2323 _GLIBCXX_MOVE3(__first1, __last1, __result); 2324 } 2325 2326 /// This is a helper function for the __merge_adaptive routines. 2327 template<typename _BidirectionalIterator1, typename _BidirectionalIterator2, 2328 typename _BidirectionalIterator3, typename _Compare> 2329 void 2330 __move_merge_adaptive_backward(_BidirectionalIterator1 __first1, 2331 _BidirectionalIterator1 __last1, 2332 _BidirectionalIterator2 __first2, 2333 _BidirectionalIterator2 __last2, 2334 _BidirectionalIterator3 __result, 2335 _Compare __comp) 2336 { 2337 if (__first1 == __last1) 2338 { 2339 _GLIBCXX_MOVE_BACKWARD3(__first2, __last2, __result); 2340 return; 2341 } 2342 else if (__first2 == __last2) 2343 return; 2344 2345 --__last1; 2346 --__last2; 2347 while (true) 2348 { 2349 if (__comp(__last2, __last1)) 2350 { 2351 *--__result = _GLIBCXX_MOVE(*__last1); 2352 if (__first1 == __last1) 2353 { 2354 _GLIBCXX_MOVE_BACKWARD3(__first2, ++__last2, __result); 2355 return; 2356 } 2357 --__last1; 2358 } 2359 else 2360 { 2361 *--__result = _GLIBCXX_MOVE(*__last2); 2362 if (__first2 == __last2) 2363 return; 2364 --__last2; 2365 } 2366 } 2367 } 2368 2369 /// This is a helper function for the merge routines. 2370 template<typename _BidirectionalIterator1, typename _BidirectionalIterator2, 2371 typename _Distance> 2372 _BidirectionalIterator1 2373 __rotate_adaptive(_BidirectionalIterator1 __first, 2374 _BidirectionalIterator1 __middle, 2375 _BidirectionalIterator1 __last, 2376 _Distance __len1, _Distance __len2, 2377 _BidirectionalIterator2 __buffer, 2378 _Distance __buffer_size) 2379 { 2380 _BidirectionalIterator2 __buffer_end; 2381 if (__len1 > __len2 && __len2 <= __buffer_size) 2382 { 2383 if (__len2) 2384 { 2385 __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer); 2386 _GLIBCXX_MOVE_BACKWARD3(__first, __middle, __last); 2387 return _GLIBCXX_MOVE3(__buffer, __buffer_end, __first); 2388 } 2389 else 2390 return __first; 2391 } 2392 else if (__len1 <= __buffer_size) 2393 { 2394 if (__len1) 2395 { 2396 __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer); 2397 _GLIBCXX_MOVE3(__middle, __last, __first); 2398 return _GLIBCXX_MOVE_BACKWARD3(__buffer, __buffer_end, __last); 2399 } 2400 else 2401 return __last; 2402 } 2403 else 2404 { 2405 std::rotate(__first, __middle, __last); 2406 std::advance(__first, std::distance(__middle, __last)); 2407 return __first; 2408 } 2409 } 2410 2411 /// This is a helper function for the merge routines. 2412 template<typename _BidirectionalIterator, typename _Distance, 2413 typename _Pointer, typename _Compare> 2414 void 2415 __merge_adaptive(_BidirectionalIterator __first, 2416 _BidirectionalIterator __middle, 2417 _BidirectionalIterator __last, 2418 _Distance __len1, _Distance __len2, 2419 _Pointer __buffer, _Distance __buffer_size, 2420 _Compare __comp) 2421 { 2422 if (__len1 <= __len2 && __len1 <= __buffer_size) 2423 { 2424 _Pointer __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer); 2425 std::__move_merge_adaptive(__buffer, __buffer_end, __middle, __last, 2426 __first, __comp); 2427 } 2428 else if (__len2 <= __buffer_size) 2429 { 2430 _Pointer __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer); 2431 std::__move_merge_adaptive_backward(__first, __middle, __buffer, 2432 __buffer_end, __last, __comp); 2433 } 2434 else 2435 { 2436 _BidirectionalIterator __first_cut = __first; 2437 _BidirectionalIterator __second_cut = __middle; 2438 _Distance __len11 = 0; 2439 _Distance __len22 = 0; 2440 if (__len1 > __len2) 2441 { 2442 __len11 = __len1 / 2; 2443 std::advance(__first_cut, __len11); 2444 __second_cut 2445 = std::__lower_bound(__middle, __last, *__first_cut, 2446 __gnu_cxx::__ops::__iter_comp_val(__comp)); 2447 __len22 = std::distance(__middle, __second_cut); 2448 } 2449 else 2450 { 2451 __len22 = __len2 / 2; 2452 std::advance(__second_cut, __len22); 2453 __first_cut 2454 = std::__upper_bound(__first, __middle, *__second_cut, 2455 __gnu_cxx::__ops::__val_comp_iter(__comp)); 2456 __len11 = std::distance(__first, __first_cut); 2457 } 2458 2459 _BidirectionalIterator __new_middle 2460 = std::__rotate_adaptive(__first_cut, __middle, __second_cut, 2461 __len1 - __len11, __len22, __buffer, 2462 __buffer_size); 2463 std::__merge_adaptive(__first, __first_cut, __new_middle, __len11, 2464 __len22, __buffer, __buffer_size, __comp); 2465 std::__merge_adaptive(__new_middle, __second_cut, __last, 2466 __len1 - __len11, 2467 __len2 - __len22, __buffer, 2468 __buffer_size, __comp); 2469 } 2470 } 2471 2472 /// This is a helper function for the merge routines. 2473 template<typename _BidirectionalIterator, typename _Distance, 2474 typename _Compare> 2475 void 2476 __merge_without_buffer(_BidirectionalIterator __first, 2477 _BidirectionalIterator __middle, 2478 _BidirectionalIterator __last, 2479 _Distance __len1, _Distance __len2, 2480 _Compare __comp) 2481 { 2482 if (__len1 == 0 || __len2 == 0) 2483 return; 2484 2485 if (__len1 + __len2 == 2) 2486 { 2487 if (__comp(__middle, __first)) 2488 std::iter_swap(__first, __middle); 2489 return; 2490 } 2491 2492 _BidirectionalIterator __first_cut = __first; 2493 _BidirectionalIterator __second_cut = __middle; 2494 _Distance __len11 = 0; 2495 _Distance __len22 = 0; 2496 if (__len1 > __len2) 2497 { 2498 __len11 = __len1 / 2; 2499 std::advance(__first_cut, __len11); 2500 __second_cut 2501 = std::__lower_bound(__middle, __last, *__first_cut, 2502 __gnu_cxx::__ops::__iter_comp_val(__comp)); 2503 __len22 = std::distance(__middle, __second_cut); 2504 } 2505 else 2506 { 2507 __len22 = __len2 / 2; 2508 std::advance(__second_cut, __len22); 2509 __first_cut 2510 = std::__upper_bound(__first, __middle, *__second_cut, 2511 __gnu_cxx::__ops::__val_comp_iter(__comp)); 2512 __len11 = std::distance(__first, __first_cut); 2513 } 2514 2515 std::rotate(__first_cut, __middle, __second_cut); 2516 _BidirectionalIterator __new_middle = __first_cut; 2517 std::advance(__new_middle, std::distance(__middle, __second_cut)); 2518 std::__merge_without_buffer(__first, __first_cut, __new_middle, 2519 __len11, __len22, __comp); 2520 std::__merge_without_buffer(__new_middle, __second_cut, __last, 2521 __len1 - __len11, __len2 - __len22, __comp); 2522 } 2523 2524 template<typename _BidirectionalIterator, typename _Compare> 2525 void 2526 __inplace_merge(_BidirectionalIterator __first, 2527 _BidirectionalIterator __middle, 2528 _BidirectionalIterator __last, 2529 _Compare __comp) 2530 { 2531 typedef typename iterator_traits<_BidirectionalIterator>::value_type 2532 _ValueType; 2533 typedef typename iterator_traits<_BidirectionalIterator>::difference_type 2534 _DistanceType; 2535 2536 if (__first == __middle || __middle == __last) 2537 return; 2538 2539 const _DistanceType __len1 = std::distance(__first, __middle); 2540 const _DistanceType __len2 = std::distance(__middle, __last); 2541 2542 typedef _Temporary_buffer<_BidirectionalIterator, _ValueType> _TmpBuf; 2543 _TmpBuf __buf(__first, __last); 2544 2545 if (__buf.begin() == 0) 2546 std::__merge_without_buffer 2547 (__first, __middle, __last, __len1, __len2, __comp); 2548 else 2549 std::__merge_adaptive 2550 (__first, __middle, __last, __len1, __len2, __buf.begin(), 2551 _DistanceType(__buf.size()), __comp); 2552 } 2553 2554 /** 2555 * @brief Merges two sorted ranges in place. 2556 * @ingroup sorting_algorithms 2557 * @param __first An iterator. 2558 * @param __middle Another iterator. 2559 * @param __last Another iterator. 2560 * @return Nothing. 2561 * 2562 * Merges two sorted and consecutive ranges, [__first,__middle) and 2563 * [__middle,__last), and puts the result in [__first,__last). The 2564 * output will be sorted. The sort is @e stable, that is, for 2565 * equivalent elements in the two ranges, elements from the first 2566 * range will always come before elements from the second. 2567 * 2568 * If enough additional memory is available, this takes (__last-__first)-1 2569 * comparisons. Otherwise an NlogN algorithm is used, where N is 2570 * distance(__first,__last). 2571 */ 2572 template<typename _BidirectionalIterator> 2573 inline void 2574 inplace_merge(_BidirectionalIterator __first, 2575 _BidirectionalIterator __middle, 2576 _BidirectionalIterator __last) 2577 { 2578 // concept requirements 2579 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept< 2580 _BidirectionalIterator>) 2581 __glibcxx_function_requires(_LessThanComparableConcept< 2582 typename iterator_traits<_BidirectionalIterator>::value_type>) 2583 __glibcxx_requires_sorted(__first, __middle); 2584 __glibcxx_requires_sorted(__middle, __last); 2585 __glibcxx_requires_irreflexive(__first, __last); 2586 2587 std::__inplace_merge(__first, __middle, __last, 2588 __gnu_cxx::__ops::__iter_less_iter()); 2589 } 2590 2591 /** 2592 * @brief Merges two sorted ranges in place. 2593 * @ingroup sorting_algorithms 2594 * @param __first An iterator. 2595 * @param __middle Another iterator. 2596 * @param __last Another iterator. 2597 * @param __comp A functor to use for comparisons. 2598 * @return Nothing. 2599 * 2600 * Merges two sorted and consecutive ranges, [__first,__middle) and 2601 * [middle,last), and puts the result in [__first,__last). The output will 2602 * be sorted. The sort is @e stable, that is, for equivalent 2603 * elements in the two ranges, elements from the first range will always 2604 * come before elements from the second. 2605 * 2606 * If enough additional memory is available, this takes (__last-__first)-1 2607 * comparisons. Otherwise an NlogN algorithm is used, where N is 2608 * distance(__first,__last). 2609 * 2610 * The comparison function should have the same effects on ordering as 2611 * the function used for the initial sort. 2612 */ 2613 template<typename _BidirectionalIterator, typename _Compare> 2614 inline void 2615 inplace_merge(_BidirectionalIterator __first, 2616 _BidirectionalIterator __middle, 2617 _BidirectionalIterator __last, 2618 _Compare __comp) 2619 { 2620 // concept requirements 2621 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept< 2622 _BidirectionalIterator>) 2623 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 2624 typename iterator_traits<_BidirectionalIterator>::value_type, 2625 typename iterator_traits<_BidirectionalIterator>::value_type>) 2626 __glibcxx_requires_sorted_pred(__first, __middle, __comp); 2627 __glibcxx_requires_sorted_pred(__middle, __last, __comp); 2628 __glibcxx_requires_irreflexive_pred(__first, __last, __comp); 2629 2630 std::__inplace_merge(__first, __middle, __last, 2631 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 2632 } 2633 2634 2635 /// This is a helper function for the __merge_sort_loop routines. 2636 template<typename _InputIterator, typename _OutputIterator, 2637 typename _Compare> 2638 _OutputIterator 2639 __move_merge(_InputIterator __first1, _InputIterator __last1, 2640 _InputIterator __first2, _InputIterator __last2, 2641 _OutputIterator __result, _Compare __comp) 2642 { 2643 while (__first1 != __last1 && __first2 != __last2) 2644 { 2645 if (__comp(__first2, __first1)) 2646 { 2647 *__result = _GLIBCXX_MOVE(*__first2); 2648 ++__first2; 2649 } 2650 else 2651 { 2652 *__result = _GLIBCXX_MOVE(*__first1); 2653 ++__first1; 2654 } 2655 ++__result; 2656 } 2657 return _GLIBCXX_MOVE3(__first2, __last2, 2658 _GLIBCXX_MOVE3(__first1, __last1, 2659 __result)); 2660 } 2661 2662 template<typename _RandomAccessIterator1, typename _RandomAccessIterator2, 2663 typename _Distance, typename _Compare> 2664 void 2665 __merge_sort_loop(_RandomAccessIterator1 __first, 2666 _RandomAccessIterator1 __last, 2667 _RandomAccessIterator2 __result, _Distance __step_size, 2668 _Compare __comp) 2669 { 2670 const _Distance __two_step = 2 * __step_size; 2671 2672 while (__last - __first >= __two_step) 2673 { 2674 __result = std::__move_merge(__first, __first + __step_size, 2675 __first + __step_size, 2676 __first + __two_step, 2677 __result, __comp); 2678 __first += __two_step; 2679 } 2680 __step_size = std::min(_Distance(__last - __first), __step_size); 2681 2682 std::__move_merge(__first, __first + __step_size, 2683 __first + __step_size, __last, __result, __comp); 2684 } 2685 2686 template<typename _RandomAccessIterator, typename _Distance, 2687 typename _Compare> 2688 void 2689 __chunk_insertion_sort(_RandomAccessIterator __first, 2690 _RandomAccessIterator __last, 2691 _Distance __chunk_size, _Compare __comp) 2692 { 2693 while (__last - __first >= __chunk_size) 2694 { 2695 std::__insertion_sort(__first, __first + __chunk_size, __comp); 2696 __first += __chunk_size; 2697 } 2698 std::__insertion_sort(__first, __last, __comp); 2699 } 2700 2701 enum { _S_chunk_size = 7 }; 2702 2703 template<typename _RandomAccessIterator, typename _Pointer, typename _Compare> 2704 void 2705 __merge_sort_with_buffer(_RandomAccessIterator __first, 2706 _RandomAccessIterator __last, 2707 _Pointer __buffer, _Compare __comp) 2708 { 2709 typedef typename iterator_traits<_RandomAccessIterator>::difference_type 2710 _Distance; 2711 2712 const _Distance __len = __last - __first; 2713 const _Pointer __buffer_last = __buffer + __len; 2714 2715 _Distance __step_size = _S_chunk_size; 2716 std::__chunk_insertion_sort(__first, __last, __step_size, __comp); 2717 2718 while (__step_size < __len) 2719 { 2720 std::__merge_sort_loop(__first, __last, __buffer, 2721 __step_size, __comp); 2722 __step_size *= 2; 2723 std::__merge_sort_loop(__buffer, __buffer_last, __first, 2724 __step_size, __comp); 2725 __step_size *= 2; 2726 } 2727 } 2728 2729 template<typename _RandomAccessIterator, typename _Pointer, 2730 typename _Distance, typename _Compare> 2731 void 2732 __stable_sort_adaptive(_RandomAccessIterator __first, 2733 _RandomAccessIterator __last, 2734 _Pointer __buffer, _Distance __buffer_size, 2735 _Compare __comp) 2736 { 2737 const _Distance __len = (__last - __first + 1) / 2; 2738 const _RandomAccessIterator __middle = __first + __len; 2739 if (__len > __buffer_size) 2740 { 2741 std::__stable_sort_adaptive(__first, __middle, __buffer, 2742 __buffer_size, __comp); 2743 std::__stable_sort_adaptive(__middle, __last, __buffer, 2744 __buffer_size, __comp); 2745 } 2746 else 2747 { 2748 std::__merge_sort_with_buffer(__first, __middle, __buffer, __comp); 2749 std::__merge_sort_with_buffer(__middle, __last, __buffer, __comp); 2750 } 2751 std::__merge_adaptive(__first, __middle, __last, 2752 _Distance(__middle - __first), 2753 _Distance(__last - __middle), 2754 __buffer, __buffer_size, 2755 __comp); 2756 } 2757 2758 /// This is a helper function for the stable sorting routines. 2759 template<typename _RandomAccessIterator, typename _Compare> 2760 void 2761 __inplace_stable_sort(_RandomAccessIterator __first, 2762 _RandomAccessIterator __last, _Compare __comp) 2763 { 2764 if (__last - __first < 15) 2765 { 2766 std::__insertion_sort(__first, __last, __comp); 2767 return; 2768 } 2769 _RandomAccessIterator __middle = __first + (__last - __first) / 2; 2770 std::__inplace_stable_sort(__first, __middle, __comp); 2771 std::__inplace_stable_sort(__middle, __last, __comp); 2772 std::__merge_without_buffer(__first, __middle, __last, 2773 __middle - __first, 2774 __last - __middle, 2775 __comp); 2776 } 2777 2778 // stable_sort 2779 2780 // Set algorithms: includes, set_union, set_intersection, set_difference, 2781 // set_symmetric_difference. All of these algorithms have the precondition 2782 // that their input ranges are sorted and the postcondition that their output 2783 // ranges are sorted. 2784 2785 template<typename _InputIterator1, typename _InputIterator2, 2786 typename _Compare> 2787 bool 2788 __includes(_InputIterator1 __first1, _InputIterator1 __last1, 2789 _InputIterator2 __first2, _InputIterator2 __last2, 2790 _Compare __comp) 2791 { 2792 while (__first1 != __last1 && __first2 != __last2) 2793 if (__comp(__first2, __first1)) 2794 return false; 2795 else if (__comp(__first1, __first2)) 2796 ++__first1; 2797 else 2798 { 2799 ++__first1; 2800 ++__first2; 2801 } 2802 2803 return __first2 == __last2; 2804 } 2805 2806 /** 2807 * @brief Determines whether all elements of a sequence exists in a range. 2808 * @param __first1 Start of search range. 2809 * @param __last1 End of search range. 2810 * @param __first2 Start of sequence 2811 * @param __last2 End of sequence. 2812 * @return True if each element in [__first2,__last2) is contained in order 2813 * within [__first1,__last1). False otherwise. 2814 * @ingroup set_algorithms 2815 * 2816 * This operation expects both [__first1,__last1) and 2817 * [__first2,__last2) to be sorted. Searches for the presence of 2818 * each element in [__first2,__last2) within [__first1,__last1). 2819 * The iterators over each range only move forward, so this is a 2820 * linear algorithm. If an element in [__first2,__last2) is not 2821 * found before the search iterator reaches @p __last2, false is 2822 * returned. 2823 */ 2824 template<typename _InputIterator1, typename _InputIterator2> 2825 inline bool 2826 includes(_InputIterator1 __first1, _InputIterator1 __last1, 2827 _InputIterator2 __first2, _InputIterator2 __last2) 2828 { 2829 // concept requirements 2830 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 2831 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 2832 __glibcxx_function_requires(_LessThanOpConcept< 2833 typename iterator_traits<_InputIterator1>::value_type, 2834 typename iterator_traits<_InputIterator2>::value_type>) 2835 __glibcxx_function_requires(_LessThanOpConcept< 2836 typename iterator_traits<_InputIterator2>::value_type, 2837 typename iterator_traits<_InputIterator1>::value_type>) 2838 __glibcxx_requires_sorted_set(__first1, __last1, __first2); 2839 __glibcxx_requires_sorted_set(__first2, __last2, __first1); 2840 __glibcxx_requires_irreflexive2(__first1, __last1); 2841 __glibcxx_requires_irreflexive2(__first2, __last2); 2842 2843 return std::__includes(__first1, __last1, __first2, __last2, 2844 __gnu_cxx::__ops::__iter_less_iter()); 2845 } 2846 2847 /** 2848 * @brief Determines whether all elements of a sequence exists in a range 2849 * using comparison. 2850 * @ingroup set_algorithms 2851 * @param __first1 Start of search range. 2852 * @param __last1 End of search range. 2853 * @param __first2 Start of sequence 2854 * @param __last2 End of sequence. 2855 * @param __comp Comparison function to use. 2856 * @return True if each element in [__first2,__last2) is contained 2857 * in order within [__first1,__last1) according to comp. False 2858 * otherwise. @ingroup set_algorithms 2859 * 2860 * This operation expects both [__first1,__last1) and 2861 * [__first2,__last2) to be sorted. Searches for the presence of 2862 * each element in [__first2,__last2) within [__first1,__last1), 2863 * using comp to decide. The iterators over each range only move 2864 * forward, so this is a linear algorithm. If an element in 2865 * [__first2,__last2) is not found before the search iterator 2866 * reaches @p __last2, false is returned. 2867 */ 2868 template<typename _InputIterator1, typename _InputIterator2, 2869 typename _Compare> 2870 inline bool 2871 includes(_InputIterator1 __first1, _InputIterator1 __last1, 2872 _InputIterator2 __first2, _InputIterator2 __last2, 2873 _Compare __comp) 2874 { 2875 // concept requirements 2876 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 2877 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 2878 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 2879 typename iterator_traits<_InputIterator1>::value_type, 2880 typename iterator_traits<_InputIterator2>::value_type>) 2881 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 2882 typename iterator_traits<_InputIterator2>::value_type, 2883 typename iterator_traits<_InputIterator1>::value_type>) 2884 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp); 2885 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp); 2886 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp); 2887 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp); 2888 2889 return std::__includes(__first1, __last1, __first2, __last2, 2890 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 2891 } 2892 2893 // nth_element 2894 // merge 2895 // set_difference 2896 // set_intersection 2897 // set_union 2898 // stable_sort 2899 // set_symmetric_difference 2900 // min_element 2901 // max_element 2902 2903 template<typename _BidirectionalIterator, typename _Compare> 2904 bool 2905 __next_permutation(_BidirectionalIterator __first, 2906 _BidirectionalIterator __last, _Compare __comp) 2907 { 2908 if (__first == __last) 2909 return false; 2910 _BidirectionalIterator __i = __first; 2911 ++__i; 2912 if (__i == __last) 2913 return false; 2914 __i = __last; 2915 --__i; 2916 2917 for(;;) 2918 { 2919 _BidirectionalIterator __ii = __i; 2920 --__i; 2921 if (__comp(__i, __ii)) 2922 { 2923 _BidirectionalIterator __j = __last; 2924 while (!__comp(__i, --__j)) 2925 {} 2926 std::iter_swap(__i, __j); 2927 std::__reverse(__ii, __last, 2928 std::__iterator_category(__first)); 2929 return true; 2930 } 2931 if (__i == __first) 2932 { 2933 std::__reverse(__first, __last, 2934 std::__iterator_category(__first)); 2935 return false; 2936 } 2937 } 2938 } 2939 2940 /** 2941 * @brief Permute range into the next @e dictionary ordering. 2942 * @ingroup sorting_algorithms 2943 * @param __first Start of range. 2944 * @param __last End of range. 2945 * @return False if wrapped to first permutation, true otherwise. 2946 * 2947 * Treats all permutations of the range as a set of @e dictionary sorted 2948 * sequences. Permutes the current sequence into the next one of this set. 2949 * Returns true if there are more sequences to generate. If the sequence 2950 * is the largest of the set, the smallest is generated and false returned. 2951 */ 2952 template<typename _BidirectionalIterator> 2953 inline bool 2954 next_permutation(_BidirectionalIterator __first, 2955 _BidirectionalIterator __last) 2956 { 2957 // concept requirements 2958 __glibcxx_function_requires(_BidirectionalIteratorConcept< 2959 _BidirectionalIterator>) 2960 __glibcxx_function_requires(_LessThanComparableConcept< 2961 typename iterator_traits<_BidirectionalIterator>::value_type>) 2962 __glibcxx_requires_valid_range(__first, __last); 2963 __glibcxx_requires_irreflexive(__first, __last); 2964 2965 return std::__next_permutation 2966 (__first, __last, __gnu_cxx::__ops::__iter_less_iter()); 2967 } 2968 2969 /** 2970 * @brief Permute range into the next @e dictionary ordering using 2971 * comparison functor. 2972 * @ingroup sorting_algorithms 2973 * @param __first Start of range. 2974 * @param __last End of range. 2975 * @param __comp A comparison functor. 2976 * @return False if wrapped to first permutation, true otherwise. 2977 * 2978 * Treats all permutations of the range [__first,__last) as a set of 2979 * @e dictionary sorted sequences ordered by @p __comp. Permutes the current 2980 * sequence into the next one of this set. Returns true if there are more 2981 * sequences to generate. If the sequence is the largest of the set, the 2982 * smallest is generated and false returned. 2983 */ 2984 template<typename _BidirectionalIterator, typename _Compare> 2985 inline bool 2986 next_permutation(_BidirectionalIterator __first, 2987 _BidirectionalIterator __last, _Compare __comp) 2988 { 2989 // concept requirements 2990 __glibcxx_function_requires(_BidirectionalIteratorConcept< 2991 _BidirectionalIterator>) 2992 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 2993 typename iterator_traits<_BidirectionalIterator>::value_type, 2994 typename iterator_traits<_BidirectionalIterator>::value_type>) 2995 __glibcxx_requires_valid_range(__first, __last); 2996 __glibcxx_requires_irreflexive_pred(__first, __last, __comp); 2997 2998 return std::__next_permutation 2999 (__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp)); 3000 } 3001 3002 template<typename _BidirectionalIterator, typename _Compare> 3003 bool 3004 __prev_permutation(_BidirectionalIterator __first, 3005 _BidirectionalIterator __last, _Compare __comp) 3006 { 3007 if (__first == __last) 3008 return false; 3009 _BidirectionalIterator __i = __first; 3010 ++__i; 3011 if (__i == __last) 3012 return false; 3013 __i = __last; 3014 --__i; 3015 3016 for(;;) 3017 { 3018 _BidirectionalIterator __ii = __i; 3019 --__i; 3020 if (__comp(__ii, __i)) 3021 { 3022 _BidirectionalIterator __j = __last; 3023 while (!__comp(--__j, __i)) 3024 {} 3025 std::iter_swap(__i, __j); 3026 std::__reverse(__ii, __last, 3027 std::__iterator_category(__first)); 3028 return true; 3029 } 3030 if (__i == __first) 3031 { 3032 std::__reverse(__first, __last, 3033 std::__iterator_category(__first)); 3034 return false; 3035 } 3036 } 3037 } 3038 3039 /** 3040 * @brief Permute range into the previous @e dictionary ordering. 3041 * @ingroup sorting_algorithms 3042 * @param __first Start of range. 3043 * @param __last End of range. 3044 * @return False if wrapped to last permutation, true otherwise. 3045 * 3046 * Treats all permutations of the range as a set of @e dictionary sorted 3047 * sequences. Permutes the current sequence into the previous one of this 3048 * set. Returns true if there are more sequences to generate. If the 3049 * sequence is the smallest of the set, the largest is generated and false 3050 * returned. 3051 */ 3052 template<typename _BidirectionalIterator> 3053 inline bool 3054 prev_permutation(_BidirectionalIterator __first, 3055 _BidirectionalIterator __last) 3056 { 3057 // concept requirements 3058 __glibcxx_function_requires(_BidirectionalIteratorConcept< 3059 _BidirectionalIterator>) 3060 __glibcxx_function_requires(_LessThanComparableConcept< 3061 typename iterator_traits<_BidirectionalIterator>::value_type>) 3062 __glibcxx_requires_valid_range(__first, __last); 3063 __glibcxx_requires_irreflexive(__first, __last); 3064 3065 return std::__prev_permutation(__first, __last, 3066 __gnu_cxx::__ops::__iter_less_iter()); 3067 } 3068 3069 /** 3070 * @brief Permute range into the previous @e dictionary ordering using 3071 * comparison functor. 3072 * @ingroup sorting_algorithms 3073 * @param __first Start of range. 3074 * @param __last End of range. 3075 * @param __comp A comparison functor. 3076 * @return False if wrapped to last permutation, true otherwise. 3077 * 3078 * Treats all permutations of the range [__first,__last) as a set of 3079 * @e dictionary sorted sequences ordered by @p __comp. Permutes the current 3080 * sequence into the previous one of this set. Returns true if there are 3081 * more sequences to generate. If the sequence is the smallest of the set, 3082 * the largest is generated and false returned. 3083 */ 3084 template<typename _BidirectionalIterator, typename _Compare> 3085 inline bool 3086 prev_permutation(_BidirectionalIterator __first, 3087 _BidirectionalIterator __last, _Compare __comp) 3088 { 3089 // concept requirements 3090 __glibcxx_function_requires(_BidirectionalIteratorConcept< 3091 _BidirectionalIterator>) 3092 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 3093 typename iterator_traits<_BidirectionalIterator>::value_type, 3094 typename iterator_traits<_BidirectionalIterator>::value_type>) 3095 __glibcxx_requires_valid_range(__first, __last); 3096 __glibcxx_requires_irreflexive_pred(__first, __last, __comp); 3097 3098 return std::__prev_permutation(__first, __last, 3099 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 3100 } 3101 3102 // replace 3103 // replace_if 3104 3105 template<typename _InputIterator, typename _OutputIterator, 3106 typename _Predicate, typename _Tp> 3107 _OutputIterator 3108 __replace_copy_if(_InputIterator __first, _InputIterator __last, 3109 _OutputIterator __result, 3110 _Predicate __pred, const _Tp& __new_value) 3111 { 3112 for (; __first != __last; ++__first, (void)++__result) 3113 if (__pred(__first)) 3114 *__result = __new_value; 3115 else 3116 *__result = *__first; 3117 return __result; 3118 } 3119 3120 /** 3121 * @brief Copy a sequence, replacing each element of one value with another 3122 * value. 3123 * @param __first An input iterator. 3124 * @param __last An input iterator. 3125 * @param __result An output iterator. 3126 * @param __old_value The value to be replaced. 3127 * @param __new_value The replacement value. 3128 * @return The end of the output sequence, @p result+(last-first). 3129 * 3130 * Copies each element in the input range @p [__first,__last) to the 3131 * output range @p [__result,__result+(__last-__first)) replacing elements 3132 * equal to @p __old_value with @p __new_value. 3133 */ 3134 template<typename _InputIterator, typename _OutputIterator, typename _Tp> 3135 inline _OutputIterator 3136 replace_copy(_InputIterator __first, _InputIterator __last, 3137 _OutputIterator __result, 3138 const _Tp& __old_value, const _Tp& __new_value) 3139 { 3140 // concept requirements 3141 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 3142 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 3143 typename iterator_traits<_InputIterator>::value_type>) 3144 __glibcxx_function_requires(_EqualOpConcept< 3145 typename iterator_traits<_InputIterator>::value_type, _Tp>) 3146 __glibcxx_requires_valid_range(__first, __last); 3147 3148 return std::__replace_copy_if(__first, __last, __result, 3149 __gnu_cxx::__ops::__iter_equals_val(__old_value), 3150 __new_value); 3151 } 3152 3153 /** 3154 * @brief Copy a sequence, replacing each value for which a predicate 3155 * returns true with another value. 3156 * @ingroup mutating_algorithms 3157 * @param __first An input iterator. 3158 * @param __last An input iterator. 3159 * @param __result An output iterator. 3160 * @param __pred A predicate. 3161 * @param __new_value The replacement value. 3162 * @return The end of the output sequence, @p __result+(__last-__first). 3163 * 3164 * Copies each element in the range @p [__first,__last) to the range 3165 * @p [__result,__result+(__last-__first)) replacing elements for which 3166 * @p __pred returns true with @p __new_value. 3167 */ 3168 template<typename _InputIterator, typename _OutputIterator, 3169 typename _Predicate, typename _Tp> 3170 inline _OutputIterator 3171 replace_copy_if(_InputIterator __first, _InputIterator __last, 3172 _OutputIterator __result, 3173 _Predicate __pred, const _Tp& __new_value) 3174 { 3175 // concept requirements 3176 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 3177 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 3178 typename iterator_traits<_InputIterator>::value_type>) 3179 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 3180 typename iterator_traits<_InputIterator>::value_type>) 3181 __glibcxx_requires_valid_range(__first, __last); 3182 3183 return std::__replace_copy_if(__first, __last, __result, 3184 __gnu_cxx::__ops::__pred_iter(__pred), 3185 __new_value); 3186 } 3187 3188 template<typename _InputIterator, typename _Predicate> 3189 typename iterator_traits<_InputIterator>::difference_type 3190 __count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred) 3191 { 3192 typename iterator_traits<_InputIterator>::difference_type __n = 0; 3193 for (; __first != __last; ++__first) 3194 if (__pred(__first)) 3195 ++__n; 3196 return __n; 3197 } 3198 3199 #if __cplusplus >= 201103L 3200 /** 3201 * @brief Determines whether the elements of a sequence are sorted. 3202 * @ingroup sorting_algorithms 3203 * @param __first An iterator. 3204 * @param __last Another iterator. 3205 * @return True if the elements are sorted, false otherwise. 3206 */ 3207 template<typename _ForwardIterator> 3208 inline bool 3209 is_sorted(_ForwardIterator __first, _ForwardIterator __last) 3210 { return std::is_sorted_until(__first, __last) == __last; } 3211 3212 /** 3213 * @brief Determines whether the elements of a sequence are sorted 3214 * according to a comparison functor. 3215 * @ingroup sorting_algorithms 3216 * @param __first An iterator. 3217 * @param __last Another iterator. 3218 * @param __comp A comparison functor. 3219 * @return True if the elements are sorted, false otherwise. 3220 */ 3221 template<typename _ForwardIterator, typename _Compare> 3222 inline bool 3223 is_sorted(_ForwardIterator __first, _ForwardIterator __last, 3224 _Compare __comp) 3225 { return std::is_sorted_until(__first, __last, __comp) == __last; } 3226 3227 template<typename _ForwardIterator, typename _Compare> 3228 _ForwardIterator 3229 __is_sorted_until(_ForwardIterator __first, _ForwardIterator __last, 3230 _Compare __comp) 3231 { 3232 if (__first == __last) 3233 return __last; 3234 3235 _ForwardIterator __next = __first; 3236 for (++__next; __next != __last; __first = __next, (void)++__next) 3237 if (__comp(__next, __first)) 3238 return __next; 3239 return __next; 3240 } 3241 3242 /** 3243 * @brief Determines the end of a sorted sequence. 3244 * @ingroup sorting_algorithms 3245 * @param __first An iterator. 3246 * @param __last Another iterator. 3247 * @return An iterator pointing to the last iterator i in [__first, __last) 3248 * for which the range [__first, i) is sorted. 3249 */ 3250 template<typename _ForwardIterator> 3251 inline _ForwardIterator 3252 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last) 3253 { 3254 // concept requirements 3255 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 3256 __glibcxx_function_requires(_LessThanComparableConcept< 3257 typename iterator_traits<_ForwardIterator>::value_type>) 3258 __glibcxx_requires_valid_range(__first, __last); 3259 __glibcxx_requires_irreflexive(__first, __last); 3260 3261 return std::__is_sorted_until(__first, __last, 3262 __gnu_cxx::__ops::__iter_less_iter()); 3263 } 3264 3265 /** 3266 * @brief Determines the end of a sorted sequence using comparison functor. 3267 * @ingroup sorting_algorithms 3268 * @param __first An iterator. 3269 * @param __last Another iterator. 3270 * @param __comp A comparison functor. 3271 * @return An iterator pointing to the last iterator i in [__first, __last) 3272 * for which the range [__first, i) is sorted. 3273 */ 3274 template<typename _ForwardIterator, typename _Compare> 3275 inline _ForwardIterator 3276 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last, 3277 _Compare __comp) 3278 { 3279 // concept requirements 3280 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 3281 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 3282 typename iterator_traits<_ForwardIterator>::value_type, 3283 typename iterator_traits<_ForwardIterator>::value_type>) 3284 __glibcxx_requires_valid_range(__first, __last); 3285 __glibcxx_requires_irreflexive_pred(__first, __last, __comp); 3286 3287 return std::__is_sorted_until(__first, __last, 3288 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 3289 } 3290 3291 /** 3292 * @brief Determines min and max at once as an ordered pair. 3293 * @ingroup sorting_algorithms 3294 * @param __a A thing of arbitrary type. 3295 * @param __b Another thing of arbitrary type. 3296 * @return A pair(__b, __a) if __b is smaller than __a, pair(__a, 3297 * __b) otherwise. 3298 */ 3299 template<typename _Tp> 3300 _GLIBCXX14_CONSTEXPR 3301 inline pair<const _Tp&, const _Tp&> 3302 minmax(const _Tp& __a, const _Tp& __b) 3303 { 3304 // concept requirements 3305 __glibcxx_function_requires(_LessThanComparableConcept<_Tp>) 3306 3307 return __b < __a ? pair<const _Tp&, const _Tp&>(__b, __a) 3308 : pair<const _Tp&, const _Tp&>(__a, __b); 3309 } 3310 3311 /** 3312 * @brief Determines min and max at once as an ordered pair. 3313 * @ingroup sorting_algorithms 3314 * @param __a A thing of arbitrary type. 3315 * @param __b Another thing of arbitrary type. 3316 * @param __comp A @link comparison_functors comparison functor @endlink. 3317 * @return A pair(__b, __a) if __b is smaller than __a, pair(__a, 3318 * __b) otherwise. 3319 */ 3320 template<typename _Tp, typename _Compare> 3321 _GLIBCXX14_CONSTEXPR 3322 inline pair<const _Tp&, const _Tp&> 3323 minmax(const _Tp& __a, const _Tp& __b, _Compare __comp) 3324 { 3325 return __comp(__b, __a) ? pair<const _Tp&, const _Tp&>(__b, __a) 3326 : pair<const _Tp&, const _Tp&>(__a, __b); 3327 } 3328 3329 template<typename _ForwardIterator, typename _Compare> 3330 _GLIBCXX14_CONSTEXPR 3331 pair<_ForwardIterator, _ForwardIterator> 3332 __minmax_element(_ForwardIterator __first, _ForwardIterator __last, 3333 _Compare __comp) 3334 { 3335 _ForwardIterator __next = __first; 3336 if (__first == __last 3337 || ++__next == __last) 3338 return std::make_pair(__first, __first); 3339 3340 _ForwardIterator __min{}, __max{}; 3341 if (__comp(__next, __first)) 3342 { 3343 __min = __next; 3344 __max = __first; 3345 } 3346 else 3347 { 3348 __min = __first; 3349 __max = __next; 3350 } 3351 3352 __first = __next; 3353 ++__first; 3354 3355 while (__first != __last) 3356 { 3357 __next = __first; 3358 if (++__next == __last) 3359 { 3360 if (__comp(__first, __min)) 3361 __min = __first; 3362 else if (!__comp(__first, __max)) 3363 __max = __first; 3364 break; 3365 } 3366 3367 if (__comp(__next, __first)) 3368 { 3369 if (__comp(__next, __min)) 3370 __min = __next; 3371 if (!__comp(__first, __max)) 3372 __max = __first; 3373 } 3374 else 3375 { 3376 if (__comp(__first, __min)) 3377 __min = __first; 3378 if (!__comp(__next, __max)) 3379 __max = __next; 3380 } 3381 3382 __first = __next; 3383 ++__first; 3384 } 3385 3386 return std::make_pair(__min, __max); 3387 } 3388 3389 /** 3390 * @brief Return a pair of iterators pointing to the minimum and maximum 3391 * elements in a range. 3392 * @ingroup sorting_algorithms 3393 * @param __first Start of range. 3394 * @param __last End of range. 3395 * @return make_pair(m, M), where m is the first iterator i in 3396 * [__first, __last) such that no other element in the range is 3397 * smaller, and where M is the last iterator i in [__first, __last) 3398 * such that no other element in the range is larger. 3399 */ 3400 template<typename _ForwardIterator> 3401 _GLIBCXX14_CONSTEXPR 3402 inline pair<_ForwardIterator, _ForwardIterator> 3403 minmax_element(_ForwardIterator __first, _ForwardIterator __last) 3404 { 3405 // concept requirements 3406 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 3407 __glibcxx_function_requires(_LessThanComparableConcept< 3408 typename iterator_traits<_ForwardIterator>::value_type>) 3409 __glibcxx_requires_valid_range(__first, __last); 3410 __glibcxx_requires_irreflexive(__first, __last); 3411 3412 return std::__minmax_element(__first, __last, 3413 __gnu_cxx::__ops::__iter_less_iter()); 3414 } 3415 3416 /** 3417 * @brief Return a pair of iterators pointing to the minimum and maximum 3418 * elements in a range. 3419 * @ingroup sorting_algorithms 3420 * @param __first Start of range. 3421 * @param __last End of range. 3422 * @param __comp Comparison functor. 3423 * @return make_pair(m, M), where m is the first iterator i in 3424 * [__first, __last) such that no other element in the range is 3425 * smaller, and where M is the last iterator i in [__first, __last) 3426 * such that no other element in the range is larger. 3427 */ 3428 template<typename _ForwardIterator, typename _Compare> 3429 _GLIBCXX14_CONSTEXPR 3430 inline pair<_ForwardIterator, _ForwardIterator> 3431 minmax_element(_ForwardIterator __first, _ForwardIterator __last, 3432 _Compare __comp) 3433 { 3434 // concept requirements 3435 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 3436 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 3437 typename iterator_traits<_ForwardIterator>::value_type, 3438 typename iterator_traits<_ForwardIterator>::value_type>) 3439 __glibcxx_requires_valid_range(__first, __last); 3440 __glibcxx_requires_irreflexive_pred(__first, __last, __comp); 3441 3442 return std::__minmax_element(__first, __last, 3443 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 3444 } 3445 3446 // N2722 + DR 915. 3447 template<typename _Tp> 3448 _GLIBCXX14_CONSTEXPR 3449 inline _Tp 3450 min(initializer_list<_Tp> __l) 3451 { return *std::min_element(__l.begin(), __l.end()); } 3452 3453 template<typename _Tp, typename _Compare> 3454 _GLIBCXX14_CONSTEXPR 3455 inline _Tp 3456 min(initializer_list<_Tp> __l, _Compare __comp) 3457 { return *std::min_element(__l.begin(), __l.end(), __comp); } 3458 3459 template<typename _Tp> 3460 _GLIBCXX14_CONSTEXPR 3461 inline _Tp 3462 max(initializer_list<_Tp> __l) 3463 { return *std::max_element(__l.begin(), __l.end()); } 3464 3465 template<typename _Tp, typename _Compare> 3466 _GLIBCXX14_CONSTEXPR 3467 inline _Tp 3468 max(initializer_list<_Tp> __l, _Compare __comp) 3469 { return *std::max_element(__l.begin(), __l.end(), __comp); } 3470 3471 template<typename _Tp> 3472 _GLIBCXX14_CONSTEXPR 3473 inline pair<_Tp, _Tp> 3474 minmax(initializer_list<_Tp> __l) 3475 { 3476 pair<const _Tp*, const _Tp*> __p = 3477 std::minmax_element(__l.begin(), __l.end()); 3478 return std::make_pair(*__p.first, *__p.second); 3479 } 3480 3481 template<typename _Tp, typename _Compare> 3482 _GLIBCXX14_CONSTEXPR 3483 inline pair<_Tp, _Tp> 3484 minmax(initializer_list<_Tp> __l, _Compare __comp) 3485 { 3486 pair<const _Tp*, const _Tp*> __p = 3487 std::minmax_element(__l.begin(), __l.end(), __comp); 3488 return std::make_pair(*__p.first, *__p.second); 3489 } 3490 3491 template<typename _ForwardIterator1, typename _ForwardIterator2, 3492 typename _BinaryPredicate> 3493 bool 3494 __is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 3495 _ForwardIterator2 __first2, _BinaryPredicate __pred) 3496 { 3497 // Efficiently compare identical prefixes: O(N) if sequences 3498 // have the same elements in the same order. 3499 for (; __first1 != __last1; ++__first1, (void)++__first2) 3500 if (!__pred(__first1, __first2)) 3501 break; 3502 3503 if (__first1 == __last1) 3504 return true; 3505 3506 // Establish __last2 assuming equal ranges by iterating over the 3507 // rest of the list. 3508 _ForwardIterator2 __last2 = __first2; 3509 std::advance(__last2, std::distance(__first1, __last1)); 3510 for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan) 3511 { 3512 if (__scan != std::__find_if(__first1, __scan, 3513 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan))) 3514 continue; // We've seen this one before. 3515 3516 auto __matches 3517 = std::__count_if(__first2, __last2, 3518 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)); 3519 if (0 == __matches || 3520 std::__count_if(__scan, __last1, 3521 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)) 3522 != __matches) 3523 return false; 3524 } 3525 return true; 3526 } 3527 3528 /** 3529 * @brief Checks whether a permutation of the second sequence is equal 3530 * to the first sequence. 3531 * @ingroup non_mutating_algorithms 3532 * @param __first1 Start of first range. 3533 * @param __last1 End of first range. 3534 * @param __first2 Start of second range. 3535 * @return true if there exists a permutation of the elements in the range 3536 * [__first2, __first2 + (__last1 - __first1)), beginning with 3537 * ForwardIterator2 begin, such that equal(__first1, __last1, begin) 3538 * returns true; otherwise, returns false. 3539 */ 3540 template<typename _ForwardIterator1, typename _ForwardIterator2> 3541 inline bool 3542 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 3543 _ForwardIterator2 __first2) 3544 { 3545 // concept requirements 3546 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>) 3547 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>) 3548 __glibcxx_function_requires(_EqualOpConcept< 3549 typename iterator_traits<_ForwardIterator1>::value_type, 3550 typename iterator_traits<_ForwardIterator2>::value_type>) 3551 __glibcxx_requires_valid_range(__first1, __last1); 3552 3553 return std::__is_permutation(__first1, __last1, __first2, 3554 __gnu_cxx::__ops::__iter_equal_to_iter()); 3555 } 3556 3557 /** 3558 * @brief Checks whether a permutation of the second sequence is equal 3559 * to the first sequence. 3560 * @ingroup non_mutating_algorithms 3561 * @param __first1 Start of first range. 3562 * @param __last1 End of first range. 3563 * @param __first2 Start of second range. 3564 * @param __pred A binary predicate. 3565 * @return true if there exists a permutation of the elements in 3566 * the range [__first2, __first2 + (__last1 - __first1)), 3567 * beginning with ForwardIterator2 begin, such that 3568 * equal(__first1, __last1, __begin, __pred) returns true; 3569 * otherwise, returns false. 3570 */ 3571 template<typename _ForwardIterator1, typename _ForwardIterator2, 3572 typename _BinaryPredicate> 3573 inline bool 3574 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 3575 _ForwardIterator2 __first2, _BinaryPredicate __pred) 3576 { 3577 // concept requirements 3578 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>) 3579 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>) 3580 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 3581 typename iterator_traits<_ForwardIterator1>::value_type, 3582 typename iterator_traits<_ForwardIterator2>::value_type>) 3583 __glibcxx_requires_valid_range(__first1, __last1); 3584 3585 return std::__is_permutation(__first1, __last1, __first2, 3586 __gnu_cxx::__ops::__iter_comp_iter(__pred)); 3587 } 3588 3589 #if __cplusplus > 201103L 3590 template<typename _ForwardIterator1, typename _ForwardIterator2, 3591 typename _BinaryPredicate> 3592 bool 3593 __is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 3594 _ForwardIterator2 __first2, _ForwardIterator2 __last2, 3595 _BinaryPredicate __pred) 3596 { 3597 using _Cat1 3598 = typename iterator_traits<_ForwardIterator1>::iterator_category; 3599 using _Cat2 3600 = typename iterator_traits<_ForwardIterator2>::iterator_category; 3601 using _It1_is_RA = is_same<_Cat1, random_access_iterator_tag>; 3602 using _It2_is_RA = is_same<_Cat2, random_access_iterator_tag>; 3603 constexpr bool __ra_iters = _It1_is_RA() && _It2_is_RA(); 3604 if (__ra_iters) 3605 { 3606 auto __d1 = std::distance(__first1, __last1); 3607 auto __d2 = std::distance(__first2, __last2); 3608 if (__d1 != __d2) 3609 return false; 3610 } 3611 3612 // Efficiently compare identical prefixes: O(N) if sequences 3613 // have the same elements in the same order. 3614 for (; __first1 != __last1 && __first2 != __last2; 3615 ++__first1, (void)++__first2) 3616 if (!__pred(__first1, __first2)) 3617 break; 3618 3619 if (__ra_iters) 3620 { 3621 if (__first1 == __last1) 3622 return true; 3623 } 3624 else 3625 { 3626 auto __d1 = std::distance(__first1, __last1); 3627 auto __d2 = std::distance(__first2, __last2); 3628 if (__d1 == 0 && __d2 == 0) 3629 return true; 3630 if (__d1 != __d2) 3631 return false; 3632 } 3633 3634 for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan) 3635 { 3636 if (__scan != std::__find_if(__first1, __scan, 3637 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan))) 3638 continue; // We've seen this one before. 3639 3640 auto __matches = std::__count_if(__first2, __last2, 3641 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)); 3642 if (0 == __matches 3643 || std::__count_if(__scan, __last1, 3644 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)) 3645 != __matches) 3646 return false; 3647 } 3648 return true; 3649 } 3650 3651 /** 3652 * @brief Checks whether a permutaion of the second sequence is equal 3653 * to the first sequence. 3654 * @ingroup non_mutating_algorithms 3655 * @param __first1 Start of first range. 3656 * @param __last1 End of first range. 3657 * @param __first2 Start of second range. 3658 * @param __last2 End of first range. 3659 * @return true if there exists a permutation of the elements in the range 3660 * [__first2, __last2), beginning with ForwardIterator2 begin, 3661 * such that equal(__first1, __last1, begin) returns true; 3662 * otherwise, returns false. 3663 */ 3664 template<typename _ForwardIterator1, typename _ForwardIterator2> 3665 inline bool 3666 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 3667 _ForwardIterator2 __first2, _ForwardIterator2 __last2) 3668 { 3669 __glibcxx_requires_valid_range(__first1, __last1); 3670 __glibcxx_requires_valid_range(__first2, __last2); 3671 3672 return 3673 std::__is_permutation(__first1, __last1, __first2, __last2, 3674 __gnu_cxx::__ops::__iter_equal_to_iter()); 3675 } 3676 3677 /** 3678 * @brief Checks whether a permutation of the second sequence is equal 3679 * to the first sequence. 3680 * @ingroup non_mutating_algorithms 3681 * @param __first1 Start of first range. 3682 * @param __last1 End of first range. 3683 * @param __first2 Start of second range. 3684 * @param __last2 End of first range. 3685 * @param __pred A binary predicate. 3686 * @return true if there exists a permutation of the elements in the range 3687 * [__first2, __last2), beginning with ForwardIterator2 begin, 3688 * such that equal(__first1, __last1, __begin, __pred) returns true; 3689 * otherwise, returns false. 3690 */ 3691 template<typename _ForwardIterator1, typename _ForwardIterator2, 3692 typename _BinaryPredicate> 3693 inline bool 3694 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 3695 _ForwardIterator2 __first2, _ForwardIterator2 __last2, 3696 _BinaryPredicate __pred) 3697 { 3698 __glibcxx_requires_valid_range(__first1, __last1); 3699 __glibcxx_requires_valid_range(__first2, __last2); 3700 3701 return std::__is_permutation(__first1, __last1, __first2, __last2, 3702 __gnu_cxx::__ops::__iter_comp_iter(__pred)); 3703 } 3704 3705 #if __cplusplus > 201402L 3706 3707 #define __cpp_lib_clamp 201603 3708 3709 /** 3710 * @brief Returns the value clamped between lo and hi. 3711 * @ingroup sorting_algorithms 3712 * @param __val A value of arbitrary type. 3713 * @param __lo A lower limit of arbitrary type. 3714 * @param __hi An upper limit of arbitrary type. 3715 * @return max(__val, __lo) if __val < __hi or min(__val, __hi) otherwise. 3716 */ 3717 template<typename _Tp> 3718 constexpr const _Tp& 3719 clamp(const _Tp& __val, const _Tp& __lo, const _Tp& __hi) 3720 { 3721 __glibcxx_assert(!(__hi < __lo)); 3722 return (__val < __lo) ? __lo : (__hi < __val) ? __hi : __val; 3723 } 3724 3725 /** 3726 * @brief Returns the value clamped between lo and hi. 3727 * @ingroup sorting_algorithms 3728 * @param __val A value of arbitrary type. 3729 * @param __lo A lower limit of arbitrary type. 3730 * @param __hi An upper limit of arbitrary type. 3731 * @param __comp A comparison functor. 3732 * @return max(__val, __lo, __comp) if __comp(__val, __hi) 3733 * or min(__val, __hi, __comp) otherwise. 3734 */ 3735 template<typename _Tp, typename _Compare> 3736 constexpr const _Tp& 3737 clamp(const _Tp& __val, const _Tp& __lo, const _Tp& __hi, _Compare __comp) 3738 { 3739 __glibcxx_assert(!__comp(__hi, __lo)); 3740 return __comp(__val, __lo) ? __lo : __comp(__hi, __val) ? __hi : __val; 3741 } 3742 #endif // C++17 3743 #endif // C++14 3744 3745 #ifdef _GLIBCXX_USE_C99_STDINT_TR1 3746 /** 3747 * @brief Generate two uniformly distributed integers using a 3748 * single distribution invocation. 3749 * @param __b0 The upper bound for the first integer. 3750 * @param __b1 The upper bound for the second integer. 3751 * @param __g A UniformRandomBitGenerator. 3752 * @return A pair (i, j) with i and j uniformly distributed 3753 * over [0, __b0) and [0, __b1), respectively. 3754 * 3755 * Requires: __b0 * __b1 <= __g.max() - __g.min(). 3756 * 3757 * Using uniform_int_distribution with a range that is very 3758 * small relative to the range of the generator ends up wasting 3759 * potentially expensively generated randomness, since 3760 * uniform_int_distribution does not store leftover randomness 3761 * between invocations. 3762 * 3763 * If we know we want two integers in ranges that are sufficiently 3764 * small, we can compose the ranges, use a single distribution 3765 * invocation, and significantly reduce the waste. 3766 */ 3767 template<typename _IntType, typename _UniformRandomBitGenerator> 3768 pair<_IntType, _IntType> 3769 __gen_two_uniform_ints(_IntType __b0, _IntType __b1, 3770 _UniformRandomBitGenerator&& __g) 3771 { 3772 _IntType __x 3773 = uniform_int_distribution<_IntType>{0, (__b0 * __b1) - 1}(__g); 3774 return std::make_pair(__x / __b1, __x % __b1); 3775 } 3776 3777 /** 3778 * @brief Shuffle the elements of a sequence using a uniform random 3779 * number generator. 3780 * @ingroup mutating_algorithms 3781 * @param __first A forward iterator. 3782 * @param __last A forward iterator. 3783 * @param __g A UniformRandomNumberGenerator (26.5.1.3). 3784 * @return Nothing. 3785 * 3786 * Reorders the elements in the range @p [__first,__last) using @p __g to 3787 * provide random numbers. 3788 */ 3789 template<typename _RandomAccessIterator, 3790 typename _UniformRandomNumberGenerator> 3791 void 3792 shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last, 3793 _UniformRandomNumberGenerator&& __g) 3794 { 3795 // concept requirements 3796 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 3797 _RandomAccessIterator>) 3798 __glibcxx_requires_valid_range(__first, __last); 3799 3800 if (__first == __last) 3801 return; 3802 3803 typedef typename iterator_traits<_RandomAccessIterator>::difference_type 3804 _DistanceType; 3805 3806 typedef typename std::make_unsigned<_DistanceType>::type __ud_type; 3807 typedef typename std::uniform_int_distribution<__ud_type> __distr_type; 3808 typedef typename __distr_type::param_type __p_type; 3809 3810 typedef typename remove_reference<_UniformRandomNumberGenerator>::type 3811 _Gen; 3812 typedef typename common_type<typename _Gen::result_type, __ud_type>::type 3813 __uc_type; 3814 3815 const __uc_type __urngrange = __g.max() - __g.min(); 3816 const __uc_type __urange = __uc_type(__last - __first); 3817 3818 if (__urngrange / __urange >= __urange) 3819 // I.e. (__urngrange >= __urange * __urange) but without wrap issues. 3820 { 3821 _RandomAccessIterator __i = __first + 1; 3822 3823 // Since we know the range isn't empty, an even number of elements 3824 // means an uneven number of elements /to swap/, in which case we 3825 // do the first one up front: 3826 3827 if ((__urange % 2) == 0) 3828 { 3829 __distr_type __d{0, 1}; 3830 std::iter_swap(__i++, __first + __d(__g)); 3831 } 3832 3833 // Now we know that __last - __i is even, so we do the rest in pairs, 3834 // using a single distribution invocation to produce swap positions 3835 // for two successive elements at a time: 3836 3837 while (__i != __last) 3838 { 3839 const __uc_type __swap_range = __uc_type(__i - __first) + 1; 3840 3841 const pair<__uc_type, __uc_type> __pospos = 3842 __gen_two_uniform_ints(__swap_range, __swap_range + 1, __g); 3843 3844 std::iter_swap(__i++, __first + __pospos.first); 3845 std::iter_swap(__i++, __first + __pospos.second); 3846 } 3847 3848 return; 3849 } 3850 3851 __distr_type __d; 3852 3853 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i) 3854 std::iter_swap(__i, __first + __d(__g, __p_type(0, __i - __first))); 3855 } 3856 #endif 3857 3858 #endif // C++11 3859 3860 _GLIBCXX_END_NAMESPACE_VERSION 3861 3862 _GLIBCXX_BEGIN_NAMESPACE_ALGO 3863 3864 /** 3865 * @brief Apply a function to every element of a sequence. 3866 * @ingroup non_mutating_algorithms 3867 * @param __first An input iterator. 3868 * @param __last An input iterator. 3869 * @param __f A unary function object. 3870 * @return @p __f 3871 * 3872 * Applies the function object @p __f to each element in the range 3873 * @p [first,last). @p __f must not modify the order of the sequence. 3874 * If @p __f has a return value it is ignored. 3875 */ 3876 template<typename _InputIterator, typename _Function> 3877 _Function 3878 for_each(_InputIterator __first, _InputIterator __last, _Function __f) 3879 { 3880 // concept requirements 3881 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 3882 __glibcxx_requires_valid_range(__first, __last); 3883 for (; __first != __last; ++__first) 3884 __f(*__first); 3885 return __f; // N.B. [alg.foreach] says std::move(f) but it's redundant. 3886 } 3887 3888 /** 3889 * @brief Find the first occurrence of a value in a sequence. 3890 * @ingroup non_mutating_algorithms 3891 * @param __first An input iterator. 3892 * @param __last An input iterator. 3893 * @param __val The value to find. 3894 * @return The first iterator @c i in the range @p [__first,__last) 3895 * such that @c *i == @p __val, or @p __last if no such iterator exists. 3896 */ 3897 template<typename _InputIterator, typename _Tp> 3898 inline _InputIterator 3899 find(_InputIterator __first, _InputIterator __last, 3900 const _Tp& __val) 3901 { 3902 // concept requirements 3903 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 3904 __glibcxx_function_requires(_EqualOpConcept< 3905 typename iterator_traits<_InputIterator>::value_type, _Tp>) 3906 __glibcxx_requires_valid_range(__first, __last); 3907 return std::__find_if(__first, __last, 3908 __gnu_cxx::__ops::__iter_equals_val(__val)); 3909 } 3910 3911 /** 3912 * @brief Find the first element in a sequence for which a 3913 * predicate is true. 3914 * @ingroup non_mutating_algorithms 3915 * @param __first An input iterator. 3916 * @param __last An input iterator. 3917 * @param __pred A predicate. 3918 * @return The first iterator @c i in the range @p [__first,__last) 3919 * such that @p __pred(*i) is true, or @p __last if no such iterator exists. 3920 */ 3921 template<typename _InputIterator, typename _Predicate> 3922 inline _InputIterator 3923 find_if(_InputIterator __first, _InputIterator __last, 3924 _Predicate __pred) 3925 { 3926 // concept requirements 3927 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 3928 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 3929 typename iterator_traits<_InputIterator>::value_type>) 3930 __glibcxx_requires_valid_range(__first, __last); 3931 3932 return std::__find_if(__first, __last, 3933 __gnu_cxx::__ops::__pred_iter(__pred)); 3934 } 3935 3936 /** 3937 * @brief Find element from a set in a sequence. 3938 * @ingroup non_mutating_algorithms 3939 * @param __first1 Start of range to search. 3940 * @param __last1 End of range to search. 3941 * @param __first2 Start of match candidates. 3942 * @param __last2 End of match candidates. 3943 * @return The first iterator @c i in the range 3944 * @p [__first1,__last1) such that @c *i == @p *(i2) such that i2 is an 3945 * iterator in [__first2,__last2), or @p __last1 if no such iterator exists. 3946 * 3947 * Searches the range @p [__first1,__last1) for an element that is 3948 * equal to some element in the range [__first2,__last2). If 3949 * found, returns an iterator in the range [__first1,__last1), 3950 * otherwise returns @p __last1. 3951 */ 3952 template<typename _InputIterator, typename _ForwardIterator> 3953 _InputIterator 3954 find_first_of(_InputIterator __first1, _InputIterator __last1, 3955 _ForwardIterator __first2, _ForwardIterator __last2) 3956 { 3957 // concept requirements 3958 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 3959 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 3960 __glibcxx_function_requires(_EqualOpConcept< 3961 typename iterator_traits<_InputIterator>::value_type, 3962 typename iterator_traits<_ForwardIterator>::value_type>) 3963 __glibcxx_requires_valid_range(__first1, __last1); 3964 __glibcxx_requires_valid_range(__first2, __last2); 3965 3966 for (; __first1 != __last1; ++__first1) 3967 for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter) 3968 if (*__first1 == *__iter) 3969 return __first1; 3970 return __last1; 3971 } 3972 3973 /** 3974 * @brief Find element from a set in a sequence using a predicate. 3975 * @ingroup non_mutating_algorithms 3976 * @param __first1 Start of range to search. 3977 * @param __last1 End of range to search. 3978 * @param __first2 Start of match candidates. 3979 * @param __last2 End of match candidates. 3980 * @param __comp Predicate to use. 3981 * @return The first iterator @c i in the range 3982 * @p [__first1,__last1) such that @c comp(*i, @p *(i2)) is true 3983 * and i2 is an iterator in [__first2,__last2), or @p __last1 if no 3984 * such iterator exists. 3985 * 3986 3987 * Searches the range @p [__first1,__last1) for an element that is 3988 * equal to some element in the range [__first2,__last2). If 3989 * found, returns an iterator in the range [__first1,__last1), 3990 * otherwise returns @p __last1. 3991 */ 3992 template<typename _InputIterator, typename _ForwardIterator, 3993 typename _BinaryPredicate> 3994 _InputIterator 3995 find_first_of(_InputIterator __first1, _InputIterator __last1, 3996 _ForwardIterator __first2, _ForwardIterator __last2, 3997 _BinaryPredicate __comp) 3998 { 3999 // concept requirements 4000 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 4001 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 4002 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 4003 typename iterator_traits<_InputIterator>::value_type, 4004 typename iterator_traits<_ForwardIterator>::value_type>) 4005 __glibcxx_requires_valid_range(__first1, __last1); 4006 __glibcxx_requires_valid_range(__first2, __last2); 4007 4008 for (; __first1 != __last1; ++__first1) 4009 for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter) 4010 if (__comp(*__first1, *__iter)) 4011 return __first1; 4012 return __last1; 4013 } 4014 4015 /** 4016 * @brief Find two adjacent values in a sequence that are equal. 4017 * @ingroup non_mutating_algorithms 4018 * @param __first A forward iterator. 4019 * @param __last A forward iterator. 4020 * @return The first iterator @c i such that @c i and @c i+1 are both 4021 * valid iterators in @p [__first,__last) and such that @c *i == @c *(i+1), 4022 * or @p __last if no such iterator exists. 4023 */ 4024 template<typename _ForwardIterator> 4025 inline _ForwardIterator 4026 adjacent_find(_ForwardIterator __first, _ForwardIterator __last) 4027 { 4028 // concept requirements 4029 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 4030 __glibcxx_function_requires(_EqualityComparableConcept< 4031 typename iterator_traits<_ForwardIterator>::value_type>) 4032 __glibcxx_requires_valid_range(__first, __last); 4033 4034 return std::__adjacent_find(__first, __last, 4035 __gnu_cxx::__ops::__iter_equal_to_iter()); 4036 } 4037 4038 /** 4039 * @brief Find two adjacent values in a sequence using a predicate. 4040 * @ingroup non_mutating_algorithms 4041 * @param __first A forward iterator. 4042 * @param __last A forward iterator. 4043 * @param __binary_pred A binary predicate. 4044 * @return The first iterator @c i such that @c i and @c i+1 are both 4045 * valid iterators in @p [__first,__last) and such that 4046 * @p __binary_pred(*i,*(i+1)) is true, or @p __last if no such iterator 4047 * exists. 4048 */ 4049 template<typename _ForwardIterator, typename _BinaryPredicate> 4050 inline _ForwardIterator 4051 adjacent_find(_ForwardIterator __first, _ForwardIterator __last, 4052 _BinaryPredicate __binary_pred) 4053 { 4054 // concept requirements 4055 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 4056 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 4057 typename iterator_traits<_ForwardIterator>::value_type, 4058 typename iterator_traits<_ForwardIterator>::value_type>) 4059 __glibcxx_requires_valid_range(__first, __last); 4060 4061 return std::__adjacent_find(__first, __last, 4062 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred)); 4063 } 4064 4065 /** 4066 * @brief Count the number of copies of a value in a sequence. 4067 * @ingroup non_mutating_algorithms 4068 * @param __first An input iterator. 4069 * @param __last An input iterator. 4070 * @param __value The value to be counted. 4071 * @return The number of iterators @c i in the range @p [__first,__last) 4072 * for which @c *i == @p __value 4073 */ 4074 template<typename _InputIterator, typename _Tp> 4075 inline typename iterator_traits<_InputIterator>::difference_type 4076 count(_InputIterator __first, _InputIterator __last, const _Tp& __value) 4077 { 4078 // concept requirements 4079 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 4080 __glibcxx_function_requires(_EqualOpConcept< 4081 typename iterator_traits<_InputIterator>::value_type, _Tp>) 4082 __glibcxx_requires_valid_range(__first, __last); 4083 4084 return std::__count_if(__first, __last, 4085 __gnu_cxx::__ops::__iter_equals_val(__value)); 4086 } 4087 4088 /** 4089 * @brief Count the elements of a sequence for which a predicate is true. 4090 * @ingroup non_mutating_algorithms 4091 * @param __first An input iterator. 4092 * @param __last An input iterator. 4093 * @param __pred A predicate. 4094 * @return The number of iterators @c i in the range @p [__first,__last) 4095 * for which @p __pred(*i) is true. 4096 */ 4097 template<typename _InputIterator, typename _Predicate> 4098 inline typename iterator_traits<_InputIterator>::difference_type 4099 count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred) 4100 { 4101 // concept requirements 4102 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 4103 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 4104 typename iterator_traits<_InputIterator>::value_type>) 4105 __glibcxx_requires_valid_range(__first, __last); 4106 4107 return std::__count_if(__first, __last, 4108 __gnu_cxx::__ops::__pred_iter(__pred)); 4109 } 4110 4111 /** 4112 * @brief Search a sequence for a matching sub-sequence. 4113 * @ingroup non_mutating_algorithms 4114 * @param __first1 A forward iterator. 4115 * @param __last1 A forward iterator. 4116 * @param __first2 A forward iterator. 4117 * @param __last2 A forward iterator. 4118 * @return The first iterator @c i in the range @p 4119 * [__first1,__last1-(__last2-__first2)) such that @c *(i+N) == @p 4120 * *(__first2+N) for each @c N in the range @p 4121 * [0,__last2-__first2), or @p __last1 if no such iterator exists. 4122 * 4123 * Searches the range @p [__first1,__last1) for a sub-sequence that 4124 * compares equal value-by-value with the sequence given by @p 4125 * [__first2,__last2) and returns an iterator to the first element 4126 * of the sub-sequence, or @p __last1 if the sub-sequence is not 4127 * found. 4128 * 4129 * Because the sub-sequence must lie completely within the range @p 4130 * [__first1,__last1) it must start at a position less than @p 4131 * __last1-(__last2-__first2) where @p __last2-__first2 is the 4132 * length of the sub-sequence. 4133 * 4134 * This means that the returned iterator @c i will be in the range 4135 * @p [__first1,__last1-(__last2-__first2)) 4136 */ 4137 template<typename _ForwardIterator1, typename _ForwardIterator2> 4138 inline _ForwardIterator1 4139 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 4140 _ForwardIterator2 __first2, _ForwardIterator2 __last2) 4141 { 4142 // concept requirements 4143 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>) 4144 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>) 4145 __glibcxx_function_requires(_EqualOpConcept< 4146 typename iterator_traits<_ForwardIterator1>::value_type, 4147 typename iterator_traits<_ForwardIterator2>::value_type>) 4148 __glibcxx_requires_valid_range(__first1, __last1); 4149 __glibcxx_requires_valid_range(__first2, __last2); 4150 4151 return std::__search(__first1, __last1, __first2, __last2, 4152 __gnu_cxx::__ops::__iter_equal_to_iter()); 4153 } 4154 4155 /** 4156 * @brief Search a sequence for a matching sub-sequence using a predicate. 4157 * @ingroup non_mutating_algorithms 4158 * @param __first1 A forward iterator. 4159 * @param __last1 A forward iterator. 4160 * @param __first2 A forward iterator. 4161 * @param __last2 A forward iterator. 4162 * @param __predicate A binary predicate. 4163 * @return The first iterator @c i in the range 4164 * @p [__first1,__last1-(__last2-__first2)) such that 4165 * @p __predicate(*(i+N),*(__first2+N)) is true for each @c N in the range 4166 * @p [0,__last2-__first2), or @p __last1 if no such iterator exists. 4167 * 4168 * Searches the range @p [__first1,__last1) for a sub-sequence that 4169 * compares equal value-by-value with the sequence given by @p 4170 * [__first2,__last2), using @p __predicate to determine equality, 4171 * and returns an iterator to the first element of the 4172 * sub-sequence, or @p __last1 if no such iterator exists. 4173 * 4174 * @see search(_ForwardIter1, _ForwardIter1, _ForwardIter2, _ForwardIter2) 4175 */ 4176 template<typename _ForwardIterator1, typename _ForwardIterator2, 4177 typename _BinaryPredicate> 4178 inline _ForwardIterator1 4179 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 4180 _ForwardIterator2 __first2, _ForwardIterator2 __last2, 4181 _BinaryPredicate __predicate) 4182 { 4183 // concept requirements 4184 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>) 4185 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>) 4186 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 4187 typename iterator_traits<_ForwardIterator1>::value_type, 4188 typename iterator_traits<_ForwardIterator2>::value_type>) 4189 __glibcxx_requires_valid_range(__first1, __last1); 4190 __glibcxx_requires_valid_range(__first2, __last2); 4191 4192 return std::__search(__first1, __last1, __first2, __last2, 4193 __gnu_cxx::__ops::__iter_comp_iter(__predicate)); 4194 } 4195 4196 /** 4197 * @brief Search a sequence for a number of consecutive values. 4198 * @ingroup non_mutating_algorithms 4199 * @param __first A forward iterator. 4200 * @param __last A forward iterator. 4201 * @param __count The number of consecutive values. 4202 * @param __val The value to find. 4203 * @return The first iterator @c i in the range @p 4204 * [__first,__last-__count) such that @c *(i+N) == @p __val for 4205 * each @c N in the range @p [0,__count), or @p __last if no such 4206 * iterator exists. 4207 * 4208 * Searches the range @p [__first,__last) for @p count consecutive elements 4209 * equal to @p __val. 4210 */ 4211 template<typename _ForwardIterator, typename _Integer, typename _Tp> 4212 inline _ForwardIterator 4213 search_n(_ForwardIterator __first, _ForwardIterator __last, 4214 _Integer __count, const _Tp& __val) 4215 { 4216 // concept requirements 4217 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 4218 __glibcxx_function_requires(_EqualOpConcept< 4219 typename iterator_traits<_ForwardIterator>::value_type, _Tp>) 4220 __glibcxx_requires_valid_range(__first, __last); 4221 4222 return std::__search_n(__first, __last, __count, 4223 __gnu_cxx::__ops::__iter_equals_val(__val)); 4224 } 4225 4226 4227 /** 4228 * @brief Search a sequence for a number of consecutive values using a 4229 * predicate. 4230 * @ingroup non_mutating_algorithms 4231 * @param __first A forward iterator. 4232 * @param __last A forward iterator. 4233 * @param __count The number of consecutive values. 4234 * @param __val The value to find. 4235 * @param __binary_pred A binary predicate. 4236 * @return The first iterator @c i in the range @p 4237 * [__first,__last-__count) such that @p 4238 * __binary_pred(*(i+N),__val) is true for each @c N in the range 4239 * @p [0,__count), or @p __last if no such iterator exists. 4240 * 4241 * Searches the range @p [__first,__last) for @p __count 4242 * consecutive elements for which the predicate returns true. 4243 */ 4244 template<typename _ForwardIterator, typename _Integer, typename _Tp, 4245 typename _BinaryPredicate> 4246 inline _ForwardIterator 4247 search_n(_ForwardIterator __first, _ForwardIterator __last, 4248 _Integer __count, const _Tp& __val, 4249 _BinaryPredicate __binary_pred) 4250 { 4251 // concept requirements 4252 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 4253 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 4254 typename iterator_traits<_ForwardIterator>::value_type, _Tp>) 4255 __glibcxx_requires_valid_range(__first, __last); 4256 4257 return std::__search_n(__first, __last, __count, 4258 __gnu_cxx::__ops::__iter_comp_val(__binary_pred, __val)); 4259 } 4260 4261 #if __cplusplus > 201402L 4262 /** @brief Search a sequence using a Searcher object. 4263 * 4264 * @param __first A forward iterator. 4265 * @param __last A forward iterator. 4266 * @param __searcher A callable object. 4267 * @return @p __searcher(__first,__last).first 4268 */ 4269 template<typename _ForwardIterator, typename _Searcher> 4270 inline _ForwardIterator 4271 search(_ForwardIterator __first, _ForwardIterator __last, 4272 const _Searcher& __searcher) 4273 { return __searcher(__first, __last).first; } 4274 #endif 4275 4276 /** 4277 * @brief Perform an operation on a sequence. 4278 * @ingroup mutating_algorithms 4279 * @param __first An input iterator. 4280 * @param __last An input iterator. 4281 * @param __result An output iterator. 4282 * @param __unary_op A unary operator. 4283 * @return An output iterator equal to @p __result+(__last-__first). 4284 * 4285 * Applies the operator to each element in the input range and assigns 4286 * the results to successive elements of the output sequence. 4287 * Evaluates @p *(__result+N)=unary_op(*(__first+N)) for each @c N in the 4288 * range @p [0,__last-__first). 4289 * 4290 * @p unary_op must not alter its argument. 4291 */ 4292 template<typename _InputIterator, typename _OutputIterator, 4293 typename _UnaryOperation> 4294 _OutputIterator 4295 transform(_InputIterator __first, _InputIterator __last, 4296 _OutputIterator __result, _UnaryOperation __unary_op) 4297 { 4298 // concept requirements 4299 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 4300 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 4301 // "the type returned by a _UnaryOperation" 4302 __typeof__(__unary_op(*__first))>) 4303 __glibcxx_requires_valid_range(__first, __last); 4304 4305 for (; __first != __last; ++__first, (void)++__result) 4306 *__result = __unary_op(*__first); 4307 return __result; 4308 } 4309 4310 /** 4311 * @brief Perform an operation on corresponding elements of two sequences. 4312 * @ingroup mutating_algorithms 4313 * @param __first1 An input iterator. 4314 * @param __last1 An input iterator. 4315 * @param __first2 An input iterator. 4316 * @param __result An output iterator. 4317 * @param __binary_op A binary operator. 4318 * @return An output iterator equal to @p result+(last-first). 4319 * 4320 * Applies the operator to the corresponding elements in the two 4321 * input ranges and assigns the results to successive elements of the 4322 * output sequence. 4323 * Evaluates @p 4324 * *(__result+N)=__binary_op(*(__first1+N),*(__first2+N)) for each 4325 * @c N in the range @p [0,__last1-__first1). 4326 * 4327 * @p binary_op must not alter either of its arguments. 4328 */ 4329 template<typename _InputIterator1, typename _InputIterator2, 4330 typename _OutputIterator, typename _BinaryOperation> 4331 _OutputIterator 4332 transform(_InputIterator1 __first1, _InputIterator1 __last1, 4333 _InputIterator2 __first2, _OutputIterator __result, 4334 _BinaryOperation __binary_op) 4335 { 4336 // concept requirements 4337 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 4338 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 4339 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 4340 // "the type returned by a _BinaryOperation" 4341 __typeof__(__binary_op(*__first1,*__first2))>) 4342 __glibcxx_requires_valid_range(__first1, __last1); 4343 4344 for (; __first1 != __last1; ++__first1, (void)++__first2, ++__result) 4345 *__result = __binary_op(*__first1, *__first2); 4346 return __result; 4347 } 4348 4349 /** 4350 * @brief Replace each occurrence of one value in a sequence with another 4351 * value. 4352 * @ingroup mutating_algorithms 4353 * @param __first A forward iterator. 4354 * @param __last A forward iterator. 4355 * @param __old_value The value to be replaced. 4356 * @param __new_value The replacement value. 4357 * @return replace() returns no value. 4358 * 4359 * For each iterator @c i in the range @p [__first,__last) if @c *i == 4360 * @p __old_value then the assignment @c *i = @p __new_value is performed. 4361 */ 4362 template<typename _ForwardIterator, typename _Tp> 4363 void 4364 replace(_ForwardIterator __first, _ForwardIterator __last, 4365 const _Tp& __old_value, const _Tp& __new_value) 4366 { 4367 // concept requirements 4368 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 4369 _ForwardIterator>) 4370 __glibcxx_function_requires(_EqualOpConcept< 4371 typename iterator_traits<_ForwardIterator>::value_type, _Tp>) 4372 __glibcxx_function_requires(_ConvertibleConcept<_Tp, 4373 typename iterator_traits<_ForwardIterator>::value_type>) 4374 __glibcxx_requires_valid_range(__first, __last); 4375 4376 for (; __first != __last; ++__first) 4377 if (*__first == __old_value) 4378 *__first = __new_value; 4379 } 4380 4381 /** 4382 * @brief Replace each value in a sequence for which a predicate returns 4383 * true with another value. 4384 * @ingroup mutating_algorithms 4385 * @param __first A forward iterator. 4386 * @param __last A forward iterator. 4387 * @param __pred A predicate. 4388 * @param __new_value The replacement value. 4389 * @return replace_if() returns no value. 4390 * 4391 * For each iterator @c i in the range @p [__first,__last) if @p __pred(*i) 4392 * is true then the assignment @c *i = @p __new_value is performed. 4393 */ 4394 template<typename _ForwardIterator, typename _Predicate, typename _Tp> 4395 void 4396 replace_if(_ForwardIterator __first, _ForwardIterator __last, 4397 _Predicate __pred, const _Tp& __new_value) 4398 { 4399 // concept requirements 4400 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 4401 _ForwardIterator>) 4402 __glibcxx_function_requires(_ConvertibleConcept<_Tp, 4403 typename iterator_traits<_ForwardIterator>::value_type>) 4404 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 4405 typename iterator_traits<_ForwardIterator>::value_type>) 4406 __glibcxx_requires_valid_range(__first, __last); 4407 4408 for (; __first != __last; ++__first) 4409 if (__pred(*__first)) 4410 *__first = __new_value; 4411 } 4412 4413 /** 4414 * @brief Assign the result of a function object to each value in a 4415 * sequence. 4416 * @ingroup mutating_algorithms 4417 * @param __first A forward iterator. 4418 * @param __last A forward iterator. 4419 * @param __gen A function object taking no arguments and returning 4420 * std::iterator_traits<_ForwardIterator>::value_type 4421 * @return generate() returns no value. 4422 * 4423 * Performs the assignment @c *i = @p __gen() for each @c i in the range 4424 * @p [__first,__last). 4425 */ 4426 template<typename _ForwardIterator, typename _Generator> 4427 void 4428 generate(_ForwardIterator __first, _ForwardIterator __last, 4429 _Generator __gen) 4430 { 4431 // concept requirements 4432 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 4433 __glibcxx_function_requires(_GeneratorConcept<_Generator, 4434 typename iterator_traits<_ForwardIterator>::value_type>) 4435 __glibcxx_requires_valid_range(__first, __last); 4436 4437 for (; __first != __last; ++__first) 4438 *__first = __gen(); 4439 } 4440 4441 /** 4442 * @brief Assign the result of a function object to each value in a 4443 * sequence. 4444 * @ingroup mutating_algorithms 4445 * @param __first A forward iterator. 4446 * @param __n The length of the sequence. 4447 * @param __gen A function object taking no arguments and returning 4448 * std::iterator_traits<_ForwardIterator>::value_type 4449 * @return The end of the sequence, @p __first+__n 4450 * 4451 * Performs the assignment @c *i = @p __gen() for each @c i in the range 4452 * @p [__first,__first+__n). 4453 * 4454 * _GLIBCXX_RESOLVE_LIB_DEFECTS 4455 * DR 865. More algorithms that throw away information 4456 */ 4457 template<typename _OutputIterator, typename _Size, typename _Generator> 4458 _OutputIterator 4459 generate_n(_OutputIterator __first, _Size __n, _Generator __gen) 4460 { 4461 // concept requirements 4462 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 4463 // "the type returned by a _Generator" 4464 __typeof__(__gen())>) 4465 4466 for (__decltype(__n + 0) __niter = __n; 4467 __niter > 0; --__niter, ++__first) 4468 *__first = __gen(); 4469 return __first; 4470 } 4471 4472 /** 4473 * @brief Copy a sequence, removing consecutive duplicate values. 4474 * @ingroup mutating_algorithms 4475 * @param __first An input iterator. 4476 * @param __last An input iterator. 4477 * @param __result An output iterator. 4478 * @return An iterator designating the end of the resulting sequence. 4479 * 4480 * Copies each element in the range @p [__first,__last) to the range 4481 * beginning at @p __result, except that only the first element is copied 4482 * from groups of consecutive elements that compare equal. 4483 * unique_copy() is stable, so the relative order of elements that are 4484 * copied is unchanged. 4485 * 4486 * _GLIBCXX_RESOLVE_LIB_DEFECTS 4487 * DR 241. Does unique_copy() require CopyConstructible and Assignable? 4488 * 4489 * _GLIBCXX_RESOLVE_LIB_DEFECTS 4490 * DR 538. 241 again: Does unique_copy() require CopyConstructible and 4491 * Assignable? 4492 */ 4493 template<typename _InputIterator, typename _OutputIterator> 4494 inline _OutputIterator 4495 unique_copy(_InputIterator __first, _InputIterator __last, 4496 _OutputIterator __result) 4497 { 4498 // concept requirements 4499 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 4500 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 4501 typename iterator_traits<_InputIterator>::value_type>) 4502 __glibcxx_function_requires(_EqualityComparableConcept< 4503 typename iterator_traits<_InputIterator>::value_type>) 4504 __glibcxx_requires_valid_range(__first, __last); 4505 4506 if (__first == __last) 4507 return __result; 4508 return std::__unique_copy(__first, __last, __result, 4509 __gnu_cxx::__ops::__iter_equal_to_iter(), 4510 std::__iterator_category(__first), 4511 std::__iterator_category(__result)); 4512 } 4513 4514 /** 4515 * @brief Copy a sequence, removing consecutive values using a predicate. 4516 * @ingroup mutating_algorithms 4517 * @param __first An input iterator. 4518 * @param __last An input iterator. 4519 * @param __result An output iterator. 4520 * @param __binary_pred A binary predicate. 4521 * @return An iterator designating the end of the resulting sequence. 4522 * 4523 * Copies each element in the range @p [__first,__last) to the range 4524 * beginning at @p __result, except that only the first element is copied 4525 * from groups of consecutive elements for which @p __binary_pred returns 4526 * true. 4527 * unique_copy() is stable, so the relative order of elements that are 4528 * copied is unchanged. 4529 * 4530 * _GLIBCXX_RESOLVE_LIB_DEFECTS 4531 * DR 241. Does unique_copy() require CopyConstructible and Assignable? 4532 */ 4533 template<typename _InputIterator, typename _OutputIterator, 4534 typename _BinaryPredicate> 4535 inline _OutputIterator 4536 unique_copy(_InputIterator __first, _InputIterator __last, 4537 _OutputIterator __result, 4538 _BinaryPredicate __binary_pred) 4539 { 4540 // concept requirements -- predicates checked later 4541 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 4542 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 4543 typename iterator_traits<_InputIterator>::value_type>) 4544 __glibcxx_requires_valid_range(__first, __last); 4545 4546 if (__first == __last) 4547 return __result; 4548 return std::__unique_copy(__first, __last, __result, 4549 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred), 4550 std::__iterator_category(__first), 4551 std::__iterator_category(__result)); 4552 } 4553 4554 #if _GLIBCXX_HOSTED 4555 /** 4556 * @brief Randomly shuffle the elements of a sequence. 4557 * @ingroup mutating_algorithms 4558 * @param __first A forward iterator. 4559 * @param __last A forward iterator. 4560 * @return Nothing. 4561 * 4562 * Reorder the elements in the range @p [__first,__last) using a random 4563 * distribution, so that every possible ordering of the sequence is 4564 * equally likely. 4565 */ 4566 template<typename _RandomAccessIterator> 4567 inline void 4568 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last) 4569 { 4570 // concept requirements 4571 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 4572 _RandomAccessIterator>) 4573 __glibcxx_requires_valid_range(__first, __last); 4574 4575 if (__first != __last) 4576 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i) 4577 { 4578 // XXX rand() % N is not uniformly distributed 4579 _RandomAccessIterator __j = __first 4580 + std::rand() % ((__i - __first) + 1); 4581 if (__i != __j) 4582 std::iter_swap(__i, __j); 4583 } 4584 } 4585 #endif 4586 4587 /** 4588 * @brief Shuffle the elements of a sequence using a random number 4589 * generator. 4590 * @ingroup mutating_algorithms 4591 * @param __first A forward iterator. 4592 * @param __last A forward iterator. 4593 * @param __rand The RNG functor or function. 4594 * @return Nothing. 4595 * 4596 * Reorders the elements in the range @p [__first,__last) using @p __rand to 4597 * provide a random distribution. Calling @p __rand(N) for a positive 4598 * integer @p N should return a randomly chosen integer from the 4599 * range [0,N). 4600 */ 4601 template<typename _RandomAccessIterator, typename _RandomNumberGenerator> 4602 void 4603 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last, 4604 #if __cplusplus >= 201103L 4605 _RandomNumberGenerator&& __rand) 4606 #else 4607 _RandomNumberGenerator& __rand) 4608 #endif 4609 { 4610 // concept requirements 4611 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 4612 _RandomAccessIterator>) 4613 __glibcxx_requires_valid_range(__first, __last); 4614 4615 if (__first == __last) 4616 return; 4617 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i) 4618 { 4619 _RandomAccessIterator __j = __first + __rand((__i - __first) + 1); 4620 if (__i != __j) 4621 std::iter_swap(__i, __j); 4622 } 4623 } 4624 4625 4626 /** 4627 * @brief Move elements for which a predicate is true to the beginning 4628 * of a sequence. 4629 * @ingroup mutating_algorithms 4630 * @param __first A forward iterator. 4631 * @param __last A forward iterator. 4632 * @param __pred A predicate functor. 4633 * @return An iterator @p middle such that @p __pred(i) is true for each 4634 * iterator @p i in the range @p [__first,middle) and false for each @p i 4635 * in the range @p [middle,__last). 4636 * 4637 * @p __pred must not modify its operand. @p partition() does not preserve 4638 * the relative ordering of elements in each group, use 4639 * @p stable_partition() if this is needed. 4640 */ 4641 template<typename _ForwardIterator, typename _Predicate> 4642 inline _ForwardIterator 4643 partition(_ForwardIterator __first, _ForwardIterator __last, 4644 _Predicate __pred) 4645 { 4646 // concept requirements 4647 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 4648 _ForwardIterator>) 4649 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 4650 typename iterator_traits<_ForwardIterator>::value_type>) 4651 __glibcxx_requires_valid_range(__first, __last); 4652 4653 return std::__partition(__first, __last, __pred, 4654 std::__iterator_category(__first)); 4655 } 4656 4657 4658 /** 4659 * @brief Sort the smallest elements of a sequence. 4660 * @ingroup sorting_algorithms 4661 * @param __first An iterator. 4662 * @param __middle Another iterator. 4663 * @param __last Another iterator. 4664 * @return Nothing. 4665 * 4666 * Sorts the smallest @p (__middle-__first) elements in the range 4667 * @p [first,last) and moves them to the range @p [__first,__middle). The 4668 * order of the remaining elements in the range @p [__middle,__last) is 4669 * undefined. 4670 * After the sort if @e i and @e j are iterators in the range 4671 * @p [__first,__middle) such that i precedes j and @e k is an iterator in 4672 * the range @p [__middle,__last) then *j<*i and *k<*i are both false. 4673 */ 4674 template<typename _RandomAccessIterator> 4675 inline void 4676 partial_sort(_RandomAccessIterator __first, 4677 _RandomAccessIterator __middle, 4678 _RandomAccessIterator __last) 4679 { 4680 // concept requirements 4681 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 4682 _RandomAccessIterator>) 4683 __glibcxx_function_requires(_LessThanComparableConcept< 4684 typename iterator_traits<_RandomAccessIterator>::value_type>) 4685 __glibcxx_requires_valid_range(__first, __middle); 4686 __glibcxx_requires_valid_range(__middle, __last); 4687 __glibcxx_requires_irreflexive(__first, __last); 4688 4689 std::__partial_sort(__first, __middle, __last, 4690 __gnu_cxx::__ops::__iter_less_iter()); 4691 } 4692 4693 /** 4694 * @brief Sort the smallest elements of a sequence using a predicate 4695 * for comparison. 4696 * @ingroup sorting_algorithms 4697 * @param __first An iterator. 4698 * @param __middle Another iterator. 4699 * @param __last Another iterator. 4700 * @param __comp A comparison functor. 4701 * @return Nothing. 4702 * 4703 * Sorts the smallest @p (__middle-__first) elements in the range 4704 * @p [__first,__last) and moves them to the range @p [__first,__middle). The 4705 * order of the remaining elements in the range @p [__middle,__last) is 4706 * undefined. 4707 * After the sort if @e i and @e j are iterators in the range 4708 * @p [__first,__middle) such that i precedes j and @e k is an iterator in 4709 * the range @p [__middle,__last) then @p *__comp(j,*i) and @p __comp(*k,*i) 4710 * are both false. 4711 */ 4712 template<typename _RandomAccessIterator, typename _Compare> 4713 inline void 4714 partial_sort(_RandomAccessIterator __first, 4715 _RandomAccessIterator __middle, 4716 _RandomAccessIterator __last, 4717 _Compare __comp) 4718 { 4719 // concept requirements 4720 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 4721 _RandomAccessIterator>) 4722 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 4723 typename iterator_traits<_RandomAccessIterator>::value_type, 4724 typename iterator_traits<_RandomAccessIterator>::value_type>) 4725 __glibcxx_requires_valid_range(__first, __middle); 4726 __glibcxx_requires_valid_range(__middle, __last); 4727 __glibcxx_requires_irreflexive_pred(__first, __last, __comp); 4728 4729 std::__partial_sort(__first, __middle, __last, 4730 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 4731 } 4732 4733 /** 4734 * @brief Sort a sequence just enough to find a particular position. 4735 * @ingroup sorting_algorithms 4736 * @param __first An iterator. 4737 * @param __nth Another iterator. 4738 * @param __last Another iterator. 4739 * @return Nothing. 4740 * 4741 * Rearranges the elements in the range @p [__first,__last) so that @p *__nth 4742 * is the same element that would have been in that position had the 4743 * whole sequence been sorted. The elements either side of @p *__nth are 4744 * not completely sorted, but for any iterator @e i in the range 4745 * @p [__first,__nth) and any iterator @e j in the range @p [__nth,__last) it 4746 * holds that *j < *i is false. 4747 */ 4748 template<typename _RandomAccessIterator> 4749 inline void 4750 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, 4751 _RandomAccessIterator __last) 4752 { 4753 // concept requirements 4754 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 4755 _RandomAccessIterator>) 4756 __glibcxx_function_requires(_LessThanComparableConcept< 4757 typename iterator_traits<_RandomAccessIterator>::value_type>) 4758 __glibcxx_requires_valid_range(__first, __nth); 4759 __glibcxx_requires_valid_range(__nth, __last); 4760 __glibcxx_requires_irreflexive(__first, __last); 4761 4762 if (__first == __last || __nth == __last) 4763 return; 4764 4765 std::__introselect(__first, __nth, __last, 4766 std::__lg(__last - __first) * 2, 4767 __gnu_cxx::__ops::__iter_less_iter()); 4768 } 4769 4770 /** 4771 * @brief Sort a sequence just enough to find a particular position 4772 * using a predicate for comparison. 4773 * @ingroup sorting_algorithms 4774 * @param __first An iterator. 4775 * @param __nth Another iterator. 4776 * @param __last Another iterator. 4777 * @param __comp A comparison functor. 4778 * @return Nothing. 4779 * 4780 * Rearranges the elements in the range @p [__first,__last) so that @p *__nth 4781 * is the same element that would have been in that position had the 4782 * whole sequence been sorted. The elements either side of @p *__nth are 4783 * not completely sorted, but for any iterator @e i in the range 4784 * @p [__first,__nth) and any iterator @e j in the range @p [__nth,__last) it 4785 * holds that @p __comp(*j,*i) is false. 4786 */ 4787 template<typename _RandomAccessIterator, typename _Compare> 4788 inline void 4789 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, 4790 _RandomAccessIterator __last, _Compare __comp) 4791 { 4792 // concept requirements 4793 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 4794 _RandomAccessIterator>) 4795 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 4796 typename iterator_traits<_RandomAccessIterator>::value_type, 4797 typename iterator_traits<_RandomAccessIterator>::value_type>) 4798 __glibcxx_requires_valid_range(__first, __nth); 4799 __glibcxx_requires_valid_range(__nth, __last); 4800 __glibcxx_requires_irreflexive_pred(__first, __last, __comp); 4801 4802 if (__first == __last || __nth == __last) 4803 return; 4804 4805 std::__introselect(__first, __nth, __last, 4806 std::__lg(__last - __first) * 2, 4807 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 4808 } 4809 4810 /** 4811 * @brief Sort the elements of a sequence. 4812 * @ingroup sorting_algorithms 4813 * @param __first An iterator. 4814 * @param __last Another iterator. 4815 * @return Nothing. 4816 * 4817 * Sorts the elements in the range @p [__first,__last) in ascending order, 4818 * such that for each iterator @e i in the range @p [__first,__last-1), 4819 * *(i+1)<*i is false. 4820 * 4821 * The relative ordering of equivalent elements is not preserved, use 4822 * @p stable_sort() if this is needed. 4823 */ 4824 template<typename _RandomAccessIterator> 4825 inline void 4826 sort(_RandomAccessIterator __first, _RandomAccessIterator __last) 4827 { 4828 // concept requirements 4829 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 4830 _RandomAccessIterator>) 4831 __glibcxx_function_requires(_LessThanComparableConcept< 4832 typename iterator_traits<_RandomAccessIterator>::value_type>) 4833 __glibcxx_requires_valid_range(__first, __last); 4834 __glibcxx_requires_irreflexive(__first, __last); 4835 4836 std::__sort(__first, __last, __gnu_cxx::__ops::__iter_less_iter()); 4837 } 4838 4839 /** 4840 * @brief Sort the elements of a sequence using a predicate for comparison. 4841 * @ingroup sorting_algorithms 4842 * @param __first An iterator. 4843 * @param __last Another iterator. 4844 * @param __comp A comparison functor. 4845 * @return Nothing. 4846 * 4847 * Sorts the elements in the range @p [__first,__last) in ascending order, 4848 * such that @p __comp(*(i+1),*i) is false for every iterator @e i in the 4849 * range @p [__first,__last-1). 4850 * 4851 * The relative ordering of equivalent elements is not preserved, use 4852 * @p stable_sort() if this is needed. 4853 */ 4854 template<typename _RandomAccessIterator, typename _Compare> 4855 inline void 4856 sort(_RandomAccessIterator __first, _RandomAccessIterator __last, 4857 _Compare __comp) 4858 { 4859 // concept requirements 4860 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 4861 _RandomAccessIterator>) 4862 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 4863 typename iterator_traits<_RandomAccessIterator>::value_type, 4864 typename iterator_traits<_RandomAccessIterator>::value_type>) 4865 __glibcxx_requires_valid_range(__first, __last); 4866 __glibcxx_requires_irreflexive_pred(__first, __last, __comp); 4867 4868 std::__sort(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp)); 4869 } 4870 4871 template<typename _InputIterator1, typename _InputIterator2, 4872 typename _OutputIterator, typename _Compare> 4873 _OutputIterator 4874 __merge(_InputIterator1 __first1, _InputIterator1 __last1, 4875 _InputIterator2 __first2, _InputIterator2 __last2, 4876 _OutputIterator __result, _Compare __comp) 4877 { 4878 while (__first1 != __last1 && __first2 != __last2) 4879 { 4880 if (__comp(__first2, __first1)) 4881 { 4882 *__result = *__first2; 4883 ++__first2; 4884 } 4885 else 4886 { 4887 *__result = *__first1; 4888 ++__first1; 4889 } 4890 ++__result; 4891 } 4892 return std::copy(__first2, __last2, 4893 std::copy(__first1, __last1, __result)); 4894 } 4895 4896 /** 4897 * @brief Merges two sorted ranges. 4898 * @ingroup sorting_algorithms 4899 * @param __first1 An iterator. 4900 * @param __first2 Another iterator. 4901 * @param __last1 Another iterator. 4902 * @param __last2 Another iterator. 4903 * @param __result An iterator pointing to the end of the merged range. 4904 * @return An iterator pointing to the first element <em>not less 4905 * than</em> @e val. 4906 * 4907 * Merges the ranges @p [__first1,__last1) and @p [__first2,__last2) into 4908 * the sorted range @p [__result, __result + (__last1-__first1) + 4909 * (__last2-__first2)). Both input ranges must be sorted, and the 4910 * output range must not overlap with either of the input ranges. 4911 * The sort is @e stable, that is, for equivalent elements in the 4912 * two ranges, elements from the first range will always come 4913 * before elements from the second. 4914 */ 4915 template<typename _InputIterator1, typename _InputIterator2, 4916 typename _OutputIterator> 4917 inline _OutputIterator 4918 merge(_InputIterator1 __first1, _InputIterator1 __last1, 4919 _InputIterator2 __first2, _InputIterator2 __last2, 4920 _OutputIterator __result) 4921 { 4922 // concept requirements 4923 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 4924 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 4925 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 4926 typename iterator_traits<_InputIterator1>::value_type>) 4927 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 4928 typename iterator_traits<_InputIterator2>::value_type>) 4929 __glibcxx_function_requires(_LessThanOpConcept< 4930 typename iterator_traits<_InputIterator2>::value_type, 4931 typename iterator_traits<_InputIterator1>::value_type>) 4932 __glibcxx_requires_sorted_set(__first1, __last1, __first2); 4933 __glibcxx_requires_sorted_set(__first2, __last2, __first1); 4934 __glibcxx_requires_irreflexive2(__first1, __last1); 4935 __glibcxx_requires_irreflexive2(__first2, __last2); 4936 4937 return _GLIBCXX_STD_A::__merge(__first1, __last1, 4938 __first2, __last2, __result, 4939 __gnu_cxx::__ops::__iter_less_iter()); 4940 } 4941 4942 /** 4943 * @brief Merges two sorted ranges. 4944 * @ingroup sorting_algorithms 4945 * @param __first1 An iterator. 4946 * @param __first2 Another iterator. 4947 * @param __last1 Another iterator. 4948 * @param __last2 Another iterator. 4949 * @param __result An iterator pointing to the end of the merged range. 4950 * @param __comp A functor to use for comparisons. 4951 * @return An iterator pointing to the first element "not less 4952 * than" @e val. 4953 * 4954 * Merges the ranges @p [__first1,__last1) and @p [__first2,__last2) into 4955 * the sorted range @p [__result, __result + (__last1-__first1) + 4956 * (__last2-__first2)). Both input ranges must be sorted, and the 4957 * output range must not overlap with either of the input ranges. 4958 * The sort is @e stable, that is, for equivalent elements in the 4959 * two ranges, elements from the first range will always come 4960 * before elements from the second. 4961 * 4962 * The comparison function should have the same effects on ordering as 4963 * the function used for the initial sort. 4964 */ 4965 template<typename _InputIterator1, typename _InputIterator2, 4966 typename _OutputIterator, typename _Compare> 4967 inline _OutputIterator 4968 merge(_InputIterator1 __first1, _InputIterator1 __last1, 4969 _InputIterator2 __first2, _InputIterator2 __last2, 4970 _OutputIterator __result, _Compare __comp) 4971 { 4972 // concept requirements 4973 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 4974 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 4975 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 4976 typename iterator_traits<_InputIterator1>::value_type>) 4977 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 4978 typename iterator_traits<_InputIterator2>::value_type>) 4979 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 4980 typename iterator_traits<_InputIterator2>::value_type, 4981 typename iterator_traits<_InputIterator1>::value_type>) 4982 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp); 4983 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp); 4984 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp); 4985 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp); 4986 4987 return _GLIBCXX_STD_A::__merge(__first1, __last1, 4988 __first2, __last2, __result, 4989 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 4990 } 4991 4992 template<typename _RandomAccessIterator, typename _Compare> 4993 inline void 4994 __stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, 4995 _Compare __comp) 4996 { 4997 typedef typename iterator_traits<_RandomAccessIterator>::value_type 4998 _ValueType; 4999 typedef typename iterator_traits<_RandomAccessIterator>::difference_type 5000 _DistanceType; 5001 5002 typedef _Temporary_buffer<_RandomAccessIterator, _ValueType> _TmpBuf; 5003 _TmpBuf __buf(__first, __last); 5004 5005 if (__buf.begin() == 0) 5006 std::__inplace_stable_sort(__first, __last, __comp); 5007 else 5008 std::__stable_sort_adaptive(__first, __last, __buf.begin(), 5009 _DistanceType(__buf.size()), __comp); 5010 } 5011 5012 /** 5013 * @brief Sort the elements of a sequence, preserving the relative order 5014 * of equivalent elements. 5015 * @ingroup sorting_algorithms 5016 * @param __first An iterator. 5017 * @param __last Another iterator. 5018 * @return Nothing. 5019 * 5020 * Sorts the elements in the range @p [__first,__last) in ascending order, 5021 * such that for each iterator @p i in the range @p [__first,__last-1), 5022 * @p *(i+1)<*i is false. 5023 * 5024 * The relative ordering of equivalent elements is preserved, so any two 5025 * elements @p x and @p y in the range @p [__first,__last) such that 5026 * @p x<y is false and @p y<x is false will have the same relative 5027 * ordering after calling @p stable_sort(). 5028 */ 5029 template<typename _RandomAccessIterator> 5030 inline void 5031 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last) 5032 { 5033 // concept requirements 5034 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 5035 _RandomAccessIterator>) 5036 __glibcxx_function_requires(_LessThanComparableConcept< 5037 typename iterator_traits<_RandomAccessIterator>::value_type>) 5038 __glibcxx_requires_valid_range(__first, __last); 5039 __glibcxx_requires_irreflexive(__first, __last); 5040 5041 _GLIBCXX_STD_A::__stable_sort(__first, __last, 5042 __gnu_cxx::__ops::__iter_less_iter()); 5043 } 5044 5045 /** 5046 * @brief Sort the elements of a sequence using a predicate for comparison, 5047 * preserving the relative order of equivalent elements. 5048 * @ingroup sorting_algorithms 5049 * @param __first An iterator. 5050 * @param __last Another iterator. 5051 * @param __comp A comparison functor. 5052 * @return Nothing. 5053 * 5054 * Sorts the elements in the range @p [__first,__last) in ascending order, 5055 * such that for each iterator @p i in the range @p [__first,__last-1), 5056 * @p __comp(*(i+1),*i) is false. 5057 * 5058 * The relative ordering of equivalent elements is preserved, so any two 5059 * elements @p x and @p y in the range @p [__first,__last) such that 5060 * @p __comp(x,y) is false and @p __comp(y,x) is false will have the same 5061 * relative ordering after calling @p stable_sort(). 5062 */ 5063 template<typename _RandomAccessIterator, typename _Compare> 5064 inline void 5065 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, 5066 _Compare __comp) 5067 { 5068 // concept requirements 5069 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 5070 _RandomAccessIterator>) 5071 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 5072 typename iterator_traits<_RandomAccessIterator>::value_type, 5073 typename iterator_traits<_RandomAccessIterator>::value_type>) 5074 __glibcxx_requires_valid_range(__first, __last); 5075 __glibcxx_requires_irreflexive_pred(__first, __last, __comp); 5076 5077 _GLIBCXX_STD_A::__stable_sort(__first, __last, 5078 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 5079 } 5080 5081 template<typename _InputIterator1, typename _InputIterator2, 5082 typename _OutputIterator, 5083 typename _Compare> 5084 _OutputIterator 5085 __set_union(_InputIterator1 __first1, _InputIterator1 __last1, 5086 _InputIterator2 __first2, _InputIterator2 __last2, 5087 _OutputIterator __result, _Compare __comp) 5088 { 5089 while (__first1 != __last1 && __first2 != __last2) 5090 { 5091 if (__comp(__first1, __first2)) 5092 { 5093 *__result = *__first1; 5094 ++__first1; 5095 } 5096 else if (__comp(__first2, __first1)) 5097 { 5098 *__result = *__first2; 5099 ++__first2; 5100 } 5101 else 5102 { 5103 *__result = *__first1; 5104 ++__first1; 5105 ++__first2; 5106 } 5107 ++__result; 5108 } 5109 return std::copy(__first2, __last2, 5110 std::copy(__first1, __last1, __result)); 5111 } 5112 5113 /** 5114 * @brief Return the union of two sorted ranges. 5115 * @ingroup set_algorithms 5116 * @param __first1 Start of first range. 5117 * @param __last1 End of first range. 5118 * @param __first2 Start of second range. 5119 * @param __last2 End of second range. 5120 * @return End of the output range. 5121 * @ingroup set_algorithms 5122 * 5123 * This operation iterates over both ranges, copying elements present in 5124 * each range in order to the output range. Iterators increment for each 5125 * range. When the current element of one range is less than the other, 5126 * that element is copied and the iterator advanced. If an element is 5127 * contained in both ranges, the element from the first range is copied and 5128 * both ranges advance. The output range may not overlap either input 5129 * range. 5130 */ 5131 template<typename _InputIterator1, typename _InputIterator2, 5132 typename _OutputIterator> 5133 inline _OutputIterator 5134 set_union(_InputIterator1 __first1, _InputIterator1 __last1, 5135 _InputIterator2 __first2, _InputIterator2 __last2, 5136 _OutputIterator __result) 5137 { 5138 // concept requirements 5139 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 5140 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 5141 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 5142 typename iterator_traits<_InputIterator1>::value_type>) 5143 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 5144 typename iterator_traits<_InputIterator2>::value_type>) 5145 __glibcxx_function_requires(_LessThanOpConcept< 5146 typename iterator_traits<_InputIterator1>::value_type, 5147 typename iterator_traits<_InputIterator2>::value_type>) 5148 __glibcxx_function_requires(_LessThanOpConcept< 5149 typename iterator_traits<_InputIterator2>::value_type, 5150 typename iterator_traits<_InputIterator1>::value_type>) 5151 __glibcxx_requires_sorted_set(__first1, __last1, __first2); 5152 __glibcxx_requires_sorted_set(__first2, __last2, __first1); 5153 __glibcxx_requires_irreflexive2(__first1, __last1); 5154 __glibcxx_requires_irreflexive2(__first2, __last2); 5155 5156 return _GLIBCXX_STD_A::__set_union(__first1, __last1, 5157 __first2, __last2, __result, 5158 __gnu_cxx::__ops::__iter_less_iter()); 5159 } 5160 5161 /** 5162 * @brief Return the union of two sorted ranges using a comparison functor. 5163 * @ingroup set_algorithms 5164 * @param __first1 Start of first range. 5165 * @param __last1 End of first range. 5166 * @param __first2 Start of second range. 5167 * @param __last2 End of second range. 5168 * @param __comp The comparison functor. 5169 * @return End of the output range. 5170 * @ingroup set_algorithms 5171 * 5172 * This operation iterates over both ranges, copying elements present in 5173 * each range in order to the output range. Iterators increment for each 5174 * range. When the current element of one range is less than the other 5175 * according to @p __comp, that element is copied and the iterator advanced. 5176 * If an equivalent element according to @p __comp is contained in both 5177 * ranges, the element from the first range is copied and both ranges 5178 * advance. The output range may not overlap either input range. 5179 */ 5180 template<typename _InputIterator1, typename _InputIterator2, 5181 typename _OutputIterator, typename _Compare> 5182 inline _OutputIterator 5183 set_union(_InputIterator1 __first1, _InputIterator1 __last1, 5184 _InputIterator2 __first2, _InputIterator2 __last2, 5185 _OutputIterator __result, _Compare __comp) 5186 { 5187 // concept requirements 5188 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 5189 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 5190 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 5191 typename iterator_traits<_InputIterator1>::value_type>) 5192 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 5193 typename iterator_traits<_InputIterator2>::value_type>) 5194 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 5195 typename iterator_traits<_InputIterator1>::value_type, 5196 typename iterator_traits<_InputIterator2>::value_type>) 5197 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 5198 typename iterator_traits<_InputIterator2>::value_type, 5199 typename iterator_traits<_InputIterator1>::value_type>) 5200 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp); 5201 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp); 5202 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp); 5203 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp); 5204 5205 return _GLIBCXX_STD_A::__set_union(__first1, __last1, 5206 __first2, __last2, __result, 5207 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 5208 } 5209 5210 template<typename _InputIterator1, typename _InputIterator2, 5211 typename _OutputIterator, 5212 typename _Compare> 5213 _OutputIterator 5214 __set_intersection(_InputIterator1 __first1, _InputIterator1 __last1, 5215 _InputIterator2 __first2, _InputIterator2 __last2, 5216 _OutputIterator __result, _Compare __comp) 5217 { 5218 while (__first1 != __last1 && __first2 != __last2) 5219 if (__comp(__first1, __first2)) 5220 ++__first1; 5221 else if (__comp(__first2, __first1)) 5222 ++__first2; 5223 else 5224 { 5225 *__result = *__first1; 5226 ++__first1; 5227 ++__first2; 5228 ++__result; 5229 } 5230 return __result; 5231 } 5232 5233 /** 5234 * @brief Return the intersection of two sorted ranges. 5235 * @ingroup set_algorithms 5236 * @param __first1 Start of first range. 5237 * @param __last1 End of first range. 5238 * @param __first2 Start of second range. 5239 * @param __last2 End of second range. 5240 * @return End of the output range. 5241 * @ingroup set_algorithms 5242 * 5243 * This operation iterates over both ranges, copying elements present in 5244 * both ranges in order to the output range. Iterators increment for each 5245 * range. When the current element of one range is less than the other, 5246 * that iterator advances. If an element is contained in both ranges, the 5247 * element from the first range is copied and both ranges advance. The 5248 * output range may not overlap either input range. 5249 */ 5250 template<typename _InputIterator1, typename _InputIterator2, 5251 typename _OutputIterator> 5252 inline _OutputIterator 5253 set_intersection(_InputIterator1 __first1, _InputIterator1 __last1, 5254 _InputIterator2 __first2, _InputIterator2 __last2, 5255 _OutputIterator __result) 5256 { 5257 // concept requirements 5258 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 5259 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 5260 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 5261 typename iterator_traits<_InputIterator1>::value_type>) 5262 __glibcxx_function_requires(_LessThanOpConcept< 5263 typename iterator_traits<_InputIterator1>::value_type, 5264 typename iterator_traits<_InputIterator2>::value_type>) 5265 __glibcxx_function_requires(_LessThanOpConcept< 5266 typename iterator_traits<_InputIterator2>::value_type, 5267 typename iterator_traits<_InputIterator1>::value_type>) 5268 __glibcxx_requires_sorted_set(__first1, __last1, __first2); 5269 __glibcxx_requires_sorted_set(__first2, __last2, __first1); 5270 __glibcxx_requires_irreflexive2(__first1, __last1); 5271 __glibcxx_requires_irreflexive2(__first2, __last2); 5272 5273 return _GLIBCXX_STD_A::__set_intersection(__first1, __last1, 5274 __first2, __last2, __result, 5275 __gnu_cxx::__ops::__iter_less_iter()); 5276 } 5277 5278 /** 5279 * @brief Return the intersection of two sorted ranges using comparison 5280 * functor. 5281 * @ingroup set_algorithms 5282 * @param __first1 Start of first range. 5283 * @param __last1 End of first range. 5284 * @param __first2 Start of second range. 5285 * @param __last2 End of second range. 5286 * @param __comp The comparison functor. 5287 * @return End of the output range. 5288 * @ingroup set_algorithms 5289 * 5290 * This operation iterates over both ranges, copying elements present in 5291 * both ranges in order to the output range. Iterators increment for each 5292 * range. When the current element of one range is less than the other 5293 * according to @p __comp, that iterator advances. If an element is 5294 * contained in both ranges according to @p __comp, the element from the 5295 * first range is copied and both ranges advance. The output range may not 5296 * overlap either input range. 5297 */ 5298 template<typename _InputIterator1, typename _InputIterator2, 5299 typename _OutputIterator, typename _Compare> 5300 inline _OutputIterator 5301 set_intersection(_InputIterator1 __first1, _InputIterator1 __last1, 5302 _InputIterator2 __first2, _InputIterator2 __last2, 5303 _OutputIterator __result, _Compare __comp) 5304 { 5305 // concept requirements 5306 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 5307 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 5308 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 5309 typename iterator_traits<_InputIterator1>::value_type>) 5310 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 5311 typename iterator_traits<_InputIterator1>::value_type, 5312 typename iterator_traits<_InputIterator2>::value_type>) 5313 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 5314 typename iterator_traits<_InputIterator2>::value_type, 5315 typename iterator_traits<_InputIterator1>::value_type>) 5316 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp); 5317 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp); 5318 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp); 5319 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp); 5320 5321 return _GLIBCXX_STD_A::__set_intersection(__first1, __last1, 5322 __first2, __last2, __result, 5323 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 5324 } 5325 5326 template<typename _InputIterator1, typename _InputIterator2, 5327 typename _OutputIterator, 5328 typename _Compare> 5329 _OutputIterator 5330 __set_difference(_InputIterator1 __first1, _InputIterator1 __last1, 5331 _InputIterator2 __first2, _InputIterator2 __last2, 5332 _OutputIterator __result, _Compare __comp) 5333 { 5334 while (__first1 != __last1 && __first2 != __last2) 5335 if (__comp(__first1, __first2)) 5336 { 5337 *__result = *__first1; 5338 ++__first1; 5339 ++__result; 5340 } 5341 else if (__comp(__first2, __first1)) 5342 ++__first2; 5343 else 5344 { 5345 ++__first1; 5346 ++__first2; 5347 } 5348 return std::copy(__first1, __last1, __result); 5349 } 5350 5351 /** 5352 * @brief Return the difference of two sorted ranges. 5353 * @ingroup set_algorithms 5354 * @param __first1 Start of first range. 5355 * @param __last1 End of first range. 5356 * @param __first2 Start of second range. 5357 * @param __last2 End of second range. 5358 * @return End of the output range. 5359 * @ingroup set_algorithms 5360 * 5361 * This operation iterates over both ranges, copying elements present in 5362 * the first range but not the second in order to the output range. 5363 * Iterators increment for each range. When the current element of the 5364 * first range is less than the second, that element is copied and the 5365 * iterator advances. If the current element of the second range is less, 5366 * the iterator advances, but no element is copied. If an element is 5367 * contained in both ranges, no elements are copied and both ranges 5368 * advance. The output range may not overlap either input range. 5369 */ 5370 template<typename _InputIterator1, typename _InputIterator2, 5371 typename _OutputIterator> 5372 inline _OutputIterator 5373 set_difference(_InputIterator1 __first1, _InputIterator1 __last1, 5374 _InputIterator2 __first2, _InputIterator2 __last2, 5375 _OutputIterator __result) 5376 { 5377 // concept requirements 5378 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 5379 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 5380 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 5381 typename iterator_traits<_InputIterator1>::value_type>) 5382 __glibcxx_function_requires(_LessThanOpConcept< 5383 typename iterator_traits<_InputIterator1>::value_type, 5384 typename iterator_traits<_InputIterator2>::value_type>) 5385 __glibcxx_function_requires(_LessThanOpConcept< 5386 typename iterator_traits<_InputIterator2>::value_type, 5387 typename iterator_traits<_InputIterator1>::value_type>) 5388 __glibcxx_requires_sorted_set(__first1, __last1, __first2); 5389 __glibcxx_requires_sorted_set(__first2, __last2, __first1); 5390 __glibcxx_requires_irreflexive2(__first1, __last1); 5391 __glibcxx_requires_irreflexive2(__first2, __last2); 5392 5393 return _GLIBCXX_STD_A::__set_difference(__first1, __last1, 5394 __first2, __last2, __result, 5395 __gnu_cxx::__ops::__iter_less_iter()); 5396 } 5397 5398 /** 5399 * @brief Return the difference of two sorted ranges using comparison 5400 * functor. 5401 * @ingroup set_algorithms 5402 * @param __first1 Start of first range. 5403 * @param __last1 End of first range. 5404 * @param __first2 Start of second range. 5405 * @param __last2 End of second range. 5406 * @param __comp The comparison functor. 5407 * @return End of the output range. 5408 * @ingroup set_algorithms 5409 * 5410 * This operation iterates over both ranges, copying elements present in 5411 * the first range but not the second in order to the output range. 5412 * Iterators increment for each range. When the current element of the 5413 * first range is less than the second according to @p __comp, that element 5414 * is copied and the iterator advances. If the current element of the 5415 * second range is less, no element is copied and the iterator advances. 5416 * If an element is contained in both ranges according to @p __comp, no 5417 * elements are copied and both ranges advance. The output range may not 5418 * overlap either input range. 5419 */ 5420 template<typename _InputIterator1, typename _InputIterator2, 5421 typename _OutputIterator, typename _Compare> 5422 inline _OutputIterator 5423 set_difference(_InputIterator1 __first1, _InputIterator1 __last1, 5424 _InputIterator2 __first2, _InputIterator2 __last2, 5425 _OutputIterator __result, _Compare __comp) 5426 { 5427 // concept requirements 5428 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 5429 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 5430 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 5431 typename iterator_traits<_InputIterator1>::value_type>) 5432 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 5433 typename iterator_traits<_InputIterator1>::value_type, 5434 typename iterator_traits<_InputIterator2>::value_type>) 5435 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 5436 typename iterator_traits<_InputIterator2>::value_type, 5437 typename iterator_traits<_InputIterator1>::value_type>) 5438 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp); 5439 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp); 5440 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp); 5441 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp); 5442 5443 return _GLIBCXX_STD_A::__set_difference(__first1, __last1, 5444 __first2, __last2, __result, 5445 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 5446 } 5447 5448 template<typename _InputIterator1, typename _InputIterator2, 5449 typename _OutputIterator, 5450 typename _Compare> 5451 _OutputIterator 5452 __set_symmetric_difference(_InputIterator1 __first1, 5453 _InputIterator1 __last1, 5454 _InputIterator2 __first2, 5455 _InputIterator2 __last2, 5456 _OutputIterator __result, 5457 _Compare __comp) 5458 { 5459 while (__first1 != __last1 && __first2 != __last2) 5460 if (__comp(__first1, __first2)) 5461 { 5462 *__result = *__first1; 5463 ++__first1; 5464 ++__result; 5465 } 5466 else if (__comp(__first2, __first1)) 5467 { 5468 *__result = *__first2; 5469 ++__first2; 5470 ++__result; 5471 } 5472 else 5473 { 5474 ++__first1; 5475 ++__first2; 5476 } 5477 return std::copy(__first2, __last2, 5478 std::copy(__first1, __last1, __result)); 5479 } 5480 5481 /** 5482 * @brief Return the symmetric difference of two sorted ranges. 5483 * @ingroup set_algorithms 5484 * @param __first1 Start of first range. 5485 * @param __last1 End of first range. 5486 * @param __first2 Start of second range. 5487 * @param __last2 End of second range. 5488 * @return End of the output range. 5489 * @ingroup set_algorithms 5490 * 5491 * This operation iterates over both ranges, copying elements present in 5492 * one range but not the other in order to the output range. Iterators 5493 * increment for each range. When the current element of one range is less 5494 * than the other, that element is copied and the iterator advances. If an 5495 * element is contained in both ranges, no elements are copied and both 5496 * ranges advance. The output range may not overlap either input range. 5497 */ 5498 template<typename _InputIterator1, typename _InputIterator2, 5499 typename _OutputIterator> 5500 inline _OutputIterator 5501 set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1, 5502 _InputIterator2 __first2, _InputIterator2 __last2, 5503 _OutputIterator __result) 5504 { 5505 // concept requirements 5506 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 5507 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 5508 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 5509 typename iterator_traits<_InputIterator1>::value_type>) 5510 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 5511 typename iterator_traits<_InputIterator2>::value_type>) 5512 __glibcxx_function_requires(_LessThanOpConcept< 5513 typename iterator_traits<_InputIterator1>::value_type, 5514 typename iterator_traits<_InputIterator2>::value_type>) 5515 __glibcxx_function_requires(_LessThanOpConcept< 5516 typename iterator_traits<_InputIterator2>::value_type, 5517 typename iterator_traits<_InputIterator1>::value_type>) 5518 __glibcxx_requires_sorted_set(__first1, __last1, __first2); 5519 __glibcxx_requires_sorted_set(__first2, __last2, __first1); 5520 __glibcxx_requires_irreflexive2(__first1, __last1); 5521 __glibcxx_requires_irreflexive2(__first2, __last2); 5522 5523 return _GLIBCXX_STD_A::__set_symmetric_difference(__first1, __last1, 5524 __first2, __last2, __result, 5525 __gnu_cxx::__ops::__iter_less_iter()); 5526 } 5527 5528 /** 5529 * @brief Return the symmetric difference of two sorted ranges using 5530 * comparison functor. 5531 * @ingroup set_algorithms 5532 * @param __first1 Start of first range. 5533 * @param __last1 End of first range. 5534 * @param __first2 Start of second range. 5535 * @param __last2 End of second range. 5536 * @param __comp The comparison functor. 5537 * @return End of the output range. 5538 * @ingroup set_algorithms 5539 * 5540 * This operation iterates over both ranges, copying elements present in 5541 * one range but not the other in order to the output range. Iterators 5542 * increment for each range. When the current element of one range is less 5543 * than the other according to @p comp, that element is copied and the 5544 * iterator advances. If an element is contained in both ranges according 5545 * to @p __comp, no elements are copied and both ranges advance. The output 5546 * range may not overlap either input range. 5547 */ 5548 template<typename _InputIterator1, typename _InputIterator2, 5549 typename _OutputIterator, typename _Compare> 5550 inline _OutputIterator 5551 set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1, 5552 _InputIterator2 __first2, _InputIterator2 __last2, 5553 _OutputIterator __result, 5554 _Compare __comp) 5555 { 5556 // concept requirements 5557 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 5558 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 5559 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 5560 typename iterator_traits<_InputIterator1>::value_type>) 5561 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 5562 typename iterator_traits<_InputIterator2>::value_type>) 5563 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 5564 typename iterator_traits<_InputIterator1>::value_type, 5565 typename iterator_traits<_InputIterator2>::value_type>) 5566 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 5567 typename iterator_traits<_InputIterator2>::value_type, 5568 typename iterator_traits<_InputIterator1>::value_type>) 5569 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp); 5570 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp); 5571 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp); 5572 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp); 5573 5574 return _GLIBCXX_STD_A::__set_symmetric_difference(__first1, __last1, 5575 __first2, __last2, __result, 5576 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 5577 } 5578 5579 template<typename _ForwardIterator, typename _Compare> 5580 _GLIBCXX14_CONSTEXPR 5581 _ForwardIterator 5582 __min_element(_ForwardIterator __first, _ForwardIterator __last, 5583 _Compare __comp) 5584 { 5585 if (__first == __last) 5586 return __first; 5587 _ForwardIterator __result = __first; 5588 while (++__first != __last) 5589 if (__comp(__first, __result)) 5590 __result = __first; 5591 return __result; 5592 } 5593 5594 /** 5595 * @brief Return the minimum element in a range. 5596 * @ingroup sorting_algorithms 5597 * @param __first Start of range. 5598 * @param __last End of range. 5599 * @return Iterator referencing the first instance of the smallest value. 5600 */ 5601 template<typename _ForwardIterator> 5602 _GLIBCXX14_CONSTEXPR 5603 _ForwardIterator 5604 inline min_element(_ForwardIterator __first, _ForwardIterator __last) 5605 { 5606 // concept requirements 5607 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 5608 __glibcxx_function_requires(_LessThanComparableConcept< 5609 typename iterator_traits<_ForwardIterator>::value_type>) 5610 __glibcxx_requires_valid_range(__first, __last); 5611 __glibcxx_requires_irreflexive(__first, __last); 5612 5613 return _GLIBCXX_STD_A::__min_element(__first, __last, 5614 __gnu_cxx::__ops::__iter_less_iter()); 5615 } 5616 5617 /** 5618 * @brief Return the minimum element in a range using comparison functor. 5619 * @ingroup sorting_algorithms 5620 * @param __first Start of range. 5621 * @param __last End of range. 5622 * @param __comp Comparison functor. 5623 * @return Iterator referencing the first instance of the smallest value 5624 * according to __comp. 5625 */ 5626 template<typename _ForwardIterator, typename _Compare> 5627 _GLIBCXX14_CONSTEXPR 5628 inline _ForwardIterator 5629 min_element(_ForwardIterator __first, _ForwardIterator __last, 5630 _Compare __comp) 5631 { 5632 // concept requirements 5633 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 5634 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 5635 typename iterator_traits<_ForwardIterator>::value_type, 5636 typename iterator_traits<_ForwardIterator>::value_type>) 5637 __glibcxx_requires_valid_range(__first, __last); 5638 __glibcxx_requires_irreflexive_pred(__first, __last, __comp); 5639 5640 return _GLIBCXX_STD_A::__min_element(__first, __last, 5641 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 5642 } 5643 5644 template<typename _ForwardIterator, typename _Compare> 5645 _GLIBCXX14_CONSTEXPR 5646 _ForwardIterator 5647 __max_element(_ForwardIterator __first, _ForwardIterator __last, 5648 _Compare __comp) 5649 { 5650 if (__first == __last) return __first; 5651 _ForwardIterator __result = __first; 5652 while (++__first != __last) 5653 if (__comp(__result, __first)) 5654 __result = __first; 5655 return __result; 5656 } 5657 5658 /** 5659 * @brief Return the maximum element in a range. 5660 * @ingroup sorting_algorithms 5661 * @param __first Start of range. 5662 * @param __last End of range. 5663 * @return Iterator referencing the first instance of the largest value. 5664 */ 5665 template<typename _ForwardIterator> 5666 _GLIBCXX14_CONSTEXPR 5667 inline _ForwardIterator 5668 max_element(_ForwardIterator __first, _ForwardIterator __last) 5669 { 5670 // concept requirements 5671 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 5672 __glibcxx_function_requires(_LessThanComparableConcept< 5673 typename iterator_traits<_ForwardIterator>::value_type>) 5674 __glibcxx_requires_valid_range(__first, __last); 5675 __glibcxx_requires_irreflexive(__first, __last); 5676 5677 return _GLIBCXX_STD_A::__max_element(__first, __last, 5678 __gnu_cxx::__ops::__iter_less_iter()); 5679 } 5680 5681 /** 5682 * @brief Return the maximum element in a range using comparison functor. 5683 * @ingroup sorting_algorithms 5684 * @param __first Start of range. 5685 * @param __last End of range. 5686 * @param __comp Comparison functor. 5687 * @return Iterator referencing the first instance of the largest value 5688 * according to __comp. 5689 */ 5690 template<typename _ForwardIterator, typename _Compare> 5691 _GLIBCXX14_CONSTEXPR 5692 inline _ForwardIterator 5693 max_element(_ForwardIterator __first, _ForwardIterator __last, 5694 _Compare __comp) 5695 { 5696 // concept requirements 5697 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 5698 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 5699 typename iterator_traits<_ForwardIterator>::value_type, 5700 typename iterator_traits<_ForwardIterator>::value_type>) 5701 __glibcxx_requires_valid_range(__first, __last); 5702 __glibcxx_requires_irreflexive_pred(__first, __last, __comp); 5703 5704 return _GLIBCXX_STD_A::__max_element(__first, __last, 5705 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 5706 } 5707 5708 #if __cplusplus >= 201402L 5709 /// Reservoir sampling algorithm. 5710 template<typename _InputIterator, typename _RandomAccessIterator, 5711 typename _Size, typename _UniformRandomBitGenerator> 5712 _RandomAccessIterator 5713 __sample(_InputIterator __first, _InputIterator __last, input_iterator_tag, 5714 _RandomAccessIterator __out, random_access_iterator_tag, 5715 _Size __n, _UniformRandomBitGenerator&& __g) 5716 { 5717 using __distrib_type = uniform_int_distribution<_Size>; 5718 using __param_type = typename __distrib_type::param_type; 5719 __distrib_type __d{}; 5720 _Size __sample_sz = 0; 5721 while (__first != __last && __sample_sz != __n) 5722 { 5723 __out[__sample_sz++] = *__first; 5724 ++__first; 5725 } 5726 for (auto __pop_sz = __sample_sz; __first != __last; 5727 ++__first, (void) ++__pop_sz) 5728 { 5729 const auto __k = __d(__g, __param_type{0, __pop_sz}); 5730 if (__k < __n) 5731 __out[__k] = *__first; 5732 } 5733 return __out + __sample_sz; 5734 } 5735 5736 /// Selection sampling algorithm. 5737 template<typename _ForwardIterator, typename _OutputIterator, typename _Cat, 5738 typename _Size, typename _UniformRandomBitGenerator> 5739 _OutputIterator 5740 __sample(_ForwardIterator __first, _ForwardIterator __last, 5741 forward_iterator_tag, 5742 _OutputIterator __out, _Cat, 5743 _Size __n, _UniformRandomBitGenerator&& __g) 5744 { 5745 using __distrib_type = uniform_int_distribution<_Size>; 5746 using __param_type = typename __distrib_type::param_type; 5747 using _USize = make_unsigned_t<_Size>; 5748 using _Gen = remove_reference_t<_UniformRandomBitGenerator>; 5749 using __uc_type = common_type_t<typename _Gen::result_type, _USize>; 5750 5751 __distrib_type __d{}; 5752 _Size __unsampled_sz = std::distance(__first, __last); 5753 __n = std::min(__n, __unsampled_sz); 5754 5755 // If possible, we use __gen_two_uniform_ints to efficiently produce 5756 // two random numbers using a single distribution invocation: 5757 5758 const __uc_type __urngrange = __g.max() - __g.min(); 5759 if (__urngrange / __uc_type(__unsampled_sz) >= __uc_type(__unsampled_sz)) 5760 // I.e. (__urngrange >= __unsampled_sz * __unsampled_sz) but without 5761 // wrapping issues. 5762 { 5763 while (__n != 0 && __unsampled_sz >= 2) 5764 { 5765 const pair<_Size, _Size> __p = 5766 __gen_two_uniform_ints(__unsampled_sz, __unsampled_sz - 1, __g); 5767 5768 --__unsampled_sz; 5769 if (__p.first < __n) 5770 { 5771 *__out++ = *__first; 5772 --__n; 5773 } 5774 5775 ++__first; 5776 5777 if (__n == 0) break; 5778 5779 --__unsampled_sz; 5780 if (__p.second < __n) 5781 { 5782 *__out++ = *__first; 5783 --__n; 5784 } 5785 5786 ++__first; 5787 } 5788 } 5789 5790 // The loop above is otherwise equivalent to this one-at-a-time version: 5791 5792 for (; __n != 0; ++__first) 5793 if (__d(__g, __param_type{0, --__unsampled_sz}) < __n) 5794 { 5795 *__out++ = *__first; 5796 --__n; 5797 } 5798 return __out; 5799 } 5800 5801 #if __cplusplus > 201402L 5802 #define __cpp_lib_sample 201603 5803 /// Take a random sample from a population. 5804 template<typename _PopulationIterator, typename _SampleIterator, 5805 typename _Distance, typename _UniformRandomBitGenerator> 5806 _SampleIterator 5807 sample(_PopulationIterator __first, _PopulationIterator __last, 5808 _SampleIterator __out, _Distance __n, 5809 _UniformRandomBitGenerator&& __g) 5810 { 5811 using __pop_cat = typename 5812 std::iterator_traits<_PopulationIterator>::iterator_category; 5813 using __samp_cat = typename 5814 std::iterator_traits<_SampleIterator>::iterator_category; 5815 5816 static_assert( 5817 __or_<is_convertible<__pop_cat, forward_iterator_tag>, 5818 is_convertible<__samp_cat, random_access_iterator_tag>>::value, 5819 "output range must use a RandomAccessIterator when input range" 5820 " does not meet the ForwardIterator requirements"); 5821 5822 static_assert(is_integral<_Distance>::value, 5823 "sample size must be an integer type"); 5824 5825 typename iterator_traits<_PopulationIterator>::difference_type __d = __n; 5826 return _GLIBCXX_STD_A:: 5827 __sample(__first, __last, __pop_cat{}, __out, __samp_cat{}, __d, 5828 std::forward<_UniformRandomBitGenerator>(__g)); 5829 } 5830 #endif // C++17 5831 #endif // C++14 5832 5833 _GLIBCXX_END_NAMESPACE_ALGO 5834 } // namespace std 5835 5836 #endif /* _STL_ALGO_H */ 5837