《Effective STL》

haoji

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返回一个函数对象，我们必须从这个对象中提

haoji

取想要的统计信息。在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之间有差别？
我尚待听到一个令人信服的解释。

haoji

Center of STL Study
——最优秀的STL学习网站
仿函数、仿函数类、函数等
无论喜欢或不喜欢，函数和类似函数的对象——仿函数——遍布STL。关联容器使用它们来使元素保持有
序；find_if这样的算法使用它们来控制它们的行为；如果缺少它们，那么比如for_each和transform这样的组件
就没有意义了；比如not1和bind2nd这样的适配器会积极地产生它们。
是的，在你看到的STL中的每个地方，你都可以看见仿函数和仿函数类。包括你的源代码中。如果不知道怎
么写行为良好的仿函数就不可能有效地使用STL。由于这样的情况，本章的大部分专注于解释怎么使你的仿
函数行为和STL期望的方式一样。但有一个条款，专注于不同的主题，那个条款肯定会受到因需要用
ptr_fun、mem_fun和mem_fun_ref弄乱他们的代码而感到惊讶的人的关注。如果你喜欢，你可以从那个条款
（条款41）开始，但请别以它为终止。一旦你了解了那些函数，你会需要剩下条款的信息来确认你的仿函数
完全地配合它们和STL的其他部分。

haoji

Center of STL Study
——最优秀的STL学习网站
条款38：把仿函数类设计为用于值传递
C和C++都不允许你真的把函数作为参数传递给其他函数。取而代之的是，你必须传指针给函数。比如，这
里有一个标准库函数qsort的声明：
void qsort(void *base, size_t nmemb, size_t size,
int (*cmpfcn)(const void*, const void*));
条款46解释了为什么sort算法一般来说是比qsort函数更好的选择，但在这里那不是问题。问题是qsort声明的参
数cmpfcn。一旦你忽略了所有的星号，就可以清楚地看出作为cmpfcn传递的实参，一个指向函数的指针，是
从调用端拷贝（也就是，值传递）给qsort。这是C和C++标准库都遵循的一般准则，也就是，函数指针是值
传递。
STL函数对象在函数指针之后成型，所以STL中的习惯是当传给函数和从函数返回时函数对象也是值传递的
（也就是拷贝）。最好的证据是标准的for_each声明，这个算法通过值传递获取和返回函数对象：
template<class InputIterator,
class Function>
Function // 注意值返回
for_each(InputIterator first,
InputIterator last,
Function f); // 注意值传递
实际上，值传递的情况并不是完全打不破的，因为for_each的调用者在调用点可以显式指定参数类型。比
如，下面的代码可以使for_each通过引用传递和返回它的仿函数：
class DoSomething:
public unary_function<int, void> { // 条款40解释了这个基类
public:
void operator()(int x) {...}
...
};

haoji

typedef deque<int>::iterator DequeIntIter; // 方便的typedef
deque<int> di;
...
DoSomething d; // 建立一个函数对象
...
for_each<DequeIntIter, // 调用for_each，参数
DoSomething&>(di.begin(), // 类型是DequeIntIter
di.end(), // 和DoSomething&；
d); // 这迫使d按引用
// 传递和返回
但是STL的用户不能做这样的事，如果函数对象是引用传递，有些STL算法的实现甚至不能编译。在本条款的
剩余部分，我会继续假设函数对象总是值传递。实际上，这事实上总是真的。
因为函数对象以值传递和返回，你的任务就是确保当那么传递（也就是拷贝）时你的函数对象行为良好。这
暗示了两个东西。第一，你的函数对象应该很小。否则它们的拷贝会很昂贵。第二，你的函数对象必须单态
（也就是，非多态）——它们不能用虚函数。那是因为派生类对象以值传递代入基类类型的参数会造成切割
问题：在拷贝时，它们的派生部分被删除。（切割问题怎么影响你使用STL的另一个例子参见条款3。）
当然效率很重要，避免切割问题也是，但不是所有的仿函数都是小的、单态的。函数对象比真的函数优越的
的原因之一是仿函数可以包含你需要的所有状态。有些函数对象自然会很重，保持传这样的仿函数给STL算
法和传它们的函数版本一样容易是很重要的。
禁止多态仿函数是不切实际的。C++支持继承层次和动态绑定，这些特性在设计仿函数类和其他东西的时候
一样有用。仿函数类如果缺少继承就像C++缺少“++”。的确有办法让大的和/或多态的函数对象仍然允许
它们把以值传递仿函数的方式遍布STL。
这就是了。带着你要放进你的仿函数类的数据和/或多态，把它们移到另一个类中。然后给你的仿函数一个指
向这个新类的指针。比如，如果你想要建立一个包含很多数据的多态仿函数类。
template<typename T>
class BPFC: // BPFC = “Big Polymorphic
public // Functor Class”
unary_function<T, void> { // 条款40解释了这个基类
private:
Widget w; // 这个类有很多数据，
Int x; // 所以用值传递

haoji

... // 会影响效率
public:
virtual void operator()(const T& val) const; // 这是一个虚函数，
... // 所以切割时会出问题
};
建立一个包含一个指向实现类的指针的小而单态的类，然后把所有数据和虚函数放到实现类：
template<typename T> // 用于修改的BPFC
class BPFCImpl
public unary_function<T, void> { // 的新实现类
private:
Widget w; // 以前在BPFC里的所有数据
int x; // 现在在这里
...
virtual ~BPFCImpl(); // 多态类需要
// 虚析构函数
virtual void operator()(const T& val) const;
friend class BPFC<T>; // 让BPFC可以访问这些数据
};
template<typename T>
class BPFC: // 小的，单态版的BPFC
public unary_function<T, void> {
private:
BPFCImpl<T> *pImpl; // 这是BPFC唯一的数据
public:
void operator()(const T& val) const // 现在非虚；
{ // 调用BPFCImpl的
pImpl->operator() (val);
}
...
};
BPFC:perator()的实现例证了BPFC所有的虚函数是怎么实现的：它们调用了在BPFCImpl中它们真的虚函
数。结果是仿函数类（BPFC）是小而单态的，但可以访问大量状态而且行为多态。

haoji

我在这里忽略了很多细节，因为我勾勒出的基本技术在C++圈子中已经广为人知了。《Effective C++》的条款
34中有。在Gamma等的《设计模式》[6]中，这叫做“Bridge模式”。Sutter在他的《Exceptional C++》[8]中叫
它“Pimpl惯用法”.
从STL的视角看来，要记住的最重要的东西是使用这种技术的仿函数类必须支持合理方式的拷贝。如果你是
上面BPFC的作者，你就必须保证它的拷贝构造函数对指向的BPFCImpl对象做了合理的事情。也许最简单的
合理的东西是引用计数，使用类似Boost的shared_ptr，你可以在条款50中了解它.
实际上，对于本条款的目的，唯一你必须担心的是BPFC的拷贝构造函数的行为，因为当在STL中被传递或从
一个函数返回时，函数对象总是被拷贝——值传递，记得吗？那意味着两件事。让它们小，而且让它们单
态。

haoji

Center of STL Study
——最优秀的STL学习网站
条款39：用纯函数做判断式
我讨厌为你做这些，但我们必须从一个简短的词汇课开始：
● 判断式是返回bool（或者其他可以隐式转化为bool的东西）。判断式在STL中广泛使用。标准关联容器
的比较函数是判断式，判断式函数常常作为参数传递给算法，比如find_if和多种排序算法。（排序算
法的概览可以在条款31找到。）
● 纯函数是返回值只依赖于参数的函数。如果f是一个纯函数，x和y是对象，f(x, y)的返回值仅当x或y的
值改变的时候才会改变。
在C++中，由纯函数引用的所有数据不是作为参数传进的就是在函数生存期内是常量。（一般，这样
的常量应该声明为const。）如果一个纯函数引用的数据在不同次调用中可能改变，在不同的时候用同
样的参数调用这个函数可能导致不同的结果，那就与纯函数的定义相反。
现在已经很清楚用纯函数作判断式是什么意思了。我要做的所有事情就是使你相信我的建议是有根据的。要
帮我完成这件事，我希望你能原谅我再增加一个术语所给你带来的负担。
● 一个判断式类是一个仿函数类，它的operator()函数是一个判断式，也就是，它的operator()返回true或
false（或其他可以隐式转换到true或false的东西）。正如你可以预料到的，任何STL想要一个判断式的
地方，它都会接受一个真的判断式或一个判断式类对象。
就这些了，我保证！现在我们已经准备好学习为什么这个条款提供了有遵循价值的指引。
条款38解释了函数对象是传值，所以你应该设计可以拷贝的函数对象。用于判断式的函数对象，有另一个理
由设计当它们拷贝时行为良好。算法可能拷贝仿函数，在使用前暂时保存它们，而且有些算法实现利用了这
个自由。这个论点的一个重要结果是判断式函数必须是纯函数。
想知道这是为什么，先让我们假设你想要违反这个约束。考虑下面（坏的实现）的判断式类。不管传递的是
什么实参，它严格地只返回一次true：第三次被调用的时候。其他时候它返回假。
class BadPredicate: // 关于这个基类的更多信息
public unary_function<Widget, bool> { // 请参见条款40
public:
BadPredicate(): timesCalled(0) {} // 把timesCalled初始化为0
bool operator()(const Widget&)

haoji

{
return ++timesCalled == 3;
}
private:
size_t timesCalled;
};
假设我们用这个类来从一个vector<Widget>中除去第三个Widget：
vector<Widget> vw; // 建立vector，然后
// 放一些Widgets进去
vw.erase(remove_if(vw.begin(), // 去掉第三个Widget;
vw.end(), // 关于erase和remove_if的关系
BadPredicate()), // 请参见条款32
vw.end());
这段代码看起来很合理，但对于很多STL实现，它不仅会从vw中除去第三个元素，它也会除去第六个！
要知道这是怎么发生的，就该看看remove_if一般是怎么实现的。记住remove_if不是一定要这么实现：
template <typename FwdIterator, typename Predicate>
FwdIterator remove_if(FwdIterator begin, FwdIterator end, Predicate p)
{
begin = find_if(begin, end, p);
if (begin == end) return begin;
else {
FwdIterator next = begin;
return remove_copy_if(++next, end. begin, p);
}
}
这段代码的细节不重要，但注意判断式p先传给find_if，后传给remove_copy_if。当然，在两种情况中，p是传
值——是拷贝——到那些算法中的。（技术上说，这不需要是真的，但实际上，是真的。详细资料请参考条
款38。）

haoji

最初调用remove_if（用户代码中要从vw中除去第三个元素的那次调用）建立一个匿名BadPredicate对象，它把
内部的timesCalled成员清零。这个对象（在remove_if内部叫做p）然后被拷贝到find_if，所以find_if也接收了一
个timesCalled等于0的BadPredicate对象。find_if“调用”那个对象直到它返回true，所以调用了三次，find_if然
后返回控制权到remove_if。remove_if继续运行后面的调用remove_copy_if，传p的另一个拷贝作为一个判断
式。但p的timesCalled成员仍然是0！find_if没有调用p，它调用的只是p的拷贝。结果，第三次remove_copy_if
调用它的判断式，它也将会返回true。这就是为什么remove_if最终会从vw中删除两个Widgets而不是一个。
最简单的使你自己不摔跟头而进入语言陷阱的方法是在判断式类中把你的operator()函数声明为const。如果你
这么做了，你的编译器不会让你改变任何类数据成员。
class BadPredicate:
public unary_function<Widget, bool> {
public:
bool operator()(const Widget&) const
{
return ++timesCalled == 3; // 错误！在const成员函数中
} // 不能改变局部数据
};
因为这是避免我们刚测试过的问题的一个直截了当的方法，我几乎可以把本条款的题目改为“在判断式类中
使operator()成为const”。但那走得不够远。甚至const成员函数可以访问multable数据成员、非const局部静态
对象、非const类静态对象、名字空间域的非const对象和非const全局对象。一个设计良好的判断式类也保证它
的operator()函数独立于任何那类对象。在判断式类中把operator()声明为const对于正确的行为来说是必要的，
但不够充分。一个行为良好的operator()当然是const，但不只如此。它也得是一个纯函数。
本条款的前面，我强调了任何STL想要一个判断式的地方，它都会接受一个真的判断式或一个判断式类对
象。它在两个方向上都是对的。在STL任何可以接受一个判断式类对象的地方，一个判断式函数（可能由
ptr_fun改变——参见条款41）也是受欢迎的。你现在明白判断式类中的operator()函数应该是纯函数，所以这
个限制也扩展到判断式函数。作为一个判断式，这个函数和从BadPredicate类产生的对象一样糟：
bool anotherBadPredicate(const Widget&, const Widget&)
{
static int timesCalled = 0; // 不！不！不！不！不！不！不！
return ++timesCalled == 3; // 判断式应该是纯函数，
} // 纯函数没有状态
不管你怎么写你的判断式，它们都应该是纯函数。