Копировать конструктор вопроса Липпмана

Question

Я пытался найти копию ctro qs, приведенную в lipman, и не уверен, правильно ли я понял. Так как у класса есть указатели на себя, это немного смутило меня. Вот код

#include <iostream>
#include <string>

using namespace std;

class BinStrTreeNode{

      public:
         BinStrTreeNode(const string& val):_val(val){ 
              _leftchild = new BinStrTreeNode("nup");
              _rightchild = new BinStrTreeNode("rup");
              cout << "ctor" << endl;
         };
         BinStrTreeNode(const BinStrTreeNode&);
     private:
         string _val;
         BinStrTreeNode *_leftchild;
         BinStrTreeNode *_rightchild;
};

BinStrTreeNode::BinStrTreeNode(const BinStrTreeNode& rhs):_val(rhs._val){
    cout << "copy ctor" << endl;
    _leftchild = new BinStrTreeNode(*(rhs._leftchild));
    _rightchild = new BinStrTreeNode(*(rhs._rightchild));
}

И это дает ошибку сегментации. Я знаю, что мне нужно определить dtor тоже, но сначала я должен понять это правильно. Как мне определить копию ctor, оператор присваивания для такого класса?

Спасибо

Answer 1

Вы в принципе правильно поняли.
Вы просто забыли проверить наличие указателей NULL.

BinStrTreeNode::BinStrTreeNode(const BinStrTreeNode& rhs)
    :_val(rhs._val)
    ,_leftchild(NULL)
    ,_rightchild(NULL)
{
    cout << "copy ctor" << endl;
    if (rhs._leftchild  != NULL) {_leftchild  = new BinStrTreeNode(*(rhs._leftchild));}
    if (rhs._rightchild != NULL) {_rightchild = new BinStrTreeNode(*(rhs._rightchild));}
}

Обратите внимание, что деревья не будут указывать на узел выше (или себя) в дереве (как это было быбольше не быть деревом, это был бы график).Если ваш код представляет собой график, то вам нужно переписать его, чтобы сделать копию графика, которая намного сложнее, так как вам нужно отслеживать, какие узлы были скопированы на карте.

Хотя лично ясделаю еще один шаг и сделаю все в списке инициализаторов:
Хотя я бы просто сказал, что это личное предпочтение.

BinStrTreeNode::BinStrTreeNode(const BinStrTreeNode& rhs)
    :_val(rhs._val)
    ,_leftchild ((rhs._leftchild  == NULL)?NULL:new BinStrTreeNode(*(rhs._leftchild)))
    ,_rightchild((rhs._rightchild == NULL)?NULL:new BinStrTreeNode(*(rhs._rightchild)))
{
    cout << "copy ctor" << endl;
}

Циклические деревья (графики АКА)

Давайте начнем с нуля здесь:
В этой ситуации нам нужно отслеживать каждый узел, который мы создаем.Затем, когда указатель указывает назад на узел, который уже был скопирован, мы используем скопированный узел, а не создаем новый (в противном случае мы оказываемся в рекурсивном кошмаре после цикла вокруг и вокруг и вокруг).

typedef std::map<BinStrTreeNode*,BinStrTreeNode*>   CopyMap;
BinStrTreeNode::BinStrTreeNode(const BinStrTreeNode& rhs)
    :_val(rhs._val)
{
    CopyMap    copyMap;
    copyMap[&rhs] = this;

    left  = copyGraph(left,copyMap);
    right = copyGraph(right,copyMap) 
}

private:
BinStrTreeNode* BinStrTreeNode::copyGraph(BinStrTreeNode* node,CopyMap& copyMap)
{
    if (node == NULL)
    {    return NULL;
    }

    if (copyMap[node] != NULL)
    {    return copyMap[ndoe];
    }

    return new BinStrTreeNode(*node, copyMap);
}
BinStrTreeNode::BinStrTreeNode(const BinStrTreeNode& rhs, CopyMap& copyMap)
    :_val(rhs._val)
{
    copyMap[&rhs] = this;
    left  = copyGraph(left,copyMap);
    right = copyGraph(right,copyMap) 
}

Answer 2

Ваша основная проблема заключается в том, что оба конструктора бесконечно повторяются:

• Ваш конструктор будет повторяться до тех пор, пока вы не получите переполнение стека или пока new не выдаст std::bad_alloc.
• Ваш конструктор копирования будет выполнять рекурсию до тех пор, пока вы не получите переполнение стека или пока он не встретит недопустимого левого ребенка или правого потомка, когда произойдет ошибка segfault.завершающее условие.Всем функциям, включая конструкторы, нужен путь кода, который не повторяется.

Answer 3

Ваш конструктор копирования является рекурсивным.Возможно, вы исчерпали память или получили новое исключение выброса из памяти или, скорее всего, разыменовали нулевой указатель в одном из вызовов конструктора копирования.