diff options
| -rw-r--r-- | 01-21.md | 5 | ||||
| -rw-r--r-- | 01-26.md | 287 | ||||
| -rw-r--r-- | 01-26_1.png | bin | 0 -> 10126 bytes | |||
| -rw-r--r-- | 01-26_2.png | bin | 0 -> 22271 bytes |
4 files changed, 292 insertions, 0 deletions
@@ -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; +``` + + + +### 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 + + + +### 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 Binary files differnew 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 Binary files differnew file mode 100644 index 0000000..ada968e --- /dev/null +++ b/01-26_2.png |
