Skip List C++

[PhantoM123]

I'm trying to implement the Skip List using this article
http://epaperpress.com/sortsearch/download/skiplist.pdf

  #include<iostream>
#include<cstdlib>
#include<ctime>
#include<limits>

using namespace std;

	template<class T>
	class SkipList{
		private:
			int MaxLevel;
			
			class SkipNode{
				public:
					T* key;
					SkipNode* forward[100];
					SkipNode(T* key){
						this->key=key;
					}
					~SkipNode(){}
			};
			
			SkipNode *header,*NIL;
			float probability;
			int level;
			
			int randomLevel(){
				srand(time(0));
				int lvl = 0;
				while( (float(rand())/RAND_MAX < probability) && (lvl < MaxLevel) )
					lvl++;
				return lvl;
			}
			
		public:
			SkipList(float probability, int maxlvl){
				header=new SkipNode(NULL);
				NIL=new SkipNode(numeric_limits<T*>::max());
				level=1;
				MaxLevel=maxlvl;
				for(int i=1; i<MaxLevel; i++){
					header->forward[i]=NIL;
				}
			}
			
			SkipNode* search(T* key){
				SkipNode* cursor = header;
				int i=level;
				for(i=level; i>0; i--)
					while(*(cursor->forward[i]->key) < (*key))
						cursor=cursor->forward[i];	
				cursor=cursor->forward[i];
				if(cursor->key == *key) 
					return cursor;
				return NULL;
			}
			
			SkipList* insert(T* key){
				SkipNode* cursor = header;
				SkipNode* update[MaxLevel+1];
				for(int i=level; i>0; i--){
					while(*(cursor->forward[i]->key) < *(key))
						cursor=cursor->forward[i];
					update[i]=cursor;
				}
				cursor=cursor->forward[1];
				if(*(cursor->key) == *(key)) //Node already inserted
					return this;
				int lvl = randomLevel();
				if(lvl > level){
					for(int i=level; i<lvl; i++)
						update[i]=header;
					level=lvl;
				}
				SkipNode* x = new SkipNode(key);
				for(int i=1; i<level; i++){
					x->forward[i] = update[i]->forward[i];
					update[i]->forward[i] = x;
				}
				return this;
			}
			
			SkipList* erase(T* key){
				SkipNode* cursor = header;
				SkipNode* update[MaxLevel+1];
				for(int i=level; i>0; i--){
					while(*(cursor->forward[i]->key) < *(key))
						cursor=cursor->forward[i];
					update[i]=cursor;
				}
				cursor=cursor->forward[1];
				if(*(cursor->key) == *(key)){
					for(int i=1; i<level && update[i]->forward[i] != cursor; i++){
						update[i]->forward[i] = cursor->forward[i];
					}
					cursor->~SkipNode();
					while(level>1 && header->forward[level]==NIL){
						level=level-1;	
					}
				}
				return this;
			}
			
			SkipList* print(){
			    SkipNode* cursor = header->forward[1];
			    while (cursor != NIL) {
				cout << "Key: " << cursor->key << " ";	
			    cursor = cursor->forward[0];
			    }
			    return this;
			}
	};
	
	main(){
		SkipList<int>* list = new SkipList<int>(0.50, 4);
		int a=2;
		int b=3;
		list->insert(&a)->insert(&b);
		list->print();
	}

It gives me Segmentation Fault on line 61 (the for-cycle on the insert), but I can't understand why. May you help me please? My deadline is on two days. Thanks.

[Duthomhas]

I've only glanced at the code, but you seem to have a couple issues to deal with.

The cause of your segfault is probably your off-by-one error on line 66.

You should not be dynamically allocating the SkipList, just the nodes.

I'm not sure why you are maintaining separate NIL nodes. This makes life more complicated (and leakier) than it needs to be. If there are no more nodes, just make the next pointer a nullptr.

You are maintaining a very large node by having an array of 100 next pointers for every node. You are also not tracking the number of levels per node. Make sure to reduce and be careful about it:

struct SkipNode
{
  std::size_t level;
  T*          key;
  SkipNode*   forward[];
};

SkipNode* CreateSkipNode( std::size_t level )
{
  SkipNode* node = ::operator new( sizeof(SkipNode) + sizeof(SkipNode*) * level );
  node->level    = n;
  node->key      = nullptr;
  while (n--) node->forward[ n ] = nullptr;
  return node;
}

SkipNode* CreateSkipNode( const T& key, std::size_t level )
{
  SkipNode* node = CreateSkipNode( level );
  node->key = new T( key );
  return node;
}

void DeleteSkipNode( SkipNode* node )
{
  if (node)
  {
    if (node->key) delete node->key;
    if (node->forward[ 0 ]) DeleteSkipNode( node->forward[ 0 ] );
    ::operator delete( node );
  }
}

Your head node is just a dummy, it does not have data attached to it, but it should have all the levels. If necessary, you can reallocate to create new levels, or you can just allocate max-levels at the start. This is an implementation detail you should decide and stick to.

Your use of the word “key” is a little distracting, since this limits your skiplist to, essentially, a set. If you are looking to create an associative array, you will want your data to include both key and value. A std::map does this by using a std::pair <key, value> . You could do the same. That is, make sure it is clear in your head that your “key” is only a key in terms of whatever your lookup function is defined to be.

Your main should look like this:

int main()
{
  SkipList<int> list;
  list.insert( 2 ).insert( 3 );
  list.print();
}

The print function is nice, but I would make sure to add an overloaded stream insertion operator:

template <typename T>
class SkipList
{
  ...
  std::ostream& print( std::ostream& outs ) ...
};

template <typename T>
std::ostream& operator << ( std::ostream& outs, const SkipList <T> & list )
{
  return list.print( outs );
}

Your main function then becomes:

int main()
{
  SkipList<int> list;
  list.insert( 2 ).insert( 3 );
  cout << list << "\n";
}

Hope this helps.

[PhantoM123]

I've fixed the list, thanks for the help.