#define MAX_LEVEL 16

 typedef int KeyType;

 typedef int ValueType;

 typedef struct nodeStructure* Node;

 struct nodeStructure

 {

     KeyType key;

     ValueType value;

     Node forward[];

 };

 class SkipList

 {

 public:

     SkipList();

     Node createNode(int level, const KeyType& key, const ValueType& value);

     void createList();

     bool insert(const KeyType& key, const ValueType& value);

     bool erase(const KeyType& key, ValueType& value);

     bool search(const KeyType& key, ValueType& value);

 private:

     int randomLevel();

 private:

     int _level;

     Node _header;

 };

 #include "SkipList.h"

 #include <iostream>

 SkipList::SkipList()

 {

     _level = ;

     _header = createNode(MAX_LEVEL, , );

     Node tail = createNode(, 0x7fffffff, );

     for (int i = ; i < MAX_LEVEL; ++i)

         _header->forward[i] = tail;

 }

 Node SkipList::createNode(int level, const KeyType& key, const ValueType& value)

 {

     Node node = (Node)malloc(

         sizeof(nodeStructure) + sizeof(Node) * level);

     node->key = key;

     node->value = value;

     return node;

 }

 int SkipList::randomLevel()

 {

     int k = ;

     // 50% k++

     while (rand() % )

         k++;

     return (k < MAX_LEVEL) ? k : MAX_LEVEL - ;

 }

 bool SkipList::insert(const KeyType& key, const ValueType& value)

 {

     Node update[MAX_LEVEL];

     Node node = _header;

     // search

     for (int i = _level; i >= ; --i)

     {

         while (node->forward[i]->key < key)

             node = node->forward[i];

         // record previous node

         update[i] = node;

     }

     // same key

     if (node->forward[]->key == key)

         return false;

     int level = randomLevel();

     // update level

     if (level > _level)

     {

         for (int i = _level + ; i <= level; ++i)

             update[i] = _header;

         _level = level;

     }

     // update pointer

     Node insNode = createNode(level, key, value);

     for (int i = level; i >= ; --i)

     {

         node = update[i];

         insNode->forward[i] = node->forward[i];

         node->forward[i] = insNode;

     }

     return true;

 }

 // similar to insert

 bool SkipList::erase(const KeyType& key, ValueType& value)

 {

     Node update[MAX_LEVEL];

     Node node = _header;

     for (int i = _level; i >= ; --i)

     {

         while (node->forward[i]->key < key)

             node = node->forward[i];

         update[i] = node;

     }

     node = node->forward[];

     if (node->key != key)

         return false;

     for (int i = ; i < _level; ++i)

     {

         if (update[i]->forward[i] != node)

             break;

         update[i]->forward[i] = node->forward[i];

     }

     free(node);

     return true;

 }

 bool SkipList::search(const KeyType& key, ValueType& value)

 {

     Node node = _header;

     for (int i = _level; i >= ; --i)

         // find the last node->key < key

         while (node->forward[i]->key < key)

             node = node->forward[i];

     // node->key >= key

     node = node->forward[];

     if (node->key == key)

     {

         value = node->value;

         return true;

     }

     return false;

 }