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

Question

我的目标是表示一个三维空间，该空间被离散为非均匀的bin。

一个bin包含任意类型的元素(类型是确定的)
添加仓位(或仓位所在的区间)时，如果它与之前添加的仓位相交，则应将两者合并。

现在我只添加bin(interval)，然后迭代以获得属于正确bin的元素，但也许在未来我可能需要更改元素/interval并同时访问元素
使用此数据结构的算法应该具有时间效率。

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

现在我正在用包装纸做这件事。F.e.只有两个维度(Y，Z)，并设置为仓：

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-trees或区间树(fe from cgal)编写自己的数据结构。或者调整或扩展助推：：icl。但我不是最高级的程序员。

所以我的问题是：

尽管我的做法很丑陋。。。这会奏效吗？或者可能会出现某些问题吗？

是否有更合适的数据结构？

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

非常感谢您的帮助

Answer 1

是否有更合适的数据结构？

也许你正在寻找Boost几何空间索引容器(例如rtree)

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