c++ - Boost `interval_map` - 如何自定义触摸聚合

Question

在将它们添加到集合期间， Boost ICLinterval_set可以加入相互接触的右开区间。例如，interval和将被加入成为一个 interval 。[0,4)[4,8)[0,8)

这对于interval_map- 间隔更复杂，它们相互接触并具有不同的关联值，不会被连接：

#include <iostream>
#include <utility>

#include <boost/icl/interval_map.hpp>

namespace icl = boost::icl;

using IMap = icl::interval_map<int, int>;

int main()
{
  IMap m;
  m += std::make_pair(IMap::interval_type::right_open(0, 4), 1);
  m += std::make_pair(IMap::interval_type::right_open(4, 8), 2);
  std::cout << m << std::endl;
}

该测试程序的输出如下：

{([0,4)->1)([4,8)->2)}

我知道如何自定义重叠聚合的过程，但是我需要自定义另一种情况 -触摸聚合。例如，如果区间相互接触并且左区间的值等于右区间的值减去 1，则区间必须连接，并且生成的区间必须具有左区间的值。所以，上面的程序应该打印：

{([0,8)->1)}

是否可以使用当前可用的 Boost ICL 做到这一点？

我可以对 使用奇怪的操作来做我想做的事interval_map，但我认为这会很麻烦而且效率不高。我更愿意指出正确的方向来使用当前可用的 ICL 自定义、仿函数等。

标签： c++boost-icl

Answer 1

这对于 interval_map 来说更复杂 - 相互接触并具有不同关联值的间隔不会被连接：

没有区别，真的。

我知道如何自定义重叠聚合的过程，但是我需要自定义另一种情况 - 触摸聚合。

你似乎在暗示

 m += std::make_pair(IMap::interval_type::right_open(4, 8), 2);

将插入[4, 8) -> 2.

事实并非如此。这是一个共域组合操作，结果取决于地图的先前状态。

当然，你可以这样写：

m.set({Ival::right_open(4, 8), 2});

如果需要，您可以查询前面的插槽，因此您的操作可能如下所示：

// returns true if joined with preceding slot
bool fill_slot(IMap& m, int from, int till, int value) {
    bool joined = false;
    auto slot = Ival::right_open(from, till);

    if (within(slot, m)) {
        // There is overlap, I don't know how  you want to handle this.
        // You can add some logic here.
    } else {
        auto preceding = m(from - 1);

        if (preceding && value == preceding + 1) {
            joined = true;
            value = preceding;
        }
    }

    m.set({slot, value});
    return joined;
}

现在您可以编写测试用例，例如：

int main() {
    {
        IMap m;
        fill_slot(m,  0,  4,  1);
        fill_slot(m,  4,  8,  2);
        std::cout << m << std::endl;
    }
    {
        IMap m;
        fill_slot(m,  0,  4,  1);
        fill_slot(m,  4,  8,  3);
        std::cout << m << std::endl;
    }
    {
        IMap m;
        fill_slot(m,  0,  4,  1);
        fill_slot(m,  5,  8,  2);
        std::cout << m << std::endl;
    }
}

他们打印Live On Coliru

{([0,8)->1)}
{([0,4)->1)([4,8)->3)}
{([0,4)->1)([5,8)->2)}