Re: [Patch] First bits of the algo merge

[chris jefferson <caj at cs dot york dot ac dot uk>]

Howard Hinnant wrote:
>
> On Dec 14, 2005, at 10:38 AM, Howard Hinnant wrote:
>
>> On Dec 14, 2005, at 10:32 AM, Paolo Carlini wrote:
>>
>>> Paolo Carlini wrote:
>>>
>>>>> In order to check that everything was fine (also wrt
>>>>> __ops::bind2nd), I
>>>>> decided to implement first the full change in v7-branch... and
>>>>> stumbled
>>>>> on partial_sort_copy. The problem is that the predicate is both
>>>>> passed
>>>>> to helpers working on the result iterators (i.e., make_heap,
>>>>> sort_heap)
>>>>> and on a pair (first, result_first). Therefore, *which*
>>>>> value_types?!?
>>>>>
>>>> Well, maybe the issue is not so serious, because, among the concepts
>>>> naturally there is:
>>>>
>>>>      __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
>>>> _OutputValueType>)
>>>>
>>>> and, if I understand correctly, that appear to imply that
>>>> <_OutputValueType, _OutputValueType> is fine.
>>>>
>>>>
>>> Actually, this issue is nasty, very nasty, and affects much more
>>> seriously equal_range, binary_search and other functions which pass
>>> around the predicate.
>>>
>>> Honestly, I'm about to give up, at least as far as mainline is
>>> concerned.
>>
>> I just now looked at partial_sort_copy and came to the same
>> conclusion you did (<_OutputValueType, _OutputValueType>).  I'll go
>> look at equal_range and binary_search...
>
> <slapping forehead>  My Bad!  I got us started down the wrong track with:
>
>> +  template<typename _Lhs, typename _Rhs>
>> +  struct equal_to
>> +  {
>> +      bool
>> +      operator()(const _Lhs& __lhs, const _Rhs& __rhs) const
>> +      { return __lhs == __rhs; }
>> +  };
>
> That part about explicitly declaring the types is right.  The
> implementation of equal_to (and less) is wrong.
>
> It should look more like:
>
> template <class _Lhs, class _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 <class _Lhs>
> struct equal_to<_Lhs, _Lhs>
> {
>     bool operator()(const _Lhs& __lhs, const _Lhs& __rhs) const
> {return __lhs == __rhs;}
> };

After chucking this through my own code, the only problem I found was
you also need:

template <class _Lhs>
struct equal_to<_Lhs, const _Lhs>
{
    bool operator()(const _Lhs& __lhs, const _Lhs& __rhs) const {return
__lhs == __rhs;}
};

template <class _Lhs>
struct equal_to<const _Lhs, _Lhs>
{
    bool operator()(const _Lhs& __lhs, const _Lhs& __rhs) const {return
__lhs == __rhs;}
};

to make equal_to<int, const int> work.

Chris