Post-class 01/19

2 files changed, 519 insertions, 0 deletions

diff --git a/01-14.md b/01-14.md
index 11abf45..0fc5245 100644
--- a/01-14.md
+++ b/01-14.md
@@ -471,3 +471,7 @@ istream& operator >>(istream& ins, point& target){
 - Two solutions:
 	- To write new member functions to set a point's coordinates and use these member functions within the input function's implementation
 	- You can grant special permission for the input functino to access the private members of the point class - Called a **Friend Function**
+
+---
+
+[01/19 ->](01-19.md)
diff --git a/01-19.md b/01-19.md
new file mode 100644
index 0000000..5b32d08
--- /dev/null
+++ b/01-19.md
@@ -0,0 +1,515 @@
+[\<- 01/14](01-14.md)
+
+---
+
+# Operator Overloading (cont.)
+
+## Friend Functions
+
+- A **friend function** is a function that **is not a member function**, but that still has access to the private members of the objects of a class
+- To declare a friend function, the function's prototype is placed in a class definition, preceded by the keyword `friend`
+
+```
+class point{
+
+	public:
+		//...
+		//FRIEND FUNCTIONS
+		friend istream& operator >>(istream& ins, point& target);
+
+	private:
+		//...
+};
+```
+
+- Even though the prototypes for friend functions appear in the class definition, **friends are not member functions**
+- Therefore, **it is not activated by a particular object of a class**
+- All of the information that the friend function manipulates must be present in its parameters
+- Friendship may be provided to any function, not just to operator functions
+- Friendship should be limited to functions that are written by the programmer who implements the class
+
+```
+#include <iostream>
+using namespace std;
+
+class Box{
+	double width;
+
+	public:
+		friend void printWidth(Box box);
+		void setWidth(double wid) {width = wid;};
+};
+
+void printWidth(Box box){
+	cout << "Width of box : " << box.width << endl;
+}
+
+int main(){
+	Box box;
+	box.setWidth(10.0);
+
+	printWidth(box);
+
+	return 0;
+}
+```
+
+---
+
+# The Standard Template Library (STL) and the Pair Class
+
+- It is important for you to understand how to build and test your own data structures
+- However, you'll find that a suitable data structure has already been built for you to use in an application
+- In C++, **a variety of container classes**, called the **Standard Template Library (STL)**, are available
+
+## The Pair Class
+
+- Each pair object **can hold two pieces of data**
+- Example: integer and a double number; or a char and a bool value; or even a couple of throttles
+
+```
+#include <utility>   //provides the pair class
+using namespace std; //The pair is part of the std namespace
+
+int main(){
+	pair<int, double> p;
+	p.first = 42;    //first is the member variable for the int piece
+	p.second = 9.25; //second is the member variable for the double
+	//...
+}
+```
+
+```
+template<class T1, class T2>
+struct pair;
+```
+
+- This class couples together a pair of values, which may be of different types (T1 and T2)
+- The individual values can be accessed through its **public members** `first` and `second`
+- The **data types of these two pieces are specified in the angle brackets**, as part of the object's declaration
+- We'll see more of these angle brackets later. They are called the **template instantiation**
+
+```
+template<class T1, class T2>
+pair<T1, T2> make_pair(T1 x, T2 y);
+```
+
+- Constructs a pair of object with its first element set to `x` and its second element set to `y`
+
+- Example:
+
+```
+#include <utility>  //std::pair
+#include <iostream> //std::cout
+
+int main(){
+	std::pair<int, int> foo;
+	std::pair<int, int> bar;
+
+	foo = std::make_pair(1, 2);
+	bar = std::make_pair(0.5, 'B'); //implicit conversion
+
+	std::cout << "foo: " << foo.first << ", " << foo.second << '\n';
+	std::cout << "bar: " << bar.first << ", " << bar.second << '\n';
+
+	return 0;
+}
+```
+
+- Output:
+
+```
+foo: 1, 2
+bar: 0, 66
+```
+
+- Note: 66 is the decimal ASCII number of 'B'
+
+- Another Example:
+
+```
+#include <utility>  //std::pair, std::make_pair
+#include <string>   //std::string
+#include <iostream> //std::cout
+
+int main(){
+	std::pair<std::string, int> university, myuniversity;
+
+	university = std::make_pair("SCU", 95053);
+
+	myuniversity = university;
+
+	std::cout << "My University: " << myuniversity.first << '\n';
+	std::cout << "My University Zip: " << myuniversity.second << '\n';
+	return 0;
+}
+```
+
+- Output:
+
+```
+My University: SCU
+My University Zip: 95053
+```
+
+---
+
+# Summary
+
+- Object-oriented programming (OOP) supports **information hiding** by placing data in packages called **objects**
+- Objects are implemented via **classes**
+- **Member functions** enable the manipulation of objects
+- An **Abstract Data Type (ADT)/data structure/class:** A new data type, together with the functions to manipulate the type
+	- The term **abstract** refers to the fact that we emphasize the abstract specification of **what has been provided, disassociated from any actual implementation**
+- Information hiding is provided by **private** member variables
+- Declaring a function as a **friend function** enables access to private members
+- A **constructor** is a member function that is automatically called to initialize a data structure
+- Using **namespace** avoids conflicts between different items with the same name
+- **Header file** includes documentation and class definition
+- **Implementation file** includes the implementation of the member functions
+- C++ provides three common kinds of parameters: **value parameters, reference parameters, const reference parameters**
+- C++ allow you to **overload operators** for your new data structures
+- Many built-in classes are provided by the **Standard Template Library**
+
+---
+
+# Data Structures and Other Objects Using C++
+
+## Container Classes
+
+- A **container class** is a data type that is capable of holding a collection of items
+
+### Bags
+
+- For the first example, think about a bag
+- Inside the bag are some numbers
+
+### Summary of the Bag Operations
+
+1. A bag can be put in its **initial state**, which is an empty bag
+2. Numbers can be **inserted** into the bag
+3. You may check how many **occurences** of a certain number are in the bag
+4. Numbers can be **removed** from the bag
+5. You can check **how many** numbers are in the bag
+
+### The Bag Class
+
+- C++ classes can be used to implement a container class such as a bag
+- The class definition includes:
+	- The heading of the definition
+	- A constructor prototype
+	- Prototypes for public member functions
+	- Private member variables
+
+```
+class bag{
+
+	public:
+		bag();
+		void insert(...);
+		void remove(...);
+		...and so on
+
+	private:
+		We'll look at private members later
+};
+```
+
+### Using the Bag in a Program
+
+- Here is typical code from a program that uses the new bag class:
+
+```
+bag ages;
+
+//Record the ages of three children
+ages.insert(4);
+ages.insert(8);
+ages.insert(4);
+```
+
+### The Header File and Implementation File
+
+- The programmer who writes the new bag class must write two files:
+	- `bag1.hxx`, a header file that contains documentation and the class definition
+	- `bag1.cxx`, an implementation file that contains the implementations of the bag's member functions
+
+### Documentation for the Bag Class
+
+- The documentation gives **prototypes and specifications** for the bag member functions
+- Specifications are written as **precondition/postcondition** contracts
+- Everything needed to **use** the bag class is included in this comment
+
+### The Bag's Class Definition
+
+- After the documentation, the header file has the class definition that we've seen before
+
+### The Implementation File
+
+- As with any class, the actual definitions of the member functions are placed in a separate implementation file
+- The **definitions** of the bag's member functions are in `bag1.cxx`
+
+### Implementation Details
+
+- The entries of a bag will be stored in the front part of an array, as shown in this example
+
+|[0]|[1]|[2]|[3]|...|
+|---|---|---|---|---|
+|4  |8  |4  |   |   |
+
+- We also need to keep track of how many numbers are in the bag
+	- An integer to keep track of the bag's size: `int size`
+
+### Bag: Private Members (1st Try)
+
+- One Solution:
+
+```
+class bag{
+
+	public:
+		...
+
+	private:
+		int data[20];
+		size_t count;
+};
+```
+
+- `size_t` is a non-negative integer, defined at the machine level
+
+### An Example of Calling Insert
+
+```
+void bag::insert(int new_entry)
+```
+
+- Before calling insert, we might have this bag b:
+	- `b.count: 2`
+	- `b.data: `
+
+|[0]|[1]|[2]|...|
+|---|---|---|---|
+|8  |4  |   |   |
+
+### Bag: Private Members (2nd Try)
+
+- A more flexible solution:
+
+```
+class bag{
+
+	public:
+		static const size_t CAPACITY = 20;
+
+	private:
+		int data[CAPACITY];
+		size_t count;
+};
+```
+
+### An Example of Calling Insert
+
+- We make a function call `b.insert(17)`
+	- What values will be in `b.data` and `b.count` after the member function finishes?
+	- After calling `b.insert(17)`, we will have this bag b:
+		- `b.count: 3`
+		- `b.data: `
+
+|[0]|[1]|[2]|...|
+|---|---|---|---|
+|8  |4  |17 |   |
+
+### Pseudocode for bag::insert
+
+1. `assert(size() < CAPACITY);`
+2. Place `new_entry` in the appropriate location of the data array
+3. Add one to the member variable count
+
+```
+data[count] = new_entry;
+++count;
+
+//alternatively:
+data[count++] = new_entry;
+```
+
+### Other Kinds of Bags
+
+- In this example, we have implemented a bag containing **integers**
+- But we could have had a bag of **float numbers**, a bag of **characters**, a bag of **strings**...
+
+### A typedef for value_type
+
+- Instead of forcing the bag to always include integers, we use the name `value_type` for the data type of the items in a bag
+
+```
+class bag{
+
+	public:
+		typedef int value_type;
+		...
+};
+```
+
+- Bag functions can use the name `value_type` as a synonym for the data type `int`
+- Other functions, which are not bag member functions, can use the name `bag::value_type` as the type of the items in a bag
+
+### Implementation: A typedef for size_type
+
+- In addition to the `value_type`, our bag defines another data type that can be used for variables that keep track of how many items are in a bag
+- This type will be called `size_type`, with its definition near the top of the bag class definition:
+
+```
+class <Name of the class>{
+
+	public:
+		typedef <A data type such as int or double> <A new name>;
+		typedef <an integer type of some kind> size_type;
+		...
+};
+```
+
+### Specification - The std::size_t Data Type
+
+- The data type `size_t` is an integer data type that can **hold only non-negative numbers**
+- C++ implementation guarantees that the values of the `size_t` type are sufficient to hold the size of any variable that can be declared on your machine
+
+```
+class bag{
+
+	public:
+		typedef int value_type;
+		typedef std::size_t size_type;
+		...
+};
+```
+
+- To use `size_t` in a header file, we must include `cstdlib` and use the full name `std::size_t`
+- The actual size of `size_t` is platform-dependent: On 32-bit and 64-bit systems `size_t` will take 32 and 64 bits, respectively
+
+### The Header File and Implementation File
+
+- The programmer who writes the new bag class must write two files:
+	- `bag1.hpp`, a header file that contains documentation and the class definition
+	- `bag1.cxx`, an implementation file that contains the implementations of the bag's member functions
+
+```
+//FILE: bag1.h
+//CLASS PROVIDED: bag (part of the namespace scu_coen79_3)
+
+//TYPEDEF and MEMBER CONSTANTS for the bag class:
+//typedef int value_type
+//bag::value_type is the data type of the items in the bag. It may be any of the C++ built-in types (int, char, etc.), or a class with a default constructor, an assignment operator, and operators to test for equality (x == y) and non-equality (x != y)
+
+//typedef size_t size_type
+//bag::size_type is the data type of any variable that keeps track of how many items are in a bag
+
+//static const size_type CAPACITY = 20
+//bag::CAPACITY is the maximum number of items that a bag can hold
+
+//CONSTRUCTOR for the bag class:
+//bag()
+//Postcondition: The bag has been initialized as an empty bag
+
+//MODIFICATION MEMBER FUNCTIONS for the bag class:
+//size_type erase(const value_type& target);
+//Postcondition: All copies of target have been removed from the bag
+//Postcondition: The return value is the number of copies removed (which could be zero)
+
+//bool erase_one(const value_type& target)
+//Postcondition: If target was in the bag, then one copy has been removed; otherwise the bag is unchanged
+//Postcondition: A true return value indicates that one copy was removed; false indicates that nothing was removed
+
+//void insert(const value_type& entry)
+//Precondition:  size() < CAPACITY
+//Postcondition: A new copy of entry has been added to the bag
+
+//void operator +=(const bag& addend)
+//Precondition:  size() + addend.size() <= CAPACITY
+//Postcondition: Each item in addend has been added to this bag
+
+//CONSTANT MEMBER FUNCTIONS for the bag class:
+//size_type size() const
+//Postcondition: The return value is the total number of items in the bag
+
+//size_type count(const value_type& target) const
+//Postcondition: The return value is number of times target is in the bag
+
+//NONMEMBER FUNCTIONS for the bag class:
+//bag operator +(const bag& b1, const bag& b2)
+//Precondition:  b1.size() + b2.size() <= bag::CAPACITY
+//Postcondition: The bag returned is the union of b1 and b2
+
+//VALUE SEMANTICS for the bag class:
+//Assignments and the copy constructor may be used with bag objects
+```
+
+### The Invariant of a Class
+
+- We need to state **how the member variables of the bag class are used** to represent a bag of items
+- There are two rules for our bag implementation
+	- The number of items in the bag is stored in the member variable `used`
+	- For an empty bag, we do not care what is stored in any of `data`; for a non-empty bag, the items in the bag are stored in `data[0]` through `data[used-1]`, and we don't care what is stored in the rest of data
+- The rules that dictate how the member variables of a class represent a value (such as a bag of items) are called the **invariant** of the class
+- With the exception of the constructors, each function depends on the invariant being valid when the function is called
+- Check out the wikipedia article on class invariant
+
+### += Operator
+
+```
+void bag::operator +=(const bag& addend){
+	size_type i; //an array index
+
+	assert(size() + addend.size() <= CAPACITY);
+	for(i = 0; i < addend.used; ++i){
+		data[used] = addend.data[i];
+		++used;
+	}
+}
+```
+
+- If we activate `b+=b` then the private member variable used is the same variable as `addend.used`
+- Each iteration of the loop adds 1 to `used`, and hence `addend.used` is also increasing, and the loop never ends
+- What is the solution?
+
+### += Correct Implementation
+
+- The implementation uses the `copy` function from the `<algorithm>` Standard Library
+
+```
+void bag::operator +=(const bag& addend){
+
+	assert(size() + addend.size() <= CAPACITY);
+	copy(addend.data, addend.data + addend.used, data + used);
+	used += addend.used;
+}
+```
+
+### Time Analysis for the Bag Functions
+
+|Operation          |Time Analysis                                   |
+|-------------------|------------------------------------------------|
+|Default constructor|O(1) (Constant time)                            |
+|count              |O(n) (n is the size of the bag)                 |
+|erase_one          |O(n) (Linear time)                              |
+|erase              |O(n) (Linear time)                              |
+|+= another bag     |O(n) (n is the size of the other bag)           |
+|b1 + b2            |O(n1 + n2) (n1 and n2 are the sizes of the bags)|
+|insert             |O(1) (Constant time)                            |
+|size               |O(1) (Constant time)                            |
+
+- `erase_one` sometimes requires fewer than n x (number of statements in the loop); however, this does not change the fact that the function is O(n)
+	- In the worst case, the loop does execute a full `n` iterations, therefore the correct time analysis is no better than O(n)
+- Several of the other bag functions do not contain any loops at all, and do not call any functions with loops
+	- Example, when an item is added to a bag, the new item is always placed at the end of the array
+
+## Summary
+
+- A **container class** is a class where each object contains a collection of items
+	- Examples: Bags and sequences classes
+- `typedef` statement makes it easy to alter the data type of the underlying items
+- The simplest implementations of container classes use a **partially filled array**, which requires each object to have at least two member variables:
+	- The array
+	- A variable to keep track of how much of the array is being used
+- At the top of the implementation file: When you design a class, always make an explicit statement of the rules (**invariant of the class**) that dictate how the member variables are used