Доктор Память: действительно ли эти линии вызывают утечки памяти? - PullRequest
Новая
       25

Доктор Память: действительно ли эти линии вызывают утечки памяти?

0 голосов
/ 16 июня 2019

У меня есть следующий код: 

class Node {
    public:
        int data;
        Node* parent;
        std::unique_ptr<Node> left;
        std::unique_ptr<Node> right;
    public:       
        explicit Node(int d) : data(d),
                               parent(nullptr),
                               left(nullptr),
                               right(nullptr) { }
        /*
            Some functions
        */                  
};

class dt {
    private:            
        Node* root;
    private:        
        void add_helper(Node* parent, Node* node); 
        /*
                Some helper functions
        */      
    public:
        dt() : root(nullptr) {}
        ~dt() {
            delete root;
        } 
        /*
                Some functions
        */       
        void add(int data);        
};


void dt::add(int data) {
    if(!root) {
        root = new Node(data); // 1: memory leak
        return;
    }   
    Node* node = new Node(data); // 2: memory leak
    add_helper(root, node);
}

Когда я сканирую этот код на утечки памяти Dr.Память показывает ошибки в строках, упомянутых в комментариях выше.Но они действительно утечки памяти? dt имеет деструктор, в котором удаляется указатель root .Когда деструктор начнет удалять узел root , он будет рекурсивно удален и удалит всех его потомков.Или что-то еще происходит?

1 Ответ

1 голос
/ 16 июня 2019

действительно ли эти строки вызывают утечки памяти?

Память, выделенная в строке Node* node = new Node(data), потенциально утечка. По крайней мере, пример не показывает, где указатель будет удален. Право собственности может быть передано в add_helper, но это исключено из примера.

Я не знаком с доктором Памяти, но предположил бы, что он сообщает, где была выделена утечка памяти; не там, где было утечка.

Более того, если вы сделаете копию экземпляра dt, поведение программы будет неопределенным, поскольку и оригинал, и копия будут пытаться удалить скопированный указатель.

Чтобы исправить и потенциальную утечку памяти, и потенциальный UB, используйте уникальный указатель. Так же, как вы использовали с Node.

Я не могу использовать unqiue_ptr для root, потому что есть несколько указателей на один и тот же узел.

Делая delete root; в деструкторе, ваш класс приобретает уникальное владение указателем. Если это предположение верно, то нет проблем с использованием уникального указателя. Если предположение неверно, то деструктор, вероятно, ведет к неопределенному поведению. Использование этого вместо уникального указателя не является решением. Возможно, вам придется использовать совместно используемый указатель.

Наконец, если ваше дерево не сбалансировано, неявный рекурсивный деструктор имеет линейно увеличивающуюся глубину рекурсии в худшем случае, что может легко вызвать переполнение стека. Вам следует либо сбалансировать дерево (например, с помощью red-back или аугментаций AVL), либо использовать итеративный алгоритм для уничтожения дочерних элементов.

...