Chapter 4 - Notes

Array Basics

Characteristics of an Array

• An array is a collection of elements

• All elements contained in an array are of the same kind

• All elements in an array are stored sequentially in memory

Declaring and Initialising

• Array declaration

ElementType ArrayName [number of elements] = {initial value(s)}

• Per-element initialisation

int numbers[5] = {0, 1, 2, 3, 4};

• All elements at once

int numbers[5] = {0};

• Partial initialisation

int numbers[5] = {10, 20};  // First two initialised to 10, 20; the rest to 0

Such arrays are static arrays - the number of elements they contain (and memory it consumes) are constant and fixed at compilation time.

Arrays in Memory

• Elements are stored sequentially in memory, expanding in one direction

• Memory consumed by an array: (size of one element) * (number of elements)

Accessing Data in an Array

• Arrays in C++ are zero-indexed - arrays begin with index 0.

  • The first element in array numbers is numbers[0], the second is numbers[1]

  • The last element of an array of size n is n-1

• When accessing the element at index N, the compiler does the following:

  • Starts at the memory address of the first element

  • Skips N elements by adding the offset: N * (size of one element) to get the address of the element at index N.

In C++ the compiler does not perform bound checking, checking if the index is within the boundaries of the array.

It is the responsibility of the programmer to ensure that the array is never accessed beyond its bounds.

Modifying Data in an Array

• Assignment is similar to accessing: numbers[3] = value

• Remember that the Nth element is stored at index N-1 (zero-indexed)

Multi-dimensional Arrays

• Multi-dimensional arrays are arrays with more than one dimension

	Column 0	Column 1	Column 2
Row 0	Element 0	Element 1	Element 2
Row 1	Element 3	Element 4	Element 5

• The above two-dimensional array can be viewed as an array of 2 elements (2 rows), each element itself being an array of 3 elements (3 columns).

• The above can be declared as:

int table[2][3] = {{0, 1, 2}, {3, 4, 5}};

int table[2][3] = {
    {0, 1, 2},
    {3, 4, 5}
};

Multi-dimensional Arrays in Memory

• Although we can model multi-dimensional arrays, the underlying memory where the array is contained is one-dimensional.

• This means that the following syntax would also work:

int table[2][3] = {0, 1, 2, 3, 4, 5};

• The previous method of declaring an array-of-arrays is easier to picture and understand.

Accessing data in Multi-dimensional Arrays

• Think of multi-dimensional arrays as arrays whose elements are also arrays.

  • Use the first subscript to address the row where the element you want to access is

  • Use the second subscript to address the element in that row.

• Therefore, to address an element in row 0, column 2 of a two-dimensional array: table[0][2]

  • table[0] gives an array (row), which we further index into

Dynamic Arrays

• Dynamic arrays are arrays whose sizes are not fixed at compile-time (opposite of static arrays)

• C++ provides a convenient and easy-to-use dynamic array: std::vector

Usage

• Create a vector

std::vector<TYPE> myVector; 

• Create a vector with a predetermined size

std::vector<TYPE> myVector(5);  // Vector has 5 elements, uninitialised 

• Create a vector with initialised values

std::vector<TYPE> myVector(4, 0);  // Vector has 4 elements, all set to 0

• Get the size of a vector

myVector.size();