c++ - 对范围项使用 std::set 容器

Question

我想在 std::set 中存储一堆范围项容器。

此数据结构应通过重载 std::set 的比较来快速判断特定输入范围是否包含在该集合当前包含的范围之一中。为了使用 set::find检查集合中的一项是否包含输入范围参数的方法。

它还应该支持表示单个点的范围项 (start_range == end_range)。

这是我的实现:

#include <iostream>
#include <map>
#include <set>
using std::set;
using std::map;

class range : public std::pair<int,int>
{
public:
    range(int lower, int upper)
    {
        if (upper < lower)
        {
           first = upper;
           second = lower;
        }
        else
        {
           first = lower;
           second = upper;
        }
    }
    range(int val)
    {
        first = second = val;
    }
    bool operator<(range const & b) const
    {
        if (second < b.first)
        {
            return true;
        }
        return false;
    }
};

下面是我测试数据结构的方式:

int main(int argc, const char * argv[])
{
    std::map<int, std::set<range>> n;

    n[1].insert(range(-50,-40));
    n[1].insert(range(40,50));
    n[2].insert(range(-30,-20));
    n[2].insert(range(20,30));
    n[3].insert(range(-20,-10));
    n[3].insert(range(10,20));

    range v[] = {range(-50,-41), range(30,45), range(-45,-45), range(25,25)};
    int j[] = {1,2,3};
    for (int l : j)
    {
        for (range i : v)
        {
            if (n[l].find(i) != n[l].end())
            {
                std::cout << l << "," << i.first << ","  << i.second << " : " 
                          << n[l].find(range(i))->first  << " "
                          << n[l].find(range(i))->second << std::endl;
            }
        }
    }
}

这是我得到的结果:

1,-50,-41 : -50 -40 --> good 
1,30,45 : 40 50     --> bad
1,-45,-45 : -50 -40 --> good
2,30,45 : 20 30     --> bad
2,25,25 : 20 30     --> good

如您所见，我的代码确实很好地支持单点范围(-45 包含在范围 (-50,-40) 中，25 包含在范围 (20,30) 中)

然而，至于更广泛的范围，我现在的运营商<能够找到 contained关系是equal对于 set术语(意思是对于范围 a 和 b a<b && a<b 。

有没有办法改变这个运算符使其工作？

Answer 1

听起来非常适合使用 Boost Interval Container Library .简而言之，您可以

#include <boost/icl/interval_set.hpp>

// Helper function template to reduce explicit typing:
template <class T>
auto closed(T&& lower, T&& upper)
{
   return boost::icl::discrete_interval<T>::closed(std::forward<T>(lower),
        std::forward<T>(upper));
}

boost::icl::interval_set<int> ranges;

ranges.insert(closed(1, 2));
ranges.insert(closed(42, 50));

std::cout << contains(ranges, closed(43, 46)) << "\n"; // true
std::cout << contains(ranges, closed(42, 54)) << "\n"; // false

这应该很容易插入您的 std::map 并且无需进一步调整即可使用。