Page History

The C++ Standard Library implements numerous common algorithms which accept a predicate function object. According to the C++ Standard, [algorithms.general], paragraph 10, states [ISO/IEC 14882-2014]:

[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]

Because it is implementation-defined whether an algorithm uses copies of predicate function objects, all predicate function objects must either implement a pure function call operator, or must wrap the predicate function object in a std::reference_wrapper<T> (or an equivalent solution). Pure function calls are ones for which the return value depends only on the function parameters, and not stateful information. Note that marking the function call operator as const is beneficial, but insufficient, for creating a pure function, as data members with the mutable storage class specifier may still be modified within a const member function.

Noncompliant Code Example

This noncompliant code example attempts to remove the third item in a container

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 third invocation.

#include <algorithm>
#include <functional>
#include <iostream>
#include <vector><iterator>
 
using namespace std;
 #include <vector>
  
class BadPredicate : public std::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 << endltemplate <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(), BadPredicate()), v.end());

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

  return 0;
}
  print_container(v.begin(), v.end());
}

However, std::remove_if() is permitted However, the remove_if is permitted by the standard to construct and use extra copies of its predicate function. Such Any such extra copies confound the timesCalled variablemay result in unexpected output.

Implementation Details

For instance, this This program produces the following results, using gcc 4.8.1 with libstdc++:

Vector contains

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

Vector contains

Contains: 0 1 3 4 6 7 8 9

This result arises when because std::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)

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) being removed, as well as the sixth element (5) – two distinct predicate functions are used.

Compliant Solution (std::reference_wrapper)

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 objectA simple way to prevent this behavior is to declare the predicate's operator() to be const.

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

  bool operator()(const int &) const {
    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());

  BadPredicate BP;
  v.erase(std::remove_if(v.begin(), v.end(), std::ref(BP)), v.end());
  print_container(v.begin(), v.end());
}

The compiler will fail to build this program because of the attempt to increment a class field within a const method.above code produces the expected results, where only the third element is removed:

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)

The proper way to remove a container element based on position is with iterator arithmeticRemoving 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.v.erase(v.begin() + 3);
  print_container(v.begin(), v.end());
}

Risk Assessment

Predicates that contain internal Using a predicates function object that contains state can produce unexpected values after usage.

Automated Detection

Related Vulnerabilities

Search for vulnerabilities resulting from the violation of this rule on the CERT website.

Related Guidelines

Bibliography

 : Make predicates pure functions