Arrays

Array declaration and definition

Here are some float variables showing the duration of episodes in a series.

float episode_duration_min1 = 20.5;
float episode_duration_min2 = 20.5;
…
float episode_duration_min9 = 20.5;

Arrays let us create and access multiple variables of the same type under the same variable name.

float episode_duration_min[9] = {20.5, 20.5, 20.5, 20.5, 20.5, 20.5, 20.5, 20.5, 20.5};

The square brackets indicate that this is an array declaration. The number inside tells the compiler how many variables to declare.

You can define your array with an initializer list. This is the comma-separated list of values inside curly brackets.

The computer sets aside memory for the array before the program runs. This allows for better performance but requires a fixed size for the array. This means that the compiler needs to know the size of the array when the program compiles. You can't use a variable to set the size of the array.

Array Indexing

Each variable in the array is called an element.

The index is the placement of the element in the array. We access an element by putting its index inside square brackets.

int array = {1,2,3,4};

std::cout << array[2]; // This will print 3

The index of an array starts at 0, which means that array[0] refers to the first element in an array. The code above will print the 3rd element, which has a value of 3. The last element will have an index that's one smaller than the size of the array.

In an array of size 4 (int array_ex[4];) the element with index 4 would not exist since it's the 5th element (out of 4). Using array_ex[4] will give unpredictable results.

The compiler doesn't stop you from accessing elements outside the declared range. It might give you a warning, but your program will compile and run. Not only does it let you use indices that are equal to or higher than the size, but it also lets you use negative indices. If you try to access an element out of range, it will use the memory located where the element would be if it existed.

Think of an array of size 20 as a piece of paper with 20 lines. If you try to draw on the 22nd or -3rd line you would be drawing on the table.

Using data from outside the range will give you junk data. Changing the value of unknown data can lead to unexpected behavior - often crashing.

Pro tip: don't draw on the table.

Arrays in loops

We can use loops to go through array elements.

Declare a counting variable as 0 and continue the loop until the counting variable reaches the array-size. This ensures that you start at the first element and end with the last.

int your_array[8] = {0, 2, 4, 6, 8, 10, 12, 14};
int array_size = 8;
for (int i = 0; i < array_size; i++)
{
        std::cout << i << ", ";
}

0, 2, 4, 6, 8, 10, 12, 14,

Here is a program using multiple loops.

#include <iostream>

int main() 
{
	int number_arr[5];

	// fill array by prompting the user 5 times to fill in the array element with index i
	for (int i = 0; i < 5; i++)
	{
		std::cout << "enter number " << i <<"/5.\n";
		std::cin >> number_arr[i];
	}

	std::cout << "What do you want to find?\n1=smallest number\n2=largest number\n";
	int operation;
	std::cin >> operation;

	// This is checking if the user wants to find the smallest number
	if (operation == 1)
	{
		// We will get the smallest number by comparing the numbers in the array, This variable will hold the smallest number.
		int smallest_num = number_arr[0];
		// Since we already assigned number_arr[0] as a start, we can start looping at 1 instead of 0
		for (int i = 1; i< 5)
		{
			// If the number number_array with index i is smaller than our current largest number, we want to make it our current smallest number
			if (number_arr[i] > smallest_num )
				smallest_num = number_arr[i];
		}
		// Once we have compared all numbers and stored the smallest we can output it.
		std::cout << "The smallest number is: " << smallest_num ;
	}
	// This is checking if the user wants to find the largest number
	else if (operation == 2)
	{
		// We will get the greatest number by comparing the numbers in the array, This variable will hold the greatest number.
		int largest_num = number_arr[0];
		// Since we already assigned number_arr[0] as a start, we can start looping at 1 instead of 0
		for (int i = 1; i< 5)
		{
			// If the number number_array with index i is larger than our current largest number, we want to make it our current largest number
			if (number_arr[i] > largest_num)
				largest_num = number_arr[i];
		}
		// Once we have compared all numbers and stored the smallest we can output it.
		std::cout << "The largest number is: " << largest_num;
	}
	// This will only go through if the user inputs an operation that isn't supported
	else
	{
		std::cout << "You didn't input a valid operation";
	}

}

This program uses loops number_arr in 3 places. First to collect values for the elements. Then one of two loops run to compare all the elements.

sizeof

The sizeof operator tells you how much space on the computer a variable takes (measured in bytes).

Integers take up 4 bytes of space, so sizeof(intVariable) is evaluates as 4.

int example = 0;
std::cout << sizeof(example);

4

An array of 4 integers will have size 4 x 4bytes.

int arr[4] = {1,2,3,4};
int array_bytes = sizeof(arr); // this will be 16

array_bytes is 16.

We can use the sizeof operator to get the size of an array.

float array[5];
int array_size = sizeof(array) / sizeof(array[0])

array_size is 5.

This lets us write more modular code that won't break if we change the size of the array.

float number_array[5] = {3, 9, 27, 81, 243};
// Double the value of each entry
int number_array_size = sizeof(number_array) / sizeof(number_array[0]);
for (int i = 0; i < number_array_size; i++)
{
	number_array[i]*=2;
}

Here's an example of using sizeof to loop an entire array. This code doubles the value of each element.

You can also use this to access elements from the back of the array, instead of the front.

int test_arr[5] = { 2, 4, 6, 8, 10};
int arr_size = sizeof(test_arr) / sizeof(test_arr[0])
int last_element = test_arr[arr_size - 1]; // This will be 10

Keep in mind that the sizeof an array will be 1 higher than the index of its last element.

Multidimensional Arrays

You can make an array of arrays by adding another set of square brackets. This can be useful for representing grids or tables.

float multi_dimentional_array[3][4];

This is a 3x4 array, which means it stores 12 values in total.

You can add further dimensions by adding more sets of square brackets.

float multi_dimentional_array[10][3][4];

This is a 10x3x4 array that stores 120 float values

The last number is the innermost array size.

This will work

// [2][4] means 2 sets of 4
int multi_array[2][4] = { {1,2,3,4},{5,6,7,8} };

This will NOT work

// It does not mean 4 sets of 2
int multi_array[2][4] = { {1,2},{3,4},{5,6},{7,8}};

The first set of square brackets targets the outer array. The following brackets go deeper, selecting inner arrays.

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

    multi_array[2];
    std::cout << multi_array[1][2] << ", " << multi_array[1][0] << ", " << multi_array[0][2] << ", " << multi_array[1][3] <<;

6, 4, 3, 7

Arrays' technical implementation

When you declare a variable, the computer finds space for it and assigns that space to hold the data. It places it wherever there is space. This means that 2 variables declared next to each other can be at very different places in memory.

In an array; all the elements are next to each other in memory.

The array identifier(name) is an address to the first element's location. You can think of an address as directions to the variable. When we use the access operator array[x], it accesses the element located x spaces after the start.

Arrays in function parameters

You can pass an array into a function like this:

#include <iostream>

float get_greatest_value(float float_arr[5])
{
	float greatest_val = float_arr[0];
	for (int i = 0; i < 5; i++)
	{
		if (greatest_val < float_arr[i])
			greatest_val = float_arr[i];
	}

	return greatest_val;
}

int main() 
{
	float number_arr[5] = { 7, 6, 1, 2, 3};

	std::cout << "The largest value is: " << get_greatest_value(number_arr);
}

This is great, but limits the function to arrays of size 5.

The more flexible way is not passing a size for the array.

#include <iostream>

float get_greatest_value(float float_arr[], int arr_size = 5)
{
	float greatest_val = float_arr[0];
	for (int i = 0; i < arr_size; i++)
	{
		if (greatest_val < float_arr[i])
			greatest_val = float_arr[i];
	}

	return greatest_val;
}

int main() 
{
	float number_arr[5] = { 7, 6, 1, 2, 3};

	std::cout << "The largest value is: " << get_greatest_value(number_arr, sizeof(number_arr) / sizeof(number_arr[0]));
}

Passing float_arr[] without a size lets you use the function with any size array.

As mentioned earlier; the array identifier by itself is just the location of the first element of the array. Normally variables passed into a function are copied. This lets you freely change them inside the function without affecting variables passed into the function. However, arrays passed into the function are passed by address (the location of the first element). When we pass an address, we are passing directions to a variable. Even though the directions are a copy, they still lead to the same place.

There are 3 notable consequences of the parameter being an address.

1. Changes to the array inside the function will change the original array.
2. The argument passed has to be an address. This means that the argument has to be the array identifier, like in the example above. You cannot pass an initializer list.
3. The function doesn't have access to the size of the array, so the sizeof operator doesn't work. To fix this, we can include a parameter to pass the information about the array's size.

We will cover addresses and how variables and arrays function in memory later in the course.

Dynamic arrays

Imagine a program that lets the user decide how many numbers they are going to input.

#include <iostream>

int main()
{
	std::cout << "How many inputs do you want?";
	int input_count;
	std::cin >> input_count;

	for (int i = 0; i < input_count; i++)
	{
		std::cout << "Input your number";
		std::cin >> ???; // Where can we save all our inputs?
	}
}

In this case, we don't know the size of the array before the program runs.

A dynamic array is an array that isn't fixed in size. This is good here because we won't know the size of the array before the program starts.

We can make dynamic arrays by manually doing what the compiler does when we declare an array. Then we re-allocate space for the array whenever its size changes. This can be bothersome and convoluted.

Luckily, C++ offers a very useful container for this called std::vector.

std::vector is located inside the <vector> header. It's a container for dynamic arrays. It gives us access to easy resizing of arrays with high performance and a high level of safety.

std::vector

To initialize a vector array, we type std::vector, followed by the datatype that we want our elements to be - inside of angle brackets (<>).

std::vector<float> our_dynamic_array = {1.4f, 12.f, 142.3f, 42.f};

You don't have to specify an array size because the size is adaptive. The size of the vector will adjust to the size of the initializer list.

We can loop through it like a normal array, and print out the numbers.

#include <iostream>
#include <vector>

int main()
{
	std::vector <int> arr = {10,20,30,40,50};
	for (int i = 0; i < 5; i++)
		std::cout << arr[i] << "\n";
}

10
20
30
40
50

std::vector has some unique functionality that we haven't encountered yet. We can call functions in relation to the container.

You can get the size of the vector by using the size() function. You do this by typing .size() after the vector name.

	std::vector <int> arr = {10,20,30,40,50};
	for (int i = 0; i < arr.size(); i++)
		std::cout << arr[i] << "\n";

When you do this, the function is called in relation to the vector object (in this case arr).

Functions called in relation to a container are called member functions, or methods. We'll cover them in more detail later when we get into designing our own datatypes.

When you pass std::vector to a function, all the data is copied, including the elements.

This means that changes inside the function won't affect the variables you pass into it. This also means that you can pass an initializer list as the function arguments. Member functions like size also keep working, so there's no need for an extra size parameter.

std::vector - push and pop

As mentioned earlier, when we declare a vector, it dynamically allocates memory to store elements. You can think of this as finding lines on a piece of paper with space to write down the elements on (one element per line).

Let's say that you are using lines 10-17 to hold an array of size 8. If you want to remove the element with index 4, you can't just erase what's on line 14, since the line is still there. You have to erase line 14 and move 15, 16, and 17 up one line. The same holds for elements in std::vector.

To insert or remove data in the middle, all the following elements need to be repositioned. This means that the back of the vector will be the most efficient place to add or remove elements.

.push_back(element) Adds a new element to the end of the vector.

.pop_back() Removes the last element of a vector.

Here is a program to demonstrate push_back:

#include <iostream>
#include <vector>

int main()
{
	std::cout << "Input numbers you want to sum.\nOnce you input 0 the summation will stop.\n";

	std::vector<float> numbers;
	while (true)
	{
		float input;
		std::cin >> input;

		// If the user input is 0 break/end the loop
		if (input == 0)
			break;

		numbers.push_back(input);
	}

	float sum = 0;
	// Looping through every numbers index
	for (int i = 0; i < numbers.size(); i++)
	{
		sum += numbers[i];
		// Using a ternary operator to output + after each number that isn't the last, and = after the last number.
		std::cout << numbers[i] << (i==numbers.size()-1 ? " = " : " + ");
	}

	std::cout << sum;
}

This program lets the user input numbers they want to sum. It outputs the equation together with the sum of the numbers.

It asks the user to input numbers to sum until they input the number 0. The 0 input indicates that they are done inputting numbers. For every input (except the last 0), we use push_back to add the number to our vector.

Once all the numbers are in our vector, we declare the sum variable and loop our array to add to it. Inside the loop, we also output each element followed by a + symbol. For our last element, we add = behind it instead. Then we output the sum.

std::vector::insert

You can use the insert() method to insert an element somewhere in the container.

The most basic version of the insert function takes 2 arguments. The first argument is the location you want to insert something. The second argument is what you want to insert.

std::vector<int> arr = {1, 2, 3, 4, 6, 7, 8, 9};
arr.insert(arr.begin() + 4, 5);

When specifying where you want to insert an element, we do so with iterators (arr.begin()). You can think of the iterator begin() as a pointer to the first element of arr. Iterators are also used in other STL containers that we cover later in the course.

After getting an iterator with the begin() function, you can add the index of where you want to insert your element.

Here, the number 5 will have an index of 4 once inserted. Once the code has run, arr will be {1,2,3,4,5,6,7,8,9}

Here are some function overloads for insert():

Inserting multiple copies of a value:

std::vector<int> our_vector = {1, 3, 4};
our_vector.insert(our_vector.begin() + 1, 3, 2); // Inserts three copies of value '2'

The value of our_vector is {1,2,2,2,3,4} after this code.

Inserting with an initializer list:

std::vector<int> our_vector = {1, 4};
our_vector.insert(our_vector.begin() + 1, {2, 3}); // Inserts 2, 3 starting at index 1

The value of our_vector here is {1, 2, 3, 4}

Inserting another vector's elements into a vector:

std::vector<int> vec1 = {1, 2, 5, 6};
std::vector<int> vec2 = {3, 4, 5, 6};

// The arguments here are ([the iterator location of vec1 to insert elements], [the iterator start of the elements], [The iterator end of the elements])
vec1.insert(vec1.begin() + 2, vec2.begin(), vec2.begin() + 2); // Inserts {3, 4} from the vector { 3, 4, 5, 6 }

// Will output: 1 2 3 4 5 6
for (int num : vec1)
	std::cout << num << " ";

std::vector::erase

The .erase() function removes an element from a vector.

The most basic version of the erase function takes the position of the element you want to remove as its only argument and removes that element.

Like the insert operator, we base our position on an iterator.

Here is a sequence of numbers interrupted by a stray number.

vector<int> sequence = {1, 2, 3, 4, 5, 6, 7, 12, 8, 9};

To remove the stray number, we use erase(begin() + 7), which removes the element with index 7.

vector<int> sequence = {1, 2, 3, 4, 5, 6, 7, 12, 8, 9};
sequence.erase(sequence.begin() + 7);
// The value of 'sequence' here is { 1, 2, 3, 4, 5, 6, 7, 8, 9 }

You can also remove a range of elements. To do so; specify the starting location as the first argument, and their end in the second argument (both using iterators).

vector<int> sequence = {1, 2, 3, 4, 5, 6, 7, 12, 8, 9};
sequence.erase(sequence.begin() + 8, sequence.begin() + 10);
// The value of 'sequence' here is { 1, 2, 3, 4, 5, 6, 7 }

Iterators

There are more iterators you can use for points of reference than .begin().

Here is a list of the basic iterators, and where they point to in a vector. The r in front of some of them stands for reverse. They are used for backward iteration.

std::vector<int> our_vector = {1,2,3,4,5,6,7,8};

.begin(): points to the start, or the first element (1)

.end(): points to one position after the last element (where 9 would have been)

.rbegin(): points to the end as if it was the first element (8)

.rend(): points one position before the first element.

It's important to note that .end(), and .rend() point to elements that do not exist. This has to be adjusted for when adding or subtracting to the location.

Iteration loops

This loop iterates over each element in an array and prints it. The index variable isn't used for anything else than iteration.

std::vector<int> int_vec = {1, 2, 3, 4, 5}; 
for (int i=0; i <  int_vec.size(); i++)
{
	std::cout << int_vec[i] << " ";
}

1 2 3 4 5 

When you want to iterate through a container like an array or vector and don't need an index variable you can use a range-based for-loop.

Here is the syntax:

std::vector<int> int_vec = {1, 2, 3, 4, 5};
for (int element : int_vec ) {
	std::cout << element << " ";
}

1 2 3 4 5 

In this example, element represents the current element of int_vec for each iteration. The loop will iterate over each element in the array, making the code cleaner and more concise.

The range-based for-loop is particularly useful when you need to perform operations on each element of a container and don't need access to the index variable. It provides a simpler and more intuitive way to loop through containers in C++.

By adding the & symbol to the element int& element : int_vec, we can create a reference to the element instead of a copy. This means that modifying it will change the value in the loop.

std::vector<int> int_vec = {1, 2, 3, 4, 5};
for (int element : int_vec )
	element = 1;
for (int element : int_vec )
	std::cout << element << " ";

1 2 3 4 5

std::vector<int> int_vec = {1, 2, 3, 4, 5};
for (int& element : int_vec )
	element = 1;
for (int element : int_vec )
	std::cout << element << " ";

1 1 1 1 1

std::deque

std::deque, pronounced "deck", is another dynamic array that allows for resizing. It's found in the <deque> header.

deque is short for "double-ended queue". The major difference from vectors lies in their double-endedness. This allows it to change the front of the array with .push_front() and .pop_front() in the same ways you would use .push_back() and .pop_back() for the back.

std::deque divides its elements into multiple blocks. This allows it to grow without frequent reallocations. This comes at the cost of being slower at accessing elements.

std::deque is a good option for std::vector if you need fast insertions and deletions at both ends.