Arrays

An array consists of several of the same type of thing stored in consecutive memory addresses. If A is an array, then A[i] is the i-th thing in array A. All subscripting is from 0 in C/C++. So if you have an array A of four things, then those things are A[0], A[1], A[2] and A[3].

A[i] is a variable. You can get its value, and assign a new value to it.

Creating an array in the run-time stack

You can create an array in any area of memory. To create an array in the run-time stack, you declare it inside a function. Write
int x[20];
to declare an array x of 20 integers (numbered 0 to 19). Some versions of C++ allow the size to be any expression, but others require the size to be a constant, not something that you compute. When the size is a constant, you almost always use a named constant to select the size. That way, it is easy to modify the size later. You write, for example,
const int namesize = 40; char name[namesize];
Normally, the constant is put someplace where it can easily be found and changed. You can make the constant global.

If you are not declaring an array, but are merely referring to one that is created elsewhere (as you do in a parameter list of a function heading) you do not need to give the size. You can write int x[] to indicate that x is an array of integers that was created by somebody else.

Creating an array in the run-time stack
You can create an array in any area of memory. To create an array in the run-time stack, you declare it inside a function. Write int x[20]; to declare an array x of 20 integers (numbered 0 to 19). Some versions of C++ allow the size to be any expression, but others require the size to be a constant, not something that you compute. When the size is a constant, you almost always use a named constant to select the size. That way, it is easy to modify the size later. You write, for example, const int namesize = 40; char name[namesize]; Normally, the constant is put someplace where it can easily be found and changed. You can make the constant global. If you are not declaring an array, but are merely referring to one that is created elsewhere (as you do in a parameter list of a function heading) you do not need to give the size. You can write `int x[]` to indicate that x is an array of integers that was created by somebody else.

Equivalence of arrays and pointers

In C/C++, an array is really just the address where the array begins. So it is a pointer to the first thing in the array. If you declare array x by
int x[20];
then x itself has type int* -- a pointer to an integer. It points to the first integer in the array. Recall that, when p is a pointer, p[i] abbreviates *(p+i). It is no different for arrays. A[i] abbreviates *(A+i).

An array is treated as the address of the first member of the array.

Equivalence of arrays and pointers
In C/C++, an array is really just the address where the array begins. So it is a pointer to the first thing in the array. If you declare array x by int x[20]; then x itself has type int* -- a pointer to an integer. It points to the first integer in the array. Recall that, when p is a pointer, p[i] abbreviates (p+i). It is no different for arrays. A[i] abbreviates (A+i). An array is treated as the address of the first member of the array.

Creating an array in the heap

Allocating an array in C++

To allocate an array of 20 chars in the heap in C++, you can write
char* p = new char[20];
Notice that p has type char*. Here, p will be set to the address of the first byte of the array. To set the third byte of this array to 'a', you would write
p[2] = 'a';
(Recall that the first byte is p[0].) One nice feature about allocation in the heap is that you can compute the amount of memory to allocate. If integer variable n has a value, then you can write
char* s = new char[n];
to allocate n bytes in the heap.

Deallocating an array in C++

To deallocate an array that was allocated using new, you use delete followed by []. For example,
delete[] s;
deletes the array that s points to. Use [] if and only if the memory was allocated using new T[...].

Allocating and deallocating arrays in C

To create an array in C, you can use standard function malloc. For example,
char* s = (char*) malloc(20*sizeof(char));
allocates 20 bytes, and stores the address of the first of those bytes into pointer variable s. Statement
int* x = (int*) malloc(10*sizeof(int));
makes x point to a newly allocated array of 10 ints.

To deallocate an array that was allocated using malloc, use function free. You say
free(x);
to deallocate the memory that pointer x points to, regardless of whether x points to one thing or a whole array.

WARNING. Never try to deallocate, or delete, just a part of an array that you have allocated. You can only deallocate the entire array.

Logical and physical size of an array

Often, you do not make use of all of the memory in an array. You might, for example, allocate some maximum size that you think you will need when you create the array. When you use the array, you typically find that you do not need all of that space.

At any given time, an array has two sizes. The physical size tells how much room is available. That is, it tells how large the array is. The logical size tells how much of the room is in use. Think of a hotel. The physical size is the number of rooms that the hotel has. The logical size is the number of occupied rooms.

It is important to remember the distinction between logical and physical size because one very common mistake is to use the physical size in a place where you really meant to use the logical size. Pay attention to that. Don't count on every room in the hotel being rented every night.

Logical and physical size of an array
Often, you do not make use of all of the memory in an array. You might, for example, allocate some maximum size that you think you will need when you create the array. When you use the array, you typically find that you do not need all of that space. At any given time, an array has two sizes. The physical size tells how much room is available. That is, it tells how large the array is. The logical size tells how much of the room is in use. Think of a hotel. The physical size is the number of rooms that the hotel has. The logical size is the number of occupied rooms. It is important to remember the distinction between logical and physical size because one very common mistake is to use the physical size in a place where you really meant to use the logical size. Pay attention to that. Don't count on every room in the hotel being rented every night.

Null-Terminated Strings

Arrays of characters are used to represent strings. The string begins at the beginning of the array, but it does not always occupy the entire physical size of the array. Instead, a marker is put in the array to indicate the end of the string. The marker is the null character, '\0'. For example, the string "abc" would be represented as an array as follows.

Address Content

p 'a'

p+1 'b'

p+2 'c'

p+3 '\0'

Note that the null is not the character '0'. When a null character is at the end of a string, it is called the null terminator of the string.

When you write "abc" in a C/C++ program, the compiler allocates four bytes, and fills them as shown above, with '\0' in the last byte. The type of "abc" is char* -- a pointer to the first byte of the string.

In general, strings are stored in two parts: the pointer, which serves as the handle of the string; and the memory that is pointed to, which holds the content of the string. When you deal with strings, you must be aware of these two parts. Even though you often think of a variable of type char* as holding a string, it does not actually point to any string until you set it to point to appropriate memory.