C++ 树类:构造函数/复制/内存泄漏? [英] C++ Tree class : constructor / copy / memory leak?

问题描述

假设我有一个二叉树类，它的目的是将一个实数区间 (a, b) 归纳为许多小区间，选取中点.注意:我实际上正在编写的课程涉及平面中的三角形，但想法是相同的.

这个类在头文件中的样子:

类树{民众:树(双&a，双&b，int深度)；~树();树 getCopy() const;私人的:Tree(double *a, double *b, int depth, int maxDepth);双*a，*b；整数深度，最大深度；树 *leftChild, *rightChild;};

请注意，树存储指向双精度 a 和 b 的指针，而不是实际的双精度.这样做的原因是为了节省内存(和速度?)，观察到 a 和 b 将被许多子树共享(我知道 double 很轻"，但在我的实际课程中，我有一些更重"的东西)").

现在是主构造函数:

Tree::Tree(double *a, double *b, int depth, int maxDepth) :深度(深度)，最大深度(最大深度){如果(深度 == 最大深度){this->a = new double(*a);this->b = new double(*b);}别的{这-> a = a;这-> b = b;}如果(深度== 0){左孩子 = 0;右孩子 = 0;}别的{double * midpoint = new double((*a+*b)/2);leftChild = new Tree(a, midpoint, depth - 1, maxDepth);rightChild = new Tree(midpoint, b, depth - 1, maxDepth);}}

和析构函数:

Tree::~Tree(){如果(深度== 0){删除 b;}别的{删除leftChild；删除rightChild；}如果(深度 == 最大深度){删除一个；}}

我希望这两个函数都是正确的.请注意，构造函数是私有的，它是递归调用的构造函数.公共构造函数如下:

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

我知道这看起来很奇怪，我担心这样做可能会造成内存泄漏?但另一方面，如果我写道:

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

那不会失败吗?让我尝试通过考虑等效函数来解释为什么我认为它可能会失败

<代码>{树 T(&a, &b, depth, depth);*这= T;}

我在想，只要这个函数退出，对象 T 就会被销毁，因此子项被删除等.

同样的问题也适用于复制功能:

Tree Tree::getCopy() const{返回树(a，b，深度，深度)；}

那么问题来了:写这些函数的正确方法是什么?我也愿意听取关于我编写这门课的方式的一般性评论.提前致谢！

解决方案

公共构造函数如下:

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

<块引用>

我知道这看起来很奇怪，我担心这样做可能会造成内存泄漏?

您(确实)造成了内存泄漏.

一种解决方案是像这样重写它:

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

Placement-new 不会分配内存但仍会进行调用.我不确定这是否有任何隐藏的陷阱.

解决方案仍然很奇怪.如果您正在使用 C++11，您应该根据移动构造函数来实现(如果可能，转发构造函数调用).否则，您应该根据 std::shared_ptr(和/或可能是 pimpl 习惯用法)来实现.

另一个(更)优雅的解决方案是实现三大半"(void Tree::swap(Tree& x); and the big 三)；然后，你可以写:

<代码>{交换(树(&a，&b，深度，深度))；}

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!

解决方案

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

这篇关于C++ 树类:构造函数/复制/内存泄漏?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！