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.

Chapter 18 // Exercise 10 - 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 10

Look at the "array solution" to the palindrome problem in section 18.7.2. Fix it to deal with long strings by (a) reporting if an input string was too long and (b) allowing an arbitrarily long string. Comment on the complexity of the two versions.

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

In this one, he didn't say we couldn't use the std library, so I used cin.getline() instead of just the normal cin >>. This allows whitespace to be read as getline() only skips new lines (unless you give it a different delimiting character). Getline() will then continue reading up until the max and append a terminating 0, regardless of whether there were any characters to read.

The next problem was checking if the reading stopped because the buffer ran out of characters or there were too many characters. We can use cin.fail() to check if the stream failed to read. The failbit will be set if it reaches the end of the buffer and still hasn't encountered the delimiting character. A message can then be printed and cin needs to be reset for the next iteration.

I'm not sure if we were supposed to do it a different way as this wasn't entirely complex so I can't comment on the complexity of the two versions. 

http://www.cplusplus.com/reference/istream/istream/getline/

Chapter 18 // Exercise 9 - 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 9

Consider the memory layout in section 17.4. Write a program that tells the order in which static storage, the stack, and the free store are laid out in memory. In which direction does the stack grow: upward toward higher addresses or downward toward lower addresses? In an array on the free store, are elements with higher indices allocated at higher or lower addresses?

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

So going off Bjarne's description of static, stack and heap I managed to print some global variables and a bunch of locals/new'd values but I'm unsure what to do with the stack? His description says "...It sets aside some memory to be used when you call functions, and they need space for their arguments and local variables". You can print the address of where the function is but I don't think you can print the size of the function? I had a look around and that generally is something that can't be done.

I also couldn't compare the addresses for different functions unless they're identical but the ones included in the program were in places near each other but didn't trend one specific way.

const char*'s and newed up char arrays always grew downwards but newed up double arrays grew upwards.

I'm not convinced I've done this exercise correctly.

Chapter 18 // Exercise 8 - 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 8

Rewrite all the functions in section 18.7 to use the approach of making a backward copy of the string and then comparing; for example, take "home", generate "emoh", and compare those two strings to see that they are different, so home isn't a palindrome.

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

.

Chapter 18 // Exercise 7 - 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 7

Write versions of the cat_dot()s from the previous exercises to take C-style strings as arguments and return a free-store-allocated C-style string as the result. Do not use standard library functions or types in the implementation. Test these functions with several strings. Be sure to free (using delete) all the memory you allocated from the free store (using new). Compare the effort involved in this exercise with the effort involved for exercises 5 and 6.

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

Creating this cat_dot was fairly straightforward if a little cumbersome. 

Chapter 18 // Exercise 5, 6 - 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 5, 6

5. Write a function, string cat_dot(const string& s1, const string& s2), that concatenates two strings with a dot in between. For example, cat_dot("Niels", "Bohr") will return a string containing Neils.Bohr.

6. Modify cat_dot() from the previous exercise to take a string to be used as the seperator (rather than the dot) as its third argument.

Github: https://github.com/l-paz91/principles-practice/blob/master/Chapter%2018/Exercise%205%2C%206

He did these two chapter 4 style exercises to make the next one tedious as hell. I don't want to implement this with pointers and arrays and no standard library lol.

Chapter 18 // Exercise 4 - 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 4

Consider what happens if you give strdup(), findx(), and strcmp() an argument that is not a C-style string. Try it! First figure out how to get a char* that doesn't point to a zero-terminated array of characters and then use it (never do this in real - non-experimental - code; it can create havoc). 

Try it with free-store allocated and stack-allocated "fake C-style strings." If the results looks reasonable, turn off debug mode. Redesign and re-implement those three functions so that they take another argument giving the maximum number of elements allowed in argument strings. Then test that with correct C-style strings and "bad" strings.

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

My 'fake' c-style string of 'windows' reported a length of 20 and as such printed garbage after printing windows. It also didn't find 'd' in windows; it returned 'ws'. FindX returned a c-style string so strcmp turned out to work but I think that was just a fluke. That was all just in debug mode. When I switched to release it all worked properly. Visual Studio; built by wizards.

Interestingly when I examined the disassembly of the release build, the initial fake string (which was reporting a size of 8) was still being given 20 spaces:

646E6977h is "dniw" or "wind"...I'm not sure where the "ows" has gone but it's being moved into the esp register with an offset of 20. Even stranger is that after the initialisation, VS reports that Windows has 7 elements but the last 3 are garbage.

It then clears the eax register to 0 and continues assigning the rest of characters of the fake string and at esp+24 adds 'w' and 'o'. Then at esp+26 adds 's'.

The disassembly from the debug build is much more straightforward but uses more cycles:

From what I can gather here, it's storing 'w' into chars and then the rest at an offset in the ebp register. 

One day, I hope I'm as smart as the people who build compilers because this is fascinating. But anyway, the exercise still needs completing.

Instead of relying on my custom function arrayLength() to supply the length, I added an argument to strcmp, strdup and findx to take in the length of the array.

Chapter 18 // Exercise 3 - 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 3

Write a function, int strcmp(const char* s1, const char* s2), that compares C-style strings. Let it return a negative number if s1 is lexicographically before s2, zero if s1 equals s2, and a positive number if s1 is lexicographically after s2. Do not use any standard library functions. Do not use subscripting; use the dereference operator * instead.

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

I thought I had this in the bag by just comparing the C-style strings with < and > like you can with strings but I temporarily forgot that this only compares the first character instead. This is a problem if you have words like 'chili' and 'chilly'. So I calculated the shortest length (don't want to be accessing random memory if one of the variables is shorter than the other) and checked to see if each character was either less than the other character or equal to it. If one of them was true, continue to check, if both are false than the entire string is alphabetically after the other. I also used a bool to keep track if the first character was before as the next one may be after and that would return 1 for instances like "bra" and "zebra" as b is before z but r is after e.

Chapter 18 // Exercise 2 - 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 2

Write a function, char* findx(const char* s, const char* x), that finds the first occurrence of the C-style string x in s. Do not use any standard library functions. Do not use subscripting; use the dereference operator * instead.

Github: https://github.com/l-paz91/principles-practice/blob/master/Chapter%2017/Exercise%205

I actually already did this in Chapter 17 Exercise 5, so I'm just going to link that here.

https://lptcp.blogspot.com/2020/09/chapter-17-exercise-5-principles.html

Chapter 18 // Exercise 1 - 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 1

Write a function, char* strdup(const char*), that copies a C-style string into memory it allocates on the free store. Do not use any standard library functions. Do not use subscripting; use the dereference operator * instead.

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

A bit tedious and I used const_cast. This was exactly the same as exercise 4 in Chapter 17 only then we could use the subscript operator.

Chapter 18 // Vector Drills - Principles & Practice Using C++

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

Chapter 18 // Vector Drills

1 - Define a global vector<int> gv; initialise it with ten ints, 1, 2, 4, 8, 16, etc.

2 - Define a function f() taking a vector<int> argument.

3 - In f():

    a. Define a local vector<int> lv with the same number of elements as the argument vector.

    b. Copy the values from gv into lv.

    c. Print out the elements of lv.

    d. Define a local vector<int> lv2; initialise it to be a copy of the argument vector.

    e. Print out the elements of lv2.

4. In main():

    a. Call f() with gv as its argument.

    b. Define a vector<int> vv, and initialise it with the first ten factorial values (1, 2*1, 3*2*1, 4*3*2*1,             etc.).

    c. Call f() with vv as its argument.

Github: https://github.com/l-paz91/principles-practice/blob/master/Chapter%2018/VectorDrills

Oh I love vector. You can just get on with your life.