std:: partial_sum

Dado binary_op como la operación binaria real:

• Si se satisface cualquiera de las siguientes condiciones, el programa está mal formado:

• El tipo de valor de InputIt no es construible desde * first .
• acc no es escribible en d_first .
• El resultado de binary_op ( acc, * iter ) (hasta C++20) binary_op ( std :: move ( acc ) , * iter ) (desde C++20) no es convertible implícitamente al tipo de valor de InputIt .

• Dado d_last como el iterador a ser devuelto , si alguna de las siguientes condiciones se satisface, el comportamiento es indefinido:

• binary_op modifica cualquier elemento de [ first , last ) o [ d_first , d_last ) .
• binary_op invalida cualquier iterador o subrango en [ first , last ] o [ d_first , d_last ] .

1. ↑ El valor real que se asignará es el resultado de la asignación en el paso anterior. Asumimos que el resultado de la asignación es acc aquí.

Parámetros

Valor de retorno

Iterador al elemento después del último elemento escrito, o d_first si [ first , last ) está vacío.

Complejidad

Dado \(\scriptsize N\) N como std:: distance ( first, last ) :

Implementación posible

template<class InputIt, class OutputIt>
constexpr // desde 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 desde C++20
        *++d_first = sum;
    }
    return ++d_first;
    // o, desde C++14:
    // return std::partial_sum(first, last, d_first, std::plus<>());
}

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

Notas

acc se introdujo debido a la resolución de LWG issue 539 . La razón de usar acc en lugar de sumar directamente los resultados (es decir, * ( d_first + 2 ) = ( * first + * ( first + 1 ) ) + * ( first + 2 ) ; ) es porque la semántica de este último es confusa si los siguientes tipos no coinciden:

• el tipo de valor de InputIt
• el(los) tipo(s) escribible(s) de OutputIt
• los tipos de los parámetros de operator + o op
• el tipo de retorno de operator + o op

acc sirve como el objeto intermedio para almacenar y proporcionar los valores para cada paso del cálculo:

• su tipo es el tipo de valor de InputIt
• se escribe en d_first
• su valor se pasa a operator + o op
• almacena el valor de retorno de operator + o 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];
// CORRECTO: utiliza operator+(char, char) y asigna valores char al array int
std::partial_sum(i_array, i_array + 4, o_array);
// ERROR: no se pueden asignar valores not_int al array int
std::partial_sum(e_array, e_array + 4, o_array);
// CORRECTO: realiza conversiones cuando es necesario
// 1. crea "acc" de tipo char (el tipo de valor)
// 2. los argumentos char se usan para multiplicación long (char -> long)
// 3. el producto long se asigna a "acc" (long -> char)
// 4. "acc" se asigna a un elemento de "o_array" (char -> int)
// 5. vuelve al paso 2 para procesar los elementos restantes en el rango de entrada
std::partial_sum(i_array, i_array + 4, o_array, std::multiplies<long>{});

Ejemplo

#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 << "Los primeros " << v.size() << " números pares son: ";
    // escribir el resultado al flujo cout
    std::partial_sum(v.cbegin(), v.cend(), 
                     std::ostream_iterator<int>(std::cout, " "));
    std::cout << '\n';
    // escribir el resultado de vuelta al vector v
    std::partial_sum(v.cbegin(), v.cend(),
                     v.begin(), std::multiplies<int>());
    std::cout << "Las primeras " << v.size() << " potencias de 2 son: ";
    for (int n : v)
        std::cout << n << ' ';
    std::cout << '\n';
}

Los primeros 10 números pares son: 2 4 6 8 10 12 14 16 18 20 
Las primeras 10 potencias de 2 son: 2 4 8 16 32 64 128 256 512 1024

Informes de defectos

Los siguientes informes de defectos que modifican el comportamiento se aplicaron retroactivamente a los estándares de C++ publicados anteriormente.

Véase también