What is predicate in C++?

The C++ standard defines Predicate as follows (25/7):

The Predicate parameter is used whenever an algorithm expects a function object that when applied to the result of dereferencing the corresponding iterator returns a value testable as true. In other words, if an algorithm takes Predicate pred as its argument and first as its iterator argument, it should work correctly in the construct if (pred(*first)){...}. The function object pred shall not apply any non-constant function through the dereferenced iterator. This function object may be a pointer to function, or an object of a type with an appropriate function call operator.

There's an analogous definition of BinaryPredicate with two parameters.

So in English, it's a function or an object with a operator() overload, that:

• takes a single parameter. In the case of algorithms, the parameter type is implicitly convertible from the type of the dereferenced iterator of the algorithm in question, or is a const reference to such a type, or at a push it can be a non-const reference to the exact type as long as the iterator isn't a const_iterator.
• returns a value that can be tested for truth in an if statement (and hence because of C++'s language rules, also in a while loop and so on).
• doesn't modify its arguments (at least, not as long as the parameter type is const-correct...)

Additionally, since many algorithms don't specify the exact order of operations they perform, you might find that you get unpredictable behavior if your predicate isn't consistent, i.e. if the result depends on anything other than the input value that can change between calls.

As well as algorithms, the logical negator not1 in <functional> takes a Predicate template parameter. In that case, there's an extra requirement (20.3/5):

To enable adaptors and other components to manipulate function objects that take one or two arguments it is required that the function objects correspondingly provide typedefs argument_type and result_type for function objects that take one argument and first_argument_type, second_argument_type, and result_type for function objects that take two arguments.

A predicate is a C++ function returning a boolean or an object having a bool operator() member. A unary predicate takes one argument, a binary takes two, and so on. Examples of questions predicates can answer for a particular algorithm are:

• Is this element what we are looking for?
• Is the first of two arguments ordered first in our order?
• Are the two arguments equal?

Almost all STL algorithms take a predicate as last argument.

You can construct new predicates using standard, self-defined, and/or predicate-making classes (here is a good reference).