CODEWITHSUNDEEP
c++rangeintersectionset-intersection
1110101001
1110101001

Reputation: 5107

C++ - Finding intersection of two ranges

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.

Upvotes: 14

Views: 15611

Answers (4)

y_159
y_159

Reputation: 556

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.

Upvotes: 7

Casey
Casey

Reputation: 10976

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

Upvotes: -1

yau
yau

Reputation: 555

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>.

Upvotes: 5

Angew is no longer proud of SO
Angew is no longer proud of SO

Reputation: 171197

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

Upvotes: 42

Related Questions