Lines Matching refs:__first
817 all_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
819 for (; __first != __last; ++__first)
820 if (!__pred(*__first))
830 any_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
832 for (; __first != __last; ++__first)
833 if (__pred(*__first))
843 none_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
845 for (; __first != __last; ++__first)
846 if (__pred(*__first))
856 for_each(_InputIterator __first, _InputIterator __last, _Function __f)
858 for (; __first != __last; ++__first)
859 __f(*__first);
869 for_each_n(_InputIterator __first, _Size __orig_n, _Function __f)
875 __f(*__first);
876 ++__first;
879 return __first;
888 find(_InputIterator __first, _InputIterator __last, const _Tp& __value_)
890 for (; __first != __last; ++__first)
891 if (*__first == __value_)
893 return __first;
901 find_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
903 for (; __first != __last; ++__first)
904 if (__pred(*__first))
906 return __first;
914 find_if_not(_InputIterator __first, _InputIterator __last, _Predicate __pred)
916 for (; __first != __last; ++__first)
917 if (!__pred(*__first))
919 return __first;
957 if (!__pred(*__m1, *__m2)) // mismatch, restart with a new __first
1109 adjacent_find(_ForwardIterator __first, _ForwardIterator __last, _BinaryPredicate __pred)
1111 if (__first != __last)
1113 _ForwardIterator __i = __first;
1116 if (__pred(*__first, *__i))
1117 return __first;
1118 __first = __i;
1127 adjacent_find(_ForwardIterator __first, _ForwardIterator __last)
1130 return _VSTD::adjacent_find(__first, __last, __equal_to<__v>());
1138 count(_InputIterator __first, _InputIterator __last, const _Tp& __value_)
1141 for (; __first != __last; ++__first)
1142 if (*__first == __value_)
1152 count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
1155 for (; __first != __last; ++__first)
1156 if (__pred(*__first))
1483 __search_n(_ForwardIterator __first, _ForwardIterator __last,
1487 return __first;
1493 if (__first == __last) // return __last if no element matches __value_
1495 if (__pred(*__first, __value_))
1497 ++__first;
1499 // *__first matches __value_, now match elements after here
1500 _ForwardIterator __m = __first;
1504 …if (++__c == __count) // If pattern exhausted, __first is the answer (works for 1 element pattern)
1505 return __first;
1508 if (!__pred(*__m, __value_)) // if there is a mismatch, restart with a new __first
1510 __first = __m;
1511 ++__first;
1520 __search_n(_RandomAccessIterator __first, _RandomAccessIterator __last,
1524 return __first;
1525 _Size __len = static_cast<_Size>(__last - __first);
1534 if (__first >= __s) // return __last if no element matches __value_
1536 if (__pred(*__first, __value_))
1538 ++__first;
1540 // *__first matches __value_, now match elements after here
1541 _RandomAccessIterator __m = __first;
1545 …if (++__c == __count) // If pattern exhausted, __first is the answer (works for 1 element pattern)
1546 return __first;
1548 if (!__pred(*__m, __value_)) // if there is a mismatch, restart with a new __first
1550 __first = __m;
1551 ++__first;
1561 search_n(_ForwardIterator __first, _ForwardIterator __last,
1565 (__first, __last, __convert_to_integral(__count), __value_, __pred,
1572 search_n(_ForwardIterator __first, _ForwardIterator __last, _Size __count, const _Tp& __value_)
1575 return _VSTD::search_n(__first, __last, __convert_to_integral(__count),
1633 __copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
1635 for (; __first != __last; ++__first, (void) ++__result)
1636 *__result = *__first;
1648 __copy(_Tp* __first, _Tp* __last, _Up* __result)
1650 const size_t __n = static_cast<size_t>(__last - __first);
1652 _VSTD::memmove(__result, __first, __n * sizeof(_Up));
1659 copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
1661 return _VSTD::__copy(__unwrap_iter(__first), __unwrap_iter(__last), __unwrap_iter(__result));
1669 __copy_backward(_BidirectionalIterator __first, _BidirectionalIterator __last, _OutputIterator __re…
1671 while (__first != __last)
1684 __copy_backward(_Tp* __first, _Tp* __last, _Up* __result)
1686 const size_t __n = static_cast<size_t>(__last - __first);
1690 _VSTD::memmove(__result, __first, __n * sizeof(_Up));
1698 copy_backward(_BidirectionalIterator1 __first, _BidirectionalIterator1 __last,
1701 return _VSTD::__copy_backward(__unwrap_iter(__first),
1711 copy_if(_InputIterator __first, _InputIterator __last,
1714 for (; __first != __last; ++__first)
1716 if (__pred(*__first))
1718 *__result = *__first;
1735 copy_n(_InputIterator __first, _Size __orig_n, _OutputIterator __result)
1741 *__result = *__first;
1745 ++__first;
1746 *__result = *__first;
1760 copy_n(_InputIterator __first, _Size __orig_n, _OutputIterator __result)
1764 return _VSTD::copy(__first, __first + __n, __result);
1772 __move(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
1774 for (; __first != __last; ++__first, (void) ++__result)
1775 *__result = _VSTD::move(*__first);
1787 __move(_Tp* __first, _Tp* __last, _Up* __result)
1789 const size_t __n = static_cast<size_t>(__last - __first);
1791 _VSTD::memmove(__result, __first, __n * sizeof(_Up));
1798 move(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
1800 return _VSTD::__move(__unwrap_iter(__first), __unwrap_iter(__last), __unwrap_iter(__result));
1808 __move_backward(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
1810 while (__first != __last)
1823 __move_backward(_Tp* __first, _Tp* __last, _Up* __result)
1825 const size_t __n = static_cast<size_t>(__last - __first);
1829 _VSTD::memmove(__result, __first, __n * sizeof(_Up));
1837 move_backward(_BidirectionalIterator1 __first, _BidirectionalIterator1 __last,
1840 …return _VSTD::__move_backward(__unwrap_iter(__first), __unwrap_iter(__last), __unwrap_iter(__resul…
1852 transform(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _UnaryOperation …
1854 for (; __first != __last; ++__first, (void) ++__result)
1855 *__result = __op(*__first);
1875 replace(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __old_value, const _Tp& __new…
1877 for (; __first != __last; ++__first)
1878 if (*__first == __old_value)
1879 *__first = __new_value;
1887 replace_if(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, const _Tp& __new_v…
1889 for (; __first != __last; ++__first)
1890 if (__pred(*__first))
1891 *__first = __new_value;
1899 replace_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result,
1902 for (; __first != __last; ++__first, (void) ++__result)
1903 if (*__first == __old_value)
1906 *__result = *__first;
1915 replace_copy_if(_InputIterator __first, _InputIterator __last, _OutputIterator __result,
1918 for (; __first != __last; ++__first, (void) ++__result)
1919 if (__pred(*__first))
1922 *__result = *__first;
1931 __fill_n(_OutputIterator __first, _Size __n, const _Tp& __value_)
1933 for (; __n > 0; ++__first, (void) --__n)
1934 *__first = __value_;
1935 return __first;
1941 fill_n(_OutputIterator __first, _Size __n, const _Tp& __value_)
1943 return _VSTD::__fill_n(__first, __convert_to_integral(__n), __value_);
1951 __fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, forward_iterator_tag)
1953 for (; __first != __last; ++__first)
1954 *__first = __value_;
1960 __fill(_RandomAccessIterator __first, _RandomAccessIterator __last, const _Tp& __value_, random_acc…
1962 _VSTD::fill_n(__first, __last - __first, __value_);
1968 fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)
1970 …_VSTD::__fill(__first, __last, __value_, typename iterator_traits<_ForwardIterator>::iterator_cate…
1978 generate(_ForwardIterator __first, _ForwardIterator __last, _Generator __gen)
1980 for (; __first != __last; ++__first)
1981 *__first = __gen();
1989 generate_n(_OutputIterator __first, _Size __orig_n, _Generator __gen)
1993 for (; __n > 0; ++__first, (void) --__n)
1994 *__first = __gen();
1995 return __first;
2002 remove(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)
2004 __first = _VSTD::find(__first, __last, __value_);
2005 if (__first != __last)
2007 _ForwardIterator __i = __first;
2012 *__first = _VSTD::move(*__i);
2013 ++__first;
2017 return __first;
2024 remove_if(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
2026 __first = _VSTD::find_if<_ForwardIterator, typename add_lvalue_reference<_Predicate>::type>
2027 (__first, __last, __pred);
2028 if (__first != __last)
2030 _ForwardIterator __i = __first;
2035 *__first = _VSTD::move(*__i);
2036 ++__first;
2040 return __first;
2048 remove_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result, const _Tp& __v…
2050 for (; __first != __last; ++__first)
2052 if (!(*__first == __value_))
2054 *__result = *__first;
2066 remove_copy_if(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _Predicate …
2068 for (; __first != __last; ++__first)
2070 if (!__pred(*__first))
2072 *__result = *__first;
2083 unique(_ForwardIterator __first, _ForwardIterator __last, _BinaryPredicate __pred)
2085 …__first = _VSTD::adjacent_find<_ForwardIterator, typename add_lvalue_reference<_BinaryPredicate>::…
2086 (__first, __last, __pred);
2087 if (__first != __last)
2091 _ForwardIterator __i = __first;
2093 if (!__pred(*__first, *__i))
2094 *++__first = _VSTD::move(*__i);
2095 ++__first;
2097 return __first;
2103 unique(_ForwardIterator __first, _ForwardIterator __last)
2106 return _VSTD::unique(__first, __last, __equal_to<__v>());
2113 __unique_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _BinaryPredi…
2116 if (__first != __last)
2118 typename iterator_traits<_InputIterator>::value_type __t(*__first);
2121 while (++__first != __last)
2123 if (!__pred(__t, *__first))
2125 __t = *__first;
2136 __unique_copy(_ForwardIterator __first, _ForwardIterator __last, _OutputIterator __result, _BinaryP…
2139 if (__first != __last)
2141 _ForwardIterator __i = __first;
2144 while (++__first != __last)
2146 if (!__pred(*__i, *__first))
2148 *__result = *__first;
2150 __i = __first;
2159 __unique_copy(_InputIterator __first, _InputIterator __last, _ForwardIterator __result, _BinaryPred…
2162 if (__first != __last)
2164 *__result = *__first;
2165 while (++__first != __last)
2166 if (!__pred(*__result, *__first))
2167 *++__result = *__first;
2176 unique_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _BinaryPredica…
2179 (__first, __last, __result, __pred,
2187 unique_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
2190 return _VSTD::unique_copy(__first, __last, __result, __equal_to<__v>());
2198 __reverse(_BidirectionalIterator __first, _BidirectionalIterator __last, bidirectional_iterator_tag)
2200 while (__first != __last)
2202 if (__first == --__last)
2204 _VSTD::iter_swap(__first, __last);
2205 ++__first;
2212 __reverse(_RandomAccessIterator __first, _RandomAccessIterator __last, random_access_iterator_tag)
2214 if (__first != __last)
2215 for (; __first < --__last; ++__first)
2216 _VSTD::iter_swap(__first, __last);
2222 reverse(_BidirectionalIterator __first, _BidirectionalIterator __last)
2224 …_VSTD::__reverse(__first, __last, typename iterator_traits<_BidirectionalIterator>::iterator_categ…
2232 reverse_copy(_BidirectionalIterator __first, _BidirectionalIterator __last, _OutputIterator __resul…
2234 for (; __first != __last; ++__result)
2243 __rotate_left(_ForwardIterator __first, _ForwardIterator __last)
2246 value_type __tmp = _VSTD::move(*__first);
2247 _ForwardIterator __lm1 = _VSTD::move(_VSTD::next(__first), __last, __first);
2254 __rotate_right(_BidirectionalIterator __first, _BidirectionalIterator __last)
2259 _BidirectionalIterator __fp1 = _VSTD::move_backward(__first, __lm1, __last);
2260 *__first = _VSTD::move(__tmp);
2266 __rotate_forward(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last)
2271 swap(*__first, *__i);
2272 ++__first;
2275 if (__first == __middle)
2278 _ForwardIterator __r = __first;
2279 if (__first != __middle)
2284 swap(*__first, *__i);
2285 ++__first;
2288 if (__first == __middle)
2292 else if (__first == __middle)
2315 __rotate_gcd(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator _…
2320 const difference_type __m1 = __middle - __first;
2324 _VSTD::swap_ranges(__first, __middle, __middle);
2328 for (_RandomAccessIterator __p = __first + __g; __p != __first;)
2341 __p2 = __first + (__m1 - __d);
2345 return __first + __m2;
2351 __rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last,
2357 if (_VSTD::next(__first) == __middle)
2358 return _VSTD::__rotate_left(__first, __last);
2360 return _VSTD::__rotate_forward(__first, __middle, __last);
2366 __rotate(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __…
2372 if (_VSTD::next(__first) == __middle)
2373 return _VSTD::__rotate_left(__first, __last);
2375 return _VSTD::__rotate_right(__first, __last);
2377 return _VSTD::__rotate_forward(__first, __middle, __last);
2383 __rotate(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __las…
2389 if (_VSTD::next(__first) == __middle)
2390 return _VSTD::__rotate_left(__first, __last);
2392 return _VSTD::__rotate_right(__first, __last);
2393 return _VSTD::__rotate_gcd(__first, __middle, __last);
2395 return _VSTD::__rotate_forward(__first, __middle, __last);
2401 rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last)
2403 if (__first == __middle)
2406 return __first;
2407 return _VSTD::__rotate(__first, __middle, __last,
2416 rotate_copy(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last, _OutputIt…
2418 return _VSTD::copy(__first, __middle, _VSTD::copy(__middle, __last, __result));
2426 min_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
2430 if (__first != __last)
2432 _ForwardIterator __i = __first;
2434 if (__comp(*__i, *__first))
2435 __first = __i;
2437 return __first;
2443 min_element(_ForwardIterator __first, _ForwardIterator __last)
2445 return _VSTD::min_element(__first, __last,
2492 max_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
2496 if (__first != __last)
2498 _ForwardIterator __i = __first;
2500 if (__comp(*__first, *__i))
2501 __first = __i;
2503 return __first;
2510 max_element(_ForwardIterator __first, _ForwardIterator __last)
2512 return _VSTD::max_element(__first, __last,
2580 minmax_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
2584 std::pair<_ForwardIterator, _ForwardIterator> __result(__first, __first);
2585 if (__first != __last)
2587 if (++__first != __last)
2589 if (__comp(*__first, *__result.first))
2590 __result.first = __first;
2592 __result.second = __first;
2593 while (++__first != __last)
2595 _ForwardIterator __i = __first;
2596 if (++__first == __last)
2606 if (__comp(*__first, *__i))
2608 if (__comp(*__first, *__result.first))
2609 __result.first = __first;
2617 if (!__comp(*__first, *__result.second))
2618 __result.second = __first;
2630 minmax_element(_ForwardIterator __first, _ForwardIterator __last)
2632 return _VSTD::minmax_element(__first, __last,
2663 _Iter __first = __t.begin();
2665 std::pair<_Tp, _Tp> __result(*__first, *__first);
2667 ++__first;
2670 if (__comp(*__first, __result.first))
2671 __result.first = *__first;
2673 __result.second = *__first;
2674 ++__first;
2677 while (__first != __last)
2679 _Tp __prev = *__first++;
2680 if (__comp(*__first, __prev)) {
2681 if ( __comp(*__first, __result.first)) __result.first = *__first;
2686 if (!__comp(*__first, __result.second)) __result.second = *__first;
2689 __first++;
2983 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
2988 difference_type __d = __last - __first;
2993 for (--__last, --__d; __first < __last; ++__first, --__d)
2997 swap(*__first, *(__first + __i));
3004 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
3012 difference_type __d = __last - __first;
3015 for (--__last; __first < __last; ++__first, --__d)
3019 swap(*__first, *(__first + __i));
3028 _SampleIterator __sample(_PopulationIterator __first,
3035 for (; __first != __last && __k < __n; ++__first, (void)++__k)
3036 __output_iter[__k] = *__first;
3038 for (; __first != __last; ++__first, (void)++__k) {
3041 __output_iter[__r] = *__first;
3049 _SampleIterator __sample(_PopulationIterator __first,
3054 _Distance __unsampled_sz = _VSTD::distance(__first, __last);
3055 for (__n = _VSTD::min(__n, __unsampled_sz); __n != 0; ++__first) {
3059 *__output_iter++ = *__first;
3069 _SampleIterator __sample(_PopulationIterator __first,
3082 __first, __last, __output_iter, _CommonType(__n),
3090 _SampleIterator sample(_PopulationIterator __first,
3093 return _VSTD::__sample(__first, __last, __output_iter, __n, __g);
3098 void shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
3108 difference_type __d = __last - __first;
3112 for (--__last, --__d; __first < __last; ++__first, --__d)
3116 swap(*__first, *(__first + __i));
3123 is_partitioned(_InputIterator __first, _InputIterator __last, _Predicate __pred)
3125 for (; __first != __last; ++__first)
3126 if (!__pred(*__first))
3128 if ( __first == __last )
3130 ++__first;
3131 for (; __first != __last; ++__first)
3132 if (__pred(*__first))
3141 __partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, forward_iterator_…
3145 if (__first == __last)
3146 return __first;
3147 if (!__pred(*__first))
3149 ++__first;
3151 for (_ForwardIterator __p = __first; ++__p != __last;)
3155 swap(*__first, *__p);
3156 ++__first;
3159 return __first;
3164 __partition(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred,
3171 if (__first == __last)
3172 return __first;
3173 if (!__pred(*__first))
3175 ++__first;
3179 if (__first == --__last)
3180 return __first;
3182 swap(*__first, *__last);
3183 ++__first;
3190 partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
3193 … (__first, __last, __pred, typename iterator_traits<_ForwardIterator>::iterator_category());
3201 partition_copy(_InputIterator __first, _InputIterator __last,
3205 for (; __first != __last; ++__first)
3207 if (__pred(*__first))
3209 *__out_true = *__first;
3214 *__out_false = *__first;
3225 partition_point(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
3228 difference_type __len = _VSTD::distance(__first, __last);
3232 _ForwardIterator __m = __first;
3236 __first = ++__m;
3242 return __first;
3249 __stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred,
3252 // *__first is known to be false
3255 return __first;
3258 _ForwardIterator __m = __first;
3261 swap(*__first, *__m);
3264 return __first;
3272 // Update __first to always point to the end of the trues
3274 ::new(__t) value_type(_VSTD::move(*__first));
3277 _ForwardIterator __i = __first;
3282 *__first = _VSTD::move(*__i);
3283 ++__first;
3293 // Move falses back into range, but don't mess up __first which points to first false
3294 __i = __first;
3298 return __first;
3302 _ForwardIterator __m = __first;
3305 // recurse on [__first, __m), *__first know to be false
3309 …_ForwardIterator __first_false = __stable_partition<_PredRef>(__first, __m, __pred, __len2, __p, _…
3341 __stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred,
3345 // Either prove all true and return __first or point to first false
3348 if (__first == __last)
3349 return __first;
3350 if (!__pred(*__first))
3352 ++__first;
3354 // We now have a reduced range [__first, __last)
3355 // *__first is known to be false
3358 difference_type __len = _VSTD::distance(__first, __last);
3367 (__first, __last, __pred, __len, __p, forward_iterator_tag());
3372 __stable_partition(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred,
3375 // *__first is known to be false
3380 swap(*__first, *__last);
3385 _BidirectionalIterator __m = __first;
3388 swap(*__first, *__m);
3393 swap(*__first, *__m);
3402 // Update __first to always point to the end of the trues
3404 ::new(__t) value_type(_VSTD::move(*__first));
3407 _BidirectionalIterator __i = __first;
3412 *__first = _VSTD::move(*__i);
3413 ++__first;
3423 *__first = _VSTD::move(*__i);
3424 __i = ++__first;
3426 // Move falses back into range, but don't mess up __first which points to first false
3430 return __first;
3434 _BidirectionalIterator __m = __first;
3437 …// recurse on [__first, __m-1], except reduce __m-1 until *(__m-1) is true, *__first know to be fa…
3441 _BidirectionalIterator __first_false = __first;
3445 if (__m1 == __first)
3452 __first_false = __stable_partition<_PredRef>(__first, __m1, __pred, __len_half, __p, __bit);
3480 __stable_partition(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred,
3486 // Either prove all true and return __first or point to first false
3489 if (__first == __last)
3490 return __first;
3491 if (!__pred(*__first))
3493 ++__first;
3495 // __first points to first false, everything prior to __first is already set.
3496 // Either prove [__first, __last) is all false and return __first, or point __last to last true
3499 if (__first == --__last)
3500 return __first;
3502 // We now have a reduced range [__first, __last]
3503 // *__first is known to be false
3506 difference_type __len = _VSTD::distance(__first, __last) + 1;
3515 (__first, __last, __pred, __len, __p, bidirectional_iterator_tag());
3521 stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
3524 … (__first, __last, __pred, typename iterator_traits<_ForwardIterator>::iterator_category());
3531 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
3533 if (__first != __last)
3535 _ForwardIterator __i = __first;
3538 if (__comp(*__i, *__first))
3540 __first = __i;
3549 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last)
3551 …return _VSTD::is_sorted_until(__first, __last, __less<typename iterator_traits<_ForwardIterator>::…
3559 is_sorted(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
3561 return _VSTD::is_sorted_until(__first, __last, __comp) == __last;
3567 is_sorted(_ForwardIterator __first, _ForwardIterator __last)
3569 …return _VSTD::is_sorted(__first, __last, __less<typename iterator_traits<_ForwardIterator>::value_…
3672 __selection_sort(_BirdirectionalIterator __first, _BirdirectionalIterator __last, _Compare __comp)
3675 for (--__lm1; __first != __lm1; ++__first)
3679 (__first, __last, __comp);
3680 if (__i != __first)
3681 swap(*__first, *__i);
3687 __insertion_sort(_BirdirectionalIterator __first, _BirdirectionalIterator __last, _Compare __comp)
3690 if (__first != __last)
3692 _BirdirectionalIterator __i = __first;
3697 for (_BirdirectionalIterator __k = __i; __k != __first && __comp(__t, *--__k); --__j)
3706 __insertion_sort_3(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
3709 _RandomAccessIterator __j = __first+2;
3710 __sort3<_Compare>(__first, __first+1, __j, __comp);
3722 } while (__j != __first && __comp(__t, *--__k));
3731 __insertion_sort_incomplete(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare _…
3733 switch (__last - __first)
3739 if (__comp(*--__last, *__first))
3740 swap(*__first, *__last);
3743 _VSTD::__sort3<_Compare>(__first, __first+1, --__last, __comp);
3746 _VSTD::__sort4<_Compare>(__first, __first+1, __first+2, --__last, __comp);
3749 _VSTD::__sort5<_Compare>(__first, __first+1, __first+2, __first+3, --__last, __comp);
3753 _RandomAccessIterator __j = __first+2;
3754 __sort3<_Compare>(__first, __first+1, __j, __comp);
3768 } while (__j != __first && __comp(__t, *--__k));
3815 __sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
3825 difference_type __len = __last - __first;
3832 if (__comp(*--__last, *__first))
3833 swap(*__first, *__last);
3836 _VSTD::__sort3<_Compare>(__first, __first+1, --__last, __comp);
3839 _VSTD::__sort4<_Compare>(__first, __first+1, __first+2, --__last, __comp);
3842 _VSTD::__sort5<_Compare>(__first, __first+1, __first+2, __first+3, --__last, __comp);
3847 _VSTD::__insertion_sort_3<_Compare>(__first, __last, __comp);
3851 _RandomAccessIterator __m = __first;
3862 … __n_swaps = _VSTD::__sort5<_Compare>(__first, __first + __delta, __m, __m+__delta, __lm1, __comp);
3868 __n_swaps = _VSTD::__sort3<_Compare>(__first, __m, __lm1, __comp);
3872 // partition [__first, __m) < *__m and *__m <= [__m, __last)
3874 _RandomAccessIterator __i = __first;
3879 if (!__comp(*__i, *__m)) // if *__first == *__m
3881 // *__first == *__m, *__first doesn't go in first part
3887 // *__first == *__m, *__m <= all other elements
3888 // Parition instead into [__first, __i) == *__first and *__first < [__i, __last)
3889 ++__i; // __first + 1
3891 if (!__comp(*__first, *--__j)) // we need a guard if *__first == *(__last-1)
3896 return; // [__first, __last) all equivalent elements
3897 if (__comp(*__first, *__i))
3907 // [__first, __i) == *__first and *__first < [__j, __last) and __j == __last - 1
3912 while (!__comp(*__first, *__i))
3914 while (__comp(*__first, *--__j))
3922 // [__first, __i) == *__first and *__first < [__i, __last)
3925 __first = __i;
3963 // [__first, __i) < *__m and *__m <= [__i, __last)
3969 // [__first, __i) < *__i and *__i <= [__i+1, __last)
3973 bool __fs = _VSTD::__insertion_sort_incomplete<_Compare>(__first, __i, __comp);
3985 __first = ++__i;
3991 if (__i - __first < __last - __i)
3993 _VSTD::__sort<_Compare>(__first, __i, __comp);
3995 __first = ++__i;
4000 // _VSTD::__sort<_Compare>(__first, __i, __comp);
4010 sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4015 __sort<_Comp_ref>(__first, __last, __c);
4018 __sort<_Comp_ref>(__first, __last, __comp);
4025 sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
4027 …_VSTD::sort(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>()…
4033 sort(_Tp** __first, _Tp** __last)
4035 _VSTD::sort((size_t*)__first, (size_t*)__last, __less<size_t>());
4041 sort(__wrap_iter<_Tp*> __first, __wrap_iter<_Tp*> __last)
4043 _VSTD::sort(__first.base(), __last.base());
4049 sort(__wrap_iter<_Tp*> __first, __wrap_iter<_Tp*> __last, _Compare __comp)
4052 _VSTD::sort<_Tp*, _Comp_ref>(__first.base(), __last.base(), __comp);
4093 __lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __co…
4096 difference_type __len = _VSTD::distance(__first, __last);
4100 _ForwardIterator __m = __first;
4104 __first = ++__m;
4110 return __first;
4116 lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4119 return __lower_bound<_Comp_ref>(__first, __last, __value_, __comp);
4125 lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)
4127 return _VSTD::lower_bound(__first, __last, __value_,
4135 __upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __co…
4138 difference_type __len = _VSTD::distance(__first, __last);
4142 _ForwardIterator __m = __first;
4148 __first = ++__m;
4152 return __first;
4158 upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4161 return __upper_bound<_Comp_ref>(__first, __last, __value_, __comp);
4167 upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)
4169 return _VSTD::upper_bound(__first, __last, __value_,
4177 __equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __co…
4180 difference_type __len = _VSTD::distance(__first, __last);
4184 _ForwardIterator __m = __first;
4188 __first = ++__m;
4201 __lower_bound<_Compare>(__first, __m, __value_, __comp),
4206 return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
4212 equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
4217 return __equal_range<_Comp_ref>(__first, __last, __value_, __c);
4220 return __equal_range<_Comp_ref>(__first, __last, __value_, __comp);
4227 equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)
4229 return _VSTD::equal_range(__first, __last, __value_,
4238 __binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __…
4240 __first = __lower_bound<_Compare>(__first, __last, __value_, __comp);
4241 return __first != __last && !__comp(__value_, *__first);
4247 binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __co…
4252 return __binary_search<_Comp_ref>(__first, __last, __value_, __c);
4255 return __binary_search<_Comp_ref>(__first, __last, __value_, __comp);
4262 binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)
4264 return _VSTD::binary_search(__first, __last, __value_,
4352 __buffered_inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _Bidirect…
4363 …for (_BidirectionalIterator __i = __first; __i != __middle; __d.__incr((value_type*)0), (void) ++_…
4365 __half_inplace_merge(__buff, __p, __middle, __last, __first, __comp);
4375 _RBi(__middle), _RBi(__first),
4382 __inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIter…
4395 (__first, __middle, __last, __comp, __len1, __len2, __buff);
4396 … // shrink [__first, __middle) as much as possible (with no moves), returning if it shrinks to 0
4397 for (; true; ++__first, (void) --__len1)
4401 if (__comp(*__middle, *__first))
4404 // __first < __middle < __last
4405 // *__first > *__middle
4406 // partition [__first, __m1) [__m1, __middle) [__middle, __m2) [__m2, __last) such that
4408 // [__first, __m1) <= [__middle, __m2)
4412 _BidirectionalIterator __m1; // "median" of [__first, __middle)
4414 difference_type __len11; // distance(__first, __m1)
4422 __m1 = __upper_bound<_Compare>(__first, __middle, *__m2, __comp);
4423 __len11 = _VSTD::distance(__first, __m1);
4429 // It is known *__first > *__middle
4430 swap(*__first, *__middle);
4435 __m1 = __first;
4442 // [__first, __m1) [__m1, __middle) [__middle, __m2) [__m2, __last)
4449 … __inplace_merge<_Compare>(__first, __m1, __middle, __comp, __len11, __len21, __buff, __buff_size);
4451 __first = __middle;
4459 // __inplace_merge<_Compare>(__first, __m1, __middle, __comp, __len11, __len21, __buff, __…
4471 inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterat…
4476 difference_type __len1 = _VSTD::distance(__first, __middle);
4485 return _VSTD::__inplace_merge<_Comp_ref>(__first, __middle, __last, __c, __len1, __len2,
4489 return _VSTD::__inplace_merge<_Comp_ref>(__first, __middle, __last, __comp, __len1, __len2,
4497 inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterat…
4499 _VSTD::inplace_merge(__first, __middle, __last,
4576 __stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
4634 __stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
4646 if (__comp(*--__last, *__first))
4647 swap(*__first, *__last);
4652 __insertion_sort<_Compare>(__first, __last, __comp);
4656 _RandomAccessIterator __m = __first + __l2;
4661 __stable_sort_move<_Compare>(__first, __m, __comp, __l2, __buff);
4665 …__merge_move_assign<_Compare>(__buff, __buff + __l2, __buff + __l2, __buff + __len, __first, __com…
4670 // __first, __comp);
4673 __stable_sort<_Compare>(__first, __m, __comp, __l2, __buff, __buff_size);
4675 … __inplace_merge<_Compare>(__first, __m, __last, __comp, __l2, __len - __l2, __buff, __buff_size);
4681 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4685 difference_type __len = __last - __first;
4696 __stable_sort<_Comp_ref>(__first, __last, __c, __len, __buf.first, __buf.second);
4699 __stable_sort<_Comp_ref>(__first, __last, __comp, __len, __buf.first, __buf.second);
4706 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
4708 …_VSTD::stable_sort(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_…
4715 is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4718 difference_type __len = __last - __first;
4721 _RandomAccessIterator __pp = __first;
4724 _RandomAccessIterator __cp = __first + __c;
4743 is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last)
4745 …return _VSTD::is_heap_until(__first, __last, __less<typename iterator_traits<_RandomAccessIterator…
4753 is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4755 return _VSTD::is_heap_until(__first, __last, __comp) == __last;
4761 is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
4763 …return _VSTD::is_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::val…
4770 __sift_up(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
4777 _RandomAccessIterator __ptr = __first + __len;
4788 __ptr = __first + __len;
4798 push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4803 __sift_up<_Comp_ref>(__first, __last, __c, __last - __first);
4806 __sift_up<_Comp_ref>(__first, __last, __comp, __last - __first);
4813 push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
4815 …_VSTD::push_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_ty…
4822 __sift_down(_RandomAccessIterator __first, _RandomAccessIterator /*__last*/,
4831 difference_type __child = __start - __first;
4837 _RandomAccessIterator __child_i = __first + __child;
4862 __child_i = __first + __child;
4878 __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
4883 swap(*__first, *--__last);
4884 __sift_down<_Compare>(__first, __last, __comp, __len - 1, __first);
4891 pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4896 __pop_heap<_Comp_ref>(__first, __last, __c, __last - __first);
4899 __pop_heap<_Comp_ref>(__first, __last, __comp, __last - __first);
4906 pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
4908 …_VSTD::pop_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_typ…
4915 __make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4918 difference_type __n = __last - __first;
4924 __sift_down<_Compare>(__first, __last, __comp, __n, __first + __start);
4932 make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4937 __make_heap<_Comp_ref>(__first, __last, __c);
4940 __make_heap<_Comp_ref>(__first, __last, __comp);
4947 make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
4949 …_VSTD::make_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_ty…
4956 __sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4959 for (difference_type __n = __last - __first; __n > 1; --__last, --__n)
4960 __pop_heap<_Compare>(__first, __last, __comp, __n);
4966 sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
4971 __sort_heap<_Comp_ref>(__first, __last, __c);
4974 __sort_heap<_Comp_ref>(__first, __last, __comp);
4981 sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
4983 …_VSTD::sort_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_ty…
4990 __partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator…
4993 __make_heap<_Compare>(__first, __middle, __comp);
4994 typename iterator_traits<_RandomAccessIterator>::difference_type __len = __middle - __first;
4997 if (__comp(*__i, *__first))
4999 swap(*__i, *__first);
5000 __sift_down<_Compare>(__first, __middle, __comp, __len, __first);
5003 __sort_heap<_Compare>(__first, __middle, __comp);
5009 partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator _…
5015 __partial_sort<_Comp_ref>(__first, __middle, __last, __c);
5018 __partial_sort<_Comp_ref>(__first, __middle, __last, __comp);
5025 partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator _…
5027 _VSTD::partial_sort(__first, __middle, __last,
5035 __partial_sort_copy(_InputIterator __first, _InputIterator __last,
5041 for (; __first != __last && __r != __result_last; (void) ++__first, ++__r)
5042 *__r = *__first;
5045 for (; __first != __last; ++__first)
5046 if (__comp(*__first, *__result_first))
5048 *__result_first = *__first;
5059 partial_sort_copy(_InputIterator __first, _InputIterator __last,
5065 return __partial_sort_copy<_Comp_ref>(__first, __last, __result_first, __result_last, __c);
5068 return __partial_sort_copy<_Comp_ref>(__first, __last, __result_first, __result_last, __comp);
5075 partial_sort_copy(_InputIterator __first, _InputIterator __last,
5078 return _VSTD::partial_sort_copy(__first, __last, __result_first, __result_last,
5086 __nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __l…
5096 difference_type __len = __last - __first;
5103 if (__comp(*--__last, *__first))
5104 swap(*__first, *__last);
5108 _RandomAccessIterator __m = __first;
5109 _VSTD::__sort3<_Compare>(__first, ++__m, --__last, __comp);
5115 __selection_sort<_Compare>(__first, __last, __comp);
5119 _RandomAccessIterator __m = __first + __len/2;
5121 unsigned __n_swaps = _VSTD::__sort3<_Compare>(__first, __m, --__lm1, __comp);
5123 // partition [__first, __m) < *__m and *__m <= [__m, __last)
5125 _RandomAccessIterator __i = __first;
5130 if (!__comp(*__i, *__m)) // if *__first == *__m
5132 // *__first == *__m, *__first doesn't go in first part
5138 // *__first == *__m, *__m <= all other elements
5139 // Parition instead into [__first, __i) == *__first and *__first < [__i, __last)
5140 ++__i; // __first + 1
5142 if (!__comp(*__first, *--__j)) // we need a guard if *__first == *(__last-1)
5147 return; // [__first, __last) all equivalent elements
5148 if (__comp(*__first, *__i))
5158 // [__first, __i) == *__first and *__first < [__j, __last) and __j == __last - 1
5163 while (!__comp(*__first, *__i))
5165 while (__comp(*__first, *--__j))
5173 // [__first, __i) == *__first and *__first < [__i, __last)
5179 __first = __i;
5215 // [__first, __i) < *__m and *__m <= [__i, __last)
5221 // [__first, __i) < *__i and *__i <= [__i+1, __last)
5229 // Check for [__first, __i) already sorted
5230 __j = __m = __first;
5238 // [__first, __i) sorted
5260 // __nth_element<_Compare>(__first, __nth, __i, __comp);
5266 __first = ++__i;
5274 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __las…
5279 __nth_element<_Comp_ref>(__first, __nth, __last, __c);
5282 __nth_element<_Comp_ref>(__first, __nth, __last, __comp);
5289 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __las…
5291 …_VSTD::nth_element(__first, __nth, __last, __less<typename iterator_traits<_RandomAccessIterator>:…
5604 __next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
5607 if (__first == __last || __first == --__i)
5621 if (__i == __first)
5623 _VSTD::reverse(__first, __last);
5632 next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
5637 return __next_permutation<_Comp_ref>(__first, __last, __c);
5640 return __next_permutation<_Comp_ref>(__first, __last, __comp);
5647 next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last)
5649 return _VSTD::next_permutation(__first, __last,
5657 __prev_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
5660 if (__first == __last || __first == --__i)
5674 if (__i == __first)
5676 _VSTD::reverse(__first, __last);
5685 prev_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
5690 return __prev_permutation<_Comp_ref>(__first, __last, __c);
5693 return __prev_permutation<_Comp_ref>(__first, __last, __comp);
5700 prev_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last)
5702 return _VSTD::prev_permutation(__first, __last,