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

Solution 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!

Solution 2

First of all, you aren't initializing it to anything. Do you mean:

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

Also, why are you initializing an int and char to NULL? Usually people use NULL for pointers.

Also, how about naming your enum and benefiting from the type safety of enums, instead of using them as ints?

Also, no need to create a new variable to make a pointer to the vertex. When you call insert, you can pass in &r.

Also, as Peter points out, why not just use push_back()?

Your code should look more like this:

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

Solution 3

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

Solution 4

You have not initialized it, so you're inserting at a random/uninitialized place/pointer.

Normal ways of adding items to a std::list include its methods push_back and push_front; you'd normally use insert only if you had previously otherwise determined the specific spot in which you want to insert one more item.

View more solutions