Skip to content
Tutorials Center
My learning

Topics

Lesson 101 of 171 ยท The Standard Library (STL)

std::set and std::unordered_set

Learn C++ std::set, std::multiset and std::unordered_set - unique elements, ordered vs hashed sets, custom ordering, removing duplicates and set operations with algorithms.

A set is a collection of unique values with one central question: is this value in it? Has this user already voted, have we visited this graph node, which tags does an article have? std::set<T> (header <set>) answers in O(log n) and keeps its elements sorted. std::unordered_set<T> (header <unordered_set>) answers in O(1) on average using a hash table. Both silently ignore attempts to insert a value that's already present.

You can think of a set as a std::map with keys and no values; indeed, the ordered and hashed sets are built from the same trees and hash tables as std::map and std::unordered_map. In this lesson you'll learn how to use both kinds, std::multiset for repeated values, custom ordering (and how a bad comparator can lose data), three ways to remove duplicates, and the set algorithms: union, intersection and difference.

std::set: unique and sorted

A std::set is a balanced binary search tree of values. Insertion, lookup and erasure are O(log n), iteration runs from smallest to largest, and inserting a duplicate does nothing. insert tells you which happened by returning a std::pair<iterator, bool>:

C++ A set keeps one sorted copy of each value

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

The lower_bound pair at the end is a prefix search: every string that starts with c sorts between "c" and "d". That kind of query is only possible because the set is ordered.

Elements are read-only

A set's elements are effectively const: iterators to a std::set<T> yield const T&. Changing an element in place would break the tree's order, so the compiler won't let you. To "modify" an element, erase it and insert the new value, or use extract (C++17) to take the node out, change node.value(), and insert it back without a new allocation:

C++
auto node = tags.extract("stl");
node.value() = "standard-library";
tags.insert(std::move(node));

Ordering and equivalence

The default comparator is std::less<T>, which uses operator<. You can pass a different one as the second template argument: std::set<int, std::greater<>> iterates from largest to smallest, and std::less<> enables lookups with types other than T (for example std::string_view for a set of std::string).

For your own types, the easiest path is a defaulted operator<=> (see Operator Overloading), which compares members in declaration order. Be careful with hand-written comparators, though. A set considers two elements equivalent when neither is less than the other, and equivalent elements count as duplicates. A comparator that looks at only part of an object silently throws data away:

C++ A comparator decides what counts as a duplicate

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

With the hour-only comparator, Ivo's 18:00 booking is "equivalent" to Kim's and is rejected. That's correct behavior if you meant "one booking per hour", and a silent bug if you didn't. Make sure your comparator distinguishes every pair of values you consider different, and that it's a strict weak ordering (never <=, which makes comp(a, a) true and breaks the tree).

std::multiset: sorted, with duplicates

std::multiset<T> (also in <set>) keeps every inserted value, sorted, with duplicates next to each other. It's useful for a sorted bag of values that changes over time: scores on a leaderboard, prices in an order book, the values in a sliding window.

  • insert always succeeds and returns an iterator.
  • count(v) returns how many copies exist; equal_range(v) gives all of them.
  • Pitfall: erase(v) removes all copies of v. To remove one, erase by iterator: ms.erase(ms.find(v)) (after checking that find didn't return end()).
C++ A multiset leaderboard

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

std::distance on set iterators walks one step at a time, so counting a range is O(k) for k elements. Standard sets don't support O(log n) rank queries; you'd need a specialized tree for that.

std::unordered_set: hashed membership

When you only need "is it there?" and don't care about order, std::unordered_set<T> is usually faster: average O(1) for insert, contains and erase. It has the same hashing rules, buckets, reserve and custom-hash options as std::unordered_map, so everything from the unordered_map lesson applies, including the need to write a hasher for std::pair and your own structs.

Typical jobs: tracking visited states in a search, detecting duplicates in a stream, and fast blocklists or allowlists.

C++ Seen-before checks with unordered_set

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

seen.insert(event).second is the idiom for "add it, and tell me whether it was new", performing only one hash lookup instead of a contains followed by an insert.

Removing duplicates from a vector

There are three common ways, with different results:

  1. Sort and unique (sorted output, no extra container): std::ranges::sort(v); auto [first, last] = std::ranges::unique(v); v.erase(first, last);. unique only removes adjacent duplicates, which is why you sort first. Usually the fastest option for numbers.
  2. Build a std::set (sorted output): std::set<T> s(v.begin(), v.end());. Simple, but allocates a node per distinct value.
  3. std::unordered_set with the insert idiom (keeps the original order, as shown above).

Pick by whether you need the original order, and remember that a vector-based approach almost always uses less memory than a node-based set.

Set operations with algorithms

<algorithm> provides the classic operations from mathematics on sorted ranges: std::set_union, std::set_intersection, std::set_difference, std::set_symmetric_difference, plus std::includes to test for a subset. A std::set is always sorted, so it qualifies directly; a vector works too once it's sorted. Each algorithm runs in linear time, O(n + m), and writes into an output iterator:

C++ Union, intersection and difference

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

std::back_inserter(v) turns each write into v.push_back(...); std::inserter(s, pos) turns it into s.insert(pos, ...). Both are covered with the other iterator adaptors in Iterators.

Unordered sets aren't sorted, so these algorithms don't apply to them. For hashed sets, loop over the smaller set and test contains on the larger one, which is O(min(n, m)) on average:

C++
std::unordered_set<int> common;
for (int x : small) {
    if (large.contains(x)) {
        common.insert(x);
    }
}

C++23 also adds std::flat_set (header <flat_set>, supported in GCC 15): a sorted vector with a set's interface. It's slower to insert into than std::set but faster to search and iterate, and much smaller in memory.

Choosing a set

Need Choose
Membership tests, no order needed std::unordered_set
Sorted iteration, smallest/largest, range or prefix queries std::set
Sorted values with repeats std::multiset
Built once, then mostly read sorted std::vector or std::flat_set
A fixed set of small integers (0 to N) std::bitset or std::vector<bool>

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. std::set<int> s{3, 1, 3, 2, 1}; What does printing s show?

    A set stores each value once and keeps values sorted, so duplicates disappear and iteration goes from smallest to largest.
  2. 2. std::multiset<int> ms{5, 5, 5, 7}; ms.erase(5); How many elements are left?

    erase(value) removes every element equal to the value, leaving only 7. To remove a single copy, erase the iterator returned by find.
  3. 3. A set of structs uses a comparator that compares only the id member. You insert two objects with the same id but different names. What happens?

    A set treats elements as duplicates when neither compares less than the other. With an id-only comparator, the two objects are equivalent, so the second is not inserted.
  4. 4. What is the idiomatic, single-lookup way to add x to an unordered_set and know whether it was new?

    insert returns a pair whose bool is true only when the element was actually added, so one call both inserts and reports. The contains-then-insert version hashes twice.
  5. 5. Why can't std::set_intersection be used directly on two std::unordered_set objects?

    The set algorithms walk both inputs in sorted order in a single pass. Unordered sets iterate in arbitrary order, so the result would be wrong; loop and use contains instead.

Summary

  • std::set stores unique values sorted in a tree: O(log n) operations, ordered queries with lower_bound, read-only elements (use extract to change one).
  • insert returns pair<iterator, bool>; .second tells you whether the value was new.
  • The comparator defines both order and what counts as a duplicate; comparing only part of an object silently drops elements.
  • std::multiset keeps duplicates. erase(value) removes all copies; erase by iterator to remove one.
  • std::unordered_set gives average O(1) membership tests with the same hashing rules as unordered_map.
  • Remove duplicates with sort + unique, a std::set, or an unordered_set when the original order matters.
  • std::ranges::set_union, set_intersection, set_difference, set_symmetric_difference and includes work on sorted ranges in linear time.

Next: std::pair and std::tuple, the small types that group values together, including the pairs that maps hand you.