Standard-Library Search Algorithms

Suppose you need a small yes-or-no function. Given a string and a character, it should report whether that character appears anywhere in the string. You could write a loop yourself that walks through the characters one at a time. The standard library, however, already offers a search algorithm that does the scanning for you. This article starts with a working function that uses that algorithm, so you can see its behavior before we explain the mechanism behind it.

Read the function once and keep it in mind as you go through the rest of this article. The questions that follow are not about how find scans internally. They are about what find gives back and how that value is tested. Notice that to predict the answer for a given input, you do not need to know the scanning details. You only need to know what the call returns and how the caller tests that value.

The key idea to hold onto is this: the return value of find is always an iterator. It is never a plain character and never a yes-or-no flag. Because the result is an iterator, the caller is responsible for deciding what that iterator means. If find locates a matching element, the iterator points at that element. If it does not, the iterator is the same value that end() produces. Both outcomes come back through the same kind of value, so the caller has to test which one happened.

In the diagram, the position holding t is the one the returned iterator refers to. Suppose instead you searched for a character that does not appear anywhere in cat, such as z. The search would walk past every real position, never find a match, and return the value that end() refers to. The returned iterator in that case does not point at any character in the string at all. It is simply the boundary marker that signals the search ran out of range.

The test p != s.end() is the entire decision in has_c. The variable p holds whatever find returned. If p is different from s.end(), then find stopped at a real matching position, so the character is present. If p equals s.end(), then find ran out of range without a match, so the character is absent. The comparison never inspects the character itself. It only checks where the iterator points. Because of this, the same test works for any element type that find can search, not only characters.

The source gives a second way to write the same function. Instead of storing the iterator in a named variable and using an if statement, you can return the comparison directly. The two versions perform the same search and the same comparison, so they return the same result for every input. The direct version is shorter, while the first version makes the intermediate iterator easy to see. Both are correct, and you can choose whichever reads more clearly to you.

Now consider how find reaches its result. It moves through the range one element at a time, starting at the first position. At each element it asks whether the element matches the value being searched for. If it does, the search stops immediately and returns an iterator to that element. If it does not, the search moves on to the next element. If the search reaches the end of the range without a match, it stops and returns end(). In other words, a match causes an early stop, while a miss causes the search to run all the way to the end.

The range that find searches is described by two iterators: begin() and end(). The range includes the element at begin() but stops before end(). This is why end() is called a sentinel: it marks the position just past the last element rather than an element itself. Because end() is not a real element, it must never be read, and it is the value you compare against to detect a failed search. The position begin() is the first element that find examines, while end() is the boundary where the scan ends if nothing matches.