The Standard Template Library

What the STL is#

The Standard Template Library is the collection of generic, template-based containers, iterators, and algorithms that ships as part of C++'s standard library — std::vector, std::map, std::sort, and dozens more. It's the single biggest reason idiomatic modern C++ almost never needs a hand-rolled dynamic array or linked list: the STL's containers are extensively battle-tested, are implemented as templates (so they work with any element type, built on exactly the generic-programming mechanism covered on the previous page), and their algorithms are written once, generically, to work across any compatible container rather than being duplicated per container type.

std::vector — a dynamic array#

std::vector<T> is the default, go-to sequence container in C++ — a contiguous, resizable array that grows automatically as elements are added:

#include <vector>
#include <iostream>

int main() {
    std::vector<int> numbers = {10, 20, 30};

    numbers.push_back(40);          // append — grows the vector automatically
    numbers[0] = 15;                  // direct indexed access, like a raw array

    std::cout << numbers.size() << "\n";  // 4
    std::cout << numbers[1] << "\n";       // 20

    for (int n : numbers) {           // range-based for — the idiomatic way to iterate
        std::cout << n << " ";        // 15 20 30 40
    }
    std::cout << "\n";
}

std::vector stores its elements contiguously in memory (just like a raw array), which gives it O(1) random access via [] and excellent cache performance — this is why it's the correct default container to reach for unless you have a specific reason (frequent insertion in the middle, for instance) to choose something else.

std::map — an ordered key-value container#

std::map<K, V> stores key-value pairs, automatically kept sorted by key, backed internally by a balanced binary search tree:

#include <map>
#include <iostream>

int main() {
    std::map<std::string, int> ages;

    ages["Ada"] = 30;
    ages["Grace"] = 45;
    ages["Linus"] = 28;

    std::cout << ages["Grace"] << "\n"; // 45

    for (const auto& [name, age] : ages) { // structured bindings (C++17) unpack each pair
        std::cout << name << ": " << age << "\n";
    }
    // Ada: 30      <- printed in KEY-SORTED order, not insertion order
    // Grace: 45
    // Linus: 28

    if (ages.find("Nobody") == ages.end()) { // find() returns end() when the key isn't present
        std::cout << "Nobody not found\n";
    }
}

For cases that don't need the keys kept in sorted order, std::unordered_map<K, V> (a hash table) is usually faster — O(1) average lookup versus std::map's O(log n) — and is the right default whenever you don't specifically need iteration in sorted key order.

Iterators#

An iterator is a generalized pointer — an object that can be dereferenced (*it) to get an element and advanced (++it) to move to the next one, giving every STL container a uniform way to be traversed regardless of its actual internal structure:

#include <vector>
#include <iostream>

int main() {
    std::vector<int> numbers = {10, 20, 30};

    for (std::vector<int>::iterator it = numbers.begin(); it != numbers.end(); ++it) {
        std::cout << *it << " "; // 10 20 30
    }
    std::cout << "\n";

    // The same loop, with auto — this is what you'll actually write in practice
    for (auto it = numbers.begin(); it != numbers.end(); ++it) {
        std::cout << *it << " "; // 10 20 30
    }
}

A range-based for loop (used throughout this track) is really syntactic sugar over exactly this iterator pattern — for (int n : numbers) compiles down to essentially the same begin()/end()/++ loop written by hand above. Iterators are what let a single generic algorithm like std::sort work identically across std::vector, a plain array, or any other container that exposes compatible iterators — the algorithm only ever talks to the iterators, never to the container's internals directly.

Algorithms: std::sort, std::find, and friends#

The <algorithm> header provides generic algorithms that operate on a range, specified as a pair of iterators (begin, end) — completely decoupled from any specific container type:

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

int main() {
    std::vector<int> numbers = {5, 2, 8, 1, 9, 3};

    std::sort(numbers.begin(), numbers.end()); // sorts in place, ascending by default
    for (int n : numbers) std::cout << n << " "; // 1 2 3 5 8 9
    std::cout << "\n";

    std::sort(numbers.begin(), numbers.end(), std::greater<int>()); // descending, custom comparator
    for (int n : numbers) std::cout << n << " "; // 9 8 5 3 2 1
    std::cout << "\n";

    auto it = std::find(numbers.begin(), numbers.end(), 5);
    if (it != numbers.end()) {
        std::cout << "Found 5 at position " << std::distance(numbers.begin(), it) << "\n";
    }

    int count = std::count_if(numbers.begin(), numbers.end(), [](int n) { return n > 3; });
    std::cout << count << " numbers greater than 3\n"; // 4
}

std::find returns an iterator to the first matching element, or end() if nothing matched — checking against end() is the standard idiom for "was it actually found," directly analogous to checking std::map::find against .end() above. std::count_if, std::sort with a custom comparator, and many other algorithms accept a lambda (an inline, anonymous function) to customize their behavior without writing a separate named function just for one call site.

Putting it together: a complete example#

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

struct Employee {
    std::string name;
    int salary;
};

int main() {
    std::vector<Employee> employees = {
        {"Ada", 85000},
        {"Grace", 95000},
        {"Linus", 78000},
    };

    // Sort by salary, descending, using a lambda as the comparator
    std::sort(employees.begin(), employees.end(), [](const Employee& a, const Employee& b) {
        return a.salary > b.salary;
    });

    std::map<std::string, int> salaryByName; // rebuild as a sorted lookup structure
    for (const auto& e : employees) {
        salaryByName[e.name] = e.salary;
    }

    for (const auto& e : employees) {
        std::cout << e.name << ": " << e.salary << "\n";
    }
    // Grace: 95000
    // Ada: 85000
    // Linus: 78000

    auto highEarner = std::find_if(employees.begin(), employees.end(), [](const Employee& e) {
        return e.salary > 90000;
    });
    if (highEarner != employees.end()) {
        std::cout << highEarner->name << " earns over 90000\n"; // Grace earns over 90000
    }
}

Common mistakes#

• Reaching for std::map by default when std::unordered_map would do — pay the O(log n) cost of a sorted map only when you actually need sorted iteration; otherwise the hash table is faster.
• Comparing an iterator from one container against end() of a different container (or against an iterator from before a resize invalidated it) — iterators are only meaningful relative to the exact container instance and state they came from.
• Modifying a std::vector (especially via push_back, which can trigger a reallocation) while holding onto iterators or references into it from before the modification — those iterators/references can be silently invalidated.
• Writing a manual index-based or pointer-based loop where a standard algorithm (std::sort, std::find, std::count_if) already does exactly what's needed, more concisely and with a name that documents the intent.

Interview questions#

Q: What's the difference between std::map and std::unordered_map, and when would you choose one over the other? std::map keeps its keys sorted (backed by a balanced tree), giving O(log n) lookup and insertion but also ordered iteration. std::unordered_map is backed by a hash table, giving O(1) average-case lookup and insertion but with no defined iteration order. Choose std::unordered_map by default for pure key-value lookup performance; choose std::map specifically when you need the keys iterated in sorted order, or need operations like finding the smallest key greater than some value.

Q: What is an iterator, conceptually, and why does the STL's algorithm library depend on it so heavily? An iterator is an object that generalizes the idea of a pointer into a sequence — it can be dereferenced to get the current element and advanced to move to the next one, using a uniform interface regardless of what's actually stored underneath (a contiguous array, a tree, a linked list). Because algorithms like std::sort and std::find are written purely in terms of a begin/end pair of iterators rather than any specific container type, the same algorithm implementation works unchanged across every STL container (and even raw arrays) that expose compatible iterators — this decoupling of algorithms from containers is the core design idea of the whole STL.