C++使用操作符重载构建双边树--什么是好的内存解决方案？

Question

所以我之前问了这个问题：，C++ return by value - what happens with the pointer inside?，我想知道，如果我进一步强制父母必须有一个指向他们孩子的指针列表，有没有什么好的解决方案，就不会有任何共享和弱指针的内存泄漏，因为我需要在操作符的主体内动态分配内存。您可以假设计算图是非循环的。

具体考虑my.h：

class Interface{
public:
    int myid();
    Interface(double in);
    ~Interface(){
            std::cout<<"Destroy "<<myid()<<std::endl;
     }
    friend Interface operator+(const Interface& a, const Interface& b);
    void tree();
private:
    class Impl;
    std::shared_ptr<Impl> pimpl;
};
Interface operator+(const Interface& a, const Interface& b);

和my.cpp：

class autodiff::Interface::Impl{
public:
    static int id;
    int myid;
    double value;
    std::vector<std::shared_ptr<autodiff::Interface::Impl>> children;
    std::vector<std::weak_ptr<autodiff::Interface::Impl>> parents;
    Impl(double val) : value(val), myid(++id){};
    ~Impl(){
        std::cout<<"Destroy: "<<myid<<std::endl;
        for(auto it:children)
            it.reset();
    }
    void tree();

};

autodiff::Interface::Interface(double in){
    pimpl = std::make_shared<Impl>(in);
}

int autodiff::Interface::myid() {
    return pimpl->myid;
}

autodiff::Interface& autodiff::operator+(const Interface &a, const Interface &b) {
    Interface* ch = new Interface(a.pimpl->value + b.pimpl->value);
    a.pimpl->children.push_back(ch->pimpl);
    b.pimpl->children.push_back(ch->pimpl);
    ch->pimpl->parents.push_back(a.pimpl);
    ch->pimpl->parents.push_back(b.pimpl);
    return *ch;
}
void autodiff::Interface::tree() {
    pimpl->tree();
}
void autodiff::Interface::Impl::tree() {
    std::cout<<myid<<"-(";
    for(int i=0;i<parents.size();i++)
        if(auto tmp = parents[i].lock())
            std::cout<<tmp->myid<<",";
    std::cout<<")"<<std::endl;
    for(int i=0;i<parents.size();i++)
        if(auto tmp = parents[i].lock())
            tmp->tree();
}

int autodiff::Interface::Impl::id = 0;

输出为：

5-(4,3,)
4-(1,2,)
1-()
2-()
3-()
Destroy: 3
Destroy: 2
Destroy: 1

我想要和期望的是：

5-(4,3,)
4-(1,2,)
1-()
2-()
3-()
Destroy 3
Destroy 2
Destroy 1
Destroy 5
Destroy 4

我的问题是，为什么临时创建的对象4和5不能自动释放？在销毁1、2、3之后，这些实例可能只有weak_ptr而没有shared_ptr，还是我错了？

Answer 1

我没有读到您前面的问题，但是当我编写一个二叉树实现时，我发现使用指向子节点的std::unique_ptr和指向父节点的简单观察原始指针是很方便的，例如

struct Node
{
    Node *parent;
    std::unique_ptr<Node> right;
    std::unique_ptr<Node> left;
};

所有这些都应该初始化为std::nullptr。这样，一旦Node被析构，left或right下面的整个子树就会被正确地析构，因此不需要递归地执行此操作。“观察”指向父节点的指针意味着你永远不应该对它做一些与内存相关的操作，特别是不要删除。