C++ 树数据结构 [英] C++ Tree Data Structure

问题描述

背景:

所以我一直在将一些旧的 Java 代码移植到 C++，但我遇到了一个问题，这使得处理变得非常困难.我的项目使用树数据结构来表示 3D 动画的节点层次结构.

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 ...
}

在 Java 中，创建一个允许修改等的树非常简单.

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

问题:

我遇到了 C++ 的问题，如果不手动分配新的内存块并移动现有的内存块，就无法轻松添加数组，因此我切换到 std::vector.向量的问题是做我刚刚在内部描述的使指向那里元素的任何指针无效的问题.所以基本上如果你不想使用指针，你需要一种方法来支持它们，这样保存实际节点的内存就不会移动.我认为你可以使用 std::shared_ptr/std::unique_ptr 将节点包装在 std::vector 中，我试图使用这种方法，但它变得非常笨拙.另一种选择是有一个树"类来包装节点类并且是操作它的接口，但是(对于我的用例)处理切断分支并将它们变成自己的树会很烦人并可能附加不同的分支.

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.

我在网上看到的大多数例子都是有 2 个节点而不是动态的二叉树，或者他们有很多关于内存泄漏等的评论.我希望有一个很好的 C++ 替代上面显示的 Java 代码(没有内存泄漏)问题等).另外我不会做任何排序，树的目的是维护层次结构而不是排序.

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.

老实说，我真的不确定要往哪个方向发展，过去 2 天我一直在尝试不同的方法，但没有一个感觉"正确，而且通常很难管理，任何帮助将不胜感激！

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!

关于为什么 shared_ptrs 笨拙的

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.

推荐答案

您可以将节点存储在单个向量中，并使用在调整向量大小时不会改变的相对指针:

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;

添加节点:

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

这篇关于C++ 树数据结构的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！