std::set and std::unordered_set

A set is a map without values: it stores keys, each at most once, and answers whether a key is present. std::set keeps them sorted and std::unordered_set hashes them, exactly as their map counterparts do.

Sets are the right tool for membership, for removing duplicates and for the set algebra of intersection, union and difference. The keys of a set are const, which is the one difference from a map that shows up in the compiler errors.

A set is usually the smallest container that answers a membership question, and std::set is the one to reach for when the keys should come out in order; the hashed version takes over when only presence matters and the data is large.

Insertion into a set is logarithmic and does not invalidate the other iterators, which makes it the container for a membership check in the middle of a loop that also inserts.

Unique keys in order

insert adds a key and ignores it when it is already there. The program inserts five values of which two are duplicates, and the set holds three.

Iteration is in ascending order because std::set keeps the keys sorted with operator<. That order costs a tree walk per operation and gives ordered output and ordered search for free.

count returns 1 or 0 for a set, and contains does the same since C++20. find returns an iterator to the key or end(), which is the form to use when the key is needed afterwards.

#include <iostream> #include <set> int main() { std::set<int> values; values.insert(3); values.insert(1); values.insert(3); values.insert(2); values.insert(1); for (int value : values) { std::cout << value << ' '; } std::cout << ' ' << values.size() << '\n'; }

g++ -std=c++23 -Wall -Wextra set.cpp -o set_demo
./set_demo

1 2 3 3

A hashed set

std::unordered_set has the same insert and find with average constant-time cost instead of logarithmic. The order of iteration is unspecified, so it is the right container when the order does not matter.

The program inserts three names and asks whether two of them are present with contains. The answers are independent of the order, which is why a membership test is the natural use of this container.

For a small set of integers the difference in speed is invisible; for a lookup in a loop over millions of keys it is the reason to choose the hashed version.

#include <iostream> #include <string> #include <unordered_set> int main() { std::unordered_set<std::string> names{"ada", "bob", "cyd"}; std::cout << names.contains("bob") << ' ' << names.contains("zed") << '\n'; std::cout << names.size() << '\n'; }

g++ -std=c++23 -Wall -Wextra unordered_set.cpp -o unordered_set_demo
./unordered_set_demo

1 0
3

Erase by value and by iterator

erase takes a key or an iterator. The key version returns the number of removed elements, which is 0 or 1 for a set; the iterator version returns the iterator after the removed element.

The program removes one key by value and one by iterator, then prints the remaining keys. The second erase uses the iterator from find, which is the pattern for removing an element the code has already located.

Erasing invalidates the iterator that was passed and nothing else, which is why a loop that erases advances with the returned iterator, as in lesson 049.

#include <iostream> #include <set> int main() { std::set<int> values{1, 2, 3, 4, 5}; values.erase(2); auto it = values.find(4); if (it != values.end()) { values.erase(it); } for (int value : values) { std::cout << value << ' '; } std::cout << '\n'; }

g++ -std=c++23 -Wall -Wextra erase.cpp -o erase_set
./erase_set

1 3 5

Set operations

std::set_intersection, set_union, set_difference and set_symmetric_difference take two sorted ranges and write the result to an output iterator. A std::set is already sorted, so it can be passed directly.

The program intersects two sets and collects the common keys in a vector. The output iterator is a back_inserter, which appends to the vector and grows it as needed.

The algorithms work on any sorted ranges, including sorted vectors, which is often faster than two sets because the data is contiguous. They do not require the inputs to be std::set at all.

#include <algorithm> #include <iostream> #include <iterator> #include <set> #include <vector> int main() { std::set<int> first{1, 2, 3, 4}; std::set<int> second{3, 4, 5, 6}; std::vector<int> common; std::set_intersection(first.begin(), first.end(), second.begin(), second.end(), std::back_inserter(common)); for (int value : common) { std::cout << value << ' '; } std::cout << '\n'; }

g++ -std=c++23 -Wall -Wextra ops.cpp -o set_ops
./set_ops

3 4

The keys of a set are const

A set keeps its elements ordered, so the key of an element cannot change: the tree would be in the wrong place. The iterator of a std::set therefore yields a const reference, and assigning through it is an error.

The program writes through a set iterator and the compiler says the assignment writes to a read-only location. The fix is to erase the old key and insert the new one, which repositions the element.

std::map has the same rule for its keys and allows writes to the values. That is the difference between the two containers in one sentence.

#include <set> int main() { std::set<int> values{1, 2, 3}; auto it = values.begin(); *it = 5; return 0; }

g++ -std=c++23 -Wall -Wextra write_key.cpp -o write_key

write_key.cpp: In function 'int main()':
write_key.cpp:7:9: error: assignment of read-only location 'it.std::_Rb_tree_const_iterator<int>::operator*()'
7 | *it = 5;
| ~~~~^~~

Exercises

1. Insert the words of a sentence into a std::set and print how many distinct words there are.
2. Compute the union and the difference of the two sets in ops.cpp and print both.
3. Replace the set in set.cpp with a std::vector and remove the duplicates with sort and unique.

The code on this page was built with g++ 15.2.0 and run on Alpine Linux 3.24.3 (x86_64) in a Docker container. The programs whose section shows a compiler error were compiled until that error and were not run.

Article author: Arthur Isaev