This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
Re: [Patch] First bits of the algo merge
Howard Hinnant wrote:
> Now you don't have to pull your hair out in <algorithm>. ;-)
Right you are! Thanks!
I'm finishing testing (already past 25_algorithms) the below in
v7-branch (mainline compiler is currently broken, anyway).
The only non-obvious thing is that I'm also fixing some concept checks,
in partial_sort_copy, lower_bound, upper_bound, equal_range and
binary_search.
In the case of partial_sort_copy we were enforcing
_LessThanComparableConcept<_InputValueType> and for the latter
_LessThanComparableConcept<_Tp> and _SameTypeConcept<_Tp, _ValueType>
(with a puzzling SGI comment about "slightly too strict checks").
The adjusted concepts are minimal, consistent with those present in the
predicated versions for the algos, that is, essentially, just
_LessThanOpConcept<_ValueType, _Tp> (+ the swapped
_LessThanOpConcept<_Tp, _ValueType> for the last two algos).
Howard, can you confirm that we are actually improving on those concept
checks? ;)
Paolo.
////////////////////////
Index: include/bits/stl_algobase.h
===================================================================
--- include/bits/stl_algobase.h (revision 108473)
+++ include/bits/stl_algobase.h (working copy)
@@ -226,7 +226,7 @@
{
// concept requirements
__glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
- return min(__a, __b, __gnu_cxx::__ops::less());
+ return min(__a, __b, __gnu_cxx::__ops::less<_Tp>());
}
/**
@@ -245,7 +245,7 @@
{
// concept requirements
__glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
- return max(__a, __b, __gnu_cxx::__ops::less());
+ return max(__a, __b, __gnu_cxx::__ops::less<_Tp>());
}
// All of these auxiliary structs serve two purposes. (1) Replace
@@ -835,12 +835,16 @@
mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
_InputIterator2 __first2)
{
+ typedef typename iterator_traits<_InputIterator1>::value_type
+ _ValueType1;
+ typedef typename iterator_traits<_InputIterator2>::value_type
+ _ValueType2;
+
// concept requirements
- __glibcxx_function_requires(_EqualOpConcept<
- typename iterator_traits<_InputIterator1>::value_type,
- typename iterator_traits<_InputIterator2>::value_type>)
- return std::mismatch(__first1, __last1, __first2,
- __gnu_cxx::__ops::equal_to());
+ __glibcxx_function_requires(_EqualOpConcept<_ValueType1, _ValueType2>)
+
+ return std::mismatch(__first1, __last1, __first2, __gnu_cxx::__ops::
+ equal_to<_ValueType1, _ValueType2>());
}
/**
@@ -860,8 +864,7 @@
typename _BinaryPredicate>
inline bool
equal(_InputIterator1 __first1, _InputIterator1 __last1,
- _InputIterator2 __first2,
- _BinaryPredicate __binary_pred)
+ _InputIterator2 __first2, _BinaryPredicate __binary_pred)
{
// concept requirements
__glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
@@ -890,12 +893,16 @@
equal(_InputIterator1 __first1, _InputIterator1 __last1,
_InputIterator2 __first2)
{
+ typedef typename iterator_traits<_InputIterator1>::value_type
+ _ValueType1;
+ typedef typename iterator_traits<_InputIterator2>::value_type
+ _ValueType2;
+
// concept requirements
- __glibcxx_function_requires(_EqualOpConcept<
- typename iterator_traits<_InputIterator1>::value_type,
- typename iterator_traits<_InputIterator2>::value_type>)
- return std::equal(__first1, __last1, __first2,
- __gnu_cxx::__ops::equal_to());
+ __glibcxx_function_requires(_EqualOpConcept<_ValueType1, _ValueType2>)
+
+ return std::equal(__first1, __last1, __first2, __gnu_cxx::__ops::
+ equal_to<_ValueType1, _ValueType2>());
}
/**
@@ -953,18 +960,20 @@
lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1,
_InputIterator2 __first2, _InputIterator2 __last2)
{
+ typedef typename iterator_traits<_InputIterator1>::value_type
+ _ValueType1;
+ typedef typename iterator_traits<_InputIterator2>::value_type
+ _ValueType2;
+
// concept requirements
- __glibcxx_function_requires(_LessThanOpConcept<
- typename iterator_traits<_InputIterator1>::value_type,
- typename iterator_traits<_InputIterator2>::value_type>)
- __glibcxx_function_requires(_LessThanOpConcept<
- typename iterator_traits<_InputIterator2>::value_type,
- typename iterator_traits<_InputIterator1>::value_type>)
+ __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
+ __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
+
return std::lexicographical_compare(__first1, __last1, __first2,
- __last2, __gnu_cxx::__ops::less());
+ __last2, __gnu_cxx::__ops::
+ less<_ValueType1, _ValueType2>());
}
-
inline bool
lexicographical_compare(const unsigned char* __first1,
const unsigned char* __last1,
Index: include/bits/stl_heap.h
===================================================================
--- include/bits/stl_heap.h (revision 108409)
+++ include/bits/stl_heap.h (working copy)
@@ -1,6 +1,6 @@
// Heap implementation -*- C++ -*-
-// Copyright (C) 2001, 2004, 2005 Free Software Foundation, Inc.
+// Copyright (C) 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library. This library is free
// software; you can redistribute it and/or modify it under the
@@ -88,7 +88,11 @@
template<typename _RandomAccessIterator, typename _Distance>
inline bool
__is_heap(_RandomAccessIterator __first, _Distance __n)
- { return std::__is_heap(__first, __gnu_cxx::__ops::less(), __n); }
+ {
+ typedef typename iterator_traits<_RandomAccessIterator>::value_type
+ _ValueType;
+ return std::__is_heap(__first, __gnu_cxx::__ops::less<_ValueType>(), __n);
+ }
template<typename _RandomAccessIterator>
inline bool
@@ -181,7 +185,7 @@
_DistanceType((__last - __first) - 1),
_DistanceType(0),
__gnu_cxx::__move(*(__last - 1)),
- __gnu_cxx::__ops::less());
+ __gnu_cxx::__ops::less<_ValueType>());
}
template<typename _Tp, typename _RandomAccessIterator, typename _Distance,
@@ -250,8 +254,6 @@
__glibcxx_requires_valid_range(__first, __last);
__glibcxx_requires_heap_pred(__first, __last, __comp);
- typedef typename iterator_traits<_RandomAccessIterator>::value_type
- _ValueType;
std::__pop_heap(__first, __last - 1, __last - 1, __comp);
}
@@ -279,7 +281,7 @@
__glibcxx_requires_heap(__first, __last);
std::__pop_heap(__first, __last - 1, __last - 1,
- __gnu_cxx::__ops::less());
+ __gnu_cxx::__ops::less<_ValueType>());
}
/**
@@ -344,7 +346,7 @@
// concept requirements
__glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
- std::make_heap(__first, __last, __gnu_cxx::__ops::less());
+ std::make_heap(__first, __last, __gnu_cxx::__ops::less<_ValueType>());
}
/**
@@ -384,11 +386,13 @@
inline void
sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
{
+ typedef typename iterator_traits<_RandomAccessIterator>::value_type
+ _ValueType;
+
// concept requirements
- __glibcxx_function_requires(_LessThanComparableConcept<
- typename iterator_traits<_RandomAccessIterator>::value_type>)
+ __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
- std::sort_heap(__first, __last, __gnu_cxx::__ops::less());
+ std::sort_heap(__first, __last, __gnu_cxx::__ops::less<_ValueType>());
}
} // namespace std
Index: include/bits/predefined_ops.h
===================================================================
--- include/bits/predefined_ops.h (revision 108409)
+++ include/bits/predefined_ops.h (working copy)
@@ -39,21 +39,61 @@
{
namespace __ops
{
- struct less
- {
- template<typename _Lhs, typename _Rhs>
+ template<typename _Lhs, typename _Rhs = _Lhs>
+ struct less
+ {
bool
+ operator()(const _Lhs& __lhs, const _Lhs& __rhs) const
+ { return __lhs < __rhs; }
+
+ bool
operator()(const _Lhs& __lhs, const _Rhs& __rhs) const
{ return __lhs < __rhs; }
- };
+
+ bool
+ operator()(const _Rhs& __lhs, const _Lhs& __rhs) const
+ { return __lhs < __rhs; }
+
+ bool
+ operator()(const _Rhs& __lhs, const _Rhs& __rhs) const
+ { return __lhs < __rhs; }
+ };
- struct equal_to
- {
- template<typename _Lhs, typename _Rhs>
+ template<typename _Lhs>
+ struct less<_Lhs, _Lhs>
+ {
bool
+ operator()(const _Lhs& __lhs, const _Lhs& __rhs) const
+ { return __lhs < __rhs; }
+ };
+
+ template<typename _Lhs, typename _Rhs = _Lhs>
+ struct equal_to
+ {
+ bool
+ operator()(const _Lhs& __lhs, const _Lhs& __rhs) const
+ { return __lhs == __rhs; }
+
+ bool
operator()(const _Lhs& __lhs, const _Rhs& __rhs) const
{ return __lhs == __rhs; }
- };
+
+ bool
+ operator()(const _Rhs& __lhs, const _Lhs& __rhs) const
+ { return __lhs == __rhs; }
+
+ bool
+ operator()(const _Rhs& __lhs, const _Rhs& __rhs) const
+ { return __lhs == __rhs; }
+ };
+
+ template<typename _Lhs>
+ struct equal_to<_Lhs, _Lhs>
+ {
+ bool
+ operator()(const _Lhs& __lhs, const _Lhs& __rhs) const
+ { return __lhs == __rhs; }
+ };
/**
* @if maint
@@ -63,7 +103,7 @@
* binary predicates given to algorithms in the standard library.
* @endif
*/
- template<typename _Comp, typename _Value>
+ template<typename _Comp, typename _Lhs, typename _Value>
class __bind2nd
{
_Comp _M_comp;
@@ -73,11 +113,10 @@
explicit
__bind2nd(_Comp __comp, const _Value& __inval)
: _M_comp(__comp), _M_value(__inval) {}
-
- template<typename _Lhs>
- bool
- operator()(const _Lhs& __lhs)
- { return _M_comp(__lhs, _M_value); }
+
+ bool
+ operator()(const _Lhs& __lhs)
+ { return _M_comp(__lhs, _M_value); }
};
/**
@@ -85,26 +124,26 @@
* Specialisation of __bind2nd for equality.
* @endif
*/
- template<typename _Value>
- class __bind2nd<__gnu_cxx::__ops::equal_to, _Value>
+ template<typename _Lhs, typename _Value>
+ class __bind2nd<__gnu_cxx::__ops::equal_to<_Lhs, _Value>, _Lhs, _Value>
{
const _Value& _M_value;
public:
explicit
- __bind2nd(__gnu_cxx::__ops::equal_to, const _Value& __inval)
+ __bind2nd(__gnu_cxx::__ops::equal_to<_Lhs, _Value>,
+ const _Value& __inval)
: _M_value(__inval) {}
-
- template<typename _Lhs>
+
bool
operator()(const _Lhs& __lhs)
{ return __lhs == _M_value; }
};
- template<typename _Comp, typename _Value>
- inline __bind2nd<_Comp, _Value>
+ template<typename _Lhs, typename _Value, typename _Comp>
+ inline __bind2nd<_Comp, _Lhs, _Value>
bind2nd(_Comp __comp, const _Value& __value)
- { return __bind2nd<_Comp, _Value>(__comp, __value); }
+ { return __bind2nd<_Comp, _Lhs, _Value>(__comp, __value); }
} // namespace __ops
} // namespace __gnu_cxx
Index: include/bits/stl_algo.h
===================================================================
--- include/bits/stl_algo.h (revision 108409)
+++ include/bits/stl_algo.h (working copy)
@@ -124,7 +124,8 @@
{
// concept requirements
__glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
- return std::__median(__a, __b, __c, __gnu_cxx::__ops::less());
+
+ return std::__median(__a, __b, __c, __gnu_cxx::__ops::less<_Tp>());
}
/**
@@ -375,10 +376,14 @@
inline _ForwardIterator
adjacent_find(_ForwardIterator __first, _ForwardIterator __last)
{
+ typedef typename iterator_traits<_ForwardIterator>::value_type
+ _ValueType;
+
// concept requirements
- __glibcxx_function_requires(_EqualityComparableConcept<
- typename iterator_traits<_ForwardIterator>::value_type>)
- return std::adjacent_find(__first, __last, __gnu_cxx::__ops::equal_to());
+ __glibcxx_function_requires(_EqualityComparableConcept<_ValueType>)
+
+ return std::adjacent_find(__first, __last, __gnu_cxx::__ops::
+ equal_to<_ValueType>());
}
/**
@@ -445,6 +450,11 @@
_BinaryPredicate __predicate, forward_iterator_tag,
forward_iterator_tag)
{
+ typedef typename iterator_traits<_ForwardIterator1>::value_type
+ _ValueType1;
+ typedef typename iterator_traits<_ForwardIterator2>::value_type
+ _ValueType2;
+
// General case.
_ForwardIterator2 __p1, __p;
__p1 = __first2; ++__p1;
@@ -452,9 +462,9 @@
while (__first1 != __last1)
{
- __first1 = std::find_if(__first1, __last1,
- __gnu_cxx::__ops::bind2nd(__predicate,
- *__first2));
+ __first1 = std::find_if(__first1, __last1, __gnu_cxx::__ops::
+ bind2nd<_ValueType1, _ValueType2>(__predicate,
+ *__first2));
if (__first1 == __last1)
return __last1;
@@ -491,6 +501,11 @@
_BinaryPredicate __predicate, random_access_iterator_tag,
random_access_iterator_tag)
{
+ typedef typename iterator_traits<_ForwardIterator1>::value_type
+ _ValueType1;
+ typedef typename iterator_traits<_ForwardIterator2>::value_type
+ _ValueType2;
+
typedef typename iterator_traits<_ForwardIterator2>::difference_type
_Distance;
_Distance __length(__last2 - __first2);
@@ -499,16 +514,16 @@
return __last1;
_ForwardIterator1 __lastpossible(__last1 - __length + 1);
- __first1 = std::find_if(__first1, __lastpossible,
- __gnu_cxx::__ops::bind2nd(__predicate,
- *__first2));
+ __first1 = std::find_if(__first1, __lastpossible, __gnu_cxx::__ops::
+ bind2nd<_ValueType1, _ValueType2>(__predicate,
+ *__first2));
while(__first1 != __lastpossible)
{
if (std::equal(__first1, __first1 + __length, __first2, __predicate))
return __first1;
- __first1 = std::find_if(__first1 + 1, __lastpossible,
- __gnu_cxx::__ops::bind2nd(__predicate,
- *__first2));
+ __first1 = std::find_if(__first1 + 1, __lastpossible, __gnu_cxx::__ops::
+ bind2nd<_ValueType1, _ValueType2>(__predicate,
+ *__first2));
}
return __last1;
}
@@ -540,12 +555,16 @@
_ForwardIterator2 __first2, _ForwardIterator2 __last2,
_BinaryPredicate __predicate)
{
+ typedef typename iterator_traits<_ForwardIterator1>::value_type
+ _ValueType1;
+ typedef typename iterator_traits<_ForwardIterator2>::value_type
+ _ValueType2;
+
// concept requirements
__glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
__glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
__glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
- typename iterator_traits<_ForwardIterator1>::value_type,
- typename iterator_traits<_ForwardIterator2>::value_type>)
+ _ValueType1, _ValueType2>)
__glibcxx_requires_valid_range(__first1, __last1);
__glibcxx_requires_valid_range(__first2, __last2);
@@ -557,8 +576,9 @@
_ForwardIterator2 __tmp(__first2);
++__tmp;
if (__tmp == __last2)
- return std::find_if(__first1, __last1,
- __gnu_cxx::__ops::bind2nd(__predicate, *__first2));
+ return std::find_if(__first1, __last1, __gnu_cxx::__ops::
+ bind2nd<_ValueType1, _ValueType2>(__predicate,
+ *__first2));
return std::__search(__first1, __last1, __first2, __last2, __predicate,
std::__iterator_category(__first1),
@@ -593,14 +613,18 @@
search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
_ForwardIterator2 __first2, _ForwardIterator2 __last2)
{
+ typedef typename iterator_traits<_ForwardIterator1>::value_type
+ _ValueType1;
+ typedef typename iterator_traits<_ForwardIterator2>::value_type
+ _ValueType2;
+
// concept requirements
- __glibcxx_function_requires(_EqualOpConcept<
- typename iterator_traits<_ForwardIterator1>::value_type,
- typename iterator_traits<_ForwardIterator2>::value_type>)
+ __glibcxx_function_requires(_EqualOpConcept<_ValueType1, _ValueType2>)
+
return std::search(__first1, __last1, __first2, __last2,
- __gnu_cxx::__ops::equal_to());
+ __gnu_cxx::__ops::
+ equal_to<_ValueType1, _ValueType2>());
}
-
/**
@@ -618,15 +642,17 @@
_Integer __count, const _Tp& __val,
_BinaryPredicate __binary_pred, std::forward_iterator_tag)
{
+ typedef typename iterator_traits<_ForwardIterator>::value_type
+ _ValueType;
+
// concept requirements
__glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
__glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
- typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
+ _ValueType, _Tp>)
__glibcxx_requires_valid_range(__first, __last);
- __first = std::find_if(__first, __last,
- __gnu_cxx::__ops::bind2nd(__binary_pred,
- __val));
+ __first = std::find_if(__first, __last, __gnu_cxx::__ops::
+ bind2nd<_ValueType, _Tp>(__binary_pred, __val));
while (__first != __last)
{
typename iterator_traits<_ForwardIterator>::difference_type
@@ -642,9 +668,8 @@
return __first;
if (__i == __last)
return __last;
- __first = std::find_if(++__i, __last,
- __gnu_cxx::__ops::bind2nd(__binary_pred,
- __val));
+ __first = std::find_if(++__i, __last, __gnu_cxx::__ops::
+ bind2nd<_ValueType, _Tp>(__binary_pred, __val));
}
return __last;
}
@@ -664,7 +689,6 @@
_Integer __count, const _Tp& __val,
_BinaryPredicate __binary_pred, std::random_access_iterator_tag)
{
-
typedef typename std::iterator_traits<_RandomAccessIter>::difference_type
_DistanceType;
@@ -725,12 +749,14 @@
_Integer __count, const _Tp& __val,
_BinaryPredicate __binary_pred)
{
+ typedef typename iterator_traits<_ForwardIterator>::value_type
+ _ValueType;
+
if (__count <= 0)
return __first;
if (__count == 1)
- return std::find_if(__first, __last,
- __gnu_cxx::__ops::bind2nd(__binary_pred,
- __val));
+ return std::find_if(__first, __last, __gnu_cxx::__ops::
+ bind2nd<_ValueType, _Tp>(__binary_pred, __val));
return std::__search_n(__first, __last, __count, __val, __binary_pred,
std::__iterator_category(__first));
}
@@ -753,11 +779,14 @@
search_n(_ForwardIterator __first, _ForwardIterator __last,
_Integer __count, const _Tp& __val)
{
+ typedef typename iterator_traits<_ForwardIterator>::value_type
+ _ValueType;
+
// concept requirements
- __glibcxx_function_requires(_EqualOpConcept<
- typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
+ __glibcxx_function_requires(_EqualOpConcept<_ValueType, _Tp>)
+
return std::search_n(__first, __last, __count, __val,
- __gnu_cxx::__ops::equal_to());
+ __gnu_cxx::__ops::equal_to<_ValueType, _Tp>());
}
@@ -1322,11 +1351,14 @@
unique_copy(_InputIterator __first, _InputIterator __last,
_OutputIterator __result)
{
+ typedef typename iterator_traits<_InputIterator>::value_type
+ _ValueType;
+
// concept requirements
- __glibcxx_function_requires(_EqualityComparableConcept<
- typename iterator_traits<_InputIterator>::value_type>)
+ __glibcxx_function_requires(_EqualityComparableConcept<_ValueType>)
+
return std::unique_copy(__first, __last, __result,
- __gnu_cxx::__ops::equal_to());
+ __gnu_cxx::__ops::equal_to<_ValueType>());
}
/**
@@ -1387,10 +1419,14 @@
inline _ForwardIterator
unique(_ForwardIterator __first, _ForwardIterator __last)
{
+ typedef typename iterator_traits<_ForwardIterator>::value_type
+ _ValueType;
+
// concept requirements
- __glibcxx_function_requires(_EqualityComparableConcept<
- typename iterator_traits<_ForwardIterator>::value_type>)
- return std::unique(__first, __last, __gnu_cxx::__ops::equal_to());
+ __glibcxx_function_requires(_EqualityComparableConcept<_ValueType>)
+
+ return std::unique(__first, __last, __gnu_cxx::__ops::
+ equal_to<_ValueType>());
}
/**
@@ -2317,7 +2353,9 @@
// concept requirements
__glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
- std::partial_sort(__first, __middle, __last, __gnu_cxx::__ops::less());
+
+ std::partial_sort(__first, __middle, __last, __gnu_cxx::__ops::
+ less<_ValueType>());
}
/**
@@ -2417,11 +2455,13 @@
_OutputValueType;
// concept requirements
+ __glibcxx_function_requires(_LessThanOpConcept<_InputValueType,
+ _OutputValueType>)
__glibcxx_function_requires(_LessThanComparableConcept<_OutputValueType>)
- __glibcxx_function_requires(_LessThanComparableConcept<_InputValueType>)
return std::partial_sort_copy(__first, __last, __result_first,
- __result_last, __gnu_cxx::__ops::less());
+ __result_last, __gnu_cxx::__ops::
+ less<_InputValueType, _OutputValueType>());
}
/**
@@ -2586,7 +2626,8 @@
// concept requirements
__glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
- std::sort(__first, __last, __gnu_cxx::__ops::less());
+
+ std::sort(__first, __last, __gnu_cxx::__ops::less<_ValueType>());
}
@@ -2660,13 +2701,10 @@
_ValueType;
// concept requirements
- // Note that these are slightly stricter than those of the 4-argument
- // version, defined previously. The difference is in the strictness of
- // the comparison operations... so for looser checking, define your own
- // comparison function, as was intended.
- __glibcxx_function_requires(_SameTypeConcept<_Tp, _ValueType>)
- __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
- return std::lower_bound(__first, __last, __val, __gnu_cxx::__ops::less());
+ __glibcxx_function_requires(_LessThanOpConcept<_ValueType, _Tp>)
+
+ return std::lower_bound(__first, __last, __val, __gnu_cxx::__ops::
+ less<_ValueType, _Tp>());
}
/**
@@ -2739,10 +2777,10 @@
_ValueType;
// concept requirements
- // See comments on lower_bound.
- __glibcxx_function_requires(_SameTypeConcept<_Tp, _ValueType>)
- __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
- return std::upper_bound(__first, __last, __val, __gnu_cxx::__ops::less());
+ __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>)
+
+ return std::upper_bound(__first, __last, __val, __gnu_cxx::__ops::
+ less<_Tp, _ValueType>());
}
/**
@@ -2903,11 +2941,16 @@
_InputIterator2 __first2, _InputIterator2 __last2,
_OutputIterator __result)
{
+ typedef typename iterator_traits<_InputIterator1>::value_type
+ _ValueType1;
+ typedef typename iterator_traits<_InputIterator2>::value_type
+ _ValueType2;
+
// concept requirements
- __glibcxx_function_requires(_LessThanComparableConcept<
- typename iterator_traits<_InputIterator1>::value_type>)
+ __glibcxx_function_requires(_LessThanComparableConcept<_ValueType1>)
+
return std::merge(__first1, __last1, __first2, __last2, __result,
- __gnu_cxx::__ops::less());
+ __gnu_cxx::__ops::less<_ValueType2, _ValueType1>());
}
/**
@@ -3224,7 +3267,9 @@
// concept requirements
__glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
- std::inplace_merge(__first, __middle, __last, __gnu_cxx::__ops::less());
+
+ std::inplace_merge(__first, __middle, __last, __gnu_cxx::__ops::
+ less<_ValueType>());
}
/**
@@ -3330,7 +3375,9 @@
// concept requirements
__glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
- return std::stable_sort(__first, __last, __gnu_cxx::__ops::less());
+
+ return std::stable_sort(__first, __last, __gnu_cxx::__ops::
+ less<_ValueType>());
}
/**
@@ -3405,7 +3452,8 @@
// concept requirements
__glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
- std::nth_element(__first, __nth, __last, __gnu_cxx::__ops::less());
+ std::nth_element(__first, __nth, __last, __gnu_cxx::__ops::
+ less<_ValueType>());
}
/**
@@ -3428,8 +3476,7 @@
template<typename _ForwardIterator, typename _Tp, typename _Compare>
pair<_ForwardIterator, _ForwardIterator>
equal_range(_ForwardIterator __first, _ForwardIterator __last,
- const _Tp& __val,
- _Compare __comp)
+ const _Tp& __val, _Compare __comp)
{
typedef typename iterator_traits<_ForwardIterator>::value_type
_ValueType;
@@ -3497,11 +3544,11 @@
_ValueType;
// concept requirements
- // See comments on lower_bound.
- __glibcxx_function_requires(_SameTypeConcept<_Tp, _ValueType>)
- __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
+ __glibcxx_function_requires(_LessThanOpConcept<_ValueType, _Tp>)
+ __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>)
- return std::equal_range(__first, __last, __val, __gnu_cxx::__ops::less());
+ return std::equal_range(__first, __last, __val, __gnu_cxx::__ops::
+ less<_ValueType, _Tp>());
}
/**
@@ -3524,12 +3571,15 @@
binary_search(_ForwardIterator __first, _ForwardIterator __last,
const _Tp& __val, _Compare __comp)
{
+ typedef typename iterator_traits<_ForwardIterator>::value_type
+ _ValueType;
+
// concept requirements
__glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
__glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
- typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
- __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, _Tp,
- typename iterator_traits<_ForwardIterator>::value_type>)
+ _ValueType, _Tp>)
+ __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
+ _Tp, _ValueType>)
__glibcxx_requires_partitioned_pred(__first, __last, __val, __comp);
_ForwardIterator __i = std::lower_bound(__first, __last, __val, __comp);
@@ -3552,13 +3602,16 @@
binary_search(_ForwardIterator __first, _ForwardIterator __last,
const _Tp& __val)
{
+ typedef typename iterator_traits<_ForwardIterator>::value_type
+ _ValueType;
+
// concept requirements
- // See comments on lower_bound.
- __glibcxx_function_requires(_SameTypeConcept<_Tp,
- typename iterator_traits<_ForwardIterator>::value_type>)
- __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
- return std::binary_search(__first, __last, __val,
- __gnu_cxx::__ops::less());
+ __glibcxx_function_requires(_LessThanOpConcept<_ValueType, _Tp>)
+ __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>)
+ __glibcxx_requires_partitioned(__first, __last, __val);
+
+ return std::binary_search(__first, __last, __val, __gnu_cxx::__ops::
+ less<_ValueType, _Tp>());
}
// Set algorithms: includes, set_union, set_intersection, set_difference,
@@ -3635,11 +3688,16 @@
includes(_InputIterator1 __first1, _InputIterator1 __last1,
_InputIterator2 __first2, _InputIterator2 __last2)
{
+ typedef typename iterator_traits<_InputIterator1>::value_type
+ _ValueType1;
+ typedef typename iterator_traits<_InputIterator2>::value_type
+ _ValueType2;
+
// concept requirements
- __glibcxx_function_requires(_LessThanComparableConcept<
- typename iterator_traits<_InputIterator1>::value_type>)
- return std::includes(__first1, __last1, __first2, __last2,
- __gnu_cxx::__ops::less());
+ __glibcxx_function_requires(_LessThanComparableConcept<_ValueType1>)
+
+ return std::includes(__first1, __last1, __first2, __last2,
+ __gnu_cxx::__ops::less<_ValueType1, _ValueType2>());
}
/**
@@ -3729,11 +3787,16 @@
_InputIterator2 __first2, _InputIterator2 __last2,
_OutputIterator __result)
{
+ typedef typename iterator_traits<_InputIterator1>::value_type
+ _ValueType1;
+ typedef typename iterator_traits<_InputIterator2>::value_type
+ _ValueType2;
+
// concept requirements
- __glibcxx_function_requires(_LessThanComparableConcept<
- typename iterator_traits<_InputIterator1>::value_type>)
- return std::set_union(__first1, __last1, __first2, __last2, __result,
- __gnu_cxx::__ops::less());
+ __glibcxx_function_requires(_LessThanComparableConcept<_ValueType1>)
+
+ return std::set_union(__first1, __last1, __first2, __last2, __result,
+ __gnu_cxx::__ops::less<_ValueType1, _ValueType2>());
}
/**
@@ -3814,11 +3877,17 @@
_InputIterator2 __first2, _InputIterator2 __last2,
_OutputIterator __result)
{
+ typedef typename iterator_traits<_InputIterator1>::value_type
+ _ValueType1;
+ typedef typename iterator_traits<_InputIterator2>::value_type
+ _ValueType2;
+
// concept requirements
- __glibcxx_function_requires(_LessThanComparableConcept<
- typename iterator_traits<_InputIterator1>::value_type>)
+ __glibcxx_function_requires(_LessThanComparableConcept<_ValueType1>)
+
return std::set_intersection(__first1, __last1, __first2, __last2,
- __result, __gnu_cxx::__ops::less());
+ __result, __gnu_cxx::__ops::
+ less<_ValueType1, _ValueType2>());
}
/**
@@ -3905,11 +3974,17 @@
_InputIterator2 __first2, _InputIterator2 __last2,
_OutputIterator __result)
{
+ typedef typename iterator_traits<_InputIterator1>::value_type
+ _ValueType1;
+ typedef typename iterator_traits<_InputIterator2>::value_type
+ _ValueType2;
+
// concept requirements
- __glibcxx_function_requires(_LessThanComparableConcept<
- typename iterator_traits<_InputIterator1>::value_type>)
+ __glibcxx_function_requires(_LessThanComparableConcept<_ValueType1>)
+
return std::set_difference(__first1, __last1, __first2, __last2,
- __result, __gnu_cxx::__ops::less());
+ __result, __gnu_cxx::__ops::
+ less<_ValueType1, _ValueType2>());
}
/**
@@ -3998,11 +4073,16 @@
_InputIterator2 __first2, _InputIterator2 __last2,
_OutputIterator __result)
{
+ typedef typename iterator_traits<_InputIterator1>::value_type
+ _ValueType1;
+ typedef typename iterator_traits<_InputIterator2>::value_type
+ _ValueType2;
+
// concept requirements
- __glibcxx_function_requires(_LessThanComparableConcept<
- typename iterator_traits<_InputIterator1>::value_type>)
+ __glibcxx_function_requires(_LessThanComparableConcept<_ValueType1>)
return std::set_symmetric_difference(__first1, __last1, __first2, __last2,
- __result, __gnu_cxx::__ops::less());
+ __result, __gnu_cxx::__ops::
+ less<_ValueType1, _ValueType2>());
}
// min_element and max_element, with and without an explicitly supplied
@@ -4045,10 +4125,14 @@
inline _ForwardIterator
max_element(_ForwardIterator __first, _ForwardIterator __last)
{
+ typedef typename iterator_traits<_ForwardIterator>::value_type
+ _ValueType;
+
// concept requirements
- __glibcxx_function_requires(_LessThanComparableConcept<
- typename iterator_traits<_ForwardIterator>::value_type>)
- return std::max_element(__first, __last, __gnu_cxx::__ops::less());
+ __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
+
+ return std::max_element(__first, __last, __gnu_cxx::__ops::
+ less<_ValueType>());
}
/**
@@ -4090,10 +4174,14 @@
inline _ForwardIterator
min_element(_ForwardIterator __first, _ForwardIterator __last)
{
+ typedef typename iterator_traits<_ForwardIterator>::value_type
+ _ValueType;
+
// concept requirements
- __glibcxx_function_requires(_LessThanComparableConcept<
- typename iterator_traits<_ForwardIterator>::value_type>)
- return std::min_element(__first, __last, __gnu_cxx::__ops::less());
+ __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
+
+ return std::min_element(__first, __last, __gnu_cxx::__ops::
+ less<_ValueType>());
}
// next_permutation and prev_permutation, with and without an explicitly
@@ -4172,10 +4260,14 @@
next_permutation(_BidirectionalIterator __first,
_BidirectionalIterator __last)
{
+ typedef typename iterator_traits<_BidirectionalIterator>::value_type
+ _ValueType;
+
// concept requirements
- __glibcxx_function_requires(_LessThanComparableConcept<
- typename iterator_traits<_BidirectionalIterator>::value_type>)
- return std::next_permutation(__first, __last, __gnu_cxx::__ops::less());
+ __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
+
+ return std::next_permutation(__first, __last, __gnu_cxx::__ops::
+ less<_ValueType>());
}
/**
@@ -4252,10 +4344,14 @@
prev_permutation(_BidirectionalIterator __first,
_BidirectionalIterator __last)
{
+ typedef typename iterator_traits<_BidirectionalIterator>::value_type
+ _ValueType;
+
// concept requirements
- __glibcxx_function_requires(_LessThanComparableConcept<
- typename iterator_traits<_BidirectionalIterator>::value_type>)
- return std::prev_permutation(__first, __last, __gnu_cxx::__ops::less());
+ __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
+
+ return std::prev_permutation(__first, __last, __gnu_cxx::__ops::
+ less<_ValueType>());
}
// find_first_of, with and without an explicitly supplied comparison function.
@@ -4317,12 +4413,17 @@
find_first_of(_InputIterator __first1, _InputIterator __last1,
_ForwardIterator __first2, _ForwardIterator __last2)
{
+ typedef typename iterator_traits<_InputIterator>::value_type
+ _ValueType1;
+ typedef typename iterator_traits<_ForwardIterator>::value_type
+ _ValueType2;
+
// concept requirements
- __glibcxx_function_requires(_EqualOpConcept<
- typename iterator_traits<_InputIterator>::value_type,
- typename iterator_traits<_ForwardIterator>::value_type>)
+ __glibcxx_function_requires(_EqualOpConcept<_ValueType1, _ValueType2>)
+
return std::find_first_of(__first1, __last1, __first2, __last2,
- __gnu_cxx::__ops::equal_to());
+ __gnu_cxx::__ops::
+ equal_to<_ValueType1, _ValueType2>());
}
// find_end, with and without an explicitly supplied comparison function.
@@ -4475,12 +4576,17 @@
find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
_ForwardIterator2 __first2, _ForwardIterator2 __last2)
{
+ typedef typename iterator_traits<_ForwardIterator1>::value_type
+ _ValueType1;
+ typedef typename iterator_traits<_ForwardIterator2>::value_type
+ _ValueType2;
+
// concept requirements
- __glibcxx_function_requires(_EqualOpConcept<
- typename iterator_traits<_ForwardIterator1>::value_type,
- typename iterator_traits<_ForwardIterator2>::value_type>)
+ __glibcxx_function_requires(_EqualOpConcept<_ValueType1, _ValueType2>)
+
return std::find_end(__first1, __last1, __first2, __last2,
- __gnu_cxx::__ops::equal_to());
+ __gnu_cxx::__ops::
+ equal_to<_ValueType1, _ValueType2>());
}
} // namespace std
Index: src/string-inst.cc
===================================================================
--- src/string-inst.cc (revision 106945)
+++ src/string-inst.cc (working copy)
@@ -76,7 +76,7 @@
template
const C*
__find_if(const C*, const C*,
- __gnu_cxx::__ops::__bind2nd<bool(*)(const C&, const C&), C>,
+ __gnu_cxx::__ops::__bind2nd<bool(*)(const C&, const C&), C, C>,
random_access_iterator_tag);
} // namespace std