12.1 The Set ADT

What a set is

The three things a set gives you:

• add(x): insert $x$ if not already present; no-op otherwise.

• remove(x): remove $x$ if present.

• contains(x): membership query.

That’s it. Everything else (union, intersection, filter, map, subset) is built on top of these three.

Keys vs. elements

When the elements are primitives (ints, strings), each element is its own key. When the elements are objects — a Student with name, phone, id — the set uses one field as the key and compares elements by that. The rest of the object is just cargo.

// C++ lets you choose: the element type IS the key, or you supply
// a hash/comparator that extracts a key.
std::unordered_set<int> primes;
std::unordered_set<Student, StudentHash, StudentEq> roster;

// Or use a map if you need key/value separation.
std::unordered_map<int, Student> rosterById;

Where the Set impls live in cs-300

The Set ADT has no canonical implementation --- the right impl depends on the workload. cs-300 has already given you four of them:

This chapter does not re-derive any of those. It treats them as black-box impls of the same ADT and asks: when do you pick which? Plus the impls cs-300 has not covered yet --- bitset (§12.5), DSU (§12.6), Bloom filter (§12.7) --- which fill out the Set-impl space.

Set vs. Sequence: the two ADTs CS 300 covers

Subset testing

$X \subseteq Y$ iff every element of $X$ is in $Y$. Trivial algorithm:

bool isSubset(const std::unordered_set<int>& sub,
              const std::unordered_set<int>& sup) {
    for (int x : sub)
        if (!sup.count(x)) return false;
    return true;
}

Cost: $O(|X|)$ if contains is $O(1)$ (hash set). If sup is a sorted structure (tree set), it’s $O(|X| \log |Y|)$.

12.2 Set Operations

Union, intersection, difference

Union and intersection are commutative ($X \cup Y = Y \cup X$). Difference is not.

The picture: union / intersection / difference / symmetric difference

The four most common binary set operations have a clean Venn-diagram visual. $A \triangle B$ (symmetric difference) is the XOR --- elements in exactly one of the two sets: $A \triangle B \;=\; (A \cup B) \setminus (A \cap B) \;=\; (A \setminus B) \cup (B \setminus A).$

::: center :::

The fifth operation, subset testing ($A \subseteq B$), is not a Venn region --- it is a yes/no predicate (“is $A$‘s circle entirely inside $B$‘s circle?”). Subsection below.

C++ implementations

The <algorithm> header provides set operations on sorted ranges, which means any sorted container:

#include <set>
#include <algorithm>
#include <iterator>

std::set<int> a{54, 19, 75}, b{75, 12}, out;

std::set_union(a.begin(), a.end(), b.begin(), b.end(),
               std::inserter(out, out.end()));
// out = {12, 19, 54, 75}

out.clear();
std::set_intersection(a.begin(), a.end(), b.begin(), b.end(),
                      std::inserter(out, out.end()));
// out = {75}

out.clear();
std::set_difference(a.begin(), a.end(), b.begin(), b.end(),
                    std::inserter(out, out.end()));
// out = {19, 54}

For std::unordered_set, you write the loops explicitly:

std::unordered_set<int> setUnion(const std::unordered_set<int>& a,
                                 const std::unordered_set<int>& b) {
    std::unordered_set<int> r(a);
    r.insert(b.begin(), b.end());
    return r;
}

std::unordered_set<int> setIntersect(const std::unordered_set<int>& a,
                                     const std::unordered_set<int>& b) {
    // Iterate the smaller one -- saves time.
    const auto& smaller = a.size() <= b.size() ? a : b;
    const auto& larger  = a.size() <= b.size() ? b : a;
    std::unordered_set<int> r;
    for (int x : smaller)
        if (larger.count(x)) r.insert(x);
    return r;
}

std::unordered_set<int> setDiff(const std::unordered_set<int>& a,
                                const std::unordered_set<int>& b) {
    std::unordered_set<int> r;
    for (int x : a)
        if (!b.count(x)) r.insert(x);
    return r;
}

Cost analysis

Assume hash-based sets with $O(1)$ expected insert and lookup.

::: center Operation Cost Why

Union $|A| + |B|$ $O(|A| + |B|)$ insert all Intersection $O(\min(|A|, |B|))$ scan smaller, probe larger Difference $A \setminus B$ $O(|A|)$ scan $A$, probe $B$ Subset $A \subseteq B$ $O(|A|)$ scan $A$, probe $B$ :::

For sorted (tree) sets, add a $\log n$ factor for each membership probe.

Symmetric difference

The <algorithm> header provides this directly on sorted ranges:

#include <set>
#include <algorithm>
#include <iterator>

std::set<int> a{1, 3, 5, 7}, b{3, 4, 5, 6}, out;
std::set_symmetric_difference(
    a.begin(), a.end(), b.begin(), b.end(),
    std::inserter(out, out.end()));
// out = {1, 4, 6, 7}

For unordered sets, the hand-rolled form is setUnion(setDiff(a, b), setDiff(b, a)) or, equivalently, $O(|A| + |B|)$ via two scan-and-probe passes. Use cases: change detection between two snapshots ($A$ = “yesterday’s user IDs,” $B$ = “today’s”; $A \triangle B$ = churn), file diffs, version-control “these lines are in exactly one of the two revisions.”

Subset testing, formally

The isSubset algorithm sketched in §12.1 is the canonical form. Cost analysis warrants a separate look:

• Hashed superset: $O(|A|)$ expected, since each $\texttt{contains}_B(a)$ is $O(1)$ expected.

• Sorted (tree / B-tree) superset: $O(|A| \cdot \log |B|)$ deterministic --- one tree probe per element of $A$.

• Both sides sorted: fall back to a sorted-merge variant. Two pointers, advance the smaller; if at any point you advance off the end of $A$ before exhausting it via matches, $A \not\subseteq B$. Cost $O(|A| + |B|)$ --- tighter than $|A| \log |B|$ when $|A|$ is close to $|B|$, looser when $|A| \ll |B|$.

The pick: hashed superset for small $|A|$ relative to $|B|$ (“does this 5-element query set fit inside this million-element cache?”); sorted-merge for $|A| \approx |B|$ (“are these two billion-row tables equal?”).

Strict subset ($A \subseteq B$ and $A \ne B$) is the same algorithm plus a $|A| < |B|$ check.

Power set

Brute enumeration: each subset corresponds to a length-$n$ bitmask where bit $i$ indicates whether $X[i]$ is included. C++:

#include <vector>
#include <cstdint>

template<typename T>
std::vector<std::vector<T>> powerSet(const std::vector<T>& xs) {
    const std::size_t n = xs.size();
    std::vector<std::vector<T>> result;
    result.reserve(1ULL << n);                // 2^n
    for (std::uint64_t mask = 0; mask < (1ULL << n); ++mask) {
        std::vector<T> sub;
        for (std::size_t i = 0; i < n; ++i)
            if (mask & (1ULL << i)) sub.push_back(xs[i]);
        result.push_back(std::move(sub));
    }
    return result;
}

Cost: $\Theta(n \cdot 2^n)$ time and space. Practical only for $n \le 20$-ish ($2^{20} \approx 10^6$); past that, you do not enumerate the power set, you iterate subsets lazily (same loop, no materialised result).

Filter and map

Two higher-order operations borrowed from functional programming:

#include <unordered_set>
#include <functional>

template<typename T, typename Pred>
std::unordered_set<T> setFilter(const std::unordered_set<T>& s, Pred p) {
    std::unordered_set<T> r;
    for (const auto& x : s) if (p(x)) r.insert(x);
    return r;
}

template<typename T, typename U, typename Fn>
std::unordered_set<U> setMap(const std::unordered_set<T>& s, Fn f) {
    std::unordered_set<U> r;
    for (const auto& x : s) r.insert(f(x));
    return r;
}

// Usage:
auto evens = setFilter(nums, [](int x){ return x % 2 == 0; });
auto lengths = setMap<std::string, size_t>(words,
                   [](const std::string& w){ return w.size(); });

Python / JavaScript / Rust / Haskell / Scala all have these as first-class methods on their set (and collection) types. C++ got closer in C++20 with std::ranges::filter_view and std::ranges::transform_view, but the syntax is still clunky compared to xs.filter(...).map(...) in better-styled languages.

12.3 Static vs. Dynamic Sets

::: center Operation Dynamic Static

Construct from collection yes yes Count elements yes yes Search / contains yes yes Add yes no Remove yes no Union / intersection / difference (return new) yes yes Filter / map (return new) yes yes :::

Why would you ever want a static set?

Choosing in practice

::: center Use case Choice

Allowed-country codes loaded at startup Static — set once, read forever Stop-words for a search engine Static — fixed per language Users currently online Dynamic — changes constantly Session IDs issued today Dynamic — grows over time Finalized vote tallies (after the election) Static — sealed after a deadline Shopping cart contents Dynamic — user modifies it :::

C++ idioms for static sets

C++ doesn’t have a built-in frozen set. Common workarounds:

// 1. Wrap in const.
const std::unordered_set<std::string> STOP_WORDS{"a", "an", "the", "of"};

// 2. C++17 initializer at static scope.
constexpr std::array<int, 4> ALLOWED_CODES{200, 301, 302, 404};
// Binary-search in a sorted array -- cache-friendly, no dynamic allocation.

// 3. Compile-time perfect hash via gperf, for pathological performance.

Perfect hashing for static sets

Perfect hashing requires the key set to be known up front (the set must be static); given that, you can construct a hash function custom-tailored to those keys.

The canonical construction is FKS (Fredman, Komlós, and Szemerédi, 1984) --- a two-level scheme. CLRS §11.5 walks the proof; the architecture in two sentences:

1. Level 1. Hash all $n$ keys into a primary table of size $m_1 = n$ slots using a universal hash $h_1$. Some slots will collide --- expected.

2. Level 2. For each level-1 slot containing $k$ keys, allocate a secondary hash table of size $m_2 = k^2$ and pick a level-2 hash $h_2$ (drawn from the same universal family) such that all $k$ keys land in distinct level-2 slots. The $k^2$ size ensures a perfect $h_2$ exists with probability $\ge 1/2$ --- a few rejection-sampling rounds find one.

Total expected space: $O(n)$ (the $\sum k_i^2$ telescopes to $O(n)$ under universal hashing). Lookup: two hash evaluations + two slot reads. Strictly $O(1)$ worst case for any key in $S$.

In production: gperf (GNU Perfect Hash Function Generator) takes a list of strings at build time and emits a C/C++ hash function and lookup table. Used for keyword sets in compilers, HTTP-header tables, MIME types, anywhere the universe is small, fixed, and lookup speed matters. Modern alternatives include cmph (C minimal perfect hashing library) and phf (Rust’s compile-time perfect-hash crate).

When to reach for it: static set, small enough that construction time is not a barrier ($\le 10^5$ keys is comfortable; $10^6$ is feasible), and the marginal cost of expected-case-only lookup matters --- compiler keyword tables, kernel syscall tables, embedded firmware look-up.

Sets you’ll actually use

::: center Container Order Typical implementation

std::set sorted red-black tree (ch. 9) std::unordered_set hash order open-addressed hash table std::multiset sorted, allows dups red-black tree Python set hash order open-addressed hash table Python frozenset hash order immutable hash table Java HashSet / TreeSet — hash / red-black Rust HashSet / BTreeSet — hash / B-tree :::

12.4 Multiset (duplicates allowed)

The terms “multiset” and “bag” are interchangeable in algorithm-textbook usage; “multiset” is the C++ STL spelling (std::multiset / std::multimap).

The STL multiset, three behavioural deltas

std::multiset<K> is RB-backed (same as std::set), ordered, allows duplicates. The three operations whose behaviour changes versus std::set:

• count(k) returns 0 or more (vs. 0 or 1 on std::set). Cost $O(\log n + m(k))$ --- one tree probe to find the first occurrence, then a linear scan of the duplicates run.

• erase(k) removes ALL occurrences of $k$ (vs. at most one on std::set). To remove a single occurrence, take an iterator from find(k) and erase(it).

• equal_range(k) returns $[\texttt{lower\_bound}, \texttt{upper\_bound})$ --- the half-open range of all occurrences of $k$. The canonical way to iterate all duplicates without re-probing.

#include <set>
#include <iostream>

std::multiset<int> ms{1, 3, 3, 3, 5, 7};

std::cout << ms.count(3);             // 3
ms.erase(3);                          // removes ALL three 3s
// ms is now {1, 5, 7}

ms.insert({2, 2, 2, 4});
auto [lo, hi] = ms.equal_range(2);
for (auto it = lo; it != hi; ++it)
    std::cout << *it << ' ';          // 2 2 2

// Remove exactly one occurrence of 2.
ms.erase(ms.find(2));

Set ops on multisets, contrasted

The set-theoretic operations generalise to multisets, but multiplicities have to be combined, and the choice of combiner is the only thing the standard does not legislate.

::: center Op Set rule Multiset rule (multiplicities)

$A \cup B$ $x \in A \lor x \in B$ $m_A(x) + m_B(x)$ (sum, default) $A \cup B$ (alt) --- $\max(m_A(x), m_B(x))$ (max, also valid) $A \cap B$ $x \in A \land x \in B$ $\min(m_A(x), m_B(x))$ $A \setminus B$ $x \in A \land x \notin B$ $\max(0, m_A(x) - m_B(x))$ $A \triangle B$ $(A \setminus B) \cup (B \setminus A)$ $|m_A(x) - m_B(x)|$ $A \subseteq B$ $\forall x: x \in A \Rightarrow x \in B$ $\forall x: m_A(x) \le m_B(x)$ :::

Cross-link: heaps as multisets

ch. 7 (heaps) already works on multiset semantics: a priority queue with two equal-priority elements stores both. The heap-property comparison uses $\le$ (or $\ge$ for max-heaps), not $<$ --- this is the multiset-friendly form, and it lets duplicate priorities coexist in the heap without pseudo-tiebreaking. Almost every concrete impl in cs-300 (heap, BST, hash table) extends to multisets by relaxing one strict-inequality to non-strict. ch. 7’s gap-analysis Set/Multiset note made this explicit; §12.4 is the ADT-side framing.

12.5 Bitset / characteristic vector

Implementations

C++ gives three flavours, picked by whether $n$ is known at compile time:

• std::bitset<N> --- $N$ a compile-time constant. All ops are constexpr-eligible; the compiler often unrolls the word-loop. Fixed size; cannot grow or shrink at runtime. Standard-library, no extra dependencies.

• std::vector<uint64_t> --- the hand-rolled form. Size is $\lceil N / 64 \rceil$ words; you write the indexing (word = bits[i / 64], mask = 1ULL << (i % 64)). Use this when $N$ is runtime-determined and you need word-level access for the bit-twiddling kernels.

• boost::dynamic_bitset --- the production-grade runtime-sized bitset. Same word-array internals, plus growth / shrink, popcount, find-first / find-next, and the standard set-op overloads.

Set ops as bitwise ops

Once both sides are bitset-encoded, every binary set operation becomes a single bitwise instruction per word. Across $\lceil N/w \rceil$ words (where $w = 64$ on most CPUs):

::: center Set op Bitwise form

$A \cup B$ a |= b (per word) $A \cap B$ a &= b $A \setminus B$ a &= ~b $A \triangle B$ a ^= b $|S|$ (cardinality) popcount per word, sum contains$(i)$ (a[i/64] >> (i%64)) & 1 :::

All $O(\lceil N / w \rceil)$ word ops --- linear in universe size, not in set cardinality, and usually 32—64$\times$ faster than the equivalent hash-set or tree-set impl due to word-level parallelism + cache streaming. Modern CPUs have a dedicated popcnt instruction (1 cycle latency); compilers emit it for std::popcount (C++20) and __builtin_popcount.

The picture: a 64-bit word as a bitset

::: center :::

The diagram above shows the set $\{5, 12, 17, 33\}$ over the universe $\{0, \ldots, 63\}$. Each set bit ($1$) is an element of $S$; each clear bit ($0$) is absent. The whole set is one uint64_t: S = (1ULL << 5) | (1ULL << 12) | (1ULL << 17) | (1ULL << 33).

12.6 Disjoint-Set Union (Union-Find)

Use cases

• Connectivity tracking. “Are $u$ and $v$ in the same connected component?” Each addEdge(u, v) is a unite; each query is a find comparison.

• Kruskal’s MST (ch. 10 §10.12). Already covered in the chapter on graphs --- cycles in the partial MST are detected by “the next edge $(u, v)$ has find(u) == find(v).” DSU is the algorithm-shaped reason Kruskal is $O(E \log E)$ and not $O(E \cdot V)$. Cross-link: ch. 10 §10.12 has the Kruskal application; this section has the ADT framing.

• Tarjan’s offline strongly-connected-components. Off-line variant of SCC computation that uses DSU instead of the recursion stack from ch. 10 §10.6.

• Online dynamic graph connectivity (incremental only). DSU answers “are $u$ and $v$ connected?” under a stream of edge insertions in $O(\alpha(n))$ amortised per op. Decremental connectivity (edge removals) is much harder and needs different machinery.

• Equivalence-class management. Type-inference unification, image-segmentation flood fill, percolation theory.

Implementation: parent-pointer forest

Each set is an up-tree: every element points at a parent; the root points at itself and is the canonical representative. find(x) walks parent pointers to the root. unite(x, y) computes rx = find(x) and ry = find(y), then makes one root the parent of the other.

struct DSU {
    std::vector<int> parent, rank_;
    explicit DSU(int n) : parent(n), rank_(n, 0) {
        for (int i = 0; i < n; ++i) parent[i] = i;
    }
    int find(int x) {
        // Path compression: every node on the find-path
        // points directly at the root after the call.
        return parent[x] == x ? x
                              : parent[x] = find(parent[x]);
    }
    bool unite(int x, int y) {
        int rx = find(x), ry = find(y);
        if (rx == ry) return false;            // already united
        // Union by rank: shorter tree under taller.
        if (rank_[rx] < rank_[ry]) std::swap(rx, ry);
        parent[ry] = rx;
        if (rank_[rx] == rank_[ry]) ++rank_[rx];
        return true;
    }
};

The two optimisations

• Union by rank (or size). Each root carries a “rank” (an upper bound on tree height; in the size-based variant, the subtree’s element count instead). When uniting two trees, the shorter one is attached under the taller. Without compression this alone gives $O(\log n)$ per op (depth $\le \log_2 n$).

• Path compression. During find, after locating the root, re-point every node on the find-path directly at the root. Flattens the tree lazily --- the work is paid by the same query that needed the answer.

Either optimisation alone is $O(\log n)$. Together, the amortised cost per op drops to $O(\alpha(n))$, where $\alpha$ is the inverse Ackermann function --- a function so slowly growing that $\alpha(n) \le 4$ for any $n \le 2^{2^{2^{2^{16}}}}$ (approximately $2^{65536}$). For any input that fits in the universe, DSU is effectively constant per operation.

Theorem (Tarjan 1975, refined Tarjan—van Leeuwen 1984). The amortised cost of $m$ find / unite operations on $n$ elements with both optimisations is $\Theta(m \cdot \alpha(m, n))$. The matching lower bound shows this is optimal in the pointer-machine model. CLRS Ch 21 walks the proof; this chapter takes it as a black box.

The picture: parent forest, union step, path compression

::: center :::

In panel (c), the dashed arrow shows the new direct parent edge 5 -> 3 that path compression installed: previously $5 \to 7 \to 3$ (depth 2), now $5 \to 3$ (depth 1). Every subsequent find(5) costs one parent read instead of two.

12.7 Bloom filter

Construction and queries

#include <vector>
#include <cstdint>
#include <functional>

class BloomFilter {
    std::vector<std::uint64_t> bits;     // m bits packed in 64-bit words
    std::size_t m;                        // bit count
    int k;                                // # hash functions

    std::size_t hash(std::size_t seed, std::uint64_t x) const {
        // Cheap two-hash trick: combine std::hash with a salt.
        return (std::hash<std::uint64_t>{}(x ^ seed)) % m;
    }
public:
    BloomFilter(std::size_t m_, int k_)
        : bits((m_ + 63) / 64, 0), m(m_), k(k_) {}

    void insert(std::uint64_t x) {
        for (int i = 0; i < k; ++i) {
            std::size_t b = hash(i * 0x9E3779B97F4A7C15ULL, x);
            bits[b / 64] |= (1ULL << (b % 64));
        }
    }
    bool contains(std::uint64_t x) const {
        for (int i = 0; i < k; ++i) {
            std::size_t b = hash(i * 0x9E3779B97F4A7C15ULL, x);
            if (!(bits[b / 64] & (1ULL << (b % 64)))) return false;
        }
        return true;            // probably present (or false positive)
    }
};

No erase. A naive Bloom filter cannot delete: any bit set might be “shared” between multiple inserted keys, so clearing it could turn a true positive into a false negative, breaking the one-sided-error contract. The counting-Bloom variant in the next notebox restores delete by replacing each bit with a small counter.

The false-positive-rate formula

After inserting $n$ keys into an $m$-bit table with $k$ hash functions (assumed independent and uniform), the probability that a specific bit is still $0$ is $\left(1 - 1/m\right)^{kn} \approx e^{-kn/m}$. A query for a never-inserted $y$ is a false positive iff all $k$ of its bits happen to be set, which happens with probability: $p \;\approx\; \bigl(1 - e^{-kn/m}\bigr)^k.$

Differentiating w.r.t. $k$ and setting $\frac{\partial p}{\partial k}=0$ gives the optimal number of hash functions: $k^\star \;=\; \frac{m}{n} \ln 2 \;\approx\; 0.6931 \cdot \frac{m}{n}.$ At $k = k^\star$, the false-positive rate simplifies to $p^\star = (1/2)^{k^\star}$, equivalently $m \approx -n \log_2 p^\star / \ln 2 \approx 1.44 \cdot n \cdot \log_2(1/p^\star)$ bits. Useful calibrations:

::: center $p^\star$ $m / n$ $k^\star$

0.10 4.79 4 0.01 9.59 7 0.001 14.38 10 $10^{-4}$ 19.18 14 $10^{-5}$ 23.97 17 :::

A 1% false-positive rate costs $\sim 9.6$ bits per element. Compare std::unordered_set, which costs $\sim 32$ bytes per element ($256\times$ more). That space ratio is the entire business case for Bloom filters.

Use cases

• Database existence pre-check. “Is this key maybe in the table?” Avoid a disk read when the Bloom filter says no. RocksDB and LevelDB attach a per-SST-file Bloom filter so LSM compaction does not chase missing keys through every level.

• CDN edge caching. “Is this URL maybe in the cache?” False-positive cost: one wasted RAM probe. False-negative cost: a cache miss that should have been a hit. The asymmetry justifies one-sided error.

• Network packet filtering. Squid web cache, firewall blacklist pre-checks. Cheap reject of known non-members before the expensive deep inspection.

• DNS negative caching. “Have we recently failed to resolve this name?” Bloom filter answers in microseconds; falling back on DNS itself takes milliseconds.

• Distributed-systems set reconciliation. Compare two large sets between nodes by exchanging Bloom filters first --- only fall back on full set reconciliation if the filters say there might be a difference.

12.8 Production references and further reading