Класс C++ Tree: конструктор / копирование / утечка памяти?

Предположим, у меня есть класс бинарного дерева, цель которого - индуктивно разрезать реальный интервал (a, b) на множество небольших интервалов, выбирая средние точки. NB: класс, который я на самом деле пишу, имеет дело с треугольниками на плоскости, но идея та же самая.

Вот как класс выглядит в заголовочном файле:

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 будут совместно использоваться многими дочерними деревьями (я знаю, что double довольно "легкий", но в моем реальном классе у меня есть кое-что "более тяжелое" ").

Теперь вот главный конструктор:

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

Таким образом, вопрос: как правильно написать эти функции? Я также готов услышать общие замечания о том, как я пишу этот класс. Заранее спасибо!

Источник

3 ответа

Решение

Публичный конструктор выглядит следующим образом:

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));
}
Источник

Вы создаете утечку здесь:

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

Вы выделяете новый объект Tree, используя new, и вы нигде не удаляете его.

Кроме того, вы не следуете правилу трех. Вы создали класс, который реализует деструктор, и правило трех гласит, что (обычно), когда вы создаете любой из: конструктор копирования, оператор присваивания или деструктор, тогда вам обычно нужны все из них.

Я предлагаю вам сделать Tree(double *a, double *b, int глубину, int maxDepth) статической функцией и вызывать ее из вашего открытого конструктора (ов) по мере необходимости.

Источник

Я думаю 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 ищите значения.

Источник
Другие вопросы по тегам