This changes everything ...

Up till now, a program couldn't store -- couldn't remember -- anything except in variables. This meant that the program couldn't remember more data than the number of variables than the programmer put into the program. Essentially the program can't remember more data than the programmer typed in while creating the program.

Arrays shatter that limitation: An array is a single variable with which a program can store and retrieve a nearly limitless amount of data.

How to use an array

For example, you can create and use an array of 10 ints as follows:

1. Ask for 10 consecutive int objects in memory.
2. Have a variable that points to the first of these.
3. From this pointer variable you access a particular one of the 10 ints by index.

Allocating space for an array: new operator

For example, to allocate 10 ints in memory and set p to point to the first of them, we'd write:

int* p; // declare a pointer p p = new int[10]; // p points to a newly allocated array of 10 ints

new type[number]

Accessing the items of an array: index

int* p; // declare a pointer p p = new int[10]; // p points to a newly allocated array of 10 ints

At this point, we can access any of these int objects by the indices 0,1,2,3,4,5,6,7,8,9. For example:

• To get the first int in the array, we write p[0].
• To get the second int in the array, we write p[1].
• To get the third int in the array, we write p[2].
• ...
• To get the last int in the array, we write p[9].

In summary:

The following picture depicts what's going on when we create an array of 4 ints and assign a value to one of the ints in the array.

DECLARE VARIABLES		Notes on scope: The pointer is a variable with name and scope like we're used to. That is, the pointer p is a local variable of main, and is part of that function call record on the stack.
ALLOCATE SPACE		Notes on scope: However, the array that pointer points to is in a different area of the program's memory called, the heap. The array itself is not part of any function call record on the stack. That's what this picture is showing you.
ASSIGN A VALUE

Dereference (i.e., *) and indexing (i.e., [])

Since p points to the first element of the array, *p is actually the same as p[0]. Applying the same logic, it also holds that p[i] is the same as *(p+i).

p[i] is equivalent to *(p+i)

A Simple Problem

Note that since we can access each element of an array by index, we could access them in any order, including in reverse order.

int main()
{
  // Get number of doubles from user
  int n;
  cout << "How many doubles? ";
  cin >> n;

  // Construct array
  double* A;
  A = new double[n];

  // Read numbers
  cout << "Enter " << n << " doubles: ";
  for(int i = 0; i < n; i++)
    cin >> A[i];

  // Write in reverse order
  cout << "In reverse your numbers are: ";
  for(int j = n - 1; j >= 0; j--)
    cout << A[j] << " ";
  cout << endl;

  return 0;
}

The variable is just a pointer! Not the array itself!

If you keep this in mind, some things that might otherwise trip you up make perfect sense. For example:

• What happens when I assign one pointer to anther?

What's hopefully clear here is that by creating a new pointer q and setting q = p, we did not create a new array populated with the same integer values. We just created a new pointer and set it to point to the same old array.

Quick check

int* pa = new int[3];
int* pb = new int[3];
pa[0] = 1;  pa[1] = 2;  pa[2] = 3;
pb[0] = 6; pb[1] = 7; pb[2] = 8;

int* q;
q = pb;
q[1]++;
cout << pa[1] << " " << pb[1] << " " << q[1] << endl;

q = pa;
q[1]++;
cout << pa[1] << " " << pb[1] << " " << q[1] << endl;

2 8 8
3 8 3

Objects allocated with new have no scope and live until you kill them

So, for example, if you wrote a function that called new to allocate some space, the objects in memory created by new would not be destroyed when the function returned, even though the pointer we had goes out of scope.

Take this example:

Before the function call
During the function call
After the function call

Destroying an array: delete []

For example:

char* p;
p = new char[30]; 	// creates 30 consecutive char's in memory
delete [] p;        // destroys the objects created by new

A note on types

bool* B = new bool[10];

If we have the declaration

string* A = new string[20];

Each element of an array is an lvalue.

This means that A[5] is not a copy of the index-5 element of the array, it is the actual index-5 element. You can modify it. For example:

• The following code snippet is perfectly valid.

  
  string* A = new string[20];
  A[5] = "hello";
  

• The following code snippet is perfectly valid, too:

  
  int* C = new int[10];    // C has type int*
  cin >> C[2];             // read an integer from the user to C[2]
  C[2]++;                  // increment C[2]
  

  You might wonder how an expression C[2]++ should be evaluated. If you look at the operator precedence table (under resources) you'll see that [.] has very high precedence, so C[2]++ evaluates as (C[2])++.

Quick check

string* A = new string[20];
A[5] = "hello";

Declaring multiple pointer variables at the same time

int* p, q;    

int *p, *q;   

int* p;      
int* q;

If you wanted both p and q to be "pointers to ints", you'd have to write

int *p, *q;   // now you are declaring two pointers!!

This is unfortunate; it's just because the syntax of C++ is inherited from that of C. For this reason, when it comes to pointers, we recommend that you always declare a single pointer variable.

Practice Problems

1. Write a program to compute dot-products of vectors. If v = [a1,a2,...,am] and w = [b1,b2,...,bm] are two vectors of dimension m, the dot product of v and w is a1*b1 + a2*b2 + ... + am*bm. Your program will get a dimension m from the user, read in two vectors of length m, and print out their dot product. Here's a sample run:

   Enter dimension: 4
   Enter two vectors: 
   [3,-1,0,2]
   [5,0,9,-7]
   Dot product = 1

   Try it for yourself and then take a look at a solution.

2. Write a program that reads a list of banned words from a file, stores them in an array, and then simply reads words from the user and returns "banned" or "not banned" until the word "end" is encountered. The file starts with a number, which is the number of banned words, and then the words themselves are listed. The file banned.txt is a good example. Here's a solution.

Do you know...

1. How do you create an array of 10 doubles?
2. How do you delete an array?
3. Consider two pointer variables p and q. When q=p; is executed, will the whole array be copied?

   Answer: No

4. Consider the following code:

   int* p = new int[n];

   • What is the type of p?
   • What is the type of p[0]?
   • What should be the type of n?