了解std :: accumulate

Question

我想知道为什么std::accumulate(aka 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;

还有可选的第4个参数,允许用任何其他操作替换添加.

我听过的理由是,如果你需要说不加,而是乘以向量的元素,我们需要其他(非零)初始值:

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

你做出了一个错误的假设:那种类型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);
}

所以在这个例子中,我们int在一组Employee对象上积累一个值.在这里,累积和不是我们实际总结的变量类型.

示例#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 2

事情的方式,对于确保范围不是空的并且想要从范围的第一个元素开始累积的代码来说,这很烦人.根据用于累积的操作,使用的"零"值并不总是很明显.

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

一个观点是两个世界中最好的当然是提供两种功能.例如,Haskell提供了两个foldl1和foldr1(它们需要非空列表)foldl和foldr(镜像std::transform).

另一个观点是,由于一个可以通过一个简单的转换实现另一个(正如你已经证明的那样:std::transform(std::next(b), e, *b, f)- std::next是C++ 11,但重点仍然存在),最好将接口设置为最小的它可以没有真正失去表现力.