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