STL.zip_C++STL_C++标准库_C标准库_STL_welcomeuof

// algorithm standard header #pragma once #ifndef _ALGORITHM_ #define _ALGORITHM_ #ifndef RC_INVOKED #include <xmemory> #pragma pack(push,_CRT_PACKING) #pragma warning(push,_STL_WARNING_LEVEL) #pragma warning(disable: _STL_DISABLED_WARNINGS) #pragma push_macro("new") #undef new _STD_BEGIN // COMMON SORT PARAMETERS const int _ISORT_MAX = 32; // maximum size for insertion sort // STRUCT TEMPLATE _Temporary_buffer template<class _Diff> constexpr ptrdiff_t _Temporary_buffer_size(const _Diff _Value) { // convert an iterator difference_type to a ptrdiff_t for use in _Temporary_buffer using _CT = common_type_t<ptrdiff_t, _Diff>; _CT _Max_possible = PTRDIFF_MAX; if (static_cast<_CT>(_Value) > _Max_possible) { return (PTRDIFF_MAX); } return (static_cast<ptrdiff_t>(_Value)); } template<class _Ty> struct _Temporary_buffer { // temporary storage template<class _Diff> explicit _Temporary_buffer(const _Diff _Requested_size) { // get temporary storage const pair<_Ty *, ptrdiff_t> _Raw = _Get_temporary_buffer<_Ty>(_Temporary_buffer_size(_Requested_size)); _Data = _Raw.first; _Capacity = _Raw.second; } _Temporary_buffer(const _Temporary_buffer&) = delete; _Temporary_buffer& operator=(const _Temporary_buffer&) = delete; ~_Temporary_buffer() _NOEXCEPT { // return temporary storage _Return_temporary_buffer(_Data); } _Ty * _Data; ptrdiff_t _Capacity; }; // STRUCT TEMPLATE _Temporary_range template<class _Ty> struct _Temporary_range { // a range of objects constructed in a temporary buffer using value_type = _Ty; explicit _Temporary_range(_Temporary_buffer<_Ty>& _Buffer) : _Data(_Buffer._Data), _Capacity(_Buffer._Capacity), _Size(0) { // construct a range around a temporary buffer } template<class _FwdIt> _Temporary_range(_Temporary_buffer<_Ty>& _Buffer, const _FwdIt _First, const _FwdIt _Last, const ptrdiff_t _Count) : _Data(_Buffer._Data), _Capacity(_Buffer._Capacity), _Size(_Count) { // construct a range around a temporary buffer, and move another range into it _Uninitialized_move_unchecked(_First, _Last, _Data); } _Temporary_range(const _Temporary_range&) = delete; _Temporary_range& operator=(const _Temporary_range&) = delete; ~_Temporary_range() _NOEXCEPT { // destroy constructed elements _Destroy_range(_Data, _Data + _Size); } _Ty * _Begin() { // get the beginning of this range return (_Data); } _Ty * _End() { // get the end of this range return (_Data + _Size); } void push_back(_Ty&& _Val) { // add an element to the end _Construct_in_place(_Data[_Size], _STD move(_Val)); ++_Size; } _Ty * _Data; ptrdiff_t _Capacity; ptrdiff_t _Size; }; // FUNCTION TEMPLATE for_each template<class _InIt, class _Fn> inline _Fn for_each(_InIt _First, _InIt _Last, _Fn _Func) { // perform function for each element [_First, _Last) _DEBUG_RANGE(_First, _Last); auto _UFirst = _Unchecked(_First); const auto _ULast = _Unchecked(_Last); for (; _UFirst != _ULast; ++_UFirst) { _Func(*_UFirst); } return (_Func); } #if _HAS_CXX17 template<class _ExPo, class _FwdIt, class _Fn, _Enable_if_execution_policy_t<_ExPo> = 0> inline void for_each(_ExPo&& _Exec, _FwdIt _First, _FwdIt _Last, _Fn _Func) _NOEXCEPT; // FUNCTION TEMPLATE for_each_n template<class _InIt, class _Diff, class _Fn> inline _InIt for_each_n(_InIt _First, const _Diff _Count_raw, _Fn _Func) { // perform function for each element [_First, _First + _Count) _Algorithm_int_t<_Diff> _Count = _Count_raw; auto _UFirst = _Unchecked_n(_First, _Count); for (; 0 < _Count; --_Count, (void)++_UFirst) { _Func(*_UFirst); } return (_Rechecked(_First, _UFirst)); } template<class _ExPo, class _FwdIt, class _Diff, class _Fn, _Enable_if_execution_policy_t<_ExPo> = 0> inline _FwdIt for_each_n(_ExPo&& _Exec, _FwdIt _First, _Diff _Count_raw, _Fn _Func) _NOEXCEPT; #if _ITERATOR_DEBUG_ARRAY_OVERLOADS template<class _InTy, size_t _InSize, class _Diff, class _Fn> inline _InTy * for_each_n(_InTy (&_First)[_InSize], const _Diff _Count_raw, _Fn _Func) { // perform function for each element [_First, _First + _Count) _Algorithm_int_t<_Diff> _Count = _Count_raw; _DEBUG_ARRAY_SIZE(_First, _Count); _InTy * _UFirst = _First; for (; 0 < _Count; --_Count, (void)++_UFirst) { _Func(*_UFirst); } return (_UFirst); } template<class _ExPo, class _SourceTy, size_t _SourceSize, class _Diff, class _Fn, _Enable_if_execution_policy_t<_ExPo> = 0> inline _SourceTy * for_each_n(_ExPo&& _Exec, _SourceTy (&_First)[_SourceSize], _Diff _Count_raw, _Fn _Func) _NOEXCEPT; #endif /* _ITERATOR_DEBUG_ARRAY_OVERLOADS */ #endif /* _HAS_CXX17 */ // FUNCTION TEMPLATE find_if template<class _InIt, class _Pr> _NODISCARD inline _InIt find_if(_InIt _First, const _InIt _Last, _Pr _Pred) { // find first satisfying _Pred _DEBUG_RANGE(_First, _Last); auto _UFirst = _Unchecked(_First); const auto _ULast = _Unchecked(_Last); for (; _UFirst != _ULast; ++_UFirst) { if (_Pred(*_UFirst)) { break; } } return (_Rechecked(_First, _UFirst)); } #if _HAS_CXX17 template<class _ExPo, class _FwdIt, class _Pr, _Enable_if_execution_policy_t<_ExPo> = 0> _NODISCARD _FwdIt find_if(_ExPo&& _Exec, _FwdIt _First, const _FwdIt _Last, _Pr _Pred) _NOEXCEPT; #endif /* _HAS_CXX17 */ // FUNCTION TEMPLATE find_if_not template<class _InIt, class _Pr> _NODISCARD inline _InIt find_if_not(_InIt _First, const _InIt _Last, _Pr _Pred) { // find first element that satisfies !_Pred _DEBUG_RANGE(_First, _Last); auto _UFirst = _Unchecked(_First); const auto _ULast = _Unchecked(_Last); for (; _UFirst != _ULast; ++_UFirst) { if (!_Pred(*_UFirst)) { break; } } return (_Rechecked(_First, _UFirst)); } #if _HAS_CXX17 template<class _ExPo, class _FwdIt, class _Pr, _Enable_if_execution_policy_t<_ExPo> = 0> _NODISCARD inline _FwdIt find_if_not(_ExPo&& _Exec, _FwdIt _First, _FwdIt _Last, _Pr _Pred) _NOEXCEPT; #endif /* _HAS_CXX17 */ // FUNCTION TEMPLATE adjacent_find template<class _FwdIt, class _Pr> _NODISCARD inline _FwdIt adjacent_find(const _FwdIt _First, _FwdIt _Last, _Pr _Pred) { // find first satisfying _Pred with successor _DEBUG_RANGE(_First, _Last); auto _UFirst = _Unchecked(_First); auto _ULast = _Unchecked(_Last); if (_UFirst != _ULast) { for (auto _UNext = _UFirst; ++_UNext != _ULast; _UFirst = _UNext) { if (_Pred(*_UFirst, *_UNext)) { _ULast = _UFirst; break; } } } return (_Rechecked(_Last, _ULast)); } template<class _FwdIt> _NODISCARD inline _FwdIt adjacent_find(const _FwdIt _First, const _FwdIt _Last) { // find first matching successor return (_STD adjacent_find(_First, _Last, equal_to<>())); } #if _HAS_CXX17 template<class _ExPo, class _FwdIt, class _Pr, _Enable_if_execution_policy_t<_ExPo> = 0> _NODISCARD inline _FwdIt adjacent_find(_ExPo&& _Exec, _FwdIt _First, _FwdIt _Last, _Pr _Pred) _NOEXCEPT; template<class _ExPo, class _FwdIt, _Enable_if_execution_policy_t<_ExPo> = 0> _NODISCARD inline _FwdIt adjacent_find(_ExPo&& _Exec, const _FwdIt _First, const _FwdIt _Last) _NOEXCEPT { // find first matching successor return (_STD adjacent_find(_STD forward<_ExPo>(_Exec), _First, _Last, equal_to<>())); } #endif /* _HAS_CXX17 */ // FUNCTION TEMPLATE count_if template<class _InIt, class _Pr> _NODISCARD inline _Iter_diff_t<_InIt> count_if(_InIt _First, _InIt _Last, _Pr _Pred) { // count elements satisfying _Pred _DEBUG_RANGE(_First, _Last); auto _UFirst = _Unchecked(_First); const auto _ULast = _Unchecked(_Last); _Iter_diff_t<_InIt> _Count = 0; for (; _UFirst != _ULast; ++_UFirst) { if (_Pred(*_UFirst)) { ++_Cou