COMP171
Fall 2006
Pointers
and
dynamic objects
Pointers and dynamic objects/ Slide 2
Topics
Pointers
Memory addresses
Declaration
Dereferencing a pointer
Pointers to pointer
Static vs. dynamic objects
new and delete
Pointers and dynamic objects/ Slide 3
Computer Memory
Each variable is assigned a memory slot (the
size depends on the data type) and the
variable’s data is stored there
emory address: 1020 1024 1032
… … 100 … 1024 …
a
Variable a’s value, i.e., 100, is
int a = 100; stored at memory location 1024
Pointers and dynamic objects/ Slide 4
Pointers
A pointer is a variable used to store the
address of a memory cell.
We can use the pointer to reference this
memory cell
Memory address: 1020 1024 1032
… … 100 … 1024 …
integer
pointer
Pointers and dynamic objects/ Slide 5
Pointer Types
Pointer
C++ has pointer types for each type of object
Pointers to int objects
Pointers to char objects
Pointers to user-defined objects
(e.g., RationalNumber)
Even pointers to pointers
Pointers to pointers to int objects
Pointers and dynamic objects/ Slide 6
Pointer Variable
Declaration of Pointer variables
type* pointer_name;
//or
type *pointer_name;
where type is the type of data pointed to (e.g. int, char, double)
Examples:
int *n;
RationalNumber *r;
int **p; // pointer to pointer
Pointers and dynamic objects/ Slide 7
Address Operator &
The "address of " operator (&) gives the memory
address of the variable
Usage: &variable_name
Memory address: 1020 1024
… … 100 … … …
a
int a = 100;
//get the value,
cout << a; //prints 100
//get the memory address
cout << &a; //prints 1024
Pointers and dynamic objects/ Slide 8
Address Operator &
Memory address: 1020 1024 1032
… 88 100 … … …
a b
#include <iostream>
using namespace std; Result is:
void main(){ The address of a is: 1020
int a, b; The address of b is: 1024
a = 88;
b = 100;
cout << "The address of a is: " << &a << endl;
cout << "The address of b is: " << &b << endl;
}
Pointers and dynamic objects/ Slide 9
Pointer Variables
Memory address: 1020 1024 1032
… 88 100 … 1024 …
a p
int a = 100; Result is:
int *p = &a; 100 1024
cout << a << " " << &a <<endl; 1024 1032
cout << p << " " << &p <<endl;
The value of pointer p is the address of variable a
A pointer is also a variable, so it has its own memory address
Pointers and dynamic objects/ Slide 10
Pointer to Pointer
What is the output?
58 58 58
Pointers and dynamic objects/ Slide 11
Dereferencing Operator *
We can access to the value stored in the variable
pointed to by using the dereferencing operator (*),
Memory address: 1020 1024 1032
… 88 100 … 1024 …
a p
int a = 100;
int *p = &a;
Result is:
cout << a << endl; 100
cout << &a << endl; 1024
cout << p << " " << *p << endl; 1024 100
cout << &p << endl; 1032
Pointers and dynamic objects/ Slide 12
Don’t get confused
Declaring a pointer means only that it is a pointer: int
*p;
Don’t be confused with the dereferencing operator, which
is also written with an asterisk (*). They are simply two
different tasks represented with the same sign
int a = 100, b = 88, c = 8;
int *p1 = &a, *p2, *p3 = &c;
p2 = &b; // p2 points to b
p2 = p1; // p2 points to a
b = *p3; //assign c to b
*p2 = *p3; //assign c to a Result is:
cout << a << b << c; 888
Pointers and dynamic objects/ Slide 13
A Pointer Example
Memory Layout
The code
Box diagram
void doubleIt(int x, main
int * p)
{ p 8192
a 16 (8200)
*p = 2 * x;
} doubleIt
int main(int argc, const x 9
char * argv[]) (8196)
{
int a = 16;
a 16 main
doubleIt (8192)
doubleIt(9, &a);
return 0;
} x 9
a gets 18 p
Pointers and dynamic objects/ Slide 14
Another Pointer Example
#include <iostream> Let’s figure out:
using namespace std; value1==? / value2==?
int main (){
int value1 = 5, value2 = 15; Also, p1=? p2=?
int *p1, *p2;
p1 = &value1; // p1 = address of value1
p2 = &value2; // p2 = address of value2
*p1 = 10; // value pointed to by p1=10
*p2 = *p1; // value pointed to by p2= value //
pointed to by p1
p1 = p2; // p1 = p2 (pointer value copied)
*p1 = 20; // value pointed to by p1 = 20
cout << "value1==" << value1 << "/ value2==" << value2;
return 0;
}
Pointers and dynamic objects/ Slide 15
Another Pointer Example
int a = 3;
char s = ‘z’;
double d = 1.03;
int *pa = &a;
char *ps = &s;
double *pd = &d;
% sizeof returns the # of bytes…
cout << sizeof(pa) << sizeof(*pa)
<< sizeof(&pa) << endl;
cout << sizeof(ps) << sizeof(*ps)
<< sizeof(&ps) << endl;
cout << sizeof(pd) << sizeof(*pd)
<< sizeof(&pd) << endl;
Pointers and dynamic objects/ Slide 16
Reference Variables
A reference is an additional name to
an existing memory location
Pointer: Reference:
x 9 x
9
ref
ref
int x = 9;
int x=9;
int &ref = x;
int *ref;
ref = &x;
Pointers and dynamic objects/ Slide 17
Reference Variables
A reference variable serves as an alternative name for
an object
int m = 10;
int &j = m; // j is a reference variable
cout << “value of m = “ << m << endl;
//print 10
j = 18;
cout << “value of m = “ << m << endl;
// print 18
Pointers and dynamic objects/ Slide 18
Reference Variables
A reference variable always refers to the
same object. Assigning a reference variable
with a new value actually changes the value
of the referred object.
Reference variables are commonly used for
parameter passing to a function
Pointers and dynamic objects/ Slide 19
Traditional Pointer Usage
void IndirectSwap(char *Ptr1, char *Ptr2){
char temp = *Ptr1;
*Ptr1 = *Ptr2;
*Ptr2 = temp;
}
int main() {
char a = 'y';
char b = 'n';
IndirectSwap(&a, &b);
cout << a << b << endl;
return 0;
}
Pointers and dynamic objects/ Slide 20
Pass by Reference
void IndirectSwap(char& y, char& z) {
char temp = y;
y = z;
z = temp;
}
int main() {
char a = 'y';
char b = 'n';
IndirectSwap(a, b);
cout << a << b << endl;
return 0;
}
Pointers and dynamic objects/ Slide 21
Pointers and Arrays
The name of an array points only to the first
element not the whole array.
1000
1004
1008
1012
1016
Pointers and dynamic objects/ Slide 22
Array Name is a pointer constant
#include <iostream>
using namespace std;
void main (){
int a[5];
cout << "Address of a[0]: " << &a[0] << endl
<< "Name as pointer: " << a << endl;
}
Result:
Address of a[0]: 0x0065FDE4
Name as pointer: 0x0065FDE4
Pointers and dynamic objects/ Slide 23
Dereferencing An Array Name
This element is
called a[0] or
*a
#include <iostream>
a[0] 2 using namespace std;
a void main(){
a[1] 4
int a[5] = {2,4,6,8,22};
a[2] 6 cout << *a << " "
<< a[0];
a[3] 8
} //main
a[4] 22
a
Pointers and dynamic objects/ Slide 24
Array Names as Pointers
To access an array, any pointer to the first element
can be used instead of the name of the array.
We could replace *p by *a
#include <iostream>
a p using namespace std;
void main(){
a[0] 2 22
int a[5] = {2,4,6,8,22};
a[1] 4 int *p = a;
a[2] 6 cout << a[0] << " "
a[3] 8 << *p;
a[4] 22 }
a
Pointers and dynamic objects/ Slide 25
Multiple Array Pointers
Both a and p are pointers to the same array.
#include <iostream>
a[0] using namespace std;
a[0] 22 void main(){
2 p
44 int a[5] = {2,4,6,8,22};
a[1] 4 int *p = &a[1];
a[2] 6 cout << a[0] << " "
a[3] 8 p[0] << p[-1];
cout << a[1] << " "
a[4] 22 << p[0];
}
Pointers and dynamic objects/ Slide 26
Pointer Arithmetic
Given a pointer p, p+n refers to the element that
is offset from p by n positions.
a 2 p - 1
a + 1 4 p
a + 2 6 p + 1
a + 3 8 p + 2
a + 4 22 p + 3
Pointers and dynamic objects/ Slide 27
Dereferencing Array Pointers
a[0] or *(a + 0) 2 a
a[1] or *(a + 1) 4 a + 1
a[2] or *(a + 2) 6 a + 2
a[3] or *(a + 3) 8 a + 3
a[4] or *(a + 4) 22 a + 4
*(a+n) is identical to a[n]
Note: flexible pointer syntax
Pointers and dynamic objects/ Slide 28
Array of Pointers & Pointers to Array
a
p
b
c
An array of Pointers A pointer to an array
int a = 1, b = 2, c = 3; int list[5] = {9, 8, 7, 6, 5};
int *p[5]; int *p;
p[0] = &a; P = list;//points to 1st entry
p[1] = &b; P = &list[0];//points to 1st entry
p[2] = &c; P = &list[1];//points to 2nd entry
P = list + 1; //points to 2nd entry
Pointers and dynamic objects/ Slide 29
NULL pointer
NULL is a special value that indicates an empty pointer
If you try to access a NULL pointer, you will get an error
int *p;
p = 0;
cout << p << endl; //prints 0
cout << &p << endl;//prints address of p
cout << *p << endl;//Error!
Pointers and dynamic objects/ Slide 30
Storing 2D Array in 1D Array
int twod[3][4] = {{0,1,2,3}, {4,5,6,7},
{8,9,10,11}};
int oned[12];
for(int i=0; i<3; i++){
for(int j=0; j<4 ; j++)
oned[i*4+j] = twod[i][j];
}
Pointers and dynamic objects/ Slide 31
Pointer to 2-Dimensional Arrays
table table[i] =
&table[i][0]
refers to
table + 1 table[ 0] or *( table + 0 ) the address
of the ith
row
table + 2 table[ 1] or *( table + 1 )
table[ 2] or *( table + 2 )
int table[3][4] = {{1,2,3,4}, *(table[i]+j)
What is = table[i][j]
{5,6,7,8},{9,10,11,12}};
**table
? for(int i=0; i<3; i++){
for(int j=0; j<4; j++)
cout << *(*(table+i)+j);
cout << endl;
}
Dynamic
Objects
Pointers and dynamic objects/ Slide 33
Memory Management
Static Memory Allocation
Memory is allocated at compilation time
Dynamic Memory
Memory is allocated at running time
Pointers and dynamic objects/ Slide 34
Static vs. Dynamic Objects
Static object
Dynamic object
(variables as declared in function calls)
Memory is acquired
Memory is acquired by
automatically program with an allocation
request
new operation
Memory is returned Dynamic objects can exist
automatically when object beyond the function in which
goes out of scope they were allocated
Object memory is returned
by a deallocation request
delete operation
Memory Allocation
Pointers and dynamic objects/ Slide 35
new
delete
{ int* ptr;
int a[200]; ptr = new int[200];
… …
} delete [] ptr;
Pointers and dynamic objects/ Slide 36
Object (variable) creation: New
Syntax
ptr = new SomeType;
where ptr is a pointer of type SomeType
Example
int* p = new int;
Uninitialized int variable
p
Object (variable) destruction:
Pointers and dynamic objects/ Slide 37
Delete
Syntax
delete p;
storage pointed to by p is returned to free store and p is now
undefined
Example
int* p = new int;
*p = 10;
delete p;
p 10
Pointers and dynamic objects/ Slide 38
Array of New:
dynamic arrays
Syntax
P = new SomeType[Expression];
Where
P is a pointer of type SomeType
Expression is the number of objects to be constructed
-- we are making an array
Because of the flexible pointer syntax, P can
be considered to be an array
Pointers and dynamic objects/ Slide 39
Example
Dynamic Memory Allocation
Request for “unnamed” memory from the Operating System
int *p, n=10; new
p = new int;
p
p = new int[100];
new
p
new
p = new int[n]; p
Pointers and dynamic objects/ Slide 40
Memory Allocation Example
Want an array of unknown size
#include <iostream>
using namespace std;
void main()
{
int n;
cout << “How many students? “;
cin >> n;
int *grades = new int[n];
for(int i=0; i < n; i++){
int mark;
cout << “Input Grade for Student” << (i+1) << “ ? :”;
cin >> mark;
grades[i] = mark;
}
. . .
printMean( grades, n ); // call a function with dynamic array
. . .
}
Pointers and dynamic objects/ Slide 41
Freeing (or deleting) Memory
Pointers and dynamic objects/ Slide 42
A Simple Dynamic List Example
cout << "Enter list size: ";
int n;
cin >> n;
int *A = new int[n];
if(n<=0){
cout << "bad size" << endl;
return 0;
}
initialize(A, n, 0); // initialize the array A with value 0
print(A, n);
A = addElement(A,n,5); //add an element of value 5 at the end of A
print(A, n);
A = deleteFirst(A,n); // delete the first element from A
print(A, n);
selectionSort(A, n); // sort the array (not shown)
print(A, n);
delete [] A;
Pointers and dynamic objects/ Slide 43
Initialize
void initialize(int list[], int size, int value){
for(int i=0; i<size; i++)
list[i] = value;
}
Pointers and dynamic objects/ Slide 44
print()
void print(int list[], int size) {
cout << "[ ";
for(int i=0; i<size; i++)
cout << list[i] << " ";
cout << "]" << endl;
}
Remember in C++, array parameters are always passed
by reference. That is, void print(int list[], int size) {…} is the same as
void print(int * list , int size) {…}
Note: no & used here, so, the pointer itself is passed by value
Pointers and dynamic objects/ Slide 45
Adding Elements
// for adding a new element to end of array
int* addElement(int list[], int& size, int value){
int* newList = new int [size+1]; // make new array
if(newList==0){
cout << "Memory allocation error for addElement!" << endl;
exit(-1);
}
for(int i=0; i<size; i++)
newList[i] = list[i];
if(size) delete [] list;
newList[size] = value;
size++;
return newList;
}
Pointers and dynamic objects/ Slide 46
Delete the first element
// for deleting the first element of the array
int* deleteFirst(int list[], int& size){
if(size <= 1){
if( size) delete list;
size = 0;
return NULL;
}
int* newList = new int [size-1]; // make new array
if(newList==0){
cout << "Memory allocation error for deleteFirst!" << endl;
exit(-1);
}
for(int i=0; i<size-1; i++) // copy and delete old array
newList[i] = list[i+1];
delete [] list;
size--;
return newList;
}
Pointers and dynamic objects/ Slide 47
Adding Element (version 2)
// for adding a new element to end of array
// here “list” is a reference to a pointer variable: if the value of
the pointer is changed in function, the change is global.
void addElement( int * & list, int & size, const int value ){
int * newList = new int [size + 1];
if( newList == NULL ){
cout << "Memory allocation error for addElement!" << endl;
exit(-1);
}
for( int i = 0; i < size; i++ )
newList[ i ] = list[ i ];
if( size ) delete [] list;
newList[ size ] = value;
size++;
list = newList;
return;
}
Pointers and dynamic objects/ Slide 48
Deleting Element (version 2)
void deleteFirst( int * & list, int & size ){
if( size <= 1 ){
if( size )
delete list;
list = NULL;
size = 0;
return;
}
delete list; // delete the first element
list++;
size--;
return;
}
Pointers and dynamic objects/ Slide 49
Another Main program
int main(){
int * A = NULL;
int size = 0;
int i;
for( i = 0; i < 10; i++ )
addElement( A, size, i );
for( i = 0; i < 10; i++ )
cout << A[i] << " ";
cout << endl;
for( i = 0; i < 4; i++ )
deleteFirst( A, size );
for( i = 0; i < 6; i++ )
cout << A[i] << " ";
cout << endl;
0123456789
return 0; 456789
}
Pointers and dynamic objects/ Slide 50
Dangling Pointer Problem
int *A = new int[5];
for(int i=0; i<5; i++)
A[i] = i;
int *B = A;
A
0 1 2 3 4
B
delete [] A; Locations do not belong to program
B[0] = 1; // illegal!
A —
?
B
Pointers and dynamic objects/ Slide 51
Memory Leak Problem
int *A = new int [5];
for(int i=0; i<5; i++)
A[i] = i;
A 0 1 2 2 3 4
These locations cannot be
A = new int [5]; accessed by program
A 0 1 2 3 4
— — — — —
Pointers and dynamic objects/ Slide 52
A Dynamic 2D Array
A dynamic array is table
an array of pointers 32 18 12 24
to save space when table[0]
not all rows of the table[1] 13 11 16 12 42 19 14
array are full. table[2]
22
table[3]
int **table; table[4] 13 13 14
table[5]
11 18
table = new int*[6];
…
table[0] = new int[4];
table[1] = new int[7];
table[2] = new int[1];
table[3] = new int[3];
table[4] = new int[2];
table[5] = NULL;
Pointers and dynamic objects/ Slide 53
Memory Allocation
int **table;
table = new int*[6];
table[0]= new int[3];
table[1]= new int[1];
table[2]= new int[5];
table[3]= new int[10];
table[4]= new int[2];
table[5]= new int[6];
table[0][0] = 1; table[0][1] = 2; table[0][2] = 3;
table[1][0] = 4;
table[2][0] = 5; table[2][1] = 6; table[2][2] = 7; table[2]
[3] = 8; table[2][4] = 9;
table[4][0] = 10; table[4][1] = 11;
cout << table[2][5] << endl;
Pointers and dynamic objects/ Slide 54
Memory Deallocation
Memory leak is a serious bug!
Each row must be deleted individually
Be careful to delete each row before deleting
the table pointer.
for(int i=0; i<6; i++)
delete [ ] table[i];
delete [ ] table;
Pointers and dynamic objects/ Slide 55
Create a matrix of any dimensions, m by n:
Put it into a function:
nt m, n; int m, n;
cin >> m >> n >> endl;
in >> m >> n >> endl;
int** mat;
mat = imatrix(m,n);
nt** mat; …
at = new int*[m]; int** imatrix(nr, nc) {
int** m;
m = new int*[nr];
or (int i=0;i<m;i++) for (int i=0;i<nr;i++)
mat[i] = new int[n]; m[i] = new int[nc];
return m;
}
