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

Question

Boost ICL interval_set 可以加入 right-open 间隔，这些间隔在将它们添加到集合时相互接触。例如，区间 [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 定制、仿函数等。

Answer 1

This is more complicated for the interval_map - intervals, which touch each other and have different associated values, won't be joined:

真的没有区别。

I know how to customize the process of aggregating on overlap, however I need to customize another case - aggregating on touch.

你好像在暗示

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

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

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

当然可以这么写:

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)}