CODEWITHSUNDEEP
c++
FlatAssembler
FlatAssembler

Reputation: 782

Using default copy constructor corrupts a tree in C++

For example:

#include <iostream>
#include <vector>
#include <string>

using namespace std;

struct TreeNode {
    vector<TreeNode> children;
    string name;
};

int main() {
    TreeNode leafNode;
    leafNode.name="c";
    TreeNode middleNode;
    middleNode.name="b";
    middleNode.children.push_back(leafNode);
    TreeNode rootNode;
    rootNode.name="a";
    rootNode.children.push_back(middleNode);
    rootNode=rootNode.children[0];
    cout <<rootNode.name <<endl;
}

Outputs c, in both CLANG and GCC. Of course, I'd expect it to output b. What's going on here?

Upvotes: 1

Views: 181

Answers (2)

sba
sba

Reputation: 199

You should not use self assignment or self copy construction. There is partial assignment rootNode=rootNode.children[0]; To avoid this problem should use pointers

#include <iostream>
#include <vector>
#include <string>
#include <memory> // for std::shared_ptr

using namespace std;

struct TreeNode; // forward declaration

using TreeNodePtr = std::shared_ptr<TreeNode>;

struct TreeNode {
    vector<TreeNodePtr> children;
    string name;
};

int main() {
    auto leafNode = std::make_shared<TreeNode>();
    leafNode->name="c";
    auto middleNode = std::make_shared<TreeNode>();
    middleNode->name="b";
    middleNode->children.push_back(leafNode);
    auto rootNode = std::make_shared<TreeNode>();
    rootNode->name="a";
    rootNode->children.push_back(middleNode);
    rootNode=rootNode->children[0];
    cout <<rootNode->name <<endl;
}

Upvotes: 1

Excelcius
Excelcius

Reputation: 1690

As others have pointed out in the comments, you should really try to setup a debugger and debug your code first. That is how you learn a lot in programming.

However, if you are not used to debugging it will probably be hard for you to find the issue, since the code in question is compiler generated.

You are right that the copy constructor more or less corrupts your data. But that is not the compilers fault. The default copy constructor takes its argument by reference and you are passing a reference of a member of rootNode to the copy constructor of rootNode. So in effect you are overwriting the object with a part of itself.

What more or less happens during the assignment or copy:

TreeNode(const TreeNode& other) {
  children = other.children;
  name = other.name;
}

So if you pass rootNode.children[0] to this operation, it will effectively be reduced to this:

rootNode.children = rootNode.children[0].children; // copies the children of 'b' to 'a'
rootNode.name     = rootNode.children[0].name;     // children[0] now refers to the first 
                                                   // of 'b's children, so name will be 'c' !!

A possible workaround is to create a true copy first using:

rootNode = TreeNode{ rootNode.children[0] };

The behavior might be different depending on the compiler. In VS2019 I get an empty output when trying your example.

Upvotes: 2

Related Questions