Dynamic Memory Management
COSC1076 Week 03
Problem Solving
Copyright By PowCoder代写 加微信 powcoder
Problem Solving
Problem Solving is about find software solutions to problems • It’s an obvious statement, but what does it actually mean?
Software Design
Implementation
Week 03 | Dynamic Memory Management COSC1076
A typedef is a user-defined type that is a synonym for another type
Generally, typedefs are used for: • Program Clarity
• Abstraction
• Truncation
New Type name
Existing Type
Week 03 | Dynamic Memory Management COSC1076
Pointers & References
The most important topic in the course!
Computer Memory
Each byte has a unique address
• This is how a computer can find a piece of memory
• Addresses are stored in hex, and adjacent memory locations are sequential
Pointer Name Memory
character:
0x0004fca4
0x0004fca8
0x0004fca9
Week 03 | Dynamic Memory Management COSC1076
Pointers & References
A reference type is denoted in syntax using a ‘&’
int value = 7;
int* ptr = &value;
int& ref = value;
ptr = NULL;
int* ptr int value int& ref
Week 03 | Dynamic Memory Management COSC1076
Classes Declaration
C++ Class Declaration
class Example {
Example(int value);
Public, Protected, & Private Scopes
void publicMethod(); protected:
Class Name
Constructor Method
Fields can be arrays or other classes
int protectedVariable;
int protectedMethod(double param);
double privateArray[LENGTH];
void privateMethod(int* ptr, double& ref);
Don’t forget ‘;’
Week 03 | Dynamic Memory Management COSC1076
Class Method Definitions
C++ Class method definitions provide the implementation of each method • Definitions provided individually
• Scope is not relevant to the definition
• The Class name creates a namespace!
Return Type
Class Name Method Name Parameters
Namespace separator
int Example::protectedMethod(double param) {
Week 03 | Dynamic Memory Management COSC1076
Class Initialisation
Objects (variables of a given class) can be created like any other variable • Does not need to be “new’ed”
The constructor is called when defining the variable
• Use bracket notation to provide the parameters to a class object
No return type Constructor Parameter Object definition Example ex(10);
variable/object Constructor Class is a type name Parameters
Example::Example(int value) { protectedVariable = value;
Week 03 | Dynamic Memory Management COSC1076
Access Class Members
Class members (variables and methods) are accessed using dot ‘.’ Syntax For pointers to object, arrow syntax ‘->’ is a shortcut for dereferencing
Example ex(10);
ex.publicMethod();
Example* ptrEx = &ex; (*ex).publicMethod();
ex->publicMethod();
Class members can only be accessed from the correct scope
• Public members are always accessible
• Private members are only accessible only from within the class
• Protected members can be accessed from this class and all children
Week 03 | Dynamic Memory Management COSC1076
“this” Pointer
Like in Java, C++ Classes have a special keyword this
• It gives a pointer to the current object of the class
• Using the keyword, all methods and fields of the class can be accessed • Works in constructors and methods
Example::Example(int value) {
this->protectedVariable = value;
int Example::protectedMethod(double param) {
this->protectedVariable = param;
Week 03 | Dynamic Memory Management COSC1076
Class & Functions
Pass classes to functions either by • Pointer
• Reference
Passing the class directly: • Is possible
– Requires a special constructor (called a copy constructor) – We will cover this in future week(s)
Week 03 | Dynamic Memory Management COSC1076
Arrays are …. pointers?
Arrays in Memory
Unsurprisingly in memory, an array is a sequence of adjacent memory cells • The address of each array location is based on the arrays type
int array[10]
0x0004fca4
0x0004fca8
0x0004fcab
Week 03 | Dynamic Memory Management COSC1076
Arrays in Memory
How does an array actually work?
• That is, how does a compiler or program access the correct cell in memory? • Static access:
• Dynamic access:
int array[10] = {1};
array[0] = 2;
int i = 2;
array[i] = -1;
Week 03 | Dynamic Memory Management COSC1076
Arrays as Pointers
An array is actually an abstraction for using pointers!
The actual array “variable” is a pointer to the first element of the array
The square-bracket lookup notation is short-hand for: • Go to the memory location of the array
• Go to the ‘ith’ memory location from this
• Dereference that memory address
Week 03 | Dynamic Memory Management COSC1076
Arrays as Pointers
In C/C++, a pointer type is another way to represent an array
int array[10]
int* array;
• The first version actually set’s aside the memory for the array
• The second can be interpreted as an array, but only sets aside memory for a single pointer
The “pointer form” of an array is often used in functions and methods
Week 03 | Dynamic Memory Management COSC1076
Arrays with Functions
Arrays being a pointer is the reason why arrays are passed-by-reference
• They are actually “pass-by-value on the pointer to the start of the array”
void foo(int array[]);
The “pointer form” of an array is often used in functions and methods
void foo(int* array);
• Both of these function prototypes achieve the same functionality
Week 03 | Dynamic Memory Management COSC1076
Arrays are different** (sort-of)
• Arrays (as parameters) operate through pass-by-reference • The actual array is passed.
– Changing a value in the array within the called function modifies the value from the calling function
Calling Function
Called Function
pass-by-reference
** As we will see next week:
Under-the-hood an array is implemented using a pointer
The pointer is copied (pass-by-value)
The high-level effect to the programmer is pass-by-reference
Week 03 | Dynamic Memory Management COSC1076
Multi-Dimensional Arrays
Multi-dimensional arrays are “pointers-to-pointers” • They use multiple star’s for short-hand
int array2D[ROWS][COLS];
int** array2D;
Week 03 | Dynamic Memory Management COSC1076
Multi-Dimensional Arrays
The best way to think of them, is as an “array-of-arrays” • At the first layer, is an array
• Each element of this is another array
int array2D[ROWS][COLS]; array2D:
Week 03 | Dynamic Memory Management COSC1076
Multi-File Programs
File Types
C/C++ has two types of files: • Header files (.h / .hpp)
• Source files (c.pp)
Week 03 | Dynamic Memory Management COSC1076
Header Files
Header files contain definitions, such as • Function prototypes
• Class descriptions
• Typedef’s
• Common #define’s
Header files do not contain any code implementation
The purpose of the header files is to describe to source files all of the information that is required in order to implement some part of the code
Week 03 | Dynamic Memory Management COSC1076
Source Files
Code files have source code definitions / implementations
• In a single combined program, every function or class method may only have a single implementation
To successfully provide implementations, the code must be given all necessary declarations to fully describe all types and classes that are being used
• Definitions in header files are included in the code file
#include “header.h” – For local header files, use double-quotes
– Use relative-path to the header file from the code file
Week 03 | Dynamic Memory Management COSC1076
Multiple Includes
What happens if a header file in included multiple times? • Can create naming errors re-declaration errors.
Two solutions
1. Be careful about what files are included, but this quickly becomes infeasible with long include chains
2. Use pre-processor commands
Week 03 | Dynamic Memory Management COSC1076
#ifdef / #ifndef / #endif
The pre-processor can be used to see if a name as been #define’d • #ifdef – check if a definition exists
• #ifndef – check if a definition does not exist
• #endif – Close a #if check
Any code between a #if check will only be included if the check passes • If the check does not pass, the code is essentially ignored
Typical pattern for a header file:
/* Header file implementation */ #endif // TERM_FOR_HEADER_FILE
#ifndef TERM_FOR_HEADER_FILE
#define TERM_FOR_HEADER_FILE
Week 03 | Dynamic Memory Management COSC1076
C/C++ Compilation Process
C++ Source File (.cpp)
Pre-processor Compiler Assembler File (.s) Object File (.o) Executable
Week 03 | Dynamic Memory Management
C/C++ Preprocessor
Prepare source code files for actual compilation Process ‘#’ pre-preprocessor directives
• Process#includestatements
– locates and includes header files
• Process#definestatements – find-and-replace
• Process#ifdefstatements – will see later
• Process#pragmastatements
– compiler specific directive, not used in this course
Week 03 | Dynamic Memory Management COSC1076
Program Memory Management
How does a program manage memory?
We have informally discussed things like:
• The program “setting aside memory”
• Declaring a variable, “creates memory”
• Seen array overflow, that is, “reading beyond the end of an array”
• Mentioned that the “operating system does stuff”
The question, is what is happening?
Application
Operating System
Hardware/CPU
Week 03 | Dynamic Memory Management COSC1076
Application Structure
There are two general components to an application/program that we are concerned with:
• Program code loaded into computer memory
• Allocated memory for storing program data, such as
– Variables
– Function parameters
– Program control information
Week 03 | Dynamic Memory Management COSC1076
Program Code
Each line of code is converted into assembly instructions
An assembly instruction is a single operation that the CPU can execute
To run a program, the assembly instructions are loaded into memory
• Thus, every instruction has an associated memory address
• The operating system uses an instruction pointer (memory address) to track the instruction in a program that it is up to
Instruction Pointer
JUMP 0x004a
Week 03 | Dynamic Memory Management COSC1076
Memory Structure
In a typical program, memory is managed in two forms • Automatic memory allocation
• Dynamic, programmer controlled, memory allocation
Automatic memory allocation is managed through the programming language complier (C/C++) or interpreter (Java)
• The typical method for this is the Program (or Call) Stack
Dynamic memory allocation, is maintained by the programmer through the
programming language
• This is typically done on the Heap (or Free Store)
Operating Systems and CPUs provide
Week 03 | Dynamic Memory Management COSC1076
Program/Call Stack
The C++ compiler automatically handles allocating and de-allocating of memory for variables and function calls.
• The compiler generates CPU instructions for memory management • A data structure called a stack
In the stack
• As memory is required, a block (of the correct size) is allocated by being
pushed onto the stack
• Once memory is no-longer required, blocks are de-allocated by being
popped off the stack
• This forms an ordered structure, using FILO (first-in, last-out)
• That is, the first allocated block is the last to be de-allocated
Week 03 | Dynamic Memory Management COSC1076
Program/Call Stack
A stack is used, because of how memory is allocated
Lowest address
Highest address
Bottom of stack (main)
Variables (function 2)
Return address (function 2)
Memory allocation has two components
1. Variable allocation 2. Function call
Parameters (function 2)
Return Value (function 2)
Variables (function 1)
Return address (function 1)
Parameters (function 1)
Return Value (function 1)
Variables (of main)
Week 03 | Dynamic Memory Management COSC1076
Program/Call Stack – Local Variables
int main (void) {
int a = 7; int b = 8; int c = 9;
0x00….. (&a)
int d = 10;
int array[2] = {11, 12};
int* ptr = &a;
Bottom of stack (main)
return EXIT_SUCCESS;
Week 03 | Dynamic Memory Management COSC1076
Program/Call Stack – Scoping
int main (void) {
int array[2] = {11, 12};
for(int i = 0; i < 2; ++i)
cout << array[i] << endl;
int a = 10;
return EXIT_SUCCESS;
Bottom of stack (main)
Week 03 | Dynamic Memory Management COSC1076
Program/Call Stack - Scoping
int main (void) {
int array[2] = {11, 12};
for(int i = 0; i < 2; ++i)
cout << array[i] << endl;
int a = 10;
Bottom of stack (main)
return EXIT_SUCCESS;
Week 03 | Dynamic Memory Management COSC1076
Program/Call Stack - Scoping
int main (void) {
int array[2] = {11, 12};
for(int i = 0; i < 2; ++i)
cout << array[i] << endl;
int a = 10;
Bottom of stack (main)
return EXIT_SUCCESS;
Week 03 | Dynamic Memory Management COSC1076
Program/Call Stack - Scoping
int main (void) {
int array[2] = {11, 12};
for(int i = 0; i < 2; ++i)
cout << array[i] << endl;
int a = 10;
Bottom of stack (main)
return EXIT_SUCCESS;
Week 03 | Dynamic Memory Management COSC1076
Program/Call Stack - Function Call
int main (void) {
int a = 7;
int b = 0;
b = foo(a);
return EXIT_SUCCESS;
int foo(int x) {
int y = 3;
return x + y;
Bottom of stack (main)
Week 03 | Dynamic Memory Management COSC1076
Program/Call Stack - Function Call
int main (void) {
int a = 7;
int b = 0;
b = foo(a);
y ret addr
x ret val b
return EXIT_SUCCESS;
0x001a... (return to main)
int foo(int x) {
int y = 3;
return x + y;
Bottom of stack (main)
Week 03 | Dynamic Memory Management COSC1076
Program/Call Stack - Function Call
int main (void) {
int a = 7;
int b = 0;
b = foo(a);
y ret addr
x ret val b
return EXIT_SUCCESS;
0x001a... (return to main)
int foo(int x) {
int y = 3;
return x + y;
Bottom of stack (main)
Week 03 | Dynamic Memory Management COSC1076
Program/Call Stack - Function Call
int main (void) {
int a = 7;
int b = 0;
b = foo(a);
y ret addr
x ret val b
return EXIT_SUCCESS;
0x001a... (return to main)
Bottom of stack (main)
int foo(int x) {
int y = 3;
return x + y;
Week 03 | Dynamic Memory Management COSC1076
Program/Call Stack - Function Call
int main (void) {
int a = 7;
int b = 0;
b = foo(a);
y ret addr
x ret val b
return EXIT_SUCCESS;
0x001a... (return to main)
int foo(int x) {
Bottom of stack (main)
int y = 3;
return x + y;
Week 03 | Dynamic Memory Management COSC1076
Program/Call Stack
The operating system determines and manages the location of the program stack in physical memory. The OS may
• Limit the total size of the stack
• Randomly position the stack
• Clear (set to zero) all stack memory locations
Week 03 | Dynamic Memory Management COSC1076
Heap (Free Store)
The programmer manages the allocation and de-allocation of memory on the
In Java, objects are allocated on the heap
Object obj = new Object();
• The “new” keyword creates the object • The object is stored on the heap
Week 03 | Dynamic Memory Management COSC1076
Heap - De-allocation
Any memory that is allocated, should be de-allocated
• Also called “freeing” or “deleting” memory
• By de-allocating memory, a program can re-use it for another purpose
• If memory is not “cleaned-up", the Operating System is not aware that memory is no longer needed
- Any new memory that a program requires, must be allocated elsewhere
Java has automated garbage collection, so the programmer does not have to be concerned with de-allocating the memory
• In C++, You (the programmer) MUST de-allocate all memory
Only when a program is terminated, will the operating system reclaim all memory that was not de-allocated
Week 03 | Dynamic Memory Management COSC1076
Call Stack vs Heap
The operating system determines the size and location in physical memory of: • Program Store
• Call Stack
Generally, the heap is significantly larger than the call stack
• The call stack should be used to store small, short-lived, scoped data
• The heap is good for storing data that is not bounded within the scope of a single function or method
• Objects are placed on the Heap
• Local variable are placed on the stack
In C++, we will operate with a similar model
Week 03 | Dynamic Memory Management COSC1076
Dynamic Memory Management
Dynamic Memory Management
Dynamic Memory Management is about managing memory on the heap The key principle: Everything you create, you must delete
Week 03 | Dynamic Memory Management COSC1076
Allocating Memory on the Heap
In C/C++ memory is allocated on the heap using the ‘new’ keyword
int* a = new int;
Returns a “new” memory Type of memory
pointer to generate
• The “new” returns a pointer to the allocated memory • The allocated memory is not initialised
- This can be done separately
• The compiler/OS will set aside enough memory based on the type
Week 03 | Dynamic Memory Management COSC1076
Allocating Memory on the Heap
The allocated memory may also be initialised inline, using “bracket” notation
int* a = new int(7); Initialise
• Use of this is dependent on the type
- Some types do not support inline allocation and initialisation.
• As with all other memory, the allocated memory must initialised!
Week 03 | Dynamic Memory Management COSC1076
Deleting Memory on the Heap
Memory is de-allocated using the “delete” keyword
“delete” memory delete on pointer
• Delete is called on the pointer (not dereference)
• Once a pointer has been deleted, that memory location cannot be used • Best practice is to set any deleted pointer to NULL
Week 03 | Dynamic Memory Management COSC1076
Issues with Memory Management
Memory Leaks
• If you loose a pointer to any allocated memory, you can’t get it back • That memory is lost, and cannot be re-allocated
• The only way to get the memory back is to terminate the program
• This is the largest cause of programs using up too much memory
Double delete
• Deleting the same location twice, results in a memory error
Delete on NULL
• Not possible
• May cause an error on some operating systems - so be careful!
Week 03 | Dynamic Memory Management COSC1076
Primitive Types
All primitive types can be allocated using the type keyword.
int* a = new int;
double* d = new double;
char* c = new char;
Primitive types can be initialised inline.
int* a = new int(7);
double* d = new double(7.5);
char* c = new char(‘a’);
Delete operates as already shown
Week 03 | Dynamic Memory Management COSC1076
Pointers to other Types
Pointers to types can be allocated
int** a = new int*;
double** d = new double*;
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com