Нахождение пересечения двух диапазонов
Каков наилучший способ найти пересечение двух диапазонов в C ++? Например, если у меня есть один диапазон как [1 … 20] включительно, а другой как [13 … 45] включительно, я хочу получить [13 … 20], так как это пересечение между ними.
Я думал об использовании встроенной функции пересечения множеств в C ++, но сначала мне пришлось бы преобразовать диапазон в набор, что потребовало бы слишком большого времени вычисления для больших значений.
Решение
intersection = { std::max(arg1.min, arg2.min), std::min(arg1.max, arg2.max) };
if (intersection.max < intersection.min) {
intersection.markAsEmpty();
}
Другие решения
Для полноты картины я хотел бы добавить «положительный ответ».
Если вы уже используете boost, вам не нужно писать собственный код, но вы можете использовать только заголовок
#include <boost/numeric/interval.hpp>
и использовать intersect функция, имеющая дело с типом interval<T>,
В 2018 году использование std::set_intersection настоятельно рекомендуется: https://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