David E. Goldschmidt, Ph.D.

Example 19: Dynamic Memory Allocation

Three Types of Memory:

• When memory is allocated inside a function via variable creation, this is called automatic memory allocation.
• For the example code below, space for local variables is allocated in each function call and eliminated when variables go out of scope. This memory is allocated on the runtime stack.

// automatic memory allocation
//    (allocated on the runtime stack)
int x = 5;
double y;

• Variables may be allocated using the static keyword, indicating they will not be eliminated when they go out of scope. Instead, they retain their values, but are only accessible within the scope where they are defined. This is called static memory allocation and a useful application is shown in the example below:

// automatic memory allocation (allocated on the runtime stack)
int x = 5;
double y;

while ( x > 0 )
{
  // static memory allocation
  //   (variables are not eliminated when they go out scope)
  //   (and they instead retain their values)
  static bool first_time = true;
  if ( first_time ) {
    cout << "first time through the loop, x is " << x << '\n';
    first_time = false;
  }
  x--;
}

• When memory is explicitly allocated as needed, this is called dynamic memory allocation. This memory is allocated on the runtime heap.
• Dynamic Memory is:
  1. Created using the new operator.
  2. Accessed through pointers.
  3. Eliminated through the delete operator.
• Here’s a simple example involving the dynamic allocation of integers:

// dynamic memory allocation (allocated on the runtime heap)
//   (use the "new" keyword)
int * p = new int;
*p = 400;
cout << "p points to an int with value " << *p << '\n';

int * q = new int;
*q = *p;
*p = 500;
cout << "p points to " << *p << " and q points to " << *q << '\n';

delete p;   // relinquish that memory
delete q;

• The expression new int asks the system for a new chunk of memory that is large enough to hold an integer. Therefore, the following statement allocates a new chunk of memory large enough to hold an integer and stores the memory address of the start of this memory in the pointer variable p.

int * p = new int;

• The statement delete p takes the integer memory pointed to by p and returns it to the system for re-use.
• This memory is allocated from and returned to a special area of memory called the runtime heap. By contrast, local variables and function parameters are allocated from a different memory area called the runtime stack.
• In between the new and delete statements, memory is treated just like memory for an ordinary variable, except the only way to access it is through pointers.
• Dynamic allocation of such primitives as int and double is not very significant. What is more important is the dynamic allocation of arrays and objects.

Exercises:

1. What is the output of the following code? Draw a picture of the stack and the heap to help figure this out.

double * p = new double;
*p = 35.1;
double * q = p;
cout << *p << " and " << *q << '\n';
p = new double;
*p = 27.1;
cout << *p << " and " << *q << '\n';
*q = 12.5;
cout << *p << " and " << *q << '\n';
delete p;
delete q;

2. What do you think the output is if the following line is added to the end of the above code?

cout << *p << " and " << *q << '\n';

3. What happens when the following code is added to the end of the above code?

double * r = new double;
*r = 48.6;
cout << *p << " and " << *q << '\n';

Example 20: Dynamic Allocation of Arrays

Dynamic Allocation of Arrays:

• Declaring the size of an array at compile time does not offer much flexibility.
• We can dynamically allocate an array based at runtime. This gets us part-way toward the behavior of a vector.
• Here is an example of how to do this:

int main()
{
  cout << "Enter the size of the array: ";
  int n;
  cin >> n;

  double * a = new double[ n ];

  for ( int i = 0 ; i < n ; i++ ) {
    a[i] = sqrt( i );
  }

  for ( int i = 0 ; i < n ; i++ ) {
    if ( double( int( a[i] ) ) == a[i] ) {
      cout << i << " is a perfect square " << endl;
    }
  }

  delete [] a;

  return 0;
}

• Consider the dynamic allocation line:

  double * a = new double[ n ];

• The expression new double[ n ] asks the system to dynamically allocate enough consecutive memory to hold n double values.
  1. What's crucially important is that n is a variable.
  2. Therefore, its value and, as a result, the size of the array are not known until the program is executed.
  3. When this happens, the memory must be allocated dynamically at runtime.
• The address of the start of the allocated memory is assigned to the pointer variable a.
• After this, a is treated as though it's an array. In fact, the expression a[i] is exactly equivalent to the following pointer arithmetic and dereferencing expression:

    a[i] = sqrt( i );   // *(a+i) = sqrt( i );

• After we are done using the array, the delete [] a statement releases the memory allocated for the entire array. Without the [], only the first value in the array would be released.

Exercises:

1. Write code to:
   1. Dynamically allocate an array of n integers.
   2. Point to this array using the integer pointer variable a.
   3. Read n values into the array from the stream cin.
2. Next, suppose we wanted to double the size of array a without losing the values. This requires the following:
   1. Write code to allocate an array of size 2*n, pointed to by integer pointer variable temp (which will later become a).
   2. Write code to copy the n values of a into the first n locations of array temp.
   3. Write code to delete array a.
   4. Write code to assign temp to a.

Example 21: Dynamic Allocation of Objects

Dynamic Allocation of Objects:

• We can dynamically allocate arrays of objects, as shown in the following example:

int n;
cin >> n;

class foo {
public:
  string a, b;
};

foo * farray = new foo[ n ];

• For dynamically allocated objects, the default constructor (the constructor that takes no arguments) must be defined.

Example 22: Designing our Own Vector Class

Vector Public Interface:

• In creating our own version of the vector class, we will start by considering the public interface:

public: // Member functions and other operators
  T& operator[] ( size_type i );
  const T& operator[] ( size_type i ) const;
  void push_back( const T& t );
  void clear();
  bool empty() const;
  iterator erase( iterator p );
  size_type size() const;
  void resize( size_type n );

public: // Iterator operations
  iterator begin();
  const_iterator begin() const;
  iterator end();
  const_iterator end();

• This is an excerpt from the Vec.h header file. Our focus will be on the use of templates, the underlying representation, and memory management.

Templated Class Declarations and Member Function Definitions:

• In terms of just the layout of the code in Vec.h, the biggest difference is that this is a templated class, allowing different types of primitives and objects to be stored using this container class.
• The template keyword and the template type name must appear before the class declaration, as in:

template <class T> class Vec

• Within the class declaration, T is used as a type and all member functions are said to be "templated over type T."
• In the actual text of the code files, templated member functions are often defined inside the class declaration. The templated functions defined outside the template class declaration must be preceeded by the phrase template <class T> class Vec. Further, when Vec is referred to, it must be Vec<T>.
• Therefore, for member function create() (there are two versions), we have:

template <class T> void Vec<T>::create( // ...

Syntax and Compilation:

• Templated classes and templated member functions are not actually created (i.e. compiled) until they are needed.
• Compilation of the class declaration is triggered by a line of the following form in which int replaces T. This also compiles the default constructor for Vec<int> (because it is the constructor used here).

Vec<int> v1;

• Other member functions are not compiled unless they are used.
• When a different type is used with Vec, the template class declaration is compiled again, this time for example with double replacing T instead of int. Again, only the member functions used are actually compiled.

Vec<double> z;

• This is very different from ordinary classes, which are usually compiled separately and all functions are compiled regardless of whether or not they are needed.
• Code of templated classes and member functions must be available where they are used. As a result, member function definitions are often included in the class declaration or included below the class declaration but still in the .h file.
• If member function definitions are placed in a separate .cpp file, this file must be included via #include, just like the .h file, because the compiler needs to see it to generate code.

Member Variables:

• Looking inside the Vec<T> class at the member variables, we find three such member variables defined:
1. m_data is a pointer to the start of the array (after it has been allocated).
2. m_size indicates the number of locations currently in use in the vector (exactly what the size() member function should return).
3. m_alloc is the number of entries in the dynamically allocated block of memory (i.e. how much memory is actually allocated for the array).

Typedefs, Iterators, and Pointers:

• Several types are created through typedef statements in the first public area of Vec.
• Once created, the names can be used as ordinary class type names. Therefore, Vec<int>::size_type is the size type, defined here as an unsigned int.
• Also, Vec<int>::iterator is an iterator type defined by the Vec<int> class. Think of an iterator as a pointer, as it is defined as T *.
• Internal to the declarations and member functions, T * and iterator may be used interchangeably.
• The ++ and -- operators on pointers automatically apply to iterators.

Random Access:

• Access to the individual locations of the Vec is provided through operator[].
• Syntactically, use of this operator is translated by the compiler into a call to a function called operator[]. For example, if v is of type Vec<int>, then v[i] = 5 translates to v.operator[](i) = 5.
• As for most classes, there are two versions of the overloaded operator[] function in Vec:
  • A non-const version that returns a reference to m_data[i]. This is applied to non-const Vec<T> objects, allowing the contents of the internal array to be modified.
  • A const that returns m_data as a const reference so that it cannot be modified. As a result, it is the one used for const Vec<T> objects.

Classes With Dynamically Allocated Memory:

• Each object must do its own dynamic memory allocation.
• And we must be careful to keep the memory of each object instance separate from all others. This requires that we write (very carefully) our own:
  • Copy constructor
  • Assignment operator
  • Destructor (which releases dynamically allocated memory when an object goes out of scope or is itself eliminated)

Copy Constructor and this:

• The copy constructor must allocate a new array for the objects being constructed, copy the contents of the array of the passed object, and set the pointer, size, and allocation member variables appropriately.
• The actual copying is done in a private member function called copy(), which is used elsewhere, too. As an exercise, write the private member function copy().
• All class objects have a special pointer defined called this, which points to the current object. Note that this cannot be changed.
• The expression *this is a reference to the class object.
• The this pointer is used in several ways, including the following:
  • Make it clear (and sometimes remove name ambiguity) when member variables of the current object are being used.
  • Check to see when an assignment is self-referencing (e.g. v = v).
  • Return a reference to the current object using *this.

Assignment Operators and Vec:

• Assignment operators of the form v1 = v2 are translated by the compiler to v1.operator=(v2).
• Cascaded assignment operators are translated as shown below:

v1 = v2 = v3;   // v1.operator=( v2.operator=(v3) );

• Therefore, the value of the assignment operator (i.e. the result of v2 = v3) must be suitable for input to a second assignment operator. This means the result of an assignment operator ought to be a reference to an object.
• The implementation of an assignment operator usually takes on the same form for every class. This is illustrated by Vec<T> code, summarized as follows:
  • Do no real work if there is a self-assignment (since there is nothing to copy).
  • Otherwise, delete the contents of the current object, then copy the passed object, just as is done in the copy constructor.
  • Return a reference to the (copied) current object using the this pointer.

Destructors:

• Destructors are called implicitly when an automatic object goes out of scope or a dynamic object is deleted. A destructor can never be called explicitly.
• A destructor typically deletes the dynamic memory "owned" by the class, as in:

  // destructor
  ~Vec() { delete [] m_data; }

Increasing the Size of the Vec:

• The push_back() function adds to the end of the array, increasing m_size by one T location.
• But what if m_size == m_alloc, which means the allocated array is full? We need to increase the size of the array. Therefore we need to:
  1. Allocate a new, larger array. The best strategy is generally to double the size of the current array.
  2. If the array size was originally zero, doubling does nothing. We must be sure that the resulting size is at least 1.
  3. Next, we need to copy the contents of the current array to the newly allocated array.
  4. Finally, we must delete the current array and make the m_data pointer point to the start of the newly allocated array, then adjust the m_size and m_alloc variables appropriately.