CODEWITHSUNDEEP
c++c++11
Kevin
Kevin

Reputation: 671

Why are my deque elements moving around?

I am implementing a simple Tree class to use in a parser, where I need to traverse the structure of the parse tree and build it up incrementally.

This is a stripped-down version of the class that demonstrates the issue (executable in this repl.it session):

template <typename T>
class Tree {
  T val;
  std::deque<Tree<T>> children;

 public:
  Tree() {}
  Tree(T value) : val(value) {}
  Tree(T value, std::deque<Tree<T>> children) : val(value), children(children) {}

  std::deque<Tree<T>> getChildren() { return this->children; }

  void appendChild(T value) {
    this->children.push_back(value);
    // this->children.emplace_back(value);
    std::cout << "Appended child to node with value " << this->val << ".\n";
    printChildren();
  }

  void printChildren() {
    std::cout << "children for " << this << "(" << this->val << ")"
              << ": { ";
    for (auto &child : this->children) {
      std::cout << &child << "(" << child.val << ") ";
    }
    std::cout << "}\n";
  }
};

For each node, the children are stored in a std::deque so children can be added to either end. In testing my class, I am finding that I cannot rely on the structure produced by building up the tree incrementally as opposed to all-at-once with an initializer list.

Here's some code to exercise the class and show what's happening:

std::cout << "Constructing Tree\n\n";
Tree<int> t(1);
t.appendChild(2);
t.getChildren()[0].appendChild(3);

std::cout << "\n\nPrinting tree from main\n\n";
t.printChildren();
t.getChildren()[0].printChildren();

This has the following output:

Constructing Tree

Appended child to node with value 1.
children for 0x7ffe9fd41820(1): { 0xb69080(2) }
Appended child to node with value 2.
children for 0xb694a0(2): { 0xb696b0(3) }


Printing tree from main

children for 0x7ffe9fd41820(1): { 0xb69080(2) }
children for 0xb698c0(2): { }

As you can see, the addresses of the node with the value 2 are different each time they are printed out. When it's first appended to the 1 node, it has the address 0xb69080. After it gets its own children, it has the address 0xb694a0. Then, when it's accessed from the main function, it has the address 0xb698c0.

Additionally, it seems that when it gets moved it somehow loses its children. The last line should show that the 2 node has a single child with value 3.

What's going on here?

Upvotes: 0

Views: 98

Answers (1)

max66
max66

Reputation: 66200

I suppose your problem is here

std::deque<Tree<T>> getChildren() { return this->children; }

getChildren() return a copy of children.

Try with 

std::deque<Tree<T>> & getChildren() { return this->children; }
// .................^

to return a reference to the internal children, if you want modify it using the returned value.

I mean: if getChildren() return a copy of children, with

t.getChildren()[0].appendChild(3);

you append a child with value 3 to the first element of the copy of children returned by getChildren().

This copy isn't saved so it's a temporary value that is destroyed immediately after, losing the 3 child appended.

Upvotes: 4

Related Questions