Chapter 33

Home

Sets for Unique Items

A set is like a map with only keys — it stores unique elements and tells you whether something has been seen before. Sets power duplicate removal, presence checks, and intersection problems.

When to Use a Set

Use a set when you only care about existence, not counts or associated values. Common scenarios:

Duplicate detection

"Does this array contain duplicates?" Insert each element into a set — if an insert fails, it's a duplicate.

Seen tracking

"Have I visited this node before?" BFS/DFS on graphs uses a set to track visited nodes.

Membership test

"Is this word in the dictionary?" Build a set of valid words and check each input against it.

C++ — std::unordered_set

#include <bits/stdc++.h>
using namespace std;

int main() {
    unordered_set<int> s;

    s.insert(10);
    s.insert(20);
    s.insert(10);  // ignored — already present

    cout << s.size() << "\n";        // 2
    cout << s.count(10) << "\n";     // 1 (found)
    cout << s.count(99) << "\n";     // 0 (not found)

    // Iterate
    for (int x : s) cout << x << " ";

    s.erase(10);
    return 0;
}

Rust — HashSet

use std::collections::HashSet;

fn main() {
    let mut s = HashSet::new();

    s.insert(10);
    s.insert(20);
    s.insert(10);  // ignored

    println!("{}", s.len());               // 2
    println!("{}", s.contains(&10));       // true
    println!("{}", s.contains(&99));       // false

    for &x in &s { print!("{} ", x); }

    s.remove(&10);
}

💡 Sets are just maps without values

Internally, unordered_set/HashSet works exactly like unordered_map/HashMap — it hashes the element and stores it in a bucket. O(1) average insert, delete, and lookup.

Duplicate Detection in One Pass

The classic use: check if an array has duplicates without nested loops.

C++

bool has_duplicates(vector<int>& arr) {
    unordered_set<int> seen;
    for (int x : arr) {
        if (seen.count(x)) return true;
        seen.insert(x);
    }
    return false;
}

Rust

fn has_duplicates(arr: &[i32]) -> bool {
    let mut seen = HashSet::new();
    for &x in arr {
        if !seen.insert(x) { return true; }
    }
    false
}

insert() returns true if the value was new, false if it already existed. Rustic one-liner.

Ordered Sets

Like maps, sets come in unordered (hash) and ordered (tree) flavours. Use ordered when you need sorted iteration or range queries.

C++ — std::set (ordered, red-black tree)

set<int> s;  // ordered, O(log N) operations
s.insert(50);
s.insert(10);
s.insert(30);
// Iteration order: 10, 30, 50

// Find smallest element ≥ 25
auto it = s.lower_bound(25);
if (it != s.end()) cout << *it << "\n";  // 30

📐 Rust uses BTreeSet for ordered

use std::collections::BTreeSet; — same API as HashSet but with sorted iteration and range() queries. O(log N) operations.

Key Takeaways

Practice