////EDIT #2: Deleted all the previous info and just post the working code now. Previous question became too lengthy:
#include <iostream>
#include <vector>
using namespace std;
template<class T>
class Node{
T data;
vector<Node<T>*> adjacent;
friend class Graph;
public:
int n;
Node(T initData) : data(initData), n(0){}
void addAdjacent(Node<T>& other){
adjacent.push_back(&other);
n++;
}
T getData(){
return data;
}
Node<T>* getEdge(int edgeNum){
return adjacent[edgeNum];
}
};
template<class T>
class GraphCl{
int n;
vector<Node<T>*> nodes;
T input;
public:
GraphCl(int size): n(size){
for (int i=0;i<n;i++){
cout << "Enter data for node " << i << ": ";
cin >> input;
nodes.push_back(new Node<T>(input)) ;
}
}
void addEdge(int baseNode, int edgeNode){
nodes[baseNode]->addAdjacent(*nodes[edgeNode]);
}
void printGraph(){
for (int i=0;i<n;i++){
Node<T> *base = nodes[i];
cout << "Data of node " << i <<": "<< base->getData() <<endl;
for (int j=0;j<base->n;j++){
cout << "Edge #"<< j+1 << " of node " << i << ": " << base->getEdge(j) <<endl;
}
}
}
};
int main(){
GraphCl<int> *myGraph = new GraphCl<int>(5);
myGraph->addEdge(0,1);
myGraph->addEdge(0,2);
myGraph->addEdge(0,3);
myGraph->addEdge(0,4);
myGraph->addEdge(3,1);
myGraph->addEdge(3,0);
myGraph->printGraph();
return 0;
}
Output:
Enter data for node 0: -34
Enter data for node 1: 12
Enter data for node 2: 56
Enter data for node 3: 3
Enter data for node 4: 23
Data of node 0: -34
Edge #1 of node 0: 0x7fbeebd00040
Edge #2 of node 0: 0x7fbeebd00080
Edge #3 of node 0: 0x7fbeebe00000
Edge #4 of node 0: 0x7fbeebd000d0
Data of node 1: 12
Data of node 2: 56
Data of node 3: 3
Edge #1 of node 3: 0x7fbeebd00040
Edge #2 of node 3: 0x7fbeebd00000
Data of node 4: 23
As you can see this simple implementation is working. I decided to just cut out all the complicated stuff and keep it simple with dynamically changing vectors. Obviously less efficient but I can work from here on. Since I am new with C++ the previous implementation just got my head spinning 360 degrees thinking about where all the pointers to pointers went, without even thinking about memory allocation. The above code basically is a directed graph that is very sensitive to input errors, so I got to work on it still. Thanks for all the help!
Answering the updated question
There are a few issues with putting Nodes directly in a std::vector in your case.
Using a std::vector is great for many things, but if you are doing that, you should make sure not to take pointers to vectors. Remember, pointers refer to exact addresses in memory of where an object is stored. A vector is a growable container of elements. To store elements contiguously, the vector allocates a bunch of memory, puts objects there, and if it has to grow, it will allocate more memory and move the objects around. It is essentially doing something similar to what you are doing in your Node and grow (except, in its case, its explicitly destroying the objects before freeing the old memory).
Notice that your Grow function allocates new memory and copies the pointers. Simlarly, vectors can allocate new memory and copy the data over. This means that holding pointers to data in a vector is bad. The only guarantee a vector gives you is that its data will continue to be accessible using array-style indexing, find, iteration, etc., not that the data will exist in the same memory location forever.
Explaining the exact bug you are seeing
The vector is invoking a copy constructor. The default copy constructor copies every field one-by-one. This is not what you want in the case of Node, because then you have two vectors that think they own the Node** adjacent memory location. When the first node (the old copy) is being destroyed, it will free its adjacent nodes (which is the same as the copy's adjacent node). When the new copy is being destroyed, it will attempt to free that same memory location, but it is already freed. You also have the problem here that, if you attempted to access the memory after it has been destroyed in the first node, you'll be in trouble.
Why was this bug showing up when you were only adding nodes?
When a vector grows to a certain amount, it needs to resize. In most implementation, the process is roughly:
Your bug is showing up because of steps 2 and 3, basically.
Fixing this particular bug
For your case, the default copy constructor is no good because copying a node should meet a deep copy of all of the data. A regular copy in C++ will copy all of the data on the class or struct itself. If the data is a pointer, then the pointer is copied, not the thing its pointing to.
Override the copy constructor and assignment operator:
Node(const Node<T>& other) : data(other.data), capacity(other.capacity), n(other.n) {
adjacent = reinterpret_cast<Node**>(malloc(capacity * sizeof(Node**)));
memcpy(adjacent, other.adjacent, capacity * sizeof(Node**));
}
Node<T>& operator= (const Node<T>& other) {
data = other.data;
capacity = other.capacity;
n = other.n;
adjacent = reinterpret_cast<Node**>(malloc(capacity * sizeof(Node**)));
memcpy(adjacent, other.adjacent, capacity * sizeof(Node**));
}
A Bigger Problem
A bigger problem with your code is that the use of an std::vector and pointers to its elements. Choose one of: