在处理大量整数数据时，重复的加法和其他操作可能导致整数溢出。当这个问题出现时，即使是简单的算法也可能难以实现。通常的解决方案是使用更高精度的数据类型进行中间值的计算，比如long long或double。本文提供了一种替代算法，用于在需要精确计算的前提下计算大量整数值的平均值，因此使用double进行中间值计算不是一个选项。这种算法的灵感来自于一个在CodeProject上提出的问题：
用户k5054在提到的帖子中发布的一个链接指向了累积移动平均方法：
这种方法提供了一种计算一系列数字平均值的替代方式。虽然该方法并不关心整数溢出的问题，但它提供了一种增量确定系列一部分平均值的方法，从而避免了需要一个持有相当大值的中间值，这个值可能会受到溢出的影响。
该算法逐步计算所有值x_i的累积移动平均值（CMA）直到某一点。为了避免每次迭代都需要重新访问之前的值，计算使用了基于之前平均值的替代公式：
CMA_{n+1} = CMA_n + (x_{n+1} - CMA_n) / (n+1)
在这个等式中，所有值和中间结果都与原始值的量级相同。能得到的最大的中间值是最大值和最小输入值之间的差：例如，如果这两个值分别存储在x_1和x_2中，那么上述公式将在第二次迭代时计算差值x_2 - x_1。
这个公式假设了精确计算：如果第二个求和项的除法是整数除法，一些分数会被截断，这些分数加起来可能会成为一个显著的数量。因此，需要跟踪除法的累积余数（CMR）：
CMA_{n+1} = CMA_n + (x_{n+1} - CMA_n + CMR_n) div (n+1)
CMR_{n+1} = (x_{n+1} - CMA_n + CMR_n) mod (n+1)
这里最大的中间值是两个公式中使用的除数(x_{n+1} - CMA_n + CMR_n)。减法最多能提供x_i的最小值和最大值之间的差，CMR可以是-n到n之间的任何值（如果除数是负数，余数可以是负的）。因此，只要输入值的范围不会覆盖整数类型的大部分整数范围，或者元素数量接近所使用的整数类型的最大整数值，就不会发生溢出。
代码使用了C++11特性decltype和std::remove_reference。在VS2010中实现并测试了它。注意，故意没有使用n_values的大小类型，尽管它不能是负数。原因是对于混合有符号/无符号参数，除法和模运算符不总是提供预期的结果。此外，为了避免溢出，n_values必须在基本类型的范围内。
#include <utility>
template<class container_iterator>
auto average(const container_iterator start, container_iterator end)
->typename std::remove_reference<decltype(*start)>::type
{
typedef std::remove_reference<decltype(*start)>::type basetype;
basetype cumulated_average = 0;
basetype cumulated_remainder = 0;
basetype addendum = 0;
basetype n_values = 0;
for(auto pvalue = start; pvalue != end; ++pvalue) {
++n_values;
addendum = *pvalue - cumulated_average + cumulated_remainder;
cumulated_average += addendum / n_values;
cumulated_remainder = addendum % n_values;
}
return cumulated_average;
}
代码提供了一个函数，可以像STL库中的许多算法一样使用。它接受两个参数，定义了容器中的值范围。该函数将自动从这些参数中派生容器内值的类型。如果编译器不支持C++11特性decltype和std::remove_reference，可以将值类型作为模板参数列表的参数添加。
可以通过简单地传递两个迭代器或指针来调用这个函数，这些迭代器或指针指向想要计算平均值的容器的第一个和最后一个元素。下面是一个示例：
void test_average() {
char cvalues[] = {13, 7, -27, 34, -3, 22, 33, -1, 18, 29, 13, 7, -27, 34, -3, 22, 33, -1, 18, 29, 13, 7, -27, 34, -3, 22, 33, -1, 18, 29, 13, 7, -27, 34, -3, 22, 33, -1, 18, 29, 13, 7, -27, 34, -3, 22, 33, -1, 18, 29};
auto cavg = average(cvalues, cvalues+50);
}
在调试这个示例时，发现值的范围是：cvalues: -27到+34 cumulated_remainder: -28到+25 cumulated_average: -2到+13 所有值都在预测的范围内。这只是一个测试用例，但原始代码确实包含更多的调试代码，以帮助确保cumulated_average和cumulated_remainder的值始终准确。
这是第一次实际使用decltype，而且在试图弄清楚如何正确使用它时，第一次听说std::remove_reference。这些新的语言特性非常有用，如果还没有阅读过它们，非常值得一读。在这个例子中，使用它们节省了一个模板参数。但更重要的是，它节省了调用者提供它的努力，也节省了验证传递给函数的迭代器实际上指向完全相同类型的值的努力。