c++ - C ++ - 查找两个范围的交集

Question

在 C++ 中找到两个范围交集的最佳方法是什么？例如，如果我有一个包含 [1...20] 的范围，另一个包含 [13...45] 的范围，我想获得 [13...20]，因为这是它们之间的交集。

我曾考虑在 C++ 中使用本机集合交集函数，但我首先必须将范围转换为集合，这对于大值会花费太多计算时间。

Answer 1

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

Answer 2

为了完整起见，我想添加一个“增强答案”。

如果您已经在使用 boost，则无需编写自己的代码，但可以仅使用标头

#include <boost/numeric/interval.hpp>

并使用intersect处理类型的函数interval<T>。

Answer 3

简单的答案是只找到交集范围的结束值，然后迭代这个范围。

说范围[l1, r1]，[l2, r2]它们之间的交集可以计算为：

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

只需遍历范围[l, r]即可获得交点值。

Answer 4

2018年std::set_intersection强烈推荐使用：https ://en.cppreference.com/w/cpp/algorithm/set_intersection 。它不必来自 a std::set，但必须对范围进行排序。

例子：

#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 << ' ';
}

输出：

5 7