Graphs using Adjacency List in c++

Question

I am trying to implement a graph in C++. I am representing a node in graph using a structure which contains two variables -
a) an integer to contain some information about the node.
b) a list to contain index of other vertex which are connected to it.
Following 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 is compiling fine but I am getting a run time error while I am pushing back an element in the list. Is there any problem in my structure.
I am using code blocks and GNU GCC, C++ 98 compiler to compile my code.

Answer 1

malloc is a C function - it shouldn't be used with C++ objects, which is very well explained here (short answer: in C++, when you are not dealing with POD types, std::list in your case, you must call the object's constructor to have the actual object ready for use, and malloc() does not do that).

You should used new instead. While malloc only allocates a block of memory of size vertex, new does that and also initializes std::list aswell by calling it's constructor (interesting to point out that when you call delete(), you are calling your object's desctructor aswell).

Here is a piece of code that works for your case, although I suggest you to start using more C++ features within 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;
}