Mixing
C++ Tree Data Structure
C++ Tree Data Structure
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.
std::vector
std::shared_ptr
std::unique_ptr
std::vector
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.
std::list
std::vector
What is the maximum number of children a node can have? Do you care about performance (1) to an extreme degree, (2) a little, or (3) not really? Do you need to be able to remove nodes from the tree, or only add them?
– John Zwinck
Jun 30 at 2:07
@JohnZwinck It would be mostly a read only tree, so modification to the structure could be slower if it would mean iterating would be faster. As far as the max number of children, there is no clearly defined max, each node can have any number of child nodes. Preferably be able to add / remove nodes, but once the tree is built these operations would be less common.
– Hex Crown
Jun 30 at 2:20
What exactly is so "unwieldy" about std::shared_ptr? The only thing about this, is that you will have to figure out what to do about circular references. The classical solution for this is to use weak pointers for the parent node.
– Sam Varshavchik
Jun 30 at 2:32
If
std::shared_ptr<tree> everywhere is unwieldy, use an alias.– n.m.
2 days ago
std::shared_ptr<tree>
3 Answers
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.
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());
Yeah, I was considering this approach, the thing that had initially steered me away was that the list of nodes would have be be a separate "part", I was hoping the data structure could be self contained in the node itself without an external "helper". In my use-case the "node" is the object that is manipulated directly, rather than a "tree" interface that acts as the accessor. But If this is the only simple way of doing this, perhaps I'll give it another go.
– Hex Crown
Jun 30 at 7:13
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:
vector
forward_list
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;
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);
//...
};
//...
};
By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.
Try
std::listinstead ofstd::vectorfor a quick and dirty solution. Pointers to list elements are not invalidated if elements from the list are removed. But again, this is quick and dirty if you are ok with using std::list.– PaulMcKenzie
Jun 30 at 2:00