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.

#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

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.

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.

#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).

#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.

#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.

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.

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).

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.

// 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 << " ";
}

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.

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

#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

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

Finding

// 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 }

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.

// 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}

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.

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.

​The Standard Template Library (STL)

​1. Containers

​Sequential Containers (Ordered)

​Associative Containers (Key-Value / Sorted)

​Unordered Containers (Hash Tables)

​Container Performance Comparison

​Container Selection Quick Guide

​When to Reach for Something Other Than vector

​2. Iterators

​Range-Based For Loop

​3. Algorithms

​Sorting & Searching

​Transformations

​Finding

​4. Lambdas (Anonymous Functions)

​Capture Clauses

​Summary

The Standard Template Library (STL)

1. Containers

Sequential Containers (Ordered)

Associative Containers (Key-Value / Sorted)

Unordered Containers (Hash Tables)

Container Performance Comparison

Container Selection Quick Guide

When to Reach for Something Other Than `vector`

2. Iterators

Range-Based For Loop

3. Algorithms

Sorting & Searching

Transformations

Finding

4. Lambdas (Anonymous Functions)

Capture Clauses

Summary