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