Alexandre Oliva wrote:
>
> Roman Lechtchinsky writes:
>
> > Hi,
> > in 25.1.2 [lib.alg.find] in the Dec 96 WP the find algorithm is defined
> > as:
>
> > template<class InputIterator, class T>
> > InputIterator find(InputIterator first, InputIterator last, const T&
> > value);
>
> > The requirements section says: "Type T is EqualityComparable".
>
> I believe it should say:
>
> The type of (*first) is EqualityComparable with type T.
>
> But the definition of EqualityComparable only handles a single type at
> once, there's no definition (that I could find) for equality between
> different types.  However, if those values are of different types,
> some properties might not hold.
>
> The standard says that:
>
> For all a, a==a.

Obviously not possible for operator==(T1,T2)

> If a == b, b == a.

simple: For each operator==(T1,T2) define the operator==(T2,T1)
to do the same (probably by just returning arg2==arg1).

> If a == b && b == c, then a == c.

This could be replaced by

If a==b && a==c && T2 is EqualityComparable, then b==c.

Because of the second demand, for operator==(T1,T1) it is the same
as the original demand (just exchange the names of a and b, and
reverse the first equality). For operator==(T1,T2) it defines a
reasonable semantics (in fact, it would even be reasonable to demand
that T2 is EqualityComparable), and the analog demand for the second
parameter is forced by the modified second demand.

BTW, if you lower the second demand to

if a==b && operator==(T2,T1) exist, then b==a

you'll have to add the "two class transitivity" for the second
parameter to your demand list as well.

>
> Should this be required even if a and b are not of the same type (or
> share a common base class, for instance)?  I don't think find would
> depend on such properties, so it should not require this from type T.
> Different requirements should be established for comparations between
> different types, so that one can create appropriate operators and be
> sure that no unexpected property will be required by different
> implementations.
>
> It would be wise to add EqualityComparableWith.
> InequalityComparableWith may require more careful thought, as the
> standard templates for operator>, operator<= and operator>= assume
> both T1<T2 and T2<T1 are available.

Especially the "two class transitivity" given above is essential for
find. It would be very astonishing, if the following failed (assuming
find doesn't get to the end of the container, of course):

typedef container<myclass> cont;
typedef container<myclass>::iterator iter;

cont c;
fill(c);

// store the first object of container in "first"
iter cont==c.begin()
myclass first=*cont;

// find the next occurrence of this object and store it in "second"
++cont;
myclass second=*find(cont,c.end(),first);

assert(first==second);
---
[ comp.std.c++ is moderated.  To submit articles: try just posting with      ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

Hi,

in 25.1.2 [lib.alg.find] in the Dec 96 WP the find algorithm is defined
as:

template<class InputIterator, class T>
InputIterator find(InputIterator first, InputIterator last, const T&
value);

The requirements section says: "Type T is EqualityComparable".
I wonder if this requirement actually makes sense. It is not required
that the value type of InputIterator is T and thus operator==() for T
might not be the one used for comparisons. In particular, IMO the
following example is undefined:

class A {};
class B {};
bool operator==( const A&, const B& );
A *first, *last;
find( first, last, B() );

but if
bool operator==( const B&, const B& );
is added it becomes legal even though this operator isn't used by the
algorithm at all. If my analysis is correct I suggest to drop this
requirement for find, count, replace, remove and search_n ( I've
probably missed some). In algorithms like find_first_of or mismatch
there is no such requirement even though they use operator==(), too; the
"Returns" section describes how operator==() is invoked which is IMO
sufficient.

Bye

Roman
---
[ comp.std.c++ is moderated.  To submit articles: try just posting with      ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

Roman Lechtchinsky writes:

> Hi,
> in 25.1.2 [lib.alg.find] in the Dec 96 WP the find algorithm is defined
> as:

> template<class InputIterator, class T>
> InputIterator find(InputIterator first, InputIterator last, const T&
> value);

> The requirements section says: "Type T is EqualityComparable".

I believe it should say:

The type of (*first) is EqualityComparable with type T.

But the definition of EqualityComparable only handles a single type at
once, there's no definition (that I could find) for equality between
different types.  However, if those values are of different types,
some properties might not hold.

The standard says that:

For all a, a==a.
If a == b, b == a.
If a == b && b == c, then a == c.


Should this be required even if a and b are not of the same type (or
share a common base class, for instance)?  I don't think find would
depend on such properties, so it should not require this from type T.
Different requirements should be established for comparations between
different types, so that one can create appropriate operators and be
sure that no unexpected property will be required by different
implementations.

It would be wise to add EqualityComparableWith.
InequalityComparableWith may require more careful thought, as the
standard templates for operator>, operator<= and operator>= assume
both T1<T2 and T2<T1 are available.

--
Alexandre Oliva
mailto:oliva@dcc.unicamp.br mailto:aoliva@acm.org
Universidade Estadual de Campinas, SP, Brasil
---
[ comp.std.c++ is moderated.  To submit articles: Try just posting with your
                newsreader.  If that fails, use mailto:std-c++@ncar.ucar.edu
  comp.std.c++ FAQ: http://reality.sgi.com/austern/std-c++/faq.html
  Moderation policy: http://reality.sgi.com/austern/std-c++/policy.html
  Comments? mailto:std-c++-request@ncar.ucar.edu
]

Roman Lechtchinsky wrote:
>
> Hi,
>
> in 25.1.2 [lib.alg.find] in the Dec 96 WP the find algorithm is defined
> as:
>
> template<class InputIterator, class T>
> InputIterator find(InputIterator first, InputIterator last, const T&
> value);
>
> The requirements section says: "Type T is EqualityComparable".
> I wonder if this requirement actually makes sense. It is not required
> that the value type of InputIterator is T and thus operator==() for T
> might not be the one used for comparisons. In particular, IMO the
> following example is undefined:

The term EqualityComparable is not the same as saying that
operator==() must be used, it only means that the following must be
legal:

   InputIterator a;
   const T& b = /* something */;
   *a == b;


--
___________________________________________________________________
Marcelo Cantos, Research Assistant          marcelo@mds.rmit.edu.au
Multimedia Database Systems Group              Tel: +61-3-9282-2497
723 Swanston St, Carlton VIC 3053, Australia   Fax: +61-3-9282-2490
---
[ comp.std.c++ is moderated.  To submit articles: Try just posting with your
                newsreader.  If that fails, use mailto:std-c++@ncar.ucar.edu
  comp.std.c++ FAQ: http://reality.sgi.com/austern/std-c++/faq.html
  Moderation policy: http://reality.sgi.com/austern/std-c++/policy.html
  Comments? mailto:std-c++-request@ncar.ucar.edu
]

Marcelo Cantos writes:

> The term EqualityComparable is not the same as saying that
> operator==() must be used, it only means that the following must be
> legal:

>    InputIterator a;
>    const T& b = /* something */;
>    *a == b;

Read it again.  It refers to the section where EqualityComparable is
defined, and the definition is for a single type, so that there must be
a way to compare (==) instances of that class, but that is not the
purpose.

--
Alexandre Oliva
mailto:oliva@dcc.unicamp.br mailto:aoliva@acm.org
Universidade Estadual de Campinas, SP, Brasil
---
[ comp.std.c++ is moderated.  To submit articles: try just posting with      ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]