S1: Classes and Dynamic (Run-time) Memory Management
Copyright: S. Shekhar, C. S. Dept., University of Minnesota, Minneapolis, MN 55455. Csci,3321,Winter.(home)
S2: Why use Pointers and Dynamic data structures?
  • What are Dynamic data structures?
    • Collections which expand and contract as program executes.
    • Different from Arrays, whose sizes are fixed at creation
  • Why do we use Dynamic data structures?
    • 1. Flexibility - conceptually closer to many data-structures
      • e.g. Unix directory, roadmaps, electrical circuits, machine design blue-prints, ...
    • 2. Simplify programming - do not need to decide max_size
    • 3. Performance - may save memory
      • e.g. interpreter for Lisp, Magic (VLSI design editor), AutoCAD
Copyright: S. Shekhar, C. S. Dept., University of Minnesota, Minneapolis, MN 55455. Csci,3321,Winter.(home)
S3: Implementing DDS with Pointers: Memory management
  • Three areas of memory during program execution
    • Static Area - holds global variables
    • Program Stack - holds local variables from functions/blocks
    • Heap (free memory) - for dynamic use by program via pointers
  • How is Dynamic data structures implemented?
    • Declare Pointers
    • Allocate memory at run-time as elements come (new, constructor)
    • Deallocate memory if elements are deleted (delete, destructor)
    • A garbage collector recycles memory (Green thing!)
  • Example: TreeList class
    • Declaration in class: (Tree* list;)
    • Allocated by constructor (list = new Tree[size];)
    • Deallocated was implicit
Copyright: S. Shekhar, C. S. Dept., University of Minnesota, Minneapolis, MN 55455. Csci,3321,Winter.(home)
S4: Comparing Implementations
  • Two Major Choices for Implementing Data Structures
    • Array Based OR Pointer Based
    • Ex. Binary Tree - which implementation is preferred?
Copyright: S. Shekhar, C. S. Dept., University of Minnesota, Minneapolis, MN 55455. Csci,3321,Winter.(home)
S5: Review Ch#2.5: Pointers ADT
  • Pointers: Construct for dynamic data structures
  • Review Pointer as an Abstract Data Type
    • Data: memory address of base type T (unsigned integer)
    • Operations: address (&), dereference (*), assignment,
      • memory allocation (new), deallocation (delete),
      • arithmetic and relational.
    • C++: What will the following print?
      char str[] = "ABCDEFG";
      char *PC = str, *PC2 = PC + 1;
      short X = 33; short *PX = &X; //PX points to X
      cout << *PC << endl ; //
      PC =+ 4; cout << *PC << endl ; // pointer + number - > pointer
      PC--; cout << *PC << endl ;
      cout << (PC2 - PC) << endl ; // pointer - pointer - > number
Copyright: S. Shekhar, C. S. Dept., University of Minnesota, Minneapolis, MN 55455. Csci,3321,Winter.(home)
S6: Ch#8.1 Memory allocation/deallocation in C++
  • Q? How did we allocate/deallocate memory in C?
    • void* malloc( numBytes ) -- > pointer to allocated space
      int *p; p = malloc( sizeof(int) );
    • calloc(#Items, itemSize)- > space for an array of items
      • initialized to 0
    • realloc( *oldSpace, sizeNewSpace) -- > pointer to new space
      • copies oldSpace to newSpace, deallocates oldSpace.
    • Q? So, What is new in C++?
    • (i) new: create object and return pointer or NULL (0)
      int *p; p = new int; // Q? Compare C++ new and C-malloc()
      if (p == 0) cerr << "memory problems" << endl;
      //(1) operator not function, (2) sizeof() not needed,
      //(3) typed return pointer
      int *jp = new int[10]; // dynamic array allocation
    • (ii) delete: destroy object pointed to
      delete ip; // delete an object
      delete [] jp; // delete an array - note syntax
Copyright: S. Shekhar, C. S. Dept., University of Minnesota, Minneapolis, MN 55455. Csci,3321,Winter.(home)
S7: More on Pointers in C++
  • Syntax and Semantics
    float *p, *q, *r; student *s, *t; // declaration
    p = new float; q = new float(0.0) ; // storage allocation
    • p = 1.0; *q = *p; r = q ; // assignment
      cout << *p << *q << *r ; // usage
  • Access via * and - > operators
    s = new student; (*s).id = 1111; strcpy(s- > name, "Mary");
    cout << s- > id << (*s).name;
  • Pointer comparison (==, !=)
    if (p != q) cout << "p and q are different" ;
  • Semantics: Box-pointer diagrams help
Copyright: S. Shekhar, C. S. Dept., University of Minnesota, Minneapolis, MN 55455. Csci,3321,Winter.(home)
S8: Box Pointer Diagrams
  • Pointer Semantics: Box-pointer diagrams
    • Trace (declaration, memory allocation, assignment, ...)
    • Ex. Draw box pointer diagram after each statement of program
  • Q? Contrast the pairs by predicting output of cout statements:
    cout << p << *p;
    cout << (p == q) << ((*p) == (*q));
    cout << (r == q) << (p == q);
    • Compare (*s).name vs. *(s.name) vs. *s.name
      • priority(.) > priority(*))
    • Ex. 8.1, 8.2 (pp 369-370)
Copyright: S. Shekhar, C. S. Dept., University of Minnesota, Minneapolis, MN 55455. Csci,3321,Winter.(home)
S9: Common Errors With Pointers
  • Use dereferencing operator (*, - > ) whenever needed.
    • Tree *t1, *t2; /* ... */ cout << t1.frequency(); // error
  • Use new and delete operators with pointers
    • Tree t1; t1 = new Tree; delete t1;
    • Tree *t1; *t1 = new Tree; delete t1*; //error
  • Never reference a node after it is deallocated
    • delete t1; cout << t1- > frequency() ; // error
    • do not return pointer to local var of functions
  • Never reference a pointer before it is allocated
    • Tree *t1; cout << t1- > freq ; // error
  • Avoid Memory allocation in infinite loop
    • do { t1- > left = new Tree; t1 = t1- > left } while (TRUE);
Copyright: S. Shekhar, C. S. Dept., University of Minnesota, Minneapolis, MN 55455. Csci,3321,Winter.(home)
S10: Ch#8.2 Dynamically Allocated Objects
  • Issue 1: Interaction between new/delete and constructor/destructor
  • Initialization of dynamic Objects of a class type
    • "new" allocates memory and then implicitly invokes constructor
      TreeList* tl1; tl1 = new TreeList(30); // dynamic creation
      // "new" allocate memory for tl1- > size, tl1- > list
      // constructor allocates memory for list[0] ... list[29]
  • Deallocation of dynamic objects
    • "delete" calls destructor before deallocating memory
      delete tl1;
  • Ex. Identify implicit calls to constructor and destructor:
    void function1( const int m1, int m2)
    { TreeList tl(m1); //....
    }
    void main(void)
    { TreeList *ttt;
    TreeList sss(20);
    ttt = new TreeList(20);
    function1(1, 2);
    delete ttt;
    }
Copyright: S. Shekhar, C. S. Dept., University of Minnesota, Minneapolis, MN 55455. Csci,3321,Winter.(home)
S11: Ch#8.2 Dynamically Allocated Objects (Contd.)
  • Issue 2: Objects of a class type w/ pointer data-members
  • (2A:): Constructor may need to allocate memory for those
    TreeList::TreeList(const int maxsz) {
    assert(maxsz > = 0);
    size = maxsz; // static data member = > no "new" op.
    list = new Tree[maxsz]; // memory allocation pointer
    }
  • Q? Can we initialize elements of "new Tree[maxsz]"?
  • (2B:) Destructor should free memory used by pointer data members
    TreeList::~TreeList( ) {
    assert(maxsz > = 0);
    delete [] list; // memory deallocation for dynamic data member
    }
  • Destructor member function
    • Has no parameters, no return type
    • Called whenever an object is deleted
      • Ex. Program termination - global objects die
      • Ex. block/function exits - local objects die
    • Q? Can a class have multiple Destructors? multiple constructors?
Copyright: S. Shekhar, C. S. Dept., University of Minnesota, Minneapolis, MN 55455. Csci,3321,Winter.(home)
S12: Ch#8.3 Copying and Assignment of Dynamically Allocated Objects
  • (2C:) Copy constructor should copy values not pointers
    TreeList::TreeList(const TreeList & X) {
    size = X.size;
    list = new Tree[X.size]; // avoid list = X.list
    for (int i=0; i < size; i++) list[i] = X.list[i];
    }
  • Without a Copy Constructor, default is to copy pointers
  • Copy Constructor
    TreeList A(50), B = A, C(A); // initialize B using A
    • Called implicitly in following situations:
      • (i) Use of = in declaration to create a new object
      • (ii)Parameter passed by value / object returned by function
    • Create a new object using contents of another object
    • Facilitates initialization by copying an existing object
    • No repetition of data-member values across objects in declaration
  • Restrictions
    • Has one parameter of same type as class
    • Parameter is passed by reference only!
    • Q? What happens if parameter is passed by value, (if compiler does not flag it)?
Copyright: S. Shekhar, C. S. Dept., University of Minnesota, Minneapolis, MN 55455. Csci,3321,Winter.(home)
S13: Ch#8.3 Copying and Assignment of Dynamically Allocated Objects
  • (2D:) Overloaded =operator should copy values not pointers
    TreeList::Operator=(const TreeList & X) {
    size = X.size;
    for (int i=0; i < size; i++) list[i] = X.list[i]; // avoid: list = X.list
    return *this; } // return object
  • Without overloaded operator=, default is to copy pointers
  • Overloaded assignment operator (=)
    • Called implicitly = is used outside declaration ;
      TreeList A(50), B;
      B = A; // assign fields of B , the values from fields of A
    • Q? How is operator= different from the Copy constructor?
      • no memory allocation (B exists), returns object
    • Reserved word "this"
    • Each C++ object has a pointer data-member named "this"
    • Defined automatically when object is created
    • Private: Can be used only inside member functions
    • "this" = pointer to the object :: "*this" = object itself
    • Q? Inside A, What are this- > size , this- > list ?
Copyright: S. Shekhar, C. S. Dept., University of Minnesota, Minneapolis, MN 55455. Csci,3321,Winter.(home)
S14: More Restrictions
  • Object created w/ "new" do not take initializing values
    • It will use default constructor if available
      String* s1 = new String[2] = { "good", "bad" }; // error
    • Do not "delete" a pointer which is already deallocated
      Tree t1; t1 = new Tree; delete t1; delete t1; //error
    • Destructor - no argument, no return value, no overloading!
    • Class with pointer data members
    • Always overload =, ==, !=, and define copy constructor
    • Copy constructor: Do not pass argument by value!
    • C::C( C x) { ... } // error
  • Operator=, Copy constructor: Copy values, not pointers!
  • Error to use "this" on left hand side of an assignment
    this = ...; //error
Copyright: S. Shekhar, C. S. Dept., University of Minnesota, Minneapolis, MN 55455. Csci,3321,Winter.(home)

The views and opinions expressed in this page are strictly those of the page author.
The contents of this page have not been reviewed or approved by the University of Minnesota.