What is predicate in C++?

Question

Can you give some example or a link to a topic.

Solution 1

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

Solution 2

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.

Solution 3

It is not specific to C++ (or even computer languages). In natural language grammar, in a statement such as the gate is open, the is open part is the predicate and is either true or false, so say you had a class cGate, with a member function bool cGate::isOpen(), such a function would be a predicate.

Essentially if the function asks a question about the object state or value and the result is either true or false, then it is a predicate.

Solution 4

A predicate is simply a function that returns true or false depending on whether its input(s) satisfy some condition. In general, a predicate function should be pure; it should always return the same result when given the same input (so bool isDateInPast(Date &date) would be a bad predicate).

They are often used, for example, as callbacks for STL sorting routines (i.e. "is input a less than input b?").

View more solutions

Comments

[Clifford]

@Mr E: The great thing about Stack Overflow is that increasingly Google searches on programming related issues link to here. If such questions were not answered here, that would never happen and SO would never have reached critical mass. So "google it" is never a satisfactory answer.

[YXD]

Depends. Agree on Google-ability, but I was never under the impression that SO should serve as a replacement for a basic language reference. It's also good to see that the person asking the question has put even the smallest amount of effort into finding the answer, so that they can point out what particular aspect they are having trouble understanding. There are different opinions on this: meta.stackexchange.com/questions/33376/… meta.stackexchange.com/questions/8724/…

[munish]

I thought it might be different in C++ as I saw many other similar questions here and I never thought it would be too simple as just true and false here. I was just going through a program and found it and I thought by looking at the code that its(Predicate) something used for searching through STL conatiners ,googled some sites too but still i had doubt's and I was not clear.I was thinking that its something used for iterating through the class objects atributes.Sorry about that anyway

[YXD]

No need to apologize, just bear in mind that you'll get more useful results if you give some background to your problem.

[Steve Jessop]

@Mr E: did you try that search yourself? The definition given by the top hit is wrong, so +1 to the questioner for at least trying to consult people more likely than average to give correct answers.

[Clifford]

@munish: You are right in C++ specifically it can refer to the predicate parameter of an STL algorithm and similar usages. Your question may or may not refer to that, I took it in a more general grammatical sense, so I learned something, so just as well that you did not just Google it since the question genuinely adds to the SO repository (IMO). I suggest however that you change the body text to something less demanding and more expansive to avoid unnecessary closure and down-votes.

[fauxCoder]

@MrE I have, that's how I got here...

[3bdalla]

How this question can be "not a real question" ? Isn't the title enough to write an answer ?

[Rick]

@3bdalla They said the "not a real question" reason is just used to be used in the old days.

[pio]

funny enough, my first match of google search of c++ predicate refer to here. maybe it's because of the first comment that the questioner should google c++ predicate.. :)

[fmunshi]

That link says it has to be a unary function too.

[Oliver Charlesworth]

@Simon: Yeah, that's not a very general link. I'll remove it from my answer.

[Ben Voigt]

Predicates are commonly used in STL searching routines, e.g. copy_if. And yes, they are unary. The ordering function is not considered a predicate.

[Steve Jessop]

Predicates don't have to be functions, then can instead be functors. And at least for the purposes of standard algorithms they don't have to return something that's either bool or has operator bool(), it can return anything that's testable as true or false. So built-in types that convert to bool, such as pointers, are also OK.

[Steve Jessop]

@Ben: the requirements for Compare parameters are strictly stronger than the requirements for BinaryPredicate parameters, though. Comparators must return true or false (rather than any truth-testable value), and of course must implement a strict weak order. But since C++0x used the term Predicate rather than UnaryPredicate, we're forced to conclude that while a "binary predicate" is a "predicate" in English, a BinaryPredicate is not a Predicate in standard-ese. Crazy stuff :-)