std::ranges::fold_left_with_iter, std::ranges::fold_left_with_iter_result

Defined in header `<algorithm>`
Call signature
template< std::input_iterator I, std::sentinel_for<I> S, class T, /indirectly-binary-left-foldable/<T, I> F > constexpr ranges::fold_left_with_iter_result<I, /* see below */> fold_left_with_iter( I first, S last, T init, F f );	(1)	(since C++23) (until C++26)
template< std::input_iterator I, std::sentinel_for<I> S, class T = std::iter_value_t<I>, /indirectly-binary-left-foldable/<T, I> F > constexpr ranges::fold_left_with_iter_result<I, /* see below */> fold_left_with_iter( I first, S last, T init, F f );	(1)		(since C++26)
template< ranges::input_range R, class T, /indirectly-binary-left-foldable/<T, ranges::iterator_t<R>> F > constexpr ranges::fold_left_with_iter_result<ranges::borrowed_iterator_t<R>, /* see below */> fold_left_with_iter( R&& r, T init, F f );	(2)	(since C++23) (until C++26)
template< ranges::input_range R, class T = ranges::range_value_t<R>, /indirectly-binary-left-foldable/<T, ranges::iterator_t<R>> F > constexpr ranges::fold_left_with_iter_result<ranges::borrowed_iterator_t<R>, /* see below */> fold_left_with_iter( R&& r, T init, F f );	(2)		(since C++26)
Helper class template
template< class I, class T > using fold_left_with_iter_result = ranges::in_value_result<I, T>;	(3)	(since C++23)

For the definition of /*indirectly-binary-left-foldable*/, see this page.

Left-folds the elements of the source range, that is, returns the result of evaluation of the chain expression:
f(f(f(f(init, x₁), x₂), ...), x_n), where x₁, x₂, ..., x_n are elements of the source range. Also returns the past-the-end iterator of the source range.

1) The source range is [first, last).

2) The source range is r.

3) The return type alias template.

The function-like entities described on this page are algorithm function objects (informally known as niebloids), that is:

Explicit template argument lists cannot be specified when calling any of them.
None of them are visible to argument-dependent lookup.
When any of them are found by normal unqualified lookup as the name to the left of the function-call operator, argument-dependent lookup is inhibited.

Parameters

first, last	-	the iterator-sentinel pair defining the source range
r	-	the source range
init	-	the initial value of the fold
f	-	the binary function object

Return value

A ranges::fold_left_with_iter_result object where:

The data member in holds the past-the-end iterator of the source range.
The data member value holds the left-fold result, which is init if the source range is empty.

The second template argument of the return type is the decayed type of F's result type.

Notes

The following table compares all constrained folding algorithms. U below is the fold result type, it is the decayed type of F's result type.

Fold function template	Starts from	Initial value	Return type
ranges::fold_left	left	`init`	U
ranges::fold_left_first	left	first element	std::optional<U>
ranges::fold_right	right	`init`	U
ranges::fold_right_last	right	last element	std::optional<U>
ranges::fold_left_with_iter	left	`init`	(1) ranges::in_value_result<I,U> (2) ranges::in_value_result<BR,U>, where BR is ranges::borrowed_iterator_t<R>
ranges::fold_left_first_with_iter	left	first element	(1) ranges::in_value_result<I,std::optional<U>> (2) ranges::in_value_result<BR,std::optional<U>> where BR is ranges::borrowed_iterator_t<R>

Feature-test macro	Value	Std	Feature
`__cpp_lib_ranges_fold`	`202207L`	(C++23)	`std::ranges` fold algorithms
`__cpp_lib_algorithm_default_value_type`	`202403L`	(C++26)	List-initialization for algorithms (1,2)

Possible implementations

class fold_left_with_iter_fn
{
    template<class O, class I, class S, class T, class F>
    constexpr auto impl(I&& first, S&& last, T&& init, F f) const
    {
        using U = std::decay_t<std::invoke_result_t<F&, T, std::iter_reference_t<I>>>;
        using Ret = ranges::fold_left_with_iter_result<O, U>;
        if (first == last)
            return Ret{std::move(first), U(std::move(init))};
        U accum = std::invoke(f, std::move(init), *first);
        for (++first; first != last; ++first)
            accum = std::invoke(f, std::move(accum), *first);
        return Ret{std::move(first), std::move(accum)};
    }
public:
    template<std::input_iterator I, std::sentinel_for<I> S, class T = std::iter_value_t<I>,
             /*indirectly-binary-left-foldable*/<T, I> F>
    constexpr auto operator()(I first, S last, T init, F f) const
    {
        return impl<I>(std::move(first), std::move(last), std::move(init), std::ref(f));
    }
    
    using BR = ranges::borrowed_iterator_t<R>;
    
    template<ranges::input_range R, class T = ranges::range_value_t<R>,
             /*indirectly-binary-left-foldable*/<T, ranges::iterator_t<R>> F>
    constexpr auto operator()(R&& r, T init, F f) const
    {
        return impl<BR>(ranges::begin(r), ranges::end(r), std::move(init), std::ref(f));
    }
    
    template<ranges::forward_range R, class T = ranges::range_value_t<R>,
             /*indirectly-binary-left-foldable*/<T, ranges::iterator_t<R>> F>
    constexpr auto operator()(R&& r, T init, F f) const
    {
        return impl<BR>(ranges::begin(r),
                        ranges::next(ranges::begin(r), ranges::end(r)),
                        std::move(init), std::ref(f));
    }
};

inline constexpr fold_left_with_iter_fn fold_left_with_iter;

Example

#include <algorithm>
#include <cassert>
#include <complex>
#include <functional>
#include <ranges>
#include <utility>
#include <vector>

int main()
{
    namespace ranges = std::ranges;

    std::vector v{1, 2, 3, 4, 5, 6, 7, 8};
    
    auto sum = ranges::fold_left_with_iter(v.begin(), v.end(), 6, std::plus<int>());
    assert(sum.value == 42);
    assert(sum.in == v.end());
    
    auto mul = ranges::fold_left_with_iter(v, 0X69, std::multiplies<int>());
    assert(mul.value == 4233600);
    assert(mul.in == v.end());
    
    // Get the product of the std::pair::second of all pairs in the vector:
    std::vector<std::pair<char, float>> data {{'A', 2.f}, {'B', 3.f}, {'C', 3.5f}};
    auto sec = ranges::fold_left_with_iter
    (
        data | ranges::views::values, 2.0f, std::multiplies<>()
    );
    assert(sec.value == 42);
    
    // Use a program defined function object (lambda-expression):
    auto lambda = [](int x, int y){ return x + 0B110 + y; };
    auto val = ranges::fold_left_with_iter(v, -42, lambda);
    assert(val.value == 42);
    assert(val.in == v.end());

    using CD = std::complex<double>;
    std::vector<CD> nums{{1, 1}, {2, 0}, {3, 0}};
    #ifdef __cpp_lib_algorithm_default_value_type
        auto res = ranges::fold_left_with_iter(nums, {7, 0}, std::multiplies{});
    #else
        auto res = ranges::fold_left_with_iter(nums, CD{7, 0}, std::multiplies{});
    #endif
    assert((res.value == CD{42, 42}));
}

References

C++23 standard (ISO/IEC 14882:2024):

27.6.18 Fold [alg.fold]

ranges::fold_left (C++23)	left-folds a range of elements (algorithm function object)
ranges::fold_left_first (C++23)	left-folds a range of elements using the first element as an initial value (algorithm function object)
ranges::fold_right (C++23)	right-folds a range of elements (algorithm function object)
ranges::fold_right_last (C++23)	right-folds a range of elements using the last element as an initial value (algorithm function object)
ranges::fold_left_first_with_iter (C++23)	left-folds a range of elements using the first element as an initial value, and returns a pair (iterator, optional) (algorithm function object)
accumulate	sums up or folds a range of elements (function template)
reduce (C++17)	similar to `std::accumulate`, except out of order (function template)