Liste STL pour contenir des pointeurs de structure

Question

J'ai une structure appelée sommet et j'ai créé quelques conseils pour eux. Ce que je veux faire est d'ajouter ces pointeurs à une liste. Mon code ci-dessous, quand il tente d'insérer le pointeur dans la liste, crée une erreur de segmentation. Quelqu'un peut-il expliquer s'il vous plaît ce qui se passe?

#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

Il y a plusieurs choses mal ici.

Tout d'abord, vous n'êtes pas initialisera la iterator, comme d'autres ont dit de:

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

Pour ce faire, et votre code sera bien. Mais votre code est fait d'une mauvaise manière.

Pourquoi êtes-vous allouez la liste dans le tas? Regardez votre code: vous avez une fuite de mémoire. Vous n'êtes pas appeler delete r_list nulle part. C'est pourquoi vous devez utiliser des pointeurs intelligents ( std::unique_ptr , std::shared_ptr si vous avez 11, équivalents Boost C + autrement: boost::scoped_ptr et boost::shared_ptr )

Mais mieux encore, il suffit de faire sur la pile:

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

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

r_list.insert(it, pr);

En outre, en utilisant l'itérateur pour insérer va sur des choses le long chemin. Il suffit d'utiliser avant push () ou push back () :

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

r_list.push_back(pr);

Une autre chose. Si votre liste survive le sommet que vous avez construit, il pointera quelque chose d'invalide

Par exemple:

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

Une solution consiste à stocker des pointeurs de sommets de tas alloués:

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

Maintenant, même après que la fonction de la liste pointe vers un sommet de tas alloué valide. Cela a maintenant le problème que lorsque vous avez fini d'utiliser la liste, vous devez passer par le lsit et appeler delete sur chaque élément. Ce problème est assisté en utilisant le rel="nofollow Boost pointeur Library Container .

La meilleure façon, cependant, est de simplement stocker des sommets eux-mêmes (plutôt que des pointeurs vers eux):

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

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

r_list.push_back(r);

Si vous donnez vertex un constructeur, vous pouvez même simplement les construire en place:

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

(ceux-ci sont maintenant en dehors de votre problème)

Tout d'abord, NULL est généralement utilisé que lorsqu'ils traitent avec des pointeurs. Depuis distance et parent ne sont pas des pointeurs, utilisez 0 pour les initialiser, plutôt que NULL:

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

En second lieu, l'utilisation constants plutôt que #define:

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

Enfin, donnez votre nom ENUM, ou le placer dans un espace de noms:

enum Color { WHITE, GRAY, BLACK };

espère que ces aide!

Answer 2

Vous n'avez pas initialisées le iterator, il est donc pas valable pour insérer avec. Vous pouvez utiliser à la place r_list->push_back(pr), par exemple.

En outre, les pointeurs dans votre liste ne vont pas être valide une fois r est hors de portée. De toute évidence, ce n'est pas un problème dans ce cas, car il est en main(), mais je suppose que ce n'est pas l'exemple exact où vous allez utiliser le code, il peut revenir à vous mordre ...

Answer 3

Tout d'abord, vous n'êtes pas à quoi que ce soit it initialise. Voulez-vous dire:

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

En outre, pourquoi êtes-vous un int et initialisez char NULL? Habituellement, les gens utilisent NULL pour les pointeurs.

En outre, que diriez-vous de nommer votre ENUM et bénéficier de la sécurité de type de énumérations, au lieu de les utiliser comme ints?

De plus, pas besoin de créer une nouvelle variable pour faire un pointeur vers le sommet. Lorsque vous appelez insert, vous pouvez passer &r.

En outre, comme le souligne Peter, pourquoi ne pas simplement utiliser push_back()?

Votre code devrait ressembler à ceci:

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

Vous ne l'avez pas initialisé it, de sorte que vous insérez dans un lieu / pointeur aléatoire / non initialisée.

façons normales d'ajouter des éléments à un std::list comprennent ses méthodes push_back et push_front; vous utilisez normalement insert que si vous aviez par ailleurs déterminé l'endroit précis où vous souhaitez insérer un autre élément.