This page is a snapshot from the LWG issues list, see the Library Active Issues List for more information and the meaning of New status.
ranges::fold_meow
is overconstrainedSection: 27.6.18 [alg.fold] Status: New Submitter: Hewill Kang Opened: 2024-05-03 Last modified: 2024-06-24
Priority: 3
View other active issues in [alg.fold].
View all other issues in [alg.fold].
View all issues with New status.
Discussion:
The two convertible_to
constraints required by ranges::fold_meow
mainly
check whether the decayed result type of the binary operator can be constructed by both the invoke type
and the initial value type.
constructible_from
seems more appropriate here because we don't need to care whether
the two types can be converted implicitly and explicitly.
Taking string
and string_view
as examples, the former can only be explicitly constructed by
the latter and can be assigned by the latter, which makes ranges::fold_meow
unable to fold
ranges whose elements are of type string
with an initial value of type string_view
:
vector<string> vs{"a", "b", "c"};
string_view init{"d"};
auto result = ranges::fold_right(vs, init, plus{}); // still ill-formed after P2591R5 as the constraint is not satisfied
In addition, the two movable
constraints in the function signature seem to be too strict as well since we
only need to check that the decayed result type and the initial type can be move-constructible (one for returned by
elidable move and one for move into other overloads) instead of whether they can be move-assignable.
[2024-06-24; Reflector poll]
Set priority to 3 after reflector poll.
"NAD. Constraining algorithms is not about limiting the constraints to
the bare minimum required by implementation details. That's what the C++0x
attempt did - in an effort to maintain backward compatibility - and it's a mess.
While the string
/string_view
case might look superficially appealing,
it would also allow vector<string>
/int
,
which is much less so."
Proposed resolution:
This wording is relative to N4981.
Modify 27.4 [algorithm.syn], header <algorithm>
synopsis, as indicated:
#include <initializer_list> // see 17.10.2 [initializer.list.syn] namespace std { […] namespace ranges { […] template<class F, class T, class I, class U> concept indirectly-binary-left-foldable-impl = // exposition onlymovablemove_constructible<T> &&movablemove_constructible<U> &&convertible_toconstructible_from<T,U, T> && invocable<F&, U, iter_reference_t<I>> && assignable_from<U&, invoke_result_t<F&, U, iter_reference_t<I>>>; template<class F, class T, class I> concept indirectly-binary-left-foldable = // exposition only copy_constructible<F> && indirectly_readable<I> && invocable<F&, T, iter_reference_t<I>> &&convertible_toconstructible_from<decay_t<invoke_result_t<F&, T, iter_reference_t<I>>>,decay_t<invoke_result_t<F&, T, iter_reference_t<I>>>>&& indirectly-binary-left-foldable-impl<F, T, I, decay_t<invoke_result_t<F&, T, iter_reference_t<I>>>>; […] } […] }
Modify 27.6.18 [alg.fold] as indicated:
template<bidirectional_iterator I, sentinel_for<I> S, class T = iter_value_t<I>, indirectly-binary-right-foldable<T, I> F> constexpr auto ranges::fold_right(I first, S last, T init, F f); template<bidirectional_range R, class T = range_value_t<R>, indirectly-binary-right-foldable<T, iterator_t<R>> F> constexpr auto ranges::fold_right(R&& r, T init, F f);-3- Effects: Equivalent to:
[…]using U = decay_t<invoke_result_t<F&, iter_reference_t<I>, T>>; if (first == last) return U(std::move(init)); I tail = ranges::next(first, last); U accum=(invoke(f, *--tail, std::move(init))); while (first != tail) accum = invoke(f, *--tail, std::move(accum)); return accum;template<input_iterator I, sentinel_for<I> S, class T = iter_value_t<I>, indirectly-binary-left-foldable<T, I> F> constexpr see below ranges::fold_left_with_iter(I first, S last, T init, F f); template<input_range R, class T = range_value_t<R>, indirectly-binary-left-foldable<T, iterator_t<R>> F> constexpr see below ranges::fold_left_with_iter(R&& r, T init, F f);-6- Let
-7- Effects: Equivalent to:U
bedecay_t<invoke_result_t<F&, T, iter_reference_t<I>>>
.if (first == last) return {std::move(first), U(std::move(init))}; U accum=(invoke(f, std::move(init), *first)); for (++first; first != last; ++first) accum = invoke(f, std::move(accum), *first); return {std::move(first), std::move(accum)};-8- Remarks: The return type is
fold_left_with_iter_result<I, U>
for the first overload andfold_left_with_iter_result<borrowed_iterator_t<R>, U>
for the second overload.