Dynamic arrays

A dynamic array is a random access, variable-size list data structure that allows elements to be added or removed.

Dynamic arrays overcome a limit of static arrays, which have a fixed capacity that needs to be specified at allocation.

In C++, the dynamic array is implemented as vector. The length of a C++ vector is not fixed, but all its elements should be of the same type, which is specified at allocation.

Declaration:

You start a vector declaration by using the vector keyword, then writing the type of the elements inside <>, along with the name of the vector, like this:

vector<string> sandwich;

You can also initialize a vector at declaration by using the = operator with an opening bracket, end it with a closing bracket, and put a comma between each entry, like this:

vector<string> sandwich = {"peanut butter", "jelly", "bread"};

You can also initialize a vector at declaration providing the number of elements and their initial value, like this:

//Vector consisting of 5 strings, all equal to "Andrew":
vector<string> sandwich(5, "Andrew");

Random access:

We can access the data inside vectors using indexes. Vectors use zero-based indexing, so the first element in a vector has an index of 0.

vector<int> array = {50, 60, 70};
int data = array[1];

// array[0] is 50, and data has the value 60

Appending:

An easy way to append data to the end of a vector is via the push_back() function.

.push_back() takes one parameter and "pushes" it onto the end of the vector.

Examples:

vector<int> arr1 = {1, 2, 3};
arr1.push_back(4);

// arr1 now has the value [1, 2, 3, 4]

Popping:

Another way to change the data in a vector is with the .pop_back() function.

.pop_back() is used to pop a value off of the end of a vector. It is a void function.

In other words, .pop_back() removes the last element from a vector, but doesn't return anything.

vector<int> threeArr = {1, 4, 6};
threeArr.pop_back();

// threeArray has now the value [1, 4];

Changing elements:

The entries of vectors are mutable and can be changed freely, using indices and the bracket notation.

vector<int> ourArray = {50, 40, 30};
ourArray[0] = 15;

// ourArray now has the value [15, 40, 30]

Getting the size:

We can get the size of a vector using the .size() function.

vector<int> ourArray = {50, 40, 30};
cout << ourArray.size();

ourArray.pop_back();
cout << ourArray.size();

// This will print 3, then 2

All the operations above are considered to take O(1) time to be executed.

Iterating through the elements:

We can iterate throught the elements of a vector using a for loop and the : operator like this:

vector<string> sandwich = {"peanut butter", "jelly", "bread"};
for (string ingredient : sandwich) {
    cout << ingredient << "\n";
}

// This will print the strings "peanut butter", "jelly" and "bread" on three separate lines

We can also iterate throught the elements of a vector using indices and a for loop like this:

vector<string> sandwich = {"peanut butter", "jelly", "bread"};
for (int i = 0; i < sandwich.size(); i++) {
    cout << sandwich[i] << "\n";
}

// This will print the strings "peanut butter", "jelly" and "bread" on three separate lines

Both ways take O(n) time, where n is the length of the array we iterate on.

How the dynamic array works behind the scenes is not trivial and you might be asked to explain this in interviews. So make sure you watch this video to fully understand how the dynamic array operates: