E.Groll E.Groll - 1 month ago 6
C++ Question

std::stack.top() changes member (which is a pointer) of elements

During debugging the second execution of while loop the code below produces an

out_of_range
exception. I noticed that:

before stack.top():

enter image description here

after stack.top():

enter image description here

Does anyone know why this happens and how to fix it?

#include <iostream>
#include <stack>
#include <vector>
#include <memory>
#include <functional>

int replacement;
int toreplace;

class Node
{
public:
int id_;
std::vector<Node*> children;
Node* at(int i)
{
return children.at(i);
}
std::vector<Node*> GetChildren() {
return children;
}
Node(int id_) {
this->id_ = id_;
}
};

class CPreorderStackFrame
{
public:
Node* node_;
CPreorderStackFrame* root_;
int index_;
explicit CPreorderStackFrame(Node* node_, CPreorderStackFrame* root_, int index_)
{
this->node_ = node_;
this->root_ = root_;
this->index_ = index_;
}
void replaceChildrenByIndex(Node* replace, int index)
{
replace->id_ = node_->at(index)->id_;
delete node_->GetChildren()[index];
node_->GetChildren()[index] = replace;
}
bool hasChildren() {
return !(node_->GetChildren().empty());
}
};

void pre_order_traverse(Node* root,
std::function<std::unique_ptr<Node>(Node*)> visit)
{ // always: root != NULL
std::stack<CPreorderStackFrame> mystack;
mystack.push(CPreorderStackFrame(root, NULL, NULL));
while (!mystack.empty())
{
CPreorderStackFrame cur = mystack.top();
mystack.pop();
std::unique_ptr<Node> replace = visit(cur.node_);
if (replace)
{
cur.root_->replaceChildrenByIndex(replace.release(), cur.index_);
}
else if (cur.hasChildren())
{
for (int i = cur.node_->GetChildren().size() - 1; i >= 0; --i)
{ //preorder requires right to left
Node *topush = cur.node_->at(i);
if (topush)
{
CPreorderStackFrame nextFrame(topush, &cur, i);
mystack.emplace(nextFrame); //hier ist noch alles richtig
}
}
}
}
}


std::unique_ptr<Node> print_visit(Node* node) {
std::cout << node->id_ << ' ';
return NULL;
}


std::unique_ptr<Node> replace_visit(Node* node) {
std::cout << node->id_ << ' ';
if (node->id_ == toreplace) {
std::unique_ptr<Node> retval(new Node(replacement));
return retval;
}
return NULL;
}


int main() {

toreplace = 3;
replacement = 8;

Node *a = new Node(1);
Node *b = new Node(2);
Node *c = new Node(3);
Node *d = new Node(4);
Node *e = new Node(5);
Node *f = new Node(3);
Node *g = new Node(3);
Node *h = new Node(42);
Node *i = new Node(42);

a->children.push_back(b);
a->children.push_back(c);
a->children.push_back(d);
a->children.push_back(e);
b->children.push_back(f);
b->children.push_back(g);
b->children.push_back(h);
b->children.push_back(i);

pre_order_traverse(a, replace_visit);
return 0;
}

Answer

One problem is

std::vector<Node*> GetChildren()

which means that

delete node_->GetChildren()[index];
node_->GetChildren()[index] = replace;

is destroying an object, but only replacing its address in a copy of the vector.
Dereferencing that element in the original vector is undefined.

You need to return by reference, or move the removal code into Node.

Another problem, and the immediate cause of your observations, is that

CPreorderStackFrame nextFrame(topush, &cur, i);
mystack.emplace(nextFrame);

is storing a pointer to the automatic object cur, whose lifetime ends with the end of the iteration.
Dereferencing the pointer after that is undefined.

Most (probably all) compilers will reuse that object's storage for the next iteration, which means that all your CPreorderStackFrames store the same pointer, and not a single one of them is valid by the time you dereference it.

It looks like the root doesn't need to be a pointer at all.