Grafici con l'elenco Adjacency in C++

Question

Sto cercando di implementare un grafico in C++. Sto rappresentando un nodo nel grafico usando una struttura che contiene due variabili -
a) un intero per contenere alcune informazioni sul nodo.
b) un elenco per contenere l'indice di altri vertici che sono collegati ad esso.
Di seguito è riportato il codice.

// 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; 
} 

Il codice sta compilando bene, ma sto ottenendo un errore di tempo di esecuzione mentre sto spingendo indietro di un elemento nella lista. C'è qualche problema nella mia struttura.
Sto usando i blocchi di codice e il compilatore GNU GCC, C++ 98 per compilare il mio codice.

Answer 1

malloc è una funzione C - non deve essere usato con gli oggetti C++, which is very well explained here(risposta breve: in C++, quando non si tratta di POD tipi, std::list nel tuo caso, si deve chiamare costruttore dell'oggetto per avere l'oggetto reale pronto per l'uso, e malloc() non lo fa).

You should used new instead. Mentre malloc assegna solo un blocco di memoria della dimensione vertex, new lo fa e inizializza anche std::list anche chiamando il suo costruttore (interessante notare che quando si chiama delete(), si chiama anche il descrittore dell'oggetto).

Ecco un pezzo di codice che funziona per il vostro caso, anche se vi consiglio di iniziare a utilizzare più funzioni C++ all'interno di progetti C++:

#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

Un paio di cose.

1. Poiché si utilizza malloc non constructor viene mai chiamato, e come tale il membro non primitiva adj non è mai costruito ed è NULL.

2. Si sta perdendo memoria poiché non si libera/elimina alcuna memoria allocata dinamicamente.

3. Se si utilizza C++, perché si utilizza malloc anziché new e delete?

4. Non è necessario dire struct vertex nello sizeof per C++.

Per risolvere il problema si potrebbe fare:

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

o

// 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>; 

Linea di fondo davvero non si dovrebbe usare malloc qui.

Answer 3

Questa è la risposta di UpAndAdam, scritto completamente.

// 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; 
}