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

Go through the chapter and do all Try This exercises that you haven't already done.

Try This Pg 761

Github: 

https://github.com/l-paz91/principles-practice/blob/master/Chapter%2021/Exercise%201/TryThis%20pg761

To see if they were truly logically different, I went into debug mode and then compared the disassembly created.

You can see that Visual Studio produced identical code, however that is in debug mode. In release mode, it was slightly different:

The first implementation is faster and could be more optimised due to the NOP instruction which I believe aligns the loop in "jump chunks" (very brief explanation because I don't fully understand yet) which can help with instruction fetches. Both loops are doing basically the same thing though:

• setting the conditional jump
• comparing the contents of the iterator with 4
• jumping back to the top while the condition is not equal and increasing the iterator

Try This Pg 765

Github: N/A

1. The value could be changed without you knowing, potentially breaking a part of the code.

2. Someone could change the predicate to use a different name value.

3. Someone could try an make the value global to access it in other places; or start using it where they're not supposed to.

I'd hate to see it in any application.

Try This Pg 774

Github: 

https://github.com/l-paz91/principles-practice/blob/master/Chapter%2021/Exercise%201/Try%20This%20pg774

.

Try This Pg 785

Github: 

https://github.com/l-paz91/principles-practice/blob/master/Chapter%2021/Exercise%201/TryThis%20pg784

This one confused me a bit as on pg 783 he puts {"AA"] = "Alcoa Inc."} in the constructor of the map dow_name. This wouldn't compile in VS2019 and gave errors due to the '] ='. 

Also, the code didn't run initially when using inner_product() given on pg784. It asserted with the error "cannot dereference end map/set iterator". Turns out that Bjarne is a sneaky fox. The lines:

double alcoaprice = dowPrice["AAA"];

double bowingPrice = dowPrice["BA"];

ADD to the map if those keys are not found so my dowPrice map became a size of 5 whereas dowWeight was still 3. This caused the dereferencing error on the map iterator. I will not forget ever again that map will default add an element if it doesn't exist.

Try This Pg 787

Github: 

https://github.com/l-paz91/principles-practice/blob/master/Chapter%2021/Exercise%201/TryThis%20pg787

I'm pretty sure I'm running with at least C++17 so this worked. The order was different.

Try This Pg 792

Github: 

https://github.com/l-paz91/principles-practice/blob/master/Chapter%2021/Exercise%201/TryThis%20pg792

I set max_size to INT_MAX and that still caused an error. For this the overflow caused an exception so it was quite bad and I would not be tempted to ship it.

Chapter 21 // Drill 3 - 1, 2, 3, 4, 5, 6, 7, 8, 9, 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 21 // Drill 3.1

Read some floating-point values (at least 16 values) from a file into a vector<doubles> called vd.

Chapter 21 // Drill 3.2

Output vd to cout.

Chapter 21 // Drill 3.3

Make a vector vi of type vector<int> with the same number of elements as vd; copy the elements from vd into vi.

Chapter 21 // Drill 3.4

Output the pairs of (vd[i], vi[i]) to cout, one pair per line.

Chapter 21 // Drill 3.5

Output the sum of the elements of vd.

Chapter 21 // Drill 3.6

Output the difference between the sum of the elements of vd and the sum of the elements of vi.

Chapter 21 // Drill 3.7

There is a standard library algorithm called reverse that takes a sequence (pair of iterators) as arguments; reverse vd, and output vd to cout.

Chapter 21 // Drill 3.8

Compute the mean value of the elements in vd; output it.

Chapter 21 // Drill 3.9

Make a new vector<double> called vd2 and copy all elements of vd with values lower than (less than) the mean into vd2.

Chapter 21 // Drill 3.10

Sort vd, output it again.

Github: https://github.com/l-paz91/principles-practice/tree/master/Chapter%2021/Drill%203

With drill 9 I found out about std::copy_if():
https://en.cppreference.com/w/cpp/algorithm/copy

Chapter 21 // Drill 2 - 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 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 21 // Drill 2.1

Define a map<string, int> called msi.

Chapter 21 // Drill 2.2

Insert ten (name, value) pairs into it, e.g., msi["lecture"]=21.

Chapter 21 // Drill 2.3

Output the (name, value) pairs to cout in some format of your choice.

Chapter 21 // Drill 2.4

Erase the (name, value) pairs from msi.

Chapter 21 // Drill 2.5

Write a function that reads value pairs from cin and places them in msi.

Chapter 21 // Drill 2.6

Read 10 pairs from input and enter them into msi.

Chapter 21 // Drill 2.7

Write the elements of msi to cout.

Chapter 21 // Drill 2.8

Output the sum of the (integer) values in msi.

Chapter 21 // Drill 2.9

Define a map<int, string> called mis.

Chapter 21 // Drill 2.10

Enter the values from msi into mis; that is, if msi has an element ("lecture",21), mis should have an element (21, "lecture").

Chapter 21 // Drill 2.11

Output the elements of mis to cout.

Github: https://github.com/l-paz91/principles-practice/blob/master/Chapter%2021/Drill%202%20-%20All%20drills

For Drill 2.4 I wasn't sure if he meant erase a few or erase all so I went with erase all.

With Drill 2.7 I think he meant create an overload of the output operator for the map as creating a print function has already been done.

Whilst doing 2.9 I decided to make my functions more generic so they could accept maps of almost any type.

Chapter 21 // Drill 1 - 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 21 // Drill 1.8

Repeat the exercise with a list<Item> rather than a vector<Item>.

Github: https://github.com/l-paz91/principles-practice/blob/master/Chapter%2021/Drill%201/Drill%208

I had to do two minimal things to get this work;

1 - Use advance instead of It + num.

2 - Use the sort() provided by the list container instead of just the standard one.

Chapter 21 // Drill 1 - 1, 2, 3, 4, 5, 6, 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 21 // Drill 1.1

Define struct Item { string name; int iid; double value; /* ... */};, make a vector<Item>, vi, and fill it with ten items from a file.

Chapter 21 // Drill 1.2

Sort vi by name.

Chapter 21 // Drill 1.3

Sort vi by iid.

Chapter 21 // Drill 1.4

Sort vi by value; print it in order of decreasing value (i.e., largest value first).

Chapter 21 // Drill 1.5

Insert Item{"horse shoe", 99, 12.34} and Item{"Canon S400", 9988, 499.95}.

Chapter 21 // Drill 1.6

Remove (erase) two Items identified by name from vi.

Chapter 21 // Drill 1.7

Remove (erase) two Items identified by iid from vi.

Github: 

https://github.com/l-paz91/principles-practice/blob/master/Chapter%2021/Drill%201/Drill%201%2C2%2C3%2C4%2C5%2C6%2C7

New things all around in this exercise. I used the code from page 791 to start with and added operator>> to Item so I didn't have to modify it. This worked perfectly and vector happily constructed 10 Items using the data from the text file thanks to the operator overload. The input code is a bit hardcoded however it allows Items to have spaces in the name value as it uses getline().

For the second drill I tried my hand at creating a function object to sort the name. They are very easy to use.

For sorting by value I allowed a bool to passed to the function object which allows it to switch between increasing/decreasing order.

Whilst doing Drill 6 I also found out that std::remove_if will erase a member of a custom object when passed a predicate to find that member; very cool.

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.