0

考虑以下程序：

#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';
}

输出是

1
10
30
2

问题：

  • 为什么最后一行是2？
  • 区间图是不是应该把值加起来，所以它是 5？
  • 如何实现添加间隔并+=保留值的行为？

我想要以下结果：

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

也就是说，当添加间隔时，它们被合并，并且组合值被存储用于整个合并的间隔。

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

4

2 回答 2

1

问题是

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

现在您可以使用编译器资源管理器

#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方式对我来说似乎是“错误的”，即使是固定比较：

Live On 编译器资源管理器

#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是有意的，想要的吗？

于 2022-02-21T23:25:53.397 回答
1

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

如何实现添加间隔并+=保留值的行为？

我发现了另一种实现方式，更简单，但可以很容易地根据我想要的行为进行定制。它将区间类型作为模板参数，并使用方法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 可以针对相同的行为进行定制，但要了解它是否可能以及如何做到这一点更加复杂。

于 2022-02-21T14:46:31.780 回答