Searching in Strings

A string is one of the most common kinds of data a program handles. Names, messages, file paths, and user input are all strings. When you write a string literal or read text from a user, you usually think of the text as a single value. That is a useful way to think about it at first, but working with strings effectively requires a more detailed picture of what that value is and how a program can reach into it. This article introduces that picture. It is the starting point for the rest of the chapter, because searching, regular expression notation, and iterators all depend on it.

The section introduces a simple model. Picture a row of numbered slots with one character in each slot. The slot numbers are the positions. Reading a character means naming its position. Searching, pattern matching, and iteration all reduce to ways of visiting or comparing these slots in some order. Hold this picture in mind as you follow the diagram below, which traces the three characters of cat.

Notice what the diagram shows. Each slot holds exactly one character. The slots are arranged in a definite order, so the first character comes before the second and the second before the third. The position number is what lets a program say which character it means. Nothing about this model depends on the particular characters or on how long the string is. It applies to any string, whatever its length.

The word ordered is the important part. Order is what makes a string more than a bag of letters. If you had only the letters c, a, and t with no order attached, you could not say which one comes first. Because a string keeps its characters in order, every character has a place that can be referred to, and two strings made of the same letters can still differ when their letters are arranged differently.

Once a string is seen as a sequence, the next question is how its positions are counted. Many programming languages, including C++, number the characters of a string starting from 0 rather than 1. The first character is at position 0. A string with n characters therefore has positions running from 0 up to n minus 1, which can be written as $0 \leq i \leq n-1$ for any valid position i. The last character is always at length minus 1, not at the length itself.

This convention is worth fixing in your mind early. It affects nearly every operation that touches a string's contents, because every search result, every iteration, and every reference to a character is expressed as one of these numbers. If you count from 1 by habit while the string counts from 0, the numbers you compute will point at the wrong characters.

The section names searching as the first of three ways to work with string contents. Searching asks where a piece of text occurs. Its answer is a position: when the pattern is found, the search returns the position of the match, and when it is not found, the search returns a not-found result instead. The flowchart below illustrates the general idea of how a search can move through the ordered positions to reach that answer. It is a generic illustration of visiting slots in order, not a description of one particular library's internals.

Read the flowchart as a loop over the same numbered slots from the earlier diagram. Each pass checks one position, and the loop ends in one of two results. A found result is a position number, which you can then use to refer to the matched character. A not-found result is a different kind of answer, so a program must be prepared to handle it rather than assume a position was always returned.

The section introduces three topics that build on the sequence model. Each one answers a different question about a string, so it helps to keep them apart. The table below compares what each operates on and what it gives back, based on the roles the section assigns to each.

All three rely on the fact that positions are ordered. That shared dependence is why the chapter presents them in sequence, and why this article covers the ordered model before any of them. The later articles will describe the details of each topic, so here the goal is only to recognise the three roles and the common foundation beneath them.

An off-by-one error happens when a position is one too large or one too small. Because the numbering starts at 0, the most common version is treating the length as if it were a valid position. The diagram below compares the intended last character of cat with the position an off-by-one mistake would point to.

The before side shows the correct reasoning: the last character is at length minus 1, which is position 2. The after side shows the error: position 3 is the length, and it does not name any character in cat. The fix is to subtract 1 from the length whenever you need the last position, and to remember that valid positions stop one short of the length.