Function Objects and Standard Algorithms

A function object extends the meaning of a standard algorithm by supplying behavior that the algorithm itself does not know.

Programming

A Common Belief About Helper Functions

Many learners who first meet predicates treat them as ordinary helpers. The reasoning goes like this: a predicate is a small piece of code the algorithm calls, so it can do whatever is convenient, as long as it eventually returns an answer. Under that belief, a predicate that quietly changes the value it was given looks harmless. It might keep a running total, or it might normalize the data before checking it.

This belief is a real and specific misconception, and correcting it reveals what a predicate is actually for. The rest of this article traces what happens inside an algorithm when it calls a predicate, and why the predicate has to leave its argument alone.

EASY

Before reading on: if a predicate changes the value it receives, does the algorithm's data stay the same after the algorithm finishes asking its question?

Hints

Think about where the predicate's argument comes from. Is it a copy, or is it a value that belongs to the data being processed?
Consider what the algorithm assumes about the data while it is only searching or counting.

Your attempt (not saved)

What a Standard Algorithm Does Not Know

A standard algorithm in the STL is written to do one general job, such as searching a sequence, counting matching items, or rearranging values. The algorithm does not know your particular rule for what counts as a match, and it does not know what should happen to each element. The general job stays fixed. The specific rule has to come from somewhere else.

A function object is the piece that supplies that rule. It is an object that can be called like a function. By passing a function object to a standard algorithm, you give the algorithm a wider range of meanings than it would have on its own. The algorithm supplies the looping and the bookkeeping, and the function object supplies the behavior the algorithm cannot know in advance.

Definition

A function object extends the meaning of a standard algorithm by supplying behavior that the algorithm itself does not know.

Predicates Answer a Yes or No Question

Definition

A predicate is a function object used to give standard algorithms a wider range of meanings, typically by answering a yes or no question about a value. Each call takes one value and returns true or false.

The difference from a plain value check is about where the decision lives. A plain check is written directly inside the algorithm's own code, so changing the rule means changing the algorithm. A predicate is passed in from outside. The algorithm keeps the same looping code, and the rule it applies is whatever function object you hand it.

Where does the decision logic live in each approach, and how does swapping the predicate change the algorithm's behavior without changing its code?

Tracing a Counting Algorithm Through a Predicate

Consider a predicate that answers whether a number is even. The standard algorithm count_if walks through a range, calls the predicate on each element in turn, and counts the elements for which the predicate returns true. The algorithm controls the walk. The predicate controls the answer for each element.

cpp

struct IsEven {
    bool operator()(int value) const {
        return value % 2 == 0;
    }
};

int main() {
    std::vector<int> numbers = {2, 7, 4, 9};
    int count = std::count_if(numbers.begin(), numbers.end(), IsEven{});
}

struct IsEven {
    bool operator()(int value) const {
        return value % 2 == 0;
    }
};

int main() {
    std::vector<int> numbers = {2, 7, 4, 9};
    int count = std::count_if(numbers.begin(), numbers.end(), IsEven{});
}

Output

count = 2

Notes on the code

struct IsEven is a function object: it can be called like a function
operator() takes one int and returns bool, which makes it a predicate
IsEven{} creates the function object and passes it to the algorithm
count_if does the looping and counting; IsEven supplies the yes or no answer

What happens to each element as the algorithm walks through the range, and how does the predicate's true or false result decide what the algorithm does next?

Worked example

Tracing count_if with IsEven

Trace what count_if does with the range 2, 7, 4, 9 and the predicate IsEven.

1
Step 1
The algorithm takes the first element, 2, and passes it to IsEven. IsEven returns true, so the running count becomes 1.
2
Step 2
The algorithm moves to 7. IsEven returns false, so the count stays at 1.
3
Step 3
The algorithm moves to 4. IsEven returns true, so the count becomes 2.
4
Step 4
The algorithm moves to 9. IsEven returns false, so the count stays at 2. The range is exhausted.

Result

count_if returns 2. The algorithm handled the looping and counting, and the predicate handled only the question asked of each value.

Why a Predicate Must Leave Its Argument Alone

The rule that a predicate must not modify its argument is the central correction to the misconception above. An algorithm calls a predicate on values that belong to the data it is processing. If the predicate changes one of those values as a side effect, the data is altered by the act of asking a question about it.

The algorithm was written to find, count, or select items, not to mutate them. A predicate that changes its input breaks the assumption the algorithm relies on. The predicate should only inspect the value it receives, which keeps the data safe while the algorithm asks its questions.

When a predicate changes its argument, what is different about the element's state before and after the call, and why does that break the algorithm?

Spotting a Predicate That Writes to Its Input

The before and after versions below use the same yes or no question. The first version takes its argument by reference and writes a new value into it before answering. The second version reads the argument and answers without changing anything.

Before

struct DoublesAndChecks {
    bool operator()(int& value) const {
        value = value * 2;
        return value > 10;
    }
};

The predicate writes the doubled value back into the element, so the data is changed by the question.

After

struct DoublesAndChecks {
    bool operator()(const int& value) const {
        return value * 2 > 10;
    }
};

The predicate only reads the element and computes an answer, so the data is unchanged after every call.

Code walkthrough

A read-only predicate that checks whether a value exceeds a limit.

1
The parameter is declared const int&, so the predicate receives the element without the right to change it.
2
The return type is bool, so the algorithm gets a yes or no answer for each element.
3
The expression value * 2 > 10 is computed into a temporary result; the element itself is never assigned to.
4
Because the predicate only inspects, the algorithm can keep counting or selecting with the data exactly as it was stored.

Mistakes With Predicates

Common mistake
Keeping a running total inside the predicate
What it looks like
A predicate that adds each value it sees to a member variable, then returns true when the total passes a limit.
Why it fails
The predicate is no longer answering a question about one value. Its answers depend on how many times the algorithm has called it, and the bookkeeping is mixed into the check.
Do this instead
Keep the predicate a pure yes or no question about the value it receives. If a total is needed, compute it with code that is clearly separate from the question being asked.
Common mistake
Normalizing the data before checking it
What it looks like
A predicate that divides the value it receives by a scale factor and assigns the result back, then compares the new value to a threshold.
Why it fails
The data is altered by the act of asking a question. The algorithm was written to find or select items, not to mutate them, so the stored values no longer match what the caller supplied.
Do this instead
Compute the scaled value in a local variable inside the predicate, leave the argument untouched, and return the comparison result.
Common mistake
Writing a plain value check inside the algorithm when the rule may change later, which forces you to edit the algorithm instead of passing in a different predicate

Writing Your Own Read-Only Predicate

Work through the following task using the same pattern as IsEven. Your predicate should be a function object with one argument and a bool result, and it should only inspect the value it receives.