Tree being replaced by junk values, when printing tree info

Question

So this is a problem I noticed with a small project I'm working on and I can't figure out what's going on, or what to search to fix it, so I wrote this small program to recreate the problem. I haven't worked with c++ in a few years so apologies if this is a really obvious problem.

#include <iostream>
#include <vector>
using namespace std;
class Cell{
    int score;
    Cell* next_l;
    Cell* next_r;
    public:
    Cell(int s = 0, Cell *r = nullptr, Cell *l = nullptr){
        this -> score = s;
        this -> next_l = l;
        this -> next_r = r;
    }
    int getScore(){
        return this -> score;
    }
    void disp(){
        cout << "Score: " << this -> score << endl;  //Problem Line
        if(this -> next_r != nullptr){
            this -> next_r -> disp();
        }
        if(this -> next_l != nullptr){
            this -> next_l -> disp();
        }
    }
};
// returns a cell that's the head of a binary tree 
// formed by replacing last two cells in the vector
// with a Cell pointing to those two cells instead,
// and then calling this function on that new vector of cells.
Cell make_tree(vector<Cell> &cells){  
    if(cells.size() == 1){
        return cells[0];
    }else{
        Cell c1 = *(cells.end() - 1);
        cells.pop_back();
        Cell c2 = *(cells.end() - 1);
        cells.pop_back();
        Cell cell = Cell(c1.getScore() + c2.getScore(), &c1, &c2);
        cells.push_back(cell);
        return make_tree(cells);
    }
}
int main(){
    vector<Cell> cells;
    for(int i = 0; i < 3; i++){
        Cell *ptr{new Cell(i)};
        cells.push_back(*ptr);
    }
    Cell head = make_tree(cells);
    head.disp();
    return 0;
}

So the line that I marked as //Problem Line is where I faced confusion while debugging. After printing the score, for some reason, all the values in the tree after a certain depth get replaced by random junk. This eventually leads to a segmentation fault. I have no idea how to proceed with fixing this problem.

Forget pointers for a moment, and try something like this: https://stackoverflow.com/a/15473485/7916438 - right now you are leaking all objects you create, btw. — tevemadar, Nov 29 '20 at 09:00

Marko Mahnič · Accepted Answer · 2020-11-29T09:33:38.440

The problem is that you are taking pointers to local variables in this line:

  Cell cell = Cell(c1.getScore() + c2.getScore(), &c1, &c2);

The members next_l and next_r are pointing to variables c1 and c2 that are on the stack which is not ok. These values are invalid the moment the function terminates and are overwritten when other function calls are made afterward.

Try to change the code so that the cells will be placed in vector<Cell*> cells. Then your code will look like:

Cell* make_tree(vector<Cell*> &cells) {  
   ...
   Cell* c1 = *(cells.end() - 1);
   cells.pop_back();
   Cell* c2 = *(cells.end() - 1);
   cells.pop_back();
   Cell* cell = new Cell(c1->getScore() + c2->getScore(), c1, c2);
   cells.push_back( cell );
   return make_tree( cells );
   ...
}

You will have to delete the resulting cell (delete head;) at the end of the program and you will also have to write a destructor for Cell that will delete its left and right children. You could avoid this by using shared pointers (std::shared_ptr) instead of raw pointers:

std::shared_ptr<Cell> next_l, next_r
vector<std::shared_ptr<Cell>> cells;
std::shared_ptr<Cell> make_tree(vector<std::shared_ptr<Cell>> &cells)
std::shared_ptr<Cell> c1, c2
auto cell = std::make_shared<Cell>(c1->getScore() + c2->getScore(), c1, c2)

Because of std::make_shared you will also need the default constructor:

class Cell{
   ...
   Cell() = default;
   ...
};

oh! I was under the impression that as long as a pointer is pointing to a memory location, the location would be reserved but this makes a lot of sense. Thank You! I don't understand what the std::make_shared thing is but I'll check up on that myself. Meanwhile, I'm guessing using a destructor function that recursively destroys all the pointers at a deeper level, should handle the memory problem right? — Adam Jijo, Nov 29 '20 at 10:40
If you don't destroy the children in the destructor, you will have memory leaks. If you use raw pointers (Cell*) you have to do that manually. If you use `shared_ptr` children are destroyed automatically when there are no more references to them. `make_shared` is a shorthand for `shared_ptr(new Cell())` with additional provisions for reducing memory fragmentation and reducing cache misses. — Marko Mahnič, Nov 29 '20 at 11:21

Tree being replaced by junk values, when printing tree info

1 Answers1