diff options
Diffstat (limited to 'contrib/libstdc++/include/bits/stl_algo.h')
| -rw-r--r-- | contrib/libstdc++/include/bits/stl_algo.h | 914 |
1 files changed, 635 insertions, 279 deletions
diff --git a/contrib/libstdc++/include/bits/stl_algo.h b/contrib/libstdc++/include/bits/stl_algo.h index 74956d75b4d5..cf3cd71851a0 100644 --- a/contrib/libstdc++/include/bits/stl_algo.h +++ b/contrib/libstdc++/include/bits/stl_algo.h @@ -1,6 +1,7 @@ // Algorithm implementation -*- C++ -*- -// Copyright (C) 2001, 2002, 2003, 2004 Free Software Foundation, Inc. +// Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006 +// 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 @@ -67,8 +68,8 @@ // See concept_check.h for the __glibcxx_*_requires macros. -namespace std -{ +_GLIBCXX_BEGIN_NAMESPACE(std) + /** * @brief Find the median of three values. * @param a A value. @@ -166,8 +167,8 @@ namespace std */ template<typename _InputIterator, typename _Tp> inline _InputIterator - find(_InputIterator __first, _InputIterator __last, - const _Tp& __val, input_iterator_tag) + __find(_InputIterator __first, _InputIterator __last, + const _Tp& __val, input_iterator_tag) { while (__first != __last && !(*__first == __val)) ++__first; @@ -181,8 +182,8 @@ namespace std */ template<typename _InputIterator, typename _Predicate> inline _InputIterator - find_if(_InputIterator __first, _InputIterator __last, - _Predicate __pred, input_iterator_tag) + __find_if(_InputIterator __first, _InputIterator __last, + _Predicate __pred, input_iterator_tag) { while (__first != __last && !__pred(*__first)) ++__first; @@ -196,8 +197,8 @@ namespace std */ template<typename _RandomAccessIterator, typename _Tp> _RandomAccessIterator - find(_RandomAccessIterator __first, _RandomAccessIterator __last, - const _Tp& __val, random_access_iterator_tag) + __find(_RandomAccessIterator __first, _RandomAccessIterator __last, + const _Tp& __val, random_access_iterator_tag) { typename iterator_traits<_RandomAccessIterator>::difference_type __trip_count = (__last - __first) >> 2; @@ -248,8 +249,8 @@ namespace std */ template<typename _RandomAccessIterator, typename _Predicate> _RandomAccessIterator - find_if(_RandomAccessIterator __first, _RandomAccessIterator __last, - _Predicate __pred, random_access_iterator_tag) + __find_if(_RandomAccessIterator __first, _RandomAccessIterator __last, + _Predicate __pred, random_access_iterator_tag) { typename iterator_traits<_RandomAccessIterator>::difference_type __trip_count = (__last - __first) >> 2; @@ -294,6 +295,17 @@ namespace std } /** + * @if maint + * This is an overload of find() for streambuf iterators. + * @endif + */ + template<typename _CharT> + typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value, + istreambuf_iterator<_CharT> >::__type + find(istreambuf_iterator<_CharT>, istreambuf_iterator<_CharT>, + const _CharT&); + + /** * @brief Find the first occurrence of a value in a sequence. * @param first An input iterator. * @param last An input iterator. @@ -311,8 +323,8 @@ namespace std __glibcxx_function_requires(_EqualOpConcept< typename iterator_traits<_InputIterator>::value_type, _Tp>) __glibcxx_requires_valid_range(__first, __last); - return std::find(__first, __last, __val, - std::__iterator_category(__first)); + return std::__find(__first, __last, __val, + std::__iterator_category(__first)); } /** @@ -333,8 +345,8 @@ namespace std __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, typename iterator_traits<_InputIterator>::value_type>) __glibcxx_requires_valid_range(__first, __last); - return std::find_if(__first, __last, __pred, - std::__iterator_category(__first)); + return std::__find_if(__first, __last, __pred, + std::__iterator_category(__first)); } /** @@ -413,9 +425,8 @@ namespace std { // concept requirements __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) - __glibcxx_function_requires(_EqualityComparableConcept< - typename iterator_traits<_InputIterator>::value_type >) - __glibcxx_function_requires(_EqualityComparableConcept<_Tp>) + __glibcxx_function_requires(_EqualOpConcept< + typename iterator_traits<_InputIterator>::value_type, _Tp>) __glibcxx_requires_valid_range(__first, __last); typename iterator_traits<_InputIterator>::difference_type __n = 0; for ( ; __first != __last; ++__first) @@ -608,6 +619,92 @@ namespace std } /** + * @if maint + * This is an uglified + * search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&) + * overloaded for forward iterators. + * @endif + */ + template<typename _ForwardIterator, typename _Integer, typename _Tp> + _ForwardIterator + __search_n(_ForwardIterator __first, _ForwardIterator __last, + _Integer __count, const _Tp& __val, + std::forward_iterator_tag) + { + __first = std::find(__first, __last, __val); + while (__first != __last) + { + typename iterator_traits<_ForwardIterator>::difference_type + __n = __count; + _ForwardIterator __i = __first; + ++__i; + while (__i != __last && __n != 1 && *__i == __val) + { + ++__i; + --__n; + } + if (__n == 1) + return __first; + if (__i == __last) + return __last; + __first = std::find(++__i, __last, __val); + } + return __last; + } + + /** + * @if maint + * This is an uglified + * search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&) + * overloaded for random access iterators. + * @endif + */ + template<typename _RandomAccessIter, typename _Integer, typename _Tp> + _RandomAccessIter + __search_n(_RandomAccessIter __first, _RandomAccessIter __last, + _Integer __count, const _Tp& __val, + std::random_access_iterator_tag) + { + + typedef typename std::iterator_traits<_RandomAccessIter>::difference_type + _DistanceType; + + _DistanceType __tailSize = __last - __first; + const _DistanceType __pattSize = __count; + + if (__tailSize < __pattSize) + return __last; + + const _DistanceType __skipOffset = __pattSize - 1; + _RandomAccessIter __lookAhead = __first + __skipOffset; + __tailSize -= __pattSize; + + while (1) // the main loop... + { + // __lookAhead here is always pointing to the last element of next + // possible match. + while (!(*__lookAhead == __val)) // the skip loop... + { + if (__tailSize < __pattSize) + return __last; // Failure + __lookAhead += __pattSize; + __tailSize -= __pattSize; + } + _DistanceType __remainder = __skipOffset; + for (_RandomAccessIter __backTrack = __lookAhead - 1; + *__backTrack == __val; --__backTrack) + { + if (--__remainder == 0) + return (__lookAhead - __skipOffset); // Success + } + if (__remainder > __tailSize) + return __last; // Failure + __lookAhead += __remainder; + __tailSize -= __remainder; + } + } + + /** * @brief Search a sequence for a number of consecutive values. * @param first A forward iterator. * @param last A forward iterator. @@ -627,33 +724,109 @@ namespace std { // concept requirements __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) - __glibcxx_function_requires(_EqualityComparableConcept< - typename iterator_traits<_ForwardIterator>::value_type>) - __glibcxx_function_requires(_EqualityComparableConcept<_Tp>) + __glibcxx_function_requires(_EqualOpConcept< + typename iterator_traits<_ForwardIterator>::value_type, _Tp>) __glibcxx_requires_valid_range(__first, __last); if (__count <= 0) return __first; - else + if (__count == 1) + return std::find(__first, __last, __val); + return std::__search_n(__first, __last, __count, __val, + std::__iterator_category(__first)); + } + + /** + * @if maint + * This is an uglified + * search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&, + * _BinaryPredicate) + * overloaded for forward iterators. + * @endif + */ + template<typename _ForwardIterator, typename _Integer, typename _Tp, + typename _BinaryPredicate> + _ForwardIterator + __search_n(_ForwardIterator __first, _ForwardIterator __last, + _Integer __count, const _Tp& __val, + _BinaryPredicate __binary_pred, std::forward_iterator_tag) + { + while (__first != __last && !__binary_pred(*__first, __val)) + ++__first; + + while (__first != __last) { - __first = std::find(__first, __last, __val); - while (__first != __last) + typename iterator_traits<_ForwardIterator>::difference_type + __n = __count; + _ForwardIterator __i = __first; + ++__i; + while (__i != __last && __n != 1 && __binary_pred(*__i, __val)) { - typename iterator_traits<_ForwardIterator>::difference_type - __n = __count; - _ForwardIterator __i = __first; ++__i; - while (__i != __last && __n != 1 && *__i == __val) - { - ++__i; - --__n; - } - if (__n == 1) - return __first; - else - __first = std::find(__i, __last, __val); + --__n; } - return __last; + if (__n == 1) + return __first; + if (__i == __last) + return __last; + __first = ++__i; + while (__first != __last && !__binary_pred(*__first, __val)) + ++__first; + } + return __last; + } + + /** + * @if maint + * This is an uglified + * search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&, + * _BinaryPredicate) + * overloaded for random access iterators. + * @endif + */ + template<typename _RandomAccessIter, typename _Integer, typename _Tp, + typename _BinaryPredicate> + _RandomAccessIter + __search_n(_RandomAccessIter __first, _RandomAccessIter __last, + _Integer __count, const _Tp& __val, + _BinaryPredicate __binary_pred, std::random_access_iterator_tag) + { + + typedef typename std::iterator_traits<_RandomAccessIter>::difference_type + _DistanceType; + + _DistanceType __tailSize = __last - __first; + const _DistanceType __pattSize = __count; + + if (__tailSize < __pattSize) + return __last; + + const _DistanceType __skipOffset = __pattSize - 1; + _RandomAccessIter __lookAhead = __first + __skipOffset; + __tailSize -= __pattSize; + + while (1) // the main loop... + { + // __lookAhead here is always pointing to the last element of next + // possible match. + while (!__binary_pred(*__lookAhead, __val)) // the skip loop... + { + if (__tailSize < __pattSize) + return __last; // Failure + __lookAhead += __pattSize; + __tailSize -= __pattSize; + } + _DistanceType __remainder = __skipOffset; + for (_RandomAccessIter __backTrack = __lookAhead - 1; + __binary_pred(*__backTrack, __val); --__backTrack) + { + if (--__remainder == 0) + return (__lookAhead - __skipOffset); // Success + } + if (__remainder > __tailSize) + return __last; // Failure + __lookAhead += __remainder; + __tailSize -= __remainder; } } @@ -687,40 +860,14 @@ namespace std if (__count <= 0) return __first; - else + if (__count == 1) { - while (__first != __last) - { - if (__binary_pred(*__first, __val)) - break; - ++__first; - } - while (__first != __last) - { - typename iterator_traits<_ForwardIterator>::difference_type - __n = __count; - _ForwardIterator __i = __first; - ++__i; - while (__i != __last && __n != 1 && __binary_pred(*__i, __val)) - { - ++__i; - --__n; - } - if (__n == 1) - return __first; - else - { - while (__i != __last) - { - if (__binary_pred(*__i, __val)) - break; - ++__i; - } - __first = __i; - } - } - return __last; + while (__first != __last && !__binary_pred(*__first, __val)) + ++__first; + return __first; } + return std::__search_n(__first, __last, __count, __val, __binary_pred, + std::__iterator_category(__first)); } /** @@ -918,7 +1065,10 @@ namespace std __glibcxx_requires_valid_range(__first, __last); for ( ; __first != __last; ++__first, ++__result) - *__result = *__first == __old_value ? __new_value : *__first; + if (*__first == __old_value) + *__result = __new_value; + else + *__result = *__first; return __result; } @@ -952,7 +1102,10 @@ namespace std __glibcxx_requires_valid_range(__first, __last); for ( ; __first != __last; ++__first, ++__result) - *__result = __pred(*__first) ? __new_value : *__first; + if (__pred(*__first)) + *__result = __new_value; + else + *__result = *__first; return __result; } @@ -1153,14 +1306,39 @@ namespace std * @if maint * This is an uglified unique_copy(_InputIterator, _InputIterator, * _OutputIterator) - * overloaded for output iterators. + * overloaded for forward iterators and output iterator as result. + * @endif + */ + template<typename _ForwardIterator, typename _OutputIterator> + _OutputIterator + __unique_copy(_ForwardIterator __first, _ForwardIterator __last, + _OutputIterator __result, + forward_iterator_tag, output_iterator_tag) + { + // concept requirements -- taken care of in dispatching function + _ForwardIterator __next = __first; + *__result = *__first; + while (++__next != __last) + if (!(*__first == *__next)) + { + __first = __next; + *++__result = *__first; + } + return ++__result; + } + + /** + * @if maint + * This is an uglified unique_copy(_InputIterator, _InputIterator, + * _OutputIterator) + * overloaded for input iterators and output iterator as result. * @endif */ template<typename _InputIterator, typename _OutputIterator> _OutputIterator __unique_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result, - output_iterator_tag) + input_iterator_tag, output_iterator_tag) { // concept requirements -- taken care of in dispatching function typename iterator_traits<_InputIterator>::value_type __value = *__first; @@ -1178,14 +1356,14 @@ namespace std * @if maint * This is an uglified unique_copy(_InputIterator, _InputIterator, * _OutputIterator) - * overloaded for forward iterators. + * overloaded for input iterators and forward iterator as result. * @endif */ template<typename _InputIterator, typename _ForwardIterator> _ForwardIterator __unique_copy(_InputIterator __first, _InputIterator __last, _ForwardIterator __result, - forward_iterator_tag) + input_iterator_tag, forward_iterator_tag) { // concept requirements -- taken care of in dispatching function *__result = *__first; @@ -1200,16 +1378,46 @@ namespace std * This is an uglified * unique_copy(_InputIterator, _InputIterator, _OutputIterator, * _BinaryPredicate) - * overloaded for output iterators. + * overloaded for forward iterators and output iterator as result. + * @endif + */ + template<typename _ForwardIterator, typename _OutputIterator, + typename _BinaryPredicate> + _OutputIterator + __unique_copy(_ForwardIterator __first, _ForwardIterator __last, + _OutputIterator __result, _BinaryPredicate __binary_pred, + forward_iterator_tag, output_iterator_tag) + { + // concept requirements -- iterators already checked + __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, + typename iterator_traits<_ForwardIterator>::value_type, + typename iterator_traits<_ForwardIterator>::value_type>) + + _ForwardIterator __next = __first; + *__result = *__first; + while (++__next != __last) + if (!__binary_pred(*__first, *__next)) + { + __first = __next; + *++__result = *__first; + } + return ++__result; + } + + /** + * @if maint + * This is an uglified + * unique_copy(_InputIterator, _InputIterator, _OutputIterator, + * _BinaryPredicate) + * overloaded for input iterators and output iterator as result. * @endif */ template<typename _InputIterator, typename _OutputIterator, typename _BinaryPredicate> _OutputIterator __unique_copy(_InputIterator __first, _InputIterator __last, - _OutputIterator __result, - _BinaryPredicate __binary_pred, - output_iterator_tag) + _OutputIterator __result, _BinaryPredicate __binary_pred, + input_iterator_tag, output_iterator_tag) { // concept requirements -- iterators already checked __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, @@ -1232,25 +1440,25 @@ namespace std * This is an uglified * unique_copy(_InputIterator, _InputIterator, _OutputIterator, * _BinaryPredicate) - * overloaded for forward iterators. + * overloaded for input iterators and forward iterator as result. * @endif */ template<typename _InputIterator, typename _ForwardIterator, typename _BinaryPredicate> _ForwardIterator __unique_copy(_InputIterator __first, _InputIterator __last, - _ForwardIterator __result, - _BinaryPredicate __binary_pred, - forward_iterator_tag) + _ForwardIterator __result, _BinaryPredicate __binary_pred, + input_iterator_tag, forward_iterator_tag) { // concept requirements -- iterators already checked __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, - typename iterator_traits<_ForwardIterator>::value_type, - typename iterator_traits<_InputIterator>::value_type>) + typename iterator_traits<_ForwardIterator>::value_type, + typename iterator_traits<_InputIterator>::value_type>) *__result = *__first; while (++__first != __last) - if (!__binary_pred(*__result, *__first)) *++__result = *__first; + if (!__binary_pred(*__result, *__first)) + *++__result = *__first; return ++__result; } @@ -1266,6 +1474,15 @@ namespace std * from groups of consecutive elements that compare equal. * unique_copy() is stable, so the relative order of elements that are * copied is unchanged. + * + * @if maint + * _GLIBCXX_RESOLVE_LIB_DEFECTS + * DR 241. Does unique_copy() require CopyConstructible and Assignable? + * + * _GLIBCXX_RESOLVE_LIB_DEFECTS + * DR 538. 241 again: Does unique_copy() require CopyConstructible and + * Assignable? + * @endif */ template<typename _InputIterator, typename _OutputIterator> inline _OutputIterator @@ -1280,11 +1497,11 @@ namespace std typename iterator_traits<_InputIterator>::value_type>) __glibcxx_requires_valid_range(__first, __last); - typedef typename iterator_traits<_OutputIterator>::iterator_category - _IterType; - - if (__first == __last) return __result; - return std::__unique_copy(__first, __last, __result, _IterType()); + if (__first == __last) + return __result; + return std::__unique_copy(__first, __last, __result, + std::__iterator_category(__first), + std::__iterator_category(__result)); } /** @@ -1301,6 +1518,11 @@ namespace std * true. * unique_copy() is stable, so the relative order of elements that are * copied is unchanged. + * + * @if maint + * _GLIBCXX_RESOLVE_LIB_DEFECTS + * DR 241. Does unique_copy() require CopyConstructible and Assignable? + * @endif */ template<typename _InputIterator, typename _OutputIterator, typename _BinaryPredicate> @@ -1315,12 +1537,11 @@ namespace std typename iterator_traits<_InputIterator>::value_type>) __glibcxx_requires_valid_range(__first, __last); - typedef typename iterator_traits<_OutputIterator>::iterator_category - _IterType; - - if (__first == __last) return __result; - return std::__unique_copy(__first, __last, __result, - __binary_pred, _IterType()); + if (__first == __last) + return __result; + return std::__unique_copy(__first, __last, __result, __binary_pred, + std::__iterator_category(__first), + std::__iterator_category(__result)); } /** @@ -1412,29 +1633,39 @@ namespace std template<typename _BidirectionalIterator> void __reverse(_BidirectionalIterator __first, _BidirectionalIterator __last, - bidirectional_iterator_tag) + bidirectional_iterator_tag) { while (true) if (__first == __last || __first == --__last) return; else - std::iter_swap(__first++, __last); + { + std::iter_swap(__first, __last); + ++__first; + } } /** * @if maint * This is an uglified reverse(_BidirectionalIterator, * _BidirectionalIterator) - * overloaded for bidirectional iterators. + * overloaded for random access iterators. * @endif */ template<typename _RandomAccessIterator> void __reverse(_RandomAccessIterator __first, _RandomAccessIterator __last, - random_access_iterator_tag) + random_access_iterator_tag) { + if (__first == __last) + return; + --__last; while (__first < __last) - std::iter_swap(__first++, --__last); + { + std::iter_swap(__first, __last); + ++__first; + --__last; + } } /** @@ -1454,7 +1685,7 @@ namespace std { // concept requirements __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept< - _BidirectionalIterator>) + _BidirectionalIterator>) __glibcxx_requires_valid_range(__first, __last); std::__reverse(__first, __last, std::__iterator_category(__first)); } @@ -1525,15 +1756,17 @@ namespace std __rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last, - forward_iterator_tag) + forward_iterator_tag) { - if ((__first == __middle) || (__last == __middle)) + if (__first == __middle || __last == __middle) return; _ForwardIterator __first2 = __middle; do { - swap(*__first++, *__first2++); + swap(*__first, *__first2); + ++__first; + ++__first2; if (__first == __middle) __middle = __first2; } @@ -1543,7 +1776,9 @@ namespace std while (__first2 != __last) { - swap(*__first++, *__first2++); + swap(*__first, *__first2); + ++__first; + ++__first2; if (__first == __middle) __middle = __first2; else if (__first2 == __last) @@ -1565,16 +1800,19 @@ namespace std { // concept requirements __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept< - _BidirectionalIterator>) + _BidirectionalIterator>) - if ((__first == __middle) || (__last == __middle)) + if (__first == __middle || __last == __middle) return; std::__reverse(__first, __middle, bidirectional_iterator_tag()); std::__reverse(__middle, __last, bidirectional_iterator_tag()); while (__first != __middle && __middle != __last) - swap(*__first++, *--__last); + { + swap(*__first, *--__last); + ++__first; + } if (__first == __middle) std::__reverse(__middle, __last, bidirectional_iterator_tag()); @@ -1596,9 +1834,9 @@ namespace std { // concept requirements __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< - _RandomAccessIterator>) + _RandomAccessIterator>) - if ((__first == __middle) || (__last == __middle)) + if (__first == __middle || __last == __middle) return; typedef typename iterator_traits<_RandomAccessIterator>::difference_type @@ -1620,7 +1858,7 @@ namespace std for (_Distance __i = 0; __i < __d; __i++) { - const _ValueType __tmp = *__first; + _ValueType __tmp = *__first; _RandomAccessIterator __p = __first; if (__k < __l) @@ -1719,7 +1957,8 @@ namespace std __glibcxx_requires_valid_range(__first, __middle); __glibcxx_requires_valid_range(__middle, __last); - return std::copy(__first, __middle, copy(__middle, __last, __result)); + return std::copy(__first, __middle, + std::copy(__middle, __last, __result)); } /** @@ -2194,10 +2433,10 @@ namespace std __final_insertion_sort(_RandomAccessIterator __first, _RandomAccessIterator __last) { - if (__last - __first > _S_threshold) + if (__last - __first > int(_S_threshold)) { - std::__insertion_sort(__first, __first + _S_threshold); - std::__unguarded_insertion_sort(__first + _S_threshold, __last); + std::__insertion_sort(__first, __first + int(_S_threshold)); + std::__unguarded_insertion_sort(__first + int(_S_threshold), __last); } else std::__insertion_sort(__first, __last); @@ -2213,10 +2452,10 @@ namespace std __final_insertion_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { - if (__last - __first > _S_threshold) + if (__last - __first > int(_S_threshold)) { - std::__insertion_sort(__first, __first + _S_threshold, __comp); - std::__unguarded_insertion_sort(__first + _S_threshold, __last, + std::__insertion_sort(__first, __first + int(_S_threshold), __comp); + std::__unguarded_insertion_sort(__first + int(_S_threshold), __last, __comp); } else @@ -2225,7 +2464,47 @@ namespace std /** * @if maint - * This is a helper function for the sort routine. + * This is a helper function for the sort routines. + * @endif + */ + template<typename _RandomAccessIterator> + void + __heap_select(_RandomAccessIterator __first, + _RandomAccessIterator __middle, + _RandomAccessIterator __last) + { + typedef typename iterator_traits<_RandomAccessIterator>::value_type + _ValueType; + + std::make_heap(__first, __middle); + for (_RandomAccessIterator __i = __middle; __i < __last; ++__i) + if (*__i < *__first) + std::__pop_heap(__first, __middle, __i, _ValueType(*__i)); + } + + /** + * @if maint + * This is a helper function for the sort routines. + * @endif + */ + template<typename _RandomAccessIterator, typename _Compare> + void + __heap_select(_RandomAccessIterator __first, + _RandomAccessIterator __middle, + _RandomAccessIterator __last, _Compare __comp) + { + typedef typename iterator_traits<_RandomAccessIterator>::value_type + _ValueType; + + std::make_heap(__first, __middle, __comp); + for (_RandomAccessIterator __i = __middle; __i < __last; ++__i) + if (__comp(*__i, *__first)) + std::__pop_heap(__first, __middle, __i, _ValueType(*__i), __comp); + } + + /** + * @if maint + * This is a helper function for the sort routines. * @endif */ template<typename _Size> @@ -2254,7 +2533,7 @@ namespace std * the range @p [middle,last) then @p *j<*i and @p *k<*i are both false. */ template<typename _RandomAccessIterator> - void + inline void partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last) @@ -2269,10 +2548,7 @@ namespace std __glibcxx_requires_valid_range(__first, __middle); __glibcxx_requires_valid_range(__middle, __last); - std::make_heap(__first, __middle); - for (_RandomAccessIterator __i = __middle; __i < __last; ++__i) - if (*__i < *__first) - std::__pop_heap(__first, __middle, __i, _ValueType(*__i)); + std::__heap_select(__first, __middle, __last); std::sort_heap(__first, __middle); } @@ -2295,7 +2571,7 @@ namespace std * are both false. */ template<typename _RandomAccessIterator, typename _Compare> - void + inline void partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last, @@ -2312,10 +2588,7 @@ namespace std __glibcxx_requires_valid_range(__first, __middle); __glibcxx_requires_valid_range(__middle, __last); - std::make_heap(__first, __middle, __comp); - for (_RandomAccessIterator __i = __middle; __i < __last; ++__i) - if (__comp(*__i, *__first)) - std::__pop_heap(__first, __middle, __i, _ValueType(*__i), __comp); + std::__heap_select(__first, __middle, __last, __comp); std::sort_heap(__first, __middle, __comp); } @@ -2353,8 +2626,9 @@ namespace std __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) __glibcxx_function_requires(_ConvertibleConcept<_InputValueType, _OutputValueType>) + __glibcxx_function_requires(_LessThanOpConcept<_InputValueType, + _OutputValueType>) __glibcxx_function_requires(_LessThanComparableConcept<_OutputValueType>) - __glibcxx_function_requires(_LessThanComparableConcept<_InputValueType>) __glibcxx_requires_valid_range(__first, __last); __glibcxx_requires_valid_range(__result_first, __result_last); @@ -2421,6 +2695,8 @@ namespace std __glibcxx_function_requires(_ConvertibleConcept<_InputValueType, _OutputValueType>) __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, + _InputValueType, _OutputValueType>) + __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, _OutputValueType, _OutputValueType>) __glibcxx_requires_valid_range(__first, __last); __glibcxx_requires_valid_range(__result_first, __result_last); @@ -2463,7 +2739,7 @@ namespace std typedef typename iterator_traits<_RandomAccessIterator>::value_type _ValueType; - while (__last - __first > _S_threshold) + while (__last - __first > int(_S_threshold)) { if (__depth_limit == 0) { @@ -2499,7 +2775,7 @@ namespace std typedef typename iterator_traits<_RandomAccessIterator>::value_type _ValueType; - while (__last - __first > _S_threshold) + while (__last - __first > int(_S_threshold)) { if (__depth_limit == 0) { @@ -2550,7 +2826,8 @@ namespace std if (__first != __last) { - std::__introsort_loop(__first, __last, __lg(__last - __first) * 2); + std::__introsort_loop(__first, __last, + std::__lg(__last - __first) * 2); std::__final_insertion_sort(__first, __last); } } @@ -2586,8 +2863,8 @@ namespace std if (__first != __last) { - std::__introsort_loop(__first, __last, __lg(__last - __first) * 2, - __comp); + std::__introsort_loop(__first, __last, + std::__lg(__last - __first) * 2, __comp); std::__final_insertion_sort(__first, __last, __comp); } } @@ -2613,13 +2890,8 @@ namespace std _DistanceType; // concept requirements - // Note that these are slightly stricter than those of the 4-argument - // version, defined next. The difference is in the strictness of the - // comparison operations... so for looser checking, define your own - // comparison function, as was intended. __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) - __glibcxx_function_requires(_SameTypeConcept<_Tp, _ValueType>) - __glibcxx_function_requires(_LessThanComparableConcept<_Tp>) + __glibcxx_function_requires(_LessThanOpConcept<_ValueType, _Tp>) __glibcxx_requires_partitioned(__first, __last, __val); _DistanceType __len = std::distance(__first, __last); @@ -2715,10 +2987,8 @@ namespace std _DistanceType; // concept requirements - // See comments on lower_bound. __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) - __glibcxx_function_requires(_SameTypeConcept<_Tp, _ValueType>) - __glibcxx_function_requires(_LessThanComparableConcept<_Tp>) + __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>) __glibcxx_requires_partitioned(__first, __last, __val); _DistanceType __len = std::distance(__first, __last); @@ -2961,16 +3231,19 @@ namespace std _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result) { + typedef typename iterator_traits<_InputIterator1>::value_type + _ValueType1; + typedef typename iterator_traits<_InputIterator2>::value_type + _ValueType2; + // concept requirements __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, - typename iterator_traits<_InputIterator1>::value_type>) - __glibcxx_function_requires(_SameTypeConcept< - typename iterator_traits<_InputIterator1>::value_type, - typename iterator_traits<_InputIterator2>::value_type>) - __glibcxx_function_requires(_LessThanComparableConcept< - typename iterator_traits<_InputIterator1>::value_type>) + _ValueType1>) + __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, + _ValueType2>) + __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>) __glibcxx_requires_sorted(__first1, __last1); __glibcxx_requires_sorted(__first2, __last2); @@ -3019,17 +3292,20 @@ namespace std _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp) { + typedef typename iterator_traits<_InputIterator1>::value_type + _ValueType1; + typedef typename iterator_traits<_InputIterator2>::value_type + _ValueType2; + // concept requirements __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) - __glibcxx_function_requires(_SameTypeConcept< - typename iterator_traits<_InputIterator1>::value_type, - typename iterator_traits<_InputIterator2>::value_type>) __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, - typename iterator_traits<_InputIterator1>::value_type>) + _ValueType1>) + __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, + _ValueType2>) __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, - typename iterator_traits<_InputIterator1>::value_type, - typename iterator_traits<_InputIterator2>::value_type>) + _ValueType2, _ValueType1>) __glibcxx_requires_sorted_pred(__first1, __last1, __comp); __glibcxx_requires_sorted_pred(__first2, __last2, __comp); @@ -3610,13 +3886,13 @@ namespace std __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>) __glibcxx_requires_valid_range(__first, __last); - _Temporary_buffer<_RandomAccessIterator, _ValueType> - buf(__first, __last); - if (buf.begin() == 0) + _Temporary_buffer<_RandomAccessIterator, _ValueType> __buf(__first, + __last); + if (__buf.begin() == 0) std::__inplace_stable_sort(__first, __last); else - std::__stable_sort_adaptive(__first, __last, buf.begin(), - _DistanceType(buf.size())); + std::__stable_sort_adaptive(__first, __last, __buf.begin(), + _DistanceType(__buf.size())); } /** @@ -3654,12 +3930,86 @@ namespace std _ValueType>) __glibcxx_requires_valid_range(__first, __last); - _Temporary_buffer<_RandomAccessIterator, _ValueType> buf(__first, __last); - if (buf.begin() == 0) + _Temporary_buffer<_RandomAccessIterator, _ValueType> __buf(__first, + __last); + if (__buf.begin() == 0) std::__inplace_stable_sort(__first, __last, __comp); else - std::__stable_sort_adaptive(__first, __last, buf.begin(), - _DistanceType(buf.size()), __comp); + std::__stable_sort_adaptive(__first, __last, __buf.begin(), + _DistanceType(__buf.size()), __comp); + } + + + template<typename _RandomAccessIterator, typename _Size> + void + __introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth, + _RandomAccessIterator __last, _Size __depth_limit) + { + typedef typename iterator_traits<_RandomAccessIterator>::value_type + _ValueType; + + while (__last - __first > 3) + { + if (__depth_limit == 0) + { + std::__heap_select(__first, __nth + 1, __last); + // Place the nth largest element in its final position. + std::iter_swap(__first, __nth); + return; + } + --__depth_limit; + _RandomAccessIterator __cut = + std::__unguarded_partition(__first, __last, + _ValueType(std::__median(*__first, + *(__first + + (__last + - __first) + / 2), + *(__last + - 1)))); + if (__cut <= __nth) + __first = __cut; + else + __last = __cut; + } + std::__insertion_sort(__first, __last); + } + + template<typename _RandomAccessIterator, typename _Size, typename _Compare> + void + __introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth, + _RandomAccessIterator __last, _Size __depth_limit, + _Compare __comp) + { + typedef typename iterator_traits<_RandomAccessIterator>::value_type + _ValueType; + + while (__last - __first > 3) + { + if (__depth_limit == 0) + { + std::__heap_select(__first, __nth + 1, __last, __comp); + // Place the nth largest element in its final position. + std::iter_swap(__first, __nth); + return; + } + --__depth_limit; + _RandomAccessIterator __cut = + std::__unguarded_partition(__first, __last, + _ValueType(std::__median(*__first, + *(__first + + (__last + - __first) + / 2), + *(__last - 1), + __comp)), + __comp); + if (__cut <= __nth) + __first = __cut; + else + __last = __cut; + } + std::__insertion_sort(__first, __last, __comp); } /** @@ -3678,9 +4028,8 @@ namespace std * holds that @p *j<*i is false. */ template<typename _RandomAccessIterator> - void - nth_element(_RandomAccessIterator __first, - _RandomAccessIterator __nth, + inline void + nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last) { typedef typename iterator_traits<_RandomAccessIterator>::value_type @@ -3693,23 +4042,11 @@ namespace std __glibcxx_requires_valid_range(__first, __nth); __glibcxx_requires_valid_range(__nth, __last); - while (__last - __first > 3) - { - _RandomAccessIterator __cut = - std::__unguarded_partition(__first, __last, - _ValueType(std::__median(*__first, - *(__first - + (__last - - __first) - / 2), - *(__last - - 1)))); - if (__cut <= __nth) - __first = __cut; - else - __last = __cut; - } - std::__insertion_sort(__first, __last); + if (__first == __last || __nth == __last) + return; + + std::__introselect(__first, __nth, __last, + std::__lg(__last - __first) * 2); } /** @@ -3729,11 +4066,9 @@ namespace std * holds that @p comp(*j,*i) is false. */ template<typename _RandomAccessIterator, typename _Compare> - void - nth_element(_RandomAccessIterator __first, - _RandomAccessIterator __nth, - _RandomAccessIterator __last, - _Compare __comp) + inline void + nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, + _RandomAccessIterator __last, _Compare __comp) { typedef typename iterator_traits<_RandomAccessIterator>::value_type _ValueType; @@ -3746,23 +4081,11 @@ namespace std __glibcxx_requires_valid_range(__first, __nth); __glibcxx_requires_valid_range(__nth, __last); - while (__last - __first > 3) - { - _RandomAccessIterator __cut = - std::__unguarded_partition(__first, __last, - _ValueType(std::__median(*__first, - *(__first - + (__last - - __first) - / 2), - *(__last - 1), - __comp)), __comp); - if (__cut <= __nth) - __first = __cut; - else - __last = __cut; - } - std::__insertion_sort(__first, __last, __comp); + if (__first == __last || __nth == __last) + return; + + std::__introselect(__first, __nth, __last, + std::__lg(__last - __first) * 2, __comp); } /** @@ -3792,10 +4115,9 @@ namespace std _DistanceType; // concept requirements - // See comments on lower_bound. __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) - __glibcxx_function_requires(_SameTypeConcept<_Tp, _ValueType>) - __glibcxx_function_requires(_LessThanComparableConcept<_Tp>) + __glibcxx_function_requires(_LessThanOpConcept<_ValueType, _Tp>) + __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>) __glibcxx_requires_partitioned(__first, __last, __val); _DistanceType __len = std::distance(__first, __last); @@ -3906,12 +4228,12 @@ namespace std binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __val) { + typedef typename iterator_traits<_ForwardIterator>::value_type + _ValueType; + // concept requirements - // See comments on lower_bound. __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) - __glibcxx_function_requires(_SameTypeConcept<_Tp, - typename iterator_traits<_ForwardIterator>::value_type>) - __glibcxx_function_requires(_LessThanComparableConcept<_Tp>) + __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>) __glibcxx_requires_partitioned(__first, __last, __val); _ForwardIterator __i = std::lower_bound(__first, __last, __val); @@ -3938,12 +4260,13 @@ namespace std binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __val, _Compare __comp) { + typedef typename iterator_traits<_ForwardIterator>::value_type + _ValueType; + // concept requirements __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, - typename iterator_traits<_ForwardIterator>::value_type, _Tp>) - __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, _Tp, - typename iterator_traits<_ForwardIterator>::value_type>) + _Tp, _ValueType>) __glibcxx_requires_partitioned_pred(__first, __last, __val, __comp); _ForwardIterator __i = std::lower_bound(__first, __last, __val, __comp); @@ -3976,14 +4299,16 @@ namespace std includes(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2) { + typedef typename iterator_traits<_InputIterator1>::value_type + _ValueType1; + typedef typename iterator_traits<_InputIterator2>::value_type + _ValueType2; + // concept requirements __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) - __glibcxx_function_requires(_SameTypeConcept< - typename iterator_traits<_InputIterator1>::value_type, - typename iterator_traits<_InputIterator2>::value_type>) - __glibcxx_function_requires(_LessThanComparableConcept< - typename iterator_traits<_InputIterator1>::value_type>) + __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>) + __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>) __glibcxx_requires_sorted(__first1, __last1); __glibcxx_requires_sorted(__first2, __last2); @@ -4023,15 +4348,18 @@ namespace std includes(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, _Compare __comp) { + typedef typename iterator_traits<_InputIterator1>::value_type + _ValueType1; + typedef typename iterator_traits<_InputIterator2>::value_type + _ValueType2; + // concept requirements __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) - __glibcxx_function_requires(_SameTypeConcept< - typename iterator_traits<_InputIterator1>::value_type, - typename iterator_traits<_InputIterator2>::value_type>) __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, - typename iterator_traits<_InputIterator1>::value_type, - typename iterator_traits<_InputIterator2>::value_type>) + _ValueType1, _ValueType2>) + __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, + _ValueType2, _ValueType1>) __glibcxx_requires_sorted_pred(__first1, __last1, __comp); __glibcxx_requires_sorted_pred(__first2, __last2, __comp); @@ -4070,16 +4398,20 @@ namespace std _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result) { + typedef typename iterator_traits<_InputIterator1>::value_type + _ValueType1; + typedef typename iterator_traits<_InputIterator2>::value_type + _ValueType2; + // concept requirements __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, - typename iterator_traits<_InputIterator1>::value_type>) - __glibcxx_function_requires(_SameTypeConcept< - typename iterator_traits<_InputIterator1>::value_type, - typename iterator_traits<_InputIterator2>::value_type>) - __glibcxx_function_requires(_LessThanComparableConcept< - typename iterator_traits<_InputIterator1>::value_type>) + _ValueType1>) + __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, + _ValueType2>) + __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>) + __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>) __glibcxx_requires_sorted(__first1, __last1); __glibcxx_requires_sorted(__first2, __last2); @@ -4132,17 +4464,22 @@ namespace std _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp) { + typedef typename iterator_traits<_InputIterator1>::value_type + _ValueType1; + typedef typename iterator_traits<_InputIterator2>::value_type + _ValueType2; + // concept requirements __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) - __glibcxx_function_requires(_SameTypeConcept< - typename iterator_traits<_InputIterator1>::value_type, - typename iterator_traits<_InputIterator2>::value_type>) __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, - typename iterator_traits<_InputIterator1>::value_type>) + _ValueType1>) + __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, + _ValueType2>) __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, - typename iterator_traits<_InputIterator1>::value_type, - typename iterator_traits<_InputIterator2>::value_type>) + _ValueType1, _ValueType2>) + __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, + _ValueType2, _ValueType1>) __glibcxx_requires_sorted_pred(__first1, __last1, __comp); __glibcxx_requires_sorted_pred(__first2, __last2, __comp); @@ -4193,16 +4530,18 @@ namespace std _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result) { + typedef typename iterator_traits<_InputIterator1>::value_type + _ValueType1; + typedef typename iterator_traits<_InputIterator2>::value_type + _ValueType2; + // concept requirements __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, - typename iterator_traits<_InputIterator1>::value_type>) - __glibcxx_function_requires(_SameTypeConcept< - typename iterator_traits<_InputIterator1>::value_type, - typename iterator_traits<_InputIterator2>::value_type>) - __glibcxx_function_requires(_LessThanComparableConcept< - typename iterator_traits<_InputIterator1>::value_type>) + _ValueType1>) + __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>) + __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>) __glibcxx_requires_sorted(__first1, __last1); __glibcxx_requires_sorted(__first2, __last2); @@ -4247,17 +4586,20 @@ namespace std _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp) { + typedef typename iterator_traits<_InputIterator1>::value_type + _ValueType1; + typedef typename iterator_traits<_InputIterator2>::value_type + _ValueType2; + // concept requirements __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) - __glibcxx_function_requires(_SameTypeConcept< - typename iterator_traits<_InputIterator1>::value_type, - typename iterator_traits<_InputIterator2>::value_type>) __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, - typename iterator_traits<_InputIterator1>::value_type>) + _ValueType1>) + __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, + _ValueType1, _ValueType2>) __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, - typename iterator_traits<_InputIterator1>::value_type, - typename iterator_traits<_InputIterator2>::value_type>) + _ValueType2, _ValueType1>) __glibcxx_requires_sorted_pred(__first1, __last1, __comp); __glibcxx_requires_sorted_pred(__first2, __last2, __comp); @@ -4301,16 +4643,18 @@ namespace std _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result) { + typedef typename iterator_traits<_InputIterator1>::value_type + _ValueType1; + typedef typename iterator_traits<_InputIterator2>::value_type + _ValueType2; + // concept requirements __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, - typename iterator_traits<_InputIterator1>::value_type>) - __glibcxx_function_requires(_SameTypeConcept< - typename iterator_traits<_InputIterator1>::value_type, - typename iterator_traits<_InputIterator2>::value_type>) - __glibcxx_function_requires(_LessThanComparableConcept< - typename iterator_traits<_InputIterator1>::value_type>) + _ValueType1>) + __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>) + __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>) __glibcxx_requires_sorted(__first1, __last1); __glibcxx_requires_sorted(__first2, __last2); @@ -4359,17 +4703,20 @@ namespace std _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp) { + typedef typename iterator_traits<_InputIterator1>::value_type + _ValueType1; + typedef typename iterator_traits<_InputIterator2>::value_type + _ValueType2; + // concept requirements __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) - __glibcxx_function_requires(_SameTypeConcept< - typename iterator_traits<_InputIterator1>::value_type, - typename iterator_traits<_InputIterator2>::value_type>) __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, - typename iterator_traits<_InputIterator1>::value_type>) + _ValueType1>) + __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, + _ValueType1, _ValueType2>) __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, - typename iterator_traits<_InputIterator1>::value_type, - typename iterator_traits<_InputIterator2>::value_type>) + _ValueType2, _ValueType1>) __glibcxx_requires_sorted_pred(__first1, __last1, __comp); __glibcxx_requires_sorted_pred(__first2, __last2, __comp); @@ -4413,16 +4760,20 @@ namespace std _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result) { + typedef typename iterator_traits<_InputIterator1>::value_type + _ValueType1; + typedef typename iterator_traits<_InputIterator2>::value_type + _ValueType2; + // concept requirements __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, - typename iterator_traits<_InputIterator1>::value_type>) - __glibcxx_function_requires(_SameTypeConcept< - typename iterator_traits<_InputIterator1>::value_type, - typename iterator_traits<_InputIterator2>::value_type>) - __glibcxx_function_requires(_LessThanComparableConcept< - typename iterator_traits<_InputIterator1>::value_type>) + _ValueType1>) + __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, + _ValueType2>) + __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>) + __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>) __glibcxx_requires_sorted(__first1, __last1); __glibcxx_requires_sorted(__first2, __last2); @@ -4475,17 +4826,22 @@ namespace std _OutputIterator __result, _Compare __comp) { + typedef typename iterator_traits<_InputIterator1>::value_type + _ValueType1; + typedef typename iterator_traits<_InputIterator2>::value_type + _ValueType2; + // concept requirements __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) - __glibcxx_function_requires(_SameTypeConcept< - typename iterator_traits<_InputIterator1>::value_type, - typename iterator_traits<_InputIterator2>::value_type>) __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, - typename iterator_traits<_InputIterator1>::value_type>) + _ValueType1>) + __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, + _ValueType2>) + __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, + _ValueType1, _ValueType2>) __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, - typename iterator_traits<_InputIterator1>::value_type, - typename iterator_traits<_InputIterator2>::value_type>) + _ValueType2, _ValueType1>) __glibcxx_requires_sorted_pred(__first1, __last1, __comp); __glibcxx_requires_sorted_pred(__first2, __last2, __comp); @@ -5143,6 +5499,6 @@ namespace std __comp); } -} // namespace std +_GLIBCXX_END_NAMESPACE #endif /* _ALGO_H */ |