Chapter 20 // Exercise 20 - Principles & Practice Using C++

In this exercise I am using Visual Studio 2019 and a modified version of the std_lib_facilities header found here.

Chapter 20 // Exercise 20

Run a small timing experiment to compare the cost of using vector and list. You can find an explanation of how to time a program in section 26.6.1. Generate N random int values in the range [0:N). As each int is generated, insert it into a vector<int> (which grows by one element each time). 

Keep the vector sorted; that is, a value is inserted after every previous value that is less than or equal to the new value and before every previous value that is larger than the new value. Now do the same experiment using a list<int> to hold to the ints. For which N is the list faster than the vector? Try to explain your result. This experiment was first suggested by John Bentley.

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

I really enjoyed this exercise; I love performance related programming (that's why it's my job). There's nothing quite like watching numbers go smaller.

All the results are in seconds.

1,000,000 ints:

Vector<int> { 31.82, 31, 31, 31, 31 }

List<int>{ 10+ minutes, I then gave up and cancelled it because I'm lazy }

100,000 ints:

Vector<int> { 0.816,  0.818, 0.817, 0.816, 0.818 }

List<int> { cancelled at 6+ minutes }

10,000 ints:

Vector<int> { 0.057, 0.054, 0.054, 0.054, 0.054 }

List<int> { 7, 7, 7, 7,  }

1000 ints:

Vector<int> { 0.005, 0.005, 0.005, 0.005, 0.005 }

List<int> { 0.086, 0.085, 0.085, 0.085, 0.085 }

100 ints:

Vector<int> { 0.0007644, 0.000715, 0.0005206, 0.0005139,  0.0000.5122 }

List<int> { 0.001, 0.001, 0.001, 0.001, 0.001 }

For inserting into the sorted vector/list I used this:

https://stackoverflow.com/questions/15843525/how-do-you-insert-the-value-in-a-sorted-vector

For the first experiment I was expecting the list to be slower but not that slow. It got to 3 minutes on the first test and I walked off to go do the hoovering. To be honest I was always expecting the vector to be faster due to the fact that elements in a vector are stored next to each other in memory so you get a nice cache win when iterating through vectors. With a list, the elements are all over the place so it will probably be destroying the cache.

It's even more interesting because the vector has to bump everything along with each insertion and increase it's memory allocation.

I was interested though on how to make the list faster. Especially because he wants to know which N the list is faster? I quickly implemented my own insert and that was surprising. At 1000 elements, the list was faster than the vector by about 0.8 seconds. At 10,000 the vector took 15 seconds and the list 7.8. After that I stopped testing because it got into the minutes for both containers.

So the moral of the story is; don't re-invent the wheel, use std::upper_bounds and a vector.

If you'd like to know more about the cache, please check out this excellent talk from Scott Meyers:

https://www.youtube.com/watch?v=WDIkqP4JbkE&ab_channel=NOKIATechnologyCenterWroc%C5%82aw

And with that I am FINALLY done with Chapter 20. I started it on April 7th and I procrastinated for 5 whole months.

Chapter 20 // Exercise 19 - Principles & Practice Using C++

In this exercise I am using Visual Studio 2019 and a modified version of the std_lib_facilities header found here.

Chapter 20 // Exercise 19

Define a range-checked iterator for list (a bidirectional iterator).

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

For this one I decided to expand on the one I did for vector in the previous exercise. That one was a friend class of std::vector but what if I made it a stand-alone class that can act as random/bidirectional for just about any container?

You give CheckedIterator the parent type (like vector<int> or list<string>) and it deduces the type of the container based on the iterator using std::iterator_traits<It>::reference:

https://en.cppreference.com/w/cpp/iterator/iterator_traits

I left in the random-access methods like operator+= but had to slightly change how I do the range check so it would work for both vectors and lists.

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

In this exercise I am using Visual Studio 2019 and a modified version of the std_lib_facilities header found here.

Chapter 20 // Exercise 18

Define a range-checked iterator for vector (a random-access iterator).

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

I used this page to help me decide what to put in the range-checked iterator:

https://stackoverflow.com/questions/20809103/self-made-iterator-with-range-checking

Then I added a class declaration to vector that Bjarne created in std_lib_facilities so I could indeed give std::vector a ranged-checked iterator. Because CheckedIt is a class inside of std::vector, I gave it a constructor that takes in a pointer to the parent vector; this way the iterator can easily get the size and begin/end iterators from the parent. If the vector shrinks/grows, the range checking won't break as it always checks the parent's size. I also made it so it only deals with std::vector<T>::iterator meaning I could easily implement assignment and boolean checks.

I then forgot that he tagged on (random-access iterator) to the exercise and realised I hadn't implemented the other things a random-access iterator can do. Thanks

https://www.geeksforgeeks.org/random-access-iterators-in-cpp/

Chapter 20 // Exercise 17 - Principles & Practice Using C++

In this exercise I am using Visual Studio 2019 and a modified version of the std_lib_facilities header found here.

Chapter 20 // Exercise 17

Define an ownership_vector that holds pointers to objects like pvector but provides a mechanism for the user to decide which objects are owned by the vector (i.e., which objects are deleted by the destructor). Hint: This exercise is simple if you were awake for Chapter 13.

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

I had to go back and refresh my memory on what Chapter 13 was. It was one of the graphics chapters and I immediately remembered vector_ref. Here Bjarne uses two vectors as member variables. They both hold pointers to objects but one deletes objects when destroyed. Vector_ref is introduced on page 465 in section 13.10. There is also more information in Appendix E on page 1212.

For this I removed some constructors that didn't make sense and when I thought about it, most methods in std::vector didn't really fit having two vectors as members so I deleted them.

Chapter 20 // Exercise 16 - Principles & Practice Using C++

In this exercise I am using Visual Studio 2019 and a modified version of the std_lib_facilities header found here.

Chapter 20 // Exercise 16

Define an ovector that is like a pvector except that [] and * operators return a reference to the object pointed to by an element rather than the pointer.

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

Due to how I'd implemented the PVector this was quite tricky. I ended up discovering std::remove_pointer<Type>::type in the std library which handily removes pointers from pointer types. So this allows the templated type to still only allow pointer types but when accessing via [] it decays the type and allows it to return a reference to the contents of the pointer whilst still being templated.

https://en.cppreference.com/w/cpp/types/remove_pointer

For operator * I just returned *vector[0] as I believe de-reffing a vector decays to the first element?

Chapter 20 // Exercise 15 - Principles & Practice Using C++

In this exercise I am using Visual Studio 2019 and a modified version of the std_lib_facilities header found here.

Chapter 20 // Exercise 15

Define a pvector to be like a vector of pointers except that it contains pointers to objects and its destructor deletes each object.

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

I found the wording on this one really confusing. Like does he mean a vector of pointers to anything (like vector<void*>) or like a vector<int*> where each object is just a standard type. I understand what he's getting us to do though because a vector doesn't call the destructor for a plain pointer. So whereas string will clean itself up when it goes out of scope, a pointer to a string won't call strings destructor when it goes out of scope (because raw pointers don't have destructors) and then a memory leak is created.

At first I tried to inherit from std::vector and add a new destructor but I have no idea what a _Compressed_pair<_Alty, _Scary_val> _MyPair is and just calling delete[] _MyPair wouldn't compile so I gave up as it was completely beyond me. Also I learnt that std::vectors destructor is not virtual so I can't modify it anyway. Google says it's best to not inherit from std::vector unless absolutely necessary.

I ended up creating a class that has a std::vector as a member variable and implementing most std::vector methods with the destructor explicitly calling delete on each pointer element. Using my best friend _CrtDumpMemoryLeaks() at the end of main shows how PVector cleans up after itself and a std::vector leaks memory:

I then added a static_assert to the class to prevent it from compiling if the type given is not a pointer.

Chapter 20 // Exercise 14 - Principles & Practice Using C++

In this exercise I am using Visual Studio 2019 and a modified version of the std_lib_facilities header found here.

Chapter 20 // Exercise 14

Define a singly-linked list, slist, in the style of std::list. Which operations from list could you reasonably eliminate from slist because it doesn't have back pointers?

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

So here is the documentation for std::list:

https://en.cppreference.com/w/cpp/container/list

And here is the documentation for a std::forward_list:

https://en.cppreference.com/w/cpp/container/forward_list

A list is usually implemented as a doubly linked list whereas the forward_list is a singly linked list. As Slist can only go forwards, the back() function can be removed. There also can't be any functions that place elements at the back of the list.

I decided to use the definition given for forward_list and try and implement that (minus the allocator and various constructors). I ended up leaving out merge and remove but added functions like swap(), resize(), clear() and maxSize().

Chapter 20 // Exercise 13 - Principles & Practice Using C++

In this exercise I am using Visual Studio 2019 and a modified version of the std_lib_facilities header found here.

Chapter 20 // Exercise 13

We don't really need a "real" one-past-the-end Link for a list. Modify your solution to the previous exercise to use 0 to represent a pointer to the (non-existent) one-past-the-end Link (list<Elem>::end()); that way, the size of an empty list can be equal to the size of a single pointer.

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

This made getting the back() element a little trickier. I just started at the head until the next link was nullptr then returned the value. Removing Tail made pushFront a little less complicated though.

At first I cheated and added a get() function to the iterator but I decided to remove it and use only what had been given for the iterator.

Chapter 20 // Exercise 12 - Principles & Practice Using C++

In this exercise I am using Visual Studio 2019 and a modified version of the std_lib_facilities header found here.

Chapter 20 // Exercise 12

Complete the definition of list from section 20.4.1-2 and get the high() example to run. Allocate a Link to represent one past the end.

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

This one involves some copying from the book but not all the functions in List need implementing, I'm sure he'll have us do that at some point. When implementing pushFront(), I almost forgot to make the current first's previous pointer point at the new front. It's not needed to make this exercise work but the iterators can go forwards and backwards.

I also initially forgot to clean up memory. It's a good thing Irun _CrtDumpMemoryLeaks() at the end of every program to remind me. For that I just created a destructor in MyList that deletes each link until it reaches nullptr.

I was about to post and realised that I hadn't made a Link that points at one past the end. To implement the Tail, I made it null first, created the Head, then newed up the Tail and made the Head point at the tail. This allows easy access to the last element in the list by just using mTail->mPrev->mValue.

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

In this exercise I am using Visual Studio 2019 and a modified version of the std_lib_facilities header found here.

Chapter 20 // Exercise 11

Given a list<int> as a (by-reference) parameter, make a vector<double> and copy the elements of the list into it. Verify that the copy was complete and correct. Then print the elements sorted in increasing value.

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

This one was pretty simple as std::vector has a handy range constructor (since C++98). Basically you give it an iterator to a start and end position in the container and it will copy over those values into the vector. It's a nice one-liner:

vector<double> doubleVector(list.begin(), list.end());

Chapter 20 // Exercise 10 - Principles & Practice Using C++

In this exercise I am using Visual Studio 2019 and a modified version of the std_lib_facilities header found here.

Chapter 20 // Exercise 10

Define a version of the word-counting program where the user can specify the set of whitespace characters.

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

I guess for this one he meant that the user can supply several characters at once so "a, 1, -, 9" are "whitespace" characters. For this I created a simple function called isCustomWhitespace(char c, string s). This used std::strings find() function to find c in s. I could then just use this like I did in the previous exercise with isspace() and isalpha().

Chapter 20 // Exercise 9 - Principles & Practice Using C++

In this exercise I am using Visual Studio 2019 and a modified version of the std_lib_facilities header found here.

Chapter 20 // Exercise 9

Define a program that counts the number of words in a Document. Provide two versions: one that defines word as " a whitespace-separated sequence of characters" and one that defines word as "a sequence of consecutive alphabetic characters." For example, with the former definition, alpha.numeric and as12b are both single words, whereas with the second definition they are both two words.

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

This table on character handling functions is extremely useful:

http://www.cplusplus.com/reference/cctype/

I didn't know that isspace() will count control characters like \n as spaces. It made this exercise a lot simpler.

For the first one I iterated through every character and if the current character was a space then I increased the word count; but only if the previous character was not a space.

For the seconds one I increased the word count if the current character was not an alphabetic character; but only if the previous character was an alphabetic character.

Chapter 20 // Exercise 8 - Principles & Practice Using C++

In this exercise I am using Visual Studio 2019 and a modified version of the std_lib_facilities header found here.

Chapter 20 // Exercise 8

Define a function that counts the number of characters in a Document.

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

This one was pretty simple. Instead of iterating through every character in the document, I just added up the sizes of the vectors in the list that makes up a document.

Chapter 20 // Exercise 7 - Principles & Practice Using C++

In this exercise I am using Visual Studio 2019 and a modified version of the std_lib_facilities header found here.

Chapter 20 // Exercise 7

Find the lexicographical last string in an unsorted vector<string>.

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

This exercise is a "gotcha". Lexicographical order is basically alphabetical order but to computers, uppercase is alphabetically before lowercase so Zebra would come before zany when it should be after.

Since Bjarne goes on about the std library in this chapter I had a poke round the library to see what functions I could use:

• string::compare() does not compare lexicographically.
• strcmp() does not compare lexicographically.
• std::lexicographical_compare() ironically does not compare lexicographically but there is another version that takes a predicate.

Creating a function to do this though was an exercise in Chapter 18 (exercise 3). I'll need to go back and edit that as I didn't stop to think about uppercase and lowercase characters. Bjarne you devious snake.

So instead I created a simple predicate function that you can pass to lexicographical_compare that returns if tolower(char 1) < tolower(char 2). This solves the problem.

Chapter 20 // Exercise 6 - Principles & Practice Using C++

In this exercise I am using Visual Studio 2019 and a modified version of the std_lib_facilities header found here.

Chapter 20 // Exercise 6

Write a find-and-replace operation for Documents based on section 20.6.2

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

It's been so long since I read this chapter I forgot about the second half and had to re-read it.

Then I did some unreal stuff for a month, forgot again and had to re-read it again...

To say I procrastinated is an understatement. This exercise involves getting the code from section 20.6.2 to run. This means you need to write the match() function on page 740. Once you've done that you're halfway there as you have a way to find a word. 

Match() is trivial. Since we have a string and iterators to the start and end of the document, we just loop through the string checking if the contents of the iterator matches each character, advancing the iterator each time round. If we get to the end of the string without returning false, we've found a match.

So that takes care of "find". To "replace", I got a reference to the vector of characters (the line) from the iterator. Worked out at what index the iterator was at by using this:

https://stackoverflow.com/questions/2152986/what-is-the-most-effective-way-to-get-the-index-of-an-iterator-of-an-stdvector

Then erased the characters from the vector and inserted the new ones.

So that was my first iteration of FindAndReplace(). It's great for finding and replacing individual words and sentences but not sequences of letters that can't be considered words like the example he gives in the chapter (ones containing special characters like secret\nhomestead). This one is a bit trickier. Let's say I have the lines:

"This is a line ending with a secret"

"homestead is a word."

We can return an iterator to point at the start of secret as finding the string "secret\nhomestead" is easy using match(). However, how would the text editor replace this? Remove secret, replace it with the word and remove homestead. Or remove secret and replace homestead with the word. Or even merging the two lines together with the replacement word? 

I decided to go with the last one and merge the lines together; deleting any lines as necessary.

One thing I haven't allowed is the replacement string to insert new lines. So if you want to replace "banana" with "banana\napple" it won't insert a new line. But cout will make it look like a new line has been inserted. I may do that later. 

EDIT 30/06/2023

Whilst doing Chapter 26 - Exercise 7. It asks to create tests for this code. So I got the code off github and found it no longer compiles. I'm guessing they've updated iterator standards over the past few years and it now requires you to have certain features defined. Either way std::find() would no longer work for the iterator class as defined in the book, so I re-wrote the find_text to not use std::find(). You can find that code here:

https://github.com/l-paz91/principles-practice/tree/master/Chapter%2026/Exercise%207

Chapter 20 // Exercise 5 - Principles & Practice Using C++

In this exercise I am using Visual Studio 2019 and a modified version of the std_lib_facilities header found here.

Chapter 20 // Exercise 5

Define an input and output operator (<< and >>) for vector.

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

At first I was confused as to whether he meant std::vector or the vector we created. I decided to go with std::vector. We basically did this in Drill 14 of Chapter 19 by reading in { val, val, val } into vectors.

That seems like an odd way to type data in. So I decided on an input loop that just asks for data until you enter ctrl+z to break the loop. The main problem with this is that I have no idea how to allow reading a string with whitespace but also reading in other types. It kind of seems impossible but I'm not experienced enough to say for sure. At this point, I just ignored whitespace to bypass this problem but input and output operators for any type is begging for trouble.

EDIT 01/06/2021

After some thinking (and some googling) I realised that there is no graceful way to make a stringstream convert to any type. I was thinking of checking if T was of type std::string but comments rightfully said you should be specialising your functions more and knowing the kind of types it will be using. I eventually used this suggestion and created 2 input overloads; one for integers/characters and another for strings.

https://stackoverflow.com/questions/40554964/c-how-to-check-if-variable-is-stdstring-type

I also spent the evening adding google test to my project so I could add some automated unit tests to my project and not have to faff about with input on a console window when testing. You can read about it here:

Chapter 20 // Exercise 4 - Principles & Practice Using C++

In this exercise I am using Visual Studio 2019 and a modified version of the std_lib_facilities header found here.

Chapter 20 // Exercise 4

Find and fix the errors in the Jack-and-Jill example from section 20.3.1 by using STL techniques throughout.

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

I didn't see anything completely serious. High() can return a pointer to garbage if the containers passed in are empty. To combat this getFromJack() and getFromJill() check to see if the file is empty. If it, it returns a nullptr. That way we're not doing any unnecessary memory allocations and we can gracefully handle checks for nullptrs without crashing the program with errors. Having a nullptr is perfectly fine so I didn't want to error if the file was empty. 

I also modified getFromJill() to be able to handle any size to prevent unwanted allocations. getFromJack() is a bit more difficult as array size must be specified at compile time. A way to get round that is to read jack's data into a vector first then create the array from that size but that kind of defeats the point of using an array. I'm going to leave it the way it is for getFromJack() as arrays should be used when you know the size.

EDIT 14/06/2021

I showed this exercise to one of our senior engine programmers who pointed out that there is no handling for if the pointers supplied to high() are the correct way round. He said this could cause a near infinite loop. To be honest it never occurred to me to pass in the pointers the wrong way round, why would someone do that? I guess that's why I'm not a QA tester.

Chapter 20 // Exercise 3 - Principles & Practice Using C++

In this exercise I am using Visual Studio 2019 and a modified version of the std_lib_facilities header found here.

Chapter 20 // Exercise 3

Look at the palindrome examples (section 18.7); redo the Jack-and-Jill example from section 20.1.2 using that variety of techniques.

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

The wording of this confused me as those palindrome examples are about palindromes; i.e., words that are the same backwards and forwards; what has that got to do with reading in doubles?

But I stared at section 18.7.1 and realised at the heart it's just comparing two things which is what high is doing. So I re-did high to compare using the techniques from the string, array and pointer examples.

The "string" one was a bit tricky to adapt as there's really no point in going backwards unless I'm comparing two, then comparing again against the current high.

The array one was simple enough and I could use indexing which is always nice. Also, you don't need to change Jill's data into an array as a vector is basically an array; you just give it the address of the first element and the size.

I didn't do the pointer one because I had already done that in exercise 2.

Chapter 20 // Exercise 2 - Principles & Practice Using C++

In this exercise I am using Visual Studio 2019 and a modified version of the std_lib_facilities header found here.

Chapter 20 // Exercise 2

Get the Jack-and-Jill example from section 20.1.2 to work. Use input from a couple of small files to test it.

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

.

Chapter 20 // Exercise 1 - Principles & Practice Using C++

In this exercise I am using Visual Studio 2019 and a modified version of the std_lib_facilities header found here.

Chapter 20 // Exercise 1

If you haven't already, do all the Try this exercises in the chapter.

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

pg714

The one on p714 is subjective but personally I would just change 

vector<double>* jill_data 

to 

vector<double>& jill_data

incidentally, this is exactly what he does in the next section.

pg715

Here, double* high is a local variable and it is returning a pointer to a local variable. This will cause a dangling pointer as you can't return pointers to locals.  I am so dumb. After spending an evening battling with heap corruption because I thought this function was leaking memory I realised it's returning a pointer to something we already have on the stack and does not need to be newed up. GAH. I have a feeling he wanted us to discover that...

Also, the function only works with doubles and relies on values being contiguous in memory. Therefore containers like array and vector must be used. A list wouldn't work as the pointers can be anywhere in memory.

pg722

A little annoying as I couldn't use any subscripting.

pg724

The only thing I can think of is that high() is a returning a copy of the iterators into pointers? But it's creating a value on the stack due to it being a copy....I honestly don't know for this one. It ran fine when I recreated it.

pg728

push_front on a vector would be very expensive as it then needs to modify the position of everything else in the vector; what if you have a vector of 1000+ items? That's a lot of wasted cycles. A vector does have insert() which allows you to put an element anywhere in the vector and it will re-organise everything after the insertion, so you could use it to "push something to the front" if you wanted.

For the implementation, I'm lazy and rather than go get the vector I created in previous exercises I simply added push_front to the actual std::vector via Bjarne's std_lib_facilities header file and used insert().

pg739

This felt too easy....

pg742 - 1

This one is a bit confusing as I'm not sure if meant to use 1 function to compare all 4 or a separate one for each. Also, should we have passed it in as a string? Eventually I decided on 2 separate functions due to char* not being as flexible as the others.

pg742-2

This one was so annoying.