Non generic Skip List implementation in C++ Version 2

Question

Edit: This code was reworked and repostetd under a new question: Generic Skip list implementation in C++ Version 3

This is a follow up of: Non generic Skip List implementation in C++

If you don't know what a Skiplist is: https://en.wikipedia.org/wiki/Skip_list

I continued the work on the Skiplist. I tried to incorporate the improvements suggested. I still don't feel ready to add more stuff ( Iterator class, Template Skipnode). I think it's better to first present the progress so far.

A short summary of what has changed:

Documentation / Clean up the code:

I added alot more comments and tried to make the code more readable in general. I hope the code is now easier to follow. I think one of the reasons not many people commented last time, was the missing explanations in the code.

Vector:

I removed the false micromanagement of vectors size.

Random Generator:

The random generator was reworked like suggested.

Rules of Five:

I implemented the missing functions Copy Constructor, Move Constructor, Copy Assignment and Move assignment.

Implementation of Head Element:

Head now doesn't hold key and value anymore, it only contains pointers.

Unit Tests:

I added Unit Tests in seperate cpp / h files to test the vector more systematically.

skiplist.h

#ifndef SKIP_LIST_GUARD
#define SKIP_LIST_GUARD

#include <iostream>
#include <random>
#include <vector>

namespace skiplist {

    class Skiplist {
    public:
        Skiplist() = default;                   // constructor
        ~Skiplist() noexcept;                   // destructor

        Skiplist(const Skiplist& other);                // copy constructor
        Skiplist& operator=(const Skiplist& other);     // copy assignment

        Skiplist(Skiplist&& other);                     // move constructor
        Skiplist& operator=(Skiplist&& other);          // move assignment

        void insert(int key, int value);    // insert elements, double keys are not allowed
        bool erase(int key);                // search for an element and erase it from the skip list
        int* find(int key);                 // find element by key and return the value
        void clear() noexcept;              // erase all elements 

        size_t size() const;                                // return count of nodes
        int get_top_level() const { return top_level; }     // maximum height the skiplist has reached

        void print(std::ostream& os) const;                 // prints out all elements in list, replace if iterators implemented (for const auto & x : skiplist)
        void debug_print(std::ostream& os) const;           // show all the levels for debug only. can this be put into skiplist_unit_tests ?
    private:
        struct Skipnode;                // forward declaration so Basenode can have Skiplist*

        struct Basenode  {                                      // Empty node, mainly created to represent head element. 
                                                                // Is there a way to get a empty head with no key / values without using this ?
            Basenode(int in_level);
            Basenode(const std::vector<Skipnode*>& in_next);

            std::vector <Skipnode*> next;
        };

        struct Skipnode : Basenode {                                    // derived so with Basenode* we can start the iteration of the node on head
            Skipnode(int in_key, int in_value, int in_level);
            Skipnode(int in_key, int in_value, const std::vector<Skipnode*>& in_next);

            int key;
            int value;
        };

        size_t top_level_of_new_node();         // helper function to calculate level of new node random

        Basenode head{0};                   // element before first element containg pointers to all the first elements of each level
        size_t top_level = 0;               // maximum level the nodes have reached so far
        std::mt19937 random_engine = std::mt19937{ std::random_device{}() };  //random generator member
    };

    bool next_level(std::mt19937& eng);         // flip coin helper function returning true or false random
}
#endif

skiplist.cpp

#include "skiplist.h"

namespace skiplist {


    Skiplist::Basenode::Basenode(int in_level)
        :next{ in_level,nullptr }
    {
    }

    Skiplist::Basenode::Basenode(const std::vector<Skipnode*>& in_next)
        : next{ in_next }
    {
    }

    Skiplist::Skipnode::Skipnode(int in_key, int in_value, int in_level)
        :key{ in_key }, value{ in_value }, Basenode{in_level}
    {
    }

    Skiplist::Skipnode::Skipnode(int in_key, int in_value, const std::vector<Skipnode*>& in_next)
        : key{ in_key }, value{ in_value }, Basenode{in_next}
    {
    }

    Skiplist::~Skiplist() noexcept      // destructor
    {
        if (top_level == 0) return;

        Skipnode* current_position = head.next[0];   //start on first element

        while (current_position->next[0] != nullptr) {

            Skipnode* lastpos = current_position;
            current_position = current_position->next[0];
            delete lastpos;
        }
        delete current_position;         //delete last element
    }

    Skiplist::Skiplist(const Skiplist& other)       // copy constructor
        :head{other.head},top_level{other.top_level}, random_engine{other.random_engine }
        // on the first level let the other Skiplist present its elements and make a deep copy of them
        // now still the higher levels point to the other node so this is fixed in the second part
        // then the next level pointers are installed linked to the elements of the new node
    {
        if (top_level == 0) return;     // no elements are present so dont bother to allocate nodes

        {
            // installment of lowest level, each element is located here
            Skipnode* other_node = other.head.next[0];
            Basenode* current_position = &head;

            while (other_node != nullptr) {
                Skipnode* new_node = new Skipnode{ other_node->key,other_node->value,other_node->next };

                current_position->next[0] = new_node;
                current_position = current_position->next[0];
                other_node = other_node->next[0];
            }
            current_position->next[0] = nullptr;
        }

        // installment of the other levels
        for (size_t curr = 1; curr < top_level; ++curr) {

            Basenode* current_position = &head;                         // the current position of the level[curr]
            Skipnode* next_position = current_position->next[curr];     // next position after curr containing still pointers to the other skiplist
            Basenode* lowest_position = &head;                          // lowest level position used to find the new pointers and attach them "behind" current

            while (lowest_position != nullptr && next_position != nullptr) {

                if (lowest_position->next[0]->key  == next_position->key) {     // check by unique key, address of next pos is still of the other skiplist

                    current_position->next[curr] = lowest_position->next[0];        // lowest is the valid address of new node
                    current_position = current_position->next[curr];
                    next_position = next_position->next[curr];                      // go to next element of other node

                    if (next_position == nullptr) {                     // case end is reached
                        current_position->next[curr] = nullptr;
                        current_position = current_position->next[curr];
                    }
                }
                else {      // forward position of lowest level until other key == next position key
                    lowest_position = lowest_position->next[0];
                }
            }
        }   
    }

    Skiplist& Skiplist::operator=(const Skiplist& other)        // copy assignment
        // copy assignmnt currently the same as copy constructor
        // would it be better to reuse the already existing space?
        // maybe override the values of already available nodes
    {
        if (&other == this) return *this;

        head = other.head;
        top_level = other.top_level;
        random_engine = other.random_engine;;

        if (top_level == 0) return *this;       // no elements are present so dont bother to allocate nodes

        {
            // installment of lowest level, each element is located here
            Skipnode* other_node = other.head.next[0];
            Basenode* current_position = &head;

            while (other_node != nullptr) {
                Skipnode* new_node = new Skipnode{ other_node->key,other_node->value,other_node->next };

                current_position->next[0] = new_node;
                current_position = current_position->next[0];
                other_node = other_node->next[0];
            }
            current_position->next[0] = nullptr;
        }

        // installment of the other levels
        for (size_t curr = 1; curr < top_level; ++curr) {

            Basenode* current_position = &head;                         // the current position of the level[curr]
            Skipnode* next_position = current_position->next[curr];     // next position after curr containing still pointers to the other skiplist
            Basenode* lowest_position = &head;                          // lowest level position used to find the new pointers and attach them "behind" current

            while (lowest_position != nullptr && next_position != nullptr) {

                if (lowest_position->next[0]->key == next_position->key) {      // check by unique key, address of next pos is still of the other skiplist

                    current_position->next[curr] = lowest_position->next[0];        // lowest is the valid address of new node
                    current_position = current_position->next[curr];
                    next_position = next_position->next[curr];                      // go to next element of other node

                    if (next_position == nullptr) {                     // case end is reached
                        current_position->next[curr] = nullptr;
                        current_position = current_position->next[curr];
                    }
                }
                else {      // forward position of lowest level until other key == next position key
                    lowest_position = lowest_position->next[0];
                }
            }
        }
        return *this;
    }

    Skiplist::Skiplist(Skiplist&& other)    // move constructor
        :head{ other.head }, top_level{ other.top_level }, random_engine{ other.random_engine }
    {
        head.next = other.head.next;    // point all other nodes to new location
        other.head = Basenode{ 0 };     // empty other head so the connections to the nodes are gone
        other.top_level = 0;
        other.random_engine = std::mt19937{ std::random_device{}() };
    }

    Skiplist& Skiplist::operator=(Skiplist&& other)         // move assignment
    {
        head = other.head;
        top_level = other.top_level;
        random_engine = other.random_engine;

        head.next = other.head.next;    // point all other nodes to new location
        other.head = Basenode{ 0 };     // empty other head so the connections to the nodes are gone
        other.top_level = 0;
        other.random_engine = std::mt19937{ std::random_device{}() };
        return *this;
    }

    size_t Skiplist::top_level_of_new_node()
        // flips a "coin" true / false . As long as the result is true the level gets increased
        // the chance to reach a higher level decreases evey time by roughly half
        // e.g. level 2 = 50% 3 = 25% etc.
        // This is to make sure that on higher levels there are less nodes then on the lower ones
        // the count of nodes on each levels should be arround half of the count of nodes on the level before
        // if calculated level is bigger than the max level it gets increased
    {
        size_t new_node_level = 0;

        do {
            ++new_node_level;

            if (new_node_level == (top_level + 1)) {         //new node can maximum grow by one lvl;
                ++top_level;

                head.next.resize(head.next.size() + 1, nullptr);        // head.next size must be always = top size
                break;
            }
        } while (next_level(random_engine));     //flip coin. every time it is true go to the next lvl

        return new_node_level;
    }

    void Skiplist::insert(int key, int value)
        // first key and value is inserted into a new insert_node.
        // the level until were the node is present is calculated "random"
        //
        // Then the right position for the node is searched:
        // The search starts on the highest level of the insert_node
        // if next node on the level is not exist or the value of the key bigger
        // check if node is high enough to be on this height
        // if high enough install node between current and next
    {
        // make a new node which is present until the calculated_level

        Skipnode* new_node = new Skipnode(key, value, top_level_of_new_node());    //create new node

        size_t current_level = top_level;   //start on highest lvl
        Basenode* current_position = &head;   //start on first element

        bool node_added = false;

        do {
            const size_t curr = current_level - 1;      // for readability

            if (current_position->next[curr] == nullptr || current_position->next[curr]->key > key) {

                if (new_node->next.size() >= current_level) {       // is node on this level?

                    node_added = true;

                    new_node->next[curr] = current_position->next[curr];        // install new node before next node
                    current_position->next[curr] = new_node;
                }

                --current_level;      // go to the next lower lvl
            }
            else {
                current_position = current_position->next[curr];        // move to the next element on the level
            }
        } while (current_level > 0);

        if (!node_added)            // case new node could not be added if new key == key in table
            delete new_node;
    }

    bool Skiplist::erase(int key)
        // starts search on the highest lvl of the skiplist
        // if a node with the erase key is found the algorith goes 
        // down until the lowest lvl.
        // on the way down all links with the key in the list are removed
        // on the lowest lvl the current node which contains the erase key is deleted
    {
        size_t current_level = top_level;    //start on highest lvl
        Basenode* current_position = &head;   //start on head

        while (current_level > 0) {

            const size_t curr = current_level - 1;      // for readability
            const size_t top = top_level - 1;       // for readability

            if ((current_position->next[curr] == nullptr) || (current_position->next[curr]->key > key)) {
                --current_level;
            }
            else if (current_position->next[curr]->key == key) {     //key found on current lvl

                --current_level;                                     // go down first before link is deleted

                if (current_level != 0)
                    current_position->next[curr] = current_position->next[curr]->next[curr];   // take out pointer of found element from list on current level
                else {                      // first level of skip node is reached 
                    Skipnode* delete_node = current_position->next[current_level];              // store position for delete 
                    current_position->next[curr] = current_position->next[curr]->next[curr];                            // take out pointer of list
                    delete delete_node;                                                                                 // delete current position found node 

                    while (head.next[top_level - 1] == nullptr  /*&& top_level > 1*/) {  //no nodes on highest lvl 
                        --top_level;
                        if (top_level == 0)
                            break;
                    }

                    return true;
                }
            }
            else {
                current_position = current_position->next[curr];        // iterate horizontal on current lvl
            }
        }
        return false;
    }

    int* Skiplist::find(int key) 
        // find element by key and return pointer to value
        // first it is iterated horizontal and vertical until the last level is reached
        // on the last level if the keys match the val is returned
    {
        Basenode* current_position = &head;       //start on head
        size_t current_level = top_level;       //start on highest lvl

        while (current_level > 1) {         
            const size_t curr = current_level - 1;      // for readability

            if (current_position->next[curr] == nullptr || (current_position->next[curr]->key >= key)) {
                --current_level;                                        // traverse veertical
            }
            else {
                current_position = current_position->next[curr];        // traverse horizontal
            }
        }

        while (current_position->next[0] != nullptr) {  

            if (current_position->next[0]->key == key) {      // element found
                current_position = current_position->next[0];

                return &static_cast<Skipnode*>(current_position)->value;
            }
            current_position = current_position->next[0];
        }
        return nullptr; //element was not found;
    }

    void Skiplist::clear() noexcept
    {
        if (top_level == 0) return;

        Skipnode* current_position = head.next[0];   //start on first element

        while (current_position->next[0] != nullptr) {

            Skipnode* lastpos = current_position;
            current_position = current_position->next[0];
            delete lastpos;
        }
        delete current_position;         //delete last element

        top_level = 0;
        head = Basenode{ 0 };
    }

    size_t Skiplist::size() const
        // size of the skipnode is calculated on request
    {
        if (top_level == 0) return 0;      //special case nothing is build yet

        size_t size = 0;

        const Basenode* current_position = &head;

        if (current_position->next.empty())
            return size;

        while (current_position->next[0] != nullptr) {
            ++size;
            current_position = current_position->next[0];
        }
        return size;
    }

    void Skiplist::print(std::ostream& os) const
        //prints out all elements
    {
        if (top_level == 0)
            return;

        const Skipnode* current_position = head.next[0];

        while (current_position != nullptr) {
            os << current_position->key << "/" << current_position->value << " ";
            current_position = current_position->next[0];
        }
        os << "\n";
    }

    void Skiplist::debug_print(std::ostream& os) const
        //messy debug routine to print with all available layers
    {
        if (top_level == 0) {
            os << "empty" << '\n';
            return;
        }

        Basenode* current_position = const_cast<Basenode*>(&head);
        size_t current_level = current_position->next.size() - 1;

        current_position = current_position->next[current_level];

        if (head.next[0] == nullptr)
            return;

        while (current_level >= 0) {
            os << "lvl: " << current_level << "\t";

            Basenode* lastpos = const_cast<Basenode*>(&head);

            while (current_position != nullptr) {

                if (current_level > 0) {

                    int void_count = 0;

                    while (lastpos != nullptr && static_cast<Skipnode*>(lastpos)->key != static_cast<Skipnode*>(current_position)->key) {
                        lastpos = lastpos->next[0];
                        ++void_count;
                    }

                    for (int i = 0; i < void_count - 1; ++i)
                        os << "-/-- ";
                }
                if (current_position != &head)
                    os << static_cast<Skipnode*>(current_position)->key << "/" << static_cast<Skipnode*>(current_position)->value << " ";
                current_position = static_cast<Skipnode*>(current_position->next[current_level]);
            }
            os << "\n";

            if (current_level == 0)
                break;

            --current_level;
            current_position = const_cast<Basenode*>(&head);
        }
    }

    bool next_level(std::mt19937& eng)
    {
        static auto val = std::mt19937::result_type{ 0 };
        static auto bit = std::mt19937::word_size;

        if (bit >= std::mt19937::word_size)
            val = eng();

        return val & (std::mt19937::result_type{ 1 } << (bit++));
    }
}

skiplist_unit_test.h

#ifndef SKIPLIST_UNIT_TEST_GUARD_280620182216
#define SKIPLIST_UNIT_TEST_GUARD_280620182216

#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <chrono>
#include "skiplist.h"

namespace skiplist::unit_test {

    int get_random(int min, int max);

    void insert_print(int key, int val, Skiplist& sk, const std::string& skiplist_name, std::ostream& os);
    void erase_print(int key, Skiplist& sk, const std::string& skiplist_name, std::ostream& os);
    void info_print(const Skiplist& a, const std::string& a_name, std::ostream& os);

    void test_insert_and_erase(std::ostream& os);
    void test_leakage_of_memory(std::ostream& os);
    void test_find(std::ostream& os);

    void test_copy_constructor(std::ostream& os);
    void test_move_constructor(std::ostream& os);

    void test_copy_assignment(std::ostream& os);
    void test_move_assignment(std::ostream& os);

    void test_performance_of_insert_delete(std::ostream& os, const int repeats, const int count_of_elements);
}

#endif

skiplist_unit_test

#include "skiplist_unit_test.h"

namespace skiplist::unit_test{

    int get_random(int min, int max)
    {
        static std::random_device rd;
        static std::mt19937 mt(rd());
        std::uniform_int_distribution<int> distribution(min, max);
        return distribution(mt);
    }

    void insert_print(int key, int val, Skiplist& sk, const std::string& skiplist_name, std::ostream& os)
    {
        sk.insert(key, val);
        os << "insert in " << skiplist_name << " key " << key << " and val  " << val << '\n' << '\n';
    }

    void erase_print(int key, Skiplist& sk, const std::string& skiplist_name, std::ostream& os)
    {
        sk.erase(key);
        os << "erase from " << skiplist_name << " key " << key << '\n' << '\n';
    }

    void info_print(const Skiplist& a, const std::string& a_name, std::ostream& os)
    {
        os << "Skiplist " << a_name << ":\n";
        a.debug_print(os);
        os << "top_lvl:" << a.get_top_level() << '\n';
        os << "size:" << a.size() << '\n' << '\n';
    }

    void test_insert_and_erase(std::ostream& os)
    {
        os << "test_insert_and_erase START\n";

        Skiplist skiplist;
        std::vector<int> keys{ 1,6,2,7,3,8,4,9,5 };

        for (const auto& x : keys) {
            skiplist.insert(x, x + 10);

            skiplist.print(os);

            skiplist.debug_print(os);
            os << '\n';
        }

        skiplist.debug_print(os);
        os << "size:" << skiplist.size() << '\n';

        if (skiplist.size() != keys.size())
            std::cout << "Invalid Size!!!\n";

        os << "top_level:" << skiplist.get_top_level() << '\n';

        std::sort(keys.begin(), keys.end());

        for (const auto& x : keys) {
            os << '\n';
            os << "delete " << x << '\n';
            skiplist.erase(x);
            skiplist.debug_print(os);
            os << "size:" << skiplist.size() << '\n';
        }
        os << "test_insert_and_erase FINNISHED\n";
    }

    void test_leakage_of_memory(std::ostream& os)
        // insert and erase repeatly into a skip list 
        // if no memory leak there shouldnt be more memory and more memory used
    {
        std::vector<int>keys;

        constexpr int fill_size = 100000;;
        constexpr int repeats = 10;

        for (int i = 0; i < fill_size; ++i)
            keys.push_back(i);

        Skiplist skiplist;

        for (int i = 0; i < repeats; ++i) {

            for (const auto&x : keys)
                skiplist.insert(x, x + 10);

            for (const auto&x : keys)
                skiplist.erase(x);

        }
    }

    void test_find(std::ostream& os)
    {
        os << "test_find START\n";

        Skiplist skiplist;
        std::vector<int> keys{ 1,6,2,7,3,8,4,9,5 };

        for (const auto& x : keys)
            skiplist.insert(x, x + 10);

        skiplist.debug_print(os);

        std::sort(keys.begin(), keys.end());

        for (const auto& x : keys) {
            const int search_value = x + 10;

            os << "searching with key " << x << " for value " << search_value << '\t';

            int* value = skiplist.find(x);

            if (value == nullptr) {
                os << "TEST FAILED\n";
                continue;
            }

            os << "found:" << *value << '\t';

            if (*value == search_value)
                os << "TEST PASSED\n";
            else
                os << "TEST FAILED\n";
        }

        const int invalid_key = keys.back() + 1;

        os << "searching with key " << invalid_key << " not in skiplist" << '\t';

        int* value = skiplist.find(invalid_key);        // insert element which should not be found

        if (value == nullptr) {
            os << "not found" << '\t';
            os << "TEST PASSED\n";
        }
        else {
            os << "found:" << *value << '\t';
            os << "TEST FAILED\n";
        }
        os << "test_find FINNISHED\n";
    }

    void test_copy_constructor(std::ostream& os)
    {
        os << "test_copy_constructor START\n";

        Skiplist a;

        for (int i = 2; i<10; ++i)
            a.insert(i, i + 10);

        info_print(a, "a", os);

        Skiplist b{ a };

        info_print(b, "b", os);

        a.clear();

        info_print(a, "a", os);
        info_print(b, "b", os);

        os << "test_copy_constructor FINISHED\n";
    }

    void test_move_constructor(std::ostream& os)
    {
        os << "test_move_constructor START\n";

        Skiplist a;

        for (int i = 2; i<10; ++i)
            a.insert(i, i + 10);

        info_print(a, "a", os);

        Skiplist b{ std::move(a) };

        info_print(a, "a", os);
        info_print(b, "b", os);


        for (int i = 12; i<15; ++i)
            a.insert(i, i + 20);

        info_print(a, "a", os);
        info_print(b, "b", os);

        os << "test_move_constructor FINISHED\n";
    }


    void test_copy_assignment(std::ostream& os)
    {
        os << "test_copy_assignment START\n";

        Skiplist a;

        for (int i = 2; i<10; ++i)
            a.insert(i, i + 10);

        info_print(a, "a", os);

        Skiplist b;

        b = a;

        info_print(b, "b", os);     // b should be the same like a

        a.clear();                  // clearing a should do nothing with b

        info_print(a, "a", os);
        info_print(b, "b", os);

        os << "test_copy_constructor FINISHED\n";
    }


    void test_move_assignment(std::ostream& os)
    {
        os << "test_move_assignment START\n";

        Skiplist a;

        for (int i = 2; i<10; ++i)      // fill first list
            a.insert(i, i + 10);

        info_print(a, "a", os);

        Skiplist b;

        for (int i = 12; i<15; ++i)     // fill second list with other values
            b.insert(i, i + 10);

        info_print(b, "b", os);

        b = std::move(a);                   

        info_print(a, "a", os);     // a should be empty
        info_print(b, "b", os);     // b should contain a's values, b's values get override

        a.clear();                  // clearing a should do nothing with b

        info_print(a, "a", os);
        info_print(b, "b", os);

        os << "test_move_constructor FINISHED\n";
    }

    void test_performance_of_insert_delete(std::ostream& os,const int repeats, const int count_of_elements)
    {
        os << "test_performance_of_insert_delete START\n";

        std::vector <int> rnd;
        std::map <int, int > mp;

        for (int i = 0; i < repeats; ++i) {

            //fill vector with n unique random elements
            for (int j = 0; j < count_of_elements; ++j) {   
                int in = 0;
                while (true) {
                    in = get_random(1, std::numeric_limits<int>::max());
                    bool twice = false;
                    auto it = mp.find(in);
                    if (it == mp.end())
                        break;
                }
                rnd.push_back(in);
                mp.insert(std::make_pair(in, i));
            }
            os << rnd.size() << "\n";

            mp.clear();

            os << '\n';

            //fill map and skiplist and compar

            // fill skiplist
            auto begin_sk = std::chrono::system_clock::now();

            Skiplist sk;
            for (std::size_t i = 0; i < rnd.size(); ++i)
                sk.insert(rnd[i], i);

            auto end_sk = std::chrono::system_clock::now();
            os << "skiplist filled.    Time:" << std::chrono::duration_cast<std::chrono::milliseconds>(end_sk - begin_sk).count() << "\n";

            // erase skiplist
            auto begin_sk_d = std::chrono::system_clock::now();

            for (std::size_t i = 0; i < rnd.size(); ++i)
                sk.erase(rnd[i]);
            auto end_sk_d = std::chrono::system_clock::now();

            os << "skiplist deleted. Time:" << std::chrono::duration_cast<std::chrono::milliseconds>(end_sk_d - begin_sk_d).count() << "\n";
            os << '\n';

            // fill map
            auto  begin_mp = std::chrono::system_clock::now();

            std::map<int, int> mp;
            for (std::size_t i = 0; i < rnd.size(); ++i)
                mp.insert(std::pair<int, int>(rnd[i], i));

            auto  end_mp = std::chrono::system_clock::now();

            os << "map   filled.       Time:" << std::chrono::duration_cast<std::chrono::milliseconds>(end_mp - begin_mp).count() << "\n";

            // erase map
            auto  begin_mp_d = std::chrono::system_clock::now();
            for (std::size_t i = 0; i < rnd.size(); ++i)
                mp.erase(rnd[i]);
            auto  end_mp_d = std::chrono::system_clock::now();

            os << "map deleted.      Time:" << std::chrono::duration_cast<std::chrono::milliseconds>(end_mp_d - begin_mp_d).count() << "\n";
            os << '\n';
        }
        os << "test_performance_of_insert_delete FINISHED\n";
    }
}

main.cpp

#include <iostream>
#include <vector>
#include <string>
#include <fstream>
#include "skiplist_unit_test.h"

int get_random(int min, int max)
{
    static std::random_device rd;
    static std::mt19937 mt(rd());
    std::uniform_int_distribution<int> distribution(min, max);
    return distribution(mt);
}

int main()
try {
    std::ofstream ofs{ "skiplist_unit_test_results.txt" };

    skiplist::unit_test::test_insert_and_erase(ofs);
    skiplist::unit_test::test_leakage_of_memory(ofs);
    skiplist::unit_test::test_find(ofs);

    skiplist::unit_test::test_copy_constructor(ofs);
    skiplist::unit_test::test_move_constructor(ofs);
    skiplist::unit_test::test_copy_assignment(ofs);
    skiplist::unit_test::test_move_assignment(ofs);

    skiplist::unit_test::test_performance_of_insert_delete(ofs, 3, 100'000);
}
catch (std::runtime_error& e) {
    std::cerr << e.what() << "\n";
    std::cin.get();
}
catch (...) {
    std::cerr << "unknown error\n";
    std::cin.get();
}

During making the changes / reworking the code. The following Questions came up:

Representation of the Skipnode-Pointers

Last time it was suggested to replace Vector with sth "faster" for representing the collection of pointers in the nodes. I just have no Idea what could be used.

Performance

Probaly related to the vector question is the performance Issue. If i run the test were i insert and delete compared to std::map the skiplist is still as slow as before. To give you some values:

100000

skiplist filled.Time:2478
skiplist deleted.Time : 2671

map   filled.Time : 800
map deleted.Time : 1676

200000

skiplist filled.Time : 5390
skiplist deleted.Time : 5411

map   filled.Time : 1650
map deleted.Time : 3408

300000

skiplist filled.Time : 7774
skiplist deleted.Time : 7948

map   filled.Time : 2380
map deleted.Time : 4970

So the skiplist is still 3 times slower than map. I get roughly the same results like with the mikromanagement in the vector i did in the last question. So there must be something which really eats alot of performance

EDIT: It was commented that map is superior to skiplist with insert / delete. So which container would be better to use for a compare. Is there a common Skiplist implementation in c++ to use?

Implementation of Copy Assignment

Currently the Copy constructor is implemented like the copy assignment. The code is repeditive. Is it a good idea in the move assignment to take old nodes if present and refill them with the new key / values?

Representation of the Headnode

The Head Element is now a Basenode for the Skipnodes. This is feels kinda ugly like a dirty hack to me. I even have to use at some places in the code statci_cast to cast to the key / values. I tryed to live without head but then the algorithms couldnt be implemented. Any suggestions are very welcome.

Unit Tests

I added the Unit Tests. Im not very expirience in writing Unit Tests. Currently each function tests a aspect of the skiplist and gives some report. Is this a good approach.

Test for leaking Memory

In the Unit Tests i tryed to test for leaking memory. Currently i allocate several times memory and deallocate it. During the run i look if the used memory increases manually in the debugger. Is this a good approach? I assume not.

Random Generator

Last time someone suggested to move Random Generator completely out of the class, and to put it in a separate class. I didn't understand how. Is the current implementation inside the class ok?

General

Beside these questions who burn me under the tip feel free to make any suggestions for improvements.

Answer 1

Performance

std::vector inside Basenode kills this implementation's performance.

Why that?

The contents (std::vector::data()) are stored outside of Basenode, somewhere else on the heap. This causes 100% more pointer indirection, which in turn likely means 100% more cache misses and thus 100% more trips to main memory. And main memory is slow.

How can we fix this?

We would need something like an "inplace" std::vector. std::array comes close, but we don't know the size at compile time.

But since we know that all the Skipnodes (and thus Basenodes) will be allocated dynamically, we can manually specify their size using malloc (or similar).

Example:

struct Skipnode {
    int key;
    int value;
    size_t level;
    Skipnode* next[1]; // <--
};

Skipnode* allocate_node(int key, int value, size_t level) {
    auto node = std::aligned_alloc(alignof(Skipnode), sizeof(Skipnode) + (level - 1) * sizeof(Skipnode*));

    new(node) Skipnode{key, value, level, nullptr};

    return reinterpret_cast<Skipnode*>(node);
}

void free_node(Skipnode* node) {
    node->~Skipnode();

    std::free(node);
}

What is the significance of Skipnode* next[1];?

Since we artificially increased the size of the Skipnode instance by (level - 1) * sizeof(Skipnode*) to store the links to the next Skipnodes, we want to be able to address them.

We could simply write Skipnode* next; and use some manual pointer arithmetic to get the \$n^{th}\$ layer's next pointer like this: auto nth_level_next = *((&node->next) + n); But this is hardly readable.

However, *((&node->next) + n) is basically the same as (&node->next)[n] (as a[b] basically translates to *(a + b)). And this interpretation says "give me the \$n^{th}\$ array element of the array starting at &node->next", and we can make that more explicit by actually starting a 1-element array there. (The name of a C-style inplace array is basically just a pointer to that address already.)

We know next will always at least contain 1 link, so this is well defined by the C++ standard. If this wasn't the case, we could still make it work by either...

• using non-standard compiler extensions: Simply add Skipnode* next[0]; and the compiler will do the rest (though we will lose portability for compilers who don't support this!)

... or...

• using auto next = reinterpret_cast<Skipnode**>(node + 1); auto nth_level_next = next[n]; and deal with possible alignment problems ourselves.

Since we can now simply write node->next[n] to get the \$n^{th}\$ next link (only if n < node->level, of course), this simplifies the rest of the implementation.

However, this makes it hard to use std::unique_ptr for automatic memory management. This is a trade-off of correctness by design and performance. You could add extra code to explicitly support std::unique_ptr (as lowest level next links), but that would complicate the code without much gain (as you'd have to special case the code for the lowest layer everywhere).

Using the provided benchmark, this nearly halved the runtime of Skiplist on my machine (Win 10, intel Core i7-4770K, using MSVC 2017.3)

Old values (2 000 000 elements each):

skiplist filled.    Time:3580
skiplist deleted. Time:3366

map   filled.       Time:1556
map deleted.      Time:1972

New values (again for 2 000 000 elements):

skiplist filled.  Time:1929
skiplist deleted. Time:1792

map filled.       Time:1568
map deleted.      Time:2006

Further improvements?

• I didn't test custom allocators. I expect that using a good region-based allocator should again improve the performance of the Skiplist somewhat (at least while the whole list manages to fit into L3 cache).

Benchmarking

The performance evaluation is based on a single benchmark, but the actual performance will likely differ for different usage patterns. Use multiple benchmarks covering different aspects to thoroughly evaluate performance!

I added a benchmark that inserts the first 10% of rnd, then for the 90% left removes the "oldest" element for each new element inserted and then removes the remaining 10%. And the difference between the fixed Skiplist and MSVC's implementation of std::map are basically zero.

And there are many other cases left!

Class design

• Skiplist currently doesn't check upon insertion whether a value is already present upon insertion, so it will allow multiple entries with the same key (so its behavior is closer to std::multimap than std::map). Is this intended? And if yes, what is the intended behavior for other operations when encountering multiple entries with the same key?

• Returning an int* from find feels awkward. Why not use std::optional<int> instead?

• Copy assignment and copy constructor logic basically only differ in the amount of cleanup required. Maybe extract the common logic into a helper function?

• In the move constructor all member variables get copy constructed. Maybe use std::move to move construct them instead?

• Same problem in the move assignment operator.

• The copy and move assignment operators leak memory due to not releasing the old Skipnodes.

• erase could be marked noexcept.

• find, size and get_top_level could be marked const noexcept.

• It would be nice to have some kind of iterators over the whole Skiplist (e.g. for use with standard library algorithms).

• An indicator whether the Skiplist is empty might come in handy.

• next_level contains a bug: bit is never reset to 0 when a new val is generated. This means you generate a new val for every call, and the left shift operator takes a too large right hand side value.

  It works on x86 platforms because the processor ignores the too high bits of the right operand when shifting, but that isn't guaranteed everywhere.

  On other platforms, the processor might nearly always generate false for next_level (unless bit just overflowed), which would turn the Skiplist into a singly linked list for most purposes.

  Fixing this didn't gain any perceivable performance on my machine, as the additional time spent on generating some more random numbers upon insertion got dwarfed by the cache misses when navigating the Skiplist.

• Also, val in next_level might not have been generated from the passed eng. I'd suggest either keeping eng as a static scoped variable inside next_level or combining eng, val and bits into a struct or class to be passed in.

• Is there a need for erase to return a bool?

Unit testing

First off, you might want to use a unit testing framework. While doing everything by hand can work, it quickly gets confusing to separate actual tested logic from custom glue code for setting up a test and evaluating the result.

Also, you might want to let the computer verify that the results actually are as expected. The current format still requires a human to evaluate the generated output.

Next, remove all unnecessary clutter! They just distact from the actual intention behind the test.

Some examples:

void test_insertion_adds_value() {
    auto list = Skiplist{}; // setup

    list.insert(1, 2); // action

    auto match = list.find(1); // verification
    assert(match != nullptr, "list should contain the inserted value");
    assert(*match == 2, "the found value should match the inserted one");
}

// Assuming insertion of the same key should overwrite the existing value (see above)
void test_multiple_insertion_of_same_key_overwrites() {
    auto list = Skiplist{};

    list.insert(1, 2);
    list.insert(1, 3);

    assert(list.size() == 1, "existing value should have been overwritten");

    auto match = list.find(1);
    assert(match != nullptr, "value should still be found");
    assert(*match == 3, "only the new value should exist");
}

These test cases are easy to understand, and don't require much human action: If there is no output, they passed. If there is output, something failed. Simple as that!

Testing for memory leaks

This is hard. You could try to use tools like address sanitizer (built into clang) or valgrind, but they aren't guaranteed to catch everything (and might slow things down significantly).

If you choose to allow custom allocators for Skiplist, one could pass a facade over an actual allocator which verifies that every allocated piece of memory through this allocator got properly released (and then only once). This would catch memory leaks whereever this special allocator gets used. However, this also doesn't cover everything, as allocators cannot be used everywhere.

In the end, it's preferable to use interfaces that are correct by design, e.g. by using std::unique_ptr and std::shared_ptr, as those are trusted (and already thoroughly tested) to properly clean up used memory.

Answer 2

✘ Your move-assignment operator is not moving, but doing the same copy as the regular assignment.

---

The various constructors that have a few initializers but no body can go inline in the class definition.

---

BTW, destructors are noexcept by default.

---

Don’t make explicit tests against nullptr. In general (for pointers and smart pointers) use the contextual conversion to bool to indicate “OK to use”.

---

Why isn’t find a const member?

---

⧺C.149 — no naked new or delete.

You should probably make this a unique_ptr as a drop-in replacement without otherwise changing the architecture.