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