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