c++ - 基于区间的数据结构(类似于boost icl)

Question

我的目标是表示一个 3D 空间，该空间被非均匀地离散化为 bin。

一个 bin 包含任意类型的元素(类型是确定的)。
当添加一个 bin(或 bin 所在的区间)并且它与之前添加的 bin 相交时，两者都应该合并。

现在我只添加 bins(intervals) 然后我迭代以获取属于正确 bin 的元素，但也许将来我可能需要同时更改元素/间隔和访问元素.
使用这种数据结构的算法应该是时间高效的。

到目前为止，我倾向于尽可能使用现有的库和数据结构。
Boost::ICL 接缝很方便，但问题可能出在合并上。

现在我正在用一个包装器来做这件事。 F.e.只有两个维度(Y，Z)和一个集合作为 bin:

class Set_wrapper : public boost::enable_shared_from_this<Set_wrapper>
{
public:
    Set_wrapper() :
        mValue(new boost::shared_ptr<std::set<int> >(new std::set<int>()))
    {
    }
    Set_wrapper(const std::set<int> & s)
    {
        mValue.reset(new boost::shared_ptr<std::set<int> >(new std::set<int>(s)));
    }
    void operator+=(const Set_wrapper &s)
    {
        Set_wrapper* sp = (Set_wrapper*) &s;
        (*sp->mValue)->insert((*mValue)->begin(), (*mValue)->end());
        *mValue = *(sp->mValue);
    }
    bool operator==(const Set_wrapper &s) const
    {
        return *s.mValue == *mValue;
    }

    boost::shared_ptr<boost::shared_ptr<std::set<int>>> mValue;

};

typedef interval_map<double, Set_wrapper> ZMap;

class Z_map_wrapper : public boost::enable_shared_from_this<Z_map_wrapper>
{
public:
    Z_map_wrapper() :
        mValue(new boost::shared_ptr<ZMap>(new ZMap()))
    {
    }
    Z_map_wrapper(const ZMap & s)
    {
        mValue.reset(new boost::shared_ptr<ZMap>(new ZMap(s)));
    }

    void operator+=(const Z_map_wrapper &s)
    {
        Z_map_wrapper* sp = (Z_map_wrapper*) &s;
        for(auto it = (*mValue)->begin(); it != (*mValue)->end(); ++it)
        {
          *(*sp->mValue) += std::make_pair(it->first, it->second);
        }
        *mValue = *(sp->mValue);
    }
    bool operator==(const Z_map_wrapper &s) const
    {
        return *s.mValue == *mValue;
    }

    boost::shared_ptr<boost::shared_ptr<ZMap>> mValue;

};

typedef interval_map<double, Z_map_wrapper> YMap;

这对我来说有点老套:-)

另一种选择是使用 b 树或区间树(来自 cgal 的 fe)编写我自己的数据结构。 或者改编或扩展 boost::icl。但我不是最高级的程序员。

所以我的问题是:

尽管我的方法很丑陋......这会奏效还是会出现某些问题？

有没有更合适的数据结构？

实现自己的数据结构时需要考虑什么？

非常感谢您的帮助

Answer 1

Are there any data structures that might be more suitable?

也许您正在寻找 Boost 几何图形 Spatial Index containers (例如 rtree)

这可能意味着您必须进行合并，但至少您可以免费获得可伸缩性要求:查找速度快、空间查询可用并且迭代是一项功能。