Back to all concepts
Intermediate 11 min

Set and Multiset

Master std::set and std::multiset for automatically sorted, unique (or duplicate) element storage with fast lookups

Discover how std::set and std::multiset automatically maintain sorted, unique elements with efficient logarithmic operations.

A Simple Example 

#include <iostream>
#include <set>

int main() {
    // std::set - unique, sorted elements
    std::set<int> numbers{5, 2, 8, 2, 1, 9};  // Duplicates ignored

    std::cout << "Set contents (auto-sorted): ";
    for (int num : numbers) {
        std::cout << num << " ";  // 1 2 5 8 9 (no duplicate 2!)
    }
    std::cout << "\n";

    // Insertion
    auto [iter, inserted] = numbers.insert(3);
    std::cout << "Inserted 3: " << std::boolalpha << inserted << "\n";  // true

    auto [iter2, inserted2] = numbers.insert(5);
    std::cout << "Inserted 5: " << inserted2 << "\n";  // false (already exists)

    // Lookup - O(log n)
    if (numbers.find(8) != numbers.end()) {
        std::cout << "Found 8" << "\n";
    }

    // Count - returns 0 or 1 for set
    std::cout << "Count of 5: " << numbers.count(5) << "\n";  // 1

    // std::multiset - allows duplicates
    std::multiset<int> multiNumbers{5, 2, 8, 2, 1, 9};
    std::cout << "\nMultiset contents: ";
    for (int num : multiNumbers) {
        std::cout << num << " ";  // 1 2 2 5 8 9 (duplicates kept!)
    }
    std::cout << "\n";
    std::cout << "Count of 2: " << multiNumbers.count(2) << "\n";  // 2

    return 0;
}

Breaking It Down

std::set - Unique Elements

  • What it is: Sorted container using balanced binary search tree (typically red-black tree)
  • Automatically maintains sorted order and enforces uniqueness
  • O(log n) insertion, deletion, and lookup
  • Use for: Removing duplicates, maintaining sorted unique values, membership tests

std::multiset - Allows Duplicates

  • What it is: Like set but allows multiple identical elements
  • Still maintains sorted order
  • count() can return values greater than 1
  • Use for: Frequency counting, priority-based processing with duplicates

Insert Operation

  • set::insert() returns pair<iterator, bool>
  • The iterator points to the element (new or existing)
  • The bool indicates if insertion succeeded (false if duplicate)
  • Remember: Structured bindings make this readable: auto [iter, inserted] = set.insert(val)

When to Use Set vs Vector

  • Use set when you need: automatic sorting, uniqueness, fast lookups
  • Use vector when you need: random access, cache locality, back operations
  • Set trades memory overhead for automatic ordering
  • Remember: If you don't need sorting or uniqueness, vector is usually better

Why This Matters

  • Sets are perfect when you need automatic sorting and uniqueness guarantees.
  • They're ideal for membership testing, removing duplicates, range queries, and maintaining sorted data.
  • Understanding sets helps you write cleaner code that doesn't manually sort or check for duplicates.

Critical Insight

Set is like a VIP guest list that's always alphabetically sorted and never has duplicates. When you add a name, the bouncer checks if it's already there (O(log n) thanks to binary search tree), and if not, adds it in the right sorted position.

You never have to manually sort or check for duplicates - the set does it automatically as part of insertion!

Best Practices

Use set for automatic uniqueness: When you need to remove duplicates and maintain order, set does both automatically.

Prefer find() over count() for existence: find() is slightly more efficient as it returns immediately when found.

Use multiset for frequency counting: When you need to count occurrences while maintaining sorted order.

Consider unordered_set for speed: If you don't need sorted order, unordered_set provides O(1) operations instead of O(log n).

Common Mistakes

Trying to modify elements: Set elements are immutable because they're used as keys for ordering. To change a value, erase and insert.

Expecting O(1) lookup: Sets use O(log n) lookup, not O(1). Use unordered_set for O(1) average case.

Iterator invalidation: Inserting or erasing elements doesn't invalidate iterators to other elements.

Debug Challenge

This code needs to track unique values in sorted order. Click the highlighted line to fix the container choice:

1 #include <iostream>
2 #include <vector>
3
4 int main() {
5 std::vector<int> unique{5, 2, 8, 2, 1};
6 // Need auto-sorted, no duplicates
7 return 0;
8 }

Quick Quiz

  1. What happens when you insert a duplicate into std::set?
Insertion is ignored, returns false
Exception is thrown
Old value is replaced
  1. What's the time complexity of set::find()?
O(log n)
O(1)
O(n)

Practice Playground

Time to try out what you just learned! Play with the example code below, experiment by making changes and running the code to deepen your understanding.

Lesson Progress

  • Fix This Code
  • Quick Quiz
  • Practice Playground - run once