Typically, we don’t want to write algorithms that only work with one specific type of container, such as a std::vector. We’d prefer to write algorithms that work across a wide range of containers.

For example, the goal might be to write an algorithm that works across different array implementations such as std::vector, std::array, or even array views such as std::span. But perhaps it could also work with containers that use a different data structure entirely, such as linked list implementations.

Rather than having to write various implementations of our algorithm to support different access patterns, we can use a technique called iterators.

Iterators are a type of object like any other - these types are designed to support traversal through containers in a standardized way.

Instead of writing algorithms that work with containers, we can write algorithms that work with iterators. Then, any container type can be compatible with our algorithms - the container class just needs to provide a couple of member functions that can return iterator objects.

Similar to arrays like std::vector and std::array, a linked list lets us store a sequential collection of objects.

Unlike arrays, linked lists store their objects in a more free-form memory layout, that causes them to have different performance characteristics. We covered these characteristics, and their implications, in more detail in the previous lesson:

Earlier in the course, we introduced the concept of a multidimensional array (or vector), which we could use to represent more complex data structures.

For example, we could represent a 2D grid using an array of arrays:

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

1Top Left: 1
2Bottom Right: 9

This approach has a few drawbacks.

When we're programming, we're writing code to perform a specific task. An algorithm is a set of instructions - the procedure we ask the computer to perform - to complete that task.

For any task, there are a huge number of possible algorithms we can write to complete it. How do we decide on which one to use?

Typically, one of the main considerations we have is that we generally prefer algorithms that require fewer actions to complete. An algorithm that requires fewer instructions to complete its task is generally going to be able to complete that task faster.

Being conscious of the performance of our algorithms is particularly important in two scenarios:

1. Real-Time Graphics

If we are writing a program that involves real-time interactivity, we typically want to update the user's screen at least 60 times per second to make our application feel responsive.

This gives us approximately 16 milliseconds to generate each update. If one of the algorithms we use in that process takes 10 milliseconds, most of our budget is immediately gone.

2. Big Data

In other contexts, we might not be dealing with short timeframes - rather, we might be dealing with large amounts of data. If we're creating software that analyses a billion records, and our algorithm spends 10 milliseconds on each record, our program will take four months to run.

In the previous lesson, we introduced the concept of algorithm complexity, and "Big O" notation for categorizing different algorithms.

One of the example problems we used was creating an algorithm to determine if an array, such as a std::vector, contained any duplicate objects.

We saw we could solve it using the following algorithm, which has a quadratic run time, that is $O(n^2)$:

1bool HasDuplicate(std::vector<int>& Input) {
2  for (size_t i{0}; i < Input.size(); ++i) {
3    for (size_t j{0}; j < Input.size(); ++j) {
4      if (Input[i] == Input[j] && i != j) {
5        return true;
6      }
7    }
8  }
9  return false;
10}

In this lesson, we’ll introduce some techniques for writing better algorithms. A large component of this is creating data structures that are appropriate for the problems we’re trying to solve.

Inevitably, we will want to store a group of data that has the same type. For example, let's imagine we have 5 characters.

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

We may want to group these characters, to form a party. This is where arrays can help us. Arrays are objects designed to store a collection of other objects.

Under the hood, arrays are a contiguous block of memory, big enough to store all our objects. Therefore, to create an array, we need to know the type of objects it will contain, and how many of them we need to store.

At this point, we’ve covered how to create both dynamic arrays using std::vector, and statically-sized arrays using std::array.

However, there is another, older way to create arrays in C++. These are commonly called C-style arrays.

Where possible, we should avoid using them. They have many problems, and this lesson will cover some of them. However, they are a fundamental, built-in part of the language, so we should familiarise ourselves with them.

They crop up all the time when integrating with other APIs and libraries, so we’ll regularly encounter them.

In the previous lesson, we introduced classic, C-style arrays. We also outlined some of their main problems and recommended they not be used because of those issues.

But sometimes, we can’t avoid them. In complex projects, we’ll often integrate with third-party libraries, or APIs provided by the platforms or operating systems we’re building for. Those libraries may provide us with C-style arrays, or expect us to provide them as arguments for their functions.

C++20 introduced the std::span class to help us work with these arrays, while mitigating most of their problems.

In this lesson, we will delve into two important aspects of error handling: the std::terminate() function and the noexcept specifier. We will explore:

• What std::terminate() is and when it is used.
• How to customize the behavior of std::terminate() using std::set_terminate().
• The significance of the noexcept specifier and its impact on functions.
• Practical implications of noexcept in move semantics, and the std::move_if_noexcept() function.

A common scenario in exception handling is the need to store and transfer exceptions to other functions, and potentially rethrow those exceptions.

In this lesson, we delve into the nuances of rethrowing exceptions. We'll explore various scenarios, including conditional rethrowing, preventing data loss during rethrowing, and advanced techniques using std::exception_ptr.