C++ Tree Data Structure

Question

Background:

So I've been porting some of my older Java code to C++, and I've come across an issue that's making proceeding quite difficult. My project uses a tree data-structure to represent the node hierarchy for 3D animation.

Java:

public final class Node {

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

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

In Java, its quite simple to create a tree that allows for modification etc.

Problem:

I'm running into issues is with C++, arrays cannot easily be added to without manually allocating a new chunk of memory and having the existing ones moved over so I switched to std::vector. Vectors have the issue of doing what I just described internally making any pointers to there elements invalid. So basically if you wan't to use pointers you need a way to back them so memory holding the actual nodes doesn't move. I herd you can use std::shared_ptr/std::unique_ptr to wrap the nodes in the std::vector, and I tried to play around with that approach but it becomes quite unwieldy. Another option would be to have a "tree" class that wraps the node class and is the interface to manipulate it, but than (for my use case) it would be quite annoying to deal with cutting branches off and making them into there own trees and possibly attaching different branches.

Most examples I see online are Binary trees that have 2 nodes rather than being dynamic, or they have many comments about memory leaks / etc. I'm hoping there's a good C++ alternative to the java code shown above (without memory leak issues etc). Also I won't be doing ANY sorting, the purpose of the tree is to maintain the hierarchy not to sort it.

Honestly I'm really unsure of what direction to go, I've spent the last 2 days trying different approaches but none of them "feel" right, and are usually really awkward to manage, any help would be appreciated!

Edit:

An edit as to why shared_ptrs are unwieldy:

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);
        }
    }

};

working with pointers like above becomes really quite verbose, and I was hoping for a more simple solution.

Answer 1

vector, forward_list, ..., any std container class (other than built-in array or std::array) may be used. Your trouble seems to be that java classes are refrence types, while C++ classes are value types. The snippet below triggers "infinite recursion" or "use of incomplete type" error at compiletime:

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

the mParent member must be a reference type. In order to impose reference semantics you can make it a raw pointer:

node* mParent;

you may also use pointer as the argument type to the container, but as a C++ beginer that would most probably lead to memory leaks and wierd runtime errors. we should try to stay away from manual memory management for now. So the I modify your snippet to:

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);
        //...
    };
    //...
};

Answer 2

You could store your nodes in a single vector and use relative pointers that are not changed when the vectors are resized:

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;

To add a node:

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);

To remove a node:

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

The only reason for the difference you're seeing is if you put the objects directly in the vector itself in c++ (which you cannot do in Java.) Then their addresses are bound to the current allocated buffer in the vector. The difference is in Java, all the objects themselves are allocated, so only an "object reference" is actually in the array. The equivalent in c++ would be to make a vector of pointers (hopefully wrapped in smart pointer objects) so the vector elements only are an address, but the objects live in fixed memory. It adds an extra pointer hop, but then would behave more like what you expect in java.

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

Given the above, the X elements in myVec are contiguous, in the allocation. sizeof(myVec[0]) == sizeof(X). But if you put pointers in the vector:

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

This should behave more like what you want, and the pointers will not become invalid when the vector resizes. The pointers will merely be copied.

Another way you could do this would be to change things a little in your design. Consider an alternate to pointers entirely, where your tree contains a vector of elements, and your nodes contain vectors of integers, which are the index into that vector.