Maps and Their Sequences of Key-Value Pairs

The next pair is nuts with 50.

Programming

A Warehouse Question and the Search Behind It

Imagine a warehouse inventory where each item name is paired with its stock count. A manager asks, "Which is the first item with more than 42 units on hand?" Answering this means checking entries one at a time until one meets a rule. The rule 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 follows that idea into programming. The central question is how a condition like "greater than 42" can be handed to an algorithm as an input, so that the same search routine works for many different rules. The condition has a name: a predicate. Keep the inventory picture in mind, because each section returns to a concrete search and follows what happens to each element as it is examined.

What a Predicate Is

Definition

A predicate is a specified requirement or condition that an element must fulfill. For each element an algorithm examines, the predicate must return a yes or no answer.

A predicate therefore has three parts that work together: the algorithm, which visits elements; the element, which is the thing being examined; and the requirement, which the element either meets or does not meet. The algorithm does not need to know what the requirement is. It only needs to ask the question and act on the yes or no answer.

Tracing the Search Through a Map

The source describes a search of a map of type map<string,int> for the first value larger than 42. The search examines pairs of type pair<const string,int> in sequence, and it tests the int in each pair against the requirement that it be greater than 42. The diagram below shows how each element moves through the search: the search takes one pair at a time, hands it to the predicate, and then either stops with that pair or moves on.

In what order does the search visit each pair, and what does the condition return for each one before the search moves on?

Read the trace step by step. The search starts at the first pair, bolts with 30. The predicate answers no, so the search advances. The next pair is nuts with 50. The predicate answers yes, so the search ends at that element. The pair washers with 45 is never examined, because the search usually stops at the first element that satisfies the requirement. The loop and the stopping rule stay the same no matter what condition is supplied; only the answer at the decision point depends on the rule.

Worked example

Following one search from start to finish

A map presents its pairs in this order: bolts with 30, nuts with 50, washers with 45. Find the first pair whose value is greater than 42.

1
Visit the first pair
The search takes bolts with 30 and gives it to the predicate. Is 30 greater than 42? No, so the search does not stop.
2
Visit the second pair
The search moves to nuts with 50 and asks the same question. Is 50 greater than 42? Yes, so the search stops here.
3
Stop without visiting the rest
The pair washers with 45 is not examined at all. Its value would also have passed the test, but the first match is the only one the search needs to return.

Result

The search returns nuts with 50.

Built-In Action Versus Supplied Predicate

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. A routine that searches for a count above 42 is the same routine that would search for a count above 100; 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.

The alternative 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 part that varies between calls, which is what makes the algorithm reusable.

How does an algorithm with a hard-coded action differ from one that accepts a predicate, and what changes when the caller passes a different condition?

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.

What the Predicate Actually Receives

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. The value is the int part. The diagram below shows the structure of that sequence, with each pair holding a key and a value.

What does a single element in the sequence contain, and which part of each pair does the predicate actually examine? The predicate examines the value part of each pair.

This matters for 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.

A Predicate Written in C++

The following program is a generated illustration of the idea. The function find_first is the algorithm: it owns the loop and the stopping rule. The predicate is passed in as a parameter named pred. The caller supplies a lambda that receives one pair and returns true or false.

cpp

#include <map>
#include <string>
#include <iostream>

template <typename Pred>
void find_first(const std::map<std::string, int>& m, Pred pred) {
    for (const auto& p : m) {
        if (pred(p)) {
            std::cout << p.first << " : " << p.second << std::endl;
            return;
        }
    }
    std::cout << "no match" << std::endl;
}

int main() {
    std::map<std::string, int> stock = {{"bolts", 30}, {"nuts", 50}, {"washers", 45}};
    find_first(stock, [](const std::pair<const std::string, int>& p) {
        return p.second > 42;
    });
}

#include <map>
#include <string>
#include <iostream>

template <typename Pred>
void find_first(const std::map<std::string, int>& m, Pred pred) {
    for (const auto& p : m) {
        if (pred(p)) {
            std::cout << p.first << " : " << p.second << std::endl;
            return;
        }
    }
    std::cout << "no match" << std::endl;
}

int main() {
    std::map<std::string, int> stock = {{"bolts", 30}, {"nuts", 50}, {"washers", 45}};
    find_first(stock, [](const std::pair<const std::string, int>& p) {
        return p.second > 42;
    });
}

Output

nuts : 50

Notes on the code

find_first owns the loop and the stop-on-first-match rule; it never changes between calls
pred(p) is the decision point where the supplied requirement is asked about the current pair
The lambda receives a whole pair and tests p.second, the int value part
Calling find_first with a different lambda changes the rule without touching the loop

What do you think happens?

Before reading the output: if the lambda's test were changed to p.second > 100, what would find_first print?

Reveal answer

Answer:

no match

No value in the map (30, 50, 45) is greater than 100, so pred never returns true, the loop finishes, and the fallback message is printed.

Mistakes When Writing or Reading a Predicate

Common mistake
Testing the key instead of the value
What it looks like
```
return p.first > 42; inside the lambda for a map<string,int>
```
Why it fails
p.first is the string key, and the requirement is about the int count. The predicate looks at the wrong part of the pair, so the comparison does not express the rule.
Do this instead
Test the value portion: return p.second > 42;
Common mistake
Treating the element as a bare integer
What it looks like
Writing a lambda that takes an int parameter and expects to receive only the count
Why it fails
The test receives a whole pair, not a bare integer, so the parameter type does not match what the search passes in.
Do this instead
Accept the pair, as in const std::pair<const std::string, int>& p, and read p.second inside the condition.
Common mistake
Returning something other than a yes or no answer
Why it fails
A predicate must return a yes or no answer for each element. The decision point only knows how to choose between two paths.
Do this instead
Make every path through the predicate return a true or false result.
Common mistake
Misreading where the search stops
Why it fails
The search usually stops at the first element that satisfies the predicate, so later matching elements are never examined. Reading the output as the last or all matches gives the wrong answer.
Do this instead
Trace the sequence in order and stop at the first yes.

Before

find_first(stock, [](const std::pair<const std::string, int>& p) {
    return p.first > 42;
});

The predicate tests the string key, so it does not express the count requirement and will not compile, because a string cannot be compared with 42.

After

find_first(stock, [](const std::pair<const std::string, int>& p) {
    return p.second > 42;
});

The predicate tests the int value part of the same pair and prints nuts : 50.

Practice Changing the Requirement

EASY

Keep find_first unchanged and write a new lambda that finds the first pair in the same stock map whose value is less than 40. Predict which pair the search returns before running it, and trace the sequence bolts, nuts, washers one element at a time.

Hints

Start with bolts, whose value is 30. Ask the predicate whether 30 is less than 40.
Stop at the first yes. The loop itself should not change at all.
Check that your lambda reads p.second rather than p.first.

Your attempt (not saved)

Key Takeaways

A predicate is a specified requirement or condition that an element must fulfill, returning a yes or no answer for each element an algorithm examines.
A map presents its contents as (key, value) pairs, so a predicate receives a whole pair and must examine the part it needs, such as the int value.
A search with a supplied predicate keeps the same loop and stopping logic on every call; only the test at the decision point changes.
The search usually stops at the first element that satisfies the predicate, so the trace must follow the sequence in order.
Common predicate mistakes include testing the key instead of the value, treating the element as a bare integer, and returning something other than a yes or no answer.

Related concepts

More concepts starting with M