summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorlshprung <lshprung@yahoo.com>2021-01-26 10:00:52 -0800
committerlshprung <lshprung@yahoo.com>2021-01-26 10:00:52 -0800
commitce4ab12872270cda61a5c72e8420ddb730cd4c29 (patch)
treea8ab6e2d585eaa35b80eced6190cc6a53ef4990d
parenta8a1645a8d6ca451d620b942dd5744705e85af0b (diff)
Post-class 01/26
-rw-r--r--01-21.md5
-rw-r--r--01-26.md287
-rw-r--r--01-26_1.pngbin0 -> 10126 bytes
-rw-r--r--01-26_2.pngbin0 -> 22271 bytes
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
Binary files differ
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
Binary files differ