39.判断式必须为纯函数

Posted on | In

基础概念

 
在开始本节内容之前，有基础概念如下：

  • 判断式是返回bool或者返回值可以隐式转化为bool的东西.举例而言，默认谓词即为判断式.
  • 纯函数是返回值只依赖参数的函数，参数不改变则返回值不变（不具备状态），纯函数中所有的数据只有两种：参数、常量。
  • 一个判断式类是一个仿函数类，它的成员函数operator()返回0或者1，STL算法可以接受一个真正的判断式或一个判断式对象作为谓词。

为什么判断式必须为纯函数

 
前文说过，函数对象在STL算法中pass-by-value。判断式作为一个函数对象，存在另一个设计特性：STL可能会先拷贝它们，然后在需要的时候使用它们的拷贝。这个设计特性的直接反映就是：判别式函数必须是纯函数。

问题实例

下述的判断式类功能为：仅在第三次调用时返回true.

1
2
3
4
5
6
7
8
9
class BadPredicate:public unary_function<Widget, bool> {
public:
    BadPredicate(): timesCalled(0) {}
    bool operator()(const Widget&){
        return ++timesCalled == 3;
    }
private:
    size_t timesCalled;
};

看起来似乎没毛病。于是我们用它来作为谓词抹除容器内的第三个元素：
1
2
vector<Widget> vw;
vw.erase(remove_if(vw.begin(),vw.end(),BadPredicate()), vw.end());

事实上调用完成后不仅仅会抹除第三个元素，第六个元素也会被抹除。

问题剖析

上述问题的产生原因在于remove_if的实现：

1
2
3
4
5
6
7
8
9
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的copy先被传递给find_if，再被传递给remove_copy_if.
首先，我们构造了一个匿名判断类对象，并用它初始化了判断类对象p,然后p被拷贝到findif中（time被初始化为0），然后调用了3次以后，p的拷贝的time增长为3，返回true.控制权回归remove_if，然后remove_copy_if拷贝了p，此时time为0，（而不是3），因此到第六个元素的时候又触发了true。

解决方案

最简单的方法是把operator()函数声明为const，如此一来，你的编译器不会通过任何改变任何数据成员的指令。
但这是不够的，因为const成员函数还是能改变mutable成员，非const局部静态对象，非const类静态对象、命名空间中的非const对象，以及非const的全局对象。
总的来说，一个行为正常的判断类operator()必然是const的，但还有更严格的要求：必须是纯函数。