When to Use string and When Not To

Kenji wrote a helper that finds where a word ends, and called it once for every word of a 60,000-character text. The answers were right, and the program crawled. He started rewriting the loop, as he does. Amara read the helper's first line, size_t word_end(const string text, size_t start), and added one character: &. The program became well over a hundred times faster. This lesson is about that one character, and about the other times a string is not the tool.

Four questions about your text

A string is the right default for text, but not for every job. Four questions settle almost every case.

To own characters means to hold them in memory you are responsible for, and to free that memory when you are done. A string owns its characters. A view, which this lesson meets below, only looks at characters that something else owns. Kenji's answers: many characters, text, and owned by the caller, because his helper only reads them. Question 3 sends him away from a by-value string parameter. So the questions name the type before you write the line.

The comparison chart

Here are the five types side by side. A char array is C's char name[20]; a const char* is a pointer to the first character of text that ends with '\0', like a string literal. The cells follow each type's page on cppreference. n is the number of characters.

Read the string column top to bottom: it owns, knows its length, grows, and still hands C a '\0'-ended text through c_str(). Its one price is the copy, O(n). The two columns that copy in O(1), const char* and string_view, pay with the last row. They hold no characters of their own, so when the owner goes, they point at nothing. A vector<char> owns and grows like a string but promises no '\0' and offers no text functions such as find. So the cheap copies are the unsafe ones, and the safe ones copy.

The decision flowchart

The same questions as a flowchart, in the order to ask them. Start at the top and follow your answers.

Kenji's walk: many characters, text, and owned by the caller, so the third box sends him right, to const string& or string_view. The last line is the honest one about letters. Lesson 01 showed that Maria's name in Bangla has size 21 for 7 code points. And one letter on screen can be more than one code point. Counting what a reader sees as letters needs Unicode rules. ICU (International Components for Unicode) is the library that holds them; Chromium and Android both ship it. This track does not teach it; it is the name to search for when you need it.

Passing text to a function: by value, const& or string_view

How a function takes its text says what it may do with it, and what each call costs.

Here is Kenji's helper written three ways, each called once per word of the same text. word_end returns the position of the next space after start, or the text's size when there is none. The program times each loop with chrono::steady_clock, a clock that only moves forward.

#include <chrono>
#include <iostream>
#include <string>
#include <string_view>
using namespace std;

size_t word_end_by_value(const string text, size_t start) {
    size_t space = text.find(' ', start);
    return space == string::npos ? text.size() : space;
}

size_t word_end_by_ref(const string& text, size_t start) {
    size_t space = text.find(' ', start);
    return space == string::npos ? text.size() : space;
}

size_t word_end_by_view(string_view text, size_t start) {
    size_t space = text.find(' ', start);
    return space == string_view::npos ? text.size() : space;
}

int main() {
    string text;
    for (int k = 0; k < 3000; k++) {
        text += "Bob fixes bugs fast ";
    }

    auto t0 = chrono::steady_clock::now();
    size_t a = 0;
    for (size_t i = 0; i < text.size();) {
        size_t end = word_end_by_value(text, i);
        a += end - i;
        i = end + 1;
    }
    auto t1 = chrono::steady_clock::now();
    size_t b = 0;
    for (size_t i = 0; i < text.size();) {
        size_t end = word_end_by_ref(text, i);
        b += end - i;
        i = end + 1;
    }
    auto t2 = chrono::steady_clock::now();
    size_t c = 0;
    for (size_t i = 0; i < text.size();) {
        size_t end = word_end_by_view(text, i);
        c += end - i;
        i = end + 1;
    }
    auto t3 = chrono::steady_clock::now();

    chrono::duration<double, milli> va = t1 - t0, vb = t2 - t1, vc = t3 - t2;
    cout << text.size() << " characters, 12000 calls each\n";
    cout << "by value:       " << a << " letters, " << va.count() << " ms\n";
    cout << "by const&:      " << b << " letters, " << vb.count() << " ms\n";
    cout << "by string_view: " << c << " letters, " << vc.count() << " ms\n";
    return 0;
}

60000 characters, 12000 calls each
by value:       48000 letters, 16.6773 ms
by const&:      48000 letters, 0.087271 ms
by string_view: 48000 letters, 0.09158 ms

One run on Compiler Explorer, GCC 12 at -O2 -std=c++17, the Playground's flags. In eleven runs of the same program, by value took 15.8 to 32.6 ms and const& 0.07 to 0.11 ms, so by value was between 152 and 405 times slower in each run. string_view matched const& in ten runs and took 0.94 ms in one. Every by-value call copied all 60,000 characters into a new buffer and freed it again: 12,000 calls, about 720 million bytes. A run that counted allocations saw 12,000 for the 12,000 calls, so the compiler skipped none of the copies.

The const in const string text did not help, because it only stops the function from changing its own copy. The copy is made anyway. So a read-only parameter is const string& or string_view, and here the two cost the same.

string_view: a pointer and a length

A string_view, from <string_view> in C++17, is a view: it holds a pointer to someone else's characters and how many of them to look at. Making one costs O(1), copying one costs O(1), and so does its substr, which only moves the pointer and changes the length. It has most of a string's reading functions, size, [], find and substr among them, and nothing that changes the characters.

#include <iostream>
#include <string>
#include <string_view>
using namespace std;

int main() {
    string text = "Maria asks why, every time";
    string_view all = text;
    string_view who = all.substr(0, 5);
    string_view what = all.substr(6, 8);

    cout << "sizeof(string_view): " << sizeof(string_view) << " bytes\n";
    cout << "who:  [" << who << "] starts " << who.data() - text.data() << " bytes into text\n";
    cout << "what: [" << what << "] starts " << what.data() - text.data() << " bytes into text\n";

    text[0] = 'm';
    cout << "after text[0] = 'm', who is [" << who << "]\n";
    return 0;
}

sizeof(string_view): 16 bytes
who:  [Maria] starts 0 bytes into text
what: [asks why] starts 6 bytes into text
after text[0] = 'm', who is [maria]

On GCC 12 for a 64-bit machine a view is 16 bytes, an 8-byte pointer and an 8-byte length, however long the text. data() gives the view's pointer, and both views point inside text, at 0 and at 6. When text changed, who showed the change, because it never had characters of its own. So a view is a window onto the text, not a copy of it.

The trap: a view that outlives its text

A window is only useful while the house is standing. If the characters a view points at are destroyed, the view still has its pointer and its length, and nothing tells it. Using it is undefined behaviour. The easiest way to get there is a temporary: a value with no name, destroyed at the end of the statement that made it. string::substr returns a new string, so it makes one.

#include <iostream>
#include <string>
#include <string_view>
using namespace std;

int main() {
    string record = "Amara Okafor, room 12, the north building";
    string_view place = record.substr(14, 27);
    cout << "place: [" << place << "]\n";
    return 0;
}

GCC 12 compiled it with no message, at the Playground's flags and with -Wall -Wextra too. One run on Compiler Explorer printed place: [, then 16 bytes of unreadable garbage, then th building]. The 27-character temporary was freed at the semicolon, and the memory allocator had already written over its first 16 bytes. Another run printed different garbage. The fix is to keep the characters: string place = record.substr(14, 27);, or view the original with string_view(record).substr(14, 27). So a view is safe exactly as long as its owner lives, and the compiler will not check that for you.

#include <iostream>
#include <string_view>
using namespace std;

int main() {
    string_view files[] = {"test_parser.cpp", "main.cpp", "test_report.cpp", "notes.txt"};
    for (string_view name : files) {
        if (name.starts_with("test_") && name.ends_with(".cpp")) {
            name.remove_prefix(5);
            name.remove_suffix(4);
            cout << "test: " << name << '\n';
        } else {
            cout << "skip: " << name << '\n';
        }
    }
    return 0;
}

test: parser
skip: main.cpp
test: report
skip: notes.txt

#include <iostream>
#include <string>
#include <string_view>
using namespace std;

int count_words(string_view text) {
    int words = 0;
    bool in_word = false;
    for (char c : text) {
        if (c == ' ') {
            in_word = false;
        } else if (!in_word) {
            in_word = true;
            words++;
        }
    }
    return words;
}

int main() {
    string line = "Amara writes the cleanest code";
    char old_style[] = "Bob rushes";

    cout << count_words("a literal works too") << '\n';
    cout << count_words(line) << '\n';
    cout << count_words(old_style) << '\n';
    cout << count_words(string_view(line).substr(6, 10)) << '\n';
    return 0;
}

4
5
2
2

#include <cstring>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    // The first eight bytes of every PNG image file.
    vector<unsigned char> header{0x89, 'P', 'N', 'G', 0x0D, 0x0A, 0x1A, 0x0A};
    cout << "bytes:";
    for (unsigned char b : header) {
        cout << ' ' << (int)b;
    }
    cout << "\nsize(): " << header.size() << '\n';

    char packet[] = {'H', 'I', 0, 'Z', 0};
    cout << "a packet of " << sizeof(packet) << " bytes, strlen says " << strlen(packet) << '\n';
    return 0;
}

bytes: 137 80 78 71 13 10 26 10
size(): 8
a packet of 5 bytes, strlen says 2

#include <iostream>
#include <string>
using namespace std;

char grade(int mark) {
    if (mark >= 80) {
        return 'A';
    }
    if (mark >= 65) {
        return 'B';
    }
    if (mark >= 50) {
        return 'C';
    }
    return 'F';
}

int main() {
    int marks[] = {84, 55, 91, 47, 70};
    string grades;
    for (int m : marks) {
        grades += grade(m);
    }
    cout << "grades: " << grades << " (" << grades.size() << " papers)\n";
    return 0;
}

grades: ACAFB (5 papers)

string line = "Maria asks why, every time";
string_view who = string_view(line).substr(0, 5);
cout << who << '\n';
cout << who.data() << '\n';

char answer[] = "yes";
if (answer == "yes") {
    cout << "same\n";
} else {
    cout << "different\n";
}

string_view room_label(int n) {
    string label = "room number " + to_string(n) + ", north building";
    return label;
}

string_view a = "abc";
string_view b = string("abc");

#include <iostream>
#include <string>
#include <string_view>
using namespace std;

// Return a view of the first word of line: the characters before the
// first space, or the whole line if it has no space. Make no copy.
string_view first_word(string_view line) {
    return line;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string line;
    while (getline(cin, line)) {
        cout << first_word(line) << '\n';
    }
    return 0;
}

#include <iostream>
#include <string>
using namespace std;

int main() {
    int q;
    cin >> q;
    for (int i = 0; i < q; i++) {
        string count, kind, owner;
        cin >> count >> kind >> owner;
        // Ask the flowchart's questions in its order, and print one type.
    }
    return 0;
}

#include <iostream>
#include <string>
using namespace std;

// Kenji's helper: does pattern appear in text, starting at index i?
// It gives the right answer, and it is far too slow on a long text.
// Change only this function, never main.
bool starts_at(string text, string pattern, size_t i) {
    return text.substr(i, pattern.size()) == pattern;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string text, pattern;
    getline(cin, text);
    getline(cin, pattern);

    long long count = 0;
    for (size_t i = 0; i + pattern.size() <= text.size(); i++) {
        if (starts_at(text, pattern, i)) {
            count++;
        }
    }
    cout << count << '\n';
    return 0;
}

That is the end of this module's free lessons. Next come the problems page and the module test. For Pro readers, lesson 05 is "Under the Hood: The Small String Buffer, Growth and the Cost of +" (Pro). Lesson 06 is "CP and Interview Pack: string Patterns, Questions and the Bug Gallery" (Pro).