Library

since C++98

Intermediate

Set and Heap Algorithms

Set algorithms operating on sorted ranges and heap operations — multiset semantics, complexity guarantees, and C++20 ranges versions.

Set and Heap Algorithmssince C++98

Six algorithms in <algorithm> that compute multiset relationships (union, intersection, difference, subset) over sorted ranges, plus five heap algorithms implementing priority-queue operations on any random-access range.

Overview

The set algorithms treat sorted ranges as mathematical multisets: element multiplicity is preserved according to well-defined rules. If an element appears M times in the first range and N times in the second:

Algorithm	Output count per element
`set_union`	max(M, N)
`set_intersection`	min(M, N)
`set_difference`	max(0, M − N)
`set_symmetric_difference`	\|M − N\|

All four produce a sorted output range using the same ordering relation as the inputs. The heap algorithms implement a binary max-heap stored in a flat array, guaranteeing the maximum element is always at v[0].

Critical preconditions for set algorithms:

Both input ranges must be sorted under the same comparator passed to the algorithm. Violating this is undefined behavior, not just wrong results.
The output range must not overlap either input range.
The comparator must be a strict weak ordering.

Syntax

cpp

// All set operation overloads follow this pattern (C++98):
template<class InputIt1, class InputIt2, class OutputIt>
OutputIt std::set_union(InputIt1 first1, InputIt1 last1,
                        InputIt2 first2, InputIt2 last2,
                        OutputIt d_first);

template<class InputIt1, class InputIt2, class OutputIt, class Compare>
OutputIt std::set_union(InputIt1 first1, InputIt1 last1,
                        InputIt2 first2, InputIt2 last2,
                        OutputIt d_first, Compare comp);

// Same pattern applies to: set_intersection, set_difference,
// set_symmetric_difference, includes.

// Heap operations (C++98):
template<class RandomIt> void std::make_heap(RandomIt first, RandomIt last);
template<class RandomIt> void std::push_heap(RandomIt first, RandomIt last);
template<class RandomIt> void std::pop_heap(RandomIt first, RandomIt last);
template<class RandomIt> void std::sort_heap(RandomIt first, RandomIt last);

// Heap validation (C++11):
template<class RandomIt> bool     std::is_heap(RandomIt first, RandomIt last);
template<class RandomIt> RandomIt std::is_heap_until(RandomIt first, RandomIt last);

Examples

Set union — all elements from A and B

cpp

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

std::vector<int> a{1, 2, 3, 3, 5};
std::vector<int> b{2, 3, 3, 3, 6};

std::vector<int> out;
out.reserve(a.size() + b.size());  // exact upper bound for union

std::set_union(a.begin(), a.end(), b.begin(), b.end(),
               std::back_inserter(out));
// out: {1, 2, 3, 3, 3, 5, 6}
// 3 appears max(2, 3) = 3 times — multiset semantics

Set intersection — elements present in both

cpp

std::vector<int> a{1, 2, 3, 3, 5};
std::vector<int> b{2, 3, 3, 3, 6};

std::vector<int> out;
out.reserve(std::min(a.size(), b.size()));

std::set_intersection(a.begin(), a.end(), b.begin(), b.end(),
                      std::back_inserter(out));
// out: {2, 3, 3}
// 3 appears min(2, 3) = 2 times

Set difference — elements in A but not B

cpp

std::vector<int> a{1, 2, 3, 3, 5};
std::vector<int> b{3, 4};

std::vector<int> out;
out.reserve(a.size());

std::set_difference(a.begin(), a.end(), b.begin(), b.end(),
                    std::back_inserter(out));
// out: {1, 2, 3, 5}
// 3 appears max(0, 2-1) = 1 time

Symmetric difference — elements in exactly one of A or B

cpp

std::vector<int> a{1, 2, 3, 3};
std::vector<int> b{3, 3, 3, 5};

std::vector<int> out;
out.reserve(a.size() + b.size());

std::set_symmetric_difference(a.begin(), a.end(), b.begin(), b.end(),
                               std::back_inserter(out));
// out: {1, 2, 3, 5}
// 3 appears |2-3| = 1 time

includes — subset test

cpp

std::vector<int> universe{1, 2, 3, 4, 5, 6};
std::vector<int> sub{2, 4, 6};

bool ok = std::includes(universe.begin(), universe.end(),
                        sub.begin(), sub.end());
// true: every element of sub appears in universe

// Empty range is always a subset of anything:
std::vector<int> empty;
std::includes(universe.begin(), universe.end(),
              empty.begin(), empty.end());  // always true

Custom comparator — must match the sort order

cpp

struct Event {
    int timestamp;
    std::string name;
};

auto by_time = [](const Event& x, const Event& y) {
    return x.timestamp < y.timestamp;
};

// Both ranges already sorted by timestamp:
std::vector<Event> log1 = {{1, "boot"}, {3, "login"}, {7, "logout"}};
std::vector<Event> log2 = {{2, "connect"}, {3, "auth"}, {9, "disconnect"}};

std::vector<Event> merged;
merged.reserve(log1.size() + log2.size());

// Pass the same comparator used for sorting:
std::set_union(log1.begin(), log1.end(),
               log2.begin(), log2.end(),
               std::back_inserter(merged), by_time);

C++20 ranges — projections eliminate the comparator boilerplate

cpp

// C++20
#include <algorithm>

struct Person { std::string name; int score; };

// Both sorted by name:
std::vector<Person> team_a{{"Alice", 92}, {"Bob", 78}, {"Carol", 85}};
std::vector<Person> team_b{{"Bob", 78}, {"Dave", 90}};

std::vector<Person> combined;
std::ranges::set_union(team_a, team_b,
                       std::back_inserter(combined),
                       std::less{},
                       &Person::name,   // projection for range 1
                       &Person::name);  // projection for range 2
// combined: Alice, Bob, Carol, Dave

Heap Operations

A binary max-heap stored in a flat array satisfies: for every index i, v[i] >= v[2i+1] and v[i] >= v[2i+2]. The standard only guarantees v[0] is maximum; all other positions are unspecified.

Building and modifying a heap

cpp

#include <algorithm>
#include <vector>
#include <cassert>

std::vector<int> v{3, 1, 4, 1, 5, 9, 2, 6};

// O(N) — build max-heap in-place (not O(N log N) — often misquoted):
std::make_heap(v.begin(), v.end());
// v[0] == 9; rest of order is unspecified

// O(log N) — insert: push_back first, then sift up:
v.push_back(10);
std::push_heap(v.begin(), v.end());
// v[0] == 10; heap property fully restored

// O(log N) — extract max: moves it to end, shrinks heap range:
std::pop_heap(v.begin(), v.end());
int max_val = v.back();  // 10
v.pop_back();            // must call separately — pop_heap does NOT remove
// v[0] == 9; heap restored over [begin, end)

// C++11: validate heap property:
assert(std::is_heap(v.begin(), v.end()));

Min-heap with comparator — comparator must be consistent

cpp

std::vector<int> v{3, 1, 4, 1, 5, 9};

std::make_heap(v.begin(), v.end(), std::greater<int>{});
// v[0] == 1 (minimum)

v.push_back(0);
// Pass the SAME comparator — mixing is undefined behavior:
std::push_heap(v.begin(), v.end(), std::greater<int>{});
// v[0] == 0

std::pop_heap(v.begin(), v.end(), std::greater<int>{});
v.pop_back();

sort_heap — heapsort

cpp

// Calling sort_heap destroys the heap property:
std::vector<int> v{3, 1, 4, 1, 5, 9};
std::make_heap(v.begin(), v.end());   // O(N)
std::sort_heap(v.begin(), v.end());   // O(N log N)
// v: {1, 1, 3, 4, 5, 9} — sorted ascending

Manual priority queue vs `std::priority_queue`

cpp

// Manual approach exposes the underlying vector — useful for bulk
// inspection or modifications (e.g., implementing decrease-key):
struct Task {
    int priority;
    std::string name;
    bool operator<(const Task& o) const { return priority < o.priority; }
};

std::vector<Task> pq;

auto push_task = [&](Task t) {
    pq.push_back(std::move(t));
    std::push_heap(pq.begin(), pq.end());
};

auto pop_task = [&]() -> Task {
    std::pop_heap(pq.begin(), pq.end());
    Task t = std::move(pq.back());
    pq.pop_back();
    return t;
};

push_task({3, "low"});
push_task({10, "urgent"});
push_task({5, "medium"});
Task next = pop_task();  // {10, "urgent"}

// For everything else, prefer the adaptor — it prevents heap invariant bugs:
// std::priority_queue<Task> wraps the same heap ops with a cleaner interface.

Best Practices

Reserve output capacity before writing. The bounds below are exact maximums — no reallocation will occur:

cpp

out.reserve(a.size() + b.size());              // set_union, set_symmetric_difference
out.reserve(std::min(a.size(), b.size()));     // set_intersection
out.reserve(a.size());                         // set_difference (a minus b)

Assert sorted preconditions in debug builds. The algorithms produce no diagnostic — silent wrong output is the failure mode:

cpp

assert(std::is_sorted(a.begin(), a.end(), comp));
assert(std::is_sorted(b.begin(), b.end(), comp));

Prefer std::ranges:: versions (C++20) when projections are involved. They eliminate the need to wrap field access in a lambda comparator.

Know when sorted-range algorithms beat std::set. For bulk one-shot operations on already-sorted data (merging sorted log files, diffing sorted ID lists), the linear-time set algorithms are faster than repeated std::set::insert. For repeated membership tests against a stable set, std::set or std::unordered_set is the right tool.

Common Pitfalls

Unsorted input is undefined behavior, not degraded output. There is no runtime check. The standard imposes this as a precondition.

Mixing comparators between sort and algorithm:

cpp

// BUG: sorted descending, algorithm uses default ascending:
std::sort(a.begin(), a.end(), std::greater<int>{});
std::sort(b.begin(), b.end(), std::greater<int>{});
std::set_union(a.begin(), a.end(), b.begin(), b.end(),
               std::back_inserter(out));  // UB — comparator mismatch
// Fix: pass std::greater<int>{} to set_union as well

Confusing std::merge with set_union. std::merge concatenates all elements (total count M + N, no deduplication). For a = {1,1} and b = {1}, merge produces {1,1,1} while set_union produces {1,1}.

Output overlapping input:

cpp

// BUG: writing back into one of the input vectors invalidates iterators:
std::set_union(a.begin(), a.end(), b.begin(), b.end(),
               std::back_inserter(a));  // UB

Forgetting pop_back() after pop_heap. pop_heap moves the maximum to v.back() and restores the heap over [begin, end-1). The element is still in the vector — you must call v.pop_back() yourself.

Inconsistent heap comparators across make_heap / push_heap / pop_heap are undefined behavior. Store the comparator alongside the vector when the type is not the default.

Complexity

Algorithm	Time	Comparisons
`set_union`	O(M + N)	at most 2(M+N) − 1
`set_intersection`	O(M + N)	at most 2·min(M,N)
`set_difference`	O(M + N)	at most 2M − 1
`set_symmetric_difference`	O(M + N)	at most 2(M+N) − 1
`includes`	O(M + N)	at most 2N − 1
`make_heap`	O(N)	at most 3N comparisons
`push_heap`	O(log N)
`pop_heap`	O(log N)
`sort_heap`	O(N log N)
`is_heap` / `is_heap_until`	O(N)	C++11

std::ranges Set Operations (C++20)

The ranges versions add projections and sentinel support without changing the underlying algorithm. Every set algorithm in <algorithm> has a std::ranges:: counterpart that accepts range objects directly, accepts separate projections for each input, and works with non-iterator sentinels — eliminating the need to call .begin()/.end() manually.

Projections let you compare elements by a derived key rather than wrapping the comparator in a lambda. The projection is applied to each element before the comparator sees it, keeping the call site concise:

cpp

// C++20
#include <algorithm>
#include <vector>
#include <string>

struct Employee {
    int     id;
    std::string dept;
    int     salary;
};

// Both ranges sorted by id:
std::vector<Employee> team_a{{1, "eng", 120000}, {3, "eng", 95000}, {5, "hr", 80000}};
std::vector<Employee> team_b{{2, "mkt", 75000},  {3, "eng", 95000}, {7, "eng", 110000}};

// Intersection by id — which employees appear in both lists?
std::vector<Employee> both;
std::ranges::set_intersection(team_a, team_b,
                              std::back_inserter(both),
                              std::less{},
                              &Employee::id,   // projection for team_a
                              &Employee::id);  // projection for team_b
// both: {{3, "eng", 95000}}

Sentinels allow the algorithm to work over ranges that don't share a common iterator type, such as null-terminated sequences or lazy views that compute the end on demand. The ranges overloads return a named struct (ranges::set_union_result, etc.) carrying both input and output iterators, which is useful when you need to know where each range was exhausted:

cpp

// C++20
#include <algorithm>
#include <vector>
#include <iterator>

std::vector<int> a{1, 3, 5, 7};
std::vector<int> b{2, 3, 6, 7};
std::vector<int> out;

auto result = std::ranges::set_symmetric_difference(
    a, b, std::back_inserter(out));
// result.in1 points to a.end()
// result.in2 points to b.end()
// result.out is the past-the-end output iterator
// out: {1, 2, 5, 6}

All five set algorithms (set_union, set_intersection, set_difference, set_symmetric_difference, includes) have direct std::ranges:: equivalents added in C++20. std::ranges::includes returns bool, while the four output-producing algorithms return a result struct.

Multi-way Merge with std::merge

std::merge is a two-way operation, but applying it iteratively produces a correct k-way sorted merge. The simplest correct approach is to merge pairs of ranges into a temporary, then merge that temporary with the next range. Each pass is O(total elements), so merging k sorted ranges of size n each costs O(k·n·log k) when done via a reduction tree — the same asymptotic cost as a heap-based k-way merge but with better cache behavior for small k:

cpp

// C++11
#include <algorithm>
#include <vector>
#include <iterator>

std::vector<std::vector<int>> sorted_chunks{
    {1, 5, 9},
    {2, 6, 10},
    {3, 7, 11},
    {4, 8, 12}
};

// Pairwise reduction: merge [0]+[1] → tmp01, merge [2]+[3] → tmp23,
// then merge tmp01+tmp23 → result.
auto pairwise_merge = [](std::vector<int> x, const std::vector<int>& y) {
    std::vector<int> out;
    out.reserve(x.size() + y.size());
    std::merge(x.begin(), x.end(), y.begin(), y.end(),
               std::back_inserter(out));
    return out;
};

std::vector<int> tmp01 = pairwise_merge(sorted_chunks[0], sorted_chunks[1]);
std::vector<int> tmp23 = pairwise_merge(sorted_chunks[2], sorted_chunks[3]);
std::vector<int> result = pairwise_merge(tmp01, tmp23);
// result: {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}

Unlike set_union, std::merge never deduplicates: if element v appears M times across all input ranges, it appears exactly M times in the output. For large k (dozens of sorted streams, e.g., external sort merge phase), a heap-based k-way merge is more cache-efficient because it avoids materialising intermediate vectors:

cpp

// C++17
#include <algorithm>
#include <queue>
#include <vector>

// Heap-based k-way merge — each entry is {value, chunk_index, element_index}.
using Entry = std::tuple<int, int, int>;

std::vector<std::vector<int>> chunks{{1,4,7},{2,5,8},{3,6,9}};
std::priority_queue<Entry, std::vector<Entry>, std::greater<Entry>> pq;

for (int i = 0; i < (int)chunks.size(); ++i)
    if (!chunks[i].empty())
        pq.emplace(chunks[i][0], i, 0);

std::vector<int> merged;
merged.reserve(27);  // total elements across all chunks

while (!pq.empty()) {
    auto [val, ci, ei] = pq.top(); pq.pop();
    merged.push_back(val);
    if (ei + 1 < (int)chunks[ci].size())
        pq.emplace(chunks[ci][ei + 1], ci, ei + 1);
}
// merged: {1, 2, 3, 4, 5, 6, 7, 8, 9}

Set Operations on std::set — Node-level Merging (C++17)

std::set::merge transfers nodes between two sets without allocating or copying elements. Introduced in C++17, it splices nodes from the source set into the destination set if the key is not already present, leaving only the duplicates behind in the source. This is O(N log(size + N)) with zero heap allocations for the moved elements:

cpp

// C++17
#include <set>
#include <string>

std::set<std::string> primary{"apple", "cherry", "elderberry"};
std::set<std::string> secondary{"banana", "cherry", "date"};

// "cherry" is in both — it stays in secondary; others move to primary:
primary.merge(secondary);

// primary:   {"apple", "banana", "cherry", "date", "elderberry"}
// secondary: {"cherry"}   ← only the duplicate remains

The transferred nodes are relinked rather than reallocated, so existing pointers, references, and iterators to moved elements remain valid and now point into the destination container. This guarantee distinguishes merge from erasing-and-inserting:

cpp

// C++17
#include <set>

std::set<int> dst{1, 3};
std::set<int> src{2, 3, 4};

// Save a reference before merging:
const int& ref_to_2 = *src.find(2);

dst.merge(src);
// ref_to_2 is still valid — it now refers to the node in dst
// src: {3}  (3 was already in dst, so its node was not moved)

std::map, std::multiset, and std::multimap all have merge in C++17. For multiset/multimap, every node from the source is always accepted because duplicate keys are permitted, making merge equivalent to a move-insert of every element.

Multiset Operations — Duplicates and equal_range

The set algorithms respect element multiplicity by design, but multisets benefit from targeted queries using std::equal_range. When you need to count or locate all copies of a specific value in a sorted range, std::equal_range returns a [first, last) subrange in O(log N):

cpp

// C++11
#include <algorithm>
#include <vector>
#include <iterator>

std::vector<int> ms{1, 2, 2, 2, 3, 3, 5};  // sorted multiset

auto [lo, hi] = std::equal_range(ms.begin(), ms.end(), 2);
std::ptrdiff_t count = std::distance(lo, hi);  // 3
// [lo, hi) spans all copies of 2

set_intersection and set_difference handle duplicates according to the multiplicity rules from the Overview table, which correctly models multiset semantics. A concrete example shows all three duplicate-aware outputs together:

cpp

// C++11
#include <algorithm>
#include <vector>
#include <iterator>

std::vector<int> a{1, 2, 2, 2, 3};  // 2 appears 3×
std::vector<int> b{2, 2, 3, 3, 4};  // 2 appears 2×, 3 appears 2×

std::vector<int> isect, diff, sym;

std::set_intersection(a.begin(), a.end(), b.begin(), b.end(),
                      std::back_inserter(isect));
// isect: {2, 2, 3}  — min(3,2)=2 twos, min(1,2)=1 three

std::set_difference(a.begin(), a.end(), b.begin(), b.end(),
                    std::back_inserter(diff));
// diff: {1, 2}      — max(0, 3-2)=1 two, max(0,1-2)=0 threes

std::set_symmetric_difference(a.begin(), a.end(), b.begin(), b.end(),
                              std::back_inserter(sym));
// sym: {1, 2, 3, 4} — |3-2|=1 two, |1-2|=1 three

When working with std::multiset directly, use count() for membership queries and equal_range() to iterate over all copies without calling the set algorithms at all. The algorithms shine when input is a plain sorted std::vector and you need a one-shot output range rather than a live container.

See Also

std::merge — merges two sorted ranges retaining all duplicates (M + N total elements)
std::inplace_merge — merges two consecutive sorted sub-ranges in-place, O(N log N)
std::sort — prerequisite for all set algorithms
std::priority_queue — container adaptor wrapping the heap operations
std::set — ordered associative container with O(log N) per-element operations