IT 279: Algorithms and Data Structures, Week 1 recap

What is a memory leak?

- Losing track of dynamically allocated memory so that it is not freed or deallocated.

 

What is a dangling pointer?

- A pointer that points at memory that has already been freed (or deallocated).

 

What is the purpose of a destructor in C++?

- To free any dynamically allocated memory that the object uses before the object itself is deallocated.

 

 

Recursion

int func1(int num)
{
	if(num < 5)
    	return 12;
    else
    	return func1(num-1)+3;
}

 

func1(5) = func1(4) + 3 

func1(4) = 12

func1(5) = 15

 

func1(6) = func1(5) + 3 = 18

 

 

 

Greatest Common Divisor(GCD) using a recursive algorithm

#include <iostream>

int gcd(int num1, int num2) {
	if (num2 == 0) {
    	return num1;
    }
    return gcd(num2, num1 % num2);
}

int main() {
	std::cout << "GCD of 14 and 28 is: " << gcd(14, 28) << std::endl;
    return 0;
}

 

Dynamic Classes

 

'This' is a pointer to the current object instance, that the method belongs to.

 

new in C++

1. Allocates a space for a data item in the heap.

2. Returns a pointer to that item.

3. Can be used with any type, not just classes.

 

int* myPtr = new int;

string* myStrPtr = new string("Hello");

 

Dynamic arrays

int* scores = new int[10];

string* names = new string[24];

 

In each case allocates space for as many items as indicated.

Also, they can be initialized:

int* scores = new int[10]{4, 5, 6};

 

Managing dynamic arrays

Need a pointer to the data

Need the capacity/size of the array

If the array may not be full, we need the number of items.

 

Cleaning up

For statically allocated variables, this is not an issue.

No garbage collector in C++.

We must free the memory, using delete.

 

How to clean up?

delete myPtr; // for single items

delete [] scores; // for dynamic arrays

 

delete does not change the value of the pointer/the target.

Only tells the system that the memory is no longer in use so that it can be reallocated.

 

Why use delete?

Memory stays in use/unavailable.

int *intPtr = new int;
*intPtr = 5;
intPtr = new int;
*intPtr = 10;

The first intPtr still hold 5.

This situation is called Memory leak.

 

Dangling pointers

Using a pointer that points to deleted memory

Calling delete on a pointer that points to a memory that has already been deleted.

This can be avoided by setting the pointer to NULL immediately after we free them.

 

Necessary Methods

The destructor

The copy constructor

The assignment operator (also called the copy assignment operator)

 

Why the Destructors?

Called when the object is destroyed

~Classname()
{
	delete dynamicData;
}

The deletion code needs to correspond to the dynamic data.

 

Copy constructors

Passing as parameter:

Vector<MyClass> myCollection;
MyClass myObject;
myCollection.push_back(myObject);

Explicit copy constructor call:

MyClass myObject = new MyClass(myOldObject);

Declaration-initialization:

MyClass myObject = myOldObject;

 

Correct copy constructor

Needs to allocate the memory and copy ALL of the data

className::className(const ClassName& orig)
{
    this->staticData = orig.staticData;
    this->allocatedData = new type;
    *(this->allocatedData) = *(orig.allocatedData);
}

 

Copying the data

Depends on the dynamic data that is being copied.

The example copies one item.

For an array, need to run a for loop or use an appropriate library call.

For linked list or tree, need to go through and copy all of the nodes.

 

The Assignment Operator

object2 = object1;

Both objects already exist.

Then,

Delete existing memory (like destructor)

Allocated the right new memory and copy all the data (like copy constructor)

return *this; (all assignment operators return the assigned value)

 

Self-Assignment

obejct1 = object2

Serious problem occurs if deletion happens

 

Being Smart

We should not call the destructor.

We should not call the copy constructor.

We should avoid code duplication.

Solution: Private helper methods.

 

Helper methods

Create a private copy method.

Copy constructor contains only a call to that method.

Create a private clear/destroy method (containing exactly the code needed in destructor)

Destructor contains a call to that method.

 

Recap

Need a destructor that frees all dynamically allocated memory the object controls.

Need a copy constructor that allocates the dynamic memory and copies all data.

Need an assignment operator that does both (unless self-assignment).

 

Dynamic Class Variations

How will code be different when dealing with a dynamic array?

How will code be different when dealing with a linked list?

 

Smart Assignment Operator

ClassName& ClassName::operator=(const ClassName& rhs)
{
    if(this!=rhs) // self assignment
    {
        clear(); // call clean-up helper method
        copy(rhs);
    }
    return *this;
}