Using Predicates with Algorithms

Imagine a warehouse inventory listed as item names paired with stock counts. A manager asks, "Which is the first item with more than 42 units on hand?" Answering that question means checking entries one at a time until one of them meets a rule. The rule here is not a plain equality check, as it would be if you were looking for one exact count. It is a condition that changes from one question to the next.

This article looks at how that condition can be handed to an algorithm as an input, so that the same search routine works for many different rules. The inventory picture stays in mind throughout. Each section returns to a concrete search and follows what happens to each element as it is examined.

Some algorithms have a fixed action built into their logic. They always do the same thing to each element they visit. That works well when the task never changes. In many practical cases, however, the task differs from one call to another. The routine that searches for a count above 42 is the same routine that would search for a count above 100, and the only difference is the rule being applied.

Writing a separate search routine for each rule would duplicate the same looping logic again and again. Every copy would visit elements in the same order, stop at the same kind of point, and differ only in one comparison. The effort of maintaining that duplicated looping logic grows with every new rule.

The alternative to a fixed action is to treat the requirement as something the caller supplies. The algorithm keeps the looping and visiting logic, and the caller provides the piece that decides what each element must satisfy. That supplied piece is the one that varies between calls, which is what makes the algorithm reusable.

The practical benefit is that the caller can change the search rule without touching the loop. Replacing the threshold, or replacing the whole test with a different condition, changes only the question asked at the decision point. The surrounding machinery of visiting elements in order and stopping on a match is reused unchanged.

A map stores associations between keys and values. To search a map with a predicate, we need to know what the algorithm actually sees as its elements. A map gives access to its contents as a sequence of (key, value) pairs. In C++ terms, a map<string,int> presents its elements as pair<const string,int> objects. The key is the string part, which the map treats as fixed once an entry exists, and the value is the int part.

This structure matters when writing a predicate. The test does not receive a bare integer when searching a map of this kind. It receives a whole pair, so the condition must look at the value portion of that pair to decide whether it qualifies. A predicate that ignores this structure will not behave as the reader expects.

The search in the diagram takes one pair at a time and hands it to the predicate. The first pair fails the test, so the search advances. The second pair passes, so the search stops there and the third pair is never examined. The predicate is the only part that knows the threshold of 42. The traversal itself stays the same no matter what condition is supplied.

The control flow follows a predictable pattern. The algorithm starts at the beginning of the sequence and asks the supplied requirement about the current element. A yes answer ends the search at that element. A no answer advances to the next element and repeats the question. The flowchart later in this article traces this same cycle for a different search.

When find locates a match, the iterator points at the first matching position, which is the first l in hello here. When nothing matches, the iterator equals end(), the position just past the last element. In the diagram, end() is shown after the final character, because it marks the boundary of the range rather than a real element.

The source describes this as a convention shared by many standard-library search algorithms: they return end() to signal that nothing was found. Once you recognize that convention, you can apply the same reasoning to other searches as well.

The decision is a single comparison. The variable holding the returned iterator is compared with s.end(). If the two differ, find stopped at a real matching position. If they are the same, find ran out of range without a match. The comparison does not inspect the character itself, so the same test works for any element type that find can search, not only characters.

Suppose you need a small yes-or-no function: given a string and a character, report whether that character appears anywhere in the string. You could write a loop yourself, but the standard library already offers a search algorithm that does the scanning for you. The function below uses find so you can see the behavior, and the explanation follows from what find returns.

The same behavior can be written more compactly by returning the comparison directly. The two versions perform the same search and the same comparison, so they return the same result for every input.

Running the same function with 'c' instead of 'z' takes a different path. The search would stop at the first character, the comparison would find a real position, and the function would return true. The difference between the two cases lies entirely in what find returned.