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
Paolo Carlini wrote:
>I'm finishing testing (already past 25_algorithms) the below in
>v7-branch (mainline compiler is currently broken, anyway).
>
>
I like the below version slightly better: the template parameters of
__ops::bind2nd and its helpers are now much more readable.
Also, double checked the concept checks, now seem right to me,
consistent with the actual operations carried out and the predicated
counterparts.
Tested x86-linux.
Paolo.
//////////////////
2005-12-15 Paolo Carlini <pcarlini@suse.de>
* include/bits/stl_algo.h (partial_sort_copy, lower_bound,
upper_bound, equal_range, binary_search): Fix concept checks.
2005-12-15 Paolo Carlini <pcarlini@suse.de>
Howard Hinnant <hhinnant@apple.com>
* include/bits/predefined_ops.h (struct less, struct equal_to,
class bind2nd): Fix to allow for proxy iterators lacking operator==
on the proxy type.
* include/bits/stl_algobase.h (min, max, mismatch, equal,
lexicographical_compare): Adjust callers.
* include/bits/stl_heap.h (is_heap, push_heap, pop_heap, make_heap,
sort_heap): Likewise.
* include/bits/stl_algo.h (__median, adjacent_find, __search, search,
__search_n, search_n, unique_copy, unique, partial_sort,
partial_sort_copy, sort, lower_bound, upper_bound, merge,
inplace_merge, stable_sort, nth_element, equal_range, binary_search,
includes, set_union, set_intersection, set_difference,
set_symmetric_difference, max_element, min_element, next_permutation,
prev_permutation, find_first_of, find_end): Likewise.
* src/string-inst.cc: Adjust __find_if instantiation.
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 std::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 std::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,21 +103,20 @@
* binary predicates given to algorithms in the standard library.
* @endif
*/
- template<typename _Comp, typename _Value>
+ template<typename _Lhs, typename _Value, typename _Comp>
class __bind2nd
{
+ const _Value& _M_value;
_Comp _M_comp;
- const _Value& _M_value;
public:
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); }
+ __bind2nd(const _Value& __inval, _Comp __comp)
+ : _M_value(__inval), _M_comp(__comp) {}
+
+ 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(const _Value& __inval,
+ __gnu_cxx::__ops::equal_to<_Lhs, _Value>)
: _M_value(__inval) {}
-
- template<typename _Lhs>
+
bool
operator()(const _Lhs& __lhs)
{ return __lhs == _M_value; }
};
- template<typename _Comp, typename _Value>
- inline __bind2nd<_Comp, _Value>
- bind2nd(_Comp __comp, const _Value& __value)
- { return __bind2nd<_Comp, _Value>(__comp, __value); }
+ template<typename _Lhs, typename _Value, typename _Comp>
+ inline __bind2nd<_Lhs, _Value, _Comp>
+ bind2nd(const _Value& __value, _Comp __comp)
+ { return __bind2nd<_Lhs, _Value, _Comp>(__value, __comp); }
} // 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>(*__first2, __predicate));
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,17 +514,19 @@
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>(*__first2, __predicate));
+
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));
- }
+ {
+ if (std::equal(__first1, __first1 + __length, __first2, __predicate))
+ return __first1;
+ __first1 = std::find_if(__first1 + 1, __lastpossible,
+ __gnu_cxx::__ops::
+ bind2nd<_ValueType1,
+ _ValueType2>(*__first2, __predicate));
+ }
return __last1;
}
@@ -540,12 +557,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 +578,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>(*__first2,
+ __predicate));
return std::__search(__first1, __last1, __first2, __last2, __predicate,
std::__iterator_category(__first1),
@@ -593,14 +615,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,33 +644,35 @@
_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>(__val, __binary_pred));
while (__first != __last)
- {
- typename iterator_traits<_ForwardIterator>::difference_type
- __n = __count;
- _ForwardIterator __i = __first;
- ++__i;
- while (__i != __last && __n != 1 && *__i == __val)
{
+ typename iterator_traits<_ForwardIterator>::difference_type
+ __n = __count;
+ _ForwardIterator __i = __first;
++__i;
- --__n;
- }
- if (__n == 1)
- return __first;
- if (__i == __last)
- return __last;
- __first = std::find_if(++__i, __last,
- __gnu_cxx::__ops::bind2nd(__binary_pred,
- __val));
+ while (__i != __last && __n != 1 && *__i == __val)
+ {
+ ++__i;
+ --__n;
+ }
+ if (__n == 1)
+ return __first;
+ if (__i == __last)
+ return __last;
+ __first = std::find_if(++__i, __last, __gnu_cxx::__ops::
+ bind2nd<_ValueType, _Tp>(__val,
+ __binary_pred));
}
return __last;
}
@@ -664,7 +692,6 @@
_Integer __count, const _Tp& __val,
_BinaryPredicate __binary_pred, std::random_access_iterator_tag)
{
-
typedef typename std::iterator_traits<_RandomAccessIter>::difference_type
_DistanceType;
@@ -679,28 +706,28 @@
__tailSize -= __pattSize;
while (1) // the main loop...
- {
- // __lookAhead here is always pointing to the last element of next
- // possible match.
- while (!__binary_pred(*__lookAhead, __val)) // the skip loop...
{
- if (__tailSize < __pattSize)
- return __last; // Failure
- __lookAhead += __pattSize;
- __tailSize -= __pattSize;
+ // __lookAhead here is always pointing to the last element of next
+ // possible match.
+ while (!__binary_pred(*__lookAhead, __val)) // the skip loop...
+ {
+ if (__tailSize < __pattSize)
+ return __last; // Failure
+ __lookAhead += __pattSize;
+ __tailSize -= __pattSize;
+ }
+ _DistanceType __remainder = __skipOffset;
+ for (_RandomAccessIter __backTrack = __lookAhead - 1;
+ __binary_pred(*__backTrack, __val); --__backTrack)
+ {
+ if (--__remainder == 0)
+ return (__lookAhead - __skipOffset); // Success
+ }
+ if (__remainder > __tailSize)
+ return __last; // Failure
+ __lookAhead += __remainder;
+ __tailSize -= __remainder;
}
- _DistanceType __remainder = __skipOffset;
- for (_RandomAccessIter __backTrack = __lookAhead - 1;
- __binary_pred(*__backTrack, __val); --__backTrack)
- {
- if (--__remainder == 0)
- return (__lookAhead - __skipOffset); // Success
- }
- if (__remainder > __tailSize)
- return __last; // Failure
- __lookAhead += __remainder;
- __tailSize -= __remainder;
- }
}
/**
@@ -725,12 +752,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>(__val, __binary_pred));
return std::__search_n(__first, __last, __count, __val, __binary_pred,
std::__iterator_category(__first));
}
@@ -753,11 +782,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 +1354,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 +1422,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 +2356,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 +2458,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 +2629,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 +2704,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 +2780,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 +2944,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 +3270,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 +3378,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 +3455,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 +3479,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 +3547,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 +3574,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 +3605,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 +3691,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 +3790,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 +3880,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 +3977,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 +4076,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 +4128,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 +4177,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 +4263,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 +4347,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 +4416,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 +4579,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<C, C, bool(*)(const C&, const C&)>,
random_access_iterator_tag);
} // namespace std