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] = ©_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?)?
find
s 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.