556. Is Compare a BinaryPredicate?

Section: 26.8 [alg.sorting] Status: C++11 Submitter: Martin Sebor Opened: 2006-02-05 Last modified: 2016-01-28

Priority: Not Prioritized

View all other issues in [alg.sorting].

View all issues with C++11 status.

Discussion:

In 25, p8 we allow BinaryPredicates to return a type that's convertible to bool but need not actually be bool. That allows predicates to return things like proxies and requires that implementations be careful about what kinds of expressions they use the result of the predicate in (e.g., the expression in if (!pred(a, b)) need not be well-formed since the negation operator may be inaccessible or return a type that's not convertible to bool).

Here's the text for reference:

...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)){...}.

In 25.3, p2 we require that the Compare function object return true of false, which would seem to preclude such proxies. The relevant text is here:

Compare is used as a function object which returns true if the first argument is less than the second, and false otherwise...

[ Portland: Jack to define "convertible to bool" such that short circuiting isn't destroyed. ]

[ 2009-07-28 Reopened by Alisdair. No longer solved by concepts. ]

[ 2009-10 Santa Cruz: ]

Move to Review once wording received. Stefanus to send proposed wording.

[ 2009-10 Santa Cruz: ]

Move to Review once wording received. Stefanus to send proposed wording.

[ 2009-10-24 Stefanus supplied wording. ]

Move to Review once wording received. Stefanus to send proposed wording. Old proposed wording here:

I think we could fix this by rewording 25.3, p2 to read somthing like:

-2- Compare is used as a function object which returns true if the first argument a BinaryPredicate. The return value of the function call operator applied to an object of type Compare, when converted to type bool, yields true if the first argument of the call is less than the second, and false otherwise. Compare comp is used throughout for algorithms assuming an ordering relation. It is assumed that comp will not apply any non-constant function through the dereferenced iterator.

[ 2010-01-17: ]

Howard expresses concern that the current direction of the proposed wording outlaws expressions such as:

if (!comp(x, y))

Daniel provides wording which addresses that concern.

The previous wording is saved here:

Change 26.8 [alg.sorting] p2:

Compare is used as a function object. The return value of the function call operator applied to an object of type Compare, when converted to type bool, yields true if the first argument of the call which returns true if the first argument is less than the second, and false otherwise. Compare comp is used throughout for algorithms assuming an ordering relation. It is assumed that comp will not apply any non-constant function through the dereferenced iterator.

[ 2010-01-22 Moved to Tentatively Ready after 5 positive votes on c++std-lib. ]

Proposed resolution:

1. Change 26.1 [algorithms.general]/7+8 as indicated. [This change is recommended to bring the return value requirements of BinaryPredicate and Compare in sync.]

   7 The Predicate parameter is used whenever an algorithm expects a function object that when applied to the result of dereferencing the corresponding iterator returns a value testable as true. In other words, if an algorithm takes Predicate pred as its argument and first as its iterator argument, it should work correctly in the construct if (pred(*first)){...} pred(*first) contextually converted to bool (7.3 [conv]). The function object pred shall not apply any nonconstant function through the dereferenced iterator. This function object may be a pointer to function, or an object of a type with an appropriate function call operator.

   8 The BinaryPredicate parameter is used whenever an algorithm expects a function object that when applied to the result of dereferencing two corresponding iterators or to dereferencing an iterator and type T when T is part of the signature returns a value testable as true. In other words, 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)){...} binary_pred(*first1, *first2) contextually converted to bool (7.3 [conv]). 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)){...} construct binary_pred(*first1, value) contextually converted to bool (7.3 [conv]). binary_pred shall not apply any non-constant function through the dereferenced iterators.

2. Change 26.8 [alg.sorting]/2 as indicated:

   2 Compare is used as a function object type (22.10 [function.objects]). The return value of the function call operation applied to an object of type Compare, when contextually converted to type bool (7.3 [conv]), yields true if the first argument of the call which returns true if the first argument is less than the second, and false otherwise. Compare comp is used throughout for algorithms assuming an ordering relation. It is assumed that comp will not apply any non-constant function through the dereferenced iterator.