Topic: Defect in N2134: conflicting requirements for BinaryPredicate


Author: "James Kanze" <james.kanze@gmail.com>
Date: Wed, 31 Jan 2007 11:46:18 CST
Raw View
The general requirements for BinaryPredicate (in [algorithm]/8)
contradict the implied specific requirements for some functions.
In particular, it says that:

    [...] if an algorithm takes BinaryPredicate binary_pred
    as its argument and first1 and first2 as its iterator
    arguments, it should work correctly in the construct if
    (binary_pred (*first1 , *first2 )){...}.
    BinaryPredicate always takes the first iterator type as
    its first argument, that is, in those cases when T value
    is part of the signature, it should work correctly in
    the context of if (binary_pred (*first1 , value)){...}.

In the description of upper_bound ([upper.bound]/2), however,
the use is described as "!comp(value, e)", where e is an element
of the sequence (a result of dereferencing *first).

In the description of lexicographical_compare, we have both
"*first1 < *first2" and "*first2 < *first1" (which presumably
implies "comp( *first1, *first2 )" and "comp( *first2,
*first1 )".

Logically, the BinaryPredicate is used as an ordering
relationship, with the semantics of "less than".  Depending on
the function, it may be used to determine equality, or any of
the inequality relationships; doing this requires being able to
use it with either parameter first.  I would thus suggest that
the requirement be:

    [...]
    BinaryPredicate always takes the first iterator
    value_type as one of its arguments, it is unspecified
    which.  If an algorithm takes BinaryPredicate
    binary_pred as its argument and first1 and first2 as its
    iterator arguments, it should work correctly both in the
    construct if (binary_pred (*first1 , *first2 )){...} and
    if (binary_pred (*first2, *first1)){...}.  In those
    cases when T value is part of the signature, it should
    work correctly in the context of if (binary_pred
    (*first1 , value)){...} and of if (binary_pred (value,
    *first1)){...}. [Note: if the two types are not
    identical, and neither is convertable to the other, this
    may require that the BinaryPredicate be a functional
    object with two overloaded operator()() functions.]

Alternatively, one could specify an order for each function.
IMHO, this would be more work for the committee, more work
for the implementors, and of no real advantage for the user:
some functions, such as lexicographical_compare or
equal_range, will still require both functions, and it seems
like a much easier rule to teach that both functions are
always required, rather than to have a complicated list of
when you only need one, and which one.

--
James Kanze (GABI Software)             email:james.kanze@gmail.com
Conseils en informatique orient   e objet/
                   Beratung in objektorientierter Datenverarbeitung
9 place S   mard, 78210 St.-Cyr-l'   cole, France, +33 (0)1 30 23 00 34


---
[ 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    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]





Author: "Douglas Gregor" <doug.gregor@gmail.com>
Date: Thu, 1 Feb 2007 11:47:00 CST
Raw View
On Jan 31, 12:46 pm, "James Kanze" <james.ka...@gmail.com> wrote:
> Logically, the BinaryPredicate is used as an ordering
> relationship, with the semantics of "less than".  Depending on
> the function, it may be used to determine equality, or any of
> the inequality relationships; doing this requires being able to
> use it with either parameter first.  I would thus suggest that
> the requirement be:
>
>     [...]
>     BinaryPredicate always takes the first iterator
>     value_type as one of its arguments, it is unspecified
>     which.  If an algorithm takes BinaryPredicate
>     binary_pred as its argument and first1 and first2 as its
>     iterator arguments, it should work correctly both in the
>     construct if (binary_pred (*first1 , *first2 )){...} and
>     if (binary_pred (*first2, *first1)){...}.  In those
>     cases when T value is part of the signature, it should
>     work correctly in the context of if (binary_pred
>     (*first1 , value)){...} and of if (binary_pred (value,
>     *first1)){...}. [Note: if the two types are not
>     identical, and neither is convertable to the other, this
>     may require that the BinaryPredicate be a functional
>     object with two overloaded operator()() functions.]

There is definitely a problem with the BinaryPredicate requirements.
However, I think this change is strengthening the requirements on
BinaryPredicate, which means breaking user code, because some types
that met the old BinaryPredicate requirements will not meet the new
BinaryPredicate requirements.

I think the best answer is to do as you say below:

> Alternatively, one could specify an order for each function.
> IMHO, this would be more work for the committee, more work
> for the implementors, and of no real advantage for the user:
> some functions, such as lexicographical_compare or
> equal_range, will still require both functions, and it seems
> like a much easier rule to teach that both functions are
> always required, rather than to have a complicated list of
> when you only need one, and which one.

This is what the committee will end up doing when it evolves the
standard library to use concepts. Each algorithm will state all of the
requirements on its inputs using the concepts mechanism. Some uses of
BinaryPredicate will take the "reference" types of the iterators, some
will take the value types, some will take T's, etc. As you mentioned,
some algorithms do use the BinaryPredicate requirement multiple times
with different inputs. If you'd like to see how the standard
algorithms are specified using concepts, please refer to the proposal
to update chapter 25 of the standard to use concepts, here:

  http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n2084.pdf

I believe that document addresses all of the BinaryPredicate-related
issues.

More information about Concepts can be found in the latest concepts
proposal, here:

  http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n2081.pdf

  Cheers,
  Doug

---
[ 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    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]