C++ 跟踪离散 space 序列

Question

我有一个离散的 space（比如整数）。他们分成几组说：

group A: 1, 4, 6
group B: 2, 3, 5
etc

组中的项目是有序的，组与组之间没有重复的数字。

我有一个处理程序，可以将每个组的新项目汇集在一起，其中可能有零个或多个新项目。

说：

pool Group A - returns 1, 4
pool Group B - returns 2, 3
pool Group A - returns 6
pool Group B - returns 5

向组中添加新项目并将其合并的过程是连续的。

我需要能够随时判断已经处理过的离散 space 中是否存在漏洞。

在这个例子中，当我处理 1 - 结果是 no - 没有洞。然后我一处理4，这就在1和4之间创建了一个洞。然后添加2，还有洞，但是当我添加3时，就没有洞了。

我正在考虑使用 boost::interval，我只是在每个项目出现时添加它。看起来非常容易实现，但是提升间隔针对间隔进行了优化。我不喜欢使用 std::vector 或 boost::dynamic_bitset，因为我没有理由继续增加跟踪的内存占用。我不需要处理了哪些数字 - 我只需要能够判断是否存在漏洞。

性能要求高。我很好奇有没有更好的方法来做到这一点。有什么想法吗？

Answer 1

正如您所怀疑的，您确实可以使用 Boost ICL。

默认区间组合样式是"Joining"。这正是您所需要的！所以，回家了运行.

这是一个简单的演示，其中包含示例中给出的输入事件。我打印每个事件的记录状态（支持 Boost ICL IO！）。

Live On Coliru

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

using Set      = boost::icl::interval_set<int>;
using Interval = Set::interval_type;

int main() {

    Set record;

    // pool Group A - returns 1, 4
    // pool Group B - returns 2, 3
    // pool Group A - returns 6
    // pool Group B - returns 5

    int stepcount = 0;

    for (int sample : {
            1, 4,
            2, 3,
            6,
            5 })
    {
        record.insert(sample);
        std::cout << "state at #" << ++stepcount << ": " << record << "\n";
    }
}

打印：

state at #1: {[1,1]}
state at #2: {[1,1][4,4]}
state at #3: {[1,2][4,4]}
state at #4: {[1,4]}
state at #5: {[1,4][6,6]}
state at #6: {[1,6]}

如你所见，当3关闭时，差距确实消失了。这似乎正是你 want/described.

Note You'll be happy to know that if holes are rare/big (contiguous ranges are "holes") then ICL will even get you highly compressed storage representation. That's in the core of the library features. So, profile things, I think you'll be fine with this.

如果您需要更好的可扩展性，您或许可以选择 t运行cate 随着数量的增加您不再需要的 "history"。你会做

record.erase(Interval::open(0, 4));
std::cout << "state after erase: " << record << "\n";

哪个会打印

state after erase: {[4,6]}

C++ 跟踪离散 space 序列

c++ tracking discrete space sequence

c++

boost

intervals