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