Regular Expression Functions and Iterators

A regular expression iterator, std::regex_iterator, iterates over matches and submatches of a pattern in a string.

Programming

Finding Every Place a Pattern Applies

A regular expression describes a pattern, and a search with that pattern can find many places in a string where the pattern applies. Knowing that a match exists is only the first step. Often a program needs to visit each result in turn: each place where the pattern matched, or each stretch of text the pattern did not match. The C++ regular expression library provides iterators for exactly this purpose.

An iterator is an object that moves through a sequence one element at a time. The regex iterators move through the results of a pattern search. In this article you will meet two of them, and you will see that they answer two different questions about the same text.

Two Iterators, Two Questions

Definition

A regular expression iterator, std::regex_iterator, iterates over matches and submatches of a pattern in a string.

Definition

A regular expression token iterator, std::regex_token_iterator, iterates over non-matches, the pieces of text between matches.

Both iterators work on the same kind of input, but they answer different questions about the same text. The regex iterator asks which parts of the text the pattern matched. The token iterator asks which parts the pattern did not match. Because these two questions cover the whole string between them, a program that needs every piece of the text can run one loop of each kind.

What the Match Iterator Visits

A regex iterator is constructed from three things: the beginning and end of the input text, and the pattern. A default-constructed iterator serves as the end marker. A loop advances the iterator with ++ and stops when it reaches the end marker. Each time the iterator is dereferenced, it gives access to the current match, and that match can be converted to a string to read its text.

The source describes the regex iterator as visiting matches and submatches. A match is the piece of text the whole pattern matched. Submatches are the parts of a match that the pattern captures separately. The iterator therefore gives you the matched pieces as its primary output, and each match it yields is a result you can read as text.

cpp

#include <iostream>
#include <regex>
#include <string>

int main() {
    const std::string text = "a cat, a bat";
    const std::regex pattern("[cb]at");

    std::sregex_iterator it(text.begin(), text.end(), pattern);
    std::sregex_iterator end;   // default-constructed end marker

    for (; it != end; ++it) {
        std::cout << it->str() << "\n";
    }
}

#include <iostream>
#include <regex>
#include <string>

int main() {
    const std::string text = "a cat, a bat";
    const std::regex pattern("[cb]at");

    std::sregex_iterator it(text.begin(), text.end(), pattern);
    std::sregex_iterator end;   // default-constructed end marker

    for (; it != end; ++it) {
        std::cout << it->str() << "\n";
    }
}

Output

cat
bat

Notes on the code

The iterator is built from the start and end of the text plus the pattern.
The default-constructed iterator end serves as the stop condition.
++ moves the iterator to the next match.
Dereferencing the iterator and calling str() reads the matched text.

What the Token Iterator Visits

The token iterator takes one extra argument that selects what it yields. In the C++ library this argument is a submatch index. The value -1 asks the iterator to yield the non-matching pieces of the input rather than the matches. The token iterator therefore walks the text in the gaps that the pattern leaves behind.

Because the matches and the non-matches together make up the whole input, a token iterator over non-matches shows exactly the text that a match iterator skipped. Nothing in the string is lost between the two views: each piece of text appears in exactly one of the two lists.

cpp

#include <iostream>
#include <regex>
#include <string>

int main() {
    const std::string text = "a cat, a bat";
    const std::regex pattern("[cb]at");

    std::sregex_token_iterator it(text.begin(), text.end(), pattern, -1);
    std::sregex_token_iterator end;

    for (; it != end; ++it) {
        std::cout << "[" << it->str() << "]\n";
    }
}

#include <iostream>
#include <regex>
#include <string>

int main() {
    const std::string text = "a cat, a bat";
    const std::regex pattern("[cb]at");

    std::sregex_token_iterator it(text.begin(), text.end(), pattern, -1);
    std::sregex_token_iterator end;

    for (; it != end; ++it) {
        std::cout << "[" << it->str() << "]\n";
    }
}

Notes on the code

The fourth argument -1 asks for the non-matching pieces.
The same pattern and text are used as in the match loop, so the two loops can be compared directly.

Tracing a Match Loop Step by Step

Take the string a cat, a bat and the pattern that matches cat or bat. Counting character positions from zero, cat occupies positions 2 to 4 and bat occupies positions 9 to 11. A match loop begins on the first match, cat. Each ++ moves the iterator forward to the next match, bat. One more ++ reaches the end marker and the loop stops. The loop visits exactly two elements, and the gap text between them is never produced.

After each increment, which match does the regex iterator point to, and where in the string does that match begin and end?

Tracing a Token Loop Through the Gaps

Now run the token loop over the same string with -1. The first piece is the text before the first match: the letter a and a space, which occupies positions 0 and 1. The second piece is the match cat, but the token iterator with -1 skips it. The third piece is the gap between the two matches, the comma, space, a, and space, which is a non-match. The fourth piece is bat, which is again a match and is skipped. The sequence of non-matches the loop yields is therefore the first gap followed by the middle gap.

In what order does a token iterator with -1 produce the pieces of the string, and where do the non-matching gaps fall relative to each match?

The diagram lays out the pieces in the order a loop over the token iterator encounters them. It reads from left to right. The first position is a non-match, the second is a match, the third is a non-match, and the fourth is a match. A loop that uses only the match iterator would visit positions one and three. A loop that uses the token iterator with -1 would visit positions zero and two, which are the gaps.

Comparing What Each Loop Produces

Given the same pattern and input, how do the elements visited by the regex iterator and the token iterator differ?

Feature	Regex iterator	Regex token iterator
Standard type	std::regex_iterator	std::regex_token_iterator
What it visits	Matches and submatches	Non-matches, the pieces between matches
Extra argument	None beyond the text and pattern	A submatch index; -1 selects non-matches
Answers the question	Which parts did the pattern match?	Which parts did the pattern not match?
Example output for a cat, a bat	cat, bat	a , a

Two iterators over the same input and pattern

Because the two iterators split the same string into complementary parts, you can use them together. The match loop gives you the parts the pattern identified, and the token loop gives you the parts it left alone. Between them they account for all of the text in the string.

Mistakes Beginners Make With These Iterators

Common mistake
Expecting the token iterator to yield matches by default
Why it fails
The token iterator selects its output through the submatch argument. Without the value -1, the token iterator is not asking for non-matches, so it is not the tool for the gap pieces.
Do this instead
Pass -1 as the final argument when you want the non-matching pieces of the input.
Common mistake
Forgetting the end marker
Why it fails
A loop over either iterator needs a stopping condition. The default-constructed iterator is the end marker, and the loop stops when the iterator reaches it.
Do this instead
Create a default-constructed iterator of the same type and compare the working iterator against it in the loop condition.
Common mistake
Reading only the match loop and assuming the rest of the text is missing
Why it fails
The text between matches is not lost. It is simply not visited by the match iterator, and the token iterator with -1 visits exactly that text.
Do this instead
Run the token loop over the same string when you need the skipped text.
Common mistake
Mixing up the two iterator types when reading a program, since both work on the same input and pattern

Practice Tracing Both Loops

MEDIUM

Using the string a cat, a bat and the pattern [cb]at, write down the sequence of pieces a regex iterator yields, then the sequence a token iterator with -1 yields. Check that every character of the string appears in exactly one of your two lists.

Hints

Start with the first match, then list the text before it as a non-match.
The match iterator skips the gaps, and the token iterator skips the matches.
The trailing position after bat has no characters, so it does not appear in either list.

Your attempt (not saved)

Key Takeaways

A regular expression iterator, std::regex_iterator, iterates over matches and submatches of a pattern in a string.
A regular expression token iterator, std::regex_token_iterator, iterates over non-matches, selected with the submatch value -1.
A regex iterator is built from the start and end of the text and the pattern, and a default-constructed iterator serves as the end marker.
A match loop and a non-match loop over the same string together account for all of the text in that string.

Related concepts

More concepts starting with R