处理设定间隔的算法 [英] Algorithm to deal with set intervals

问题描述

实现需要跟踪C ++中的设置间隔的类的最佳方法是什么？我希望利用现有的STL或Boost库，但除了使用标准容器之外，我不得不手工实现该算法，这是一件非常棘手的事情，而且由于工作量大，我不得不以牺牲一些性能为代价来简化它最后期限。必须有更好的方法。

What is the best way to go about implementing a class which needs to keep track of set intervals in C++? I was hoping to leverage existing STL or Boost libraries but other than using standard containers, I had to resort to implementing the algorithm by hand which was surprisingly tricky to get right and I had to simplify it at the cost of some performance because of a work deadline. There must be a better way.

例如，我需要以下行为：

For example, I need the following type of behaviour:

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)

注意子范围由下限和上限组成，表示从下限到上限的连续元素集合，其中两个边界都包括在该集合中。该集合的构建是从下限开始，然后递增（operator ++）直到达到上限。

Notes A Subrange consists of a lower bound and an upper bound and denotes a contiguous set of elements from the lower bound to the upper bound, where both bounds are included in the set. The set is constructed starting from the lower bound and incrementing (operator++) until the upper bound is reached.

我看过Boost Interval，它处理区间算术，并且没有似乎无法解决我的问题，但是文档对我而言并不容易理解。如果有人认为这会有所帮助，那么他们可以告诉我如何实现上述示例。

I have looked at Boost Interval which deals with interval arithmetic and doesn't seem to solve my problem but then the documentation is not easy for me to follow. If someone thinks that it will help, then could they please show me how to implement the above example.

出于好奇。我的用例是代理服务器中的缓存算法，该算法需要跟踪客户端请求的数据的时间间隔，并且最好只从尚未缓存的服务器中请求时间间隔的那些部分。如果客户A要求提供2016年1月1日至2016年1月3日的数据，则客户B要求提供2016年1月5日至2016年1月6日的数据，客户C要求提供2016年1月6日至9日的数据-2016年1月-如果客户端D要求从2016年1月1日到2016年1月9日的数据，则代理应该只向服务器请求2016年1月4日，因为其余日期已被缓存。 / p>

For the curious. My use case was for a caching algorithm in a proxy server which needed to keep track of time-intervals of data requested by clients and optimally only ask for those portions of time-intervals from the server that had not already been cached. If client A asks for data from 1-Jan-2016 to 3-Jan-2016, client B asks for data from 5-Jan-2016 to 6-Jan-2016, client C asks for data from 6-Jan-2016 to 9-Jan-2016, then if client D asks for data from 1-Jan-2016 to 9-Jan-2016, then the proxy should only ask the server for 4-Jan-2016 because the rest of the dates are already cached.

推荐答案

您可以使用提升间隔容器库（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]

实时示例

这篇关于处理设定间隔的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！