std::accumulate算法知识：一个看似简单实则无所不能的算法

关于std::accumulate算法的知识

• 一、简介
• 二、基本用法
• • 2.1、数值类型
  • 2.2、其他类型
  • 三、合理利用 std::accumulate
  • 四、std::accumulate 的进一步使用
  • 五、总结

    一、简介

    如果有一个算法可以做各种各样的事情，那一定是std::accumulate。重要的是要知道怎么使用它，以及什么时候不使用它。

    关于std::accumulate首先要知道的是它的头文件是，不像其他算法的头文件在。

    std::accumulate用于汇总一个范围。即std::accumulate接受一个元素集合，并且只返回一个值。它可以用于实现各种算法,但同时也要谨慎使用,否则会造成代码难以理解。

    二、基本用法

    2.1、数值类型

    如果不指定任何内容，则std::accumulate对其所取范围内的所有元素求和。这个和是用operator+完成的。由于需要两个值来调用operator+，因此还需要一个初始值来启动算法。

    函数原型：

    templateT accumulate(InputIterator first, InputIterator last, T initialValue);
    

    因此，对于一个数字集合，std::accumulate将它们相加：

    std::vector numbers = { 2, 9, -4, 2 };
    int sum = std::accumulate(begin(numbers), end(numbers), 0);
    

    这里有个小陷阱。上面的代码适用于整型，但看看这段非整型的代码：

    std::vector doubles = { 1.5, 2, 3.5 };
    double sum = std::accumulate(begin(doubles), end(doubles), 0);
    

    结果将会输出6。我们期望的是1.5 + 2 + 3.5 = 7，而不是6。要理解发生了什么，再看一下std::accumulate的原型：

    templateT accumulate(InputIterator first, InputIterator last, T initialValue);
    

    注意，类型T不一定与范围内元素的类型相关。在调用时，它是从第三个参数0推导出来的。而0是一个整型！所以T是int。因此，std::accumulate与int一起工作，并截断每个求和的结果。

    一个简单的修复方法是第三个参数传递一个double类型：

    std::vector doubles = { 1.5, 2, 3.5 };
    double sum = std::accumulate(begin(doubles), end(doubles), 0.);
    

    这时的结果才是7。这个例子值得关注，因为在这个例子中，代码编译和失败都是通过的。

    2.2、其他类型

    除了数字类型，没有什么可以阻止std::accumulate在其他类型上使用。任何实现operator+的类型都可以选择std::accumulate。

    在std::string上，使用operator+执行串联操作：

    std::vector words = { "Winter ", "is ", "Coming." };
    std::string sentence = std::accumulate(begin(words), end(words), std::string(""));
    

    这里需要注意，需要传递std::string("")而不仅仅是""作为初始值，因为后者导致T是const char*而不是std::string，并且无法编译。

    另外，即使范围内元素的类型没有实现operator+，它仍然可以使用std::accumulate和它的第二个重载，该重载接受一个函数(或函数对象)来代替operator+。这个函数的两个参数甚至可以是不同的类型。

    举例：有一个可以载几个人的电梯，目前他们的总重量小于一定的限制。下面的代码计算电梯中人群的总重量：

    double totalWeight = std::accumulate(begin(group), end(group), 0.,
                        [](double currentWeight, Person const& person) { return currentWeight + person.getWeight();
                        });
    

    看看算法的最后一个参数。它代表一个函数（这里是一个 lambda 表达式），该函数接受一个初始值（这里为 0.）和一个要“吸收”到当前值中的新元素。算法在“吸收”或“累积”了整个范围中的所有元素之后返回当前值。

    三、合理利用 std::accumulate

    这种过度设计提供了很多可能性。但是其中一些应该避免，因为它们会导致难以理解的代码，甚至在某些情况下需要用很大精力来解开。

    原则：std::accumulate将一个范围的总结模型化为一个值。但要注意的是，它不模拟函数应用。

    引用前面的例子，想要计算电梯中每个人的体重可以使用std::accumulate以以下方式实现：

    std::accumulate(begin(group), end(group), &weights,
                    [](std::vector* currentWeights, Person const& person) { currentWeights->push_back(person.getWeight());
                        return currentWeights;
                    });
    

    但这是错误的。记住，这是很容易犯的错误，不要这样实现代码。为什么是错的？因为这段代码遍历一个范围，对每个元素应用一个函数，并将结果放入一个新的集合中。这是std::transform在代码中要表达的内容。

    相反，这段代码使用std::accumulate来将一个范围汇总为一个值，并扭曲了它的用法。其结果是，大量的代码并不能说明什么，而且还告诉它是错误的。换句话说，它扼杀了代码的表现力。

    为了让代码更有表现力，应该使用std::transform：

    std::transform(begin(group), end(group), std::back_inserter(weights),
                   [](Person const& person){ return person.getWeight();});
    

    什么时候不应该使用std::accumulate？当std::accumulate的返回值被丢弃时，表明该工具不适合使用。

    四、std::accumulate 的进一步使用

    使用std::accumulate()可以实现STL中的几乎所有算法！此外，accumulate还可以用来实现与std::all_of功能等效的代码，但不会出现短路的情况。

    std::accumulate(std::begin(booleans), std::end(booleans), true, std::logical_and<>())
    

    还有更多。慢慢摸索…

    五、总结

    std::accumulate()是一把有力的算法函数，但使用时需要明确它的原理和适用场景。它擅长于将一个范围汇总为单一值，但不擅长于对每个元素进行函数应用并收集结果。使用时要时刻谨记这一原则，以确保代码清晰易懂，体现算法的本意。