一个有趣的判断式问题

Posted on | In

前言

看effective stl看到一个很有趣的问题,说的是传递判断式不要传递有副作用的表达式,而要用纯函数做判断式,这里简单来回味一下,因为自己很智障的琢磨了好一会.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>
using namespace std;
template <typename ForwardIterator, typename UnaryPredicate>
ForwardIterator remove_if_my(ForwardIterator first, ForwardIterator last,
                             UnaryPredicate pred) {
  ForwardIterator result = first;
  while (first != last) {
    if (!(pred(*first))) {
      *result = *first;
      ++result;
    }
    ++first;
  }
  return result;
}
template <typename ForwardIterator, typename UnaryPredicate>
ForwardIterator remove_if_my2(ForwardIterator first, ForwardIterator last,
                              UnaryPredicate pred) {
  first = find_if(first, last, pred);
  if (first == last)
    return first;
  else {
    ForwardIterator next = first;
    return remove_copy_if(++next, last, first, pred);
  }
}
template <typename T> class BadPredicate : public unary_function<T, bool> {
public:
  BadPredicate() : timeCalled(0) {}
  bool operator()(const T &) { return ++timeCalled == 3; }

private:
  size_t timeCalled;
};
int main() {
  vector<int> vt{1, 2, 3, 4, 5, 6, 7, 8, 9};
  auto vt2 = vt;
  vt.erase(remove_if_my(vt.begin(), vt.end(), BadPredicate<int>()), vt.end());
  auto print = [](const int &i) { cout << i << " "; };
  cout << "vt: ";
  for_each(vt.begin(), vt.end(), print);
  cout << endl;
  vt2.erase(remove_if_my2(vt2.begin(), vt2.end(), BadPredicate<int>()),
            vt2.end());
  cout << "vt2: ";
  for_each(vt2.begin(), vt2.end(), print);
  cout << endl;
}

代码输出

上面的输出肯定是不一样的(笑),不然我也不会写这篇博客的,下面是输出的结果.

vt: 1 2 4 5 6 7 8 9
vt2: 1 2 4 5 7 8 9

为什么会出现vt2少了两个数字的情况呢,这个问题一开始令我非常的疑惑,看了effective stl上面的解释也不是十分理解,后来发现begin指向的是3(原谅我有点晕的脑子),但是这也是个有趣的问题,为什么6也会被删掉呢,问题的关键是我们的pred是按值拷贝传给find_if和remove_copy_if的,所以实际上对于传给find_if和remove_copy_if的两个pred都是不同的对象,他们的timeCalled都是从0开始的,所以在调用remove_copy_if的时候,我们的6也会被认为是符合remove的条件的,而没有被拷贝到目标区间中去,这就是我们的问题所在.
但是对于我们第一种实现,就没有这个问题了,pred只在一个地方被使用,所以一切OK,输出也是正常的,但是从实现的角度来看,我们这个实现明显是比第二种实现低效的,我使用了c++自己实现的remove_if测试了一下,c++使用的应该也是类似于第二种实现,

解决

第一种直观的解决办法是使用const成员函数,在const成员函数中我们改变局部数据timeCalled是不合法的.但是使用const成员函数还不错,但是并不足够好,因为const成员函数可以访问mutable数据成员,非const局部静态对象,非const类静态对象,名字空间域的非const对象和非const全局对象.一个设计良好的判断式类也保证它的operator()函数独立于任何那类对象.在判断式类中把operator()声明为const对于正确的行为来说是必须的,但是不够充分.
更好的解决办法就是effective stl的条款39所主要叙述的,一个行为良好的operator()当然是const,但是不止如此,它也需要是一个纯函数.
先介绍下纯函数,纯函数是返回值只依赖于参数的函数,如果f是一个纯函数,x和y是对象,f(x,y)的返回值仅当x或y的值改变时才会改变..在c++中,由纯函数引用的所有数据不是作为参数传进的就是在函数生存期内是常量.(一般,这样的常量应该声明为const).
上面就是我们对于这种问题的解法.

总结

结语:从实现的角度来看,remove_if在上面的两个实现肯定都是合法的,但是如果我们的代码是依赖于实现的,那么它的可移植性肯定是不高的,对于我们来说,肯定也是个不好习惯,所以我们也要避免避免依赖于实现的代码.