std::list of std::pairs with pointers

Question

I'm writing some simple connected component code and running into a weird weird segfault.

My code is as follows; with some definitions first.

Node* node;

typedef std::pair<int, Node*> Edge;

struct Node {
    ...
    std::list<Edge> neighbors;
    ...
}

The code that segfaults is below:

if (node->neighbors.empty())
{
    node->label = label_set.make();
}
else
{
    Node* first_neighbor = node->neighbors.front().second;
    node->label = first_neighbor->label;
    int i = 0;
    for (list<Edge>::iterator it = node->neighbors.begin(); it != node->neighbors.end(); it++)
    {   
        i ++;
        Node* n2 = (Node*)it->second;
        node->label = label_set.merge(node->label, n2->label);
    }
}

The really really weird bit is the following:

(lldb) p node->neighbors
(std::list<std::pair<int, _Node *>, std::allocator<std::pair<int, _Node *> > >) $4 = size=1 {
  [0] = {
    first = 78
    second = 0x00d85520
  }
}
(lldb) p *it
(std::pair<int, _Node *>) $8 = {
  first = 0
  second = 0xa0a45254
}
(lldb) p n2
(Node *) $5 = 0xa0a45254

Seeing this, I understand the segfault. n2 is set to a completely weird value. It's not in the list; am I not iterating the list correctly? Is n2 filled with random data because it is out of the list bounds? But then how did my iteration escape the bounds? I'm clueless.

EDIT: I'm definitely outside the list bounds: at the time of the segfault i == 3.

EDIT2 Could it have something to do with the way I keep track of the nodes?

https://gist.github.com/noio/3082a0f351edb1821e90

Answer 1

Here is possibly what is happening:

If you did comment out the last line in the for loop that calls label_set.merge, you're left with a simple loop that supposedly goes from the beginning to the end of a std::list.

The increment is there (even though it would be better to have done ++it, but that's another story), plus all you're doing in the loop is retrieving it->second. However, your loop, as you claim, runs forever.

Since this is the case, one conclusion is that either node is invalid, or that node->neighbors is invalid. You need to check your code to make sure you're not mismanaging memory or pointers. You may also be better off using a smart pointer as opposed to a raw pointer (maybe even a

std::pair<int, std::shared_ptr<Node>>

if the Node pointer is indeed shared between various objects).

As to the debugger, you can have values that look ok within an invalid object. What is probably happening is that the debugger is showing you what the values are of the various members in an invalid object. Since the object is invalid, those values can be anything, including reasonable looking values.

Edit:

The link you posted here: https://gist.github.com/noio/3082a0f351edb1821e90

shows you obtaining the address of the last item in the vector<Node>. This is dangerous if the vector resizes to a larger capacity, as a vector's iterators will become invalidated. Do not hold onto pointer values that point to data within the vector, unless you can guarantee that the vector will not be resized in the time you're using the pointer.