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

### 631. conflicting requirements for `BinaryPredicate`

Section: 25 [algorithms] Status: NAD Submitter: James Kanze Opened: 2007-01-31 Last modified: 2016-01-28

Priority: Not Prioritized

View other active issues in [algorithms].

View all other issues in [algorithms].

View all issues with NAD status.

Discussion:

The general requirements for ``BinaryPredicate`` (in 25 [algorithms]/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` (25.8.4.3 [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:

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.

[ Toronto: Moved to Open. ConceptGCC seems to get `lower_bound` and `upper_bound` to work withoutt these changes. ]

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

[ 2009-10 Santa Cruz: ]

> Move to Review. The small problem with the "iterator type" will be fixed. The cited functions (`lower_bound`, `uppwer_bound`, `equal_range`) don't actually use `BinaryPredicate` , and where it is used, it is consistent with [algorithm]/8, so the main complaint of the issue is moot.

[ 2010-01-16 Beman clarified wording. ]

[ 2010-01-31: Moved to Tentatively NAD after 5 positive votes on c++std-lib. Rationale added below. ]

Rationale:

[ post San Francisco: ]

> Solved by N2759.

2010-01-31: The draft standard is well specified as is, and this specification is desired. Issues 556 and 870 solve the remaining unclearness regarding the meaning of BinaryPredicate.

Proposed resolution:

Change 25 [algorithms] paragraph 8 as indicated:

> 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. `BinaryPredicate` always takes the first iterator `value_type` as one of its arguments; which argument is unspecified. In other words, if 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)){...}`. `BinaryPredicate` always takes the first iterator type as its first argument, that is, in 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)){...}`. `binary_pred` shall not apply any non-constant function through the dereferenced iterators. [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. — end note]