STL List to hold structure pointers

Question

I have a structure called vertex and I created some pointers to them. What I want to do is add those pointers to a list. My code below, when it tries to insert the pointer into the list, creates a segmentation fault. Can someone please explain what is going on?

#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

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!

Answer 2

You haven't initialised the iterator, so it's not valid to insert with. You could use r_list->push_back(pr) instead, for example.

Also, the pointers in your list aren't going to be valid once r goes out of scope. Obviously that's not a problem in this case since it's in main(), but I assume this isn't the exact example where you're going to use the code, so it may come back to bite you...