Proposed resolution:

This wording is relative to N4988.

1. Modify [func.search.bm] as indicated:

   boyer_moore_searcher(RandomAccessIterator1 pat_first,
                        RandomAccessIterator1 pat_last,
                        Hash hf = Hash(),
                        BinaryPredicate pred = BinaryPredicate());
   

   -1- Preconditions: The value type of RandomAccessIterator1 meets the Cpp17DefaultConstructible, Cpp17CopyConstructible, and Cpp17CopyAssignable requirements.

   -2- Let V be iterator_traits<RandomAccessIterator1>::value_type. For any two values A and B of type V, if pred(A, B) == true is true, then hf(A) == hf(B) is true.

   […]

   template<class RandomAccessIterator2>
     pair<RandomAccessIterator2, RandomAccessIterator2>
       operator()(RandomAccessIterator2 first, RandomAccessIterator2 last) const;
   

   […]

   -7- Returns: A pair of iterators i and j such that

   1. (7.1) — i is the first iterator in the range [first, last - (pat_last_ - pat_first_)) such that for every non-negative integer n less than pat_last_ - pat_first_ the following condition holds: pred(*(i + n), *(pat_first_ + n)) != false is true, and

   2. (7.2) — j == next(i, distance(pat_first_, pat_last_)) is true.

2. Modify [func.search.bmh] as indicated:

   boyer_moore_horspool_searcher(RandomAccessIterator1 pat_first,
                                 RandomAccessIterator1 pat_last,
                                 Hash hf = Hash(),
                                 BinaryPredicate pred = BinaryPredicate());
   

   -1- Preconditions: The value type of RandomAccessIterator1 meets the Cpp17DefaultConstructible, Cpp17CopyConstructible, and Cpp17CopyAssignable requirements.

   -2- Let V be iterator_traits<RandomAccessIterator1>::value_type. For any two values A and B of type V, if pred(A, B) == is true, then hf(A) == hf(B) is true.

   […]

   template<class RandomAccessIterator2>
     pair<RandomAccessIterator2, RandomAccessIterator2>
       operator()(RandomAccessIterator2 first, RandomAccessIterator2 last) const;
   

   […]

   -7- Returns: A pair of iterators i and j such that

   1. (7.1) — i is the first iterator in the range [first, last - (pat_last_ - pat_first_)) such that for every non-negative integer n less than pat_last_ - pat_first_ the following condition holds: pred(*(i + n), *(pat_first_ + n)) != false is true, and

   2. (7.2) — j == next(i, distance(pat_first_, pat_last_)) is true.

3. Modify [associative.reqmts.general] as indicated:

   -3- The phrase "equivalence of keys" means the equivalence relation imposed by the comparison object. That is, two keys k1 and k2 are considered to be equivalent if for the comparison object comp, !comp(k1, k2) == false && !comp(k2, k1) == false is true.

   […]

   -177- The fundamental property of iterators of associative containers is that they iterate through the containers in the non-descending order of keys where non-descending is defined by the comparison that was used to construct them. For any two dereferenceable iterators i and j such that distance from i to j is positive, the following condition holds:

   !value_comp(*j, *i) == false is true.

   -178- For associative containers with unique keys the stronger condition holds:

   value_comp(*i, *j) != false is true.

4. Modify [list.ops] as indicated:

   size_type remove(const T& value);
   template<class Predicate> size_type remove_if(Predicate pred);
   

   -15- Effects: Erases all the elements in the list referred to by a list iterator i for which the following conditions hold: *i == value is true, pred(*i) != false is true. Invalidates only the iterators and references to the erased elements.

   -16- Returns: The number of elements erased.

   -17- Throws: Nothing unless an exception is thrown by *i == value or pred(*i) != false.

   […]

5. Modify [alg.find] as indicated:

   [Drafting note: Sub-bullets (1.4), (1.5), and (1.6) below regarding invoke expressions are similarly required model boolean-testable, as specified by concept predicate ([concept.predicate]), therefore the explicit conversion is removed here for consistency]

   -1- Let E be:

   1. (1.1) — *i == value for find;

   2. (1.2) — pred(*i) != false for find_if;

   3. (1.3) — !pred(*i) == false for find_if_not;

   4. (1.4) — bool(invoke(proj, *i) == value) for ranges::find;

   5. (1.5) — bool(invoke(pred, invoke(proj, *i))) for ranges::find_if;

   6. (1.6) — bool(!invoke(pred, invoke(proj, *i))) for ranges::find_if_not.

   -2- Returns: The first iterator i in the range [first, last) for which E is true. Returns last if no such iterator is found.

6. Modify [alg.find.first.of] as indicated:

   -1- Let E be:

   1. (1.1) — *i == *j for the overloads with no parameter pred;

   2. (1.2) — pred(*i, *j) != false for the overloads with a parameter pred and no parameter proj1;

   3. (1.3) — bool(invoke(pred, invoke(proj1, *i), invoke(proj2, *j))) for the overloads with parameters pred and proj1.

   […]

   -3- Returns: The first iterator i in the range [first1, last1) such that for some iterator j in the range [first2, last2) E holds is true. Returns last1 if [first2, last2) is empty or if no such iterator is found.

7. Modify [alg.adjacent.find] as indicated:

   -1- Let E be:

   1. (1.1) — *i == *(i + 1) for the overloads with no parameter pred;

   2. (1.2) — pred(*i, *(i + 1)) != false for the overloads with a parameter pred and no parameter proj;

   3. (1.3) — bool(invoke(pred, invoke(proj, *i), invoke(proj, *(i + 1)))) for the overloads with both parameters pred and proj.

   -2- Returns: The first iterator i such that both i and i + 1 are in the range [first, last) for which E holds is true. Returns last if no such iterator is found.

8. Modify [alg.count] as indicated:

   -1- Let E be:

   1. (1.1) — *i == value for the overloads with no parameter pred or proj;

   2. (1.2) — pred(*i) != false for the overloads with a parameter pred but no parameter proj;

   3. (1.3) — invoke(proj, *i) == value for the overloads with a parameter proj but no parameter pred;

   4. (1.4) — bool(invoke(pred, invoke(proj, *i))) for the overloads with both parameters proj and pred.

   -2- Effects: Returns the number of iterators i in the range [first, last) for which E holds is true.

9. Modify [alg.mismatch] as indicated:

   -2- Let E be:

   1. (2.1) — !(*(first1 + n) == *(first2 + n)) for the overloads with no parameter pred;

   2. (2.2) — !pred(*(first1 + n), *(first2 + n)) == false for the overloads with a parameter pred and no parameter proj1;

   3. (2.3) — !invoke(pred, invoke(proj1, *(first1 + n)), invoke(proj2, *(first2 + n))) for the overloads with both parameters pred and proj1.

   […]

   -4- Returns: { first1 + n, first2 + n }, where n is the smallest integer in [0, N) such that E holds is true, or N if no such integer exists.

10. Modify [alg.search] as indicated:

    -1- Returns: The first iterator i in the range [first1, last1 - (last2-first2)) such that for every non-negative integer n less than last2 - first2 the following corresponding conditions hold: *(i + n) == *(first2 + n) is true, pred(*(i + n), *(first2 + n)) != false is true. Returns first1 if [first2, last2) is empty, otherwise returns last1 if no such iterator is found.

    […]

    -6- Let E be pred(*(i + n), value) != false for the overloads with a parameter pred, and *(i + n) == value otherwise.

    -7- Returns: The first iterator i in the range [first, last - count) such that for every non-negative integer n less than count the condition E is true. Returns last if no such iterator is found.

11. Modify [alg.sorting.general] as indicated:

    [Drafting note: The wording below does not require extra "is true" added to the adjusted expressions. This is comparable to the E cases above, since [alg.sorting.general] p2 already points out:

    The return value of the function call operation applied to an object of type Compare, when converted to bool, yields true if the first argument of the call is less than the second, and false otherwise.

    ]

    -3- For all algorithms that take Compare, there is a version that uses operator< instead. That is, comp(*i, *j) != false defaults to *i < *j != false. For algorithms other than those described in [alg.binary.search], comp shall induce a strict weak ordering on the values.

[ 2024-08-03; Daniel provides improved wording ]

The current wording is inconsistent in regard to explicit conversion to bool and lack of them in cases of expressions whose value is required to satisfy the boolean-testable constraints. To realize consistent results for all subclause references touched by the changes required by this issue I decided that every E definition remains unconverted but and that every E evaluation is interpreted as if an implied bool conversion has been applied based on the reflector preference for that simplified approach.

Nonetheless, during the wording preparation I noticed that the wording in the Throws: element [list.ops] p17 is seriously missing the additional extra conversion to bool for both expressions, because the boolean-testable requirements do not impose a no-throw requirement for that conversion, and they must therefore be included here.

This problem will be handled by a separate issue (LWG 4132), because the rationale for this change is different from the actual target of this issue and not related to the other consistency adjustments done by the wording below.

[ 2024-08-02; Reflector poll ]

Set priority to 3 after reflector poll. "Needs more 'is `true`' added". "Would prefer not to have explicit conversions to `bool` unless `boolean-testable` requires that. The 'Let E be' lists don't need an 'is true' there, but the use of 'E' should say 'is true'". [alg.search] and [func.search.bm] have changed editorially in the draft, the proposed resolution needs updating.

[ 2024-07-27; Daniel comments ]

I would recommend to add a wrapping "bool(pred([…]))" and possibly even extend to "bool(pred([…])) is true" following our usual wording convention, since an English phrase of the form "if pred([…])" where pred([…]) is potential non-bool and the English "if" is not a C++ language if (with built-in conversion semantics) doesn't sound like a meaningful phrase to me.

The boolean-testable concept introduced in P1964R2 places appropriate constraints on boolean-ish types, so that !pred(x) or i != last && pred(*i) always has a valid definition.

Subsequently, P2167R3 applied this concept to [algorithms.requirements] p6, requiring that decltype(pred(*first)) should model boolean-testable.

However, boolean-testable does not guarantee that pred(*i) != false is valid, because the type may overload operator==. It is necessary to replace this form of expression with an appropriate one as we do in P1964R2.