Моя цель - представить трехмерное пространство, которое дискретизировано неоднородно в виде ящиков.Структура данных на основе интервала (аналогично boost icl)
Бункер содержит элементы произвольного типа (тип определяется).
При добавлении бункера (или интервала, в котором находится корзина), и он пересекается с предыдущим добавленным бином, оба должны быть объединены.
Сейчас я только добавляю бункеры (интервалы), а потом я повторяю, чтобы получить элементы, принадлежащие правильному бункеру, но, возможно, в будущем мне может потребоваться изменить элементы/интервалы и получить доступ к элементам в то же самое время время.
Алгоритм, который использует эту структуру данных, должен быть эффективным по времени.
До сих пор я старался использовать существующие библиотеки и структуры данных, когда это возможно.
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;
Это швы немного Hacky мне :-)
Другой вариант должен был бы написать свою собственную структуру данных, используя б деревья или интервальные деревья (fe от cgal). Адаптация или расширение boost :: icl. Но я не самый продвинутый программист.
Так что мои вопросы:
Несмотря на уродство моего подхода ... это будет работать или существуют определенные проблемы, которые могут возникнуть?
Существуют ли какие-либо структуры данных, которые могут быть более подходящими?
Что мне нужно учитывать при реализации моей собственной структуры данных?
Большое спасибо за вашу помощь