Lesson 10: Strings and Regular Expressions

Lesson 0010 — A Tour of C++, Chapter 10 (§10.1–§10.5)

Text manipulation is a major part of most programs. This chapter covers the three standard facilities for it: string — a regular type that owns a mutable sequence of characters, saving most users from C-style pointer manipulation of char arrays; string_view — a non-owning (pointer, length) pair for reading character sequences however they're stored; and regular expressions via std::regex for finding patterns in text. All three work with a variety of character types (e.g., Unicode).

10.1 Introduction

The C++ standard library offers a string type to save most users from C-style manipulation of arrays of characters through pointers. A string_view type allows us to manipulate sequences of characters however they may be stored (e.g., in a std::string or a char[]). Regular expression matching is offered to help find patterns in text, in a form similar to what is common in most modern languages. Both strings and regex objects can use a variety of character types (e.g., Unicode).

10.2 Strings

The standard library provides a string type to complement the string literals (§1.2.1); string is a regular type (§8.2, §14.5) — it can be default constructed, copied, compared with ==, and ordered — for owning and manipulating a sequence of characters of various character types. The most visible operation is concatenation:

string compose(const string& name, const string& domain) {
    return name + '@' + domain;
}
auto addr = compose("dmr","bell-labs.com");   // addr = "dmr@bell-labs.com"

"Addition" of strings means concatenation. You can concatenate a string, a string literal, a C-style string, or a character to a string. The standard string has a move constructor, so returning even long strings by value is efficient (§6.2.2).

In many applications the most common form of concatenation is adding something to the end of a string, directly supported by +=:

void m2(string& s1, string& s2) {
    s1 = s1 + '\n';   // append newline (creates a temporary)
    s2 += '\n';       // append newline (in place)
}

The two are semantically equivalent, but += is more explicit about what it does, more concise, and possibly more efficient — it appends in place instead of materializing a temporary.

A string is mutable: besides = and +=, subscripting ([]) and substring operations are supported:

string name = "Niels Stroustrup";
void m3() {
    string s = name.substr(6,10);   // s = "Stroustrup" (copy of substring)
    name.replace(0,5,"nicholas");   // name becomes "nicholas Stroustrup"
    name[0] = toupper(name[0]);     // name becomes "Nicholas Stroustrup"
}

substr() returns a copy of the substring; the first argument is an index (a position), the second is the length. Indexing starts from 0. replace() replaces a substring with a value — and the replacement need not be the same size as the substring it replaces. Among the many other operations: comparison (==, !=), lexicographical ordering (<, <=, >, >=), subscripting with [] or at() (as for vector, §12.2.2), iteration (begin(), end()), input (§11.3), and streaming (§11.7.3). Strings can be compared against each other, against C-style strings, and against string literals.

If you need a C-style string (a zero-terminated array of char), string offers read-only access to its contained characters via c_str() (and data()):

void print(const string& s) {
    printf("For people who like printf: %s\n", s.c_str());
}

A string literal is by definition a const char*. To get a literal of type std::string, use the s suffix (from std::literals::string_literals, §6.6):

auto cat = "Cat"s;   // a std::string
auto dog = "Dog";    // a C-style string: a const char*

10.2.1 string Implementation

Implementing a string class is a popular and useful exercise — but for general-purpose use, our carefully crafted first attempts rarely match the standard string in convenience or performance. These days, string is usually implemented using the short-string optimization (SSO): short string values are kept in the string object itself, and only longer strings are placed on free store:

string s1 {"Annemarie"};              // short string: fits in the object
string s2 {"Annemarie Stroustrup"};   // long string: on the free store

When a string's value changes from short to long (and vice versa), its representation adjusts appropriately. How many characters can a "short" string have? Implementation-defined — "about 14 characters" isn't a bad guess.

The actual performance of strings can depend critically on the run-time environment. In multi-threaded implementations, memory allocation can be relatively costly; and when lots of strings of differing lengths are used, memory fragmentation can result. These are the main reasons the short-string optimization has become ubiquitous.

To handle multiple character sets, string is really an alias for a general template basic_string with character type char:

template<typename Char> class basic_string { /* string of Char */ };
using string = basic_string<char>;

A user can define strings of arbitrary character types — e.g., for a Japanese character type Jchar: using Jstring = basic_string<Jchar>; — and do all the usual string operations on it.

10.3 String Views

The most common use of a sequence of characters is to pass it to some function to read. Options: pass a string by value, a reference to a string, a C-style string, or a non-standard string type. In all cases, passing a substring adds complexity. The standard answer is string_view: basically a (pointer, length) pair denoting a sequence of characters.

A string_view gives access to a contiguous sequence of characters, stored any which way — in a string, in a C-style string, wherever. Like a pointer or reference, it does not own the characters it points to; in that it resembles an STL pair of iterators (§13.3). Consider a function concatenating two character sequences:

string cat(string_view sv1, string_view sv2) {
    string res {sv1};          // initialize from sv1
    return res += sv2;         // append from sv2 and return
}

string king = "Harold";
auto s1 = cat(king, "William");        // HaroldWilliam: string and const char*
auto s2 = cat(king, king);             // HaroldHarold: string and string
auto s3 = cat("Edward", "Stephen"sv);  // EdwardStephen: const char* and string_view
auto s4 = cat("Canute"sv, king);       // CanuteHarold
auto s5 = cat({&king[0],2}, "Henry"sv);    // HaHenry
auto s6 = cat({&king[0],2}, {&king[2],4}); // Harold

This cat() has three advantages over a compose() taking const string& arguments (§10.2):

• It can be used for character sequences managed in many different ways.
• We can easily pass a substring.
• We don't have to create a string to pass a C-style string argument.

Note the sv ("string view") suffix, made visible via using namespace std::literals::string_view_literals; (§6.6). Why bother with a suffix? When we pass "Edward" we need to construct a string_view from a const char*, which requires counting the characters — for "Stephen"sv the length is computed at compile time.

A string_view defines a range, so we can traverse its characters:

void print_lower(string_view sv1) {
    for (char ch : sv1) cout << tolower(ch);
}

One significant restriction: a string_view is a read-only view of its characters — you cannot use one to pass characters to a function that modifies its argument. For writing, consider a span (§15.2.2).

Think of a string_view as a kind of pointer; to be used, it must point to something:

string_view bad() {
    string s = "Once upon a time";
    return {&s[5],4};   // bad: returning a pointer to a local
}                        // s is destroyed before the view is used

The behavior of out-of-range access to a string_view is undefined. If you want guaranteed range checking, use at() (which throws out_of_range for attempted out-of-range access) or gsl::string_span (§15.2.2).

10.4 Regular Expressions

Regular expressions are a powerful tool for text processing: they provide a way to simply and tersely describe patterns in text (e.g., a U.S. postal code such as TX 77845, or an ISO-style date such as 2009-06-07) and to efficiently find such patterns. In <regex>, the standard library provides support in the form of the std::regex class and its supporting functions:

• regex_match() — match a regular expression against a string (of known size) (§10.4.2).
• regex_search() — search for a string that matches a regular expression in an (arbitrarily long) stream of data (§10.4.1).
• regex_replace() — search and replace matches.
• regex_iterator — iterate over matches and submatches (§10.4.3).
• regex_token_iterator — iterate over non-matches.

Regular expressions are compiled into state machines for efficient execution [Cox, 2007]; the regex type performs this compilation at run time. Define a pattern:

regex pat {R"(\w{2}\s*\d{5}(-\d{4})?)"};   // U.S. postal code pattern: XXddddd-dddd and variants

The pattern starts with two letters (\w{2}), optionally followed by some space (\s*), followed by five digits (\d{5}), and optionally followed by a dash and four digits (-\d{4}). I use a raw string literal starting with R"( and terminated by )" — this allows backslashes and quotes to be used directly in the string. Raw strings are particularly suitable for regular expressions because they tend to contain a lot of backslashes. Had I used a conventional string, the pattern would have been "\\w{2}\\s*\\d{5}(-\\d{4})?" — every backslash doubled.

10.4.1 Searching

The simplest way of using a pattern is to search for it in a stream:

int lineno = 0;
for (string line; getline(cin,line); ) {   // read into line buffer
    ++lineno;
    smatch matches;                        // matched strings go here
    if (regex_search(line, matches, pat))  // search for pat in line
        cout << lineno << ": " << matches[0] << '\n';
}

regex_search(line, matches, pat) searches the line for anything matching pat and stores the matches in matches; it returns false if nothing matched. smatch is a vector of submatches of type string — the "s" stands for "sub" or "string". The first element, matches[0], is the complete match. With an ifstream, the same loop reads a file looking for U.S. postal codes; for an optional subpattern we check matches[1].matched before printing it, since the optional group (-\d{4})? may be absent. The newline character \n can be part of a pattern, so multiline patterns are possible — but then we obviously shouldn't read one line at a time.

10.4.2 Regular Expression Notation

The regex library can recognize several variants of regular expression notation. The default is a variant of the ECMA standard used for ECMAScript (more commonly known as JavaScript). The syntax is based on special characters:

Example: a line starting with zero or more A's, followed by one or more B's, followed by an optional C — ^A*B+C?$. Matches: AAAAAAAAAAAABBBBBBBBBC, BC, B. Does not match: AAAAA (no B), AAAABC (initial space), AABBCC (too many C's).

A part of a pattern is considered a subpattern (which can be extracted separately from an smatch) if it is enclosed in parentheses:

\d+-\d+      // no subpatterns
\d+(-\d+)    // one subpattern
(\d+)(-\d+)  // two subpatterns

A pattern can be optional or repeated (default: exactly once) with a suffix:

A suffix ? after any repetition notation makes the pattern matcher lazy (non-greedy): it looks for the shortest match rather than the longest. By default the matcher always looks for the longest match — the Max Munch rule. For ababab, (ab)+ matches all of ababab, while (ab)+? matches only the first ab.

The most common character classifications have names, written in a regular expression as [[:name:]] (bracketed by [: :], used within a [] character class): alnum, alpha, blank (whitespace that is not a line separator), cntrl, d / digit, graph, lower, print, punct, s / space, upper, w (word character: alphanumeric plus underscore), xdigit. Several shorthand abbreviations are also supported:

Languages supporting regexes often also provide \l / \u (lower/upper) and \L / \U (their negations) — but these are nonstandard. For full portability, use the character class names rather than these abbreviations.

Consider a pattern describing C++ identifiers: an underscore or a letter, followed by a possibly empty sequence of letters, digits, or underscores. To illustrate the subtleties, a few false attempts:

[:alpha:][:alnum:]*              // wrong: characters from the set ":alpha" followed by ...
[[:alpha:]][[:alnum:]]*          // wrong: doesn't accept underscore ('_' is not alpha)
([[:alpha:]]|_)[[:alnum:]]*      // wrong: underscore is not part of alnum either
([[:alpha:]]|_)([[:alnum:]]|_)*  // OK, but clumsy
[[:alpha:]_][[:alnum:]_]*        // OK: include the underscore in the character classes
[_[:alpha:]][_[:alnum:]]*        // also OK
[_[:alpha:]]\w*                  // \w is equivalent to [_[:alnum:]]

The classic mistakes: forgetting the [: :] brackets, and forgetting that _ is neither alpha nor alnum — it must be added to the classes explicitly (or handled via \w). The simplest usable version:

bool is_identifier(const string& s) {
    regex pat {R"([_[:alpha:]]\w*)"};   // underscore or letter, then zero or more \w
    return regex_match(s, pat);
}

Note that regex_match() matches the complete input — exactly what "is this whole string an identifier?" needs.

A group (a subpattern) is delimited by parentheses. If you need parentheses that should not define a subpattern, use (?: rather than plain (:

(\s|:|,)*(\d*)     // optional spaces, colons, commas, then an optional number
(?:\s|:|,)*(\d*)   // same, but the separators are not stored as a submatch

The (?: variant saves the engine from having to store the first characters — it has only one subpattern.

The last pattern finds XML tag/end-tag markers. Note the non-greedy .*? for the text between tags: with plain greedy .*, matching <b>bright</b> side of <b>life</b> would pair the first < with the last > — correct behavior for a regex, but unlikely what the programmer wanted.

10.4.3 Iterators

We can define a regex_iterator to iterate over a sequence of characters finding matches for a pattern. A sregex_iterator (a regex_iterator<string>) outputs all whitespace-separated words in a string:

void test() {
    string input = "aa as; asd ++e^asdf asdfg";
    regex pat {R"(\s+(\w+))"};
    for (sregex_iterator p(input.begin(), input.end(), pat);
         p != sregex_iterator{}; ++p)
        cout << (*p)[1] << '\n';   // the first submatch of each match
}
// outputs: as  asd  asdfg  — the first word "aa" is missed (no preceding whitespace)

Simplifying the pattern to R"((\w+))" captures every word: aa as asd e asdf asdfg. A regex_iterator is a bidirectional iterator — so we cannot directly iterate over an istream (which offers only an input iterator). We cannot write through a regex_iterator, and the default regex_iterator{} is the only possible end-of-sequence.

10.5 Advice

Here is a summary of the guidance from this chapter. All 28 items, with the section where each is introduced. The C++ Core Guidelines link each item to its recommended practice.

Retrieval Quiz

Notes

Primary source: Stroustrup, B. (2022). A Tour of C++, 3rd ed., Chapter 10: "Strings and Regular Expressions." Addison-Wesley.
Reference: Chapter 1–10 Quick Reference & Glossary — keep it beside you while you study.
Recommended supplement: cppreference on std::basic_string, std::string_view, regular expressions, and string literals.

Questions? Ask your agent — your teacher — about anything unclear: when a string_view dangles, why a regex pattern needs doubling in ordinary strings, or how Max Munch bites XML parsing. Follow-ups are expected, not optional.

Chapters

1. Lesson 1: The Basics (Ch. 1)
2. Lesson 2: User-Defined Types (Ch. 2)
3. Lesson 3: Separate Compilation (Ch. 3)
4. Lesson 4: Error Handling (Ch. 4)
5. Lesson 5: Classes (Ch. 5)
6. Lesson 6: Essential Operations (Ch. 6)
7. Lesson 7: Templates (Ch. 7)
8. Lesson 8: Concepts and Generic Programming (Ch. 8)
9. Lesson 9: Library Overview (Ch. 9)
10. Lesson 10: Strings and Regular Expressions (Ch. 10 — this lesson)
11. Lesson 11: Input and Output (Ch. 11)
12. Lesson 12: Containers (Ch. 12)
13. Lesson 13: Algorithms (Ch. 13)
14. Lesson 14: Ranges (Ch. 14)
15. Lesson 15: Pointers and Containers (Ch. 15)
16. Lesson 16: Utilities (Ch. 16)
17. Lesson 17: Numerics (Ch. 17)
18. Lesson 18: Concurrency (Ch. 18)
19. Lesson 19: History and Compatibility (Ch. 19)