From 43b0b86abaa63e3a5795b066c1a5fef9a60d8f0d Mon Sep 17 00:00:00 2001 From: lshprung Date: Tue, 2 Feb 2021 10:10:03 -0800 Subject: Post-class 02/02 --- 01-28.md | 4 + 02-02.md | 548 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 02-02_1.png | Bin 0 -> 5508 bytes 02-02_2.png | Bin 0 -> 9188 bytes 02-02_3.png | Bin 0 -> 11761 bytes 02-02_4.png | Bin 0 -> 6744 bytes 02-02_5.png | Bin 0 -> 26239 bytes 02-02_6.png | Bin 0 -> 9873 bytes 02-02_7.png | Bin 0 -> 18195 bytes 9 files changed, 552 insertions(+) create mode 100644 02-02.md create mode 100644 02-02_1.png create mode 100644 02-02_2.png create mode 100644 02-02_3.png create mode 100644 02-02_4.png create mode 100644 02-02_5.png create mode 100644 02-02_6.png create mode 100644 02-02_7.png diff --git a/01-28.md b/01-28.md index d144117..79fc8c3 100644 --- a/01-28.md +++ b/01-28.md @@ -452,3 +452,7 @@ delete b_ptr; - When `delete b_ptr` is executed, the destructor for `*b_ptr` is automatically activated - The destructor ensures that the dynamic array used by `*b_ptr` is released + +--- + +[02/02 ->](02-02.md) diff --git a/02-02.md b/02-02.md new file mode 100644 index 0000000..73a51d6 --- /dev/null +++ b/02-02.md @@ -0,0 +1,548 @@ +[\<- 01/28](01-28.md) + +--- + +## The Bag Class with Dynamic Arrays (cont.) + +### Header File for the Bag Class with a Dynamic Array + +``` +// FILE: bag2.h (part of the namespace scu_coen79_4) +// CLASS PROVIDED: bag +#ifndef SCU_COEN79_BAG2_H +#define SCU_COEN79_BAG2_H +#include //provides size_t + +namespace scu_coen79_4{ + + class bag{ + + public: + //TYPEDEFS and MEMBER CONSTANTS + typedef int value_type; + typedef std::size_t size_type; + static const size_type DEFAULT_CAPACITY = 30; + + //CONSTRUCTOR and DESTRUCTOR + bag(size_type initial_capacity = DEFAULT CAPACITY); + bag(const bag& source); //copy constructor + ~bag(); //destructor + + //MODIFICATION MEMBER FUNCTIONS + void reserve(size_type new_capacity); //increases the bag's current capacity to the new capacity + bool erase_one(const value_type& target); + size_type erase(const value_type& target); + void insert(const value_type& entry); //inserts a new copy of entry to the bag + void operator +=(const bag& addend); + void operator =(const bag& source); //enables a bag to have same items and capacity as source + + //CONSTANT MEMBER FUNCTIONS + size_type size() const {return used;}; + size_type count(const value_type& target) const; + + private: + //Pointer to partially filled dynamic array + value_type *data; + + //How much of array is being used + size_type used; + + //Current capacity of the bag + size_type capacity; + }; + + //NONMEMBER FUNCTIONS for the bag class + bag operator +(const bag& b1, const bag& b2); +} + +#endif +``` + +### The Revised Bag Class - Implementation + +- Three functions are particularly important: + 1. Constructors + 2. Destructor + 3. Assignment operator +- These three member functions are always needed when a class uses dynamic memory + +- **The constructors**: Each of the constructors is responsible for setting up the three private member variables in a way that satisfies the invariant of the dynamic bag class +- **Constructor**: + +``` +bag::bag(size_type initial_capacity){ + data = new value_type[initial_capacity]; + capacity = initial_capacity; + used = 0; +} +``` + +- `initial_capacity` tells how many items to allocate for the dynamic array + +- **Copy Constructor**: + +``` +bag::bag(const bag& source){ + //Library facilities used: algorithm + + data = new value_type[source.capacity]; + capacity = source.capacity; + used = source.used; + copy(source.data, source.data + used, data); +} +``` + +- `copy()` takes in three arguments: + - The start + - The end + - The destination +- The capacity of the dynamic array is the same as the capacity of the bag that is being copied +- After the dynamic array has been allocated, the items may be copied into a newly allocated array + +- **The destructor**: The primary responsibility of the destructor is **releasing dynamic memory** + +``` +bag::~bag(){ + delete [] data; +} +``` + +**The assignment operator** + +- Assignment operator vs. Copy constructor: + - The assignment operator is not constructing a new bag, meaning that there is already a partially filled array allocated + - The size of this array might need to be changed + - If we allocate a new array, then the original array must be returned to the heap + - In the assignment operator, it is possible that the source parameter (which is being copied) is the same object that activates the operator + - With a `bag b`, this would occur if a programmer writes `b = b` (called a **self assignment**) + +``` +void bag::operator =(const bag& source){ + value_type *new_data; + + //If needed, allocate ar array with a different size + if(capacity != source.capacity){ + new_data = new value_type[source.capacity]; + delete [] data; + data = new_data; + capacity = source.capacity; + } + + used = source.used; + copy(source.data, source.data + used, data); +} +``` + +- The solution for the self-assignment is to provide a special check at the start of the operator +- If we find that an assignment such as `b = b` is occurring, then we will return immediately +- We can check for this condition by determining whether source is the same object as the object that activated the operator + +``` +//Check for possible self-assignment: +if(this == &source) return; +``` + +- `this` is a **pointer** to the object that activated the function +- `&source` is the **address** of the `source` object +- Revised assignment operator: + +``` +void bag::operator =(const bag& source){ + value_type *new_data; + + if(this == &source) return; //Check for self-assignment + + //If needed, allocate ar array with a different size + if(capacity != source.capacity){ + new_data = new value_type[source.capacity]; + delete [] data; + data = new_data; + capacity = source.capacity; + } + + used = source.used; + copy(source.data, source.data + used, data); +} +``` + +Example: + +- Assume that `source` is a bag with a capacity of 5, and the bag that activated the function has a mere capacity of 2 +- When the assignment begins, we have this situation + +![diagram](02-02_1.png) + +- Since the current capacity (which is 2) is not equal to the amount needed (which is 5), the code enters the body of the if-statement +- In the body, we have a local variable, `new_data`, which is set to point to a newly allocated array of five items: + +![diagram](02-02_2.png) + +- Once the new array has been allocated: + - We return the old array to the heap + - Assign `data = new_data`, so that the data pointer points to the new array + +![diagram](02-02_3.png) + +- Capacity is changed to 5 +- We no longer need the local variable `new_data` + +![diagram](02-02_4.png) + +- At this point: + - Copy the items from source's array into the newly allocated array + - Set the value of `used` + +- Why not to use the following two statements for memory allocation instead of using a local variable? + +``` +delete [] data; //Release old array +data = new value_type[source.capacity]; //Allocate new array +``` + +- When the destructor is given an invalid object (such as our invalid bag): + - The destructor may cause an error message that will be more confusing than the usual message from `bad_alloc` + - Programs will be harder to debug +- The invalid bag also makes it harder for experienced programmers to deal with the `bad_alloc` exception in a way that tries to recover without halting the program +- Because of these problems: **Member functions must always ensure that all objects are valid prior to calling new** + +### The reserve member function + +- `reserve` member function is used to change the capacity of a bag + +``` +void bag::reserve(size_type new_capacity){ + //Postcondition: The bag's current capacity is changed to the new_capacity (but not less than the number of items already in the bag) + + value_type large_array; + if(new_capacity == capacity) return; //The allocated memory is already the right size + if(new_capacity < used) new_capacity = used; //can't allocate less than used + + larger_array = new value_type[new_capacity]; + copy(data, data + used, larger_array); + delete [] data; + data = larger_array; + capacity = new_capacity; +} +``` + +### The insert and operator += member functions + +``` +void bag::insert(const value_type& entry){ + if (used == capacity) reserve(used+1); + data[used] = entry; + ++used; +} +``` + +``` +void bag::operator +=(const bag& addend){ + //Library facilities used: algorithm + + if(used + addend.used > capacity) reserve(used + addend.used); + copy(addend.data, addend.data + addend.used, data + used); + used += addend.used; +} +``` + +### The operator + member function + +``` +bag operator +(const bag& b1, const bag& b2){ + + bag answer(b1.size() + b2.size()); //The function declares a bag of sufficient size + answer += b1; + answer += b2; + return answer; +} +``` + +--- + +## Prescription for a Dynamic Class + +### Four Rules + +- When a class uses **dynamic memory**, follow these four rules: + - Some of the member variables of the class are **pointers** + - Member functions **allocate and release dynamic memory** + - The **automatic value semantics of the class is overridden** + - The **class has a destructor** to return all dynamic memory to the heap + +### Special Important of the Copy Constructor + +- The **copy constructor** is used when **one object is to be initialized as a copy of another**, as in the declaration: + +``` +bag y(x); //Initialize y as a copy of x +``` + +- There are three other common situations where the copy constructor is used + +1. Alternative syntax: The first situation is really just an alternative syntax for using the copy constructor to initialize **a newly declared object**: + +``` +bag y = x; //Initialize y as a copy of x +``` + +2. The second situation that uses the copy constructor is **when a return value of a function is an object** + - Example: The bag's `operator+` returns a `bag` object + - The function computes its answer in a local variable, and then has a return statement + - When the return statement is executed, the value from the local variable is copied to a temporary location called the **return location** + - The local variable itself is then destroyed (along with any other local variables), and the function returns to the place where it was called + +3. A third situation arises **when a value parameter is an object** + - Example: `int rotations_needed(point p);` + - When the function is called, **the actual argument is copied to the formal parameter p** + - The copying occurs **by using the copy constructor** + +--- + +## Smart Pointers + +``` +class smartIntPtr{ + int *ptr; //Actual pointer + + public: + //Constructor: + smartIntPtr(int *p = NULL) {ptr = p;}; + + //Destructor + ~smartIntPtr() {delete ptr;}; + + //Overloading dereferncing operator + int& operator *() {return *ptr;}; +}; + +int main(){ + smartIntPtr ptr(new int()); + *ptr = 20; + cout << *ptr << endl; + + return 0; +} +``` + +--- + +## Clarifying the this Keyword + +``` +class Test{ + + public: + void printAddress() {cout << "My address is: " << this << endl;}; +}; + +int main(){ + Test obj1; + obj1.printAddress(); + return 0; +} + +//Output: +My address is: 0x7fff5fbff6d8 +``` + +``` +class Test{ + + private: + int x, y; + + public: + Test(int x = 0; int y = 0) {this->x = x; this->y = y;} + Test& setX(int a) {x = a; return *this;}; + Test& setY(int b) {y = b; return *this;}; + void print() {cout << "x = " << x << "y = " << y << endl;}; +}; + +int main(){ + Test obj1(5, 5); + obj1.setX(10).setY(20); + + obj1.print(); + return 0; +} + +//Output: +x = 10 y = 20 +``` + +- We return the reference to the calling object +- This allows us to chain the operations +- Another alternative in the main function if `setX()` and `setY()` return `this` instead of `*this`: + +``` +Test *obj1 = new Test(5, 5); +obj1->setX(10)->setY(20); +``` + +--- + +# Data Structures and Other Objects + +### Linked Lists in Action + +- Chapter 5 introduces the often-used data structure of linked lists +- This presentation shows how to implement the most common operations on linked lists + +## Declaration for Linked Lists + +- For this presentation, nodes in a linked list are objects as shown here + +![diagram](02-02_5.png) + +``` +class node{ + + public: + typedef double value_type; + //... + + private: + value_type data_field; + node *link_field; +}; +``` + +- The `data_field` of each node is a type called `value_type`, defined by a typedef +- Each node also contains a `link_field` which is a pointer to another node +- A program can keep track of the front node by using a pointer variable such as `head_ptr` +- Keep in mind that `head_ptr` is not a node -- it is a pointer to a node +- We represent the empty list by storing `null` in the head pointer + +## Node Class + +``` +//Constructor +Node(const value_type init_data = value_type(), node* init_link=NULL) {data_field = init_data; link_field = init_link;}; + +//Member functions to set the data and link fields +void set_data(const value_type& new_data) {data_field = new_data;}; +void set_link(node *new_link) {link_field = new_link;}; + +//Constant member functions to retrieve the current data +value_type data() const {return data_field}; + +//Two slightly different member functions to retrieve the current link: +const node *link() const {return link_field;}; +node *link() {return link_field;}; + +private: + value_type data_field; + node* link_field; +``` + +- Whenever a member function returns a `*`, you have to write two functions + 1. const + 2. non const + +## Clarifying the const Keyword + +- Consider the pointer to a node: `node *p;` +- We can allocate a node for `p` to point to (through using `p = new node`) and then activate any of the member functions (`p->set_data()` or `p->data()`) +- Now consider this pointer parameter declared using `const` keyword: `const node *c;` +- The `const` keyword means that the pointer `c` cannot be used to change the node + - Pointer `c` cannot be used to activate non-constant member functions + - The pointer `c` can move and point to many different node, by we are forbidden from using `c` to change any of those nodes that `c` points to + +- Note that: + - We cannot assign a const pointer to a non-const pointer + - We can assign a non-const pointer to a const pointer + +### Example 1 + +``` +node *node_ptr1 = new node; +node *node_ptr2 = new node; + +const node const_node_ptr1 = node_ptr1; + +const node_ptr1->set_data(5); //Invalid +const_node_ptr1 = node_ptr2; //Valid +``` + +- A const pointer cannot be used for activating non-const member functions +- A new value can be assigned to a const pointer + +### Example 2: node *const c = &first + +``` +node *const c = &first; + +node *node_ptr1 = new node; +node *node_ptr2 = new node; + +const node const_node_ptr1 = node_ptr1; + +const node_ptr1->set_data(5); //Valid +const_node_ptr1 = node_ptr2; //Invalid +``` + +- If you want to create a **pointer that can be set once during its definition and never changed to point to a new object**, then put the word `const` after the `*` + +### Node's Constant Member Functions + +- A node's constant member functions should never provide a result that could later be used to change any part of the linked list +- Example: The purpose of the link member function is to obtain a copy of a node's link field +- At first glance, this sounds like a constant member function since retrieving a member variable does not change an object +- So we might write this: + +``` +node *link() const {return link_field;}; +``` + +### Problem with const + +- The node's constant member functions should never provide a result that we can later use to change any part of the linked list + +``` +node *link() const {return link_field;}; +``` + +![diagram](02-02_6.png) + +``` +node *second = head_ptr->link(); +``` + +![diagram](02-02_7.png) + +``` +second->set_data(9.2); //!!!!!!!! +``` + +### Solution 1 + +- It makes sense to implement link as a non-constant member function: + - Making the function non-constant **provides better accuracy about how the function's results might be used** +- `link` implementation as a non-constant member function: + +``` +node *link() {return link_field;}; +``` + +**This solution has another problem**: + - Suppose that `c` is defined as `const node *c` + - With the above non-constant link implementation, we could never activate `c->link()`, because it can only activate const functions + +### Final Solution + +``` +const node *link() const {return link_field;}; +``` + +- This **second version** is a constant member function: + - `c->link()` can be used, even if `c` is declared with the `const` keyword + - The return value from the `const` version of the function cannot be used to change any part of the linked list + - The compiler converts the `link_field` to the type `const node*` for the `const` version function + +### Rule for const Member Functions + +- When the return value of a member function is a pointer to a node, you should generally have two version: + - A `const` version that returns a `const node *` + - An ordinary version that return an ordinary pointer to a node +- When both a const and non-const version of a function are present: + - The **compiler automatically chooses the correct version** depending on whether the function was activated by a constant node (such as `const node *c`) or by an ordinary node diff --git a/02-02_1.png b/02-02_1.png new file mode 100644 index 0000000..7ab2a10 Binary files /dev/null and b/02-02_1.png differ diff --git a/02-02_2.png b/02-02_2.png new file mode 100644 index 0000000..a76d117 Binary files /dev/null and b/02-02_2.png differ diff --git a/02-02_3.png b/02-02_3.png new file mode 100644 index 0000000..aeddce6 Binary files /dev/null and b/02-02_3.png differ diff --git a/02-02_4.png b/02-02_4.png new file mode 100644 index 0000000..0201a7c Binary files /dev/null and b/02-02_4.png differ diff --git a/02-02_5.png b/02-02_5.png new file mode 100644 index 0000000..a3e8029 Binary files /dev/null and b/02-02_5.png differ diff --git a/02-02_6.png b/02-02_6.png new file mode 100644 index 0000000..5461bf4 Binary files /dev/null and b/02-02_6.png differ diff --git a/02-02_7.png b/02-02_7.png new file mode 100644 index 0000000..82993e9 Binary files /dev/null and b/02-02_7.png differ -- cgit