Writing Safe Algorithm Helpers

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

Programming

A Helper That Seems Harmless

Imagine you are asking a question about every value in a collection. The question is a small helper, and it seems reasonable that the helper could do whatever is convenient, as long as it eventually gives you an answer. Perhaps it keeps a running total, or it tidies up the value before checking it. Nothing about that looks dangerous. Many learners who first meet predicates hold exactly this belief, and it is a real and specific misconception.

This article starts from that belief and corrects it. The correction reveals what a predicate is actually for, and why the helper is not allowed to change the data it is asking about. By the end you should be able to explain the rule, spot code that breaks it, and write a predicate that only reads its input.

What a Function Object Adds

Definition

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

A standard algorithm 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, or what should happen to each element. The 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 same general procedure, such as counting, can now answer many different questions, because the question is supplied from outside.

Think of the algorithm as a general procedure that walks through a sequence and asks something of each element. The function object is the specific question. Changing the question changes what the algorithm finds, without rewriting the procedure itself.

Predicates and Plain Value Checks

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.

A predicate is therefore a specific kind of function object. It takes a value and returns a yes or no answer, and the algorithm uses that answer to decide what to do with the element. Compare this with writing the condition directly inside a loop or inside a hand-written algorithm. In that case the rule is hard-wired into the procedure, so reusing the procedure for a different rule means editing it.

Where the decision logic lives in a plain value check compared with a predicate, and what changes when the algorithm is reused with a different condition.

The practical benefit is reuse. A standard algorithm can be left alone while different predicates change what it counts, finds, or selects. A plain check forces you to rewrite or duplicate the procedure whenever the rule changes.

Why Predicates Must Stay Read Only

The rule that a predicate must not modify its argument is the central correction to the misconception. 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 algorithm may then give a result that reflects a modified sequence, while the caller believes the sequence is untouched.

A predicate that only reads its argument keeps the data safe while the algorithm asks its questions. The safe rule is simple to state: the predicate inspects the value it receives and returns an answer, and nothing else.

How the element's value looks before and after a predicate that changes its argument runs, compared with one that only reads it.

The diagram shows the effect of a mutating predicate. Before the call, the fourth element holds 10. After a predicate that normalizes its argument runs, the same element holds 0. A predicate that only reads its argument would leave every element exactly as it was.

Tracing the Algorithm's Calls

A standard algorithm repeatedly calls the function object on each element. The order of the visits is what makes a mutating predicate especially damaging, because a change made during one call is still present when the algorithm reaches later elements, and when it reaches the same element again on a later pass.

In what order the algorithm visits elements, and when it calls the predicate for each one.

Each visit receives one element as its argument and returns one yes or no answer. If the predicate changes the element during a visit, the sequence the algorithm is working through has already been altered by the time it finishes. Any later question that reads the same sequence sees the altered values.

A Safe Predicate in Code

The following example is an original illustration built for this article. It uses the C++ standard library's count-if algorithm, which walks a sequence and counts the elements for which a predicate returns true. The lambda used as the predicate is a function object. First, the safe version: the predicate receives each value and only compares it. Then a version that breaks the rule, so you can see the effect on the data.

Code walkthrough

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> values = {3, 8, 5, 10};

    // Safe predicate: reads its argument and answers a yes or no question.
    auto safe = std::count_if(values.begin(), values.end(),
                              [](int v) { return v > 6; });
    std::cout << "safe count: " << safe << std::endl;

    // Unsafe predicate: changes its argument while asking the question.
    auto unsafe = std::count_if(values.begin(), values.end(),
                                [](int& v) { v = v % 10; return v > 6; });
    std::cout << "unsafe count: " << unsafe << std::endl;

    std::cout << "values after unsafe predicate:";
    for (int v : values) {
        std::cout << " " << v;
    }
    std::cout << std::endl;
    return 0;
}

1
The vector starts as 3, 8, 5, 10.
2
The safe predicate asks whether each value is greater than 6. Only 8 and 10 qualify, so the count is 2, and the vector is unchanged.
3
The unsafe predicate first replaces each value with its remainder after dividing by 10. The value 10 becomes 0, and the question is then asked of the new value. Only 8 qualifies, so the count is 1.
4
After the unsafe call, the vector holds 3, 8, 5, 0. The question asked by the predicate has altered the data it was asking about.

The safe lambda takes its argument by value and only compares it.
The unsafe lambda takes its argument by reference, so assigning to it writes into the vector.
The unsafe count is correct for the values as they were modified, but the vector itself has been permanently changed.

Output

safe count: 2
unsafe count: 1
values after unsafe predicate: 3 8 5 0

Output

safe count: 2
unsafe count: 1
values after unsafe predicate: 3 8 5 0

Mistakes That Break the Rule

Common mistake
Letting the predicate keep a running total
What it looks like
A predicate that adds each value to a counter captured from outside and then tests the value.
Why it fails
The predicate changes state that the algorithm did not expect it to change, so the answer depends on how many times and in what order it was called.
Do this instead
Keep the predicate's answer a function of the value it receives. Store totals in the calling code, outside the predicate.
Common mistake
Normalizing the data inside the predicate
What it looks like
A predicate that trims or rescales the value before comparing it, as in the unsafe lambda above.
Why it fails
The normalization is written back into the sequence, so the data changes as a side effect of asking a question.
Do this instead
Compute the normalized value into a local variable, compare that local value, and leave the argument alone.
Common mistake
Taking the argument by non-const reference without need
What it looks like
Declaring the parameter as int& when the predicate only reads it.
Why it fails
A reference parameter gives the predicate the ability to write into the data, even when the code does not intend to.
Do this instead
Take the argument by value or by const reference when the predicate only needs to inspect it.
Common mistake
Assuming a predicate is safe because it eventually returns a yes or no answer

Practice Writing a Read-Only Predicate

EASY

Write a predicate that returns true for values greater than 6 and that never changes its argument. Then decide whether the following predicate is safe: a lambda that takes an int reference, adds 1 to it, and then returns whether it is greater than 6.

Hints

Take the argument by value or by const reference so the predicate can only read it.
Any assignment or increment applied to the parameter changes the element when the parameter is a reference.
The second predicate returns an answer, but it writes into the sequence while doing so.

Your attempt (not saved)

MEDIUM

Explain, in one or two sentences, why a predicate that keeps a running total is a problem even when its answers look correct on a single run.