Introduction

std::set_intersection computes common elements between two sorted ranges. Its complexity is linear in the total number of input elements examined, which makes it efficient for already sorted data. Understanding this complexity helps you reason about both algorithm runtime and preprocessing costs.

Time Complexity of set_intersection

For two sorted ranges of sizes n and m, set_intersection runs in at most n + m - 1 comparisons in typical implementations, so complexity is linear in n + m. The algorithm advances iterators through both ranges similarly to merge logic.

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main() {
6    std::vector<int> a{1, 2, 3, 5, 8};
7    std::vector<int> b{2, 3, 4, 8, 9};
8    std::vector<int> out;
9
10    std::set_intersection(a.begin(), a.end(),
11                          b.begin(), b.end(),
12                          std::back_inserter(out));
13
14    for (int x : out) std::cout << x << ' ';
15    std::cout << '
16';
17}

Because both inputs are traversed once, this is often faster and simpler than nested lookups when ranges are already sorted.

Sorted Input Requirement and Overall Cost

The algorithm requires sorted ranges under the same comparator. If inputs are unsorted, you must sort first, which adds preprocessing cost. In that scenario, total runtime becomes sorting plus intersection.

1std::sort(a.begin(), a.end());
2std::sort(b.begin(), b.end());
3std::vector<int> out;
4std::set_intersection(a.begin(), a.end(), b.begin(), b.end(), std::back_inserter(out));

When data is reused for multiple intersections, sorting once and intersecting many times is usually effective. If data is one shot and unsorted, hashing approaches may be competitive depending on memory and distribution.

Practical Performance Considerations

Big O gives growth behavior, but constants still matter. Iterator category, cache locality, and output allocation strategy all affect real speed. For large vectors, reserving output capacity can reduce reallocations.

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));

Also ensure comparator consistency. If one range uses custom ordering and the other does not, results are undefined. Keep comparator policy centralized to avoid subtle correctness bugs.

Duplicates, Output Size, and Correctness

set_intersection writes each common value the minimum number of times it appears in both ranges. This matters when inputs contain duplicates because output size can be smaller than either input but larger than the count of distinct shared values.

1std::vector<int> a{1, 2, 2, 2, 3};
2std::vector<int> b{2, 2, 4};
3std::vector<int> out;
4
5std::set_intersection(a.begin(), a.end(),
6                      b.begin(), b.end(),
7                      std::back_inserter(out));
8// out is 2, 2

From a complexity perspective, duplicate density does not change the linear scan property, but it does affect output allocation and downstream processing costs. If you need unique intersection only, run deduplication or use set containers first.

For robust code, add unit tests covering empty ranges, identical ranges, and highly duplicated ranges. Complexity reasoning is useful, but correctness across edge shapes is what prevents production defects.

When memory footprint matters, stream output to an iterator that writes into a preallocated buffer or file backed structure instead of building large temporary vectors. Algorithmic complexity stays linear, but memory behavior can improve significantly for large datasets.

If one input is much smaller than the other and unsorted, an alternative strategy is hashing the small input and scanning the larger input once. Compare this against sorting plus intersection with real benchmarks before choosing an implementation.

Common Pitfalls

• Calling set_intersection on unsorted ranges.
• Assuming complexity excludes sorting when inputs are not pre sorted.
• Ignoring comparator consistency across both ranges.
• Forgetting that duplicate handling follows sorted sequence semantics.
• Benchmarking without including allocation overhead.

Summary

• std::set_intersection is linear in total input range lengths.
• Sorted input is required for correctness.
• Include sorting time when inputs are initially unsorted.
• Reserve output capacity for large datasets.
• Validate comparator and data assumptions in tests.