c++ - C++ - 2 つの範囲の交点を見つける

Question

C++で2つの範囲の交点を見つける最良の方法は何ですか? たとえば、[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

完全を期すために、「ブーストアンサー」を追加したいと思います。

すでにブーストを使用している場合は、独自のコードを記述する必要はありませんが、ヘッダーのみを取ることができます

#include <boost/numeric/interval.hpp>

intersecttype を扱う関数を使用しますinterval<T>。

Answer 3

2018 年には、httpsstd::set_intersection ://en.cppreference.com/w/cpp/algorithm/set_intersection の使用を強くお勧めします。からである必要はありませんが、範囲をソートする必要があります。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