Generic Skip list implementation in C++ Version 3

Question

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

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

I tried to incorporate as much improvements as possible from the code review of the last skip list.

Also the following changes were made:

Templates: I turned the skip list into a generic template to support all kinds of types (not only int). The skip list cpp was removed and everything goes into the .h-file

Adapting to STL: I checked out which functions std::map provides and tried to implement most of them. I tried to provide similar Interfaces so STL algorithms can work.

Unit Tests: I tried to clean up the tests and make most of them run automatically.

skip_list.h

#ifndef SKIP_LIST_GUARD_170720181942
#define SKIP_LIST_GUARD_170720181942

#include <map>          // std::pair
#include <random>       // generation of the levels
#include <vector>       // for head implementation

namespace skip_list {

    template<typename Key,typename T>
    class Skip_list {
    private:
        struct Skip_node;                                                       // forward declaration because iterator class needs to know about the node
        std::vector<Skip_node*> head = std::vector<Skip_node*>(1, nullptr);     // element before first element containg pointers to all the first elements of each level
    public:
        using key_type = Key;
        using mapped_type = T;

        using value_type = std::pair<const key_type, mapped_type>;
        using size_type = std::size_t;

        template<typename IT, bool is_const>
        class iterator_base {
        public:
            using node_type = typename std::conditional<is_const, Skip_node const, Skip_node>::type;
            using value_type = typename std::conditional<is_const, IT const, IT>::type;

            iterator_base()
                : curr{ nullptr }
            {
            };

            explicit iterator_base(node_type* pos)
                : curr{ pos }
            {
            };

            iterator_base& operator=(const iterator_base& other)        // copy assignment
            {
                curr = other.curr;
                return *this;
            }

            // the order is determinde by the key so compare by it
            bool operator==(const iterator_base& b) const { return curr == b.curr; }
            bool operator!=(const iterator_base& b) const { return curr != b.curr; }

            bool operator>(const iterator_base& b) const {
                ////assume nullptr is the biggest element
                if (curr != nullptr && b.curr != nullptr)
                    return curr->value.first > b.curr->value.first;
                else if (curr == nullptr && b.curr != nullptr)
                    return true;
                else    // (curr != nullptr && b == nullptr)
                    return false;
            }

            bool operator<(const iterator_base& b) const 
            {
                return (!(curr < b.curr) && (curr != b.curr));
            }

            bool operator>=(const iterator_base& b) const 
            {
                return ((curr == b.curr) || (b.curr > curr));
            }

            bool operator<=(const iterator_base& b) const 
            {
                return ((curr == b.curr) || (b.curr < curr));
            }

            iterator_base& operator++()
            // if next element is empty dont increase more
            {
                if (curr == nullptr)
                    return *this;

                curr = curr->next[0];
                return *this;
            }

            iterator_base& operator+=(const int offset)
            {
                if (offset <= 0) return *this;

                for (int i = 0; i < offset; ++i)
                    ++*this;

                return *this;
            }

            iterator_base operator+(const int offset)
            {
                iterator_base it = *this;
                it += offset;
                return it;
            }

            value_type& operator*() { return curr->value; }
            value_type* operator->() { return &curr->value; }

        private:
            node_type* curr;

            friend class Skip_list;     // to access curr in skiplist functions
        };

        using iterator = iterator_base<value_type,false>;
        using const_iterator = iterator_base<value_type const,true>;

        Skip_list() = default;                  // constructor

        ~Skip_list() noexcept                   // destructor
        {
            free_all_nodes(head[0]);
        }

        Skip_list(const Skip_list& other)               // copy constructor
        {
            try {
                copy_nodes(other);
            }
            catch (...) {                   // if copy constructor fails, clean up mess and re-throw
                free_all_nodes(head[0]);
                throw;
            }
        }

        Skip_list& operator=(const Skip_list& other)        // copy assignment
        {
            auto backup = std::move(head);  // keep backup to provide better exception guarantee

            try {
                copy_nodes(other);
            }
            catch (...) {
                free_all_nodes(head[0]);
                head = std::move(backup);
                throw;
            }

            free_all_nodes(backup[0]);

            return *this;
        }

        Skip_list(Skip_list&& other) noexcept                       // move constructor
            :head{ std::move(other.head) }
        {
            other.head.assign(1, nullptr);
        }

        Skip_list& operator=(Skip_list&& other) noexcept            // move assignment
        {
            if (this != &other) {
                free_all_nodes(head[0]);
                head = std::move(other.head);
                other.head.assign(1, nullptr);
            }

            return *this;
        }

        // ------------Iterators
        iterator begin() noexcept 
        {
            return iterator{ head[0] };
        }

        iterator end() noexcept
        {
            return iterator{ nullptr };
        }

        const_iterator begin() const noexcept
        {
            return const_iterator{ head[0] };
        }

        const_iterator end() const noexcept
        {
            return const_iterator{ nullptr };
        }

        const_iterator cbegin() const noexcept
        {
            return begin();
        }

        const_iterator cend() const noexcept
        {
            return end();
        }

        // ------------capacity
        bool empty() const noexcept
        {
            return (head[0] == nullptr);
        }

        size_type size() const noexcept         // return count of nodes
        {
            Skip_list<Key, T>::size_type counter = Skip_list<Key, T>::size_type{};

            for (auto index = head[0]; index != nullptr; index = index->next[0], ++counter);

            return counter;
        }

        size_type max_size() const noexcept
        {
            return size_type{ static_cast<size_type>(-1) };
        }

        // ------------element access
        mapped_type& operator[] (const key_type& key)
        {
            return find(key)->second;
        }
        mapped_type& operator[] (key_type&& key)
        {
            return find(key)->second;
        }

        // ------------modifiers
        std::pair<iterator, bool> insert(const value_type& value);
        size_type erase(const key_type& key);   // search for an element and erase it from the skip list

        void clear() noexcept               // erase all elements 
        {
            free_all_nodes(head[0]);
            head.assign(1, nullptr);
        }

        // ------------Operations
        iterator find(const key_type& key);
        const_iterator find(const key_type& key) const;

        size_type count(const key_type& key) const
        {
            return find(key) != end() ? 1 : 0;
        }

        size_type top_level() const { return head.size(); }     // maximum height the Skip_list has reached

        void debug_print(std::ostream& os) const;           // show all the levels for debug only. can this be put into skiplist_unit_tests ?
    private:
        size_type generate_level() const;
        static bool next_level() noexcept;

        struct Skip_node{
            value_type value;       // key / T
            size_type levels;
            Skip_node* next[1];
        };

        static Skip_node* allocate_node(value_type value, size_type levels);
        static void free_node(Skip_node* node);

        void copy_nodes(const Skip_list& other);                    
        static void free_all_nodes(Skip_node* head) noexcept;       
    };

    template<typename Key, typename T>
    std::pair<typename Skip_list<Key,T>::iterator, bool> Skip_list<Key,T>::insert(const value_type& value)
        // if key is already present the position of that key is returned and false for no insert
        //
        // if new key inserted or value of given key was replaced return next pos as iterator and indicate change with true
        // otherwise return iterator end() and false
    {
        const auto insert_level = generate_level();     // top level of new node
        const auto insert_node = allocate_node(value, insert_level);
        Skip_list::Skip_node* old_node = nullptr;

        while (head.size() < insert_level) {
            head.push_back(nullptr);
        }

        auto level = head.size();
        auto next = head.data();

        Skip_list::iterator insert_pos;
        bool added = false;

        while (level > 0) {
            const auto index = level - 1;
            auto node = next[index];

            if (node == nullptr || node->value.first > value.first) {   //compare by key

                if (level <= insert_level) {

                    insert_node->next[index] = next[index];
                    next[index] = insert_node;

                    if (!added) {
                        insert_pos = Skip_list::iterator{ next[index] };
                        added = true;
                    }
                }
                --level;
            }
            else if (node->value.first == value.first) {
                // key already present, keep node with more levels
                //  -> no need to insert new node into list if not needed
                //  -> if insert_node->levels > node->levels, we already modified the list
                //     so continuing and removing the other node seems like the easier option
                //     (compared to retracing where links to insert_node have been made)

                if (node->levels >= insert_level) {
                    node->value.second = value.second;
                    free_node(insert_node);

                    return std::make_pair(Skip_list::iterator{ node }, true);
                }

                old_node = node;

                insert_node->next[index] = node->next[index];
                next[index] = insert_node;
                --level;
            }
            else {
                next = node->next;
            }
        }

        if (old_node != nullptr) {
            free_node(old_node);
        }

        return std::make_pair(insert_pos, added);
    }

    template<typename Key, typename T>
    typename Skip_list<Key,T>::size_type Skip_list<Key,T>::erase(const key_type& key)
        // starts search on the highest lvl of the Skip_list
        // if a node with the erase key is found the algorithm 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
        //
        // the return type indicates how many elements are deleted (like std::map)
        // it can become only 0 or 1
    {
        Skip_node* node = nullptr;

        auto level = head.size();
        auto next = head.data();

        while (level > 0) {

            const auto link_index = level - 1;

            if (!next[link_index] || next[link_index]->value.first > key) {
                --level;
            }
            else if (next[link_index]->value.first == key) {
                node = next[link_index];
                next[link_index] = node->next[link_index];
                --level;
            }
            else {
                next = next[link_index]->next;
            }
        }

        while (head.size() > 1 && head.back() == nullptr) head.pop_back();

        if (node) {     // element to erase was found and taken out of list
            free_node(node);
            return 1;
        }
        else {
            return 0;
        }
    }

    template<typename Key, typename T>
    typename Skip_list<Key,T>::const_iterator Skip_list<Key,T>::find(const key_type& key) const
        // first it is iterated horizontal and vertical until the last level is reached
        // on the last level if the keys match the iterator pointing to it is returned
    {
        auto level = head.size();
        auto next = head.data();

        while (level > 0) {
            const auto index = level - 1;

            if (!next[index] || next[index]->value.first > key) {
                --level;
            }
            else if (next[index]->value.first == key) {
                return const_iterator{ next[index] };
            }
            else {
                next = next[index]->next;
            }
        }
        return end();
    }

    template<typename Key, typename T>
    typename Skip_list<Key,T>::iterator Skip_list<Key,T>::find(const key_type& key)
        // same as const_iterator function, is there a way to not have this redundant?
    {
        auto level = head.size();
        auto next = head.data();

        while (level > 0) {
            const auto index = level - 1;

            if (!next[index] || next[index]->value.first > key) {
                --level;
            }
            else if (next[index]->value.first == key) {
                return iterator{ next[index] };
            }
            else {
                next = next[index]->next;
            }
        }
        return end();
    }

    template<typename Key, typename T>
    void Skip_list<Key,T>::debug_print(std::ostream& os) const
        //messy debug routine to print with all available layers
    {
        if (head[0] == nullptr) {
            os << "empty" << '\n';
            return;
        }

        auto level = head.size();
        auto next = head.data();

        os << "lvl: " << level << " ";

        while (level > 0) {

            const auto index = level - 1;

            if (!next[index]) {
                os << '\n';
                --level;

                if (level > 0) {
                    os << "lvl: " << index << " ";
                    next = head.data();     // point back to begining
                }
            }
            else {
                os << next[index]->value.first << '/' << next[index]->value.second << ' ';
                next = next[index]->next;
            }
        }
    }

    template<typename Key, typename T>
    typename Skip_list<Key,T>::size_type Skip_list<Key,T>::generate_level() const
        // generate height of new node
    {
        size_type new_node_level = size_type{};

        do {
            ++new_node_level;
        } while (new_node_level <= head.size() && next_level());

        return new_node_level;
    }

    template<typename Key, typename T>
    bool Skip_list<Key,T>::next_level() noexcept
        // arround 50% chance that next level is reached
    {
        static auto engine = std::mt19937{ std::random_device{}() };
        static auto value = std::mt19937::result_type{ 0 };
        static auto bit = std::mt19937::word_size;

        if (bit >= std::mt19937::word_size) {
            value = engine();
            bit = 0;
        }

        const auto mask = std::mt19937::result_type{ 1 } << (bit++);
        return value & mask;
    }

    template<typename Key, typename T>
    typename Skip_list<Key,T>::Skip_node* Skip_list<Key, T>::allocate_node(value_type value, size_type levels)
    {
        const auto node_size = sizeof(Skip_node) + (levels - 1) * sizeof(Skip_node*);
#ifdef _MSC_VER         // Visual Studio doesnt support  aligned alloc yet ( new in C++ 17)
        const auto node = _aligned_malloc(node_size, alignof(Skip_node));
#else
        const auto node = std::aligned_alloc(alignof(skip_node), node_size);
#endif
        new(node) Skip_node{ value, levels, nullptr };

        return reinterpret_cast<Skip_node*>(node);
    }

    template<typename Key, typename T>
    void Skip_list<Key,T>::free_node(Skip_node* node)
    {
        node->~Skip_node(); // proper destroy potentially dynamicall alocatet types in skip_node

#ifdef _MSC_VER
        _aligned_free(node);
#else
        std::free(node);
#endif
    }

    template<typename Key, typename T>
    void Skip_list<Key,T>::copy_nodes(const Skip_list& other)
        // precondition: head isn't owner of any nodes
    {
        head.assign(other.head.size(), nullptr);

        auto tail = std::vector<Skip_node**>{};

        tail.reserve(head.size());
        std::for_each(std::begin(head), std::end(head), [&](auto&& link) { tail.push_back(&link); });

        for (auto node = other.head[0]; node != nullptr; node = node->next[0]) {
            const auto copy_node = allocate_node(node->value, node->levels);

            for (auto i = 0u; i < copy_node->levels; ++i) {
                *tail[i] = copy_node;
                tail[i] = &copy_node->next[i];
            }
        }

        std::for_each(std::begin(tail), std::end(tail), [](auto link) { *link = nullptr; });
    }

    template<typename Key, typename T>
    void Skip_list<Key,T>::free_all_nodes(Skip_node* head) noexcept
    {
        for (auto index = head; index != nullptr;) {
            const auto temp = index;
            index = index->next[0];
            free_node(temp);
        }
    }
}
#endif

skip_list_unit_test.h

#ifndef SKIPLIST_UNIT_TEST_GUARD_280620182216
#define SKIPLIST_UNIT_TEST_GUARD_280620182216

#include <chrono>
#include <iostream>
#include <map>
#include <string>
#include <vector>

#include "skip_list.h"

namespace skip_list::unit_test {

    int get_random(int min, int max);

    namespace copy_and_assignment {
        void copy_constructor(std::ostream& os);        // OK
        void move_constructor(std::ostream& os);        // OK
        void copy_assignment(std::ostream& os);     // OK
        void move_assignment(std::ostream& os);     // OK

        void run_all(std::ostream& os);
    }

    namespace iterator {
        void iterator(std::ostream& os);                // OK
        void const_iterator(std::ostream& os);          // OK

        void run_all(std::ostream& os);
    }


    namespace capacity {
        void empty(std::ostream& os);                   // OK
        void max_size(std::ostream& os);                // OK

        void run_all(std::ostream& os);
    }

    namespace modifiers {
        void insert_and_erase(std::ostream& os);        // OK
        void insert_same(std::ostream& os);             // OK
        void iterator_find(std::ostream& os);           // OK

        void run_all(std::ostream& os);
    }

    namespace element_access {
        void access_operator(std::ostream& os);     // OK

        void run_all(std::ostream& os);
    }

    namespace misc {
        void performance_of_insert_delete(std::ostream& os, const int repeats, const int count_of_elements);    // OK
        void debug_print(std::ostream& os);         // OK
        void leakage_of_memory(std::ostream& os);
    }
}

#endif

skip_list_unit_test.cpp

#include "skip_list_unit_test.h"

namespace skip_list::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);
}

namespace copy_and_assignment {
    void copy_constructor(std::ostream& os)
    {
        os << "test_copy_constructor START\n";
        Skip_list<int,int> a;

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

        Skip_list b{ a };

        auto it_a = a.begin();
        auto it_b = b.begin();

        bool equal = true;
        for (; it_a != a.end(), it_b != b.end(); ++it_a, ++it_b) {
            if (it_a->first != it_b->first || it_a->second != it_b->second) {
                equal = false;
            }
        }

        if (equal)  os << "Skip_list a == b " << "PASSED\n";
        else        os << "Skip_list a == b " << "FAILED\n";

        a.clear();

        if (a.begin() == a.end() && b.begin() == b.end())   os << "Skip_list a != b " << "FAILED\n";
        else                                                os << "Skip_list a != b " << "PASSED\n";

        os << "test_copy_constructor FINISHED\n\n";
    }

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

        Skip_list<int, int> a;

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

        Skip_list<int,int> a_before{ a };       // make tmp copy to check with b
        Skip_list<int, int> b{ std::move(a) };

        auto it_a_before = a.begin();
        auto it_b = b.begin();

        bool equal = true;
        for (; it_a_before != a_before.end(), it_b != b.end(); ++it_a_before, ++it_b) {

            if (it_a_before != a_before.end() && it_b != b.end()) {

                if (it_a_before->first != it_b->first || it_a_before->second != it_b->second) {
                    equal = false;
                }
            }
        }

        os << "move content of a into b\n";

        if (equal)  os << "Skip_list a(before move) == b " << "PASSED\n";
        else        os << "Skip_list a(before move) == b " << "FAILED\n";

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

        os << "test_move_constructor FINISHED\n\n";
    }

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

        Skip_list<int, int> a;

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

        Skip_list<int, int> b = a;

        auto it_a = a.begin();
        auto it_b = b.begin();

        bool equal = true;
        for (; it_a != a.end(), it_b != b.end(); ++it_a, ++it_b) {
            if (it_a->first != it_b->first || it_a->second != it_b->second) {
                equal = false;
            }
        }

        if (equal)  os << "Skip_list a == b " << "PASSED\n";
        else        os << "Skip_list a == b " << "FAILED\n";

        a.clear();

        if (a.begin() == a.end() && b.begin() == b.end())   os << "Skip_list a != b " << "FAILED\n";
        else                                                os << "Skip_list a != b " << "PASSED\n";

        os << "test_copy_constructor FINISHED\n\n";
    }

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

        Skip_list<int, int> a;

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

        Skip_list<int, int> a_before{ a };      // make tmp copy to check with b
        Skip_list<int, int> b = std::move(a);

        auto it_a_before = a.begin();
        auto it_b = b.begin();

        bool equal = true;
        for (; it_a_before != a_before.end(), it_b != b.end(); ++it_a_before, ++it_b) {

            if (it_a_before != a_before.end() && it_b != b.end()) {

                if (it_a_before->first != it_b->first || it_a_before->second != it_b->second) {
                    equal = false;
                }
            }
        }

        os << "move content of a into b\n";

        if (equal)  os << "Skip_list a(before move) == b " << "PASSED\n";
        else        os << "Skip_list a(before move) == b " << "FAILED\n";

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

        os << "test_move_constructor FINISHED\n\n";
    }

    void run_all(std::ostream& os)
    {
        copy_constructor(os);
        move_constructor(os);
        copy_assignment(os);
        move_assignment(os);
    }
}

namespace iterator {
    void iterator(std::ostream& os)
    {
        os << "test_iterator START\n";

        std::vector<std::pair<int, int>> insert =
        {
            {  1 ,  10  },
            {  2 ,  11  },
            {  3 ,  12  },
            {  4 ,  13  },
            {  5 ,  14  },
            {  6 ,  15  },
        };

        Skip_list<int, int> test;

        for (const auto& x : insert) {
            test.insert(x);
        }

        for (Skip_list<int, int>::iterator it = test.begin(); it != test.end(); ++it) {
            os << (*it).first << '/' << (*it).second << '\n';
        }

        for (const auto& x : test)
            os << x.first << '/' << x.second << '\n';

        auto it1 = test.begin();
        auto it2 = test.end();

        os << "auto it1 = test.begin();\t";
        os << "auto it2 = test.end()\n";

        if (it1 != it2) os << "(it1 != it2) " << "PASSED" << '\n';
        else            os << "(it1 != it2) " << "FAILED" << '\n';

        if (it1 == it1) os << "(it1 == it1) " << "PASSED" << '\n';
        else            os << "(it1 == it1) " << "FAILED" << '\n';

        if (it1 < it2)  os << "(it1 < it2) " << "PASSED" << '\n';
        else            os << "(it1 < it2) " << "FAILED" << '\n';

        if (it2 > it1)  os << "(it2 > it1) " << "PASSED" << '\n';
        else            os << "(it2 > it1) " << "FAILED" << '\n';

        if (it1 <= it2) os << "(it1 <= it2) " << "PASSED" << '\n';
        else            os << "(it1 <= it2) " << "FAILED" << '\n';

        if (it2 >= it2) os << "(it2 >= it2) " << "PASSED" << '\n';
        else            os << "(it2 >= it2) " << "FAILED" << '\n';

        it2 = it1 + 3;
        it1 += 3;

        if (it1->first == 4 && it1->second == 13)   os << "it1 += 3; " << "PASSED" << '\n';
        else                                        os << "it1 += 3; " << "FAILED" << '\n';

        if (it2->first == 4 && it2->second == 13)   os << "it2 = it1 + 3; " << "PASSED" << '\n';
        else                                        os << "it2 = it1 + 3; " << "FAILED" << '\n';

        os << "test_iterator FINISHED\n\n";
    }

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

        std::vector<std::pair<int, int>> insert =
        {
            { std::make_pair( 1 ,  10 ) },
            { std::make_pair( 2 ,  11 ) },
            { std::make_pair( 3 ,  12 ) },
            { std::make_pair( 4 ,  13 ) },
            { std::make_pair( 5 ,  14 ) },
            { std::make_pair( 6 ,  15 ) },
        };

        Skip_list<int, int> test;

        for (const auto& x : insert) {
            test.insert(x);
        }

        for (Skip_list<int, int>::const_iterator it = test.cbegin(); it != test.cend(); ++it) {
            os << (*it).first << '/' << (*it).second << '\n';
        }

        for (const auto& x : test)
            os << x.first << '/' << x.second << '\n';

        auto it1 = test.begin();
        auto it2 = test.end();

        os << "auto it1 = test.begin();\n";
        os << "auto it2 = test.end()\n";

        if (it1 < it2)  os << "(it1 < it2) " << "PASSED" << '\n';
        else            os << "(it1 < it2) " << "FAILED" << '\n';

        if (it1 <= it2) os << "(it1 < it2) " << "PASSED" << '\n';
        else            os << "(it1 < it2) " << "FAILED" << '\n';

        if (it1 <= it1) os << "(it1 <= it1) " << "PASSED" << '\n';
        else            os << "(it1 <= it1) " << "FAILED" << '\n';

        if (it2 > it1)  os << "(it2 > it1) " << "PASSED" << '\n';
        else            os << "(it2 > it1) " << "FAILED" << '\n';

        if (it2 >= it2) os << "(it2 >= it2) " << "PASSED" << '\n';
        else            os << "(it2 >= it2) " << "FAILED" << '\n';

        if (it1 != it2) os << "(it1 != it2) " << "PASSED" << '\n';
        else            os << "(it1 != it2) " << "FAILED" << '\n';

        if (it1 == it1) os << "(it1 == it1) " << "PASSED" << '\n';
        else            os << "(it1 == it1) " << "FAILED" << '\n';

        it2 = it1 + 3;
        it1 += 3;

        if (it1->first == 4 && it1->second == 13)   os << "it1 += 3; " << "PASSED" << '\n';
        else                                        os << "it1 += 3; " << "FAILED" << '\n';

        if (it2->first == 4 && it2->second == 13)   os << "it2 = it1 + 3; " << "PASSED" << '\n';
        else    os << "it2 = it1 + 3; " << "FAILED" << '\n';

        os << "test_const_iterator FINISHED\n\n";
    }

    void run_all(std::ostream& os)
    {
        iterator(os);
        const_iterator(os);
    }
}

namespace capacity {
    void empty(std::ostream& os)
    {
        os << "test_empty START\n";

        Skip_list<int, int> sk;

        if (sk.empty()) os << "empty == true" << " PASSED" << '\n';
        else            os << "empty == true" << " FAILED" << '\n';

        sk.insert({ std::make_pair( 1 ,  10 ) });

        sk.debug_print(os);

        if (!sk.empty()) os << "empty == false" << " PASSED" << '\n';
        else            os << "empty == false" << " FAILED" << '\n';

        os << "test_empty FINISHED\n\n";
    }

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

        Skip_list<int, int> sk;

        os << sk.max_size() << '\n';

        os << "test_max_size FINISHED\n\n";
    }

    void run_all(std::ostream& os)
    {
        empty(os);
        max_size(os);
    }
}

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

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

        for (const auto& x : keys) {
            auto ret = Skip_list.insert(std::make_pair(x ,  x + 10 ));

            os << "insert " << x << " Iterator " << ret.first->first;

            if ((*ret.first).first == x)    os << " PASSED\n"; // key  == iterator == inserted
            else                            os << " FAILED\n";

            os << "insert " << x << " True " << std::boolalpha << ret.second;           // on insert the true flag should be set
            if (ret.second) os << " PASSED\n";
            else            os << " FAILED\n";
        }

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

        for (const auto& x : keys) {
            if (Skip_list.erase(x)) os << "Delete " << x << " PASSED\n";
            else                    os << "Delete " << x << " FAILED\n";
        }
        os << "test_insert_and_erase FINNISHED\n\n";
    }

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

        Skip_list<int, int> sk;

        sk.insert(std::make_pair( 1 ,  5 ));

        if(sk[1] == 5)  os << "sk[1] == 5" << " PASSED\n";
        else            os << "sk[1] == 5" << " FAILED\n";

        if (sk.size() == 1) os << "sk.size() == 1" << " PASSED\n";
        else                os << "sk.size() == 1" << " FAILED\n";

        sk.insert(std::make_pair( 1 ,  10 ));

        if (sk[1] == 10) os << "sk[1] == 10" << " PASSED\n";
        else             os << "sk[1] == 10" << " FAILED\n";

        if(sk.size() == 1)  os << "sk.size() == 1" << " PASSED\n";
        else                os << "sk.size() == 1" << " FAILED\n";

        os << "insert_same FINNISHED\n\n";
    }

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

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

        for (const auto& x : keys)
            sk.insert(std::make_pair(x ,  x + 10 ));

        sk.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';

            Skip_list<int, int>::iterator it = sk.find(x);

            if (it == sk.end()) {
                os << "TEST FAILED\n";
                continue;
            }

            os << "found:" << it->second << '\t';

            if (it->second == 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 Skip_list" << '\t';

        auto it = sk.find(invalid_key);     // insert element which should not be found

        if (it == sk.end()) {
            os << "not found" << '\t';
            os << "TEST PASSED\n";
        }
        else {
            os << "found:" << it->second << '\t';
            os << "TEST FAILED\n";
        }
        os << "test_find FINNISHED\n\n";
    }

    void run_all(std::ostream& os)
    {
        insert_and_erase(os);
        iterator_find(os);
    }
}

namespace element_access {
    void access_operator(std::ostream& os)
    {
        os << "test_access_operator START\n";

        Skip_list<int, int> sk;

        sk.insert(std::make_pair(1, 10));
        sk.insert(std::make_pair(2, 20));
        sk.insert(std::make_pair(3, 30));


        if (sk[2] == 20)    os << "sk[2] == 20" << " PASSED " << '\n';
        else                os << "sk[2] == 20" << " FAILED " << '\n';

        const int key = 2;

        if (sk[key] == 20)  os << "sk[const 2] == 20" << " PASSED " << '\n';
        else                os << "sk[const 2] == 20" << " FAILED " << '\n';

        os << "test_access_operator FINISHED\n\n";
    }

    void run_all(std::ostream& os)
    {
        access_operator(os);
    }
}

namespace misc {

    void 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 Skip_list and compar

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

            Skip_list<int, int> sk;
            for (std::size_t i = 0; i < rnd.size(); ++i)
                sk.insert(std::make_pair( rnd[i] ,  static_cast<Skip_list<int, int>::mapped_type>(i) ));

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

            // erase Skip_list
            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 << "Skip_list 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\n";
    }

    void 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);

        Skip_list<int, int> Skip_list;

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

            for (const auto&x : keys)
                Skip_list.insert(std::make_pair( x ,  x + 10 ));

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

        }
    }

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

        Skip_list<int, int> sk;

        for (int i = 0; i < 10; ++i) {
            sk.insert(std::make_pair(i, i * 2));
        }

        sk.debug_print(os);
        os << "test_debug_print FINISHED\n\n";
    }
}

main.cpp

#include <fstream>

#include "skip_list_unit_test.h"

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

    skip_list::unit_test::copy_and_assignment::run_all(ofs);
    skip_list::unit_test::iterator::run_all(ofs);
    skip_list::unit_test::capacity::run_all(ofs);
    skip_list::unit_test::modifiers::run_all(ofs);
    skip_list::unit_test::element_access::run_all(ofs);

    skip_list::unit_test::misc::debug_print(ofs);
    //skip_list::unit_test::misc::leakage_of_memory(ofs);
    skip_list::unit_test::misc::performance_of_insert_delete(ofs,3, 1'000'000); 
}
catch (std::runtime_error& e) {
    std::cerr << e.what() << "\n";
    std::cin.get();
}
catch (...) {
    std::cerr << "unknown error\n";
    std::cin.get();
}

There are some implementation details which bother me:

struct Skip_node and std::vector<Skip_node*> head are declared as private before public declarations follow because some public functions need to know them before The remaining private functions follow. Can this be simplified (defining the iterator outside of the class?)?

finds definitions only differ in constness. Is it possible to implement them both more efficient, not duplicating most of the code?

I defined short functions directly in the class. Is this a good practice or does it destroy readability in you're opinion?

I wonder if i did everything with the templating the correct way?

Please let me know any improvements suggestions which come in youre mind while checking the code.

Answer 1

skip_list.h

#include <map>          // std::pair
#include <random>       // generation of the levels
#include <vector>       // for head implementation

You're missing quite a few includes for some of the stuff you use in your implementation. While trying to keep the number of includes down is commendable, you have cut it down a bit too far. Your code may "work" on one compiler because their standard library happens to be laid out in a way that everything you need ends up included by these three headers, but that won't be true for all. I'd bet big money that this won't compile on at least a few of the major standard library implementations.

If I take a list of all the std elements in the header:

• vector (<vector>)
• pair/make_pair (<utility>)
• size_t (<cstddef>, <cstdlib> and a bunch of others)
• conditional (<type_traits>)
• move() (<utility>)
• ostream (<ostream>; can't just use <iosfwd> because we need std::ostream's implementation)
• mt19937 (<random>)
• random_device (<random>)
• aligned_alloc() (<cstdlib>)
• free() (<cstdlib>)
• for_each() (<algorithm>)
• begin()/end() (<iterator>)

then the minimal list of headers you'll need is:

#include <algorithm>
#include <cstdlib>
#include <iterator>
#include <ostream>
#include <random>
#include <type_traits>
#include <utility>
#include <vector>

Note that you don't need <map>. Including it just for std::pair is massive overkill.

If you're really concerned about compile times, you can cut out <iterator> by using head.begin() and head.end() rather than std::begin(head) and std::end(head). The begin()/end() free functions are the right thing to use by default, and in generic code. But in this case, you know that head is a vector, and if that changes, a whole hell of a lot more is going to have to change in your code than just the begin/end iterator functions. (And if you do make that change, and the new type of head doesn't have a begin()/end(), it will be a noisy fail - it won't compile - so you'll know to fix it easily.)

Another header possibly worth removing is <algorithm>. Using std::for_each() is absolutely the right thing to do normally. But if you are concerned about compile times, you can replace it easily with a for loop and a comment that it's just doing for_each(). <algorithm> is a particularly heavyweight header - it has tons of template functions, many of which have multiple static-dispatch optimized versions - so it's worth removing if you can manage it. (I wouldn't recommend removing <algorithm> if you were using more complicated algorithms... but for_each() is hard to screw up.)

Note that I'm not saying you should remove <iterator> and <algorithm>... realistically speaking, sooner or later most every non-trivial translation unit is going to need those anyway. I'm just saying that if you're concerned about compile times, you could.

But that's about the limit of what you can safely remove and still be portably compilable.

template<typename IT, bool is_const>
class iterator_base {

It is unwise to use something like IT as an identifier. All caps (or "screaming snake case") is conventionally assumed to be the domain of the preprocessor. (Granted, anyone defining macros with names like IT deserves whatever grief they get.)

You could use It instead. But IT/It is not a very helpful name here. That parameter really represents the iterator's value type. So you could use ValueType.

Just as a suggestion, since you're declaring the const-ness with the value type, you don't really need the is_const parameter. That's really just duplicating information. You could do:

template <typename ValueType>
class iterator_base {
    using value_type = ValueType;
    using node_type = std::conditional_t<std::is_const_v<ValueType>, Skip_node const, Skip_node>;

    // ...

};

using iterator       = iterator_base<value_type>;
using const_iterator = iterator_base<value_type const>;

and then you wouldn't have to worry about what iterator_base<value_type const, false> is.

iterator_base()
    : curr{ nullptr }
{
};

I think you've got a stray semi-colon there (and in the next constructor).

If you'd set curr to nullptr as an aggregate initializer (in other words, define node_type* curr = nullptr; in the class), then you could just use = default; here.

Something you really should consider doing for all the functions in your iterator class is adding noexcept and constexpr whenever possible. The reasoning is that a fairly normal workload for a container is to be filled up with data once, then searched many, many times during the run of the program, then cleared out at the end. Even if the container's elements are constantly being added and removed, it's probably still true that you're going to be iterating way more than anything else you might be doing with the container.

Thus, you want to make your iterators as fast and as flexible as possible. There's no reason either of the constructors can't be both constexpr and noexcept. (They should be in any case, because you use them in noexcept begin()/end() functions in Skip_list.) In fact, pretty much every function in the iterator can be both! (Except operator++ can't be constexpr because it uses vector's operator[], which isn't constexpr... yet!)

explicit iterator_base(node_type* pos)
    : curr{ pos }
{
};

This probably shouldn't be part of the public interface. You should look into making this private, or otherwise accessible only by Skip_list.

iterator_base& operator=(const iterator_base& other)        // copy assignment
{
    curr = other.curr;
    return *this;
}

You don't need this - it's just the default, implicitly-generated implementation. And in fact, defining it breaks stuff. Once you define copy assignment or copy construction or the destructor, you suppress the move ops.

The iterator class doesn't need any of the implicitly generated operations customized except default construction (and even that could be defaulted if you used an in-class initializer for curr). So don't customize any of them.

bool operator>(const iterator_base& b) const {
    ////assume nullptr is the biggest element
    if (curr != nullptr && b.curr != nullptr)
        return curr->value.first > b.curr->value.first;
    else if (curr == nullptr && b.curr != nullptr)
        return true;
    else    // (curr != nullptr && b == nullptr)
        return false;
}

I'm about to dive into a detailed bit about iterators, but before I do, I think the logic in the above function is broken. If I'm reading it right, you are saying that iterators compare greater than if what they point to compares greater than?

In other words, if you have a two-element list with contents { 100, 5 }, and it1 points to the first element (it's what you get from begin()) while it2 points to the second element... then even though (++it1) == it2, you're saying that it1 > it2. So it2 is after it1, but it1 > it2 (because 100 > 5). Am I understanding that correctly?

That logic seems a bit broken to me: an iterator should be greater than another iterator if it is after it... regardless of what the two iterators point to. If you want to compare what the iterators point to, that should be *it1 > *it2.

In any case, I'd say that you shouldn't bother fixing this function... because you shouldn't have it at all. To explain why... well, let's get into iterator categories.

Iterator categories

So you're making an iterator type. Awesome. But there's more to an iterator type than just naming it iterator and returning it from begin() and end().

You need to start by looking at the basic iterator requirements. They are:

1. CopyConstructible
2. CopyAssignable
3. Destructible
4. Swappable
5. std::iterator_traits<It> has member typedefs value_type, difference_type, reference, pointer, and iterator_category
6. Dereferenceable (generally) - that is, *r works
7. Incrementable - that is, ++r works

Your iterator_base type supports 1-3 by default, no problem (the implicitly generated operations all work fine). Since the type is movable, it's swappable, so that covers 4. You've implemented operator* and operator++, so that covers 6 and 7. That leaves 5.

iterator_base has value_type. That just leaves difference_type, reference, pointer, and iterator_category.

difference_type can just be std::ptrdiff_t, unless you have a reason to make it something else. You'll need to include <cstddef> to get it, but that's a trivial header.

pointer and reference can just be value_type* and value_type& respectively. No problems there.

That just leaves iterator_category. This is the one you should give the most thought to.

Every C++ programmer should familiarize themselves with the iterator categories, so let's review. The standard iterator categories are:

• InputIterator/OutputIterator
  • ForwardIterator
    • BidirectionalIterator
      • RandomAccessIterator

So which iterator category is right for Skip_list?

This a design decision you have to make, but you'll usually be constrained by practical considerations. If I have an iterator to some element in the middle of a Skip_list is it practical to go backwards? If no, then you don't have a BidirectionalIterator - at best you have ForwardIterator. If I have an iterator pointing to the start of a skip list, can I copy it, then increment both iterators separately, and have both point to the same element (in other words, if it1 == it2 (and both are valid and not past-the-end), then ++it1 == ++it2)? Seems so. So it sounds like the natural iterator category for Skip_list is ForwardIterator.

Okay, assuming your iterator is a ForwardIterator, what are the requirements? They are (ignoring dereferencing):

1. DefaultConstructible
2. multipass
3. reference must be value_type& (or value_type const&)
4. equality and inequality comparison defined over the whole sequence (but not necessarily between different sequences)
5. it++
6. From InputIterator/OutputIterator:
   1. EqualityComparable
   2. it1 != it2
   3. ++it
   4. From Iterator
      1. (already covered above)

So iterator_base needs:

• default constructor => (you've got this already)
• multipass capable => (you've got this already)
• (in)equality defined over whole sequence => (you've got this already)
• value_type => (you've got this already)
• difference_type => std::ptrdiff_t
• reference => value_type&
• pointer => value_type*
• iterator_category => std::forward_iterator_tag
• operator== => (you've got this already)
• operator!= => (you've got this already)
• operator++ (prefix) => (you've got this already)
• operator++ (postfix) => missing! (but trivial to implement as just auto temp = *this; ++(*this); return temp;)

What's important to note is which operations are NOT there:

• operator>
• operator<
• operator>=
• operator<=
• operator+=
• operator+

Since your iterator is only going to be a forward iterator, defining those operations is just a waste of time. No algorithm is going to use them.

You see, understanding the iterator categories is not just important for knowing which functions your iterator needs... it's also important for understand which functions your iterator doesn't need.

So basically, and I know this sucks, I'm suggesting that you throw out every function in iterator_base except:

• iterator_base()
• iterator_base(node_type*) (though this shouldn't be part of the public interface; up to you whether it's worth hiding or not)
• operator==
• operator!=
• operator++
• operator*
• operator->

and then adding:

• a typedef for difference_type (set to std::ptrdiff_t)
• a typedef for reference (set to value_type&)
• a typedef for pointer (set to value_type*)
• a typedef for iterator_category (set to std::forward_iterator_tag)
• operator++(int)

and all that will make iterator_base a standard-library conforming iterator.

Note that if you think you can implement iterator_base with an operator--, then maybe you could make it a bidirectional iterator. Maybe even random access. But if you can't do those things, don't bother. In particular, the way you've implemented operator+/operator+=, it's really just looping over operator++, which is not the point of operator+/operator+=. I can do that myself with std::next() or std::advance().

Alright, that's enough iterator evangelizing, back to the code....

iterator_base& operator++()
// if next element is empty dont increase more
{
    if (curr == nullptr)
        return *this;

    curr = curr->next[0];
    return *this;
}

That if test bothers me, because you're testing something that should literally never happen, and quietly hiding a critical logic error. The right thing to do here is to either assert, or rely on contracts, or just throw/terminate when it happens. Asserting or using contracts is particularly nice, because once testing is done, that check can go away. And that's important, because, remember, iterators should be fast.

So that's it for iterator_base... now back to Skip_list.

~Skip_list() noexcept                   // destructor
{
    free_all_nodes(head[0]);
}

You don't need to specify that destructors are noexcept; they are by default. It doesn't hurt, though.

Skip_list(const Skip_list& other)               // copy constructor
{
    try {
        copy_nodes(other);
    }
    catch (...) {                   // if copy constructor fails, clean up mess and re-throw
        free_all_nodes(head[0]);
        throw;
    }
}

Skip_list& operator=(const Skip_list& other)        // copy assignment
{
    auto backup = std::move(head);  // keep backup to provide better exception guarantee

    try {
        copy_nodes(other);
    }
    catch (...) {
        free_all_nodes(head[0]);
        head = std::move(backup);
        throw;
    }

    free_all_nodes(backup[0]);

    return *this;
}

All of the above is correct (assuming copy_nodes() works). However, you've got a bit of code duplication going on.

Whenever you're writing a type that manages resources, there are really only two patterns for handling the copy ops:

1. Write the copy constructor, then write copy assignment using the copy-and-swap idiom. This is safer, but less efficient.
2. Write the copy assignment, then write copy construction as default-construct-and-assign. This is more efficient, but dangerous.

Deciding which one to use is fairly easy:

1. If your type can reuse memory AND you can implement reusing that memory safely, use option 2. (For example, std::vector and std::string can reuse existing capacity when copying.)
2. Otherwise, use option 1.

Skip_list can reuse memory. So the big question is... can you do the copy while reusing memory safely?

The way I see it, that depends on two things:

1. The source list is smaller than the destination list (you are copying a smaller list into a bigger one) or the same size. If the source list is bigger, the vectors may need to reallocate for resizing, which could throw.
2. The value_type is nothrow copy assignable (std::is_nothrow_copy_assignable).

So here's your design decision: You can take the easy path and just write a good copy constructor, then use copy-and-swap for your copy assignment. Or you can take the hard path for maximum performance, and write a badass copy assignment operator that falls back to copy-and-swap if the destination list has less capacity or value_type is not nothrow copy assignable, but otherwise does an in-place copy that reuses the existing capacity.

If you take the latter option, your code might look something like this:

Skip_list(Skip_list const& other) :
    Skip_list{}
{
    *this = other;
}

auto operator=(Skip_list const& other) -> Skip_list&
{
    // If the value_type isn't nothrow copy assignable, don't even
    // bother.
    if constexpr (!std::is_nothrow_copy_assignable<value_type>)
    {
        copy_and_swap_with_(other);
    }
    else
    {
        // ??? should either be size() or some way to determine
        // capacity
        if (??? >= other.size())
        {
            copy_in_place_(other, head); // this should never throw
        }
        else
        {
            copy_and_swap_with_(other);
        }
    }

    return *this;
}

static auto copy_and_swap_with_(Skip_list const& other)
{
    auto temp_head = std::vector<Skip_node*>(other.head.size(), nullptr);

    copy_in_place_(other, temp_head);

    // By the time we get here, the dangerous copying is done.
    std::swap(head, temp_head);
}

static auto copy_in_place_(Skip_list const& other, std::vector<Skip_node*>& head)
{
    // An algorithm that tries to reuse any existing vector
    // capacity and allocated nodes as it copies from other.head
    // to head. If other's contents can fully fit in head and its
    // descendants, then there should be no allocations at all.
}

That's complicated stuff! But it could be worth the performance gain if you're bold. Otherwise, the easy option is:

Skip_list(Skip_list const& other)
{
    try
    {
        // You might as well implement copy_nodes() right here,
        // because you won't need it anywhere else.
        copy_nodes(other);
    }
    catch (...)
    {
        free_all_nodes(head[0]);
        throw;
    }
}

auto operator=(Skip_list const& other) -> Skip_list&
{
    using std::swap;

    auto temp = other;
    swap(temp, *this);
    return *this;
}

On to the move ops....

    Skip_list(Skip_list&& other) noexcept                       // move constructor
        :head{ std::move(other.head) }
    {
        other.head.assign(1, nullptr);
    }

    Skip_list& operator=(Skip_list&& other) noexcept            // move assignment
    {
        if (this != &other) {
            free_all_nodes(head[0]);
            head = std::move(other.head);
            other.head.assign(1, nullptr);
        }

        return *this;
    }

The move constructor is fine, but the move assignment operator concerns me.

The problem with it is that freeing all the nodes is an expensive operation - especially if the list is really large. That defeats the whole purpose of move ops. When I move something, I expect it to be as fast as computerly possible. Waiting for a massive list to get freed level by level, node-by-node, with all the attendant locking that a multi-thread-aware free store will require... it's not something I want to sit around waiting for if I'm moving something.

The smart way to implement move ops for most complex types is to first implement swapping:

friend auto swap(Skip_list& a, Skip_list& b) noexcept
{
    using std::swap;
    swap(a.head, b.head);
}

Skip_list(Skip_list&& other) noexcept :
    Skip_list{}
{
    using std::swap;
    swap(*this, other);
}

auto operator=(Skip_list&& other) -> Skip_list& noexcept
{
    using std::swap;
    swap(*this, other);
    return *this;
}

That pattern is pretty universal, and it's almost impossible to beat the efficiency even before optimization. If you look carefully, you'll notice that your existing implementations were really just swapping already, more or less.

size_type size() const noexcept         // return count of nodes
{
    Skip_list<Key, T>::size_type counter = Skip_list<Key, T>::size_type{};

    for (auto index = head[0]; index != nullptr; index = index->next[0], ++counter);

    return counter;
}

Just really technical and nitpicky note: Your size() function is O(n). The standard library generally expects size() to be O(1). I know that it's a bit of a silly requirement, but that's how it is. That's why std::forward_list doesn't have size() (even though it does have resize() and max_size(), go figure).

Technically to be standards-conformant, what you'd have to do is keep a size member to keep track of the size (and maybe while you're at it, a capacity member to keep track of the capacity). But frankly, I wouldn't sweat it.

size_type max_size() const noexcept
{
    return size_type{ static_cast<size_type>(-1) };
}

While getting the max value of an unsigned type this way "works", it's kinda hacky. For clarity you should really do return std::numeric_limits<size_type>::max();.

// ------------element access
mapped_type& operator[] (const key_type& key)
{
    return find(key)->second;
}
mapped_type& operator[] (key_type&& key)
{
    return find(key)->second;
}

Given the stated intention of matching the mapping interface, shouldn't these functions insert the key and a value-initialized value if the find fails?

// ------------modifiers
std::pair<iterator, bool> insert(const value_type& value);
size_type erase(const key_type& key);   // search for an element and erase it from the skip list

I'd say you're missing some very important overloads:

// *very* important for efficient insertions
auto insert(value_type&&) -> std::pair<iterator, bool>;

// *very* important for efficient removals
auto erase(const_iterator) -> iterator;
auto erase(iterator) -> iterator;

and quite a few existing functions can be implemented efficiently using these.

Whew, that takes us to the end of the Skip_list declaration.

On to the externally-defined functions!

template<typename Key, typename T>
std::pair<typename Skip_list<Key,T>::iterator, bool> Skip_list<Key,T>::insert(const value_type& value)

The first concern I have with this function is that it's way too complicated. Surely the logic can be broken up into smaller components. It seems to me that insertion is a matter of first calling lower_bound() (in the std::map interface), then if the returned iterator isn't end() and the its key equals the key of value replacing second... otherwise doing an actual insert before the iterator. Granted I'm simplifying because std::map has bidirectional iterators - you'd need a slightly different interface. But the point is: one function, one task. Right now insert() is doing two tasks: 1) finding the insert position; and 2) doing the insert.

The second concern is that its semantics are... weird. std::map's insert() either inserts a new key/value pair or does nothing. This insert can insert a new key/value pair, do nothing, or update a value, depending on, it looks like, a flip of a coin. If that's intentional, that's fine... but it probably means you have to give up masquerading as a std::map. How do I distinguish between the three cases, anyway? The bool, if true, tells me that the value's been updated... but it doesn't tell me whether the key was already in the list or not (which is what std::map's bool tells me). You may need a different return value - perhaps a custom type that has the iterator and an enumeration that describes what actually happened.

The third concern is that you have some leakage issues. Just take a look at the first few lines:

const auto insert_level = generate_level();     // top level of new node
const auto insert_node = allocate_node(value, insert_level);
Skip_list::Skip_node* old_node = nullptr;

while (head.size() < insert_level) {
    head.push_back(nullptr);
}

allocate_node() allocates the node - looooong before you even know if you need it, by the way - and then you do push_back() on head. push_back() might throw, and if it does, you leak the node.

Even if you fix that issue, there's a larger issue that you allocate this node even though there are paths where it's not needed. The logic of when/if the new node is used is buried within ifs within ifs within loops.

I think the first step of working out a function like this is to figure out exactly which operations can throw. Most of what you're doing in this function is just integer and pointer compares, pointer swapping, and constructing/assigning pairs (of iterator and bool) and iterators, which is all noexcept. The things that might throw are:

• changing the size of the head vector
• allocating a new node
• node->value.first > value.first and node->value.first == value.first
• node->value.second = value.second
• some stuff in generate_level() can also technically throw, but if it does, your whole program is crashing, so it's not really a concern, but we'll consider it anyway

Your goal should be do absolutely nothing to the Skip_list data structure until you're past all that dangerous stuff, so that if any of it throws, the Skip_list itself remains unchanged - this is the strong exception guarantee.

So keeping all that in mind, your plan should be something like this:

1. Generate your insert level. This shouldn't throw (if it does, your program terminates), but even if it does, no harm, because you haven't changed anything yet.
2. Search through the list for where you'll be inserting/replacing the node. If anything throws here, no harm, because you haven't changed anything. After this phase, you should never need to use node->value.first > value.first or node->value.first == value.first again (so you'll probably need a flag saying whether you found the key exactly or not).
3. If you found the key exactly, and its level is higher than your insert level, do node->value.second = value.second, and then return. If the assignment throws, no harm (assuming the value type's operator= implements the strong exception guarantee - if it doesn't, there's nothing you can do about it anyway).
4. Allocate the new node. If this fails, no harm, because you haven't changed anything. Put the new node in a smart pointer (I'll explain how below).
5. Resize your head to the right number of levels. If this fails, it will cause the allocated node to be freed (because you would be using a smart pointer).
6. At this point, you have done every operation that might throw. Now just insert the node... this can't fail.

That gets you the strong exception guarantee, with no leakage.

A few details to mention:

while (head.size() < insert_level) {
    head.push_back(nullptr);
}

Repeated push_back() is something you want to avoid when you can. Vectors have plenty of functions to assist. For example:

if (head.size() < insert_level)
    head.resize(insert_level, nullptr);

Now, here is a major code smell:

const auto insert_node = allocate_node(value, insert_level);

// ...

free_node(insert_node);

Although it's disguised by custom functions, this is basically nothing more than:

const auto insert_node = new Skip_node{value, insert_level, nullptr};

// ...

delete insert_node;

and that's simply unacceptable in modern C++.

The right way to do this is with smart pointers:

const auto insert_node = std::unique_ptr<Skip_node>{new Skip_node{value, insert_level, nullptr}};
// should be make_unique, but I'm making a larger point, so bear with me

// ...

// automatic cleanup

But of course, you can't do that, because this would clean up insert_node with delete insert_node;, and you need it to clean up with free_node(insert_node);. But this is exactly why unique_ptr has a deleter:

// probably should be defined in Skip_list
class Skip_node_deleter
{
public:
    explicit Skip_node_deleter(Skip_list& owner) noexcept :
        _owner{&owner}
    {}

    auto operator(Skip_node* p) const noexcept
    {
        if (p)
            _owner->free_node(p);
    }

private:
    Skip_list* _owner;
};

const auto insert_node = std::unique_ptr<Skip_node, Skip_node_deleter>{
    allocate_node(value, insert_level),
    Skip_node_deleter{*this}
};

// ...

// automatic cleanup

Even better would be if allocate_node() returned std::unique_ptr<Skip_node, Skip_node_deleter>, as it probably should:

auto insert_node = allocate_node(value, insert_level);
// note: Dropped the const. You'll see why shortly.

// ...

// automatic cleanup

Okay, but there are still some complications. Sometimes you don't want to delete the node. Sometimes the node you want to delete is not the one you got from allocate_node() (it's the old node).

No problem:

auto insert_node = allocate_node(value, insert_level);

// Pure insertion case:
insert_node->next[index] = next[index];
next[index] = insert_node.release(); // note the added ".release()"

// Replacing old node case:
auto const old_node = std::unique_ptr<Skip_node, Skip_node_deleter>{node, Skip_node_deleter{*this}}; // store the old node in a unique ptr to be cleaned up
insert_node->next[index] = node->next[index];
next[index] = insert_node.release(); // note the added ".release()"
// OR, for a little less typing (although a little less clarity), you can reuse insert_node:
insert_node->next[index] = node->next[index];
next[index] = insert_node.release(); // note the added ".release()"
insert_node.reset(node); // store the old node in the unique_ptr, so it gets cleaned up

(It may also be worthwhile to cut down on the verbiage with a helper function to_unique_ptr(Skip_node* p, Skip_list& o) that returns unique_ptr<Skip_node, Skip_node_deleter>{p, Skip_node_deleter{o}}. That would make the old_node line above simplify to auto const old_node = to_unique_ptr(node, *this);.)

Basically, I suggest you treat free_node() like delete; anywhere you see it being called (except in the unique pointer's deleter class) is a code smell.

On to erase()!

template<typename Key, typename T>
typename Skip_list<Key,T>::size_type Skip_list<Key,T>::erase(const key_type& key)

Much of the commentary about insert() applies here, too. In this, the danger ops (the ones that might throw) are next[link_index]->value.first > key and next[link_index]->value.first == key, so you don't want to touch anything until you're done with those.

In this function, you continue to iterate through the list after finding the node you want to erase (and removing it). Is there a reason for that? Couldn't you just break after the node is removed?

If there's some reason you have to keep iterating through the list after finding the node, then you can't do the erase until you're done iterating (more specifically, comparing). So you'd have to store the link index you want to remove, and do the actual removal after the iterating (and comparing) is done.

template<typename Key, typename T>
typename Skip_list<Key,T>::const_iterator Skip_list<Key,T>::find(const key_type& key) const
template<typename Key, typename T>
typename Skip_list<Key,T>::iterator Skip_list<Key,T>::find(const key_type& key)

You're concerned about the duplication, and it's a legitimate concern, but it seems to me you have a trivial way out of it. Just have a private const _find() function that returns a pointer, or null. Even in a const Skip_list, while head may be a const vector, it's still a const vector of Skip_node*. Note, not const Skip_node*. From that pointer you can construct an iterator or a const_iterator.

I'll skip debug_print(), because it's just for debugging.

generate_level() and next_level() are both cool.

    template<typename Key, typename T>
    typename Skip_list<Key,T>::Skip_node* Skip_list<Key, T>::allocate_node(value_type value, size_type levels)
    {
        const auto node_size = sizeof(Skip_node) + (levels - 1) * sizeof(Skip_node*);
#ifdef _MSC_VER         // Visual Studio doesnt support  aligned alloc yet ( new in C++ 17)
        const auto node = _aligned_malloc(node_size, alignof(Skip_node));
#else
        const auto node = std::aligned_alloc(alignof(skip_node), node_size);
#endif
        new(node) Skip_node{ value, levels, nullptr };

        return reinterpret_cast<Skip_node*>(node);
    }

You have another potential memory leak here. After the allocation, you call placement new. That might throw, leaking the allocated memory. You should use a smart pointer. More on that in a second.

I'm not really sure there's any call for aligned_alloc() here. If you weren't concerned about supporting older compilers, then meh. But the fact that you need conditional compilation here screams out for help. If you really, really needed aligned_alloc(), then fine, you'd have to grit your teeth and live with it. But... do you? What are you really gaining here? Skip_node already contains a pointer member, and pointers are quite often the maximally-aligned type. When they're not, they're very close to. On my machine, aligned_alloc() might save you 8 bytes, or 0, so an average of 4 bytes per allocation. Personally, I'd say it's just not worth it for the added maintenance hassle of conditional compilation. Might as well just use malloc().

(To really make the point that conditional compilation is a massive headache: I can tell you only tried compiling on MSVC, because didn't you notice the typo?)

You're also missing an opportunity to use std::move() with value.

And I would suggest that this function should return a smart pointer. It makes the intention of the function super clear - there's no ambiguity over who owns the returned pointer, or how it should be freed (no chance of someone using std::free() when they should be using _aligned_free()) - and it makes client code smarter and easier to write safely.

So putting it all together:

template<typename Key, typename T>
auto Skip_list<Key, T>::allocate_node(value_type value, size_type levels)
    // expects levels > 0
{
    const auto node_size = sizeof(Skip_node) + (levels - 1) * sizeof(Skip_node*);

    auto const free = [](auto p) { std::free(p); };
    auto node = std::unique_ptr<std::byte*, decltype(free)>{std::malloc(node_size), free};

    new(node.get()) Skip_node{std::move(value), levels, nullptr};

    return to_unique_ptr(reinterpret_cast<Skip_node*>(node.release()), *this);
}

It could be made even simpler if you used new rather than malloc for the allocation. It would also make it okay to not check for nullptr if the allocation fails (which you currently don't).

class Skip_node_deleter
{
public:
    auto operator(Skip_node* p) const noexcept
    {
        if (p)
        {
            p->~Skip_node();

            auto raw_p = reinterpret_cast<std::byte*>(p);
            delete[] raw_p;
        }
    }
};

template<typename Key, typename T>
auto Skip_list<Key, T>::allocate_node(value_type value, size_type levels) ->
    std::unique_ptr<Skip_node*, Skip_node_deleter>
    // expects levels > 0
{
    const auto node_size = sizeof(Skip_node) + (levels - 1) * sizeof(Skip_node*);

    auto node = std::make_unique<std::byte[]>(node_size);

    new(node.get()) Skip_node{value, levels, nullptr};

    return {reinterpret_cast<Skip_node*>(node.release())};

    // Or better yet, define: using node_ptr = std::unique_ptr<Skip_node*, Skip_node_deleter>;
    // then just do:
    // return node_ptr{reinterpret_cast<Skip_node*>(node.release())};
}

// This function is no longer necessary.
template<typename Key, typename T>
void Skip_list<Key,T>::free_node(Skip_node* node);

Now, the next function is copy_nodes(). At this point I've made many recommendations - about how to do copying, using smart pointers for nodes, and cautions about looking for the throwing functions - that I'd just be repeating here. So I'm just going to point out the trouble spots:

head.assign(other.head.size(), nullptr);

I think working with head directly like this is a mistake. There are a lot of things in this function that could throw, and if they do, they leave the skip list in a weird state.

I think what you should do is either work on a new head vector, then move it into head once the dust settles...

... OR if copying the values and keys is noexcept and this->size() is greater than or equal to other.size(), then trying to do all the copying with no allocations.

This is basically choosing between copy-and-swap and a strategy that reuses capacity. You need at least copy-and-swap; the capacity-reusing strategy can be an optimization when possible.

for (auto node = other.head[0]; node != nullptr; node = node->next[0]) {
    const auto copy_node = allocate_node(node->value, node->levels);

Before this loop, there are a couple of dangerous allocations for the two vectors, but they are not problematic (other than for the fact that you're using head directly, rather than a temporary) - if they fail, *this is untouched.

In the loop you start allocating nodes, and once the first one succeeds, if any further iterations fail, you get leaks.

The way to handle this is with smart pointers. Assuming you modify allocate_node() to return smart pointers, what you could do is allocate a vector for all the nodes you'll need. Something like this:

template<typename Key, typename T>
void Skip_list<Key,T>::copy_nodes(const Skip_list& other)
    // precondition: head isn't owner of any nodes
{
    // ...

    auto nodes = std::vector<node_ptr>{};
    nodes.reserve(other.size());

    for (auto node = other.head[0]; node != nullptr; node = node->next[0]) {
        nodes.push_back(allocate_node(node->value, node->levels));

        for (auto i = 0u; i < copy_node->levels; ++i) {
            *tail[i] = nodes.back().get();
            tail[i] = &nodes.back()->next[i];
        }
    }

    // ...

    // once the dust has settled, there's no need for us to manage
    // the nodes anymore:
    for (auto&& node : nodes)
        node.release();

    // ...
}

And that's it for the review! But before wrapping up, there's one more thing I think I should mention.

Testing

While I commend that you're actually testing your code, I'm a little concerned about how you're doing it. Your testing code is huge, and insanely complex (for testing code). And even worse, to check whether tests passed or not, you have to manually read through a bunch of output.

You really need to adopt a testing framework. They take care of the vast majority of the boilerplate (so you don't need to worry about testing your testing code). And using a test framework is good practice in any case, so it's not like you're wasting your time familiarizing yourself with a test framework.

I'll just give a very, very brief example using the Google Test Framework, because that's one of the more popular options.

The first thing you need to do is get the Google Test Frame work. No problem. Just clone the git repository, then cd into the scripts directory, and run ./fuse_gtest_files.py output. That will produce a directory output, and within that directory is another directory called gtest. You can copy that directory into any project you want to do testing in.

Then all you need to do is create a source file(s) for your tests and add that and gtest/gtest-all.cc to the project sources.

In your case, your test file might look like this:

#include "gtest/gtest.h"

#include "skip_list.h"

// your tests go here

int main(int argc, char* argv[]) {
    ::testing::InitGoogleTest(&argc, argv);
    return RUN_ALL_TESTS();
}

So what exactly would you test? Well, let's start at the top:

template<typename Key,typename T>
class Skip_list {
private:
    struct Skip_node;                                                       // forward declaration because iterator class needs to know about the node
    std::vector<Skip_node*> head = std::vector<Skip_node*>(1, nullptr);     // element before first element containg pointers to all the first elements of each level
public:
    using key_type = Key;
    using mapped_type = T;

    using value_type = std::pair<const key_type, mapped_type>;
    using size_type = std::size_t;

Ignore the private section - you shouldn't test private stuff - so let's start by testing the types. Let's make sure that when we do Skip_list<Foo, Bar>, key_type is Foo, mapped_type is Bar, value_type is std::pair<const Foo, Bar>, and size_type is std::size_t.

Let's start with key_type. How would we test that?

Well, it could be as simple as:

TEST(SkipListTest, KeyTypeIsCorrect)
{
    EXPECT_TRUE((std::is_same_v<typename Skip_list<int, std::string>::key_type, int>));
}

That's it. The same idea goes for the other types:

TEST(SkipListTest, MappedTypeIsCorrect)
{
    EXPECT_TRUE((std::is_same_v<typename Skip_list<int, std::string>::key_type, std::string>));
}

TEST(SkipListTest, ValueTypeIsCorrect)
{
    EXPECT_TRUE((std::is_same_v<typename Skip_list<int, std::string>::key_type, std::pair<int const, std::string>>));
}

TEST(SkipListTest, SizeTypeIsCorrect)
{
    EXPECT_TRUE((std::is_integral_v<typename Skip_list<int, std::string>::size_type>));
    EXPECT_TRUE((std::is_unsigned_v<typename Skip_list<int, std::string>::size_type>));
}

Note that in the last case we don't test specifically for std::size_t. That's because the requirement for size_type in containers is just an unsigned integral type. So that's what we test.

Each test should test one thing, should be as simple as possible, generally with only a single assertion at the end. (If you have multiple assertions, as in the last test above, it's because you're testing multiple aspects of one thing.) The general pattern is "arrange -> act -> assert": set up the scenario, do the action being tested, then check that the effects of the action are correct.

Here's a more involved test:

TEST(SkipListTest, EraseActuallyErases)
{
    // ASSEMBLE the scenario.
    auto list = Skip_list<int, std::string>{};
    list.insert(std::pair<int, std::string>{42, "foo"});

    // Guard assertion (not *really* necessary because you should
    // be testing insert() separately, but a common practice).
    ASSERT_TRUE(list.find(42) != list.end());

    // ACT.
    list.erase(42);

    // ASSERT the effects.
    ASSERT_TRUE(list.find(42) == list.end());
}

Now, this is all fine... but you can do even better using parameterized tests.

Skip_list is a template. The type tests above only test Skip_list<int, string>. But what if you'd accidentally done using key_type = int;. The key type test above would pass! But the key type would still be int even in Skip_list<string, float>.

What you really want to do is try a bunch of different types for K in Skip_list<K, V>, and verify that key_type is always K. Here's how to do that, but, fair warning, Google Test is a bit clunky for this kind of thing.

First, you need to define a testing class that is a template:

template <typename T>
class SkipListTypesTest : public ::testing::Test {};

This is necessary so we can vary the type of T.

Next, we need to declare that this is a typed test:

TYPED_TEST_CASE_P(SkipListTypesTest);

Next, we need to write the tests. For type-parameterized tests you use the TYPED_TEST_P macro rather than TEST. In each test, T is TypeParam.

Now, there's one little complication here, and that's that we don't just want a single type. Skip_list requires two template types. And then on top of that, we'd need the expected result type. How do we fit 3+ types into T?

Simple, with a tuple.

To do the type tests above, we need a tuple with:

1. the given key type
2. the given value type
3. the expected key_type
4. the expected mapped_type
5. the expected value_type

So T, and thus TypeParam, is a 5-tuple.

The key type test becomes:

TYPED_TEST_P(SkipListTypesTest, KeyTypeIsCorrect)
{
    using K = std::tuple_element_t<0, TypeParam>;
    using V = std::tuple_element_t<1, TypeParam>;
    using expected = std::tuple_element_t<2, TypeParam>;

    EXPECT_TRUE((std::is_same_v<typename Skip_list<K, V>::key_type, expected>));
}

And the other type tests are similar.

Unfortunately, we're not done with Google Test yet, because now we have to manually register all the tests:

REGISTER_TYPED_TEST_CASE_P(SkipListTypesTest,
    KeyTypeIsCorrect,
    MappedTypeIsCorrect,
    ValueTypeIsCorrect,
    SizeTypeIsCorrect
);

Don't forget to add any other tests you create there.

And now we have to actually create the test types:

using SkipListTypesTestTypes = ::testing::Types<
    //          K            V           key_type     mapped_type  value_type
    std::tuple<int,         int,         int,         int,         std::pair<int const, int>>,
    std::tuple<std::string, int,         std::string, int,         std::pair<std::string const, int>>,
    std::tuple<int,         std::string, int,         std::string, std::pair<int const, std::string>>
>;

You can add as many more test case data sets there as you please.

And finally Google Test requires us to manually instantiate everything:

INSTANTIATE_TYPED_TEST_CASE_P(TypeTest, SkipListTypesTest, SkipListTypesTestTypes);

And now your tests will run.

Here's what it looks like all put together:

#include "gtest/gtest.h"

#include "skip_list.h"

// Member type tests -----------------------------------------------
template <typename T>
class SkipListTypesTest : public ::testing::Test {};

TYPED_TEST_CASE_P(SkipListTypesTest);

TYPED_TEST_P(SkipListTypesTest, KeyTypeIsCorrect)
{
    using K = std::tuple_element_t<0, TypeParam>;
    using V = std::tuple_element_t<1, TypeParam>;
    using expected = std::tuple_element_t<2, TypeParam>;

    EXPECT_TRUE((std::is_same_v<typename Skip_list<K, V>::key_type, expected>));
}

TYPED_TEST_P(SkipListTypesTest, MappedTypeIsCorrect)
{
    using K = std::tuple_element_t<0, TypeParam>;
    using V = std::tuple_element_t<1, TypeParam>;
    using expected = std::tuple_element_t<3, TypeParam>;

    EXPECT_TRUE((std::is_same_v<typename Skip_list<K, V>::mapped_type, expected>));
}

TYPED_TEST_P(SkipListTypesTest, ValueTypeIsCorrect)
{
    using K = std::tuple_element_t<0, TypeParam>;
    using V = std::tuple_element_t<1, TypeParam>;
    using expected = std::tuple_element_t<4, TypeParam>;

    EXPECT_TRUE((std::is_same_v<typename Skip_list<K, V>::value_type, expected>));
}

TYPED_TEST_P(SkipListTypesTest, SizeTypeIsCorrect)
{
    using K = std::tuple_element_t<0, TypeParam>;
    using V = std::tuple_element_t<1, TypeParam>;

    EXPECT_TRUE((std::is_integral_v<typename Skip_list<K, V>::size_type>));
    EXPECT_TRUE((std::is_unsigned_v<typename Skip_list<K, V>::size_type>));
}

REGISTER_TYPED_TEST_CASE_P(SkipListTypesTest,
    KeyTypeIsCorrect,
    MappedTypeIsCorrect,
    ValueTypeIsCorrect,
    SizeTypeIsCorrect
);

using SkipListTypesTestTypes = ::testing::Types<
    //          K            V           key_type     mapped_type  value_type
    std::tuple<int,         int,         int,         int,         std::pair<int const, int>>,
    std::tuple<std::string, int,         std::string, int,         std::pair<std::string const, int>>,
    std::tuple<int,         std::string, int,         std::string, std::pair<int const, std::string>>
>;

INSTANTIATE_TYPED_TEST_CASE_P(TypeTest, SkipListTypesTest, SkipListTypesTestTypes);

// any other tests you like ----------------------------------------
TEST(SkipListTest, EraseActuallyErases)
{
    auto list = Skip_list<int, std::string>{};
    list.insert(std::pair<int, std::string>{42, "foo"});

    ASSERT_TRUE(list.find(42) != list.end());

    list.erase(42);

    ASSERT_TRUE(list.find(42) == list.end());
}

// Main ------------------------------------------------------------
int main(int argc, char* argv[]) {
    ::testing::InitGoogleTest(&argc, argv);
    return RUN_ALL_TESTS();
}

And so on for all the other tests you'd like to run. Each member of the class should get its own test, and the iterators need to be tested too. You'll end up with a bunch of tiny tests - and some tests will be type-parameterized (like above, where you can run the same test with a bunch of different types), others will be value-parameterized (so you have a single test run with a bunch of different data), but not all need to be.

The one headache you'll have to deal with is that your code is basically all written, and now you're writing the tests after the fact. That's bad. The right way to do it is to write the test first. It will fail, of course... but you want that. When you see it fail, you know for sure the test is actually being tested. Only after you see the test failing do you write the code in your class to make it pass. Then once it passes, you know you're done.

Writing tests after the fact is a pain in the ass, because you have to be careful to make sure the test is actually running. Always write the test first. Found a bug? Write a test case that catches it... then go to fix the bug - the bug is fixed when the bug test case passes.

And that's finally it for the review! Hope this helped!