Re: [Patch] First bits of the algo merge

[Howard Hinnant <hhinnant at apple dot com>]

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