处理设定间隔的算法

Question

实现一个需要在C++中跟踪设置间隔的类的最佳方法是什么？我希望利用现有的STL或Boost库,但除了使用标准容器之外,我不得不求助于手动实现算法,这非常难以实现,我必须以某些性能为代价来简化它,因为工作最后期限.肯定有更好的办法.

例如,我需要以下类型的行为:

class SubRange
{
public:
SubRange(const T& lower_bound, const T& upper_bound);
...
};

Subrange r1(1,3);
Subrange r2(5,6);
Subrange r3(6,9);

Subrange tot = r1+r2+r3;
cout << tot;  //displays (1,3) (5,9)

Subrange gaps = SubRange(1,9) - tot;
cout << gaps; // displays (4,4)

注释子范围由下限和上限组成,表示从下限到上限的连续元素集,其中两个边界都包含在集合中.从下限和递增(运算符++)开始构造集合,直到达到上限.

我已经看过Boost Interval处理区间运算并且似乎没有解决我的问题但是文档对我来说并不容易.如果有人认为它会有所帮助,那么他们可以告诉我如何实现上面的例子.

对于好奇.我的用例是代理服务器中的缓存算法,它需要跟踪客户端请求的数据的时间间隔,并且最好只询问服务器中尚未缓存的那些时间间隔部分.如果客户A要求2016年1月1日至2016年1月3日的数据,客户B要求提供2016年1月5日至2016年1月6日的数据,客户C要求提供2016年1月6日至9日的数据-Jan-2016,然后如果客户D要求2016年1月1日到2016年1月9日的数据,那么代理应该只询问服务器2016年1月4日,因为其余日期已经缓存.

Answer 1

您可以使用Boost Interval Container Library(ICL)执行此任务:

#include <iostream>
#include <boost/icl/interval_set.hpp>

int main()
{
    using IntervalSet = boost::icl::interval_set<int>;
    using Interval = boost::icl::interval<int>;

    IntervalSet set;

    set.insert(Interval::closed(1,3));
    set.insert(Interval::closed(5,6));
    set.insert(Interval::closed(6,9));

    std::cout << set << std::endl;

    IntervalSet total;
    total.insert(Interval::closed(1,9));

    std::cout << total << std::endl;

    IntervalSet diff_set = total - set;
    std::cout << diff_set << std::endl;

    for (auto it : diff_set)
    {
        // convert (possibly) open interval into closed
        std::cout << "[" << boost::icl::first(it) << "," << boost::icl::last(it) << "]"<< std::endl;
    }
}

输出:

{[1,3][5,9]}
{[1,9]}
{(3,5)}
[4,4]

live example