CTR44-CPP. Predicate functors should not have non-static non-const data fields

STL containers that take predicate functors are perfectly free to make multiple copies of the predicate, and often do, because typically predicates are passed by value. [Meyers 01] Item 38) If a predicate stores and uses internal state, then its state values at the end of a predicate-based function call are implementation-defined, and usually unexpected.

Non-Compliant Code Example

This example tries to remove the 3rd item in a container of widgets by using a predicate that returns true only on its 3rd invocation.

#include <algorithm>
#include <iostream>
#include <vector>
 
using namespace std;
 
class BadPredicate: public unary_function<int, bool> {
  size_t timesCalled;
public:
  BadPredicate() : timesCalled(0) {}

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

int main () {
  vector<int> v;
  for (int i = 0; i < 10; i++) {
    v.push_back(i);
  }
  cout << "Vector contains:";
  for (const auto &i : v) {
    cout << " " << i;
  }
  cout << endl;

  v.erase(remove_if(v.begin(), v.end(), BadPredicate()), v.end());

  cout << "Vector contains:";
  for (const auto &i : v) {
    cout << " " << i;
  }
  cout << endl;

  return 0;
}

However, the remove_if is permitted by the standard to construct and use extra copies of its predicate function. Such extra copies confound the timesCalled variable.

Implementation Details

For instance, this program produces the following results, using gcc 4.8.1:

Vector contains: 0 1 2 3 4 5 6 7 8 9
Vector contains: 0 1 3 4 6 7 8 9

This result arises when remove_if makes two copies of the predicate before invoking it. It uses the first copy until it receives a true response (when removing 2), and uses the second copy. The second copy again returns true on its 3rd invocation, causing the 5 to also be removed.

Compliant Solution (const)

A simple way to prevent this behavior is to declare the predicate's operator() to be const.

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

The compiler will fail to build this program because of the attempt to increment a class field within a const method.

Compliant Solution (Iterator arithmetic)

The proper way to remove a container element based on position is with iterator arithmetic:

v.erase(v.begin() + 3);

Risk Assessment

Predicates that contain internal state can produce unexpected values after usage.

Bibliography

[Meyers 01] Item 39: Make predicates pure functions