STL — Standard Template Library
The Standard Template Library packages the data structures every program needs — dynamic arrays, linked lists, trees, hash tables — into ready-made, heavily optimized templates, so you almost never have to hand-write a container again.
By the time you've learned templates, you already understand how a class like vector<T> could be written from scratch — a resizable buffer, a size and capacity, a handful of member functions. The Standard Template Library is the payoff for that understanding: it's a collection of such templates, written once by the C++ standard committee and implementation vendors, tested exhaustively, and tuned for performance in ways a hand-rolled version rarely matches on a first try. The STL has four cooperating pieces — containers that store objects, iterators that let algorithms walk over any container the same way, algorithms that operate through iterators instead of container types, and function objects that customize algorithm behavior — but this page focuses on the first piece: the containers themselves, what each one is actually good at, and how to pick the right one for a given access pattern.
What the STL Actually Is
"STL" is often used loosely to mean "the C++ standard library," but strictly it refers to a specific design: generic containers (templates parameterized on the element type), iterators that abstract over how a container is traversed, algorithms that are written once against iterators and work on any container that supplies them, and function objects (including lambdas) that let algorithms be customized without rewriting them. The payoff of that separation is enormous: std::sort doesn't know or care whether it's sorting a std::vector<int> or a std::vector<std::string> — it's written entirely in terms of iterators and a comparison, and the compiler generates a specialized, fast version for whatever type you actually use it with.
values.begin() and values.end() hand std::sort a pair of iterators, not the vector itself. std::sort has no special knowledge of std::vector — it only knows how to work with random-access iterators, and std::vector happens to provide them.
Containers themselves fall into three broad families: sequence containers, which keep elements in a linear order you control (array, vector, deque, list, forward_list); container adaptors, which restrict a sequence container to a narrower interface for a specific access pattern (stack, queue, priority_queue); and associative containers, which keep elements ordered by key or hashed by key so lookup is fast (set, multiset, map, multimap, and their unordered_ counterparts). The rest of this page walks through each family.
#include <vector>
#include <algorithm>
#include <iostream>
int main()
{
std::vector<int> values{5, 3, 8, 1, 9};
std::sort(values.begin(), values.end());
for (int v : values)
std::cout << v << " ";
std::cout << "\n";
return 0;
}Sequence Containers: array and vector
std::array<T, N> is the closest thing the STL has to a raw C-style array: its size N is fixed at compile time, it lives on the stack (or wherever it's declared) with no heap allocation at all, and it adds bounds-checked access (.at()), .size(), and iterator support on top of the same contiguous-storage guarantees a raw array gives you. Use it whenever the size is genuinely fixed and known at compile time — a 3D vector's three components, a fixed-size lookup table.
scores.at(2) throws std::out_of_range if the index is invalid; scores[2] would not check and would be undefined behavior on an out-of-range index. std::array's size (5 here) is part of its type, fixed forever once written.
std::vector<T> is the workhorse of C++ — a dynamically resizable array backed by contiguous heap storage. Because storage is contiguous, indexing with operator[] is O(1) and iterating a vector is extremely cache-friendly, which is why vector is almost always the right default container unless you have a specific reason to reach for something else.
push_back appends an element, growing the underlying buffer (typically by doubling) whenever capacity runs out. reserve(100) preallocates room for 100 elements up front so subsequent push_back calls don't need to reallocate at all, which matters when you know roughly how large the vector will get.
nums starts empty: size 0, capacity 0.
Each push_back may trigger a reallocation if capacity is exhausted, copying or moving every existing element to new storage.
reserve(100) allocates space for 100 elements without changing size — nums.size() is still 3 afterward.
Indexing with nums[i] is O(1) because the storage is contiguous.
#include <array>
#include <iostream>
int main()
{
std::array<int, 5> scores{90, 85, 77, 100, 60};
std::cout << "size: " << scores.size() << "\n";
std::cout << "third element: " << scores.at(2) << "\n";
return 0;
}#include <vector>
#include <iostream>
int main()
{
std::vector<int> nums;
nums.push_back(10);
nums.push_back(20);
nums.push_back(30);
nums.reserve(100);
for (size_t i = 0; i < nums.size(); ++i)
std::cout << nums[i] << " ";
std::cout << "\n(capacity: " << nums.capacity() << ")\n";
return 0;
}Sequence Containers: deque, list, and forward_list
std::deque<T> ("double-ended queue") supports O(1) insertion and removal at both the front and the back, unlike vector, which is only O(1) at the back. It achieves this by storing elements in fixed-size chunks rather than one contiguous block, which costs it a small amount of indexing overhead compared to vector but makes push_front practical.
push_front(1) and push_back(5) are both O(1) on a deque. The same two calls on a std::vector would make push_front O(n), since every existing element would have to shift over to make room at the beginning.
std::list<T> is a doubly linked list: every element is a separately allocated node with a pointer to the next node and the previous one. Insertion and removal at any position are O(1) once you already hold an iterator to that position, because splicing a node in or out only touches a few pointers — but list gives up random access entirely (no operator[]) and has much worse cache locality than vector or deque, since nodes can be scattered anywhere in memory.
std::next(lst.begin(), 2) advances an iterator two steps forward without disturbing lst.begin() itself. Inserting at that position is O(1) for a list, whereas the same insert on a vector would be O(n) because every element from that position onward would need to shift right.
std::forward_list<T> is a singly linked list — each node points only forward, never backward — chosen when memory overhead matters more than the ability to traverse backward or query the size in O(1) (forward_list deliberately has no .size() member, since computing it would require an O(n) traversal that programmers might not expect to be slow).
#include <deque>
#include <iostream>
int main()
{
std::deque<int> dq{2, 3, 4};
dq.push_front(1);
dq.push_back(5);
for (int v : dq)
std::cout << v << " ";
std::cout << "\n";
return 0;
}#include <list>
#include <iostream>
int main()
{
std::list<int> lst{1, 2, 4, 5};
auto it = std::next(lst.begin(), 2); // points at 4
lst.insert(it, 3); // insert 3 before it
for (int v : lst)
std::cout << v << " ";
std::cout << "\n";
return 0;
}Container Adaptors: stack, queue, and priority_queue
A container adaptor isn't a data structure of its own — it wraps an existing sequence container and exposes only a narrow, purpose-built interface on top of it, hiding operations that don't fit the adaptor's intended access pattern. std::stack<T> gives you push, pop, and top, restricting access to last-in-first-out (LIFO) order; by default it's built on top of std::deque, but you can supply any sequence container that supports back(), push_back(), and pop_back().
Pushing 1, 2, 3 and then repeatedly reading top() and popping prints 3 2 1 — the most recently pushed element comes out first, which is exactly what LIFO means. Notice pop() removes the top element but returns nothing; you must call top() before pop() to get the value.
std::queue<T> is the FIFO (first-in-first-out) counterpart: push adds to the back, pop removes from the front, and front()/back() peek at either end. std::priority_queue<T> is different in kind — it keeps its elements ordered by priority rather than by insertion order, so pop() always removes the largest element (by default; a custom comparator can flip that to smallest) rather than the oldest one. Internally it's typically built on a std::vector organized as a binary heap.
Even though 5, 1, 9, 3 were pushed in that order, priority_queue always exposes the largest remaining element at top(), so this prints 9 5 3 1 — largest to smallest — regardless of insertion order.
#include <stack>
#include <iostream>
int main()
{
std::stack<int> s;
s.push(1);
s.push(2);
s.push(3);
while (!s.empty())
{
std::cout << s.top() << " ";
s.pop();
}
std::cout << "\n";
return 0;
}#include <queue>
#include <iostream>
int main()
{
std::priority_queue<int> pq;
pq.push(5);
pq.push(1);
pq.push(9);
pq.push(3);
while (!pq.empty())
{
std::cout << pq.top() << " ";
pq.pop();
}
std::cout << "\n";
return 0;
}Associative Containers: set and map
Associative containers keep their elements sorted by key at all times, typically using a self-balancing binary search tree (a red-black tree in most implementations), which gives O(log n) insertion, lookup, and removal. std::set<T> stores unique keys with no separate value; std::map<K, V> stores key-value pairs, one value per unique key.
operator[] on a map either finds the existing value for a key or default-constructs one if the key isn't present yet, which is why ages["Alice"] = 30; works even though "Alice" was never inserted first. Iterating a std::map always visits keys in sorted order — here alphabetically — which is a guarantee set and map both make and unordered_map does not.
ages["Alice"] = 30 inserts a new key "Alice" with value 30, since it doesn't exist yet.
ages["Bob"] = 25 does the same for "Bob".
insert({"Carol", 35}) adds a third entry explicitly, without risking accidentally overwriting an existing key the way operator[] can.
The range-for with structured bindings [name, age] destructures each std::pair<const std::string, int> as it's visited, in sorted key order: Alice, Bob, Carol.
std::multiset and std::multimap relax the uniqueness constraint, allowing duplicate keys — useful when you need a sorted collection that can legitimately contain the same key more than once, such as a multiset of exam scores where ties are expected.
#include <map>
#include <iostream>
int main()
{
std::map<std::string, int> ages;
ages["Alice"] = 30;
ages["Bob"] = 25;
ages.insert({"Carol", 35});
for (const auto& [name, age] : ages)
std::cout << name << ": " << age << "\n";
return 0;
}Unordered Associative Containers: unordered_set and unordered_map
std::unordered_set<T> and std::unordered_map<K, V> trade the sorted-order guarantee for speed: they're backed by a hash table, giving average-case O(1) insertion, lookup, and removal instead of a sorted container's O(log n). The cost is that iteration order is unspecified and can even change between runs of the same program, and worst-case complexity degrades to O(n) if many keys hash to the same bucket.
++wordCount[word] relies on operator[] default-constructing a 0 for any word seen for the first time, then increments it in place. Because this is an unordered_map, the printed order of cat, dog, bird is not guaranteed to match insertion order or any predictable order at all — only the counts (cat: 3, dog: 2, bird: 1) are guaranteed correct.
Choosing between the ordered and unordered version of a container comes down to one question: do you need the elements sorted, or do you only need fast lookup? If you need to iterate keys in order, or need range queries like "all keys between X and Y" (which lower_bound and upper_bound support on ordered containers), use set/map. If you only ever look things up by exact key and don't care about order, unordered_set/unordered_map is typically faster.
#include <unordered_map>
#include <iostream>
int main()
{
std::unordered_map<std::string, int> wordCount;
for (const std::string& word : {"cat", "dog", "cat", "bird", "dog", "cat"})
++wordCount[word];
for (const auto& [word, count] : wordCount)
std::cout << word << ": " << count << "\n";
return 0;
}Choosing the Right Container
In practice, default to std::vector unless a specific access pattern argues against it: frequent insertion/removal at the front pushes you toward deque, frequent insertion/removal in the middle with iterators already in hand pushes you toward list, fast key lookup with sorted iteration pushes you toward map/set, and fast key lookup with no ordering requirement pushes you toward unordered_map/unordered_set. Reach for a container adaptor (stack, queue, priority_queue) whenever the algorithm you're implementing is naturally described as LIFO, FIFO, or priority-ordered — trying to enforce that discipline by hand on a raw vector is exactly the kind of bug an adaptor exists to prevent.
Why is std::vector the recommended default container in C++, and what specific property of list or deque would make you choose one of those instead?
std::vector stores elements contiguously, giving O(1) indexed access and excellent cache locality, which makes it the fastest choice for the vast majority of access patterns. Choose std::list when you need O(1) insertion/removal at arbitrary positions given an existing iterator (with no shifting of other elements), or std::deque when you need O(1) push/pop at both the front and back, which vector cannot provide at the front.
What is a container adaptor, and how does std::stack differ from a container in its own right like std::vector?
A container adaptor doesn't implement its own storage — it wraps an existing sequence container (deque by default for stack) and restricts the interface exposed to callers to a specific access pattern. std::stack only exposes push, pop, top, empty, and size, deliberately hiding operations like indexed access that don't fit LIFO usage, even though the underlying deque supports them.
Why does std::map guarantee sorted iteration order while std::unordered_map does not, and what's the practical trade-off between them?
std::map is implemented as a balanced binary search tree ordered by key, so an in-order traversal naturally visits keys from smallest to largest; std::unordered_map is implemented as a hash table, where an element's position depends on its hash value and bucket layout, not its key's relative order. The trade-off is speed versus ordering: unordered_map offers average O(1) operations but no ordering guarantee, while map offers O(log n) operations with guaranteed sorted iteration and support for range queries.
Why can push_back on a std::vector invalidate iterators, pointers, and references into that vector, even ones that point at elements far from the one just added?
If the vector's current capacity is exhausted, push_back must allocate a new, larger buffer and move (or copy) every existing element into it, then release the old buffer. Every iterator, pointer, and reference into the old buffer is now dangling, regardless of which element it referred to, because the entire buffer it pointed into no longer exists.
What does it mean for map["key"] = value to have a side effect even when you only meant to read the value, and how do you check for a key's existence safely?
operator[] on std::map and std::unordered_map inserts the key with a default-constructed value if it isn't already present, so writing if (m["key"] == expected) as a read can silently add a new entry with a default value as a side effect. Use m.find("key") != m.end() or m.count("key") to test existence without mutating the map.
Write a C++ program that reads a sequence of words and uses a std::map<std::string, int> to count how many times each word appears, then prints the counts in alphabetical order.
Because std::map keeps its keys sorted, iterating counts after all insertions naturally prints the words alphabetically (apple, banana, cherry) without any separate sorting step. Each ++counts[word] either creates a new entry starting at 0 (then increments to 1) or increments an existing count.
Write a C++ program that uses std::stack<char> to check whether a string of parentheses '(', ')', '[', ']', '{', '}' is balanced.
Every opening bracket is pushed onto the stack. Every closing bracket must match the most recently pushed opening bracket (the top of the stack) — if it doesn't, or the stack is already empty, the string is unbalanced. After processing the whole string, the stack must be empty too, or there were unmatched opening brackets left over. "([{}])" prints true, "([)]" prints false because ) closes against [ instead of (.
What does this code print, and why doesn't v.capacity() equal v.size()?
It prints 4 <some number >= 10> — v.size() is 4 because there are 4 elements after the push_back, but v.capacity() reflects the reserved buffer size, which reserve(10) guaranteed to be at least 10, and pushing one more element (going from 3 to 4) doesn't need to reallocate since capacity already covers it. size() and capacity() measure different things: size is how many elements are actually stored, capacity is how many the current buffer could hold before a reallocation is needed.
Write a C++ program that uses a std::priority_queue<int> to find the 3 largest values in a vector of integers.
Constructing the priority_queue directly from the vector's iterators builds the underlying heap from all the values in one pass. Popping the top three times in a row yields the three largest values in descending order — 11, 9, 8 — because top() always exposes the current maximum, and pop() removes it and re-heapifies so the next-largest value becomes the new top.
Container Access Insert/erase (end) Insert/erase (middle) Ordered?
---------------------------------------------------------------------------------------
array<T,N> O(1) n/a (fixed size) n/a n/a
vector<T> O(1) O(1) amortized (back) O(n) insertion order
deque<T> O(1) O(1) (both ends) O(n) insertion order
list<T> O(n) O(1) O(1) with iterator insertion order
set/map O(log n) O(log n) O(log n) sorted by key
unordered_set/map O(1) average O(1) average O(1) average unspecifiedstd::vector<int> v{1, 2, 3};
v.reserve(10);
v.push_back(4);
std::cout << v.size() << " " << v.capacity() << "\n";