Lesson 19 • Advanced
Advanced Containers
Deep dive into vector internals, map vs. unordered_map, deque, list, and container adapters like stack and queue.
What You'll Learn
- ✓ vector capacity, growth, and reserve
- ✓ map vs. unordered_map trade-offs
- ✓ deque and list internals
- ✓ stack, queue, and priority_queue adapters
Choosing the Right Container
The STL offers many containers, each optimised for different access patterns. Choosing the right one can mean the difference between O(1) and O(n) operations.
| Container | Structure | Access | Insert/Remove |
|---|---|---|---|
vector | Contiguous array | O(1) random | O(1) back, O(n) middle |
deque | Chunked array | O(1) random | O(1) front/back |
list | Doubly-linked | O(n) sequential | O(1) anywhere* |
map | Red-black tree | O(log n) | O(log n) |
unordered_map | Hash table | O(1) average | O(1) average |
* O(1) insert/remove for list requires an iterator to the position.
vector Internals
Watch capacity grow, use reserve and shrink_to_fit
#include <iostream>
#include <vector>
using namespace std;
int main() {
cout << "=== vector Internals ===" << endl;
vector<int> v;
cout << "Empty: size=" << v.size() << " capacity=" << v.capacity() << endl;
// Watch capacity grow (typically doubles)
for (int i = 0; i < 20; i++) {
size_t oldCap = v.capacity();
v.push_back(i);
if (v.capacity() != oldCap) {
cout << "Grew! size=" << v.size()
<< " capacity=" << v.capa
...map, set & Hash Containers
Compare ordered vs. unordered containers and their performance
#include <iostream>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
using namespace std;
int main() {
// map — ordered (red-black tree), O(log n)
cout << "=== map (ordered) ===" << endl;
map<string, int> ages;
ages["Alice"] = 30;
ages["Bob"] = 25;
ages["Charlie"] = 35;
ages.insert({"Diana", 28});
// Iteration is in sorted key order
for (const auto& [name, age] : ages) {
cout << name << ": " << age << endl;
}
...deque, list & Adapters
Use deque, linked lists, stacks, queues, and priority queues
#include <iostream>
#include <deque>
#include <list>
#include <forward_list>
#include <queue>
#include <stack>
using namespace std;
int main() {
// deque — double-ended queue (chunked array)
cout << "=== deque ===" << endl;
deque<int> dq;
dq.push_back(2);
dq.push_back(3);
dq.push_front(1); // O(1) — unlike vector!
dq.push_front(0);
cout << "deque: ";
for (int n : dq) cout << n << " ";
cout << endl;
cout << "Random access: dq[2] = " << dq[2] << e
...Common Mistakes
⚠️ Using [] on map for lookup: map[key] inserts a default value if the key doesn't exist. Use find() or count() to check first.
⚠️ Assuming list is fast: list has poor cache locality — even O(1) operations can be slower than vector's O(n) due to cache misses.
⚠️ Not reserving vectors: Without reserve(), frequent push_back causes repeated reallocations and copies.
Pro Tips
💡 Default to vector: vector is almost always the best container due to contiguous memory and cache friendliness. Only switch when you have a specific need.
💡 Use emplace: emplace_back, emplace, and try_emplace construct objects in-place, avoiding copies.
💡 Structured bindings: Use for (auto& [key, val] : map) for cleaner iteration over maps (C++17).
📋 Quick Reference
| Operation | Syntax |
|---|---|
| Pre-allocate | vec.reserve(n); |
| Check map key | if (m.count(key)) |
| Structured binding | auto& [k, v] = *it; |
| Emplace | vec.emplace_back(args...); |
| Shrink | vec.shrink_to_fit(); |
Lesson Complete!
You now understand the internals and trade-offs of every major STL container. Next: Move Semantics Advanced — perfect forwarding, rvalue references, and copy elision.
Sign up for free to track which lessons you've completed and get learning reminders.