std::ranges...iter_result(3)

🎀 std::ranges...iter_result — C++ Standard Libary 🎀

okay bestie, welcome to the std::ranges...iter_result(3) page from the C++ Standard Libary manual 💖 this one is literally the fold-algorithm-with-an-iterator girlies, so grab a snack 🍓

---

✨ NAME ✨

std::ranges::fold_left_first_with_iter, std::ranges::fold_left_first_with_iter_result — yep, both of them, they're a package deal 🫶

---

🦋 Synopsis 🦋

so first off, these live in the header <algorithm> ✨

Call signature

(1) since C++23:

template< std::input_iterator I, std::sentinel_for<I> S,
          /*indirectly-binary-left-foldable*/<std::iter_value_t<I>, I> F >
requires std::constructible_from<
             std::iter_value_t<I>, std::iter_reference_t<I>>
constexpr /* see description */
    fold_left_first_with_iter( I first, S last, F f );

(2) since C++23:

template< ranges::input_range R,
          /*indirectly-binary-left-foldable*/<
              ranges::range_value_t<R>, ranges::iterator_t<R>> F >
requires std::constructible_from<
             ranges::range_value_t<R>, ranges::range_reference_t<R>>
constexpr /* see description */
    fold_left_first_with_iter( R&& r, F f );

Helper concepts

(3) exposition only*:

template< class F, class T, class I >
concept /*indirectly-binary-left-foldable*/ = /* see description */;

Helper class template

(4) since C++23:

template< class I, class T >
using fold_left_first_with_iter_result =
    ranges::in_value_result<I, T>;

---

💜 Description 💜 (no heading in the original, but like… it's the vibe)

so what does it DO 👀 it left-folds the elements of the given range, which is a fancy way of saying it returns the result of evaluating this chain expression:

f(f(f(f(x[1], x[2]), x[3]), ...), x[n])

where x[1], x[2], ..., x[n] are elements of the range. slay 💅

informally, ranges::fold_left_first_with_iter behaves like std::accumulate's overload that accepts a binary predicate, except that the *first is used internally as an initial element. no cap 🧚

🫶 the behavior is undefined if [first, last) is not a valid range. like, fr fr, don't do that, it's giving undefined behavior and not in a cute way 😭

1. the range is [first, last).
2. same as (1), except that it uses r as the range, as if by using ranges::begin(r) as first and ranges::end(r) as last.
3. equivalent to… (see the helper concepts below ⬇️)
4. the return type alias. see the "Return value" section for details ✨

🧚 3) equivalent to:

(3A) exposition only*:

template< class F, class T, class I, class U >
concept /*indirectly-binary-left-foldable-impl*/ =
    std::movable<T> &&
    std::movable<U> &&
    std::convertible_to<T, U> &&
    std::invocable<F&, U, std::iter_reference_t<I>> &&
    std::assignable_from<U&,
        std::invoke_result_t<F&, U, std::iter_reference_t<I>>>;

(3B) exposition only*:

template< class F, class T, class I >
concept /*indirectly-binary-left-foldable*/ =
    std::copy_constructible<F> &&
    std::indirectly_readable<I> &&
    std::invocable<F&, T, std::iter_reference_t<I>> &&
    std::convertible_to<std::invoke_result_t<F&, T,
        std::iter_reference_t<I>>,
        std::decay_t<std::invoke_result_t<F&, T,
        std::iter_reference_t<I>>>> &&
    /*indirectly-binary-left-foldable-impl*/<F, T, I,
        std::decay_t<std::invoke_result_t<F&, T,
        std::iter_reference_t<I>>>>;

💅 the niebloid tea 💅

the function-like entities described on this page are 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.

in practice, they may be implemented as function objects, or with special compiler extensions 👑

---

💖 Parameters 💖

• first, last — the range of elements to fold
• r — the range of elements to fold
• f — the binary function object

---

🌸 Return value 🌸

let U be decltype(ranges::fold_left(std::move(first), last, std::iter_value_t<I>(*first), f)) ✨

1. an object of type ranges::fold_left_first_with_iter_result<I, std::optional<U>>.
   • the member ranges::in_value_result::in holds an iterator to the end of the range.
   • the member ranges::in_value_result::value holds the result of the left-fold of given range over f.

if the range is empty, the return value is {std::move(first), std::optional<U>()}. (empty range rights 🥲)

2. same as (1) except that the return type is ranges::fold_left_first_with_iter_result<ranges::borrowed_iterator_t<R>, std::optional<U>>.

---

🦋 Possible implementations 🦋

like, here's roughly how the girlies implement it, iykyk:

class fold_left_first_with_iter_fn
{
    template<class O, class I, class S, class F>
    constexpr auto impl(I&& first, S&& last, F f) const
    {
        using U = decltype(
            ranges::fold_left(std::move(first), last, std::iter_value_t<I>(*first), f)
        );
        using Ret = ranges::fold_left_first_with_iter_result<O, std::optional<U>>;
        if (first == last)
            return Ret{std::move(first), std::optional<U>()};
        std::optional<U> init(std::in_place, *first);
        for (++first; first != last; ++first)
            *init = std::invoke(f, std::move(*init), *first);
        return Ret{std::move(first), std::move(init)};
    }

public:
    template<std::input_iterator I, std::sentinel_for<I> S,
             /*indirectly-binary-left-foldable*/<std::iter_value_t<I>, I> F>
    requires std::constructible_from<std::iter_value_t<I>, std::iter_reference_t<I>>
    constexpr auto operator()(I first, S last, F f) const
    {
        return impl<I>(std::move(first), std::move(last), std::ref(f));
    }

    template<ranges::input_range R, /*indirectly-binary-left-foldable*/<
        ranges::range_value_t<R>, ranges::iterator_t<R>> F>
    requires
        std::constructible_from<ranges::range_value_t<R>, ranges::range_reference_t<R>>
    constexpr auto operator()(R&& r, F f) const
    {
        return impl<ranges::borrowed_iterator_t<R>>(
            ranges::begin(r), ranges::end(r), std::ref(f)
        );
    }
};

inline constexpr fold_left_first_with_iter_fn
    fold_left_first_with_iter;

---

⭐ Complexity ⭐

exactly ranges::distance(first, last) - 1 (assuming the range is not empty) applications of the function object f 🎀 that's it, that's the math, we love efficiency 💅

---

🍓 Notes 🍓

the following little rundown compares all the constrained folding algorithms (converted out of table jail for your reading pleasure 🫶). every one of them: Fold function template → starts from / initial value / return type:

• ranges::fold_left → starts from left / initial value init / return type U
• ranges::fold_left_first → starts from left / initial value first element / return type std::optional<U>
• ranges::fold_right → starts from right / initial value init / return type U
• ranges::fold_right_last → starts from right / initial value last element / return type std::optional<U>
• ranges::fold_left_with_iter → starts from left / initial value init / return type (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 → starts from left / initial value first element / return type (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 🔥

• __cpp_lib_ranges_fold → value 202207L → std (C++23) → feature: std::ranges fold algorithms

---

💅 Example 💅

run this, bestie (the original says // Run this code 🫶):

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

int main()
{
    std::vector v{1, 2, 3, 4, 5, 6, 7, 8};

    auto sum = std::ranges::fold_left_first_with_iter
    (
        v.begin(), v.end(), std::plus<int>()
    );
    std::cout << "sum: " << sum.value.value() << '\n';
    assert(sum.in == v.end());

    auto mul = std::ranges::fold_left_first_with_iter(v, std::multiplies<int>());
    std::cout << "mul: " << mul.value.value() << '\n';
    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', 7.f}};
    auto sec = std::ranges::fold_left_first_with_iter
    (
        data | std::ranges::views::values, std::multiplies<>()
    );
    std::cout << "sec: " << sec.value.value() << '\n';

    // use a program defined function object (lambda-expression):
    auto lambda = [](int x, int y) { return x + y + 2; };
    auto val = std::ranges::fold_left_first_with_iter(v, lambda);
    std::cout << "val: " << val.value.value() << '\n';
    assert(val.in == v.end());
}

Output

sum: 36
mul: 40320
sec: 42
val: 50

ate. no crumbs. 💀✨

---

🌈 References 🌈

• C++23 standard (ISO/IEC 14882:2023):
• 27.6.18 Fold [alg.fold]

---

👑 See also 👑

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

---

and that's the whole page bestie 🫶💖 this iconic little number came straight from http://cppreference.com 🌈, dated 2024.06.10, and it's filed under std::ranges...iter_result(3) in the C++ Standard Libary manual. go fold something, ily 🎀✨