Древовидная структура C ++

Question

Справочная информация:

Итак, я портировал часть своего старого Java-кода на C ++, и я столкнулся с проблемой, которая затрудняет работу. Мой проект использует древовидную структуру данных для представления иерархии узлов для 3D-анимации.

Java

public final class Node {

    private final Node mParent;
    private final ArrayList<Node> mChildren;

    //private other data, add/remove children / parents, etc ...
}

В Java довольно просто создать дерево, которое позволяет модифицировать и т. Д.

Проблема:

Я сталкиваюсь с проблемами, связанными с C ++, невозможно легко добавить массивы без выделения вручную нового фрагмента памяти и перемещения существующих, поэтому я переключился на std::vector. У векторов есть проблема делать то, что я только что описал, внутренне делая любые указатели на элементы там недействительными. Поэтому, если вы не хотите использовать указатели, вам нужен способ их поддержки, чтобы память, содержащая фактические узлы, не двигалась. Я считаю, что вы можете использовать std::shared_ptr / std::unique_ptr, чтобы обернуть узлы в std::vector, и я попытался поиграть с этим подходом, но он становится довольно громоздким. Другим вариантом было бы иметь класс «tree», который оборачивает класс узла и является интерфейсом для его манипулирования, но чем (для моего случая использования) было бы довольно раздражающе иметь дело с обрезкой веток и превращением их в собственные деревья и возможно прикрепление разных веток.

Большинство примеров, которые я вижу в Интернете, представляют собой двоичные деревья, которые имеют 2 узла, а не являются динамическими, или они содержат много комментариев об утечках памяти / и т. Д. Я надеюсь, что есть хорошая альтернатива C ++ коду java, показанному выше (без утечки памяти) вопросы и т. д.). Также я не буду заниматься ЛЮБОЙ сортировкой, цель дерева - поддерживать иерархию, чтобы не сортировать ее.

Честно говоря, я действительно не уверен, в каком направлении идти, я провел последние 2 дня, пробуя разные подходы, но ни один из них не "чувствует" себя хорошо, и, как правило, им действительно неудобно управлять, любая помощь будет признательна!

Edit:

Редактирование того, почему shared_ptrs громоздки:

class tree : std::enable_shared_from_this<tree> {

    std::shared_ptr<tree> parent;
    std::vector<std::shared_ptr<tree>> children;

public:

    void set_parent(tree& _tree) {
        auto this_shared_ptr = shared_from_this();
        if (parent != nullptr) {
            auto vec = parent->children;

            auto begin = vec.begin();
            auto end = vec.end();

            auto index = std::distance(begin, std::find_if(begin, end, [&](std::shared_ptr<tree> const& current) -> bool {
                return *current == this_shared_ptr;
            }));

            vec.erase(std::remove(begin, end, index), end);
        }
        parent = std::shared_ptr<tree>(&_tree);
        if (parent != nullptr) {
            parent->children.push_back(this_shared_ptr);
        }
    }

};

работа с указателями, как указано выше, становится довольно многословной, и я надеялся на более простое решение.

Answer 1

Единственная причина разницы, которую вы видите, состоит в том, что вы помещаете объекты непосредственно в сам вектор в c ++ (что вы не можете сделать в Java.) Затем их адреса привязываются к текущему выделенному буферу в векторе. Разница в том, что в Java все объекты выделены, поэтому в массиве находится только «ссылка на объект». Эквивалентом в c ++ было бы создание вектора указателей (возможно, обернутых в объекты интеллектуальных указателей), чтобы векторные элементы были только адресом, а объекты находились в фиксированной памяти. Он добавляет дополнительный указатель прыжка, но тогда будет вести себя больше, чем вы ожидаете в Java.

struct X {
   char buf[30];
};
std::vector<X> myVec{ X() };

Учитывая вышеизложенное, элементы X в myVec являются смежными в распределении. sizeof (myVec [0]) == sizeof (X). Но если вы поместите указатели на вектор:

std::vector<unique_ptr<X>> myVec2{ make_unique<X>() };

Это должно вести себя больше как то, что вы хотите, и указатели не станут недействительными при изменении размера вектора. Указатели будут просто скопированы.

Еще один способ сделать это - немного изменить свой дизайн. Рассмотрим альтернативу указателям целиком, где ваше дерево содержит вектор элементов, а ваши узлы содержат векторы целых чисел, которые являются индексом для этого вектора.

Answer 2

Вы можете хранить свои узлы в одном векторе и использовать относительные указатели, которые не изменяются при изменении размеров векторов:

typedef int32_t Offset;
struct Node {
    Node(Offset p) : parent(p) {}
    Offset parent = 0; // 0 means no parent, so root node
    std::vector<Offset> children;
};

std::vector<Node> tree;
std::vector<uint32_t> free_list;

Чтобы добавить узел:

uint32_t index;
if (free_list.empty()) {
    index = tree.size();
    tree.emplace_back(parent_index - tree.size());
} else {
    index = free_list.back();
    free_list.pop_back();
    tree[index].parent = parent_index - index;
}

tree[parent_index].children.push_back(index - parent_index);

Чтобы удалить узел:

assert(node.children.empty());
if (node.parent) {
    Node* parent = &node + node.parent;
    auto victim = find(parent->children.begin(), parent->children.end(), -node.parent);
    swap(*victim, parent->children.back()); // more efficient than erase from middle
    parent->children.pop_back();
}
free_list.push_back(&node - tree.data());

Answer 3

vector, forward_list, ..., может использоваться любой класс контейнера std (кроме встроенного массива или std :: array). Похоже, ваша проблема в том, что классы java являются типами refrence, а классы C ++ являются типами значений. Фрагмент ниже вызывает ошибку «бесконечная рекурсия» или «использование неполного типа» во время компиляции:

class node{
    node mParent;//trouble
    std::vector<node> children;
    //...
};

Член mParent должен быть ссылочным типом. Для наложения ссылочной семантики вы можете сделать ее необработанным указателем:

node* mParent;

Вы также можете использовать указатель в качестве типа аргумента для контейнера, но как новичок в C ++, который, скорее всего, приведет к утечкам памяти и странным ошибкам во время выполнения. мы должны стараться пока держаться подальше от ручного управления памятью. Поэтому я изменяю ваш фрагмент кода на:

class node{
private:
    node*  const mParent;
    std::vector<node> children;
public:
    //node(node const&)=delete;//do you need copies of nodes? you have to properly define this if yes.
    node(node *parent):
        mParent{parent}{};
    void addChild(/*???*/){
         children.emplace_back(this);
        //...
    };
    //...
};