Dynamic Arrays using std::vector

Inevitably, we will want to store a group of related objects. That might be a collection of characters in a party; a collection of buttons on a UI; and countless other use cases.

Let's imagine we have these objects, which we want to store and manage as a single collection:

1class Character {};
2Character Frodo;
3Character Gandalf;
4Character Gimli;
5Character Legolas;
6Character Aragorn;

Programmers have invented a huge range of options for storing collections of objects. These containers are broadly called data structures, and which data structure we should use depends on our specific requirements. We’ll cover a much wider range of data structures in the next course. Here, we’ll introduce the most common choice - the dynamic array.

Under the hood, arrays are a contiguous block of memory, big enough to store multiple objects in sequence.

There are hundreds of implementations of arrays in C++ that we can use, and we can even create our own once we learn more advanced topics. In this lesson, we’re using the standard library’s implementation of dynamic arrays, which is called std::vector.

A std::vector is simply a way to store objects - it doesn’t relate to the geometric notion of a vector which is often used to represent positions and movement. and forces. It’s just an unfortunately confusing name.

Creating an Array using std::vector

To use std::vector, we need to #include <vector>. We can then declare a vector by giving it a name, and specifying the type of objects it will contain within angled brackets: < and >. The following example shows how we can declare a std::vector called MyVector that stores int objects:

1#include <vector>
2
3std::vector<int> MyVector;

We can provide it with some initial values:

1#include <vector>
2
3std::vector<int> MyVector { 1, 2, 3, 4, 5 };

When we are initializing the values at the same time we declare the vector, we can optionally remove the type. The compiler can infer what type the vector will be storing, based on the type of objects we provided as its initial values:

1#include <vector>
2
3std::vector MyVector { 1, 2, 3, 4, 5 };

To do this, the compiler is using Class Template Argument Deduction (CTAD), which we’ll cover more in the intermediate course:

Accessing Items using the [] operator

We can access the members of our array using the subscript operator, which uses [] syntax. For example, to access an object within MyVector, we’d use Myector[x], where x is the index of the element we want to access.

The index of an element within an array is simply its position, however, the index is zero-based, meaning we start counting from 0. This means the first element of the vector is at index 0, the second element is at index 1, and so on.

For example, to access the elements of our vector, we would do this:

1#include <vector>
2
3std::vector MyVector { 1, 2, 3, 4, 5 };
4
5int FirstElement { MyVector[0] };
6int SecondElement { MyVector[1] };
7int ThirdElement { MyVector[2] };
8int LastElement { MyVector[4] };

As with all values, the index can be derived from any expression that results in an integer:

1#include <iostream>
2#include <vector>
3
4int CalculateIndex() { return 1 + 1; }
5
6int main() {
7  std::vector MyVector{
8    "First", "Second", "Third"};
9
10  // Log out the element at index 0
11  std::cout << MyVector[3 - 3] << '\n';
12
13  // Log out the element at index 1
14  int Index{1};
15  std::cout << MyVector[Index] << '\n';
16
17  // Log out the element at index 2
18  std::cout << MyVector[CalculateIndex()];
19}

This code logs out elements at indices 0, 1, and 2 in order:

1First
2Second
3Third

Array Size

The size of an array refers to the number of elements it currently contains. This is also sometimes called the "length" of the array.

The size() function returns the current size of our std::vector:

1#include <iostream>
2#include <vector>
3
4int main() {
5  std::vector MyVector{
6    "First", "Second", "Third"};
7
8  std::cout << "Size: " << MyVector.size();
9}

1Size: 3

Note that because indexing is zero-based, this means the last element of a vector is at an index of one less than its size(). For a vector of size 3, the last element is at index 2.

We can get the last element by applying this arithmetic within the subscript operator, or by using the back() function:

1#include <iostream>
2#include <vector>
3
4int main() {
5  std::vector MyVector{
6    "First", "Second", "Third"};
7
8  std::cout << "Last Element: "
9    << MyVector[MyVector.size() - 1];
10  std::cout << "\nLast Element: "
11    << MyVector.back();
12}

1Last Element: Third
2Last Element: Third

Adding Items to std::vector

Once our vector is created, we’ll often want to add more items to it. Typically, we want to add items to the end of arrays, as this has performance benefits over adding them to the start. We’ll cover the performance characteristics of containers in more detail in the next course.

std::vector and many other data structures provide two ways of adding objects:

• Pushing an object involves moving or copying an existing object into the container
• Emplacing an object involves creating a new object directly within the container

Creating an object in place has performance benefits over creating it elsewhere and then moving it so, where possible, we should prefer emplacing over pushing.

With std::vector, we’re adding items to the back of the container, so the respective functions are called: push_back() and emplace_back()

push_back()

If an object has already been constructed, and we want to add it to the back of our vector, we can use push_back():

1#include <iostream>
2#include <vector>
3
4class Character {
5 public:
6  std::string Name;
7};
8
9int main() {
10  Character Legolas{"Legolas"};
11  std::vector<Character> MyVector;
12  MyVector.push_back(Legolas);
13
14  std::cout << "First character: "
15    << MyVector[0].Name;
16}

1First character: Legolas

emplace_back()

If the object we want to add does not already exist, we can construct it right inside of the vector, using emplace_back().

The arguments we call emplace_back() with will be passed to the constructor of the object type the vector stores:

1#include <iostream>
2#include <vector>
3
4class Character {
5 public:
6  std::string Name;
7};
8
9int main() {
10  std::vector<Character> MyVector;
11  MyVector.emplace_back("Legolas");
12
13  std::cout << "First character: "
14    << MyVector[0].Name;
15}

Modifying Objects

We can modify objects in a std::vector as usual. We can replace the object using the assignment operator, =:

1#include <iostream>
2#include <vector>
3
4int main() {
5  std::vector MyVector{1, 2, 3};
6
7  std::cout << "Second number: "
8    << MyVector[1];
9  MyVector[1] = 42;
10  std::cout << "\nSecond number: "
11    << MyVector[1];
12}

1Second number: 2
2Second number: 42

We can also call functions on our objects as needed:

1#include <iostream>
2#include <vector>
3
4class Character {
5 public:
6  Character(std::string Name) : mName{Name} {}
7  std::string GetName() { return mName; };
8  void SetName(std::string Name){
9    mName = Name;
10  }
11
12 private:
13  std::string mName;
14};
15
16int main() {
17  std::vector<Character> MyVector;
18  MyVector.emplace_back("Roderick");
19
20  std::cout << "First character: "
21    << MyVector[0].GetName();
22  MyVector[0].SetName("Anna");
23  std::cout << "\nFirst character: "
24    << MyVector[0].GetName();
25}

1First character: Roderick
2First character: Anna

Storing Complex Types in Arrays

Our above example uses vectors with values, but we can store pointers and references in arrays too:

1#include <vector>
2
3class Character {};
4
5// A collection of characters
6std::vector<Character>;
7
8// A collection of character pointers
9std::vector<Character*>;
10
11// A collection of const character references
12std::vector<const Character&>;

Arrays can also store other arrays. This creates "multidimensional arrays". For example, a 3x3 grid could be represented as an array of 3 rows, each row being an array of 3 items

1#include <vector>
2#include <iostream>
3
4std::vector<std::vector<int>> MyGrid {{
5  { 1, 2, 3 },
6  { 4, 5, 6 },
7  { 7, 8, 9 }
8}};
9
10int main() {
11  std::cout
12    << "Top Left: " << MyGrid[0][0];
13
14  std::cout << "\nBottom Right: "
15    // Alternatively: MyGrid.back().back()
16    << MyGrid[2][2];
17}

1Top Left: 1
2Bottom Right: 9

1using Grid = std::vector<std::vector<int>>;
2
3Grid MyGrid {{
4  { 1, 2, 3 },
5  { 4, 5, 6 },
6  { 7, 8, 9 }
7}};

Passing std::vector Objects to Functions

We can treat a collection of objects like any other value. Below, we pass a collection to a function:

1#include <iostream>
2#include <vector>
3
4using Grid = std::vector<std::vector<int>>;
5
6void LogTopLeft(Grid GridToLog) {
7  std::cout << "Top Left: " << GridToLog[0][0];
8}
9
10int main() {
11  Grid MyGrid {{
12    { 1, 2, 3 },
13    { 4, 5, 6 },
14    { 7, 8, 9 }
15  }};
16
17  LogTopLeft(MyGrid);
18}

As with any other parameter, arrays are passed by value by default. The performance implications are particularly important here, as copying a collection of objects is inherently more expensive than copying a single object.

We can pass by reference in the usual way, with or without const:

1#include <iostream>
2#include <vector>
3
4using Grid = std::vector<std::vector<int>>;
5
6void LogTopLeft(const Grid& GridToLog) {
7  std::cout << "Top Left: " << GridToLog[0][0];
8}
9
10void SetTopLeft(Grid& GridToLog, int Value) {
11  GridToLog[0][0] = Value;
12}
13
14int main() {
15  Grid MyGrid {{
16    { 1, 2, 3 },
17    { 4, 5, 6 },
18    { 7, 8, 9 }
19  }};
20
21  SetTopLeft(MyGrid, 42);
22  LogTopLeft(MyGrid);
23}

1Top Left: 42

We can also generate and use pointers in the normal way. The following code replicates the previous example, using pointers instead of references:

1#include <iostream>
2#include <vector>
3
4using Grid = std::vector<std::vector<int>>;
5
6void LogTopLeft(const Grid* GridToLog) {
7  std::cout << "Top Left: "
8    << (*GridToLog)[0][0];
9}
10
11void SetTopLeft(Grid* GridToLog, int Value) {
12  (*GridToLog)[0][0] = Value;
13}
14
15int main() {
16  Grid MyGrid {{
17    { 1, 2, 3 },
18    { 4, 5, 6 },
19    { 7, 8, 9 }
20  }};
21
22  SetTopLeft(&MyGrid, 42);
23  LogTopLeft(&MyGrid);
24}

1Top Left: 42

Looping over Arrays using a for-loop

A common task we have when working with arrays is to perform some action on every object in the collection. We can do this with a for loop:

1#include <iostream>
2#include <vector>
3
4int main() {
5  std::vector MyVector{1, 2, 3};
6
7  for (int i{0}; i < MyVector.size(); ++i) {
8    std::cout << MyVector[i] << ", ";
9  }
10}

11, 2, 3,

Using the size_t type

There is an issue with using int values as the index of vectors: the size of vectors can be larger than the maximum value storable in an int.

To deal with this problem, we have the size_t data type. size_t is guaranteed to be large enough to match the largest possible size of the vector.

Because of this, it is the recommended way of storing vector indices:

1#include <iostream>
2#include <vector>
3
4int main() {
5  std::vector MyVector{1, 2, 3};
6
7  for (size_t i{0}; i < MyVector.size(); ++i) {
8    std::cout << MyVector[i] << ", ";
9  }
10}

11, 2, 3,

Using Range-based for-loops

Often, we usually don’t need to work with indices at all - we just want to iterate over everything in the vector.

For those scenarios, we can use this syntax:

1#include <iostream>
2#include <vector>
3
4int main() {
5  std::vector MyVector{1, 2, 3};
6
7  for (int Number : MyVector) {
8    std::cout << Number << ", ";
9  }
10}

11, 2, 3,

This is known as a range-based for loop. We cover these in more detail in the next course, including how to make our custom types compatible with this syntax.

Similar to functions, range-based loops can receive their parameters by reference or value, with value being the default. This means each item in the collection is copied into the body of the loop. We should consider passing by reference instead, particularly if the type we’re using is expensive to copy:

1#include <iostream>
2#include <vector>
3
4int main() {
5  std::vector MyVector{1, 2, 3};
6
7  for (int& Number : MyVector) {
8    std::cout << Number << ", ";
9  }
10}

11, 2, 3,

Just like when we’re passing by reference into a function if the loop body isn’t going to modify that reference, we should consider marking it as const:

1#include <iostream>
2#include <vector>
3
4int main() {
5  std::vector MyVector{1, 2, 3};
6
7  for (const int& Number : MyVector) {
8    std::cout << Number << ", ";
9  }
10}

11, 2, 3,

Memory Management: capacity() and reserve()

std::vector and other arrays keep our objects in contiguous blocks of memory on our system. As we push or emplace objects into our array, it may run out of space.

The std::vector class handles that scenario for us automatically - if it needs more space, it will move itself and all the objects it contains to a new, bigger location in memory with more space.

We can see how much capacity the current memory location has using the capacity() function:

1#include <iostream>
2#include <vector>
3
4int main() {
5  std::vector MyVector{1, 2, 3, 4, 5};
6
7  std::cout << "Capacity: " << MyVector.size()
8    << "/" << MyVector.capacity();
9
10  MyVector.emplace_back(6);
11
12  std::cout << "\nCapacity: " << MyVector.size()
13    << "/" << MyVector.capacity();
14}

1Capacity: 5/5
2Capacity: 6/7

Here, we see the std::vector initially has a capacity of 5, with all 5 spaces being taken. When we push a 6th object, the vector needs to move everything to a new, bigger location.

This new location has enough space to store 7 objects. We’re currently only storing 6, so we have room for one more before it needs to move again.

Proactively Reserving Space with reserve()

Moving a vector to a new location has a performance cost, so if we’re able to reduce movements, we should consider it.

If we know how many objects our std::vector is likely to need to store, we can directly reserve() it. Below, we ask our std::vector to move to a location with room for 100 objects:

1#include <iostream>
2#include <vector>
3
4int main() {
5  std::vector MyVector{1, 2, 3, 4, 5};
6  MyVector.reserve(100);
7
8  std::cout << "Capacity: " << MyVector.size()
9    << "/" << MyVector.capacity();
10}

Now, it has plenty of room to grow before it needs to move again:

1Capacity: 5/100

Naturally, a std::vector with a capacity for 100 objects will consume more system memory than one with a capacity of only 5.

But if we think it’s going to grow to 100 objects eventually anyway, we may as well just reserve that space from the start and eliminate all the expensive moving.

Summary

In this lesson, we've explored the essentials of dynamic arrays, with a particular focus on std::vector. You've learned how to create, access, modify, and efficiently manage collections of objects, laying a strong foundation for more advanced programming concepts.

Main Points Learned

• Understanding the difference between static and dynamic arrays, and the flexibility of std::vector.
• Creating, initializing, and accessing elements in a std::vector, including using push_back() and emplace_back() methods.
• Techniques for modifying elements within a std::vector, and the implications of passing vectors to functions.
• Managing complex data types and multidimensional arrays using std::vector.
• Effective looping through vectors using both traditional and range-based for loops, and the importance of size_t in managing vector sizes.
• How std::vector manages its capacity, and how we can interact with that mechanism using capacity() and reserve().

Preview of the Next Lesson

In the upcoming lesson, we'll delve into bitwise operators and bit flags. This topic involves manipulating data at the binary level, which is essential for certain types of low-level programming, optimization, and handling of compact data structures. We’ll cover:

• Binary Basics and Object Representation: Gain an understanding of binary numbers and how data is represented as a series of binary digits, or bits.
• Understanding Bitwise Operators: Learn about bitwise AND, OR, XOR, NOT, and how they are used to manipulate individual bits.
• Bit Flags and Bit Masks: Explore how to use bitwise operators to create and manipulate sets of options, often known as bit flags.
• Shifting Bits: Understand the use of left and right shift operators and their impact on data.
• Practical Applications: See real-world examples of how bitwise operations are used in areas like graphics programming, system programming, and optimizing memory usage.

Next Lesson

Bitwise Operators and Bit Flags

Unravel the fundamentals of bitwise operators and bit flags in this practical lesson

ContinueView Course