A quick crash tour of C++ basics, for those with previous object oriented programming experience.

An introduction to data structures and algorithms from a practical, hardware-first perspective. Learn how the physical layout of your data in memory impacts performance.

Data Structures & Algorithms

Understand how our code interacts with physical hardware. Learn about virtual memory, the stack vs. heap, cache lines, and prefetching.

CPUs, Memory, and Locality

Learn how input size affects execution speed and the most common class of algorithms.

Polynomial Algorithms

Working with massive datasets using divide and conquer strategies, and the the required trade-offs.

Logarithmic and Linearithmic Algorithms

Learn why some problems are impossible to solve exactly and how we can use approximations like Monte Carlo simulations to cheat.

NP-Hard and Approximations

Whirlwind Tour of C++ Basics

This course introduces algorithm analysis with a practical focus on how CPUs execute code and fetch data. Topics include growth rates, locality, and why memory layout matters.

If you're completely new to programming or want a thorough introduction, we recommend starting with our introductory course:

New to Programming?

Practical Algorithm Analysis

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`.


<Interactive id="dsa-contiguous-linked-add-item">


Accessibility Note: An interactive component visualizing a block of memory. It displays several objects.

- When the "Contiguous" button is clicked, the objects are arranged tightly together in a single block, one after another.
- When the "Linked" button is clicked, the objects are scattered randomly across the memory space. Arrows are drawn from one object to the next, visualizing the pointers that connect them.

</Interactive>


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


<Interactive id="dsa-tree-graph">


Accessibility Note: An interactive component visualizing a collection of objects stored in memory.  Buttons allow the nodes to be linked in two different ways - as a tree, or as a more complex graph


</Interactive>


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.


<Interactive id="dsa-complex-data-structures">


Accessibility Note: An interactive component visualizing a collection of objects stored in memory.  Buttons allow the nodes to be arranged in two different ways - as an unrolled list, or as a chunked array.


</Interactive>


## The Movement of Information


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**.


## Zero-Cost Abstractions


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:


<CodeFile path="player.c">


```c++
#include <stdio.h>

// The "Shape" of our data
typedef struct {
  int id;
  int health;
} Player;

// The "Movement" of our data
void take_damage_c(Player* p, int amount) {
  p->health -= amount;
}

int main() {
  Player p{1, 100};
  take_damage_c(&p, 10);
  printf("Player Health: %d\n", p.health);
  return 0;
}
```


</CodeFile>


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.


<CodeFile path="player.cpp">


```c++
#include <stdio.h>

// The "Shape" and "Movement" combined
class Player {
public:
  int id;
  int health;

  void take_damage(int amount) {
    health -= amount;
  }
};

int main() {
  Player p{1, 100};
  p.take_damage(10);
  printf("Player Health: %d\n", p.health);
  return 0;
}
```


</CodeFile>


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](https://godbolt.org/) 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`.


## Summary


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.

The Hardware Reality & Memory Model

Algorithm Analysis and Big O Notation

Dynamic Arrays using `std::vector`

Linked Lists using `std::forward_list`

Chandler Carruth "There Are No Zero-cost Abstractions"

Foundations of C++ (Section on Abstraction)

Data-oriented design

C++ Core Guidelines: Performance

Effective Modern C++

Compiler Explorer

Start your journey into high-performance C++ with our introduction to data structures and algorithms. We discard abstract theory for hardware reality, focusing on how memory layout dictates the efficiency of your code.

Data Structures & Algorithms

Understanding the Basics

Practical Applications

Common Mistakes

Next Steps

Additional Resources

Assessment Preparation

Practical Algorithm Analysis