std::ranges::fold_left_first_with_iter, std::ranges::fold_left_first_with_iter_result

Определён в заголовочном файле `<algorithm>`
Сигнатура вызова
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 ranges::fold_left_first_with_iter_result <I, std::optional</* see below */>> fold_left_first_with_iter( I first, S last, F f );	(1)	(начиная с 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 ranges::fold_left_first_with_iter_result <ranges::borrowed_iterator_t<R>, std::optional</* see below */>> fold_left_first_with_iter( R&& r, F f );	(2)	(начиная с C++23)
Вспомогательный шаблон
template< class I, class T > using fold_left_first_with_iter_result = ranges::in_value_result<I, T>;	(3)	(начиная с C++23)

Определение /*indirectly-binary-left-foldable*/ см. на этой странице.

Выполняет свёртку слева элементов исходного диапазона, то есть возвращает результат вычисления цепочечного выражения:
f(f(f(f(x₁, x₂), x₃), ...), x_n), где x₁, x₂, ..., x_n — элементы исходного диапазона. Также возвращает итератор, указывающий за конец исходного диапазона.

1) Исходный диапазон — это [first, last).

2) Исходный диапазон — это r.

3) Псевдоним типа возвращаемого значения.

Описанные на этой странице объекты, подобные функциям, являются объектами-функциями алгоритмов (неофициально известными как niebloids), то есть:

При вызове любого из них нельзя указывать явный список аргументов шаблона.
Ни один из них не доступен для поиска, зависящего от аргументов.
Если имя любого из них обнаружено посредством обычного неквалифицированного поиска в качестве имени слева от оператора вызова функции, поиск, зависящий от аргументов, подавляется.

Параметры

first, last	-	пара итератора и сентинела, задающая исходный диапазон
r	-	исходный диапазон
f	-	объект двоичной функции

Возвращаемое значение

Объект типа ranges::fold_left_first_with_iter_result, в котором:

Член данных in содержит итератор, указывающий за конец исходного диапазона.
Член данных value содержит объект std::optional с результатом свёртки слева либо не содержит значения, если исходный диапазон пуст.

Тип значения std::optional в возвращаемом типе — это тип результата F после удаления ссылок и квалификаторов.

Примечания

В следующей таблице сравниваются все алгоритмы свёртки с ограничениями. U ниже — тип результата свёртки; это тип результата F после удаления ссылок и квалификаторов.

Шаблон функции свёртки	Начальное направление	Начальное значение	Возвращаемый тип
ranges::fold_left	слева	`init`	U
ranges::fold_left_first	слева	первый элемент	std::optional<U>
ranges::fold_right	справа	`init`	U
ranges::fold_right_last	справа	последний элемент	std::optional<U>
ranges::fold_left_with_iter	слева	`init`	(1) ranges::in_value_result<I,U> (2) ranges::in_value_result<BR,U>, где BR — это ranges::borrowed_iterator_t<R>
ranges::fold_left_first_with_iter	слева	первый элемент	(1) ranges::in_value_result<I,std::optional<U>> (2) ranges::in_value_result<BR,std::optional<U>> где BR — это ranges::borrowed_iterator_t<R>

Макрос проверки поддержки возможностей	Значение	Стандарт	Возможность
`__cpp_lib_ranges_fold`	`202207L`	(C++23)	`std::ranges` алгоритмы свёртки

Возможные реализации

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));
    }
    
    using BR = ranges::borrowed_iterator_t<R>;
    
    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<BR>(ranges::begin(r), ranges::end(r), std::ref(f));
    }
    
    template<ranges::forward_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<BR>(ranges::begin(r),
                        ranges::next(ranges::begin(r), ranges::end(r)),
                        std::ref(f));
    }
};

inline constexpr fold_left_first_with_iter_fn fold_left_first_with_iter;

Пример

#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());
}

Вывод:

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

Ссылки

Стандарт C++23 (ISO/IEC 14882:2024):

27.6.18 Свёртка [alg.fold]

См. также

ranges::fold_left (C++23)	выполняет свёртку элементов диапазона слева (объект-функция алгоритма)
ranges::fold_left_first (C++23)	выполняет свёртку элементов диапазона слева, используя первый элемент в качестве начального значения (объект-функция алгоритма)
ranges::fold_right (C++23)	выполняет свёртку элементов диапазона справа (объект-функция алгоритма)
ranges::fold_right_last (C++23)	выполняет свёртку элементов диапазона справа, используя последний элемент в качестве начального значения (объект-функция алгоритма)
ranges::fold_left_with_iter (C++23)	выполняет свёртку элементов диапазона слева и возвращает пару (итератор, значение) (объект-функция алгоритма)
accumulate	суммирует элементы диапазона или выполняет их свёртку (шаблон функции)
reduce (C++17)	похож на `std::accumulate`, но порядок вычислений не фиксирован (шаблон функции)

© cppreference.com
Licensed under the Creative Commons Attribution-ShareAlike Unported License v3.0.
https://en.cppreference.com/cpp/algorithm/ranges/fold_left_first_with_iter