[Bug c++/14039] New: bug in std::find

["jsiek at osl dot iu dot edu" <gcc-bugzilla at gcc dot gnu dot org>]

The expression (*__first == __val) appears in the implementation
std::find. However, __first is only required to be an input iterator,
so *__first is required to be convertible to the value type
but not necessarily comparable with the value type. So
const value_type& x = *__first;
x == __value
would be a valid alternative.

The following program demonstrates the problem.


#include <algorithm>

namespace detail {
  class dummy_constructor { };
}

template <class T = int>
class null_archetype {
private:
  null_archetype() { }
  null_archetype(const null_archetype&) { }
  null_archetype& operator=(const null_archetype&) { return *this; }
public:
  null_archetype(detail::dummy_constructor) { }
  template <class TT>
  friend void dummy_friend(); // just to avoid warnings
};

class boolean_archetype {
public:
  boolean_archetype(const boolean_archetype&) { }
  operator bool() const { return true; }
  boolean_archetype(detail::dummy_constructor) { }
private:
  boolean_archetype() { }
  boolean_archetype& operator=(const boolean_archetype&) { return *this; }
};

template <class T>
class static_object
{
public:
    static T& get()
    {
        static char d[sizeof(T)];
        return *reinterpret_cast<T*>(d);
    }
};

template <class Base = null_archetype<> >
class equality_comparable2_first_archetype : public Base {
public:
  equality_comparable2_first_archetype(detail::dummy_constructor x) 
    : Base(x) { }
};
template <class Base = null_archetype<> >
class equality_comparable2_second_archetype : public Base {
public:
  equality_comparable2_second_archetype(detail::dummy_constructor x) 
    : Base(x) { }
};
template <class Base1, class Base2>
boolean_archetype
operator==(const equality_comparable2_first_archetype<Base1>&,
           const equality_comparable2_second_archetype<Base2>&) 
{
  return boolean_archetype(static_object<detail::dummy_constructor>::get());
}
template <class Base1, class Base2>
boolean_archetype
operator!=(const equality_comparable2_first_archetype<Base1>&,
           const equality_comparable2_second_archetype<Base2>&)
{
  return boolean_archetype(static_object<detail::dummy_constructor>::get());
}


template <class T, int I = 0>
class input_iterator_archetype
{
private:
  typedef input_iterator_archetype self;
public:
  typedef std::input_iterator_tag iterator_category;
  typedef T value_type;
  struct reference {
    operator const value_type&() const { return static_object<T>::get(); }
  };
  typedef const T* pointer;
  typedef std::ptrdiff_t difference_type;
  self& operator=(const self&) { return *this;  }
  bool operator==(const self&) const { return true; }
  bool operator!=(const self&) const { return true; }
  reference operator*() const { return reference(); }
  self& operator++() { return *this; }
  self operator++(int) { return *this; }
};


int main()
{
  typedef equality_comparable2_first_archetype<> Left;
  input_iterator_archetype< Left > in;
  detail::dummy_constructor dummy_cons;
  equality_comparable2_second_archetype<> value(dummy_cons);
  in = std::find(in, in, value);
}

-- 
           Summary: bug in std::find
           Product: gcc
           Version: 3.1
            Status: UNCONFIRMED
          Severity: normal
          Priority: P2
         Component: c++
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: jsiek at osl dot iu dot edu
                CC: gcc-bugs at gcc dot gnu dot org


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=14039