Reputation: 1
I am doing Stroustrup's PPP2 chapter 18 exercise 11: "Research and implement a skip list."
This code gives the exception: Exception thrown at 0x00007FF61A3E656F in Skip List.exe: 0xC0000005: Access violation reading location 0x0000000000000020.
#include <iostream>
#include <vector>
#include <math.h>
// Error on lines 91 & 95: read-access violation: could be related to nullptr in constructors
// Only the first half is relevant to the exception
//
const int maxLevel = 16;
class Node {
public:
std::vector<Node*> next; // vector to hold next nodes at each level
int value;
Node(int value, int level) : value(value), next(level+1, nullptr) {}; // each node knows its position in the hierarchy, next vector is initialized to have level+1 elements, all set to 0
void addNext(Node* node, int level) // add space for upcoming elements if next is not big enough
{
if (level >= next.size())
{
next.resize(level + 1, 0);
}
next[level] = node;
}
~Node() // destructor
{
for (auto& n : next)
{
delete n;
}
}
};
class skipList {
int level;
Node* head; // starting point of the skipList
double P; // fraction/percentage of promotion
public:
skipList() : level(1), head(), P(0.5) {}; // Default
skipList(int level, Node* head, double P) : level(level), head(head), P(P) // Constructor with parameters
{
try {
if (head == nullptr)
{
std::runtime_error("head can't be nullptr");
}
}
catch (std::exception& e)
{
std::cerr << "Exception: " << e.what() << std::endl;
}
catch (...)
{
std::cerr << "Unkown Exception!" << std::endl;
}
}
// main functions
void insert(int value);
void remove(int value);
void search(int value);
void display();
// helper functions
int randomNumber();
};
int skipList::randomNumber()
{
float r = (float)rand() / RAND_MAX;
int lvl = 0;
while (r < P && lvl < maxLevel)
{
lvl++;
r = (float)rand() / RAND_MAX;
}
return lvl;
}
void skipList::insert(int value)
// Insert into base level
// Promote the inserted element depending on a probability
// Repeat until highest level or no promotion possible
try {
// Key of next node is less than key to be inserted then we keep on moving forward on the same level
// Key of next node is greater than the key to be inserted then we store the pointer to current node i at update[i] and move one level down and continue our search.
Node* newNode = new Node(value, 0);
Node** current = &head;
for (int i = level; i >= 0; --i)
{
if (*current == nullptr) break;
while ((*current)->value < value && *current != nullptr)
{
current = &(*current)->next[i]; // increment current, & returns address of pointer to next
}
if (*current != nullptr || (*current)->value > value)
// reached point of insertion or end of level
{
break;
}
else
{
newNode->addNext(*current, i);
*current = newNode;
}
}
int rlvl = randomNumber(); // generate random level for node
// If level is increasing
if (rlvl <= maxLevel && rlvl != level)
{
//Add new nodes at the top level
for (int i = level; i < rlvl; ++i)
{
newNode->addNext(newNode, i);
}
// Update the head pointer
head = newNode;
level = rlvl;
}
}
catch (std::exception& e)
{
std::cerr << "Exception: " << e.what() << std::endl;
}
catch (...)
{
std::cerr << "Unkown Exception!\n";
}
void skipList::display()
// Function to display the skipList
{
std::cout << "\n\n\t---skipList---\n\n";
for (int i = level; i >= 0; i--) // start at top level, go down
{
Node* temp = head;
while (temp != nullptr)
{
std::cout << temp->value << " ";
temp = temp->next[i];
}
std::cout << std::endl;
}
}
int main()
{
// seed randnum generator
srand((unsigned)time(0));
// insert() test
Node node(1, 1);
skipList SkipList(1, &node, 0.5);
for (int i = 1; i <= 15; i++)
{
SkipList.insert(i);
}
SkipList.display();
}
After removing certain pieces of the code, it seems like the issue is me dereferencing a nullptr in the nested while loop and if statement in skipList::insert(): (*current)->value >/< value
. When I get rid of this piece of code, it runs but outputs nothing. I have added a cout before this if statemment: if (*current == nullptr) break;
, and it outputs a bunch of 0's, which I assume means its a nullptr. I've tried changing around my constructors but nothing I do seems to fix it.
Any help is appreciated! Thanks in advance!
Upvotes: 0
Views: 52