C++ Tree class : constructor / copy / memory leak?

问题:

Suppose I have a binary tree class whose purpose is to inductively cut a real interval (a, b) into many small intervals, picking midpoints. NB: the class I'm actually writing deals with triangles in the plane but the idea is the same.

Here is what the class looks like in the header file:

class Tree
{
public:
    Tree(double &a, double &b, int depth);
    ~Tree();

    Tree getCopy() const;

private:        
    Tree(double *a, double *b, int depth, int maxDepth);

    double *a, *b;
    int depth, maxDepth;    
    Tree *leftChild, *rightChild;
};

Note that the tree stores pointers towards doubles a and b, rather than the actual doubles. The reason for that is to save memory (and speed?), observing that a and b are going to be shared by many children trees (I know that a double is quite "light" but in my actual class, I have something "heavier").

Now here is the main constructor:

Tree::Tree(double *a, double *b, int depth, int maxDepth) :
    depth(depth), maxDepth(maxDepth)
{    
    if (depth == maxDepth)
    {
        this->a = new double(*a);
        this->b = new double(*b);
    }
    else
    {
        this->a = a;
        this->b = b;
    }


    if (depth == 0)
    {
        leftChild = 0;
        rightChild = 0;
    }
    else
    {
        double * midpoint = new double((*a+*b)/2);
        leftChild = new Tree(a, midpoint, depth - 1, maxDepth);
        rightChild = new Tree(midpoint, b, depth - 1, maxDepth);
    }

}

And the destructor:

Tree::~Tree()
{
    if (depth == 0)
    {
        delete b;
    }
    else
    {
        delete leftChild;
        delete rightChild;
    }

    if (depth == maxDepth)
    {
        delete a;
    }
}

I hope both of these functions are correct. Notice that the constructor is private, it is the one that is called recursively. The public constructor is the following:

Tree::Tree(double &a, double &b, int depth)
{
    *this = *(new Tree(&a, &b, depth, depth));
}

I know this looks weird, and I'm worried I might be creating a memory leak by doing this? But on the other hand, if I wrote:

    *this = Tree(&a, &b, depth, depth);

Wouldn't that fail? Let me try to explain why I think it might fail by considering the equivalently function

{
    Tree T(&a, &b, depth, depth);
    *this = T;
}

I'm thinking that as soon as this function is exited, the object T is destroyed, therefore the children are deleted etc.

The same concern goes for the copy function:

Tree Tree::getCopy() const
{
    return Tree(a, b, depth, depth);
}

So the question is: what is the correct way to write these functions? I'm also open to hearing general remarks about the way I write this class. Thanks in advance!

回答1:

The public constructor is the following:

Tree::Tree(double &a, double &b, int depth)
{
    *this = *(new Tree(&a, &b, depth, depth));
}

I know this looks weird, and I'm worried I might be creating a memory leak by doing this?

You are (indeed) creating a memory leak.

One solution would be to re-write it like this:

new(this) Tree(&a, &b, depth, depth);

Placement-new would not allocate the memory but still make the call. I'm not sure if there are any hidden pitfalls with this though.

The solution is still weird though. If you are working with C++11, you should implement in terms of a move-constructor (and if possible, forward the constructor call). Otherwise, you should implement in terms of std::shared_ptr (and/or maybe the pimpl idiom).

Edit: Another (more) elegant solution would be to implement "the big three and a half" (void Tree::swap(Tree& x); and the big three); Then, you could write:

{
     swap(Tree(&a, &b, depth, depth));
}

回答2:

You are creating a leak here:

Tree::Tree(double &a, double &b, int depth)
{
    *this = *(new Tree(&a, &b, depth, depth));
}

You allocate new Tree object using new and you don't delete it anywhere.

Additionally you are not following the rule of three. You created a class which implements destructor, and the rule of three says that (usually) when you create any of: copy constructor, assignment operator or destructor then you usually need all of them.

I suggest you make Tree(double *a, double *b, int depth, int maxDepth) a static function and you call that from your public constructor(s) as needed.

回答3:

I think maxDepth is the same for every objects of the class, so make it static (and you will only need one initialization of its value):

static int maxDepth;

And then I would rewrite the private and public constructor in one constructor (your actual public one make a memory leak):

Tree::Tree(double &a, double &b, int depth)
{
    // stuff from private constructor
}

Try to stay consistent with the types you use:

double * midpoint = new double((*a + *b) / 2.0);   // 2.0 is double; 2 is int

And finally I really don't get the:

Tree(&a, &b, depth, depth);  // why ... depth, depth ... ???

You said, you don't wanted to waste memory and so you used pointer, but actually the pointer also have a size... If only the leafs of your tree contain a and b (but it seems to me, this isn't the case here), you could do something like this:

class Tree
{
    // functors declarations

    bool isLeaf = false;
    int depth, maxDepth;    
    Tree *leftChild, *rightChild;
};

Tree::Tree(double a, double b, int depth): depth(depth) {
    if (depth == maxDepth) {
            isLeaf = true;
            this->leftChild = new double(a);
            this->rightChild = new double(b);
    }
}

And then if isLeaf is false look for the children and if it's true look for the values.