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 ]