In this homework, you are going to implement a c++ version skiplist. The skiplist follows the general instrustion from HW2, the C-version template.
Besides, there are some additional requirements:
Consider learning those topics as well as the following topics before you start:
Implement a Skip List in C++. See the header file skiplist.h and skiplist.hpp for further details. You need to add definitions in the skiplist.h, according to the instructions in the comments and implement all functions in skiplist.hpp. Updated.
Compilation of the source code requires no errors or warnings and conformity to the C++ 11 standard. Here is the Makefile we will use for grading.
The whole assignment consists of three classes:
iterator. The later two classes are nested classes of
You are required to implement skiplists with following rules:
#define RAND_HALF (RAND_MAX)/2 node_level = 0; while (node_level < s->height_limit - 1 && rand() < RAND_HALF) ++node_level;
key = NULL and value = NULL. The height of the dummy header always equals the height_limit for the list.
deleteIntfunctions are used for allocating memory for int and copying its value.
Template Programming is used throughout the whole assignment, for generic programming. The Key, Value and Compare functions are all in generic type.
find function of skiplist will return an iterator to the found element. For the iterator, you are required to implement 6 different operators:
Besides, you are required to implement the const_iterator as the const version of iterator.
find() on const skiplist that should return
const_iterator, which observes the const-correctness for an iterator of a const list.
We require that you will have one line with comments for every four non-blank lines. Comments have to be meaningful and in English.
No memory leaks are allowed. Memory leaks will be automatically detected and manually screened and will result in a decrease in your score after the deadline.
You should submit a compressed file named as
hw7.tar to autolab.
The directory tree of your submission should look like the following :
├── skiplist.h └── skiplist.hpp
Note: your submission should NOT contain
Note: We will test your program using the functions declared in the header file provided as well as some other functions defined by us. The output of the individual test cases will NOT be given in auto-grader and any attempt at retrieving the test cases or the program outputs will be seen as plagiarism.
The test environment on autolab is Ubuntu 16.04 with gcc 5.xLast modified: