C++ - Finding intersection of two ranges

Question

What is the best way to find the intersection of two ranges in C++? For example, if I have one range as [1...20] inclusive, and another as [13...45] inclusive, I want to get [13...20], as that is the intersection between them.

I thought about using the native set intersection function in C++, but I would first have to convert the range into a set, which would take too much computation time for large values.

Quagga

Just write a bunch of ifs. – Molest

set_intersection takes input and output iterators, so you don't have to convert the range into set but... what exactly is a range? – Uriia

Have you looked at this: cplusplus.com/reference/algorithm/set_intersection – Ideational

Answer 1

intersection = { std::max(arg1.min, arg2.min), std::min(arg1.max, arg2.max) };
if (intersection.max < intersection.min) {
  intersection.markAsEmpty();
}

Donn

Answer 2

A simple answer in two steps:

• find end values of intersection range
• List item iterate over this range.

say for the range [l1, r1], [l2, r2] intersection between them can be calculated as:

 if ((r1 < l2) ||  (r2 < l1)) then no intersection exits.
 else l = max(l1, l2) and r = min(r1, r2)

just iterate over the range [l, r] to get the intersection values.

Dekaliter

Answer 3

For the sake of completeness I would like to add a 'boost answer'.

If you're already using boost, you don't need to write your own code but can take the header-only

#include <boost/numeric/interval.hpp>

and use the intersect function dealing with the type interval<T>.

Shon

Answer 4

In 2018, the use of std::set_intersection is highly recommended: https://en.cppreference.com/w/cpp/algorithm/set_intersection. It doesn't have to be from a std::set but the ranges do have to be sorted.

Example:

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
int main()
{
    std::vector<int> v1{1,2,3,4,5,6,7,8};
    std::vector<int> v2{        5,  7,  9,10};
    std::sort(v1.begin(), v1.end());
    std::sort(v2.begin(), v2.end());

    std::vector<int> v_intersection;

    std::set_intersection(v1.begin(), v1.end(),
                          v2.begin(), v2.end(),
                          std::back_inserter(v_intersection));
    for(int n : v_intersection)
        std::cout << n << ' ';
}

Output:

5 7

Bookmark

This is not exactly the same and requires far more memory. And uses far more time to compute. – Epitome

The OP wanted the intersection of intervals, as specified by their lower and upper bounds, not the intersection of sets of objects. – Placement