std:: partial_sum

Дано binary_op как фактическую бинарную операцию:

• Если выполняется любое из следующих условий, программа является некорректной:

• Тип значения InputIt не конструируется из * first .
• acc не является записываемым в d_first .
• Результат binary_op ( acc, * iter ) (до C++20) binary_op ( std :: move ( acc ) , * iter ) (начиная с C++20) не является неявно преобразуемым к типу значения InputIt .

• Пусть d_last является итератором, который должен быть возвращён . Если выполняется любое из следующих условий, поведение не определено:

• binary_op изменяет любой элемент в [ first , last ) или [ d_first , d_last ) .
• binary_op инвалидирует любой итератор или поддиапазон в [ first , last ] или [ d_first , d_last ] .

1. ↑ Фактическое значение для присваивания является результатом присваивания на предыдущем шаге. Предполагаем, что результатом присваивания здесь является acc .

Параметры

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

Итератор на элемент, следующий за последним записанным элементом, или d_first если [ first , last ) является пустым.

Сложность

Дано \(\scriptsize N\) N как std:: distance ( first, last ) :

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

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++20
        *++d_first = sum;
    }
    return ++d_first;
    // или, начиная с C++14:
    // return std::partial_sum(first, last, d_first, std::plus<>());
}

template<class InputIt, class OutputIt, class BinaryOp>
constexpr // since C++20
OutputIt partial_sum(InputIt first, InputIt last, 
                     OutputIt d_first, BinaryOp 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++20
        *++d_first = acc;
    }
    return ++d_first;
}

Примечания

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

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

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

• его тип - это тип значения InputIt
• он записывается в d_first
• его значение передается в operator + или op
• он сохраняет возвращаемое значение operator + или 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: использует operator+(char, char) и присваивает значения char массиву int
std::partial_sum(i_array, i_array + 4, o_array);
// Ошибка: невозможно присвоить значения not_int массиву int
std::partial_sum(e_array, e_array + 4, o_array);
// OK: выполняет преобразования при необходимости
// 1. создает "acc" типа char (тип значения)
// 2. аргументы char используются для умножения long (char -> long)
// 3. произведение long присваивается "acc" (long -> char)
// 4. "acc" присваивается элементу "o_array" (char -> int)
// 5. возврат к шагу 2 для обработки оставшихся элементов входного диапазона
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 << "Первые " << v.size() << " четных числа: ";
    // записать результат в поток cout
    std::partial_sum(v.cbegin(), v.cend(), 
                     std::ostream_iterator<int>(std::cout, " "));
    std::cout << '\n';
    // записать результат обратно в вектор v
    std::partial_sum(v.cbegin(), v.cend(),
                     v.begin(), std::multiplies<int>());
    std::cout << "Первые " << v.size() << " степени двойки: ";
    for (int n : v)
        std::cout << n << ' ';
    std::cout << '\n';
}

Первые 10 четных чисел: 2 4 6 8 10 12 14 16 18 20 
Первые 10 степеней двойки: 2 4 8 16 32 64 128 256 512 1024

Отчёты о дефектах

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

Смотрите также