#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <memory.h>

template<typename K, typename V, int factor = 272, int max_level = 12>
struct skip_list {
    struct node {
        K key;
        V val;
        node** next;
    };

    node* head = 0;
    int level = 0;
    int count = 0;

    int size() {
        return count;
    }

    V* set(const K& key) {
        if (!head) {
            head = new node();
            head->next = new node*[max_level];
            memset(&head->next[0], 0, sizeof(node*) * max_level);
        }

        V* v = get(key);
        if (v) {
            return v;
        }

        int lv = random();
        node* nd = new node();
        nd->key = key;
        nd->next = new node*[lv];
        memset(&nd->next[0], 0, sizeof(node*) * lv);

        for (int i = this->level; i < lv; i++) {
            head->next[i] = nd;
        }
        node* search = head;
        for (int i = this->level - 1; i >= 0; i--) {
            search = this->select_closest(search, i, key);
            if (i >= lv) {
                continue;
            }
            if (search->next[i]) {
                nd->next[i] = search->next[i];
                search->next[i] = nd;
            } else {
                search->next[i] = nd;
            }
        }
        if (lv > this->level) {
            this->level = lv;
        }

        ++this->count;
        return &nd->val;
    }

    V* get(const K& key) {
        node* search = head;
        for (int i = this->level - 1; i >= 0; i--) {
            search = this->select_closest(search, i, key);
            node* tar = search->next[i];
            if (tar && !(tar->key < key || key < tar->key)) {
                return &tar->val;
            }
        }
        return nullptr;
    }

    void del(const K& key) {
        node* search = head;
        node* find = nullptr;
        for (int i = this->level - 1; i >= 0; i--) {
            search = this->select_closest(search, i, key);
            node* tar = search->next[i];
            if (tar && !(tar->key < key || key < tar->key)) {
                search->next[i] = tar->next[i];
                find = tar;
            }
        }
        if (!find) {
            return;
        }
        delete[] find->next;
        delete find;
        --this->count;
    }

private:
    static inline int random() {
        int lv = 1;
        while (rand() % 1001 < factor && lv < max_level) {
            ++lv;
        }
        return lv;
    }

    static inline node* select_closest(node* search, int i, const K& k) {
        while (search->next[i] && search->next[i]->key < k) {
            search = search->next[i];
        }
        return search;
    }
};

https://www.jianshu.com/p/9d8296562806