1

我正在尝试使用 重新实现树数据结构std::unique_ptr，其想法是父节点将拥有其子节点，这些子节点存储在unique_ptr.

出于接口原因，我需要一个节点自行销毁的方法。在这种情况下，我认为节点要从其父节点中的子向量中擦除自身。

以下实现“有效”（在 c++11 编译器中），但它非常丑陋，我确信这是处理此问题的次优方法。

#include <iostream>
#include <memory>
#include <vector>
#include <algorithm>

struct Node {
    typedef std::vector<std::unique_ptr<Node>> vec_node_uptr;

    unsigned        id;
    Node*           parent;
    vec_node_uptr   child_nodes;

    // ctor
    Node(unsigned id): id(id){ parent = nullptr; }

    void add_child(Node* new_child){
        new_child -> parent = this;
        child_nodes.push_back( std::unique_ptr<Node>(std::move(new_child) ) );
    }

    int where_am_i(){
        int result_ = 0;
        for(auto& i: this -> parent -> child_nodes) {
            if (this == i.get()) {
                return result_;
            } else {
                result_++;
            }
        }
    }

    void suicide(){
        parent -> child_nodes.erase(parent -> child_nodes.begin()+ where_am_i());
    }
};


int main()
{
    std::unique_ptr<Node> root(new Node(0));

    root -> add_child(new Node(1));
    root -> add_child(new Node(2));

    root -> child_nodes[0] -> add_child(new Node(3));
    root -> child_nodes[0] -> add_child(new Node(4));
    root -> child_nodes[1] -> add_child(new Node(5));
    root -> child_nodes[1] -> add_child(new Node(6));

    root -> child_nodes[1] -> suicide();

    return 0;
}

有什么建议么？也许使用std::find？

4

2 回答 2

1

您可以使用 find_if 和 lambda 更优雅地解决这个问题：

void suicide() 
{
    auto& parentsChildren = parent->child_nodes;
    parentsChildren.erase(find_if(begin(parentsChildren), end(parentsChildren), 
                           [&](const unique_ptr<Node>& node) { return node.get() == this; }));
}
于 2013-06-07T13:10:51.540 回答
1

如果您希望where_am_i()当前数据结构具有恒定时间，则需要在节点本身中存储索引或迭代器。这是（a）重复和（b）将带来进一步的复杂性，因为每当您删除不是其父级的最后一个子级的节点时，您将需要更新所有后续子级的索引/迭代器......

再说一次，制作一个 constant-time 可能没有真正的优势where_am_i()，因为从向量中删除一个元素无论如何都是 O(n) ，除非你总是从末尾（或接近末尾）删除。

但是，如果您通常从末尾删除，并且如果从不需要将一组子节点的所有权从父节点转移，那么这里有一个替代的、更简单的设计，它避免了在每个节点中存储索引或迭代器的需要节点：

C++ 标准保证std::vectors 与数组一样，其内容将在内存中连续布局。因此，如果child_nodes向量实际上按值存储其元素——即，如果它被声明为

typedef std::vector<Node> vec_node_uptr;
vec_node_uptr child_nodes;

然后你可以通过简单地从给定元素的地址中减去向量中第一个元素的地址来在恒定时间内找到位置，让指针算术为你做除法：

size_t where_am_i() {
    return this - &parent->child_nodes[0];
}
于 2013-06-07T13:10:56.567 回答