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".
#include <set> std::set<int> s = {5, 1, 3, 3}; // 1 3 5 s.insert(4);
Try it
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.
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
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::setvs sorted vector: a vector sorted once and searched withstd::binary_searchis 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; usestd::inserterfor a set target. - Both iterator types are constant:
iteratorandconst_iteratorboth giveconst Key&. - Use the member
find, notstd::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? Usestd::unordered_set. - Pairs as elements work out of the box because
std::pairhasoperator<; good for(distance, node)priority sets in graph code.