Re: [Patch] First bits of the algo merge

[Howard Hinnant <hhinnant at apple dot com>]

Fwiw, here's an updated exploration tool.  It incorporates two of  
Chris's comments:

1.  Adds the <T, const T> specializations.

2.  Adds METHOD_C:  This is an equal algorithm that does not forward  
to the predicated version (i.e. today's mainline code).

The demo is set up with an example which breaks under A, but not  
under B and C.  It is again a proxy iterator case, but this time the  
proxy has state that it wants to update on each conversion to T (for  
whatever reasons, I put in a count to update just as an example).

Comments and/or variations on this exploration welcome.

-Howard


#define METHOD_A 0
#define METHOD_B 1
#define METHOD_C 2

#define METHOD METHOD_A

#if METHOD == METHOD_A

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

#elif METHOD == METHOD_B

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

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

#endif

#include <iterator>

template <class InputIterator1, class InputIterator2, class  
BinaryPredicate>
inline
bool
equal(InputIterator1 first1, InputIterator1 last1,
      InputIterator2 first2, BinaryPredicate pred)
{
    for (; first1 != last1; ++first1, ++first2)
        if (!pred(*first1, *first2))
            return false;
    return true;
}

template <class InputIterator1, class InputIterator2>
inline
bool
equal(InputIterator1 first1, InputIterator1 last1, InputIterator2  
first2)
{
    typedef typename  
std::iterator_traits<InputIterator1>::value_type value_type1;
    typedef typename  
std::iterator_traits<InputIterator2>::value_type value_type2;
#if METHOD == METHOD_A
    return ::equal(first1, last1, first2, equal_to());
#elif METHOD == METHOD_B
    return ::equal(first1, last1, first2, equal_to<value_type1,  
value_type2>());
#elif METHOD == METHOD_C
    for (; first1 != last1; ++first1, ++first2)
        if (!(*first1 == *first2))
            return false;
    return true;
#endif
}

#include <iostream>
#include <iterator>
#include <cstddef>

template <typename T>
class iterator
{
    class proxy
    {
        friend class iterator;
        iterator* const iter_;
        int count_convert_;

        explicit proxy(iterator* iter) : iter_(iter), count_convert_ 
(0) {}
    public:
        operator T& ()       {++count_convert_; return iter_->deref();}

        T& operator= (const T& rh) {return iter_->deref() = rh;}
    };

public:
    typedef T value_type;
    typedef std::ptrdiff_t difference_type;
    typedef proxy pointer;
    typedef proxy reference;
    typedef std::random_access_iterator_tag iterator_category;

private:
    T* ptr_;

    T& deref() {return *ptr_;}

public:
    iterator(T* v) : ptr_(v) {}

    T* base() const {return ptr_;}

    proxy operator*() {return proxy(this);}
    proxy operator->() {return proxy(this);}
    const proxy operator->() const {return proxy 
(const_cast<iterator*>(this));}

    iterator& operator++() {++ptr_; return *this;}
    iterator operator++(int) {iterator tmp(*this); operator++();  
return tmp;}
    iterator& operator--() {--ptr_; return *this;}
    iterator operator--(int) {iterator tmp(*this); operator--();  
return tmp;}

    iterator& operator+=(difference_type n) {ptr_ += n; return *this;}
    iterator operator+(difference_type n) const {return iterator 
(*this) += n;}
    reference operator [] (difference_type i) const {return *(*this  
+ i);}

    iterator& operator-=(difference_type n) {return operator+=(-n);}
    iterator operator-(difference_type n) const {return iterator 
(*this) -= n;}
};

template <class T>
inline
iterator<T>
operator + (typename iterator<T>::difference_type n, const  
iterator<T>& y)
{
    return iterator<T>(y) += n;
}

template <class T>
inline
typename iterator<T>::difference_type
operator -(const iterator<T>& x, const iterator<T>& y)
{
    return x.base() - y.base();
}

template <class T>
inline
bool
operator ==(const iterator<T>& x, const iterator<T>& y)
{
    return x.base() == y.base();
}

template <class T>
inline
bool
operator !=(const iterator<T>& x, const iterator<T>& y)
{
    return !(x == y);
}

template <class T>
inline
bool
operator <(const iterator<T>& x, const iterator<T>& y)
{
    return x.base() < y.base();
}

template <class T>
inline
bool
operator >(const iterator<T>& x, const iterator<T>& y)
{
    return y < x;
}

template <class T>
inline
bool
operator <=(const iterator<T>& x, const iterator<T>& y)
{
    return !(y < x);
}

template <class T>
inline
bool
operator >=(const iterator<T>& x, const iterator<T>& y)
{
    return !(x < y);
}

struct BigNum
{
};

bool operator==(const BigNum&, const BigNum&) {return true;}

int main()
{
    BigNum   b[3];
    iterator<BigNum>   bb(b);
    std::cout << equal(b, b+3, b) << '\n';
    std::cout << equal(bb, bb+3, bb) << '\n';
}