C++ building a double sided Tree with operator overloading - what is good memory solution?

Question

So following this question I asked before: C++ return by value - what happens with the pointer inside? I was wondering if further I impose that the parents have to have a list of pointer to their children, is there any good solution, in terms of not having any memory leaks with shared and weak pointers in any way, since I will need to dynamically allocate memory inside the body of the operator. You can assume that the compute graph is acyclic.

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

And the 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;

The output is:

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

Where what I want and expect was:

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

My question is why aren't the temporary created objects 4 and 5 get freed automatically? After 1,2,3 are destroyed there could be only weak_ptr to those instance and no shared_ptr or am I wrong?

score 0 · Answer 1 · answered Mar 22 '15 at 21:14

0

I didn't read your previous question, but when I was once writing a binary tree implementation, I found it convenient to use std::unique_ptr to the children nodes and a simple observing raw pointer to the parent node, i.e. something like

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

All these should be initialized to std::nullptr. With this, the whole subtree below left or right is correctly destructed once Node is destructed, so there is no need to do this recursively. "Observing pointer" to the parent node means you should never do some memory-related action with it, particularly no delete.

answered Mar 22 '15 at 21:14

davidhigh

14,652
2
44
75

So in my case, a child can have more than 1 parent, and I'm overloading the operator+ such that it takes two instances of class Node and creates a new one and returns it. Now this means that I must return by reference not by value from operator+ because of expressions like a+b+c, where there is a temporary object. In terms this means that with raw pointers the temporary node won't be cleaned. – Alex Botev Mar 22 '15 at 21:19
@Belov: yes, my answer refers to the special case of a [tree](http://en.wikipedia.org/wiki/Tree_%28data_structure%29). For a general acyclic graph, you can switch to a `shared_ptr`-to-the-children / `weak_ptr`-to-the-parent implementation. – davidhigh Mar 22 '15 at 21:30
it sounds like you want to returns a unique_ptr<> from operator+ then – Arvid Mar 22 '15 at 21:31
Thanks, that would probably work, only thing left is how do get inside an operator+ overloading from a Reference(Node& p1) to make a weak poitner? do you know? – Alex Botev Mar 22 '15 at 21:32
@Arvid: I have no idea what `operator+` shall do here, and before that I wouldn't want to give any advice. Moreover, in general I don't even know what `operator+` *should* do for two nodes, so I wouldn't use it at all. – davidhigh Mar 22 '15 at 21:36
yeah, after posting that I realized it's not clear at all what should happen. I was sort of imagining taking two unique_ptr<> to subtrees and moving them into the new parent node and returning that. It makes for an unusual operator+ for sure. – Arvid Mar 23 '15 at 01:06
@Belov: without knowing deeper exactly what you're looking for. If your nodes derive from std::enable_shared_from_this, you can ask shared_from_this() which you can make a weak pointer from. It might very well be the case that shared_ptr<> and weak_ptr<> is the right tool for you, keep in mind though that you allow cycles if you're not careful. – Arvid Mar 23 '15 at 01:09
Could you look at the link I post, it contains code which roughly explains what I want, without the extra thing of having pointers from parents->children. I didn't want to copy the whole question, in short I need a wrapper around a numeric class and to overload operators. – Alex Botev Mar 23 '15 at 01:28

C++ building a double sided Tree with operator overloading - what is good memory solution?

1 Answers1