[Patch] First bits of the algo merge

[Howard Hinnant]

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;}
};

Now you don't have to pull your hair out in <algorithm>. ;-)

Sorry for the false start.  That proxy test is still on the way...

-Howard