CertC++-CTR58ΒΆ

Predicate function objects should not be mutable

Required inputs: IR

The C++ standard library implements numerous common algorithms that accept a predicate function object. The C++ Standard, [algorithms.general], paragraph 10 [ ISO/IEC 14882-2014], states the following:

[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 copies a predicate function object, any such object must either

  • implement a function call operator that does not mutate state related to the function object's identity, such as nonstatic data members or captured values, or
  • wrap the predicate function object in a  std::reference_wrapper<T> (or an equivalent solution).

Marking the function call operator as  const is beneficial, but insufficient, because 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. 

#include <algorithm>
#include <functional>
#include <iostream>
#include <iterator>
#include <vector>
  
class MutablePredicate : public std::unary_function<int, bool> {
  size_t timesCalled;
public:
  MutablePredicate() : 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());

  v.erase(std::remove_if(v.begin(), v.end(), MutablePredicate()), v.end());
  print_container(v.begin(), v.end());
}

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

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

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) and sixth element ( 5) being removed; 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 uses std::ref to wrap 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 MutablePredicate : public std::unary_function<int, bool> {
  size_t timesCalled;
public:
  MutablePredicate() : 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());

  MutablePredicate mp;
  v.erase(std::remove_if(v.begin(), v.end(), std::ref(mp)), v.end());
  print_container(v.begin(), v.end());
}

The above compliant solution demonstrates using a reference wrapper over a functor object but can similarly be used with a stateful lambda. The 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 predicate function object that contains state can produce unexpected values.

Rule Severity Likelihood Remediation Cost Priority Level
CTR58-CPP Low Likely High P3 L3
Bibliography
[ ISO/IEC 14882-2014] Subclause 25.1, "General"
[ Meyers 2001] Item 39, "Make Predicates Pure Functions"
Excerpt from SEI CERT C++ Coding Standard [https://cmu-sei.github.io/secure-coding-standards/sei-cert-cpp-coding-standard/rules/containers-ctr/ctr58-cpp], Copyright (C) 1995-2026 Carnegie Mellon University. See section 9.4. "3rd-Party Licenses" in the documentation for full details.

Possible Messages

Key

Text

Severity

Disabled

modifies_state

Call operator of predicate passed to {} modifies state.

None

False

nonconst_op

Call operator of predicate passed to {} is not const.

None

False

Options