C++ algorithm: std::set_intersection Function Template

C++ std::set_intersection

The std::set_intersection function computes the intersection of two sorted ranges and stores the result in a destination range. The result contains only the elements that are present in both input ranges. Both ranges must be sorted according to the same criteria for the function to work correctly.

---

Syntax of std::set_intersection

template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator set_intersection(InputIterator1 first1, InputIterator1 last1,
                                InputIterator2 first2, InputIterator2 last2,
                                OutputIterator result);

template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
OutputIterator set_intersection(InputIterator1 first1, InputIterator1 last1,
                                InputIterator2 first2, InputIterator2 last2,
                                OutputIterator result, Compare comp);

Parameters of std::set_intersection

Parameter	Description
first1, last1	Input iterators defining the first sorted range.
first2, last2	Input iterators defining the second sorted range.
result	Output iterator to the beginning of the destination range where the result is stored.
comp (optional)	A binary comparison function that defines the order of elements. Defaults to <.

---

Return Value of std::set_intersection

Returns an iterator to the end of the destination range containing the intersection of the two input ranges.

---

Examples for std::set_intersection

Example 1: Basic Usage of std::set_intersection

This example demonstrates finding the intersection of two sorted vectors:

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

int main() {
    std::vector<int> set1 = {1, 3, 5, 7};
    std::vector<int> set2 = {3, 5, 6, 7};
    std::vector<int> result(std::min(set1.size(), set2.size()));

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

    result.resize(it - result.begin()); // Adjust size to remove unused elements

    std::cout << "Intersection of sets: ";
    for (int n : result) {
        std::cout << n << " ";
    }
    std::cout << std::endl;

    return 0;
}

Explanation:

1. Include necessary headers:
   • <iostream>: Used for input/output operations.
   • <algorithm>: Includes the std::set_intersection function.
   • <vector>: Used for the std::vector container.
2. Initialize two sorted sets:
   • set1: A vector containing {1, 3, 5, 7}.
   • set2: A vector containing {3, 5, 6, 7}.
   • Both vectors must be sorted in ascending order for std::set_intersection to work correctly.
3. Prepare a result vector:
   • A vector named result is initialized with a size equal to the minimum size of set1 and set2.
4. Perform the set intersection operation:
   • The function std::set_intersection calculates the common elements between set1 and set2.
   • It takes five arguments:
     • set1.begin(): Iterator pointing to the beginning of set1.
     • set1.end(): Iterator pointing to the end of set1.
     • set2.begin(): Iterator pointing to the beginning of set2.
     • set2.end(): Iterator pointing to the end of set2.
     • result.begin(): Iterator pointing to the beginning of the result vector, where the intersecting elements will be stored.
   • The function returns an iterator pointing to the end of the resulting range in the result vector.
5. Resize the result vector:
   • The size of the result vector is adjusted to remove unused elements using result.resize(it - result.begin()).
6. Output the intersection of the sets:
   • The program uses a for loop to iterate over the elements in the result vector and prints them separated by spaces.
   • The output is: "Intersection of sets: 3 5 7", as these are the common elements between set1 and set2.

Output:

Intersection of sets: 3 5 7

Example 2: Using a Custom Comparison Function for std::set_intersection

This example demonstrates finding the intersection of two sorted ranges in descending order using a custom comparison function:

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

bool descending(int a, int b) {
    return a > b;
}

int main() {
    std::vector<int> set1 = {7, 5, 3, 1};
    std::vector<int> set2 = {7, 6, 5, 3};
    std::vector<int> result(std::min(set1.size(), set2.size()));

    auto it = std::set_intersection(set1.begin(), set1.end(), set2.begin(), set2.end(), result.begin(), descending);

    result.resize(it - result.begin()); // Adjust size to remove unused elements

    std::cout << "Intersection of sets in descending order: ";
    for (int n : result) {
        std::cout << n << " ";
    }
    std::cout << std::endl;

    return 0;
}

Output:

Intersection of sets in descending order: 7 5 3

Exception Handling in std::set_intersection

The std::set_intersection function does not throw exceptions on its own. However, the comparison function passed as an argument may throw exceptions, which can be caught and handled appropriately.

Example 1: Exception in Custom Comparison Function

This example demonstrates how exceptions in a custom comparison function are handled:

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

bool faulty_compare(int a, int b) {
    if (a == 3 || b == 3) {
        throw std::runtime_error("Comparison involving 3 is not allowed.");
    }
    return a < b;
}

int main() {
    std::vector<int> set1 = {1, 3, 5, 7};
    std::vector<int> set2 = {3, 5, 6, 7};
    std::vector<int> result(std::min(set1.size(), set2.size()));

    try {
        auto it = std::set_intersection(set1.begin(), set1.end(), set2.begin(), set2.end(), result.begin(), faulty_compare);

        result.resize(it - result.begin()); // Adjust size to remove unused elements

        std::cout << "Intersection of sets: ";
        for (int n : result) {
            std::cout << n << " ";
        }
        std::cout << std::endl;
    } catch (const std::exception& e) {
        std::cerr << "Exception caught: " << e.what() << std::endl;
    }

    return 0;
}

Output:

Exception caught: Comparison involving 3 is not allowed.