Elements of a Vector of pointers to structs have same address

Question

I'm trying to implement a disjoint Forest Data Structure. In short, it is a data structure of sets with no common elements and can easily perform operations such as combining 2 sets and finding the set of an element. Each set has certain number of elements.

I'm implementing a set as a tree and each element of a set is a Node type. Here's my DisjointForesh.h file:

#ifndef STD_VECTOR
#define STD_VECTOR
#include <vector>
#endif

#ifndef DISJOINTFOREST_DISJOINTFOREST_H
#define DISJOINTFOREST_DISJOINTFOREST_H

struct TreeRoot;

struct Node{
    int rank = 0;
    int id;
    TreeRoot* parentTree;
    Node* parent;
    int value;
};

struct TreeRoot{
    std::vector<Node *> nodes;
    int id;
};

TreeRoot makeSet(int x);
.......

#endif //DISJOINTFOREST_DISJOINTFOREST_H

DisjointForest.cpp:

#ifndef STD_VECTOR
#define STD_VECTOR
#include <vector>
#endif
#include "DisjointForest.h"

TreeRoot makeSet(int x){
    TreeRoot tree;
    Node node;
    node.value = x;
    node.parent = &node;
    tree.nodes.push_back(&node);
    tree.id = node.value;
    node.parentTree = &tree;
    return tree;
}
........

Initialially, I make a Tree, containing one node. The node parent points to itself (initially) and parentTree points to the Tree the node belongs to. Each Tree has a vector of pointers to nodes, determining all the nodes it contains and an id which is the same as the value of the first node in the vector/the value of node with which it is created.

I plan to do many Union operations where a nodes parent will point to other nodes and parentTree will point to other Trees. Similarly, find-set(x) operation should return a tree, where Node x belongs.

Here's my main.cpp:

#include <iostream>
#include "DisjointForest.h"

void printParentAddress(TreeRoot &tree){
    for(Node* nodes: tree.nodes){
        std::cout << nodes->value << "-->" << nodes->parentTree->id << '\n';
    }
}

void printNodesInTree(TreeRoot &tree){
    for(Node* nodes: tree.nodes){
        std::cout << nodes->value << ' ';
    }
}


int main() {
    std::vector<TreeRoot> trees;
    std::vector<Node *> nodes;
    for(int index = 0; index < 8; ++index){
        TreeRoot tree = makeSet(index);
        Node *node = tree.nodes[0];
        trees.push_back(tree);
        nodes.push_back(node);
    }


    std::cout << "Total trees: " << trees.size() << '\n';
    std::cout << "Total nodes: " << nodes.size() << '\n';
//
    std::cout << "Printing all nodes with parent trees:\n";
    for(Node *node: nodes){
        std::cout << node->value << "-->" << node->parentTree->id << '\n';
        std::cout << node << '\n';
}

    return 0;
}

I get the following output:

Total trees: 8
Total nodes: 8
Printing all nodes with parent trees:
-749254164-->0
0x7ffe0cd60cf0
-749254164-->0
0x7ffe0cd60cf0
-749254164-->0
0x7ffe0cd60cf0
-749254164-->0
0x7ffe0cd60cf0
-749254164-->0
0x7ffe0cd60cf0
-749254164-->0
0x7ffe0cd60cf0
-749254164-->0
0x7ffe0cd60cf0
-749254164-->0
0x7ffe0cd60cf0

As you can see:

1. Each Nodes value is a garbage value
2. Each Node has the same address
3. Parent ID is 0 while it should be the same as nodes value

I don't understand why the above three are happening. I was expecting the values from 0-7 and different addresses for each node.I'm relatively new to c++ and therefore, I'm finding it difficult to debug this program.

Could you please help me figure out where I'm going wrong? Any suggestions to optimize my code will also be helpful. Please let me know if any additional information is required.

Answer 1

TreeRoot makeSet(int x){
    TreeRoot tree;
    Node node;
    node.value = x;
    node.parent = &node;
    tree.nodes.push_back(&node);
    tree.id = node.value;
    node.parentTree = &tree;
    return tree;
}

node is local to the block of this for function and has automatic storage. At the end of the function, the lifetime of node ends and it is automatically destroyed.

The returned tree points to this destroyed node. Those pointers become invalid as soon as the function returns.

for(Node *node: nodes){
    std::cout << node->value << "-->" << node->parentTree->id << '\n';

Here, you indirect through invalid pointers attempting to access non-existing objects. The behaviour of the program is undefined.