The idea
set keeps distinct values in sorted order; insert, erase and find are O(log n). multiset is the same but allows duplicates.
Its real strength is order queries on data that keeps changing: lower_bound(x) is the first value ≥ x, upper_bound(x) the first value > x, begin() the smallest, rbegin() the largest. Iterators step to the next or previous value.
Reach for it when you need “the closest value to x” or “the smallest value still available” while inserting and deleting.
Sample problem
220. Contains Duplicate III ↗ Hard
Decide whether there are two different indices i and j with |i − j| ≤ indexDiff and |nums[i] − nums[j]| ≤ valueDiff.
nums = [8,1,14,5,11], indexDiff = 2, valueDiff = 3 output = true (14 and 11)
Why the solution works
For each index only the previous indexDiff values matter, so keep them in a sliding window.
The question for the window is “does it contain a value in the range [x − valueDiff, x + valueDiff]?”. A sorted set answers it with one lower_bound: find the smallest value ≥ x − valueDiff and check that it is ≤ x + valueDiff.
A hash set could not do this: it only finds exact values. The ordered set is what makes a range lookup O(log n) while values keep entering and leaving.
Complexity: O(n log k) time, O(k) memory, with k = indexDiff.
Watch out
- On a
multiset,erase(value)removes every copy. Erase an iterator to remove one. - Use the member
s.lower_bound(x). The free functionlower_bound(s.begin(), s.end(), x)is O(n) on a set. - Never dereference
end()or step back frombegin(): test first.