diff options
Diffstat (limited to 'contrib/libstdc++/include/bits/stl_algobase.h')
| -rw-r--r-- | contrib/libstdc++/include/bits/stl_algobase.h | 591 |
1 files changed, 342 insertions, 249 deletions
diff --git a/contrib/libstdc++/include/bits/stl_algobase.h b/contrib/libstdc++/include/bits/stl_algobase.h index d482529bf9ef..6f19febfe1e1 100644 --- a/contrib/libstdc++/include/bits/stl_algobase.h +++ b/contrib/libstdc++/include/bits/stl_algobase.h @@ -1,6 +1,7 @@ // Bits and pieces used in algorithms -*- C++ -*- -// Copyright (C) 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc. +// Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007 +// Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the @@ -15,7 +16,7 @@ // You should have received a copy of the GNU General Public License along // with this library; see the file COPYING. If not, write to the Free -// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, +// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, // USA. // As a special exception, you may use this file as part of a free software @@ -66,18 +67,68 @@ #include <climits> #include <cstdlib> #include <cstddef> -#include <new> #include <iosfwd> #include <bits/stl_pair.h> -#include <bits/type_traits.h> +#include <bits/cpp_type_traits.h> +#include <ext/type_traits.h> #include <bits/stl_iterator_base_types.h> #include <bits/stl_iterator_base_funcs.h> #include <bits/stl_iterator.h> #include <bits/concept_check.h> #include <debug/debug.h> -namespace std -{ +_GLIBCXX_BEGIN_NAMESPACE(std) + + /** + * @brief Swaps two values. + * @param a A thing of arbitrary type. + * @param b Another thing of arbitrary type. + * @return Nothing. + * + * This is the simple classic generic implementation. It will work on + * any type which has a copy constructor and an assignment operator. + */ + template<typename _Tp> + inline void + swap(_Tp& __a, _Tp& __b) + { + // concept requirements + __glibcxx_function_requires(_SGIAssignableConcept<_Tp>) + + _Tp __tmp = __a; + __a = __b; + __b = __tmp; + } + + // See http://gcc.gnu.org/ml/libstdc++/2004-08/msg00167.html: in a + // nutshell, we are partially implementing the resolution of DR 187, + // when it's safe, i.e., the value_types are equal. + template<bool _BoolType> + struct __iter_swap + { + template<typename _ForwardIterator1, typename _ForwardIterator2> + static void + iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b) + { + typedef typename iterator_traits<_ForwardIterator1>::value_type + _ValueType1; + _ValueType1 __tmp = *__a; + *__a = *__b; + *__b = __tmp; + } + }; + + template<> + struct __iter_swap<true> + { + template<typename _ForwardIterator1, typename _ForwardIterator2> + static void + iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b) + { + swap(*__a, *__b); + } + }; + /** * @brief Swaps the contents of two iterators. * @param a An iterator. @@ -106,36 +157,17 @@ namespace std __glibcxx_function_requires(_ConvertibleConcept<_ValueType2, _ValueType1>) - const _ValueType1 __tmp = *__a; - *__a = *__b; - *__b = __tmp; + typedef typename iterator_traits<_ForwardIterator1>::reference + _ReferenceType1; + typedef typename iterator_traits<_ForwardIterator2>::reference + _ReferenceType2; + std::__iter_swap<__are_same<_ValueType1, _ValueType2>::__value && + __are_same<_ValueType1 &, _ReferenceType1>::__value && + __are_same<_ValueType2 &, _ReferenceType2>::__value>:: + iter_swap(__a, __b); } /** - * @brief Swaps two values. - * @param a A thing of arbitrary type. - * @param b Another thing of arbitrary type. - * @return Nothing. - * - * This is the simple classic generic implementation. It will work on - * any type which has a copy constructor and an assignment operator. - */ - template<typename _Tp> - inline void - swap(_Tp& __a, _Tp& __b) - { - // concept requirements - __glibcxx_function_requires(_SGIAssignableConcept<_Tp>) - - const _Tp __tmp = __a; - __a = __b; - __b = __tmp; - } - - #undef min - #undef max - - /** * @brief This does what you think it does. * @param a A thing of arbitrary type. * @param b Another thing of arbitrary type. @@ -219,113 +251,122 @@ namespace std return __a; } - // All of these auxiliary functions serve two purposes. (1) Replace + // All of these auxiliary structs serve two purposes. (1) Replace // calls to copy with memmove whenever possible. (Memmove, not memcpy, // because the input and output ranges are permitted to overlap.) // (2) If we're using random access iterators, then write the loop as // a for loop with an explicit count. - template<typename _InputIterator, typename _OutputIterator> - inline _OutputIterator - __copy(_InputIterator __first, _InputIterator __last, - _OutputIterator __result, input_iterator_tag) + template<bool, typename> + struct __copy { - for (; __first != __last; ++__result, ++__first) - *__result = *__first; - return __result; - } + template<typename _II, typename _OI> + static _OI + copy(_II __first, _II __last, _OI __result) + { + for (; __first != __last; ++__result, ++__first) + *__result = *__first; + return __result; + } + }; - template<typename _RandomAccessIterator, typename _OutputIterator> - inline _OutputIterator - __copy(_RandomAccessIterator __first, _RandomAccessIterator __last, - _OutputIterator __result, random_access_iterator_tag) - { - typedef typename iterator_traits<_RandomAccessIterator>::difference_type - _Distance; - for (_Distance __n = __last - __first; __n > 0; --__n) - { - *__result = *__first; - ++__first; - ++__result; + template<bool _BoolType> + struct __copy<_BoolType, random_access_iterator_tag> + { + template<typename _II, typename _OI> + static _OI + copy(_II __first, _II __last, _OI __result) + { + typedef typename iterator_traits<_II>::difference_type _Distance; + for(_Distance __n = __last - __first; __n > 0; --__n) + { + *__result = *__first; + ++__first; + ++__result; + } + return __result; } - return __result; - } + }; - template<typename _Tp> - inline _Tp* - __copy_trivial(const _Tp* __first, const _Tp* __last, _Tp* __result) + template<> + struct __copy<true, random_access_iterator_tag> { - std::memmove(__result, __first, sizeof(_Tp) * (__last - __first)); - return __result + (__last - __first); - } - - template<typename _InputIterator, typename _OutputIterator> - inline _OutputIterator - __copy_aux2(_InputIterator __first, _InputIterator __last, - _OutputIterator __result, __false_type) - { return std::__copy(__first, __last, __result, - std::__iterator_category(__first)); } - - template<typename _InputIterator, typename _OutputIterator> - inline _OutputIterator - __copy_aux2(_InputIterator __first, _InputIterator __last, - _OutputIterator __result, __true_type) - { return std::__copy(__first, __last, __result, - std::__iterator_category(__first)); } - - template<typename _Tp> - inline _Tp* - __copy_aux2(_Tp* __first, _Tp* __last, _Tp* __result, __true_type) - { return std::__copy_trivial(__first, __last, __result); } + template<typename _Tp> + static _Tp* + copy(const _Tp* __first, const _Tp* __last, _Tp* __result) + { + std::memmove(__result, __first, sizeof(_Tp) * (__last - __first)); + return __result + (__last - __first); + } + }; - template<typename _Tp> - inline _Tp* - __copy_aux2(const _Tp* __first, const _Tp* __last, _Tp* __result, - __true_type) - { return std::__copy_trivial(__first, __last, __result); } + template<typename _II, typename _OI> + inline _OI + __copy_aux(_II __first, _II __last, _OI __result) + { + typedef typename iterator_traits<_II>::value_type _ValueTypeI; + typedef typename iterator_traits<_OI>::value_type _ValueTypeO; + typedef typename iterator_traits<_II>::iterator_category _Category; + const bool __simple = (__is_scalar<_ValueTypeI>::__value + && __is_pointer<_II>::__value + && __is_pointer<_OI>::__value + && __are_same<_ValueTypeI, _ValueTypeO>::__value); - template<typename _InputIterator, typename _OutputIterator> - inline _OutputIterator - __copy_ni2(_InputIterator __first, _InputIterator __last, - _OutputIterator __result, __true_type) - { - typedef typename iterator_traits<_InputIterator>::value_type - _ValueType; - typedef typename __type_traits< - _ValueType>::has_trivial_assignment_operator _Trivial; - return _OutputIterator(std::__copy_aux2(__first, __last, __result.base(), - _Trivial())); + return std::__copy<__simple, _Category>::copy(__first, __last, __result); } - template<typename _InputIterator, typename _OutputIterator> - inline _OutputIterator - __copy_ni2(_InputIterator __first, _InputIterator __last, - _OutputIterator __result, __false_type) + // Helpers for streambuf iterators (either istream or ostream). + template<typename _CharT> + typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value, + ostreambuf_iterator<_CharT> >::__type + __copy_aux(_CharT*, _CharT*, ostreambuf_iterator<_CharT>); + + template<typename _CharT> + typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value, + ostreambuf_iterator<_CharT> >::__type + __copy_aux(const _CharT*, const _CharT*, ostreambuf_iterator<_CharT>); + + template<typename _CharT> + typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value, _CharT*>::__type + __copy_aux(istreambuf_iterator<_CharT>, istreambuf_iterator<_CharT>, + _CharT*); + + template<bool, bool> + struct __copy_normal + { + template<typename _II, typename _OI> + static _OI + __copy_n(_II __first, _II __last, _OI __result) + { return std::__copy_aux(__first, __last, __result); } + }; + + template<> + struct __copy_normal<true, false> { - typedef typename iterator_traits<_InputIterator>::value_type _ValueType; - typedef typename __type_traits< - _ValueType>::has_trivial_assignment_operator _Trivial; - return std::__copy_aux2(__first, __last, __result, _Trivial()); - } + template<typename _II, typename _OI> + static _OI + __copy_n(_II __first, _II __last, _OI __result) + { return std::__copy_aux(__first.base(), __last.base(), __result); } + }; - template<typename _InputIterator, typename _OutputIterator> - inline _OutputIterator - __copy_ni1(_InputIterator __first, _InputIterator __last, - _OutputIterator __result, __true_type) + template<> + struct __copy_normal<false, true> { - typedef typename _Is_normal_iterator<_OutputIterator>::_Normal __Normal; - return std::__copy_ni2(__first.base(), __last.base(), - __result, __Normal()); - } + template<typename _II, typename _OI> + static _OI + __copy_n(_II __first, _II __last, _OI __result) + { return _OI(std::__copy_aux(__first, __last, __result.base())); } + }; - template<typename _InputIterator, typename _OutputIterator> - inline _OutputIterator - __copy_ni1(_InputIterator __first, _InputIterator __last, - _OutputIterator __result, __false_type) + template<> + struct __copy_normal<true, true> { - typedef typename _Is_normal_iterator<_OutputIterator>::_Normal __Normal; - return std::__copy_ni2(__first, __last, __result, __Normal()); - } + template<typename _II, typename _OI> + static _OI + __copy_n(_II __first, _II __last, _OI __result) + { return _OI(std::__copy_aux(__first.base(), __last.base(), + __result.base())); } + }; /** * @brief Copies the range [first,last) into result. @@ -354,116 +395,114 @@ namespace std typename iterator_traits<_InputIterator>::value_type>) __glibcxx_requires_valid_range(__first, __last); - typedef typename _Is_normal_iterator<_InputIterator>::_Normal __Normal; - return std::__copy_ni1(__first, __last, __result, __Normal()); - } - - template<typename _BidirectionalIterator1, typename _BidirectionalIterator2> - inline _BidirectionalIterator2 - __copy_backward(_BidirectionalIterator1 __first, - _BidirectionalIterator1 __last, - _BidirectionalIterator2 __result, - bidirectional_iterator_tag) - { - while (__first != __last) - *--__result = *--__last; - return __result; - } - - template<typename _RandomAccessIterator, typename _BidirectionalIterator> - inline _BidirectionalIterator - __copy_backward(_RandomAccessIterator __first, _RandomAccessIterator __last, - _BidirectionalIterator __result, random_access_iterator_tag) - { - typename iterator_traits<_RandomAccessIterator>::difference_type __n; - for (__n = __last - __first; __n > 0; --__n) - *--__result = *--__last; - return __result; + const bool __in = __is_normal_iterator<_InputIterator>::__value; + const bool __out = __is_normal_iterator<_OutputIterator>::__value; + return std::__copy_normal<__in, __out>::__copy_n(__first, __last, + __result); } - - // This dispatch class is a workaround for compilers that do not - // have partial ordering of function templates. All we're doing is - // creating a specialization so that we can turn a call to copy_backward - // into a memmove whenever possible. - template<typename _BidirectionalIterator1, typename _BidirectionalIterator2, - typename _BoolType> - struct __copy_backward_dispatch - { - static _BidirectionalIterator2 - copy(_BidirectionalIterator1 __first, _BidirectionalIterator1 __last, - _BidirectionalIterator2 __result) - { return std::__copy_backward(__first, __last, __result, - std::__iterator_category(__first)); } + // Overload for streambuf iterators. + template<typename _CharT> + typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value, + ostreambuf_iterator<_CharT> >::__type + copy(istreambuf_iterator<_CharT>, istreambuf_iterator<_CharT>, + ostreambuf_iterator<_CharT>); + + template<bool, typename> + struct __copy_backward + { + template<typename _BI1, typename _BI2> + static _BI2 + __copy_b(_BI1 __first, _BI1 __last, _BI2 __result) + { + while (__first != __last) + *--__result = *--__last; + return __result; + } }; - template<typename _Tp> - struct __copy_backward_dispatch<_Tp*, _Tp*, __true_type> - { - static _Tp* - copy(const _Tp* __first, const _Tp* __last, _Tp* __result) - { - const ptrdiff_t _Num = __last - __first; - std::memmove(__result - _Num, __first, sizeof(_Tp) * _Num); - return __result - _Num; - } + template<bool _BoolType> + struct __copy_backward<_BoolType, random_access_iterator_tag> + { + template<typename _BI1, typename _BI2> + static _BI2 + __copy_b(_BI1 __first, _BI1 __last, _BI2 __result) + { + typename iterator_traits<_BI1>::difference_type __n; + for (__n = __last - __first; __n > 0; --__n) + *--__result = *--__last; + return __result; + } }; - template<typename _Tp> - struct __copy_backward_dispatch<const _Tp*, _Tp*, __true_type> - { - static _Tp* - copy(const _Tp* __first, const _Tp* __last, _Tp* __result) - { - return std::__copy_backward_dispatch<_Tp*, _Tp*, __true_type> - ::copy(__first, __last, __result); - } + template<> + struct __copy_backward<true, random_access_iterator_tag> + { + template<typename _Tp> + static _Tp* + __copy_b(const _Tp* __first, const _Tp* __last, _Tp* __result) + { + const ptrdiff_t _Num = __last - __first; + std::memmove(__result - _Num, __first, sizeof(_Tp) * _Num); + return __result - _Num; + } }; template<typename _BI1, typename _BI2> inline _BI2 __copy_backward_aux(_BI1 __first, _BI1 __last, _BI2 __result) { - typedef typename __type_traits<typename iterator_traits<_BI2>::value_type> - ::has_trivial_assignment_operator _Trivial; - return - std::__copy_backward_dispatch<_BI1, _BI2, _Trivial>::copy(__first, - __last, - __result); + typedef typename iterator_traits<_BI1>::value_type _ValueType1; + typedef typename iterator_traits<_BI2>::value_type _ValueType2; + typedef typename iterator_traits<_BI1>::iterator_category _Category; + const bool __simple = (__is_scalar<_ValueType1>::__value + && __is_pointer<_BI1>::__value + && __is_pointer<_BI2>::__value + && __are_same<_ValueType1, _ValueType2>::__value); + + return std::__copy_backward<__simple, _Category>::__copy_b(__first, + __last, + __result); } - template <typename _BI1, typename _BI2> - inline _BI2 - __copy_backward_output_normal_iterator(_BI1 __first, _BI1 __last, - _BI2 __result, __true_type) - { return _BI2(std::__copy_backward_aux(__first, __last, __result.base())); } + template<bool, bool> + struct __copy_backward_normal + { + template<typename _BI1, typename _BI2> + static _BI2 + __copy_b_n(_BI1 __first, _BI1 __last, _BI2 __result) + { return std::__copy_backward_aux(__first, __last, __result); } + }; - template <typename _BI1, typename _BI2> - inline _BI2 - __copy_backward_output_normal_iterator(_BI1 __first, _BI1 __last, - _BI2 __result, __false_type) - { return std::__copy_backward_aux(__first, __last, __result); } + template<> + struct __copy_backward_normal<true, false> + { + template<typename _BI1, typename _BI2> + static _BI2 + __copy_b_n(_BI1 __first, _BI1 __last, _BI2 __result) + { return std::__copy_backward_aux(__first.base(), __last.base(), + __result); } + }; - template <typename _BI1, typename _BI2> - inline _BI2 - __copy_backward_input_normal_iterator(_BI1 __first, _BI1 __last, - _BI2 __result, __true_type) + template<> + struct __copy_backward_normal<false, true> { - typedef typename _Is_normal_iterator<_BI2>::_Normal __Normal; - return std::__copy_backward_output_normal_iterator(__first.base(), - __last.base(), - __result, __Normal()); - } + template<typename _BI1, typename _BI2> + static _BI2 + __copy_b_n(_BI1 __first, _BI1 __last, _BI2 __result) + { return _BI2(std::__copy_backward_aux(__first, __last, + __result.base())); } + }; - template <typename _BI1, typename _BI2> - inline _BI2 - __copy_backward_input_normal_iterator(_BI1 __first, _BI1 __last, - _BI2 __result, __false_type) + template<> + struct __copy_backward_normal<true, true> { - typedef typename _Is_normal_iterator<_BI2>::_Normal __Normal; - return std::__copy_backward_output_normal_iterator(__first, __last, - __result, __Normal()); - } + template<typename _BI1, typename _BI2> + static _BI2 + __copy_b_n(_BI1 __first, _BI1 __last, _BI2 __result) + { return _BI2(std::__copy_backward_aux(__first.base(), __last.base(), + __result.base())); } + }; /** * @brief Copies the range [first,last) into result. @@ -494,11 +533,39 @@ namespace std typename iterator_traits<_BI2>::value_type>) __glibcxx_requires_valid_range(__first, __last); - typedef typename _Is_normal_iterator<_BI1>::_Normal __Normal; - return std::__copy_backward_input_normal_iterator(__first, __last, - __result, __Normal()); + const bool __bi1 = __is_normal_iterator<_BI1>::__value; + const bool __bi2 = __is_normal_iterator<_BI2>::__value; + return std::__copy_backward_normal<__bi1, __bi2>::__copy_b_n(__first, + __last, + __result); } + template<bool> + struct __fill + { + template<typename _ForwardIterator, typename _Tp> + static void + fill(_ForwardIterator __first, _ForwardIterator __last, + const _Tp& __value) + { + for (; __first != __last; ++__first) + *__first = __value; + } + }; + + template<> + struct __fill<true> + { + template<typename _ForwardIterator, typename _Tp> + static void + fill(_ForwardIterator __first, _ForwardIterator __last, + const _Tp& __value) + { + const _Tp __tmp = __value; + for (; __first != __last; ++__first) + *__first = __tmp; + } + }; /** * @brief Fills the range [first,last) with copies of value. @@ -520,31 +587,8 @@ namespace std _ForwardIterator>) __glibcxx_requires_valid_range(__first, __last); - for ( ; __first != __last; ++__first) - *__first = __value; - } - - /** - * @brief Fills the range [first,first+n) with copies of value. - * @param first An output iterator. - * @param n The count of copies to perform. - * @param value A reference-to-const of arbitrary type. - * @return The iterator at first+n. - * - * This function fills a range with copies of the same value. For one-byte - * types filling contiguous areas of memory, this becomes an inline call to - * @c memset. - */ - template<typename _OutputIterator, typename _Size, typename _Tp> - _OutputIterator - fill_n(_OutputIterator __first, _Size __n, const _Tp& __value) - { - // concept requirements - __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,_Tp>) - - for ( ; __n > 0; --__n, ++__first) - *__first = __value; - return __first; + const bool __scalar = __is_scalar<_Tp>::__value; + std::__fill<__scalar>::fill(__first, __last, __value); } // Specialization: for one-byte types we can use memset. @@ -572,6 +616,55 @@ namespace std std::memset(__first, static_cast<unsigned char>(__tmp), __last - __first); } + template<bool> + struct __fill_n + { + template<typename _OutputIterator, typename _Size, typename _Tp> + static _OutputIterator + fill_n(_OutputIterator __first, _Size __n, const _Tp& __value) + { + for (; __n > 0; --__n, ++__first) + *__first = __value; + return __first; + } + }; + + template<> + struct __fill_n<true> + { + template<typename _OutputIterator, typename _Size, typename _Tp> + static _OutputIterator + fill_n(_OutputIterator __first, _Size __n, const _Tp& __value) + { + const _Tp __tmp = __value; + for (; __n > 0; --__n, ++__first) + *__first = __tmp; + return __first; + } + }; + + /** + * @brief Fills the range [first,first+n) with copies of value. + * @param first An output iterator. + * @param n The count of copies to perform. + * @param value A reference-to-const of arbitrary type. + * @return The iterator at first+n. + * + * This function fills a range with copies of the same value. For one-byte + * types filling contiguous areas of memory, this becomes an inline call to + * @c memset. + */ + template<typename _OutputIterator, typename _Size, typename _Tp> + _OutputIterator + fill_n(_OutputIterator __first, _Size __n, const _Tp& __value) + { + // concept requirements + __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, _Tp>) + + const bool __scalar = __is_scalar<_Tp>::__value; + return std::__fill_n<__scalar>::fill_n(__first, __n, __value); + } + template<typename _Size> inline unsigned char* fill_n(unsigned char* __first, _Size __n, const unsigned char& __c) @@ -582,7 +675,7 @@ namespace std template<typename _Size> inline signed char* - fill_n(char* __first, _Size __n, const signed char& __c) + fill_n(signed char* __first, _Size __n, const signed char& __c) { std::fill(__first, __first + __n, __c); return __first + __n; @@ -596,7 +689,6 @@ namespace std return __first + __n; } - /** * @brief Finds the places in ranges which don't match. * @param first1 An input iterator. @@ -686,8 +778,8 @@ namespace std typename iterator_traits<_InputIterator1>::value_type, typename iterator_traits<_InputIterator2>::value_type>) __glibcxx_requires_valid_range(__first1, __last1); - - for ( ; __first1 != __last1; ++__first1, ++__first2) + + for (; __first1 != __last1; ++__first1, ++__first2) if (!(*__first1 == *__first2)) return false; return true; @@ -718,7 +810,7 @@ namespace std __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) __glibcxx_requires_valid_range(__first1, __last1); - for ( ; __first1 != __last1; ++__first1, ++__first2) + for (; __first1 != __last1; ++__first1, ++__first2) if (!__binary_pred(*__first1, *__first2)) return false; return true; @@ -755,7 +847,8 @@ namespace std __glibcxx_requires_valid_range(__first1, __last1); __glibcxx_requires_valid_range(__first2, __last2); - for (;__first1 != __last1 && __first2 != __last2; ++__first1, ++__first2) + for (; __first1 != __last1 && __first2 != __last2; + ++__first1, ++__first2) { if (*__first1 < *__first2) return true; @@ -790,8 +883,8 @@ namespace std __glibcxx_requires_valid_range(__first1, __last1); __glibcxx_requires_valid_range(__first2, __last2); - for ( ; __first1 != __last1 && __first2 != __last2 - ; ++__first1, ++__first2) + for (; __first1 != __last1 && __first2 != __last2; + ++__first1, ++__first2) { if (__comp(*__first1, *__first2)) return true; @@ -837,6 +930,6 @@ namespace std #endif /* CHAR_MAX == SCHAR_MAX */ } -} // namespace std +_GLIBCXX_END_NAMESPACE #endif |