How to Find Intersection of Two Sets in C++ Quickly

To find the intersection of two sets in C++, use the std::set_intersection algorithm from the <algorithm> header. It requires sorted input ranges and outputs the common elements into a container like std::vector or std::set.

Syntax

The std::set_intersection function finds common elements between two sorted ranges. It has this form:

std::set_intersection(
    InputIt1 first1, InputIt1 last1,
    InputIt2 first2, InputIt2 last2,
    OutputIt d_first);

Where:

• first1, last1: iterators for the first sorted range
• first2, last2: iterators for the second sorted range
• d_first: iterator to the start of the destination container

The function copies the common elements to the destination and returns an iterator to the end of the output range.

cpp

std::set_intersection(
    InputIt1 first1, InputIt1 last1,
    InputIt2 first2, InputIt2 last2,
    OutputIt d_first);

Example

This example shows how to find the intersection of two std::set<int> containers and store the result in a std::vector<int>. Both sets are already sorted, which is required.

cpp

#include <iostream>
#include <set>
#include <vector>
#include <algorithm>

int main() {
    std::set<int> set1 = {1, 2, 3, 4, 5};
    std::set<int> set2 = {3, 4, 5, 6, 7};

    std::vector<int> intersection;

    // Reserve enough space for the intersection
    intersection.reserve(std::min(set1.size(), set2.size()));

    auto it = std::set_intersection(
        set1.begin(), set1.end(),
        set2.begin(), set2.end(),
        std::back_inserter(intersection));

    std::cout << "Intersection elements: ";
    for (int num : intersection) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

Output

Intersection elements: 3 4 5 

Common Pitfalls

• Input ranges must be sorted: std::set_intersection requires both input containers to be sorted. If they are not, the result will be incorrect or empty.
• Output container size: The output container should have enough space or use an inserter like std::back_inserter to avoid overflow.
• Using unsorted containers: If you use containers like std::unordered_set, you must first copy and sort them before using std::set_intersection.

cpp

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

int main() {
    std::vector<int> v1 = {5, 3, 1, 4, 2}; // Not sorted
    std::vector<int> v2 = {3, 4, 5, 6, 7};
    std::vector<int> intersection;

    // Wrong: input not sorted
    auto it_wrong = std::set_intersection(
        v1.begin(), v1.end(),
        v2.begin(), v2.end(),
        std::back_inserter(intersection));

    std::cout << "Wrong intersection size: " << (it_wrong - intersection.begin()) << std::endl;

    // Correct: sort before intersection
    std::sort(v1.begin(), v1.end());
    intersection.clear();
    auto it_right = std::set_intersection(
        v1.begin(), v1.end(),
        v2.begin(), v2.end(),
        std::back_inserter(intersection));

    std::cout << "Correct intersection elements: ";
    for (int n : intersection) std::cout << n << " ";
    std::cout << std::endl;

    return 0;
}

Output

Wrong intersection size: 0
Correct intersection elements: 3 4 5 

Quick Reference

• Use std::set_intersection from <algorithm> for intersection.
• Input containers must be sorted.
• Use std::back_inserter to safely insert into output containers like std::vector.
• Works with any sorted ranges, not just std::set.

Key Takeaways

Use std::set_intersection with sorted input ranges to find common elements.

Always ensure input containers are sorted before calling std::set_intersection.

Use std::back_inserter to safely add results to dynamic containers like std::vector.

std::set_intersection works with any sorted ranges, not just std::set containers.