Compreender a DST:: acumular
quero saber porque é necessário std::accumulate (aka reduce) terceiro parâmetro. Para aqueles que não sabem o que é accumulate, é usado assim:
vector<int> V{1,2,3};
int sum = accumulate(V.begin(), V.end(), 0);
// sum == 6
a chamada para {[5] } é equivalente a:
sum = 0; // 0 - value of 3rd param
for (auto x : V) sum += x;
existe também um quarto parâmetro opcional, que permite substituir a adição por qualquer outra operação.
a lógica que eu ouvi é que se você precisa dizer não para somar, mas multiplicar elementos de um vetor, precisamos de outros (não-zero) iniciais valor:
vector<int> V{1,2,3};
int product = accumulate(V.begin(), V.end(), 1, multiplies<int>());
mas porque não gostar do valor inicial do Python - set para V.begin(), e usar o intervalo a partir de V.begin()+1. Algo do género:
int sum = accumulate(V.begin()+1, V.end(), V.begin());
isto vai funcionar para qualquer operação. porque é que o terceiro parâmetro é necessário?
5 answers
Da forma como as coisas são, é irritante para o código que sabe com certeza que um intervalo não está vazio e que quer começar a acumular a partir do primeiro elemento do intervalo. Dependendo da operação que é usada para acumular, nem sempre é óbvio qual é o valor "zero" a usar.
Se por outro lado você só fornecer uma versão que requer intervalos não-vazios, é irritante para os chamadores que não sabem com certeza que seus intervalos não estão vazios. Um encargo adicional é colocado sobre o.
Uma perspectiva é que o melhor de ambos os mundos é, obviamente, fornecer ambas as funcionalidades. Como exemplo, Haskell fornece tantofoldl1 e foldr1 (que exigem listas não-vazias) ao lado de foldl e foldr (que espelham std::transform).
Uma outra perspectiva é que uma vez que uma pode ser implementada em termos da outra com uma transformação trivial (como você demonstrou: std::transform(std::next(b), e, *b, f) -- std::next é C++11 mas o ponto ainda está), é preferível fazer a interface tão mínima como pode ser sem perda real de poder expressivo.
Está a fazer uma suposição errada: esse tipo {[4] } é do mesmo tipo que o InputIterator.
Mas std::accumulate é genérico, e permite todos os tipos diferentes de acumulação criativa e reduções.
Exemplo N. º 1: acumular Salário entre os trabalhadores
Aqui está um exemplo simples: uma classe Employee, com muitos campos de dados.
class Employee {
/** All kinds of data: name, ID number, phone, email address... */
public:
int monthlyPay() const;
};
std::accumulate posso fazer isso:
/** 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);
}
int sobre uma coleção de objetos Employee. Aqui, a soma de acumulação não é o mesmo tipo de variável que estamos na verdade somando.
Exemplo # 2: acumular uma média
Você pode usar accumulate para tipos mais complexos de acumulações também-talvez quer adicionar valores a um vetor; talvez você tenha alguma estatística arcana que você está rastreando através da entrada; etc. O que você acumula não tempara ser apenas um número; pode ser algo mais complexo.
Por exemplo, aqui está um exemplo simples de usar accumulate para calcular a média de um vetor 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();
}
Exemplo # 3: acumular uma média de execução
Outra razão pela qual você precisa do valor inicial é porque esse valor não é sempre o valor padrão / neutro para o cálculo que está a fazer.
Vamos basear-nos no exemplo comum que já vimos. Mas agora, nós queremos uma classe que possa manter uma média de execução [[[25]} -- isto é, podemos continuar a alimentar-nos de novos valores, e verificar a média até agora , através de várias chamadas.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 é um caso em que confiamos absolutamente em ser capaz de definir esse valor inicial para std::accumulate - nós precisamos para ser capaz de iniciar a acumulação de diferentes partida.
Em Resumo, std::accumulateé bom para qualquer momento que você está iterando ao longo de um intervalo de entrada, e construindo um único resultado através desse intervalo. Mas o resultado não precisa ser do mesmo tipo que o intervalo, e você não pode fazer qualquer suposição sobre o valor inicial a usar -- e é por isso que você deve ter uma instância inicial para usar como o resultado acumulativo.
v.begin() + 1 não estiver implementado (porque o v só implementa ++, não generaliza a adição)? E se o tipo do acumulador não for o tipo dos elementos? Exemplo.
std::accumulate(v.begin(), v.end(), 0, [](long count, char c){
return isalpha(c) ? count + 1 : count
});
Porque algoritmos de biblioteca padrão devem funcionar para intervalos arbitrários de iteradores (compatíveis). Então o primeiro argumento para accumulate não tem que ser begin(), pode ser qualquer iterador entre begin() e um antes end(). Também pode estar a usar iteradores invertidos.
T{}.
No entanto, std::accumulate é bastante antigo; vem do STL original. A nossa base de código tem uma lógica chique std::enable_if para distinguir entre "2 iteradores e valor inicial"e" 2 iteradores e Operador de redução". Isso requer C++11. O nosso código também usa um tipo de retorno posterior (auto accumulate(...) -> ...) para calcular o tipo de retorno, outro recurso C++11.