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

...

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 (functor)

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

...

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

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

...

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

Noncompliant Code Example (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());
}

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 object.

#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 &) {
    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 above compliant solution demonstrates using a reference wrapper over a functor object, but can similarly used with a stateful lambda. The 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)

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

...