What must hold before set_union?

Each input range must be sorted with the same comparison; output is sorted accordingly.

Can I write results into one of the inputs?

Overlapping input and output ranges can cause undefined behavior — use a separate buffer or back_inserter.

set_difference vs set_symmetric_difference?

Difference is A\\B; symmetric difference is elements in exactly one of A or B — useful for diffs and sync.

Duplicates in inputs?

Multiset-style behavior: duplicates are carried through per the standard algorithms — unique first if you need sets.

C++ Set Operations on Sorted Ranges: set_union, intersection & difference

2026년 3월 12일 · 10분 읽기 · 수정 2026년 3월 12일 Intermediate tutorial

이 글의 핵심

Sorted-range set algorithms in C++: math meaning, includes, and practical patterns.

What are set algorithms?

They implement set operations on sorted ranges (not only std::set): union, intersection, difference, symmetric difference, and subset test includes.

Operations

Algorithm	Notation	Meaning
`set_union`	∪	All keys in order
`set_intersection`	∩	In both
`set_difference`	A − B	In A not in B
`set_symmetric_difference`	△	In exactly one
`includes`	⊇	Subsequence / subset test

flowchart TD
    A["A = 1, 2, 3, 4"]
    B["B = 3, 4, 5, 6"]
    
    A --> U["Union\n1, 2, 3, 4, 5, 6"]
    B --> U
    
    A --> I["Intersection\n3, 4"]
    B --> I
    
    A --> D["Difference A-B\n1, 2"]
    B --> D
    
    A --> S["Symmetric diff.\n1, 2, 5, 6"]
    B --> S

Requirements

Sort both ranges with the same comparator before calling. Output typically via std::back_inserter.

includes

Tests whether the second sorted range appears as a subsequence of the first (subset / “all of B in A” for unique sorted keys).

Production patterns

Permissions (sorted includes), tag intersection, change detection with two set_difference calls — same structure as Korean article.

FAQ

Covers definition, sorting requirement, duplicates, O(n+m) merge phase, includes, std::set container vs algorithms, back_inserter, and Effective STL / cppreference.

C++ Algorithm Sort
C++ Algorithm Partition
C++ Algorithm MinMax

Keywords

set_union, set_intersection, set_difference, set_symmetric_difference, includes, sorted range, STL