Free Handbook · Every example compiled & verified

Data Structures & Algorithms

Build arrays, linked lists, stacks, hash maps, trees, heaps and graphs by hand in C++, then use the STL version, plus search, sort and DP.

0 / 145 lessons🔥 0 day streak

ShareX LinkedIn

Module 13 · what you'll be able to do

Pick an STL container from its cost table instead of defaulting to whatever you used last
Build a growable array, a linked list, a hash map, a binary search tree and a heap by hand with raw and smart pointers
Use std::vector, std::unordered_map, std::stack, std::queue, std::deque, std::list, std::priority_queue, std::set and std::map correctly
Represent a graph as an adjacency list and trace BFS and DFS by hand
Write binary search, merge sort and a bottom-up dynamic-programming table, then reach for std::lower_bound and std::sort

The cost table: what each container really costs

Every data structure is a trade-off between how fast you can find, add and remove things, and how much memory and cache-friendliness you give up to get there. C++ makes those costs visible: the standard guarantees the complexity of every container operation, so choosing a container is choosing a row of the table below.

Big-O hides constants. A vector often beats a list even for middle insertions on small n, because walking contiguous memory is far faster than chasing pointers.
Container	Index	Find	Insert	Remove	Notes
`std::vector`	O(1)	O(n)	O(1) amortised at end, O(n) elsewhere	O(1) at end, O(n) elsewhere	Contiguous memory. The default choice.
`std::deque`	O(1)	O(n)	O(1) at both ends	O(1) at both ends	Chunked blocks; backs `std::queue`.
`std::list` / `forward_list`	—	O(n)	O(1) at a known iterator	O(1) at a known iterator	One heap node per element; slow to walk.
`std::unordered_map` / `set`	—	O(1) average, O(n) worst	O(1) average	O(1) average	Hash table. No order.
`std::map` / `set`	—	O(log n)	O(log n)	O(log n)	Balanced tree (red-black). Sorted order, `lower_bound`.
`std::priority_queue`	top only, O(1)	—	O(log n)	O(log n) top only	Binary heap inside a vector.
`std::stack` / `std::queue`	top/front only	—	O(1)	O(1)	Adapters over deque (or vector/list).

C++main.cpp

#include <iostream>
#include <vector>

int main() {
    std::vector<int> v{10, 20, 30};
    v.push_back(40);              // amortised O(1): add at the end
    std::cout << v[2] << '\n';    // O(1): jump straight to index 2
    v.insert(v.begin(), 5);       // O(n): every element shifts right
    v.pop_back();                 // O(1): remove from the end
    for (int x : v) std::cout << x << ' ';
    std::cout << "\nsize " << v.size() << '\n';
}

Outputcompiled & run with real C++

30
5 10 20 30 
size 4

The same container, three different costs depending on where you touch it.

Your turn

Replace v.insert(v.begin(), 5) with a std::deque and push_front(5). Which operation got cheaper, and which one did you give up nothing for?

How this module is organised

Each lesson builds the structure by hand first, with raw pointers or std::unique_ptr, so you see what the library is doing for you. Then it shows the STL version you should actually use at work. Interviews ask for the first; code reviews expect the second.

A growable array by hand, then std::vector

A std::vector is three things: a pointer to a heap block, how many elements are in use (size) and how many fit before it must grow (capacity). When it is full, it allocates a bigger block, moves the elements across, and frees the old one. Doubling the capacity each time means the total copying stays proportional to n, which is why push_back is amortised O(1).

C++main.cpp

#include <cstddef>
#include <iostream>

class IntVec {
    int* data_ = nullptr;
    std::size_t size_ = 0, cap_ = 0;
public:
    IntVec() = default;
    ~IntVec() { delete[] data_; }
    IntVec(const IntVec&) = delete;             // keep the example small:
    IntVec& operator=(const IntVec&) = delete;  // no copies allowed

    void push_back(int x) {
        if (size_ == cap_) {                    // full: grow to double
            std::size_t newCap = cap_ == 0 ? 1 : cap_ * 2;
            int* bigger = new int[newCap];
            for (std::size_t i = 0; i < size_; ++i) bigger[i] = data_[i];
            delete[] data_;
            data_ = bigger;
            cap_ = newCap;
            std::cout << "grew to " << cap_ << '\n';
        }
        data_[size_++] = x;
    }
    int operator[](std::size_t i) const { return data_[i]; }
    std::size_t size() const { return size_; }
};

int main() {
    IntVec v;
    for (int i = 1; i <= 5; ++i) v.push_back(i * 10);
    std::cout << "size " << v.size() << ", v[4] = " << v[4] << '\n';
}

Outputcompiled & run with real C++

grew to 1
grew to 2
grew to 4
grew to 8
size 5, v[4] = 50

new[] / delete[] by hand. Copying is deleted so two IntVecs can never free the same block (the rule of three from Module 07).

Your turn

Add a pop_back() and a bounds-checked at(i) that throws std::out_of_range. Then write the copy constructor properly so copying is allowed again.

The real thing does all of that, plus copy and move, exception safety and reserve to allocate once when you know the size in advance.

C++main.cpp

#include <iostream>
#include <vector>

int main() {
    std::vector<int> v;
    v.reserve(5);                       // one allocation up front
    for (int i = 1; i <= 5; ++i) v.push_back(i * 10);
    std::cout << "size " << v.size() << ", v[4] = " << v[4] << '\n';
    std::cout << "at(1) = " << v.at(1) << '\n';   // bounds-checked access
    v.erase(v.begin() + 1);             // O(n): closes the gap
    for (int x : v) std::cout << x << ' ';
    std::cout << '\n';
}

Outputcompiled & run with real C++

size 5, v[4] = 50
at(1) = 20
10 30 40 50

Your turn

Call v.at(10) inside a try block and print the exception's what(). Then try v[10] and notice it does not throw: it is undefined behaviour.

Growth invalidates pointers

When a vector reallocates, every pointer, reference and iterator into it now points at freed memory. Holding int& first = v[0] across a push_back is a classic use-after-free. Either reserve first or re-read the element after growing.

A linked list by hand, then std::list

A linked list stores each element in its own heap node that points to the next one. In modern C++ the cleanest ownership model is: each node owns the next node through a std::unique_ptr. Destroying the head destroys the whole chain, with no delete anywhere. Code that only looks at nodes uses plain raw pointers from .get().

C++main.cpp

#include <iostream>
#include <memory>

struct Node {
    int value;
    std::unique_ptr<Node> next;   // this node OWNS the rest of the list
};

class List {
    std::unique_ptr<Node> head_;
public:
    void push_front(int v) {
        head_ = std::make_unique<Node>(Node{v, std::move(head_)});
    }
    void reverse() {
        std::unique_ptr<Node> prev;
        while (head_) {
            std::unique_ptr<Node> next = std::move(head_->next);
            head_->next = std::move(prev);
            prev = std::move(head_);
            head_ = std::move(next);
        }
        head_ = std::move(prev);
    }
    void print() const {
        for (const Node* n = head_.get(); n; n = n->next.get())  // raw pointer = just looking
            std::cout << n->value << (n->next ? " -> " : "\n");
    }
};

int main() {
    List list;
    for (int v : {3, 2, 1}) list.push_front(v);
    list.print();
    list.reverse();
    list.print();
}

Outputcompiled & run with real C++

1 -> 2 -> 3
3 -> 2 -> 1

Reversal moves ownership one link at a time. Every std::move hands a node from one unique_ptr to another.

Your turn

Add push_back in O(1) by keeping a raw Node* tail_ alongside head_. Why is tail_ a raw pointer and not a second unique_ptr?

Interviewers usually ask for the raw-pointer version. Here is the same reversal with Node*, traced on the list 1 -> 2 -> 3:

VisualizeReversing 1 -> 2 -> 3 with three pointersStep 1 / 9

1Node* reverse(Node* head) {
2    Node* prev = nullptr;
3    while (head) {
4        Node* next = head->next;
5        head->next = prev;
6        prev = head;
7        head = next;
8    }
9    return prev;
10}

Line 2

prev starts empty; head points at node 1.

Variables now

`head`	`1`
`prev`	`nullptr`

All 9 steps as a table

Step	Line	What happened	Variables now
1	2	prev starts empty; head points at node 1.	`head = 1` `prev = nullptr`
2	4	Save the rest of the list before cutting the link.	`next = 2`
3	5	Node 1 now points backwards, to nothing.
4	7	Advance: prev is node 1, head is node 2.	`prev = 1` `head = 2`
5	5	Node 2 now points back to node 1.	`next = 3`
6	7	Advance again.	`prev = 2` `head = 3`
7	5	Node 3 now points back to node 2.	`next = nullptr`
8	7	head becomes nullptr, so the loop ends.	`prev = 3` `head = nullptr`
9	9	prev is the new head: 3 -> 2 -> 1.

The STL gives you std::list (doubly linked: walk both ways, O(1) insert/erase at any iterator) and std::forward_list (singly linked, one pointer per node).

C++main.cpp

#include <forward_list>
#include <iostream>
#include <list>

int main() {
    std::list<int> dl{1, 2, 3};          // doubly linked
    auto it = std::next(dl.begin());     // points at 2
    dl.insert(it, 99);                   // O(1) at a known position
    dl.push_front(0);
    for (int x : dl) std::cout << x << ' ';
    std::cout << '\n';

    std::forward_list<int> sl{1, 2, 3};  // singly linked, smaller nodes
    sl.reverse();
    for (int x : sl) std::cout << x << ' ';
    std::cout << '\n';
}

Outputcompiled & run with real C++

0 1 99 2 3 
3 2 1

In real jobs

Linked lists are rare in production C++. Each node is a separate allocation scattered across memory, so walking one misses the CPU cache constantly. Reach for std::list only when you truly need iterators that stay valid while you insert and erase around them (an LRU cache is the classic case). Otherwise, use std::vector.

Stacks: last in, first out

A stack only lets you touch the top: push, pop, peek. A std::vector already does that at its back end, so a hand-built stack is a thin template around one.

C++main.cpp

#include <iostream>
#include <stdexcept>
#include <string>
#include <vector>

template <typename T>
class Stack {
    std::vector<T> items_;
public:
    void push(T v) { items_.push_back(std::move(v)); }
    T pop() {
        if (items_.empty()) throw std::out_of_range("pop from empty stack");
        T top = std::move(items_.back());
        items_.pop_back();
        return top;
    }
    bool empty() const { return items_.empty(); }
};

int main() {
    Stack<std::string> s;
    s.push("a"); s.push("b"); s.push("c");
    while (!s.empty()) std::cout << s.pop() << ' ';
    std::cout << '\n';
    try { s.pop(); } catch (const std::out_of_range& e) { std::cout << e.what() << '\n'; }
}

Outputcompiled & run with real C++

c b a 
pop from empty stack

Your turn

Add a const T& top() const that throws on an empty stack, and a size().

std::stack is an adapter: it wraps a deque (by default) and exposes only the stack operations. Note the split API: top() reads, pop() removes and returns void. That design exists so a throwing copy can never lose the element you were removing.

C++main.cpp

#include <iostream>
#include <stack>
#include <string>

bool balanced(const std::string& s) {
    std::stack<char> open;
    for (char c : s) {
        if (c == '(' || c == '[' || c == '{') { open.push(c); continue; }
        if (c != ')' && c != ']' && c != '}') continue;
        if (open.empty()) return false;
        char want = c == ')' ? '(' : c == ']' ? '[' : '{';
        if (open.top() != want) return false;
        open.pop();                       // pop() returns void: read top() first
    }
    return open.empty();
}

int main() {
    for (std::string s : {"(a[b]{c})", "(]", "((", "v[i] = f(x);"})
        std::cout << s << " -> " << (balanced(s) ? "ok" : "bad") << '\n';
}

Outputcompiled & run with real C++

(a[b]{c}) -> ok
(] -> bad
(( -> bad
v[i] = f(x); -> ok

The canonical stack problem: every closer must match the most recent unmatched opener.

Your turn

Return the index of the first unmatched character instead of a bool, or -1 if balanced.

Queues, deques and a ring buffer

A queue is first in, first out: add at the back, remove from the front. Removing from the front of a vector is O(n) because everything shifts, so std::queue sits on a std::deque, which is O(1) at both ends.

C++main.cpp

#include <deque>
#include <iostream>
#include <queue>

int main() {
    std::queue<std::string> jobs;          // FIFO, built on std::deque
    jobs.push("build"); jobs.push("test"); jobs.push("deploy");
    while (!jobs.empty()) {
        std::cout << jobs.front() << ' ';
        jobs.pop();
    }
    std::cout << '\n';

    std::deque<int> d{2, 3};
    d.push_front(1);                       // O(1) at both ends
    d.push_back(4);
    std::cout << d.front() << ' ' << d.back() << ' ' << d[2] << '\n';
    d.pop_front();
    d.pop_back();
    for (int x : d) std::cout << x << ' ';
    std::cout << '\n';
}

Outputcompiled & run with real C++

build test deploy 
1 4 3
2 3

When the maximum size is known, a ring buffer is the fastest queue there is: a fixed array plus a head index and a count, wrapping with %. It never allocates, which is why audio pipelines, network drivers and embedded firmware use it.

C++main.cpp

#include <array>
#include <iostream>

class RingQueue {                  // fixed capacity, no allocation at all
    std::array<int, 4> buf_{};
    std::size_t head_ = 0, count_ = 0;
public:
    bool push(int v) {
        if (count_ == buf_.size()) return false;           // full
        buf_[(head_ + count_) % buf_.size()] = v;
        ++count_;
        return true;
    }
    bool pop(int& out) {
        if (count_ == 0) return false;                     // empty
        out = buf_[head_];
        head_ = (head_ + 1) % buf_.size();
        --count_;
        return true;
    }
};

int main() {
    RingQueue q;
    for (int i = 1; i <= 5; ++i) std::cout << "push " << i << (q.push(i) ? " ok\n" : " full\n");
    int v;
    q.pop(v); q.pop(v);
    q.push(6); q.push(7);                                  // wraps around
    while (q.pop(v)) std::cout << v << ' ';
    std::cout << '\n';
}

Outputcompiled & run with real C++

push 1 ok
push 2 ok
push 3 ok
push 4 ok
push 5 full
3 4 6 7

After two pops, pushes 6 and 7 wrap into the slots that 1 and 2 used.

Your turn

Make the capacity a template parameter: template <std::size_t N> class RingQueue.

Hash maps and sets

A hash table turns a key into a bucket number with a hash function, so looking up a key means checking one short bucket instead of the whole collection. That is O(1) on average. The worst case (every key in one bucket) is O(n), which is why a good hash function matters.

C++main.cpp

#include <functional>
#include <iostream>
#include <list>
#include <string>
#include <utility>
#include <vector>

class StringIntMap {                       // separate chaining
    std::vector<std::list<std::pair<std::string, int>>> buckets_;
    std::size_t bucketFor(const std::string& k) const {
        return std::hash<std::string>{}(k) % buckets_.size();
    }
public:
    explicit StringIntMap(std::size_t n) : buckets_(n) {}
    void put(const std::string& k, int v) {
        for (auto& [key, val] : buckets_[bucketFor(k)])
            if (key == k) { val = v; return; }    // update in place
        buckets_[bucketFor(k)].emplace_back(k, v);
    }
    const int* get(const std::string& k) const {
        for (const auto& [key, val] : buckets_[bucketFor(k)])
            if (key == k) return &val;
        return nullptr;                           // not found
    }
};

int main() {
    StringIntMap ages(8);
    ages.put("ada", 36);
    ages.put("bob", 25);
    ages.put("ada", 37);
    const int* a = ages.get("ada");
    std::cout << "ada " << (a ? *a : -1) << '\n';
    std::cout << "cy " << (ages.get("cy") ? "found" : "missing") << '\n';
}

Outputcompiled & run with real C++

ada 37
cy missing

Separate chaining: each bucket is a small list of key/value pairs.

Your turn

Track the element count and, when it passes 0.75 x the bucket count, rehash everything into twice as many buckets. That is exactly what std::unordered_map does behind max_load_factor.

std::unordered_map is the production version. Two traps: operator[] inserts a default value when the key is missing (use find or contains to only look), and iteration order is unspecified, so sort before printing anything a test or a user depends on.

C++main.cpp

#include <algorithm>
#include <iostream>
#include <sstream>
#include <string>
#include <unordered_map>
#include <vector>

int main() {
    std::string text = "the cat and the dog and the bird";
    std::unordered_map<std::string, int> count;
    std::istringstream in(text);
    for (std::string w; in >> w;) ++count[w];     // operator[] inserts 0 first

    // Iteration order of an unordered_map is unspecified: sort before printing.
    std::vector<std::pair<std::string, int>> rows(count.begin(), count.end());
    std::sort(rows.begin(), rows.end(), [](const auto& a, const auto& b) {
        return a.second != b.second ? a.second > b.second : a.first < b.first;
    });
    for (const auto& [w, n] : rows) std::cout << w << ' ' << n << '\n';

    std::cout << "has cat: " << count.contains("cat") << '\n';   // C++20
    std::cout << "has cow: " << count.contains("cow") << '\n';
}

Outputcompiled & run with real C++

the 3
and 2
bird 1
cat 1
dog 1
has cat: 1
has cow: 0

C++main.cpp

#include <iostream>
#include <unordered_set>
#include <vector>

int main() {
    std::vector<int> nums{4, 1, 4, 9, 1, 7};
    std::unordered_set<int> seen;
    for (int n : nums) {
        auto [it, inserted] = seen.insert(n);   // insert tells you if it was new
        if (!inserted) std::cout << "duplicate " << n << '\n';
    }
    std::cout << "distinct " << seen.size() << '\n';
}

Outputcompiled & run with real C++

duplicate 4
duplicate 1
distinct 4

Your turn

Rewrite it with a std::set<int>. The output is the same; what changes about cost and iteration order?

Custom keys

To use your own struct as an unordered_map key it needs operator== and a hash: specialise std::hash<YourType> or pass a hasher type as the third template argument. For std::map it needs operator< (or operator<=> in C++20) instead.

Binary search trees, then std::set and std::map

A binary search tree keeps every key in the left subtree smaller than its node and every key in the right subtree larger. Search, insert and delete each walk one path from the root, so they cost O(height): O(log n) if the tree is balanced, O(n) if you insert sorted data and it degenerates into a line.

C++main.cpp

#include <iostream>
#include <memory>

struct Node {
    int key;
    std::unique_ptr<Node> left, right;
};

void insert(std::unique_ptr<Node>& root, int key) {
    if (!root) { root = std::make_unique<Node>(Node{key, nullptr, nullptr}); return; }
    if (key < root->key) insert(root->left, key);
    else if (key > root->key) insert(root->right, key);   // ignore duplicates
}

bool contains(const Node* n, int key) {
    while (n) {
        if (key == n->key) return true;
        n = key < n->key ? n->left.get() : n->right.get();
    }
    return false;
}

void inorder(const Node* n) {            // left, self, right = sorted order
    if (!n) return;
    inorder(n->left.get());
    std::cout << n->key << ' ';
    inorder(n->right.get());
}

int main() {
    std::unique_ptr<Node> root;
    for (int k : {50, 30, 70, 20, 40, 60, 80}) insert(root, k);
    inorder(root.get());
    std::cout << '\n' << contains(root.get(), 60) << ' ' << contains(root.get(), 65) << '\n';
}

Outputcompiled & run with real C++

20 30 40 50 60 70 80 
1 0

Each node owns its children through unique_ptr, so the whole tree frees itself when root goes out of scope.

Your turn

Write int height(const Node*). Then insert 1..7 in order and print the height: that is the degenerate case.

std::set and std::map are self-balancing trees (red-black in every major implementation), so they stay O(log n) whatever order you insert in. Their superpower over hash tables is order: sorted iteration and range queries with lower_bound / upper_bound.

C++main.cpp

#include <iostream>
#include <map>
#include <set>
#include <string>

int main() {
    std::set<int> s{50, 30, 70, 20, 40};          // a balanced tree, kept sorted
    for (int x : s) std::cout << x << ' ';
    std::cout << '\n';
    std::cout << "first >= 45: " << *s.lower_bound(45) << '\n';
    std::cout << "first > 50:  " << *s.upper_bound(50) << '\n';

    std::map<std::string, int> stock{{"pear", 3}, {"apple", 5}};
    stock["fig"] = 1;
    stock.erase("pear");
    for (const auto& [name, qty] : stock) std::cout << name << '=' << qty << ' ';
    std::cout << '\n';
}

Outputcompiled & run with real C++

20 30 40 50 70 
first >= 45: 50
first > 50:  70
apple=5 fig=1

Heaps and std::priority_queue

A binary heap is a complete tree stored flat in an array: the children of index i are at 2i+1 and 2i+2. In a min-heap every parent is no larger than its children, so the minimum is always at index 0. Push adds at the end and sifts up; pop moves the last element to the root and sifts down. Both walk one path: O(log n).

C++main.cpp

#include <iostream>
#include <utility>
#include <vector>

class MinHeap {
    std::vector<int> a_;      // children of i live at 2i+1 and 2i+2
public:
    void push(int v) {
        a_.push_back(v);
        std::size_t i = a_.size() - 1;
        while (i > 0 && a_[(i - 1) / 2] > a_[i]) {         // sift up
            std::swap(a_[(i - 1) / 2], a_[i]);
            i = (i - 1) / 2;
        }
    }
    int pop() {
        int top = a_[0];
        a_[0] = a_.back();
        a_.pop_back();
        std::size_t i = 0;
        while (true) {                                      // sift down
            std::size_t l = 2 * i + 1, r = l + 1, m = i;
            if (l < a_.size() && a_[l] < a_[m]) m = l;
            if (r < a_.size() && a_[r] < a_[m]) m = r;
            if (m == i) break;
            std::swap(a_[i], a_[m]);
            i = m;
        }
        return top;
    }
    bool empty() const { return a_.empty(); }
};

int main() {
    MinHeap h;
    for (int v : {5, 3, 8, 1, 9, 2}) h.push(v);
    while (!h.empty()) std::cout << h.pop() << ' ';
    std::cout << '\n';
}

Outputcompiled & run with real C++

1 2 3 5 8 9

Your turn

Add a top() and make pop() safe on an empty heap. Then heapify an existing vector in O(n) by sifting down from index n/2 - 1 to 0.

std::priority_queue is a max-heap by default. For a min-heap pass std::greater<int> as the comparator. Pairs compare by their first member first, which makes (priority, payload) an easy task queue.

C++main.cpp

#include <functional>
#include <iostream>
#include <queue>
#include <string>
#include <vector>

int main() {
    std::priority_queue<int> maxq;                                    // max-heap by default
    std::priority_queue<int, std::vector<int>, std::greater<int>> minq;  // min-heap
    for (int v : {5, 3, 8, 1}) { maxq.push(v); minq.push(v); }
    std::cout << "max " << maxq.top() << ", min " << minq.top() << '\n';

    using Task = std::pair<int, std::string>;                         // (priority, name)
    std::priority_queue<Task> tasks;
    tasks.push({2, "email"});
    tasks.push({9, "outage"});
    tasks.push({5, "review"});
    while (!tasks.empty()) {
        std::cout << tasks.top().second << ' ';
        tasks.pop();
    }
    std::cout << '\n';
}

Outputcompiled & run with real C++

max 8, min 1
outage review email

Your turn

Keep only the 3 largest numbers from a stream using a min-heap of size 3: push each value, and pop whenever the size exceeds 3. That is the top-k pattern.

Recursion and the call stack

A recursive function solves a problem by calling itself on a smaller version of it. It needs a base case that stops the recursion and a recursive case that moves towards it. Each call gets its own stack frame; the default stack on most systems is 1-8 MB, so very deep recursion (hundreds of thousands of frames) crashes with a stack overflow where a loop would not.

C++main.cpp

#include <iostream>

long long factorial(int n) {
    if (n <= 1) return 1;              // base case stops the recursion
    return n * factorial(n - 1);       // each call waits for a smaller one
}

int sumDigits(int n) {
    return n < 10 ? n : n % 10 + sumDigits(n / 10);
}

int main() {
    std::cout << factorial(5) << '\n';
    std::cout << factorial(20) << '\n';
    std::cout << sumDigits(90417) << '\n';
}

Outputcompiled & run with real C++

120
2432902008176640000
21

Visualizefactorial(3) winding down and back upStep 1 / 7

1long long factorial(int n) {
2    if (n <= 1) return 1;
3    return n * factorial(n - 1);
4}
5int main() {
6    long long r = factorial(3);
7}

Line 6

main calls factorial(3).

Variables now

n 3

All 7 steps as a table

Step	Line	What happened	Variables now
1	6	main calls factorial(3).	`n = 3`
2	3	n is not <= 1, so factorial(3) waits on factorial(2).	`n = 3`
3	3	factorial(2) waits on factorial(1). Three frames are now on the stack.	`n = 2`
4	2	Base case: factorial(1) returns 1.	`n = 1`
5	3	factorial(2) resumes and returns 2 * 1 = 2.	`n = 2`
6	3	factorial(3) resumes and returns 3 * 2 = 6.	`n = 3`
7	6	Back in main with the answer.	`r = 6`

Overflow is silent

factorial(21) overflows a 64-bit long long. Signed overflow is undefined behaviour in C++, not a wrap-around you can detect afterwards. Check the range before you multiply, or use a wider or arbitrary-precision type.

Graphs: adjacency lists, BFS and DFS

A graph is nodes plus edges. The usual C++ representation is an adjacency list: std::vector<std::vector<int>> where g[u] lists the neighbours of node u. It costs O(V + E) memory, unlike an adjacency matrix's O(V²).

BFS (breadth-first search) explores in rings using a queue, so the first time it reaches a node is along a shortest path in an unweighted graph. DFS (depth-first search) goes as deep as possible first, using recursion or an explicit stack; it is the tool for connectivity, cycle detection and topological order. Both visit each node and edge once: O(V + E).

C++main.cpp

#include <iostream>
#include <queue>
#include <vector>

using Graph = std::vector<std::vector<int>>;   // adjacency list

std::vector<int> bfsDistances(const Graph& g, int start) {
    std::vector<int> dist(g.size(), -1);
    std::queue<int> q;
    dist[start] = 0;
    q.push(start);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : g[u])
            if (dist[v] == -1) { dist[v] = dist[u] + 1; q.push(v); }
    }
    return dist;
}

void dfs(const Graph& g, int u, std::vector<bool>& seen) {
    seen[u] = true;
    std::cout << u << ' ';
    for (int v : g[u]) if (!seen[v]) dfs(g, v, seen);
}

int main() {
    Graph g(6);
    auto edge = [&](int a, int b) { g[a].push_back(b); g[b].push_back(a); };
    edge(0, 1); edge(0, 2); edge(1, 3); edge(2, 3); edge(3, 4);   // node 5 is isolated
    std::vector<int> d = bfsDistances(g, 0);
    for (int i = 0; i < 6; ++i) std::cout << i << ':' << d[i] << ' ';
    std::cout << "\nDFS from 0: ";
    std::vector<bool> seen(6, false);
    dfs(g, 0, seen);
    std::cout << '\n';
}

Outputcompiled & run with real C++

0:0 1:1 2:1 3:2 4:3 5:-1 
DFS from 0: 0 1 3 2 4

Node 5 has no edges, so BFS never reaches it and its distance stays -1.

Your turn

Store each node's parent during BFS and print the actual shortest path from 0 to 4, not just its length.

VisualizeBFS from node 0 (edges 0-1, 0-2, 1-3, 2-3, 3-4)Step 1 / 9

1dist[0] = 0; q.push(0);
2while (!q.empty()) {
3    int u = q.front(); q.pop();
4    for (int v : g[u])
5        if (dist[v] == -1) { dist[v] = dist[u] + 1; q.push(v); }
6}

Line 1

Start at 0 with distance 0.

Variables now

`q`	`[0]`
`dist`	`0:0`

All 9 steps as a table

Step	Line	What happened	Variables now
1	1	Start at 0 with distance 0.	`q = [0]` `dist = 0:0`
2	3	Take 0 off the front.	`u = 0` `q = []`
3	5	Neighbours 1 and 2 are new: distance 1, queued.	`q = [1, 2]` `dist = 0:0 1:1 2:1`
4	3	Take 1.	`u = 1` `q = [2]`
5	5	0 is already seen; 3 is new at distance 2.	`q = [2, 3]` `dist = 0:0 1:1 2:1 3:2`
6	3	Take 2. Both neighbours (0 and 3) are already seen.	`u = 2` `q = [3]`
7	5	Take 3: neighbour 4 is new at distance 3.	`u = 3` `q = [4]` `dist = 0:0 1:1 2:1 3:2 4:3`
8	3	Take 4. Its only neighbour, 3, is seen.	`u = 4` `q = []`
9	2	Queue empty: every reachable node has its shortest distance.

Weighted edges

When edges have different costs, BFS no longer finds shortest paths. Use Dijkstra's algorithm: the same loop with a std::priority_queue of (distance, node) in place of the plain queue.

Binary search, then std::lower_bound

On sorted data, binary search checks the middle element and throws away the half that cannot contain the target. Each step halves the range, so a million elements need about 20 comparisons: O(log n).

C++main.cpp

#include <iostream>
#include <vector>

int binarySearch(const std::vector<int>& a, int target) {
    int lo = 0, hi = static_cast<int>(a.size()) - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;      // not (lo + hi) / 2: that can overflow
        if (a[mid] == target) return mid;
        if (a[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

int main() {
    std::vector<int> a{2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
    std::cout << binarySearch(a, 23) << ' ' << binarySearch(a, 7) << '\n';
}

Outputcompiled & run with real C++

5 -1

VisualizeSearching for 23Step 1 / 7

1int lo = 0, hi = 9;                // a = {2,5,8,12,16,23,38,56,72,91}
2while (lo <= hi) {
3    int mid = lo + (hi - lo) / 2;
4    if (a[mid] == target) return mid;
5    if (a[mid] < target) lo = mid + 1;
6    else hi = mid - 1;
7}

Line 1

The whole array is in range.

Variables now

`lo`	`0`
`hi`	`9`

All 7 steps as a table

Step	Line	What happened	Variables now
1	1	The whole array is in range.	`lo = 0` `hi = 9`
2	3	mid = 4, a[4] = 16.	`mid = 4`
3	5	16 < 23, so the answer is to the right.	`lo = 5`
4	3	mid = 5 + (9 - 5) / 2 = 7, a[7] = 56.	`mid = 7`
5	6	56 > 23, so discard the right half.	`hi = 6`
6	3	mid = 5 + (6 - 5) / 2 = 5, a[5] = 23.	`mid = 5`
7	4	Found it at index 5 after three comparisons.

In real code use the <algorithm> versions. std::lower_bound returns the first position whose value is not less than the target, which answers "is it here?", "where does it start?" and "where would it go?" in one call.

C++main.cpp

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> a{2, 5, 8, 8, 8, 16, 23};
    std::cout << std::boolalpha << std::binary_search(a.begin(), a.end(), 16) << '\n';
    auto lo = std::lower_bound(a.begin(), a.end(), 8);   // first element >= 8
    auto hi = std::upper_bound(a.begin(), a.end(), 8);   // first element >  8
    std::cout << "8 appears " << (hi - lo) << " times, from index " << (lo - a.begin()) << '\n';
    auto ins = std::lower_bound(a.begin(), a.end(), 10);
    std::cout << "10 would go at index " << (ins - a.begin()) << '\n';
}

Outputcompiled & run with real C++

true
8 appears 3 times, from index 2
10 would go at index 5

Your turn

Use std::equal_range to get both bounds in one call.

Sorting: by hand, then std::sort

Insertion sort is O(n²) but very fast on tiny or nearly-sorted inputs. Merge sort splits the range in half, sorts each half and merges them: O(n log n) always, and stable (equal elements keep their order), at the cost of O(n) extra memory.

C++main.cpp

#include <iostream>
#include <vector>

void insertionSort(std::vector<int>& a) {            // O(n^2), great for tiny inputs
    for (std::size_t i = 1; i < a.size(); ++i) {
        int key = a[i];
        std::size_t j = i;
        while (j > 0 && a[j - 1] > key) { a[j] = a[j - 1]; --j; }
        a[j] = key;
    }
}

void mergeSort(std::vector<int>& a, std::size_t lo, std::size_t hi) {  // [lo, hi)
    if (hi - lo < 2) return;
    std::size_t mid = lo + (hi - lo) / 2;
    mergeSort(a, lo, mid);
    mergeSort(a, mid, hi);
    std::vector<int> merged;
    std::size_t i = lo, j = mid;
    while (i < mid && j < hi) merged.push_back(a[i] <= a[j] ? a[i++] : a[j++]);
    while (i < mid) merged.push_back(a[i++]);
    while (j < hi) merged.push_back(a[j++]);
    for (std::size_t k = 0; k < merged.size(); ++k) a[lo + k] = merged[k];
}

int main() {
    std::vector<int> a{5, 2, 9, 1, 5, 6}, b = a;
    insertionSort(a);
    mergeSort(b, 0, b.size());
    for (int x : a) std::cout << x << ' ';
    std::cout << '\n';
    for (int x : b) std::cout << x << ' ';
    std::cout << '\n';
}

Outputcompiled & run with real C++

1 2 5 5 6 9 
1 2 5 5 6 9

Your turn

Count the comparisons each algorithm makes on a 1,000-element reversed vector. The gap is the difference between n² and n log n.

std::sort is an introsort (quicksort that falls back to heapsort, plus insertion sort for small ranges): O(n log n) worst case, not stable. std::stable_sort is the stable one. Both take a comparator that must be a strict weak ordering: use <, never <=, or the behaviour is undefined.

C++main.cpp

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

struct Person { std::string name; int age; };

int main() {
    std::vector<Person> people{{"cy", 30}, {"ada", 25}, {"bob", 30}, {"dee", 25}};

    std::sort(people.begin(), people.end(),
              [](const Person& a, const Person& b) { return a.name < b.name; });
    // stable_sort keeps equal ages in their current (alphabetical) order
    std::stable_sort(people.begin(), people.end(),
                     [](const Person& a, const Person& b) { return a.age < b.age; });
    for (const auto& p : people) std::cout << p.name << '(' << p.age << ") ";
    std::cout << '\n';

    std::vector<int> v{5, 2, 9, 1};
    std::ranges::sort(v, std::greater{});             // C++20 ranges, descending
    for (int x : v) std::cout << x << ' ';
    std::cout << '\n';
}

Outputcompiled & run with real C++

ada(25) dee(25) bob(30) cy(30) 
9 5 2 1

Sort by name, then stable-sort by age: ties in age stay alphabetical. That is how you sort by several keys.

Algorithm	Time	Extra memory	Stable
Insertion sort	O(n²), O(n) if nearly sorted	O(1)	Yes
Merge sort	O(n log n)	O(n)	Yes
Quicksort	O(n log n) average, O(n²) worst	O(log n)	No
Heapsort	O(n log n)	O(1)	No
`std::sort`	O(n log n)	O(log n)	No
`std::stable_sort`	O(n log n)	O(n) if available	Yes

Dynamic programming

Dynamic programming applies when a problem breaks into overlapping subproblems: the same smaller question gets asked again and again. Store each answer once, either top-down (recursion plus a memo cache) or bottom-up (fill a table from the smallest case).

C++main.cpp

#include <iostream>
#include <unordered_map>

long long calls = 0;

long long fibSlow(int n) { ++calls; return n < 2 ? n : fibSlow(n - 1) + fibSlow(n - 2); }

long long fibMemo(int n, std::unordered_map<int, long long>& memo) {
    ++calls;
    if (n < 2) return n;
    if (auto it = memo.find(n); it != memo.end()) return it->second;
    return memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
}

long long fibTable(int n) {                  // bottom-up, O(1) memory
    long long a = 0, b = 1;
    for (int i = 0; i < n; ++i) { long long t = a + b; a = b; b = t; }
    return a;
}

int main() {
    std::cout << fibSlow(30) << " in " << calls << " calls\n";
    calls = 0;
    std::unordered_map<int, long long> memo;
    std::cout << fibMemo(30, memo) << " in " << calls << " calls\n";
    std::cout << fibTable(90) << '\n';
}

Outputcompiled & run with real C++

832040 in 2692537 calls
832040 in 59 calls
2880067194370816120

Same answer, 2.7 million calls versus 59.

Coin change is the classic bottom-up table: best[a] is the fewest coins that make amount a, built from every smaller amount.

C++main.cpp

#include <algorithm>
#include <climits>
#include <iostream>
#include <vector>

// Fewest coins that add up to `amount`, or -1 if impossible.
int minCoins(const std::vector<int>& coins, int amount) {
    std::vector<int> best(amount + 1, INT_MAX);
    best[0] = 0;                                   // zero coins make 0
    for (int a = 1; a <= amount; ++a)
        for (int c : coins)
            if (c <= a && best[a - c] != INT_MAX)
                best[a] = std::min(best[a], best[a - c] + 1);
    return best[amount] == INT_MAX ? -1 : best[amount];
}

int main() {
    std::cout << minCoins({1, 5, 10, 25}, 63) << '\n';   // 25+25+10+1+1+1
    std::cout << minCoins({1, 3, 4}, 6) << '\n';         // 3+3, greedy would say 4+1+1
    std::cout << minCoins({5, 10}, 3) << '\n';
}

Outputcompiled & run with real C++

6
2
-1

Your turn

Change the table to count the number of ways to make the amount instead of the fewest coins. Loop over coins in the outer loop so each combination is counted once.

Spotting a DP problem

The wording gives it away: "the minimum number of", "the number of ways to", "the longest ... such that". Write the brute-force recursion first, notice it recomputes the same arguments, then add the cache.

Cheat sheet: which container, which algorithm

You need to…	Reach for
Keep a list and index into it	`std::vector` (always the first thing to try)
Add and remove at both ends	`std::deque`
Undo, nesting, "most recent"	`std::stack`
Process in arrival order, BFS	`std::queue`
Look up by key, order irrelevant	`std::unordered_map` / `unordered_set`
Look up by key and iterate in order, range queries	`std::map` / `std::set` + `lower_bound`
Always take the smallest / largest next	`std::priority_queue`
Search sorted data	`std::lower_bound`, `std::binary_search`
Sort	`std::sort`, or `std::stable_sort` for multi-key sorts
Fixed-size array known at compile time	`std::array`

Amortised O(1): An operation that is occasionally expensive (a vector reallocating) but O(1) on average over a long sequence of calls.
Adjacency list: A graph stored as, for each node, the list of its neighbours: vector> in C++.
BFS: Breadth-first search: explore a graph ring by ring with a queue; finds shortest paths in unweighted graphs.
DFS: Depth-first search: follow one path as deep as possible before backtracking, with recursion or a stack.
Container adapter: std::stack, std::queue and std::priority_queue: restricted interfaces wrapped around another container.
Heap: A complete binary tree stored in an array where every parent is <= (min-heap) or >= (max-heap) its children.
Load factor: Elements divided by buckets in a hash table. When it passes max_load_factor the table rehashes into more buckets.
Memoisation: Caching the result of a function call by its arguments so a repeated subproblem is computed once.
Stable sort: A sort that keeps equal elements in their original relative order.
Strict weak ordering: The rule a sort comparator must follow: behave like <, never like <=.

Quick check

You need the users sorted by name and must also find "every name starting from 'M'" quickly. Which container fits best?

Quick check

Why does std::queue use std::deque underneath instead of std::vector?

← Module 12C++ + Tools Module 14 →Problem Solving

Frequently asked questions

Should I learn data structures by hand in C++ or just use the STL?

Both, in that order. Building a vector, linked list and heap by hand once teaches you pointers, ownership and what the costs mean, and interviews still ask for it. At work, use the STL: it is faster, tested and what reviewers expect.

Is std::unordered_map always faster than std::map?

For single lookups on large data, usually yes: O(1) average versus O(log n). But std::map keeps keys sorted, supports range queries with lower_bound, and has no worst-case rehash spikes. For small maps the difference is often negligible, so choose by whether you need order.

Why is std::vector preferred over std::list in C++?

Contiguous memory. Walking a vector streams through the CPU cache, while each list node is a separate allocation somewhere else in memory. In practice a vector is faster even for many middle insertions until n gets large.

Finish the C++ handbook, then get hired

Sit the exam for your certificate, run your resume through the ATS checker, and see the jobs that ask for exactly this.

Check my resume

Found this course useful? Share it.

ShareX LinkedIn

Comments

Join the conversation. Sign in to leave a comment — we'd love to hear your thoughts.