Skip to content
Tutorials Center
My learning

Topics

C++ Reference ยท Containers

C++ std::set class

Reference for std::set: sorted unique elements, O(log n) insert, find and erase, set algorithms such as union and intersection, lower_bound and custom comparators.

std::set<T> stores unique elements in sorted order. Inserting a value that is already present does nothing. Insertion, lookup and erasure take O(log n) time and iteration visits the elements in ascending order. Like std::map, it is normally a balanced binary tree, and iterators and references stay valid when other elements are inserted or erased.

Elements are const: you cannot change one in place, because that could break the ordering. To "modify" an element, erase it and insert the new value (or use extract, C++17). A set is the right tool for membership tests, deduplication with sorted output, and range queries such as "smallest element not less than x".

C++
#include <set>
std::set<int> s = {5, 1, 3, 3};   // 1 3 5
s.insert(4);

Try it

C++ Unique, sorted and searchable

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.

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.

Syntax

C++
template <class Key, class Compare = std::less<Key>,
          class Allocator = std::allocator<Key>>
class set;

std::pair<iterator, bool> insert(const Key& k);
template <class... A> std::pair<iterator, bool> emplace(A&&...);
iterator find(const Key& k) const;      bool contains(const Key& k) const;   // contains: C++20
size_type count(const Key& k) const;    // 0 or 1
iterator lower_bound(const Key& k);     iterator upper_bound(const Key& k);
size_type erase(const Key& k);          iterator erase(const_iterator pos);
node_type extract(const Key& k);        // C++17
Name Description
Key Element type, ordered by Compare.
Compare A strict weak ordering. Elements that are neither less nor greater than each other are the same element.
k The value to insert, find or erase.

Returns: insert returns an iterator to the element and whether it was newly inserted; find returns end() if absent; erase(key) returns 0 or 1.

Errors / undefined behavior: dereferencing end() is undefined. A comparator that is not a strict weak ordering breaks the container. Mutating an element through a cast is undefined.

Usage notes

  • Complexity: O(log n) for insert, find, erase, lower_bound; O(n) iteration; O(1) size().
  • std::set vs sorted vector: a vector sorted once and searched with std::binary_search is smaller and faster to scan if the data rarely changes.
  • Set algorithms (std::set_union, set_intersection, set_difference, includes) work on any sorted ranges and write to an output iterator; use std::inserter for a set target.
  • Both iterator types are constant: iterator and const_iterator both give const Key&.
  • Use the member find, not std::find, which is O(n).
  • Custom order: std::set<int, std::greater<int>> sorts descending. Equivalence under the comparator, not ==, decides duplicates.
  • Duplicates allowed? Use std::multiset. Faster lookup, no order? Use std::unordered_set.
  • Pairs as elements work out of the box because std::pair has operator<; good for (distance, node) priority sets in graph code.