STL List to hold structure pointers

c++, list, pointers, segmentation-fault, stl

Solution

There are several things wrong here.

First off, you aren't initializing the iterator, like other's have said:

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

Do this and your code will be fine. But your code is done in a bad manner.

Why are you allocating the list from the heap? Look at your code: you have a memory leak. You aren't calling `delete r_list` anywhere. This is why you should use smart pointers (`std::unique_ptr`, `std::shared_ptr` if you have C++11, boost equivalents otherwise : `boost::scoped_ptr` and `boost::shared_ptr`)

But better yet, just do it on the stack:

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

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

r_list.insert(it, pr);

In addition, using the iterator to insert is going about things the long way. Just use push front() or push back():

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

r_list.push_back(pr);

Another thing: if your list outlives the vertex you've constructed, it will be pointing to something invalid.

For example:

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

One solution is to store pointers to heap-allocated vertices:

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

Now even after the function the list is pointing to a valid heap-allocated vertex. This now has the problem that when you're done using the list, you need to go through the lsit and call `delete` on each element. This problem is assisted by using the Boost Pointer Container Library.

The best way, though, is to just store vertices themselves (rather than pointers to them):

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

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

r_list.push_back(r);

If you give vertex a constructor, you can even just construct them in-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));

(these are now outside your problem)

Firstly, NULL is generally only used when dealing with pointers. Since `distance` and `parent` are not pointers, use `0` to initialize them, rather than `NULL`:

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

Secondly, use `constants` rather than `#define`:

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

Lastly, give your enum a name, or place it in a namespace:

enum Color { WHITE, GRAY, BLACK };

Hope these help!

Problem

Original source