0

I'm working on this assignment to implement a skip list in c++. Part of the instructions was to do this utilizing a vector of doubly linked lists of nodes and to simulate infinity and negative infinity using the max values accepted for an integer. Also, we cant use pointers only iterators. In my constructor, if I set the height to anything less than 9 when I execute (compiles fine) I get this error:Error in `./a.out': double free or corruption (out): 0x00000000006cb2f0. I'm not sure how since I am not allocating any memory dynamically, also why would it work fine for say 9 or 10 but not for 2? I have included the code for the class.

This is my header file:

#include<iostream>
#include<list>
#include<vector>
using namespace std;

struct SkipNode{
    int value;
    list<SkipNode>::iterator down;
    SkipNode(int x=0):value(x) {};
};

class SkipList{
    private:
        vector<list<SkipNode>> List;
        int size;
        int height;
    public:
        bool isEmpty(){ return List.begin() == List.end();}
        void insert(int x);
        void remove();
        SkipNode search();
        SkipList();
        void printFirstLevel();
        void printList();
};

This is my cpp file:

#include <limits>
#include <ctime>
#include "SkipList.h"
using namespace std;

SkipList::SkipList(): size(0), height(8){
    list<SkipNode> Initial;
    Initial.push_front(numeric_limits<int>::max());
    Initial.push_front(numeric_limits<int>::min());
    for(int i =0;i<height;i++){
        List.push_back(Initial);
    }

    for(int y=height-1; y>0; y--){
        (*List[y].begin()).down = List[y-1].begin();
        (*List[y].end()--).down = List[y-1].end()--;
    }

}

And this is the main function I am using to test it:

#include<iostream>
#include<forward_list>
#include<vector>
#include "SkipList.h"
using namespace std;

int main(){
    SkipList test;
}

I am literally just creating a new object. If I comment out the following line:

(*List[y].end()--).down = List[y-1].end()--;

then it also runs properly but then its not setting the down iterator I have in each node to the one "undearneath" it.

FrankieD
  • 1
  • 1
  • 1
    Please extract a [mcve] from your program, your question is off-topic without it. Also, as a new user here, take the [tour] and read [ask]. – Ulrich Eckhardt Apr 09 '19 at 04:54
  • "Extract" sounds like "use part of it". That is not sufficient. The "Complete" and "Verfiable" will require adding code. It is explained in the link given by Ulrich. – Yunnosch Apr 09 '19 at 05:01
  • 1
    `list::iterator down;` causes undefined behaviour, you can not instantiate a standard container with incomplete type (except for a handful of specific cases). [Ref](https://stackoverflow.com/questions/8329826/can-standard-container-templates-be-instantiated-with-incomplete-types) – M.M Apr 09 '19 at 05:11
  • Forgive me but I have read the links provided and I still dont quite get what you mean by complete example. That is all the code I have just the constructor so far and just creating an object in main. – FrankieD Apr 09 '19 at 05:11
  • 1
    You also cause undefined behaviour by writing to `List[y].end().down` (the `end()` iterator means one-past-the-end, you can't write through it). – M.M Apr 09 '19 at 05:14
  • 1
    A third issue is that `down` will be invalidated by vector reallocation [ref](https://stackoverflow.com/questions/26378894/stdlist-are-the-iterators-invalidated-on-move) – M.M Apr 09 '19 at 05:15
  • But doesn't the decrement operator I included: (*List[y].end()--).down = List[y-1].end()--; take me back one position which means I am not one past the end but at the end? – FrankieD Apr 09 '19 at 05:17
  • Also I just realized that this only happens when the vector needs to resize to fit more items so I think it is a vector reallocation issue. Any tips on how to complete the assignment. Its weird because the down iterator is required. – FrankieD Apr 09 '19 at 05:22
  • 1
    `(*List[y].end()--).down = List[y-1].end()--;` What is this lime supposed to do? If you want to access the last element, then that's `.back()`. Also `(*x).y` is annoying to read, please write `x->y` instead. – n. m. could be an AI Apr 09 '19 at 05:34
  • 1
    @FrankieD post-increment means to use the old value – M.M Apr 09 '19 at 05:35
  • Thank you so much your input was very helpful. @M.M, of course, how could I forget that, fixing that fixed the issue. Thank you so much! – FrankieD Apr 09 '19 at 05:42

0 Answers0