Homework 7

Computer Architecture I ShanghaiTech University

Skip Lists in C++


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:


General Instructions

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: skiplist, _listnode and iterator. The later two classes are nested classes of skiplist.

SkipList Implementation Details (This part is identical to that of HW2)

You are required to implement skiplists with following rules:

C++ Template

Template Programming is used throughout the whole assignment, for generic programming. The Key, Value and Compare functions are all in generic type.


The 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. begin(), end() and find() on const skiplist that should return const_iterator, which observes the const-correctness for an iterator of a const list.

Const Correctness

We enforce const correctness throughout the whole assignment. Any function / variable that does not required mutable should be defined as const, and any function support operation on an const object should be defined accessible for const object.


We require that you will have one line with comments for every four non-blank lines. Comments have to be meaningful and in English.

Memory safety

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.

Copy Constructor

In order to avoid double free for skiplist nodes, we deleted the copy constructor (for skiplist only). You may cast a non-const skiplist to const skiplist by const_cast operator.


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 main() function


The autolab will go online by the end of this week.

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.

Test Environment

The test environment on autolab is Ubuntu 16.04 with gcc 5.x

Last modified: