Start learning free

LESSON 229 OF 667 · SETS

Sets in C++: unordered_set, insert and count

Lesson Read the full explanation

TL ; DR:

An unordered_set holds values without repeats. Inserting a value that is already in it changes nothing.


unordered_set<string> pets = {"cat", "dog", "cat"};   // cat goes in once

pets.insert("fish");                         // a new value

pets.insert("dog");                          // already in it, no change

cout << pets.size() << endl;                 // 3

cout << pets.count("dog") << endl;           // 1, so dog is in it

Full lesson:

A vector keeps every value you put in it, repeats too. Sometimes you only need to know which values there are. A set is made for that.

A set holds each value once. Inserting a value that is already in it changes nothing.

  • unordered_set<string> s; makes an empty set of strings.
  • s.insert(x) puts x in the set s.
  • s.count(x) is 1 when x is in the set, and 0 when it isn't.
  • s.size() gives how many values the set holds.
  • unordered_set<string> s(v.begin(), v.end()); builds a set from the vector v. Its repeats go in once.

Checking s.count(x) is fast, even for a big set. In a vector, you'd look at the values one by one.

C++17 sets have no contains. It only came in C++20. Test s.count(x) > 0 instead.

An unordered_set has no order and no indexes. s[0] doesn't compile.

Your task

The camp's sign-up vector, names, has some names twice. Build an unordered_set named kids from it.

Then Zoe signs up, and Ava signs up again. Insert both names into kids.

Last, if "Leo" is in kids, print Leo is coming.

The code already prints the number of kids twice.

Expected output:

3 kids
4 kids
Leo is coming
STEP 1 OF 3
    Ctrl + Enter to check

    C++ · SETS

    Sets in C++, explained

    What a set is

    A vector keeps every value you put in it, repeats included. Sometimes you only need to know which values exist. A set is made for that: it holds each value once, and inserting a value that is already there changes nothing. C++'s hash-based set is unordered_set.

    unordered_set<string> pets = {"cat", "dog", "cat"};   // cat goes in once

pets.insert("fish");     // a new value
pets.insert("dog");      // already in it, no change

cout << pets.size() << endl;         // 3
cout << pets.count("dog") << endl;   // 1, so dog is in it

    The operations

    • unordered_set<string> s; makes an empty set of strings.
    • s.insert(x) puts x in the set.
    • s.count(x) is 1 when x is in the set and 0 when it isn't. A set holds each value once, so it never gives more than 1.
    • s.size() is the number of values it holds.
    • unordered_set<string> s(v.begin(), v.end()); builds a set from a vector v. The repeats go in once.

    A lookup with count is fast even for a big set, because it jumps to where the value would be instead of looking at the values one by one, as a search in a vector does.

    Why not just use a vector?

    Take vector<int> v = {4, 8, 4, 15, 8, 4};. Building unordered_set<int> distinct(v.begin(), v.end()); gives a set whose size() is 3, while v.size() is still 6. To ask "is 15 in here?" with a vector you would look at the values one by one; the set answers with a single count.

    Strings in a set are compared by their characters, not by where they sit in memory, so "cat" typed twice is the same value. Case matters, though: "Cat" and "cat" are two different values, and a set would hold both.

    Traps

    • No contains in C++17. That member only arrived in C++20, so the lesson tests s.count(x) > 0. Calling contains in C++17 gives the error "has no member named 'contains'".
    • No indexes and no order. s[0] doesn't compile (there is no operator[] for a set). To use every value, loop over the set; the order is not fixed.
    • insert says whether it added. It returns a pair whose second is true when the value was new and false when it was already there. Inserting "pen" into an empty set gives true, and inserting it again gives false with the size still 1. The lesson doesn't need it, but it is how you can tell.

    The lesson's task

    The vector names is {"Ava", "Leo", "Ava", "Mia", "Leo"}: Ava and Leo each appear twice. The task builds kids from it, then signs up Zoe and Ava again, then checks for Leo.

    1. Build kids from names.begin() and names.end(). The set holds Ava, Leo and Mia, so its size is 3.
    2. Insert "Zoe" and then "Ava". Zoe is new, and Ava is already in the set, so the size becomes 4, not 5.
    3. If kids.count("Leo") > 0, print Leo is coming.
    class Solution {
public:
    void mainFunction() {
        vector<string> names = {"Ava", "Leo", "Ava", "Mia", "Leo"};

        unordered_set<string> kids(names.begin(), names.end());
        cout << kids.size() << " kids" << endl;

        kids.insert("Zoe");
        kids.insert("Ava");
        cout << kids.size() << " kids" << endl;

        if (kids.count("Leo") > 0) {
            cout << "Leo is coming" << endl;
        }
    }
};

    The output is:

    3 kids
4 kids
Leo is coming

    Key takeaways

    • A set keeps each value once; repeats are ignored.
    • insert adds, count tests (1 or 0), size counts.
    • Build a set from a vector with (v.begin(), v.end()) to drop its repeats.
    • In C++17 use count(x) > 0, not contains.
    Keep going with C++500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free