> ## Documentation Index
> Fetch the complete documentation index at: https://resources.devweekends.com/llms.txt
> Use this file to discover all available pages before exploring further.

# Standard Template Library

> Containers, Iterators, and Algorithms

<img src="https://mintcdn.com/devweeekends/0kwJwOL2KCwg2YYu/images/courses/cpp-crash-course/stl-containers.svg?fit=max&auto=format&n=0kwJwOL2KCwg2YYu&q=85&s=604ba158a4d41bbaca738b152c4983e9" alt="STL Containers" width="1080" height="1080" data-path="images/courses/cpp-crash-course/stl-containers.svg" />

# The Standard Template Library (STL)

The STL is C++'s superpower. It provides efficient, tested, and reusable components. **Rule #1 of C++**: If it's in the STL, don't write it yourself. Why write a buggy linked list when `std::list` exists and is optimized by experts?

***

## 1. Containers

Containers are data structures that store collections of objects. They manage memory automatically (using RAII internally), so you never need to `new`/`delete` when using them. Picking the right container is one of the most impactful performance decisions you will make in C++.

### Sequential Containers (Ordered)

**`std::vector`** (Dynamic Array)

* **What is it?**: A contiguous, dynamically-growing array. Elements are stored side-by-side in memory, which means the CPU cache can prefetch them efficiently.
* **Use by default**: 99% of the time, `vector` is the right choice. Even for small collections where you might think a linked list is "theoretically better," `vector` wins because of cache locality. Bjarne Stroustrup himself has demonstrated this in benchmarks.
* **Operations**: O(1) random access (`[]`), O(1) amortized `push_back`, O(n) insert in the middle.

```cpp theme={null}
#include <vector>

std::vector<int> nums = {1, 2, 3};
nums.push_back(4);       // Add to end: {1, 2, 3, 4}
nums[0] = 10;            // O(1) random access by index
nums.emplace_back(5);    // Construct in-place (avoids a copy for complex types)

// Reserve capacity upfront if you know the approximate size
// This avoids repeated reallocations as the vector grows
nums.reserve(1000);      // Allocates space for 1000 ints, size stays the same
```

<Warning>
  **Common pitfall -- iterator invalidation**: When a `vector` grows beyond its capacity, it allocates a new, larger block and moves all elements. This invalidates every pointer, reference, and iterator to its elements. Never hold an iterator across a `push_back` that might trigger a reallocation. If you need stable references, consider `std::deque` or `std::list`.
</Warning>

**`std::array`** (Fixed-Size Array)

* **What is it?**: A safer version of C-style arrays (`int arr[5]`).
* **Use when**: Size is known at compile time and won't change.
* **Zero overhead**: No dynamic allocation.

```cpp theme={null}
#include <array>
std::array<int, 3> point = {10, 20, 30};
```

### Associative Containers (Key-Value / Sorted)

**`std::map`** (Ordered Map)

* **What is it?**: A tree-based dictionary.
* **Order**: Keys are always sorted (alphabetically or numerically).
* **Complexity**: O(log n).

```cpp theme={null}
#include <map>

std::map<std::string, int> scores;
scores["Alice"] = 100;
scores["Bob"] = 90;

// Iterates in alphabetical order of keys: Alice, then Bob
for (const auto& [name, score] : scores) {
    std::cout << name << ": " << score << "\n";
}
```

### Unordered Containers (Hash Tables)

**`std::unordered_map`**

* **What is it?**: A hash table. Keys are hashed into buckets for near-instant lookup.
* **Order**: No guaranteed order. Elements may appear in any sequence when iterating.
* **Complexity**: O(1) average for insert, find, and erase. O(n) worst case if many keys hash to the same bucket (hash collision).
* **Use when**: You need fast lookups and do not care about iteration order. This is the right choice for caches, memoization tables, and symbol tables.

```cpp theme={null}
#include <unordered_map>

std::unordered_map<std::string, int> cache;
cache["result_a"] = 42;
cache["result_b"] = 99;

// O(1) average lookup -- much faster than std::map for large datasets
if (cache.count("result_a")) {
    std::cout << cache["result_a"];  // 42
}
```

### Container Performance Comparison

| Container       | Access     | Insert (end)                  | Insert (middle)    | Find                          | Erase              | Memory layout               | Sorted?                 |
| :-------------- | :--------- | :---------------------------- | :----------------- | :---------------------------- | :----------------- | :-------------------------- | :---------------------- |
| `vector`        | O(1) index | O(1) amortized                | O(n)               | O(n) linear / O(log n) sorted | O(n)               | Contiguous                  | No (unless you sort it) |
| `deque`         | O(1) index | O(1) front and back           | O(n)               | O(n)                          | O(n)               | Chunked blocks              | No                      |
| `list`          | O(n)       | O(1) anywhere (with iterator) | O(1) with iterator | O(n)                          | O(1) with iterator | Scattered nodes             | No                      |
| `array`         | O(1) index | N/A (fixed size)              | N/A                | O(n)                          | N/A                | Contiguous, stack-allocated | No                      |
| `map`           | O(log n)   | O(log n)                      | N/A                | O(log n)                      | O(log n)           | Red-black tree nodes        | Yes (by key)            |
| `unordered_map` | O(1) avg   | O(1) avg                      | N/A                | O(1) avg                      | O(1) avg           | Hash table + buckets        | No                      |
| `set`           | O(log n)   | O(log n)                      | N/A                | O(log n)                      | O(log n)           | Red-black tree nodes        | Yes                     |
| `unordered_set` | O(1) avg   | O(1) avg                      | N/A                | O(1) avg                      | O(1) avg           | Hash table                  | No                      |

### Container Selection Quick Guide

Choosing the right container matters. Here is a practical decision tree:

* **Need a sequence of elements?** Use `std::vector` (default) or `std::deque` (fast insert at front).
* **Need key-value pairs with sorted keys?** Use `std::map`.
* **Need key-value pairs with fast lookup?** Use `std::unordered_map`.
* **Need to ensure no duplicates?** Use `std::set` or `std::unordered_set`.
* **Need a fixed-size array?** Use `std::array`.
* **Need a FIFO queue?** Use `std::queue` (adapter over `std::deque`).
* **Need a priority queue?** Use `std::priority_queue`.

<Note>
  **The `vector` almost always wins in practice**: Even for operations where `list` has better theoretical complexity (O(1) insert vs O(n)), `std::vector` is often faster for collections under \~10,000 elements because of CPU cache effects. Contiguous memory means the CPU prefetcher loads the next elements before you ask for them. Linked list nodes are scattered across the heap, causing cache misses on every traversal. Bjarne Stroustrup's benchmarks show `vector` beating `list` for insert-in-the-middle operations up to surprisingly large sizes. Default to `vector` and switch only when profiling proves otherwise.
</Note>

### When to Reach for Something Other Than `vector`

| Situation                                           | Use instead                                                      | Why                                                       |
| :-------------------------------------------------- | :--------------------------------------------------------------- | :-------------------------------------------------------- |
| Frequent insert/remove at the front                 | `std::deque`                                                     | O(1) at both ends, no reallocation of existing elements   |
| Elements must not move in memory (stable addresses) | `std::list` or `std::deque`                                      | `vector` reallocation invalidates all pointers/references |
| Need sorted iteration AND fast lookup               | `std::map` or `std::set`                                         | Tree structure keeps elements ordered at all times        |
| Need O(1) key lookup, order does not matter         | `std::unordered_map`                                             | Hash table is 3-10x faster than `map` for large datasets  |
| Fixed number of elements known at compile time      | `std::array`                                                     | Zero heap allocation, same performance as C array         |
| Need a thread-safe FIFO queue                       | Build on `std::queue` + mutex (or use a lock-free queue library) | No STL container is thread-safe by default                |

***

## 2. Iterators

Iterators are the glue between Containers and Algorithms. Think of them as a universal "cursor" that knows how to move through any container, regardless of its internal structure. A vector iterator moves through contiguous memory; a map iterator walks a balanced tree. But the interface is the same -- that is the power of abstraction.

* `begin()`: Points to the first element.
* `end()`: Points to **one past** the last element (this is a sentinel, not a valid element).

```cpp theme={null}
std::vector<int> nums = {10, 20, 30};

// Explicit iterator usage (rarely needed in modern C++)
for (auto it = nums.begin(); it != nums.end(); ++it) {
    std::cout << *it << " ";  // Dereference (*it) to get the value, like a pointer
}
```

### Range-Based For Loop

This syntactic sugar uses iterators behind the scenes but is much cleaner. **Prefer this in all new code.**

```cpp theme={null}
// By value -- copies each element (fine for int, bad for large objects)
for (int x : nums) {
    std::cout << x << " ";
}

// By const reference -- no copy, no modification. The preferred default.
for (const auto& x : nums) {
    std::cout << x << " ";
}
```

<Tip>
  **Why does `end()` point past the last element?** This "half-open range" convention `[begin, end)` makes empty ranges natural (`begin == end`), makes computing size trivial (`end - begin`), and makes chaining ranges easy. It is used consistently throughout the STL and is one of those design decisions that seems odd at first but proves elegant in practice.
</Tip>

***

## 3. Algorithms

The `<algorithm>` header contains 100+ functions for sorting, searching, and manipulating ranges. They are often faster and less buggy than writing your own loops.

### Sorting & Searching

```cpp theme={null}
#include <algorithm>
#include <vector>

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

// Sort (O(n log n))
std::sort(nums.begin(), nums.end()); // {1, 3, 5, 9}

// Binary Search (Requires sorted range) - Returns true/false
bool found = std::binary_search(nums.begin(), nums.end(), 5); // true
```

### Transformations

```cpp theme={null}
// Multiply every element by 2
std::for_each(nums.begin(), nums.end(), [](int& n) {
    n *= 2;
});
```

### Finding

```cpp theme={null}
// Find first even number
auto it = std::find_if(nums.begin(), nums.end(), [](int n) {
    return n % 2 == 0;
});

if (it != nums.end()) {
    std::cout << "Found: " << *it;
}
```

***

## 4. Lambdas (Anonymous Functions)

Lambdas allow you to write small, throwaway functions inline. They are perfect for passing to algorithms like `sort` or `find_if`. Before C++11, you had to write separate functor classes for this -- lambdas eliminated that boilerplate entirely.

**Syntax**: `[capture](parameters) -> return_type { body }`

```cpp theme={null}
int multiplier = 10;

// Capture 'multiplier' by value so we can use it inside the lambda
auto timesTen = [multiplier](int n) {
    return n * multiplier;
};

std::cout << timesTen(5); // 50
```

### Capture Clauses

* `[]`: No capture. The lambda cannot access any variables from the enclosing scope. This is the safest option.
* `[=]`: Capture all local variables by value (copy). The lambda gets its own snapshot.
* `[&]`: Capture all local variables by reference (can modify originals).
* `[x]`: Capture only `x` by value. **Prefer explicit captures** -- they make dependencies clear.
* `[&x]`: Capture only `x` by reference.
* `[=, &x]`: Capture everything by value, except `x` by reference.

```cpp theme={null}
// Practical example: custom sort by absolute value
std::vector<int> nums = {-5, 3, -1, 4, -2};
std::sort(nums.begin(), nums.end(), [](int a, int b) {
    return std::abs(a) < std::abs(b);  // Sort by magnitude
});
// Result: {-1, -2, 3, 4, -5}
```

<Warning>
  **Dangling reference pitfall**: If you capture a local variable by reference (`[&]`) and the lambda outlives the variable (e.g., you return the lambda or store it), the reference dangles and accessing it is undefined behavior. Capture by value when the lambda might outlive the enclosing scope. This is especially dangerous with `std::async` and `std::thread`.
</Warning>

***

## Summary

* **Containers**: Use `std::vector` by default. Use `std::map` for sorted keys, `std::unordered_map` for speed.
* **Iterators**: Abstract the navigation of data.
* **Algorithms**: Prefer `std::sort`, `std::find`, etc., over writing raw loops.
* **Lambdas**: Write concise, local functions for algorithms.

Next, we'll look at the cutting edge: **Modern C++ (C++11 to C++20)** features.