631. conflicting requirements for BinaryPredicate

Section: 26 [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 26 [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 (26.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 26 [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]