Introduction & Syntax
STL Containers · Study material
STL containers are the ready-made data structures of the C++ Standard Library: dynamic arrays, linked lists, balanced trees, hash tables, stacks, queues and heaps, all as class templates that work with any element type. Choosing the right container is one of the most important decisions in a C++ program – it decides whether a lookup takes a microsecond or a second – and it is a favourite topic in coding interviews and competitive programming. This page explains every standard container with programs you can run: vector, deque, list, array, set, map, unordered_map, stack, queue, priority_queue and the modern span and flat_map, with complexities, traps and a guide to choosing. Then test yourself with 60 practice questions – 20 MCQs, 20 predict-the-output puzzles, 10 find-the-error programs and 10 complete programs – verified on a real C++ compiler.
On this page
- The four families: sequence, associative, unordered and adapters
- vector, deque, list, forward_list and array
- set, multiset, map, multimap and their unordered versions
- stack, queue and priority_queue
- Complexities, insert vs emplace, the operator[] trap, erasing safely, iterator invalidation
- C++20/23: contains, erase_if, span, flat_map
The container families
| Family | Containers | Organised by |
|---|---|---|
| Sequence | vector, deque, list, forward_list, array | position (the order you insert) |
| Ordered associative | set, multiset, map, multimap | sorted key (balanced tree) |
| Unordered associative | unordered_set, unordered_multiset, unordered_map, unordered_multimap | hash of the key |
| Adapters | stack, queue, priority_queue | a restricted interface over another container |
| Views / flat (C++20/23) | span, flat_map, flat_set | contiguous storage |
Sequence containers
std::vector is the default choice: contiguous memory, cache-friendly, O(1) access and amortised O(1) push_back. deque adds fast insertion at the front; list and forward_list insert and remove anywhere in O(1) given an iterator, and never move their elements; array is a fixed-size wrapper around a C array.
#include <array>
#include <deque>
#include <forward_list>
#include <iostream>
#include <list>
#include <vector>
int main() {
std::vector<int> v{3, 1, 4}; // contiguous, fast at the back, random access
v.push_back(1);
v.insert(v.begin() + 1, 9); // O(n): shifts later elements
std::deque<int> d{2, 3}; // fast at BOTH ends, random access
d.push_front(1);
d.push_back(4);
std::list<int> l{1, 2, 4}; // doubly linked: O(1) insert anywhere you have an iterator
auto it = l.begin();
++it; ++it;
l.insert(it, 3);
std::forward_list<int> f{2, 3}; // singly linked, smallest overhead
f.push_front(1);
std::array<int, 3> a{7, 8, 9}; // fixed size, no heap allocation
for (int x : v) std::cout << x << ' ';
std::cout << "| " << d.front() << d.back() << d[1] << " | ";
for (int x : l) std::cout << x;
std::cout << " | ";
for (int x : f) std::cout << x;
std::cout << " | " << a.size() << a[2] << '\n';
return 0;
}
3 9 1 4 1 | 142 | 1234 | 123 | 39
Ordered associative containers: set and map
Implemented as balanced binary search trees (usually red-black trees), they keep keys sorted and give O(log n) insert, find and erase. set/map keep unique keys; multiset/multimap allow duplicates.
#include <iostream>
#include <map>
#include <set>
#include <string>
int main() {
std::set<std::string> tags{"cpp", "stl", "cpp", "algo"}; // unique, sorted
std::multiset<int> scores{70, 85, 70, 92}; // sorted, duplicates kept
std::map<std::string, int> stock{{"pen", 40}, {"book", 12}}; // key -> value, sorted by key
stock["bag"] = 5; // insert or overwrite
stock.at("pen") -= 10; // at(): throws if the key is missing
for (const auto& t : tags) std::cout << t << ' ';
std::cout << "| " << scores.count(70) << ' ' << *scores.rbegin() << " | ";
for (const auto& [item, qty] : stock) std::cout << item << '=' << qty << ' ';
std::cout << "| " << stock.contains("ink") << tags.contains("stl") << '\n'; // C++20
return 0;
}
algo cpp stl | 2 92 | bag=5 book=12 pen=30 | 01
Unordered containers: hash tables
unordered_map and unordered_set give O(1) average lookup by hashing keys into buckets, at the cost of no ordering and O(n) worst case. Custom key types need a hash function and ==.
#include <iostream>
#include <string>
#include <unordered_map>
#include <unordered_set>
struct Point {
int x, y;
bool operator==(const Point&) const = default;
};
struct PointHash { // needed to use Point as a key
std::size_t operator()(const Point& p) const {
return std::hash<int>{}(p.x) * 31 + std::hash<int>{}(p.y);
}
};
int main() {
std::unordered_map<std::string, int> freq; // hash table: O(1) average lookup
for (std::string w : {"to", "be", "or", "not", "to", "be"}) ++freq[w];
std::cout << freq["to"] << freq["be"] << freq["not"] << ' ' << freq.size() << '\n';
std::unordered_set<Point, PointHash> visited{{0, 0}, {1, 2}};
visited.insert({1, 2}); // duplicate: ignored
std::cout << visited.size() << visited.contains({1, 2}) << visited.contains({2, 1}) << '\n';
// Iteration order of unordered containers is unspecified – never rely on it
return 0;
}
221 4 210
Container adapters
Adapters expose a restricted interface over another container: stack (LIFO, default deque), queue (FIFO, default deque) and priority_queue (a binary heap over vector, largest element on top by default). They have no iterators.
#include <functional>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
int main() {
std::stack<int> st; // LIFO
for (int x : {1, 2, 3}) st.push(x);
std::cout << "stack top " << st.top();
st.pop();
std::cout << " then " << st.top() << '\n';
std::queue<int> q; // FIFO
for (int x : {1, 2, 3}) q.push(x);
q.pop();
std::cout << "queue front " << q.front() << " back " << q.back() << '\n';
std::priority_queue<int> maxq; // largest on top (a heap)
std::priority_queue<int, std::vector<int>, std::greater<>> minq; // smallest on top
for (int x : {5, 1, 8, 3}) { maxq.push(x); minq.push(x); }
std::cout << "max " << maxq.top() << ", min " << minq.top() << ", size " << maxq.size() << '\n';
return 0;
}
stack top 3 then 2 queue front 2 back 3 max 8, min 1, size 4
Complexity of common operations
| Container | Access by index | Insert/erase at end | Insert/erase at front | Insert/erase in middle | Find by value/key |
|---|---|---|---|---|---|
| vector | O(1) | amortised O(1) | O(n) | O(n) | O(n) (O(log n) if sorted) |
| deque | O(1) | O(1) | O(1) | O(n) | O(n) |
| list | – | O(1) | O(1) | O(1) with iterator | O(n) |
| set / map | – | O(log n) | O(log n) | ||
| unordered_set / map | – | O(1) average, O(n) worst | O(1) average | ||
| priority_queue | top O(1) | push/pop O(log n) | – | ||
insert, emplace, try_emplace and the operator[] trap
map[key] inserts a default-constructed value when the key is missing – even when you only meant to read it. Use find, contains or at for lookups. insert and emplace never overwrite; try_emplace builds the value only if needed; insert_or_assign always writes.
#include <iostream>
#include <map>
#include <string>
int main() {
std::map<std::string, int> m{{"asha", 91}};
// operator[] INSERTS a default value when the key is missing
if (m["ravi"] == 0) std::cout << "size after lookup: " << m.size() << '\n';
// insert / emplace never overwrite; they report whether insertion happened
auto [it1, ok1] = m.insert({"asha", 50});
auto [it2, ok2] = m.emplace("meena", 85);
std::cout << ok1 << ' ' << it1->second << ' ' << ok2 << '\n';
// try_emplace: constructs only if absent; insert_or_assign: always writes
m.try_emplace("asha", 10);
m.insert_or_assign("ravi", 78);
// find: look up without inserting
if (auto it = m.find("john"); it == m.end()) std::cout << "john not found\n";
for (const auto& [k, v] : m) std::cout << k << '=' << v << ' ';
std::cout << '\n';
return 0;
}
size after lookup: 2 0 91 1 john not found asha=91 meena=85 ravi=78
Erasing elements and iterator invalidation
Erasing from a container while iterating needs care: an erased iterator is invalid, so use the iterator returned by erase. For vectors, C++20 std::erase_if replaces the erase-remove idiom.
#include <algorithm>
#include <iostream>
#include <map>
#include <vector>
int main() {
// C++20: std::erase / std::erase_if replace the erase-remove idiom
std::vector<int> v{1, 2, 3, 4, 5, 6, 7, 8};
std::erase_if(v, [](int x) { return x % 2 == 0; });
for (int x : v) std::cout << x << ' ';
// The classic erase-remove idiom (still everywhere in older code)
std::vector<int> w{5, 0, 5, 1, 5};
w.erase(std::remove(w.begin(), w.end(), 5), w.end());
std::cout << "| " << w.size() << '\n';
// Erasing while looping: use the iterator returned by erase
std::map<int, char> m{{1, 'a'}, {2, 'b'}, {3, 'c'}, {4, 'd'}};
for (auto it = m.begin(); it != m.end(); ) {
if (it->first % 2) it = m.erase(it); // never ++ an erased iterator
else ++it;
}
for (const auto& [k, c] : m) std::cout << k << c << ' ';
std::cout << '\n';
return 0;
}
1 3 5 7 | 2 2b 4d
| Container | What invalidates iterators/references |
|---|---|
| vector | insertion that reallocates (all); insert/erase (at and after the point) |
| deque | insert in the middle (all); push at the ends (iterators, not references) |
| list, set, map | only the erased element |
| unordered_* | rehashing (iterators, not references); the erased element |
Modern additions: span and flat_map
std::span (C++20) is a cheap non-owning view of contiguous elements – the modern replacement for "pointer + size" parameters. std::flat_map (C++23) is a sorted map stored in contiguous arrays: slower inserts, but faster lookups and iteration than a tree.
#include <array>
#include <flat_map>
#include <iostream>
#include <span>
#include <string>
#include <vector>
// std::span: a non-owning view of contiguous elements – works for arrays, vectors, std::array
int total(std::span<const int> s) { int t = 0; for (int x : s) t += x; return t; }
int main() {
int raw[] = {1, 2, 3};
std::vector<int> v{10, 20, 30, 40};
std::array<int, 2> a{100, 200};
std::cout << total(raw) << ' ' << total(v) << ' ' << total(a) << ' ' << total(std::span(v).subspan(1, 2)) << '\n';
// C++23 std::flat_map: a sorted map stored in two contiguous vectors – cache-friendly lookups
std::flat_map<std::string, int> fm{{"pune", 411}, {"delhi", 110}, {"agra", 282}};
fm["mumbai"] = 400;
for (const auto& [city, pin] : fm) std::cout << city << ':' << pin << ' ';
std::cout << '\n';
return 0;
}
6 100 300 50 agra:282 delhi:110 mumbai:400 pune:411
Which container should I use?
| Need | Use |
|---|---|
| A list of items, mostly appended and read | vector (the default) |
| Fixed number of elements known at compile time | array |
| Add/remove at both ends (sliding window, BFS) | deque |
| Many insertions/erasures in the middle, stable references | list |
| Unique items, need sorted order or range queries | set |
| Key → value, need order (lower_bound, smallest key) | map |
| Key → value, fastest lookup, order irrelevant | unordered_map |
| Always process the largest/smallest next | priority_queue |
| Undo history, bracket matching | stack |
| Process in arrival order | queue |
Common mistakes
- Reading with map[key] – silently inserts entries.
- Keeping iterators or references to vector elements across push_back.
- Erasing inside a range-for loop – invalidates the hidden iterator.
- Relying on unordered_map order – it can change between runs and compilers.
- Using list for speed – vector is usually faster even for middle inserts on small data.
- Calling top()/front() on an empty adapter – undefined behaviour.
- Forgetting the comparator meaning –
priority_queuewithstd::greatergives a min-heap.
Key points to remember
- Default to vector; choose others for a specific reason.
- set/map: sorted, O(log n). unordered_*: hashed, O(1) average, no order.
- Adapters (stack, queue, priority_queue) restrict another container's interface.
- map[key] inserts; use find/contains/at to read.
- Use the iterator returned by erase; prefer std::erase_if in C++20.
- Know which operations invalidate iterators for each container.
Frequently asked questions
What is the difference between map and unordered_map?
map is a balanced tree: keys sorted, O(log n) operations, needs <. unordered_map is a hash table: no order, O(1) average operations, needs a hash and ==.
What is the difference between vector and list?
vector stores elements contiguously with O(1) indexing; list is a doubly linked list with O(1) insertion anywhere (given an iterator) but no indexing and poor cache locality.
What are the three components of the STL?
Containers, algorithms and iterators (plus function objects); iterators connect algorithms to containers.
Where can I learn more?
Read C++ vector, C++ map and unordered_map and C++ set, then practise with the exercises below.