Document number:   P1716R3
Date:   2019-11-06
Audience:   Library Working Group
Reply-to:  
Tomasz Kamiński <tomaszkam at gmail dot com>

ranges compare algorithm are over-constrained

1. Introduction

In this paper, we argue that the ranges version of the compare algorithm (like equal, mismatch, search) are over-constrained (they impose the validity of invocations that are never used). Thus they compare limited functionality in comparison to their STL1 counterparts.

To address above issues we propose the replace the indirect_relation<T, U> concept with the indirect_binary_predicate<T, U>, that requires only that pred(*t, *u) is well-formed (and drop unnecessary pred(*t, *t), pred(*u, *t) and pred(*u, *u) requirements).

This paper was reviewed by LEWG and was fowarded to LWG for inclusion for C++20, during the Cologne meeting.

2. Revision history

2.4. Revision 3

2.3. Revision 2

2.2. Revision 1

Included alternative names for proposed concepts that are constient with P1754:

2.1. Revision 0

Initial revision.

3. Motivation and Scope

With the current specification the range version of the compare algorithm (like equal, mismatch, search), are requiring that the provided functor f models the indirect_relation<T, U> — that implies that given the pair of iterator t of type T and u of type U, the following expression needs to be well-formed:

[ Note: For simplicitly we ignore the projection functionality. ]

Out of the above only the second (f(*t, *u)) expression is required for the implementation of the algorithms.

As consequence of the above decision, the code that was working correctly with the non-range version of the algorithm:

std::vector<std::string> texts;
std::vector<std::size_T> lengths;

auto [ti, si] = std::mismatch(texts.begin(), texts.end(),
                              lengths.begin(), lengths.end(),
                              [](std::string const& text, std::size_t lenght) { return text.size() == lenght; });

will not longer work, when migrated to ranges version:

auto [ti, si] = std::ranges::mismatch(text, lengts, [](std::string const& text, std::size_t lenght) { return text.size() == lenght; });

The other example of the limitation of the expressiveness of the current specification is the issue reported by Eric Niebler on the github page, that lead to the creation of this paper.

The range-v3 calendar example has the following: 
mismatch(rng-of-iterators, rng-of-sentinels, std::not_equal_to<>{})
This compiles in master but not in the deep-integration branch where mismatch is (properly) constrained with indirect_relation.

To address the above issue we propose to replace indirect_relation constrain with the indirect_binary_predicate (that will impose only f(*t, *t)) in the following algorithms:

In addition we propose to change indirectly_comparable to be refiment of indirect_binary_predicate instead of indirect_relation, thus addressing:

Finally, we introduce the equivalence_relation (and indirect_equivalence_relation) to correctly constrain following algorithms (thier impose this requirement in non-range version):

3.2. binary_predicate vs equivalence_relation

Above we propose to replace indirect_relation with either indirect_binary_predicate or indirect_equivalence_relation, depending on the algorithm. This may lead to the question, if we should not use indirect_equivalence_relation for each of the algorithms — the predicates presented in examples from the above section, seem to model equivalence, but only lack overloads for other argument types combinations.

Such approach will however silently prevent the some frequent usages of the compare algorithms like:

  // searching for first inversion in range
  auto it = std::ranges::adjacent_find(vec, std::greater{});

  auto searchPattern = [](std::string_view text, std::string_view pattern) { std::ranges::search(text, pattern); };
  // checking if all patterns can be found with in coresponding corpus
  std::ranges::equal(texts, patterns, searchPattern);

If these algorithms would be constrained with indirect_equivalence_relation the above code would still compile (all syntactic requirement as met as comparators are homogeneous), however, the code will have undefined behaviour — both std::greater<> and serachPattern does not meet the semantic requirements for equivalence relation, as they are not symmetric.

3.2. Specification requirements

Constrains currently placed on the compare algorithms are over-constrained in context of their specification. Majority of the algorithms are defined to find (or just inform about existence) a pair of iterators i1 (pointing into first range) and i2 (pointing into second range), for which the following expression:

invoke(pred, invoke(proj1, *i1), invoke(proj2, *i2))

returns either true or false value. [ Note: Rest of them are defined in terms of other compare algorithms. ]

To illustrate: the specification of serach from [alg.search]:

template<forward_iterator I1, sentinel_for<I1> S1, forward_iterator I2,
         sentinel_for<I2> S2, class Pred = ranges::equal_to,
         class Proj1 = identity, class Proj2 = identity>
  requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
  constexpr subrange<I1>
    ranges::search(I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = {},
                   Proj1 proj1 = {}, Proj2 proj2 = {});
template<forward_range R1, forward_range R2, class Pred = ranges::equal_to,
         class Proj1 = identity, class Proj2 = identity>
  requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2>
  constexpr safe_subrange_t<R1>
    ranges::search(R1&& r1, R2&& r2, Pred pred = {},
                   Proj1 proj1 = {}, Proj2 proj2 = {});
Returns:

 

  • {i, i + (last2 - first2)}, where i is the first iterator in the range [first1, last1 - (last2 - first2)) such that for every non-negative integer n less than last2 - first2 the condition 
    bool(invoke(pred, invoke(proj1, *(i + n)), invoke(proj2, *(first2 + n))))
    is true
  • Returns {last1, last1} if no such iterator exists.

Complexity:

At most (last1 - first1) * (last2 - first2) applications of the corresponding predicate and projections.

To implement above specification only the invocation of f(proj1(*i1), proj2(*i2)) is required, and any other combinations of argument (like f(proj(*i1), proj1(*i1))) is unnecessary.

3.3. Non-range specification

The old non-range algorithms are constrained using the BinaryPredicate requirements, that was implied by the template parameter. Per [algorithms.requirements], this only requires the predicate to be invocable with iterators provided in order of their occurrence in range signature:

When not otherwise constrained, 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 with respective value types T1 and T2, it should work correctly in the construct binary_pred(*first1, *first2) contextually converted to bool ([conv]).

[ Note: is_permutation, unique and unique_copy imposes additional requirement on predicate: it should impose equivalence relation on the arguments. ]

Due above, the non-range versions of the algorithms are more general and applicable, than their ranges counterpart. In addition, this unnecessary complicate the migration of the code to the rangified version of STL.

4. Proposed Wording

The proposed wording changes refer to N4830 (C++ Working Draft, 2019-08-15).

Apply following changes to [concepts.syn] Header <concepts> synopsis:

// [concept.relation], concept relation
template<class R, class T, class U>
  concept relation = see below;


// [concept.equivalencerelation], concept equivalence_relation
template<class R, class T, class U>
  concept equivalence_relation = see below;


// [concept.strictweakorder], concept strict_weak_order
template<class R, class T, class U>
  concept strict_weak_order = see below;

Insert following section after [concept.relation] Concept equivalence_relation:

Concept equivalence_relation [concept.equivalencerelation]

template<class R, class T, class U>
  concept equivalence_relation = relation<R, T, U>;
A relation models equivalence_relation only if it imposes an equivalence relation on its arguments.

Apply following changes to section [iterator.synopsis] Header <iterator> synopsis:

template<class F, class I1, class I2 = I1>
  concept indirect_binary_predicaterelation = see below;

template<class F, class I1, class I2 = I1>
  concept indirect_equivalence_relation = see below;

template<class F, class I1, class I2 = I1>
  concept indirect_strict_weak_order = see below;

Apply following changes to section [indirectcallable.indirectinvocable] Indirect callables:

template<class F, class I1, class I2 = I1>
  concept indirect_binary_predicaterelation =
    readable<I1> && readable<I2> &&
    copy_constructible<F> &&
    predicaterelation<F&, iter_value_t<I1>&, iter_value_t<I2>&> &&
    predicaterelation<F&, iter_value_t<I1>&, iter_reference_t<I2>> &&
    predicaterelation<F&, iter_reference_t<I1>, iter_value_t<I2>&> &&
    predicaterelation<F&, iter_reference_t<I1>, iter_reference_t<I2>> &&
    predicaterelation<F&, iter_common_reference_t<I1>, iter_common_reference_t<I2>>;

template<class F, class I1, class I2 = I1>
  concept indirect_equivalence_relation =
    readable<I1> && readable<I2> &&
    copy_constructible<F> &&
    equivalence_relation<F&, iter_value_t<I1>&, iter_value_t<I2>&> &&
    equivalence_relation<F&, iter_value_t<I1>&, iter_reference_t<I2>> &&
    equivalence_relation<F&, iter_reference_t<I1>, iter_value_t<I2>&> &&
    equivalence_relation<F&, iter_reference_t<I1>, iter_reference_t<I2>> &&
    equivalence_relation<F&, iter_common_reference_t<I1>, iter_common_reference_t<I2>>;

template<class F, class I1, class I2 = I1>
  concept indirect_strict_weak_order =
    readable<I1> && readable<I2> &&
    copy_constructible<F> &&
    strict_weak_order<F&, iter_value_t<I1>&, iter_value_t<I2>&> &&
    strict_weak_order<F&, iter_value_t<I1>&, iter_reference_t<I2>> &&
    strict_weak_order<F&, iter_reference_t<I1>, iter_value_t<I2>&> &&
    strict_weak_order<F&, iter_reference_t<I1>, iter_reference_t<I2>> &&
    strict_weak_order<F&, iter_common_reference_t<I1>, iter_common_reference_t<I2>>;

Apply following changes to section [alg.req.ind.cmp] Concept indirectly_comparable:

template<class I1, class I2, class R, class P1 = identity, 
        class P2 = identity>
   concept indirectly_comparable 
      = indirect_binary_predicaterelation<R, projected<I1, P1>, projected<I2, P2>>;

Apply following changes to section [algorithm.syn] Header <algorithm> synopsis:

namespace ranges {

template<input_iterator I, sentinel_for<I> S, class T, class Proj = identity>
  requires indirect_binary_predicaterelation<ranges::equal_to, projected<I, Proj>, const T*>
  constexpr I find(I first, S last, const T& value, Proj proj = {});

template<input_range R, class T, class Proj = identity>
  requires indirect_binary_predicaterelation<ranges::equal_to, projected<iterator_t<R>, Proj>, const T*>
  constexpr safe_iterator_t<R>
     find(R&& r, const T& value, Proj proj = {});

template<input_iterator I, sentinel_for<I> S, class Proj = identity,
         indirect_unary_predicate<projected<I, Proj>> Pred>
constexpr I find_if(I first, S last, Pred pred, Proj proj = {});

template<input_range R, class Proj = identity,
         indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
constexpr safe_iterator_t<R>
  find_if(R&& r, Pred pred, Proj proj = {});

template<input_iterator I, sentinel_for<I> S, class Proj = identity,
         indirect_unary_predicate<projected<I, Proj>> Pred>
constexpr I find_if_not(I first, S last, Pred pred, Proj proj = {});

template<input_range R, class Proj = identity,
         indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
constexpr safe_iterator_t<R> find_if_not(R&& r, Pred pred, Proj proj = {});

}

[...]

namespace ranges {

template<input_iterator I1, sentinel_for<I1> S1, forward_iterator I2, sentinel_for<I2> S2,
         class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity,
         indirect_relation<projected<I1, Proj1>,
                          projected<I2, Proj2>> Pred = ranges::equal_to>
  requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
  constexpr I1 find_first_of(I1 first1, S1 last1, I2 first2, S2 last2,
                             Pred pred = {},
                             Proj1 proj1 = {}, Proj2 proj2 = {});

template<input_range R1, forward_range R2, class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity,
        indirect_relation<projected<iterator_t<R1>, Proj1>,
                         projected<iterator_t<R2>, Proj2>> Pred = ranges::equal_to>
  requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2>
  constexpr safe_iterator_t<R1>
    find_first_of(R1&& r1, R2&& r2,
                  Pred pred = {},
                  Proj1 proj1 = {}, Proj2 proj2 = {});

}

[...]

namespace ranges {

template<forward_iterator I, sentinel_for<I> S, class Proj = identity,
         indirect_binary_predicaterelation<projected<I, Proj>, projected<I, Proj>> Pred = ranges::equal_to>
  constexpr I adjacent_find(I first, S last, Pred pred = {},
                            Proj proj = {});

template<forward_range R, class Proj = identity,
         indirect_binary_predicaterelation<projected<iterator_t<R>, Proj>, projected<iterator_t<R>, Proj>> Pred = ranges::equal_to>
  constexpr safe_iterator_t<R>
    adjacent_find(R&& r, Pred pred = {}, Proj proj = {});

}

[...]

namespace ranges {

template<input_iterator I, sentinel_for<I> S, class T, class Proj = identity>
  requires indirect_binary_predicaterelation<ranges::equal_to, projected<I, Proj>, const T*>
  constexpr iter_difference_t<I>
    count(I first, S last, const T& value, Proj proj = {});

template<input_range R, class T, class Proj = identity>
  requires indirect_binary_predicaterelation<ranges::equal_to, projected<iterator_t<R>, Proj>, const T*>
  constexpr range_difference_t<R>
    count(R&& r, const T& value, Proj proj = {});

template<input_iterator I, sentinel_for<I> S, class Proj = identity,
         indirect_unary_predicate<projected<I, Proj>> Pred>
  constexpr iter_difference_t<I>
    count_if(I first, S last, Pred pred, Proj proj = {});

template<input_range R, class Proj = identity,
         indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
  constexpr range_difference_t<R>
    count_if(R&& r, Pred pred, Proj proj = {});

}

[...]

namespace ranges {

[...]

template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2,
         class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity,
         indirect_relation<projected<I1, Proj1>,
                          projected<I2, Proj2>> Pred = ranges::equal_to>
  requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
  constexpr mismatch_result<I1, I2>
    mismatch(I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = {},
             Proj1 proj1 = {}, Proj2 proj2 = {});


template<input_range R1, input_range R2,
         class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity,
         indirect_relation<projected<iterator_t<R1>, Proj1>,
                          projected<iterator_t<R2>, Proj2>> Pred = ranges::equal_to>
  requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2>
  constexpr mismatch_result<safe_iterator_t<R1>, safe_iterator_t<R2>>
    mismatch(R1&& r1, R2&& r2, Pred pred = {},
             Proj1 proj1 = {}, Proj2 proj2 = {});

}

[...]

namespace ranges {

template<forward_iterator I1, sentinel_for<I1> S1, forward_iterator I2,
         sentinel_for<I2> S2, class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity,
         indirect_equivalence_relation<projected<I1, Proj1>, projected<I2, Proj2>> Pred = ranges::equal_to>
  requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
  constexpr bool is_permutation(I1 first1, S1 last1, I2 first2, S2 last2,
                                Pred pred = {},
                                Proj1 proj1 = {}, Proj2 proj2 = {});

template<forward_range R1, forward_range R2, class Pred = ranges::equal_to,
         class Proj1 = identity, class Proj2 = identity,
         indirect_equivalence_relation<projected<iterator_t<R1>, Proj1>, projected<iterator_t<R2>, Proj2>> Pred = ranges::equal_to>
  requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2>
  constexpr bool is_permutation(R1&& r1, R2&& r2, Pred pred = {},
                                Proj1 proj1 = {}, Proj2 proj2 = {});

}

[...]

namespace ranges {

template<input_iterator I, sentinel_for<I> S, class T1, class T2, class Proj = identity>
  requires writable<I, const T2&> &&
           indirect_binary_predicaterelation<ranges::equal_to, projected<I, Proj>, const T1*>
  constexpr I
    replace(I first, S last, const T1& old_value, const T2& new_value, Proj proj = {});

template<input_range R, class T1, class T2, class Proj = identity>
  requires writable<iterator_t<R>, const T2&> &&
    indirect_binary_predicaterelation<ranges::equal_to, projected<iterator_t<R>, Proj>, const T1*>
constexpr safe_iterator_t<R>
  replace(R&& r, const T1& old_value, const T2& new_value, Proj proj = {});

template<input_iterator I, sentinel_for<I> S, class T, class Proj = identity,
         indirect_unary_predicate<projected<I, Proj>> Pred>
  requires writable<I, const T&>
  constexpr I replace_if(I first, S last, Pred pred, const T& new_value, Proj proj = {});

template<input_range R, class T, class Proj = identity,
         indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
requires writable<iterator_t<R>, const T&>
  constexpr safe_iterator_t<R> replace_if(R&& r, Pred pred, const T& new_value, Proj proj = {});

}

[...]

namespace ranges {

template<class I, class O>
using replace_copy_result = copy_result<I, O>;

template<input_iterator I, sentinel_for<I> S, class T1, class T2, output_iterator<const T2&> O,
         class Proj = identity>
  requires indirectly_copyable<I, O> &&
           indirect_binary_predicaterelation<ranges::equal_to, projected<I, Proj>, const T1*>
constexpr replace_copy_result<I, O>
  replace_copy(I first, S last, O result, const T1& old_value, const T2& new_value,
               Proj proj = {});

template<input_range R, class T1, class T2, output_iterator<const T2&> O,
         class Proj = identity>
  requires indirectly_copyable<iterator_t<R>, O> &&
           indirect_binary_predicaterelation<ranges::equal_to, projected<iterator_t<R>, Proj>, const T1*>
  constexpr replace_copy_result<safe_iterator_t<R>, O>
    replace_copy(R&& r, O result, const T1& old_value, const T2& new_value,
                 Proj proj = {});

template<class I, class O>
  using replace_copy_if_result = copy_result<I, O>;

template<input_iterator I, sentinel_for<I> S, class T, output_iterator<const T&> O,
          class Proj = identity, indirect_unary_predicate<projected<I, Proj>> Pred>
  requires indirectly_copyable<I, O>
  constexpr replace_copy_if_result<I, O>
    replace_copy_if(I first, S last, O result, Pred pred, const T& new_value,
                    Proj proj = {});

template<input_range R, class T, output_iterator<const T&> O, class Proj = identity,
         indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
  requires indirectly_copyable<iterator_t<R>, O>
  constexpr replace_copy_if_result<safe_iterator_t<R>, O>
    replace_copy_if(R&& r, O result, Pred pred, const T& new_value,
                    Proj proj = {});

}

[...]

namespace ranges {

template<permutable I, sentinel_for<I> S, class T, class Proj = identity>
  requires indirect_binary_predicaterelation<ranges::equal_to, projected<I, Proj>, const T*>
  constexpr subrange<I> remove(I first, S last, const T& value, Proj proj = {});

template<forward_range R, class T, class Proj = identity>
  requires permutable<iterator_t<R>> &&
           indirect_binary_predicaterelation<ranges::equal_to, projected<iterator_t<R>, Proj>, const T*>
constexpr safe_subrange_t<R>
  remove(R&& r, const T& value, Proj proj = {});

template<permutable I, sentinel_for<I> S, class Proj = identity,
  indirect_unary_predicate<projected<I, Proj>> Pred>
  constexpr subrange<I> remove_if(I first, S last, Pred pred, Proj proj = {});

template<forward_range R, class Proj = identity,
         indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
  requires permutable<iterator_t<R>>
  constexpr safe_subrange_t<R>
    remove_if(R&& r, Pred pred, Proj proj = {});

}

[...]

namespace ranges {

template<class I, class O>
using remove_copy_result = copy_result<I, O>;

template<input_iterator I, sentinel_for<I> S, weakly_incrementable O, class T,
         class Proj = identity>
  requires indirectly_copyable<I, O> &&
           indirect_binary_predicaterelation<ranges::equal_to, projected<I, Proj>, const T*>
  constexpr remove_copy_result<I, O>
    remove_copy(I first, S last, O result, const T& value, Proj proj = {});

template<input_range R, weakly_incrementable O, class T, class Proj = identity>
  requires indirectly_copyable<iterator_t<R>, O> &&
           indirect_binary_predicaterelation<ranges::equal_to, projected<iterator_t<R>, Proj>, const T*>
  constexpr remove_copy_result<safe_iterator_t<R>, O>
    remove_copy(R&& r, O result, const T& value, Proj proj = {});

template<class I, class O>
  using remove_copy_if_result = copy_result<I, O>;

template<input_iterator I, sentinel_for<I> S, weakly_incrementable O,
         class Proj = identity, indirect_unary_predicate<projected<I, Proj>> Pred>
  requires indirectly_copyable<I, O>
  constexpr remove_copy_if_result<I, O>
    remove_copy_if(I first, S last, O result, Pred pred, Proj proj = {});

template<input_range R, weakly_incrementable O, class Proj = identity,
         indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
  requires indirectly_copyable<iterator_t<R>, O>
  constexpr remove_copy_if_result<safe_iterator_t<R>, O>
    remove_copy_if(R&& r, O result, Pred pred, Proj proj = {});

}

[...]

namespace ranges {

template<permutable I, sentinel_for<I> S, class Proj = identity,
  indirect_equivalence_relation<projected<I, Proj>> C = ranges::equal_to>
  constexpr I unique(I first, S last, C comp = {}, Proj proj = {});

template<forward_range R, class Proj = identity,
         indirect_equivalence_relation<projected<iterator_t<R>, Proj>> C = ranges::equal_to>
  requires permutable<iterator_t<R>>
  constexpr safe_iterator_t<R>
    unique(R&& r, C comp = {}, Proj proj = {});

}

[...]

namespace ranges {

template<class I, class O>
using unique_copy_result = copy_result<I, O>;

template<input_iterator I, sentinel_for<I> S, weakly_incrementable O,
         class Proj = identity, indirect_equivalence_relation<projected<I, Proj>> C = ranges::equal_to>
  requires indirectly_copyable<I, O> &&
           (forward_iterator<I> ||
            (input_iterator<O> && same_as<iter_value_t<I>, iter_value_t<O>>) ||
            indirectly_copyable_storable<I, O>)
  constexpr unique_copy_result<I, O>
    unique_copy(I first, S last, O result, C comp = {}, Proj proj = {});

template<input_range R, weakly_incrementable O, class Proj = identity,
         indirect_equivalence_relation<projected<iterator_t<R>, Proj>> C = ranges::equal_to>
  requires indirectly_copyable<iterator_t<R>, O> &&
          (forward_iterator<iterator_t<R>> ||
           (input_iterator<O> && same_as<iter_value_t<iterator_t<R>>, iter_value_t<O>>) ||
            indirectly_copyable_storable<iterator_t<R>, O>)
  constexpr unique_copy_result<safe_iterator_t<R>, O>
    unique_copy(R&& r, O result, C comp = {}, Proj proj = {});

}

Apply following changes to section [alg.find] Find:

template<input_iterator I, sentinel_for<I> S, class T, class Proj = identity>
  requires indirect_binary_predicaterelation<ranges::equal_to, projected<I, Proj>, const T*>
  constexpr I ranges::find(I first, S last, const T& value, Proj proj = {});

template<input_range R, class T, class Proj = identity>
  requires indirect_binary_predicaterelation<ranges::equal_to, projected<iterator_t<R>, Proj>, const T*>
  constexpr safe_iterator_t<R>
     ranges::find(R&& r, const T& value, Proj proj = {});

Apply following changes to section [alg.find.first.of] Find first:

template<input_iterator I1, sentinel_for<I1> S1, forward_iterator I2, sentinel_for<I2> S2,
         class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity,
         indirect_relation<projected<I1, Proj1>,
                          projected<I2, Proj2>> Pred = ranges::equal_to>
  requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
  constexpr I1 ranges::find_first_of(I1 first1, S1 last1, I2 first2, S2 last2,
                                     Pred pred = {},
                                     Proj1 proj1 = {}, Proj2 proj2 = {});

template<input_range R1, forward_range R2, class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity,
        indirect_relation<projected<iterator_t<R1>, Proj1>,
                         projected<iterator_t<R2>, Proj2>> Pred = ranges::equal_to>
  requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2>
  constexpr safe_iterator_t<R1>
    ranges::find_first_of(R1&& r1, R2&& r2,
                          Pred pred = {},
                          Proj1 proj1 = {}, Proj2 proj2 = {});

Apply following changes to section [alg.adjacent.find] Adjacent find:

template<forward_iterator I, sentinel_for<I> S, class Proj = identity,
         indirect_binary_predicaterelation<projected<I, Proj>, projected<I, Proj>> Pred = ranges::equal_to>
  constexpr I ranges::adjacent_find(I first, S last, Pred pred = {},
                                    Proj proj = {});

template<forward_range R, class Proj = identity,
         indirect_binary_predicaterelation<projected<iterator_t<R>, Proj>, projected<iterator_t<R>, Proj>> Pred = ranges::equal_to>
  constexpr safe_iterator_t<R>
    ranges::adjacent_find(R&& r, Pred pred = {}, Proj proj = {});

Apply following changes to section [alg.count] Count:

template<input_iterator I, sentinel_for<I> S, class T, class Proj = identity>
  requires indirect_binary_predicaterelation<ranges::equal_to, projected<I, Proj>, const T*>
  constexpr iter_difference_t<I>
    ranges::count(I first, S last, const T& value, Proj proj = {});

template<input_range R, class T, class Proj = identity>
  requires indirect_binary_predicaterelation<ranges::equal_to, projected<iterator_t<R>, Proj>, const T*>
  constexpr range_difference_t<R>
    ranges::count(R&& r, const T& value, Proj proj = {});

Apply following changes to section [mismatch] Mismatch:

template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2,
         class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity,
         indirect_relation<projected<I1, Proj1>,
                          projected<I2, Proj2>> Pred = ranges::equal_to>
  requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
  constexpr ranges::mismatch_result<I1, I2>
    ranges::mismatch(I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = {},
                     Proj1 proj1 = {}, Proj2 proj2 = {});


template<input_range R1, input_range R2,
         class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity,
         indirect_relation<projected<iterator_t<R1>, Proj1>,
                          projected<iterator_t<R2>, Proj2>> Pred = ranges::equal_to>
  requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2>
  constexpr ranges::mismatch_result<safe_iterator_t<R1>, safe_iterator_t<R2>>
    ranges::mismatch(R1&& r1, R2&& r2, Pred pred = {},i
                     Proj1 proj1 = {}, Proj2 proj2 = {});

Apply following changes to section [alg.is.permutation] Is permutation:

template<forward_iterator I1, sentinel_for<I1> S1, forward_iterator I2,
         sentinel_for<I2> S2, class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity,
         indirect_equivalence_relation<projected<I1, Proj1>, projected<I2, Proj2>> Pred = ranges::equal_to>
  requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
  constexpr bool ranges::is_permutation(I1 first1, S1 last1, I2 first2, S2 last2,
                                        Pred pred = {},
                                        Proj1 proj1 = {}, Proj2 proj2 = {});

template<forward_range R1, forward_range R2, class Pred = ranges::equal_to,
         class Proj1 = identity, class Proj2 = identity,
         indirect_equivalence_relation<projected<iterator_t<R1>, Proj1>, projected<iterator_t<R2>, Proj2>> Pred = ranges::equal_to>
  requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2>
  constexpr bool ranges::is_permutation(R1&& r1, R2&& r2, Pred pred = {},
                                        Proj1 proj1 = {}, Proj2 proj2 = {});

Apply following changes to section [alg.replace] Replace:

template<input_iterator I, sentinel_for<I> S, class T1, class T2, class Proj = identity>
  requires writable<I, const T2&> &&
           indirect_binary_predicaterelation<ranges::equal_to, projected<I, Proj>, const T1*>
  constexpr I
    ranges::replace(I first, S last, const T1& old_value, const T2& new_value, Proj proj = {});

template<input_range R, class T1, class T2, class Proj = identity>
  requires writable<iterator_t<R>, const T2&> &&
    indirect_binary_predicaterelation<ranges::equal_to, projected<iterator_t<R>, Proj>, const T1*>
constexpr safe_iterator_t<R>
  ranges::replace(R&& r, const T1& old_value, const T2& new_value, Proj proj = {});

[...]

template<input_iterator I, sentinel_for<I> S, class T1, class T2, output_iterator<const T2&> O,
         class Proj = identity>
  requires indirectly_copyable<I, O> &&
           indirect_binary_predicaterelation<ranges::equal_to, projected<I, Proj>, const T1*>
constexpr ranges::replace_copy_result<I, O>
  ranges::replace_copy(I first, S last, O result, const T1& old_value, const T2& new_value,
                       Proj proj = {});

template<input_range R, class T1, class T2, output_iterator<const T2&> O,
         class Proj = identity>
  requires indirectly_copyable<iterator_t<R>, O> &&
           indirect_binary_predicaterelation<ranges::equal_to, projected<iterator_t<R>, Proj>, const T1*>
  constexpr ranges::replace_copy_result<safe_iterator_t<R>, O>
    ranges::replace_copy(R&& r, O result, const T1& old_value, const T2& new_value,
                         Proj proj = {});

Apply following changes to section [alg.remove] Remove:

template<permutable I, sentinel_for<I> S, class T, class Proj = identity>
  requires indirect_binary_predicaterelation<ranges::equal_to, projected<I, Proj>, const T*>
  constexpr subrange<I> ranges::remove(I first, S last, const T& value, Proj proj = {});

template<forward_range R, class T, class Proj = identity>
  requires permutable<iterator_t<R>> &&
           indirect_binary_predicaterelation<ranges::equal_to, projected<iterator_t<R>, Proj>, const T*>
constexpr safe_subrange_t<R>
  ranges::remove(R&& r, const T& value, Proj proj = {});

[...]

template<input_iterator I, sentinel_for<I> S, weakly_incrementable O, class T,
         class Proj = identity>
  requires indirectly_copyable<I, O> &&
           indirect_binary_predicaterelation<ranges::equal_to, projected<I, Proj>, const T*>
  constexpr ranges::remove_copy_result<I, O>
    ranges::remove_copy(I first, S last, O result, const T& value, Proj proj = {});

template<input_range R, weakly_incrementable O, class T, class Proj = identity>
  requires indirectly_copyable<iterator_t<R>, O> &&
           indirect_binary_predicaterelation<ranges::equal_to, projected<iterator_t<R>, Proj>, const T*>
  constexpr ranges::remove_copy_result<safe_iterator_t<R>, O>
    ranges::remove_copy(R&& r, O result, const T& value, Proj proj = {});

Apply following changes to section [alg.unique] Unique:

template<permutable I, sentinel_for<I> S, class Proj = identity,
  indirect_equivalence_relation<projected<I, Proj>> C = ranges::equal_to>
  constexpr I ranges::unique(I first, S last, C comp = {}, Proj proj = {});

template<forward_range R, class Proj = identity,
         indirect_equivalence_relation<projected<iterator_t<R>, Proj>> C = ranges::equal_to>
  requires permutable<iterator_t<R>>
  constexpr safe_iterator_t<R>
    ranges::unique(R&& r, C comp = {}, Proj proj = {});

[...]

template<input_iterator I, sentinel_for<I> S, weakly_incrementable O,
         class Proj = identity, indirect_equivalence_relation<projected<I, Proj>> C = ranges::equal_to>
  requires indirectly_copyable<I, O> &&
           (forward_iterator<I> ||
            (input_iterator<O> && same_as<iter_value_t<I>, iter_value_t<O>>) ||
            indirectly_copyable_storable<I, O>)
  constexpr unique_copy_result<I, O>
    ranges::unique_copy(I first, S last, O result, C comp = {}, Proj proj = {});

template<input_range R, weakly_incrementable O, class Proj = identity,
         indirect_equivalence_relation<projected<iterator_t<R>, Proj>> C = ranges::equal_to>
  requires indirectly_copyable<iterator_t<R>, O> &&
          (forward_iterator<iterator_t<R>> ||
           (input_iterator<O> && same_as<iter_value_t<iterator_t<R>>, iter_value_t<O>>) ||
            indirectly_copyable_storable<iterator_t<R>, O>)
  constexpr unique_copy_result<safe_iterator_t<R>, O>
    ranges::unique_copy(R&& r, O result, C comp = {}, Proj proj = {});

Update the value of the __cpp_lib_ranges in [version.syn] "Header <version> synopsis" to reflect the date of approval of this proposal.

5. Implementability

Implementation of the changes proposed in this paper, may be found in following pull request for cmcstl2.

6. Acknowledgements

Special thanks and recognition goes to Sabre (http://www.sabre.com) for supporting the production of this proposal and author's participation in standardization committee.

7. References

  1. Eric Niebler, "[Indirect]Relation + non-comparable sentinels and input iterators == :-(", (Issue 599, https://github.com/ericniebler/stl2/issues/599)
  2. Herb Sutter et al., "Rename concepts to standard_case for C++20, while we still can" (P1754R1, https://wg21.link/p1754r1)
  3. Richard Smith, "Working Draft, Standard for Programming Language C++" (N4830, https://wg21.link/n4830)
  4. Casey Carter et al., "cmcstl2", (https://github.com/CaseyCarter/cmcstl2)
  5. Tomasz Kamiński, "Implemented changes from P1716", (Pull request #310, https://github.com/CaseyCarter/cmcstl2/pull/310)