Chapter 18 // Exercise 11 - Principles & Practice Using C++

In this exercise I am using Visual Studio 2017 and the std_lib_facilities header provided by Stroustrup.

Chapter 18 // Exercise 11

Look up (e.g., on the web) skip list and implement that kind of list. This is not an easy exercise.

Github: https://github.com/l-paz91/principles-practice/tree/master/Chapter%2018/Exercise%2011

I sighed...I sighed when I googled "skip list". Why Bjarne? This exercise took me a good 2 weeks as I was determined to solve it using only pointers and arrays. You can use a vector to make it a bit simpler but I noticed that the vector implementation I did bumped the memory usage of the program way up; I was a little shocked at the overhead vector brings.

To solve this I used a paper written by William Pugh (the inventor of Skip lists) found here:

https://www.epaperpress.com/sortsearch/download/skiplist.pdf

It contains pseudo code for each function but it's written in Pascal. I had fun trying to decode that....not. Pascal for the most part is relatively similar to C++; the main issue was working out when I had to de-reference or new something up. At one point I was convinced his code didn't work but of course it was just me that wasn't working.

One of the most annoying parts of this task though was trying to debug it. As all my arrays had to be dynamically allocated at runtime, that meant I could only access them via pointers. Pointers only point at the first value of the array so the watch window isn't that helpful. That is unless you know the tricks of the watch window!

A skip list is pretty much made up of Nodes, a node contains a value and an array of pointers to other nodes ahead of it. mHead is the start of the Skip list and we can see here that it's array mNext is only showing us mNext[0]. How do you find out what mNext[1] is at this point?

Well, just right click on the value in Local values, add a watch to it (the right click menu didn't show up in the recording), then add the subscript operators on the end and access whichever part of the array you want!

That's great for specific parts of the array. But what if you want to glance quickly at the entire array? Well if the array has been dynamically allocated, in the watch window, click on a new line and type in:

nameOfPointer, numberOfElements

hit enter and Visual Studio will give you a normal looking array list!

(All those values are supposed to be null by the way).

Now, this only works with ints (I'm not doing templated types just yet although I can see Bjarne making that an exercise in later chapters). And I'm sure there is an error somewhere but for the most part it "works on my machine" lol. I've already spent a bit too much time on this one exercise.