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