CKTIS / C++
std::set_intersection — intersection of sorted ranges
std::set_intersection copies the common elements of two sorted ranges to a separate destination. It retains duplicates according to the smaller occurrence count, rather than producing only unique values.
Version: C++23; repository compiler flag, production runtime not attested
Syntax
#include <algorithm>
std::set_intersection(first1, last1, first2, last2, result);
std::set_intersection(first1, last1, first2, last2, result, comp);std::set_intersection, declared in <algorithm>, computes the intersection of [first1, last1) and [first2, last2). It does not require std::set containers. This entry covers the classic iterator overloads without an execution policy; they return an iterator past the last element written.
Both ranges must already be sorted using the same ordering: std::less{} by default, or the supplied comparator for the comp overload. The comparator must define a strict weak ordering. Equivalence means !comp(a, b) && !comp(b, a), not necessarily a == b. Unsorted inputs violate a precondition.
If an equivalent value occurs m times in the first range and n times in the second, the result contains the first min(m, n) corresponding elements from the first range. The result stays sorted. The number of comparisons is linear in the combined input length.
The output range must not overlap either input. An ordinary output iterator requires enough writable elements; reserve() alone does not create them. The example uses std::back_inserter(common) to append to a separate vector. The source is an evolving working draft; the example is restricted to API available in C++23.
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, 7};
std::vector<int> common;
std::set_intersection(a.begin(), a.end(), b.begin(), b.end(),
std::back_inserter(common));
for (std::size_t i = 0; i < common.size(); ++i) {
if (i != 0) std::cout << ' ';
std::cout << common[i];
}
std::cout << '\n';
}
Result
2 2 7
The displayed code and declared result were verified in an isolated environment using the method recorded in the verification evidence for this exact version.