Step 3 of 6

std::set

A set is a map with keys but no values. std::set<T> holds unique values in sorted order. Inserting something that's already there does nothing, which makes a set the natural tool for "remove duplicates" and "have I seen this before?".

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

int main() {
    std::vector<int> rolls = {4, 2, 6, 2, 4, 4, 1};
    std::set<int> seen(rolls.begin(), rolls.end());   // build from a range
    seen.insert(6);                                    // already there: no change
    seen.insert(3);

    for (int x : seen) std::cout << x << " ";
    std::cout << "\n" << seen.size() << " distinct, has 5? " << seen.contains(5) << "\n";

    std::vector<int> back(seen.begin(), seen.end());  // and back to a vector
    std::cout << "smallest " << back.front() << ", largest " << back.back() << "\n";
}

1 2 3 4 6 
5 distinct, has 5? 0
smallest 1, largest 6

How it works

• Containers can be built from any range given as two iterators: std::set<int> s(v.begin(), v.end()) inserts every element of v. The same trick turns a set back into a vector.
• Iterating a set always goes in sorted order.
• insert returns a pair whose .second is true if the value was new. That lets you detect duplicates as you go:

if (!seen.insert(x).second) { /* x was a duplicate */ }

• Like map, a set is a balanced tree: insert, erase and lookup are O(log n).

Common mistakes

• Trying to change an element in place. Set elements are const, because changing one could break the sorted order. Erase it and insert the new value instead.
• Using a set when you need to keep duplicates. That's std::multiset, or just a sorted vector.

Your turn: write std::vector<std::string> unique_sorted(const std::vector<std::string>& v) that returns the distinct strings in sorted order.

Previous: Look up without inserting Next: unordered_map