STLport-4.5.zip_C++标准模板_STLport 4.5_STLport-4.6.2_stlport_stlpor

/* * * 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 _STLP_ALGO_C # define _STLP_ALGO_C _STLP_BEGIN_NAMESPACE 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, 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 _ForwardIter1, class _ForwardIter2> _ForwardIter1 search(_ForwardIter1 __first1, _ForwardIter1 __last1, _ForwardIter2 __first2, _ForwardIter2 __last2) { _STLP_DEBUG_CHECK(__check_range(__first1, __last1)) _STLP_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; _ForwardIter1 __current = __first1; while (__first1 != __last1) { __first1 = find(__first1, __last1, *__first2); if (__first1 == __last1) return __last1; __p = __p1; __current = __first1; if (++__current == __last1) return __last1; while (*__current == *__p) { if (++__p == __last2) return __first1; if (++__current == __last1) return __last1; } ++__first1; } return __first1; } // search_n. Search for __count consecutive copies of __val. template <class _ForwardIter, class _Integer, class _Tp> _ForwardIter search_n(_ForwardIter __first, _ForwardIter __last, _Integer __count, const _Tp& __val) { _STLP_DEBUG_CHECK(__check_range(__first, __last)) if (__count <= 0) return __first; else { __first = find(__first, __last, __val); while (__first != __last) { _Integer __n = __count - 1; _ForwardIter __i = __first; ++__i; while (__i != __last && __n != 0 && *__i == __val) { ++__i; --__n; } if (__n == 0) return __first; else __first = find(__i, __last, __val); } return __last; } } template <class _ForwardIter, class _Integer, class _Tp, class _BinaryPred> _ForwardIter search_n(_ForwardIter __first, _ForwardIter __last, _Integer __count, const _Tp& __val, _BinaryPred __binary_pred) { _STLP_DEBUG_CHECK(__check_range(__first, __last)) if (__count <= 0) return __first; else { while (__first != __last) { if (__binary_pred(*__first, __val)) break; ++__first; } while (__first != __last) { _Integer __n = __count - 1; _ForwardIter __i = __first; ++__i; while (__i != __last && __n != 0 && __binary_pred(*__i, __val)) { ++__i; --__n; } if (__n == 0) return __first; else { while (__i != __last) { if (__binary_pred(*__i, __val)) break; ++__i; } __first = __i; } } return __last; } } template <class _ForwardIter1, class _ForwardIter2> _ForwardIter1 find_end(_ForwardIter1 __first1, _ForwardIter1 __last1, _ForwardIter2 __first2, _ForwardIter2 __last2) { _STLP_DEBUG_CHECK(__check_range(__first1, __last1)) _STLP_DEBUG_CHECK(__check_range(__first2, __last2)) return __find_end(__first1, __last1, __first2, __last2, # if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION) _STLP_ITERATOR_CATEGORY(__first1, _ForwardIter1), _STLP_ITERATOR_CATEGORY(__first2, _ForwardIter2), # else forward_iterator_tag(), forward_iterator_tag(), # endif __equal_to(_STLP_VALUE_TYPE(__first1, _ForwardIter1)) ); } // unique and unique_copy template <class _InputIterator, class _OutputIterator, class _BinaryPredicate, class _Tp> _STLP_INLINE_LOOP _OutputIterator __unique_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _BinaryPredicate __binary_pred, _Tp*) { _Tp __value = *__first; *__result = __value; while (++__first != __last) if (!__binary_pred(__value, *__first)) { __value = *__first; *++__result = __value; } return ++__result; } template <class _InputIter, class _OutputIter, class _BinaryPredicate> inline _OutputIter __unique_copy(_InputIter __first, _InputIter __last,_OutputIter __result, _BinaryPredicate __binary_pred, const output_iterator_tag &) { return __unique_copy(__first, __last, __result, __binary_pred, _STLP_VALUE_TYPE(__first, _InputIter)); } template <class _InputIter, class _ForwardIter, class _BinaryPredicate> _STLP_INLINE_LOOP _ForwardIter __unique_copy(_InputIter __first, _InputIter __last, _ForwardIter __result, _BinaryPredicate __binary_pred, const forward_iterator_tag &) { *__result = *__first; while (++__first != __last) if (!__binary_pred(*__result, *__first)) *++__result = *__first; return ++__result; } # if defined (_STLP_NONTEMPL_BASE_MATCH_BUG) template <class _InputIterator, class _BidirectionalIterator, class _BinaryPredicate> inline _BidirectionalIterator __unique_copy(_InputIterator __first, _InputIterator __last, _BidirectionalIterator __result, _BinaryPredicate __binary_pred, const bidirectional_iterator_tag &) { return __unique_copy(__first, __last, __result, __binary_pred, forward_iterator_tag()); } template <class _InputIterator, class _RandomAccessIterator, class _BinaryPredicate> inline _RandomAccessIterator __unique_copy(_InputIterator __first, _InputIterator __last, _RandomAccessIterator __result, _BinaryPredicate __binary_pred, const random_access_iterator_tag &) { return __un