C++ Sets and Multisets

1 minute read

Published:

Overview

Sets store keys without associated values. The main choices are:

  • std::set: unique values in sorted order.
  • std::multiset: sorted values with duplicates.
  • std::unordered_set: unique values with average O(1) lookup.

Common Includes

#include <set>
#include <unordered_set>
#include <vector>

set

std::set stores unique values in sorted order. Operations are O(log n).

std::set<int> seen;

seen.insert(5);
seen.insert(2);
seen.insert(5);                           // duplicate ignored

if (seen.find(2) != seen.end()) {
  // exists
}

seen.erase(5);

Ordered operations:

auto lower = seen.lower_bound(10);        // first value >= 10
auto upper = seen.upper_bound(10);        // first value > 10

Iterate sorted:

for (int x : seen) {
  // ascending order
}

multiset

std::multiset stores values in sorted order and allows duplicates. This is useful when both order and multiplicity matter.

std::multiset<int> values;

values.insert(5);
values.insert(2);
values.insert(5);                         // duplicate stored

int smallest = *values.begin();
int largest = *values.rbegin();

Erase one duplicate:

auto it = values.find(5);
if (it != values.end()) {
  values.erase(it);                       // erases one 5
}

Erase all duplicates:

values.erase(5);                          // erases every 5

Sliding-window min/max sketch:

std::multiset<int> window;

window.insert(new_value);

auto old = window.find(old_value);
if (old != window.end()) {
  window.erase(old);                      // remove one outgoing value
}

int min_value = *window.begin();
int max_value = *window.rbegin();

unordered_set

std::unordered_set stores unique values with average O(1) insert, erase, and lookup.

std::unordered_set<int> seen;

seen.insert(10);
seen.insert(20);

if (seen.find(10) != seen.end()) {
  // exists
}

seen.erase(20);

Duplicate detection:

bool containsDuplicate(const std::vector<int>& nums) {
  std::unordered_set<int> seen;

  for (int x : nums) {
    if (seen.find(x) != seen.end()) {
      return true;
    }
    seen.insert(x);
  }

  return false;
}

Choosing a Set

NeedContainer
Sorted unique valuesset
Sorted values with duplicatesmultiset
Fast existence check, no orderunordered_set
Lower/upper boundset or multiset
Sliding sorted window with duplicatesmultiset

Complexity

ContainerInsertDeleteLookupOrdered iteration
setO(log n)O(log n)O(log n)Yes
multisetO(log n)O(log n)O(log n)Yes
unordered_setO(1) averageO(1) averageO(1) averageNo

Checklist

  • Use set when uniqueness and sorted order both matter.
  • Use multiset when duplicate values must be represented separately.
  • Use unordered_set when only membership matters.
  • For multiset, use erase(iterator) to remove one occurrence.
  • Do not rely on iteration order for unordered_set.

Leave a Comment

You May Also Enjoy