How To Create A Skip List in C++?

Posted on 2009-05-10
Last Modified: 2012-06-21
I'm working on an assignment for one of my classes that I'm having a lot of trouble with.  Basically we have to implement a skip list that stores rectangle names and their coordinates.  We also have to implement a couple of other functions, like:

insert name x y w h  (where x y is the bottom coordinate of the rectangle, w is the width, h is the height, and name is the key that it will be sorted by in the skip list)

remove name

remove x y w h

rangesearch x y w h (report all rectangles in the skip list that intersect the query rectangle)

allintersections  (report all rectangles that intersect with others)

search name (return parameters of rectangle name)

Also, when we implement the skip list, in order to receive full credit we need to implement it using node splicing, where basically you store within a node an array called forward that keeps a number of pointers equal to the number of lists in participates in.

We also need to maintain a header array that points to the beginning of the lists at each level. Since the number of levels can grow during insertion of successive nodes I also need to implement a procedure that allows the forward array to be extendible.

I cannot use existing STL C++ templates either.  I pretty much understand the concept, but I'm having trouble translating it into code, so what I'm looking for in a good solution is a link to or example code that does what I have described.

Question by:btlovesyou

Assisted Solution

zwei earned 200 total points
ID: 24350102
This might help (describes implementing skip lists in c++):
LVL 39

Accepted Solution

itsmeandnobodyelse earned 300 total points
ID: 24361828
Below is my own implementation of a SkipList.

The bastypes.h containes some typedefs which you easily can replace. The mutex.h contains a mutex class based on CRITICAL_SECTION resource.

As it is an assignment I can't you give the implementation (which is in skiplist.cpp that must be included by the source using the SkipList).

But you may ask for any implementation and I could give you some code snippets if somewhat is unclear.

#ifndef SKIPLIST_H

#define SKIPLIST_H

// standard includes

#include <stdlib.h>

#include <time.h>


#ifdef _WINDOWS

// suppress warning <<duplicate template instantiation>>

   #pragma warning( disable : 4660 )



// @enum Skiplist limits



   SKIPLIST_MAXLEVEL    = 15, // @emem for about 1 billion (10^9) nodes

   SKIPLIST_PROBABILITY = 4   // @emem probability for next higher skip list 1/4


// project includes

#ifndef BASTYPES_H

   #include <bastypes.h>


#ifndef MUTEX_H

   #include <mutex.h>


// forward declaration

template <class TData, class TKey>

class SkipList;

template <class TData, class TKey>

class SkipListIterator;

template <class TData, class TKey>

class SkipPosition;

#define SkipPositionPtr SkipPosition<TData, TKey>*


// @doc   SkipPosition


// @class One node (element) of a skip list. A SkipPosition has a copy of the

//   <nl> key and a pointer to the data part of the element.


template <class TData, class TKey>

class SkipPosition


// @dataprivate


   // Attributes

   TData*                        m_pData;          // @cmember pointer to data

   TKey                          m_key;            // @cmember copy of key

   SkipPosition<TData, TKey>**   m_pArrForward;    // @cmember array of forward pointers

#ifdef _DEBUG

   int                           m_nLevel;         // skip level for debug purposes


// @funcpublic


   // constructors, destructor

   // @cmember constructor for head node; gets all 16 levels

   SkipPosition(int nLevel);

   // @cmember constructor for data nodes; gets a computed level

   SkipPosition(int nLevel, TData* pData, const TKey& key);

   // @cmember destructor deletes the array (chain) but not the data


   // @cmember get new pointer array depending on level

   void init(int nLevel);


   // @cmember get forward pointer of level idx

   SkipPosition<TData, TKey>*  getForward(int idx)

      { return m_pArrForward[idx]; }

   // @cmember get data pointer

   TData*                       getData()

      { return m_pData; }

   // @cmember get reference of key

   const TKey&                  getKey()

      { return m_key; }

   // @cmember set new forward pointer for level idx (chaining)

   void                         setForward(int idx, SkipPosition<TData, TKey>* pForward)

      { m_pArrForward[idx] = pForward; }

#ifdef _DEBUG

   int                          getLevel()

      { return m_nLevel; }


   friend class SkipList<TData, TKey>;

   friend class SkipListIterator<TData, TKey>;



// @class   Balanced template dictionary. The balancing is done

//          by using a random number of single chained sorted lists.

//          The list of level 0 contains all nodes, level 1 about 1/4,

//          level 2 about 1/16 and so on. For each new node the level

//          of skiplists will be randomly computed. The search strategy

//          is now to start at the highest skip level till the new

//          key is less than one of the nodes keys, go one level

//          down searching again, and so on. On level 0 the key is

//          or a new insertion point is found.


template <class TData, class TKey>

class SkipList


// @dataprivate


   // Attributes

   SkipPosition<TData, TKey>     m_head;     // @cmember head node

   int                           m_nLevel;   // @cmember current maximal level

   CriticalSection               m_cs;       // @cmember to make the map thread-safe

   bool                          m_multiple; // @cmember multiple entries having the same key allowed

// @funcprivate

   // compute random level from 0 to SKIPLIST_MAXLEVEL

   int      randomSkipLevel();

// @funcpublic


   // @cmember default constructor


   // @cmember constructor to set multiple Flag

   SkipList(bool multipleAllowed);

   // @cmember destructor; deletes all nodes but no data


   // operations

   // @cmember   new node

   void         insert( TData* pData, const TKey& key );

   // @cmember remove existing node and return data pointer

   TData*       remove( const TKey& key, TData* pData = NULL );

   // @cmember remove existing node where a not unique key is indexed

   TData*       removeMultiple( const TKey& key, int idx, TData* pData = NULL  );

   // @cmember find node by key

   TData*       find( const TKey& key   );

   // @cmember find node by key and index (if key is not unique)

   TData*       findMultiple( const TKey& key, int idx );

   // @cmember get first node (not using an iterator)

   TData*       getFirst();

   // @cmember get first key (not using an iterator)

   TKey*        getFirstKey();

   // @cmember pop first node (get first node and remove it)

   TData*       popFirst();

   // @cmember check if empty

   bool         isEmpty()

      {  return (m_head.getForward(0) == NULL); }

   // @cmember removes and deletes all data items

   int          deleteAllData();

   // @cmember  gives reference to existing value or insert nodes

   TData&       operator[] (const TKey& key);

   // @cmember get number of entries  

   int          getCount();

   friend class SkipListIterator<TData, TKey>;



// @doc   SkipListIterator


// @class Iterator for a SkipList dictionary.

//   <nl> Step forward (ascending sort order) to SkipList


template <class TData, class TKey>

class SkipListIterator


// @dataprivate


   // Attributes

   SkipList<TData, TKey>*     m_pList;       // @cmember pointer to SkipList

   SkipPosition<TData, TKey>* m_pCur;        // @cmember current node

   int                        m_nCurLevel;   // @cmember current level

   TKey                       m_curKey;      // @cmember current key

// @funcpublic


   // constructor / destructor

   // @cmember constructor; gets the SkipList to iterate on

   SkipListIterator(SkipList<TData, TKey>* pList)

      : m_pList(pList), m_pCur(NULL) {}

   // @cmember default destructor

  ~SkipListIterator() {}

   // @cmember get next element

   TData*      getNext( bool& bFirst );

   // @cmember find next element and set current to find position

   TData*      findNext( bool& bFirst, const TKey& key );

   // @cmember return last key found

   const TKey* getCurrentKey() const;

#ifdef _DEBUG

   int      getCurLevel();



#endif // SKIPLIST_H

Open in new window


Featured Post

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

This article will show you some of the more useful Standard Template Library (STL) algorithms through the use of working examples.  You will learn about how these algorithms fit into the STL architecture, how they work with STL containers, and why t…
C++ Properties One feature missing from standard C++ that you will find in many other Object Oriented Programming languages is something called a Property (…
The viewer will learn how to clear a vector as well as how to detect empty vectors in C++.
The viewer will be introduced to the member functions push_back and pop_back of the vector class. The video will teach the difference between the two as well as how to use each one along with its functionality.

911 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

23 Experts available now in Live!

Get 1:1 Help Now