std::set_union, set_intersection and set_difference on Sorted Ranges: Duplicates, Comparators and Silent Wrong Output

What these algorithms actually do

The five set algorithms in <algorithm> — set_union, set_intersection, set_difference, set_symmetric_difference and includes — are not tied to std::set. They take two sorted ranges and walk them in lockstep, like the merge step of merge sort. At each step they compare the two current elements and decide whether to emit the smaller one, skip it, or emit it and advance both sides.

That design has three consequences that explain nearly every bug people hit with them:

1. They are linear. One pass, at most 2 * (N1 + N2) - 1 comparisons. No hashing, no tree lookups, no allocation apart from what your output iterator does.
2. They trust you about the order. Nothing checks that the inputs are sorted. If they are not, the merge logic still runs and produces some output — just not the right one.
3. The output is sorted too, so the result of one set algorithm can be fed straight into another.

Algorithm	Math	Emits
set_union	A ∪ B	everything from both, shared values once
set_intersection	A ∩ B	values present in both
set_difference	A − B	values in A that are not in B
set_symmetric_difference	A △ B	values in exactly one of them
includes	B ⊆ A	returns bool, no output

The basic calls

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>

template <class C> void print(const char* name, const C& c) {
    std::cout << name << ":";
    for (const auto& x : c) std::cout << ' ' << x;
    std::cout << '\n';
}

int main() {
    std::vector<int> a = {1, 3, 5, 7};
    std::vector<int> b = {2, 3, 6, 7};
    std::vector<int> u, i, d, s;

    std::set_union(a.begin(), a.end(), b.begin(), b.end(), std::back_inserter(u));
    std::set_intersection(a.begin(), a.end(), b.begin(), b.end(), std::back_inserter(i));
    std::set_difference(a.begin(), a.end(), b.begin(), b.end(), std::back_inserter(d));
    std::set_symmetric_difference(a.begin(), a.end(), b.begin(), b.end(), std::back_inserter(s));

    print("union", u);
    print("intersection", i);
    print("difference", d);
    print("symdiff", s);
}

Output (g++ 10.3, -std=c++17):

union: 1 2 3 5 6 7
intersection: 3 7
difference: 1 5
symdiff: 1 2 5 6

Note the argument order matters only for set_difference (A − B is not B − A) and includes (the second range is tested as a subset of the first).

Output iterators: give the algorithm somewhere to write

Every one of these (except includes) writes through an output iterator and returns the iterator one past the last element it wrote. There are three correct ways to supply it:

• std::back_inserter(vec) — appends with push_back. The simplest choice and what most code should use.
• std::inserter(someSet, someSet.end()) — inserts into an associative container. Because the output arrives sorted, the end() hint makes each insertion amortized constant.
• A pre-sized buffer, then trim with the returned iterator:

std::vector<int> out(a.size() + b.size());           // upper bound for union
auto last = std::set_union(a.begin(), a.end(), b.begin(), b.end(), out.begin());
out.erase(last, out.end());                          // out: 1 2 3 5 6 7

The upper bound is a.size() + b.size() for union and symmetric difference, min(a.size(), b.size()) for intersection and a.size() for difference. The pre-sized version avoids repeated reallocation, which matters in a hot loop.

The one thing that does not work is result.begin() on an empty vector. That writes through an iterator into zero elements of storage — undefined behavior that usually shows up as heap corruption far away from the call. Writing into one of the input ranges (a.begin() as the output) is also undefined: the standard requires the output not to overlap the inputs, and with union the output is typically longer than a anyway.

Duplicates: inputs are multisets

Sorted vectors can contain repeated values, and the algorithms define exactly what happens. If a value appears m times in A and n times in B:

Algorithm	Copies emitted
set_union	max(m, n)
set_intersection	min(m, n)
set_difference	max(m − n, 0)
set_symmetric_difference	`
includes	true only if B’s count ≤ A’s count for every value

std::vector<int> m1 = {1, 2, 2, 2, 3};
std::vector<int> m2 = {2, 2, 3, 3, 4};
// union:        1 2 2 2 3 3 4
// intersection: 2 2 3
// difference:   1 2
// symdiff:      1 2 3 4

Those outputs were copied from a real run. This is exactly the behavior you want when counting inventory (“I need two of these bolts and have three”), and exactly the behavior you do not want when you think of the vector as a set of IDs and one ID was accidentally pushed twice. If you want true set semantics, deduplicate first:

std::sort(v.begin(), v.end());
v.erase(std::unique(v.begin(), v.end()), v.end());

The same rule makes includes stricter than people expect: includes({1,2,3,4,5}, {2,2}) returns false, because A contains only one 2.

Pitfall 1: unsorted input gives quietly wrong results

std::vector<int> x = {3, 1, 4};
std::vector<int> y = {1, 4, 5};
std::vector<int> bad;
std::set_intersection(x.begin(), x.end(), y.begin(), y.end(), std::back_inserter(bad));
// bad: 4     (the correct intersection is 1 4)

No crash, no warning at -Wall -Wextra, just a missing 1. The merge saw 3 vs 1, advanced y past 1, and never came back. Technically the precondition violation is undefined behavior, but in practice libstdc++ just produces wrong output, which is worse than a crash because it passes tests that happen to use sorted fixtures.

The cheapest defense in development is libstdc++‘s debug mode, which does check the order:

$ g++ -std=c++17 -D_GLIBCXX_DEBUG set2.cpp && ./a.out
.../bits/stl_algo.h:5310:
In function:
    _OIter std::set_intersection(_IIter1, _IIter1, _IIter2, _IIter2, _OIter) [...]

Error: elements in iterator range [__first1, __last1) are not sorted.

(The process aborts with exit code 3.) I turn -D_GLIBCXX_DEBUG on in test builds for any code that leans on sorted-range algorithms — set_*, binary_search, lower_bound, merge. Note that it changes the ABI of standard containers, so every translation unit that shares them must be built the same way. In release code, an assert(std::is_sorted(v.begin(), v.end())) at the boundary where data enters your system is a cheap alternative.

Pitfall 2: sorted, but with a different comparator

“Sorted” means sorted by the comparator the algorithm uses. If you sort descending and then call the algorithm with its default operator<, you have the same bug as unsorted input:

std::vector<int> dA = {7, 5, 3, 1};
std::vector<int> dB = {7, 6, 3, 2};
std::vector<int> r1, r2;
std::set_intersection(dA.begin(), dA.end(), dB.begin(), dB.end(),
                      std::back_inserter(r1));                     // r1: 7
std::set_intersection(dA.begin(), dA.end(), dB.begin(), dB.end(),
                      std::back_inserter(r2), std::greater<>{});   // r2: 7 3

The one I have personally lost the most time to is the string version of this: one list sorted case-insensitively for display, the other sorted with plain std::string::operator<, and a set_difference between them that reported “missing” entries which were clearly present when you looked at the data. Both lists looked sorted. The fix is to define the ordering once — a named comparator type — and use it for both the sort calls and the set algorithm, so the three can never drift apart.

Structs and projections

For records, the comparator decides what “equal” means (two elements are equivalent when neither is less than the other). The classic algorithms even allow the two ranges to have different element types, as long as the comparator accepts both argument orders:

struct User { int id; std::string name; };

std::vector<User> active = {{1, "ann"}, {4, "bo"}, {9, "cy"}};   // sorted by id
std::vector<int>  bannedIds = {4, 9};                            // sorted

struct ById {
    bool operator()(const User& u, int id) const { return u.id < id; }
    bool operator()(int id, const User& u) const { return id < u.id; }
};
std::vector<User> keep;
std::set_difference(active.begin(), active.end(), bannedIds.begin(), bannedIds.end(),
                    std::back_inserter(keep), ById{});
// keep: 1:ann

C++20 adds std::ranges::set_union and friends, which take whole ranges and projections, so you no longer write the comparator by hand:

std::vector<User> banned = {{4, ""}, {9, ""}};
std::ranges::set_difference(active, banned, std::back_inserter(keep),
                            {}, &User::id, &User::id);

There is a catch I hit when porting the heterogeneous version: the ranges algorithms require std::mergeable, which means the output must be writable from both input element types. Passing std::vector<int> as the second range with a back_inserter into std::vector<User> does not compile on g++ 10.3:

error: no match for call to '(const std::ranges::__set_difference_fn) (std::vector<User>&,
       std::vector<int>&, std::back_insert_iterator<std::vector<User> >, ...)'
...
note: the required expression '*__o =(forward<_Tp>)(__t)' is invalid

So for “records minus a list of keys”, the classic algorithm with a two-way comparator is still the tool; the ranges version is nicer when both sides have the same type.

A worked example: permission checks

#include <algorithm>
#include <iterator>
#include <string>
#include <vector>

class PermissionChecker {
    std::vector<std::string> granted_;
    std::vector<std::string> required_;
public:
    PermissionChecker(std::vector<std::string> granted, std::vector<std::string> required)
        : granted_(std::move(granted)), required_(std::move(required)) {
        std::sort(granted_.begin(), granted_.end());
        std::sort(required_.begin(), required_.end());
    }
    bool hasAll() const {
        return std::includes(granted_.begin(), granted_.end(),
                             required_.begin(), required_.end());
    }
    std::vector<std::string> missing() const {
        std::vector<std::string> out;
        std::set_difference(required_.begin(), required_.end(),
                            granted_.begin(), granted_.end(),
                            std::back_inserter(out));
        return out;
    }
};

// PermissionChecker c({"read", "write", "execute"}, {"read", "write", "delete"});
// c.hasAll()  -> false
// c.missing() -> {"delete"}

The constructor sorts both inputs once, so every later query is linear and allocation-free (apart from the result). The same shape — sort once at the boundary, then run several set algorithms — works for directory sync (files to upload = remote − local, files to delete = local − remote, unchanged = intersection) and tag filters.

Sorted vector, std::set or unordered_set?

• Sorted std::vector + set algorithms: contiguous memory, one linear pass, very cache-friendly. Best when the data is built once and queried, or when you already have sorted batches. Cost: you maintain the ordering yourself.
• std::set: iteration is already sorted, so the algorithms work directly on s.begin(), s.end(), and uniqueness is guaranteed so the duplicate rules never surprise you. Each node is a separate allocation, though, and building the result via std::inserter allocates per element. For union specifically, C++17’s a.merge(b) splices nodes without copying: with a = {1,3,5} and b = {3,4,5}, a becomes {1,3,4,5} and the duplicates 3 5 stay behind in b.
• std::unordered_set: no order, so the set algorithms do not apply. Iterate over the smaller set and call count/contains on the larger one; that is expected O(min(n, m)) and often the fastest option when the sets are large and unordered.

As a rule of thumb, if you find yourself sorting two vectors only to intersect them once, compare that against dropping one side into an unordered_set. If the data is already sorted, or you need the sorted output anyway, the set algorithms are hard to beat.

Related Articles

• C++ Sort Algorithms: std::sort, stable_sort, partial_sort
• set vs unordered_set in C++
• C++ Search Algorithms: binary_search, lower_bound, upper_bound
• Erase-remove and std::unique cleanup