Chapter 6: The Standard Template Library (STL)
The STL is the heart of C++. Master it, and you'll write efficient, expressive code.
STL Philosophy
┌─────────────────────────────────────────────────────────────┐
│ 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 │
│ ↓ ↓ │
│ Forward Iterator ←───────────┘ │
│ ↓ │
│ Bidirectional Iterator │
│ ↓ │
│ Random Access Iterator │
│ ↓ │
│ 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/unord_set│
│ │ │
│ └── No ──▶ Need insert at both ends?│
│ │ │
│ ├── Yes ──▶ deque│
│ └── No ──▶ Need middle insert?│
│ │
│ ├── Yes ──▶ list│
│ └── No ──▶ vector│
│ │
└─────────────────────────────────────────────────────────────┘
Exercises
Container Practice
- Implement a word frequency counter using unordered_map
- Find the top 10 most frequent words
Algorithm Mastery
- Implement a simple scheduler using priority_queue
- Use algorithms to analyze a dataset (find outliers, compute stats)
Custom Type in Containers
- Create a Person class with name and age
- Store in set (define operator<)
- Store in unordered_set (define hash)
Iterator Practice
- Write a function that accepts iterators (generic)
- Implement a simple transform function using iterators
Previous: 05 - Modern C++ Features Next: 07 - Build Systems