C++ Set

A set holds each value at most once. Adding a value that is already there does nothing. std::set keeps its values sorted; std::unordered_set does not keep any order but is usually faster for large sets.

Creating and adding

#include <iostream>
#include <set>

int main() {
    std::set<int> s = {5, 1, 5, 3, 1};
    s.insert(4);
    s.insert(3);                 // already there: ignored
    std::cout << "size " << s.size() << ":";
    for (int x : s) std::cout << " " << x;     // always in sorted order
    std::cout << "\n";
    return 0;
}

size 4: 1 3 4 5

Looking up and removing

contains (C++20) or count tells whether a value is in the set; find returns an iterator to it, or end() when it is missing; erase removes it.

#include <iostream>
#include <set>
#include <string>

int main() {
    std::set<std::string> visited = {"Delhi", "Mumbai", "Pune"};
    std::cout << std::boolalpha;
    std::cout << "Pune: " << visited.contains("Pune") << "\n";
    std::cout << "Goa: " << (visited.count("Goa") > 0) << "\n";
    visited.erase("Mumbai");
    for (const auto& c : visited) std::cout << c << " ";
    std::cout << "\n";
    return 0;
}

Pune: true
Goa: false
Delhi Pune 

Looking up a value in a set takes time proportional to the logarithm of its size, so it stays fast even with millions of values, unlike searching a vector from start to end.

Removing duplicates

Putting the elements of a vector into a set removes duplicates and sorts them in one step:

#include <iostream>
#include <set>
#include <vector>

int main() {
    std::vector<int> v = {4, 2, 4, 9, 2, 7};
    std::set<int> unique(v.begin(), v.end());
    std::cout << unique.size() << " different values:";
    for (int x : unique) std::cout << " " << x;
    std::cout << "\n";
    return 0;
}

4 different values: 2 4 7 9

unordered_set

std::unordered_set (header unordered_set) stores its values in a hash table: lookups take about the same short time however big the set is, but the values come out in no particular order. Use it when you only ask "is this value there?" and do not need sorted output.

Elements cannot change

Values in a set cannot be modified in place, because that could break the sorted order. Remove the old value and insert the new one instead. To store your own types in a std::set, they need an operator< (see Operator Overloading).

Practice exercises

1. Read words until "end" and print how many different words there were.
2. Print the letters that appear in both "programming" and "language" using two sets.
3. Find the first repeated number in a vector by inserting into a set and checking the result.