| Document number | P3757R0 |
| Date | 2025-06-21 |
| Audience | LEWG, SG9 (Ranges) |
| Reply-to | Hewill Kang <hewillk@gmail.com> |
This is the follow up of P2997.
This paper proposes removing the requirement that a callable be invocable with the value-type of an iterator in the
indirectly_unary_invocable and related concepts.
This change simplifies usage, avoids cryptic template errors, and enables support for projectors that return
non-movable types.
Initial revision.
The indirectly_unary_invocable currently has the following definition:
template<class F, class I>
concept indirectly_unary_invocable =
indirectly_readable<I> &&
copy_constructible<F> &&
invocable<F&, indirect-value-t<I>> &&
invocable<F&, iter_reference_t<I>> &&
common_reference_with<
invoke_result_t<F&, indirect-value-t<I>>,
invoke_result_t<F&, iter_reference_t<I>>>;
The red part is the lvalue reference to value-type of iterator in most cases, i.e.,
iter_value_t<I>&:
the concept requires F to be invocable with both the reference type and the value-type of
I, even if the value-type is never actually used in practice.
Unfortunately, this prevents some intuitive spellings, for example (godbolt):
vector<string> v;
ranges::for_each(v | views::as_rvalue, [](string&& s) { /* */ });
ranges::for_each requires indirectly_unary_invocable, so the lambda
also needs to be able to take with string&
even though we pass a range of string&&, since string& cannot bind to
string&&, the constraint is
not satisfied.
The error message from the compiler is even worse. From libc++ it is:
<source>:8:1: error: no matching function for call to object of type 'const __for_each'
8 | std::ranges::for_each(v | std::views::as_rvalue, [](std::string&& s) { /* */ });
| ^~~~~~~~~~~~~~~~~~~~~
/opt/compiler-explorer/clang-20.1.0/bin/../include/c++/v1/__algorithm/ranges_for_each.h:63:3: note: candidate template ignored: constraints not satisfied [with _Range = invoke_result_t<const __fn &, vector<string, allocator<string>> &>, _Proj = identity, _Func = (lambda at <source>:8:50)]
63 | operator()(_Range&& __range, _Func __func, _Proj __proj = {}) const {
| ^
/opt/compiler-explorer/clang-20.1.0/bin/../include/c++/v1/__algorithm/ranges_for_each.h:61:13: note: because 'indirectly_unary_invocable<(lambda at <source>:8:50), projected<iterator_t<as_rvalue_view<ref_view<vector<string, allocator<string> > > > >, identity> >' evaluated to false
61 | indirectly_unary_invocable<projected<iterator_t<_Range>, _Proj>> _Func>
| ^
/opt/compiler-explorer/clang-20.1.0/bin/../include/c++/v1/__iterator/concepts.h:206:60: note: because 'invocable<(lambda at <source>:8:50) &, __indirect_value_t<__type> >' evaluated to false
206 | indirectly_readable<_It> && copy_constructible<_Fp> && invocable<_Fp&, __indirect_value_t<_It>> &&
| ^
/opt/compiler-explorer/clang-20.1.0/bin/../include/c++/v1/__concepts/invocable.h:28:3: note: because 'std::invoke(std::forward<_Fn>(__fn), std::forward<_Args>(__args)...)' would be invalid: no matching function for call to 'invoke'
28 | std::invoke(std::forward<_Fn>(__fn), std::forward<_Args>(__args)...); // not required to be equality preserving
| ^
/opt/compiler-explorer/clang-20.1.0/bin/../include/c++/v1/__algorithm/ranges_for_each.h:55:3: note: candidate function template not viable: requires at least 3 arguments, but 2 were provided
55 | operator()(_Iter __first, _Sent __last, _Func __func, _Proj __proj = {}) const {
| ^ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1 error generated.
This is cryptic and not easy to understand: the reason marked in red only shows that
invocable<lambda&, __indirect_value_t<__type>> is false, and that's it. Unless the user
actually look
the implementation of __indirect_value_t, it is unlikely to know what going on here, which
is annoying.
Moreover, this requirement for value-type invocability also blocks other reasonable use cases, for example (godbolt):
struct NonMovable {
int val_;
NonMovable(int val) : val_(val) {}
NonMovable(NonMovable&&) = delete;
auto operator<=>(const NonMovable&) const = default;
};
vector<int> v{1, 2, 3, 4, 5};
ranges::sort(v, {}, [](int val) { return NonMovable{val}; });
We are trying to project the elements into non-movable-but-comparable objects for sorting,
but this is currently prohibited because projected has the following signature:
template<indirectly_readable I, indirectly_regular_unary_invocable<I> Proj>
using projected = /* */;
where indirectly_unary_invocable requires common_reference_with<invoke_result_t<Proj&, indirect-value-t<I>>,
invoke_result_t<Proj&, iter_reference_t<I>>>, so we need to
satisfy common_reference_with<NonMovable, NonMovable> since the lambda returns
NonMovable, which in turn needs to satisfy convertible_to<NonMovable, NonMovable>.
But that is always false
because
non-movable objects cannot be converted to each other.
In other words, the common_reference_with requirement involving
indirect-value-t<I> in
indirectly_unary_invocable prevents the use of projectors that return non-movable types. This is a
significant limitation.
This raises the question: why does indirectly_unary_invocable require value-type invocability at all?
P2997
indirectly helps us trace the history of why the corresponding binary version concept, i.e.,
indirect_equivalence_relation, requires this: because we do need to construct the value-type for
comparing.
For example, the implementation of ranges::unique_copy, which relies on
indirect_equivalence_relation, is as follows:
template <class _InputIter, class _OutputIter, class _BinaryPredicate,
class _Tp>
_OutputIter __unique_copy(_InputIter __first, _InputIter __last,
_OutputIter __result,
_BinaryPredicate __binary_pred, _Tp*) {
_Tp __value = *__first;
*__result = __value;
while (++__first != __last)
if (!__binary_pred(__value, *__first)) {
__value = *__first;
*++__result = __value;
}
return ++__result;
}
We can see that temporary construction of the value-type is unavoidable, as
indirect_equivalence_relation spells it out:
template<class F, class I1, class I2 = I1>
concept indirect_equivalence_relation =
indirectly_readable<I1> && indirectly_readable<I2> &&
copy_constructible<F> &&
equivalence_relation<F&, indirect-value-t<I1>, indirect-value-t<I2>> &&
equivalence_relation<F&, indirect-value-t<I1>, iter_reference_t<I2>> &&
equivalence_relation<F&, iter_reference_t<I1>, indirect-value-t<I2>> &&
equivalence_relation<F&, iter_reference_t<I1>, iter_reference_t<I2>>;
It appears that the unary version simply inherits this pattern from its binary counterpart.
However, this is completely unnecessary if we look at algorithms with such constrain, for example,
the most typical ranges::for_each:
// for_each. Apply a function to every element of a range.
template <class _InputIter, class _Function>
_Function for_each(_InputIter __first, _InputIter __last, _Function __f) {
for ( ; __first != __last; ++__first)
__f(*__first);
return __f;
}
we only dereference the iterator and invoke the function on the reference in each iteration, there is no value-type involved.
However, the original example is rejected because of indirectly_unary_invocable, which is the only
reason. The code compiles successfully if we switch to
std::for_each instead.
In the context of ranges, references are usually preferred over values. Constructing value-types is unnecessary unless required, as it can cause excessive copying. There seems to be no compelling reason to require a function to accept an iterator's lvalue value-type when accepting its reference would suffice.
Moreover, other common algorithms, such as count_if, etc.,
also
do not produce value-type if we look at their implementation:
template <class _InputIter, class _Predicate>
typename iterator_traits<_InputIter>::difference_type
count_if(_InputIter __first, _InputIter __last, _Predicate __pred) {
typename iterator_traits<_InputIter>::difference_type __n = 0;
for ( ; __first != __last; ++__first)
if (__pred(*__first))
++__n;
return __n;
}
However, they are currently subject to this unnecessary constraint because of indirect_unary_predicate.
Here is the summary table:
| Algorithm | Unary constraint concept | Requires value-type invocation? | Explanation |
|---|---|---|---|
ranges::for_each, for_each_n |
indirectly_unary_invocable |
❌ | Only involve invoke(f, invoke(proj, *it)) |
ranges::all_of, any_of, none_of |
indirect_unary_predicate |
❌ | Only involve invoke(pred, invoke(proj, *it)) |
ranges::find_if, find_if_not |
indirect_unary_predicate |
❌ | Only involve invoke(pred, invoke(proj, *it)) |
ranges::find_last_if, find_last_if_not |
indirect_unary_predicate |
❌ | Only involve invoke(pred, invoke(proj, *it)) |
ranges::count_if |
indirect_unary_predicate |
❌ | Only involve invoke(pred, invoke(proj, *it)) |
ranges::copy_if, replace_if, replace_copy_if, remove_if,
remove_copy_if
|
indirect_unary_predicate |
❌ | Only involve invoke(pred, invoke(proj, *it)) |
ranges::is_partitioned |
indirect_unary_predicate |
❌ | Only involve invoke(pred, invoke(proj, *it)) |
ranges::partition, stable_partition, partition_copy,
partition_point
|
indirect_unary_predicate |
❌ | Only involve invoke(pred, invoke(proj, *it)) |
ranges::filter_view, take_while_view, drop_while_view |
indirect_unary_predicate |
❌ | Only involve invoke(pred, *it) |
std::projected<I, Proj> |
indirectly_regular_unary_invocable |
❌ | Only involve invoke_result_t<Proj&, iter_reference_t<I>> |
std::projected_value_t<I, Proj> |
indirectly_regular_unary_invocable |
✅ | Involve invoke_result_t<Proj&, iter_value_t<I>&> |
It is worth noting that projected_value_t is the only one that actually requires the use of value-type
of iterators by desgin:
template<indirectly_readable I, indirectly_regular_unary_invocable<I> Proj> using projected_value_t = remove_cvref_t<invoke_result_t<Proj&, iter_value_t<I>&>>;
This means that once we remove the value-type invocability requirement in
indirectly_regular_unary_invocable,
it is necessary to reconstrain the template parameters of projected_value_t:
template<indirectly_readable I, copy_constructible Proj> requires invocable<Proj&, iter_value_t<I>&> using projected_value_t = remove_cvref_t<invoke_result_t<Proj&, iter_value_t<I>&>>;
And this seems to be a more appropriate signature, as the main point of
indirectly_regular_unary_invocable is to check invocability on
the reference, which is irrelevant compared to the actual definition of projected_value_t.
In summary, the current design of indirect unary callable concepts leads to needless complexity. Relaxing them to only focus on the reference type of iterator would allow constraint algorithms to behave more sensibly without triggering cryptic errors. Furthermore, this change enables support for projectors that return non-movable objects, which is a significant improvement.
Bump __cpp_lib_ranges in 17.3.2 [version.syn]: