2
\$\begingroup\$

Skip List Header File

#include <random>
#include <iostream>
#include <algorithm>

struct Node {
    Node(int vv, Node*nn = nullptr) : val{ vv }, next{ nn }{}
    Node() : val{ 0 }, next{ nullptr } {} 
    //Node(const Node &n);      //copy constructor
    //Node& operator=(Node &n); //copy assignment

    ~Node() { 
        std::cout << "node deleted" << std::endl; 
    }
    int val{ 0 };
    int level{ 0 };
    Node* next;

};

class Nodes {
public:

    Nodes(int ss) :sz{ ss }, elem{new Node[ss]} {}
    Nodes() :sz{ 1 }, elem{new Node[1]} {}
    Nodes(const Nodes& n);

    //copy operations not used 
    /*
    Nodes& operator=(const Nodes&n);
    Nodes(Nodes&& n);
    Nodes& operator=(Nodes&& n);
    */

    //subscript operator
    Node& operator[](int i){ return elem[i]; }

    ~Nodes() {
        delete[] elem;
        std::cout << "nodes deleted" << std::endl;
    }
 private:
    int sz;
    Node* elem;

};



class Skip_list {
public:

    // hard coded max height for simplicity
    // creates two Nodes containers for nil and header 
    //links header->nil
    Skip_list():height{20}, header_arr{20}, nil_arr{20} {
        for (int i = 0; i < height; ++i) {
            header_arr[i].level = i;
            header_arr[i].val = INT_MIN;

            nil_arr[i].level = i;
            nil_arr[i].val = INT_MAX;

            header_arr[i].next = &nil_arr[i];
        }
    }

    void print(); // print all values of nodes
    void insert(int val); // add new value to skip list

    // free all memory allocated for nodes between header and nill;
    // header and nil deallocation is handled by Nodes destructor
    ~Skip_list() {
        int count = 0;
        Node* p = &header_arr[0];

        while (p) {
          p=p->next; 
          ++count;
        }
        Node** base=new Node*[count];
        p = &header_arr[0];

        for (int i = 0; i < count; ++i) {
            base[i] = p;
            p = p->next;
        }

        for (int i = 1; i < count-1; ++i) {
           delete[] base[i];
        }
        delete[] base;
        std::cout << "destructor" <<std:: endl;
    }
    void del(int val); // remove item from list and deallocate associated 
memory
    Node* find(int val);

private:
    int height; 
    Nodes header_arr;    
    Nodes nil_arr;     
};


int rand_height(int max); // random number generator;

Skip List cpp File

#include "skip_list.h"

Nodes::Nodes(const Nodes &n) : sz{n.sz}, elem{new Node[n.sz]}{
    for (int i = 0; i < sz; ++i) {
    elem[i] = n.elem[i];
    }
}

// Nodes container copy constructors not necessary for this implementation 
/*
Nodes& Nodes::operator=(const Nodes &n){
    if (sz < n.sz) {
        Node* elem_temp = new Node[n.sz];

        for (int i = 0; i < n.sz; ++i) 
            elem_temp[i] = n.elem[i];

        delete[] elem;
        elem = elem_temp;
        sz = n.sz;
        return *this;
    }
    else{
        for (int i = 0; i < n.sz; ++i) 
            elem[i] = n.elem[i];
        return *this;
    }
}


Nodes::Nodes(Nodes&& n) :sz{ n.sz }, elem{ n.elem } {
    n.sz = 0;
    n.elem = nullptr;
}


Nodes& Nodes::operator=(Nodes&& n) {
    delete[] elem;
    elem = n.elem;
    n.sz = 0;
    n.elem = nullptr;
    return *this;
}
*/

void Skip_list::insert(int val) {
    // create array of nodes with value=val 
    int max_level = height - 1;

    // gets random val between 1 and num elements in header
    int temp_levels = rand_height(height); 

    Node* n_temp=new Node[temp_levels];

    for (int i = 0; i < temp_levels; ++i) {
    n_temp[i].val = val;
    n_temp[i].level = i;
}

    //adding new node/s to Skip_list
    Node* p = &header_arr[max_level];
    Node* p_n = &n_temp[temp_levels - 1];

    for (int i = max_level; i>=0 ;--i) {
        p = &header_arr[i];
        while (p_n->val > p->next->val)
        p = p->next;

        if (p_n->val == p->next->val) {
            std::cout << "value already exsists in table" << std::endl;
            break;
        }

        if (p_n->level == p->level ) {
            p_n->next = p->next;
            p->next = p_n;      
            p_n = --p_n;
        }
    }
}

Node* Skip_list::find(int n) {
    Node* p = &header_arr[height - 1];
    int i = 0;
    for (int i =height-1; i >= 0;--i) {

        p = &header_arr[i];

        while (n > p->next->val) 
            p = p->next;

        if (p->next->val == n) {
            p = p->next;
            p = p - i; //get address of index 0 for array with value n
            return p; 
        }
    }

    return nullptr;

}

void Skip_list::del(int n) {

    Node* p = &header_arr[height - 1];

    for (int i = height - 1; i >= 0; --i) {

        p = &header_arr[i];

        while (n > p->next->val)
            p = p->next;

        if (p->next->val == n) {

            Node* p2 = p->next; // pointer to node w/val n

            //remove array of n from list
            for (int j = 0; j <= i; ++j) {

                // maintain continuity in list
                p->next = p2->next; 

                // decrements vertically in list
                if (j < i) {
                    --p;        
                    --p2;       
                }
            }

            delete[] p2;
            break;
        }
    }
}


void Skip_list::print() {

    Node* p = &header_arr[height-1];

    for (int i = height-1; i >= 0; --i) {
        p = &header_arr[i];

        while (p) {
            std::cout << p->val << ' ';
            p = p->next;
        }
        std::cout << std::endl;
    }
}

int rand_height(int max){
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<int> dis(1, max);
    return dis(rd);
}

Test of Implementation

/* 
Bjarne Stroustrup's "Programming Principles and Practices Using C++"
Exercise 11 of Chapter 18
Implementation of a Skip list
*/

#include "skip_list.h"

void test() {
    Skip_list sl;
    sl.insert(10 );
    sl.insert(12 );
    sl.insert(5 );
    sl.insert(6);
    sl.insert(7);
    sl.insert(8);
    sl.insert(9);
    sl.print();

    Node* n5 = sl.find(5);
    Node* n10 = sl.find(10);
    Node* n12 = sl.find(12);

    std::cout << n5  <<  ' ' << n5->val << std::endl;
    std::cout << n10 << ' ' << n10->val << std::endl;
    std::cout << n12 << ' ' << n12->val << std::endl;
    sl.del(12);

    Node* n12d= sl.find(12);

    if (n12d!=nullptr)
        std::cout << n12d << ' ' << n12d->val << std::endl;
    else
        std::cout << "not found" << std::endl;
}


int main() {

    test();

    char quit;
    std::cout << std::endl;
    std::cout << "enter a char to exit" << std::endl;
    std::cin >> quit;

    return 0;
}

Please point out any errors or implementation details that should be addressed.

\$\endgroup\$

2 Answers 2

4
\$\begingroup\$

Reviewing just the header:

Missing header guards.

Your Skip List Header File needs header guards.

std::cout is not for logging in final code.

At worse, use std::cerr, but ideally use a proper logging library like spdlog, or a log callback. Otherwise, your class cannot be used in any application that actually uses std::cout for its output.

Using std::cout is ok while developing, but once you are done, it has to go.

Your constructors should be explicit

consider the following:

void foo(Nodes const& n);

...

foo(3);

How misleading!

Don't just comment out the copy constructors and = operators

delete them explicitely instead.

Nodes {
  Nodes(Nodes const&) = delete;
};

Be consistent about in-class inlining.

You have very long functions defined in the header, yet you still have a .cpp file. Be consistent, either implement the whole thing in a header, or move any non-trivial function to the .cpp file.

Be consistent about how you default-initialize things.

Are you doing it in the default constructor, or in the member declaration? make up your mind. I prefer the following:

struct Node {
    Node(int vv, Node*nn = nullptr) : val{ vv }, next{ nn } {}
    Node() = default; 

    int val{ 0 };
    int level{ 0 };
    Node* next{ nullptr };
};
\$\endgroup\$
2
  • \$\begingroup\$ I could use some clarification with regards to Your constructors should be explicit . Thank you for your work and thank you in advance for clarifications. \$\endgroup\$
    – seabiscuit
    Apr 18, 2018 at 22:33
  • 1
    \$\begingroup\$ Due to historical reasons, single argument constructors allow for the implicit creation of objects. This is almost always undesirable, so single-arguments should be marked with the explicit keyword unless you really need implicit conversion support. \$\endgroup\$
    – user128454
    Apr 19, 2018 at 2:03
1
\$\begingroup\$

Don’t use naked new/delete. You have a pointer and a sz; why not just use a std::vector? Or in general, use unique_ptr (which works with arrays now) rather than a raw pointer.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.