Knowledge baseExam Center
ENEnglish
Choose language13

CKTIS / C++

std::set_difference — difference of sorted ranges

std::set_difference copies the difference of two sorted ranges into a separate destination. It accounts for duplicates: each equivalent occurrence in the second range cancels one occurrence from the first range's result.

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

Syntax

std::set_difference(first1, last1, first2, last2, result)
std::set_difference(first1, last1, first2, last2, result, comp)

std::set_difference, declared in <algorithm>, computes the directional difference A − B, not the symmetric difference. It accepts two half-open iterator ranges and an output iterator; it does not require std::set containers. The calls described here do not use an execution policy.

Both ranges must be sorted using the same ordering: std::less{} by default, or comp in the second form. The comparator must define a strict weak ordering. Equivalence means !comp(a, b) && !comp(b, a), not necessarily a == b. Violating the sortedness precondition causes undefined behavior.

The algorithm preserves duplicates: for m equivalent elements in the first range and n in the second, it copies the last max(m - n, 0) elements from the first, in their original order. The result is sorted; the inputs remain unchanged.

The destination must not overlap either input range. If the output iterator overwrites elements in a range, that range must contain enough existing writable elements. An output iterator need not refer to existing elements, though: std::back_inserter appends elements to a container, and std::ostream_iterator writes to a stream. The returned iterator points past the written result. Complexity is linear in the combined input lengths, excluding any prior sorting.

Examples

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

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

    std::set_difference(a.begin(), a.end(), b.begin(), b.end(),
                        std::back_inserter(difference));

    for (std::size_t i = 0; i < difference.size(); ++i) {
        if (i != 0) std::cout << ' ';
        std::cout << difference[i];
    }
    std::cout << '\n';
}

Result

1 2 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