Standard Algorithms and Containers

Many programs are checked by small tests. A test runs a function on known input and looks for anything unexpected. The test in this article checks find_all(), a function that searches a string for every occurrence of one character. Before you read any explanation, read the test itself and notice what it does with each result it receives.

The test contains no list of expected output and no counting. It makes one promise: every position that find_all() reports should hold an 'a'. If that promise is broken even once, a message appears. The test is therefore about the quality of each individual result, not about how many results there are.

A test that prints nothing is easy to misread. A beginner may think the test never ran, or that the function returned nothing at all. The way to tell the difference is to remember what the loop does. The loop runs once for each match, so a silent run still means that find_all() produced matches and that each of them was checked.

An iterator is a handle that refers to one place inside a container. The places in a C++ string are numbered from zero, so the first character sits at position 0, the next at position 1, and so on. An iterator tells you which place it is pointing to. It does not carry the letter itself. The letter is found by looking at the place the iterator refers to.

The distinction between the position and the value is the key to reading the test. The check does not ask where the iterator is. It asks what the iterator refers to. Two iterators can refer to different positions and still hold the same letter, and an iterator at position 1 is not the same thing as the character a.

The loop variable p starts at the first match that find_all() returns. Each time the loop body finishes, p moves on to the next match, and the loop body runs again with p pointing at that match. The loop stops when no matches remain. In this way the loop variable uses the iterators returned by find_all() to visit every match in turn.

Each iteration examines one result and only that result. The loop does not compare the matches with one another, and it does not keep a total. Its only job is to ask, for the current match, whether the value it refers to is an 'a'.

To see the test succeed in detail, trace the string by hand. Count positions from zero. The table below shows the first six characters of the text and marks each one as accepted or rejected, along with the 'a' positions that appear later in the string. The full string has 22 characters, and the four 'a' positions found in it are 1, 6, 9 and 19.

The four positions in this trace are a generated check of the source example rather than a fact the source states. Their value is that they show what a correct result looks like, so you have something to compare against when a result does not match.

Now suppose find_all() were broken and reported a position that holds a different letter, such as the r at position 2. The loop would reach that result and the if condition would become true, so the message bug! would appear. The output alone tells you that a mismatch happened, but not which result caused it.

The divergence is at the single loop iteration where the character under p is not 'a'. In the broken example, that is the iteration whose match sits at position 2. Every earlier iteration stayed silent, and every later one would only be checked after the message had already been printed in that earlier iteration.

So far find_all() has been used on a string, but the idea behind it is not tied to strings. The principle that makes this possible is that iterators and standard algorithms behave the same way on every standard container for which their use makes sense. An algorithm does not need to know which kind of container it is working with, as long as the container provides the iterators the algorithm needs.

Because the algorithm only asks for iterators, the same search can be written to work on other standard containers instead of searching only a string for a character. The test would still express the same expectation in that case: every match reported should satisfy the condition being searched for. The string and the other container types share the iterator interface, and that shared interface is what lets one generic find_all() operate on all of them.