为什么 boost::icl::interval_map 不加起来呢？

Question

考虑以下程序：

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

struct Value
{
    explicit Value(int v) : v(v), is_empty(false) {}
    Value() : v(0), is_empty(true) {}

    Value& operator+=(const Value& other)
    {
        v += other.v;
        return *this;
    }

    bool operator==(const Value& other) const { return is_empty == other.is_empty; }
    bool operator!=(const Value& other) const { return is_empty != other.is_empty; }

    int v;
    bool is_empty;
};

int main()
{
    boost::icl::interval_map<int, Value> m;
    m.add(std::make_pair(boost::icl::interval<int>::right_open(10, 20), Value(2)));
    m.add(std::make_pair(boost::icl::interval<int>::right_open(15, 30), Value(3)));
    std::cout << m.iterative_size() << '\n';
    std::cout << m.begin()->first.lower() << '\n';
    std::cout << m.begin()->first.upper() << '\n';
    std::cout << m.begin()->second.v << '\n';
}

输出为

问题：

为什么最后一行是2？
区间图不是希望把值加起来，所以是5吗？
如何实现添加区间并保留+=中的值的行为？

我想要以下结果：

{([10,20)->(2))+
      ([15,30)->(3))+ 
                       ([40,50)->(11))}
=
{([10,30)->(5))([40,50)->(11))}

也就是说，当区间相加时，它们被合并，合并后的值被存储为整个合并的区间。

这个操作可能没有数学意义，但这是我程序中需要的。（此外，我不会减去间隔）。

Answer 1

这是我自己对最后一个问题的务实回答的尝试：

How to achieve the behavior that intervals are added and the value from += is preserved?

我找到了另一个 implementation，它更简单，但可以很容易地根据我想要的行为进行定制。它采用区间类型作为模板参数，并使用方法 join 来连接区间，所以我用我自己的区间类型专门化它，它添加值并在连接上求和值：

#include <iostream>
#include "interval_tree.hpp"

using iv_base = lib_interval_tree::interval<int, lib_interval_tree::right_open>;
struct iv_t : iv_base
{
    int value;

    iv_t(const iv_base& base, int v)
        : iv_base(base)
        , value(v)
    {
    }

    iv_t(value_type low, value_type high, int v)
        : iv_base(low, high)
        , value(v)
    {
    }

    iv_t join(iv_t const& other) const
    {
        return iv_t(iv_base::join(other), value + other.value);
    }
};

using it_t = lib_interval_tree::interval_tree<iv_t>;

int main()
{
    it_t it;

    it.insert_overlap(iv_t( 10, 20, 2 ));
    it.insert_overlap(iv_t{ 15, 30, 3 });
    it.insert_overlap(iv_t{ 40, 50, 11 });

    for (decltype(auto) v : it)
    {
        std::cout << v.low() << ".." << v.high() << ":" << v.value << "\n";
    }
}

输出为：

10..30:5
40..50:11

完全可能 Boost.Icl 可以针对相同的行为进行自定义，但要了解是否可能以及如何进行更复杂。

Answer 2

问题在于

bool operator==(const Value& other) const { return is_empty == other.is_empty; }
bool operator!=(const Value& other) const { return is_empty != other.is_empty; }

使任何值“相同”。这使得行为未指定，并且可能最终合并任何接触间隔并保持先前的值（因为根据您自己的operator==它是“相等的”）。

让我们用 C++ 生成更正确的比较：

struct Value {
    explicit Value(int v) : value(v) {}
    Value() : is_empty(true) {}

    Value& operator+=(const Value& other) { value += other.value; return *this; }

    auto operator<=>(Value const&) const = default;

    bool is_empty = false;
    int  value    = 0;
};

现在你可以Live On Compiler Explorer

#include <iostream>
#include <boost/icl/interval_map.hpp>
int main()
{
    namespace icl = boost::icl;
    using I = icl::interval<int>;
    using Value = int;

    auto const a = std::make_pair(I::right_open(10, 20), Value(2));
    auto const b = std::make_pair(I::right_open(15, 30), Value(3));
    auto const c = std::make_pair(I::right_open(40, 50), Value(11));

    icl::interval_map<int, Value> m;
    m.add(a);
    m.add(b);
    m.add(c);

    std::cout << m << "\n";

    m.subtract(a);

    std::cout << m << "\n";
}

打印

{([10,15)->(2))([15,20)->(5))([20,30)->(3))([40,50)->(11))}

但是，我很难理解 Value 在 optional<int> 上添加了什么，实际上已经是 interval_map 的行为了：

int main()
{
    namespace icl = boost::icl;
    using I = icl::interval<int>;

    auto const a = std::make_pair(I::right_open(10, 20), 2);
    auto const b = std::make_pair(I::right_open(15, 30), 3);
    auto const c = std::make_pair(I::right_open(40, 50), 11);

    icl::interval_map<int, int> m;
    m.add(a);
    m.add(b);
    m.add(c);

    std::cout << m << "\n";

    m.subtract(a);

    std::cout << m << "\n";
}

打印：

{([10,15)->2)([15,20)->5)([20,30)->3)([40,50)->11)}
{([15,30)->3)([40,50)->11)}

事实上，在某些方面，您的习惯 Value 对我来说似乎是“错误的”，evem 与固定比较：

Live On Compiler Explorer

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

struct Value {
    explicit Value(int v) : value(v) {}
    Value() : is_empty(true) {}

    Value& operator+=(const Value& other) { value += other.value; return *this; }
    Value& operator-=(const Value& other) { value -= other.value; return *this; }

    auto operator<=>(Value const&) const = default;

    bool is_empty = false;
    int  value    = 0;

    friend std::ostream& operator<<(std::ostream& os, Value const& v) {
        return v.is_empty ? os << "#EMPTY" : os << v.value;
    }
};

int main()
{
    namespace icl = boost::icl;
    using I = icl::interval<int>;

    auto const a = std::make_pair(I::right_open(10, 20), Value(2));
    auto const b = std::make_pair(I::right_open(15, 30), Value(3));
    auto const c = std::make_pair(I::right_open(40, 50), Value(11));

    icl::interval_map<int, Value> m;
    m.add(a);
    m.add(b);
    m.add(c);

    std::cout << m << "\n";

    m.subtract(a);

    std::cout << m << "\n";
}

打印

{([10,15)->2)([15,20)->5)([20,30)->3)([40,50)->11)}
{([10,15)->0)([15,30)->3)([40,50)->11)}

[10,15)->0 是真的想要的吗？

为什么 boost::icl::interval_map 不加起来呢？

Why wouldn't boost::icl::interval_map add up the value?

c++

boost

interval-tree

boost-icl