The find Algorithm and Searching for Values

Imagine a warehouse inventory in which each item name is paired with a stock count. 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. Nothing about this question is a plain equality check. The manager is not looking for one exact count. The condition is a rule that changes from one question to the next.

This article looks at how that changing condition can be handed to an algorithm as an input. When the condition is an input, the same search routine can answer many different questions. We will return to the inventory example throughout, following what happens to each entry as it is examined.

A predicate must return a yes or no answer for each element it is given. In the inventory search, the predicate is the rule 'more than 42 units'. For each entry, the rule answers yes or no. The search usually stops at the first element that satisfies it, so the predicate is the part that decides when the search is finished.

Why does an algorithm need a predicate at all? Some algorithms have a fixed action built into their logic. They always do the same thing to each element they visit, which works well when the task never changes. In practice the task often differs from one call to the next. A search for a count above 42 uses the same looping logic as a search for a count above 100. The only difference is the rule being applied. Writing a separate search routine for each rule would repeat the same looping logic again and again. A predicate removes that repetition by letting the caller supply the rule.

There are two ways an algorithm can decide what to do with each element. In the first, the action is built in. The algorithm always performs the same test, and every call uses that same test. In the second, the action is supplied by the caller as a parameter. The algorithm keeps its looping and visiting logic, and the caller provides the piece that decides what each element must satisfy. The supplied piece is the part that varies between calls, and that is what makes the algorithm reusable.

Replacing the threshold, or replacing the whole test with a different condition, changes only the question asked at the decision point. Visiting elements in order and stopping on a match is reused unchanged. Read the comparison as two columns: the left column is fixed, and the right column is what a caller can swap.

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 string part is the key, which the map treats as fixed once an entry exists. The int part is the value.

The source describes a search of a map<string,int> for the first value larger than 42. The search examines pair<const string,int> elements in sequence and tests the int in each pair against the requirement that it be greater than 42. Here is the inventory traced as the search walks through it. Each pair is a name and a count, and the test is whether the count satisfies $value > 42$.

When an algorithm's action is a parameter, control moves in a predictable pattern. The algorithm starts at the beginning of the sequence, asks the supplied requirement about the current element, and chooses one of two paths based on the answer. A yes answer ends the search at that element. A no answer advances to the next element and repeats the question. The diagram below traces this cycle for a single pair.

The predicate is the only part of this cycle that knows the particular threshold. The traversal itself stays the same no matter what condition is supplied. This is why the same loop can answer a question about 42 today and a question about 100 tomorrow.