Lecture Notes 8 – Pointers and dynamic memory

CSS 501 – Data Structures and Object-Oriented Programming

 

Reading for this lecture:      

Carrano, Interlude 2 (skip 2.4).

5th Edition Section 4.1

Chapter 4.1

 

To be covered in this lecture:

 

Collections

Collections of objects are the among the most common abstract data types. Examples include lists, stacks, queues, heaps, and trees. Each type collects that data in different ways. In this class, we will examine all of these data types.

 

All of these abstract data types can be implemented using an array. However, this is often not the best implementation for two reasons:

 

Over the next few lectures, we are going to discuss the use of a linked list of objects using pointers to store collections of data, in general, and to implement a list data type, in particular. While linked lists also have drawbacks for some applications, they avoid the problems mentioned above. Linked lists are very important; we will be using them to implement several abstract data types. For example, you could have a list of sorted integers, where each integer “pointed” to the next one in the list:

                1 -> 5 -> 21 -> 37 -> 71 -> 114

Elements can be inserted and deleted by telling the numbers to point to different places, rather than shifting data around in an array.

 

Pointers

Some of you are probably already be familiar with pointers in C or C++. If you have programmed only in Java or C#, then these may seem mysterious. C++ uses a different syntax than C to allocate and deallocate memory dynamically. These statements describe some correct and incorrect ways of using pointers (see the comments for notes on what isn’t correct).

 

int *p;

*p = 42;      // Don’t do this, yet! Where does p point to?

p = new int;  // Allocates memory for one int.

*p = 42;     

int *q;

q = p;        // q and p point to the same location.

*q = 43;

cout << *p << endl;

q = new int;

p = q;        // This causes a memory leak!

delete q;     // This deallocates the memory

//     location that p and q point to.

q = NULL;

p = NULL;     // Pointer that don’t point to

// valid location should be set to NULL.

 

 

Dynamic allocation of arrays is similar:

                int *myArray, size = 30;

       myArray = new int[size];   // size is num of elements in

       myArray[0] = 1;

       delete[] myArray;          // For arrays, you use delete[].

 

 

Strange … no … bizarre C/C++ notations that are legal, used in the last century (but still used) and VERY unCOOL!!

 

int *myArray = new int[size];     // this is ok

 

int *p = myArray;    // points to the beginning of the array

// this also points at the beginning of the array

p = &(myArray[0]);  

 

// pointer arithmetic, actual "increment" is datatype size

p = p + 1;           // or p++, points to next array element

*p = 3;              // this is the same as myArray[1] = 3

// (not too bad)

 

// try this … not as cool

p = &(myArray[2]);

p = p - 3;           // points to myArray[-1]!!

*p = 4;              // Crash, we hope!

 

// very, I mean VERY uncool

p = &(myArray[16]);

*(p+6) = 18;         // myArray[22] = 18!! USE INDEX!!

 

// now this is strange, and BAD!!

p = &(myArray[20]);

p[0] = 18;           // same as myArray[20] = 18

p[2] = 14;           // same as *(p+2)=22, or myArray[22]=14

 

// ALWAYS remember to delete the corresponding new

delete[] myArray;

 

 

Pointers to classes/structs

What if you have a pointer to a struct or class?

                struct myStruct

       {

              int aNumber;

              bool status;

       };

 

       myStruct *myPtr;

       myPtr = new myStruct;

 

// error! since . takes precedence over *.

       *myPtr.status = false;    

 

// The last two statements are equivalent.

       (*myPtr).status = true;

       myPtr->status = true;                     

 

Array of structs:

myStruct *myPtr;

myStruct *myArray = new myStruct[20];

 

myArray[3].aNumber = 5;    // this is ok

 

myPtr = myArray;           // myPtr points to myArray[0]

(*myPtr).aNumber = 18;     // myArray[0].aNumber = 18

myPtr->status = false;     // myArray[0].status = false

 

// pointer arithmetic

myPtr++;                   // to next entry, or myArray[1]

myPtr->aNumber = 21; // myArray[1].aNumber = 21

 

// this are legal, BUT DO NOT EVER EVER do this!!

((&(myArray[5])) + 4 )->aNumber = 18;

(&(myArray[5]))[-2].aNumber = 18;

(*(&(myArray[5]))).aNumber = 18;

 

       delete [] myArray;         // ALWAYS delete our new.

 

 

Structs vs Class:

class myClass {

private:

int aNumber;

       char *myPtr;

public:

       bool status;

 

// default constructor

       myClass()    

: aNumber(0), status(false)       // ß WHAT IS THIS?

       {

// Destructor IS VERY important in this case!! (why?)

              myPtr = new char[100];           

}

 

// No way for C++ run time to

// know what to do without the destructor!

       ~myClass() { delete [] myPtr;}

};

 

1.     Without default constructor, cannot allocate an array of class instance

2.     Notice the destructor!

3.     Not much else different!