C++ STL Overview: Containers, Algorithms & Iterators Explained
Table of Contents
What Is the STL?
The Standard Template Library (STL) is C++’s collection of generic data structures and algorithms. It ships with every C++ compiler and provides battle-tested, performance-optimized implementations of containers like vectors, maps, and sets, plus over 100 algorithms that operate on them. The STL is built entirely on templates, which means it works with any type — built-in or user-defined — with zero runtime overhead from generics.
Before the STL, C++ programmers wrote their own linked lists, hash tables, and sorting routines for every project. The STL changed everything by providing a common vocabulary of containers and algorithms that every C++ developer knows. When you see std::vector, std::sort, or std::find, you immediately understand what the code does.
The Three Pillars
The STL is organized around three connected concepts:
Containers store data. They manage memory, handle element construction/destruction, and provide access to their elements. Think of them as data structures: arrays, linked lists, trees, hash tables.
Algorithms process data. They sort, search, transform, copy, and manipulate elements. Algorithms don’t know or care which container holds the data — they work through iterators.
Iterators connect containers to algorithms. They provide a uniform interface for traversing elements, regardless of the underlying container. This separation is the STL’s genius: M containers × N algorithms requires only M + N implementations, not M × N.
#include <vector>
#include <algorithm>
#include <iostream>
int main() {
std::vector<int> data = {5, 2, 8, 1, 9, 3}; // container
// Algorithm operates through iterators
std::sort(data.begin(), data.end());
for (const auto& val : data) { // range-based for uses iterators
std::cout << val << " ";
}
// Output: 1 2 3 5 8 9
}Sequence Containers
Sequence containers maintain elements in the order you insert them:
#include <vector>
#include <deque>
#include <list>
#include <forward_list>
#include <array>
// std::vector — dynamic array, the default choice
std::vector<int> v = {1, 2, 3};
v.push_back(4); // O(1) amortized
v[0] = 10; // O(1) random access
// Best for: most situations, sequential access, random access
// std::deque — double-ended queue
std::deque<int> d = {1, 2, 3};
d.push_front(0); // O(1) — vector can't do this efficiently
d.push_back(4); // O(1)
d[2] = 10; // O(1) random access
// Best for: push/pop at both ends
// std::list — doubly-linked list
std::list<int> lst = {1, 2, 3};
auto it = lst.begin();
std::advance(it, 1);
lst.insert(it, 99); // O(1) insert anywhere (given iterator)
lst.splice(lst.end(), other_list); // O(1) merge
// Best for: frequent insert/remove in the middle
// std::forward_list — singly-linked list
std::forward_list<int> fl = {1, 2, 3};
fl.push_front(0); // O(1)
// Best for: minimal memory overhead, forward-only traversal
// std::array — fixed-size, stack-allocated
std::array<int, 5> arr = {1, 2, 3, 4, 5};
arr[0] = 10; // O(1), bounds-checked with .at()
// Best for: compile-time known size, zero overheadRule of thumb: Use std::vector by default. Its contiguous memory layout gives excellent cache performance that beats linked structures in almost every real-world benchmark. Only switch to another container when profiling proves it’s a bottleneck.
Associative Containers
Associative containers maintain elements in sorted order using a balanced binary tree (typically Red-Black tree). All operations are O(log n):
#include <set>
#include <map>
// std::set — sorted unique elements
std::set<int> s = {3, 1, 4, 1, 5}; // {1, 3, 4, 5} — duplicates removed
s.insert(2); // O(log n)
s.count(3); // 1 (exists) or 0 (not found)
s.find(4); // returns iterator or s.end()
// std::map — sorted key-value pairs
std::map<std::string, int> ages;
ages["Alice"] = 30; // insert or update
ages["Bob"] = 25;
ages.insert({"Charlie", 35});
for (const auto& [name, age] : ages) { // structured bindings (C++17)
std::cout << name << ": " << age << "\n";
}
// Output is alphabetical: Alice: 30, Bob: 25, Charlie: 35
// std::multiset — allows duplicates
std::multiset<int> ms = {3, 1, 4, 1, 5, 1}; // {1, 1, 1, 3, 4, 5}
ms.count(1); // 3
// std::multimap — allows duplicate keys
std::multimap<std::string, std::string> phonebook;
phonebook.insert({"Alice", "555-1234"});
phonebook.insert({"Alice", "555-5678"}); // two entries for AliceUnordered Containers
Unordered containers use hash tables for O(1) average-case lookups. They trade sorted order for speed:
#include <unordered_set>
#include <unordered_map>
// std::unordered_set — hash-based unique elements
std::unordered_set<std::string> words = {"hello", "world", "foo"};
words.insert("bar"); // O(1) average
words.count("hello"); // O(1) average
// std::unordered_map — hash-based key-value pairs
std::unordered_map<std::string, int> freq;
std::string text = "the cat sat on the mat";
// Count word frequencies
for (const auto& word : split(text)) { // hypothetical split
freq[word]++; // O(1) average insert/lookup
}
// Bucket interface — inspect hash distribution
std::cout << "Buckets: " << freq.bucket_count() << "\n";
std::cout << "Load factor: " << freq.load_factor() << "\n";
// Reserve space to avoid rehashing
freq.reserve(1000); // pre-allocate for 1000 elementsChoose unordered_map over map when you need fast lookups and don’t care about order. Choose map when you need sorted iteration or range queries (lower_bound, upper_bound).
Container Adapters
Adapters wrap an underlying container to provide a restricted interface:
#include <stack>
#include <queue>
// std::stack — LIFO (Last In, First Out)
std::stack<int> stk; // backed by std::deque by default
stk.push(1);
stk.push(2);
stk.push(3);
stk.top(); // 3
stk.pop(); // removes 3
// std::queue — FIFO (First In, First Out)
std::queue<int> q; // backed by std::deque by default
q.push(1);
q.push(2);
q.front(); // 1
q.back(); // 2
q.pop(); // removes 1
// std::priority_queue — max-heap by default
std::priority_queue<int> pq;
pq.push(3);
pq.push(1);
pq.push(4);
pq.top(); // 4 (largest)
pq.pop(); // removes 4
// Min-heap:
std::priority_queue<int, std::vector<int>, std::greater<int>> min_pq;Iterators
Iterators are the glue between containers and algorithms. They abstract element access into a pointer-like interface:
#include <vector>
#include <iterator>
#include <iostream>
std::vector<int> v = {10, 20, 30, 40, 50};
// Forward iteration
for (auto it = v.begin(); it != v.end(); ++it) {
std::cout << *it << " "; // dereference like a pointer
}
// Reverse iteration
for (auto rit = v.rbegin(); rit != v.rend(); ++rit) {
std::cout << *rit << " "; // 50 40 30 20 10
}
// Const iteration (read-only)
for (auto cit = v.cbegin(); cit != v.cend(); ++cit) {
// *cit = 99; // ERROR: const iterator
std::cout << *cit << " ";
}
// Iterator arithmetic (random-access iterators only)
auto it = v.begin();
it += 3; // jump to 4th element
auto dist = it - v.begin(); // 3
std::cout << v[dist]; // 40Iterator categories form a hierarchy: Input (read once, forward) → Forward (read/write, forward, multi-pass) → Bidirectional (+ backward) → Random Access (+ jumps, arithmetic). Containers provide iterators of different categories: vector gives random-access, list gives bidirectional, forward_list gives forward-only. Algorithms require a minimum iterator category — std::sort needs random-access, so it works with vector but not list.
Algorithms
The <algorithm> header provides 100+ functions that operate on iterator ranges:
#include <algorithm>
#include <numeric>
#include <vector>
std::vector<int> v = {5, 2, 8, 1, 9, 3, 7, 4, 6};
// Sorting
std::sort(v.begin(), v.end()); // ascending
std::sort(v.begin(), v.end(), std::greater<>{}); // descending
std::stable_sort(v.begin(), v.end()); // preserves equal order
std::partial_sort(v.begin(), v.begin()+3, v.end()); // top 3 sorted
// Searching
auto it = std::find(v.begin(), v.end(), 5); // linear search
bool found = std::binary_search(v.begin(), v.end(), 5); // requires sorted
auto lb = std::lower_bound(v.begin(), v.end(), 5); // first >= 5
// Counting and checking
int count = std::count_if(v.begin(), v.end(), [](int x) { return x > 5; });
bool all = std::all_of(v.begin(), v.end(), [](int x) { return x > 0; });
bool any = std::any_of(v.begin(), v.end(), [](int x) { return x > 8; });
// Transforming
std::vector<int> doubled(v.size());
std::transform(v.begin(), v.end(), doubled.begin(), [](int x) { return x * 2; });
// Accumulating (in <numeric>)
int sum = std::accumulate(v.begin(), v.end(), 0);
int product = std::accumulate(v.begin(), v.end(), 1, std::multiplies<>{});
// Removing (erase-remove idiom)
v.erase(std::remove_if(v.begin(), v.end(), [](int x) { return x < 3; }), v.end());
// Min/Max
auto [min_it, max_it] = std::minmax_element(v.begin(), v.end());
// Copying and filling
std::vector<int> dest(5);
std::copy_n(v.begin(), 5, dest.begin());
std::fill(dest.begin(), dest.end(), 0);
std::iota(dest.begin(), dest.end(), 1); // {1, 2, 3, 4, 5}Choosing the Right Container
Here’s a decision guide for selecting STL containers:
Need random access by index? Use vector (dynamic) or array (fixed). Need fast push/pop at both ends? Use deque. Need frequent insert/remove in the middle? Use list (but measure first — vector often wins anyway due to cache). Need sorted unique keys? Use set. Need sorted key-value pairs? Use map. Need O(1) lookups by key? Use unordered_map. Need a LIFO stack? Use stack. Need a FIFO queue? Use queue. Need elements sorted by priority? Use priority_queue.
When unsure, start with vector. It’s cache-friendly, has low overhead, and outperforms theoretically superior containers for small-to-medium datasets. Only optimize to a different container when profiling shows a bottleneck.
Ranges (C++20)
C++20 introduced ranges, which modernize how you compose algorithms. Instead of passing iterator pairs, you pass the container directly and chain operations with the pipe operator:
#include <ranges>
#include <vector>
#include <iostream>
int main() {
std::vector<int> nums = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
// Traditional STL approach
std::vector<int> result;
std::copy_if(nums.begin(), nums.end(), std::back_inserter(result),
[](int x) { return x % 2 == 0; });
std::transform(result.begin(), result.end(), result.begin(),
[](int x) { return x * x; });
// Ranges approach (C++20) — lazy, composable, no temporaries
auto even_squares = nums
| std::views::filter([](int x) { return x % 2 == 0; })
| std::views::transform([](int x) { return x * x; });
for (int val : even_squares) {
std::cout << val << " "; // 4 16 36 64 100
}
// Ranges algorithms accept containers directly
std::ranges::sort(nums);
auto it = std::ranges::find(nums, 5);
bool all_pos = std::ranges::all_of(nums, [](int x) { return x > 0; });
}Views are lazy — they don’t create intermediate containers. The filtering and transforming happen as you iterate, which saves memory and often improves performance. Ranges are the future of STL-style programming in C++.
Common Mistakes
Iterator invalidation. Modifying a container while iterating over it can invalidate iterators. vector::push_back may reallocate, invalidating all iterators. map::erase invalidates the erased iterator but not others. Know your container’s invalidation rules.
Using [] on maps without checking. map[key] inserts a default-constructed value if the key doesn’t exist. Use .find() or .count() to check existence first, or .at() which throws if missing.
Sorting a list with std::sort. std::sort requires random-access iterators. list provides bidirectional iterators. Use list.sort() member function instead.
Premature optimization. Choosing unordered_map “because O(1)” without benchmarking. For small maps (under ~100 elements), a sorted vector of pairs often beats both map and unordered_map due to cache locality.
Summary
The STL provides containers (data storage), algorithms (data processing), and iterators (the bridge between them). Sequence containers (vector, deque, list) maintain insertion order. Associative containers (set, map) maintain sorted order via trees. Unordered containers use hash tables for O(1) lookups. Adapters (stack, queue, priority_queue) restrict container interfaces. Over 100 algorithms in <algorithm> handle sorting, searching, transforming, and more. C++20 ranges modernize the interface with lazy composition. In the next lesson, you’ll dive deep into std::array — the fixed-size container that replaces C-style arrays with zero overhead.
