C++ Reference ยท Algorithms
The std::set_union, set_intersection and set_difference algorithms
Reference for C++ set_union, set_intersection, set_difference, set_symmetric_difference and includes: set algebra on sorted ranges, with duplicates handled.
The set algorithms in <algorithm> combine two sorted ranges and write a sorted result. They work on any sorted ranges, not just on std::set: sorted vectors, arrays and deques all qualify. std::set_union writes elements that are in either range, std::set_intersection those in both, std::set_difference those in the first but not the second, and std::set_symmetric_difference those in exactly one. std::includes checks whether one sorted range contains all elements of another.
All of them run in linear time with one pass over each input. They handle duplicates by multiplicity: if a value appears 3 times in A and twice in B, the intersection contains it twice and the union three times.
std::set_intersection(a.begin(), a.end(), b.begin(), b.end(), std::back_inserter(out));
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 InIt1, class InIt2, class OutIt> OutIt set_union(InIt1 f1, InIt1 l1, InIt2 f2, InIt2 l2, OutIt out); OutIt set_intersection(InIt1 f1, InIt1 l1, InIt2 f2, InIt2 l2, OutIt out); OutIt set_difference(InIt1 f1, InIt1 l1, InIt2 f2, InIt2 l2, OutIt out); OutIt set_symmetric_difference(InIt1 f1, InIt1 l1, InIt2 f2, InIt2 l2, OutIt out); bool includes(InIt1 f1, InIt1 l1, InIt2 f2, InIt2 l2); // every function also has an overload with a trailing Compare comp
| Name | Description |
|---|---|
f1, l1 |
The first sorted range. |
f2, l2 |
The second sorted range. |
out |
Output iterator that receives the result (a back_inserter, or an iterator into pre-sized storage). |
comp |
The strict weak ordering both inputs are sorted by. |
Returns: the output iterator one past the last element written (a bool for includes).
Errors / undefined behavior: both inputs must be sorted by the same ordering, and the output must not overlap either input. If the output container is too small, writing is undefined behavior.
Usage notes
- Multiplicity rules: with m copies in the first range and n in the second,
set_unionwrites max(m, n),set_intersectionmin(m, n),set_differencemax(m - n, 0), andset_symmetric_difference|m - n|. - Where elements come from: in a union, equivalent elements are taken from the first range; in an intersection, they are also taken from the first.
- Complexity: at most 2 * (N1 + N2) - 1 comparisons, one linear pass.
- Not for unsorted data: feeding unsorted input does not fail; it silently produces wrong results. Sort both sides first.
- Differs from
std::merge:mergekeeps all elements of both inputs;set_uniondrops the duplicated part. - Real sets: for
std::setthe same operations are written with the algorithms plusstd::inserter(result_set, result_set.end()). A C++23 ranges version exists asstd::ranges::set_unionetc. includesis a subset test (with multiplicity):{1,1}is not included in.