Page History

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.

...

#include <algorithm>
#include <iostream>
#include <vector>
 
using namespace std;
 
class BadPredicate: public unary_function< intfunction<int, bool> {
  size_t timesCalled;
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)const auto &i : v) {
    cout << " " << *iti;
  }
  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)const auto &i : v) {
    cout << " " << *it;i;
  }
  cout << endl;

  return 0;
}

...

For instance, this program produces the following results, using G++ gcc 4.3.2 on Linux8.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.

...

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.

...