std::partial_sum

template< class InputIt, class OutputIt >
OutputIt partial_sum( InputIt first, InputIt last, OutputIt d_first );

template< class InputIt, class OutputIt >
constexpr OutputIt partial_sum( InputIt first, InputIt last,
                                OutputIt d_first );

template< class InputIt, class OutputIt, class BinaryOperation >
OutputIt partial_sum( InputIt first, InputIt last,
                      OutputIt d_first, BinaryOperation op );

template< class InputIt, class OutputIt, class BinaryOperation >
constexpr OutputIt partial_sum( InputIt first, InputIt last,
                                OutputIt d_first, BinaryOperation op );

Если [first, last) не пусто, вычисляет частичные суммы элементов в его поддиапазонах и записывает суммы в диапазон, начинающийся с d_first, при этом применяя std::move к своим операндам слева(с C++11).

Внутренне используется переменная acc, тип которой соответствует типу значения InputIt, в качестве аккумулятора для промежуточных результатов.

std::iterator_traits<InputIt>::value_type acc = *first;
*d_first = acc;
 
acc = std::move(acc) + *(first + 1);
*(d_first + 1) = acc;
 
acc = std::move(acc) + *(first + 2);
*(d_first + 2) = acc;
 
acc = std::move(acc) + *(first + 3);
*(d_first + 3) = acc;
// ...

std::iterator_traits<InputIt>::value_type acc = *first;
*d_first = acc;
 
acc = op(std::move(acc), *(first + 1));
*(d_first + 1) = acc;
 
acc = op(std::move(acc), *(first + 2));
*(d_first + 2) = acc;
 
acc = op(std::move(acc), *(first + 3));
*(d_first + 3) = acc;
// ...

Параметры

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

Итератор на элемент после последнего записанного элемента или d_first если [first, last) пусто.

Сложность

Учитывая N как std::distance(first, last) - 1:

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

template<class InputIt, class OutputIt>
constexpr // since C++20
OutputIt partial_sum(InputIt first, InputIt last, OutputIt d_first)
{
    if (first == last)
        return d_first;
 
    typename std::iterator_traits<InputIt>::value_type sum = *first;
    *d_first = sum;
 
    while (++first != last)
    {
        sum = std::move(sum) + *first; // std::move since C++11
        *++d_first = sum;
    }
 
    return ++d_first;
 
    // or, since C++14:
    // return std::partial_sum(first, last, d_first, std::plus<>());
}

template<class InputIt, class OutputIt, class BinaryOperation>
constexpr // since C++20
OutputIt partial_sum(InputIt first, InputIt last, 
                     OutputIt d_first, BinaryOperation op)
{
    if (first == last)
        return d_first;
 
    typename std::iterator_traits<InputIt>::value_type acc = *first;
    *d_first = acc;
 
    while (++first != last)
    {
        acc = op(std::move(acc), *first); // std::move since C++11
        *++d_first = acc;
    }
 
    return ++d_first;
}

Примечания

acc был введён из-за решения LWG issue 539. Причина использования acc вместо непосредственного суммирования результатов (т.е. *(d_first + 2) = (*first + *(first + 1)) + *(first + 2);) заключается в том, что семантика последнего является неясной, если типы не совпадают:

• тип значения InputIt
• тип(ы) записи OutputIt
• типы параметров оператора+ или op
• тип возвращаемого значения оператора+ или op

acc служит промежуточным объектом для хранения и предоставления значений на каждом шаге вычисления:

• его тип равен типу значения InputIt
• он записывается в d_first
• его значение передаётся оператору+ или op
• он хранит возвращаемое значение оператора+ или op

enum not_int { x = 1, y = 2 };
 
char i_array[4] = {100, 100, 100, 100};
not_int e_array[4] = {x, x, y, y};
int  o_array[4];
 
// OK: uses operator+(char, char) and assigns char values to int array
std::partial_sum(i_array, i_array + 4, o_array);
 
// Error: cannot assign not_int values to int array
std::partial_sum(e_array, e_array + 4, o_array);
 
// OK: performs conversions when needed
// 1. creates `acc` of type char (the value type)
// 2. the char arguments are used for long multiplication (char -> long)
// 3. the long product is assigned to `acc` (long -> char)
// 4. `acc` is assigned to an element of `o_array` (char -> int)
// 5. go back to step 2 to process the remaining elements in the input range
std::partial_sum(i_array, i_array + 4, o_array, std::multiplies<long>{});

Пример

#include <functional>
#include <iostream>
#include <iterator>
#include <numeric>
#include <vector>
 
int main()
{
    std::vector<int> v(10, 2); // v = {2, 2, 2, 2, 2, 2, 2, 2, 2, 2}
 
    std::cout << "The first " << v.size() << " even numbers are: ";
    // write the result to the cout stream
    std::partial_sum(v.cbegin(), v.cend(), 
                     std::ostream_iterator<int>(std::cout, " "));
    std::cout << '\n';
 
    // write the result back to the vector v
    std::partial_sum(v.cbegin(), v.cend(),
                     v.begin(), std::multiplies<int>());
 
    std::cout << "The first " << v.size() << " powers of 2 are: ";
    for (int n : v)
        std::cout << n << ' ';
    std::cout << '\n';
}

The first 10 even numbers are: 2 4 6 8 10 12 14 16 18 20 
The first 10 powers of 2 are: 2 4 8 16 32 64 128 256 512 1024

Отчёты об ошибках

Следующие отчёты об ошибках, изменяющие поведение, были применены ретроактивно к ранее опубликованным стандартам C++.

См. также