对范围项目使用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关系（这意味着对于范围a和b 。equalseta<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并且无需进一步调整即可使用。

Answer 2

你operator <定义偏序： (30,45) < (40, 50) == false同时(40, 50) < (30, 45) == false使来讲std::set和std::map他们是平等的。这就是为什么您得到这些结果。

有一篇关于偏序的论文：https : //en.wikipedia.org/wiki/Partially_ordered_set

您可能想使用std::unordered_map或以某种方式定义范围的总订单。

我建议operator <比较且仅当（a + b）/ 2 <（c + d）/ 2为总阶时，才能比较范围边界的算术平均值，即（a，b）<（c，d）。请注意，您可能希望将float用于算术平均值。

为了进行测试，我建议使用以下代码草案（我从头开始编写但未对其进行测试）。-1表示不包含this

int range::firstContainsMe(const std::vector<range> rangesVec)
{
    for (size_t i = 0; i < rangesVec; i++) {
        if (lower >= rangesVec[i].lower && upper <= rangesVec[i].upper) {
            return i;
        }
    }
    return -1;
}