Graphs using the list of attachments in C ++

Question

I am trying to implement a graph in C ++. I represent node in a graph using a structure that contains two variables -
a) an integer containing some information about node.
b) a list containing a list of other vertices associated with it.
Below is the code.

// Graphs using adjacency list #include <iostream> #include <list> #include <cstdlib> using namespace std; // structure to represent a vertex(node) in a graph typedef struct vertex{ int info; list<int> adj; // adjacency list of edges contains the indexes to vertex } *vPtr; int main(){ vPtr node = (vPtr)malloc(sizeof(struct vertex)); node->info = 34; // some arbitrary value (node->adj).push_back(2); // trying to insert a value in the list return 0; } 

The code compiles fine, but I get a runtime error while I return the item in the list. Are there any problems in my structure.
I use the code blocks and the GNU GCC compiler, C ++ 98 to compile my code.

Answer 1

malloc is a C function - it should not be used with C ++ objects, which is very well explained here (short answer: in C ++, when you are not related to POD , std::list in your case, you should call the constructor of the object so that it is ready to use, and malloc() does not).

Instead, use new . While malloc only allocates a vertex sized memory block, new does this, and also initializes std::list and also calls its constructor (it is interesting to note that when you call delete() , you call your descriptor object).

Here is a snippet of code that works for your case, although I suggest you start using more C ++ features in C ++ projects:

 #include <iostream> #include <list> #include <cstdlib> #include <new> using namespace std; // structure to represent a vertex(node) in a graph typedef struct vertex{ int info; list<int> adj; // adjacency list of edges contains the indexes to vertex } *vPtr; int main(){ cout << "allocating memory for our vertex struct... \n"; vPtr node = new vertex(); node->info = 34; // some arbitrary value (node->adj).push_back(2); // trying to insert a value in the list cout << "cleaning allocated memory... \n"; delete(node); return 0; } 

Answer 2

A couple of things.

• Since you use malloc no constructor , it is ever called, and as such a non-primitive member, adj never built and NULL.

• You are losing memory because you never free or delete any dynamically allocated memory.

• If you are using C ++, why are you using malloc instead of new and delete ?

• You do not need to specify struct vertex in sizeof for C ++.

To fix this, you can do:

 vPtr node = new struct vertex(); // also change to delete instead of free 

or

 // use current malloc line, change adj to be a pointer to a list and new it // but this will cause additional problems for you since you really need to use a constructor for STL::list node->adj = new list<int>; 

On the bottom line, you should not use malloc here.

Answer 3

This is an UpAndAdam answer written in full.

 // Graphs using adjacency list // #include <iostream> #include <list> #include <cstdlib> using namespace std; // structure to represent a vertex(node) in a graph typedef struct vertex{ int info; list<int> *adj; // adjacency list of edges contains the indexes to vertex } *vPtr; int main(){ vPtr node = (vPtr)malloc(sizeof(struct vertex)); node->adj = new list<int>; node->info = 34; // some arbitrary value (node->adj)->push_back(2); // trying to insert a value in the list return 0; }