ARR44-CPP. Predicate functors should not have non-static 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.

class BadPredicate: public unary_function< int, bool> {
public:
  BadPredicate() : timesCalled(0) {}

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

int main () {
  vector<int> v;
  for (int i = 0; i < 10; i++) v.push_back(i);

  cout << "Vector contains:";
  for (vector<int>::iterator it = v.begin(); it != v.end(); ++it)
    cout << " " << *it;
  cout << endl;

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

  cout << "Vector contains:";
  for (vector<int>::iterator it = v.begin(); it != v.end(); ++it)
    cout << " " << *it;
  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 G++ 4.3.2 on Linux

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

ARR43-CPP. Do not access collapsed elements from a remove(), remove_if() or unique() operation      06. Arrays and the STL (ARR)      07. Characters and Strings (STR)