First of all, as DarthGizka mentioned, your code is easy to read and understand and except for the memory leak I mentioned in the comments I don't see any errors. I also don't hav
HoweverI can't really contribute on the general question, of how effective skiplists are or what would be the best algorithm to determine the height of each node, however, I think there are still a few things that can be improved in your current implementation:
I believe this is more of a proof-of-concept, but on if you go on with it, you should probably strive to make a interface more similar to STL-like associative containers. Meaning in particular, providing iterators, making a template out of it, providing the typical type defstypedefs and functions (e.g. size()) a.s.o. As mentioned by others, this would also make it easier to compare it to other data structures.
Finally, std::vector seems to be a pretty heavy member for the list nodes (due to the size overhead and the additional memory allocation). If the maximum level is a compiletime constant, you should probably use a member array instead (possibly using multiple different node classes of different sizes, as suggested by DarthGizka).
#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>
class Skip_list {
public:
Skip_list();
~Skip_list();
// non-modifying member functions
/*
It prints the key, value, level
of each node of the skip list.
Prints two nodes per line.
*/
void print() const;
/*
It searches the skip list and
returns the element corresponding
to the searchKey; otherwise it returns
failure, in the form of null pointer.
*/
std::string* find(int searchKey) const;
// modifying member functions
/*
It searches the skip list for elements
with seachKey, if there is an element
with that key its value is reassigned to the
newValue, otherwise it creates and splices
a new node, of random level.
*/
void insert(int searchKey, const std::string& newValue);
/*
It deletes the element containing
searchKey, if it exists.
*/
void erase(int searchKey);
private:
struct Node {
int key;
std::string value;
// pointers to successor nodes
std::vector<Node*> forward;
Node(int k, const std::string& v, int level):
key(k), value(v),forward(level,nullptr)
{}
};
// Generates node levels in the range [1, maxLevel).
int randomLevel() const;
//Returns number of incoming and outgoing pointers
static int nodeLevel(const Node* v);
//creates a node on the heap and returns a pointer to it.
static Node* makeNode(int key, std::string val, int level);
// Returns the first node for which node->key < searchKey is false
Node* lower_bound(int searchKey) const ;
/*
* Returns a collection of Pointers to Nodes
* result[i] hold the last node of level i+1 for which result[i]->key < searchKey is true
*/
std::vector<Node*> predecessors(int searchKey) const ;
// data members
const float probability;
const int maxLevel;
Node* head; // pointer to first node
Node* NIL; // last node
};
//==============================================================================
// Class Skip_list member implementations
Skip_list::Skip_list() :
probability(0.5),
maxLevel(16)
{
int headKey = std::numeric_limits<int>::min();
head = new Node(headKey, "head", maxLevel);
int nilKey = std::numeric_limits<int>::max();
NIL = new Node(nilKey, "NIL", maxLevel);
std::fill(head->forward.begin(), head->forward.end(), NIL);
}
Skip_list::~Skip_list() {
auto node = head;
while (node->forward[0]) {
auto tmp = node;
node = node->forward[0];
delete tmp;
}
delete node;
}
std::string* Skip_list::find(int searchKey) const {
std::string* res{};
if (auto x = lower_bound(searchKey)) {
if (x->key == searchKey && x!=NIL) {
res = &(x->value);
}
}
return res;
}
void Skip_list::print() const {
Node* list = head->forward[0];
int lineLenght = 0;
std::cout << "{";
while (list != NIL) {
std::cout << "value: " << list->value
<< ", key: " << list->key
<< ", level: " << nodeLevel(list);
list = list->forward[0];
if (list != NIL) std::cout << " : ";
if (++lineLenght % 2 == 0) std::cout << "\n";
}
std::cout << "}\n";
}
void Skip_list::insert(int searchKey, const std::string& newValue) {
auto preds = predecessors(searchKey);
{//reassign value if node exists and return
auto next = preds[0]->forward[0];
if (next->key == searchKey && next != NIL) {
next->value = newValue;
return;
}
}
// create new node
const int newNodeLevel = randomLevel();
auto newNodePtr = makeNode(searchKey, newValue, newNodeLevel);
// connect pointers of predecessors and new node to respective successors
for (int i = 0; i < newNodeLevel; ++i) {
newNodePtr->forward[i] = preds[i]->forward[i];
preds[i]->forward[i] = newNodePtr;
}
}
void Skip_list::erase(int searchKey) {
auto preds = predecessors(searchKey);
//check if the node exists
auto node = preds[0]->forward[0];
if (node->key == searchKey && node != NIL) {
return;
}
// update pointers and delete node
for (size_t i = 0; i < nodeLevel(node); ++i) {
preds[i]->forward[i] = node->forward[i];
}
delete node;
}
//###### private member functions ######
int Skip_list::nodeLevel(const Node* v) {
return v->forward.size();
}
Skip_list::Node* Skip_list::makeNode(int key, std::string val, int level) {
return new Node(key, val, level);
}
int Skip_list::randomLevel() const {
int v = 1;
while (((double)std::rand() / RAND_MAX) < probability &&
v < maxLevel) {
v++;
}
return v;
}
Skip_list::Node* Skip_list::lower_bound(int searchKey) const{
Node* x = head;
for (unsigned int i = nodeLevel(head); i-- > 0;) {
while ( x->forward[i]->key < searchKey) {
x = x->forward[i];
}
}
return x->forward[0];
}
std::vector<Skip_list::Node*> Skip_list::predecessors(int searchKey) const {
std::vector<Node*> result(nodeLevel(head),nullptr);
Node* x = head;
for (unsigned int i = nodeLevel(head); i-- > 0;) {
while (x->forward[i]->key < searchKey) {
x = x->forward[i];
}
result[i] = x;
}
return result;
}
//==================================================
int main() {
// 1.Initialize an empty Skip_list object
Skip_list s;
// 2. insert()
for (int i = 0; i < 50; ++i) {
std::stringstream ss;
ss << i;
s.insert(i, ss.str());
}
// 2a. print()
s.print();
std::cout << std::endl;
// 3. find()
auto f = s.find(10);
if (f) std::cout << "Node found!\nvalue: " << f << '\n';
else std::cout << "Node NOT found!\n";
// 4. insert() - reassign
s.insert(40, "TEST");
// 4a. print()
s.print();
std::cout << std::endl;
// 5. erase()
s.erase(40);
// 5a. print();
s.print();
std::cout << std::endl;
std::cout << "\nDone!\n";
getchar();
}
