Lista STL per tenere puntatori struttura

Question

Ho una struttura chiamata vertice e ho creato alcune indicazioni per loro. Quello che voglio fare è aggiungere i puntatori a un elenco. Il mio codice qui sotto, quando tenta di inserire il puntatore nella lista, crea un errore di segmentazione. Qualcuno può spiegare cosa sta succedendo?

#include <iostream>
#include <list>

#define NUM_VERTICES 8

using namespace std;

enum { WHITE, GRAY, BLACK };

struct vertex
{
    int color;
    int distance;
    char parent;
};

int main()
{
    //create the vertices
    vertex r = {WHITE, NULL, NULL};

    //create pointer to the vertex structures
    vertex *pr = &r;

    //create a list to hold the vertices
    list<vertex*> *r_list = new list<vertex*>;

    list<vertex*>::iterator it;

    r_list->insert(it, pr);
}

Answer 1

Ci sono diverse cose sbagliate qui.

Prima di tutto, non si è in fase di inizializzazione l'iteratore, come gli altri sono detto:

list<vertex*>::iterator it = r_list->begin();

Fare questo e il codice andrà bene. Ma il codice è fatto in un modo cattivo.

Perché l'assegnazione della lista dal mucchio? Guardate il vostro codice: si dispone di una perdita di memoria. Non sta chiamando delete r_list ovunque. Questo è il motivo per cui si dovrebbe usare puntatori intelligenti ( std::unique_ptr , std::shared_ptr se si dispone di C ++ 11, equivalenti spinta altrimenti: boost::scoped_ptr e boost::shared_ptr )

Ma meglio ancora, basta farlo sullo stack:

//create a list to hold the vertices
list<vertex*> r_list;

list<vertex*>::iterator it = r_list->begin();

r_list.insert(it, pr);

Inoltre, utilizzando l'iteratore per inserire sta andando le cose nel lungo cammino. Basta usare anteriore push () o spingere indietro () :

//create a list to hold the vertices
list<vertex*> r_list;

r_list.push_back(pr);

Un'altra cosa:. Se l'elenco sopravvive il vertice che hai costruito, si punterà a qualcosa di valido

Ad esempio:

// global
list<vertex*> r_list;

void some_function(void)
{
    //create the vertices
    vertex r = {WHITE, NULL, NULL};

    //create pointer to the vertex structures
    vertex *pr = &r;

    r_list.push_back(pr);
} // right here, vertex r stops existing: the list now contains an
  // invalid pointer.

Una soluzione è quella di memorizzare i puntatori ai vertici heap allocata:

// global
list<vertex*> r_list;

void some_function(void)
{
    //create the vertices
    vertex *r = new vertex;
    r->color = WHITE;
    r->distance = 0;
    r->parent = 0;

    r_list.push_back(r);
}

Ora, anche dopo la funzione della lista che punta a un vertice heap allocata valido. Questo ha ora il problema che quando hai finito utilizzando l'elenco, è necessario passare attraverso il lsit e chiamare delete su ogni elemento. Questo problema è assistita da utilizzando il rel="nofollow Boost Pointer contenitore libreria .

Il modo migliore, però, è quello di conservare solo i vertici stessi (invece di puntatori a loro):

//create a list to hold the vertices
list<vertex> r_list;

//create the vertices
vertex r = {WHITE, NULL, NULL};

r_list.push_back(r);

Se si dà vertice un costruttore, si può anche semplicemente costruire sul posto:

struct vertex
{
    int color;
    int distance;
    char parent;

    vertex(int _color, int _distance, char _parent) :
    color(_color),
    distance(_distance),
    parent(_parent)
    {
    }
};

//create a list to hold the vertices
list<vertex> r_list;

r_list.push_back(vertex(WHITE, NULL, NULL));

(questi sono ora fuori il vostro problema)

In primo luogo, NULL viene in genere utilizzato solo quando si tratta di puntatori. Dal momento che distance e parent non sono puntatori, utilizzare 0 per inizializzare loro, piuttosto che NULL:

//create the vertices
vertex r = {WHITE, 0, 0};

In secondo luogo, l'uso constants piuttosto che #define:

#define NUM_VERTICES 8 // <- bad
const int NumberVertices = 8; // <- good

Infine, date il vostro enum un nome, o metterla in un namespace:

enum Color { WHITE, GRAY, BLACK };

Spero che questi aiuto!

Answer 2

Non hai inizializzato l'iteratore, quindi non è valida per inserire con. Si potrebbe utilizzare r_list->push_back(pr) invece, per esempio.

Inoltre, i puntatori nel proprio elenco non stanno per essere valida una volta r esce dallo scope. Ovviamente questo non è un problema, in questo caso dal momento che è in main(), ma suppongo che non è l'esempio esatto in cui avete intenzione di utilizzare il codice, quindi potrebbe tornare a mordere voi ...

Answer 3

Prima di tutto, voi non sono in fase di inizializzazione it a nulla. Vuoi dire:

list<vertex*>::iterator it = r_list->begin();

Inoltre, perché stai inizializza un int e char NULL? Di solito la gente usa NULL per i puntatori.

Inoltre, come su di chiamare il vostro enum e beneficiando della sicurezza tipo di enumerazioni, invece di usarli come int?

Inoltre, non c'è bisogno di creare una nuova variabile per fare un puntatore al vertice. Quando si chiama inserto, è possibile passare in &r.

Inoltre, come fa notare Peter, perché non basta usare push_back()?

Il codice dovrebbe essere più simile a questo:

using namespace std;

enum Color { 
    WHITE, 
    GRAY, 
    BLACK 
};

struct vertex
{
    Color color;
    int distance;
    char parent;
};

int main(int argc, char** argv) {
    //create the vertices
    vertex r = {WHITE, 0, ''};

    //create a list to hold the vertices
    list* r_list = new list();

    list::iterator it = r_list->begin();
    r_list->insert(it, &r);

    // Or even better, use push_back (or front)
    r_list->push_back(&r);
}

Answer 4

Non hai inizializzato it, quindi si sta inserendo in un / inizializzata posto / puntatore casuale.

modi normali di aggiungere elementi a un std::list includere il suo metodi push_back e push_front; che normalmente si usa insert solo se si era in precedenza diversamente stabilito il luogo specifico in cui si desidera inserire un elemento di più.