Welcome to Week 2!

Learning Objectives

By the end of today's class, you should know...

  • How to handle preconditions when writing your access functions for the List 
  • What is an iterator and how is it used as part of the linked list class
  • The difference between a deep and shallow copy
  • How to write a copy constructor


Announcements
  • Quiz 1 on Wednesday
    • Answer 6 questions in 10 minutes
    • Will need to write simple linked list function(s) and answer conceptual questions from content of Lesson 1-3
    • From video "Things Top Performing Students Know...", what is the best way to study for this quiz?
  • Please check in with me at break if you are still waiting to get in the class
  • Next Women in Computer Science Club meeting this Wednesday from 12:30-1:30pm in ATC 202
    • This meeting featuring a speaker from Amazon!


Review Activity
  • What are the advantage of a linked list compared to an array?
    • An array compared to a linked list?
  • With a partner, write the insertStop function for the linked list.
  • What might be the precondition for this function: getStop()?
  • Is the getStop() function an access function, manipulation procedure or constructor?


The List Iterator

  • So far, the List class we have written has not been very functional.
  • We have only been able to insert data at the beginning and end of the List, but not in the middle.
  • We have only been able to access data at the beginning and end of the List, but not in the middle.
  • We need an iterator!


Iterators

  • An iterator is a special pointer that allows us to traverse a container.
  • The list iterator is a Node pointer that allows us to traverse the nodes in our List.
  • Our list iterator can move from one node to the next in the list.
  • It can thus be used to access data in the middle of the list or insert (and remove) data in the middle of the list.
  • The list iterator will be useful not only to us as the programmers, but to the users of our list.
  • Therefore, we need to write special functions to control the iterator.


The List Iterator and Its Functions

  • Let's add to our class definition to include an iterator as one fields of the list class.

class List
{

private:
         ...
       Node* start;
       Node* stop;    
       Node* iterator;
       int length;
}
  • We then initialized it to be NULL inside of our default constructor

List::List(){

    start = NULL;

    stop = NULL;

    iterator = NULL;

    length = 0;

}

  • Notice that the iterator is just a pointer to a Node. We will be moving this pointer around the List, which will allow us to access and manipulate the interior nodes.
  • We will need functions to define the behavior of the iterator.
  • These operations are as follows:
startIterator: moves the iterator to the beginning of the list
removeIterator: removes the element currently pointed to by the iterator
getIterator: returns the element currently pointed at by the iterator
insertIterator: inserts an element after the node currently pointed to by the iterator
             moveIterNext: moves the iterator up by one node towards the stop node
              moveIterPrevious: moves the iterator back one node towards the start node
             offEnd: returns whether the iterator is off the end of the list, i.e. pointing to NULL

Writing the startIterator Function
  • After the List constructor is called, the iterator is defined as being "off the end of the List" (i.e. pointing to NULL).

In the above image, the iterator is considered to be "off the end" of the List.

  • As we add and remove elements in our list using functions such as insertStart or insertStop, the position of the iterator should NOT change.
  • In fact, the ONLY way that the iterator should "move onto" the List (i.e. point at a node in the List), is when a call is made to the startIterator function.
  • The purpose of the startIterator function is to make the iterator point to the first node of the List.
  • The user can call this function whenever he or she wishes to return the iterator to the beginning of the List.
  •  It is implemented as follows:
void List::startIterator()
{
    iterator = start;
}

  • We can visualize the effect of this function with the below diagram (compared to the diagram above).

With a Partner Discuss
  • How would you write the following 3 functions:
    • getIterator: returns the element currently pointed at by the iterator
    • moveIterNext: advances the iterator by one node in the List
    • offEnd: returns whether or not the iterator is off the end of the List, i.e. NULL
  • Which of the above 2 functions have preconditions?
    • What are the preconditions and why?

   


Class Activity: Writing getIterator, moveIterNext and offEnd
  • Open your List.h, List.cpp and ListTest.cpp from your Lab 1
  • Add the startIterator function as provided in the notes above.
  • Now, write the above three functions.
  • Make sure to test each function inside your ListTest.cpp file.
  • For example:
int main() {

    List L; //calling the default constructor

    L.insertStart(5);
    L.insertStop(8);
    L.insertStart(2);

    cout << "The list should contain: 2 5 8:" << endl;
    L.displayList();
    cout << endl;
   
    cout << "Iterator should be off the end of the list" << endl;
    if (L.offEnd())
        cout << "Iterator is off the end of the list" << endl;
    else
        cout << "Iterator is not off the end of the list" << endl << endl;

    L.startIterator();
    cout << "The data at the first node is 2: " << L.getIterator() << endl;
    L.moveIterNext();
    cout << "The data in the second node is 5: " << L.getIterator() << endl;
    L.moveIterNext();
   
cout << "The data at the last node is 8: " << L.getIterator() << endl << endl;

           cout << "Iterator should NOT be off the end of the list" << endl;
    if (L.offEnd())
        cout << "Iterator is off the end of the list" << endl;
    else
        cout << "Iterator is not off the end of the list" << endl << endl;

    L.moveIterNext();   
cout << "Iterator should be off the end of the list" << endl;
    if (L.offEnd())
        cout << "Iterator is off the end of the list" << endl;
    else
        cout << "Iterator is not off the end of the list" << endl;
    
    return 0;


}


List Access Functions & Their Preconditions


  • Access functions provide information about the current state of the data structure.
  • For example, the following access function tells us whether the list is currently empty:

bool List::isEmpty()
{
    return (length==0);
}

  • Access functions typically have preconditions that we must account for as part of the function.
  • We will look at how to handle preconditions in the following section.


Handling Preconditions When Writing Access Functions

  • Recall that preconditions specify what conditions must exist for a function to be executed
  • Often, access functions will have preconditions.
  • For example, the getStart function cannot return a value for the data stored at the first node, if the list is empty.

int getStart() const;
//Returns the first element in the list
//Precondition: the list cannot be empty
  • But, what should be done when the precondition is violated?
  • Our functions must handle violated preconditions, as these situations arise often.
  • Let's examine several approaches and select the best one:
Option 1: Alert the user to this situation, by printing an error message
  • For example, for the getStart() function:

if (isEmpty())
    cout << "getStart(): List is empty. No first element." << endl;

  • Thus, the function would now be written as follows:
int List::getStart() const
{
    if (isEmpty()){
        cout << "getStart(): List is empty. No first element" << endl;
        //What is wrong with this approach???
    
    } else {
            return start -> data;
        }
    }
  • If we write the function as above, the compiler should complain to us. Why?
    • If the precondition is not met, the function will not return a value.
    • There is no return statement inside the if
    • This function MUST return a value in either case (if or else).


Option 2: Return a Dummy Value

  • One approach to solve this problem is to return a dummy value such as -1.
int List::getStart() const
{
    if (isEmpty()){
        cout << "getStart(): List is empty. No first element" << endl;
        return -1; //What is wrong with this approach???
    
    } else {
            return start -> data;
        }
    }
  • Why might the above approach be a poor one?
    • -1 could be a possible value contained in the List
    • There is no suitable dummy value for a list of integers


Option 3: Print an error message and halt the program using assert

  • I am going to recommend that we use the assert macro to halt our program whenever a precondition is violated.

        assert(length != 0); //#include <assert.h>

  • Calling assert will automatically give us a descriptive error message about what precondition was violated, in which function and on what line number. For example:

Assertion failed: (length != 0), function getStart, file ../src/List.cpp, line 62.

  • For the getStart function, we could use it like this:
#include <assert.h>
....

int List::getStart() const
{
assert(!isEmpty());
return start -> data;
}
  • There are problems with this approach as well. However, we are going to use it for the time being.
  • When you take the Advanced C++ Course next quarter, you will learn about exceptions, which are a better approach to handling preconditions that have been violated.


Class Activity: Handling Preconditions for Your List Access Functions

  • Open up your List.h, List.cpp and ListTest.cpp from your Lab 1.
  • For each of the access functions you wrote for your lab, you will need to add code to handle the preconditions.
  • Check with your neighbor if you need help, or raise your hand and ask the instructor.



List Copy Constructor

The Rule of Three

  • For your lab, you had to write the List constructor and default constructor.
  • Now, we are going to write our own copy constructor.
  • There is a famous rule-of-thumb in C++ called The Rule of Three. It specifies that if you explicitly define one or more of the following, you likely need to define all three:
    • constructor
    • copy constructor (Note: we will write the copy constructor next class.)
    • destructor


Copy Constructor
  • Copy constructors are used to create a copy of an existing object.
  • For example, in our linked list class, a copy constructor's job is to create a new list that is an identical copy of the original list.
  • We would call the copy constructor for a linked list by passing in the original list as a parameter:
List copy_list(original_list); //calling the copy constructor
  • In C++, the compiler automatically creates a copy constructor for your class. 
  • This happens for ALL classes that you write, not just the linked list class.
  • However, this default copy constructor will create a shallow copy of the List.


Deep vs Shallow Copies

  • A shallow copy simply sets all fields in the new object equal to the fields in the original object:
//pseudocode
List2.head = List1.head;
List2.tail = List1.tail;
    List2.length = List1.length;

enter image description here

Do you see how shallow copies could result in dangling pointers if one of the lists is deleted but not the other? Image Source

  • The important concept to understand here is that we need to make a deep copy rather than a shallow copy.
  • A deep copy will allocate new memory. This memory will contain a copy of the data in the original list.
  • A shallow copy will simply create new pointers to existing memory.
  • Here our goal is two separate lists containing the same data in the same order.


Why Are Deep Copies Necessary?

  • Let's say that we do not write our own copy constructor and simply call the predefined shallow copy constructor that your compiler automatically generates.
  • In this case, the shallow copy constructor will create new pointers to the start and stop of the original list.
  • But, what will happen if I call my destructor on the first list, but not the second one?
  • The second list will be pointing at memory that has been freed, resulting in dangling pointers.
  • Big problem!
  • A deep copy will avoid this problem.
  • The difference between a deep and shallow copy is an important concept, and a favorite question of interviewers!
  • Therefore, if you are having trouble understanding the difference between a deep and shallow copy, I recommend that you watch this video.

With a deep copy, we allocate new memory and then copy the contents of the original object into these new memory locations. Image Source


How to Write a Copy Constructor

  • In C++ the copy constructor follows this standard format:
classname (const classname &obj) {
   // body of constructor
} 
  • Therefore, our copy constructor needs to look like the following:
List::List(const List &list)
{
    //body of constructor
}

  • Above, the variable list is what you are trying to make a copy of.
  • Why is list a constant here?


How to Write the List Copy Constructor

  • Here is the pseudocode for the List copy constructor:


List::List(const List &list): length(list.length)
{

   if(original list is empty)

        make the new list empty

   else
   {

        //Allocate memory for a new start node

        //Copy contents of original start node into new last node

        //Move through both lists with a while loop

        while (next is not NULL)
        {

            //Copy the contents of original node into new node
        }

        Create a node pointer called stop to point at the stop node in the new list


   }
}


  • Here is the code for the copy constructor. Make sure you understand it.
List::List(const List &list)
{
   

    if(list.start == NULL) //If the original list is empty, make an empty list for this list
    {
        start = stop = iterator = NULL;
    }
    else
    {
        start = new Node(list.start->data); //calling Node constructor
        Node* temp = list.start; //set a temporary node pointer to point at the start of the original list
        iterator = start; //set iterator to point to the start node of the new list

        while(temp->next != NULL)
        {

            temp = temp->next; //advance up to the next node in the original list
            iterator->next = new Node(temp->data); //using node constructor to create new node w/ copy of data
            iterator = iterator->next; //advance to this new node

        }

        stop = iterator; //Why do I need this line of code?
        iterator = NULL;

    }
   

    length = list.length;
}

  • Why do I need to create the temp variable above?


Calling the List Copy Constructor
  • Below is an example of calling the List copy constructor:

int main() {

    List L_original; //calling the default constructor

    L_original.insertStart(5);
    L_original.insertStop(8);
    L_original.insertStart(2);

    cout << "The list should contain: 2 5 8:" << endl;
    L_original.displayList();

    List L_copy(L_original); //calling the copy constructor to make a copy of the original list
    //Alternately: List L_copy = L_original; will also call copy constructor
    
    cout << "The copy of the list should contain: 2 5 8:" << endl:
    L_copy.displayList();

    return 0;

}



Wrap Up

  • With a Partner, answer the questions from our learning objectives

Homework
  • Study for Quiz 1 next class
  • Lab 2 due one week from today


~See You Wednesday!~