libstdc++
|
00001 // Algorithm implementation -*- C++ -*- 00002 00003 // Copyright (C) 2001-2017 Free Software Foundation, Inc. 00004 // 00005 // This file is part of the GNU ISO C++ Library. This library is free 00006 // software; you can redistribute it and/or modify it under the 00007 // terms of the GNU General Public License as published by the 00008 // Free Software Foundation; either version 3, or (at your option) 00009 // any later version. 00010 00011 // This library is distributed in the hope that it will be useful, 00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00014 // GNU General Public License for more details. 00015 00016 // Under Section 7 of GPL version 3, you are granted additional 00017 // permissions described in the GCC Runtime Library Exception, version 00018 // 3.1, as published by the Free Software Foundation. 00019 00020 // You should have received a copy of the GNU General Public License and 00021 // a copy of the GCC Runtime Library Exception along with this program; 00022 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 00023 // <http://www.gnu.org/licenses/>. 00024 00025 /* 00026 * 00027 * Copyright (c) 1994 00028 * Hewlett-Packard Company 00029 * 00030 * Permission to use, copy, modify, distribute and sell this software 00031 * and its documentation for any purpose is hereby granted without fee, 00032 * provided that the above copyright notice appear in all copies and 00033 * that both that copyright notice and this permission notice appear 00034 * in supporting documentation. Hewlett-Packard Company makes no 00035 * representations about the suitability of this software for any 00036 * purpose. It is provided "as is" without express or implied warranty. 00037 * 00038 * 00039 * Copyright (c) 1996 00040 * Silicon Graphics Computer Systems, Inc. 00041 * 00042 * Permission to use, copy, modify, distribute and sell this software 00043 * and its documentation for any purpose is hereby granted without fee, 00044 * provided that the above copyright notice appear in all copies and 00045 * that both that copyright notice and this permission notice appear 00046 * in supporting documentation. Silicon Graphics makes no 00047 * representations about the suitability of this software for any 00048 * purpose. It is provided "as is" without express or implied warranty. 00049 */ 00050 00051 /** @file bits/stl_algo.h 00052 * This is an internal header file, included by other library headers. 00053 * Do not attempt to use it directly. @headername{algorithm} 00054 */ 00055 00056 #ifndef _STL_ALGO_H 00057 #define _STL_ALGO_H 1 00058 00059 #include <cstdlib> // for rand 00060 #include <bits/algorithmfwd.h> 00061 #include <bits/stl_heap.h> 00062 #include <bits/stl_tempbuf.h> // for _Temporary_buffer 00063 #include <bits/predefined_ops.h> 00064 00065 #if __cplusplus >= 201103L 00066 #include <bits/uniform_int_dist.h> 00067 #endif 00068 00069 // See concept_check.h for the __glibcxx_*_requires macros. 00070 00071 namespace std _GLIBCXX_VISIBILITY(default) 00072 { 00073 _GLIBCXX_BEGIN_NAMESPACE_VERSION 00074 00075 /// Swaps the median value of *__a, *__b and *__c under __comp to *__result 00076 template<typename _Iterator, typename _Compare> 00077 void 00078 __move_median_to_first(_Iterator __result,_Iterator __a, _Iterator __b, 00079 _Iterator __c, _Compare __comp) 00080 { 00081 if (__comp(__a, __b)) 00082 { 00083 if (__comp(__b, __c)) 00084 std::iter_swap(__result, __b); 00085 else if (__comp(__a, __c)) 00086 std::iter_swap(__result, __c); 00087 else 00088 std::iter_swap(__result, __a); 00089 } 00090 else if (__comp(__a, __c)) 00091 std::iter_swap(__result, __a); 00092 else if (__comp(__b, __c)) 00093 std::iter_swap(__result, __c); 00094 else 00095 std::iter_swap(__result, __b); 00096 } 00097 00098 /// This is an overload used by find algos for the Input Iterator case. 00099 template<typename _InputIterator, typename _Predicate> 00100 inline _InputIterator 00101 __find_if(_InputIterator __first, _InputIterator __last, 00102 _Predicate __pred, input_iterator_tag) 00103 { 00104 while (__first != __last && !__pred(__first)) 00105 ++__first; 00106 return __first; 00107 } 00108 00109 /// This is an overload used by find algos for the RAI case. 00110 template<typename _RandomAccessIterator, typename _Predicate> 00111 _RandomAccessIterator 00112 __find_if(_RandomAccessIterator __first, _RandomAccessIterator __last, 00113 _Predicate __pred, random_access_iterator_tag) 00114 { 00115 typename iterator_traits<_RandomAccessIterator>::difference_type 00116 __trip_count = (__last - __first) >> 2; 00117 00118 for (; __trip_count > 0; --__trip_count) 00119 { 00120 if (__pred(__first)) 00121 return __first; 00122 ++__first; 00123 00124 if (__pred(__first)) 00125 return __first; 00126 ++__first; 00127 00128 if (__pred(__first)) 00129 return __first; 00130 ++__first; 00131 00132 if (__pred(__first)) 00133 return __first; 00134 ++__first; 00135 } 00136 00137 switch (__last - __first) 00138 { 00139 case 3: 00140 if (__pred(__first)) 00141 return __first; 00142 ++__first; 00143 case 2: 00144 if (__pred(__first)) 00145 return __first; 00146 ++__first; 00147 case 1: 00148 if (__pred(__first)) 00149 return __first; 00150 ++__first; 00151 case 0: 00152 default: 00153 return __last; 00154 } 00155 } 00156 00157 template<typename _Iterator, typename _Predicate> 00158 inline _Iterator 00159 __find_if(_Iterator __first, _Iterator __last, _Predicate __pred) 00160 { 00161 return __find_if(__first, __last, __pred, 00162 std::__iterator_category(__first)); 00163 } 00164 00165 /// Provided for stable_partition to use. 00166 template<typename _InputIterator, typename _Predicate> 00167 inline _InputIterator 00168 __find_if_not(_InputIterator __first, _InputIterator __last, 00169 _Predicate __pred) 00170 { 00171 return std::__find_if(__first, __last, 00172 __gnu_cxx::__ops::__negate(__pred), 00173 std::__iterator_category(__first)); 00174 } 00175 00176 /// Like find_if_not(), but uses and updates a count of the 00177 /// remaining range length instead of comparing against an end 00178 /// iterator. 00179 template<typename _InputIterator, typename _Predicate, typename _Distance> 00180 _InputIterator 00181 __find_if_not_n(_InputIterator __first, _Distance& __len, _Predicate __pred) 00182 { 00183 for (; __len; --__len, ++__first) 00184 if (!__pred(__first)) 00185 break; 00186 return __first; 00187 } 00188 00189 // set_difference 00190 // set_intersection 00191 // set_symmetric_difference 00192 // set_union 00193 // for_each 00194 // find 00195 // find_if 00196 // find_first_of 00197 // adjacent_find 00198 // count 00199 // count_if 00200 // search 00201 00202 template<typename _ForwardIterator1, typename _ForwardIterator2, 00203 typename _BinaryPredicate> 00204 _ForwardIterator1 00205 __search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 00206 _ForwardIterator2 __first2, _ForwardIterator2 __last2, 00207 _BinaryPredicate __predicate) 00208 { 00209 // Test for empty ranges 00210 if (__first1 == __last1 || __first2 == __last2) 00211 return __first1; 00212 00213 // Test for a pattern of length 1. 00214 _ForwardIterator2 __p1(__first2); 00215 if (++__p1 == __last2) 00216 return std::__find_if(__first1, __last1, 00217 __gnu_cxx::__ops::__iter_comp_iter(__predicate, __first2)); 00218 00219 // General case. 00220 _ForwardIterator2 __p; 00221 _ForwardIterator1 __current = __first1; 00222 00223 for (;;) 00224 { 00225 __first1 = 00226 std::__find_if(__first1, __last1, 00227 __gnu_cxx::__ops::__iter_comp_iter(__predicate, __first2)); 00228 00229 if (__first1 == __last1) 00230 return __last1; 00231 00232 __p = __p1; 00233 __current = __first1; 00234 if (++__current == __last1) 00235 return __last1; 00236 00237 while (__predicate(__current, __p)) 00238 { 00239 if (++__p == __last2) 00240 return __first1; 00241 if (++__current == __last1) 00242 return __last1; 00243 } 00244 ++__first1; 00245 } 00246 return __first1; 00247 } 00248 00249 // search_n 00250 00251 /** 00252 * This is an helper function for search_n overloaded for forward iterators. 00253 */ 00254 template<typename _ForwardIterator, typename _Integer, 00255 typename _UnaryPredicate> 00256 _ForwardIterator 00257 __search_n_aux(_ForwardIterator __first, _ForwardIterator __last, 00258 _Integer __count, _UnaryPredicate __unary_pred, 00259 std::forward_iterator_tag) 00260 { 00261 __first = std::__find_if(__first, __last, __unary_pred); 00262 while (__first != __last) 00263 { 00264 typename iterator_traits<_ForwardIterator>::difference_type 00265 __n = __count; 00266 _ForwardIterator __i = __first; 00267 ++__i; 00268 while (__i != __last && __n != 1 && __unary_pred(__i)) 00269 { 00270 ++__i; 00271 --__n; 00272 } 00273 if (__n == 1) 00274 return __first; 00275 if (__i == __last) 00276 return __last; 00277 __first = std::__find_if(++__i, __last, __unary_pred); 00278 } 00279 return __last; 00280 } 00281 00282 /** 00283 * This is an helper function for search_n overloaded for random access 00284 * iterators. 00285 */ 00286 template<typename _RandomAccessIter, typename _Integer, 00287 typename _UnaryPredicate> 00288 _RandomAccessIter 00289 __search_n_aux(_RandomAccessIter __first, _RandomAccessIter __last, 00290 _Integer __count, _UnaryPredicate __unary_pred, 00291 std::random_access_iterator_tag) 00292 { 00293 typedef typename std::iterator_traits<_RandomAccessIter>::difference_type 00294 _DistanceType; 00295 00296 _DistanceType __tailSize = __last - __first; 00297 _DistanceType __remainder = __count; 00298 00299 while (__remainder <= __tailSize) // the main loop... 00300 { 00301 __first += __remainder; 00302 __tailSize -= __remainder; 00303 // __first here is always pointing to one past the last element of 00304 // next possible match. 00305 _RandomAccessIter __backTrack = __first; 00306 while (__unary_pred(--__backTrack)) 00307 { 00308 if (--__remainder == 0) 00309 return (__first - __count); // Success 00310 } 00311 __remainder = __count + 1 - (__first - __backTrack); 00312 } 00313 return __last; // Failure 00314 } 00315 00316 template<typename _ForwardIterator, typename _Integer, 00317 typename _UnaryPredicate> 00318 _ForwardIterator 00319 __search_n(_ForwardIterator __first, _ForwardIterator __last, 00320 _Integer __count, 00321 _UnaryPredicate __unary_pred) 00322 { 00323 if (__count <= 0) 00324 return __first; 00325 00326 if (__count == 1) 00327 return std::__find_if(__first, __last, __unary_pred); 00328 00329 return std::__search_n_aux(__first, __last, __count, __unary_pred, 00330 std::__iterator_category(__first)); 00331 } 00332 00333 // find_end for forward iterators. 00334 template<typename _ForwardIterator1, typename _ForwardIterator2, 00335 typename _BinaryPredicate> 00336 _ForwardIterator1 00337 __find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 00338 _ForwardIterator2 __first2, _ForwardIterator2 __last2, 00339 forward_iterator_tag, forward_iterator_tag, 00340 _BinaryPredicate __comp) 00341 { 00342 if (__first2 == __last2) 00343 return __last1; 00344 00345 _ForwardIterator1 __result = __last1; 00346 while (1) 00347 { 00348 _ForwardIterator1 __new_result 00349 = std::__search(__first1, __last1, __first2, __last2, __comp); 00350 if (__new_result == __last1) 00351 return __result; 00352 else 00353 { 00354 __result = __new_result; 00355 __first1 = __new_result; 00356 ++__first1; 00357 } 00358 } 00359 } 00360 00361 // find_end for bidirectional iterators (much faster). 00362 template<typename _BidirectionalIterator1, typename _BidirectionalIterator2, 00363 typename _BinaryPredicate> 00364 _BidirectionalIterator1 00365 __find_end(_BidirectionalIterator1 __first1, 00366 _BidirectionalIterator1 __last1, 00367 _BidirectionalIterator2 __first2, 00368 _BidirectionalIterator2 __last2, 00369 bidirectional_iterator_tag, bidirectional_iterator_tag, 00370 _BinaryPredicate __comp) 00371 { 00372 // concept requirements 00373 __glibcxx_function_requires(_BidirectionalIteratorConcept< 00374 _BidirectionalIterator1>) 00375 __glibcxx_function_requires(_BidirectionalIteratorConcept< 00376 _BidirectionalIterator2>) 00377 00378 typedef reverse_iterator<_BidirectionalIterator1> _RevIterator1; 00379 typedef reverse_iterator<_BidirectionalIterator2> _RevIterator2; 00380 00381 _RevIterator1 __rlast1(__first1); 00382 _RevIterator2 __rlast2(__first2); 00383 _RevIterator1 __rresult = std::__search(_RevIterator1(__last1), __rlast1, 00384 _RevIterator2(__last2), __rlast2, 00385 __comp); 00386 00387 if (__rresult == __rlast1) 00388 return __last1; 00389 else 00390 { 00391 _BidirectionalIterator1 __result = __rresult.base(); 00392 std::advance(__result, -std::distance(__first2, __last2)); 00393 return __result; 00394 } 00395 } 00396 00397 /** 00398 * @brief Find last matching subsequence in a sequence. 00399 * @ingroup non_mutating_algorithms 00400 * @param __first1 Start of range to search. 00401 * @param __last1 End of range to search. 00402 * @param __first2 Start of sequence to match. 00403 * @param __last2 End of sequence to match. 00404 * @return The last iterator @c i in the range 00405 * @p [__first1,__last1-(__last2-__first2)) such that @c *(i+N) == 00406 * @p *(__first2+N) for each @c N in the range @p 00407 * [0,__last2-__first2), or @p __last1 if no such iterator exists. 00408 * 00409 * Searches the range @p [__first1,__last1) for a sub-sequence that 00410 * compares equal value-by-value with the sequence given by @p 00411 * [__first2,__last2) and returns an iterator to the __first 00412 * element of the sub-sequence, or @p __last1 if the sub-sequence 00413 * is not found. The sub-sequence will be the last such 00414 * subsequence contained in [__first1,__last1). 00415 * 00416 * Because the sub-sequence must lie completely within the range @p 00417 * [__first1,__last1) it must start at a position less than @p 00418 * __last1-(__last2-__first2) where @p __last2-__first2 is the 00419 * length of the sub-sequence. This means that the returned 00420 * iterator @c i will be in the range @p 00421 * [__first1,__last1-(__last2-__first2)) 00422 */ 00423 template<typename _ForwardIterator1, typename _ForwardIterator2> 00424 inline _ForwardIterator1 00425 find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 00426 _ForwardIterator2 __first2, _ForwardIterator2 __last2) 00427 { 00428 // concept requirements 00429 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>) 00430 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>) 00431 __glibcxx_function_requires(_EqualOpConcept< 00432 typename iterator_traits<_ForwardIterator1>::value_type, 00433 typename iterator_traits<_ForwardIterator2>::value_type>) 00434 __glibcxx_requires_valid_range(__first1, __last1); 00435 __glibcxx_requires_valid_range(__first2, __last2); 00436 00437 return std::__find_end(__first1, __last1, __first2, __last2, 00438 std::__iterator_category(__first1), 00439 std::__iterator_category(__first2), 00440 __gnu_cxx::__ops::__iter_equal_to_iter()); 00441 } 00442 00443 /** 00444 * @brief Find last matching subsequence in a sequence using a predicate. 00445 * @ingroup non_mutating_algorithms 00446 * @param __first1 Start of range to search. 00447 * @param __last1 End of range to search. 00448 * @param __first2 Start of sequence to match. 00449 * @param __last2 End of sequence to match. 00450 * @param __comp The predicate to use. 00451 * @return The last iterator @c i in the range @p 00452 * [__first1,__last1-(__last2-__first2)) such that @c 00453 * predicate(*(i+N), @p (__first2+N)) is true for each @c N in the 00454 * range @p [0,__last2-__first2), or @p __last1 if no such iterator 00455 * exists. 00456 * 00457 * Searches the range @p [__first1,__last1) for a sub-sequence that 00458 * compares equal value-by-value with the sequence given by @p 00459 * [__first2,__last2) using comp as a predicate and returns an 00460 * iterator to the first element of the sub-sequence, or @p __last1 00461 * if the sub-sequence is not found. The sub-sequence will be the 00462 * last such subsequence contained in [__first,__last1). 00463 * 00464 * Because the sub-sequence must lie completely within the range @p 00465 * [__first1,__last1) it must start at a position less than @p 00466 * __last1-(__last2-__first2) where @p __last2-__first2 is the 00467 * length of the sub-sequence. This means that the returned 00468 * iterator @c i will be in the range @p 00469 * [__first1,__last1-(__last2-__first2)) 00470 */ 00471 template<typename _ForwardIterator1, typename _ForwardIterator2, 00472 typename _BinaryPredicate> 00473 inline _ForwardIterator1 00474 find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 00475 _ForwardIterator2 __first2, _ForwardIterator2 __last2, 00476 _BinaryPredicate __comp) 00477 { 00478 // concept requirements 00479 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>) 00480 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>) 00481 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 00482 typename iterator_traits<_ForwardIterator1>::value_type, 00483 typename iterator_traits<_ForwardIterator2>::value_type>) 00484 __glibcxx_requires_valid_range(__first1, __last1); 00485 __glibcxx_requires_valid_range(__first2, __last2); 00486 00487 return std::__find_end(__first1, __last1, __first2, __last2, 00488 std::__iterator_category(__first1), 00489 std::__iterator_category(__first2), 00490 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 00491 } 00492 00493 #if __cplusplus >= 201103L 00494 /** 00495 * @brief Checks that a predicate is true for all the elements 00496 * of a sequence. 00497 * @ingroup non_mutating_algorithms 00498 * @param __first An input iterator. 00499 * @param __last An input iterator. 00500 * @param __pred A predicate. 00501 * @return True if the check is true, false otherwise. 00502 * 00503 * Returns true if @p __pred is true for each element in the range 00504 * @p [__first,__last), and false otherwise. 00505 */ 00506 template<typename _InputIterator, typename _Predicate> 00507 inline bool 00508 all_of(_InputIterator __first, _InputIterator __last, _Predicate __pred) 00509 { return __last == std::find_if_not(__first, __last, __pred); } 00510 00511 /** 00512 * @brief Checks that a predicate is false for all the elements 00513 * of a sequence. 00514 * @ingroup non_mutating_algorithms 00515 * @param __first An input iterator. 00516 * @param __last An input iterator. 00517 * @param __pred A predicate. 00518 * @return True if the check is true, false otherwise. 00519 * 00520 * Returns true if @p __pred is false for each element in the range 00521 * @p [__first,__last), and false otherwise. 00522 */ 00523 template<typename _InputIterator, typename _Predicate> 00524 inline bool 00525 none_of(_InputIterator __first, _InputIterator __last, _Predicate __pred) 00526 { return __last == _GLIBCXX_STD_A::find_if(__first, __last, __pred); } 00527 00528 /** 00529 * @brief Checks that a predicate is false for at least an element 00530 * of a sequence. 00531 * @ingroup non_mutating_algorithms 00532 * @param __first An input iterator. 00533 * @param __last An input iterator. 00534 * @param __pred A predicate. 00535 * @return True if the check is true, false otherwise. 00536 * 00537 * Returns true if an element exists in the range @p 00538 * [__first,__last) such that @p __pred is true, and false 00539 * otherwise. 00540 */ 00541 template<typename _InputIterator, typename _Predicate> 00542 inline bool 00543 any_of(_InputIterator __first, _InputIterator __last, _Predicate __pred) 00544 { return !std::none_of(__first, __last, __pred); } 00545 00546 /** 00547 * @brief Find the first element in a sequence for which a 00548 * predicate is false. 00549 * @ingroup non_mutating_algorithms 00550 * @param __first An input iterator. 00551 * @param __last An input iterator. 00552 * @param __pred A predicate. 00553 * @return The first iterator @c i in the range @p [__first,__last) 00554 * such that @p __pred(*i) is false, or @p __last if no such iterator exists. 00555 */ 00556 template<typename _InputIterator, typename _Predicate> 00557 inline _InputIterator 00558 find_if_not(_InputIterator __first, _InputIterator __last, 00559 _Predicate __pred) 00560 { 00561 // concept requirements 00562 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 00563 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 00564 typename iterator_traits<_InputIterator>::value_type>) 00565 __glibcxx_requires_valid_range(__first, __last); 00566 return std::__find_if_not(__first, __last, 00567 __gnu_cxx::__ops::__pred_iter(__pred)); 00568 } 00569 00570 /** 00571 * @brief Checks whether the sequence is partitioned. 00572 * @ingroup mutating_algorithms 00573 * @param __first An input iterator. 00574 * @param __last An input iterator. 00575 * @param __pred A predicate. 00576 * @return True if the range @p [__first,__last) is partioned by @p __pred, 00577 * i.e. if all elements that satisfy @p __pred appear before those that 00578 * do not. 00579 */ 00580 template<typename _InputIterator, typename _Predicate> 00581 inline bool 00582 is_partitioned(_InputIterator __first, _InputIterator __last, 00583 _Predicate __pred) 00584 { 00585 __first = std::find_if_not(__first, __last, __pred); 00586 if (__first == __last) 00587 return true; 00588 ++__first; 00589 return std::none_of(__first, __last, __pred); 00590 } 00591 00592 /** 00593 * @brief Find the partition point of a partitioned range. 00594 * @ingroup mutating_algorithms 00595 * @param __first An iterator. 00596 * @param __last Another iterator. 00597 * @param __pred A predicate. 00598 * @return An iterator @p mid such that @p all_of(__first, mid, __pred) 00599 * and @p none_of(mid, __last, __pred) are both true. 00600 */ 00601 template<typename _ForwardIterator, typename _Predicate> 00602 _ForwardIterator 00603 partition_point(_ForwardIterator __first, _ForwardIterator __last, 00604 _Predicate __pred) 00605 { 00606 // concept requirements 00607 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 00608 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 00609 typename iterator_traits<_ForwardIterator>::value_type>) 00610 00611 // A specific debug-mode test will be necessary... 00612 __glibcxx_requires_valid_range(__first, __last); 00613 00614 typedef typename iterator_traits<_ForwardIterator>::difference_type 00615 _DistanceType; 00616 00617 _DistanceType __len = std::distance(__first, __last); 00618 _DistanceType __half; 00619 _ForwardIterator __middle; 00620 00621 while (__len > 0) 00622 { 00623 __half = __len >> 1; 00624 __middle = __first; 00625 std::advance(__middle, __half); 00626 if (__pred(*__middle)) 00627 { 00628 __first = __middle; 00629 ++__first; 00630 __len = __len - __half - 1; 00631 } 00632 else 00633 __len = __half; 00634 } 00635 return __first; 00636 } 00637 #endif 00638 00639 template<typename _InputIterator, typename _OutputIterator, 00640 typename _Predicate> 00641 _OutputIterator 00642 __remove_copy_if(_InputIterator __first, _InputIterator __last, 00643 _OutputIterator __result, _Predicate __pred) 00644 { 00645 for (; __first != __last; ++__first) 00646 if (!__pred(__first)) 00647 { 00648 *__result = *__first; 00649 ++__result; 00650 } 00651 return __result; 00652 } 00653 00654 /** 00655 * @brief Copy a sequence, removing elements of a given value. 00656 * @ingroup mutating_algorithms 00657 * @param __first An input iterator. 00658 * @param __last An input iterator. 00659 * @param __result An output iterator. 00660 * @param __value The value to be removed. 00661 * @return An iterator designating the end of the resulting sequence. 00662 * 00663 * Copies each element in the range @p [__first,__last) not equal 00664 * to @p __value to the range beginning at @p __result. 00665 * remove_copy() is stable, so the relative order of elements that 00666 * are copied is unchanged. 00667 */ 00668 template<typename _InputIterator, typename _OutputIterator, typename _Tp> 00669 inline _OutputIterator 00670 remove_copy(_InputIterator __first, _InputIterator __last, 00671 _OutputIterator __result, const _Tp& __value) 00672 { 00673 // concept requirements 00674 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 00675 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 00676 typename iterator_traits<_InputIterator>::value_type>) 00677 __glibcxx_function_requires(_EqualOpConcept< 00678 typename iterator_traits<_InputIterator>::value_type, _Tp>) 00679 __glibcxx_requires_valid_range(__first, __last); 00680 00681 return std::__remove_copy_if(__first, __last, __result, 00682 __gnu_cxx::__ops::__iter_equals_val(__value)); 00683 } 00684 00685 /** 00686 * @brief Copy a sequence, removing elements for which a predicate is true. 00687 * @ingroup mutating_algorithms 00688 * @param __first An input iterator. 00689 * @param __last An input iterator. 00690 * @param __result An output iterator. 00691 * @param __pred A predicate. 00692 * @return An iterator designating the end of the resulting sequence. 00693 * 00694 * Copies each element in the range @p [__first,__last) for which 00695 * @p __pred returns false to the range beginning at @p __result. 00696 * 00697 * remove_copy_if() is stable, so the relative order of elements that are 00698 * copied is unchanged. 00699 */ 00700 template<typename _InputIterator, typename _OutputIterator, 00701 typename _Predicate> 00702 inline _OutputIterator 00703 remove_copy_if(_InputIterator __first, _InputIterator __last, 00704 _OutputIterator __result, _Predicate __pred) 00705 { 00706 // concept requirements 00707 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 00708 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 00709 typename iterator_traits<_InputIterator>::value_type>) 00710 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 00711 typename iterator_traits<_InputIterator>::value_type>) 00712 __glibcxx_requires_valid_range(__first, __last); 00713 00714 return std::__remove_copy_if(__first, __last, __result, 00715 __gnu_cxx::__ops::__pred_iter(__pred)); 00716 } 00717 00718 #if __cplusplus >= 201103L 00719 /** 00720 * @brief Copy the elements of a sequence for which a predicate is true. 00721 * @ingroup mutating_algorithms 00722 * @param __first An input iterator. 00723 * @param __last An input iterator. 00724 * @param __result An output iterator. 00725 * @param __pred A predicate. 00726 * @return An iterator designating the end of the resulting sequence. 00727 * 00728 * Copies each element in the range @p [__first,__last) for which 00729 * @p __pred returns true to the range beginning at @p __result. 00730 * 00731 * copy_if() is stable, so the relative order of elements that are 00732 * copied is unchanged. 00733 */ 00734 template<typename _InputIterator, typename _OutputIterator, 00735 typename _Predicate> 00736 _OutputIterator 00737 copy_if(_InputIterator __first, _InputIterator __last, 00738 _OutputIterator __result, _Predicate __pred) 00739 { 00740 // concept requirements 00741 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 00742 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 00743 typename iterator_traits<_InputIterator>::value_type>) 00744 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 00745 typename iterator_traits<_InputIterator>::value_type>) 00746 __glibcxx_requires_valid_range(__first, __last); 00747 00748 for (; __first != __last; ++__first) 00749 if (__pred(*__first)) 00750 { 00751 *__result = *__first; 00752 ++__result; 00753 } 00754 return __result; 00755 } 00756 00757 template<typename _InputIterator, typename _Size, typename _OutputIterator> 00758 _OutputIterator 00759 __copy_n(_InputIterator __first, _Size __n, 00760 _OutputIterator __result, input_iterator_tag) 00761 { 00762 if (__n > 0) 00763 { 00764 while (true) 00765 { 00766 *__result = *__first; 00767 ++__result; 00768 if (--__n > 0) 00769 ++__first; 00770 else 00771 break; 00772 } 00773 } 00774 return __result; 00775 } 00776 00777 template<typename _RandomAccessIterator, typename _Size, 00778 typename _OutputIterator> 00779 inline _OutputIterator 00780 __copy_n(_RandomAccessIterator __first, _Size __n, 00781 _OutputIterator __result, random_access_iterator_tag) 00782 { return std::copy(__first, __first + __n, __result); } 00783 00784 /** 00785 * @brief Copies the range [first,first+n) into [result,result+n). 00786 * @ingroup mutating_algorithms 00787 * @param __first An input iterator. 00788 * @param __n The number of elements to copy. 00789 * @param __result An output iterator. 00790 * @return result+n. 00791 * 00792 * This inline function will boil down to a call to @c memmove whenever 00793 * possible. Failing that, if random access iterators are passed, then the 00794 * loop count will be known (and therefore a candidate for compiler 00795 * optimizations such as unrolling). 00796 */ 00797 template<typename _InputIterator, typename _Size, typename _OutputIterator> 00798 inline _OutputIterator 00799 copy_n(_InputIterator __first, _Size __n, _OutputIterator __result) 00800 { 00801 // concept requirements 00802 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 00803 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 00804 typename iterator_traits<_InputIterator>::value_type>) 00805 00806 return std::__copy_n(__first, __n, __result, 00807 std::__iterator_category(__first)); 00808 } 00809 00810 /** 00811 * @brief Copy the elements of a sequence to separate output sequences 00812 * depending on the truth value of a predicate. 00813 * @ingroup mutating_algorithms 00814 * @param __first An input iterator. 00815 * @param __last An input iterator. 00816 * @param __out_true An output iterator. 00817 * @param __out_false An output iterator. 00818 * @param __pred A predicate. 00819 * @return A pair designating the ends of the resulting sequences. 00820 * 00821 * Copies each element in the range @p [__first,__last) for which 00822 * @p __pred returns true to the range beginning at @p out_true 00823 * and each element for which @p __pred returns false to @p __out_false. 00824 */ 00825 template<typename _InputIterator, typename _OutputIterator1, 00826 typename _OutputIterator2, typename _Predicate> 00827 pair<_OutputIterator1, _OutputIterator2> 00828 partition_copy(_InputIterator __first, _InputIterator __last, 00829 _OutputIterator1 __out_true, _OutputIterator2 __out_false, 00830 _Predicate __pred) 00831 { 00832 // concept requirements 00833 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 00834 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator1, 00835 typename iterator_traits<_InputIterator>::value_type>) 00836 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator2, 00837 typename iterator_traits<_InputIterator>::value_type>) 00838 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 00839 typename iterator_traits<_InputIterator>::value_type>) 00840 __glibcxx_requires_valid_range(__first, __last); 00841 00842 for (; __first != __last; ++__first) 00843 if (__pred(*__first)) 00844 { 00845 *__out_true = *__first; 00846 ++__out_true; 00847 } 00848 else 00849 { 00850 *__out_false = *__first; 00851 ++__out_false; 00852 } 00853 00854 return pair<_OutputIterator1, _OutputIterator2>(__out_true, __out_false); 00855 } 00856 #endif 00857 00858 template<typename _ForwardIterator, typename _Predicate> 00859 _ForwardIterator 00860 __remove_if(_ForwardIterator __first, _ForwardIterator __last, 00861 _Predicate __pred) 00862 { 00863 __first = std::__find_if(__first, __last, __pred); 00864 if (__first == __last) 00865 return __first; 00866 _ForwardIterator __result = __first; 00867 ++__first; 00868 for (; __first != __last; ++__first) 00869 if (!__pred(__first)) 00870 { 00871 *__result = _GLIBCXX_MOVE(*__first); 00872 ++__result; 00873 } 00874 return __result; 00875 } 00876 00877 /** 00878 * @brief Remove elements from a sequence. 00879 * @ingroup mutating_algorithms 00880 * @param __first An input iterator. 00881 * @param __last An input iterator. 00882 * @param __value The value to be removed. 00883 * @return An iterator designating the end of the resulting sequence. 00884 * 00885 * All elements equal to @p __value are removed from the range 00886 * @p [__first,__last). 00887 * 00888 * remove() is stable, so the relative order of elements that are 00889 * not removed is unchanged. 00890 * 00891 * Elements between the end of the resulting sequence and @p __last 00892 * are still present, but their value is unspecified. 00893 */ 00894 template<typename _ForwardIterator, typename _Tp> 00895 inline _ForwardIterator 00896 remove(_ForwardIterator __first, _ForwardIterator __last, 00897 const _Tp& __value) 00898 { 00899 // concept requirements 00900 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 00901 _ForwardIterator>) 00902 __glibcxx_function_requires(_EqualOpConcept< 00903 typename iterator_traits<_ForwardIterator>::value_type, _Tp>) 00904 __glibcxx_requires_valid_range(__first, __last); 00905 00906 return std::__remove_if(__first, __last, 00907 __gnu_cxx::__ops::__iter_equals_val(__value)); 00908 } 00909 00910 /** 00911 * @brief Remove elements from a sequence using a predicate. 00912 * @ingroup mutating_algorithms 00913 * @param __first A forward iterator. 00914 * @param __last A forward iterator. 00915 * @param __pred A predicate. 00916 * @return An iterator designating the end of the resulting sequence. 00917 * 00918 * All elements for which @p __pred returns true are removed from the range 00919 * @p [__first,__last). 00920 * 00921 * remove_if() is stable, so the relative order of elements that are 00922 * not removed is unchanged. 00923 * 00924 * Elements between the end of the resulting sequence and @p __last 00925 * are still present, but their value is unspecified. 00926 */ 00927 template<typename _ForwardIterator, typename _Predicate> 00928 inline _ForwardIterator 00929 remove_if(_ForwardIterator __first, _ForwardIterator __last, 00930 _Predicate __pred) 00931 { 00932 // concept requirements 00933 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 00934 _ForwardIterator>) 00935 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 00936 typename iterator_traits<_ForwardIterator>::value_type>) 00937 __glibcxx_requires_valid_range(__first, __last); 00938 00939 return std::__remove_if(__first, __last, 00940 __gnu_cxx::__ops::__pred_iter(__pred)); 00941 } 00942 00943 template<typename _ForwardIterator, typename _BinaryPredicate> 00944 _ForwardIterator 00945 __adjacent_find(_ForwardIterator __first, _ForwardIterator __last, 00946 _BinaryPredicate __binary_pred) 00947 { 00948 if (__first == __last) 00949 return __last; 00950 _ForwardIterator __next = __first; 00951 while (++__next != __last) 00952 { 00953 if (__binary_pred(__first, __next)) 00954 return __first; 00955 __first = __next; 00956 } 00957 return __last; 00958 } 00959 00960 template<typename _ForwardIterator, typename _BinaryPredicate> 00961 _ForwardIterator 00962 __unique(_ForwardIterator __first, _ForwardIterator __last, 00963 _BinaryPredicate __binary_pred) 00964 { 00965 // Skip the beginning, if already unique. 00966 __first = std::__adjacent_find(__first, __last, __binary_pred); 00967 if (__first == __last) 00968 return __last; 00969 00970 // Do the real copy work. 00971 _ForwardIterator __dest = __first; 00972 ++__first; 00973 while (++__first != __last) 00974 if (!__binary_pred(__dest, __first)) 00975 *++__dest = _GLIBCXX_MOVE(*__first); 00976 return ++__dest; 00977 } 00978 00979 /** 00980 * @brief Remove consecutive duplicate values from a sequence. 00981 * @ingroup mutating_algorithms 00982 * @param __first A forward iterator. 00983 * @param __last A forward iterator. 00984 * @return An iterator designating the end of the resulting sequence. 00985 * 00986 * Removes all but the first element from each group of consecutive 00987 * values that compare equal. 00988 * unique() is stable, so the relative order of elements that are 00989 * not removed is unchanged. 00990 * Elements between the end of the resulting sequence and @p __last 00991 * are still present, but their value is unspecified. 00992 */ 00993 template<typename _ForwardIterator> 00994 inline _ForwardIterator 00995 unique(_ForwardIterator __first, _ForwardIterator __last) 00996 { 00997 // concept requirements 00998 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 00999 _ForwardIterator>) 01000 __glibcxx_function_requires(_EqualityComparableConcept< 01001 typename iterator_traits<_ForwardIterator>::value_type>) 01002 __glibcxx_requires_valid_range(__first, __last); 01003 01004 return std::__unique(__first, __last, 01005 __gnu_cxx::__ops::__iter_equal_to_iter()); 01006 } 01007 01008 /** 01009 * @brief Remove consecutive values from a sequence using a predicate. 01010 * @ingroup mutating_algorithms 01011 * @param __first A forward iterator. 01012 * @param __last A forward iterator. 01013 * @param __binary_pred A binary predicate. 01014 * @return An iterator designating the end of the resulting sequence. 01015 * 01016 * Removes all but the first element from each group of consecutive 01017 * values for which @p __binary_pred returns true. 01018 * unique() is stable, so the relative order of elements that are 01019 * not removed is unchanged. 01020 * Elements between the end of the resulting sequence and @p __last 01021 * are still present, but their value is unspecified. 01022 */ 01023 template<typename _ForwardIterator, typename _BinaryPredicate> 01024 inline _ForwardIterator 01025 unique(_ForwardIterator __first, _ForwardIterator __last, 01026 _BinaryPredicate __binary_pred) 01027 { 01028 // concept requirements 01029 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 01030 _ForwardIterator>) 01031 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 01032 typename iterator_traits<_ForwardIterator>::value_type, 01033 typename iterator_traits<_ForwardIterator>::value_type>) 01034 __glibcxx_requires_valid_range(__first, __last); 01035 01036 return std::__unique(__first, __last, 01037 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred)); 01038 } 01039 01040 /** 01041 * This is an uglified 01042 * unique_copy(_InputIterator, _InputIterator, _OutputIterator, 01043 * _BinaryPredicate) 01044 * overloaded for forward iterators and output iterator as result. 01045 */ 01046 template<typename _ForwardIterator, typename _OutputIterator, 01047 typename _BinaryPredicate> 01048 _OutputIterator 01049 __unique_copy(_ForwardIterator __first, _ForwardIterator __last, 01050 _OutputIterator __result, _BinaryPredicate __binary_pred, 01051 forward_iterator_tag, output_iterator_tag) 01052 { 01053 // concept requirements -- iterators already checked 01054 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 01055 typename iterator_traits<_ForwardIterator>::value_type, 01056 typename iterator_traits<_ForwardIterator>::value_type>) 01057 01058 _ForwardIterator __next = __first; 01059 *__result = *__first; 01060 while (++__next != __last) 01061 if (!__binary_pred(__first, __next)) 01062 { 01063 __first = __next; 01064 *++__result = *__first; 01065 } 01066 return ++__result; 01067 } 01068 01069 /** 01070 * This is an uglified 01071 * unique_copy(_InputIterator, _InputIterator, _OutputIterator, 01072 * _BinaryPredicate) 01073 * overloaded for input iterators and output iterator as result. 01074 */ 01075 template<typename _InputIterator, typename _OutputIterator, 01076 typename _BinaryPredicate> 01077 _OutputIterator 01078 __unique_copy(_InputIterator __first, _InputIterator __last, 01079 _OutputIterator __result, _BinaryPredicate __binary_pred, 01080 input_iterator_tag, output_iterator_tag) 01081 { 01082 // concept requirements -- iterators already checked 01083 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 01084 typename iterator_traits<_InputIterator>::value_type, 01085 typename iterator_traits<_InputIterator>::value_type>) 01086 01087 typename iterator_traits<_InputIterator>::value_type __value = *__first; 01088 __decltype(__gnu_cxx::__ops::__iter_comp_val(__binary_pred)) 01089 __rebound_pred 01090 = __gnu_cxx::__ops::__iter_comp_val(__binary_pred); 01091 *__result = __value; 01092 while (++__first != __last) 01093 if (!__rebound_pred(__first, __value)) 01094 { 01095 __value = *__first; 01096 *++__result = __value; 01097 } 01098 return ++__result; 01099 } 01100 01101 /** 01102 * This is an uglified 01103 * unique_copy(_InputIterator, _InputIterator, _OutputIterator, 01104 * _BinaryPredicate) 01105 * overloaded for input iterators and forward iterator as result. 01106 */ 01107 template<typename _InputIterator, typename _ForwardIterator, 01108 typename _BinaryPredicate> 01109 _ForwardIterator 01110 __unique_copy(_InputIterator __first, _InputIterator __last, 01111 _ForwardIterator __result, _BinaryPredicate __binary_pred, 01112 input_iterator_tag, forward_iterator_tag) 01113 { 01114 // concept requirements -- iterators already checked 01115 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 01116 typename iterator_traits<_ForwardIterator>::value_type, 01117 typename iterator_traits<_InputIterator>::value_type>) 01118 *__result = *__first; 01119 while (++__first != __last) 01120 if (!__binary_pred(__result, __first)) 01121 *++__result = *__first; 01122 return ++__result; 01123 } 01124 01125 /** 01126 * This is an uglified reverse(_BidirectionalIterator, 01127 * _BidirectionalIterator) 01128 * overloaded for bidirectional iterators. 01129 */ 01130 template<typename _BidirectionalIterator> 01131 void 01132 __reverse(_BidirectionalIterator __first, _BidirectionalIterator __last, 01133 bidirectional_iterator_tag) 01134 { 01135 while (true) 01136 if (__first == __last || __first == --__last) 01137 return; 01138 else 01139 { 01140 std::iter_swap(__first, __last); 01141 ++__first; 01142 } 01143 } 01144 01145 /** 01146 * This is an uglified reverse(_BidirectionalIterator, 01147 * _BidirectionalIterator) 01148 * overloaded for random access iterators. 01149 */ 01150 template<typename _RandomAccessIterator> 01151 void 01152 __reverse(_RandomAccessIterator __first, _RandomAccessIterator __last, 01153 random_access_iterator_tag) 01154 { 01155 if (__first == __last) 01156 return; 01157 --__last; 01158 while (__first < __last) 01159 { 01160 std::iter_swap(__first, __last); 01161 ++__first; 01162 --__last; 01163 } 01164 } 01165 01166 /** 01167 * @brief Reverse a sequence. 01168 * @ingroup mutating_algorithms 01169 * @param __first A bidirectional iterator. 01170 * @param __last A bidirectional iterator. 01171 * @return reverse() returns no value. 01172 * 01173 * Reverses the order of the elements in the range @p [__first,__last), 01174 * so that the first element becomes the last etc. 01175 * For every @c i such that @p 0<=i<=(__last-__first)/2), @p reverse() 01176 * swaps @p *(__first+i) and @p *(__last-(i+1)) 01177 */ 01178 template<typename _BidirectionalIterator> 01179 inline void 01180 reverse(_BidirectionalIterator __first, _BidirectionalIterator __last) 01181 { 01182 // concept requirements 01183 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept< 01184 _BidirectionalIterator>) 01185 __glibcxx_requires_valid_range(__first, __last); 01186 std::__reverse(__first, __last, std::__iterator_category(__first)); 01187 } 01188 01189 /** 01190 * @brief Copy a sequence, reversing its elements. 01191 * @ingroup mutating_algorithms 01192 * @param __first A bidirectional iterator. 01193 * @param __last A bidirectional iterator. 01194 * @param __result An output iterator. 01195 * @return An iterator designating the end of the resulting sequence. 01196 * 01197 * Copies the elements in the range @p [__first,__last) to the 01198 * range @p [__result,__result+(__last-__first)) such that the 01199 * order of the elements is reversed. For every @c i such that @p 01200 * 0<=i<=(__last-__first), @p reverse_copy() performs the 01201 * assignment @p *(__result+(__last-__first)-1-i) = *(__first+i). 01202 * The ranges @p [__first,__last) and @p 01203 * [__result,__result+(__last-__first)) must not overlap. 01204 */ 01205 template<typename _BidirectionalIterator, typename _OutputIterator> 01206 _OutputIterator 01207 reverse_copy(_BidirectionalIterator __first, _BidirectionalIterator __last, 01208 _OutputIterator __result) 01209 { 01210 // concept requirements 01211 __glibcxx_function_requires(_BidirectionalIteratorConcept< 01212 _BidirectionalIterator>) 01213 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 01214 typename iterator_traits<_BidirectionalIterator>::value_type>) 01215 __glibcxx_requires_valid_range(__first, __last); 01216 01217 while (__first != __last) 01218 { 01219 --__last; 01220 *__result = *__last; 01221 ++__result; 01222 } 01223 return __result; 01224 } 01225 01226 /** 01227 * This is a helper function for the rotate algorithm specialized on RAIs. 01228 * It returns the greatest common divisor of two integer values. 01229 */ 01230 template<typename _EuclideanRingElement> 01231 _EuclideanRingElement 01232 __gcd(_EuclideanRingElement __m, _EuclideanRingElement __n) 01233 { 01234 while (__n != 0) 01235 { 01236 _EuclideanRingElement __t = __m % __n; 01237 __m = __n; 01238 __n = __t; 01239 } 01240 return __m; 01241 } 01242 01243 inline namespace _V2 01244 { 01245 01246 /// This is a helper function for the rotate algorithm. 01247 template<typename _ForwardIterator> 01248 _ForwardIterator 01249 __rotate(_ForwardIterator __first, 01250 _ForwardIterator __middle, 01251 _ForwardIterator __last, 01252 forward_iterator_tag) 01253 { 01254 if (__first == __middle) 01255 return __last; 01256 else if (__last == __middle) 01257 return __first; 01258 01259 _ForwardIterator __first2 = __middle; 01260 do 01261 { 01262 std::iter_swap(__first, __first2); 01263 ++__first; 01264 ++__first2; 01265 if (__first == __middle) 01266 __middle = __first2; 01267 } 01268 while (__first2 != __last); 01269 01270 _ForwardIterator __ret = __first; 01271 01272 __first2 = __middle; 01273 01274 while (__first2 != __last) 01275 { 01276 std::iter_swap(__first, __first2); 01277 ++__first; 01278 ++__first2; 01279 if (__first == __middle) 01280 __middle = __first2; 01281 else if (__first2 == __last) 01282 __first2 = __middle; 01283 } 01284 return __ret; 01285 } 01286 01287 /// This is a helper function for the rotate algorithm. 01288 template<typename _BidirectionalIterator> 01289 _BidirectionalIterator 01290 __rotate(_BidirectionalIterator __first, 01291 _BidirectionalIterator __middle, 01292 _BidirectionalIterator __last, 01293 bidirectional_iterator_tag) 01294 { 01295 // concept requirements 01296 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept< 01297 _BidirectionalIterator>) 01298 01299 if (__first == __middle) 01300 return __last; 01301 else if (__last == __middle) 01302 return __first; 01303 01304 std::__reverse(__first, __middle, bidirectional_iterator_tag()); 01305 std::__reverse(__middle, __last, bidirectional_iterator_tag()); 01306 01307 while (__first != __middle && __middle != __last) 01308 { 01309 std::iter_swap(__first, --__last); 01310 ++__first; 01311 } 01312 01313 if (__first == __middle) 01314 { 01315 std::__reverse(__middle, __last, bidirectional_iterator_tag()); 01316 return __last; 01317 } 01318 else 01319 { 01320 std::__reverse(__first, __middle, bidirectional_iterator_tag()); 01321 return __first; 01322 } 01323 } 01324 01325 /// This is a helper function for the rotate algorithm. 01326 template<typename _RandomAccessIterator> 01327 _RandomAccessIterator 01328 __rotate(_RandomAccessIterator __first, 01329 _RandomAccessIterator __middle, 01330 _RandomAccessIterator __last, 01331 random_access_iterator_tag) 01332 { 01333 // concept requirements 01334 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 01335 _RandomAccessIterator>) 01336 01337 if (__first == __middle) 01338 return __last; 01339 else if (__last == __middle) 01340 return __first; 01341 01342 typedef typename iterator_traits<_RandomAccessIterator>::difference_type 01343 _Distance; 01344 typedef typename iterator_traits<_RandomAccessIterator>::value_type 01345 _ValueType; 01346 01347 _Distance __n = __last - __first; 01348 _Distance __k = __middle - __first; 01349 01350 if (__k == __n - __k) 01351 { 01352 std::swap_ranges(__first, __middle, __middle); 01353 return __middle; 01354 } 01355 01356 _RandomAccessIterator __p = __first; 01357 _RandomAccessIterator __ret = __first + (__last - __middle); 01358 01359 for (;;) 01360 { 01361 if (__k < __n - __k) 01362 { 01363 if (__is_pod(_ValueType) && __k == 1) 01364 { 01365 _ValueType __t = _GLIBCXX_MOVE(*__p); 01366 _GLIBCXX_MOVE3(__p + 1, __p + __n, __p); 01367 *(__p + __n - 1) = _GLIBCXX_MOVE(__t); 01368 return __ret; 01369 } 01370 _RandomAccessIterator __q = __p + __k; 01371 for (_Distance __i = 0; __i < __n - __k; ++ __i) 01372 { 01373 std::iter_swap(__p, __q); 01374 ++__p; 01375 ++__q; 01376 } 01377 __n %= __k; 01378 if (__n == 0) 01379 return __ret; 01380 std::swap(__n, __k); 01381 __k = __n - __k; 01382 } 01383 else 01384 { 01385 __k = __n - __k; 01386 if (__is_pod(_ValueType) && __k == 1) 01387 { 01388 _ValueType __t = _GLIBCXX_MOVE(*(__p + __n - 1)); 01389 _GLIBCXX_MOVE_BACKWARD3(__p, __p + __n - 1, __p + __n); 01390 *__p = _GLIBCXX_MOVE(__t); 01391 return __ret; 01392 } 01393 _RandomAccessIterator __q = __p + __n; 01394 __p = __q - __k; 01395 for (_Distance __i = 0; __i < __n - __k; ++ __i) 01396 { 01397 --__p; 01398 --__q; 01399 std::iter_swap(__p, __q); 01400 } 01401 __n %= __k; 01402 if (__n == 0) 01403 return __ret; 01404 std::swap(__n, __k); 01405 } 01406 } 01407 } 01408 01409 // _GLIBCXX_RESOLVE_LIB_DEFECTS 01410 // DR 488. rotate throws away useful information 01411 /** 01412 * @brief Rotate the elements of a sequence. 01413 * @ingroup mutating_algorithms 01414 * @param __first A forward iterator. 01415 * @param __middle A forward iterator. 01416 * @param __last A forward iterator. 01417 * @return first + (last - middle). 01418 * 01419 * Rotates the elements of the range @p [__first,__last) by 01420 * @p (__middle - __first) positions so that the element at @p __middle 01421 * is moved to @p __first, the element at @p __middle+1 is moved to 01422 * @p __first+1 and so on for each element in the range 01423 * @p [__first,__last). 01424 * 01425 * This effectively swaps the ranges @p [__first,__middle) and 01426 * @p [__middle,__last). 01427 * 01428 * Performs 01429 * @p *(__first+(n+(__last-__middle))%(__last-__first))=*(__first+n) 01430 * for each @p n in the range @p [0,__last-__first). 01431 */ 01432 template<typename _ForwardIterator> 01433 inline _ForwardIterator 01434 rotate(_ForwardIterator __first, _ForwardIterator __middle, 01435 _ForwardIterator __last) 01436 { 01437 // concept requirements 01438 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 01439 _ForwardIterator>) 01440 __glibcxx_requires_valid_range(__first, __middle); 01441 __glibcxx_requires_valid_range(__middle, __last); 01442 01443 return std::__rotate(__first, __middle, __last, 01444 std::__iterator_category(__first)); 01445 } 01446 01447 } // namespace _V2 01448 01449 /** 01450 * @brief Copy a sequence, rotating its elements. 01451 * @ingroup mutating_algorithms 01452 * @param __first A forward iterator. 01453 * @param __middle A forward iterator. 01454 * @param __last A forward iterator. 01455 * @param __result An output iterator. 01456 * @return An iterator designating the end of the resulting sequence. 01457 * 01458 * Copies the elements of the range @p [__first,__last) to the 01459 * range beginning at @result, rotating the copied elements by 01460 * @p (__middle-__first) positions so that the element at @p __middle 01461 * is moved to @p __result, the element at @p __middle+1 is moved 01462 * to @p __result+1 and so on for each element in the range @p 01463 * [__first,__last). 01464 * 01465 * Performs 01466 * @p *(__result+(n+(__last-__middle))%(__last-__first))=*(__first+n) 01467 * for each @p n in the range @p [0,__last-__first). 01468 */ 01469 template<typename _ForwardIterator, typename _OutputIterator> 01470 inline _OutputIterator 01471 rotate_copy(_ForwardIterator __first, _ForwardIterator __middle, 01472 _ForwardIterator __last, _OutputIterator __result) 01473 { 01474 // concept requirements 01475 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 01476 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 01477 typename iterator_traits<_ForwardIterator>::value_type>) 01478 __glibcxx_requires_valid_range(__first, __middle); 01479 __glibcxx_requires_valid_range(__middle, __last); 01480 01481 return std::copy(__first, __middle, 01482 std::copy(__middle, __last, __result)); 01483 } 01484 01485 /// This is a helper function... 01486 template<typename _ForwardIterator, typename _Predicate> 01487 _ForwardIterator 01488 __partition(_ForwardIterator __first, _ForwardIterator __last, 01489 _Predicate __pred, forward_iterator_tag) 01490 { 01491 if (__first == __last) 01492 return __first; 01493 01494 while (__pred(*__first)) 01495 if (++__first == __last) 01496 return __first; 01497 01498 _ForwardIterator __next = __first; 01499 01500 while (++__next != __last) 01501 if (__pred(*__next)) 01502 { 01503 std::iter_swap(__first, __next); 01504 ++__first; 01505 } 01506 01507 return __first; 01508 } 01509 01510 /// This is a helper function... 01511 template<typename _BidirectionalIterator, typename _Predicate> 01512 _BidirectionalIterator 01513 __partition(_BidirectionalIterator __first, _BidirectionalIterator __last, 01514 _Predicate __pred, bidirectional_iterator_tag) 01515 { 01516 while (true) 01517 { 01518 while (true) 01519 if (__first == __last) 01520 return __first; 01521 else if (__pred(*__first)) 01522 ++__first; 01523 else 01524 break; 01525 --__last; 01526 while (true) 01527 if (__first == __last) 01528 return __first; 01529 else if (!bool(__pred(*__last))) 01530 --__last; 01531 else 01532 break; 01533 std::iter_swap(__first, __last); 01534 ++__first; 01535 } 01536 } 01537 01538 // partition 01539 01540 /// This is a helper function... 01541 /// Requires __first != __last and !__pred(__first) 01542 /// and __len == distance(__first, __last). 01543 /// 01544 /// !__pred(__first) allows us to guarantee that we don't 01545 /// move-assign an element onto itself. 01546 template<typename _ForwardIterator, typename _Pointer, typename _Predicate, 01547 typename _Distance> 01548 _ForwardIterator 01549 __stable_partition_adaptive(_ForwardIterator __first, 01550 _ForwardIterator __last, 01551 _Predicate __pred, _Distance __len, 01552 _Pointer __buffer, 01553 _Distance __buffer_size) 01554 { 01555 if (__len == 1) 01556 return __first; 01557 01558 if (__len <= __buffer_size) 01559 { 01560 _ForwardIterator __result1 = __first; 01561 _Pointer __result2 = __buffer; 01562 01563 // The precondition guarantees that !__pred(__first), so 01564 // move that element to the buffer before starting the loop. 01565 // This ensures that we only call __pred once per element. 01566 *__result2 = _GLIBCXX_MOVE(*__first); 01567 ++__result2; 01568 ++__first; 01569 for (; __first != __last; ++__first) 01570 if (__pred(__first)) 01571 { 01572 *__result1 = _GLIBCXX_MOVE(*__first); 01573 ++__result1; 01574 } 01575 else 01576 { 01577 *__result2 = _GLIBCXX_MOVE(*__first); 01578 ++__result2; 01579 } 01580 01581 _GLIBCXX_MOVE3(__buffer, __result2, __result1); 01582 return __result1; 01583 } 01584 01585 _ForwardIterator __middle = __first; 01586 std::advance(__middle, __len / 2); 01587 _ForwardIterator __left_split = 01588 std::__stable_partition_adaptive(__first, __middle, __pred, 01589 __len / 2, __buffer, 01590 __buffer_size); 01591 01592 // Advance past true-predicate values to satisfy this 01593 // function's preconditions. 01594 _Distance __right_len = __len - __len / 2; 01595 _ForwardIterator __right_split = 01596 std::__find_if_not_n(__middle, __right_len, __pred); 01597 01598 if (__right_len) 01599 __right_split = 01600 std::__stable_partition_adaptive(__right_split, __last, __pred, 01601 __right_len, 01602 __buffer, __buffer_size); 01603 01604 std::rotate(__left_split, __middle, __right_split); 01605 std::advance(__left_split, std::distance(__middle, __right_split)); 01606 return __left_split; 01607 } 01608 01609 template<typename _ForwardIterator, typename _Predicate> 01610 _ForwardIterator 01611 __stable_partition(_ForwardIterator __first, _ForwardIterator __last, 01612 _Predicate __pred) 01613 { 01614 __first = std::__find_if_not(__first, __last, __pred); 01615 01616 if (__first == __last) 01617 return __first; 01618 01619 typedef typename iterator_traits<_ForwardIterator>::value_type 01620 _ValueType; 01621 typedef typename iterator_traits<_ForwardIterator>::difference_type 01622 _DistanceType; 01623 01624 _Temporary_buffer<_ForwardIterator, _ValueType> __buf(__first, __last); 01625 return 01626 std::__stable_partition_adaptive(__first, __last, __pred, 01627 _DistanceType(__buf.requested_size()), 01628 __buf.begin(), 01629 _DistanceType(__buf.size())); 01630 } 01631 01632 /** 01633 * @brief Move elements for which a predicate is true to the beginning 01634 * of a sequence, preserving relative ordering. 01635 * @ingroup mutating_algorithms 01636 * @param __first A forward iterator. 01637 * @param __last A forward iterator. 01638 * @param __pred A predicate functor. 01639 * @return An iterator @p middle such that @p __pred(i) is true for each 01640 * iterator @p i in the range @p [first,middle) and false for each @p i 01641 * in the range @p [middle,last). 01642 * 01643 * Performs the same function as @p partition() with the additional 01644 * guarantee that the relative ordering of elements in each group is 01645 * preserved, so any two elements @p x and @p y in the range 01646 * @p [__first,__last) such that @p __pred(x)==__pred(y) will have the same 01647 * relative ordering after calling @p stable_partition(). 01648 */ 01649 template<typename _ForwardIterator, typename _Predicate> 01650 inline _ForwardIterator 01651 stable_partition(_ForwardIterator __first, _ForwardIterator __last, 01652 _Predicate __pred) 01653 { 01654 // concept requirements 01655 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 01656 _ForwardIterator>) 01657 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 01658 typename iterator_traits<_ForwardIterator>::value_type>) 01659 __glibcxx_requires_valid_range(__first, __last); 01660 01661 return std::__stable_partition(__first, __last, 01662 __gnu_cxx::__ops::__pred_iter(__pred)); 01663 } 01664 01665 /// This is a helper function for the sort routines. 01666 template<typename _RandomAccessIterator, typename _Compare> 01667 void 01668 __heap_select(_RandomAccessIterator __first, 01669 _RandomAccessIterator __middle, 01670 _RandomAccessIterator __last, _Compare __comp) 01671 { 01672 std::__make_heap(__first, __middle, __comp); 01673 for (_RandomAccessIterator __i = __middle; __i < __last; ++__i) 01674 if (__comp(__i, __first)) 01675 std::__pop_heap(__first, __middle, __i, __comp); 01676 } 01677 01678 // partial_sort 01679 01680 template<typename _InputIterator, typename _RandomAccessIterator, 01681 typename _Compare> 01682 _RandomAccessIterator 01683 __partial_sort_copy(_InputIterator __first, _InputIterator __last, 01684 _RandomAccessIterator __result_first, 01685 _RandomAccessIterator __result_last, 01686 _Compare __comp) 01687 { 01688 typedef typename iterator_traits<_InputIterator>::value_type 01689 _InputValueType; 01690 typedef iterator_traits<_RandomAccessIterator> _RItTraits; 01691 typedef typename _RItTraits::difference_type _DistanceType; 01692 01693 if (__result_first == __result_last) 01694 return __result_last; 01695 _RandomAccessIterator __result_real_last = __result_first; 01696 while (__first != __last && __result_real_last != __result_last) 01697 { 01698 *__result_real_last = *__first; 01699 ++__result_real_last; 01700 ++__first; 01701 } 01702 01703 std::__make_heap(__result_first, __result_real_last, __comp); 01704 while (__first != __last) 01705 { 01706 if (__comp(__first, __result_first)) 01707 std::__adjust_heap(__result_first, _DistanceType(0), 01708 _DistanceType(__result_real_last 01709 - __result_first), 01710 _InputValueType(*__first), __comp); 01711 ++__first; 01712 } 01713 std::__sort_heap(__result_first, __result_real_last, __comp); 01714 return __result_real_last; 01715 } 01716 01717 /** 01718 * @brief Copy the smallest elements of a sequence. 01719 * @ingroup sorting_algorithms 01720 * @param __first An iterator. 01721 * @param __last Another iterator. 01722 * @param __result_first A random-access iterator. 01723 * @param __result_last Another random-access iterator. 01724 * @return An iterator indicating the end of the resulting sequence. 01725 * 01726 * Copies and sorts the smallest N values from the range @p [__first,__last) 01727 * to the range beginning at @p __result_first, where the number of 01728 * elements to be copied, @p N, is the smaller of @p (__last-__first) and 01729 * @p (__result_last-__result_first). 01730 * After the sort if @e i and @e j are iterators in the range 01731 * @p [__result_first,__result_first+N) such that i precedes j then 01732 * *j<*i is false. 01733 * The value returned is @p __result_first+N. 01734 */ 01735 template<typename _InputIterator, typename _RandomAccessIterator> 01736 inline _RandomAccessIterator 01737 partial_sort_copy(_InputIterator __first, _InputIterator __last, 01738 _RandomAccessIterator __result_first, 01739 _RandomAccessIterator __result_last) 01740 { 01741 #ifdef _GLIBCXX_CONCEPT_CHECKS 01742 typedef typename iterator_traits<_InputIterator>::value_type 01743 _InputValueType; 01744 typedef typename iterator_traits<_RandomAccessIterator>::value_type 01745 _OutputValueType; 01746 #endif 01747 01748 // concept requirements 01749 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 01750 __glibcxx_function_requires(_ConvertibleConcept<_InputValueType, 01751 _OutputValueType>) 01752 __glibcxx_function_requires(_LessThanOpConcept<_InputValueType, 01753 _OutputValueType>) 01754 __glibcxx_function_requires(_LessThanComparableConcept<_OutputValueType>) 01755 __glibcxx_requires_valid_range(__first, __last); 01756 __glibcxx_requires_irreflexive(__first, __last); 01757 __glibcxx_requires_valid_range(__result_first, __result_last); 01758 01759 return std::__partial_sort_copy(__first, __last, 01760 __result_first, __result_last, 01761 __gnu_cxx::__ops::__iter_less_iter()); 01762 } 01763 01764 /** 01765 * @brief Copy the smallest elements of a sequence using a predicate for 01766 * comparison. 01767 * @ingroup sorting_algorithms 01768 * @param __first An input iterator. 01769 * @param __last Another input iterator. 01770 * @param __result_first A random-access iterator. 01771 * @param __result_last Another random-access iterator. 01772 * @param __comp A comparison functor. 01773 * @return An iterator indicating the end of the resulting sequence. 01774 * 01775 * Copies and sorts the smallest N values from the range @p [__first,__last) 01776 * to the range beginning at @p result_first, where the number of 01777 * elements to be copied, @p N, is the smaller of @p (__last-__first) and 01778 * @p (__result_last-__result_first). 01779 * After the sort if @e i and @e j are iterators in the range 01780 * @p [__result_first,__result_first+N) such that i precedes j then 01781 * @p __comp(*j,*i) is false. 01782 * The value returned is @p __result_first+N. 01783 */ 01784 template<typename _InputIterator, typename _RandomAccessIterator, 01785 typename _Compare> 01786 inline _RandomAccessIterator 01787 partial_sort_copy(_InputIterator __first, _InputIterator __last, 01788 _RandomAccessIterator __result_first, 01789 _RandomAccessIterator __result_last, 01790 _Compare __comp) 01791 { 01792 #ifdef _GLIBCXX_CONCEPT_CHECKS 01793 typedef typename iterator_traits<_InputIterator>::value_type 01794 _InputValueType; 01795 typedef typename iterator_traits<_RandomAccessIterator>::value_type 01796 _OutputValueType; 01797 #endif 01798 01799 // concept requirements 01800 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 01801 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 01802 _RandomAccessIterator>) 01803 __glibcxx_function_requires(_ConvertibleConcept<_InputValueType, 01804 _OutputValueType>) 01805 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 01806 _InputValueType, _OutputValueType>) 01807 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 01808 _OutputValueType, _OutputValueType>) 01809 __glibcxx_requires_valid_range(__first, __last); 01810 __glibcxx_requires_irreflexive_pred(__first, __last, __comp); 01811 __glibcxx_requires_valid_range(__result_first, __result_last); 01812 01813 return std::__partial_sort_copy(__first, __last, 01814 __result_first, __result_last, 01815 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 01816 } 01817 01818 /// This is a helper function for the sort routine. 01819 template<typename _RandomAccessIterator, typename _Compare> 01820 void 01821 __unguarded_linear_insert(_RandomAccessIterator __last, 01822 _Compare __comp) 01823 { 01824 typename iterator_traits<_RandomAccessIterator>::value_type 01825 __val = _GLIBCXX_MOVE(*__last); 01826 _RandomAccessIterator __next = __last; 01827 --__next; 01828 while (__comp(__val, __next)) 01829 { 01830 *__last = _GLIBCXX_MOVE(*__next); 01831 __last = __next; 01832 --__next; 01833 } 01834 *__last = _GLIBCXX_MOVE(__val); 01835 } 01836 01837 /// This is a helper function for the sort routine. 01838 template<typename _RandomAccessIterator, typename _Compare> 01839 void 01840 __insertion_sort(_RandomAccessIterator __first, 01841 _RandomAccessIterator __last, _Compare __comp) 01842 { 01843 if (__first == __last) return; 01844 01845 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i) 01846 { 01847 if (__comp(__i, __first)) 01848 { 01849 typename iterator_traits<_RandomAccessIterator>::value_type 01850 __val = _GLIBCXX_MOVE(*__i); 01851 _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1); 01852 *__first = _GLIBCXX_MOVE(__val); 01853 } 01854 else 01855 std::__unguarded_linear_insert(__i, 01856 __gnu_cxx::__ops::__val_comp_iter(__comp)); 01857 } 01858 } 01859 01860 /// This is a helper function for the sort routine. 01861 template<typename _RandomAccessIterator, typename _Compare> 01862 inline void 01863 __unguarded_insertion_sort(_RandomAccessIterator __first, 01864 _RandomAccessIterator __last, _Compare __comp) 01865 { 01866 for (_RandomAccessIterator __i = __first; __i != __last; ++__i) 01867 std::__unguarded_linear_insert(__i, 01868 __gnu_cxx::__ops::__val_comp_iter(__comp)); 01869 } 01870 01871 /** 01872 * @doctodo 01873 * This controls some aspect of the sort routines. 01874 */ 01875 enum { _S_threshold = 16 }; 01876 01877 /// This is a helper function for the sort routine. 01878 template<typename _RandomAccessIterator, typename _Compare> 01879 void 01880 __final_insertion_sort(_RandomAccessIterator __first, 01881 _RandomAccessIterator __last, _Compare __comp) 01882 { 01883 if (__last - __first > int(_S_threshold)) 01884 { 01885 std::__insertion_sort(__first, __first + int(_S_threshold), __comp); 01886 std::__unguarded_insertion_sort(__first + int(_S_threshold), __last, 01887 __comp); 01888 } 01889 else 01890 std::__insertion_sort(__first, __last, __comp); 01891 } 01892 01893 /// This is a helper function... 01894 template<typename _RandomAccessIterator, typename _Compare> 01895 _RandomAccessIterator 01896 __unguarded_partition(_RandomAccessIterator __first, 01897 _RandomAccessIterator __last, 01898 _RandomAccessIterator __pivot, _Compare __comp) 01899 { 01900 while (true) 01901 { 01902 while (__comp(__first, __pivot)) 01903 ++__first; 01904 --__last; 01905 while (__comp(__pivot, __last)) 01906 --__last; 01907 if (!(__first < __last)) 01908 return __first; 01909 std::iter_swap(__first, __last); 01910 ++__first; 01911 } 01912 } 01913 01914 /// This is a helper function... 01915 template<typename _RandomAccessIterator, typename _Compare> 01916 inline _RandomAccessIterator 01917 __unguarded_partition_pivot(_RandomAccessIterator __first, 01918 _RandomAccessIterator __last, _Compare __comp) 01919 { 01920 _RandomAccessIterator __mid = __first + (__last - __first) / 2; 01921 std::__move_median_to_first(__first, __first + 1, __mid, __last - 1, 01922 __comp); 01923 return std::__unguarded_partition(__first + 1, __last, __first, __comp); 01924 } 01925 01926 template<typename _RandomAccessIterator, typename _Compare> 01927 inline void 01928 __partial_sort(_RandomAccessIterator __first, 01929 _RandomAccessIterator __middle, 01930 _RandomAccessIterator __last, 01931 _Compare __comp) 01932 { 01933 std::__heap_select(__first, __middle, __last, __comp); 01934 std::__sort_heap(__first, __middle, __comp); 01935 } 01936 01937 /// This is a helper function for the sort routine. 01938 template<typename _RandomAccessIterator, typename _Size, typename _Compare> 01939 void 01940 __introsort_loop(_RandomAccessIterator __first, 01941 _RandomAccessIterator __last, 01942 _Size __depth_limit, _Compare __comp) 01943 { 01944 while (__last - __first > int(_S_threshold)) 01945 { 01946 if (__depth_limit == 0) 01947 { 01948 std::__partial_sort(__first, __last, __last, __comp); 01949 return; 01950 } 01951 --__depth_limit; 01952 _RandomAccessIterator __cut = 01953 std::__unguarded_partition_pivot(__first, __last, __comp); 01954 std::__introsort_loop(__cut, __last, __depth_limit, __comp); 01955 __last = __cut; 01956 } 01957 } 01958 01959 // sort 01960 01961 template<typename _RandomAccessIterator, typename _Compare> 01962 inline void 01963 __sort(_RandomAccessIterator __first, _RandomAccessIterator __last, 01964 _Compare __comp) 01965 { 01966 if (__first != __last) 01967 { 01968 std::__introsort_loop(__first, __last, 01969 std::__lg(__last - __first) * 2, 01970 __comp); 01971 std::__final_insertion_sort(__first, __last, __comp); 01972 } 01973 } 01974 01975 template<typename _RandomAccessIterator, typename _Size, typename _Compare> 01976 void 01977 __introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth, 01978 _RandomAccessIterator __last, _Size __depth_limit, 01979 _Compare __comp) 01980 { 01981 while (__last - __first > 3) 01982 { 01983 if (__depth_limit == 0) 01984 { 01985 std::__heap_select(__first, __nth + 1, __last, __comp); 01986 // Place the nth largest element in its final position. 01987 std::iter_swap(__first, __nth); 01988 return; 01989 } 01990 --__depth_limit; 01991 _RandomAccessIterator __cut = 01992 std::__unguarded_partition_pivot(__first, __last, __comp); 01993 if (__cut <= __nth) 01994 __first = __cut; 01995 else 01996 __last = __cut; 01997 } 01998 std::__insertion_sort(__first, __last, __comp); 01999 } 02000 02001 // nth_element 02002 02003 // lower_bound moved to stl_algobase.h 02004 02005 /** 02006 * @brief Finds the first position in which @p __val could be inserted 02007 * without changing the ordering. 02008 * @ingroup binary_search_algorithms 02009 * @param __first An iterator. 02010 * @param __last Another iterator. 02011 * @param __val The search term. 02012 * @param __comp A functor to use for comparisons. 02013 * @return An iterator pointing to the first element <em>not less 02014 * than</em> @p __val, or end() if every element is less 02015 * than @p __val. 02016 * @ingroup binary_search_algorithms 02017 * 02018 * The comparison function should have the same effects on ordering as 02019 * the function used for the initial sort. 02020 */ 02021 template<typename _ForwardIterator, typename _Tp, typename _Compare> 02022 inline _ForwardIterator 02023 lower_bound(_ForwardIterator __first, _ForwardIterator __last, 02024 const _Tp& __val, _Compare __comp) 02025 { 02026 // concept requirements 02027 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 02028 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 02029 typename iterator_traits<_ForwardIterator>::value_type, _Tp>) 02030 __glibcxx_requires_partitioned_lower_pred(__first, __last, 02031 __val, __comp); 02032 02033 return std::__lower_bound(__first, __last, __val, 02034 __gnu_cxx::__ops::__iter_comp_val(__comp)); 02035 } 02036 02037 template<typename _ForwardIterator, typename _Tp, typename _Compare> 02038 _ForwardIterator 02039 __upper_bound(_ForwardIterator __first, _ForwardIterator __last, 02040 const _Tp& __val, _Compare __comp) 02041 { 02042 typedef typename iterator_traits<_ForwardIterator>::difference_type 02043 _DistanceType; 02044 02045 _DistanceType __len = std::distance(__first, __last); 02046 02047 while (__len > 0) 02048 { 02049 _DistanceType __half = __len >> 1; 02050 _ForwardIterator __middle = __first; 02051 std::advance(__middle, __half); 02052 if (__comp(__val, __middle)) 02053 __len = __half; 02054 else 02055 { 02056 __first = __middle; 02057 ++__first; 02058 __len = __len - __half - 1; 02059 } 02060 } 02061 return __first; 02062 } 02063 02064 /** 02065 * @brief Finds the last position in which @p __val could be inserted 02066 * without changing the ordering. 02067 * @ingroup binary_search_algorithms 02068 * @param __first An iterator. 02069 * @param __last Another iterator. 02070 * @param __val The search term. 02071 * @return An iterator pointing to the first element greater than @p __val, 02072 * or end() if no elements are greater than @p __val. 02073 * @ingroup binary_search_algorithms 02074 */ 02075 template<typename _ForwardIterator, typename _Tp> 02076 inline _ForwardIterator 02077 upper_bound(_ForwardIterator __first, _ForwardIterator __last, 02078 const _Tp& __val) 02079 { 02080 // concept requirements 02081 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 02082 __glibcxx_function_requires(_LessThanOpConcept< 02083 _Tp, typename iterator_traits<_ForwardIterator>::value_type>) 02084 __glibcxx_requires_partitioned_upper(__first, __last, __val); 02085 02086 return std::__upper_bound(__first, __last, __val, 02087 __gnu_cxx::__ops::__val_less_iter()); 02088 } 02089 02090 /** 02091 * @brief Finds the last position in which @p __val could be inserted 02092 * without changing the ordering. 02093 * @ingroup binary_search_algorithms 02094 * @param __first An iterator. 02095 * @param __last Another iterator. 02096 * @param __val The search term. 02097 * @param __comp A functor to use for comparisons. 02098 * @return An iterator pointing to the first element greater than @p __val, 02099 * or end() if no elements are greater than @p __val. 02100 * @ingroup binary_search_algorithms 02101 * 02102 * The comparison function should have the same effects on ordering as 02103 * the function used for the initial sort. 02104 */ 02105 template<typename _ForwardIterator, typename _Tp, typename _Compare> 02106 inline _ForwardIterator 02107 upper_bound(_ForwardIterator __first, _ForwardIterator __last, 02108 const _Tp& __val, _Compare __comp) 02109 { 02110 // concept requirements 02111 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 02112 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 02113 _Tp, typename iterator_traits<_ForwardIterator>::value_type>) 02114 __glibcxx_requires_partitioned_upper_pred(__first, __last, 02115 __val, __comp); 02116 02117 return std::__upper_bound(__first, __last, __val, 02118 __gnu_cxx::__ops::__val_comp_iter(__comp)); 02119 } 02120 02121 template<typename _ForwardIterator, typename _Tp, 02122 typename _CompareItTp, typename _CompareTpIt> 02123 pair<_ForwardIterator, _ForwardIterator> 02124 __equal_range(_ForwardIterator __first, _ForwardIterator __last, 02125 const _Tp& __val, 02126 _CompareItTp __comp_it_val, _CompareTpIt __comp_val_it) 02127 { 02128 typedef typename iterator_traits<_ForwardIterator>::difference_type 02129 _DistanceType; 02130 02131 _DistanceType __len = std::distance(__first, __last); 02132 02133 while (__len > 0) 02134 { 02135 _DistanceType __half = __len >> 1; 02136 _ForwardIterator __middle = __first; 02137 std::advance(__middle, __half); 02138 if (__comp_it_val(__middle, __val)) 02139 { 02140 __first = __middle; 02141 ++__first; 02142 __len = __len - __half - 1; 02143 } 02144 else if (__comp_val_it(__val, __middle)) 02145 __len = __half; 02146 else 02147 { 02148 _ForwardIterator __left 02149 = std::__lower_bound(__first, __middle, __val, __comp_it_val); 02150 std::advance(__first, __len); 02151 _ForwardIterator __right 02152 = std::__upper_bound(++__middle, __first, __val, __comp_val_it); 02153 return pair<_ForwardIterator, _ForwardIterator>(__left, __right); 02154 } 02155 } 02156 return pair<_ForwardIterator, _ForwardIterator>(__first, __first); 02157 } 02158 02159 /** 02160 * @brief Finds the largest subrange in which @p __val could be inserted 02161 * at any place in it without changing the ordering. 02162 * @ingroup binary_search_algorithms 02163 * @param __first An iterator. 02164 * @param __last Another iterator. 02165 * @param __val The search term. 02166 * @return An pair of iterators defining the subrange. 02167 * @ingroup binary_search_algorithms 02168 * 02169 * This is equivalent to 02170 * @code 02171 * std::make_pair(lower_bound(__first, __last, __val), 02172 * upper_bound(__first, __last, __val)) 02173 * @endcode 02174 * but does not actually call those functions. 02175 */ 02176 template<typename _ForwardIterator, typename _Tp> 02177 inline pair<_ForwardIterator, _ForwardIterator> 02178 equal_range(_ForwardIterator __first, _ForwardIterator __last, 02179 const _Tp& __val) 02180 { 02181 // concept requirements 02182 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 02183 __glibcxx_function_requires(_LessThanOpConcept< 02184 typename iterator_traits<_ForwardIterator>::value_type, _Tp>) 02185 __glibcxx_function_requires(_LessThanOpConcept< 02186 _Tp, typename iterator_traits<_ForwardIterator>::value_type>) 02187 __glibcxx_requires_partitioned_lower(__first, __last, __val); 02188 __glibcxx_requires_partitioned_upper(__first, __last, __val); 02189 02190 return std::__equal_range(__first, __last, __val, 02191 __gnu_cxx::__ops::__iter_less_val(), 02192 __gnu_cxx::__ops::__val_less_iter()); 02193 } 02194 02195 /** 02196 * @brief Finds the largest subrange in which @p __val could be inserted 02197 * at any place in it without changing the ordering. 02198 * @param __first An iterator. 02199 * @param __last Another iterator. 02200 * @param __val The search term. 02201 * @param __comp A functor to use for comparisons. 02202 * @return An pair of iterators defining the subrange. 02203 * @ingroup binary_search_algorithms 02204 * 02205 * This is equivalent to 02206 * @code 02207 * std::make_pair(lower_bound(__first, __last, __val, __comp), 02208 * upper_bound(__first, __last, __val, __comp)) 02209 * @endcode 02210 * but does not actually call those functions. 02211 */ 02212 template<typename _ForwardIterator, typename _Tp, typename _Compare> 02213 inline pair<_ForwardIterator, _ForwardIterator> 02214 equal_range(_ForwardIterator __first, _ForwardIterator __last, 02215 const _Tp& __val, _Compare __comp) 02216 { 02217 // concept requirements 02218 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 02219 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 02220 typename iterator_traits<_ForwardIterator>::value_type, _Tp>) 02221 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 02222 _Tp, typename iterator_traits<_ForwardIterator>::value_type>) 02223 __glibcxx_requires_partitioned_lower_pred(__first, __last, 02224 __val, __comp); 02225 __glibcxx_requires_partitioned_upper_pred(__first, __last, 02226 __val, __comp); 02227 02228 return std::__equal_range(__first, __last, __val, 02229 __gnu_cxx::__ops::__iter_comp_val(__comp), 02230 __gnu_cxx::__ops::__val_comp_iter(__comp)); 02231 } 02232 02233 /** 02234 * @brief Determines whether an element exists in a range. 02235 * @ingroup binary_search_algorithms 02236 * @param __first An iterator. 02237 * @param __last Another iterator. 02238 * @param __val The search term. 02239 * @return True if @p __val (or its equivalent) is in [@p 02240 * __first,@p __last ]. 02241 * 02242 * Note that this does not actually return an iterator to @p __val. For 02243 * that, use std::find or a container's specialized find member functions. 02244 */ 02245 template<typename _ForwardIterator, typename _Tp> 02246 bool 02247 binary_search(_ForwardIterator __first, _ForwardIterator __last, 02248 const _Tp& __val) 02249 { 02250 // concept requirements 02251 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 02252 __glibcxx_function_requires(_LessThanOpConcept< 02253 _Tp, typename iterator_traits<_ForwardIterator>::value_type>) 02254 __glibcxx_requires_partitioned_lower(__first, __last, __val); 02255 __glibcxx_requires_partitioned_upper(__first, __last, __val); 02256 02257 _ForwardIterator __i 02258 = std::__lower_bound(__first, __last, __val, 02259 __gnu_cxx::__ops::__iter_less_val()); 02260 return __i != __last && !(__val < *__i); 02261 } 02262 02263 /** 02264 * @brief Determines whether an element exists in a range. 02265 * @ingroup binary_search_algorithms 02266 * @param __first An iterator. 02267 * @param __last Another iterator. 02268 * @param __val The search term. 02269 * @param __comp A functor to use for comparisons. 02270 * @return True if @p __val (or its equivalent) is in @p [__first,__last]. 02271 * 02272 * Note that this does not actually return an iterator to @p __val. For 02273 * that, use std::find or a container's specialized find member functions. 02274 * 02275 * The comparison function should have the same effects on ordering as 02276 * the function used for the initial sort. 02277 */ 02278 template<typename _ForwardIterator, typename _Tp, typename _Compare> 02279 bool 02280 binary_search(_ForwardIterator __first, _ForwardIterator __last, 02281 const _Tp& __val, _Compare __comp) 02282 { 02283 // concept requirements 02284 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 02285 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 02286 _Tp, typename iterator_traits<_ForwardIterator>::value_type>) 02287 __glibcxx_requires_partitioned_lower_pred(__first, __last, 02288 __val, __comp); 02289 __glibcxx_requires_partitioned_upper_pred(__first, __last, 02290 __val, __comp); 02291 02292 _ForwardIterator __i 02293 = std::__lower_bound(__first, __last, __val, 02294 __gnu_cxx::__ops::__iter_comp_val(__comp)); 02295 return __i != __last && !bool(__comp(__val, *__i)); 02296 } 02297 02298 // merge 02299 02300 /// This is a helper function for the __merge_adaptive routines. 02301 template<typename _InputIterator1, typename _InputIterator2, 02302 typename _OutputIterator, typename _Compare> 02303 void 02304 __move_merge_adaptive(_InputIterator1 __first1, _InputIterator1 __last1, 02305 _InputIterator2 __first2, _InputIterator2 __last2, 02306 _OutputIterator __result, _Compare __comp) 02307 { 02308 while (__first1 != __last1 && __first2 != __last2) 02309 { 02310 if (__comp(__first2, __first1)) 02311 { 02312 *__result = _GLIBCXX_MOVE(*__first2); 02313 ++__first2; 02314 } 02315 else 02316 { 02317 *__result = _GLIBCXX_MOVE(*__first1); 02318 ++__first1; 02319 } 02320 ++__result; 02321 } 02322 if (__first1 != __last1) 02323 _GLIBCXX_MOVE3(__first1, __last1, __result); 02324 } 02325 02326 /// This is a helper function for the __merge_adaptive routines. 02327 template<typename _BidirectionalIterator1, typename _BidirectionalIterator2, 02328 typename _BidirectionalIterator3, typename _Compare> 02329 void 02330 __move_merge_adaptive_backward(_BidirectionalIterator1 __first1, 02331 _BidirectionalIterator1 __last1, 02332 _BidirectionalIterator2 __first2, 02333 _BidirectionalIterator2 __last2, 02334 _BidirectionalIterator3 __result, 02335 _Compare __comp) 02336 { 02337 if (__first1 == __last1) 02338 { 02339 _GLIBCXX_MOVE_BACKWARD3(__first2, __last2, __result); 02340 return; 02341 } 02342 else if (__first2 == __last2) 02343 return; 02344 02345 --__last1; 02346 --__last2; 02347 while (true) 02348 { 02349 if (__comp(__last2, __last1)) 02350 { 02351 *--__result = _GLIBCXX_MOVE(*__last1); 02352 if (__first1 == __last1) 02353 { 02354 _GLIBCXX_MOVE_BACKWARD3(__first2, ++__last2, __result); 02355 return; 02356 } 02357 --__last1; 02358 } 02359 else 02360 { 02361 *--__result = _GLIBCXX_MOVE(*__last2); 02362 if (__first2 == __last2) 02363 return; 02364 --__last2; 02365 } 02366 } 02367 } 02368 02369 /// This is a helper function for the merge routines. 02370 template<typename _BidirectionalIterator1, typename _BidirectionalIterator2, 02371 typename _Distance> 02372 _BidirectionalIterator1 02373 __rotate_adaptive(_BidirectionalIterator1 __first, 02374 _BidirectionalIterator1 __middle, 02375 _BidirectionalIterator1 __last, 02376 _Distance __len1, _Distance __len2, 02377 _BidirectionalIterator2 __buffer, 02378 _Distance __buffer_size) 02379 { 02380 _BidirectionalIterator2 __buffer_end; 02381 if (__len1 > __len2 && __len2 <= __buffer_size) 02382 { 02383 if (__len2) 02384 { 02385 __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer); 02386 _GLIBCXX_MOVE_BACKWARD3(__first, __middle, __last); 02387 return _GLIBCXX_MOVE3(__buffer, __buffer_end, __first); 02388 } 02389 else 02390 return __first; 02391 } 02392 else if (__len1 <= __buffer_size) 02393 { 02394 if (__len1) 02395 { 02396 __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer); 02397 _GLIBCXX_MOVE3(__middle, __last, __first); 02398 return _GLIBCXX_MOVE_BACKWARD3(__buffer, __buffer_end, __last); 02399 } 02400 else 02401 return __last; 02402 } 02403 else 02404 { 02405 std::rotate(__first, __middle, __last); 02406 std::advance(__first, std::distance(__middle, __last)); 02407 return __first; 02408 } 02409 } 02410 02411 /// This is a helper function for the merge routines. 02412 template<typename _BidirectionalIterator, typename _Distance, 02413 typename _Pointer, typename _Compare> 02414 void 02415 __merge_adaptive(_BidirectionalIterator __first, 02416 _BidirectionalIterator __middle, 02417 _BidirectionalIterator __last, 02418 _Distance __len1, _Distance __len2, 02419 _Pointer __buffer, _Distance __buffer_size, 02420 _Compare __comp) 02421 { 02422 if (__len1 <= __len2 && __len1 <= __buffer_size) 02423 { 02424 _Pointer __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer); 02425 std::__move_merge_adaptive(__buffer, __buffer_end, __middle, __last, 02426 __first, __comp); 02427 } 02428 else if (__len2 <= __buffer_size) 02429 { 02430 _Pointer __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer); 02431 std::__move_merge_adaptive_backward(__first, __middle, __buffer, 02432 __buffer_end, __last, __comp); 02433 } 02434 else 02435 { 02436 _BidirectionalIterator __first_cut = __first; 02437 _BidirectionalIterator __second_cut = __middle; 02438 _Distance __len11 = 0; 02439 _Distance __len22 = 0; 02440 if (__len1 > __len2) 02441 { 02442 __len11 = __len1 / 2; 02443 std::advance(__first_cut, __len11); 02444 __second_cut 02445 = std::__lower_bound(__middle, __last, *__first_cut, 02446 __gnu_cxx::__ops::__iter_comp_val(__comp)); 02447 __len22 = std::distance(__middle, __second_cut); 02448 } 02449 else 02450 { 02451 __len22 = __len2 / 2; 02452 std::advance(__second_cut, __len22); 02453 __first_cut 02454 = std::__upper_bound(__first, __middle, *__second_cut, 02455 __gnu_cxx::__ops::__val_comp_iter(__comp)); 02456 __len11 = std::distance(__first, __first_cut); 02457 } 02458 02459 _BidirectionalIterator __new_middle 02460 = std::__rotate_adaptive(__first_cut, __middle, __second_cut, 02461 __len1 - __len11, __len22, __buffer, 02462 __buffer_size); 02463 std::__merge_adaptive(__first, __first_cut, __new_middle, __len11, 02464 __len22, __buffer, __buffer_size, __comp); 02465 std::__merge_adaptive(__new_middle, __second_cut, __last, 02466 __len1 - __len11, 02467 __len2 - __len22, __buffer, 02468 __buffer_size, __comp); 02469 } 02470 } 02471 02472 /// This is a helper function for the merge routines. 02473 template<typename _BidirectionalIterator, typename _Distance, 02474 typename _Compare> 02475 void 02476 __merge_without_buffer(_BidirectionalIterator __first, 02477 _BidirectionalIterator __middle, 02478 _BidirectionalIterator __last, 02479 _Distance __len1, _Distance __len2, 02480 _Compare __comp) 02481 { 02482 if (__len1 == 0 || __len2 == 0) 02483 return; 02484 02485 if (__len1 + __len2 == 2) 02486 { 02487 if (__comp(__middle, __first)) 02488 std::iter_swap(__first, __middle); 02489 return; 02490 } 02491 02492 _BidirectionalIterator __first_cut = __first; 02493 _BidirectionalIterator __second_cut = __middle; 02494 _Distance __len11 = 0; 02495 _Distance __len22 = 0; 02496 if (__len1 > __len2) 02497 { 02498 __len11 = __len1 / 2; 02499 std::advance(__first_cut, __len11); 02500 __second_cut 02501 = std::__lower_bound(__middle, __last, *__first_cut, 02502 __gnu_cxx::__ops::__iter_comp_val(__comp)); 02503 __len22 = std::distance(__middle, __second_cut); 02504 } 02505 else 02506 { 02507 __len22 = __len2 / 2; 02508 std::advance(__second_cut, __len22); 02509 __first_cut 02510 = std::__upper_bound(__first, __middle, *__second_cut, 02511 __gnu_cxx::__ops::__val_comp_iter(__comp)); 02512 __len11 = std::distance(__first, __first_cut); 02513 } 02514 02515 std::rotate(__first_cut, __middle, __second_cut); 02516 _BidirectionalIterator __new_middle = __first_cut; 02517 std::advance(__new_middle, std::distance(__middle, __second_cut)); 02518 std::__merge_without_buffer(__first, __first_cut, __new_middle, 02519 __len11, __len22, __comp); 02520 std::__merge_without_buffer(__new_middle, __second_cut, __last, 02521 __len1 - __len11, __len2 - __len22, __comp); 02522 } 02523 02524 template<typename _BidirectionalIterator, typename _Compare> 02525 void 02526 __inplace_merge(_BidirectionalIterator __first, 02527 _BidirectionalIterator __middle, 02528 _BidirectionalIterator __last, 02529 _Compare __comp) 02530 { 02531 typedef typename iterator_traits<_BidirectionalIterator>::value_type 02532 _ValueType; 02533 typedef typename iterator_traits<_BidirectionalIterator>::difference_type 02534 _DistanceType; 02535 02536 if (__first == __middle || __middle == __last) 02537 return; 02538 02539 const _DistanceType __len1 = std::distance(__first, __middle); 02540 const _DistanceType __len2 = std::distance(__middle, __last); 02541 02542 typedef _Temporary_buffer<_BidirectionalIterator, _ValueType> _TmpBuf; 02543 _TmpBuf __buf(__first, __last); 02544 02545 if (__buf.begin() == 0) 02546 std::__merge_without_buffer 02547 (__first, __middle, __last, __len1, __len2, __comp); 02548 else 02549 std::__merge_adaptive 02550 (__first, __middle, __last, __len1, __len2, __buf.begin(), 02551 _DistanceType(__buf.size()), __comp); 02552 } 02553 02554 /** 02555 * @brief Merges two sorted ranges in place. 02556 * @ingroup sorting_algorithms 02557 * @param __first An iterator. 02558 * @param __middle Another iterator. 02559 * @param __last Another iterator. 02560 * @return Nothing. 02561 * 02562 * Merges two sorted and consecutive ranges, [__first,__middle) and 02563 * [__middle,__last), and puts the result in [__first,__last). The 02564 * output will be sorted. The sort is @e stable, that is, for 02565 * equivalent elements in the two ranges, elements from the first 02566 * range will always come before elements from the second. 02567 * 02568 * If enough additional memory is available, this takes (__last-__first)-1 02569 * comparisons. Otherwise an NlogN algorithm is used, where N is 02570 * distance(__first,__last). 02571 */ 02572 template<typename _BidirectionalIterator> 02573 inline void 02574 inplace_merge(_BidirectionalIterator __first, 02575 _BidirectionalIterator __middle, 02576 _BidirectionalIterator __last) 02577 { 02578 // concept requirements 02579 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept< 02580 _BidirectionalIterator>) 02581 __glibcxx_function_requires(_LessThanComparableConcept< 02582 typename iterator_traits<_BidirectionalIterator>::value_type>) 02583 __glibcxx_requires_sorted(__first, __middle); 02584 __glibcxx_requires_sorted(__middle, __last); 02585 __glibcxx_requires_irreflexive(__first, __last); 02586 02587 std::__inplace_merge(__first, __middle, __last, 02588 __gnu_cxx::__ops::__iter_less_iter()); 02589 } 02590 02591 /** 02592 * @brief Merges two sorted ranges in place. 02593 * @ingroup sorting_algorithms 02594 * @param __first An iterator. 02595 * @param __middle Another iterator. 02596 * @param __last Another iterator. 02597 * @param __comp A functor to use for comparisons. 02598 * @return Nothing. 02599 * 02600 * Merges two sorted and consecutive ranges, [__first,__middle) and 02601 * [middle,last), and puts the result in [__first,__last). The output will 02602 * be sorted. The sort is @e stable, that is, for equivalent 02603 * elements in the two ranges, elements from the first range will always 02604 * come before elements from the second. 02605 * 02606 * If enough additional memory is available, this takes (__last-__first)-1 02607 * comparisons. Otherwise an NlogN algorithm is used, where N is 02608 * distance(__first,__last). 02609 * 02610 * The comparison function should have the same effects on ordering as 02611 * the function used for the initial sort. 02612 */ 02613 template<typename _BidirectionalIterator, typename _Compare> 02614 inline void 02615 inplace_merge(_BidirectionalIterator __first, 02616 _BidirectionalIterator __middle, 02617 _BidirectionalIterator __last, 02618 _Compare __comp) 02619 { 02620 // concept requirements 02621 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept< 02622 _BidirectionalIterator>) 02623 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 02624 typename iterator_traits<_BidirectionalIterator>::value_type, 02625 typename iterator_traits<_BidirectionalIterator>::value_type>) 02626 __glibcxx_requires_sorted_pred(__first, __middle, __comp); 02627 __glibcxx_requires_sorted_pred(__middle, __last, __comp); 02628 __glibcxx_requires_irreflexive_pred(__first, __last, __comp); 02629 02630 std::__inplace_merge(__first, __middle, __last, 02631 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 02632 } 02633 02634 02635 /// This is a helper function for the __merge_sort_loop routines. 02636 template<typename _InputIterator, typename _OutputIterator, 02637 typename _Compare> 02638 _OutputIterator 02639 __move_merge(_InputIterator __first1, _InputIterator __last1, 02640 _InputIterator __first2, _InputIterator __last2, 02641 _OutputIterator __result, _Compare __comp) 02642 { 02643 while (__first1 != __last1 && __first2 != __last2) 02644 { 02645 if (__comp(__first2, __first1)) 02646 { 02647 *__result = _GLIBCXX_MOVE(*__first2); 02648 ++__first2; 02649 } 02650 else 02651 { 02652 *__result = _GLIBCXX_MOVE(*__first1); 02653 ++__first1; 02654 } 02655 ++__result; 02656 } 02657 return _GLIBCXX_MOVE3(__first2, __last2, 02658 _GLIBCXX_MOVE3(__first1, __last1, 02659 __result)); 02660 } 02661 02662 template<typename _RandomAccessIterator1, typename _RandomAccessIterator2, 02663 typename _Distance, typename _Compare> 02664 void 02665 __merge_sort_loop(_RandomAccessIterator1 __first, 02666 _RandomAccessIterator1 __last, 02667 _RandomAccessIterator2 __result, _Distance __step_size, 02668 _Compare __comp) 02669 { 02670 const _Distance __two_step = 2 * __step_size; 02671 02672 while (__last - __first >= __two_step) 02673 { 02674 __result = std::__move_merge(__first, __first + __step_size, 02675 __first + __step_size, 02676 __first + __two_step, 02677 __result, __comp); 02678 __first += __two_step; 02679 } 02680 __step_size = std::min(_Distance(__last - __first), __step_size); 02681 02682 std::__move_merge(__first, __first + __step_size, 02683 __first + __step_size, __last, __result, __comp); 02684 } 02685 02686 template<typename _RandomAccessIterator, typename _Distance, 02687 typename _Compare> 02688 void 02689 __chunk_insertion_sort(_RandomAccessIterator __first, 02690 _RandomAccessIterator __last, 02691 _Distance __chunk_size, _Compare __comp) 02692 { 02693 while (__last - __first >= __chunk_size) 02694 { 02695 std::__insertion_sort(__first, __first + __chunk_size, __comp); 02696 __first += __chunk_size; 02697 } 02698 std::__insertion_sort(__first, __last, __comp); 02699 } 02700 02701 enum { _S_chunk_size = 7 }; 02702 02703 template<typename _RandomAccessIterator, typename _Pointer, typename _Compare> 02704 void 02705 __merge_sort_with_buffer(_RandomAccessIterator __first, 02706 _RandomAccessIterator __last, 02707 _Pointer __buffer, _Compare __comp) 02708 { 02709 typedef typename iterator_traits<_RandomAccessIterator>::difference_type 02710 _Distance; 02711 02712 const _Distance __len = __last - __first; 02713 const _Pointer __buffer_last = __buffer + __len; 02714 02715 _Distance __step_size = _S_chunk_size; 02716 std::__chunk_insertion_sort(__first, __last, __step_size, __comp); 02717 02718 while (__step_size < __len) 02719 { 02720 std::__merge_sort_loop(__first, __last, __buffer, 02721 __step_size, __comp); 02722 __step_size *= 2; 02723 std::__merge_sort_loop(__buffer, __buffer_last, __first, 02724 __step_size, __comp); 02725 __step_size *= 2; 02726 } 02727 } 02728 02729 template<typename _RandomAccessIterator, typename _Pointer, 02730 typename _Distance, typename _Compare> 02731 void 02732 __stable_sort_adaptive(_RandomAccessIterator __first, 02733 _RandomAccessIterator __last, 02734 _Pointer __buffer, _Distance __buffer_size, 02735 _Compare __comp) 02736 { 02737 const _Distance __len = (__last - __first + 1) / 2; 02738 const _RandomAccessIterator __middle = __first + __len; 02739 if (__len > __buffer_size) 02740 { 02741 std::__stable_sort_adaptive(__first, __middle, __buffer, 02742 __buffer_size, __comp); 02743 std::__stable_sort_adaptive(__middle, __last, __buffer, 02744 __buffer_size, __comp); 02745 } 02746 else 02747 { 02748 std::__merge_sort_with_buffer(__first, __middle, __buffer, __comp); 02749 std::__merge_sort_with_buffer(__middle, __last, __buffer, __comp); 02750 } 02751 std::__merge_adaptive(__first, __middle, __last, 02752 _Distance(__middle - __first), 02753 _Distance(__last - __middle), 02754 __buffer, __buffer_size, 02755 __comp); 02756 } 02757 02758 /// This is a helper function for the stable sorting routines. 02759 template<typename _RandomAccessIterator, typename _Compare> 02760 void 02761 __inplace_stable_sort(_RandomAccessIterator __first, 02762 _RandomAccessIterator __last, _Compare __comp) 02763 { 02764 if (__last - __first < 15) 02765 { 02766 std::__insertion_sort(__first, __last, __comp); 02767 return; 02768 } 02769 _RandomAccessIterator __middle = __first + (__last - __first) / 2; 02770 std::__inplace_stable_sort(__first, __middle, __comp); 02771 std::__inplace_stable_sort(__middle, __last, __comp); 02772 std::__merge_without_buffer(__first, __middle, __last, 02773 __middle - __first, 02774 __last - __middle, 02775 __comp); 02776 } 02777 02778 // stable_sort 02779 02780 // Set algorithms: includes, set_union, set_intersection, set_difference, 02781 // set_symmetric_difference. All of these algorithms have the precondition 02782 // that their input ranges are sorted and the postcondition that their output 02783 // ranges are sorted. 02784 02785 template<typename _InputIterator1, typename _InputIterator2, 02786 typename _Compare> 02787 bool 02788 __includes(_InputIterator1 __first1, _InputIterator1 __last1, 02789 _InputIterator2 __first2, _InputIterator2 __last2, 02790 _Compare __comp) 02791 { 02792 while (__first1 != __last1 && __first2 != __last2) 02793 if (__comp(__first2, __first1)) 02794 return false; 02795 else if (__comp(__first1, __first2)) 02796 ++__first1; 02797 else 02798 { 02799 ++__first1; 02800 ++__first2; 02801 } 02802 02803 return __first2 == __last2; 02804 } 02805 02806 /** 02807 * @brief Determines whether all elements of a sequence exists in a range. 02808 * @param __first1 Start of search range. 02809 * @param __last1 End of search range. 02810 * @param __first2 Start of sequence 02811 * @param __last2 End of sequence. 02812 * @return True if each element in [__first2,__last2) is contained in order 02813 * within [__first1,__last1). False otherwise. 02814 * @ingroup set_algorithms 02815 * 02816 * This operation expects both [__first1,__last1) and 02817 * [__first2,__last2) to be sorted. Searches for the presence of 02818 * each element in [__first2,__last2) within [__first1,__last1). 02819 * The iterators over each range only move forward, so this is a 02820 * linear algorithm. If an element in [__first2,__last2) is not 02821 * found before the search iterator reaches @p __last2, false is 02822 * returned. 02823 */ 02824 template<typename _InputIterator1, typename _InputIterator2> 02825 inline bool 02826 includes(_InputIterator1 __first1, _InputIterator1 __last1, 02827 _InputIterator2 __first2, _InputIterator2 __last2) 02828 { 02829 // concept requirements 02830 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 02831 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 02832 __glibcxx_function_requires(_LessThanOpConcept< 02833 typename iterator_traits<_InputIterator1>::value_type, 02834 typename iterator_traits<_InputIterator2>::value_type>) 02835 __glibcxx_function_requires(_LessThanOpConcept< 02836 typename iterator_traits<_InputIterator2>::value_type, 02837 typename iterator_traits<_InputIterator1>::value_type>) 02838 __glibcxx_requires_sorted_set(__first1, __last1, __first2); 02839 __glibcxx_requires_sorted_set(__first2, __last2, __first1); 02840 __glibcxx_requires_irreflexive2(__first1, __last1); 02841 __glibcxx_requires_irreflexive2(__first2, __last2); 02842 02843 return std::__includes(__first1, __last1, __first2, __last2, 02844 __gnu_cxx::__ops::__iter_less_iter()); 02845 } 02846 02847 /** 02848 * @brief Determines whether all elements of a sequence exists in a range 02849 * using comparison. 02850 * @ingroup set_algorithms 02851 * @param __first1 Start of search range. 02852 * @param __last1 End of search range. 02853 * @param __first2 Start of sequence 02854 * @param __last2 End of sequence. 02855 * @param __comp Comparison function to use. 02856 * @return True if each element in [__first2,__last2) is contained 02857 * in order within [__first1,__last1) according to comp. False 02858 * otherwise. @ingroup set_algorithms 02859 * 02860 * This operation expects both [__first1,__last1) and 02861 * [__first2,__last2) to be sorted. Searches for the presence of 02862 * each element in [__first2,__last2) within [__first1,__last1), 02863 * using comp to decide. The iterators over each range only move 02864 * forward, so this is a linear algorithm. If an element in 02865 * [__first2,__last2) is not found before the search iterator 02866 * reaches @p __last2, false is returned. 02867 */ 02868 template<typename _InputIterator1, typename _InputIterator2, 02869 typename _Compare> 02870 inline bool 02871 includes(_InputIterator1 __first1, _InputIterator1 __last1, 02872 _InputIterator2 __first2, _InputIterator2 __last2, 02873 _Compare __comp) 02874 { 02875 // concept requirements 02876 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 02877 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 02878 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 02879 typename iterator_traits<_InputIterator1>::value_type, 02880 typename iterator_traits<_InputIterator2>::value_type>) 02881 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 02882 typename iterator_traits<_InputIterator2>::value_type, 02883 typename iterator_traits<_InputIterator1>::value_type>) 02884 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp); 02885 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp); 02886 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp); 02887 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp); 02888 02889 return std::__includes(__first1, __last1, __first2, __last2, 02890 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 02891 } 02892 02893 // nth_element 02894 // merge 02895 // set_difference 02896 // set_intersection 02897 // set_union 02898 // stable_sort 02899 // set_symmetric_difference 02900 // min_element 02901 // max_element 02902 02903 template<typename _BidirectionalIterator, typename _Compare> 02904 bool 02905 __next_permutation(_BidirectionalIterator __first, 02906 _BidirectionalIterator __last, _Compare __comp) 02907 { 02908 if (__first == __last) 02909 return false; 02910 _BidirectionalIterator __i = __first; 02911 ++__i; 02912 if (__i == __last) 02913 return false; 02914 __i = __last; 02915 --__i; 02916 02917 for(;;) 02918 { 02919 _BidirectionalIterator __ii = __i; 02920 --__i; 02921 if (__comp(__i, __ii)) 02922 { 02923 _BidirectionalIterator __j = __last; 02924 while (!__comp(__i, --__j)) 02925 {} 02926 std::iter_swap(__i, __j); 02927 std::__reverse(__ii, __last, 02928 std::__iterator_category(__first)); 02929 return true; 02930 } 02931 if (__i == __first) 02932 { 02933 std::__reverse(__first, __last, 02934 std::__iterator_category(__first)); 02935 return false; 02936 } 02937 } 02938 } 02939 02940 /** 02941 * @brief Permute range into the next @e dictionary ordering. 02942 * @ingroup sorting_algorithms 02943 * @param __first Start of range. 02944 * @param __last End of range. 02945 * @return False if wrapped to first permutation, true otherwise. 02946 * 02947 * Treats all permutations of the range as a set of @e dictionary sorted 02948 * sequences. Permutes the current sequence into the next one of this set. 02949 * Returns true if there are more sequences to generate. If the sequence 02950 * is the largest of the set, the smallest is generated and false returned. 02951 */ 02952 template<typename _BidirectionalIterator> 02953 inline bool 02954 next_permutation(_BidirectionalIterator __first, 02955 _BidirectionalIterator __last) 02956 { 02957 // concept requirements 02958 __glibcxx_function_requires(_BidirectionalIteratorConcept< 02959 _BidirectionalIterator>) 02960 __glibcxx_function_requires(_LessThanComparableConcept< 02961 typename iterator_traits<_BidirectionalIterator>::value_type>) 02962 __glibcxx_requires_valid_range(__first, __last); 02963 __glibcxx_requires_irreflexive(__first, __last); 02964 02965 return std::__next_permutation 02966 (__first, __last, __gnu_cxx::__ops::__iter_less_iter()); 02967 } 02968 02969 /** 02970 * @brief Permute range into the next @e dictionary ordering using 02971 * comparison functor. 02972 * @ingroup sorting_algorithms 02973 * @param __first Start of range. 02974 * @param __last End of range. 02975 * @param __comp A comparison functor. 02976 * @return False if wrapped to first permutation, true otherwise. 02977 * 02978 * Treats all permutations of the range [__first,__last) as a set of 02979 * @e dictionary sorted sequences ordered by @p __comp. Permutes the current 02980 * sequence into the next one of this set. Returns true if there are more 02981 * sequences to generate. If the sequence is the largest of the set, the 02982 * smallest is generated and false returned. 02983 */ 02984 template<typename _BidirectionalIterator, typename _Compare> 02985 inline bool 02986 next_permutation(_BidirectionalIterator __first, 02987 _BidirectionalIterator __last, _Compare __comp) 02988 { 02989 // concept requirements 02990 __glibcxx_function_requires(_BidirectionalIteratorConcept< 02991 _BidirectionalIterator>) 02992 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 02993 typename iterator_traits<_BidirectionalIterator>::value_type, 02994 typename iterator_traits<_BidirectionalIterator>::value_type>) 02995 __glibcxx_requires_valid_range(__first, __last); 02996 __glibcxx_requires_irreflexive_pred(__first, __last, __comp); 02997 02998 return std::__next_permutation 02999 (__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp)); 03000 } 03001 03002 template<typename _BidirectionalIterator, typename _Compare> 03003 bool 03004 __prev_permutation(_BidirectionalIterator __first, 03005 _BidirectionalIterator __last, _Compare __comp) 03006 { 03007 if (__first == __last) 03008 return false; 03009 _BidirectionalIterator __i = __first; 03010 ++__i; 03011 if (__i == __last) 03012 return false; 03013 __i = __last; 03014 --__i; 03015 03016 for(;;) 03017 { 03018 _BidirectionalIterator __ii = __i; 03019 --__i; 03020 if (__comp(__ii, __i)) 03021 { 03022 _BidirectionalIterator __j = __last; 03023 while (!__comp(--__j, __i)) 03024 {} 03025 std::iter_swap(__i, __j); 03026 std::__reverse(__ii, __last, 03027 std::__iterator_category(__first)); 03028 return true; 03029 } 03030 if (__i == __first) 03031 { 03032 std::__reverse(__first, __last, 03033 std::__iterator_category(__first)); 03034 return false; 03035 } 03036 } 03037 } 03038 03039 /** 03040 * @brief Permute range into the previous @e dictionary ordering. 03041 * @ingroup sorting_algorithms 03042 * @param __first Start of range. 03043 * @param __last End of range. 03044 * @return False if wrapped to last permutation, true otherwise. 03045 * 03046 * Treats all permutations of the range as a set of @e dictionary sorted 03047 * sequences. Permutes the current sequence into the previous one of this 03048 * set. Returns true if there are more sequences to generate. If the 03049 * sequence is the smallest of the set, the largest is generated and false 03050 * returned. 03051 */ 03052 template<typename _BidirectionalIterator> 03053 inline bool 03054 prev_permutation(_BidirectionalIterator __first, 03055 _BidirectionalIterator __last) 03056 { 03057 // concept requirements 03058 __glibcxx_function_requires(_BidirectionalIteratorConcept< 03059 _BidirectionalIterator>) 03060 __glibcxx_function_requires(_LessThanComparableConcept< 03061 typename iterator_traits<_BidirectionalIterator>::value_type>) 03062 __glibcxx_requires_valid_range(__first, __last); 03063 __glibcxx_requires_irreflexive(__first, __last); 03064 03065 return std::__prev_permutation(__first, __last, 03066 __gnu_cxx::__ops::__iter_less_iter()); 03067 } 03068 03069 /** 03070 * @brief Permute range into the previous @e dictionary ordering using 03071 * comparison functor. 03072 * @ingroup sorting_algorithms 03073 * @param __first Start of range. 03074 * @param __last End of range. 03075 * @param __comp A comparison functor. 03076 * @return False if wrapped to last permutation, true otherwise. 03077 * 03078 * Treats all permutations of the range [__first,__last) as a set of 03079 * @e dictionary sorted sequences ordered by @p __comp. Permutes the current 03080 * sequence into the previous one of this set. Returns true if there are 03081 * more sequences to generate. If the sequence is the smallest of the set, 03082 * the largest is generated and false returned. 03083 */ 03084 template<typename _BidirectionalIterator, typename _Compare> 03085 inline bool 03086 prev_permutation(_BidirectionalIterator __first, 03087 _BidirectionalIterator __last, _Compare __comp) 03088 { 03089 // concept requirements 03090 __glibcxx_function_requires(_BidirectionalIteratorConcept< 03091 _BidirectionalIterator>) 03092 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 03093 typename iterator_traits<_BidirectionalIterator>::value_type, 03094 typename iterator_traits<_BidirectionalIterator>::value_type>) 03095 __glibcxx_requires_valid_range(__first, __last); 03096 __glibcxx_requires_irreflexive_pred(__first, __last, __comp); 03097 03098 return std::__prev_permutation(__first, __last, 03099 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 03100 } 03101 03102 // replace 03103 // replace_if 03104 03105 template<typename _InputIterator, typename _OutputIterator, 03106 typename _Predicate, typename _Tp> 03107 _OutputIterator 03108 __replace_copy_if(_InputIterator __first, _InputIterator __last, 03109 _OutputIterator __result, 03110 _Predicate __pred, const _Tp& __new_value) 03111 { 03112 for (; __first != __last; ++__first, (void)++__result) 03113 if (__pred(__first)) 03114 *__result = __new_value; 03115 else 03116 *__result = *__first; 03117 return __result; 03118 } 03119 03120 /** 03121 * @brief Copy a sequence, replacing each element of one value with another 03122 * value. 03123 * @param __first An input iterator. 03124 * @param __last An input iterator. 03125 * @param __result An output iterator. 03126 * @param __old_value The value to be replaced. 03127 * @param __new_value The replacement value. 03128 * @return The end of the output sequence, @p result+(last-first). 03129 * 03130 * Copies each element in the input range @p [__first,__last) to the 03131 * output range @p [__result,__result+(__last-__first)) replacing elements 03132 * equal to @p __old_value with @p __new_value. 03133 */ 03134 template<typename _InputIterator, typename _OutputIterator, typename _Tp> 03135 inline _OutputIterator 03136 replace_copy(_InputIterator __first, _InputIterator __last, 03137 _OutputIterator __result, 03138 const _Tp& __old_value, const _Tp& __new_value) 03139 { 03140 // concept requirements 03141 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 03142 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 03143 typename iterator_traits<_InputIterator>::value_type>) 03144 __glibcxx_function_requires(_EqualOpConcept< 03145 typename iterator_traits<_InputIterator>::value_type, _Tp>) 03146 __glibcxx_requires_valid_range(__first, __last); 03147 03148 return std::__replace_copy_if(__first, __last, __result, 03149 __gnu_cxx::__ops::__iter_equals_val(__old_value), 03150 __new_value); 03151 } 03152 03153 /** 03154 * @brief Copy a sequence, replacing each value for which a predicate 03155 * returns true with another value. 03156 * @ingroup mutating_algorithms 03157 * @param __first An input iterator. 03158 * @param __last An input iterator. 03159 * @param __result An output iterator. 03160 * @param __pred A predicate. 03161 * @param __new_value The replacement value. 03162 * @return The end of the output sequence, @p __result+(__last-__first). 03163 * 03164 * Copies each element in the range @p [__first,__last) to the range 03165 * @p [__result,__result+(__last-__first)) replacing elements for which 03166 * @p __pred returns true with @p __new_value. 03167 */ 03168 template<typename _InputIterator, typename _OutputIterator, 03169 typename _Predicate, typename _Tp> 03170 inline _OutputIterator 03171 replace_copy_if(_InputIterator __first, _InputIterator __last, 03172 _OutputIterator __result, 03173 _Predicate __pred, const _Tp& __new_value) 03174 { 03175 // concept requirements 03176 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 03177 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 03178 typename iterator_traits<_InputIterator>::value_type>) 03179 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 03180 typename iterator_traits<_InputIterator>::value_type>) 03181 __glibcxx_requires_valid_range(__first, __last); 03182 03183 return std::__replace_copy_if(__first, __last, __result, 03184 __gnu_cxx::__ops::__pred_iter(__pred), 03185 __new_value); 03186 } 03187 03188 template<typename _InputIterator, typename _Predicate> 03189 typename iterator_traits<_InputIterator>::difference_type 03190 __count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred) 03191 { 03192 typename iterator_traits<_InputIterator>::difference_type __n = 0; 03193 for (; __first != __last; ++__first) 03194 if (__pred(__first)) 03195 ++__n; 03196 return __n; 03197 } 03198 03199 #if __cplusplus >= 201103L 03200 /** 03201 * @brief Determines whether the elements of a sequence are sorted. 03202 * @ingroup sorting_algorithms 03203 * @param __first An iterator. 03204 * @param __last Another iterator. 03205 * @return True if the elements are sorted, false otherwise. 03206 */ 03207 template<typename _ForwardIterator> 03208 inline bool 03209 is_sorted(_ForwardIterator __first, _ForwardIterator __last) 03210 { return std::is_sorted_until(__first, __last) == __last; } 03211 03212 /** 03213 * @brief Determines whether the elements of a sequence are sorted 03214 * according to a comparison functor. 03215 * @ingroup sorting_algorithms 03216 * @param __first An iterator. 03217 * @param __last Another iterator. 03218 * @param __comp A comparison functor. 03219 * @return True if the elements are sorted, false otherwise. 03220 */ 03221 template<typename _ForwardIterator, typename _Compare> 03222 inline bool 03223 is_sorted(_ForwardIterator __first, _ForwardIterator __last, 03224 _Compare __comp) 03225 { return std::is_sorted_until(__first, __last, __comp) == __last; } 03226 03227 template<typename _ForwardIterator, typename _Compare> 03228 _ForwardIterator 03229 __is_sorted_until(_ForwardIterator __first, _ForwardIterator __last, 03230 _Compare __comp) 03231 { 03232 if (__first == __last) 03233 return __last; 03234 03235 _ForwardIterator __next = __first; 03236 for (++__next; __next != __last; __first = __next, (void)++__next) 03237 if (__comp(__next, __first)) 03238 return __next; 03239 return __next; 03240 } 03241 03242 /** 03243 * @brief Determines the end of a sorted sequence. 03244 * @ingroup sorting_algorithms 03245 * @param __first An iterator. 03246 * @param __last Another iterator. 03247 * @return An iterator pointing to the last iterator i in [__first, __last) 03248 * for which the range [__first, i) is sorted. 03249 */ 03250 template<typename _ForwardIterator> 03251 inline _ForwardIterator 03252 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last) 03253 { 03254 // concept requirements 03255 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 03256 __glibcxx_function_requires(_LessThanComparableConcept< 03257 typename iterator_traits<_ForwardIterator>::value_type>) 03258 __glibcxx_requires_valid_range(__first, __last); 03259 __glibcxx_requires_irreflexive(__first, __last); 03260 03261 return std::__is_sorted_until(__first, __last, 03262 __gnu_cxx::__ops::__iter_less_iter()); 03263 } 03264 03265 /** 03266 * @brief Determines the end of a sorted sequence using comparison functor. 03267 * @ingroup sorting_algorithms 03268 * @param __first An iterator. 03269 * @param __last Another iterator. 03270 * @param __comp A comparison functor. 03271 * @return An iterator pointing to the last iterator i in [__first, __last) 03272 * for which the range [__first, i) is sorted. 03273 */ 03274 template<typename _ForwardIterator, typename _Compare> 03275 inline _ForwardIterator 03276 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last, 03277 _Compare __comp) 03278 { 03279 // concept requirements 03280 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 03281 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 03282 typename iterator_traits<_ForwardIterator>::value_type, 03283 typename iterator_traits<_ForwardIterator>::value_type>) 03284 __glibcxx_requires_valid_range(__first, __last); 03285 __glibcxx_requires_irreflexive_pred(__first, __last, __comp); 03286 03287 return std::__is_sorted_until(__first, __last, 03288 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 03289 } 03290 03291 /** 03292 * @brief Determines min and max at once as an ordered pair. 03293 * @ingroup sorting_algorithms 03294 * @param __a A thing of arbitrary type. 03295 * @param __b Another thing of arbitrary type. 03296 * @return A pair(__b, __a) if __b is smaller than __a, pair(__a, 03297 * __b) otherwise. 03298 */ 03299 template<typename _Tp> 03300 _GLIBCXX14_CONSTEXPR 03301 inline pair<const _Tp&, const _Tp&> 03302 minmax(const _Tp& __a, const _Tp& __b) 03303 { 03304 // concept requirements 03305 __glibcxx_function_requires(_LessThanComparableConcept<_Tp>) 03306 03307 return __b < __a ? pair<const _Tp&, const _Tp&>(__b, __a) 03308 : pair<const _Tp&, const _Tp&>(__a, __b); 03309 } 03310 03311 /** 03312 * @brief Determines min and max at once as an ordered pair. 03313 * @ingroup sorting_algorithms 03314 * @param __a A thing of arbitrary type. 03315 * @param __b Another thing of arbitrary type. 03316 * @param __comp A @link comparison_functors comparison functor @endlink. 03317 * @return A pair(__b, __a) if __b is smaller than __a, pair(__a, 03318 * __b) otherwise. 03319 */ 03320 template<typename _Tp, typename _Compare> 03321 _GLIBCXX14_CONSTEXPR 03322 inline pair<const _Tp&, const _Tp&> 03323 minmax(const _Tp& __a, const _Tp& __b, _Compare __comp) 03324 { 03325 return __comp(__b, __a) ? pair<const _Tp&, const _Tp&>(__b, __a) 03326 : pair<const _Tp&, const _Tp&>(__a, __b); 03327 } 03328 03329 template<typename _ForwardIterator, typename _Compare> 03330 _GLIBCXX14_CONSTEXPR 03331 pair<_ForwardIterator, _ForwardIterator> 03332 __minmax_element(_ForwardIterator __first, _ForwardIterator __last, 03333 _Compare __comp) 03334 { 03335 _ForwardIterator __next = __first; 03336 if (__first == __last 03337 || ++__next == __last) 03338 return std::make_pair(__first, __first); 03339 03340 _ForwardIterator __min{}, __max{}; 03341 if (__comp(__next, __first)) 03342 { 03343 __min = __next; 03344 __max = __first; 03345 } 03346 else 03347 { 03348 __min = __first; 03349 __max = __next; 03350 } 03351 03352 __first = __next; 03353 ++__first; 03354 03355 while (__first != __last) 03356 { 03357 __next = __first; 03358 if (++__next == __last) 03359 { 03360 if (__comp(__first, __min)) 03361 __min = __first; 03362 else if (!__comp(__first, __max)) 03363 __max = __first; 03364 break; 03365 } 03366 03367 if (__comp(__next, __first)) 03368 { 03369 if (__comp(__next, __min)) 03370 __min = __next; 03371 if (!__comp(__first, __max)) 03372 __max = __first; 03373 } 03374 else 03375 { 03376 if (__comp(__first, __min)) 03377 __min = __first; 03378 if (!__comp(__next, __max)) 03379 __max = __next; 03380 } 03381 03382 __first = __next; 03383 ++__first; 03384 } 03385 03386 return std::make_pair(__min, __max); 03387 } 03388 03389 /** 03390 * @brief Return a pair of iterators pointing to the minimum and maximum 03391 * elements in a range. 03392 * @ingroup sorting_algorithms 03393 * @param __first Start of range. 03394 * @param __last End of range. 03395 * @return make_pair(m, M), where m is the first iterator i in 03396 * [__first, __last) such that no other element in the range is 03397 * smaller, and where M is the last iterator i in [__first, __last) 03398 * such that no other element in the range is larger. 03399 */ 03400 template<typename _ForwardIterator> 03401 _GLIBCXX14_CONSTEXPR 03402 inline pair<_ForwardIterator, _ForwardIterator> 03403 minmax_element(_ForwardIterator __first, _ForwardIterator __last) 03404 { 03405 // concept requirements 03406 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 03407 __glibcxx_function_requires(_LessThanComparableConcept< 03408 typename iterator_traits<_ForwardIterator>::value_type>) 03409 __glibcxx_requires_valid_range(__first, __last); 03410 __glibcxx_requires_irreflexive(__first, __last); 03411 03412 return std::__minmax_element(__first, __last, 03413 __gnu_cxx::__ops::__iter_less_iter()); 03414 } 03415 03416 /** 03417 * @brief Return a pair of iterators pointing to the minimum and maximum 03418 * elements in a range. 03419 * @ingroup sorting_algorithms 03420 * @param __first Start of range. 03421 * @param __last End of range. 03422 * @param __comp Comparison functor. 03423 * @return make_pair(m, M), where m is the first iterator i in 03424 * [__first, __last) such that no other element in the range is 03425 * smaller, and where M is the last iterator i in [__first, __last) 03426 * such that no other element in the range is larger. 03427 */ 03428 template<typename _ForwardIterator, typename _Compare> 03429 _GLIBCXX14_CONSTEXPR 03430 inline pair<_ForwardIterator, _ForwardIterator> 03431 minmax_element(_ForwardIterator __first, _ForwardIterator __last, 03432 _Compare __comp) 03433 { 03434 // concept requirements 03435 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 03436 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 03437 typename iterator_traits<_ForwardIterator>::value_type, 03438 typename iterator_traits<_ForwardIterator>::value_type>) 03439 __glibcxx_requires_valid_range(__first, __last); 03440 __glibcxx_requires_irreflexive_pred(__first, __last, __comp); 03441 03442 return std::__minmax_element(__first, __last, 03443 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 03444 } 03445 03446 // N2722 + DR 915. 03447 template<typename _Tp> 03448 _GLIBCXX14_CONSTEXPR 03449 inline _Tp 03450 min(initializer_list<_Tp> __l) 03451 { return *std::min_element(__l.begin(), __l.end()); } 03452 03453 template<typename _Tp, typename _Compare> 03454 _GLIBCXX14_CONSTEXPR 03455 inline _Tp 03456 min(initializer_list<_Tp> __l, _Compare __comp) 03457 { return *std::min_element(__l.begin(), __l.end(), __comp); } 03458 03459 template<typename _Tp> 03460 _GLIBCXX14_CONSTEXPR 03461 inline _Tp 03462 max(initializer_list<_Tp> __l) 03463 { return *std::max_element(__l.begin(), __l.end()); } 03464 03465 template<typename _Tp, typename _Compare> 03466 _GLIBCXX14_CONSTEXPR 03467 inline _Tp 03468 max(initializer_list<_Tp> __l, _Compare __comp) 03469 { return *std::max_element(__l.begin(), __l.end(), __comp); } 03470 03471 template<typename _Tp> 03472 _GLIBCXX14_CONSTEXPR 03473 inline pair<_Tp, _Tp> 03474 minmax(initializer_list<_Tp> __l) 03475 { 03476 pair<const _Tp*, const _Tp*> __p = 03477 std::minmax_element(__l.begin(), __l.end()); 03478 return std::make_pair(*__p.first, *__p.second); 03479 } 03480 03481 template<typename _Tp, typename _Compare> 03482 _GLIBCXX14_CONSTEXPR 03483 inline pair<_Tp, _Tp> 03484 minmax(initializer_list<_Tp> __l, _Compare __comp) 03485 { 03486 pair<const _Tp*, const _Tp*> __p = 03487 std::minmax_element(__l.begin(), __l.end(), __comp); 03488 return std::make_pair(*__p.first, *__p.second); 03489 } 03490 03491 template<typename _ForwardIterator1, typename _ForwardIterator2, 03492 typename _BinaryPredicate> 03493 bool 03494 __is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 03495 _ForwardIterator2 __first2, _BinaryPredicate __pred) 03496 { 03497 // Efficiently compare identical prefixes: O(N) if sequences 03498 // have the same elements in the same order. 03499 for (; __first1 != __last1; ++__first1, (void)++__first2) 03500 if (!__pred(__first1, __first2)) 03501 break; 03502 03503 if (__first1 == __last1) 03504 return true; 03505 03506 // Establish __last2 assuming equal ranges by iterating over the 03507 // rest of the list. 03508 _ForwardIterator2 __last2 = __first2; 03509 std::advance(__last2, std::distance(__first1, __last1)); 03510 for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan) 03511 { 03512 if (__scan != std::__find_if(__first1, __scan, 03513 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan))) 03514 continue; // We've seen this one before. 03515 03516 auto __matches 03517 = std::__count_if(__first2, __last2, 03518 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)); 03519 if (0 == __matches || 03520 std::__count_if(__scan, __last1, 03521 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)) 03522 != __matches) 03523 return false; 03524 } 03525 return true; 03526 } 03527 03528 /** 03529 * @brief Checks whether a permutation of the second sequence is equal 03530 * to the first sequence. 03531 * @ingroup non_mutating_algorithms 03532 * @param __first1 Start of first range. 03533 * @param __last1 End of first range. 03534 * @param __first2 Start of second range. 03535 * @return true if there exists a permutation of the elements in the range 03536 * [__first2, __first2 + (__last1 - __first1)), beginning with 03537 * ForwardIterator2 begin, such that equal(__first1, __last1, begin) 03538 * returns true; otherwise, returns false. 03539 */ 03540 template<typename _ForwardIterator1, typename _ForwardIterator2> 03541 inline bool 03542 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 03543 _ForwardIterator2 __first2) 03544 { 03545 // concept requirements 03546 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>) 03547 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>) 03548 __glibcxx_function_requires(_EqualOpConcept< 03549 typename iterator_traits<_ForwardIterator1>::value_type, 03550 typename iterator_traits<_ForwardIterator2>::value_type>) 03551 __glibcxx_requires_valid_range(__first1, __last1); 03552 03553 return std::__is_permutation(__first1, __last1, __first2, 03554 __gnu_cxx::__ops::__iter_equal_to_iter()); 03555 } 03556 03557 /** 03558 * @brief Checks whether a permutation of the second sequence is equal 03559 * to the first sequence. 03560 * @ingroup non_mutating_algorithms 03561 * @param __first1 Start of first range. 03562 * @param __last1 End of first range. 03563 * @param __first2 Start of second range. 03564 * @param __pred A binary predicate. 03565 * @return true if there exists a permutation of the elements in 03566 * the range [__first2, __first2 + (__last1 - __first1)), 03567 * beginning with ForwardIterator2 begin, such that 03568 * equal(__first1, __last1, __begin, __pred) returns true; 03569 * otherwise, returns false. 03570 */ 03571 template<typename _ForwardIterator1, typename _ForwardIterator2, 03572 typename _BinaryPredicate> 03573 inline bool 03574 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 03575 _ForwardIterator2 __first2, _BinaryPredicate __pred) 03576 { 03577 // concept requirements 03578 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>) 03579 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>) 03580 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 03581 typename iterator_traits<_ForwardIterator1>::value_type, 03582 typename iterator_traits<_ForwardIterator2>::value_type>) 03583 __glibcxx_requires_valid_range(__first1, __last1); 03584 03585 return std::__is_permutation(__first1, __last1, __first2, 03586 __gnu_cxx::__ops::__iter_comp_iter(__pred)); 03587 } 03588 03589 #if __cplusplus > 201103L 03590 template<typename _ForwardIterator1, typename _ForwardIterator2, 03591 typename _BinaryPredicate> 03592 bool 03593 __is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 03594 _ForwardIterator2 __first2, _ForwardIterator2 __last2, 03595 _BinaryPredicate __pred) 03596 { 03597 using _Cat1 03598 = typename iterator_traits<_ForwardIterator1>::iterator_category; 03599 using _Cat2 03600 = typename iterator_traits<_ForwardIterator2>::iterator_category; 03601 using _It1_is_RA = is_same<_Cat1, random_access_iterator_tag>; 03602 using _It2_is_RA = is_same<_Cat2, random_access_iterator_tag>; 03603 constexpr bool __ra_iters = _It1_is_RA() && _It2_is_RA(); 03604 if (__ra_iters) 03605 { 03606 auto __d1 = std::distance(__first1, __last1); 03607 auto __d2 = std::distance(__first2, __last2); 03608 if (__d1 != __d2) 03609 return false; 03610 } 03611 03612 // Efficiently compare identical prefixes: O(N) if sequences 03613 // have the same elements in the same order. 03614 for (; __first1 != __last1 && __first2 != __last2; 03615 ++__first1, (void)++__first2) 03616 if (!__pred(__first1, __first2)) 03617 break; 03618 03619 if (__ra_iters) 03620 { 03621 if (__first1 == __last1) 03622 return true; 03623 } 03624 else 03625 { 03626 auto __d1 = std::distance(__first1, __last1); 03627 auto __d2 = std::distance(__first2, __last2); 03628 if (__d1 == 0 && __d2 == 0) 03629 return true; 03630 if (__d1 != __d2) 03631 return false; 03632 } 03633 03634 for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan) 03635 { 03636 if (__scan != std::__find_if(__first1, __scan, 03637 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan))) 03638 continue; // We've seen this one before. 03639 03640 auto __matches = std::__count_if(__first2, __last2, 03641 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)); 03642 if (0 == __matches 03643 || std::__count_if(__scan, __last1, 03644 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)) 03645 != __matches) 03646 return false; 03647 } 03648 return true; 03649 } 03650 03651 /** 03652 * @brief Checks whether a permutaion of the second sequence is equal 03653 * to the first sequence. 03654 * @ingroup non_mutating_algorithms 03655 * @param __first1 Start of first range. 03656 * @param __last1 End of first range. 03657 * @param __first2 Start of second range. 03658 * @param __last2 End of first range. 03659 * @return true if there exists a permutation of the elements in the range 03660 * [__first2, __last2), beginning with ForwardIterator2 begin, 03661 * such that equal(__first1, __last1, begin) returns true; 03662 * otherwise, returns false. 03663 */ 03664 template<typename _ForwardIterator1, typename _ForwardIterator2> 03665 inline bool 03666 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 03667 _ForwardIterator2 __first2, _ForwardIterator2 __last2) 03668 { 03669 __glibcxx_requires_valid_range(__first1, __last1); 03670 __glibcxx_requires_valid_range(__first2, __last2); 03671 03672 return 03673 std::__is_permutation(__first1, __last1, __first2, __last2, 03674 __gnu_cxx::__ops::__iter_equal_to_iter()); 03675 } 03676 03677 /** 03678 * @brief Checks whether a permutation of the second sequence is equal 03679 * to the first sequence. 03680 * @ingroup non_mutating_algorithms 03681 * @param __first1 Start of first range. 03682 * @param __last1 End of first range. 03683 * @param __first2 Start of second range. 03684 * @param __last2 End of first range. 03685 * @param __pred A binary predicate. 03686 * @return true if there exists a permutation of the elements in the range 03687 * [__first2, __last2), beginning with ForwardIterator2 begin, 03688 * such that equal(__first1, __last1, __begin, __pred) returns true; 03689 * otherwise, returns false. 03690 */ 03691 template<typename _ForwardIterator1, typename _ForwardIterator2, 03692 typename _BinaryPredicate> 03693 inline bool 03694 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 03695 _ForwardIterator2 __first2, _ForwardIterator2 __last2, 03696 _BinaryPredicate __pred) 03697 { 03698 __glibcxx_requires_valid_range(__first1, __last1); 03699 __glibcxx_requires_valid_range(__first2, __last2); 03700 03701 return std::__is_permutation(__first1, __last1, __first2, __last2, 03702 __gnu_cxx::__ops::__iter_comp_iter(__pred)); 03703 } 03704 03705 #if __cplusplus > 201402L 03706 03707 #define __cpp_lib_clamp 201603 03708 03709 /** 03710 * @brief Returns the value clamped between lo and hi. 03711 * @ingroup sorting_algorithms 03712 * @param __val A value of arbitrary type. 03713 * @param __lo A lower limit of arbitrary type. 03714 * @param __hi An upper limit of arbitrary type. 03715 * @return max(__val, __lo) if __val < __hi or min(__val, __hi) otherwise. 03716 */ 03717 template<typename _Tp> 03718 constexpr const _Tp& 03719 clamp(const _Tp& __val, const _Tp& __lo, const _Tp& __hi) 03720 { 03721 __glibcxx_assert(!(__hi < __lo)); 03722 return (__val < __lo) ? __lo : (__hi < __val) ? __hi : __val; 03723 } 03724 03725 /** 03726 * @brief Returns the value clamped between lo and hi. 03727 * @ingroup sorting_algorithms 03728 * @param __val A value of arbitrary type. 03729 * @param __lo A lower limit of arbitrary type. 03730 * @param __hi An upper limit of arbitrary type. 03731 * @param __comp A comparison functor. 03732 * @return max(__val, __lo, __comp) if __comp(__val, __hi) 03733 * or min(__val, __hi, __comp) otherwise. 03734 */ 03735 template<typename _Tp, typename _Compare> 03736 constexpr const _Tp& 03737 clamp(const _Tp& __val, const _Tp& __lo, const _Tp& __hi, _Compare __comp) 03738 { 03739 __glibcxx_assert(!__comp(__hi, __lo)); 03740 return __comp(__val, __lo) ? __lo : __comp(__hi, __val) ? __hi : __val; 03741 } 03742 #endif // C++17 03743 #endif // C++14 03744 03745 #ifdef _GLIBCXX_USE_C99_STDINT_TR1 03746 /** 03747 * @brief Generate two uniformly distributed integers using a 03748 * single distribution invocation. 03749 * @param __b0 The upper bound for the first integer. 03750 * @param __b1 The upper bound for the second integer. 03751 * @param __g A UniformRandomBitGenerator. 03752 * @return A pair (i, j) with i and j uniformly distributed 03753 * over [0, __b0) and [0, __b1), respectively. 03754 * 03755 * Requires: __b0 * __b1 <= __g.max() - __g.min(). 03756 * 03757 * Using uniform_int_distribution with a range that is very 03758 * small relative to the range of the generator ends up wasting 03759 * potentially expensively generated randomness, since 03760 * uniform_int_distribution does not store leftover randomness 03761 * between invocations. 03762 * 03763 * If we know we want two integers in ranges that are sufficiently 03764 * small, we can compose the ranges, use a single distribution 03765 * invocation, and significantly reduce the waste. 03766 */ 03767 template<typename _IntType, typename _UniformRandomBitGenerator> 03768 pair<_IntType, _IntType> 03769 __gen_two_uniform_ints(_IntType __b0, _IntType __b1, 03770 _UniformRandomBitGenerator&& __g) 03771 { 03772 _IntType __x 03773 = uniform_int_distribution<_IntType>{0, (__b0 * __b1) - 1}(__g); 03774 return std::make_pair(__x / __b1, __x % __b1); 03775 } 03776 03777 /** 03778 * @brief Shuffle the elements of a sequence using a uniform random 03779 * number generator. 03780 * @ingroup mutating_algorithms 03781 * @param __first A forward iterator. 03782 * @param __last A forward iterator. 03783 * @param __g A UniformRandomNumberGenerator (26.5.1.3). 03784 * @return Nothing. 03785 * 03786 * Reorders the elements in the range @p [__first,__last) using @p __g to 03787 * provide random numbers. 03788 */ 03789 template<typename _RandomAccessIterator, 03790 typename _UniformRandomNumberGenerator> 03791 void 03792 shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last, 03793 _UniformRandomNumberGenerator&& __g) 03794 { 03795 // concept requirements 03796 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 03797 _RandomAccessIterator>) 03798 __glibcxx_requires_valid_range(__first, __last); 03799 03800 if (__first == __last) 03801 return; 03802 03803 typedef typename iterator_traits<_RandomAccessIterator>::difference_type 03804 _DistanceType; 03805 03806 typedef typename std::make_unsigned<_DistanceType>::type __ud_type; 03807 typedef typename std::uniform_int_distribution<__ud_type> __distr_type; 03808 typedef typename __distr_type::param_type __p_type; 03809 03810 typedef typename remove_reference<_UniformRandomNumberGenerator>::type 03811 _Gen; 03812 typedef typename common_type<typename _Gen::result_type, __ud_type>::type 03813 __uc_type; 03814 03815 const __uc_type __urngrange = __g.max() - __g.min(); 03816 const __uc_type __urange = __uc_type(__last - __first); 03817 03818 if (__urngrange / __urange >= __urange) 03819 // I.e. (__urngrange >= __urange * __urange) but without wrap issues. 03820 { 03821 _RandomAccessIterator __i = __first + 1; 03822 03823 // Since we know the range isn't empty, an even number of elements 03824 // means an uneven number of elements /to swap/, in which case we 03825 // do the first one up front: 03826 03827 if ((__urange % 2) == 0) 03828 { 03829 __distr_type __d{0, 1}; 03830 std::iter_swap(__i++, __first + __d(__g)); 03831 } 03832 03833 // Now we know that __last - __i is even, so we do the rest in pairs, 03834 // using a single distribution invocation to produce swap positions 03835 // for two successive elements at a time: 03836 03837 while (__i != __last) 03838 { 03839 const __uc_type __swap_range = __uc_type(__i - __first) + 1; 03840 03841 const pair<__uc_type, __uc_type> __pospos = 03842 __gen_two_uniform_ints(__swap_range, __swap_range + 1, __g); 03843 03844 std::iter_swap(__i++, __first + __pospos.first); 03845 std::iter_swap(__i++, __first + __pospos.second); 03846 } 03847 03848 return; 03849 } 03850 03851 __distr_type __d; 03852 03853 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i) 03854 std::iter_swap(__i, __first + __d(__g, __p_type(0, __i - __first))); 03855 } 03856 #endif 03857 03858 #endif // C++11 03859 03860 _GLIBCXX_END_NAMESPACE_VERSION 03861 03862 _GLIBCXX_BEGIN_NAMESPACE_ALGO 03863 03864 /** 03865 * @brief Apply a function to every element of a sequence. 03866 * @ingroup non_mutating_algorithms 03867 * @param __first An input iterator. 03868 * @param __last An input iterator. 03869 * @param __f A unary function object. 03870 * @return @p __f 03871 * 03872 * Applies the function object @p __f to each element in the range 03873 * @p [first,last). @p __f must not modify the order of the sequence. 03874 * If @p __f has a return value it is ignored. 03875 */ 03876 template<typename _InputIterator, typename _Function> 03877 _Function 03878 for_each(_InputIterator __first, _InputIterator __last, _Function __f) 03879 { 03880 // concept requirements 03881 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 03882 __glibcxx_requires_valid_range(__first, __last); 03883 for (; __first != __last; ++__first) 03884 __f(*__first); 03885 return __f; // N.B. [alg.foreach] says std::move(f) but it's redundant. 03886 } 03887 03888 /** 03889 * @brief Find the first occurrence of a value in a sequence. 03890 * @ingroup non_mutating_algorithms 03891 * @param __first An input iterator. 03892 * @param __last An input iterator. 03893 * @param __val The value to find. 03894 * @return The first iterator @c i in the range @p [__first,__last) 03895 * such that @c *i == @p __val, or @p __last if no such iterator exists. 03896 */ 03897 template<typename _InputIterator, typename _Tp> 03898 inline _InputIterator 03899 find(_InputIterator __first, _InputIterator __last, 03900 const _Tp& __val) 03901 { 03902 // concept requirements 03903 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 03904 __glibcxx_function_requires(_EqualOpConcept< 03905 typename iterator_traits<_InputIterator>::value_type, _Tp>) 03906 __glibcxx_requires_valid_range(__first, __last); 03907 return std::__find_if(__first, __last, 03908 __gnu_cxx::__ops::__iter_equals_val(__val)); 03909 } 03910 03911 /** 03912 * @brief Find the first element in a sequence for which a 03913 * predicate is true. 03914 * @ingroup non_mutating_algorithms 03915 * @param __first An input iterator. 03916 * @param __last An input iterator. 03917 * @param __pred A predicate. 03918 * @return The first iterator @c i in the range @p [__first,__last) 03919 * such that @p __pred(*i) is true, or @p __last if no such iterator exists. 03920 */ 03921 template<typename _InputIterator, typename _Predicate> 03922 inline _InputIterator 03923 find_if(_InputIterator __first, _InputIterator __last, 03924 _Predicate __pred) 03925 { 03926 // concept requirements 03927 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 03928 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 03929 typename iterator_traits<_InputIterator>::value_type>) 03930 __glibcxx_requires_valid_range(__first, __last); 03931 03932 return std::__find_if(__first, __last, 03933 __gnu_cxx::__ops::__pred_iter(__pred)); 03934 } 03935 03936 /** 03937 * @brief Find element from a set in a sequence. 03938 * @ingroup non_mutating_algorithms 03939 * @param __first1 Start of range to search. 03940 * @param __last1 End of range to search. 03941 * @param __first2 Start of match candidates. 03942 * @param __last2 End of match candidates. 03943 * @return The first iterator @c i in the range 03944 * @p [__first1,__last1) such that @c *i == @p *(i2) such that i2 is an 03945 * iterator in [__first2,__last2), or @p __last1 if no such iterator exists. 03946 * 03947 * Searches the range @p [__first1,__last1) for an element that is 03948 * equal to some element in the range [__first2,__last2). If 03949 * found, returns an iterator in the range [__first1,__last1), 03950 * otherwise returns @p __last1. 03951 */ 03952 template<typename _InputIterator, typename _ForwardIterator> 03953 _InputIterator 03954 find_first_of(_InputIterator __first1, _InputIterator __last1, 03955 _ForwardIterator __first2, _ForwardIterator __last2) 03956 { 03957 // concept requirements 03958 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 03959 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 03960 __glibcxx_function_requires(_EqualOpConcept< 03961 typename iterator_traits<_InputIterator>::value_type, 03962 typename iterator_traits<_ForwardIterator>::value_type>) 03963 __glibcxx_requires_valid_range(__first1, __last1); 03964 __glibcxx_requires_valid_range(__first2, __last2); 03965 03966 for (; __first1 != __last1; ++__first1) 03967 for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter) 03968 if (*__first1 == *__iter) 03969 return __first1; 03970 return __last1; 03971 } 03972 03973 /** 03974 * @brief Find element from a set in a sequence using a predicate. 03975 * @ingroup non_mutating_algorithms 03976 * @param __first1 Start of range to search. 03977 * @param __last1 End of range to search. 03978 * @param __first2 Start of match candidates. 03979 * @param __last2 End of match candidates. 03980 * @param __comp Predicate to use. 03981 * @return The first iterator @c i in the range 03982 * @p [__first1,__last1) such that @c comp(*i, @p *(i2)) is true 03983 * and i2 is an iterator in [__first2,__last2), or @p __last1 if no 03984 * such iterator exists. 03985 * 03986 03987 * Searches the range @p [__first1,__last1) for an element that is 03988 * equal to some element in the range [__first2,__last2). If 03989 * found, returns an iterator in the range [__first1,__last1), 03990 * otherwise returns @p __last1. 03991 */ 03992 template<typename _InputIterator, typename _ForwardIterator, 03993 typename _BinaryPredicate> 03994 _InputIterator 03995 find_first_of(_InputIterator __first1, _InputIterator __last1, 03996 _ForwardIterator __first2, _ForwardIterator __last2, 03997 _BinaryPredicate __comp) 03998 { 03999 // concept requirements 04000 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 04001 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 04002 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 04003 typename iterator_traits<_InputIterator>::value_type, 04004 typename iterator_traits<_ForwardIterator>::value_type>) 04005 __glibcxx_requires_valid_range(__first1, __last1); 04006 __glibcxx_requires_valid_range(__first2, __last2); 04007 04008 for (; __first1 != __last1; ++__first1) 04009 for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter) 04010 if (__comp(*__first1, *__iter)) 04011 return __first1; 04012 return __last1; 04013 } 04014 04015 /** 04016 * @brief Find two adjacent values in a sequence that are equal. 04017 * @ingroup non_mutating_algorithms 04018 * @param __first A forward iterator. 04019 * @param __last A forward iterator. 04020 * @return The first iterator @c i such that @c i and @c i+1 are both 04021 * valid iterators in @p [__first,__last) and such that @c *i == @c *(i+1), 04022 * or @p __last if no such iterator exists. 04023 */ 04024 template<typename _ForwardIterator> 04025 inline _ForwardIterator 04026 adjacent_find(_ForwardIterator __first, _ForwardIterator __last) 04027 { 04028 // concept requirements 04029 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 04030 __glibcxx_function_requires(_EqualityComparableConcept< 04031 typename iterator_traits<_ForwardIterator>::value_type>) 04032 __glibcxx_requires_valid_range(__first, __last); 04033 04034 return std::__adjacent_find(__first, __last, 04035 __gnu_cxx::__ops::__iter_equal_to_iter()); 04036 } 04037 04038 /** 04039 * @brief Find two adjacent values in a sequence using a predicate. 04040 * @ingroup non_mutating_algorithms 04041 * @param __first A forward iterator. 04042 * @param __last A forward iterator. 04043 * @param __binary_pred A binary predicate. 04044 * @return The first iterator @c i such that @c i and @c i+1 are both 04045 * valid iterators in @p [__first,__last) and such that 04046 * @p __binary_pred(*i,*(i+1)) is true, or @p __last if no such iterator 04047 * exists. 04048 */ 04049 template<typename _ForwardIterator, typename _BinaryPredicate> 04050 inline _ForwardIterator 04051 adjacent_find(_ForwardIterator __first, _ForwardIterator __last, 04052 _BinaryPredicate __binary_pred) 04053 { 04054 // concept requirements 04055 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 04056 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 04057 typename iterator_traits<_ForwardIterator>::value_type, 04058 typename iterator_traits<_ForwardIterator>::value_type>) 04059 __glibcxx_requires_valid_range(__first, __last); 04060 04061 return std::__adjacent_find(__first, __last, 04062 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred)); 04063 } 04064 04065 /** 04066 * @brief Count the number of copies of a value in a sequence. 04067 * @ingroup non_mutating_algorithms 04068 * @param __first An input iterator. 04069 * @param __last An input iterator. 04070 * @param __value The value to be counted. 04071 * @return The number of iterators @c i in the range @p [__first,__last) 04072 * for which @c *i == @p __value 04073 */ 04074 template<typename _InputIterator, typename _Tp> 04075 inline typename iterator_traits<_InputIterator>::difference_type 04076 count(_InputIterator __first, _InputIterator __last, const _Tp& __value) 04077 { 04078 // concept requirements 04079 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 04080 __glibcxx_function_requires(_EqualOpConcept< 04081 typename iterator_traits<_InputIterator>::value_type, _Tp>) 04082 __glibcxx_requires_valid_range(__first, __last); 04083 04084 return std::__count_if(__first, __last, 04085 __gnu_cxx::__ops::__iter_equals_val(__value)); 04086 } 04087 04088 /** 04089 * @brief Count the elements of a sequence for which a predicate is true. 04090 * @ingroup non_mutating_algorithms 04091 * @param __first An input iterator. 04092 * @param __last An input iterator. 04093 * @param __pred A predicate. 04094 * @return The number of iterators @c i in the range @p [__first,__last) 04095 * for which @p __pred(*i) is true. 04096 */ 04097 template<typename _InputIterator, typename _Predicate> 04098 inline typename iterator_traits<_InputIterator>::difference_type 04099 count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred) 04100 { 04101 // concept requirements 04102 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 04103 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 04104 typename iterator_traits<_InputIterator>::value_type>) 04105 __glibcxx_requires_valid_range(__first, __last); 04106 04107 return std::__count_if(__first, __last, 04108 __gnu_cxx::__ops::__pred_iter(__pred)); 04109 } 04110 04111 /** 04112 * @brief Search a sequence for a matching sub-sequence. 04113 * @ingroup non_mutating_algorithms 04114 * @param __first1 A forward iterator. 04115 * @param __last1 A forward iterator. 04116 * @param __first2 A forward iterator. 04117 * @param __last2 A forward iterator. 04118 * @return The first iterator @c i in the range @p 04119 * [__first1,__last1-(__last2-__first2)) such that @c *(i+N) == @p 04120 * *(__first2+N) for each @c N in the range @p 04121 * [0,__last2-__first2), or @p __last1 if no such iterator exists. 04122 * 04123 * Searches the range @p [__first1,__last1) for a sub-sequence that 04124 * compares equal value-by-value with the sequence given by @p 04125 * [__first2,__last2) and returns an iterator to the first element 04126 * of the sub-sequence, or @p __last1 if the sub-sequence is not 04127 * found. 04128 * 04129 * Because the sub-sequence must lie completely within the range @p 04130 * [__first1,__last1) it must start at a position less than @p 04131 * __last1-(__last2-__first2) where @p __last2-__first2 is the 04132 * length of the sub-sequence. 04133 * 04134 * This means that the returned iterator @c i will be in the range 04135 * @p [__first1,__last1-(__last2-__first2)) 04136 */ 04137 template<typename _ForwardIterator1, typename _ForwardIterator2> 04138 inline _ForwardIterator1 04139 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 04140 _ForwardIterator2 __first2, _ForwardIterator2 __last2) 04141 { 04142 // concept requirements 04143 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>) 04144 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>) 04145 __glibcxx_function_requires(_EqualOpConcept< 04146 typename iterator_traits<_ForwardIterator1>::value_type, 04147 typename iterator_traits<_ForwardIterator2>::value_type>) 04148 __glibcxx_requires_valid_range(__first1, __last1); 04149 __glibcxx_requires_valid_range(__first2, __last2); 04150 04151 return std::__search(__first1, __last1, __first2, __last2, 04152 __gnu_cxx::__ops::__iter_equal_to_iter()); 04153 } 04154 04155 /** 04156 * @brief Search a sequence for a matching sub-sequence using a predicate. 04157 * @ingroup non_mutating_algorithms 04158 * @param __first1 A forward iterator. 04159 * @param __last1 A forward iterator. 04160 * @param __first2 A forward iterator. 04161 * @param __last2 A forward iterator. 04162 * @param __predicate A binary predicate. 04163 * @return The first iterator @c i in the range 04164 * @p [__first1,__last1-(__last2-__first2)) such that 04165 * @p __predicate(*(i+N),*(__first2+N)) is true for each @c N in the range 04166 * @p [0,__last2-__first2), or @p __last1 if no such iterator exists. 04167 * 04168 * Searches the range @p [__first1,__last1) for a sub-sequence that 04169 * compares equal value-by-value with the sequence given by @p 04170 * [__first2,__last2), using @p __predicate to determine equality, 04171 * and returns an iterator to the first element of the 04172 * sub-sequence, or @p __last1 if no such iterator exists. 04173 * 04174 * @see search(_ForwardIter1, _ForwardIter1, _ForwardIter2, _ForwardIter2) 04175 */ 04176 template<typename _ForwardIterator1, typename _ForwardIterator2, 04177 typename _BinaryPredicate> 04178 inline _ForwardIterator1 04179 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, 04180 _ForwardIterator2 __first2, _ForwardIterator2 __last2, 04181 _BinaryPredicate __predicate) 04182 { 04183 // concept requirements 04184 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>) 04185 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>) 04186 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 04187 typename iterator_traits<_ForwardIterator1>::value_type, 04188 typename iterator_traits<_ForwardIterator2>::value_type>) 04189 __glibcxx_requires_valid_range(__first1, __last1); 04190 __glibcxx_requires_valid_range(__first2, __last2); 04191 04192 return std::__search(__first1, __last1, __first2, __last2, 04193 __gnu_cxx::__ops::__iter_comp_iter(__predicate)); 04194 } 04195 04196 /** 04197 * @brief Search a sequence for a number of consecutive values. 04198 * @ingroup non_mutating_algorithms 04199 * @param __first A forward iterator. 04200 * @param __last A forward iterator. 04201 * @param __count The number of consecutive values. 04202 * @param __val The value to find. 04203 * @return The first iterator @c i in the range @p 04204 * [__first,__last-__count) such that @c *(i+N) == @p __val for 04205 * each @c N in the range @p [0,__count), or @p __last if no such 04206 * iterator exists. 04207 * 04208 * Searches the range @p [__first,__last) for @p count consecutive elements 04209 * equal to @p __val. 04210 */ 04211 template<typename _ForwardIterator, typename _Integer, typename _Tp> 04212 inline _ForwardIterator 04213 search_n(_ForwardIterator __first, _ForwardIterator __last, 04214 _Integer __count, const _Tp& __val) 04215 { 04216 // concept requirements 04217 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 04218 __glibcxx_function_requires(_EqualOpConcept< 04219 typename iterator_traits<_ForwardIterator>::value_type, _Tp>) 04220 __glibcxx_requires_valid_range(__first, __last); 04221 04222 return std::__search_n(__first, __last, __count, 04223 __gnu_cxx::__ops::__iter_equals_val(__val)); 04224 } 04225 04226 04227 /** 04228 * @brief Search a sequence for a number of consecutive values using a 04229 * predicate. 04230 * @ingroup non_mutating_algorithms 04231 * @param __first A forward iterator. 04232 * @param __last A forward iterator. 04233 * @param __count The number of consecutive values. 04234 * @param __val The value to find. 04235 * @param __binary_pred A binary predicate. 04236 * @return The first iterator @c i in the range @p 04237 * [__first,__last-__count) such that @p 04238 * __binary_pred(*(i+N),__val) is true for each @c N in the range 04239 * @p [0,__count), or @p __last if no such iterator exists. 04240 * 04241 * Searches the range @p [__first,__last) for @p __count 04242 * consecutive elements for which the predicate returns true. 04243 */ 04244 template<typename _ForwardIterator, typename _Integer, typename _Tp, 04245 typename _BinaryPredicate> 04246 inline _ForwardIterator 04247 search_n(_ForwardIterator __first, _ForwardIterator __last, 04248 _Integer __count, const _Tp& __val, 04249 _BinaryPredicate __binary_pred) 04250 { 04251 // concept requirements 04252 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 04253 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, 04254 typename iterator_traits<_ForwardIterator>::value_type, _Tp>) 04255 __glibcxx_requires_valid_range(__first, __last); 04256 04257 return std::__search_n(__first, __last, __count, 04258 __gnu_cxx::__ops::__iter_comp_val(__binary_pred, __val)); 04259 } 04260 04261 #if __cplusplus > 201402L 04262 /** @brief Search a sequence using a Searcher object. 04263 * 04264 * @param __first A forward iterator. 04265 * @param __last A forward iterator. 04266 * @param __searcher A callable object. 04267 * @return @p __searcher(__first,__last).first 04268 */ 04269 template<typename _ForwardIterator, typename _Searcher> 04270 inline _ForwardIterator 04271 search(_ForwardIterator __first, _ForwardIterator __last, 04272 const _Searcher& __searcher) 04273 { return __searcher(__first, __last).first; } 04274 #endif 04275 04276 /** 04277 * @brief Perform an operation on a sequence. 04278 * @ingroup mutating_algorithms 04279 * @param __first An input iterator. 04280 * @param __last An input iterator. 04281 * @param __result An output iterator. 04282 * @param __unary_op A unary operator. 04283 * @return An output iterator equal to @p __result+(__last-__first). 04284 * 04285 * Applies the operator to each element in the input range and assigns 04286 * the results to successive elements of the output sequence. 04287 * Evaluates @p *(__result+N)=unary_op(*(__first+N)) for each @c N in the 04288 * range @p [0,__last-__first). 04289 * 04290 * @p unary_op must not alter its argument. 04291 */ 04292 template<typename _InputIterator, typename _OutputIterator, 04293 typename _UnaryOperation> 04294 _OutputIterator 04295 transform(_InputIterator __first, _InputIterator __last, 04296 _OutputIterator __result, _UnaryOperation __unary_op) 04297 { 04298 // concept requirements 04299 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 04300 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 04301 // "the type returned by a _UnaryOperation" 04302 __typeof__(__unary_op(*__first))>) 04303 __glibcxx_requires_valid_range(__first, __last); 04304 04305 for (; __first != __last; ++__first, (void)++__result) 04306 *__result = __unary_op(*__first); 04307 return __result; 04308 } 04309 04310 /** 04311 * @brief Perform an operation on corresponding elements of two sequences. 04312 * @ingroup mutating_algorithms 04313 * @param __first1 An input iterator. 04314 * @param __last1 An input iterator. 04315 * @param __first2 An input iterator. 04316 * @param __result An output iterator. 04317 * @param __binary_op A binary operator. 04318 * @return An output iterator equal to @p result+(last-first). 04319 * 04320 * Applies the operator to the corresponding elements in the two 04321 * input ranges and assigns the results to successive elements of the 04322 * output sequence. 04323 * Evaluates @p 04324 * *(__result+N)=__binary_op(*(__first1+N),*(__first2+N)) for each 04325 * @c N in the range @p [0,__last1-__first1). 04326 * 04327 * @p binary_op must not alter either of its arguments. 04328 */ 04329 template<typename _InputIterator1, typename _InputIterator2, 04330 typename _OutputIterator, typename _BinaryOperation> 04331 _OutputIterator 04332 transform(_InputIterator1 __first1, _InputIterator1 __last1, 04333 _InputIterator2 __first2, _OutputIterator __result, 04334 _BinaryOperation __binary_op) 04335 { 04336 // concept requirements 04337 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 04338 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 04339 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 04340 // "the type returned by a _BinaryOperation" 04341 __typeof__(__binary_op(*__first1,*__first2))>) 04342 __glibcxx_requires_valid_range(__first1, __last1); 04343 04344 for (; __first1 != __last1; ++__first1, (void)++__first2, ++__result) 04345 *__result = __binary_op(*__first1, *__first2); 04346 return __result; 04347 } 04348 04349 /** 04350 * @brief Replace each occurrence of one value in a sequence with another 04351 * value. 04352 * @ingroup mutating_algorithms 04353 * @param __first A forward iterator. 04354 * @param __last A forward iterator. 04355 * @param __old_value The value to be replaced. 04356 * @param __new_value The replacement value. 04357 * @return replace() returns no value. 04358 * 04359 * For each iterator @c i in the range @p [__first,__last) if @c *i == 04360 * @p __old_value then the assignment @c *i = @p __new_value is performed. 04361 */ 04362 template<typename _ForwardIterator, typename _Tp> 04363 void 04364 replace(_ForwardIterator __first, _ForwardIterator __last, 04365 const _Tp& __old_value, const _Tp& __new_value) 04366 { 04367 // concept requirements 04368 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 04369 _ForwardIterator>) 04370 __glibcxx_function_requires(_EqualOpConcept< 04371 typename iterator_traits<_ForwardIterator>::value_type, _Tp>) 04372 __glibcxx_function_requires(_ConvertibleConcept<_Tp, 04373 typename iterator_traits<_ForwardIterator>::value_type>) 04374 __glibcxx_requires_valid_range(__first, __last); 04375 04376 for (; __first != __last; ++__first) 04377 if (*__first == __old_value) 04378 *__first = __new_value; 04379 } 04380 04381 /** 04382 * @brief Replace each value in a sequence for which a predicate returns 04383 * true with another value. 04384 * @ingroup mutating_algorithms 04385 * @param __first A forward iterator. 04386 * @param __last A forward iterator. 04387 * @param __pred A predicate. 04388 * @param __new_value The replacement value. 04389 * @return replace_if() returns no value. 04390 * 04391 * For each iterator @c i in the range @p [__first,__last) if @p __pred(*i) 04392 * is true then the assignment @c *i = @p __new_value is performed. 04393 */ 04394 template<typename _ForwardIterator, typename _Predicate, typename _Tp> 04395 void 04396 replace_if(_ForwardIterator __first, _ForwardIterator __last, 04397 _Predicate __pred, const _Tp& __new_value) 04398 { 04399 // concept requirements 04400 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 04401 _ForwardIterator>) 04402 __glibcxx_function_requires(_ConvertibleConcept<_Tp, 04403 typename iterator_traits<_ForwardIterator>::value_type>) 04404 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 04405 typename iterator_traits<_ForwardIterator>::value_type>) 04406 __glibcxx_requires_valid_range(__first, __last); 04407 04408 for (; __first != __last; ++__first) 04409 if (__pred(*__first)) 04410 *__first = __new_value; 04411 } 04412 04413 /** 04414 * @brief Assign the result of a function object to each value in a 04415 * sequence. 04416 * @ingroup mutating_algorithms 04417 * @param __first A forward iterator. 04418 * @param __last A forward iterator. 04419 * @param __gen A function object taking no arguments and returning 04420 * std::iterator_traits<_ForwardIterator>::value_type 04421 * @return generate() returns no value. 04422 * 04423 * Performs the assignment @c *i = @p __gen() for each @c i in the range 04424 * @p [__first,__last). 04425 */ 04426 template<typename _ForwardIterator, typename _Generator> 04427 void 04428 generate(_ForwardIterator __first, _ForwardIterator __last, 04429 _Generator __gen) 04430 { 04431 // concept requirements 04432 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 04433 __glibcxx_function_requires(_GeneratorConcept<_Generator, 04434 typename iterator_traits<_ForwardIterator>::value_type>) 04435 __glibcxx_requires_valid_range(__first, __last); 04436 04437 for (; __first != __last; ++__first) 04438 *__first = __gen(); 04439 } 04440 04441 /** 04442 * @brief Assign the result of a function object to each value in a 04443 * sequence. 04444 * @ingroup mutating_algorithms 04445 * @param __first A forward iterator. 04446 * @param __n The length of the sequence. 04447 * @param __gen A function object taking no arguments and returning 04448 * std::iterator_traits<_ForwardIterator>::value_type 04449 * @return The end of the sequence, @p __first+__n 04450 * 04451 * Performs the assignment @c *i = @p __gen() for each @c i in the range 04452 * @p [__first,__first+__n). 04453 * 04454 * _GLIBCXX_RESOLVE_LIB_DEFECTS 04455 * DR 865. More algorithms that throw away information 04456 */ 04457 template<typename _OutputIterator, typename _Size, typename _Generator> 04458 _OutputIterator 04459 generate_n(_OutputIterator __first, _Size __n, _Generator __gen) 04460 { 04461 // concept requirements 04462 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 04463 // "the type returned by a _Generator" 04464 __typeof__(__gen())>) 04465 04466 for (__decltype(__n + 0) __niter = __n; 04467 __niter > 0; --__niter, ++__first) 04468 *__first = __gen(); 04469 return __first; 04470 } 04471 04472 /** 04473 * @brief Copy a sequence, removing consecutive duplicate values. 04474 * @ingroup mutating_algorithms 04475 * @param __first An input iterator. 04476 * @param __last An input iterator. 04477 * @param __result An output iterator. 04478 * @return An iterator designating the end of the resulting sequence. 04479 * 04480 * Copies each element in the range @p [__first,__last) to the range 04481 * beginning at @p __result, except that only the first element is copied 04482 * from groups of consecutive elements that compare equal. 04483 * unique_copy() is stable, so the relative order of elements that are 04484 * copied is unchanged. 04485 * 04486 * _GLIBCXX_RESOLVE_LIB_DEFECTS 04487 * DR 241. Does unique_copy() require CopyConstructible and Assignable? 04488 * 04489 * _GLIBCXX_RESOLVE_LIB_DEFECTS 04490 * DR 538. 241 again: Does unique_copy() require CopyConstructible and 04491 * Assignable? 04492 */ 04493 template<typename _InputIterator, typename _OutputIterator> 04494 inline _OutputIterator 04495 unique_copy(_InputIterator __first, _InputIterator __last, 04496 _OutputIterator __result) 04497 { 04498 // concept requirements 04499 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 04500 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 04501 typename iterator_traits<_InputIterator>::value_type>) 04502 __glibcxx_function_requires(_EqualityComparableConcept< 04503 typename iterator_traits<_InputIterator>::value_type>) 04504 __glibcxx_requires_valid_range(__first, __last); 04505 04506 if (__first == __last) 04507 return __result; 04508 return std::__unique_copy(__first, __last, __result, 04509 __gnu_cxx::__ops::__iter_equal_to_iter(), 04510 std::__iterator_category(__first), 04511 std::__iterator_category(__result)); 04512 } 04513 04514 /** 04515 * @brief Copy a sequence, removing consecutive values using a predicate. 04516 * @ingroup mutating_algorithms 04517 * @param __first An input iterator. 04518 * @param __last An input iterator. 04519 * @param __result An output iterator. 04520 * @param __binary_pred A binary predicate. 04521 * @return An iterator designating the end of the resulting sequence. 04522 * 04523 * Copies each element in the range @p [__first,__last) to the range 04524 * beginning at @p __result, except that only the first element is copied 04525 * from groups of consecutive elements for which @p __binary_pred returns 04526 * true. 04527 * unique_copy() is stable, so the relative order of elements that are 04528 * copied is unchanged. 04529 * 04530 * _GLIBCXX_RESOLVE_LIB_DEFECTS 04531 * DR 241. Does unique_copy() require CopyConstructible and Assignable? 04532 */ 04533 template<typename _InputIterator, typename _OutputIterator, 04534 typename _BinaryPredicate> 04535 inline _OutputIterator 04536 unique_copy(_InputIterator __first, _InputIterator __last, 04537 _OutputIterator __result, 04538 _BinaryPredicate __binary_pred) 04539 { 04540 // concept requirements -- predicates checked later 04541 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 04542 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 04543 typename iterator_traits<_InputIterator>::value_type>) 04544 __glibcxx_requires_valid_range(__first, __last); 04545 04546 if (__first == __last) 04547 return __result; 04548 return std::__unique_copy(__first, __last, __result, 04549 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred), 04550 std::__iterator_category(__first), 04551 std::__iterator_category(__result)); 04552 } 04553 04554 #if _GLIBCXX_HOSTED 04555 /** 04556 * @brief Randomly shuffle the elements of a sequence. 04557 * @ingroup mutating_algorithms 04558 * @param __first A forward iterator. 04559 * @param __last A forward iterator. 04560 * @return Nothing. 04561 * 04562 * Reorder the elements in the range @p [__first,__last) using a random 04563 * distribution, so that every possible ordering of the sequence is 04564 * equally likely. 04565 */ 04566 template<typename _RandomAccessIterator> 04567 inline void 04568 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last) 04569 { 04570 // concept requirements 04571 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 04572 _RandomAccessIterator>) 04573 __glibcxx_requires_valid_range(__first, __last); 04574 04575 if (__first != __last) 04576 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i) 04577 { 04578 // XXX rand() % N is not uniformly distributed 04579 _RandomAccessIterator __j = __first 04580 + std::rand() % ((__i - __first) + 1); 04581 if (__i != __j) 04582 std::iter_swap(__i, __j); 04583 } 04584 } 04585 #endif 04586 04587 /** 04588 * @brief Shuffle the elements of a sequence using a random number 04589 * generator. 04590 * @ingroup mutating_algorithms 04591 * @param __first A forward iterator. 04592 * @param __last A forward iterator. 04593 * @param __rand The RNG functor or function. 04594 * @return Nothing. 04595 * 04596 * Reorders the elements in the range @p [__first,__last) using @p __rand to 04597 * provide a random distribution. Calling @p __rand(N) for a positive 04598 * integer @p N should return a randomly chosen integer from the 04599 * range [0,N). 04600 */ 04601 template<typename _RandomAccessIterator, typename _RandomNumberGenerator> 04602 void 04603 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last, 04604 #if __cplusplus >= 201103L 04605 _RandomNumberGenerator&& __rand) 04606 #else 04607 _RandomNumberGenerator& __rand) 04608 #endif 04609 { 04610 // concept requirements 04611 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 04612 _RandomAccessIterator>) 04613 __glibcxx_requires_valid_range(__first, __last); 04614 04615 if (__first == __last) 04616 return; 04617 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i) 04618 { 04619 _RandomAccessIterator __j = __first + __rand((__i - __first) + 1); 04620 if (__i != __j) 04621 std::iter_swap(__i, __j); 04622 } 04623 } 04624 04625 04626 /** 04627 * @brief Move elements for which a predicate is true to the beginning 04628 * of a sequence. 04629 * @ingroup mutating_algorithms 04630 * @param __first A forward iterator. 04631 * @param __last A forward iterator. 04632 * @param __pred A predicate functor. 04633 * @return An iterator @p middle such that @p __pred(i) is true for each 04634 * iterator @p i in the range @p [__first,middle) and false for each @p i 04635 * in the range @p [middle,__last). 04636 * 04637 * @p __pred must not modify its operand. @p partition() does not preserve 04638 * the relative ordering of elements in each group, use 04639 * @p stable_partition() if this is needed. 04640 */ 04641 template<typename _ForwardIterator, typename _Predicate> 04642 inline _ForwardIterator 04643 partition(_ForwardIterator __first, _ForwardIterator __last, 04644 _Predicate __pred) 04645 { 04646 // concept requirements 04647 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 04648 _ForwardIterator>) 04649 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, 04650 typename iterator_traits<_ForwardIterator>::value_type>) 04651 __glibcxx_requires_valid_range(__first, __last); 04652 04653 return std::__partition(__first, __last, __pred, 04654 std::__iterator_category(__first)); 04655 } 04656 04657 04658 /** 04659 * @brief Sort the smallest elements of a sequence. 04660 * @ingroup sorting_algorithms 04661 * @param __first An iterator. 04662 * @param __middle Another iterator. 04663 * @param __last Another iterator. 04664 * @return Nothing. 04665 * 04666 * Sorts the smallest @p (__middle-__first) elements in the range 04667 * @p [first,last) and moves them to the range @p [__first,__middle). The 04668 * order of the remaining elements in the range @p [__middle,__last) is 04669 * undefined. 04670 * After the sort if @e i and @e j are iterators in the range 04671 * @p [__first,__middle) such that i precedes j and @e k is an iterator in 04672 * the range @p [__middle,__last) then *j<*i and *k<*i are both false. 04673 */ 04674 template<typename _RandomAccessIterator> 04675 inline void 04676 partial_sort(_RandomAccessIterator __first, 04677 _RandomAccessIterator __middle, 04678 _RandomAccessIterator __last) 04679 { 04680 // concept requirements 04681 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 04682 _RandomAccessIterator>) 04683 __glibcxx_function_requires(_LessThanComparableConcept< 04684 typename iterator_traits<_RandomAccessIterator>::value_type>) 04685 __glibcxx_requires_valid_range(__first, __middle); 04686 __glibcxx_requires_valid_range(__middle, __last); 04687 __glibcxx_requires_irreflexive(__first, __last); 04688 04689 std::__partial_sort(__first, __middle, __last, 04690 __gnu_cxx::__ops::__iter_less_iter()); 04691 } 04692 04693 /** 04694 * @brief Sort the smallest elements of a sequence using a predicate 04695 * for comparison. 04696 * @ingroup sorting_algorithms 04697 * @param __first An iterator. 04698 * @param __middle Another iterator. 04699 * @param __last Another iterator. 04700 * @param __comp A comparison functor. 04701 * @return Nothing. 04702 * 04703 * Sorts the smallest @p (__middle-__first) elements in the range 04704 * @p [__first,__last) and moves them to the range @p [__first,__middle). The 04705 * order of the remaining elements in the range @p [__middle,__last) is 04706 * undefined. 04707 * After the sort if @e i and @e j are iterators in the range 04708 * @p [__first,__middle) such that i precedes j and @e k is an iterator in 04709 * the range @p [__middle,__last) then @p *__comp(j,*i) and @p __comp(*k,*i) 04710 * are both false. 04711 */ 04712 template<typename _RandomAccessIterator, typename _Compare> 04713 inline void 04714 partial_sort(_RandomAccessIterator __first, 04715 _RandomAccessIterator __middle, 04716 _RandomAccessIterator __last, 04717 _Compare __comp) 04718 { 04719 // concept requirements 04720 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 04721 _RandomAccessIterator>) 04722 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 04723 typename iterator_traits<_RandomAccessIterator>::value_type, 04724 typename iterator_traits<_RandomAccessIterator>::value_type>) 04725 __glibcxx_requires_valid_range(__first, __middle); 04726 __glibcxx_requires_valid_range(__middle, __last); 04727 __glibcxx_requires_irreflexive_pred(__first, __last, __comp); 04728 04729 std::__partial_sort(__first, __middle, __last, 04730 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 04731 } 04732 04733 /** 04734 * @brief Sort a sequence just enough to find a particular position. 04735 * @ingroup sorting_algorithms 04736 * @param __first An iterator. 04737 * @param __nth Another iterator. 04738 * @param __last Another iterator. 04739 * @return Nothing. 04740 * 04741 * Rearranges the elements in the range @p [__first,__last) so that @p *__nth 04742 * is the same element that would have been in that position had the 04743 * whole sequence been sorted. The elements either side of @p *__nth are 04744 * not completely sorted, but for any iterator @e i in the range 04745 * @p [__first,__nth) and any iterator @e j in the range @p [__nth,__last) it 04746 * holds that *j < *i is false. 04747 */ 04748 template<typename _RandomAccessIterator> 04749 inline void 04750 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, 04751 _RandomAccessIterator __last) 04752 { 04753 // concept requirements 04754 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 04755 _RandomAccessIterator>) 04756 __glibcxx_function_requires(_LessThanComparableConcept< 04757 typename iterator_traits<_RandomAccessIterator>::value_type>) 04758 __glibcxx_requires_valid_range(__first, __nth); 04759 __glibcxx_requires_valid_range(__nth, __last); 04760 __glibcxx_requires_irreflexive(__first, __last); 04761 04762 if (__first == __last || __nth == __last) 04763 return; 04764 04765 std::__introselect(__first, __nth, __last, 04766 std::__lg(__last - __first) * 2, 04767 __gnu_cxx::__ops::__iter_less_iter()); 04768 } 04769 04770 /** 04771 * @brief Sort a sequence just enough to find a particular position 04772 * using a predicate for comparison. 04773 * @ingroup sorting_algorithms 04774 * @param __first An iterator. 04775 * @param __nth Another iterator. 04776 * @param __last Another iterator. 04777 * @param __comp A comparison functor. 04778 * @return Nothing. 04779 * 04780 * Rearranges the elements in the range @p [__first,__last) so that @p *__nth 04781 * is the same element that would have been in that position had the 04782 * whole sequence been sorted. The elements either side of @p *__nth are 04783 * not completely sorted, but for any iterator @e i in the range 04784 * @p [__first,__nth) and any iterator @e j in the range @p [__nth,__last) it 04785 * holds that @p __comp(*j,*i) is false. 04786 */ 04787 template<typename _RandomAccessIterator, typename _Compare> 04788 inline void 04789 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, 04790 _RandomAccessIterator __last, _Compare __comp) 04791 { 04792 // concept requirements 04793 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 04794 _RandomAccessIterator>) 04795 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 04796 typename iterator_traits<_RandomAccessIterator>::value_type, 04797 typename iterator_traits<_RandomAccessIterator>::value_type>) 04798 __glibcxx_requires_valid_range(__first, __nth); 04799 __glibcxx_requires_valid_range(__nth, __last); 04800 __glibcxx_requires_irreflexive_pred(__first, __last, __comp); 04801 04802 if (__first == __last || __nth == __last) 04803 return; 04804 04805 std::__introselect(__first, __nth, __last, 04806 std::__lg(__last - __first) * 2, 04807 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 04808 } 04809 04810 /** 04811 * @brief Sort the elements of a sequence. 04812 * @ingroup sorting_algorithms 04813 * @param __first An iterator. 04814 * @param __last Another iterator. 04815 * @return Nothing. 04816 * 04817 * Sorts the elements in the range @p [__first,__last) in ascending order, 04818 * such that for each iterator @e i in the range @p [__first,__last-1), 04819 * *(i+1)<*i is false. 04820 * 04821 * The relative ordering of equivalent elements is not preserved, use 04822 * @p stable_sort() if this is needed. 04823 */ 04824 template<typename _RandomAccessIterator> 04825 inline void 04826 sort(_RandomAccessIterator __first, _RandomAccessIterator __last) 04827 { 04828 // concept requirements 04829 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 04830 _RandomAccessIterator>) 04831 __glibcxx_function_requires(_LessThanComparableConcept< 04832 typename iterator_traits<_RandomAccessIterator>::value_type>) 04833 __glibcxx_requires_valid_range(__first, __last); 04834 __glibcxx_requires_irreflexive(__first, __last); 04835 04836 std::__sort(__first, __last, __gnu_cxx::__ops::__iter_less_iter()); 04837 } 04838 04839 /** 04840 * @brief Sort the elements of a sequence using a predicate for comparison. 04841 * @ingroup sorting_algorithms 04842 * @param __first An iterator. 04843 * @param __last Another iterator. 04844 * @param __comp A comparison functor. 04845 * @return Nothing. 04846 * 04847 * Sorts the elements in the range @p [__first,__last) in ascending order, 04848 * such that @p __comp(*(i+1),*i) is false for every iterator @e i in the 04849 * range @p [__first,__last-1). 04850 * 04851 * The relative ordering of equivalent elements is not preserved, use 04852 * @p stable_sort() if this is needed. 04853 */ 04854 template<typename _RandomAccessIterator, typename _Compare> 04855 inline void 04856 sort(_RandomAccessIterator __first, _RandomAccessIterator __last, 04857 _Compare __comp) 04858 { 04859 // concept requirements 04860 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 04861 _RandomAccessIterator>) 04862 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 04863 typename iterator_traits<_RandomAccessIterator>::value_type, 04864 typename iterator_traits<_RandomAccessIterator>::value_type>) 04865 __glibcxx_requires_valid_range(__first, __last); 04866 __glibcxx_requires_irreflexive_pred(__first, __last, __comp); 04867 04868 std::__sort(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp)); 04869 } 04870 04871 template<typename _InputIterator1, typename _InputIterator2, 04872 typename _OutputIterator, typename _Compare> 04873 _OutputIterator 04874 __merge(_InputIterator1 __first1, _InputIterator1 __last1, 04875 _InputIterator2 __first2, _InputIterator2 __last2, 04876 _OutputIterator __result, _Compare __comp) 04877 { 04878 while (__first1 != __last1 && __first2 != __last2) 04879 { 04880 if (__comp(__first2, __first1)) 04881 { 04882 *__result = *__first2; 04883 ++__first2; 04884 } 04885 else 04886 { 04887 *__result = *__first1; 04888 ++__first1; 04889 } 04890 ++__result; 04891 } 04892 return std::copy(__first2, __last2, 04893 std::copy(__first1, __last1, __result)); 04894 } 04895 04896 /** 04897 * @brief Merges two sorted ranges. 04898 * @ingroup sorting_algorithms 04899 * @param __first1 An iterator. 04900 * @param __first2 Another iterator. 04901 * @param __last1 Another iterator. 04902 * @param __last2 Another iterator. 04903 * @param __result An iterator pointing to the end of the merged range. 04904 * @return An iterator pointing to the first element <em>not less 04905 * than</em> @e val. 04906 * 04907 * Merges the ranges @p [__first1,__last1) and @p [__first2,__last2) into 04908 * the sorted range @p [__result, __result + (__last1-__first1) + 04909 * (__last2-__first2)). Both input ranges must be sorted, and the 04910 * output range must not overlap with either of the input ranges. 04911 * The sort is @e stable, that is, for equivalent elements in the 04912 * two ranges, elements from the first range will always come 04913 * before elements from the second. 04914 */ 04915 template<typename _InputIterator1, typename _InputIterator2, 04916 typename _OutputIterator> 04917 inline _OutputIterator 04918 merge(_InputIterator1 __first1, _InputIterator1 __last1, 04919 _InputIterator2 __first2, _InputIterator2 __last2, 04920 _OutputIterator __result) 04921 { 04922 // concept requirements 04923 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 04924 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 04925 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 04926 typename iterator_traits<_InputIterator1>::value_type>) 04927 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 04928 typename iterator_traits<_InputIterator2>::value_type>) 04929 __glibcxx_function_requires(_LessThanOpConcept< 04930 typename iterator_traits<_InputIterator2>::value_type, 04931 typename iterator_traits<_InputIterator1>::value_type>) 04932 __glibcxx_requires_sorted_set(__first1, __last1, __first2); 04933 __glibcxx_requires_sorted_set(__first2, __last2, __first1); 04934 __glibcxx_requires_irreflexive2(__first1, __last1); 04935 __glibcxx_requires_irreflexive2(__first2, __last2); 04936 04937 return _GLIBCXX_STD_A::__merge(__first1, __last1, 04938 __first2, __last2, __result, 04939 __gnu_cxx::__ops::__iter_less_iter()); 04940 } 04941 04942 /** 04943 * @brief Merges two sorted ranges. 04944 * @ingroup sorting_algorithms 04945 * @param __first1 An iterator. 04946 * @param __first2 Another iterator. 04947 * @param __last1 Another iterator. 04948 * @param __last2 Another iterator. 04949 * @param __result An iterator pointing to the end of the merged range. 04950 * @param __comp A functor to use for comparisons. 04951 * @return An iterator pointing to the first element "not less 04952 * than" @e val. 04953 * 04954 * Merges the ranges @p [__first1,__last1) and @p [__first2,__last2) into 04955 * the sorted range @p [__result, __result + (__last1-__first1) + 04956 * (__last2-__first2)). Both input ranges must be sorted, and the 04957 * output range must not overlap with either of the input ranges. 04958 * The sort is @e stable, that is, for equivalent elements in the 04959 * two ranges, elements from the first range will always come 04960 * before elements from the second. 04961 * 04962 * The comparison function should have the same effects on ordering as 04963 * the function used for the initial sort. 04964 */ 04965 template<typename _InputIterator1, typename _InputIterator2, 04966 typename _OutputIterator, typename _Compare> 04967 inline _OutputIterator 04968 merge(_InputIterator1 __first1, _InputIterator1 __last1, 04969 _InputIterator2 __first2, _InputIterator2 __last2, 04970 _OutputIterator __result, _Compare __comp) 04971 { 04972 // concept requirements 04973 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 04974 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 04975 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 04976 typename iterator_traits<_InputIterator1>::value_type>) 04977 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 04978 typename iterator_traits<_InputIterator2>::value_type>) 04979 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 04980 typename iterator_traits<_InputIterator2>::value_type, 04981 typename iterator_traits<_InputIterator1>::value_type>) 04982 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp); 04983 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp); 04984 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp); 04985 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp); 04986 04987 return _GLIBCXX_STD_A::__merge(__first1, __last1, 04988 __first2, __last2, __result, 04989 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 04990 } 04991 04992 template<typename _RandomAccessIterator, typename _Compare> 04993 inline void 04994 __stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, 04995 _Compare __comp) 04996 { 04997 typedef typename iterator_traits<_RandomAccessIterator>::value_type 04998 _ValueType; 04999 typedef typename iterator_traits<_RandomAccessIterator>::difference_type 05000 _DistanceType; 05001 05002 typedef _Temporary_buffer<_RandomAccessIterator, _ValueType> _TmpBuf; 05003 _TmpBuf __buf(__first, __last); 05004 05005 if (__buf.begin() == 0) 05006 std::__inplace_stable_sort(__first, __last, __comp); 05007 else 05008 std::__stable_sort_adaptive(__first, __last, __buf.begin(), 05009 _DistanceType(__buf.size()), __comp); 05010 } 05011 05012 /** 05013 * @brief Sort the elements of a sequence, preserving the relative order 05014 * of equivalent elements. 05015 * @ingroup sorting_algorithms 05016 * @param __first An iterator. 05017 * @param __last Another iterator. 05018 * @return Nothing. 05019 * 05020 * Sorts the elements in the range @p [__first,__last) in ascending order, 05021 * such that for each iterator @p i in the range @p [__first,__last-1), 05022 * @p *(i+1)<*i is false. 05023 * 05024 * The relative ordering of equivalent elements is preserved, so any two 05025 * elements @p x and @p y in the range @p [__first,__last) such that 05026 * @p x<y is false and @p y<x is false will have the same relative 05027 * ordering after calling @p stable_sort(). 05028 */ 05029 template<typename _RandomAccessIterator> 05030 inline void 05031 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last) 05032 { 05033 // concept requirements 05034 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 05035 _RandomAccessIterator>) 05036 __glibcxx_function_requires(_LessThanComparableConcept< 05037 typename iterator_traits<_RandomAccessIterator>::value_type>) 05038 __glibcxx_requires_valid_range(__first, __last); 05039 __glibcxx_requires_irreflexive(__first, __last); 05040 05041 _GLIBCXX_STD_A::__stable_sort(__first, __last, 05042 __gnu_cxx::__ops::__iter_less_iter()); 05043 } 05044 05045 /** 05046 * @brief Sort the elements of a sequence using a predicate for comparison, 05047 * preserving the relative order of equivalent elements. 05048 * @ingroup sorting_algorithms 05049 * @param __first An iterator. 05050 * @param __last Another iterator. 05051 * @param __comp A comparison functor. 05052 * @return Nothing. 05053 * 05054 * Sorts the elements in the range @p [__first,__last) in ascending order, 05055 * such that for each iterator @p i in the range @p [__first,__last-1), 05056 * @p __comp(*(i+1),*i) is false. 05057 * 05058 * The relative ordering of equivalent elements is preserved, so any two 05059 * elements @p x and @p y in the range @p [__first,__last) such that 05060 * @p __comp(x,y) is false and @p __comp(y,x) is false will have the same 05061 * relative ordering after calling @p stable_sort(). 05062 */ 05063 template<typename _RandomAccessIterator, typename _Compare> 05064 inline void 05065 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, 05066 _Compare __comp) 05067 { 05068 // concept requirements 05069 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 05070 _RandomAccessIterator>) 05071 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 05072 typename iterator_traits<_RandomAccessIterator>::value_type, 05073 typename iterator_traits<_RandomAccessIterator>::value_type>) 05074 __glibcxx_requires_valid_range(__first, __last); 05075 __glibcxx_requires_irreflexive_pred(__first, __last, __comp); 05076 05077 _GLIBCXX_STD_A::__stable_sort(__first, __last, 05078 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 05079 } 05080 05081 template<typename _InputIterator1, typename _InputIterator2, 05082 typename _OutputIterator, 05083 typename _Compare> 05084 _OutputIterator 05085 __set_union(_InputIterator1 __first1, _InputIterator1 __last1, 05086 _InputIterator2 __first2, _InputIterator2 __last2, 05087 _OutputIterator __result, _Compare __comp) 05088 { 05089 while (__first1 != __last1 && __first2 != __last2) 05090 { 05091 if (__comp(__first1, __first2)) 05092 { 05093 *__result = *__first1; 05094 ++__first1; 05095 } 05096 else if (__comp(__first2, __first1)) 05097 { 05098 *__result = *__first2; 05099 ++__first2; 05100 } 05101 else 05102 { 05103 *__result = *__first1; 05104 ++__first1; 05105 ++__first2; 05106 } 05107 ++__result; 05108 } 05109 return std::copy(__first2, __last2, 05110 std::copy(__first1, __last1, __result)); 05111 } 05112 05113 /** 05114 * @brief Return the union of two sorted ranges. 05115 * @ingroup set_algorithms 05116 * @param __first1 Start of first range. 05117 * @param __last1 End of first range. 05118 * @param __first2 Start of second range. 05119 * @param __last2 End of second range. 05120 * @return End of the output range. 05121 * @ingroup set_algorithms 05122 * 05123 * This operation iterates over both ranges, copying elements present in 05124 * each range in order to the output range. Iterators increment for each 05125 * range. When the current element of one range is less than the other, 05126 * that element is copied and the iterator advanced. If an element is 05127 * contained in both ranges, the element from the first range is copied and 05128 * both ranges advance. The output range may not overlap either input 05129 * range. 05130 */ 05131 template<typename _InputIterator1, typename _InputIterator2, 05132 typename _OutputIterator> 05133 inline _OutputIterator 05134 set_union(_InputIterator1 __first1, _InputIterator1 __last1, 05135 _InputIterator2 __first2, _InputIterator2 __last2, 05136 _OutputIterator __result) 05137 { 05138 // concept requirements 05139 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 05140 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 05141 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 05142 typename iterator_traits<_InputIterator1>::value_type>) 05143 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 05144 typename iterator_traits<_InputIterator2>::value_type>) 05145 __glibcxx_function_requires(_LessThanOpConcept< 05146 typename iterator_traits<_InputIterator1>::value_type, 05147 typename iterator_traits<_InputIterator2>::value_type>) 05148 __glibcxx_function_requires(_LessThanOpConcept< 05149 typename iterator_traits<_InputIterator2>::value_type, 05150 typename iterator_traits<_InputIterator1>::value_type>) 05151 __glibcxx_requires_sorted_set(__first1, __last1, __first2); 05152 __glibcxx_requires_sorted_set(__first2, __last2, __first1); 05153 __glibcxx_requires_irreflexive2(__first1, __last1); 05154 __glibcxx_requires_irreflexive2(__first2, __last2); 05155 05156 return _GLIBCXX_STD_A::__set_union(__first1, __last1, 05157 __first2, __last2, __result, 05158 __gnu_cxx::__ops::__iter_less_iter()); 05159 } 05160 05161 /** 05162 * @brief Return the union of two sorted ranges using a comparison functor. 05163 * @ingroup set_algorithms 05164 * @param __first1 Start of first range. 05165 * @param __last1 End of first range. 05166 * @param __first2 Start of second range. 05167 * @param __last2 End of second range. 05168 * @param __comp The comparison functor. 05169 * @return End of the output range. 05170 * @ingroup set_algorithms 05171 * 05172 * This operation iterates over both ranges, copying elements present in 05173 * each range in order to the output range. Iterators increment for each 05174 * range. When the current element of one range is less than the other 05175 * according to @p __comp, that element is copied and the iterator advanced. 05176 * If an equivalent element according to @p __comp is contained in both 05177 * ranges, the element from the first range is copied and both ranges 05178 * advance. The output range may not overlap either input range. 05179 */ 05180 template<typename _InputIterator1, typename _InputIterator2, 05181 typename _OutputIterator, typename _Compare> 05182 inline _OutputIterator 05183 set_union(_InputIterator1 __first1, _InputIterator1 __last1, 05184 _InputIterator2 __first2, _InputIterator2 __last2, 05185 _OutputIterator __result, _Compare __comp) 05186 { 05187 // concept requirements 05188 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 05189 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 05190 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 05191 typename iterator_traits<_InputIterator1>::value_type>) 05192 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 05193 typename iterator_traits<_InputIterator2>::value_type>) 05194 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 05195 typename iterator_traits<_InputIterator1>::value_type, 05196 typename iterator_traits<_InputIterator2>::value_type>) 05197 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 05198 typename iterator_traits<_InputIterator2>::value_type, 05199 typename iterator_traits<_InputIterator1>::value_type>) 05200 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp); 05201 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp); 05202 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp); 05203 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp); 05204 05205 return _GLIBCXX_STD_A::__set_union(__first1, __last1, 05206 __first2, __last2, __result, 05207 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 05208 } 05209 05210 template<typename _InputIterator1, typename _InputIterator2, 05211 typename _OutputIterator, 05212 typename _Compare> 05213 _OutputIterator 05214 __set_intersection(_InputIterator1 __first1, _InputIterator1 __last1, 05215 _InputIterator2 __first2, _InputIterator2 __last2, 05216 _OutputIterator __result, _Compare __comp) 05217 { 05218 while (__first1 != __last1 && __first2 != __last2) 05219 if (__comp(__first1, __first2)) 05220 ++__first1; 05221 else if (__comp(__first2, __first1)) 05222 ++__first2; 05223 else 05224 { 05225 *__result = *__first1; 05226 ++__first1; 05227 ++__first2; 05228 ++__result; 05229 } 05230 return __result; 05231 } 05232 05233 /** 05234 * @brief Return the intersection of two sorted ranges. 05235 * @ingroup set_algorithms 05236 * @param __first1 Start of first range. 05237 * @param __last1 End of first range. 05238 * @param __first2 Start of second range. 05239 * @param __last2 End of second range. 05240 * @return End of the output range. 05241 * @ingroup set_algorithms 05242 * 05243 * This operation iterates over both ranges, copying elements present in 05244 * both ranges in order to the output range. Iterators increment for each 05245 * range. When the current element of one range is less than the other, 05246 * that iterator advances. If an element is contained in both ranges, the 05247 * element from the first range is copied and both ranges advance. The 05248 * output range may not overlap either input range. 05249 */ 05250 template<typename _InputIterator1, typename _InputIterator2, 05251 typename _OutputIterator> 05252 inline _OutputIterator 05253 set_intersection(_InputIterator1 __first1, _InputIterator1 __last1, 05254 _InputIterator2 __first2, _InputIterator2 __last2, 05255 _OutputIterator __result) 05256 { 05257 // concept requirements 05258 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 05259 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 05260 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 05261 typename iterator_traits<_InputIterator1>::value_type>) 05262 __glibcxx_function_requires(_LessThanOpConcept< 05263 typename iterator_traits<_InputIterator1>::value_type, 05264 typename iterator_traits<_InputIterator2>::value_type>) 05265 __glibcxx_function_requires(_LessThanOpConcept< 05266 typename iterator_traits<_InputIterator2>::value_type, 05267 typename iterator_traits<_InputIterator1>::value_type>) 05268 __glibcxx_requires_sorted_set(__first1, __last1, __first2); 05269 __glibcxx_requires_sorted_set(__first2, __last2, __first1); 05270 __glibcxx_requires_irreflexive2(__first1, __last1); 05271 __glibcxx_requires_irreflexive2(__first2, __last2); 05272 05273 return _GLIBCXX_STD_A::__set_intersection(__first1, __last1, 05274 __first2, __last2, __result, 05275 __gnu_cxx::__ops::__iter_less_iter()); 05276 } 05277 05278 /** 05279 * @brief Return the intersection of two sorted ranges using comparison 05280 * functor. 05281 * @ingroup set_algorithms 05282 * @param __first1 Start of first range. 05283 * @param __last1 End of first range. 05284 * @param __first2 Start of second range. 05285 * @param __last2 End of second range. 05286 * @param __comp The comparison functor. 05287 * @return End of the output range. 05288 * @ingroup set_algorithms 05289 * 05290 * This operation iterates over both ranges, copying elements present in 05291 * both ranges in order to the output range. Iterators increment for each 05292 * range. When the current element of one range is less than the other 05293 * according to @p __comp, that iterator advances. If an element is 05294 * contained in both ranges according to @p __comp, the element from the 05295 * first range is copied and both ranges advance. The output range may not 05296 * overlap either input range. 05297 */ 05298 template<typename _InputIterator1, typename _InputIterator2, 05299 typename _OutputIterator, typename _Compare> 05300 inline _OutputIterator 05301 set_intersection(_InputIterator1 __first1, _InputIterator1 __last1, 05302 _InputIterator2 __first2, _InputIterator2 __last2, 05303 _OutputIterator __result, _Compare __comp) 05304 { 05305 // concept requirements 05306 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 05307 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 05308 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 05309 typename iterator_traits<_InputIterator1>::value_type>) 05310 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 05311 typename iterator_traits<_InputIterator1>::value_type, 05312 typename iterator_traits<_InputIterator2>::value_type>) 05313 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 05314 typename iterator_traits<_InputIterator2>::value_type, 05315 typename iterator_traits<_InputIterator1>::value_type>) 05316 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp); 05317 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp); 05318 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp); 05319 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp); 05320 05321 return _GLIBCXX_STD_A::__set_intersection(__first1, __last1, 05322 __first2, __last2, __result, 05323 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 05324 } 05325 05326 template<typename _InputIterator1, typename _InputIterator2, 05327 typename _OutputIterator, 05328 typename _Compare> 05329 _OutputIterator 05330 __set_difference(_InputIterator1 __first1, _InputIterator1 __last1, 05331 _InputIterator2 __first2, _InputIterator2 __last2, 05332 _OutputIterator __result, _Compare __comp) 05333 { 05334 while (__first1 != __last1 && __first2 != __last2) 05335 if (__comp(__first1, __first2)) 05336 { 05337 *__result = *__first1; 05338 ++__first1; 05339 ++__result; 05340 } 05341 else if (__comp(__first2, __first1)) 05342 ++__first2; 05343 else 05344 { 05345 ++__first1; 05346 ++__first2; 05347 } 05348 return std::copy(__first1, __last1, __result); 05349 } 05350 05351 /** 05352 * @brief Return the difference of two sorted ranges. 05353 * @ingroup set_algorithms 05354 * @param __first1 Start of first range. 05355 * @param __last1 End of first range. 05356 * @param __first2 Start of second range. 05357 * @param __last2 End of second range. 05358 * @return End of the output range. 05359 * @ingroup set_algorithms 05360 * 05361 * This operation iterates over both ranges, copying elements present in 05362 * the first range but not the second in order to the output range. 05363 * Iterators increment for each range. When the current element of the 05364 * first range is less than the second, that element is copied and the 05365 * iterator advances. If the current element of the second range is less, 05366 * the iterator advances, but no element is copied. If an element is 05367 * contained in both ranges, no elements are copied and both ranges 05368 * advance. The output range may not overlap either input range. 05369 */ 05370 template<typename _InputIterator1, typename _InputIterator2, 05371 typename _OutputIterator> 05372 inline _OutputIterator 05373 set_difference(_InputIterator1 __first1, _InputIterator1 __last1, 05374 _InputIterator2 __first2, _InputIterator2 __last2, 05375 _OutputIterator __result) 05376 { 05377 // concept requirements 05378 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 05379 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 05380 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 05381 typename iterator_traits<_InputIterator1>::value_type>) 05382 __glibcxx_function_requires(_LessThanOpConcept< 05383 typename iterator_traits<_InputIterator1>::value_type, 05384 typename iterator_traits<_InputIterator2>::value_type>) 05385 __glibcxx_function_requires(_LessThanOpConcept< 05386 typename iterator_traits<_InputIterator2>::value_type, 05387 typename iterator_traits<_InputIterator1>::value_type>) 05388 __glibcxx_requires_sorted_set(__first1, __last1, __first2); 05389 __glibcxx_requires_sorted_set(__first2, __last2, __first1); 05390 __glibcxx_requires_irreflexive2(__first1, __last1); 05391 __glibcxx_requires_irreflexive2(__first2, __last2); 05392 05393 return _GLIBCXX_STD_A::__set_difference(__first1, __last1, 05394 __first2, __last2, __result, 05395 __gnu_cxx::__ops::__iter_less_iter()); 05396 } 05397 05398 /** 05399 * @brief Return the difference of two sorted ranges using comparison 05400 * functor. 05401 * @ingroup set_algorithms 05402 * @param __first1 Start of first range. 05403 * @param __last1 End of first range. 05404 * @param __first2 Start of second range. 05405 * @param __last2 End of second range. 05406 * @param __comp The comparison functor. 05407 * @return End of the output range. 05408 * @ingroup set_algorithms 05409 * 05410 * This operation iterates over both ranges, copying elements present in 05411 * the first range but not the second in order to the output range. 05412 * Iterators increment for each range. When the current element of the 05413 * first range is less than the second according to @p __comp, that element 05414 * is copied and the iterator advances. If the current element of the 05415 * second range is less, no element is copied and the iterator advances. 05416 * If an element is contained in both ranges according to @p __comp, no 05417 * elements are copied and both ranges advance. The output range may not 05418 * overlap either input range. 05419 */ 05420 template<typename _InputIterator1, typename _InputIterator2, 05421 typename _OutputIterator, typename _Compare> 05422 inline _OutputIterator 05423 set_difference(_InputIterator1 __first1, _InputIterator1 __last1, 05424 _InputIterator2 __first2, _InputIterator2 __last2, 05425 _OutputIterator __result, _Compare __comp) 05426 { 05427 // concept requirements 05428 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 05429 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 05430 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 05431 typename iterator_traits<_InputIterator1>::value_type>) 05432 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 05433 typename iterator_traits<_InputIterator1>::value_type, 05434 typename iterator_traits<_InputIterator2>::value_type>) 05435 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 05436 typename iterator_traits<_InputIterator2>::value_type, 05437 typename iterator_traits<_InputIterator1>::value_type>) 05438 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp); 05439 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp); 05440 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp); 05441 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp); 05442 05443 return _GLIBCXX_STD_A::__set_difference(__first1, __last1, 05444 __first2, __last2, __result, 05445 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 05446 } 05447 05448 template<typename _InputIterator1, typename _InputIterator2, 05449 typename _OutputIterator, 05450 typename _Compare> 05451 _OutputIterator 05452 __set_symmetric_difference(_InputIterator1 __first1, 05453 _InputIterator1 __last1, 05454 _InputIterator2 __first2, 05455 _InputIterator2 __last2, 05456 _OutputIterator __result, 05457 _Compare __comp) 05458 { 05459 while (__first1 != __last1 && __first2 != __last2) 05460 if (__comp(__first1, __first2)) 05461 { 05462 *__result = *__first1; 05463 ++__first1; 05464 ++__result; 05465 } 05466 else if (__comp(__first2, __first1)) 05467 { 05468 *__result = *__first2; 05469 ++__first2; 05470 ++__result; 05471 } 05472 else 05473 { 05474 ++__first1; 05475 ++__first2; 05476 } 05477 return std::copy(__first2, __last2, 05478 std::copy(__first1, __last1, __result)); 05479 } 05480 05481 /** 05482 * @brief Return the symmetric difference of two sorted ranges. 05483 * @ingroup set_algorithms 05484 * @param __first1 Start of first range. 05485 * @param __last1 End of first range. 05486 * @param __first2 Start of second range. 05487 * @param __last2 End of second range. 05488 * @return End of the output range. 05489 * @ingroup set_algorithms 05490 * 05491 * This operation iterates over both ranges, copying elements present in 05492 * one range but not the other in order to the output range. Iterators 05493 * increment for each range. When the current element of one range is less 05494 * than the other, that element is copied and the iterator advances. If an 05495 * element is contained in both ranges, no elements are copied and both 05496 * ranges advance. The output range may not overlap either input range. 05497 */ 05498 template<typename _InputIterator1, typename _InputIterator2, 05499 typename _OutputIterator> 05500 inline _OutputIterator 05501 set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1, 05502 _InputIterator2 __first2, _InputIterator2 __last2, 05503 _OutputIterator __result) 05504 { 05505 // concept requirements 05506 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 05507 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 05508 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 05509 typename iterator_traits<_InputIterator1>::value_type>) 05510 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 05511 typename iterator_traits<_InputIterator2>::value_type>) 05512 __glibcxx_function_requires(_LessThanOpConcept< 05513 typename iterator_traits<_InputIterator1>::value_type, 05514 typename iterator_traits<_InputIterator2>::value_type>) 05515 __glibcxx_function_requires(_LessThanOpConcept< 05516 typename iterator_traits<_InputIterator2>::value_type, 05517 typename iterator_traits<_InputIterator1>::value_type>) 05518 __glibcxx_requires_sorted_set(__first1, __last1, __first2); 05519 __glibcxx_requires_sorted_set(__first2, __last2, __first1); 05520 __glibcxx_requires_irreflexive2(__first1, __last1); 05521 __glibcxx_requires_irreflexive2(__first2, __last2); 05522 05523 return _GLIBCXX_STD_A::__set_symmetric_difference(__first1, __last1, 05524 __first2, __last2, __result, 05525 __gnu_cxx::__ops::__iter_less_iter()); 05526 } 05527 05528 /** 05529 * @brief Return the symmetric difference of two sorted ranges using 05530 * comparison functor. 05531 * @ingroup set_algorithms 05532 * @param __first1 Start of first range. 05533 * @param __last1 End of first range. 05534 * @param __first2 Start of second range. 05535 * @param __last2 End of second range. 05536 * @param __comp The comparison functor. 05537 * @return End of the output range. 05538 * @ingroup set_algorithms 05539 * 05540 * This operation iterates over both ranges, copying elements present in 05541 * one range but not the other in order to the output range. Iterators 05542 * increment for each range. When the current element of one range is less 05543 * than the other according to @p comp, that element is copied and the 05544 * iterator advances. If an element is contained in both ranges according 05545 * to @p __comp, no elements are copied and both ranges advance. The output 05546 * range may not overlap either input range. 05547 */ 05548 template<typename _InputIterator1, typename _InputIterator2, 05549 typename _OutputIterator, typename _Compare> 05550 inline _OutputIterator 05551 set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1, 05552 _InputIterator2 __first2, _InputIterator2 __last2, 05553 _OutputIterator __result, 05554 _Compare __comp) 05555 { 05556 // concept requirements 05557 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 05558 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 05559 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 05560 typename iterator_traits<_InputIterator1>::value_type>) 05561 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 05562 typename iterator_traits<_InputIterator2>::value_type>) 05563 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 05564 typename iterator_traits<_InputIterator1>::value_type, 05565 typename iterator_traits<_InputIterator2>::value_type>) 05566 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 05567 typename iterator_traits<_InputIterator2>::value_type, 05568 typename iterator_traits<_InputIterator1>::value_type>) 05569 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp); 05570 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp); 05571 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp); 05572 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp); 05573 05574 return _GLIBCXX_STD_A::__set_symmetric_difference(__first1, __last1, 05575 __first2, __last2, __result, 05576 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 05577 } 05578 05579 template<typename _ForwardIterator, typename _Compare> 05580 _GLIBCXX14_CONSTEXPR 05581 _ForwardIterator 05582 __min_element(_ForwardIterator __first, _ForwardIterator __last, 05583 _Compare __comp) 05584 { 05585 if (__first == __last) 05586 return __first; 05587 _ForwardIterator __result = __first; 05588 while (++__first != __last) 05589 if (__comp(__first, __result)) 05590 __result = __first; 05591 return __result; 05592 } 05593 05594 /** 05595 * @brief Return the minimum element in a range. 05596 * @ingroup sorting_algorithms 05597 * @param __first Start of range. 05598 * @param __last End of range. 05599 * @return Iterator referencing the first instance of the smallest value. 05600 */ 05601 template<typename _ForwardIterator> 05602 _GLIBCXX14_CONSTEXPR 05603 _ForwardIterator 05604 inline min_element(_ForwardIterator __first, _ForwardIterator __last) 05605 { 05606 // concept requirements 05607 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 05608 __glibcxx_function_requires(_LessThanComparableConcept< 05609 typename iterator_traits<_ForwardIterator>::value_type>) 05610 __glibcxx_requires_valid_range(__first, __last); 05611 __glibcxx_requires_irreflexive(__first, __last); 05612 05613 return _GLIBCXX_STD_A::__min_element(__first, __last, 05614 __gnu_cxx::__ops::__iter_less_iter()); 05615 } 05616 05617 /** 05618 * @brief Return the minimum element in a range using comparison functor. 05619 * @ingroup sorting_algorithms 05620 * @param __first Start of range. 05621 * @param __last End of range. 05622 * @param __comp Comparison functor. 05623 * @return Iterator referencing the first instance of the smallest value 05624 * according to __comp. 05625 */ 05626 template<typename _ForwardIterator, typename _Compare> 05627 _GLIBCXX14_CONSTEXPR 05628 inline _ForwardIterator 05629 min_element(_ForwardIterator __first, _ForwardIterator __last, 05630 _Compare __comp) 05631 { 05632 // concept requirements 05633 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 05634 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 05635 typename iterator_traits<_ForwardIterator>::value_type, 05636 typename iterator_traits<_ForwardIterator>::value_type>) 05637 __glibcxx_requires_valid_range(__first, __last); 05638 __glibcxx_requires_irreflexive_pred(__first, __last, __comp); 05639 05640 return _GLIBCXX_STD_A::__min_element(__first, __last, 05641 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 05642 } 05643 05644 template<typename _ForwardIterator, typename _Compare> 05645 _GLIBCXX14_CONSTEXPR 05646 _ForwardIterator 05647 __max_element(_ForwardIterator __first, _ForwardIterator __last, 05648 _Compare __comp) 05649 { 05650 if (__first == __last) return __first; 05651 _ForwardIterator __result = __first; 05652 while (++__first != __last) 05653 if (__comp(__result, __first)) 05654 __result = __first; 05655 return __result; 05656 } 05657 05658 /** 05659 * @brief Return the maximum element in a range. 05660 * @ingroup sorting_algorithms 05661 * @param __first Start of range. 05662 * @param __last End of range. 05663 * @return Iterator referencing the first instance of the largest value. 05664 */ 05665 template<typename _ForwardIterator> 05666 _GLIBCXX14_CONSTEXPR 05667 inline _ForwardIterator 05668 max_element(_ForwardIterator __first, _ForwardIterator __last) 05669 { 05670 // concept requirements 05671 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 05672 __glibcxx_function_requires(_LessThanComparableConcept< 05673 typename iterator_traits<_ForwardIterator>::value_type>) 05674 __glibcxx_requires_valid_range(__first, __last); 05675 __glibcxx_requires_irreflexive(__first, __last); 05676 05677 return _GLIBCXX_STD_A::__max_element(__first, __last, 05678 __gnu_cxx::__ops::__iter_less_iter()); 05679 } 05680 05681 /** 05682 * @brief Return the maximum element in a range using comparison functor. 05683 * @ingroup sorting_algorithms 05684 * @param __first Start of range. 05685 * @param __last End of range. 05686 * @param __comp Comparison functor. 05687 * @return Iterator referencing the first instance of the largest value 05688 * according to __comp. 05689 */ 05690 template<typename _ForwardIterator, typename _Compare> 05691 _GLIBCXX14_CONSTEXPR 05692 inline _ForwardIterator 05693 max_element(_ForwardIterator __first, _ForwardIterator __last, 05694 _Compare __comp) 05695 { 05696 // concept requirements 05697 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 05698 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, 05699 typename iterator_traits<_ForwardIterator>::value_type, 05700 typename iterator_traits<_ForwardIterator>::value_type>) 05701 __glibcxx_requires_valid_range(__first, __last); 05702 __glibcxx_requires_irreflexive_pred(__first, __last, __comp); 05703 05704 return _GLIBCXX_STD_A::__max_element(__first, __last, 05705 __gnu_cxx::__ops::__iter_comp_iter(__comp)); 05706 } 05707 05708 #if __cplusplus >= 201402L 05709 /// Reservoir sampling algorithm. 05710 template<typename _InputIterator, typename _RandomAccessIterator, 05711 typename _Size, typename _UniformRandomBitGenerator> 05712 _RandomAccessIterator 05713 __sample(_InputIterator __first, _InputIterator __last, input_iterator_tag, 05714 _RandomAccessIterator __out, random_access_iterator_tag, 05715 _Size __n, _UniformRandomBitGenerator&& __g) 05716 { 05717 using __distrib_type = uniform_int_distribution<_Size>; 05718 using __param_type = typename __distrib_type::param_type; 05719 __distrib_type __d{}; 05720 _Size __sample_sz = 0; 05721 while (__first != __last && __sample_sz != __n) 05722 { 05723 __out[__sample_sz++] = *__first; 05724 ++__first; 05725 } 05726 for (auto __pop_sz = __sample_sz; __first != __last; 05727 ++__first, (void) ++__pop_sz) 05728 { 05729 const auto __k = __d(__g, __param_type{0, __pop_sz}); 05730 if (__k < __n) 05731 __out[__k] = *__first; 05732 } 05733 return __out + __sample_sz; 05734 } 05735 05736 /// Selection sampling algorithm. 05737 template<typename _ForwardIterator, typename _OutputIterator, typename _Cat, 05738 typename _Size, typename _UniformRandomBitGenerator> 05739 _OutputIterator 05740 __sample(_ForwardIterator __first, _ForwardIterator __last, 05741 forward_iterator_tag, 05742 _OutputIterator __out, _Cat, 05743 _Size __n, _UniformRandomBitGenerator&& __g) 05744 { 05745 using __distrib_type = uniform_int_distribution<_Size>; 05746 using __param_type = typename __distrib_type::param_type; 05747 using _USize = make_unsigned_t<_Size>; 05748 using _Gen = remove_reference_t<_UniformRandomBitGenerator>; 05749 using __uc_type = common_type_t<typename _Gen::result_type, _USize>; 05750 05751 __distrib_type __d{}; 05752 _Size __unsampled_sz = std::distance(__first, __last); 05753 __n = std::min(__n, __unsampled_sz); 05754 05755 // If possible, we use __gen_two_uniform_ints to efficiently produce 05756 // two random numbers using a single distribution invocation: 05757 05758 const __uc_type __urngrange = __g.max() - __g.min(); 05759 if (__urngrange / __uc_type(__unsampled_sz) >= __uc_type(__unsampled_sz)) 05760 // I.e. (__urngrange >= __unsampled_sz * __unsampled_sz) but without 05761 // wrapping issues. 05762 { 05763 while (__n != 0 && __unsampled_sz >= 2) 05764 { 05765 const pair<_Size, _Size> __p = 05766 __gen_two_uniform_ints(__unsampled_sz, __unsampled_sz - 1, __g); 05767 05768 --__unsampled_sz; 05769 if (__p.first < __n) 05770 { 05771 *__out++ = *__first; 05772 --__n; 05773 } 05774 05775 ++__first; 05776 05777 if (__n == 0) break; 05778 05779 --__unsampled_sz; 05780 if (__p.second < __n) 05781 { 05782 *__out++ = *__first; 05783 --__n; 05784 } 05785 05786 ++__first; 05787 } 05788 } 05789 05790 // The loop above is otherwise equivalent to this one-at-a-time version: 05791 05792 for (; __n != 0; ++__first) 05793 if (__d(__g, __param_type{0, --__unsampled_sz}) < __n) 05794 { 05795 *__out++ = *__first; 05796 --__n; 05797 } 05798 return __out; 05799 } 05800 05801 #if __cplusplus > 201402L 05802 #define __cpp_lib_sample 201603 05803 /// Take a random sample from a population. 05804 template<typename _PopulationIterator, typename _SampleIterator, 05805 typename _Distance, typename _UniformRandomBitGenerator> 05806 _SampleIterator 05807 sample(_PopulationIterator __first, _PopulationIterator __last, 05808 _SampleIterator __out, _Distance __n, 05809 _UniformRandomBitGenerator&& __g) 05810 { 05811 using __pop_cat = typename 05812 std::iterator_traits<_PopulationIterator>::iterator_category; 05813 using __samp_cat = typename 05814 std::iterator_traits<_SampleIterator>::iterator_category; 05815 05816 static_assert( 05817 __or_<is_convertible<__pop_cat, forward_iterator_tag>, 05818 is_convertible<__samp_cat, random_access_iterator_tag>>::value, 05819 "output range must use a RandomAccessIterator when input range" 05820 " does not meet the ForwardIterator requirements"); 05821 05822 static_assert(is_integral<_Distance>::value, 05823 "sample size must be an integer type"); 05824 05825 typename iterator_traits<_PopulationIterator>::difference_type __d = __n; 05826 return _GLIBCXX_STD_A:: 05827 __sample(__first, __last, __pop_cat{}, __out, __samp_cat{}, __d, 05828 std::forward<_UniformRandomBitGenerator>(__g)); 05829 } 05830 #endif // C++17 05831 #endif // C++14 05832 05833 _GLIBCXX_END_NAMESPACE_ALGO 05834 } // namespace std 05835 05836 #endif /* _STL_ALGO_H */