рекурсия — C ++ Ветвление рекурсивной структуры?
У меня есть следующее. Структура является прототипом, поэтому она прекрасно компилируется.
struct vertexNodeInfo
{
vector<vertexNodeInfo> node;
};
Я пытаюсь написать октри вещь Я хочу использовать рекурсивную функцию, чтобы продолжить добавление узла к каждому узлу, пока я не перейду к определенной точке, и тогда функция, а не добавление другого узла, добавляет лист. Я хочу не использовать память, если нет дополнительных узлов или листьев, если это возможно.
Может быть, шаблоны помогут в этой ситуации, но я не уверен, как их использовать …
Я не думаю, что я хорошо объяснил себя. Вот схема:
Я понятия не имею, если то, что я прошу, невозможно или слишком запутанно, чтобы понять, или просто глупо, но я не могу понять это самостоятельно. Мне жаль, что я не могу объяснить это лучше.
Я использую C ++ 98/03 (VC ++ 2008) и не могу использовать C ++ 11
Любая помощь будет высоко ценится.
ДОПОЛНИТЕЛЬНАЯ ИНФОРМАЦИЯ:
Лучшее объяснение: я хочу массив массив массив массив данных. Использование памяти очень важно в этом (я храню несколько миллионов элементов, поэтому один байт имеет огромное значение). Каждый массив может содержать еще 8 массивов, но пока мне не нужно его использовать, я хочу, чтобы каждый из массивов не использовал память. Это что-то вроде октри.
ДОПОЛНИТЕЛЬНАЯ ИНФОРМАЦИЯ:
Вот еще одна диаграмма. Он немного большой, поэтому вам может потребоваться щелкнуть его правой кнопкой мыши и выбрать Open image in new tab сделать его читабельным.
Что я не хочу это «коричневые» (красные + зеленые) блоки, где каждый блок резервирует память как для большего количества узлов, так и для конечных данных. Это использовало бы слишком много памяти для моих нужд.
Это в основном то, что я пытаюсь достичь, для простоты изображено как 2D:
Решение
Без какого-либо (ручного) выделения кучи[1]:
struct NodeInfo {
int id;
};
using Tree = boost::make_recursive_variant<
NodeInfo,
std::vector<boost::recursive_variant_>
>::type;
Я знаю, что варианты имеют свою «сложность», но локальность памяти сохраняется, а ручное управление памятью исключается.
Теперь, чтобы приблизиться к заявленным целям оптимизации, вы можете использовать std::array<T, 8> вместо std::vectorили, возможно, просто сделать vector использовать обычай allocator выделить из пула памяти.
Пример программы (см. Это Жить на Колиру):
#include <iostream>
#include <boost/variant.hpp>
#include <vector>
struct NodeInfo {
int id;
};
using Tree = boost::make_recursive_variant<
NodeInfo,
std::vector<boost::recursive_variant_>
>::type;
// for nicer code:
using Branch = std::vector<Tree>;
using Leaf = NodeInfo;
static std::ostream& operator<<(std::ostream& os, Leaf const& ni) {
return os << ni.id;
}
static std::ostream& operator<<(std::ostream& os, Branch const& b) {
os << "{ ";
for (auto& child: b) os << child << " ";
return os << "}";
}
int main()
{
Branch branch1 {
Leaf { 2 },
Leaf { 1 },
Branch {
Leaf { 42 },
Leaf { -42 },
}
};
Tree tree = Branch { branch1, Leaf { 0 }, branch1 };
std::cout << tree << "\n";
}
Печать:
{ { 2 1 { 42 -42 } } 0 { 2 1 { 42 -42 } } }
[1] (вне использования std :: vector)
Другие решения
Основная структура октри
struct Node {
std::vector<T> items;
std::array<std::unique_ptr<Node>, 8> subnodes;
Box BoundingBox;
};
class Octree {
Node n;
//... stuff
public:
Octree(Box location)
: n(location) {}
};
Если вы отчаянно нуждаетесь в нескольких дополнительных байтах на конечных узлах (и нескольких байтах, потерянных на неконечных узлах), вы можете попробовать использовать указатель на массив подузлов, а не удерживать его в значении.
Сейчас, если T — точка, тогда вы можете избежать использования boost :: варианта, чтобы хранить только items или же subnodesпотому что каждая точка гарантированно существует только в одном подузле, и вы можете выбрать произвольную точку отсечки между items и имея subnodes,
Иначе, если T является своего рода ограничивающим прямоугольником, вы не можете сойти с рук, потому что ограничивающие прямоугольники, которые не вписываются полностью ни в один из подузлов, должны войти в items список, так что items Список должен существовать независимо от того, существуют ли подузлы.
Я также хочу сказать, что, если вы отчаянно нуждаетесь в оптимизации времени или пространства, вам следует серьезно заняться процедурами распределения памяти.
Редактировать: Да, я использовал массив указателей, а не указатель на массив. Короче говоря, описание правильной инициализации этого массива без какой-либо сильной поддержки C ++ 11 является полной сукой, и в моем личном использовании это не оправдывало серьезных проблем, которые у меня действительно были, черт возьми. Ты можешь попробовать std::unique_ptr<std::array<Node>, 8> если ты хочешь. По идее, это должен быть лучший выбор.
Как насчет полиморфизма?
struct TreeElem {
virtual ~TreeElem() {}
};
struct Node : public TreeElem {
std::vector<TreeElem*> _children;
};
struct Leaf : public TreeElem {
int _value;
};
Вы можете выяснить остальное (виртуальные члены TreeElem).
П.С .: Если это более чем тривиально, используйте умные указатели.
Проверь че составной шаблон и вы можете легко адаптировать его для выполнения октре. После этого создайте рекурсивную функцию, которая принимает в качестве аргумента фактическую глубину октодерева, чтобы вы могли легко выполнять то, что вы хотите. К сожалению, я плохо понимаю ваш вопрос, поэтому не могу быть более точным.