Adt lab/pointers

This is part of adt lab.

Pointers

In C/C++, there is a special kind of types: pointers. Pointer variables keep locations in the memory. These locations are also referred to as memory "addresses". To declare a pointer variable, we use symbol *:

type* variable;

For example, the following code declares p as a pointer to an integer.

  int* p;

To see how pointers work, let's follow this code.

  int a = 10;
  int b = 20;

  p = &a;
  cout << (*p) << endl;

  *p = 100;
  cout << a << endl;

  a++;
  cout << (*p) << endl;

  p = &b;
  a = *p;
  cout << a << endl;

Let's look at each step.

  p = &a;                   // step 1

To obtain a location of any variable, we use operator & (called a reference operator). After step 1, p keeps the location of a.

  *p = 100;                 // step 2

To dereference a pointer variable, we use operator *. Therefore *p refers to the "data" at the location that p points to. After step 2, *p (which is essentially a) becomes 100.

  a++;                      // step 3

As p points to a's location, if we change the value of a, *p also changes (because it is the "same" piece of data).

  p = &b;                   // step 4
  a = *p;

We can change p to point to other places.

Can we see the value of the pointer?

We can add the following line into the program after each pointer assignment.

  cout << "p: " << p << endl;

This is the output.

p: 0x7ffd9329b338
10
100
101
p: 0x7ffd9329b33c
20

The program outputs memory locations in base-16 integers. Note that the locations 0x7ffd9329b338 and 0x7ffd9329b33c in your machine and each program execution may be different. These depend on where the program is loaded into the memory and how the memory allocation actually works.

Passing parameters by reference

In C, function parameters are passed by value only. Therefore, if you want to write function swap that swaps two variables, you cannot do it like this:

void swap(int a, int b)
{
  int temp = a;
  a = b;
  b = temp;
}

  // ...
  int x = 10;  int y = 100;
  swap(x,y);
  // ... nothing changes here ...

The reason for that is that the code only modifies "local" copies a and b of x and y.

Pointers come to rescue.

If you can only pass-by-value, the only way a function can modify variables outside its scope, it to pass their address to the function.

void swap(int* a, int* b)
{
  int temp = *a;
  *a = *b;
  *b = temp;
}

  // ...
  int x = 10;  int y = 100;
  swap(&x,&y);
  // ... now x = 100, y = 10

As a quick rule, if you want a function to change a variable, pass it as a pointer, then use it "indirectly" through the pointer.

Reference types

To make our life better, C++ introduces reference types. Function swap can be written like this.

void swap(int& a, int& b)
{
  int temp = a;
  a = b;
  b = temp;
}

  // ...
  int x = 10;  int y = 100;
  swap(x,y)
  //  .. now it works!: x = 100, y = 10

Behind the scene, the implementation is pretty much like the pointer version, but it is done automatically by the compiler.

Pointer arithmetics

You can do arithmetic operations with pointers. Try to figure out how it works with this example.

Notes: We work with arrays in this example. However, the pointers actually point the the locations of the elements in the arrays. We use arrays because elements in arrays are allocated continuously on single piece of space in the memory.

  int a[10];
  double d[10];

  cout << "loc. of a[0]: " << &(a[0]) << endl;
  cout << "loc. of a[1]: " << &(a[1]) << endl;
  cout << "loc. of a[5]: " << &(a[5]) << endl;
  cout << "loc. of d[0]: " << &(d[0]) << endl;
  cout << "loc. of d[1]: " << &(d[1]) << endl;

  cout << "size of: int = " << sizeof(int) << ", double = " << sizeof(double) << endl;

  int* p = &a[0];
  cout << "p: " << p << endl;
  cout << "p+1: " << p + 1 << endl;
  cout << "p+5: " << p + 5 << endl;

  double* q = &d[1];
  cout << "q: " << q << endl;
  cout << "q+1: " << q + 1 << endl;

  int* r = &a[4];

  cout << "r - p: " << r - p << endl;

This is the output.

loc. of a[0]: 0x7ffe89a801a0
loc. of a[1]: 0x7ffe89a801a4
loc. of a[5]: 0x7ffe89a801b4
loc. of d[0]: 0x7ffe89a801d0
loc. of d[1]: 0x7ffe89a801d8
size of: int = 4, double = 8
p: 0x7ffe89a801a0
p+1: 0x7ffe89a801a4
p+5: 0x7ffe89a801b4
q: 0x7ffe89a801d8
q+1: 0x7ffe89a801e0
r - p: 4

Not only that we can use pointer arithmetic to calculate locations, we can refer the the data in that locations with the dereference operator as usual:

  *(p+1) = 100;   // this set a[1] to 100, because p+1 points to a[1]

Pointers and arrays

This is the most fascinating topics for new C/C++ programmers. As the previous example, since an element in an array is stored in the memory, it has a location and we can use a pointer to reference it. It turns out that the array variable itself can be used to refer to the first element in it.

  int a[100];

  int* p = &a[0];

  cout << "a: " << a << endl;
  cout << "p: " << p << endl;

  p++;

  cout << "p: " << p << endl;
  cout << "&a[1]: " << &a[1] << endl;

  a[5] = 100;

  cout << "a[5]: " << a[5] << endl;
  cout << "*(p+4): " << *(p+4) << endl;
  cout << "p[4]: " << p[4] << endl;

This is the output:

a: 0x7ffd2e480e70
p: 0x7ffd2e480e70
p: 0x7ffd2e480e74
&a[1]: 0x7ffd2e480e74
a[5]: 100
*(p+4): 100
p[4]: 100

From the example we can see that pointers are very flexible. We can use them as if they are arrays. We sometimes use this property when we want to pass an array to a function.

int sum(int* a, int n)
{
  int s = 0;
  for(int i=0; i<n; i++) {
    s += a[i];
  }
  return s;
}

Arrays are not pointers

Although we can use pointers and arrays interchangeably in many cases. They are not the same. Notably, you cannot assign new locations to an array.

  int a[100];
  int b[10];
  int* p;

  p = a;     // OK
  p = b;     // OK
  a = b;     // NOT OK

Also, assigning values to locations pointed by uninitialized pointers usually cause problems. So be careful when using pointers.

  int* p;

  *p = 0;     // compiles OK, but usually causes problems when running

Dynamic memory allocations

There are two ways to allocate memory. In C, you will use standard library: malloc and other related functions. In C++, there is a simpler way to allocate using the new operator.

  int* p = new int;
  double* q = new double;

You have to deallocate the memory that you allocate to the system after you finish using it using the delete operator. If you do not free the allocated memory, you might face "memory leak" problems.

To deallocate:

  delete p;
  delete q;

If you want to allocate array, you can call:

  int* p = new int[1000];

To free the memory, when you allocate arrays, you have to add []. THIS IS VERY IMPORTANT. Don't forget the [].

  delete [] p;

Strings and arrays of characters

In C, strings are stored in an array of characters. The characters are stored in the array from the first location to the end of the string; an additional zero character is stored after the last character to indicate the end of the string.

For example, string "hello" is stored in an array st like this:

s[0]: 'h'
s[1]: 'e'
s[2]: 'l'
s[3]: 'l'
s[4]: 'o'
s[5]: '\0'
s[6]: undefined

How to read strings

In C++, you can use string type to keep strings, and, as usual, you can use cin to read it.

  string st;
  cin >> st;

Standard string class provides many important string operations.

However, in our practice, we want you to work with arrays of characters. Therefore, we will use cin.getline.

  char st[1000];
  cin.getline(st,1000);

This function cin.getline(s,n) reads a string and write to an array s for at most n characters. The limit n prevents the function from overwrite the array.

Finding string length

The following code read a string with cin.getline and find the string length.

#include <iostream>
using namespace std;

int string_len(char* st)
{
  int len = 0;
  while(*st != '\0') {
    len++;
    st++;
  }
  return len;
}

main()
{
  char st[1000];
  int l;

  cin.getline(st,1000);
  l = string_len(st);

  cout << l << endl;
}