What Is Predicate in C++

What is a predicate in c#?

Predicate<T> is a functional construct providing a convenient way of basically testing if something is true of a given T object.

For example suppose I have a class:

class Person {
    public string Name { get; set; }
    public int Age { get; set; }
}

Now let's say I have a List<Person> people and I want to know if there's anyone named Oscar in the list.

Without using a Predicate<Person> (or Linq, or any of that fancy stuff), I could always accomplish this by doing the following:

Person oscar = null;
foreach (Person person in people) {
    if (person.Name == "Oscar") {
        oscar = person;
        break;
    }
}

if (oscar != null) {
    // Oscar exists!
}

This is fine, but then let's say I want to check if there's a person named "Ruth"? Or a person whose age is 17?

Using a Predicate<Person>, I can find these things using a LOT less code:

Predicate<Person> oscarFinder = (Person p) => { return p.Name == "Oscar"; };
Predicate<Person> ruthFinder = (Person p) => { return p.Name == "Ruth"; };
Predicate<Person> seventeenYearOldFinder = (Person p) => { return p.Age == 17; };

Person oscar = people.Find(oscarFinder);
Person ruth = people.Find(ruthFinder);
Person seventeenYearOld = people.Find(seventeenYearOldFinder);

Notice I said a lot less code, not a lot faster. A common misconception developers have is that if something takes one line, it must perform better than something that takes ten lines. But behind the scenes, the Find method, which takes a Predicate<T>, is just enumerating after all. The same is true for a lot of Linq's functionality.

So let's take a look at the specific code in your question:

Predicate<int> pre = delegate(int a){ return a % 2 == 0; };

Here we have a Predicate<int> pre that takes an int a and returns a % 2 == 0. This is essentially testing for an even number. What that means is:

pre(1) == false;
pre(2) == true;

And so on. This also means, if you have a List<int> ints and you want to find the first even number, you can just do this:

int firstEven = ints.Find(pre);

Of course, as with any other type that you can use in code, it's a good idea to give your variables descriptive names; so I would advise changing the above pre to something like evenFinder or isEven -- something along those lines. Then the above code is a lot clearer:

int firstEven = ints.Find(evenFinder);

What is predicate in C++?

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

What is a Predicate Delegate and where should it be used?

A predicate is a function that returns true or false. A predicate delegate is a reference to a predicate.

So basically a predicate delegate is a reference to a function that returns true or false. Predicates are very useful for filtering a list of values - here is an example.

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        List<int> list = new List<int> { 1, 2, 3 };

        Predicate<int> predicate = new Predicate<int>(greaterThanTwo);

        List<int> newList = list.FindAll(predicate);
    }

    static bool greaterThanTwo(int arg)
    {
        return arg > 2;
    }
}

Now if you are using C# 3 you can use a lambda to represent the predicate in a cleaner fashion:

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        List<int> list = new List<int> { 1, 2, 3 };

        List<int> newList = list.FindAll(i => i > 2);
    }
}

What's the predicate in C++?

There's no formal definition of a predicate in the context of C++ (that I know of anyway), but it generally means a function that can be used in a true/false context.

Here's a possible implementation of count_if from cppreference that illustrates what it's talking about:

template<class InputIt, class UnaryPredicate>
typename iterator_traits<InputIt>::difference_type
    count_if(InputIt first, InputIt last, UnaryPredicate p)
{
    typename iterator_traits<InputIt>::difference_type ret = 0;
    for (; first != last; ++first) {
        if (p(*first)) {
            ret++;
        }
    }
    return ret;
}

p must return something that can be used inside of an if statement is what it basically boils down to.

For example:

class T {};

T f(int x)
{
    return T();
}

This is not a valid predicate for count_if because T is not implicitly convertible to a bool.

In other words:

if (f(4)) { }

Is uncompilable code.

If, however, T could be implicitly converted to a bool, f would be an acceptable predicate (though very odd).

When do I use a predicate

Firstly, I'll summarize delegates and lambda expressions.

Delegates

---

In C#, delegates allow you to create types which represent functions. In other words, delegates allow you to save a reference to a method in a variable. Once, we store a reference to that method, we can use this variable to call the method it is referring to. So you are indirectly calling the method. The term "delegate" in C# very well lives up to the literal meaning of delegate.

To store a reference to a method, you first need to create a compatible delegate:

delegate int MyDelegate(string parameter)

The above statement creates a delegate that can hold a reference to any method that has a return type of int and takes a single string as parameter. For instance, I'm creating a trivial class and a method here for demo:

class AClass 
{
    public int StringLength(string str) { return str.Length; }
}

Once you create a delegate, you can use it like a type:

AClass obj = new AClass()
MyDelegate d = obj.StringLength

Notice I have skipped the parentheses after StringLength. Now I can do this:

int length = d("Hello");

This will indirectly call, obj.StringLength() and the value it returns will be returned by d and stored in length.

There's more to delegates like multicast delegates which are beyond the scope of this answer.

Why are delegates powerful?

They help you to easily pass around functions/methods just like objects. You can pass your own method to a class that knows nothing about your method but will call it later through the delegate. This allows you to embed your custom logic into code that you know nothing about.

Lambda Expressions

---

A lambda expression is nothing but a function literal. It helps to quickly create a function without creating a new class and a new method. In the previous example, I have created a class called AClass with a method StringLength. You can see that all the method body consists is of a single line. With lambdas, you can skip creating a class and a method and directly specify the method body:

MyDelegate d = str => str.Length;

The Predicate<T> Delegate

---

Predicate<T> is just another delegate as well, defined as follows:

delegate bool Predicate<T>(T obj)

This is a delegate with a generic parameter. This allows you to pass it a parameter of any type which will be specified later when the delegate variable is created but the return type is always bool. A predicate is, in essence, just a condition, that can be either true or false.

Coming to your question, with predicates, you can pass in such a condition to a method so that the method can use it to check if it holds true for something that is private to that class. You are basically passing in logic that will be executed later.

A common use case of predicates is filtering. If I have a collection of elements, and I want to filter the elements and obtain only those elements for which a condition holds true, I can use a Predicate<T> parameter:

public List<int> Filter(List<int> list, Predicate<int> filter)
{
    public var filteredList = new List<int>();
    foreach (int element in list)
    {
        if (filter(element))
        {
            filteredList.Add(element); //Add to list only if condition holds true for the element
        }
        
    }
}

Now, suppose, I have a list and I want only the even numbers and numbers greater than 5, then I can simply do this:

var numbers = new List<int>() { 1, 2, 3, 4, 5, 6, 7, 8, 9 }
var evenNumbers = Filter(numbers, element => element % 2 == 0);    // 2, 4, 6, 8
var numbersGreaterThan5 = Filter(numbers, element => element > 5); // 6, 7, 8, 9

In practice, you will hardly have to create a custom Filter() method since System.Linq already has a method/LINQ operator called Where() that does this for you. The parameter to this Where() method is not a Predicate<T> but an identical(compatibility-wise) Func<T, bool> which is another delegate defined as follows:

delegate TResult Func<in T, out TResult>(T arg)

Func<T, bool> and Predicate<T> are therefore identical regards to the methods they can reference. Moreover, you can create your own delegate with the same signature as the predicate. The framework has a bunch of them defined to make life a bit easier for you.

What does predicate mean in C?

The sentence is a declaration and definition of a pointer to a function taking one argument (char) and returning int. The pointer is initialized to the null pointer value.

The word "predicate" is the programmer's choice for the variable name.

Reference: cdecl

One might use predicate like this:

/* UNTESTED */
int IsLower(char c) { return c >= 'a' && c <= 'z'; }
int main () {
    int (*predicate)(char);

    predicate = IsLower;

    if ( (*predicate)('f') == 1 ) printf("'f' is lower case!\n");
}

What is a predicate?

The definition of a predicate, which can be found online in various sources such as here, is:

A logical expression which evaluates to TRUE or FALSE, normally to direct the execution path in code.

Referencing: Software Testing. By Mathew Hayden

Predicates in C++

Let's inspect a simple definition:

template <typename T>
struct TD;

bool is_odd(const int x) {
    return x % 2 != 0;
}

template<typename T>
void foo(T arg){
    TD<T> type_displayer;
}

int main() {
    foo(is_odd);
}

When you run this code, you get an error. An error saying that:

'TD<bool (*)(int)> type_displayer' has incomplete type

That's my favourite 'hack' to inspect the deduced type (T from foos argument). You can clearly see how I passed a function to foo in main, but the deduced type was <bool (*)(int)>, which is a pointer to a function that returns bool and takes an int as argument.

That's all it is to passing a function as an argument to a template function.

For references on function pointers, see this question and this tutorial.

How do predicate and/or predicator data members and/or member functions work in C++? What does (elem.*predicator)() do in the following snippet?

.* and ->* are the pointer-to-member operators.

Those are pointers that can store which method of a class to call.

See [expr.mptr.oper] in the standard or questions like Calling C++ class methods via a function pointer.

Designing a C++ concept with multiple invocables / predicates

I would do it this way.

First, your graph concept has several associated types. Similar to how a range in C++ has an iterator type (amongst others). We don't write range<R, I>, we just write range<R>. If R is a range, then it has some iterator type - we don't ask if R is a range with iterator I. We may not know I ex ante. Similarly, we have input_iterator<I>, and not input_iterator<I, value_type, reference, difference_type>. I defines those other things (if it's actually an iterator).

So we'll start with some aliases:

template <class G> using node_type = /* ... */;
template <class G> using edge_type = /* ... */;
// ...

Next, you want your graph type to accept an arbitrary predicate. There's no way to phrase arbitrary predicate in C++. But we can do the next best thing: just pick one arbitrary one. If the graph type works for some arbitrary private type that you define, it probably works for any such thing. Thus:

namespace impl {
    template <class G>
    struct some_predicate {
        // intentionally not default constructible
        // since predicate doesn't have to be
        some_predicate() = delete;

        // likewise doesn't have to be copyable, though you
        // may just want to default these anyway (to allow
        // having by-value predicates, for instance)
        some_predicate(some_predicate const&) = delete;
        some_predicate& operator=(some_predicate const&) = delete;

        // but it does need this call operator
        auto operator()(edge_type<G> const&,
                        node_type<G> const&,
                        node_type<G> const&,
                        edge_data_type<G> const&) const
            -> bool;
    };
}

We don't need to define that call operator since we're not using it anyway. But we can use some_predicate to build up our concept:

template <typename G>
concept ConstantDirectedGraphConcept =
    requires(G g, node_type<G> n, impl::some_predicate<G> p) {
        g.get_outputs(n, p);
        g.get_output(n, p);
        g.get_outputs_full(n, p);
        g.get_output_full(n, p);
        g.get_inputs(n, p);
        g.get_input(n, p); 
        g.get_inputs_full(n, p);
        g.get_input_full(n, p);
    };

That should get you most of the way there. If a user's graph type works with this arbitrary predicate, then it probably will work for any arbitrary predicate.

Possibly (depending on how node_type and friends are defined) this needs to be:

template <typename G>
concept ConstantDirectedGraphConcept = requires {
        typename node_type<G>;
        typename edge_type<G>;
        typename node_data_type<G>;
        typename edge_data_type<G>;   
    } && requires(G g, node_type<G> n, impl::some_predicate<G> p) {
        // ...
    }
};

---

Related Topics