From 6d9fab4c0f52489f2f19a933fa49e29518612736 Mon Sep 17 00:00:00 2001 From: lshprung Date: Tue, 9 Feb 2021 10:02:43 -0800 Subject: Post-class 02/09 --- 02-04.md | 26 ++--- 02-09.md | 260 ++++++++++++++++++++++++++++++++++++++++++++++++++ 02-09_1.png | Bin 0 -> 10578 bytes 02-11.md | 308 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 4 files changed, 583 insertions(+), 11 deletions(-) create mode 100644 02-09.md create mode 100644 02-09_1.png create mode 100644 02-11.md diff --git a/02-04.md b/02-04.md index 6f8cf25..96042bb 100644 --- a/02-04.md +++ b/02-04.md @@ -135,17 +135,17 @@ void bag::operator +=(const bag& addend){ ``` //FUNCTIONS for the linked list toolkit -std::size_t list_length(const node *head_ptr); -void list_head_insert(node *& head_ptr, const node::value_type& entry); -void list_insert(node *previous_ptr, const node::value_type& entry); -node *list_search(node *head_ptr, const node::value_type& target); -const node* list_search(const node* head_ptr, const node::value_type& target); -node *list_locate(node *head_ptr, std::size_t position); -const node *list_locate(const node *head_ptr, std::size_t position); -void list_head_remove(node *& head_ptr); -void list_remove(node *previous_ptr); -void list_clear(node *& head_ptr); -void list_copy(const node *source_ptr, node *& head_ptr, node *& tail_ptr); +std::size_t list_length(const node *head_ptr); //length of the list +void list_head_insert(node *& head_ptr, const node::value_type& entry); //insert a new head +void list_insert(node *previous_ptr, const node::value_type& entry); //insert a new node after the given node +node *list_search(node *head_ptr, const node::value_type& target); //search for a value in the list +const node* list_search(const node* head_ptr, const node::value_type& target); //search for a node with a certain value in the list +node *list_locate(node *head_ptr, std::size_t position); //return the nth node in the list +const node *list_locate(const node *head_ptr, std::size_t position); //const version of previous function +void list_head_remove(node *& head_ptr); //remove head pointer (head->next becomes the head) +void list_remove(node *previous_ptr); //remove the pointer after the given pointer +void list_clear(node *& head_ptr); //remove all nodes in list +void list_copy(const node *source_ptr, node *& head_ptr, node *& tail_ptr); //create a copy of a given list ``` ### Parameters for Linked Lists @@ -310,3 +310,7 @@ void list_head_insert(node *& head_ptr, const node::value_type& entry){ - The linked list toolkit also provides for inserting a new node elsewhere - It is easy to remove a node at the front of a list - The linked list toolkit also provides a function for removing a node elsewhere - you should read about this function and the other functions of the toolkit + +--- + +[02/09 ->](02-09.md) diff --git a/02-09.md b/02-09.md new file mode 100644 index 0000000..f8e0ed9 --- /dev/null +++ b/02-09.md @@ -0,0 +1,260 @@ +[\<- 02/04](02-04.md) + +# Dynamic Arrays vs. Linked Lists vs. Double Linked Lists + +- Many classes can be implemented with either dynamic arrays or linked lists +- **Which approach is better?** + +## Dynamic Array + +### Arrays are better at random access + +- The term **random access** refers to examining or changing an arbitrary element that is **specified by its position** in a list +- For example: + - What is the 2nd item in the list? + - Change the item at position 16 to 4 +- These are **constant time operations** for an array (or dynamic array) +- In a **linked list**, a search for an item must begin at the head and will take **O(N)** time + +### Resizing can be inefficient for a dynamic array + +- This is because: + - New memory must be allocated + - The items are then copied from the old memory to the new memory + - The old memory is deleted +- When the eventual capacity is unknown and a program must continually adjust the capacity, a linked list has advantages + +## Linked Lists + +### Linked lists are better at insertions/deletions at a cursor + +- If class operations take place at a cursor, then a linked list is better than a dynamic array +- Insertions and deletions at a cursor are generally **linear time (O(N)) for an array** (since items that are after the cursor must be shifted) +- But these operations are **constant time operations (O(1))** for a linked list + +## Doubly Linked Lists + +### Doubly linked lists are better for a two-way cursor + +- Sometimes list operations require a cursor that can move forward and backward through a list + - A **two-way cursor** +- **Double linked list** is like a simple linked list, except that **each node contains two pointers**: one pointing to the next node and one pointing to the previous node + +![diagram](02-09_1.png) + +- A possible definition for a doubly linked list of items: + +``` +class dnode{ + public: + typedef ____ value_type; + ... + + private: + value_type data_field; + dnode *link_fore; + dnode *link_back; +}; +``` + +- In C++, this is called the `std::list` +- `link_back` fields points to the previous node +- `link_fore` points to the next node in the list + +### A Class for a Node in a Doubly Linked List + +``` +#ifndef SCU_COEN79_DNODE_H +#define SCU_COEN79_DNODE_H +#include //provides size_t and NULL +namespace scu_coen79_5{ + class dnode{ + public: + // TYPEDEF + typedef double value_type; + + //CONSTRUCTOR + dnode(const value_type& init_data = value_type(), dnode *init_fore = NULL, dnode *init_back = NULL){ + data_field = init_data; + link_fore = init_fore; + link_back = init_back; + } + + //Member functions to set the data and link fields: + void set_data(const value_type& new_data) {data_field = new_data;}; + void set_fore(dnoe *new_fore) {link_fore = new_fore;}; + void set_back(dnode *new_back) {link_back = new_back;}; + + //Const member function to retrieve the current data: + value_type data() const {return data_field;}; + + //Two slightly different member functions to retrieve each current link: + const dnode *fore() const {return link_fore;}; + dnode *fore() {return link_fore;}; + const dnode *back() const { return link_back;}; + dnode *back() {return link_back;}; + + private: + value_type data_field; + dnode *link_fore; + dnode *link_back; + }; +} + +#endif +``` + +## Guidelines for Choosing Between a Dynamic Array and a Linked List + +|Case |Data Structure | +|------------------------------------|-------------------| +|Frequent random access operations |Use a dynamic array| +|Operations occur at a cursor |Use a linked list | +|Operations occur at a two-way cursor|Use a linked list | +|Frequent resizing may be needed |Use a linked list | + +## Summary + +- A **linked list** consists of node + - Each **node** contain data and a pointer to the next node in the list +- A linked list is accessed througha **head pointer** that points to the *head node* +- A linked list may have a **tail pointer** that points to the last node +- A **doubly linked list** has nodes with two pointers: one to the next node and one to the previous node + - Enables a cursor to move forward and backward +- Containers can be implemented in many different ways, such as by using a dynamic array or using a linked list +- Arrays are better at **random access** +- Linked lists are better at **insertions/removals at a cursor** + +--- + +# Template Functions + +- Introduction of templates, which are C++ feature that easily permits the reuse of existing code for new purposes +- Shows how to implement and use the simplest kinds of templates: **template functions** + +## Finding the Maximum of Two Numbers + +### Finding the Maximum of Two Integers + +- Here's a small function that you might write to find the maximum of two integers + +``` +int maximum(int a, int b){ + if(a > b) return a; + else return b; +} +``` + +### Finding the Maximum of Two Doubles + +- Here's a small function that you might write to find the maximum of two double numbers + +``` +int maximum(double a, double b){ + if(a > b) return a; + else return b; +} +``` + +### Finding the Maximum of Two Knafns + +- Here's a small function that you might write to find the maximum of two knafns + +``` +int maximum(knafn a, knafn b){ + if(a > b) return a; + else return b; +} +``` + +### One Hundred Million Functions... + +- Suppose your program uses 100,000,000 different data types, and you need maximum function for each... + +### A Template Function for Maximum + +- This template function can be used with many data types + +``` +template +Item maximum(Item a, Item b){ + if(a > b) return a; + else return b; +} +``` + +- When you write a template function, you choose a data type for the function to depend upon... +- A template prefix is also needed immediately before the function's implementation + +### Using a Template Function + +- Once a template function is defined, it may be used with any adequate data type in your program... + +``` +cout << maximum(1, 2); +cout << maxiumum(1.3, 0.9); +``` + +## Multi Parameter Templates + +``` +int array_max(int data[], size_t n){ + size_t i; + int answer; + + assert(n > 0); + answer = data[0]; + for(i = 1; i < n; i++){ + if(data[i] > answer) answer = data[i]; + return answer; +} +``` + +### Solution 1 + +``` +template +Item array_max(Item data[], size_t n){ + size_t i; + Item answer; + + assert(n > 0); + answer = data[0]; + for(i = 1; i < n; i++){ + if(data[i] > answer) answer = data[i]; + return answer; +} +``` + +- What are the problems? + - `size_t` is not generic, so passing, for example, a `const size_t` will return an error + +### Examples + +``` +const size_t SIZE = 5; +double data[SIZE]; +//... + +cout << array_max(data, SIZE); +cout << array_max(data, 5); + +template +Item array_max(Item data[], size_t n); +``` + +### Solution 2 + +``` +template +Item array_max(Item data[], Sizetype n){ + size_t i; + Item answer; + + assert(n > 0); + answer = data[0]; + for(i = 1; i < n; i++){ + if(data[i] > answer) answer = data[i]; + return answer; +} +``` diff --git a/02-09_1.png b/02-09_1.png new file mode 100644 index 0000000..4bb4eeb Binary files /dev/null and b/02-09_1.png differ diff --git a/02-11.md b/02-11.md new file mode 100644 index 0000000..5de7745 --- /dev/null +++ b/02-11.md @@ -0,0 +1,308 @@ +# Template Functions + +- Introduction of templates, which are C++ feature that easily permits the reuse of existing code for new purposes +- Shows how to implement and use the simplest kinds of templates: **template functions** + +## Finding the Maximum of Two Numbers + +### Finding the Maximum of Two Integers + +- Here's a small function that you might write to find the maximum of two integers + +``` +int maximum(int a, int b){ + if(a > b) return a; + else return b; +} +``` + +### Finding the Maximum of Two Doubles + +- Here's a small function that you might write to find the maximum of two double numbers + +``` +int maximum(double a, double b){ + if(a > b) return a; + else return b; +} +``` + +### Finding the Maximum of Two Knafns + +- Here's a small function that you might write to find the maximum of two knafns + +``` +int maximum(knafn a, knafn b){ + if(a > b) return a; + else return b; +} +``` + +### One Hundred Million Functions... + +- Suppose your program uses 100,000,000 different data types, and you need maximum function for each... + +### A Template Function for Maximum + +- This template function can be used with many data types + +``` +template +Item maximum(Item a, Item b){ + if(a > b) return a; + else return b; +} +``` + +- When you write a template function, you choose a data type for the function to depend upon... +- A template prefix is also needed immediately before the function's implementation + +### Using a Template Function + +- Once a template function is defined, it may be used with any adequate data type in your program... + +``` +cout << maximum(1, 2); +cout << maxiumum(1.3, 0.9); +``` + +## Multi Parameter Templates + +``` +int array_max(int data[], size_t n){ + size_t i; + int answer; + + assert(n > 0); + answer = data[0]; + for(i = 1; i < n; i++){ + if(data[i] > answer) answer = data[i]; + return answer; +} +``` + +### Solution 1 + +``` +template +Item array_max(Item data[], size_t n){ + size_t i; + Item answer; + + assert(n > 0); + answer = data[0]; + for(i = 1; i < n; i++){ + if(data[i] > answer) answer = data[i]; + return answer; +} +``` + +- What are the problems? + - `size_t` is not generic, so passing, for example, a `const size_t` will return an error + +### Examples + +``` +const size_t SIZE = 5; +double data[SIZE]; +//... + +cout << array_max(data, SIZE); +cout << array_max(data, 5); + +template +Item array_max(Item data[], size_t n); +``` + +### Solution 2 + +``` +template +Item array_max(Item data[], Sizetype n){ + size_t i; + Item answer; + + assert(n > 0); + answer = data[0]; + for(i = 1; i < n; i++){ + if(data[i] > answer) answer = data[i]; + return answer; +} +``` + +--- + +# Template Classes + +- A template function is a function that depends on an underlying data type +- In a similar way, when a class depends on an underlying data type, the class can be implemented as a **template class** +- For example, a single program can use a bag of integers, and a bag of characters, and a bag of strings, and... +- You do not have to determine the data type of a data structure when developing a code + +## Bag Example + +### Syntax For Template Classes + +``` +class bag{ + public: + typedef int value_type; + typedef size_t size_type; + ... +``` + +``` +template +class bag{ + public: + ... +} +``` + +- `template ` is the template prefix, and it warns the compiler that the following definition will use an unspecified data type called `Item` + +### Template Class Functions + +- The bag's `value_type` is now dependent on the `Item` type +- **Outside the template class definition** some rules are required to tell the compiler about the dependency: + - The template prefix `template ` is placed immediately before each function prototype and definition + - Outside the template class definition, each use of the class name (such as `bag`) is changed to the template class name (such as `bag`) + - Within a class definition or within a member function, we can still use the bag's type names, such as `value_type` or `size_type` + - Outside of a member function, to use a type such as `bag::size_type`, we must add a new keyword `typename`, writing the expression `typename bag::size_type` + +### Example 1 + +- For our **original class**, the function's implementation began this way: + +``` +bag operator +(const bag& b1, const bag& b2) ... +``` + +- For the **template class**, the start of the implementation is shown here: + +``` +template +bag operator +(const bag& b1, const bag& b2); +... +``` + +### Example 2 + +``` +bag::size_type bag::count(const value_type& target) const; +``` + +- Outside of a member function, you must put the keyword `typename` in front of any member of a template class is the name of a data type + +``` +template +typename bag::size_type bag::count (const Item& target) const; +``` + +## Summary: Item and typename + +|In the original Bag class |In the template bag class | +|-----------------------------------|-----------------------------| +|value_type |Item | +|size_type (inside member function) |size_type | +|size_type (outside member function)|typename bag::size_type| + +## Header File Changes + +- **In the header file**, you place the documentation and the prototypes of the functions; **then you must include the actual implementations of all the functions** + - The reason for the requirement is to make the compiler's job simpler + - **An alternative**: You can keep the implementations in a separate implementation file, but place an `include` directive at the bottom of the header file to pick up these implementations + - We include the following line at the end of the header file: + +``` +#include "bag4.template" //Include the implementation +``` + +## Do Not Place using Directive + +- Because a template class has its implementation included in the header file, we must not place any `using` directives in the implementation +- Otherwiser, every program that uses our template class will inadvertently use the `using` directives + +## Bag Class Header and Implementation Files + +### Header File for the Bag Template Class + +``` +#ifndef SCU_COEN79_BAG4_H +#define SCU_COEN79_BAG4_H +#include //Provides size_t + +namespace scu_coen79_6A{ + template + class bag{ + public: + //TYPEDEFS and MEMBER CONSTANTS + typedef std::size_t size_type; + static const size_type DEFAULT_CAPACITY = 30; + + //CONSTRUCTORS and DESTRUCTORS + bag(size_type initial_capacity = DEFAULT_CAPACITY); + bag(const bag& source); + ~bag(); + + //MODIFICATION MEMBER FUNCTIONS + size_type erase(const Item& target); + bool erase_one(const Item& target); + void insert(const Item& entry); + void operator =(const bag& source); + void operator +=(const bag& addend); + void reserve(size_type capacity); + + //CONSTANT MEMBER FUNCTIONS + size_type count(const Item& target) const; + Item grab() const; + size_type size() const {return used;}; + + private: + Item *data; //Pointer to partially filled dynamic array + size_type used; //How much of array is being used + size_type capacity; //Current capacity of the bag + }; +``` + +- Inside the template class definition: Compiler knows about the dependency on `Item` type +- Some rules are required outside of the template class definition: + - `template` is placed immediately before each function prototype and definition + - Each use of the class name is changed to the template class name (`bag`) + - We should then include the implementation of the template in the header file (needed by most compilers) + - Instead of that: we keep the implementation in a separate file + +``` +//NONMEMBER FUNCTIONS +//originally: bag operator +(const bag& b1, const bag& b2); + +template +bag& b1, const bag& b2); + +#include "bag4.template" +#endif +``` + +### Implementation File for the Bag Template Class + +``` +#include //provides copy +#include //provides assert +#include //provides rand + +namespace SCU_COEN79_6A{ + + //MEMBER CONSTANTS + template + const typename bag::size_type bag::DEFAULT_CAPACITY; +``` + +- Some compilers require the default parameters to be both in the prototype and implementation +- Remeber that: + - To refer to `size_type` outside a member function: `typename bag::size_type` +- Each definition is preceded by `template ` + +``` + //CONSTRUCTORS + template + -- cgit