diff options
Diffstat (limited to 'libstdc++-v3/include/bits/stl_algo.h')
| -rw-r--r-- | libstdc++-v3/include/bits/stl_algo.h | 1473 |
1 files changed, 917 insertions, 556 deletions
diff --git a/libstdc++-v3/include/bits/stl_algo.h b/libstdc++-v3/include/bits/stl_algo.h index 090f0d6720e..929c4ff372f 100644 --- a/libstdc++-v3/include/bits/stl_algo.h +++ b/libstdc++-v3/include/bits/stl_algo.h @@ -33,8 +33,7 @@ #include <bits/stl_heap.h> -// See concept_checks.h for the concept-checking macros -// __STL_REQUIRES, __STL_CONVERTIBLE, etc. +// See concept_check.h for the glibcpp_*_requires macros. namespace std { @@ -42,8 +41,10 @@ namespace std // __median (an extension, not present in the C++ standard). template <class _Tp> -inline const _Tp& __median(const _Tp& __a, const _Tp& __b, const _Tp& __c) { - __STL_REQUIRES(_Tp, _LessThanComparable); +inline const _Tp& __median(const _Tp& __a, const _Tp& __b, const _Tp& __c) +{ + // concept requirements + glibcpp_function_requires(LessThanComparableConcept<_Tp>); if (__a < __b) if (__b < __c) return __b; @@ -61,8 +62,10 @@ inline const _Tp& __median(const _Tp& __a, const _Tp& __b, const _Tp& __c) { template <class _Tp, class _Compare> inline const _Tp& -__median(const _Tp& __a, const _Tp& __b, const _Tp& __c, _Compare __comp) { - __STL_BINARY_FUNCTION_CHECK(_Compare, bool, _Tp, _Tp); +__median(const _Tp& __a, const _Tp& __b, const _Tp& __c, _Compare __comp) +{ + // concept requirements + glibcpp_function_requires(BinaryFunctionConcept<_Compare, bool, _Tp, _Tp>); if (__comp(__a, __b)) if (__comp(__b, __c)) return __b; @@ -80,8 +83,10 @@ __median(const _Tp& __a, const _Tp& __b, const _Tp& __c, _Compare __comp) { // for_each. Apply a function to every element of a range. template <class _InputIter, class _Function> -_Function for_each(_InputIter __first, _InputIter __last, _Function __f) { - __STL_REQUIRES(_InputIter, _InputIterator); +_Function for_each(_InputIter __first, _InputIter __last, _Function __f) +{ + // concept requirements + glibcpp_function_requires(InputIteratorConcept<_InputIter>); for ( ; __first != __last; ++__first) __f(*__first); return __f; @@ -189,28 +194,33 @@ template <class _InputIter, class _Tp> inline _InputIter find(_InputIter __first, _InputIter __last, const _Tp& __val) { - __STL_REQUIRES(_InputIter, _InputIterator); - __STL_REQUIRES_BINARY_OP(_OP_EQUAL, bool, - typename iterator_traits<_InputIter>::value_type, _Tp); - return find(__first, __last, __val, __ITERATOR_CATEGORY(__first)); + // concept requirements + glibcpp_function_requires(InputIteratorConcept<_InputIter>); + glibcpp_function_requires(EqualOpConcept< + typename iterator_traits<_InputIter>::value_type, _Tp>); + return find(__first, __last, __val, __iterator_category(__first)); } template <class _InputIter, class _Predicate> inline _InputIter find_if(_InputIter __first, _InputIter __last, - _Predicate __pred) { - __STL_REQUIRES(_InputIter, _InputIterator); - __STL_UNARY_FUNCTION_CHECK(_Predicate, bool, - typename iterator_traits<_InputIter>::value_type); - return find_if(__first, __last, __pred, __ITERATOR_CATEGORY(__first)); + _Predicate __pred) +{ + // concept requirements + glibcpp_function_requires(InputIteratorConcept<_InputIter>); + glibcpp_function_requires(UnaryPredicateConcept<_Predicate, + typename iterator_traits<_InputIter>::value_type>); + return find_if(__first, __last, __pred, __iterator_category(__first)); } // adjacent_find. template <class _ForwardIter> -_ForwardIter adjacent_find(_ForwardIter __first, _ForwardIter __last) { - __STL_REQUIRES(_ForwardIter, _ForwardIterator); - __STL_REQUIRES(typename iterator_traits<_ForwardIter>::value_type, - _EqualityComparable); +_ForwardIter adjacent_find(_ForwardIter __first, _ForwardIter __last) +{ + // concept requirements + glibcpp_function_requires(ForwardIteratorConcept<_ForwardIter>); + glibcpp_function_requires(EqualityComparableConcept< + typename iterator_traits<_ForwardIter>::value_type>); if (__first == __last) return __last; _ForwardIter __next = __first; @@ -224,11 +234,13 @@ _ForwardIter adjacent_find(_ForwardIter __first, _ForwardIter __last) { template <class _ForwardIter, class _BinaryPredicate> _ForwardIter adjacent_find(_ForwardIter __first, _ForwardIter __last, - _BinaryPredicate __binary_pred) { - __STL_REQUIRES(_ForwardIter, _ForwardIterator); - __STL_BINARY_FUNCTION_CHECK(_BinaryPredicate, bool, - typename iterator_traits<_ForwardIter>::value_type, - typename iterator_traits<_ForwardIter>::value_type); + _BinaryPredicate __binary_pred) +{ + // concept requirements + glibcpp_function_requires(ForwardIteratorConcept<_ForwardIter>); + glibcpp_function_requires(BinaryPredicateConcept<_BinaryPredicate, + typename iterator_traits<_ForwardIter>::value_type, + typename iterator_traits<_ForwardIter>::value_type>); if (__first == __last) return __last; _ForwardIter __next = __first; @@ -248,11 +260,13 @@ _ForwardIter adjacent_find(_ForwardIter __first, _ForwardIter __last, template <class _InputIter, class _Tp, class _Size> void count(_InputIter __first, _InputIter __last, const _Tp& __value, - _Size& __n) { - __STL_REQUIRES(_InputIter, _InputIterator); - __STL_REQUIRES(typename iterator_traits<_InputIter>::value_type, - _EqualityComparable); - __STL_REQUIRES(_Tp, _EqualityComparable); + _Size& __n) +{ + // concept requirements + glibcpp_function_requires(InputIteratorConcept<_InputIter>); + glibcpp_function_requires(EqualityComparableConcept< + typename iterator_traits<_InputIter>::value_type >); + glibcpp_function_requires(EqualityComparableConcept<_Tp>); for ( ; __first != __last; ++__first) if (*__first == __value) ++__n; @@ -260,10 +274,12 @@ void count(_InputIter __first, _InputIter __last, const _Tp& __value, template <class _InputIter, class _Predicate, class _Size> void count_if(_InputIter __first, _InputIter __last, _Predicate __pred, - _Size& __n) { - __STL_REQUIRES(_InputIter, _InputIterator); - __STL_UNARY_FUNCTION_CHECK(_Predicate, bool, - typename iterator_traits<_InputIter>::value_type); + _Size& __n) +{ + // concept requirements + glibcpp_function_requires(InputIteratorConcept<_InputIter>); + glibcpp_function_requires(UnaryPredicateConcept<_Predicate, + typename iterator_traits<_InputIter>::value_type>); for ( ; __first != __last; ++__first) if (__pred(*__first)) ++__n; @@ -271,11 +287,13 @@ void count_if(_InputIter __first, _InputIter __last, _Predicate __pred, template <class _InputIter, class _Tp> typename iterator_traits<_InputIter>::difference_type -count(_InputIter __first, _InputIter __last, const _Tp& __value) { - __STL_REQUIRES(_InputIter, _InputIterator); - __STL_REQUIRES(typename iterator_traits<_InputIter>::value_type, - _EqualityComparable); - __STL_REQUIRES(_Tp, _EqualityComparable); +count(_InputIter __first, _InputIter __last, const _Tp& __value) +{ + // concept requirements + glibcpp_function_requires(InputIteratorConcept<_InputIter>); + glibcpp_function_requires(EqualityComparableConcept< + typename iterator_traits<_InputIter>::value_type >); + glibcpp_function_requires(EqualityComparableConcept<_Tp>); typename iterator_traits<_InputIter>::difference_type __n = 0; for ( ; __first != __last; ++__first) if (*__first == __value) @@ -285,10 +303,12 @@ count(_InputIter __first, _InputIter __last, const _Tp& __value) { template <class _InputIter, class _Predicate> typename iterator_traits<_InputIter>::difference_type -count_if(_InputIter __first, _InputIter __last, _Predicate __pred) { - __STL_REQUIRES(_InputIter, _InputIterator); - __STL_UNARY_FUNCTION_CHECK(_Predicate, bool, - typename iterator_traits<_InputIter>::value_type); +count_if(_InputIter __first, _InputIter __last, _Predicate __pred) +{ + // concept requirements + glibcpp_function_requires(InputIteratorConcept<_InputIter>); + glibcpp_function_requires(UnaryPredicateConcept<_Predicate, + typename iterator_traits<_InputIter>::value_type>); typename iterator_traits<_InputIter>::difference_type __n = 0; for ( ; __first != __last; ++__first) if (__pred(*__first)) @@ -303,11 +323,12 @@ template <class _ForwardIter1, class _ForwardIter2> _ForwardIter1 search(_ForwardIter1 __first1, _ForwardIter1 __last1, _ForwardIter2 __first2, _ForwardIter2 __last2) { - __STL_REQUIRES(_ForwardIter1, _ForwardIterator); - __STL_REQUIRES(_ForwardIter2, _ForwardIterator); - __STL_REQUIRES_BINARY_OP(_OP_EQUAL, bool, - typename iterator_traits<_ForwardIter1>::value_type, - typename iterator_traits<_ForwardIter2>::value_type); + // concept requirements + glibcpp_function_requires(ForwardIteratorConcept<_ForwardIter1>); + glibcpp_function_requires(ForwardIteratorConcept<_ForwardIter2>); + glibcpp_function_requires(EqualOpConcept< + typename iterator_traits<_ForwardIter1>::value_type, + typename iterator_traits<_ForwardIter2>::value_type>); // Test for empty ranges if (__first1 == __last1 || __first2 == __last2) @@ -354,11 +375,12 @@ _ForwardIter1 search(_ForwardIter1 __first1, _ForwardIter1 __last1, _ForwardIter2 __first2, _ForwardIter2 __last2, _BinaryPred __predicate) { - __STL_REQUIRES(_ForwardIter1, _ForwardIterator); - __STL_REQUIRES(_ForwardIter2, _ForwardIterator); - __STL_BINARY_FUNCTION_CHECK(_BinaryPred, bool, - typename iterator_traits<_ForwardIter1>::value_type, - typename iterator_traits<_ForwardIter2>::value_type); + // concept requirements + glibcpp_function_requires(ForwardIteratorConcept<_ForwardIter1>); + glibcpp_function_requires(ForwardIteratorConcept<_ForwardIter2>); + glibcpp_function_requires(BinaryPredicateConcept<_BinaryPred, + typename iterator_traits<_ForwardIter1>::value_type, + typename iterator_traits<_ForwardIter2>::value_type>); // Test for empty ranges if (__first1 == __last1 || __first2 == __last2) @@ -412,11 +434,13 @@ _ForwardIter1 search(_ForwardIter1 __first1, _ForwardIter1 __last1, template <class _ForwardIter, class _Integer, class _Tp> _ForwardIter search_n(_ForwardIter __first, _ForwardIter __last, - _Integer __count, const _Tp& __val) { - __STL_REQUIRES(_ForwardIter, _ForwardIterator); - __STL_REQUIRES(typename iterator_traits<_ForwardIter>::value_type, - _EqualityComparable); - __STL_REQUIRES(_Tp, _EqualityComparable); + _Integer __count, const _Tp& __val) +{ + // concept requirements + glibcpp_function_requires(ForwardIteratorConcept<_ForwardIter>); + glibcpp_function_requires(EqualityComparableConcept< + typename iterator_traits<_ForwardIter>::value_type>); + glibcpp_function_requires(EqualityComparableConcept<_Tp>); if (__count <= 0) return __first; @@ -442,10 +466,13 @@ _ForwardIter search_n(_ForwardIter __first, _ForwardIter __last, template <class _ForwardIter, class _Integer, class _Tp, class _BinaryPred> _ForwardIter search_n(_ForwardIter __first, _ForwardIter __last, _Integer __count, const _Tp& __val, - _BinaryPred __binary_pred) { - __STL_REQUIRES(_ForwardIter, _ForwardIterator); - __STL_BINARY_FUNCTION_CHECK(_BinaryPred, bool, - typename iterator_traits<_ForwardIter>::value_type, _Tp); + _BinaryPred __binary_pred) +{ + // concept requirements + glibcpp_function_requires(ForwardIteratorConcept<_ForwardIter>); + glibcpp_function_requires(BinaryPredicateConcept<_BinaryPred, + typename iterator_traits<_ForwardIter>::value_type, _Tp>); + if (__count <= 0) return __first; else { @@ -481,13 +508,18 @@ _ForwardIter search_n(_ForwardIter __first, _ForwardIter __last, template <class _ForwardIter1, class _ForwardIter2> _ForwardIter2 swap_ranges(_ForwardIter1 __first1, _ForwardIter1 __last1, - _ForwardIter2 __first2) { - __STL_REQUIRES(_ForwardIter1, _Mutable_ForwardIterator); - __STL_REQUIRES(_ForwardIter2, _Mutable_ForwardIterator); - __STL_CONVERTIBLE(typename iterator_traits<_ForwardIter1>::value_type, - typename iterator_traits<_ForwardIter2>::value_type); - __STL_CONVERTIBLE(typename iterator_traits<_ForwardIter2>::value_type, - typename iterator_traits<_ForwardIter1>::value_type); + _ForwardIter2 __first2) +{ + // concept requirements + glibcpp_function_requires(Mutable_ForwardIteratorConcept<_ForwardIter1>); + glibcpp_function_requires(Mutable_ForwardIteratorConcept<_ForwardIter2>); + glibcpp_function_requires(ConvertibleConcept< + typename iterator_traits<_ForwardIter1>::value_type, + typename iterator_traits<_ForwardIter2>::value_type>); + glibcpp_function_requires(ConvertibleConcept< + typename iterator_traits<_ForwardIter2>::value_type, + typename iterator_traits<_ForwardIter1>::value_type>); + for ( ; __first1 != __last1; ++__first1, ++__first2) iter_swap(__first1, __first2); return __first2; @@ -497,9 +529,12 @@ _ForwardIter2 swap_ranges(_ForwardIter1 __first1, _ForwardIter1 __last1, template <class _InputIter, class _OutputIter, class _UnaryOperation> _OutputIter transform(_InputIter __first, _InputIter __last, - _OutputIter __result, _UnaryOperation __unary_op) { - __STL_REQUIRES(_InputIter, _InputIterator); - __STL_REQUIRES(_OutputIter, _OutputIterator); + _OutputIter __result, _UnaryOperation __unary_op) +{ + // concept requirements + glibcpp_function_requires(InputIteratorConcept<_InputIter>); + glibcpp_function_requires(OutputIteratorConcept<_OutputIter, + typename iterator_traits<_InputIter>::value_type>); for ( ; __first != __last; ++__first, ++__result) *__result = __unary_op(*__first); @@ -510,10 +545,15 @@ template <class _InputIter1, class _InputIter2, class _OutputIter, class _BinaryOperation> _OutputIter transform(_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2, _OutputIter __result, - _BinaryOperation __binary_op) { - __STL_REQUIRES(_InputIter1, _InputIterator); - __STL_REQUIRES(_InputIter2, _InputIterator); - __STL_REQUIRES(_OutputIter, _OutputIterator); + _BinaryOperation __binary_op) +{ + // concept requirements + glibcpp_function_requires(InputIteratorConcept<_InputIter1>); + glibcpp_function_requires(InputIteratorConcept<_InputIter2>); + glibcpp_function_requires(OutputIteratorConcept<_OutputIter, + // XXX really should be "the type returned by _BinaryOperation + typename iterator_traits<_InputIter1>::value_type>); + for ( ; __first1 != __last1; ++__first1, ++__first2, ++__result) *__result = __binary_op(*__first1, *__first2); return __result; @@ -523,11 +563,15 @@ _OutputIter transform(_InputIter1 __first1, _InputIter1 __last1, template <class _ForwardIter, class _Tp> void replace(_ForwardIter __first, _ForwardIter __last, - const _Tp& __old_value, const _Tp& __new_value) { - __STL_REQUIRES(_ForwardIter, _Mutable_ForwardIterator); - __STL_REQUIRES_BINARY_OP(_OP_EQUAL, bool, - typename iterator_traits<_ForwardIter>::value_type, _Tp); - __STL_CONVERTIBLE(_Tp, typename iterator_traits<_ForwardIter>::value_type); + const _Tp& __old_value, const _Tp& __new_value) +{ + // concept requirements + glibcpp_function_requires(Mutable_ForwardIteratorConcept<_ForwardIter>); + glibcpp_function_requires(EqualOpConcept< + typename iterator_traits<_ForwardIter>::value_type, _Tp>); + glibcpp_function_requires(ConvertibleConcept<_Tp, + typename iterator_traits<_ForwardIter>::value_type>); + for ( ; __first != __last; ++__first) if (*__first == __old_value) *__first = __new_value; @@ -535,11 +579,15 @@ void replace(_ForwardIter __first, _ForwardIter __last, template <class _ForwardIter, class _Predicate, class _Tp> void replace_if(_ForwardIter __first, _ForwardIter __last, - _Predicate __pred, const _Tp& __new_value) { - __STL_REQUIRES(_ForwardIter, _Mutable_ForwardIterator); - __STL_CONVERTIBLE(_Tp, typename iterator_traits<_ForwardIter>::value_type); - __STL_UNARY_FUNCTION_CHECK(_Predicate, bool, - typename iterator_traits<_ForwardIter>::value_type); + _Predicate __pred, const _Tp& __new_value) +{ + // concept requirements + glibcpp_function_requires(Mutable_ForwardIteratorConcept<_ForwardIter>); + glibcpp_function_requires(ConvertibleConcept<_Tp, + typename iterator_traits<_ForwardIter>::value_type>); + glibcpp_function_requires(UnaryPredicateConcept<_Predicate, + typename iterator_traits<_ForwardIter>::value_type>); + for ( ; __first != __last; ++__first) if (__pred(*__first)) *__first = __new_value; @@ -548,11 +596,15 @@ void replace_if(_ForwardIter __first, _ForwardIter __last, template <class _InputIter, class _OutputIter, class _Tp> _OutputIter replace_copy(_InputIter __first, _InputIter __last, _OutputIter __result, - const _Tp& __old_value, const _Tp& __new_value) { - __STL_REQUIRES(_InputIter, _InputIterator); - __STL_REQUIRES(_OutputIter, _OutputIterator); - __STL_REQUIRES_BINARY_OP(_OP_EQUAL, bool, - typename iterator_traits<_InputIter>::value_type, _Tp); + const _Tp& __old_value, const _Tp& __new_value) +{ + // concept requirements + glibcpp_function_requires(InputIteratorConcept<_InputIter>); + glibcpp_function_requires(OutputIteratorConcept<_OutputIter, + typename iterator_traits<_InputIter>::value_type>); + glibcpp_function_requires(EqualOpConcept< + typename iterator_traits<_InputIter>::value_type, _Tp>); + for ( ; __first != __last; ++__first, ++__result) *__result = *__first == __old_value ? __new_value : *__first; return __result; @@ -561,11 +613,15 @@ _OutputIter replace_copy(_InputIter __first, _InputIter __last, template <class _InputIter, class _OutputIter, class _Predicate, class _Tp> _OutputIter replace_copy_if(_InputIter __first, _InputIter __last, _OutputIter __result, - _Predicate __pred, const _Tp& __new_value) { - __STL_REQUIRES(_InputIter, _InputIterator); - __STL_REQUIRES(_OutputIter, _OutputIterator); - __STL_UNARY_FUNCTION_CHECK(_Predicate, bool, - typename iterator_traits<_InputIter>::value_type); + _Predicate __pred, const _Tp& __new_value) +{ + // concept requirements + glibcpp_function_requires(InputIteratorConcept<_InputIter>); + glibcpp_function_requires(OutputIteratorConcept<_OutputIter, + typename iterator_traits<_InputIter>::value_type>); + glibcpp_function_requires(UnaryPredicateConcept<_Predicate, + typename iterator_traits<_InputIter>::value_type>); + for ( ; __first != __last; ++__first, ++__result) *__result = __pred(*__first) ? __new_value : *__first; return __result; @@ -574,17 +630,26 @@ _OutputIter replace_copy_if(_InputIter __first, _InputIter __last, // generate and generate_n template <class _ForwardIter, class _Generator> -void generate(_ForwardIter __first, _ForwardIter __last, _Generator __gen) { - __STL_REQUIRES(_ForwardIter, _ForwardIterator); - __STL_GENERATOR_CHECK(_Generator, - typename iterator_traits<_ForwardIter>::value_type); +void generate(_ForwardIter __first, _ForwardIter __last, _Generator __gen) +{ + // concept requirements + glibcpp_function_requires(ForwardIteratorConcept<_ForwardIter>); + glibcpp_function_requires(GeneratorConcept<_Generator, + typename iterator_traits<_ForwardIter>::value_type>); + for ( ; __first != __last; ++__first) *__first = __gen(); } template <class _OutputIter, class _Size, class _Generator> -_OutputIter generate_n(_OutputIter __first, _Size __n, _Generator __gen) { - __STL_REQUIRES(_OutputIter, _OutputIterator); +_OutputIter generate_n(_OutputIter __first, _Size __n, _Generator __gen) +{ +/* + // XXX concept requirements + glibcpp_function_requires(OutputIteratorConcept<_OutputIter, + "the return type of _Generator" ?? >); +*/ + for ( ; __n > 0; --__n, ++__first) *__first = __gen(); return __first; @@ -594,11 +659,15 @@ _OutputIter generate_n(_OutputIter __first, _Size __n, _Generator __gen) { template <class _InputIter, class _OutputIter, class _Tp> _OutputIter remove_copy(_InputIter __first, _InputIter __last, - _OutputIter __result, const _Tp& __value) { - __STL_REQUIRES(_InputIter, _InputIterator); - __STL_REQUIRES(_OutputIter, _OutputIterator); - __STL_REQUIRES_BINARY_OP(_OP_EQUAL, bool, - typename iterator_traits<_InputIter>::value_type, _Tp); + _OutputIter __result, const _Tp& __value) +{ + // concept requirements + glibcpp_function_requires(InputIteratorConcept<_InputIter>); + glibcpp_function_requires(OutputIteratorConcept<_OutputIter, + typename iterator_traits<_InputIter>::value_type>); + glibcpp_function_requires(EqualOpConcept< + typename iterator_traits<_InputIter>::value_type, _Tp>); + for ( ; __first != __last; ++__first) if (!(*__first == __value)) { *__result = *__first; @@ -609,11 +678,15 @@ _OutputIter remove_copy(_InputIter __first, _InputIter __last, template <class _InputIter, class _OutputIter, class _Predicate> _OutputIter remove_copy_if(_InputIter __first, _InputIter __last, - _OutputIter __result, _Predicate __pred) { - __STL_REQUIRES(_InputIter, _InputIterator); - __STL_REQUIRES(_OutputIter, _OutputIterator); - __STL_UNARY_FUNCTION_CHECK(_Predicate, bool, - typename iterator_traits<_InputIter>::value_type); + _OutputIter __result, _Predicate __pred) +{ + // concept requirements + glibcpp_function_requires(InputIteratorConcept<_InputIter>); + glibcpp_function_requires(OutputIteratorConcept<_OutputIter, + typename iterator_traits<_InputIter>::value_type>); + glibcpp_function_requires(UnaryPredicateConcept<_Predicate, + typename iterator_traits<_InputIter>::value_type>); + for ( ; __first != __last; ++__first) if (!__pred(*__first)) { *__result = *__first; @@ -624,11 +697,15 @@ _OutputIter remove_copy_if(_InputIter __first, _InputIter __last, template <class _ForwardIter, class _Tp> _ForwardIter remove(_ForwardIter __first, _ForwardIter __last, - const _Tp& __value) { - __STL_REQUIRES(_ForwardIter, _Mutable_ForwardIterator); - __STL_REQUIRES_BINARY_OP(_OP_EQUAL, bool, - typename iterator_traits<_ForwardIter>::value_type, _Tp); - __STL_CONVERTIBLE(_Tp, typename iterator_traits<_ForwardIter>::value_type); + const _Tp& __value) +{ + // concept requirements + glibcpp_function_requires(Mutable_ForwardIteratorConcept<_ForwardIter>); + glibcpp_function_requires(ConvertibleConcept<_Tp, + typename iterator_traits<_ForwardIter>::value_type>); + glibcpp_function_requires(EqualOpConcept< + typename iterator_traits<_ForwardIter>::value_type, _Tp>); + __first = find(__first, __last, __value); _ForwardIter __i = __first; return __first == __last ? __first @@ -637,10 +714,13 @@ _ForwardIter remove(_ForwardIter __first, _ForwardIter __last, template <class _ForwardIter, class _Predicate> _ForwardIter remove_if(_ForwardIter __first, _ForwardIter __last, - _Predicate __pred) { - __STL_REQUIRES(_ForwardIter, _Mutable_ForwardIterator); - __STL_UNARY_FUNCTION_CHECK(_Predicate, bool, - typename iterator_traits<_ForwardIter>::value_type); + _Predicate __pred) +{ + // concept requirements + glibcpp_function_requires(Mutable_ForwardIteratorConcept<_ForwardIter>); + glibcpp_function_requires(UnaryPredicateConcept<_Predicate, + typename iterator_traits<_ForwardIter>::value_type>); + __first = find_if(__first, __last, __pred); _ForwardIter __i = __first; return __first == __last ? __first @@ -651,7 +731,9 @@ _ForwardIter remove_if(_ForwardIter __first, _ForwardIter __last, template <class _InputIter, class _OutputIter, class _Tp> _OutputIter __unique_copy(_InputIter __first, _InputIter __last, - _OutputIter __result, _Tp*) { + _OutputIter __result, _Tp*) +{ + // concept requirements -- taken care of in dispatching function _Tp __value = *__first; *__result = __value; while (++__first != __last) @@ -665,13 +747,17 @@ _OutputIter __unique_copy(_InputIter __first, _InputIter __last, template <class _InputIter, class _OutputIter> inline _OutputIter __unique_copy(_InputIter __first, _InputIter __last, _OutputIter __result, - output_iterator_tag) { - return __unique_copy(__first, __last, __result, __VALUE_TYPE(__first)); + output_iterator_tag) +{ + // concept requirements -- taken care of in dispatching function + return __unique_copy(__first, __last, __result, __value_type(__first)); } template <class _InputIter, class _ForwardIter> _ForwardIter __unique_copy(_InputIter __first, _InputIter __last, - _ForwardIter __result, forward_iterator_tag) { + _ForwardIter __result, forward_iterator_tag) +{ + // concept requirements -- taken care of in dispatching function *__result = *__first; while (++__first != __last) if (!(*__result == *__first)) @@ -681,22 +767,29 @@ _ForwardIter __unique_copy(_InputIter __first, _InputIter __last, template <class _InputIter, class _OutputIter> inline _OutputIter unique_copy(_InputIter __first, _InputIter __last, - _OutputIter __result) { - __STL_REQUIRES(_InputIter, _InputIterator); - __STL_REQUIRES(_OutputIter, _OutputIterator); - __STL_REQUIRES(typename iterator_traits<_InputIter>::value_type, - _EqualityComparable); + _OutputIter __result) +{ + // concept requirements + glibcpp_function_requires(InputIteratorConcept<_InputIter>); + glibcpp_function_requires(OutputIteratorConcept<_OutputIter, + typename iterator_traits<_InputIter>::value_type>); + glibcpp_function_requires(EqualityComparableConcept< + typename iterator_traits<_InputIter>::value_type>); + if (__first == __last) return __result; return __unique_copy(__first, __last, __result, - __ITERATOR_CATEGORY(__result)); + __iterator_category(__result)); } template <class _InputIter, class _OutputIter, class _BinaryPredicate, class _Tp> _OutputIter __unique_copy(_InputIter __first, _InputIter __last, _OutputIter __result, - _BinaryPredicate __binary_pred, _Tp*) { - __STL_BINARY_FUNCTION_CHECK(_BinaryPredicate, bool, _Tp, _Tp); + _BinaryPredicate __binary_pred, _Tp*) +{ + // concept requirements -- iterators already checked + glibcpp_function_requires(BinaryPredicateConcept<_BinaryPredicate, _Tp, _Tp>); + _Tp __value = *__first; *__result = __value; while (++__first != __last) @@ -711,19 +804,24 @@ template <class _InputIter, class _OutputIter, class _BinaryPredicate> inline _OutputIter __unique_copy(_InputIter __first, _InputIter __last, _OutputIter __result, _BinaryPredicate __binary_pred, - output_iterator_tag) { + output_iterator_tag) +{ + // concept requirements -- taken care of in dispatching function return __unique_copy(__first, __last, __result, __binary_pred, - __VALUE_TYPE(__first)); + __value_type(__first)); } template <class _InputIter, class _ForwardIter, class _BinaryPredicate> _ForwardIter __unique_copy(_InputIter __first, _InputIter __last, _ForwardIter __result, _BinaryPredicate __binary_pred, - forward_iterator_tag) { - __STL_BINARY_FUNCTION_CHECK(_BinaryPredicate, bool, - typename iterator_traits<_ForwardIter>::value_type, - typename iterator_traits<_InputIter>::value_type); + forward_iterator_tag) +{ + // concept requirements -- iterators already checked + glibcpp_function_requires(BinaryPredicateConcept<_BinaryPredicate, + typename iterator_traits<_ForwardIter>::value_type, + typename iterator_traits<_InputIter>::value_type>); + *__result = *__first; while (++__first != __last) if (!__binary_pred(*__result, *__first)) *++__result = *__first; @@ -733,30 +831,40 @@ _ForwardIter __unique_copy(_InputIter __first, _InputIter __last, template <class _InputIter, class _OutputIter, class _BinaryPredicate> inline _OutputIter unique_copy(_InputIter __first, _InputIter __last, _OutputIter __result, - _BinaryPredicate __binary_pred) { - __STL_REQUIRES(_InputIter, _InputIterator); - __STL_REQUIRES(_OutputIter, _OutputIterator); + _BinaryPredicate __binary_pred) +{ + // concept requirements -- predicates checked later + glibcpp_function_requires(InputIteratorConcept<_InputIter>); + glibcpp_function_requires(OutputIteratorConcept<_OutputIter, + typename iterator_traits<_InputIter>::value_type>); + if (__first == __last) return __result; return __unique_copy(__first, __last, __result, __binary_pred, - __ITERATOR_CATEGORY(__result)); + __iterator_category(__result)); } template <class _ForwardIter> -_ForwardIter unique(_ForwardIter __first, _ForwardIter __last) { - __STL_REQUIRES(_ForwardIter, _Mutable_ForwardIterator); - __STL_REQUIRES(typename iterator_traits<_ForwardIter>::value_type, - _EqualityComparable); +_ForwardIter unique(_ForwardIter __first, _ForwardIter __last) +{ + // concept requirements + glibcpp_function_requires(Mutable_ForwardIteratorConcept<_ForwardIter>); + glibcpp_function_requires(EqualityComparableConcept< + typename iterator_traits<_ForwardIter>::value_type>); + __first = adjacent_find(__first, __last); return unique_copy(__first, __last, __first); } template <class _ForwardIter, class _BinaryPredicate> _ForwardIter unique(_ForwardIter __first, _ForwardIter __last, - _BinaryPredicate __binary_pred) { - __STL_REQUIRES(_ForwardIter, _Mutable_ForwardIterator); - __STL_BINARY_FUNCTION_CHECK(_BinaryPredicate, bool, - typename iterator_traits<_ForwardIter>::value_type, - typename iterator_traits<_ForwardIter>::value_type); + _BinaryPredicate __binary_pred) +{ + // concept requirements + glibcpp_function_requires(Mutable_ForwardIteratorConcept<_ForwardIter>); + glibcpp_function_requires(BinaryPredicateConcept<_BinaryPredicate, + typename iterator_traits<_ForwardIter>::value_type, + typename iterator_traits<_ForwardIter>::value_type>); + __first = adjacent_find(__first, __last, __binary_pred); return unique_copy(__first, __last, __first, __binary_pred); } @@ -781,17 +889,24 @@ void __reverse(_RandomAccessIter __first, _RandomAccessIter __last, } template <class _BidirectionalIter> -inline void reverse(_BidirectionalIter __first, _BidirectionalIter __last) { - __STL_REQUIRES(_BidirectionalIter, _Mutable_BidirectionalIterator); - __reverse(__first, __last, __ITERATOR_CATEGORY(__first)); +inline void reverse(_BidirectionalIter __first, _BidirectionalIter __last) +{ + // concept requirements + glibcpp_function_requires(Mutable_BidirectionalIteratorConcept< + _BidirectionalIter>); + __reverse(__first, __last, __iterator_category(__first)); } template <class _BidirectionalIter, class _OutputIter> _OutputIter reverse_copy(_BidirectionalIter __first, _BidirectionalIter __last, - _OutputIter __result) { - __STL_REQUIRES(_BidirectionalIter, _BidirectionalIterator); - __STL_REQUIRES(_OutputIter, _OutputIterator); + _OutputIter __result) +{ + // concept requirements + glibcpp_function_requires(BidirectionalIteratorConcept<_BidirectionalIter>); + glibcpp_function_requires(OutputIteratorConcept<_OutputIter, + typename iterator_traits<_BidirectionalIter>::value_type>); + while (__first != __last) { --__last; *__result = *__last; @@ -819,7 +934,8 @@ _ForwardIter __rotate(_ForwardIter __first, _ForwardIter __middle, _ForwardIter __last, _Distance*, - forward_iterator_tag) { + forward_iterator_tag) +{ if (__first == __middle) return __last; if (__last == __middle) @@ -853,8 +969,12 @@ _BidirectionalIter __rotate(_BidirectionalIter __first, _BidirectionalIter __middle, _BidirectionalIter __last, _Distance*, - bidirectional_iterator_tag) { - __STL_REQUIRES(_BidirectionalIter, _Mutable_BidirectionalIterator); + bidirectional_iterator_tag) +{ + // concept requirements + glibcpp_function_requires(Mutable_BidirectionalIteratorConcept< + _BidirectionalIter>); + if (__first == __middle) return __last; if (__last == __middle) @@ -880,8 +1000,12 @@ template <class _RandomAccessIter, class _Distance, class _Tp> _RandomAccessIter __rotate(_RandomAccessIter __first, _RandomAccessIter __middle, _RandomAccessIter __last, - _Distance *, _Tp *) { - __STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator); + _Distance *, _Tp *) +{ + // concept requirements + glibcpp_function_requires(Mutable_RandomAccessIteratorConcept< + _RandomAccessIter>); + _Distance __n = __last - __first; _Distance __k = __middle - __first; _Distance __l = __n - __k; @@ -934,18 +1058,25 @@ _RandomAccessIter __rotate(_RandomAccessIter __first, template <class _ForwardIter> inline _ForwardIter rotate(_ForwardIter __first, _ForwardIter __middle, - _ForwardIter __last) { - __STL_REQUIRES(_ForwardIter, _Mutable_ForwardIterator); + _ForwardIter __last) +{ + // concept requirements + glibcpp_function_requires(Mutable_ForwardIteratorConcept<_ForwardIter>); + return __rotate(__first, __middle, __last, - __DISTANCE_TYPE(__first), - __ITERATOR_CATEGORY(__first)); + __distance_type(__first), + __iterator_category(__first)); } template <class _ForwardIter, class _OutputIter> _OutputIter rotate_copy(_ForwardIter __first, _ForwardIter __middle, - _ForwardIter __last, _OutputIter __result) { - __STL_REQUIRES(_ForwardIter, _ForwardIterator); - __STL_REQUIRES(_OutputIter, _OutputIterator); + _ForwardIter __last, _OutputIter __result) +{ + // concept requirements + glibcpp_function_requires(ForwardIteratorConcept<_ForwardIter>); + glibcpp_function_requires(OutputIteratorConcept<_OutputIter, + typename iterator_traits<_ForwardIter>::value_type>); + return copy(__first, __middle, copy(__middle, __last, __result)); } @@ -966,8 +1097,12 @@ inline _Distance __random_number(_Distance __n) { template <class _RandomAccessIter> inline void random_shuffle(_RandomAccessIter __first, - _RandomAccessIter __last) { - __STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator); + _RandomAccessIter __last) +{ + // concept requirements + glibcpp_function_requires(Mutable_RandomAccessIteratorConcept< + _RandomAccessIter>); + if (__first == __last) return; for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i) iter_swap(__i, __first + __random_number((__i - __first) + 1)); @@ -975,8 +1110,12 @@ inline void random_shuffle(_RandomAccessIter __first, template <class _RandomAccessIter, class _RandomNumberGenerator> void random_shuffle(_RandomAccessIter __first, _RandomAccessIter __last, - _RandomNumberGenerator& __rand) { - __STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator); + _RandomNumberGenerator& __rand) +{ + // concept requirements + glibcpp_function_requires(Mutable_RandomAccessIteratorConcept< + _RandomAccessIter>); + if (__first == __last) return; for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i) iter_swap(__i, __first + __rand((__i - __first) + 1)); @@ -988,8 +1127,11 @@ template <class _ForwardIter, class _OutputIter, class _Distance> _OutputIter random_sample_n(_ForwardIter __first, _ForwardIter __last, _OutputIter __out, const _Distance __n) { - __STL_REQUIRES(_ForwardIter, _ForwardIterator); - __STL_REQUIRES(_OutputIter, _OutputIterator); + // concept requirements + glibcpp_function_requires(ForwardIteratorConcept<_ForwardIter>); + glibcpp_function_requires(OutputIteratorConcept<_OutputIter, + typename iterator_traits<_ForwardIter>::value_type>); + _Distance __remaining = 0; distance(__first, __last, __remaining); _Distance __m = min(__n, __remaining); @@ -1013,9 +1155,13 @@ _OutputIter random_sample_n(_ForwardIter __first, _ForwardIter __last, _OutputIter __out, const _Distance __n, _RandomNumberGenerator& __rand) { - __STL_REQUIRES(_ForwardIter, _ForwardIterator); - __STL_REQUIRES(_OutputIter, _OutputIterator); - __STL_UNARY_FUNCTION_CHECK(_RandomNumberGenerator, _Distance, _Distance); + // concept requirements + glibcpp_function_requires(ForwardIteratorConcept<_ForwardIter>); + glibcpp_function_requires(OutputIteratorConcept<_OutputIter, + typename iterator_traits<_ForwardIter>::value_type>); + glibcpp_function_requires(UnaryFunctionConcept< + _RandomNumberGenerator, _Distance, _Distance>); + _Distance __remaining = 0; distance(__first, __last, __remaining); _Distance __m = min(__n, __remaining); @@ -1061,7 +1207,10 @@ _RandomAccessIter __random_sample(_InputIter __first, _InputIter __last, _RandomNumberGenerator& __rand, const _Distance __n) { - __STL_UNARY_FUNCTION_CHECK(_RandomNumberGenerator, _Distance, _Distance); + // concept requirements + glibcpp_function_requires(UnaryFunctionConcept< + _RandomNumberGenerator, _Distance, _Distance>); + _Distance __m = 0; _Distance __t = __n; for ( ; __first != __last && __m < __n; ++__m, ++__first) @@ -1083,8 +1232,11 @@ inline _RandomAccessIter random_sample(_InputIter __first, _InputIter __last, _RandomAccessIter __out_first, _RandomAccessIter __out_last) { - __STL_REQUIRES(_InputIter, _InputIterator); - __STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator); + // concept requirements + glibcpp_function_requires(InputIteratorConcept<_InputIter>); + glibcpp_function_requires(Mutable_RandomAccessIteratorConcept< + _RandomAccessIter>); + return __random_sample(__first, __last, __out_first, __out_last - __out_first); } @@ -1097,8 +1249,11 @@ random_sample(_InputIter __first, _InputIter __last, _RandomAccessIter __out_first, _RandomAccessIter __out_last, _RandomNumberGenerator& __rand) { - __STL_REQUIRES(_InputIter, _InputIterator); - __STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator); + // concept requirements + glibcpp_function_requires(InputIteratorConcept<_InputIter>); + glibcpp_function_requires(Mutable_RandomAccessIteratorConcept< + _RandomAccessIter>); + return __random_sample(__first, __last, __out_first, __rand, __out_last - __out_first); @@ -1110,7 +1265,8 @@ template <class _ForwardIter, class _Predicate> _ForwardIter __partition(_ForwardIter __first, _ForwardIter __last, _Predicate __pred, - forward_iterator_tag) { + forward_iterator_tag) +{ if (__first == __last) return __first; while (__pred(*__first)) @@ -1131,7 +1287,8 @@ template <class _BidirectionalIter, class _Predicate> _BidirectionalIter __partition(_BidirectionalIter __first, _BidirectionalIter __last, _Predicate __pred, - bidirectional_iterator_tag) { + bidirectional_iterator_tag) +{ while (true) { while (true) if (__first == __last) @@ -1156,18 +1313,22 @@ _BidirectionalIter __partition(_BidirectionalIter __first, template <class _ForwardIter, class _Predicate> inline _ForwardIter partition(_ForwardIter __first, _ForwardIter __last, - _Predicate __pred) { - __STL_REQUIRES(_ForwardIter, _Mutable_ForwardIterator); - __STL_UNARY_FUNCTION_CHECK(_Predicate, bool, - typename iterator_traits<_ForwardIter>::value_type); - return __partition(__first, __last, __pred, __ITERATOR_CATEGORY(__first)); + _Predicate __pred) +{ + // concept requirements + glibcpp_function_requires(Mutable_ForwardIteratorConcept<_ForwardIter>); + glibcpp_function_requires(UnaryPredicateConcept<_Predicate, + typename iterator_traits<_ForwardIter>::value_type>); + + return __partition(__first, __last, __pred, __iterator_category(__first)); } template <class _ForwardIter, class _Predicate, class _Distance> _ForwardIter __inplace_stable_partition(_ForwardIter __first, _ForwardIter __last, - _Predicate __pred, _Distance __len) { + _Predicate __pred, _Distance __len) +{ if (__len == 1) return __pred(*__first) ? __last : __first; _ForwardIter __middle = __first; @@ -1233,16 +1394,19 @@ __stable_partition_aux(_ForwardIter __first, _ForwardIter __last, template <class _ForwardIter, class _Predicate> inline _ForwardIter stable_partition(_ForwardIter __first, _ForwardIter __last, - _Predicate __pred) { - __STL_REQUIRES(_ForwardIter, _Mutable_ForwardIterator); - __STL_UNARY_FUNCTION_CHECK(_Predicate, bool, - typename iterator_traits<_ForwardIter>::value_type); + _Predicate __pred) +{ + // concept requirements + glibcpp_function_requires(Mutable_ForwardIteratorConcept<_ForwardIter>); + glibcpp_function_requires(UnaryPredicateConcept<_Predicate, + typename iterator_traits<_ForwardIter>::value_type>); + if (__first == __last) return __first; else return __stable_partition_aux(__first, __last, __pred, - __VALUE_TYPE(__first), - __DISTANCE_TYPE(__first)); + __value_type(__first), + __distance_type(__first)); } template <class _RandomAccessIter, class _Tp> @@ -1286,7 +1450,8 @@ const int __stl_threshold = 16; // sort() and its auxiliary functions. template <class _RandomAccessIter, class _Tp> -void __unguarded_linear_insert(_RandomAccessIter __last, _Tp __val) { +void __unguarded_linear_insert(_RandomAccessIter __last, _Tp __val) +{ _RandomAccessIter __next = __last; --__next; while (__val < *__next) { @@ -1299,7 +1464,8 @@ void __unguarded_linear_insert(_RandomAccessIter __last, _Tp __val) { template <class _RandomAccessIter, class _Tp, class _Compare> void __unguarded_linear_insert(_RandomAccessIter __last, _Tp __val, - _Compare __comp) { + _Compare __comp) +{ _RandomAccessIter __next = __last; --__next; while (__comp(__val, *__next)) { @@ -1312,7 +1478,8 @@ void __unguarded_linear_insert(_RandomAccessIter __last, _Tp __val, template <class _RandomAccessIter, class _Tp> inline void __linear_insert(_RandomAccessIter __first, - _RandomAccessIter __last, _Tp*) { + _RandomAccessIter __last, _Tp*) +{ _Tp __val = *__last; if (__val < *__first) { copy_backward(__first, __last, __last + 1); @@ -1324,7 +1491,8 @@ inline void __linear_insert(_RandomAccessIter __first, template <class _RandomAccessIter, class _Tp, class _Compare> inline void __linear_insert(_RandomAccessIter __first, - _RandomAccessIter __last, _Tp*, _Compare __comp) { + _RandomAccessIter __last, _Tp*, _Compare __comp) +{ _Tp __val = *__last; if (__comp(__val, *__first)) { copy_backward(__first, __last, __last + 1); @@ -1335,23 +1503,26 @@ inline void __linear_insert(_RandomAccessIter __first, } template <class _RandomAccessIter> -void __insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last) { +void __insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last) +{ if (__first == __last) return; for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i) - __linear_insert(__first, __i, __VALUE_TYPE(__first)); + __linear_insert(__first, __i, __value_type(__first)); } template <class _RandomAccessIter, class _Compare> void __insertion_sort(_RandomAccessIter __first, - _RandomAccessIter __last, _Compare __comp) { + _RandomAccessIter __last, _Compare __comp) +{ if (__first == __last) return; for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i) - __linear_insert(__first, __i, __VALUE_TYPE(__first), __comp); + __linear_insert(__first, __i, __value_type(__first), __comp); } template <class _RandomAccessIter, class _Tp> void __unguarded_insertion_sort_aux(_RandomAccessIter __first, - _RandomAccessIter __last, _Tp*) { + _RandomAccessIter __last, _Tp*) +{ for (_RandomAccessIter __i = __first; __i != __last; ++__i) __unguarded_linear_insert(__i, _Tp(*__i)); } @@ -1359,13 +1530,14 @@ void __unguarded_insertion_sort_aux(_RandomAccessIter __first, template <class _RandomAccessIter> inline void __unguarded_insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last) { - __unguarded_insertion_sort_aux(__first, __last, __VALUE_TYPE(__first)); + __unguarded_insertion_sort_aux(__first, __last, __value_type(__first)); } template <class _RandomAccessIter, class _Tp, class _Compare> void __unguarded_insertion_sort_aux(_RandomAccessIter __first, _RandomAccessIter __last, - _Tp*, _Compare __comp) { + _Tp*, _Compare __comp) +{ for (_RandomAccessIter __i = __first; __i != __last; ++__i) __unguarded_linear_insert(__i, _Tp(*__i), __comp); } @@ -1373,14 +1545,16 @@ void __unguarded_insertion_sort_aux(_RandomAccessIter __first, template <class _RandomAccessIter, class _Compare> inline void __unguarded_insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last, - _Compare __comp) { - __unguarded_insertion_sort_aux(__first, __last, __VALUE_TYPE(__first), + _Compare __comp) +{ + __unguarded_insertion_sort_aux(__first, __last, __value_type(__first), __comp); } template <class _RandomAccessIter> void __final_insertion_sort(_RandomAccessIter __first, - _RandomAccessIter __last) { + _RandomAccessIter __last) +{ if (__last - __first > __stl_threshold) { __insertion_sort(__first, __first + __stl_threshold); __unguarded_insertion_sort(__first + __stl_threshold, __last); @@ -1391,7 +1565,8 @@ void __final_insertion_sort(_RandomAccessIter __first, template <class _RandomAccessIter, class _Compare> void __final_insertion_sort(_RandomAccessIter __first, - _RandomAccessIter __last, _Compare __comp) { + _RandomAccessIter __last, _Compare __comp) +{ if (__last - __first > __stl_threshold) { __insertion_sort(__first, __first + __stl_threshold, __comp); __unguarded_insertion_sort(__first + __stl_threshold, __last, __comp); @@ -1401,7 +1576,8 @@ void __final_insertion_sort(_RandomAccessIter __first, } template <class _Size> -inline _Size __lg(_Size __n) { +inline _Size __lg(_Size __n) +{ _Size __k; for (__k = 0; __n != 1; __n >>= 1) ++__k; return __k; @@ -1451,13 +1627,17 @@ void __introsort_loop(_RandomAccessIter __first, } template <class _RandomAccessIter> -inline void sort(_RandomAccessIter __first, _RandomAccessIter __last) { - __STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator); - __STL_REQUIRES(typename iterator_traits<_RandomAccessIter>::value_type, - _LessThanComparable); +inline void sort(_RandomAccessIter __first, _RandomAccessIter __last) +{ + // concept requirements + glibcpp_function_requires(Mutable_RandomAccessIteratorConcept< + _RandomAccessIter>); + glibcpp_function_requires(LessThanComparableConcept< + typename iterator_traits<_RandomAccessIter>::value_type>); + if (__first != __last) { __introsort_loop(__first, __last, - __VALUE_TYPE(__first), + __value_type(__first), __lg(__last - __first) * 2); __final_insertion_sort(__first, __last); } @@ -1465,14 +1645,18 @@ inline void sort(_RandomAccessIter __first, _RandomAccessIter __last) { template <class _RandomAccessIter, class _Compare> inline void sort(_RandomAccessIter __first, _RandomAccessIter __last, - _Compare __comp) { - __STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator); - __STL_BINARY_FUNCTION_CHECK(_Compare, bool, - typename iterator_traits<_RandomAccessIter>::value_type, - typename iterator_traits<_RandomAccessIter>::value_type); + _Compare __comp) +{ + // concept requirements + glibcpp_function_requires(Mutable_RandomAccessIteratorConcept< + _RandomAccessIter>); + glibcpp_function_requires(BinaryPredicateConcept<_Compare, + typename iterator_traits<_RandomAccessIter>::value_type, + typename iterator_traits<_RandomAccessIter>::value_type>); + if (__first != __last) { __introsort_loop(__first, __last, - __VALUE_TYPE(__first), + __value_type(__first), __lg(__last - __first) * 2, __comp); __final_insertion_sort(__first, __last, __comp); @@ -1483,7 +1667,8 @@ inline void sort(_RandomAccessIter __first, _RandomAccessIter __last, template <class _RandomAccessIter> void __inplace_stable_sort(_RandomAccessIter __first, - _RandomAccessIter __last) { + _RandomAccessIter __last) +{ if (__last - __first < 15) { __insertion_sort(__first, __last); return; @@ -1498,7 +1683,8 @@ void __inplace_stable_sort(_RandomAccessIter __first, template <class _RandomAccessIter, class _Compare> void __inplace_stable_sort(_RandomAccessIter __first, - _RandomAccessIter __last, _Compare __comp) { + _RandomAccessIter __last, _Compare __comp) +{ if (__last - __first < 15) { __insertion_sort(__first, __last, __comp); return; @@ -1516,7 +1702,8 @@ template <class _RandomAccessIter1, class _RandomAccessIter2, class _Distance> void __merge_sort_loop(_RandomAccessIter1 __first, _RandomAccessIter1 __last, - _RandomAccessIter2 __result, _Distance __step_size) { + _RandomAccessIter2 __result, _Distance __step_size) +{ _Distance __two_step = 2 * __step_size; while (__last - __first >= __two_step) { @@ -1536,7 +1723,8 @@ template <class _RandomAccessIter1, class _RandomAccessIter2, void __merge_sort_loop(_RandomAccessIter1 __first, _RandomAccessIter1 __last, _RandomAccessIter2 __result, _Distance __step_size, - _Compare __comp) { + _Compare __comp) +{ _Distance __two_step = 2 * __step_size; while (__last - __first >= __two_step) { @@ -1582,7 +1770,8 @@ void __chunk_insertion_sort(_RandomAccessIter __first, template <class _RandomAccessIter, class _Pointer, class _Distance> void __merge_sort_with_buffer(_RandomAccessIter __first, _RandomAccessIter __last, - _Pointer __buffer, _Distance*) { + _Pointer __buffer, _Distance*) +{ _Distance __len = __last - __first; _Pointer __buffer_last = __buffer + __len; @@ -1601,7 +1790,8 @@ template <class _RandomAccessIter, class _Pointer, class _Distance, class _Compare> void __merge_sort_with_buffer(_RandomAccessIter __first, _RandomAccessIter __last, _Pointer __buffer, - _Distance*, _Compare __comp) { + _Distance*, _Compare __comp) +{ _Distance __len = __last - __first; _Pointer __buffer_last = __buffer + __len; @@ -1619,7 +1809,8 @@ void __merge_sort_with_buffer(_RandomAccessIter __first, template <class _RandomAccessIter, class _Pointer, class _Distance> void __stable_sort_adaptive(_RandomAccessIter __first, _RandomAccessIter __last, _Pointer __buffer, - _Distance __buffer_size) { + _Distance __buffer_size) +{ _Distance __len = (__last - __first + 1) / 2; _RandomAccessIter __middle = __first + __len; if (__len > __buffer_size) { @@ -1638,7 +1829,8 @@ template <class _RandomAccessIter, class _Pointer, class _Distance, class _Compare> void __stable_sort_adaptive(_RandomAccessIter __first, _RandomAccessIter __last, _Pointer __buffer, - _Distance __buffer_size, _Compare __comp) { + _Distance __buffer_size, _Compare __comp) +{ _Distance __len = (__last - __first + 1) / 2; _RandomAccessIter __middle = __first + __len; if (__len > __buffer_size) { @@ -1660,7 +1852,8 @@ void __stable_sort_adaptive(_RandomAccessIter __first, template <class _RandomAccessIter, class _Tp, class _Distance> inline void __stable_sort_aux(_RandomAccessIter __first, - _RandomAccessIter __last, _Tp*, _Distance*) { + _RandomAccessIter __last, _Tp*, _Distance*) +{ _Temporary_buffer<_RandomAccessIter, _Tp> buf(__first, __last); if (buf.begin() == 0) __inplace_stable_sort(__first, __last); @@ -1672,7 +1865,8 @@ inline void __stable_sort_aux(_RandomAccessIter __first, template <class _RandomAccessIter, class _Tp, class _Distance, class _Compare> inline void __stable_sort_aux(_RandomAccessIter __first, _RandomAccessIter __last, _Tp*, _Distance*, - _Compare __comp) { + _Compare __comp) +{ _Temporary_buffer<_RandomAccessIter, _Tp> buf(__first, __last); if (buf.begin() == 0) __inplace_stable_sort(__first, __last, __comp); @@ -1684,25 +1878,33 @@ inline void __stable_sort_aux(_RandomAccessIter __first, template <class _RandomAccessIter> inline void stable_sort(_RandomAccessIter __first, - _RandomAccessIter __last) { - __STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator); - __STL_REQUIRES(typename iterator_traits<_RandomAccessIter>::value_type, - _LessThanComparable); + _RandomAccessIter __last) +{ + // concept requirements + glibcpp_function_requires(Mutable_RandomAccessIteratorConcept< + _RandomAccessIter>); + glibcpp_function_requires(LessThanComparableConcept< + typename iterator_traits<_RandomAccessIter>::value_type>); + __stable_sort_aux(__first, __last, - __VALUE_TYPE(__first), - __DISTANCE_TYPE(__first)); + __value_type(__first), + __distance_type(__first)); } template <class _RandomAccessIter, class _Compare> inline void stable_sort(_RandomAccessIter __first, - _RandomAccessIter __last, _Compare __comp) { - __STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator); - __STL_BINARY_FUNCTION_CHECK(_Compare, bool, - typename iterator_traits<_RandomAccessIter>::value_type, - typename iterator_traits<_RandomAccessIter>::value_type); + _RandomAccessIter __last, _Compare __comp) +{ + // concept requirements + glibcpp_function_requires(Mutable_RandomAccessIteratorConcept< + _RandomAccessIter>); + glibcpp_function_requires(BinaryPredicateConcept<_Compare, + typename iterator_traits<_RandomAccessIter>::value_type, + typename iterator_traits<_RandomAccessIter>::value_type>); + __stable_sort_aux(__first, __last, - __VALUE_TYPE(__first), - __DISTANCE_TYPE(__first), + __value_type(__first), + __distance_type(__first), __comp); } @@ -1710,45 +1912,55 @@ inline void stable_sort(_RandomAccessIter __first, template <class _RandomAccessIter, class _Tp> void __partial_sort(_RandomAccessIter __first, _RandomAccessIter __middle, - _RandomAccessIter __last, _Tp*) { + _RandomAccessIter __last, _Tp*) +{ make_heap(__first, __middle); for (_RandomAccessIter __i = __middle; __i < __last; ++__i) if (*__i < *__first) __pop_heap(__first, __middle, __i, _Tp(*__i), - __DISTANCE_TYPE(__first)); + __distance_type(__first)); sort_heap(__first, __middle); } template <class _RandomAccessIter> inline void partial_sort(_RandomAccessIter __first, _RandomAccessIter __middle, - _RandomAccessIter __last) { - __STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator); - __STL_REQUIRES(typename iterator_traits<_RandomAccessIter>::value_type, - _LessThanComparable); - __partial_sort(__first, __middle, __last, __VALUE_TYPE(__first)); + _RandomAccessIter __last) +{ + // concept requirements + glibcpp_function_requires(Mutable_RandomAccessIteratorConcept< + _RandomAccessIter>); + glibcpp_function_requires(LessThanComparableConcept< + typename iterator_traits<_RandomAccessIter>::value_type>); + + __partial_sort(__first, __middle, __last, __value_type(__first)); } template <class _RandomAccessIter, class _Tp, class _Compare> void __partial_sort(_RandomAccessIter __first, _RandomAccessIter __middle, - _RandomAccessIter __last, _Tp*, _Compare __comp) { + _RandomAccessIter __last, _Tp*, _Compare __comp) +{ make_heap(__first, __middle, __comp); for (_RandomAccessIter __i = __middle; __i < __last; ++__i) if (__comp(*__i, *__first)) __pop_heap(__first, __middle, __i, _Tp(*__i), __comp, - __DISTANCE_TYPE(__first)); + __distance_type(__first)); sort_heap(__first, __middle, __comp); } template <class _RandomAccessIter, class _Compare> inline void partial_sort(_RandomAccessIter __first, _RandomAccessIter __middle, - _RandomAccessIter __last, _Compare __comp) { - __STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator); - __STL_BINARY_FUNCTION_CHECK(_Compare, bool, - typename iterator_traits<_RandomAccessIter>::value_type, - typename iterator_traits<_RandomAccessIter>::value_type); - __partial_sort(__first, __middle, __last, __VALUE_TYPE(__first), __comp); + _RandomAccessIter __last, _Compare __comp) +{ + // concept requirements + glibcpp_function_requires(Mutable_RandomAccessIteratorConcept< + _RandomAccessIter>); + glibcpp_function_requires(BinaryPredicateConcept<_Compare, + typename iterator_traits<_RandomAccessIter>::value_type, + typename iterator_traits<_RandomAccessIter>::value_type>); + + __partial_sort(__first, __middle, __last, __value_type(__first), __comp); } template <class _InputIter, class _RandomAccessIter, class _Distance, @@ -1757,7 +1969,8 @@ _RandomAccessIter __partial_sort_copy(_InputIter __first, _InputIter __last, _RandomAccessIter __result_first, _RandomAccessIter __result_last, - _Distance*, _Tp*) { + _Distance*, _Tp*) +{ if (__result_first == __result_last) return __result_last; _RandomAccessIter __result_real_last = __result_first; while(__first != __last && __result_real_last != __result_last) { @@ -1781,18 +1994,21 @@ template <class _InputIter, class _RandomAccessIter> inline _RandomAccessIter partial_sort_copy(_InputIter __first, _InputIter __last, _RandomAccessIter __result_first, - _RandomAccessIter __result_last) { - __STL_REQUIRES(_InputIter, _InputIterator); - __STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator); - __STL_CONVERTIBLE(typename iterator_traits<_InputIter>::value_type, - typename iterator_traits<_RandomAccessIter>::value_type); - __STL_REQUIRES(typename iterator_traits<_RandomAccessIter>::value_type, - _LessThanComparable); - __STL_REQUIRES(typename iterator_traits<_InputIter>::value_type, - _LessThanComparable); + _RandomAccessIter __result_last) +{ + // concept requirements + glibcpp_function_requires(InputIteratorConcept<_InputIter>); + glibcpp_function_requires(ConvertibleConcept< + typename iterator_traits<_InputIter>::value_type, + typename iterator_traits<_RandomAccessIter>::value_type>); + glibcpp_function_requires(LessThanComparableConcept< + typename iterator_traits<_RandomAccessIter>::value_type>); + glibcpp_function_requires(LessThanComparableConcept< + typename iterator_traits<_InputIter>::value_type>); + return __partial_sort_copy(__first, __last, __result_first, __result_last, - __DISTANCE_TYPE(__result_first), - __VALUE_TYPE(__first)); + __distance_type(__result_first), + __value_type(__first)); } template <class _InputIter, class _RandomAccessIter, class _Compare, @@ -1801,7 +2017,8 @@ _RandomAccessIter __partial_sort_copy(_InputIter __first, _InputIter __last, _RandomAccessIter __result_first, _RandomAccessIter __result_last, - _Compare __comp, _Distance*, _Tp*) { + _Compare __comp, _Distance*, _Tp*) +{ if (__result_first == __result_last) return __result_last; _RandomAccessIter __result_real_last = __result_first; while(__first != __last && __result_real_last != __result_last) { @@ -1826,25 +2043,31 @@ template <class _InputIter, class _RandomAccessIter, class _Compare> inline _RandomAccessIter partial_sort_copy(_InputIter __first, _InputIter __last, _RandomAccessIter __result_first, - _RandomAccessIter __result_last, _Compare __comp) { - __STL_REQUIRES(_InputIter, _InputIterator); - __STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator); - __STL_CONVERTIBLE(typename iterator_traits<_InputIter>::value_type, - typename iterator_traits<_RandomAccessIter>::value_type); - __STL_BINARY_FUNCTION_CHECK(_Compare, bool, - typename iterator_traits<_RandomAccessIter>::value_type, - typename iterator_traits<_RandomAccessIter>::value_type); + _RandomAccessIter __result_last, _Compare __comp) +{ + // concept requirements + glibcpp_function_requires(InputIteratorConcept<_InputIter>); + glibcpp_function_requires(Mutable_RandomAccessIteratorConcept< + _RandomAccessIter>); + glibcpp_function_requires(ConvertibleConcept< + typename iterator_traits<_InputIter>::value_type, + typename iterator_traits<_RandomAccessIter>::value_type>); + glibcpp_function_requires(BinaryPredicateConcept<_Compare, + typename iterator_traits<_RandomAccessIter>::value_type, + typename iterator_traits<_RandomAccessIter>::value_type>); + return __partial_sort_copy(__first, __last, __result_first, __result_last, __comp, - __DISTANCE_TYPE(__result_first), - __VALUE_TYPE(__first)); + __distance_type(__result_first), + __value_type(__first)); } // nth_element() and its auxiliary functions. template <class _RandomAccessIter, class _Tp> void __nth_element(_RandomAccessIter __first, _RandomAccessIter __nth, - _RandomAccessIter __last, _Tp*) { + _RandomAccessIter __last, _Tp*) +{ while (__last - __first > 3) { _RandomAccessIter __cut = __unguarded_partition(__first, __last, @@ -1861,16 +2084,21 @@ void __nth_element(_RandomAccessIter __first, _RandomAccessIter __nth, template <class _RandomAccessIter> inline void nth_element(_RandomAccessIter __first, _RandomAccessIter __nth, - _RandomAccessIter __last) { - __STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator); - __STL_REQUIRES(typename iterator_traits<_RandomAccessIter>::value_type, - _LessThanComparable); - __nth_element(__first, __nth, __last, __VALUE_TYPE(__first)); + _RandomAccessIter __last) +{ + // concept requirements + glibcpp_function_requires(Mutable_RandomAccessIteratorConcept< + _RandomAccessIter>); + glibcpp_function_requires(LessThanComparableConcept< + typename iterator_traits<_RandomAccessIter>::value_type>); + + __nth_element(__first, __nth, __last, __value_type(__first)); } template <class _RandomAccessIter, class _Tp, class _Compare> void __nth_element(_RandomAccessIter __first, _RandomAccessIter __nth, - _RandomAccessIter __last, _Tp*, _Compare __comp) { + _RandomAccessIter __last, _Tp*, _Compare __comp) +{ while (__last - __first > 3) { _RandomAccessIter __cut = __unguarded_partition(__first, __last, @@ -1889,12 +2117,16 @@ void __nth_element(_RandomAccessIter __first, _RandomAccessIter __nth, template <class _RandomAccessIter, class _Compare> inline void nth_element(_RandomAccessIter __first, _RandomAccessIter __nth, - _RandomAccessIter __last, _Compare __comp) { - __STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator); - __STL_BINARY_FUNCTION_CHECK(_Compare, bool, - typename iterator_traits<_RandomAccessIter>::value_type, - typename iterator_traits<_RandomAccessIter>::value_type); - __nth_element(__first, __nth, __last, __VALUE_TYPE(__first), __comp); + _RandomAccessIter __last, _Compare __comp) +{ + // concept requirements + glibcpp_function_requires(Mutable_RandomAccessIteratorConcept< + _RandomAccessIter>); + glibcpp_function_requires(BinaryPredicateConcept<_Compare, + typename iterator_traits<_RandomAccessIter>::value_type, + typename iterator_traits<_RandomAccessIter>::value_type>); + + __nth_element(__first, __nth, __last, __value_type(__first), __comp); } @@ -1926,13 +2158,16 @@ _ForwardIter __lower_bound(_ForwardIter __first, _ForwardIter __last, template <class _ForwardIter, class _Tp> inline _ForwardIter lower_bound(_ForwardIter __first, _ForwardIter __last, - const _Tp& __val) { - __STL_REQUIRES(_ForwardIter, _ForwardIterator); - __STL_REQUIRES_SAME_TYPE(_Tp, - typename iterator_traits<_ForwardIter>::value_type); - __STL_REQUIRES(_Tp, _LessThanComparable); + const _Tp& __val) +{ + // concept requirements + glibcpp_function_requires(ForwardIteratorConcept<_ForwardIter>); + glibcpp_function_requires(SameTypeConcept<_Tp, + typename iterator_traits<_ForwardIter>::value_type>); + glibcpp_function_requires(LessThanComparableConcept<_Tp>); + return __lower_bound(__first, __last, __val, - __DISTANCE_TYPE(__first)); + __distance_type(__first)); } template <class _ForwardIter, class _Tp, class _Compare, class _Distance> @@ -1961,13 +2196,16 @@ _ForwardIter __lower_bound(_ForwardIter __first, _ForwardIter __last, template <class _ForwardIter, class _Tp, class _Compare> inline _ForwardIter lower_bound(_ForwardIter __first, _ForwardIter __last, - const _Tp& __val, _Compare __comp) { - __STL_REQUIRES(_ForwardIter, _ForwardIterator); - __STL_REQUIRES_SAME_TYPE(_Tp, - typename iterator_traits<_ForwardIter>::value_type); - __STL_BINARY_FUNCTION_CHECK(_Compare, bool, _Tp, _Tp); + const _Tp& __val, _Compare __comp) +{ + // concept requirements + glibcpp_function_requires(ForwardIteratorConcept<_ForwardIter>); + glibcpp_function_requires(SameTypeConcept<_Tp, + typename iterator_traits<_ForwardIter>::value_type>); + glibcpp_function_requires(BinaryPredicateConcept<_Compare, _Tp, _Tp>); + return __lower_bound(__first, __last, __val, __comp, - __DISTANCE_TYPE(__first)); + __distance_type(__first)); } template <class _ForwardIter, class _Tp, class _Distance> @@ -1996,13 +2234,16 @@ _ForwardIter __upper_bound(_ForwardIter __first, _ForwardIter __last, template <class _ForwardIter, class _Tp> inline _ForwardIter upper_bound(_ForwardIter __first, _ForwardIter __last, - const _Tp& __val) { - __STL_REQUIRES(_ForwardIter, _ForwardIterator); - __STL_REQUIRES_SAME_TYPE(_Tp, - typename iterator_traits<_ForwardIter>::value_type); - __STL_REQUIRES(_Tp, _LessThanComparable); + const _Tp& __val) +{ + // concept requirements + glibcpp_function_requires(ForwardIteratorConcept<_ForwardIter>); + glibcpp_function_requires(SameTypeConcept<_Tp, + typename iterator_traits<_ForwardIter>::value_type>); + glibcpp_function_requires(LessThanComparableConcept<_Tp>); + return __upper_bound(__first, __last, __val, - __DISTANCE_TYPE(__first)); + __distance_type(__first)); } template <class _ForwardIter, class _Tp, class _Compare, class _Distance> @@ -2031,13 +2272,16 @@ _ForwardIter __upper_bound(_ForwardIter __first, _ForwardIter __last, template <class _ForwardIter, class _Tp, class _Compare> inline _ForwardIter upper_bound(_ForwardIter __first, _ForwardIter __last, - const _Tp& __val, _Compare __comp) { - __STL_REQUIRES(_ForwardIter, _ForwardIterator); - __STL_REQUIRES_SAME_TYPE(_Tp, - typename iterator_traits<_ForwardIter>::value_type); - __STL_BINARY_FUNCTION_CHECK(_Compare, bool, _Tp, _Tp); + const _Tp& __val, _Compare __comp) +{ + // concept requirements + glibcpp_function_requires(ForwardIteratorConcept<_ForwardIter>); + glibcpp_function_requires(SameTypeConcept<_Tp, + typename iterator_traits<_ForwardIter>::value_type>); + glibcpp_function_requires(BinaryPredicateConcept<_Compare, _Tp, _Tp>); + return __upper_bound(__first, __last, __val, __comp, - __DISTANCE_TYPE(__first)); + __distance_type(__first)); } template <class _ForwardIter, class _Tp, class _Distance> @@ -2073,13 +2317,16 @@ __equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val, template <class _ForwardIter, class _Tp> inline pair<_ForwardIter, _ForwardIter> -equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val) { - __STL_REQUIRES(_ForwardIter, _ForwardIterator); - __STL_REQUIRES_SAME_TYPE(_Tp, - typename iterator_traits<_ForwardIter>::value_type); - __STL_REQUIRES(_Tp, _LessThanComparable); +equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val) +{ + // concept requirements + glibcpp_function_requires(ForwardIteratorConcept<_ForwardIter>); + glibcpp_function_requires(SameTypeConcept<_Tp, + typename iterator_traits<_ForwardIter>::value_type>); + glibcpp_function_requires(LessThanComparableConcept<_Tp>); + return __equal_range(__first, __last, __val, - __DISTANCE_TYPE(__first)); + __distance_type(__first)); } template <class _ForwardIter, class _Tp, class _Compare, class _Distance> @@ -2116,22 +2363,28 @@ __equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val, template <class _ForwardIter, class _Tp, class _Compare> inline pair<_ForwardIter, _ForwardIter> equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val, - _Compare __comp) { - __STL_REQUIRES(_ForwardIter, _ForwardIterator); - __STL_REQUIRES_SAME_TYPE(_Tp, - typename iterator_traits<_ForwardIter>::value_type); - __STL_BINARY_FUNCTION_CHECK(_Compare, bool, _Tp, _Tp); + _Compare __comp) +{ + // concept requirements + glibcpp_function_requires(ForwardIteratorConcept<_ForwardIter>); + glibcpp_function_requires(SameTypeConcept<_Tp, + typename iterator_traits<_ForwardIter>::value_type>); + glibcpp_function_requires(BinaryPredicateConcept<_Compare, _Tp, _Tp>); + return __equal_range(__first, __last, __val, __comp, - __DISTANCE_TYPE(__first)); + __distance_type(__first)); } template <class _ForwardIter, class _Tp> bool binary_search(_ForwardIter __first, _ForwardIter __last, - const _Tp& __val) { - __STL_REQUIRES(_ForwardIter, _ForwardIterator); - __STL_REQUIRES_SAME_TYPE(_Tp, - typename iterator_traits<_ForwardIter>::value_type); - __STL_REQUIRES(_Tp, _LessThanComparable); + const _Tp& __val) +{ + // concept requirements + glibcpp_function_requires(ForwardIteratorConcept<_ForwardIter>); + glibcpp_function_requires(SameTypeConcept<_Tp, + typename iterator_traits<_ForwardIter>::value_type>); + glibcpp_function_requires(LessThanComparableConcept<_Tp>); + _ForwardIter __i = lower_bound(__first, __last, __val); return __i != __last && !(__val < *__i); } @@ -2139,11 +2392,14 @@ bool binary_search(_ForwardIter __first, _ForwardIter __last, template <class _ForwardIter, class _Tp, class _Compare> bool binary_search(_ForwardIter __first, _ForwardIter __last, const _Tp& __val, - _Compare __comp) { - __STL_REQUIRES(_ForwardIter, _ForwardIterator); - __STL_REQUIRES_SAME_TYPE(_Tp, - typename iterator_traits<_ForwardIter>::value_type); - __STL_BINARY_FUNCTION_CHECK(_Compare, bool, _Tp, _Tp); + _Compare __comp) +{ + // concept requirements + glibcpp_function_requires(ForwardIteratorConcept<_ForwardIter>); + glibcpp_function_requires(SameTypeConcept<_Tp, + typename iterator_traits<_ForwardIter>::value_type>); + glibcpp_function_requires(BinaryPredicateConcept<_Compare, _Tp, _Tp>); + _ForwardIter __i = lower_bound(__first, __last, __val, __comp); return __i != __last && !__comp(__val, *__i); } @@ -2153,15 +2409,19 @@ bool binary_search(_ForwardIter __first, _ForwardIter __last, template <class _InputIter1, class _InputIter2, class _OutputIter> _OutputIter merge(_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2, _InputIter2 __last2, - _OutputIter __result) { - __STL_REQUIRES(_InputIter1, _InputIterator); - __STL_REQUIRES(_InputIter2, _InputIterator); - __STL_REQUIRES(_OutputIter, _OutputIterator); - __STL_REQUIRES_SAME_TYPE( - typename iterator_traits<_InputIter1>::value_type, - typename iterator_traits<_InputIter2>::value_type); - __STL_REQUIRES(typename iterator_traits<_InputIter1>::value_type, - _LessThanComparable); + _OutputIter __result) +{ + // concept requirements + glibcpp_function_requires(InputIteratorConcept<_InputIter1>); + glibcpp_function_requires(InputIteratorConcept<_InputIter2>); + glibcpp_function_requires(OutputIteratorConcept<_OutputIter, + typename iterator_traits<_InputIter1>::value_type>); + glibcpp_function_requires(SameTypeConcept< + typename iterator_traits<_InputIter1>::value_type, + typename iterator_traits<_InputIter2>::value_type>); + glibcpp_function_requires(LessThanComparableConcept< + typename iterator_traits<_InputIter1>::value_type>); + while (__first1 != __last1 && __first2 != __last2) { if (*__first2 < *__first1) { *__result = *__first2; @@ -2180,16 +2440,20 @@ template <class _InputIter1, class _InputIter2, class _OutputIter, class _Compare> _OutputIter merge(_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2, _InputIter2 __last2, - _OutputIter __result, _Compare __comp) { - __STL_REQUIRES(_InputIter1, _InputIterator); - __STL_REQUIRES(_InputIter2, _InputIterator); - __STL_REQUIRES_SAME_TYPE( - typename iterator_traits<_InputIter1>::value_type, - typename iterator_traits<_InputIter2>::value_type); - __STL_REQUIRES(_OutputIter, _OutputIterator); - __STL_BINARY_FUNCTION_CHECK(_Compare, bool, - typename iterator_traits<_InputIter1>::value_type, - typename iterator_traits<_InputIter1>::value_type); + _OutputIter __result, _Compare __comp) +{ + // concept requirements + glibcpp_function_requires(InputIteratorConcept<_InputIter1>); + glibcpp_function_requires(InputIteratorConcept<_InputIter2>); + glibcpp_function_requires(SameTypeConcept< + typename iterator_traits<_InputIter1>::value_type, + typename iterator_traits<_InputIter2>::value_type>); + glibcpp_function_requires(OutputIteratorConcept<_OutputIter, + typename iterator_traits<_InputIter1>::value_type>); + glibcpp_function_requires(BinaryPredicateConcept<_Compare, + typename iterator_traits<_InputIter1>::value_type, + typename iterator_traits<_InputIter2>::value_type>); + while (__first1 != __last1 && __first2 != __last2) { if (__comp(*__first2, *__first1)) { *__result = *__first2; @@ -2210,7 +2474,8 @@ template <class _BidirectionalIter, class _Distance> void __merge_without_buffer(_BidirectionalIter __first, _BidirectionalIter __middle, _BidirectionalIter __last, - _Distance __len1, _Distance __len2) { + _Distance __len1, _Distance __len2) +{ if (__len1 == 0 || __len2 == 0) return; if (__len1 + __len2 == 2) { @@ -2247,7 +2512,8 @@ void __merge_without_buffer(_BidirectionalIter __first, _BidirectionalIter __middle, _BidirectionalIter __last, _Distance __len1, _Distance __len2, - _Compare __comp) { + _Compare __comp) +{ if (__len1 == 0 || __len2 == 0) return; if (__len1 + __len2 == 2) { @@ -2286,7 +2552,8 @@ _BidirectionalIter1 __rotate_adaptive(_BidirectionalIter1 __first, _BidirectionalIter1 __last, _Distance __len1, _Distance __len2, _BidirectionalIter2 __buffer, - _Distance __buffer_size) { + _Distance __buffer_size) +{ _BidirectionalIter2 __buffer_end; if (__len1 > __len2 && __len2 <= __buffer_size) { __buffer_end = copy(__middle, __last, __buffer); @@ -2308,7 +2575,8 @@ _BidirectionalIter3 __merge_backward(_BidirectionalIter1 __first1, _BidirectionalIter1 __last1, _BidirectionalIter2 __first2, _BidirectionalIter2 __last2, - _BidirectionalIter3 __result) { + _BidirectionalIter3 __result) +{ if (__first1 == __last1) return copy_backward(__first2, __last2, __result); if (__first2 == __last2) @@ -2338,7 +2606,8 @@ _BidirectionalIter3 __merge_backward(_BidirectionalIter1 __first1, _BidirectionalIter2 __first2, _BidirectionalIter2 __last2, _BidirectionalIter3 __result, - _Compare __comp) { + _Compare __comp) +{ if (__first1 == __last1) return copy_backward(__first2, __last2, __result); if (__first2 == __last2) @@ -2366,7 +2635,8 @@ void __merge_adaptive(_BidirectionalIter __first, _BidirectionalIter __middle, _BidirectionalIter __last, _Distance __len1, _Distance __len2, - _Pointer __buffer, _Distance __buffer_size) { + _Pointer __buffer, _Distance __buffer_size) +{ if (__len1 <= __len2 && __len1 <= __buffer_size) { _Pointer __buffer_end = copy(__first, __middle, __buffer); merge(__buffer, __buffer_end, __middle, __last, __first); @@ -2409,7 +2679,8 @@ void __merge_adaptive(_BidirectionalIter __first, _BidirectionalIter __last, _Distance __len1, _Distance __len2, _Pointer __buffer, _Distance __buffer_size, - _Compare __comp) { + _Compare __comp) +{ if (__len1 <= __len2 && __len1 <= __buffer_size) { _Pointer __buffer_end = copy(__first, __middle, __buffer); merge(__buffer, __buffer_end, __middle, __last, __first, __comp); @@ -2449,7 +2720,8 @@ void __merge_adaptive(_BidirectionalIter __first, template <class _BidirectionalIter, class _Tp, class _Distance> inline void __inplace_merge_aux(_BidirectionalIter __first, _BidirectionalIter __middle, - _BidirectionalIter __last, _Tp*, _Distance*) { + _BidirectionalIter __last, _Tp*, _Distance*) +{ _Distance __len1 = 0; distance(__first, __middle, __len1); _Distance __len2 = 0; @@ -2468,7 +2740,8 @@ template <class _BidirectionalIter, class _Tp, inline void __inplace_merge_aux(_BidirectionalIter __first, _BidirectionalIter __middle, _BidirectionalIter __last, _Tp*, _Distance*, - _Compare __comp) { + _Compare __comp) +{ _Distance __len1 = 0; distance(__first, __middle, __len1); _Distance __len2 = 0; @@ -2486,28 +2759,36 @@ inline void __inplace_merge_aux(_BidirectionalIter __first, template <class _BidirectionalIter> inline void inplace_merge(_BidirectionalIter __first, _BidirectionalIter __middle, - _BidirectionalIter __last) { - __STL_REQUIRES(_BidirectionalIter, _Mutable_BidirectionalIterator); - __STL_REQUIRES(typename iterator_traits<_BidirectionalIter>::value_type, - _LessThanComparable); + _BidirectionalIter __last) +{ + // concept requirements + glibcpp_function_requires(Mutable_BidirectionalIteratorConcept< + _BidirectionalIter>); + glibcpp_function_requires(LessThanComparableConcept< + typename iterator_traits<_BidirectionalIter>::value_type>); + if (__first == __middle || __middle == __last) return; __inplace_merge_aux(__first, __middle, __last, - __VALUE_TYPE(__first), __DISTANCE_TYPE(__first)); + __value_type(__first), __distance_type(__first)); } template <class _BidirectionalIter, class _Compare> inline void inplace_merge(_BidirectionalIter __first, _BidirectionalIter __middle, - _BidirectionalIter __last, _Compare __comp) { - __STL_REQUIRES(_BidirectionalIter, _Mutable_BidirectionalIterator); - __STL_BINARY_FUNCTION_CHECK(_Compare, bool, - typename iterator_traits<_BidirectionalIter>::value_type, - typename iterator_traits<_BidirectionalIter>::value_type); + _BidirectionalIter __last, _Compare __comp) +{ + // concept requirements + glibcpp_function_requires(Mutable_BidirectionalIteratorConcept< + _BidirectionalIter>); + glibcpp_function_requires(BinaryPredicateConcept<_Compare, + typename iterator_traits<_BidirectionalIter>::value_type, + typename iterator_traits<_BidirectionalIter>::value_type>); + if (__first == __middle || __middle == __last) return; __inplace_merge_aux(__first, __middle, __last, - __VALUE_TYPE(__first), __DISTANCE_TYPE(__first), + __value_type(__first), __distance_type(__first), __comp); } @@ -2518,14 +2799,17 @@ inline void inplace_merge(_BidirectionalIter __first, template <class _InputIter1, class _InputIter2> bool includes(_InputIter1 __first1, _InputIter1 __last1, - _InputIter2 __first2, _InputIter2 __last2) { - __STL_REQUIRES(_InputIter1, _InputIterator); - __STL_REQUIRES(_InputIter2, _InputIterator); - __STL_REQUIRES_SAME_TYPE( - typename iterator_traits<_InputIter1>::value_type, - typename iterator_traits<_InputIter2>::value_type); - __STL_REQUIRES(typename iterator_traits<_InputIter1>::value_type, - _LessThanComparable); + _InputIter2 __first2, _InputIter2 __last2) +{ + // concept requirements + glibcpp_function_requires(InputIteratorConcept<_InputIter1>); + glibcpp_function_requires(InputIteratorConcept<_InputIter2>); + glibcpp_function_requires(SameTypeConcept< + typename iterator_traits<_InputIter1>::value_type, + typename iterator_traits<_InputIter2>::value_type>); + glibcpp_function_requires(LessThanComparableConcept< + typename iterator_traits<_InputIter1>::value_type>); + while (__first1 != __last1 && __first2 != __last2) if (*__first2 < *__first1) return false; @@ -2539,15 +2823,18 @@ bool includes(_InputIter1 __first1, _InputIter1 __last1, template <class _InputIter1, class _InputIter2, class _Compare> bool includes(_InputIter1 __first1, _InputIter1 __last1, - _InputIter2 __first2, _InputIter2 __last2, _Compare __comp) { - __STL_REQUIRES(_InputIter1, _InputIterator); - __STL_REQUIRES(_InputIter2, _InputIterator); - __STL_REQUIRES_SAME_TYPE( - typename iterator_traits<_InputIter1>::value_type, - typename iterator_traits<_InputIter2>::value_type); - __STL_BINARY_FUNCTION_CHECK(_Compare, bool, - typename iterator_traits<_InputIter1>::value_type, - typename iterator_traits<_InputIter2>::value_type); + _InputIter2 __first2, _InputIter2 __last2, _Compare __comp) +{ + // concept requirements + glibcpp_function_requires(InputIteratorConcept<_InputIter1>); + glibcpp_function_requires(InputIteratorConcept<_InputIter2>); + glibcpp_function_requires(SameTypeConcept< + typename iterator_traits<_InputIter1>::value_type, + typename iterator_traits<_InputIter2>::value_type>); + glibcpp_function_requires(BinaryPredicateConcept<_Compare, + typename iterator_traits<_InputIter1>::value_type, + typename iterator_traits<_InputIter2>::value_type>); + while (__first1 != __last1 && __first2 != __last2) if (__comp(*__first2, *__first1)) return false; @@ -2562,15 +2849,19 @@ bool includes(_InputIter1 __first1, _InputIter1 __last1, template <class _InputIter1, class _InputIter2, class _OutputIter> _OutputIter set_union(_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2, _InputIter2 __last2, - _OutputIter __result) { - __STL_REQUIRES(_InputIter1, _InputIterator); - __STL_REQUIRES(_InputIter2, _InputIterator); - __STL_REQUIRES(_OutputIter, _OutputIterator); - __STL_REQUIRES_SAME_TYPE( - typename iterator_traits<_InputIter1>::value_type, - typename iterator_traits<_InputIter2>::value_type); - __STL_REQUIRES(typename iterator_traits<_InputIter1>::value_type, - _LessThanComparable); + _OutputIter __result) +{ + // concept requirements + glibcpp_function_requires(InputIteratorConcept<_InputIter1>); + glibcpp_function_requires(InputIteratorConcept<_InputIter2>); + glibcpp_function_requires(OutputIteratorConcept<_OutputIter, + typename iterator_traits<_InputIter1>::value_type>); + glibcpp_function_requires(SameTypeConcept< + typename iterator_traits<_InputIter1>::value_type, + typename iterator_traits<_InputIter2>::value_type>); + glibcpp_function_requires(LessThanComparableConcept< + typename iterator_traits<_InputIter1>::value_type>); + while (__first1 != __last1 && __first2 != __last2) { if (*__first1 < *__first2) { *__result = *__first1; @@ -2594,16 +2885,20 @@ template <class _InputIter1, class _InputIter2, class _OutputIter, class _Compare> _OutputIter set_union(_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2, _InputIter2 __last2, - _OutputIter __result, _Compare __comp) { - __STL_REQUIRES(_InputIter1, _InputIterator); - __STL_REQUIRES(_InputIter2, _InputIterator); - __STL_REQUIRES(_OutputIter, _OutputIterator); - __STL_REQUIRES_SAME_TYPE( - typename iterator_traits<_InputIter1>::value_type, - typename iterator_traits<_InputIter2>::value_type); - __STL_BINARY_FUNCTION_CHECK(_Compare, bool, - typename iterator_traits<_InputIter1>::value_type, - typename iterator_traits<_InputIter2>::value_type); + _OutputIter __result, _Compare __comp) +{ + // concept requirements + glibcpp_function_requires(InputIteratorConcept<_InputIter1>); + glibcpp_function_requires(InputIteratorConcept<_InputIter2>); + glibcpp_function_requires(SameTypeConcept< + typename iterator_traits<_InputIter1>::value_type, + typename iterator_traits<_InputIter2>::value_type>); + glibcpp_function_requires(OutputIteratorConcept<_OutputIter, + typename iterator_traits<_InputIter1>::value_type>); + glibcpp_function_requires(BinaryPredicateConcept<_Compare, + typename iterator_traits<_InputIter1>::value_type, + typename iterator_traits<_InputIter2>::value_type>); + while (__first1 != __last1 && __first2 != __last2) { if (__comp(*__first1, *__first2)) { *__result = *__first1; @@ -2626,15 +2921,19 @@ _OutputIter set_union(_InputIter1 __first1, _InputIter1 __last1, template <class _InputIter1, class _InputIter2, class _OutputIter> _OutputIter set_intersection(_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2, _InputIter2 __last2, - _OutputIter __result) { - __STL_REQUIRES(_InputIter1, _InputIterator); - __STL_REQUIRES(_InputIter2, _InputIterator); - __STL_REQUIRES(_OutputIter, _OutputIterator); - __STL_REQUIRES_SAME_TYPE( - typename iterator_traits<_InputIter1>::value_type, - typename iterator_traits<_InputIter2>::value_type); - __STL_REQUIRES(typename iterator_traits<_InputIter1>::value_type, - _LessThanComparable); + _OutputIter __result) +{ + // concept requirements + glibcpp_function_requires(InputIteratorConcept<_InputIter1>); + glibcpp_function_requires(InputIteratorConcept<_InputIter2>); + glibcpp_function_requires(OutputIteratorConcept<_OutputIter, + typename iterator_traits<_InputIter1>::value_type>); + glibcpp_function_requires(SameTypeConcept< + typename iterator_traits<_InputIter1>::value_type, + typename iterator_traits<_InputIter2>::value_type>); + glibcpp_function_requires(LessThanComparableConcept< + typename iterator_traits<_InputIter1>::value_type>); + while (__first1 != __last1 && __first2 != __last2) if (*__first1 < *__first2) ++__first1; @@ -2653,16 +2952,19 @@ template <class _InputIter1, class _InputIter2, class _OutputIter, class _Compare> _OutputIter set_intersection(_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2, _InputIter2 __last2, - _OutputIter __result, _Compare __comp) { - __STL_REQUIRES(_InputIter1, _InputIterator); - __STL_REQUIRES(_InputIter2, _InputIterator); - __STL_REQUIRES(_OutputIter, _OutputIterator); - __STL_REQUIRES_SAME_TYPE( - typename iterator_traits<_InputIter1>::value_type, - typename iterator_traits<_InputIter2>::value_type); - __STL_BINARY_FUNCTION_CHECK(_Compare, bool, - typename iterator_traits<_InputIter1>::value_type, - typename iterator_traits<_InputIter2>::value_type); + _OutputIter __result, _Compare __comp) +{ + // concept requirements + glibcpp_function_requires(InputIteratorConcept<_InputIter1>); + glibcpp_function_requires(InputIteratorConcept<_InputIter2>); + glibcpp_function_requires(SameTypeConcept< + typename iterator_traits<_InputIter1>::value_type, + typename iterator_traits<_InputIter2>::value_type>); + glibcpp_function_requires(OutputIteratorConcept<_OutputIter, + typename iterator_traits<_InputIter1>::value_type>); + glibcpp_function_requires(BinaryPredicateConcept<_Compare, + typename iterator_traits<_InputIter1>::value_type, + typename iterator_traits<_InputIter2>::value_type>); while (__first1 != __last1 && __first2 != __last2) if (__comp(*__first1, *__first2)) @@ -2681,15 +2983,19 @@ _OutputIter set_intersection(_InputIter1 __first1, _InputIter1 __last1, template <class _InputIter1, class _InputIter2, class _OutputIter> _OutputIter set_difference(_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2, _InputIter2 __last2, - _OutputIter __result) { - __STL_REQUIRES(_InputIter1, _InputIterator); - __STL_REQUIRES(_InputIter2, _InputIterator); - __STL_REQUIRES(_OutputIter, _OutputIterator); - __STL_REQUIRES_SAME_TYPE( - typename iterator_traits<_InputIter1>::value_type, - typename iterator_traits<_InputIter2>::value_type); - __STL_REQUIRES(typename iterator_traits<_InputIter1>::value_type, - _LessThanComparable); + _OutputIter __result) +{ + // concept requirements + glibcpp_function_requires(InputIteratorConcept<_InputIter1>); + glibcpp_function_requires(InputIteratorConcept<_InputIter2>); + glibcpp_function_requires(OutputIteratorConcept<_OutputIter, + typename iterator_traits<_InputIter1>::value_type>); + glibcpp_function_requires(SameTypeConcept< + typename iterator_traits<_InputIter1>::value_type, + typename iterator_traits<_InputIter2>::value_type>); + glibcpp_function_requires(LessThanComparableConcept< + typename iterator_traits<_InputIter1>::value_type>); + while (__first1 != __last1 && __first2 != __last2) if (*__first1 < *__first2) { *__result = *__first1; @@ -2709,16 +3015,19 @@ template <class _InputIter1, class _InputIter2, class _OutputIter, class _Compare> _OutputIter set_difference(_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2, _InputIter2 __last2, - _OutputIter __result, _Compare __comp) { - __STL_REQUIRES(_InputIter1, _InputIterator); - __STL_REQUIRES(_InputIter2, _InputIterator); - __STL_REQUIRES(_OutputIter, _OutputIterator); - __STL_REQUIRES_SAME_TYPE( - typename iterator_traits<_InputIter1>::value_type, - typename iterator_traits<_InputIter2>::value_type); - __STL_BINARY_FUNCTION_CHECK(_Compare, bool, - typename iterator_traits<_InputIter1>::value_type, - typename iterator_traits<_InputIter2>::value_type); + _OutputIter __result, _Compare __comp) +{ + // concept requirements + glibcpp_function_requires(InputIteratorConcept<_InputIter1>); + glibcpp_function_requires(InputIteratorConcept<_InputIter2>); + glibcpp_function_requires(SameTypeConcept< + typename iterator_traits<_InputIter1>::value_type, + typename iterator_traits<_InputIter2>::value_type>); + glibcpp_function_requires(OutputIteratorConcept<_OutputIter, + typename iterator_traits<_InputIter1>::value_type>); + glibcpp_function_requires(BinaryPredicateConcept<_Compare, + typename iterator_traits<_InputIter1>::value_type, + typename iterator_traits<_InputIter2>::value_type>); while (__first1 != __last1 && __first2 != __last2) if (__comp(*__first1, *__first2)) { @@ -2739,15 +3048,19 @@ template <class _InputIter1, class _InputIter2, class _OutputIter> _OutputIter set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2, _InputIter2 __last2, - _OutputIter __result) { - __STL_REQUIRES(_InputIter1, _InputIterator); - __STL_REQUIRES(_InputIter2, _InputIterator); - __STL_REQUIRES(_OutputIter, _OutputIterator); - __STL_REQUIRES_SAME_TYPE( - typename iterator_traits<_InputIter1>::value_type, - typename iterator_traits<_InputIter2>::value_type); - __STL_REQUIRES(typename iterator_traits<_InputIter1>::value_type, - _LessThanComparable); + _OutputIter __result) +{ + // concept requirements + glibcpp_function_requires(InputIteratorConcept<_InputIter1>); + glibcpp_function_requires(InputIteratorConcept<_InputIter2>); + glibcpp_function_requires(OutputIteratorConcept<_OutputIter, + typename iterator_traits<_InputIter1>::value_type>); + glibcpp_function_requires(SameTypeConcept< + typename iterator_traits<_InputIter1>::value_type, + typename iterator_traits<_InputIter2>::value_type>); + glibcpp_function_requires(LessThanComparableConcept< + typename iterator_traits<_InputIter1>::value_type>); + while (__first1 != __last1 && __first2 != __last2) if (*__first1 < *__first2) { *__result = *__first1; @@ -2772,16 +3085,20 @@ _OutputIter set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2, _InputIter2 __last2, _OutputIter __result, - _Compare __comp) { - __STL_REQUIRES(_InputIter1, _InputIterator); - __STL_REQUIRES(_InputIter2, _InputIterator); - __STL_REQUIRES(_OutputIter, _OutputIterator); - __STL_REQUIRES_SAME_TYPE( - typename iterator_traits<_InputIter1>::value_type, - typename iterator_traits<_InputIter2>::value_type); - __STL_BINARY_FUNCTION_CHECK(_Compare, bool, - typename iterator_traits<_InputIter1>::value_type, - typename iterator_traits<_InputIter2>::value_type); + _Compare __comp) +{ + // concept requirements + glibcpp_function_requires(InputIteratorConcept<_InputIter1>); + glibcpp_function_requires(InputIteratorConcept<_InputIter2>); + glibcpp_function_requires(SameTypeConcept< + typename iterator_traits<_InputIter1>::value_type, + typename iterator_traits<_InputIter2>::value_type>); + glibcpp_function_requires(OutputIteratorConcept<_OutputIter, + typename iterator_traits<_InputIter1>::value_type>); + glibcpp_function_requires(BinaryPredicateConcept<_Compare, + typename iterator_traits<_InputIter1>::value_type, + typename iterator_traits<_InputIter2>::value_type>); + while (__first1 != __last1 && __first2 != __last2) if (__comp(*__first1, *__first2)) { *__result = *__first1; @@ -2804,10 +3121,13 @@ set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1, // comparison function. template <class _ForwardIter> -_ForwardIter max_element(_ForwardIter __first, _ForwardIter __last) { - __STL_REQUIRES(_ForwardIter, _ForwardIterator); - __STL_REQUIRES(typename iterator_traits<_ForwardIter>::value_type, - _LessThanComparable); +_ForwardIter max_element(_ForwardIter __first, _ForwardIter __last) +{ + // concept requirements + glibcpp_function_requires(ForwardIteratorConcept<_ForwardIter>); + glibcpp_function_requires(LessThanComparableConcept< + typename iterator_traits<_ForwardIter>::value_type>); + if (__first == __last) return __first; _ForwardIter __result = __first; while (++__first != __last) @@ -2818,11 +3138,14 @@ _ForwardIter max_element(_ForwardIter __first, _ForwardIter __last) { template <class _ForwardIter, class _Compare> _ForwardIter max_element(_ForwardIter __first, _ForwardIter __last, - _Compare __comp) { - __STL_REQUIRES(_ForwardIter, _ForwardIterator); - __STL_BINARY_FUNCTION_CHECK(_Compare, bool, - typename iterator_traits<_ForwardIter>::value_type, - typename iterator_traits<_ForwardIter>::value_type); + _Compare __comp) +{ + // concept requirements + glibcpp_function_requires(ForwardIteratorConcept<_ForwardIter>); + glibcpp_function_requires(BinaryPredicateConcept<_Compare, + typename iterator_traits<_ForwardIter>::value_type, + typename iterator_traits<_ForwardIter>::value_type>); + if (__first == __last) return __first; _ForwardIter __result = __first; while (++__first != __last) @@ -2831,10 +3154,13 @@ _ForwardIter max_element(_ForwardIter __first, _ForwardIter __last, } template <class _ForwardIter> -_ForwardIter min_element(_ForwardIter __first, _ForwardIter __last) { - __STL_REQUIRES(_ForwardIter, _ForwardIterator); - __STL_REQUIRES(typename iterator_traits<_ForwardIter>::value_type, - _LessThanComparable); +_ForwardIter min_element(_ForwardIter __first, _ForwardIter __last) +{ + // concept requirements + glibcpp_function_requires(ForwardIteratorConcept<_ForwardIter>); + glibcpp_function_requires(LessThanComparableConcept< + typename iterator_traits<_ForwardIter>::value_type>); + if (__first == __last) return __first; _ForwardIter __result = __first; while (++__first != __last) @@ -2845,11 +3171,14 @@ _ForwardIter min_element(_ForwardIter __first, _ForwardIter __last) { template <class _ForwardIter, class _Compare> _ForwardIter min_element(_ForwardIter __first, _ForwardIter __last, - _Compare __comp) { - __STL_REQUIRES(_ForwardIter, _ForwardIterator); - __STL_BINARY_FUNCTION_CHECK(_Compare, bool, - typename iterator_traits<_ForwardIter>::value_type, - typename iterator_traits<_ForwardIter>::value_type); + _Compare __comp) +{ + // concept requirements + glibcpp_function_requires(ForwardIteratorConcept<_ForwardIter>); + glibcpp_function_requires(BinaryPredicateConcept<_Compare, + typename iterator_traits<_ForwardIter>::value_type, + typename iterator_traits<_ForwardIter>::value_type>); + if (__first == __last) return __first; _ForwardIter __result = __first; while (++__first != __last) @@ -2862,10 +3191,13 @@ _ForwardIter min_element(_ForwardIter __first, _ForwardIter __last, // supplied comparison function. template <class _BidirectionalIter> -bool next_permutation(_BidirectionalIter __first, _BidirectionalIter __last) { - __STL_REQUIRES(_BidirectionalIter, _BidirectionalIterator); - __STL_REQUIRES(typename iterator_traits<_BidirectionalIter>::value_type, - _LessThanComparable); +bool next_permutation(_BidirectionalIter __first, _BidirectionalIter __last) +{ + // concept requirements + glibcpp_function_requires(BidirectionalIteratorConcept<_BidirectionalIter>); + glibcpp_function_requires(LessThanComparableConcept< + typename iterator_traits<_BidirectionalIter>::value_type>); + if (__first == __last) return false; _BidirectionalIter __i = __first; @@ -2895,11 +3227,14 @@ bool next_permutation(_BidirectionalIter __first, _BidirectionalIter __last) { template <class _BidirectionalIter, class _Compare> bool next_permutation(_BidirectionalIter __first, _BidirectionalIter __last, - _Compare __comp) { - __STL_REQUIRES(_BidirectionalIter, _BidirectionalIterator); - __STL_BINARY_FUNCTION_CHECK(_Compare, bool, - typename iterator_traits<_BidirectionalIter>::value_type, - typename iterator_traits<_BidirectionalIter>::value_type); + _Compare __comp) +{ + // concept requirements + glibcpp_function_requires(BidirectionalIteratorConcept<_BidirectionalIter>); + glibcpp_function_requires(BinaryPredicateConcept<_Compare, + typename iterator_traits<_BidirectionalIter>::value_type, + typename iterator_traits<_BidirectionalIter>::value_type>); + if (__first == __last) return false; _BidirectionalIter __i = __first; @@ -2928,10 +3263,13 @@ bool next_permutation(_BidirectionalIter __first, _BidirectionalIter __last, } template <class _BidirectionalIter> -bool prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last) { - __STL_REQUIRES(_BidirectionalIter, _BidirectionalIterator); - __STL_REQUIRES(typename iterator_traits<_BidirectionalIter>::value_type, - _LessThanComparable); +bool prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last) +{ + // concept requirements + glibcpp_function_requires(BidirectionalIteratorConcept<_BidirectionalIter>); + glibcpp_function_requires(LessThanComparableConcept< + typename iterator_traits<_BidirectionalIter>::value_type>); + if (__first == __last) return false; _BidirectionalIter __i = __first; @@ -2961,11 +3299,14 @@ bool prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last) { template <class _BidirectionalIter, class _Compare> bool prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last, - _Compare __comp) { - __STL_REQUIRES(_BidirectionalIter, _BidirectionalIterator); - __STL_BINARY_FUNCTION_CHECK(_Compare, bool, - typename iterator_traits<_BidirectionalIter>::value_type, - typename iterator_traits<_BidirectionalIter>::value_type); + _Compare __comp) +{ + // concept requirements + glibcpp_function_requires(BidirectionalIteratorConcept<_BidirectionalIter>); + glibcpp_function_requires(BinaryPredicateConcept<_Compare, + typename iterator_traits<_BidirectionalIter>::value_type, + typename iterator_traits<_BidirectionalIter>::value_type>); + if (__first == __last) return false; _BidirectionalIter __i = __first; @@ -2999,11 +3340,12 @@ template <class _InputIter, class _ForwardIter> _InputIter find_first_of(_InputIter __first1, _InputIter __last1, _ForwardIter __first2, _ForwardIter __last2) { - __STL_REQUIRES(_InputIter, _InputIterator); - __STL_REQUIRES(_ForwardIter, _ForwardIterator); - __STL_REQUIRES_BINARY_OP(_OP_EQUAL, bool, - typename iterator_traits<_InputIter>::value_type, - typename iterator_traits<_ForwardIter>::value_type); + // concept requirements + glibcpp_function_requires(InputIteratorConcept<_InputIter>); + glibcpp_function_requires(ForwardIteratorConcept<_ForwardIter>); + glibcpp_function_requires(EqualOpConcept< + typename iterator_traits<_InputIter>::value_type, + typename iterator_traits<_ForwardIter>::value_type>); for ( ; __first1 != __last1; ++__first1) for (_ForwardIter __iter = __first2; __iter != __last2; ++__iter) @@ -3017,11 +3359,15 @@ _InputIter find_first_of(_InputIter __first1, _InputIter __last1, _ForwardIter __first2, _ForwardIter __last2, _BinaryPredicate __comp) { - __STL_REQUIRES(_InputIter, _InputIterator); - __STL_REQUIRES(_ForwardIter, _ForwardIterator); - __STL_BINARY_FUNCTION_CHECK(_BinaryPredicate, bool, - typename iterator_traits<_InputIter>::value_type, - typename iterator_traits<_ForwardIter>::value_type); + // concept requirements + glibcpp_function_requires(InputIteratorConcept<_InputIter>); + glibcpp_function_requires(ForwardIteratorConcept<_ForwardIter>); + glibcpp_function_requires(EqualOpConcept< + typename iterator_traits<_InputIter>::value_type, + typename iterator_traits<_ForwardIter>::value_type>); + glibcpp_function_requires(BinaryPredicateConcept<_BinaryPredicate, + typename iterator_traits<_InputIter>::value_type, + typename iterator_traits<_ForwardIter>::value_type>); for ( ; __first1 != __last1; ++__first1) for (_ForwardIter __iter = __first2; __iter != __last2; ++__iter) @@ -3092,8 +3438,10 @@ __find_end(_BidirectionalIter1 __first1, _BidirectionalIter1 __last1, _BidirectionalIter2 __first2, _BidirectionalIter2 __last2, bidirectional_iterator_tag, bidirectional_iterator_tag) { - __STL_REQUIRES(_BidirectionalIter1, _BidirectionalIterator); - __STL_REQUIRES(_BidirectionalIter2, _BidirectionalIterator); + // concept requirements + glibcpp_function_requires(BidirectionalIteratorConcept<_BidirectionalIter1>); + glibcpp_function_requires(BidirectionalIteratorConcept<_BidirectionalIter2>); + typedef reverse_iterator<_BidirectionalIter1> _RevIter1; typedef reverse_iterator<_BidirectionalIter2> _RevIter2; @@ -3119,8 +3467,10 @@ __find_end(_BidirectionalIter1 __first1, _BidirectionalIter1 __last1, bidirectional_iterator_tag, bidirectional_iterator_tag, _BinaryPredicate __comp) { - __STL_REQUIRES(_BidirectionalIter1, _BidirectionalIterator); - __STL_REQUIRES(_BidirectionalIter2, _BidirectionalIterator); + // concept requirements + glibcpp_function_requires(BidirectionalIteratorConcept<_BidirectionalIter1>); + glibcpp_function_requires(BidirectionalIteratorConcept<_BidirectionalIter2>); + typedef reverse_iterator<_BidirectionalIter1> _RevIter1; typedef reverse_iterator<_BidirectionalIter2> _RevIter2; @@ -3146,14 +3496,16 @@ inline _ForwardIter1 find_end(_ForwardIter1 __first1, _ForwardIter1 __last1, _ForwardIter2 __first2, _ForwardIter2 __last2) { - __STL_REQUIRES(_ForwardIter1, _ForwardIterator); - __STL_REQUIRES(_ForwardIter2, _ForwardIterator); - __STL_REQUIRES_BINARY_OP(_OP_EQUAL, bool, - typename iterator_traits<_ForwardIter1>::value_type, - typename iterator_traits<_ForwardIter2>::value_type); + // concept requirements + glibcpp_function_requires(ForwardIteratorConcept<_ForwardIter1>); + glibcpp_function_requires(ForwardIteratorConcept<_ForwardIter2>); + glibcpp_function_requires(EqualOpConcept< + typename iterator_traits<_ForwardIter1>::value_type, + typename iterator_traits<_ForwardIter2>::value_type>); + return __find_end(__first1, __last1, __first2, __last2, - __ITERATOR_CATEGORY(__first1), - __ITERATOR_CATEGORY(__first2)); + __iterator_category(__first1), + __iterator_category(__first2)); } template <class _ForwardIter1, class _ForwardIter2, @@ -3163,15 +3515,16 @@ find_end(_ForwardIter1 __first1, _ForwardIter1 __last1, _ForwardIter2 __first2, _ForwardIter2 __last2, _BinaryPredicate __comp) { - __STL_REQUIRES(_ForwardIter1, _ForwardIterator); - __STL_REQUIRES(_ForwardIter2, _ForwardIterator); - __STL_BINARY_FUNCTION_CHECK(_BinaryPredicate, bool, - typename iterator_traits<_ForwardIter1>::value_type, - typename iterator_traits<_ForwardIter2>::value_type); + // concept requirements + glibcpp_function_requires(ForwardIteratorConcept<_ForwardIter1>); + glibcpp_function_requires(ForwardIteratorConcept<_ForwardIter2>); + glibcpp_function_requires(BinaryPredicateConcept<_BinaryPredicate, + typename iterator_traits<_ForwardIter1>::value_type, + typename iterator_traits<_ForwardIter2>::value_type>); return __find_end(__first1, __last1, __first2, __last2, - __ITERATOR_CATEGORY(__first1), - __ITERATOR_CATEGORY(__first2), + __iterator_category(__first1), + __iterator_category(__first2), __comp); } @@ -3209,9 +3562,11 @@ bool __is_heap(_RandomAccessIter __first, _StrictWeakOrdering __comp, template <class _RandomAccessIter> inline bool is_heap(_RandomAccessIter __first, _RandomAccessIter __last) { - __STL_REQUIRES(_RandomAccessIter, _RandomAccessIterator); - __STL_REQUIRES(typename iterator_traits<_RandomAccessIter>::value_type, - _LessThanComparable); + // concept requirements + glibcpp_function_requires(RandomAccessIteratorConcept<_RandomAccessIter>); + glibcpp_function_requires(LessThanComparableConcept< + typename iterator_traits<_RandomAccessIter>::value_type>); + return __is_heap(__first, __last - __first); } @@ -3220,10 +3575,12 @@ template <class _RandomAccessIter, class _StrictWeakOrdering> inline bool is_heap(_RandomAccessIter __first, _RandomAccessIter __last, _StrictWeakOrdering __comp) { - __STL_REQUIRES(_RandomAccessIter, _RandomAccessIterator); - __STL_BINARY_FUNCTION_CHECK(_StrictWeakOrdering, bool, - typename iterator_traits<_RandomAccessIter>::value_type, - typename iterator_traits<_RandomAccessIter>::value_type); + // concept requirements + glibcpp_function_requires(RandomAccessIteratorConcept<_RandomAccessIter>); + glibcpp_function_requires(BinaryPredicateConcept<_StrictWeakOrdering, + typename iterator_traits<_RandomAccessIter>::value_type, + typename iterator_traits<_RandomAccessIter>::value_type>); + return __is_heap(__first, __comp, __last - __first); } @@ -3234,9 +3591,11 @@ inline bool is_heap(_RandomAccessIter __first, _RandomAccessIter __last, template <class _ForwardIter> bool is_sorted(_ForwardIter __first, _ForwardIter __last) { - __STL_REQUIRES(_ForwardIter, _ForwardIterator); - __STL_REQUIRES(typename iterator_traits<_ForwardIter>::value_type, - _LessThanComparable); + // concept requirements + glibcpp_function_requires(ForwardIteratorConcept<_ForwardIter>); + glibcpp_function_requires(LessThanComparableConcept< + typename iterator_traits<_ForwardIter>::value_type>); + if (__first == __last) return true; @@ -3253,10 +3612,12 @@ template <class _ForwardIter, class _StrictWeakOrdering> bool is_sorted(_ForwardIter __first, _ForwardIter __last, _StrictWeakOrdering __comp) { - __STL_REQUIRES(_ForwardIter, _ForwardIterator); - __STL_BINARY_FUNCTION_CHECK(_StrictWeakOrdering, bool, - typename iterator_traits<_ForwardIter>::value_type, - typename iterator_traits<_ForwardIter>::value_type); + // concept requirements + glibcpp_function_requires(ForwardIteratorConcept<_ForwardIter>); + glibcpp_function_requires(BinaryPredicateConcept<_StrictWeakOrdering, + typename iterator_traits<_ForwardIter>::value_type, + typename iterator_traits<_ForwardIter>::value_type>); + if (__first == __last) return true; |
