0

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

这是该类在头文件中的样子：

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

请注意，树存储指向双精度数 a 和 b 的指针，而不是实际双精度数。这样做的原因是为了节省内存（和速度？），观察到 a 和 b 将被许多子树共享（我知道双倍是相当“轻”的，但在我的实际课堂上，我有一些“更重”）。

现在这里是主要的构造函数：

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

}

和析构函数：

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

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

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

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

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

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

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

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

我在想，一旦退出此函数，对象 T 就会被销毁，因此子项会被删除等。

复制功能也有同样的问题：

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

所以问题是：编写这些函数的正确方法是什么？我也愿意听取关于我写这门课的方式的一般评论。提前致谢！

4

3 回答 3

1

公共构造函数如下：

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);和三巨头）；然后，你可以写：

{
     swap(Tree(&a, &b, depth, depth));
}
于 2013-08-08T19:40:38.460 回答
1

您正在这里创建泄漏：

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

您使用 new 分配新的 Tree 对象，并且不会在任何地方将其删除。

此外，您没有遵循三原则。您创建了一个实现析构函数的类，并且三规则表明（通常）当您创建任何一个：复制构造函数、赋值运算符或析构函数时，您通常需要所有这些。

我建议您将 Tree(double *a, double *b, int depth, int maxDepth) 设为静态函数，并根据需要从公共构造函数中调用它。

于 2013-08-08T19:38:36.040 回答
0

我认为maxDepth对于该类的每个对象都是相同的，因此请制作它static（并且您只需要对其值进行一次初始化）：

static int maxDepth;

然后我会在一个构造函数中重写私有和公共构造函数（你的实际公共构造函数会导致内存泄漏）：

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

尽量与您使用的类型保持一致：

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

最后我真的不明白：

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

你说，你不想浪费内存，所以你使用了指针，但实际上指针也有大小......如果只有你的树的叶子包含a和b（但在我看来，情况并非如此这里），你可以做这样的事情：

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

然后如果isLeaf是false寻找孩子，如果是true寻找价值观。

于 2013-08-08T19:34:14.397 回答