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