Week 26 — The STL · From Zero to AI Hero

A toolbox filled with neatly organised wrenches and tools.

The STL is your toolbox. Forty years of careful tool design, and you don't have to forge any of it yourself.

You'd be amazed how often, in real C++ code, the answer to "how do I store this?" is "use a vector". Or a std::map. Or a std::unordered_set. The Standard Template Library — designed in the early 1990s by Alexander Stepanov, shipped with every C++ compiler since — gives you a pile of well-tested data structures and algorithms for free. Knowing what's in it is half the work of writing efficient C++.

The containers you'll use 95% of the time

std::vector<T>

Dynamic array. The default container. Contiguous memory, cache-friendly.

push_back O(1) · index O(1)

std::array<T, N>

Fixed-size array on the stack. When N is known at compile time.

index O(1)

std::string

Growable string of chars. Most-used class in C++.

append O(1)*

std::unordered_map<K,V>

Hash map. Lookup by key in average O(1).

lookup O(1) avg

std::map<K,V>

Ordered map (binary tree). Slower than unordered, but keeps keys sorted.

lookup O(log N)

std::unordered_set<T>

Set of unique values, hash-based.

contains O(1) avg

std::deque<T>

Double-ended queue. Add/remove from both ends.

push_front/back O(1)

std::list<T>

Doubly-linked list. Rare in practice — vectors are usually faster.

insert/erase O(1) at iterator

If you're not sure, use std::vector. It's almost always the right answer. Modern CPUs love contiguous memory; even when an algorithm theoretically prefers a linked structure, the cache misses usually punish it harder than the algorithmic difference rewards it.

A whirlwind tour

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

int main() {
    // vector: dynamic array
    std::vector<int> scores = {87, 93, 71, 95, 82};
    scores.push_back(90);
    std::sort(scores.begin(), scores.end());
    for (int s : scores) std::cout << s << " ";
    std::cout << "\n";
    // 71 82 87 90 93 95

    // hash map: word counts
    std::unordered_map<std::string, int> counts;
    for (const auto& w : {"foo", "bar", "foo", "baz", "bar", "foo"}) {
        counts[w]++;
    }
    // counts["foo"] == 3, counts["bar"] == 2, counts["baz"] == 1

    // algorithm: max element
    auto it = std::max_element(scores.begin(), scores.end());
    std::cout << "max: " << *it << "\n";
}

Notice std::sort and std::max_element aren't members of vector. They're free functions in <algorithm> that work on any container that exposes iterators. Iterators are the STL's central abstraction — a generalised pointer that algorithms use to walk a container without knowing which container they're walking.

Templates — how the STL stays generic

Why std::vector<int> and std::vector<Account> are both well-typed and equally fast: vector is a template. The compiler stamps out a fresh, type-specific copy of the code for each T you use, and inlines it. This is sometimes called compile-time polymorphism — the trick that gives the STL its speed (no virtual dispatch overhead) without sacrificing genericity.

The downside: compile times balloon, and error messages when you misuse a template are famously baroque. Modern C++ has concepts (C++20) to constrain templates and produce friendlier errors. Most working programmers use the STL without ever needing to write a template themselves.

Why this matters for AI

Every AI codebase is shot through with STL containers. std::vector<Tensor> for layer outputs. std::unordered_map<std::string, Tensor> for parameter dictionaries. std::sort on top-K logits. The STL is the substrate — knowing it well means writing AI extensions feels like writing any other C++ code.

Half of writing fast, correct C++ is reaching for the right STL container.

Try it yourself

Write the word-count example. Try it on a real file (read with std::ifstream).
Sort a std::vector<Account> by balance, descending. Use a lambda as the comparator: std::sort(v.begin(), v.end(), [](auto& a, auto& b){ return a.balance() > b.balance(); }).
Skim cppreference.com/w/cpp/algorithm. There's an algorithm for almost everything you'd hand-write.

What's next

Code that does the right thing in the happy case is half the job. Code that does the right thing when something goes wrong — file missing, network down, allocation failed — is the other half. C++ has two main answers, and the choice between them has been a thirty-year argument.

Week 27 is Error Handling — exceptions, return codes, and graceful crashing.

Photo credit

Photo free under the Unsplash license. Tools · Alexander Schimmeck.