Post-class 01/26

4 files changed, 292 insertions, 0 deletions

diff --git a/01-21.md b/01-21.md
index 7221a67..2f1c4e2 100644
--- a/01-21.md
+++ b/01-21.md
@@ -320,6 +320,7 @@ for(i = 0; i < used; ++i){
 - 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
+- This class would be good to use if you need to do a lot of insertion, and not as many removals
 
 ---
 
@@ -332,3 +333,7 @@ for(i = 0; i < used; ++i){
 	- 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
+
+---
+
+[01/26 ->](01-26.md)
diff --git a/01-26.md b/01-26.md
new file mode 100644
index 0000000..da4652c
--- /dev/null
+++ b/01-26.md
@@ -0,0 +1,287 @@
+[\<- 01/21](01-21.md)
+
+---
+
+# Pointers and Arrays
+
+### Introduction
+
+- The container classes' capacity is declared as a **constant** in the class definition (`bag::CAPACITY`)
+- If we need bigger bages, then we can increase the constant and recompile the code
+- What if a program needs one large bag and many small bags?
+- All the bags will be of the same size!
+
+### Solution: Dynamic Structures
+
+- Provide control over the size of each bag, independent of the other bags
+- This control can come from **dynamic arrays:**
+	- Arrays whose size is determined while a program is **actually running (not at compile time)**
+
+## Pointers and Dynamic Memory
+
+### Pointers
+
+- Pointer is the memory address of a variable
+- The numbers labeling each byte are called the **memory addresses**
+- When a variable occupies several adjacent bytes, the memory address of the first byte is called the memory address of the variable
+- The address of a variable is called a **pointer**
+
+**Pointer variable** must be declared by placing an **asterisk** before the pointer variable's name:
+
+```
+double *my_first_ptr;
+```
+
+- `my_first_ptr` can hold the memory address of a double variable
+
+### Another Example
+
+```
+int *example_ptr;
+int i;
+
+example_ptr = &i;
+```
+
+- **& operator**: Is called the **address operator**, and provides the address of a variable
+
+### Pointer Variables
+
+- In C++ the variable pointed to by `example_ptr` is written `*example_ptr`
+- This is the same asterisk notation that we used to declare `*example_ptr`, **but now it has yet another meaning**
+- When the asterisk is used in this way, it is called the **dereferencing operator**, and the pointer variable is said to be **dereferenced**
+
+### Pointers and Assignment Operator
+
+```
+int i = 42;
+int *p1;
+int *p2;
+
+p1 = &i;
+p2 = &i;
+
+cout << *p1 << endl;
+cout << *p2 << endl;
+```
+
+![diagram](01-26_1.png)
+
+### Dynamic Variables and the new Operator
+
+- Real power of pointers arises when pointers are used with special kinds of variables called **dynamically allocated variables**, or more simply, **dynamic variables**
+- Dynamic variables are like ordinary variables, with two important differences:
+	- **They are not declared**
+	- **They are created during the execution of a program**
+- To create a dynamic variable while a program is running, C++ programs use an operator called `new` (declared in the global namespace)
+
+### Example
+
+```
+double *d_ptr;
+d_ptr = new double;
+```
+
+- The creation of the new dynamic variables is called **memory allocation** and the memory is **dynamic memory**
+- We may say that "`d_ptr` points to a newly allocated double variable from dynamic memory"
+- `new` operator creates a new dynamic variable of type double and returns a pointer to this new dynamic variable
+- How the memory looks like after these statements?
+
+### Dynamic Behavior
+
+- The array version of `new` is particularly useful because the number of array components can be calculated while the program is running
+- If the data type of the **array** component is a **class**, then the **default constructor** is used to initialize all components of the dynamic array
+
+```
+fruit *f_ptr;
+f_ptr = new fruit[100];
+```
+
+- The number of components can depend on factors such as user input
+- This is **dynamic behavior** - behavior that is determined when a program is running
+
+### "new" to Allocate Dynamic Arrays
+
+- `new` can allocate an entire array at once, the number of array components is listed in square brackets, immediately after the component data type
+- When `new` allocates an entire array, it actually **returns a pointer to the first component of the array**
+
+```
+doube *d_ptr;
+d_ptr = new double[10];
+```
+
+### Address Space
+
+- Divides address space into logical segments
+	- Each segment corresponds to logical entity in address space
+		- code, stack, heap
+- Each segment can be independently:
+	- be placed separately in physical memory
+	- grow and shrink
+	- be protected
+		- separate read/write/execute protection bits
+
+### Address Space Segmentation
+
+![diagram](01-26_2.md)
+
+### Stack Memory
+
+- A special region of memory that stores temporary variables created by each function (including the `main()` function)
+	- When a function declares a new variable, it is "pushed" onto the stack
+	- When a function exits, all of the variables pushed onto the stack by that function, are freed
+	- Once a stack variable is freed, that region of memory becomes available for other stack variables
+- Stack variables only exist while the function that created them is running
+- Advantage: There is no need to manage memory yourself, variables are allocated and freed automatically
+
+### Heap Memory
+
+- A region that is not managed automatically for you, and is not tightly managed by the CPU
+- Once you have allocated memory on the heap, you are responsible for releasing that memory
+	- If you fail to do this, your program will have what is known as a **memory leak**
+- When you use the `new` operator to allocate memory, this memory is allocated in the program's heap segment
+- Scope:
+	- Variables created on the heap are accessible by any function, anywhere in your program (unlike stack)
+	- **Heap variables are essentially global in scope**
+
+### "delete" Operator
+
+- The size of the heap varies from one computer to another, it could be just a few thousand bytes or more than a billion
+- Even with small programs, **it is an efficient practice to release any heap memory that is no longer needed**
+- The `delete` operator is used to return the memory of a dynamic variable back to the heap where it can be reused for more dynamic variables
+- Example:
+
+```
+int *example_ptr;
+example_ptr = new_int;
+...
+delete example_ptr;
+```
+
+- `delete` operator can also free a dynamic array of components
+- To free an entire array, the array brackets `[]` are placed after the word `delete`
+
+```
+int *example_ptr;
+example_ptr = new int[50];
+...
+delete [] example_ptr;
+```
+
+### Stack Overflow
+
+**Stack overflow** is the result of:
+- Allocating too many variables on the stack
+- Making too many nested function valls
+	- Example: Where function A calls function B calls function C calls function D...
+- Stack overflow generally causes a program to crash
+
+```
+int main(){
+	int array[100000000];
+	return 0;
+}
+```
+
+- Beyond good programming practices, static and dynamic testing, there's not much you can do
+
+### Heap and "bad_alloc" Exception
+
+- Even the largest heap can be exhausted by allocating too many dynamic variables, when the heap runs out of room, the `new` operator fails
+- The `new` operator usually indicates failure by throwing an exception called the `bad_alloc` exception
+- Normally, an exception causes an error message to be printed and the program to halt
+- Alternatively, a programmer can "catch" an exception and try to fix the problem
+	- **Exceptions** provide a way to reacto to exceptional circumstances (like runtime errors) in programs
+	- When an exception is thrown, control is transferred to its **handler**
+
+### Example 1
+
+```
+#include <iostream>
+using namespace std;
+
+int main(){
+	int input;
+	cout << "what is the input? " << '\n';
+	cin >> input;
+
+	try{
+		if(input < 20) cout << "nice number!" << '\n';
+		else throw 20;
+	}
+
+	catch(int e){
+		cout << "An exception occurred. Exception#: " << e << '\n';
+	}
+
+	return 0;
+}
+```
+
+- `Terminal: what is the input? 20`
+	- `An exception occurred. Exception#: 20`
+
+### Example 2
+
+```
+#include <iostream> //std::cout
+#include <new>      //std::bad_alloc
+
+int main(){
+
+	try{
+		int *myarray = new int[1000000];
+	}
+
+	catch(std::bad_alloc& ba){
+		std::cerr << "bad_alloc caught: " << ba.what() << '\n';
+	}
+
+	return 0;
+}
+```
+
+- If memory allocation is unsuccessful, then the output will be:
+	- `bad_alloc caught: bad allocation`
+
+---
+
+### Quiz
+
+Write a program that read a list of numbers and writes it back to screen
+
+1. The number of items is known at the beginning of time
+
+```
+void program1(int length){
+	int arr[length];
+	int i;
+
+	for(i = 0; i < length; i++){
+		std::cout << "Enter a number for index " << i << ": ";
+		std::cin >> arr[i];
+	}
+
+	for(i = 0; i < length; i++){
+		std::cout << arr[i];
+	}
+}
+```
+
+2. The number of items is unknown while you develop the program
+
+```
+void program2(){
+	int *p;
+	int length;
+	int i;
+
+	cout << "How many? ";
+	cin >> length;
+
+	p = new (nothrow)int[length];
+
+	...
+```
+
+- `nothrow` is a standard function to prevent a crash if `p` is dereferenced and `length` is 0
diff --git a/01-26_1.png b/01-26_1.png
new file mode 100644
index 0000000..c866dbb
--- /dev/null
+++ b/01-26_1.png
diff --git a/01-26_2.png b/01-26_2.png
new file mode 100644
index 0000000..ada968e
--- /dev/null
+++ b/01-26_2.png