46

我想知道为什么std::accumulate需要（又名减少）第三个参数。对于那些不知道是什么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());

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

4

5 回答 5

40

您做出了一个错误的假设：该类型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它适用于您在输入范围内迭代并在该范围内建立一个单一结果的任何时候。但是结果不需要与范围的类型相同，并且您不能对要使用的初始值做出任何假设——这就是为什么您必须有一个初始实例来用作累加结果的原因。

于 2015-02-18T19:38:39.773 回答
11

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

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

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

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

于 2012-09-28T05:24:19.050 回答
3

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

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

于 2012-09-28T05:16:53.830 回答
3

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

std::accumulate(v.begin(), v.end(), 0, [](long count, char c){
   return isalpha(c) ? count + 1 : count
});
于 2012-09-28T05:24:37.607 回答
0

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

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

于 2018-04-13T11:46:35.437 回答