Readings

The readings for Monday, August 29 are:

1. C++ Templates Tutorial

2. C++ Made Easier: The Rule of Three

3. Resource Acquisition is Initialisation (RAII) Explained

4. Data Structures and Other Objects Using C++:

   • Chapter 2 - 8 (Most of this should be review, so you can mostly skim it)

Alternative

If you do not have the primary textbook, you can use the following free alternative texts instead:

1. Data Structures & Algorithm Analysis

   • Chapter 4

2. Open Data Structures

   • Chapter 2, 3

Questions

Once you have completed the readings, answer the following questions in the reading01/README.md file in your assignments repository:

1. In the context of data structures, why would using a language with templates be advantageous?

2. In C++ Templates Tutorial, the author provides the following class template:

   //stack.h
   #pragma once
   template <class T>
   class Stack
   {
   public:
     Stack(int = 10) ;
     ~Stack() { delete [] stackPtr ; }
     int push(const T&);
     int pop(T&) ;  // pop an element off the stack
     int isEmpty()const { return top == -1 ; }
     int isFull() const { return top == size - 1 ; }
   private:
     int size ;  // Number of elements on Stack
     int top ;
     T* stackPtr ;
   } ;
   

   Unfortunately, this class violates the Rule of Three. Explain what this violation is, why it is problematic, and what you would do to fix it.

3. Suppose I wanted to implement a sequence container by using an dynamic array. What would be the complexity in terms of Big-O for the following operations:

   • Locate an element based on index
   • Insert an element in the front
   • Insert an element in the back

   What is the difference between a vector's size and capacity? How do these properties influence the insert operation?

4. Suppose I wanted to implement a sequence container by using an linked list. What would be the complexity in terms of Big-O for the following operations:

   • Locate an element based on index
   • Insert an element in the front
   • Insert an element in the back

   How does using a singly linked list instead of a doubly linked list effect the complexity of these operations?

Submission

To submit your reading assignment, you must use the development branch workflow:

1. First, create a reading01 development branch in your assignments repository:

   $ cd path/to/repo                 # Go to assignments repository
   $ git checkout master             # Make sure we start with master branch
   $ git checkout -b reading01       # Create and checkout new branch "reading01"
   

2. Once you are in the new reading01 branch, perform your work as normal:

   $ $EDITOR reading01/README.md     # Edit the `reading01/README.md` file
   $ git add reading01/README.md     # Queue up README for commit
   $ git commit                      # Commit change
   

3. When you are satisfied with your work, push the new branch to your GitLab assignments repository:

   $ git push -u origin reading01    # Send branch to GitLab
   

4. Once this is done, you will need to perform a Merge Request from this new branch to the master on your assignments repository (not the class one!).

   When you pushed your branch, git should provide you will a URL to the page to make a Merge Request. It will look something like this:

   $ git push -u origin reading01    # Send branch to GitLab
   Counting objects: 4, done.
   Delta compression using up to 4 threads.
   Compressing objects: 100% (3/3), done.
   Writing objects: 100% (4/4), 1.36 KiB | 0 bytes/s, done.
   Total 4 (delta 1), reused 0 (delta 0)
   remote:
   remote: Create merge request for reading01:
   remote:   https://gitlab.com/pbui/assignments/merge_requests/new?merge_request%5Bsource_branch%5D=reading01
   remote:
   To gitlab.com:pbui/assignments.git
   * [new branch]      reading01 -> reading01
   Branch reading01 set up to track remote branch reading01 from origin
   

   You can click on that link to go to the Merge Request page. Otherwise, go to the assignments repository project and create a Merge Request by clicking on the button at the top of the page:

   

   Next, you need to select the master branch of your own assignments repository by first clicking on the Change branches link:

   

   Then choose your own assignments repository as the target:

   

Once this is done, you will need to assign the Merge Request to the appropriate TA from the Reading 01 - TA Assignment:

You may write a message at the top of the Merge Request if you wish.

After this, the assigned TA will be notified of your Merge Request. You can continue to commit after you make the Merge Request until the deadline.