set / multiset / unordered_set

set — unique sorted keys

• Stores **unique** keys in **sorted** order (balanced tree).
• insert / find / erase are **O(log n)**.
• Inserting an existing key has no effect (set stays unique).
• Iterators walk keys in ascending order.
• **Real-life:** classroom roll numbers (no duplicates, naturally sorted); sorted unique product SKUs on a shelf list.

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

int main() {
    set<int> s = {3, 1, 2, 2}; // {1, 2, 3}
    s.insert(4);
    cout << s.count(2) << "\n"; // 1
    for (int x : s) cout << x << " ";
    cout << "\n";
    return 0;
}

multiset — sorted with duplicates

• Like set, but **duplicate keys are allowed** and kept sorted.
• count(key) returns how many times the key appears.
• equal_range(key) gives the iterator range of all equal keys.
• erase(key) removes **all** matches; erase(iterator) removes one.
• **Real-life:** exam marks where several students score 90; waiting times logged and sorted with repeats.

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

int main() {
    multiset<int> ms = {1, 2, 2, 3};
    ms.insert(2); // now three 2's
    cout << ms.count(2) << "\n"; // 3
    auto [lo, hi] = ms.equal_range(2);
    for (auto it = lo; it != hi; ++it) cout << *it << " ";
    cout << "\n";
    return 0;
}

unordered_set — unique hashed keys

• Unique keys; **not sorted** — hash buckets.
• Average **O(1)** insert/find/erase; worst case can degrade.
• Great for membership tests (“have I seen this before?”).
• Custom types need a **hash** and **equality**.
• **Real-life:** airport boarding pass scan (already boarded?); unique words in a document when order does not matter.

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

int main() {
    unordered_set<string> us = {"a", "b"};
    us.insert("c");
    us.insert("a"); // ignored — unique
    cout << (us.find("a") != us.end()) << "\n"; // 1
    cout << us.size() << "\n"; // 3
    return 0;
}

Common operations

• Shared ideas: insert, erase, find, count, size, empty, iterate with range-for.
• find returns an iterator; compare with end() for missing keys.
• Prefer count/find over assuming sorted order on unordered_set.

Real-life examples by container

• Map everyday problems to the right set type.

Set family applications

• Sets appear whenever you track membership, uniqueness, or sorted bags of keys.

When to use which

• Need sorted unique keys or ordered traversal → **set**.
• Need sorted keys **with duplicates** → **multiset**.
• Need fast unique membership, order irrelevant → **unordered_set**.
• **Real-life rule of thumb:** printer needs alphabetical unique list → set; hospital lab keeps all temperature readings → multiset; security gate only asks “seen?” → unordered_set.