This page is a snapshot from the LWG issues list, see the Library Active Issues List for more information and the meaning of C++11 status.

### 556. Is `Compare` a `BinaryPredicate`?

Section: 25.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 25.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 25.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 25.8 [alg.sorting]/2 as indicated:

   > 2 `Compare` is used as a function object type (20.14 [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.