条款37：用accumulate或for_each来统计区间

条款37：用accumulate或for_each来统计区间

有时候你需要把整个区间提炼成一个单独的数，或，更一般地，一个单独的对象。对于一般需要的信息，有特殊目的的算法来完成这个任务，比如，count告诉你区间中有多少等于某个值的元素，而count_if告诉你有多少元素满足一个判断式。区间中的最小和最大值可以通过min_element和max_element获得。

但有时，你需要用一些自定义的方式统计（summarize）区间，而且在那些情况中，你需要比count、count_if、min_element或max_element更灵活的东西。比如，你可能想要对一个容器中的字符串长度求和。你可能想要数的区间的乘积。你可能想要point区间的平均坐标。在那些情况中，你需要统计一个区间，但你需要有定义你需要统计的东西的能力。没问题。STL为你准备了那样的算法，它叫作accumulate。你可能不熟悉accumulate，因为，不像大部分算法，它不存在于<algorithm>。取而代之的是，它和其他三个“数值算法”都在<numeric>中。（那三个其它的算法是inner_product、adjacent_difference和partial_sum。）

就像很多算法，accumulate存在两种形式。带有一对迭代器和初始值的形式可以返回初始值加由迭代器划分出的区间中值的和：

list<double> ld;						// 建立一个list，放
...							// 一些double进去
double sum = accumulate(ld.begin(), Id.end(), 0.0);		// 计算它们的和，
							// 从0.0开始

在本例中，注意初始值指定为0.0，不是简单的0。这很重要。0.0的类型是double，所以accumulate内部使用了一个double类型的变量来存储计算的和。如果这么写这个调用：

double sum = accumulate(ld.begin(), Id.end(), 0);		// 计算它们的和，
							// 从0开始；
							// 这不正确！

如果初始值是int 0，所以accumulate内部就会使用一个int来保存它计算的值。那个int最后变成accumulate的返回值，而且它用来初始化和变量。这代码可以编译和运行，但和的值可能不对。不是保存真的double的list的和，它可能保存了所有的double加起来的结果，但每次加法后把结果转换为一个int。

accumulate只需要输入迭代器，所以你甚至可以使用istream_iterator和istreambuf_iterator（参见条款29）：

cout << "The sum of the ints on the standard input is"		// 打印cin中
		<< accumulate(istream_iterator<int>(cin),	// 那些int的和
				istream_iterator<int>(),
				0);

进行数值算法是accumulate的默认行为。但当使用accumulate的另一种形式，带有一个初始和值与一个任意的统计函数，这变得一般很多。

比如，考虑怎么使用accumulate来计算容器中的字符串的长度和。要计算这个和，accumulate需要知道两个东西。第一，同上，它必须知道和的开始。在我们的例子中，它是0。第二，它必须知道每次看到一个新的字符串时怎么更新这个和。要完成这个任务，我们写一个函数，它带有目前的和与新的字符串，而且返回更新的和：

string::size_type					// string::size_type的内容
stringLengthSum(string::size_type sumSoFar,		// 请看下文
			const string& s)
{
	return sumSoFar + s.size();
}

这个函数的函数体非常简单，但你可能发现自己陷于string::size_type的出现。不要那样。每个标准STL容器都有一个typedef叫做size_type，那是容器计量东西的类型。比如，这是容器的size函数的返回类型。对于所有的标准容器，size_type必须是size_t，但理论上非标准STL兼容的容器可能让size_type使用一个不同的类型（虽然我花了很多时间来想为什么它们要那么做）。对于标准容器，你可以把Container::size_type看作size_t写法的一个奇异方式。

stringLengthSum是accmulate使用的统计函数的代表。它带有到目前为止区间的统计值和区间的下一个元素，它返回新的统计值。一般来说，那意味着函数会带不同类型的参数。那就是这里所做的。到目前为止的统计值（已经看到的字符串的长度和）是string::size_type类型，而要检查的元素的类型是string。典型地在这个例子中，这里的返回类型和函数的第一个参数相同，因为它是更新了的统计值（加上了最后计算的元素）。

我们可以让accumulate这么使用stringLengthSum：

set<string> ss;					// 建立字符串的容器，
...						// 进行一些操作
string::size_type lengthSum =			// 把lengthSum设为对
	accumulate(ss.begin(), ss.end(),		// ss中的每个元素调用
			0, stringLengthSum);	// stringLengthSum的结果，使用0
						// 作为初始统计值

很好，不是吗？计算数值区间的积甚至更简单，因为我们不用写自己的求和函数。我们可以使用标准multiplies仿函数类：

vector<float> vf;					// 建立float的容器
...						// 进行一些操作
float product =					// 把product设为对vf
	accumulate(vf.begin(), vf.end(),		// 中的每个元素调用
			1.0f, multiplies<float>());	// multiplies<float>的结果，用1.0f
						// 作为初始统计值

这里唯一需要小心的东西是记得把1（作为float，不是int！）作为初始统计值，而不是0。如果我们使用0作为开始值，结果会总是0，因为0乘以任何东西也是0，不是吗？

我们的最后一个例子有一些晦涩。它完成寻找point的区间的平均值，point看起来像这样：

struct Point {
	Point(double initX, double initY): x(initX), y(initY) {}
	double x, y;
};

求和函数应该是一个叫做PointAverage的仿函数类的对象，但在我们察看PointAverage之前，让我们看看它在调用accumulate中的使用方法：

list<Point> lp;
...
Point avg =					// 对Ip中的point求平均值
	accumulate(lp.begin(), lp.end(),
			Point(0, 0), PointAverage());

简单而直接，我们最喜欢的方式。在这个例子中，初始和值是在原点的point对象，我们需要记得的是当计算区间的平均值时不要考虑那个点。

PointAverage通过记录它看到的point的个数和它们x和y部分的和的来工作。每次调用时，它更新那些值并返回目前检查过的point的平均坐标，因为它对于区间中的每个点只调用一次，它把x与y的和除以区间中的point的个数，忽略传给accumulate的初始point值，它就应该是这样：

class PointAverage:
		public binary_function<Point, Point, Point> {		// 参见条款40
public:
	PointAverage(): numPoints(0), xSum(0), ySum(0) {}
	const Point operator()(const Point& avgSoFar, const Point& p) {
		++numPoints;
		xSum += p.x;
		ySum += p.y;
		return Point(xSum/numPoints, ySum/numPoints);
	}

private:
	size_t numPoints;
	double xSum;
	double ySum;
};

这工作得很好，而且仅因为我有时候和一些非常狂热的人打交道（他们中的很多都在标准委员会），所以我才会预见到它可能失败的STL实现。不过，PointAverage和标准的第26.4.1节第2段冲突，我知道你想起来了，那就是禁止传给accumulate的函数中有副作用。成员变量numPoints、xSum和ySum的修改造成了一个副作用，所以，技术上讲，我刚展示的代码会导致结果未定义。实际上，很难想象它无法工作，但当我这么写时我被险恶的语言律师包围着，所以我别无选择，只能在这个问题上写出难懂的条文。

那很好，因为它给我了一个机会来提起for_each，另一个可以用于统计区间而且没有accumulate那么多限制的算法。正如accumulate，for_each带有一个区间和一个函数（一般是一个函数对象）来调用区间中的每个元素，但传给for_each的函数只接收一个实参（当前的区间元素），而且当完成时for_each返回它的函数。（实际上，它返回它的函数的一个拷贝——参见条款38。）值得注意的是，传给（而且后来要返回）for_each的函数可能有副作用。

除了副作用问题，for_each和accumulate的不同主要在两个方面。首先，accumulate的名字表示它是一个产生区间统计的算法，for_each听起来好像你只是要对区间的每个元素进行一些操作，而且，当然，那是那个算法的主要应用。用for_each来统计一个区间是合法的，但是它没有accumulate清楚。

其次，accumulate直接返回那些我们想要的统计值，而for_each返回一个函数对象，我们必须从这个对象中提取想要的统计信息。在C++里，那意味着我们必须给仿函数类添加一个成员函数，让我们找回我们追求的统计信息。

这又是最后一个例子，这次使用for_each而不是accumulate：

struct Point {...);					// 同上
class PointAverage:
		public unary_function<Point, void> {		// 参见条款40
public:
	PointAverage(): xSum(0), ySum(0), numPoints(0) {}
	void operator()(const Point& p)
	{
		++numPoints;
		xSum += p.x;
		ySum += p.y;
	}
	Point result() const
	{
		return Point(xSum/numPoints, ySum/numPoints);
	}

private:
	size_t numPoints;
	double xSum;
	double ySum;
};

list<Point> Ip;
...
Point avg = for_each(lp.begin(), lp.end(), PointAverage()).result;

就个人来说，我更喜欢用accumulate来统计，因为我认为它最清楚地表达了正在做什么，但是for_each也可以，而且不像accumulate，副作用的问题并不跟随for_each。两个算法都能用来统计区间。使用最适合你的那个。

你可能想知道为什么for_each的函数参数允许有副作用，而accumulate不允许。这是一个刺向STL心脏的探针问题。唉，尊敬的读者，有一些秘密总是在我们的知识范围之外。为什么accumulate和for_each之间有差别？我尚待听到一个令人信服的解释。