理解std::accumulate

Question

我想知道为什么需要std::accumulate (也就是reduce)第三个参数。对于那些不知道accumulate是什么的人来说，它是这样使用的：

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

对accumulate的调用相当于：

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

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

我听说的基本原理是，如果你需要一个向量的元素相乘，而不是相加，我们需要其他(非零)初始值：

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

但是为什么不像Python一样-设置V.begin()的初始值，并使用从V.begin()+1开始的范围。如下所示：

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

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

Answer 1

目前的情况是，如果代码知道某个范围不是空的，并且希望从范围的第一个元素开始累加，那就很烦人了。根据用于累加的操作，要使用的“零”值并不总是很明显。

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

一种观点认为，两个领域的最佳选择当然是同时提供这两种功能。例如，Haskell除了提供foldl和foldr (镜像std::transform)之外，还提供了foldl1和foldr1 (需要非空列表)。

另一种观点是，由于一个接口可以通过简单的转换来实现另一个接口(正如您已经演示过的：std::transform(std::next(b), e, *b, f) -- std::next是C++11，但要点仍然有效)，最好使接口尽可能地最小化，而不会失去真正的表达能力。

Answer 2

您做了一个错误的假设:类型T与InputIterator的类型相同。

但std::accumulate是通用的，允许各种不同类型的创造性累加和缩减。

示例#1:跨员工累计薪资

下面是一个简单的例子:一个包含许多数据字段的Employee类。

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

你不能有意义地“积累”一组员工。这是没有意义的；它是未定义的。但是，您可以定义关于员工的累计。比方说，我们想要将所有员工的月薪相加。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);
}

因此，在这个示例中，我们在Employee对象的集合上累积了一个int值。这里，累加和不是我们实际求和的变量类型。

示例#2:累加平均值

您也可以使用accumulate进行更复杂类型的累加--可能想要将值追加到一个向量中；也许您有一些难以理解的统计数据要跨输入进行跟踪；等等。您累积的不一定只是一个数字；它可以是更复杂的东西。

例如，下面是一个使用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();
}

示例#3:累加移动平均值

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

让我们以我们已经看到的平均示例为基础。但是现在，我们想要一个可以保持运行平均值的类--也就是说，我们可以继续输入新值，并在多个调用中检查到目前为止的平均值。

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
}

在这种情况下，我们完全依赖于能够为std::accumulate设置初始值-我们需要能够从不同的起点初始化累加。

总之，在遍历输入范围并构建该范围内的单个结果时，std::accumulate非常适合。但是结果不必是与范围相同的类型，并且您不能对使用哪个初始值做任何假设--这就是为什么您必须有一个初始实例作为累加结果的原因。

Answer 3

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

整个想法是将算法与数据解耦。如果我理解正确的话，你的建议需要数据中的某种结构。