Start learning free

LESSON 233 OF 667 · SETS

Removing From a Set and Looping Over It in C++

Lesson Read the full explanation

TL ; DR:

erase(x) takes x out of a set. A range-based for loop visits every value once, in no fixed order.


unordered_set<string> colors = {"red", "blue", "green"};

colors.erase("blue");

colors.erase("pink");           // not in it, nothing happens

for (string color : colors) {
    cout << color << endl;      // red and green, in any order
}

Full lesson:

s.erase(x) removes x from the set s. It returns how many values it removed. That is 1 if x was there, and 0 if it wasn't.

for (string x : s) visits each value of the set once. The order isn't fixed. That's what the "unordered" in unordered_set means.

So loop over a set when the order doesn't matter. A total, a count and a check are fine.

Don't erase values from a set while you loop over it. The loop loses its place, and the program may crash. Erase first, then loop.

Your task

In a word game, the set found holds the words a player found. The words "qqq" and "zzz" aren't allowed. Remove both from found.

The player never found "zzz", so removing it changes nothing.

Then add up the points. A word scores one point per letter. Loop over found and add each word's length to score.

The code already prints how many words are left, and the points.

Expected output:

4 words
14 points
STEP 1 OF 3
    Ctrl + Enter to check

    C++ · SETS

    Removing From Sets in C++, explained

    erase and the range-based loop

    s.erase(x) removes x from the set s. It returns how many values it removed: 1 if x was in the set and 0 if it wasn't. Erasing a value that isn't there is not an error; nothing happens.

    unordered_set<string> colors = {"red", "blue", "green"};

colors.erase("blue");
colors.erase("pink");           // not in it, nothing happens

for (string color : colors) {
    cout << color << endl;      // red and green, in any order
}

    for (string x : s) visits each value of the set once. The order isn't fixed: that is the "unordered" in unordered_set. So loop over a set when the order doesn't matter, for a total, a count or a check.

    The loop above copies each value into color. For big values such as long strings, const string& color avoids the copy. The result is the same.

    Two other ways to shrink a set are worth knowing by name. s.clear() removes every value at once, and s.size() afterwards is 0. s.empty() tells you whether anything is left. Neither is needed for this lesson, which only removes two named words. Erase is also the right tool for "take this name off the list" jobs, where the list is a set of names.

    Traps

    • Don't erase while looping over the same set. Erasing a value the loop is standing on invalidates the loop's position, so the program may crash or skip values. Erase first, then loop. If you need to remove values found during a loop, collect them in a vector and erase them after the loop.
    • Don't depend on the order. Printing the values shows them in whatever order the set keeps them. Sums and counts don't depend on it.
    • Use the return value if you need it. erase returns 1 the first time and 0 the second time you erase the same value.

    Here is that two-pass shape on the words cat, tree, qqq, moon and zzz, where the unwanted words are the three-letter words that start with a doubled letter:

    vector<string> banned;
for (string w : found) {
    if (w.size() == 3 && w[0] == w[1]) {
        banned.push_back(w);
    }
}
for (string w : banned) {
    found.erase(w);
}

    The first loop only reads found. The second loop reads banned and erases from found, which is a different container, so nothing is invalidated. Afterwards found holds 3 words.

    The lesson's task

    In a word game, found holds the words cat, tree, sun, qqq and moon. The words "qqq" and "zzz" aren't allowed. Remove both, then add up one point per letter.

    1. Call erase with "qqq" and then with "zzz". The second call removes nothing, because the player never found it. Four words are left.
    2. Loop over found with a string named word.
    3. Inside the loop, add word.size() to score.
    class Solution {
public:
    void mainFunction() {
        vector<string> words = {"cat", "tree", "sun", "qqq", "moon"};
        unordered_set<string> found(words.begin(), words.end());

        found.erase("qqq");
        found.erase("zzz");
        cout << found.size() << " words" << endl;

        int score = 0;
        for (string word : found) {
            score += word.size();
        }
        cout << score << " points" << endl;
    }
};

    The output is:

    4 words
14 points

    The four remaining words have 3, 4, 3 and 4 letters, which add up to 14, whichever order the loop visits them in. word.size() is an unsigned number, and adding it to an int is fine for small lengths like these.

    Key takeaways

    • erase(x) returns 1 or 0 and never fails for a missing value.
    • A range-based for visits every value once, in no fixed order.
    • Erase before looping, not during it.
    Keep going with C++500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free