Arrays

An array is the basic data structure that provides a collection of data contiguously stored in memory. Many adapters, such as the stack, are implemented using arrays. Their uniqueness is that array elements are all of the same type, which plays a key role in accessing array elements. For example, the following declaration creates an array of 10 integers:

int arr[]{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};

The name of the array decays to a pointer to its first element. Considering the fact that array elements have the same type, we can access any element of the array by advancing the pointer to its first element. For example, the following code prints the third element of the array: 

std::cout << *(arr + 2);

The same goes with the first element; the following three lines of code are doing the same thing:

std::cout << *(arr + 0);
std::cout << *arr;
std::cout << arr[0];

To make sure that arr[2] and *(arr + 2) do the exact same thing, we can do the following:

std::cout << *(2 + arr);

Moving the 2 behind the + won't affect the result, so the following code is valid as well:

std::cout << 2[arr];

And it prints the third element of the array.

An array element is accessed in constant time, which means accessing the first and the last elements of the array takes the same amount of time. It's because every time we access an array element, we do the following:

1. Advance the pointer by adding the corresponding numeric value
2. Read the contents of memory cells placed at the result pointer 

The type of the array indicates how many memory cells should be read (or written). The following diagram illustrates the access:

This idea is crucial when creating dynamic arrays, which are arrays that are located in the heap rather than the stack. As we already know, allocating memory from the heap gives the address of its first byte, so the only chance to access elements other than the first one, is by using pointer arithmetic:

int* arr = new int[10];
arr[4] = 2; // the same as *(arr + 4) = 2 

We will discuss more about the structure of arrays and other data structures in Chapter 6, Digging into Data Structures and Algorithms in STL.