Slides

S1: Classes and Dynamic (Run-time) Memory Management

Learning Goals:
- What Dynamic Data-Structures (DDS) are?
- What C++ features (pointers, new, delete) support DDS?
- How box-pointer diagrams help visualize DDS?
- What is the impact on Classes modeling DDS?
  - Constructors, Destructors, Operator=, Copy constructor
- Common errors
Outline
- Ch# 2.5 Pointer as an Abstract Data Type
- Ch#8.1 Memory management (new, delete operators)
- Ch# 8.2 Dynamically Allocated Objects
  - new/delete and constructors/destructors
- Ch# 8.3 Assignment (=) and Initialization (copy constructor)
- Ch# 8.4-8 Applications (safe array, string, sets)
Recommended Ex.: 8.1, 8.2, 8.4, 8.6, 8.8, 8.9, and 8.10.

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

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

S4: Comparing Implementations

Two Major Choices for Implementing Data Structures
- Array Based OR Pointer Based
- Ex. Binary Tree - which implementation is preferred?

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

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

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

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)

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);

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;
}

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?

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)?

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 ?

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