ReviseAlgo Logo

Standard Template Library (STL)

std::set and std::multiset

Ordered tree-based containers for unique (set) or duplicate (multiset) sorted elements

Interview: Sorted unique elements, O(log n) operations, and ordered iteration — common in sliding window and interval problems

std::set and std::multiset

std::set stores unique elements in sorted order using a red-black tree. std::multiset allows duplicates. Both provide O(log n) insertion, deletion, and search. Iterating produces elements in sorted order. Unlike unordered_set (hash-based), set provides ordered iteration and range queries — critical for many algorithms.

Key Operations

lower_bound(x) returns iterator to first element ≥ x. upper_bound(x) returns iterator to first element > x. These enable O(log n) range queries — essential for sliding window maximums, interval overlap detection, and sorted order maintenance.

Erase with multiset

In multiset, erase(value) removes ALL elements equal to value. To remove only ONE occurrence, use an iterator: ms.erase(ms.find(value)). This is a common bug source in interview code.

Interview Corner

Q: When would you use std::set over std::unordered_set?

A: Use set when: you need sorted order, need lower_bound/upper_bound for range queries, or when worst-case O(log n) is preferable to unordered_set's rare O(n) worst case (hash collisions). Use unordered_set when O(1) average lookup/insert is needed and order doesn't matter. For interview problems involving "maintain sorted order while inserting/deleting," set is the right tool.

Common Pitfalls

  • Multiset erase all vs erase one: ms.erase(5) removes all 5s. Use ms.erase(ms.find(5)) to remove exactly one.
  • Modifying elements through iterators: Set/multiset elements are const through iterators — modifying them would break the sorted invariant. Erase and re-insert to change a value.

Best Practices

  • Use count() on a set as a boolean exists check — it returns 0 or 1 efficiently.
  • For the sliding window maximum in a sorted structure, a multiset with begin()/rbegin() gives O(log n) per operation.