Skip to content
Tutorials Center
My learning

Topics

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.

C++
std::set_intersection(a.begin(), a.end(), b.begin(), b.end(), std::back_inserter(out));

Try it

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.

C++ Duplicates are counted by multiplicity

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 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_union writes max(m, n), set_intersection min(m, n), set_difference max(m - n, 0), and set_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: merge keeps all elements of both inputs; set_union drops the duplicated part.
  • Real sets: for std::set the same operations are written with the algorithms plus std::inserter(result_set, result_set.end()). A C++23 ranges version exists as std::ranges::set_union etc.
  • includes is a subset test (with multiplicity): {1,1} is not included in .