Knowledge baseExam Center
ENEnglish
Choose language13

CKTIS / C++

std::set_union — union of sorted ranges

std::set_union writes the sorted union of two sorted ranges. It preserves the maximum occurrence count of equivalent elements across the inputs, so the result does not necessarily contain only unique values.

Version: C++23; repository compiler flag, production runtime not attested

Syntax

#include <algorithm>
std::set_union(first1, last1, first2, last2, result);
std::set_union(first1, last1, first2, last2, result, comp);

std::set_union, declared in <algorithm>, copies the union of [first1, last1) and [first2, last2) to the output iterator result. It does not require std::set containers. This entry covers ordinary iterator overloads without an execution policy; they return an iterator past the last element written.

Both inputs must be sorted under the same strict weak ordering: std::less{} by default, or the supplied comp. Equivalence means !comp(a, b) && !comp(b, a), not necessarily a == b. Violating the sorting or non-overlap requirements causes undefined behavior.

If an equivalence class occurs m times in the first range and n times in the second, the result contains max(m, n) elements: all m from the first, followed by the final max(n - m, 0) from the second, preserving their order. This is multiset union, not complete duplicate removal.

The output range must not overlap either input and must support every write. std::back_inserter(result) grows a separate vector; reserve() alone does not create elements writable through begin(). Complexity is O(N1 + N2) for input lengths N1 and N2. The example demonstrates duplicate preservation.

Examples

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

int main() {
    const std::vector<int> a{1, 2, 2, 4};
    const std::vector<int> b{2, 3, 3, 4};
    std::vector<int> result;

    std::set_union(a.begin(), a.end(), b.begin(), b.end(),
                   std::back_inserter(result));

    const char* separator = "";
    for (int value : result) {
        std::cout << separator << value;
        separator = " ";
    }
    std::cout << '\n';
}

Result

1 2 2 3 3 4

The displayed code and declared result were verified in an isolated environment using the method recorded in the verification evidence for this exact version.

Sources