c++ - boost::icl::interval_map 重叠的 union

是否可以使 interval_map 具有以下累积行为:

[1..3]->1 +
[2..4]->2 +
[5..7]->3 +
[6..8]->4
=
[1..4]->{1,2}, [5..8]->{3,4}
+
[3..6]->42
=
[1..8]->{1,2,3,4,42}

最佳答案

我想我之前一直在为一个非常相似的问题而苦苦挣扎，并且找不到图书馆支持的方式。



我可能会自己编写插入/组合操作。

我试图在这里想出一个描述性的名称。由于操作感觉类似于将“下降”放入更大的“池”中，因此我将操作称为 mix :

template <typename Map, typename V = typename Map::segment_type>
void mix(Map& m, std::initializer_list<V> drops) {
    typename Map::codomain_combine combine;

    for (auto drop : drops) {
        // combine with all overlapping existing segments
        auto range = m.equal_range(drop.first);

        for (auto it = range.first; it != range.second; ++it) {
            combine(drop.second, it->second);
            drop.first = hull(drop.first, it->first);
        }

        m.set(drop); // logically equivalent to m.add(drop) here
    }
}

有了这个，你可以像这样表达你想要的行为:

int main() {
    using Map      = boost::icl::interval_map<int, Ints>;
    using Interval = Map::interval_type::type;
    Map m;

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

    mix(m, { {Interval::closed(1,3), {1}},
             {Interval::closed(2,4), {2}},
             {Interval::closed(5,7), {3}},
             {Interval::closed(6,8), {4}} });

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

    mix(m, { {Interval::closed(3,6), {42}} });

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

输出将是

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

完整演示

Live On Coliru

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

template <typename Map, typename V = typename Map::segment_type>
void mix(Map& m, std::initializer_list<V> drops) {
    typename Map::codomain_combine combine;

    for (auto drop : drops) {
        // combine with all overlapping existing segments
        auto range = m.equal_range(drop.first);

        for (auto it = range.first; it != range.second; ++it) {
            combine(drop.second, it->second);
            drop.first = hull(drop.first, it->first);
        }

        m.set(drop); // logically equivalent to m.add(drop) here
    }
}

// For debug: an ostreamable std::set<int>
struct Ints : std::set<int> {
    using std::set<int>::set;

    friend std::ostream& operator<<(std::ostream& os, Ints const& s) {
        os << '{';
        for(auto i : s) os << i << ",";
        return os << '}';
    }
};

int main() {
    using Map      = boost::icl::interval_map<int, Ints>;
    using Interval = Map::interval_type::type;
    Map m;

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

    mix(m, { {Interval::closed(1,3), {1}},
             {Interval::closed(2,4), {2}},
             {Interval::closed(5,7), {3}},
             {Interval::closed(6,8), {4}} });

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

    mix(m, { {Interval::closed(3,6), {42}} });

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

关于c++ - boost::icl::interval_map 重叠的 union ，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/47271414/