Lines Matching refs:__first
852 all_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
854 for (; __first != __last; ++__first)
855 if (!__pred(*__first))
866 any_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
868 for (; __first != __last; ++__first)
869 if (__pred(*__first))
880 none_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
882 for (; __first != __last; ++__first)
883 if (__pred(*__first))
893 for_each(_InputIterator __first, _InputIterator __last, _Function __f)
895 for (; __first != __last; ++__first)
896 __f(*__first);
906 for_each_n(_InputIterator __first, _Size __orig_n, _Function __f)
912 __f(*__first);
913 ++__first;
916 return __first;
926 find(_InputIterator __first, _InputIterator __last, const _Tp& __value_)
928 for (; __first != __last; ++__first)
929 if (*__first == __value_)
931 return __first;
940 find_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
942 for (; __first != __last; ++__first)
943 if (__pred(*__first))
945 return __first;
954 find_if_not(_InputIterator __first, _InputIterator __last, _Predicate __pred)
956 for (; __first != __last; ++__first)
957 if (!__pred(*__first))
959 return __first;
997 if (!__pred(*__m1, *__m2)) // mismatch, restart with a new __first
1154 adjacent_find(_ForwardIterator __first, _ForwardIterator __last, _BinaryPredicate __pred)
1156 if (__first != __last)
1158 _ForwardIterator __i = __first;
1161 if (__pred(*__first, *__i))
1162 return __first;
1163 __first = __i;
1173 adjacent_find(_ForwardIterator __first, _ForwardIterator __last)
1176 return _VSTD::adjacent_find(__first, __last, __equal_to<__v>());
1185 count(_InputIterator __first, _InputIterator __last, const _Tp& __value_)
1188 for (; __first != __last; ++__first)
1189 if (*__first == __value_)
1200 count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
1203 for (; __first != __last; ++__first)
1204 if (__pred(*__first))
1544 __search_n(_ForwardIterator __first, _ForwardIterator __last,
1548 return __first;
1554 if (__first == __last) // return __last if no element matches __value_
1556 if (__pred(*__first, __value_))
1558 ++__first;
1560 // *__first matches __value_, now match elements after here
1561 _ForwardIterator __m = __first;
1565 …if (++__c == __count) // If pattern exhausted, __first is the answer (works for 1 element pattern)
1566 return __first;
1569 if (!__pred(*__m, __value_)) // if there is a mismatch, restart with a new __first
1571 __first = __m;
1572 ++__first;
1581 __search_n(_RandomAccessIterator __first, _RandomAccessIterator __last,
1585 return __first;
1586 _Size __len = static_cast<_Size>(__last - __first);
1595 if (__first >= __s) // return __last if no element matches __value_
1597 if (__pred(*__first, __value_))
1599 ++__first;
1601 // *__first matches __value_, now match elements after here
1602 _RandomAccessIterator __m = __first;
1606 …if (++__c == __count) // If pattern exhausted, __first is the answer (works for 1 element pattern)
1607 return __first;
1609 if (!__pred(*__m, __value_)) // if there is a mismatch, restart with a new __first
1611 __first = __m;
1612 ++__first;
1623 search_n(_ForwardIterator __first, _ForwardIterator __last,
1627 (__first, __last, _VSTD::__convert_to_integral(__count), __value_, __pred,
1635 search_n(_ForwardIterator __first, _ForwardIterator __last, _Size __count, const _Tp& __value_)
1638 return _VSTD::search_n(__first, __last, _VSTD::__convert_to_integral(__count),
1694 _OrigIter __rewrap_iter(_OrigIter __first, _UnwrappedIter __result)
1696 // Precondition: __result is reachable from __first
1698 return __first + (__result - _VSTD::__unwrap_iter(__first));
1706 __copy_constexpr(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
1708 for (; __first != __last; ++__first, (void) ++__result)
1709 *__result = *__first;
1716 __copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
1718 return _VSTD::__copy_constexpr(__first, __last, __result);
1729 __copy(_Tp* __first, _Tp* __last, _Up* __result)
1731 const size_t __n = static_cast<size_t>(__last - __first);
1733 _VSTD::memmove(__result, __first, __n * sizeof(_Up));
1740 copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
1743 return _VSTD::__copy_constexpr(__first, __last, __result);
1746 _VSTD::__copy(_VSTD::__unwrap_iter(__first),
1757 __copy_backward_constexpr(_BidirectionalIterator __first, _BidirectionalIterator __last, _OutputIte…
1759 while (__first != __last)
1767 __copy_backward(_BidirectionalIterator __first, _BidirectionalIterator __last, _OutputIterator __re…
1769 return _VSTD::__copy_backward_constexpr(__first, __last, __result);
1780 __copy_backward(_Tp* __first, _Tp* __last, _Up* __result)
1782 const size_t __n = static_cast<size_t>(__last - __first);
1786 _VSTD::memmove(__result, __first, __n * sizeof(_Up));
1794 copy_backward(_BidirectionalIterator1 __first, _BidirectionalIterator1 __last,
1798 return _VSTD::__copy_backward_constexpr(__first, __last, __result);
1801 _VSTD::__copy_backward(_VSTD::__unwrap_iter(__first),
1812 copy_if(_InputIterator __first, _InputIterator __last,
1815 for (; __first != __last; ++__first)
1817 if (__pred(*__first))
1819 *__result = *__first;
1836 copy_n(_InputIterator __first, _Size __orig_n, _OutputIterator __result)
1842 *__result = *__first;
1846 ++__first;
1847 *__result = *__first;
1861 copy_n(_InputIterator __first, _Size __orig_n, _OutputIterator __result)
1865 return _VSTD::copy(__first, __first + __n, __result);
1873 __move_constexpr(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
1875 for (; __first != __last; ++__first, (void) ++__result)
1876 *__result = _VSTD::move(*__first);
1883 __move(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
1885 return _VSTD::__move_constexpr(__first, __last, __result);
1896 __move(_Tp* __first, _Tp* __last, _Up* __result)
1898 const size_t __n = static_cast<size_t>(__last - __first);
1900 _VSTD::memmove(__result, __first, __n * sizeof(_Up));
1907 move(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
1910 return _VSTD::__move_constexpr(__first, __last, __result);
1913 _VSTD::__move(_VSTD::__unwrap_iter(__first),
1924 __move_backward_constexpr(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
1926 while (__first != __last)
1934 __move_backward(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
1936 return _VSTD::__move_backward_constexpr(__first, __last, __result);
1947 __move_backward(_Tp* __first, _Tp* __last, _Up* __result)
1949 const size_t __n = static_cast<size_t>(__last - __first);
1953 _VSTD::memmove(__result, __first, __n * sizeof(_Up));
1961 move_backward(_BidirectionalIterator1 __first, _BidirectionalIterator1 __last,
1965 return _VSTD::__move_backward_constexpr(__first, __last, __result);
1968 _VSTD::__move_backward(_VSTD::__unwrap_iter(__first),
1983 transform(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _UnaryOperation …
1985 for (; __first != __last; ++__first, (void) ++__result)
1986 *__result = __op(*__first);
2006 replace(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __old_value, const _Tp& __new…
2008 for (; __first != __last; ++__first)
2009 if (*__first == __old_value)
2010 *__first = __new_value;
2018 replace_if(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, const _Tp& __new_v…
2020 for (; __first != __last; ++__first)
2021 if (__pred(*__first))
2022 *__first = __new_value;
2030 replace_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result,
2033 for (; __first != __last; ++__first, (void) ++__result)
2034 if (*__first == __old_value)
2037 *__result = *__first;
2046 replace_copy_if(_InputIterator __first, _InputIterator __last, _OutputIterator __result,
2049 for (; __first != __last; ++__first, (void) ++__result)
2050 if (__pred(*__first))
2053 *__result = *__first;
2062 __fill_n(_OutputIterator __first, _Size __n, const _Tp& __value_)
2064 for (; __n > 0; ++__first, (void) --__n)
2065 *__first = __value_;
2066 return __first;
2072 fill_n(_OutputIterator __first, _Size __n, const _Tp& __value_)
2074 return _VSTD::__fill_n(__first, _VSTD::__convert_to_integral(__n), __value_);
2082 __fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, forward_iterator_tag)
2084 for (; __first != __last; ++__first)
2085 *__first = __value_;
2091 __fill(_RandomAccessIterator __first, _RandomAccessIterator __last, const _Tp& __value_, random_acc…
2093 _VSTD::fill_n(__first, __last - __first, __value_);
2099 fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)
2101 …_VSTD::__fill(__first, __last, __value_, typename iterator_traits<_ForwardIterator>::iterator_cate…
2109 generate(_ForwardIterator __first, _ForwardIterator __last, _Generator __gen)
2111 for (; __first != __last; ++__first)
2112 *__first = __gen();
2120 generate_n(_OutputIterator __first, _Size __orig_n, _Generator __gen)
2124 for (; __n > 0; ++__first, (void) --__n)
2125 *__first = __gen();
2126 return __first;
2133 remove(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)
2135 __first = _VSTD::find(__first, __last, __value_);
2136 if (__first != __last)
2138 _ForwardIterator __i = __first;
2143 *__first = _VSTD::move(*__i);
2144 ++__first;
2148 return __first;
2155 remove_if(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
2157 __first = _VSTD::find_if<_ForwardIterator, typename add_lvalue_reference<_Predicate>::type>
2158 (__first, __last, __pred);
2159 if (__first != __last)
2161 _ForwardIterator __i = __first;
2166 *__first = _VSTD::move(*__i);
2167 ++__first;
2171 return __first;
2179 remove_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result, const _Tp& __v…
2181 for (; __first != __last; ++__first)
2183 if (!(*__first == __value_))
2185 *__result = *__first;
2197 remove_copy_if(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _Predicate …
2199 for (; __first != __last; ++__first)
2201 if (!__pred(*__first))
2203 *__result = *__first;
2214 unique(_ForwardIterator __first, _ForwardIterator __last, _BinaryPredicate __pred)
2216 …__first = _VSTD::adjacent_find<_ForwardIterator, typename add_lvalue_reference<_BinaryPredicate>::…
2217 (__first, __last, __pred);
2218 if (__first != __last)
2222 _ForwardIterator __i = __first;
2224 if (!__pred(*__first, *__i))
2225 *++__first = _VSTD::move(*__i);
2226 ++__first;
2228 return __first;
2235 unique(_ForwardIterator __first, _ForwardIterator __last)
2238 return _VSTD::unique(__first, __last, __equal_to<__v>());
2245 __unique_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _BinaryPredi…
2248 if (__first != __last)
2250 typename iterator_traits<_InputIterator>::value_type __t(*__first);
2253 while (++__first != __last)
2255 if (!__pred(__t, *__first))
2257 __t = *__first;
2268 __unique_copy(_ForwardIterator __first, _ForwardIterator __last, _OutputIterator __result, _BinaryP…
2271 if (__first != __last)
2273 _ForwardIterator __i = __first;
2276 while (++__first != __last)
2278 if (!__pred(*__i, *__first))
2280 *__result = *__first;
2282 __i = __first;
2291 __unique_copy(_InputIterator __first, _InputIterator __last, _ForwardIterator __result, _BinaryPred…
2294 if (__first != __last)
2296 *__result = *__first;
2297 while (++__first != __last)
2298 if (!__pred(*__result, *__first))
2299 *++__result = *__first;
2308 unique_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _BinaryPredica…
2311 (__first, __last, __result, __pred,
2319 unique_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
2322 return _VSTD::unique_copy(__first, __last, __result, __equal_to<__v>());
2330 __reverse(_BidirectionalIterator __first, _BidirectionalIterator __last, bidirectional_iterator_tag)
2332 while (__first != __last)
2334 if (__first == --__last)
2336 _VSTD::iter_swap(__first, __last);
2337 ++__first;
2344 __reverse(_RandomAccessIterator __first, _RandomAccessIterator __last, random_access_iterator_tag)
2346 if (__first != __last)
2347 for (; __first < --__last; ++__first)
2348 _VSTD::iter_swap(__first, __last);
2354 reverse(_BidirectionalIterator __first, _BidirectionalIterator __last)
2356 …_VSTD::__reverse(__first, __last, typename iterator_traits<_BidirectionalIterator>::iterator_categ…
2364 reverse_copy(_BidirectionalIterator __first, _BidirectionalIterator __last, _OutputIterator __resul…
2366 for (; __first != __last; ++__result)
2375 __rotate_left(_ForwardIterator __first, _ForwardIterator __last)
2378 value_type __tmp = _VSTD::move(*__first);
2379 _ForwardIterator __lm1 = _VSTD::move(_VSTD::next(__first), __last, __first);
2386 __rotate_right(_BidirectionalIterator __first, _BidirectionalIterator __last)
2391 _BidirectionalIterator __fp1 = _VSTD::move_backward(__first, __lm1, __last);
2392 *__first = _VSTD::move(__tmp);
2398 __rotate_forward(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last)
2403 swap(*__first, *__i);
2404 ++__first;
2407 if (__first == __middle)
2410 _ForwardIterator __r = __first;
2411 if (__first != __middle)
2416 swap(*__first, *__i);
2417 ++__first;
2420 if (__first == __middle)
2424 else if (__first == __middle)
2447 __rotate_gcd(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator _…
2452 const difference_type __m1 = __middle - __first;
2456 _VSTD::swap_ranges(__first, __middle, __middle);
2460 for (_RandomAccessIterator __p = __first + __g; __p != __first;)
2473 __p2 = __first + (__m1 - __d);
2477 return __first + __m2;
2483 __rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last,
2489 if (_VSTD::next(__first) == __middle)
2490 return _VSTD::__rotate_left(__first, __last);
2492 return _VSTD::__rotate_forward(__first, __middle, __last);
2498 __rotate(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __…
2504 if (_VSTD::next(__first) == __middle)
2505 return _VSTD::__rotate_left(__first, __last);
2507 return _VSTD::__rotate_right(__first, __last);
2509 return _VSTD::__rotate_forward(__first, __middle, __last);
2515 __rotate(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __las…
2521 if (_VSTD::next(__first) == __middle)
2522 return _VSTD::__rotate_left(__first, __last);
2524 return _VSTD::__rotate_right(__first, __last);
2525 return _VSTD::__rotate_gcd(__first, __middle, __last);
2527 return _VSTD::__rotate_forward(__first, __middle, __last);
2533 rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last)
2535 if (__first == __middle)
2538 return __first;
2539 return _VSTD::__rotate(__first, __middle, __last,
2548 rotate_copy(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last, _OutputIt…
2550 return _VSTD::copy(__first, __middle, _VSTD::copy(__middle, __last, __result));
2559 min_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
2563 if (__first != __last)
2565 _ForwardIterator __i = __first;
2567 if (__comp(*__i, *__first))
2568 __first = __i;
2570 return __first;
2577 min_element(_ForwardIterator __first, _ForwardIterator __last)
2579 return _VSTD::min_element(__first, __last,
2631 max_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
2635 if (__first != __last)
2637 _ForwardIterator __i = __first;
2639 if (__comp(*__first, *__i))
2640 __first = __i;
2642 return __first;
2650 max_element(_ForwardIterator __first, _ForwardIterator __last)
2652 return _VSTD::max_element(__first, __last,
2726 minmax_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
2730 pair<_ForwardIterator, _ForwardIterator> __result(__first, __first);
2731 if (__first != __last)
2733 if (++__first != __last)
2735 if (__comp(*__first, *__result.first))
2736 __result.first = __first;
2738 __result.second = __first;
2739 while (++__first != __last)
2741 _ForwardIterator __i = __first;
2742 if (++__first == __last)
2752 if (__comp(*__first, *__i))
2754 if (__comp(*__first, *__result.first))
2755 __result.first = __first;
2763 if (!__comp(*__first, *__result.second))
2764 __result.second = __first;
2777 minmax_element(_ForwardIterator __first, _ForwardIterator __last)
2779 return _VSTD::minmax_element(__first, __last,
2813 _Iter __first = __t.begin();
2815 pair<_Tp, _Tp> __result(*__first, *__first);
2817 ++__first;
2820 if (__comp(*__first, __result.first))
2821 __result.first = *__first;
2823 __result.second = *__first;
2824 ++__first;
2827 while (__first != __last)
2829 _Tp __prev = *__first++;
2830 if (__comp(*__first, __prev)) {
2831 if ( __comp(*__first, __result.first)) __result.first = *__first;
2836 if (!__comp(*__first, __result.second)) __result.second = *__first;
2839 __first++;
3142 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
3147 difference_type __d = __last - __first;
3152 for (--__last, (void) --__d; __first < __last; ++__first, (void) --__d)
3156 swap(*__first, *(__first + __i));
3163 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
3171 difference_type __d = __last - __first;
3174 for (--__last; __first < __last; ++__first, (void) --__d)
3178 swap(*__first, *(__first + __i));
3187 _SampleIterator __sample(_PopulationIterator __first,
3194 for (; __first != __last && __k < __n; ++__first, (void) ++__k)
3195 __output_iter[__k] = *__first;
3197 for (; __first != __last; ++__first, (void) ++__k) {
3200 __output_iter[__r] = *__first;
3208 _SampleIterator __sample(_PopulationIterator __first,
3213 _Distance __unsampled_sz = _VSTD::distance(__first, __last);
3214 for (__n = _VSTD::min(__n, __unsampled_sz); __n != 0; ++__first) {
3217 *__output_iter++ = *__first;
3227 _SampleIterator __sample(_PopulationIterator __first,
3240 __first, __last, __output_iter, _CommonType(__n),
3248 _SampleIterator sample(_PopulationIterator __first,
3251 return _VSTD::__sample(__first, __last, __output_iter, __n, __g);
3256 void shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
3262 difference_type __d = __last - __first;
3266 for (--__last, (void) --__d; __first < __last; ++__first, (void) --__d)
3270 swap(*__first, *(__first + __i));
3282 shift_left(_ForwardIterator __first, _ForwardIterator __last,
3289 _ForwardIterator __m = __first;
3291 if (__n >= __last - __first) {
3292 return __first;
3298 return __first;
3303 return _VSTD::move(__m, __last, __first);
3309 shift_right(_ForwardIterator __first, _ForwardIterator __last,
3313 return __first;
3317 decltype(__n) __d = __last - __first;
3321 _ForwardIterator __m = __first + (__d - __n);
3322 return _VSTD::move_backward(__first, __m, __last);
3326 if (__m == __first) {
3331 return _VSTD::move_backward(__first, __m, __last);
3333 _ForwardIterator __ret = __first;
3341 // We have an __n-element scratch space from __first to __ret.
3343 // We're essentially doing swap_ranges(__first, __ret, __trail, __lead)
3347 auto __trail = __first;
3351 _VSTD::move(__first, __trail, __ret);
3358 _ForwardIterator __mid = __first;
3362 _VSTD::move(__first, __mid, __trail);
3370 __mid = __first;
3382 is_partitioned(_InputIterator __first, _InputIterator __last, _Predicate __pred)
3384 for (; __first != __last; ++__first)
3385 if (!__pred(*__first))
3387 if ( __first == __last )
3389 ++__first;
3390 for (; __first != __last; ++__first)
3391 if (__pred(*__first))
3400 __partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, forward_iterator_…
3404 if (__first == __last)
3405 return __first;
3406 if (!__pred(*__first))
3408 ++__first;
3410 for (_ForwardIterator __p = __first; ++__p != __last;)
3414 swap(*__first, *__p);
3415 ++__first;
3418 return __first;
3423 __partition(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred,
3430 if (__first == __last)
3431 return __first;
3432 if (!__pred(*__first))
3434 ++__first;
3438 if (__first == --__last)
3439 return __first;
3441 swap(*__first, *__last);
3442 ++__first;
3449 partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
3452 … (__first, __last, __pred, typename iterator_traits<_ForwardIterator>::iterator_category());
3460 partition_copy(_InputIterator __first, _InputIterator __last,
3464 for (; __first != __last; ++__first)
3466 if (__pred(*__first))
3468 *__out_true = *__first;
3473 *__out_false = *__first;
3484 partition_point(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
3487 difference_type __len = _VSTD::distance(__first, __last);
3491 _ForwardIterator __m = __first;
3495 __first = ++__m;
3501 return __first;
3508 __stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred,
3511 // *__first is known to be false
3514 return __first;
3517 _ForwardIterator __m = __first;
3520 swap(*__first, *__m);
3523 return __first;
3531 // Update __first to always point to the end of the trues
3533 ::new ((void*)__t) value_type(_VSTD::move(*__first));
3536 _ForwardIterator __i = __first;
3541 *__first = _VSTD::move(*__i);
3542 ++__first;
3552 // Move falses back into range, but don't mess up __first which points to first false
3553 __i = __first;
3557 return __first;
3561 _ForwardIterator __m = __first;
3564 // recurse on [__first, __m), *__first know to be false
3568 …_ForwardIterator __first_false = _VSTD::__stable_partition<_PredRef>(__first, __m, __pred, __len2,…
3600 __stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred,
3604 // Either prove all true and return __first or point to first false
3607 if (__first == __last)
3608 return __first;
3609 if (!__pred(*__first))
3611 ++__first;
3613 // We now have a reduced range [__first, __last)
3614 // *__first is known to be false
3617 difference_type __len = _VSTD::distance(__first, __last);
3626 (__first, __last, __pred, __len, __p, forward_iterator_tag());
3631 __stable_partition(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred,
3634 // *__first is known to be false
3639 swap(*__first, *__last);
3644 _BidirectionalIterator __m = __first;
3647 swap(*__first, *__m);
3652 swap(*__first, *__m);
3661 // Update __first to always point to the end of the trues
3663 ::new ((void*)__t) value_type(_VSTD::move(*__first));
3666 _BidirectionalIterator __i = __first;
3671 *__first = _VSTD::move(*__i);
3672 ++__first;
3682 *__first = _VSTD::move(*__i);
3683 __i = ++__first;
3685 // Move falses back into range, but don't mess up __first which points to first false
3689 return __first;
3693 _BidirectionalIterator __m = __first;
3696 …// recurse on [__first, __m-1], except reduce __m-1 until *(__m-1) is true, *__first know to be fa…
3700 _BidirectionalIterator __first_false = __first;
3704 if (__m1 == __first)
3711 …__first_false = _VSTD::__stable_partition<_PredRef>(__first, __m1, __pred, __len_half, __p, __bit);
3739 __stable_partition(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred,
3745 // Either prove all true and return __first or point to first false
3748 if (__first == __last)
3749 return __first;
3750 if (!__pred(*__first))
3752 ++__first;
3754 // __first points to first false, everything prior to __first is already set.
3755 // Either prove [__first, __last) is all false and return __first, or point __last to last true
3758 if (__first == --__last)
3759 return __first;
3761 // We now have a reduced range [__first, __last]
3762 // *__first is known to be false
3765 difference_type __len = _VSTD::distance(__first, __last) + 1;
3774 (__first, __last, __pred, __len, __p, bidirectional_iterator_tag());
3780 stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
3783 … (__first, __last, __pred, typename iterator_traits<_ForwardIterator>::iterator_category());
3790 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
3792 if (__first != __last)
3794 _ForwardIterator __i = __first;
3797 if (__comp(*__i, *__first))
3799 __first = __i;
3809 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last)
3811 …return _VSTD::is_sorted_until(__first, __last, __less<typename iterator_traits<_ForwardIterator>::…
3820 is_sorted(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
3822 return _VSTD::is_sorted_until(__first, __last, __comp) == __last;
3829 is_sorted(_ForwardIterator __first, _ForwardIterator __last)
3831 …return _VSTD::is_sorted(__first, __last, __less<typename iterator_traits<_ForwardIterator>::value_…
3934 __selection_sort(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
3937 for (--__lm1; __first != __lm1; ++__first)
3941 (__first, __last, __comp);
3942 if (__i != __first)
3943 swap(*__first, *__i);
3949 __insertion_sort(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
3952 if (__first != __last)
3954 _BidirectionalIterator __i = __first;
3959 for (_BidirectionalIterator __k = __i; __k != __first && __comp(__t, *--__k); --__j)
3968 __insertion_sort_3(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
3971 _RandomAccessIterator __j = __first+2;
3972 _VSTD::__sort3<_Compare>(__first, __first+1, __j, __comp);
3984 } while (__j != __first && __comp(__t, *--__k));
3993 __insertion_sort_incomplete(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare _…
3995 switch (__last - __first)
4001 if (__comp(*--__last, *__first))
4002 swap(*__first, *__last);
4005 _VSTD::__sort3<_Compare>(__first, __first+1, --__last, __comp);
4008 _VSTD::__sort4<_Compare>(__first, __first+1, __first+2, --__last, __comp);
4011 _VSTD::__sort5<_Compare>(__first, __first+1, __first+2, __first+3, --__last, __comp);
4015 _RandomAccessIterator __j = __first+2;
4016 _VSTD::__sort3<_Compare>(__first, __first+1, __j, __comp);
4030 } while (__j != __first && __comp(__t, *--__k));
4077 __sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4086 difference_type __len = __last - __first;
4093 if (__comp(*--__last, *__first))
4094 swap(*__first, *__last);
4097 _VSTD::__sort3<_Compare>(__first, __first+1, --__last, __comp);
4100 _VSTD::__sort4<_Compare>(__first, __first+1, __first+2, --__last, __comp);
4103 _VSTD::__sort5<_Compare>(__first, __first+1, __first+2, __first+3, --__last, __comp);
4108 _VSTD::__insertion_sort_3<_Compare>(__first, __last, __comp);
4112 _RandomAccessIterator __m = __first;
4123 … __n_swaps = _VSTD::__sort5<_Compare>(__first, __first + __delta, __m, __m+__delta, __lm1, __comp);
4129 __n_swaps = _VSTD::__sort3<_Compare>(__first, __m, __lm1, __comp);
4133 // partition [__first, __m) < *__m and *__m <= [__m, __last)
4135 _RandomAccessIterator __i = __first;
4140 if (!__comp(*__i, *__m)) // if *__first == *__m
4142 // *__first == *__m, *__first doesn't go in first part
4148 // *__first == *__m, *__m <= all other elements
4149 // Parition instead into [__first, __i) == *__first and *__first < [__i, __last)
4150 ++__i; // __first + 1
4152 if (!__comp(*__first, *--__j)) // we need a guard if *__first == *(__last-1)
4157 return; // [__first, __last) all equivalent elements
4158 if (__comp(*__first, *__i))
4168 // [__first, __i) == *__first and *__first < [__j, __last) and __j == __last - 1
4173 while (!__comp(*__first, *__i))
4175 while (__comp(*__first, *--__j))
4183 // [__first, __i) == *__first and *__first < [__i, __last)
4186 __first = __i;
4224 // [__first, __i) < *__m and *__m <= [__i, __last)
4230 // [__first, __i) < *__i and *__i <= [__i+1, __last)
4234 bool __fs = _VSTD::__insertion_sort_incomplete<_Compare>(__first, __i, __comp);
4246 __first = ++__i;
4252 if (__i - __first < __last - __i)
4254 _VSTD::__sort<_Compare>(__first, __i, __comp);
4256 __first = ++__i;
4261 // _VSTD::__sort<_Compare>(__first, __i, __comp);
4270 __sort(_Tp** __first, _Tp** __last, __less<_Tp*>&)
4273 _VSTD::__sort<__less<uintptr_t>&, uintptr_t*>((uintptr_t*)__first, (uintptr_t*)__last, __comp);
4314 __lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __co…
4317 difference_type __len = _VSTD::distance(__first, __last);
4321 _ForwardIterator __m = __first;
4325 __first = ++__m;
4331 return __first;
4338 lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4341 return _VSTD::__lower_bound<_Comp_ref>(__first, __last, __value_, __comp);
4348 lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)
4350 return _VSTD::lower_bound(__first, __last, __value_,
4358 __upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __co…
4361 difference_type __len = _VSTD::distance(__first, __last);
4365 _ForwardIterator __m = __first;
4371 __first = ++__m;
4375 return __first;
4382 upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4385 return _VSTD::__upper_bound<_Comp_ref>(__first, __last, __value_, __comp);
4392 upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)
4394 return _VSTD::upper_bound(__first, __last, __value_,
4402 __equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __co…
4405 difference_type __len = _VSTD::distance(__first, __last);
4409 _ForwardIterator __m = __first;
4413 __first = ++__m;
4426 _VSTD::__lower_bound<_Compare>(__first, __m, __value_, __comp),
4431 return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
4438 equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4441 return _VSTD::__equal_range<_Comp_ref>(__first, __last, __value_, __comp);
4448 equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)
4450 return _VSTD::equal_range(__first, __last, __value_,
4459 __binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __…
4461 __first = _VSTD::__lower_bound<_Compare>(__first, __last, __value_, __comp);
4462 return __first != __last && !__comp(__value_, *__first);
4469 binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __co…
4472 return _VSTD::__binary_search<_Comp_ref>(__first, __last, __value_, __comp);
4479 binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)
4481 return _VSTD::binary_search(__first, __last, __value_,
4564 __buffered_inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _Bidirect…
4575 …for (_BidirectionalIterator __i = __first; __i != __middle; __d.template __incr<value_type>(), (vo…
4577 _VSTD::__half_inplace_merge<_Compare>(__buff, __p, __middle, __last, __first, __comp);
4588 _RBi(__middle), _RBi(__first),
4595 __inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIter…
4608 (__first, __middle, __last, __comp, __len1, __len2, __buff);
4609 … // shrink [__first, __middle) as much as possible (with no moves), returning if it shrinks to 0
4610 for (; true; ++__first, (void) --__len1)
4614 if (__comp(*__middle, *__first))
4617 // __first < __middle < __last
4618 // *__first > *__middle
4619 // partition [__first, __m1) [__m1, __middle) [__middle, __m2) [__m2, __last) such that
4621 // [__first, __m1) <= [__middle, __m2)
4625 _BidirectionalIterator __m1; // "median" of [__first, __middle)
4627 difference_type __len11; // distance(__first, __m1)
4635 __m1 = _VSTD::__upper_bound<_Compare>(__first, __middle, *__m2, __comp);
4636 __len11 = _VSTD::distance(__first, __m1);
4642 // It is known *__first > *__middle
4643 swap(*__first, *__middle);
4648 __m1 = __first;
4655 // [__first, __m1) [__m1, __middle) [__middle, __m2) [__m2, __last)
4662 …_VSTD::__inplace_merge<_Compare>(__first, __m1, __middle, __comp, __len11, __len21, __buff, __buff…
4664 __first = __middle;
4672 // _VSTD::__inplace_merge<_Compare>(__first, __m1, __middle, __comp, __len11, __len21, __b…
4684 inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterat…
4689 difference_type __len1 = _VSTD::distance(__first, __middle);
4695 return _VSTD::__inplace_merge<_Comp_ref>(__first, __middle, __last, __comp, __len1, __len2,
4702 inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterat…
4704 _VSTD::inplace_merge(__first, __middle, __last,
4781 __stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
4839 __stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
4851 if (__comp(*--__last, *__first))
4852 swap(*__first, *__last);
4857 _VSTD::__insertion_sort<_Compare>(__first, __last, __comp);
4861 _RandomAccessIterator __m = __first + __l2;
4866 _VSTD::__stable_sort_move<_Compare>(__first, __m, __comp, __l2, __buff);
4870 …merge_move_assign<_Compare>(__buff, __buff + __l2, __buff + __l2, __buff + __len, __first, __comp);
4875 // __first, __comp);
4878 _VSTD::__stable_sort<_Compare>(__first, __m, __comp, __l2, __buff, __buff_size);
4880 …_VSTD::__inplace_merge<_Compare>(__first, __m, __last, __comp, __l2, __len - __l2, __buff, __buff_…
4886 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4890 difference_type __len = __last - __first;
4899 _VSTD::__stable_sort<_Comp_ref>(__first, __last, __comp, __len, __buf.first, __buf.second);
4905 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
4907 …_VSTD::stable_sort(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_…
4914 is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4917 difference_type __len = __last - __first;
4920 _RandomAccessIterator __pp = __first;
4923 _RandomAccessIterator __cp = __first + __c;
4943 is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last)
4945 …return _VSTD::is_heap_until(__first, __last, __less<typename iterator_traits<_RandomAccessIterator…
4954 is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4956 return _VSTD::is_heap_until(__first, __last, __comp) == __last;
4963 is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
4965 …return _VSTD::is_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::val…
4972 __sift_up(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
4979 _RandomAccessIterator __ptr = __first + __len;
4990 __ptr = __first + __len;
5000 push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
5003 _VSTD::__sift_up<_Comp_ref>(__first, __last, __comp, __last - __first);
5009 push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
5011 …_VSTD::push_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_ty…
5018 __sift_down(_RandomAccessIterator __first, _RandomAccessIterator /*__last*/,
5027 difference_type __child = __start - __first;
5033 _RandomAccessIterator __child_i = __first + __child;
5058 __child_i = __first + __child;
5074 __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
5079 swap(*__first, *--__last);
5080 _VSTD::__sift_down<_Compare>(__first, __last, __comp, __len - 1, __first);
5087 pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
5090 _VSTD::__pop_heap<_Comp_ref>(__first, __last, __comp, __last - __first);
5096 pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
5098 …_VSTD::pop_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_typ…
5105 __make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
5108 difference_type __n = __last - __first;
5114 _VSTD::__sift_down<_Compare>(__first, __last, __comp, __n, __first + __start);
5122 make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
5125 _VSTD::__make_heap<_Comp_ref>(__first, __last, __comp);
5131 make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
5133 …_VSTD::make_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_ty…
5140 __sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
5143 for (difference_type __n = __last - __first; __n > 1; --__last, (void) --__n)
5144 _VSTD::__pop_heap<_Compare>(__first, __last, __comp, __n);
5150 sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
5153 _VSTD::__sort_heap<_Comp_ref>(__first, __last, __comp);
5159 sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
5161 …_VSTD::sort_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_ty…
5168 __partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator…
5171 _VSTD::__make_heap<_Compare>(__first, __middle, __comp);
5172 typename iterator_traits<_RandomAccessIterator>::difference_type __len = __middle - __first;
5175 if (__comp(*__i, *__first))
5177 swap(*__i, *__first);
5178 _VSTD::__sift_down<_Compare>(__first, __middle, __comp, __len, __first);
5181 _VSTD::__sort_heap<_Compare>(__first, __middle, __comp);
5187 partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator _…
5191 _VSTD::__partial_sort<_Comp_ref>(__first, __middle, __last, __comp);
5197 partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator _…
5199 _VSTD::partial_sort(__first, __middle, __last,
5207 __partial_sort_copy(_InputIterator __first, _InputIterator __last,
5213 for (; __first != __last && __r != __result_last; ++__first, (void) ++__r)
5214 *__r = *__first;
5217 for (; __first != __last; ++__first)
5218 if (__comp(*__first, *__result_first))
5220 *__result_first = *__first;
5231 partial_sort_copy(_InputIterator __first, _InputIterator __last,
5235 …return _VSTD::__partial_sort_copy<_Comp_ref>(__first, __last, __result_first, __result_last, __com…
5241 partial_sort_copy(_InputIterator __first, _InputIterator __last,
5244 return _VSTD::partial_sort_copy(__first, __last, __result_first, __result_last,
5268 __nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __l…
5277 difference_type __len = __last - __first;
5284 if (__comp(*--__last, *__first))
5285 swap(*__first, *__last);
5289 _RandomAccessIterator __m = __first;
5290 _VSTD::__sort3<_Compare>(__first, ++__m, --__last, __comp);
5296 _VSTD::__selection_sort<_Compare>(__first, __last, __comp);
5300 _RandomAccessIterator __m = __first + __len/2;
5302 unsigned __n_swaps = _VSTD::__sort3<_Compare>(__first, __m, --__lm1, __comp);
5304 // partition [__first, __m) < *__m and *__m <= [__m, __last)
5306 _RandomAccessIterator __i = __first;
5311 if (!__comp(*__i, *__m)) // if *__first == *__m
5313 // *__first == *__m, *__first doesn't go in first part
5318 // *__first == *__m, *__m <= all other elements
5319 // Partition instead into [__first, __i) == *__first and *__first < [__i, __last)
5320 ++__i; // __first + 1
5322 if (!__comp(*__first, *--__j)) { // we need a guard if *__first == *(__last-1)
5325 return; // [__first, __last) all equivalent elements
5326 } else if (__comp(*__first, *__i)) {
5335 // [__first, __i) == *__first and *__first < [__j, __last) and __j == __last - 1
5340 while (!__comp(*__first, *__i))
5342 while (__comp(*__first, *--__j))
5350 // [__first, __i) == *__first and *__first < [__i, __last)
5357 __first = __i;
5386 // [__first, __i) < *__m and *__m <= [__i, __last)
5392 // [__first, __i) < *__i and *__i <= [__i+1, __last)
5400 // Check for [__first, __i) already sorted
5401 __j = __m = __first;
5404 // [__first, __i) sorted
5434 // _VSTD::__nth_element<_Compare>(__first, __nth, __i, __comp);
5440 __first = ++__i;
5448 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __las…
5451 _VSTD::__nth_element<_Comp_ref>(__first, __nth, __last, __comp);
5457 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __las…
5459 …_VSTD::nth_element(__first, __nth, __last, __less<typename iterator_traits<_RandomAccessIterator>:…
5467 sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
5471 _VSTD::__partial_sort<_Comp_ref>(__first, __last, __last, _Comp_ref(__comp));
5473 …_VSTD::__sort<_Comp_ref>(_VSTD::__unwrap_iter(__first), _VSTD::__unwrap_iter(__last), _Comp_ref(__…
5480 sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
5482 …_VSTD::sort(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>()…
5763 __next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
5766 if (__first == __last || __first == --__i)
5780 if (__i == __first)
5782 _VSTD::reverse(__first, __last);
5791 next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
5794 return _VSTD::__next_permutation<_Comp_ref>(__first, __last, __comp);
5800 next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last)
5802 return _VSTD::next_permutation(__first, __last,
5810 __prev_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
5813 if (__first == __last || __first == --__i)
5827 if (__i == __first)
5829 _VSTD::reverse(__first, __last);
5838 prev_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
5841 return _VSTD::__prev_permutation<_Comp_ref>(__first, __last, __comp);
5847 prev_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last)
5849 return _VSTD::prev_permutation(__first, __last,