diff options
Diffstat (limited to 'libstdc++-v3/include/bits/stl_algobase.h')
| -rw-r--r-- | libstdc++-v3/include/bits/stl_algobase.h | 744 |
1 files changed, 491 insertions, 253 deletions
diff --git a/libstdc++-v3/include/bits/stl_algobase.h b/libstdc++-v3/include/bits/stl_algobase.h index fd9592af688..8f194537fd2 100644 --- a/libstdc++-v3/include/bits/stl_algobase.h +++ b/libstdc++-v3/include/bits/stl_algobase.h @@ -1,4 +1,4 @@ -// Bits and pieces used in algorithms -*- C++ -*- +// Core algorithmic facilities -*- C++ -*- // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007 // Free Software Foundation, Inc. @@ -65,39 +65,19 @@ #include <bits/c++config.h> #include <cstddef> #include <bits/functexcept.h> -#include <bits/stl_pair.h> #include <bits/cpp_type_traits.h> #include <ext/type_traits.h> #include <ext/numeric_traits.h> +#include <bits/stl_pair.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> +#include <bits/stl_move.h> // For std::swap and _GLIBCXX_MOVE _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. @@ -110,9 +90,9 @@ _GLIBCXX_BEGIN_NAMESPACE(std) { typedef typename iterator_traits<_ForwardIterator1>::value_type _ValueType1; - _ValueType1 __tmp = *__a; - *__a = *__b; - *__b = __tmp; + _ValueType1 __tmp = _GLIBCXX_MOVE(*__a); + *__a = _GLIBCXX_MOVE(*__b); + *__b = _GLIBCXX_MOVE(__tmp); } }; @@ -186,12 +166,6 @@ _GLIBCXX_BEGIN_NAMESPACE(std) _ForwardIterator1>) __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< _ForwardIterator2>) - __glibcxx_function_requires(_ConvertibleConcept< - typename iterator_traits<_ForwardIterator1>::value_type, - typename iterator_traits<_ForwardIterator2>::value_type>) - __glibcxx_function_requires(_ConvertibleConcept< - typename iterator_traits<_ForwardIterator2>::value_type, - typename iterator_traits<_ForwardIterator1>::value_type>) __glibcxx_requires_valid_range(__first1, __last1); for (; __first1 != __last1; ++__first1, ++__first2) @@ -287,19 +261,37 @@ _GLIBCXX_BEGIN_NAMESPACE(std) // If _Iterator is a __normal_iterator return its base (a plain pointer, // normally) otherwise return it untouched. See copy, fill, ... template<typename _Iterator, - bool _BoolType = __is_normal_iterator<_Iterator>::__value> + bool _IsNormal = __is_normal_iterator<_Iterator>::__value> struct __niter_base { - static const _Iterator& - __b(const _Iterator& __it) + static _Iterator + __b(_Iterator __it) { return __it; } }; template<typename _Iterator> struct __niter_base<_Iterator, true> { - static const typename _Iterator::_Iterator_type& - __b(const _Iterator& __it) + static typename _Iterator::iterator_type + __b(_Iterator __it) + { return __it.base(); } + }; + + // Likewise, for move_iterator. + template<typename _Iterator, + bool _IsMove = __is_move_iterator<_Iterator>::__value> + struct __miter_base + { + static _Iterator + __b(_Iterator __it) + { return __it; } + }; + + template<typename _Iterator> + struct __miter_base<_Iterator, true> + { + static typename _Iterator::iterator_type + __b(_Iterator __it) { return __it.base(); } }; @@ -309,12 +301,12 @@ _GLIBCXX_BEGIN_NAMESPACE(std) // (2) If we're using random access iterators, then write the loop as // a for loop with an explicit count. - template<bool, typename> - struct __copy + template<bool, bool, typename> + struct __copy_move { template<typename _II, typename _OI> static _OI - copy(_II __first, _II __last, _OI __result) + __copy_m(_II __first, _II __last, _OI __result) { for (; __first != __last; ++__result, ++__first) *__result = *__first; @@ -322,12 +314,27 @@ _GLIBCXX_BEGIN_NAMESPACE(std) } }; - template<bool _BoolType> - struct __copy<_BoolType, random_access_iterator_tag> +#ifdef __GXX_EXPERIMENTAL_CXX0X__ + template<typename _Category> + struct __copy_move<true, false, _Category> { template<typename _II, typename _OI> static _OI - copy(_II __first, _II __last, _OI __result) + __copy_m(_II __first, _II __last, _OI __result) + { + for (; __first != __last; ++__result, ++__first) + *__result = std::move(*__first); + return __result; + } + }; +#endif + + template<> + struct __copy_move<false, false, random_access_iterator_tag> + { + template<typename _II, typename _OI> + static _OI + __copy_m(_II __first, _II __last, _OI __result) { typedef typename iterator_traits<_II>::difference_type _Distance; for(_Distance __n = __last - __first; __n > 0; --__n) @@ -340,22 +347,42 @@ _GLIBCXX_BEGIN_NAMESPACE(std) } }; +#ifdef __GXX_EXPERIMENTAL_CXX0X__ template<> - struct __copy<true, random_access_iterator_tag> + struct __copy_move<true, false, random_access_iterator_tag> + { + template<typename _II, typename _OI> + static _OI + __copy_m(_II __first, _II __last, _OI __result) + { + typedef typename iterator_traits<_II>::difference_type _Distance; + for(_Distance __n = __last - __first; __n > 0; --__n) + { + *__result = std::move(*__first); + ++__first; + ++__result; + } + return __result; + } + }; +#endif + + template<bool _IsMove> + struct __copy_move<_IsMove, true, random_access_iterator_tag> { template<typename _Tp> static _Tp* - copy(const _Tp* __first, const _Tp* __last, _Tp* __result) - { + __copy_m(const _Tp* __first, const _Tp* __last, _Tp* __result) + { __builtin_memmove(__result, __first, sizeof(_Tp) * (__last - __first)); return __result + (__last - __first); } }; - template<typename _II, typename _OI> + template<bool _IsMove, typename _II, typename _OI> inline _OI - __copy_aux(_II __first, _II __last, _OI __result) + __copy_move_a(_II __first, _II __last, _OI __result) { typedef typename iterator_traits<_II>::value_type _ValueTypeI; typedef typename iterator_traits<_OI>::value_type _ValueTypeO; @@ -365,7 +392,8 @@ _GLIBCXX_BEGIN_NAMESPACE(std) && __is_pointer<_OI>::__value && __are_same<_ValueTypeI, _ValueTypeO>::__value); - return std::__copy<__simple, _Category>::copy(__first, __last, __result); + return std::__copy_move<_IsMove, __simple, + _Category>::__copy_m(__first, __last, __result); } // Helpers for streambuf iterators (either istream or ostream). @@ -379,23 +407,33 @@ _GLIBCXX_BEGIN_NAMESPACE(std) template<typename _CharT, typename _Traits> class ostreambuf_iterator; - template<typename _CharT> + template<bool _IsMove, typename _CharT> typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value, ostreambuf_iterator<_CharT, char_traits<_CharT> > >::__type - __copy_aux(_CharT*, _CharT*, - ostreambuf_iterator<_CharT, char_traits<_CharT> >); + __copy_move_a2(_CharT*, _CharT*, + ostreambuf_iterator<_CharT, char_traits<_CharT> >); - template<typename _CharT> + template<bool _IsMove, typename _CharT> typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value, ostreambuf_iterator<_CharT, char_traits<_CharT> > >::__type - __copy_aux(const _CharT*, const _CharT*, - ostreambuf_iterator<_CharT, char_traits<_CharT> >); + __copy_move_a2(const _CharT*, const _CharT*, + ostreambuf_iterator<_CharT, char_traits<_CharT> >); - template<typename _CharT> + template<bool _IsMove, typename _CharT> typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value, _CharT*>::__type - __copy_aux(istreambuf_iterator<_CharT, char_traits<_CharT> >, - istreambuf_iterator<_CharT, char_traits<_CharT> >, _CharT*); + __copy_move_a2(istreambuf_iterator<_CharT, char_traits<_CharT> >, + istreambuf_iterator<_CharT, char_traits<_CharT> >, _CharT*); + + template<bool _IsMove, typename _II, typename _OI> + inline _OI + __copy_move_a2(_II __first, _II __last, _OI __result) + { + return _OI(std::__copy_move_a<_IsMove> + (std::__niter_base<_II>::__b(__first), + std::__niter_base<_II>::__b(__last), + std::__niter_base<_OI>::__b(__result))); + } /** * @brief Copies the range [first,last) into result. @@ -423,32 +461,83 @@ _GLIBCXX_BEGIN_NAMESPACE(std) typename iterator_traits<_II>::value_type>) __glibcxx_requires_valid_range(__first, __last); - return _OI(std::__copy_aux(__niter_base<_II>::__b(__first), - __niter_base<_II>::__b(__last), - __niter_base<_OI>::__b(__result))); + return (std::__copy_move_a2<__is_move_iterator<_II>::__value> + (std::__miter_base<_II>::__b(__first), + std::__miter_base<_II>::__b(__last), __result)); + } + +#ifdef __GXX_EXPERIMENTAL_CXX0X__ + /** + * @brief Moves the range [first,last) into result. + * @param first An input iterator. + * @param last An input iterator. + * @param result An output iterator. + * @return result + (first - last) + * + * This inline function will boil down to a call to @c memmove whenever + * possible. Failing that, if random access iterators are passed, then the + * loop count will be known (and therefore a candidate for compiler + * optimizations such as unrolling). Result may not be contained within + * [first,last); the move_backward function should be used instead. + * + * Note that the end of the output range is permitted to be contained + * within [first,last). + */ + template<typename _II, typename _OI> + inline _OI + move(_II __first, _II __last, _OI __result) + { + // concept requirements + __glibcxx_function_requires(_InputIteratorConcept<_II>) + __glibcxx_function_requires(_OutputIteratorConcept<_OI, + typename iterator_traits<_II>::value_type>) + __glibcxx_requires_valid_range(__first, __last); + + return (std::__copy_move_a2<true> + (std::__miter_base<_II>::__b(__first), + std::__miter_base<_II>::__b(__last), __result)); } +#define _GLIBCXX_MOVE3(_Tp, _Up, _Vp) std::move(_Tp, _Up, _Vp) +#else +#define _GLIBCXX_MOVE3(_Tp, _Up, _Vp) std::copy(_Tp, _Up, _Vp) +#endif - template<bool, typename> - struct __copy_backward + template<bool, bool, typename> + struct __copy_move_backward { template<typename _BI1, typename _BI2> static _BI2 - __copy_b(_BI1 __first, _BI1 __last, _BI2 __result) - { + __copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result) + { while (__first != __last) *--__result = *--__last; return __result; } }; - template<bool _BoolType> - struct __copy_backward<_BoolType, random_access_iterator_tag> +#ifdef __GXX_EXPERIMENTAL_CXX0X__ + template<typename _Category> + struct __copy_move_backward<true, false, _Category> { template<typename _BI1, typename _BI2> static _BI2 - __copy_b(_BI1 __first, _BI1 __last, _BI2 __result) - { + __copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result) + { + while (__first != __last) + *--__result = std::move(*--__last); + return __result; + } + }; +#endif + + template<> + struct __copy_move_backward<false, false, random_access_iterator_tag> + { + template<typename _BI1, typename _BI2> + static _BI2 + __copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result) + { typename iterator_traits<_BI1>::difference_type __n; for (__n = __last - __first; __n > 0; --__n) *--__result = *--__last; @@ -456,22 +545,38 @@ _GLIBCXX_BEGIN_NAMESPACE(std) } }; +#ifdef __GXX_EXPERIMENTAL_CXX0X__ template<> - struct __copy_backward<true, random_access_iterator_tag> + struct __copy_move_backward<true, false, random_access_iterator_tag> + { + template<typename _BI1, typename _BI2> + static _BI2 + __copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result) + { + typename iterator_traits<_BI1>::difference_type __n; + for (__n = __last - __first; __n > 0; --__n) + *--__result = std::move(*--__last); + return __result; + } + }; +#endif + + template<bool _IsMove> + struct __copy_move_backward<_IsMove, true, random_access_iterator_tag> { template<typename _Tp> static _Tp* - __copy_b(const _Tp* __first, const _Tp* __last, _Tp* __result) - { + __copy_move_b(const _Tp* __first, const _Tp* __last, _Tp* __result) + { const ptrdiff_t _Num = __last - __first; __builtin_memmove(__result - _Num, __first, sizeof(_Tp) * _Num); return __result - _Num; } }; - template<typename _BI1, typename _BI2> + template<bool _IsMove, typename _BI1, typename _BI2> inline _BI2 - __copy_backward_aux(_BI1 __first, _BI1 __last, _BI2 __result) + __copy_move_backward_a(_BI1 __first, _BI1 __last, _BI2 __result) { typedef typename iterator_traits<_BI1>::value_type _ValueType1; typedef typename iterator_traits<_BI2>::value_type _ValueType2; @@ -481,11 +586,22 @@ _GLIBCXX_BEGIN_NAMESPACE(std) && __is_pointer<_BI2>::__value && __are_same<_ValueType1, _ValueType2>::__value); - return std::__copy_backward<__simple, _Category>::__copy_b(__first, + return std::__copy_move_backward<_IsMove, __simple, + _Category>::__copy_move_b(__first, __last, __result); } + template<bool _IsMove, typename _BI1, typename _BI2> + inline _BI2 + __copy_move_backward_a2(_BI1 __first, _BI1 __last, _BI2 __result) + { + return _BI2(std::__copy_move_backward_a<_IsMove> + (std::__niter_base<_BI1>::__b(__first), + std::__niter_base<_BI1>::__b(__last), + std::__niter_base<_BI2>::__b(__result))); + } + /** * @brief Copies the range [first,last) into result. * @param first A bidirectional iterator. @@ -503,7 +619,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) * Result may not be in the range [first,last). Use copy instead. Note * that the start of the output range may overlap [first,last). */ - template <typename _BI1, typename _BI2> + template<typename _BI1, typename _BI2> inline _BI2 copy_backward(_BI1 __first, _BI1 __last, _BI2 __result) { @@ -515,62 +631,77 @@ _GLIBCXX_BEGIN_NAMESPACE(std) typename iterator_traits<_BI2>::value_type>) __glibcxx_requires_valid_range(__first, __last); - return _BI2(std::__copy_backward_aux(__niter_base<_BI1>::__b(__first), - __niter_base<_BI1>::__b(__last), - __niter_base<_BI2>::__b(__result))); + return (std::__copy_move_backward_a2<__is_move_iterator<_BI1>::__value> + (std::__miter_base<_BI1>::__b(__first), + std::__miter_base<_BI1>::__b(__last), __result)); } - - template<bool> - struct __fill +#ifdef __GXX_EXPERIMENTAL_CXX0X__ + /** + * @brief Moves the range [first,last) into result. + * @param first A bidirectional iterator. + * @param last A bidirectional iterator. + * @param result A bidirectional iterator. + * @return result - (first - last) + * + * The function has the same effect as move, but starts at the end of the + * range and works its way to the start, returning the start of the result. + * This inline function will boil down to a call to @c memmove whenever + * possible. Failing that, if random access iterators are passed, then the + * loop count will be known (and therefore a candidate for compiler + * optimizations such as unrolling). + * + * Result may not be in the range [first,last). Use move instead. Note + * that the start of the output range may overlap [first,last). + */ + template<typename _BI1, typename _BI2> + inline _BI2 + move_backward(_BI1 __first, _BI1 __last, _BI2 __result) { - template<typename _ForwardIterator, typename _Tp> - static void - fill(_ForwardIterator __first, _ForwardIterator __last, - const _Tp& __value) - { - for (; __first != __last; ++__first) - *__first = __value; - } - }; + // concept requirements + __glibcxx_function_requires(_BidirectionalIteratorConcept<_BI1>) + __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<_BI2>) + __glibcxx_function_requires(_ConvertibleConcept< + typename iterator_traits<_BI1>::value_type, + typename iterator_traits<_BI2>::value_type>) + __glibcxx_requires_valid_range(__first, __last); - 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; - } - }; + return (std::__copy_move_backward_a2<true> + (std::__miter_base<_BI1>::__b(__first), + std::__miter_base<_BI1>::__b(__last), __result)); + } + +#define _GLIBCXX_MOVE_BACKWARD3(_Tp, _Up, _Vp) std::move_backward(_Tp, _Up, _Vp) +#else +#define _GLIBCXX_MOVE_BACKWARD3(_Tp, _Up, _Vp) std::copy_backward(_Tp, _Up, _Vp) +#endif template<typename _ForwardIterator, typename _Tp> - inline void - __fill_aux(_ForwardIterator __first, _ForwardIterator __last, - const _Tp& __value) + inline typename + __gnu_cxx::__enable_if<!__is_scalar<_Tp>::__value, void>::__type + __fill_a(_ForwardIterator __first, _ForwardIterator __last, + const _Tp& __value) { - const bool __scalar = __is_scalar<_Tp>::__value; - std::__fill<__scalar>::fill(__first, __last, __value); + for (; __first != __last; ++__first) + *__first = __value; + } + + template<typename _ForwardIterator, typename _Tp> + inline typename + __gnu_cxx::__enable_if<__is_scalar<_Tp>::__value, void>::__type + __fill_a(_ForwardIterator __first, _ForwardIterator __last, _Tp __value) + { + for (; __first != __last; ++__first) + *__first = __value; } // Specialization: for char types we can use memset. - inline void - __fill_aux(unsigned char* __first, unsigned char* __last, unsigned char __c) - { __builtin_memset(__first, __c, __last - __first); } - - inline void - __fill_aux(signed char* __first, signed char* __last, signed char __c) - { __builtin_memset(__first, static_cast<unsigned char>(__c), - __last - __first); } - - inline void - __fill_aux(char* __first, char* __last, char __c) - { __builtin_memset(__first, static_cast<unsigned char>(__c), - __last - __first); } + template<typename _Tp> + inline typename + __gnu_cxx::__enable_if<__is_byte<_Tp>::__value, void>::__type + __fill_a(_Tp* __first, _Tp* __last, _Tp __c) + { __builtin_memset(__first, static_cast<unsigned char>(__c), + __last - __first); } /** * @brief Fills the range [first,last) with copies of value. @@ -592,67 +723,36 @@ _GLIBCXX_BEGIN_NAMESPACE(std) _ForwardIterator>) __glibcxx_requires_valid_range(__first, __last); - std::__fill_aux(__niter_base<_ForwardIterator>::__b(__first), - __niter_base<_ForwardIterator>::__b(__last), __value); + std::__fill_a(std::__niter_base<_ForwardIterator>::__b(__first), + std::__niter_base<_ForwardIterator>::__b(__last), __value); } - - 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; - } - }; - template<typename _OutputIterator, typename _Size, typename _Tp> - inline _OutputIterator - __fill_n_aux(_OutputIterator __first, _Size __n, const _Tp& __value) + inline typename + __gnu_cxx::__enable_if<!__is_scalar<_Tp>::__value, _OutputIterator>::__type + __fill_n_a(_OutputIterator __first, _Size __n, const _Tp& __value) { - const bool __scalar = __is_scalar<_Tp>::__value; - return std::__fill_n<__scalar>::fill_n(__first, __n, __value); + for (; __n > 0; --__n, ++__first) + *__first = __value; + return __first; } - template<typename _Size> - inline unsigned char* - __fill_n_aux(unsigned char* __first, _Size __n, unsigned char __c) - { - std::__fill_aux(__first, __first + __n, __c); - return __first + __n; - } - - template<typename _Size> - inline signed char* - __fill_n_aux(signed char* __first, _Size __n, signed char __c) + template<typename _OutputIterator, typename _Size, typename _Tp> + inline typename + __gnu_cxx::__enable_if<__is_scalar<_Tp>::__value, _OutputIterator>::__type + __fill_n_a(_OutputIterator __first, _Size __n, _Tp __value) { - std::__fill_aux(__first, __first + __n, __c); - return __first + __n; + for (; __n > 0; --__n, ++__first) + *__first = __value; + return __first; } - template<typename _Size> - inline char* - __fill_n_aux(char* __first, _Size __n, char __c) + template<typename _Size, typename _Tp> + inline typename + __gnu_cxx::__enable_if<__is_byte<_Tp>::__value, _Tp*>::__type + __fill_n_a(_Tp* __first, _Size __n, _Tp __c) { - std::__fill_aux(__first, __first + __n, __c); + std::__fill_a(__first, __first + __n, __c); return __first + __n; } @@ -674,11 +774,10 @@ _GLIBCXX_BEGIN_NAMESPACE(std) // concept requirements __glibcxx_function_requires(_OutputIteratorConcept<_OI, _Tp>) - return _OI(std::__fill_n_aux(__niter_base<_OI>::__b(__first), __n, - __value)); + return _OI(std::__fill_n_a(std::__niter_base<_OI>::__b(__first), + __n, __value)); } - template<bool _BoolType> struct __equal { @@ -719,6 +818,110 @@ _GLIBCXX_BEGIN_NAMESPACE(std) return std::__equal<__simple>::equal(__first1, __last1, __first2); } + + template<typename, typename> + struct __lc_rai + { + template<typename _II1, typename _II2> + static _II1 + __newlast1(_II1, _II1 __last1, _II2, _II2) + { return __last1; } + + template<typename _II> + static bool + __cnd2(_II __first, _II __last) + { return __first != __last; } + }; + + template<> + struct __lc_rai<random_access_iterator_tag, random_access_iterator_tag> + { + template<typename _RAI1, typename _RAI2> + static _RAI1 + __newlast1(_RAI1 __first1, _RAI1 __last1, + _RAI2 __first2, _RAI2 __last2) + { + const typename iterator_traits<_RAI1>::difference_type + __diff1 = __last1 - __first1; + const typename iterator_traits<_RAI2>::difference_type + __diff2 = __last2 - __first2; + return __diff2 < __diff1 ? __first1 + __diff2 : __last1; + } + + template<typename _RAI> + static bool + __cnd2(_RAI, _RAI) + { return true; } + }; + + template<bool _BoolType> + struct __lexicographical_compare + { + template<typename _II1, typename _II2> + static bool __lc(_II1, _II1, _II2, _II2); + }; + + template<bool _BoolType> + template<typename _II1, typename _II2> + bool + __lexicographical_compare<_BoolType>:: + __lc(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2) + { + typedef typename iterator_traits<_II1>::iterator_category _Category1; + typedef typename iterator_traits<_II2>::iterator_category _Category2; + typedef std::__lc_rai<_Category1, _Category2> __rai_type; + + __last1 = __rai_type::__newlast1(__first1, __last1, + __first2, __last2); + for (; __first1 != __last1 && __rai_type::__cnd2(__first2, __last2); + ++__first1, ++__first2) + { + if (*__first1 < *__first2) + return true; + if (*__first2 < *__first1) + return false; + } + return __first1 == __last1 && __first2 != __last2; + } + + template<> + struct __lexicographical_compare<true> + { + template<typename _Tp, typename _Up> + static bool + __lc(const _Tp* __first1, const _Tp* __last1, + const _Up* __first2, const _Up* __last2) + { + const size_t __len1 = __last1 - __first1; + const size_t __len2 = __last2 - __first2; + const int __result = __builtin_memcmp(__first1, __first2, + std::min(__len1, __len2)); + return __result != 0 ? __result < 0 : __len1 < __len2; + } + }; + + template<typename _II1, typename _II2> + inline bool + __lexicographical_compare_aux(_II1 __first1, _II1 __last1, + _II2 __first2, _II2 __last2) + { + typedef typename iterator_traits<_II1>::value_type _ValueType1; + typedef typename iterator_traits<_II2>::value_type _ValueType2; + const bool __simple = + (__is_byte<_ValueType1>::__value && __is_byte<_ValueType2>::__value + && !__gnu_cxx::__numeric_traits<_ValueType1>::__is_signed + && !__gnu_cxx::__numeric_traits<_ValueType2>::__is_signed + && __is_pointer<_II1>::__value + && __is_pointer<_II2>::__value); + + return std::__lexicographical_compare<__simple>::__lc(__first1, __last1, + __first2, __last2); + } + +_GLIBCXX_END_NAMESPACE + +_GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_P) + /** * @brief Tests a range for element-wise equality. * @param first1 An input iterator. @@ -742,9 +945,9 @@ _GLIBCXX_BEGIN_NAMESPACE(std) typename iterator_traits<_II2>::value_type>) __glibcxx_requires_valid_range(__first1, __last1); - return std::__equal_aux(__niter_base<_II1>::__b(__first1), - __niter_base<_II1>::__b(__last1), - __niter_base<_II2>::__b(__first2)); + return std::__equal_aux(std::__niter_base<_II1>::__b(__first1), + std::__niter_base<_II1>::__b(__last1), + std::__niter_base<_II2>::__b(__first2)); } /** @@ -752,24 +955,23 @@ _GLIBCXX_BEGIN_NAMESPACE(std) * @param first1 An input iterator. * @param last1 An input iterator. * @param first2 An input iterator. - * @param binary_pred A binary predicate @link s20_3_1_base functor@endlink. - * @return A boolean true or false. + * @param binary_pred A binary predicate @link s20_3_1_base + * functor@endlink. + * @return A boolean true or false. * * This compares the elements of two ranges using the binary_pred * parameter, and returns true or * false depending on whether all of the corresponding elements of the * ranges are equal. */ - template<typename _InputIterator1, typename _InputIterator2, - typename _BinaryPredicate> + template<typename _IIter1, typename _IIter2, typename _BinaryPredicate> inline bool - equal(_InputIterator1 __first1, _InputIterator1 __last1, - _InputIterator2 __first2, - _BinaryPredicate __binary_pred) + equal(_IIter1 __first1, _IIter1 __last1, + _IIter2 __first2, _BinaryPredicate __binary_pred) { // concept requirements - __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) - __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) + __glibcxx_function_requires(_InputIteratorConcept<_IIter1>) + __glibcxx_function_requires(_InputIteratorConcept<_IIter2>) __glibcxx_requires_valid_range(__first1, __last1); for (; __first1 != __last1; ++__first1, ++__first2) @@ -792,32 +994,26 @@ _GLIBCXX_BEGIN_NAMESPACE(std) * (Quoted from [25.3.8]/1.) If the iterators are all character pointers, * then this is an inline call to @c memcmp. */ - template<typename _InputIterator1, typename _InputIterator2> - bool - lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1, - _InputIterator2 __first2, _InputIterator2 __last2) + template<typename _II1, typename _II2> + inline bool + lexicographical_compare(_II1 __first1, _II1 __last1, + _II2 __first2, _II2 __last2) { // concept requirements - __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) - __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) - __glibcxx_function_requires(_LessThanOpConcept< - typename iterator_traits<_InputIterator1>::value_type, - typename iterator_traits<_InputIterator2>::value_type>) - __glibcxx_function_requires(_LessThanOpConcept< - typename iterator_traits<_InputIterator2>::value_type, - typename iterator_traits<_InputIterator1>::value_type>) + typedef typename iterator_traits<_II1>::value_type _ValueType1; + typedef typename iterator_traits<_II2>::value_type _ValueType2; + __glibcxx_function_requires(_InputIteratorConcept<_II1>) + __glibcxx_function_requires(_InputIteratorConcept<_II2>) + __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>) + __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>) __glibcxx_requires_valid_range(__first1, __last1); __glibcxx_requires_valid_range(__first2, __last2); - for (; __first1 != __last1 && __first2 != __last2; - ++__first1, ++__first2) - { - if (*__first1 < *__first2) - return true; - if (*__first2 < *__first1) - return false; - } - return __first1 == __last1 && __first2 != __last2; + return std::__lexicographical_compare_aux + (std::__niter_base<_II1>::__b(__first1), + std::__niter_base<_II1>::__b(__last1), + std::__niter_base<_II2>::__b(__first2), + std::__niter_base<_II2>::__b(__last2)); } /** @@ -829,23 +1025,26 @@ _GLIBCXX_BEGIN_NAMESPACE(std) * @param comp A @link s20_3_3_comparisons comparison functor@endlink. * @return A boolean true or false. * - * The same as the four-parameter @c lexigraphical_compare, but uses the + * The same as the four-parameter @c lexicographical_compare, but uses the * comp parameter instead of @c <. */ - template<typename _InputIterator1, typename _InputIterator2, - typename _Compare> + template<typename _II1, typename _II2, typename _Compare> bool - lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1, - _InputIterator2 __first2, _InputIterator2 __last2, - _Compare __comp) + lexicographical_compare(_II1 __first1, _II1 __last1, + _II2 __first2, _II2 __last2, _Compare __comp) { + typedef typename iterator_traits<_II1>::iterator_category _Category1; + typedef typename iterator_traits<_II2>::iterator_category _Category2; + typedef std::__lc_rai<_Category1, _Category2> __rai_type; + // concept requirements - __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) - __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) + __glibcxx_function_requires(_InputIteratorConcept<_II1>) + __glibcxx_function_requires(_InputIteratorConcept<_II2>) __glibcxx_requires_valid_range(__first1, __last1); __glibcxx_requires_valid_range(__first2, __last2); - for (; __first1 != __last1 && __first2 != __last2; + __last1 = __rai_type::__newlast1(__first1, __last1, __first2, __last2); + for (; __first1 != __last1 && __rai_type::__cnd2(__first2, __last2); ++__first1, ++__first2) { if (__comp(*__first1, *__first2)) @@ -856,41 +1055,80 @@ _GLIBCXX_BEGIN_NAMESPACE(std) return __first1 == __last1 && __first2 != __last2; } - inline bool - lexicographical_compare(const unsigned char* __first1, - const unsigned char* __last1, - const unsigned char* __first2, - const unsigned char* __last2) - { - __glibcxx_requires_valid_range(__first1, __last1); - __glibcxx_requires_valid_range(__first2, __last2); - - const size_t __len1 = __last1 - __first1; - const size_t __len2 = __last2 - __first2; - const int __result = __builtin_memcmp(__first1, __first2, - std::min(__len1, __len2)); - return __result != 0 ? __result < 0 : __len1 < __len2; - } - - inline bool - lexicographical_compare(const char* __first1, const char* __last1, - const char* __first2, const char* __last2) - { - __glibcxx_requires_valid_range(__first1, __last1); - __glibcxx_requires_valid_range(__first2, __last2); - - if (__gnu_cxx::__numeric_traits<char>::__is_signed) - return std::lexicographical_compare((const signed char*) __first1, - (const signed char*) __last1, - (const signed char*) __first2, - (const signed char*) __last2); - else - return std::lexicographical_compare((const unsigned char*) __first1, - (const unsigned char*) __last1, - (const unsigned char*) __first2, - (const unsigned char*) __last2); - } + /** + * @brief Finds the places in ranges which don't match. + * @param first1 An input iterator. + * @param last1 An input iterator. + * @param first2 An input iterator. + * @return A pair of iterators pointing to the first mismatch. + * + * This compares the elements of two ranges using @c == and returns a pair + * of iterators. The first iterator points into the first range, the + * second iterator points into the second range, and the elements pointed + * to by the iterators are not equal. + */ + template<typename _InputIterator1, typename _InputIterator2> + pair<_InputIterator1, _InputIterator2> + mismatch(_InputIterator1 __first1, _InputIterator1 __last1, + _InputIterator2 __first2) + { + // concept requirements + __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) + __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) + __glibcxx_function_requires(_EqualOpConcept< + typename iterator_traits<_InputIterator1>::value_type, + typename iterator_traits<_InputIterator2>::value_type>) + __glibcxx_requires_valid_range(__first1, __last1); + + while (__first1 != __last1 && *__first1 == *__first2) + { + ++__first1; + ++__first2; + } + return pair<_InputIterator1, _InputIterator2>(__first1, __first2); + } + + /** + * @brief Finds the places in ranges which don't match. + * @param first1 An input iterator. + * @param last1 An input iterator. + * @param first2 An input iterator. + * @param binary_pred A binary predicate @link s20_3_1_base + * functor@endlink. + * @return A pair of iterators pointing to the first mismatch. + * + * This compares the elements of two ranges using the binary_pred + * parameter, and returns a pair + * of iterators. The first iterator points into the first range, the + * second iterator points into the second range, and the elements pointed + * to by the iterators are not equal. + */ + template<typename _InputIterator1, typename _InputIterator2, + typename _BinaryPredicate> + pair<_InputIterator1, _InputIterator2> + mismatch(_InputIterator1 __first1, _InputIterator1 __last1, + _InputIterator2 __first2, _BinaryPredicate __binary_pred) + { + // concept requirements + __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) + __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) + __glibcxx_requires_valid_range(__first1, __last1); -_GLIBCXX_END_NAMESPACE + while (__first1 != __last1 && bool(__binary_pred(*__first1, *__first2))) + { + ++__first1; + ++__first2; + } + return pair<_InputIterator1, _InputIterator2>(__first1, __first2); + } + +_GLIBCXX_END_NESTED_NAMESPACE + +// NB: This file is included within many other C++ includes, as a way +// of getting the base algorithms. So, make sure that parallel bits +// come in too if requested. +#ifdef _GLIBCXX_PARALLEL +# include <parallel/algobase.h> +#endif #endif |