c++ - Entendiendo std:: acumular

stl accumulate

Question

Quiero saber por qué se necesita el tercer parámetro std::accumulate (también conocido como reducir). Para aquellos que no saben qué es accumulate , se usa así:

vector<int> V{1,2,3};  
int sum = accumulate(V.begin(), V.end(), 0);
// sum == 6

Llamar a accumulate es equivalente a:

sum = 0;  // 0 - value of 3rd param
for (auto x : V)  sum += x;

También hay un 4º parámetro opcional, que permite reemplazar la adición con cualquier otra operación.

La razón que he escuchado es que si necesita dejar de decir no sumar, pero multiplicar los elementos de un vector, necesitamos otro valor inicial (que no sea cero):

vector<int> V{1,2,3};
int product = accumulate(V.begin(), V.end(), 1, multiplies<int>());

Pero, ¿por qué no hacer Python? Establece el valor inicial para V.begin() , y usa el rango a partir de V.begin()+1 . Algo como esto:

int sum = accumulate(V.begin()+1, V.end(), V.begin());

Esto funcionará para cualquier op. ¿Por qué se necesita el 3er parámetro?

Answer 1

Como están las cosas, es molesto para el código que sabe con certeza que un rango no está vacío y que quiere comenzar a acumularse desde el primer elemento del rango activado. Dependiendo de la operación que se utiliza para acumular, no siempre es obvio cuál es el valor ''cero'' que se debe usar.

Por otro lado, si solo proporciona una versión que requiere rangos no vacíos, es molesto para las personas que llaman que no están seguros de que sus rangos no estén vacíos. Se les pone una carga adicional.

Una perspectiva es que lo mejor de ambos mundos es, por supuesto, proporcionar ambas funcionalidades. Como ejemplo, Haskell proporciona foldl1 y foldr1 (que requieren listas no vacías) junto con foldl y foldr (que reflejan std::transform ).

Otra perspectiva es que dado que uno puede implementarse en términos del otro con una transformación trivial (como ha demostrado: std::transform(std::next(b), e, *b, f) - std::next es C ++ 11 pero el punto sigue en pie), es preferible que la interfaz sea lo más mínima posible, sin una pérdida real de poder expresivo.

Answer 2

De hecho no es necesario. Nuestra base de código tiene sobrecargas de 2 y 3 argumentos que usan un valor T{} .

Sin embargo, std::accumulate es bastante antiguo; Viene de la STL original. Nuestra base de código tiene std::enable_if lógica std::enable_if para distinguir entre "2 iteradores y valor inicial" y "2 iteradores y operador de reducción". Eso requiere C ++ 11. Nuestro código también utiliza un tipo de retorno final ( auto accumulate(...) -> ... ) para calcular el tipo de retorno, otra característica de C ++ 11.

Answer 3

Debido a que se supone que los algoritmos de biblioteca estándar funcionan para rangos arbitrarios de iteradores (compatibles). Así que el primer argumento para accumulate no tiene que ser begin() , podría ser cualquier iterador entre begin() y uno antes de end() . También podría estar utilizando iteradores inversos.

La idea general es desacoplar los algoritmos de los datos. Su sugerencia, si la comprendo correctamente, requiere cierta estructura en los datos.

Answer 4

Está haciendo una suposición errónea: ese tipo T es del mismo tipo que el InputIterator .

Pero std::accumulate es genérico, y permite todos los tipos diferentes de acumulaciones y reducciones creativas.

Ejemplo # 1: Acumular el salario entre los empleados

Aquí hay un ejemplo simple: una clase de Employee , con muchos campos de datos.

class Employee {
/** All kinds of data: name, ID number, phone, email address... */
public:
 int monthlyPay() const;
};

No se puede "acumular" de manera significativa un conjunto de empleados. Eso no tiene sentido; es indefinido Pero, puede definir una acumulación con respecto a los empleados. Digamos que queremos resumir todo el pago mensual de todos los empleados. std::accumulate puede hacer eso:

/** Simple class defining how to add a single Employee''s
 *  monthly pay to our existing tally */
auto accumulate_func = [](int accumulator, const Employee& emp)
   return accumulator + emp.monthlyPay();
 };

// And here''s how you call the actual calculation:
int TotalMonthlyPayrollCost(const vector<Employee>& V)
{
 return std::accumulate(V.begin(), V.end(), 0, accumulate_func);
}

Entonces, en este ejemplo, estamos acumulando un valor int sobre una colección de objetos Employee . Aquí, la suma acumulada no es el mismo tipo de variable que realmente estamos sumando.

Ejemplo # 2: Acumulando un promedio

También puede usar la accumulate para tipos de acumulación más complejos, tal vez desee agregar valores a un vector; tal vez tienes una estadística arcana que estás siguiendo a través de la entrada; Lo que acumulas no tiene que ser solo un número; Puede ser algo más complejo.

Por ejemplo, aquí hay un ejemplo simple de usar accumulate para calcular el promedio de un vector de ints:

// This time our accumulator isn''t an int -- it''s a structure that lets us
// accumulate an average.
struct average_accumulate_t
{
    int sum;
    size_t n;
    double GetAverage() const { return ((double)sum)/n; }
};

// Here''s HOW we add a value to the average:
auto func_accumulate_average = 
    [](average_accumulate_t accAverage, int value) {
        return average_accumulate_t(
            {accAverage.sum+value, // value is added to the total sum
            accAverage.n+1});      // increment number of values seen
    };

double CalculateAverage(const vector<int>& V)
{
    average_accumulate_t res =
        std::accumulate(V.begin(), V.end(), average_accumulate_t({0,0}), func_accumulate_average)
    return res.GetAverage();
}

Ejemplo # 3: Acumular un promedio corriente

Otra razón por la que necesita el valor inicial es porque ese valor no siempre es el valor predeterminado / neutral para el cálculo que está realizando.

Vamos a construir sobre el ejemplo promedio que ya hemos visto. Pero ahora, queremos una clase que pueda mantener un promedio móvil , es decir, podemos seguir introduciendo nuevos valores y verificar el promedio hasta el momento , a través de múltiples llamadas.

class RunningAverage
{
    average_accumulate_t _avg;
public:
    RunningAverage():_avg({0,0}){} // initialize to empty average

    double AverageSoFar() const { return _avg.GetAverage(); }

    void AddValues(const vector<int>& v)
    {
        _avg = std::accumulate(v.begin(), v.end(), 
            _avg, // NOT the default initial {0,0}!
            func_accumulate_average);
    }

};

int main()
{
    RunningAverage r;
    r.AddValues(vector<int>({1,1,1}));
    std::cout << "Running Average: " << r.AverageSoFar() << std::endl; // 1.0
    r.AddValues(vector<int>({-1,-1,-1}));
    std::cout << "Running Average: " << r.AverageSoFar() << std::endl; // 0.0
}

Este es un caso en el que confiamos absolutamente en poder establecer ese valor inicial para std::accumulate ; necesitamos poder inicializar la acumulación desde diferentes puntos de partida.

En resumen, std::accumulate es bueno para cualquier momento en el que esté iterando sobre un rango de entrada y acumulando un único resultado en ese rango. Pero el resultado no necesita ser del mismo tipo que el rango, y no puede hacer suposiciones sobre qué valor inicial usar, por lo que debe tener una instancia inicial para usar como resultado acumulado.

Answer 5

Si quisieras accumulate(V.begin()+1, V.end(), V.begin()) simplemente podrías escribir eso. Pero, ¿qué pasa si pensaste que v.begin () podría ser v.end () (es decir, v está vacío)? ¿Qué v.begin() + 1 si v.begin() + 1 no se implementa (porque v solo implementa ++, no la adición generada)? ¿Qué pasa si el tipo de acumulador no es el tipo de los elementos? P.ej.

std::accumulate(v.begin(), v.end(), 0, [](long count, char c){
   return isalpha(c) ? count + 1 : count
});