Iterator stops pointing to a value when it is added to a struct which is added to a vector of lists?

Question

The premise of the project I am doing is to make skip lists with iterators and not pointers. I have created a vector of lists of nodes. And in the node struct, it contains an iterator which is supposed to be the iterator of the list below it while preserving position. The problem is when I create a new node, set its below iterator to the list below's iterator, and later try to access it by de referencing it, it seg faults. I think this is because the iterator is not initialized and it cant be dereferenced as it does not appear to be a bounds issue.

struct Node // in header file
{
  int value;
  list<Node>::iterator below;
   Node(int v, list<Node>::iterator b){
        value = v;
        below = b;
   }
   Node(){} 
   Node(int v){
        value = v;
   }


};

vector<list<Node>> skipList; //this is the skipList initialized in the header

//insert called to add numbers to skiplist

void SkipLists::insert(int num){
    list<Node>::iterator loc;
    if(skipList.empty()){
        list<Node> nodes;
        nodes.push_back(Node(num));
        skipList.push_back(nodes);
    }else{
        loc = insertPlace(num, skipList[skipList.size()-1].begin(), skipList.size() -1);
        skipList[0].insert(loc, Node(num));

    }
    cout << "1.  " << *this << "\n\n\n";
    stack(num, loc);

    //this if statement also segfaults
    if(skipList.size() > 1){
        cout << (*(skipList[1].front().below)).value;
    }

}

//in insertPlace function it segfaults on the while loop's only if a recursive call is made. Meaning the previous value added to the skiplist had height to it. It segfaults when dereferencing it. I tested this by moving it out of the while loop.

list<Node>::iterator SkipLists::insertPlace(int num, list<Node>::iterator it, int height){
    if(height == 0){
        while(it != skipList[0].end() && skipList[0].size() > 0 && num > (*it).value){            // problem: likely not returning a good (*it).below or never setting it properly. 
            it++;
        }
        return it;
    }
    while(it != skipList[height].end() && skipList[height].size() > 0 && num > (*it).value){
        cout << "he\n";
        it++;
        cout << "lo\n";
    }
    return insertPlace(num, (*it).below, --height);
}

stack is used to add vertical elements in the skip list based on probability. This is where the nodes are given a "below" iterator.

void SkipLists::stack(int num, list<Node>::iterator loc){
    int flip = rand() % 2;
    int count = 1;
    list<Node>::iterator prev = loc;
    list<Node>::iterator it;
    while(flip == 1){
        count++;
        flip = rand() % 2;

        if(skipList.size() < count){
            list<Node> nodes;
            nodes.push_back(Node(num, prev));
            skipList.push_back(nodes);
            prev = skipList[skipList.size()-1].begin();
        }else{
            it = skipList[count-1].begin();
            while(it != skipList[count -1].end() && num > (*it).value){
                it++;
            }
            prev = skipList[count -1].insert(it,Node(num, prev));

        }
    }
}

Answer 1

vector<list<Node>> skipList; is dangerous. If a new list is added then the vector might relocate all other lists and that invalidates all stored iterators. Even though the lists can be move constructed in a new place, they are still new objects and comparing .end() with a iterator obtained from another object is undefined behaviour.

I think that is what eventually happens in your code.

[Probably not a proper answer, but its too long for a comment and I won't debug author's code to make sure.]

Answer 2

One obvious error is your Node class implementation.

If you look at your Node constructor that takes a single int, you failed to initialize the below iterator. Thus any access in attempting to dereference below will result in undefined behavior occurring, as you're doing in this line:

cout << (*(skipList[1].front().below)).value;

If the skip list is empty, you will see that your code will produce Node objects where below is not initialized.

Here is a stripped down, simple example using more or less the code you posted:

#include <list>
#include <vector>
#include <iostream>

struct Node // in header file
{
    int value;
    std::list<Node>::iterator below;
    Node(int v, std::list<Node>::iterator b) {
        value = v;
        below = b;
    }
    Node() {}
    Node(int v) {
        value = v;
    }
};

class SkipLists
{
    private:
        std::vector<std::list<Node>> skipList;
    public:
        void insert(int num);
        std::list<Node>::iterator insertPlace(int num, std::list<Node>::iterator it, int height);
        void stack(int num, std::list<Node>::iterator loc);
};

using namespace std;

void SkipLists::insert(int num) 
{
    list<Node>::iterator loc;
    if (skipList.empty()) 
    {
        list<Node> nodes;
        nodes.push_back(Node(num));
        skipList.push_back(nodes);
    }
    else 
    {
        loc = insertPlace(num, skipList[skipList.size() - 1].begin(), skipList.size() - 1);
        skipList[0].insert(loc, Node(num));

    }

    stack(num, loc);

    //this if statement also segfaults
    if (skipList.size() > 1) {
        cout << (*(skipList[1].front().below)).value;
    }
}

list<Node>::iterator SkipLists::insertPlace(int num, list<Node>::iterator it, int height) 
{
    if (height == 0) {
        while (it != skipList[0].end() && skipList[0].size() > 0 && num > (*it).value) 
        {
            it++;
        }
        return it;
    }
    while (it != skipList[height].end() && skipList[height].size() > 0 && num > (*it).value) 
    {
        cout << "he\n";
        it++;
        cout << "lo\n";
    }
    return insertPlace(num, (*it).below, --height);
}

void SkipLists::stack(int num, list<Node>::iterator loc) {
    int flip = rand() % 2;
    int count = 1;
    list<Node>::iterator prev = loc;
    list<Node>::iterator it;
    while (flip == 1) {
        count++;
        flip = rand() % 2;

        if (skipList.size() < count) {
            list<Node> nodes;
            nodes.push_back(Node(num, prev));
            skipList.push_back(nodes);
            prev = skipList[skipList.size() - 1].begin();
        }
        else {
            it = skipList[count - 1].begin();
            while (it != skipList[count - 1].end() && num > (*it).value) {
                it++;
            }
            prev = skipList[count - 1].insert(it, Node(num, prev));
        }
    }
}

// Test    
int main()
{
    SkipLists s;
    s.insert(4);
}

You will see that below is not initialized on the line you are saying your application crashes on when running this very small sample.

You also have the same issue with the Node default constructor where both the value and below members are not initialized. When you create an object, all the members should be in some sort of valid state, or "null" in some way. For iterators, it is harder to do this since there isn't a "null" iterator, unless you can set the iterator to an existing list's end() iterator.

Basically you need to design your class so that you are sure that the iterator is pointing somewhere valid, or some other means of indicating that the iterator should not be dereferenced.