The Standard Template Library (STL)

The STL is the part of C++ you reach for daily: containers, iterators, and algorithms that compose. Knowing the STL well means writing less code that does more.

STL Architecture

Three pieces, designed to work together. Containers hold data, algorithms act on data, iterators bridge the two.

+-------------------------------------------------------------+
|                    STL Architecture                         |
+-------------------------------------------------------------+
|                                                             |
|   Containers          Iterators          Algorithms         |
|   ----------          ---------          ----------         |
|   Store data          Bridge             Operate on         |
|   - vector            between            data               |
|   - map               containers         - sort             |
|   - set               and algorithms     - find             |
|   - list              - begin/end        - transform        |
|   - deque             - forward          - accumulate       |
|                       - bidirectional                       |
|                       - random access                       |
|                                                             |
|   Container <---------- Iterator ----------> Algorithm      |
|                                                             |
+-------------------------------------------------------------+

Sequence Containers

std::vector (Dynamic Array)

The most commonly used container. Use it by default.

#include <vector>

// Creation
std::vector<int> v1;                    // Empty
std::vector<int> v2(10);                // 10 elements, value 0
std::vector<int> v3(10, 42);            // 10 elements, value 42
std::vector<int> v4 = {1, 2, 3, 4, 5};  // Initializer list
std::vector<int> v5(v4.begin(), v4.end());  // From iterators

// Size and capacity
v1.size();      // Number of elements
v1.capacity();  // Allocated space
v1.empty();     // Is empty?
v1.reserve(100); // Pre-allocate (optimization)
v1.shrink_to_fit(); // Release unused capacity

// Access
v4[0];          // No bounds check (fast)
v4.at(0);       // Bounds checked (throws)
v4.front();     // First element
v4.back();      // Last element
v4.data();      // Raw pointer to data

// Modification
v1.push_back(10);       // Add to end
v1.emplace_back(10);    // Construct in place (more efficient)
v1.pop_back();          // Remove from end
v1.insert(v1.begin(), 5);  // Insert at position
v1.erase(v1.begin());   // Remove at position
v1.clear();             // Remove all

// Iteration
for (int x : v4) { }                    // Range-based
for (auto it = v4.begin(); it != v4.end(); ++it) { }  // Iterator

// 2D vector
std::vector<std::vector<int>> matrix(3, std::vector<int>(4, 0));
matrix[1][2] = 42;

Performance Characteristics:

• Random access: O(1)
• Insert/delete at end: Amortized O(1)
• Insert/delete elsewhere: O(n)

std::deque (Double-Ended Queue)

#include <deque>

std::deque<int> dq = {1, 2, 3};

dq.push_front(0);  // Add to front (O(1))
dq.push_back(4);   // Add to end (O(1))
dq.pop_front();    // Remove from front
dq.pop_back();     // Remove from end

dq[2];  // Random access (slightly slower than vector)

Use when: You need O(1) insertion at both ends.

std::list (Doubly-Linked List)

#include <list>

std::list<int> lst = {1, 2, 3, 4, 5};

lst.push_front(0);
lst.push_back(6);

// Efficient insert/remove anywhere (with iterator)
auto it = std::find(lst.begin(), lst.end(), 3);
lst.insert(it, 99);  // O(1) once you have iterator
lst.erase(it);       // O(1)

// Special list operations
lst.sort();              // Built-in sort (can't use std::sort)
lst.unique();            // Remove consecutive duplicates
lst.reverse();           // Reverse in place
lst.merge(other_list);   // Merge sorted lists
lst.splice(pos, other);  // Move elements from other list

Use when: You need frequent insertion/deletion in the middle.

std::array (Fixed-Size Array)

#include <array>

std::array<int, 5> arr = {1, 2, 3, 4, 5};

arr.size();      // 5 (constexpr)
arr[0];          // Access
arr.at(0);       // Bounds-checked access
arr.fill(0);     // Set all to 0

// Can use STL algorithms
std::sort(arr.begin(), arr.end());

Use when: Size is known at compile time.

Associative Containers

std::map (Ordered Key-Value)

#include <map>

std::map<std::string, int> ages;

// Insert
ages["Alice"] = 30;
ages.insert({"Bob", 25});
ages.emplace("Charlie", 35);

// Access
int age = ages["Alice"];          // Creates entry if missing!
int age = ages.at("Alice");       // Throws if missing

// Check existence
if (ages.count("Alice") > 0) { }  // count is 0 or 1
if (ages.contains("Alice")) { }   // C++20
if (auto it = ages.find("Alice"); it != ages.end()) {
    std::cout << it->second << "\n";
}

// Iteration (sorted by key)
for (const auto& [name, age] : ages) {
    std::cout << name << ": " << age << "\n";
}

// Erase
ages.erase("Alice");
ages.erase(ages.begin());

// C++17: insert_or_assign, try_emplace
ages.insert_or_assign("Alice", 31);  // Updates existing
ages.try_emplace("Dave", 40);        // Only if key doesn't exist

Performance: O(log n) for insert, find, erase (red-black tree).

std::unordered_map (Hash Table)

#include <unordered_map>

std::unordered_map<std::string, int> ages;

// Same interface as map, but:
// - O(1) average, O(n) worst case
// - Not sorted
// - Keys must be hashable

// For custom types, provide hash function
struct Point {
    int x, y;
    bool operator==(const Point&) const = default;
};

struct PointHash {
    size_t operator()(const Point& p) const {
        return std::hash<int>{}(p.x) ^ (std::hash<int>{}(p.y) << 1);
    }
};

std::unordered_map<Point, std::string, PointHash> points;

std::set and std::unordered_set

#include <set>
#include <unordered_set>

std::set<int> s = {3, 1, 4, 1, 5};  // {1, 3, 4, 5} - sorted, unique

s.insert(2);       // Add element
s.erase(3);        // Remove element
s.count(4);        // 0 or 1
s.contains(4);     // C++20
s.find(4);         // Iterator or end()

// Set operations
std::set<int> a = {1, 2, 3};
std::set<int> b = {2, 3, 4};

std::set<int> intersection, union_set, difference;
std::set_intersection(a.begin(), a.end(), b.begin(), b.end(),
    std::inserter(intersection, intersection.begin()));  // {2, 3}
std::set_union(a.begin(), a.end(), b.begin(), b.end(),
    std::inserter(union_set, union_set.begin()));        // {1, 2, 3, 4}
std::set_difference(a.begin(), a.end(), b.begin(), b.end(),
    std::inserter(difference, difference.begin()));      // {1}

std::multimap and std::multiset

#include <map>

std::multimap<std::string, int> scores;
scores.insert({"Alice", 100});
scores.insert({"Alice", 95});   // Duplicate keys allowed
scores.insert({"Alice", 105});

// Find all entries for key
auto range = scores.equal_range("Alice");
for (auto it = range.first; it != range.second; ++it) {
    std::cout << it->second << "\n";  // 95, 100, 105
}

Container Adaptors

std::stack (LIFO)

#include <stack>

std::stack<int> s;

s.push(1);
s.push(2);
s.push(3);

s.top();   // 3 (peek)
s.pop();   // Remove top (void)
s.empty(); // Is empty?
s.size();  // Number of elements

std::queue (FIFO)

#include <queue>

std::queue<int> q;

q.push(1);
q.push(2);

q.front();  // 1 (first in)
q.back();   // 2 (last in)
q.pop();    // Remove front

std::priority_queue (Heap)

#include <queue>

// Max heap by default
std::priority_queue<int> maxHeap;
maxHeap.push(3);
maxHeap.push(1);
maxHeap.push(4);
maxHeap.top();  // 4 (largest)
maxHeap.pop();

// Min heap
std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;
minHeap.push(3);
minHeap.push(1);
minHeap.top();  // 1 (smallest)

// Custom comparator
auto cmp = [](const Task& a, const Task& b) {
    return a.priority < b.priority;
};
std::priority_queue<Task, std::vector<Task>, decltype(cmp)> taskQueue(cmp);

Iterators

Iterator Categories

+-------------------------------------------------------------+
|                    Iterator Hierarchy                       |
+-------------------------------------------------------------+
|                                                             |
|   Input Iterator        Output Iterator                     |
|        v                      v                             |
|   Forward Iterator <----------+                             |
|        v                                                    |
|   Bidirectional Iterator                                    |
|        v                                                    |
|   Random Access Iterator                                    |
|        v                                                    |
|   Contiguous Iterator (C++20)                               |
|                                                             |
+-------------------------------------------------------------+
|   Container          |  Iterator Type                       |
|   --------------------------------------------------------  |
|   vector, array      |  Random access / contiguous          |
|   deque              |  Random access                       |
|   list               |  Bidirectional                       |
|   set, map           |  Bidirectional                       |
|   forward_list       |  Forward                             |
|   unordered_*        |  Forward                             |
+-------------------------------------------------------------+

Using Iterators

std::vector<int> v = {1, 2, 3, 4, 5};

// Basic iteration
for (auto it = v.begin(); it != v.end(); ++it) {
    std::cout << *it << " ";
}

// Reverse iteration
for (auto it = v.rbegin(); it != v.rend(); ++it) {
    std::cout << *it << " ";
}

// Const iteration
for (auto it = v.cbegin(); it != v.cend(); ++it) {
    // *it = 10;  // ERROR: const iterator
}

// Iterator arithmetic (random access only)
auto it = v.begin();
it += 3;           // Jump forward
auto dist = it - v.begin();  // Distance: 3
auto mid = v.begin() + v.size() / 2;  // Middle element

Iterator Invalidation

std::vector<int> v = {1, 2, 3, 4, 5};

// DANGEROUS: modifying container during iteration
for (auto it = v.begin(); it != v.end(); ++it) {
    if (*it == 3) {
        v.erase(it);  // Iterator invalidated!
        // it is now invalid, loop undefined behavior
    }
}

// SAFE: erase returns next valid iterator
for (auto it = v.begin(); it != v.end(); ) {
    if (*it == 3) {
        it = v.erase(it);  // Get next valid iterator
    } else {
        ++it;
    }
}

// SAFE: use remove-erase idiom
v.erase(std::remove(v.begin(), v.end(), 3), v.end());

// C++20: std::erase
std::erase(v, 3);
std::erase_if(v, [](int x) { return x % 2 == 0; });

Algorithms

Non-Modifying Algorithms

#include <algorithm>
#include <numeric>

std::vector<int> v = {1, 2, 3, 4, 5};

// Find
auto it = std::find(v.begin(), v.end(), 3);
auto it2 = std::find_if(v.begin(), v.end(), [](int x) { return x > 3; });

// Count
int count = std::count(v.begin(), v.end(), 3);
int count_if = std::count_if(v.begin(), v.end(), [](int x) { return x > 2; });

// All/Any/None
bool allPositive = std::all_of(v.begin(), v.end(), [](int x) { return x > 0; });
bool hasEven = std::any_of(v.begin(), v.end(), [](int x) { return x % 2 == 0; });
bool noNegative = std::none_of(v.begin(), v.end(), [](int x) { return x < 0; });

// Min/Max
auto minIt = std::min_element(v.begin(), v.end());
auto maxIt = std::max_element(v.begin(), v.end());
auto [minIt2, maxIt2] = std::minmax_element(v.begin(), v.end());

// Accumulate
int sum = std::accumulate(v.begin(), v.end(), 0);
int product = std::accumulate(v.begin(), v.end(), 1, std::multiplies<int>());

// Binary search (on sorted range)
std::sort(v.begin(), v.end());
bool found = std::binary_search(v.begin(), v.end(), 3);
auto lower = std::lower_bound(v.begin(), v.end(), 3);  // First >= 3
auto upper = std::upper_bound(v.begin(), v.end(), 3);  // First > 3

Modifying Algorithms

std::vector<int> v = {5, 2, 8, 1, 9, 3};

// Sort
std::sort(v.begin(), v.end());  // Ascending
std::sort(v.begin(), v.end(), std::greater<int>());  // Descending
std::sort(v.begin(), v.end(), [](int a, int b) { return a > b; });  // Custom

// Partial sort (find top N)
std::partial_sort(v.begin(), v.begin() + 3, v.end());  // First 3 sorted

// Nth element (find median, kth largest, etc.)
std::nth_element(v.begin(), v.begin() + v.size()/2, v.end());
// Middle element is now the median

// Stable sort (preserves order of equal elements)
std::stable_sort(v.begin(), v.end());

// Reverse
std::reverse(v.begin(), v.end());

// Rotate
std::rotate(v.begin(), v.begin() + 2, v.end());  // Move first 2 to end

// Shuffle
std::random_device rd;
std::mt19937 g(rd());
std::shuffle(v.begin(), v.end(), g);

// Unique (requires sorted range)
std::sort(v.begin(), v.end());
auto last = std::unique(v.begin(), v.end());
v.erase(last, v.end());  // Actually remove duplicates

// Fill
std::fill(v.begin(), v.end(), 0);
std::fill_n(v.begin(), 5, 42);  // Fill first 5

// Generate
std::generate(v.begin(), v.end(), [n = 0]() mutable { return n++; });

// Transform
std::transform(v.begin(), v.end(), v.begin(), [](int x) { return x * 2; });

// Transform two ranges
std::vector<int> a = {1, 2, 3}, b = {4, 5, 6}, result(3);
std::transform(a.begin(), a.end(), b.begin(), result.begin(),
    [](int x, int y) { return x + y; });  // {5, 7, 9}

// Copy
std::vector<int> dest(v.size());
std::copy(v.begin(), v.end(), dest.begin());
std::copy_if(v.begin(), v.end(), std::back_inserter(dest),
    [](int x) { return x > 0; });

// Remove (doesn't actually remove, just moves)
auto newEnd = std::remove(v.begin(), v.end(), 3);
v.erase(newEnd, v.end());  // Actually shrink

auto newEnd2 = std::remove_if(v.begin(), v.end(), [](int x) { return x < 0; });
v.erase(newEnd2, v.end());

// Replace
std::replace(v.begin(), v.end(), 1, 100);  // Replace all 1s with 100
std::replace_if(v.begin(), v.end(), [](int x) { return x < 0; }, 0);

Set Operations (on sorted ranges)

std::vector<int> a = {1, 2, 3, 4, 5};
std::vector<int> b = {3, 4, 5, 6, 7};
std::vector<int> result;

// Union
std::set_union(a.begin(), a.end(), b.begin(), b.end(),
    std::back_inserter(result));  // {1, 2, 3, 4, 5, 6, 7}

// Intersection
result.clear();
std::set_intersection(a.begin(), a.end(), b.begin(), b.end(),
    std::back_inserter(result));  // {3, 4, 5}

// Difference
result.clear();
std::set_difference(a.begin(), a.end(), b.begin(), b.end(),
    std::back_inserter(result));  // {1, 2}

// Symmetric difference
result.clear();
std::set_symmetric_difference(a.begin(), a.end(), b.begin(), b.end(),
    std::back_inserter(result));  // {1, 2, 6, 7}

// Includes (subset check)
bool isSubset = std::includes(a.begin(), a.end(), b.begin(), b.end());

Heap Operations

std::vector<int> v = {3, 1, 4, 1, 5, 9};

// Make max-heap
std::make_heap(v.begin(), v.end());

// Access max
int max = v.front();  // 9

// Add element
v.push_back(10);
std::push_heap(v.begin(), v.end());  // Restore heap property

// Remove max
std::pop_heap(v.begin(), v.end());  // Move max to end
v.pop_back();  // Actually remove

// Heap sort
std::sort_heap(v.begin(), v.end());  // Destroys heap, sorts ascending

Utilities

std::pair

#include <utility>

std::pair<int, std::string> p1(42, "hello");
auto p2 = std::make_pair(42, "hello");
std::pair p3{42, "hello"};  // C++17 CTAD

p1.first;   // 42
p1.second;  // "hello"

auto [num, str] = p1;  // Structured binding

std::tuple

#include <tuple>

std::tuple<int, double, std::string> t1(1, 3.14, "hello");
auto t2 = std::make_tuple(1, 3.14, "hello");

// Access
int a = std::get<0>(t1);
double b = std::get<1>(t1);
std::string c = std::get<2>(t1);

// Structured binding
auto [x, y, z] = t1;

// Tie (assign to existing variables)
int i; double d; std::string s;
std::tie(i, d, s) = t1;

// Ignore values
std::tie(i, std::ignore, s) = t1;

// Tuple size
constexpr size_t size = std::tuple_size_v<decltype(t1)>;  // 3

Choosing the Right Container

Container Selection Guide
=========================

Need random access?
    +-- Yes -> Need dynamic size?
    |             +-- Yes -> vector
    |             +-- No  -> array
    |
    +-- No  -> Need key-value pairs?
                  +-- Yes -> Need ordering?
                  |             +-- Yes -> map
                  |             +-- No  -> unordered_map
                  |
                  +-- No  -> Need unique elements?
                                +-- Yes -> set / unordered_set
                                +-- No  -> Need insert at both ends?
                                              +-- Yes -> deque
                                              +-- No  -> Need middle insert?
                                                            +-- Yes -> list
                                                            +-- No  -> vector

Default: vector. Only switch when measurement says otherwise.

Exercises

1. Container practice

   • Implement a word frequency counter using unordered_map
   • Find the top 10 most frequent words

2. Algorithm mastery

   • Implement a simple scheduler using priority_queue
   • Use algorithms to analyze a dataset (find outliers, compute stats)

3. Custom type in containers

   • Create a Person class with name and age
   • Store in set (define operator<)
   • Store in unordered_set (define a hash function)

4. Iterator practice

   • Write a generic function that accepts iterators
   • Implement a simple transform function using iterators

Next Steps

Continue to 07-build-systems.md. Up to here you have been compiling single files; real projects need CMake, dependencies, warnings, and sanitizers wired in.