STL源代码 c++标准库函数 源码

/* * * Copyright (c) 1994 * Hewlett-Packard Company * * Copyright (c) 1996,1997 * Silicon Graphics Computer Systems, Inc. * * Copyright (c) 1997 * Moscow Center for SPARC Technology * * Copyright (c) 1999 * Boris Fomitchev * * This material is provided "as is", with absolutely no warranty expressed * or implied. Any use is at your own risk. * * Permission to use or copy this software for any purpose is hereby granted * without fee, provided the above notices are retained on all copies. * Permission to modify the code and to distribute modified code is granted, * provided the above notices are retained, and a notice that the code was * modified is included with the above copyright notice. * */ #ifndef __STL_ALGO_C # define __STL_ALGO_C __STL_BEGIN_NAMESPACE template <class _BidirectionalIter, class _Distance> void __merge_without_buffer(_BidirectionalIter __first, _BidirectionalIter __middle, _BidirectionalIter __last, _Distance __len1, _Distance __len2); template <class _BidirectionalIter, class _Distance, class _Compare> void __merge_without_buffer(_BidirectionalIter __first, _BidirectionalIter __middle, _BidirectionalIter __last, _Distance __len1, _Distance __len2, _Compare __comp); template <class _BidirectionalIter1, class _BidirectionalIter2, class _BidirectionalIter3> _BidirectionalIter3 __merge_backward(_BidirectionalIter1 __first1, _BidirectionalIter1 __last1, _BidirectionalIter2 __first2, _BidirectionalIter2 __last2, _BidirectionalIter3 __result); template <class _BidirectionalIter1, class _BidirectionalIter2, class _BidirectionalIter3, class _Compare> _BidirectionalIter3 __merge_backward(_BidirectionalIter1 __first1, _BidirectionalIter1 __last1, _BidirectionalIter2 __first2, _BidirectionalIter2 __last2, _BidirectionalIter3 __result, _Compare __comp); template <class _Tp> # if !(defined (__SUNPRO_CC) && (__SUNPRO_CC < 0x420 )) inline # endif const _Tp& __median(const _Tp& __a, const _Tp& __b, const _Tp& __c) { if (__a < __b) if (__b < __c) return __b; else if (__a < __c) return __c; else return __a; else if (__a < __c) return __a; else if (__b < __c) return __c; else return __b; } template <class _Tp, class _Compare> # if !(defined (__SUNPRO_CC) && (__SUNPRO_CC < 0x420 )) inline # endif const _Tp& __median(const _Tp& __a, const _Tp& __b, const _Tp& __c, _Compare __comp) { if (__comp(__a, __b)) if (__comp(__b, __c)) return __b; else if (__comp(__a, __c)) return __c; else return __a; else if (__comp(__a, __c)) return __a; else if (__comp(__b, __c)) return __c; else return __b; } template <class _InputIter, class _Function> _Function for_each(_InputIter __first, _InputIter __last, _Function __f) { for ( ; __first != __last; ++__first) __f(*__first); return __f; } #ifdef __STL_CLASS_PARTIAL_SPECIALIZATION template <class _RandomAccessIter, class _Tp> _RandomAccessIter find(_RandomAccessIter __first, _RandomAccessIter __last, const _Tp& __val, random_access_iterator_tag) { typename iterator_traits<_RandomAccessIter>::difference_type __trip_count = (__last - __first) >> 2; for ( ; __trip_count > 0 ; --__trip_count) { if (*__first == __val) return __first; ++__first; if (*__first == __val) return __first; ++__first; if (*__first == __val) return __first; ++__first; if (*__first == __val) return __first; ++__first; } switch(__last - __first) { case 3: if (*__first == __val) return __first; ++__first; case 2: if (*__first == __val) return __first; ++__first; case 1: if (*__first == __val) return __first; ++__first; case 0: default: return __last; } } template <class _RandomAccessIter, class _Predicate> _RandomAccessIter find_if(_RandomAccessIter __first, _RandomAccessIter __last, _Predicate __pred, random_access_iterator_tag) { typename iterator_traits<_RandomAccessIter>::difference_type __trip_count = (__last - __first) >> 2; for ( ; __trip_count > 0 ; --__trip_count) { if (__pred(*__first)) return __first; ++__first; if (__pred(*__first)) return __first; ++__first; if (__pred(*__first)) return __first; ++__first; if (__pred(*__first)) return __first; ++__first; } switch(__last - __first) { case 3: if (__pred(*__first)) return __first; ++__first; case 2: if (__pred(*__first)) return __first; ++__first; case 1: if (__pred(*__first)) return __first; // ++__first; case 0: default: return __last; } } #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */ template <class _ForwardIter> _ForwardIter adjacent_find(_ForwardIter __first, _ForwardIter __last) { __STL_DEBUG_CHECK(__check_range(__first, __last)) if (__first == __last) return __last; _ForwardIter __next = __first; while(++__next != __last) { if (*__first == *__next) return __first; __first = __next; } return __last; } template <class _ForwardIter, class _BinaryPredicate> _ForwardIter adjacent_find(_ForwardIter __first, _ForwardIter __last, _BinaryPredicate __binary_pred) { __STL_DEBUG_CHECK(__check_range(__first, __last)) if (__first == __last) return __last; _ForwardIter __next = __first; while(++__next != __last) { if (__binary_pred(*__first, *__next)) return __first; __first = __next; } return __last; } template <class _InputIter, class _Tp, class _Size> void count(_InputIter __first, _InputIter __last, const _Tp& __value, _Size& __n) { __STL_DEBUG_CHECK(__check_range(__first, __last)) for ( ; __first != __last; ++__first) if (*__first == __value) ++__n; } template <class _InputIter, class _Predicate, class _Size> void count_if(_InputIter __first, _InputIter __last, _Predicate __pred, _Size& __n) { __STL_DEBUG_CHECK(__check_range(__first, __last)) for ( ; __first != __last; ++__first) if (__pred(*__first)) ++__n; } template <class _InputIter, class _Tp> __STL_DIFFERENCE_TYPE(_InputIter) count(_InputIter __first, _InputIter __last, const _Tp& __value) { __STL_DEBUG_CHECK(__check_range(__first, __last)) __STL_DIFFERENCE_TYPE(_InputIter) __n = 0; for ( ; __first != __last; ++__first) if (*__first == __value) ++__n; return __n; } template <class _InputIter, class _Predicate> __STL_DIFFERENCE_TYPE(_InputIter) count_if(_InputIter __first, _InputIter __last, _Predicate __pred) { __STL_DEBUG_CHECK(__check_range(__first, __last)) __STL_DIFFERENCE_TYPE(_InputIter) __n = 0; for ( ; __first != __last; ++__first) if (__pred(*__first)) ++__n; return __n; } template <class _ForwardIter1, class _ForwardIter2> _ForwardIter1 search(_ForwardIter1 __first1, _ForwardIter1 __last1, _ForwardIter2 __first2, _ForwardIter2 __last2) { __STL_DEBUG_CHECK(__check_range(__first1, __last1)) __STL_DEBUG_CHECK(__check_range(__first2, __last2)) // Test for empty ranges if (__first1 == __last1 || __first2 == __last2) return __first1; // Test for a pattern of length 1. _ForwardIter2 __tmp(__first2); ++__tmp; if (__tmp == __last2) return find(__first1, __last1, *__first2); // General case. _ForwardIter2 __p1, __p; __p1 = __first2; ++__p1; _For