CTR58-CPP. 谓词函数对象不应该是 mutable

原文链接：

CTR58-CPP. Predicate function objects should not be mutable

https://wiki.sei.cmu.edu/confluence/display/cplusplus/CTR58-CPP.+Predicate+function+objects+should+not+be+mutable

This has nothing to do with CTR as a group, and everything to do with the algorithmic requirements of the STL. However, I cannot think of a better place for this rule to live (aside from MSC, and I think CTR is an improvement). If we wind up with an STL category, this should probably go there.

C++ 标准库实现了众多接收谓词函数对象的通用算法。C++ 标准, [algorithms.general], paragraph 10 [ISO/IEC 14882-2014], 表述如下：

The C++ standard library implements numerous common algorithms that accept a predicate function object. The C++ Standard, [algorithms.general], paragraph 10 [ISO/IEC 14882-2014], states the following:

[Note: Unless otherwise specified, algorithms that take function objects as arguments are permitted to copy those function objects freely. Programmers for whom object identity is important should consider using a wrapper class that points to a noncopied implementation object such as reference_wrapper<T>, or some equivalent solution. — end note]

因为这是一个算法是否拷贝谓词函数的 implementation-defined ，所以任何这类对象必须符合以下二者之一：

实现一个不改变与函数对象标识相关的状态的函数调用操作，例如非静态数据成员或者被捕获的值
将谓词函数对象包装在一个 std::reference_wrapper<T> (或者等价方案)

标记该函数调用操作为 const 是有益的，但不是充分的，因为 mutable 存储类型标识符的数据成员可能依然会在一个 const 成员函数中被修改。

Because it is implementation-defined whether an algorithm copies a predicate function object, any such object must either

implement a function call operator that does not mutate state related to the function object’s identity, such as nonstatic data members or captured values, or
wrap the predicate function object in a std::reference_wrapper<T> (or an equivalent solution).

Marking the function call operator as const is beneficial, but insufficient, because data members with the mutable storage class specifier may still be modified within a const member function.

不合规的代码示例 (仿函数) Noncompliant Code Example (Functor)

这个不合规的代码示例试图使用一个在第三次调用时返回 true 的谓词来移除一个容器中的第三项。

This noncompliant code example attempts to remove the third item in a container using a predicate that returns true only on its third invocation.

#include <algorithm>
#include <functional>
#include <iostream>
#include <iterator>
#include <vector>

class MutablePredicate : public std::unary_function<int, bool> {
  size_t timesCalled;
public:
  MutablePredicate() : timesCalled(0) {}

  bool operator()(const int &) {
    return ++timesCalled == 3;
  }
};

template <typename Iter>
void print_container(Iter b, Iter e) {
  std::cout << "Contains: ";
  std::copy(b, e, std::ostream_iterator<decltype(*b)>(std::cout, " "));
  std::cout << std::endl;
}

void f() {
  std::vector<int> v{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
  print_container(v.begin(), v.end());

  v.erase(std::remove_if(v.begin(), v.end(), MutablePredicate()), v.end());
  print_container(v.begin(), v.end());
}

然而，std::remove_if() 被允许构造和使用其谓词函数额外的拷贝。任何这种额外的拷贝可能导致意外的输出。

However, std::remove_if() is permitted to construct and use extra copies of its predicate function. Any such extra copies may result in unexpected output.

实现细节 Implementation Details

使用 gcc 4.8.1 和 libstdc++ ，这个程序产生了下述结果。

This program produces the following results using gcc 4.8.1 with libstdc++.

1 2	Contains: 0 1 2 3 4 5 6 7 8 9 Contains: 0 1 3 4 6 7 8 9

这个结果的产生由于 std::remove_if 在调用前，拷贝了两份谓词函数。第一份拷贝被用来确定第一个元素在序列中的位置，谓词返回的是 true。随后的拷贝被用来移除序列中的其他元素。这个结果造成第三个元素 (2) 和第六个元素 (5) 被移除；两个不同的谓词函数被使用。

This result arises because std::remove_if makes two copies of the predicate before invoking it. The first copy is used to determine the location of the first element in the sequence for which the predicate returns true. The subsequent copy is used for removing other elements in the sequence. This results in the third element (2) and sixth element (5) being removed; two distinct predicate functions are used.

不合规的代码示例 (仿函数) Noncompliant Code Example (Lambda)

和仿函数不合规代码示例类似，这个不合规代码示例试图使用一个在其第三次调用时返回 true 的谓词 lambda 函数来移除第三项。和仿函数一样，这个 lambda 携带有局部状态信息，试图在其调用操作中修改。

Similar to the functor noncompliant code example, this noncompliant code example attempts to remove the third item in a container using a predicate lambda function that returns true only on its third invocation. As with the functor, this lambda carries local state information, which it attempts to mutate within its function call operator.

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>

template <typename Iter>
void print_container(Iter b, Iter e) {
  std::cout << "Contains: ";
  std::copy(b, e, std::ostream_iterator<decltype(*b)>(std::cout, " "));
  std::cout << std::endl;
}

void f() {
  std::vector<int> v{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
  print_container(v.begin(), v.end());

  int timesCalled = 0;
  v.erase(std::remove_if(v.begin(), v.end(), [timesCalled](const int &) mutable { return ++timesCalled == 3; }), v.end());
  print_container(v.begin(), v.end());
}

合规方案 (`std::reference_wrapper`) Compliant Solution (`std::reference_wrapper`)

这个合规方案将谓词包裹在 std::reference_wrapper<T> 对象中，确保包裹对象的拷贝全都引用相同的基础谓词对象。

This compliant solution wraps the predicate in a std::reference_wrapper<T> object, ensuring that copies of the wrapper object all refer to the same underlying predicate object.

#include <algorithm>
#include <functional>
#include <iostream>
#include <iterator>
#include <vector>

class MutablePredicate : public std::unary_function<int, bool> {
  size_t timesCalled;
public:
  MutablePredicate() : timesCalled(0) {}

  bool operator()(const int &) {
    return ++timesCalled == 3;
  }
};

template <typename Iter>
void print_container(Iter b, Iter e) {
  std::cout << "Contains: ";
  std::copy(b, e, std::ostream_iterator<decltype(*b)>(std::cout, " "));
  std::cout << std::endl;
}

void f() {
  std::vector<int> v{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
  print_container(v.begin(), v.end());

  MutablePredicate mp;
  v.erase(std::remove_if(v.begin(), v.end(), std::ref(mp)), v.end());
  print_container(v.begin(), v.end());
}

上述合规方案演示了在仿函数对象上使用的引用包裹器，但同样地可用于有状态的 lambda。这个代码产生了期望的结果，只有第三个元素被移除。

The above compliant solution demonstrates using a reference wrapper over a functor object but can similarly be used with a stateful lambda. The code produces the expected results, where only the third element is removed.

1 2	Contains: 0 1 2 3 4 5 6 7 8 9 Contains: 0 1 3 4 5 6 7 8 9

合规方案 (迭代器运算) Compliant Solution (Iterator Arithmetic)

移除一个容器中的特定元素不需要谓词函数，但是可以简单地用 std::vector::erase() 来替换，像这个合规方案。

Removing a specific element of a container does not require a predicate function but can instead simply use std::vector::erase(), as in this compliant solution.

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>

template <typename Iter>
void print_container(Iter B, Iter E) {
  std::cout << "Contains: ";
  std::copy(B, E, std::ostream_iterator<decltype(*B)>(std::cout, " "));
  std::cout << std::endl;
}

void f() {
  std::vector<int> v{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
  print_container(v.begin(), v.end());
  v.erase(v.begin() + 3);
  print_container(v.begin(), v.end());
}

风险评估 Risk Assessment

使用包含状态地谓词函数对象会产生意外的值。

Using a predicate function object that contains state can produce unexpected values.

Rule	Severity	Likelihood	Remediation Cost	Priority	Level
CTR58-CPP	Low	Likely	High	P3	L3

Automated Detection

Tool	Version	Checker	Description
Parasoft C/C++test		CERT_CPP-CTR58-a	Make predicates const pure functions
PRQA QA-C++		3225, 3226, 3227, 3228, 3229,3230, 3231, 3232, 3233, 3234