In computer science dynamic memory allocation is the allocation of memory storage for use in a computer program during the runtime of that program. It is a way of distributing ownership of limited memory resources among many pieces of data and code. A dynamically allocated object remains allocated until it is deallocated explicitly, either by the programmer or by a garbage collector this is notably different from automatic and static memory allocation. It is said that such an object has dynamic lifetime.

The problem of fulfilling an allocation request, which involves finding a block of unused memory of a certain size in the heap, is a difficult problem. A wide variety of solutions have been proposed, including:

1)Free lists
2)Paging
3)Buddy memory allocation

The main problem for most dynamic memory allocation algorithms is to avoid both internal and external fragmentation while keeping both allocation and deallocation efficient. Also, most algorithms in use have the problem that a large number of small allocations can cause wasted space due to collecting metadata; thus most programmers avoid this, sometimes by using a strategy called chunking.

[attachment=9681]
Dynamic Memory Allocation
Memory Allocation:
There are two types of memory allocation.
1) Static memory allocation -- allocated by the compiler. Exact size and type of memory must be known at compile time.
2) Dynamic memory allocation -- memory allocated during run time. Exact sizes or amounts (like the size of an array, for example) does not have to be known by the compiler in advance. This memory is allocated by the run time system. To allocate memory dynamically, we have to use pointers.
Dynamic Memory Allocation:
To dynamically allocate memory in C++, we use the new operator. To de-allocate dynamic memory, we use the delete operator. Dynamic memory is created in an area of memory often referred to as the "free store", or the "heap". We can only allocate space during run time. We cannot create new variable names during run time -- all identifiers must be known by the compiler. For this reason, creating dynamic memory involves two steps:
1. Creating the dynamic space.
2. Storing its address in a statically allocated pointer (which has a name).
This gives us a name by which we can refer to the dynamic data. We always access dynamically allocated space through a pointer.
For step (1), use the new operator, followed by the type being allocated.
new int; // dynamically allocates an int
new double; // dynamically allocates a double
new Fraction; // dynamically allocates a Fraction object
new int[40]; // dynamically allocates an array of 40 ints
These statements above are not very useful by themselves, because the allocated spaces have no names! How do we get to them?
The new operator returns the address of the allocated space, so we must capture this in a pointer (with an assignment statement).
int * p; // declare a pointer p
p = new int; // dynamically allocate an int and load address into p
double * d; // declare a pointer d
d = new double; // dynamically allocate a double and load address into d
// we can also do these in single line statements
Fraction * fp = new Fraction;
int x = 40;
int * ptr = new int[x];
Notice that this last example shows that a variable can be used as the size, when creating an array dynamically, since the allocation is happening at run time. This is different from the static allocation, which requires a constant value for the size.
Dynamically allocating objects:
We see from the examples above that this works on user-defined types as well (like Fraction). However, don't forget that the Fraction constructor has to run when we create a Fraction object. If the class has a default constructor, then this is the one that runs unless you specify otherwise. To use a different constructor, just pass in the parameters after the dynamic allocation:
Fraction * fp = new Fraction(3,5); // initializes object to 3/5
This gives us a name by which we can refer to the dynamic data. We always access dynamically allocated space through a pointer.
For step (1), use the new operator, followed by the type being allocated.
newint; // dynamically allocates an int
new double; // dynamically allocates a double
new Fraction; // dynamically allocates a Fraction object
newint[40]; // dynamically allocates an array of 40 ints
These statements above are not very useful by themselves, because the allocated spaces have no names! How do we get to them?
The new operator returns the address of the allocated space, so we must capture this in a pointer (with an assignment statement).
int * p; // declare a pointer p
p = new int; // dynamically allocate an int and load address into p
double * d; // declare a pointer d
d = new double; // dynamically allocate a double and load address into d
// we can also do these in single line statements
Fraction * fp = new Fraction;
int x = 40;
int * ptr = new int[x];
Notice that this last example shows that a variable can be used as the size, when creating an array dynamically, since the allocation is happening at run time. This is different from the static allocation, which requires a constant value for the size.
Dynamically allocating objects: We see from the examples above that this works on user-defined types as well (like Fraction). However, don't forget that the Fraction constructor has to run when we create a Fraction object. If the class has a default constructor, then this is the one that runs unless you specify otherwise. To use a different constructor, just pass in the parameters after the dynamic allocation:
Fraction * fp = new Fraction(3,5); // initializes object to 3/5
Deleting dynamic memory:
You never need to worry about getting rid of statically allocated memory. Those variables are automatically handled by the compiler, which has already determined their scope and their lifetime. However, anything you create dynamically will not be taken care of by the compiler. It is up to you to clean this memory up when you are done with it. To deallocate dynamically allocated memory, apply the delete operator to the pointer, and it will delete the dynamic memory that the pointer is pointing to. (Note: This does not deallocate the pointer).
deletefp; // deletes the fraction pointed to by fp
delete [] ptr; // deletes the array allocated in the example above
When deallocating a dynamic array, use the form:
delete [] pointername
Notation -- The arrow operator:
If we dynamically allocate an object, and therefore can only refer to it with a pointer, then how do we call its public member data or member functions? The usual format is: objectName.memberName
Consider the following:
Fraction * fp = new Fraction; // fp is a pointer to a dynamic Fraction object
How do we call the Show() function for this object? We don't have a separate name for the object, but we can refer to it by de-referencing the pointer. So, the object's effective name is: *fp
So, here are some calls to Fraction member functions:
(*fp).Show();
(*fp).Get();
(*fp).Evaluate();
Note: The parintheses here are essential, because the dot-operator has higher precedence than the * operator, and we need to dereference the pointer first! This statement would be incorrect:
*fp.Show(); // this would be the same as *(fp.Show()); which is syntactically incorrect
Since having to deal with the parinthesesisnotationally yucky (a technical computer term), we have another operator for these situations that is nicer to use -- the arrow operator -> This operator can be used instead of the dot operator when are accessing objects through pointers. Here are the equivalent function calls with the arrow operator:
fp->Show();
fp->Get();
fp -> Evaluate(); // note that the spacing is irrelevant. Just keep the arrow together ->