C++ 理解 std::accumulate

Understanding std::accumulate

提问by Leonid Volnitsky

I want to know why std::accumulate(aka reduce) 3rd parameter is needed. For those who do not know what accumulateis, it's used like so:

我想知道为什么std::accumulate（又名减少）需要第三个参数。对于那些不知道是什么accumulate的人，它是这样使用的：

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

Call to accumulateis equivalent to:

调用 toaccumulate相当于：

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

There is also optional 4th parameter, which allow to replace addition with any other operation.

还有可选的第四个参数，它允许用任何其他操作替换加法。

Rationale that I've heard is that if you need let say not to add up, but multiply elements of a vector, we need other (non-zero) initial value:

我听说的基本原理是，如果您需要说不加起来，而是乘以向量的元素，我们需要其他（非零）初始值：

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

But why not do like Python - set initial value for V.begin(), and use range starting from V.begin()+1. Something like this:

但是为什么不像 Python 那样为 设置初始值V.begin()，并使用从V.begin()+1. 像这样的东西：

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

This will work for any op. Why is 3rd parameter needed at all?

这适用于任何操作。为什么需要第三个参数？

采纳答案by Luc Danton

The way things are, it is annoying for code that knows for sure a range isn't empty and that wants to start accumulating from the first element of the range on. Depending on the operation that is used to accumulate with, it's not always obvious what the 'zero' value to use is.

事情就是这样，对于确定知道范围不为空并且想要从范围的第一个元素开始累积的代码来说，这是很烦人的。根据用于累加的操作，使用的“零”值并不总是很明显。

If on the other hand you only provide a version that requires non-empty ranges, it's annoying for callers that don't know for sure that their ranges aren't empty. An additional burden is put on them.

另一方面，如果您只提供一个需要非空范围的版本，那么对于不确定他们的范围不为空的调用者来说，这很烦人。给他们带来了额外的负担。

One perspective is that the best of both worlds is of course to provide both functionality. As an example, Haskell provides both foldl1and foldr1(which require non-empty lists) alongside foldland foldr(which mirror std::transform).

一种观点是，两全其美的当然是同时提供这两种功能。例如，Haskell 提供foldl1和foldr1（需要非空列表）和foldl和foldr（镜像std::transform）。

Another perspective is that since the one can be implemented in terms of the other with a trivial transformation (as you've demonstrated: std::transform(std::next(b), e, *b, f)-- std::nextis C++11 but the point still stands), it is preferable to make the interface as minimal as it can be with no real loss of expressive power.

另一个观点是，由于一个可以通过简单的转换根据另一个来实现（正如您所证明的：std::transform(std::next(b), e, *b, f)--std::next是 C++11，但重点仍然存在），因此最好使界面尽可能小它可以在没有真正丧失表现力的情况下进行。

回答by Ziv

You're making a mistaken assumption: that type Tis of the same type as the InputIterator.

您做出了错误的假设：该类型T与InputIterator.

But std::accumulateis generic, and allows all different kinds of creative accumulations and reductions.

但是std::accumulate是通用的，并且允许所有不同种类的创造性积累和减少。

Example #1: Accumulate salary across Employees

示例 1：累计员工的工资

Here's a simple example: an Employeeclass, with many data fields.

这是一个简单的例子：一个Employee具有许多数据字段的类。

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

You can't meaningfully "accumulate" a set of employees. That makes no sense; it's undefined. But, you can define an accumulation regardingthe employees. Let's say we want to sum up allthe monthly pay of allemployees. std::accumulatecan do that:

你不能有意义地“积累”一组员工。这是没有意义的; 它是未定义的。但是，您可以定义有关员工的累积。比方说，我们要总结所有的月薪所有员工。std::accumulate可以这样做：

/** 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);
}

So in this example, we're accumulating an intvalue over a collection of Employeeobjects. Here, the accumulation sum isn'tthe same type of variable that we're actually summing over.

所以在这个例子中，我们int在一组Employee对象上累积一个值。在这里，累加和是不是同一类型的变量，我们实际上是求和。

Example #2: Accumulating an average

示例#2：累积平均值

You can use accumulatefor more complex types of accumulations as well - maybe want to append values to a vector; maybe you have some arcane statistic you're tracking across the input; etc. What you accumulate doesn't haveto be just a number; it can be something more complex.

您也可以accumulate用于更复杂类型的累积 - 也许想要将值附加到向量；也许你有一些神秘的统计数据正在跟踪输入；等你积累什么不有是只是一个数字; 它可以是更复杂的东西。

For example, here's a simple example of using accumulateto calculate the average of a vector of ints:

例如，这是一个accumulate用于计算整数向量平均值的简单示例：

// 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();
}

Example #3: Accumulate a running average

示例 #3：累积运行平均值

Another reason you need the initial value is because that value isn't alwaysthe default/neutral value for the calculation you're making.

您需要初始值的另一个原因是该值并不总是您进行计算的默认/中性值。

Let's build on the average example we've already seen. But now, we want a class that can hold a runningaverage -- that is, we can keep feeding in new values, and check the average so far, across multiple calls.

让我们以我们已经看到的平均示例为基础。但是现在，我们想要一个可以保持运行平均值的类——也就是说，我们可以不断输入新值，并检查迄今为止的平均值，跨越多次调用。

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
}

This is a case where we absolutely rely on being able to set that initial value for std::accumulate- we needto be able to initialize the accumulation from different starting points.

在这种情况下，我们绝对依赖于能够设置初始值std::accumulate——我们需要能够从不同的起点初始化累积。

---

---

In summary, std::accumulateis good for any time you're iterating over an input range, and building upone single result across that range. But the result doesn't need to be the same type as the range, and you can't make any assumptions about what initial value to use -- which is why you must have an initial instance to use as the accumulating result.

总而言之，在std::accumulate您迭代输入范围并在该范围内构建单个结果的任何时候都有好处。但是结果不需要与范围的类型相同，并且您不能对要使用的初始值做出任何假设——这就是为什么您必须有一个初始实例用作累积结果。

回答by rici

If you wanted accumulate(V.begin()+1, V.end(), V.begin())you could just write that. But what if you thought v.begin() might be v.end() (i.e. v is empty)? What if v.begin() + 1is not implemented (because v only implements ++, not generized addition)? What if the type of the accumulator is not the type of the elements? Eg.

如果你愿意，accumulate(V.begin()+1, V.end(), V.begin())你可以写那个。但是如果你认为 v.begin() 可能是 v.end() （即 v 是空的）怎么办？如果v.begin() + 1没有实现怎么办（因为 v 只实现了++，而不是泛化加法）？如果累加器的类型不是元素的类型怎么办？例如。

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

回答by juanchopanza

Because standard library algorithms are supposed to work for arbitrary ranges of (compatible) iterators. So the first argument to accumulatedoesn't have to be begin(), it could be any iterator between begin()and one before end(). It could also be using reverse iterators.

因为标准库算法应该适用于任意范围的（兼容）迭代器。因此， 的第一个参数accumulate不一定是begin()，它可以是begin()和之前之间的任何迭代器end()。它也可以使用反向迭代器。

The whole idea is to decouple algorithms from data. Your suggestion, if I understand it correctly, requires a certain structure in the data.

整个想法是将算法与数据分离。你的建议，如果我理解正确的话，需要数据中有一定的结构。

回答by MSalters

It's indeed not needed. Our codebase has 2 and 3-argument overloads which use a T{}value.

确实不需要。我们的代码库具有使用T{}值的2 和 3 参数重载。

However, std::accumulateis pretty old; it comes from the original STL. Our codebase has fancy std::enable_iflogic to distinguish between "2 iterators and initial value" and "2 iterators and reduction operator". That requires C++11. Our code also uses a trailing return type (auto accumulate(...) -> ...) to calculate the return type, another C++11 feature.

然而，std::accumulate已经很老了；它来自原始的 STL。我们的代码库有奇特的std::enable_if逻辑来区分“2 个迭代器和初始值”和“2 个迭代器和归约运算符”。这需要 C++11。我们的代码还使用尾随返回类型 ( auto accumulate(...) -> ...) 来计算返回类型，这是 C++11 的另一个特性。