Data Structures & Algorithms

Let's start with a simple definition. A data structure is just a specific way of arranging bits in RAM. It's a physical layout. When you boil it all down, there are really only two fundamental ways to arrange a collection of objects in memory.

In a contiguous layout, all objects are packed together, side-by-side, in one unbroken block of memory. This is the memory layout associated with array structures, such as std::array and std::vector.

In a linked layout, each object is stored in its own separate chunk of memory, potentially miles apart from its neighbors. Each object holds the memory addresses of any other nodes that it is linked to. The most basic form of this are linked lists, such as std::list and std::forward_list.

More complex linked structures can be created by allowing multiple connections between nodes.

Even more advanced techniques can integrate both linking and contiguous layouts within the same structure. We can have linked lists of arrays, arrays of links to arrays, and any other combination that might be useful for the problem we're trying to solve.

If a data structure defines the shape of information, an algorithm defines the movement of that information. An algorithm is simply a set of mechanical steps to read or modify a data structure.

The shape and the movement are intrinsically linked. You can't separate them. How fast a task can be completed, and the steps an algorithm must perform to do so, is completely dependent on the physical layout of the data.

Let's consider a simple task: find the 500th player in a collection of 1000 players. How we perform this task, and therefore how quickly it can be completed, depends entirely on how the players are structured in memory

With a linked list, we start at the first player, grab the address of the second, jump to that address, grab the address of the third, and so on. We have to perform 499 pointer-hops across memory to get to the 500th element.

With a contiguous array, we instead do some math. If the array starts at memory address $A$ and each player object is $S$ bytes in size, then the 500th player is located at address $A + (499 \times S)$. We can calculate the exact address and jump there in a single operation.

When we use a std::array or std::vector, it packages this algorithm as operator[], so we can just call MyArray[500] instead. Overloading the [] operator to provide this friendly interface is an example of a zero-cost abstraction.

A common fear is that high-level features - classes, methods, templates - add "overhead" and make the code slower. This is a myth.

The guiding philosophy of C++ is the zero-cost abstraction principle, sometimes called the zero-overhead principle. It has two main parts:

1. What you don't use, you don't pay for.
2. What you do use, you couldn't code any better by hand.

This means a C++ class with a method or overloaded operator should compile down to assembly code that is just as efficient as a C implementation using standalone functions. The abstraction exists to help the programmer organize code and prevent bugs; it should not cost performance at runtime.

Here is a simple C-style program that updates a player's health:

1#include <stdio.h>
2
3// The "Shape" of our data
4typedef struct {
5  int id;
6  int health;
7} Player;
8
9// The "Movement" of our data
10void take_damage_c(Player* p, int amount) {
11  p->health -= amount;
12}
13
14int main() {
15  Player p{1, 100};
16  take_damage_c(&p, 10);
17  printf("Player Health: %d\n", p.health);
18  return 0;
19}

This is straightforward. We define a data layout with struct and a separate function to manipulate it. Now, here's the equivalent, idiomatic C++ code.

1#include <stdio.h>
2
3// The "Shape" and "Movement" combined
4class Player {
5public:
6  int id;
7  int health;
8
9  void take_damage(int amount) {
10    health -= amount;
11  }
12};
13
14int main() {
15  Player p{1, 100};
16  p.take_damage(10);
17  printf("Player Health: %d\n", p.health);
18  return 0;
19}

The C++ version uses a class, bundling the data - health - and the operation - take_damage() together. To the programmer, this helps with organization and safety. But what does the compiler do? It makes sure that we're using the class as designed, respecting rules like not changing const variables or accessing private members. And then it deletes it all.

The generated machine code for both the C and C++ version is often bit-for-bit identical. The class, the public keyword, the member function - they are all compile-time constructs that help us write better code. They have no runtime cost, because they don't exist at runtime. They are zero-cost abstractions.

This allows us to build safe, friendly, and highly organized systems without sacrificing control over the underlying machine. We get to work with helpful abstractions like std::vector and std::sort(), knowing they are just well-engineered wrappers over the raw, mechanical reality of memory and CPU instructions.

Advanced: Checking Compiler Output

Compiler Explorer provides a convenient way to see the exact output of different programs across a range of compilers.

By default, the output may not be exactly the same for C++ and C variations of the same program. This is because compilers use "Debug" mode by default, and the C++ variation will include more debugging helpers.

These are helpful when developing, but they have a performance cost. To see the zero-overhead principle in action, we pass flags to convince the compiler to build in a "Release" configuration. In GCC or Clang, the two most important flags for this are -O3 -DNDEBUG.

We've established the core principles that will guide us through this course:

1. Data Has Shape: Data structures are physical memory layouts, primarily categorized as contiguous or linked.
2. Algorithms Are Movement: How efficiently a problem can be solved and the steps than an algorithm needs to take are dictated by the shape of the data it operates on.
3. Zero-Cost Abstractions: C++ allow us to write clean, high-level code that compiles down to ruthlessly efficient machine instructions.

In the next lesson, we will explore the hardware in more depth, understanding how the CPU and memory systems actually work. We'll look at the massive performance gap between the CPU's caches and main RAM, which is the root cause of almost all performance problems in modern software.