Computer Algorithms I CS 305 Class Notes

Lecture Notes for Computer Algorithms I

21 October 2003 - Dynamic Memory

Automatic vs. manual storage allocation.
- Automatic storage allocation occurs with the help of the compiler and the run-time system.
  - Automatic is best: you don't have to worry about it, everything's taken care of for you.
  - However, automatic storage allocation may require information not available at compile time.
    - How many lines are there to read from input?
  - Also, automatic storage allocation follows the scoping layout of the program.
    - It's not possible to create storage in one place and hand it back to someplace else.
Manual storage allocation.
- Manual (or Dynamic) storage allocation solves both these problems.
  - Manual storage allocation can use run-time information while allocating storage.
  - Pointers to manually allocated storage can be passed around just like any other pointer value.
- However, in C++ anyway, manual storage allocation extracts a heavy cost.
  - The programmer is completely responsible for handling all aspects of manual storage management.
  - Any errors made are insidious and obscure: difficult to detect, difficult to track down and (occasionally) difficult to fix.
- Manual storage allocation (also known as heap allocation).
  - The new operator allocates storage for a value.
  - new T heap allocates a value of type T.
- Array allocations.
  - The array-pointer correspondence.
  - Each call to new T allocates a single value of type T.
    - That's like a single-element array.
  - The new operator can also allocate a block of values of type T.
    - That's like a multi-element array.
  - new T [n] allocates a block of n values of type T.
    - The returned pointer references the first (index 0) element in the array.
  - n may be zero, but it may not be negative.
    - Accessing elements in a zero-element array is, of course, not a very bright thing to do.
- Allocation errors.
  - new operations can go wrong at run-time.
    - No more heap space, negative array sizes.
  - Nyhoff is half-right: there is a version of new that returns a null pointer on allocation error.
    - However, this is not the default version of new.
  - By default new throws an exception when there's an allocation error.
    - new throws the bad_alloc exception.
```
#include 	// define exit-failure
#include 	// define cee
#include 		// define bad-alloc

int main() {
  try {
    int * ip = new int [-10];
    delete [] ip;
    }
  catch (std::bad_alloc ba) {
    std::cerr << "Allocation failed:  " << ba.what() << "\n";
    return EXIT_FAILURE;
    }
  }
```
    - The non-throwing version of new takes a no-throw parameter.
```
#include 	// define exit-failure
#include 	// define cerr
#include 		// define nothrow

int main() {
  int * ip = new(std::nothrow) int [100000000];
  if (ip == 0) {
    std::cerr << "Allocation failed.\n";
    return EXIT_FAILURE;
    }
  delete [] ip;
  }
```
- Deleting
  - Dynamically-allocated storage no longer needed should be returned to the heap.
    - The Heap Golden Rule: If you allocate it, you de-allocate it.
      - The Golden Rule's Adjunct: Falling off the end of main() is not freeing storage.
    - There's only a finite (but admittedly large) amount of heap space available.
    - Programmers that can't handle heap storage correctly are not to be trusted.
  - The delete operation returns the referenced storage chunk to the heap.
  - The pointer allocated must be the pointer deleted.
  - Allocated arrays must be deleted with the delete [] operator.
- Allocation-deallocation problems.
  - Storage Leaks.
  - Dangling pointers.
  - Double deallocation.
- New- vs. Old-Style dynamic storage management.
  - C++ also supports C-style (old-style) dynamic-storage management.
  - Avoid C-style dynamic-storage management.
    - It does not work with classes.
This page last modified on 23 October 2003.