std::set<T> is a sorted associative container that stores unique keys, and std::multiset<T> is the same container without the uniqueness rule. Both are typically backed by a balanced binary search tree (red-black tree in every major implementation), which gives O(log n) insert, lookup, and erase while keeping the elements in sorted order. This chapter covers what those guarantees provide, the full API, custom comparators, and when to prefer set over the hash-based unordered_set in the next chapter.

Vectors and lists store elements in insertion order. std::set does not care about insertion order. Insert 42, 7, then 19, and iterating the set produces 7 19 42. The container keeps a sorted view at all times by storing each key in a node of a balanced binary search tree.

Every major standard library implementation (libstdc++, libc++, MSVC's STL) uses a red-black tree internally. The standard does not mandate that specific structure, but it does mandate the complexity bounds, and red-black trees fit. Each node holds one key plus three pointers (parent, left child, right child) and a color bit for rebalancing. The tree invariant is the standard binary search tree invariant: every key in the left subtree is less than the node's key, and every key in the right subtree is greater.

Reading this tree in-order (left subtree, node, right subtree) gives 7 19 25 42 55 97, which is the sorted view a std::set<int> exposes. The balancing rules keep the tree height at O(log n) no matter how skewed the insertion order is, which is what gives every operation its log-time guarantee.

Every set operation that touches an element (insert, erase, find, count, lower_bound, upper_bound) is O(log n). The tree never degenerates into a linked list the way an unbalanced BST might, because the balancing rules forbid it.

The constant factor on a set is meaningfully higher than on a vector or a hash container. Each operation walks log-n nodes, each node is a separate heap allocation, and each step is a pointer chase that the CPU cannot usefully prefetch. For small data sets (a few dozen elements), a sorted std::vector plus std::lower_bound is often faster than a set, even though the asymptotic complexity is worse on paper. Pick set when the ordered-view operations it provides are needed.

insert is the workhorse for adding elements. It accepts a value (lvalue or rvalue) or an iterator range, and it returns a std::pair<iterator, bool>: the iterator points to the element with that key (existing or new), and the bool says whether the insert actually added something.

The bool flag is what makes insert the right call when whether the element was new matters. The first insert returns true (printed as 1), the second returns false because "Electronics" was already present. The structured binding spelling auto [it, inserted] is a C++17 feature and is the shortest way to read both halves of the result.

emplace constructs the element in place from its constructor arguments, avoiding a temporary. The return type and meaning is the same as insert.

emplace forwards 10 and 'x' to the std::string constructor that takes a count and a fill character, building the string directly inside the new tree node. For built-in types like int, insert and emplace are equivalent; the difference matters for types where construction is non-trivial.

Both insert and emplace are O(log n). Each call allocates one tree node on the heap, walks the tree to find the right spot, and may rebalance one or two ancestors. The allocation dominates the cost in a tight loop.

find(key) returns an iterator to the element if present, and end() if not. It is the standard lookup function.

count(key) returns the number of elements equal to key. For std::set this is always 0 or 1, since duplicates are not allowed. Some code uses s.count(x) > 0 as a membership test; that works, but find is clearer about intent.

contains(key) was added in C++20 and returns a plain bool. It is the clearest read for "is this key present?"

Compile with g++ -std=c++20. Before C++20, write wishlist.find("Notebook") != wishlist.end() instead.

find, count, and contains are all O(log n). They walk from the root to a leaf in the worst case, comparing the key at each step.

The sorted-tree structure is what makes set more than a hash table with extra steps. Three operations exploit the ordering: lower_bound, upper_bound, and equal_range.

lower_bound(key) returns an iterator to the first element not less than key. If key is in the set, that iterator points at key. If not, it points at the first element greater than key (or end() if no such element exists).

upper_bound(key) returns an iterator to the first element strictly greater than key.

Together, they bracket the range of elements equal to key. For a std::set that range is always 0 or 1 elements wide; the operations are useful for finding ranges of neighbors.

The lookup is two O(log n) calls and the walk between them is O(k) where k is the number of elements in the range. With an unordered container, the same query would be O(n) because every element has to be scanned.

equal_range(key) is the same as calling both: it returns a std::pair<iterator, iterator> of (lower_bound, upper_bound). It is mostly useful with std::multiset, where the range can be more than one element wide.

For a plain set, equal_range is a two-iterator way of saying "did find succeed?" The interesting case is multiset, covered later.

erase has three overloads. Erase by key, by iterator, or by iterator range.

erase(key) returns the number of elements removed (0 or 1 for a std::set). erase(it) and erase(first, last) return an iterator to the element after the last one removed, useful for continuing iteration.

One property of tree-based containers: erasing an element never invalidates iterators, pointers, or references to the other elements. Only the iterator to the erased element itself becomes invalid. The same holds for inserts: an insert never moves the existing elements around in memory, so existing iterators stay valid. This is one of the practical reasons to use set even when a sorted vector would have better cache behavior: long-lived iterators into a set are safe across inserts and unrelated erases.

The iterator to 30 survives the inserts and the unrelated erase. With a std::vector, an insert might have reallocated the underlying buffer and invalidated every iterator.

erase(key) is O(log n) (the find plus one node deletion). erase(it) is amortized O(1) when given an iterator directly, plus the rebalancing work. erase(first, last) is O(k log n) in the worst case, where k is the range size.

Iterating a set walks the keys in sorted order, regardless of insertion order. The default iterators (begin()/end()) move forward; rbegin()/rend() walk in reverse.

*set.begin() and *set.rbegin() are the cheapest way to get the min and max keys; both are O(1) because the tree caches pointers to its leftmost and rightmost nodes.

The iterator dereferences to a const T&. A key cannot be modified through a set iterator, because changing the key would break the tree's sorted invariant. To "change" a key, erase the old one and insert the new one.

Full iteration over a set is O(n). It does n-1 tree-successor steps, each one O(1) amortized. The hop between nodes is a pointer chase, which is why iteration through a set is slower than iteration through a vector of the same size despite the same Big-O.

By default, std::set<T> orders elements with std::less<T>, which uses operator<. For a different ordering (descending, by a member field, case-insensitive), supply a custom comparator as the second template parameter.

The simplest option is to swap the comparator type. std::greater<int> gives a descending set.

For custom logic, define a functor (a struct with operator()) and use it as the comparator type.

"books" was rejected as a duplicate of "Books" because the comparator treats them as equal (neither is less than the other under case-insensitive comparison). That is how set decides equality: two keys are equal when !comp(a, b) && !comp(b, a). There is no separate operator== call.

A lambda works too, but the syntax is bumpier because each lambda has a unique unnamed type. The lambda has to be passed to the set's constructor, and decltype is needed to spell the type.

In C++20 the constructor argument can be dropped because lambdas became default-constructible when they have no captures. Before C++20 the constructor argument is mandatory.

A common bug with custom comparators: the comparator must implement a strict weak ordering. For any two values a and b, exactly one of these holds: comp(a, b), comp(b, a), or neither (which means they are equal). A comparator that returns <= instead of < breaks the strict part, and the set misbehaves in subtle ways (duplicates leak in, lookups fail). Always use strict less-than, never less-than-or-equal.

std::multiset<T> is the same container as std::set<T>, except keys are not required to be unique. Inserting the same value three times stores it three times.

Equal keys stay grouped together in iteration order, which is what makes range queries useful here. count(key) returns the actual number of matches, no longer just 0 or 1. equal_range(key) returns the range of iterators covering all elements equal to key, the common way to iterate over duplicates.

The other API difference is that insert on a multiset returns just an iterator (not a pair), because the insert always succeeds. There is no boolean flag because there is no failure mode.

erase(key) on a multiset removes every element equal to key and returns the count.

To remove a single occurrence, use erase(it) with an iterator returned by find. That removes exactly the one element the iterator points at.

multiset::count(key) is O(log n + k) where k is the number of matches, because it has to find both ends of the equal range. equal_range(key) is O(log n).

std::unordered_set is the hash-based sibling. The two containers solve overlapping problems but in different ways, so the picking rule comes up in interviews and in code review. The short version:

unordered_set gives average O(1) for insert, erase, and find. set gives guaranteed O(log n) plus all the ordered-view operations. Without ordering needs, prefer unordered_set, because constant-factor and average-case performance both favor it. When ordering is needed, set is the only standard option short of writing a custom container.

This is not a per-operation choice; pick the container based on which operations dominate the workload. Switching containers later usually requires changing more than one line, because the iterators and the iteration order behave differently.

A small running example pulls most of these pieces together. Consider a store tracking a sorted set of product price points so the merchandising team can answer questions like "what is the cheapest product over $50?" or "list everything between $20 and $100."

Every one of those queries is O(log n). With a std::vector<double>, the data would either need to be kept sorted manually (and pay O(n) on every insert), or scanned on every query (O(n) per call). With an unordered_set<double> the range queries do not exist at all; every element would need to be scanned to answer "what is in [$20, $100]?"

Compile with g++ -std=c++20 file.cpp. The contains call is the only C++20-specific line; the rest works back to C++11.